presentation.pdf

La mthode BCours donn lEcole des Jeunes Chercheurs en Programmation

Dinard - 21 mai 2010

Marie-Laure Potet Didier Bert

VERIMAG, Grenoble, France

Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.1/108

Plan du cours

1. Introduction aux mthodes formelles- Mthode B2. Formalisme de modlisation3. Spcification des oprations : substitutions4. Les machines abstraites5. Raffinement et implmentation6. Modularit : raffinement et composition7. Applications industrielles


Particularits du logicielproduit intellectuel

cot de fabrication nulconception complexe

logiciel pour la scuritpas dusureduplication cot nulfonctionnalits complexesrapidit, ractivit

cot Validation/Vrification lev


ContraintesFiabilit (transport ferroviaire) :

Systme : 109 pannes par rame/heureLogiciel : 1011 pannes par rame/heure

non vrifiable par exprimentation

Cot du dveloppement (arospaciale) :3 les fonctionnalits embarques60 leffort de production de code

matrise du processus


Systmes critiques

Intrt limit de la redondancedouble dveloppementdouble support matrielabsence de mode derreur commun

Pas de principe de scurit intrinsquepanne 6 tat dangereuxsystme discret

Vers des techniques formelles


Le ferroviaire et B

Logiciel pour les fonctions critiques de scurit (fin 80)1) dveloppement non redond avec validation laide demthodes formelles

correction du code vis-a-vis des spcificationsfontionnelles

2) utilisation de la technique du Processeur ScuritaireCod pour la dtection des pannes matrielles

codage des donnes et vrification lexcutionetat sr si non conformit lexcution


Le ferroviaire et B ... suite

1. vrification a posteriori :ajout dassertions dans le codevrification semi-automatique

2. lien avec la spcification :rexpression formelleconformit (manuelle) du code

Mthode B (J-R Abrial)dveloppement correct par construction

Mtor : B + PSC suppression des tests unitaires


Pourquoi tudier la mthode B ?

des notions communes toute approche formellespcification, vrification, preuve

processus de dveloppement en son entierraffinement, gnration automatique de code prouv

outil et mthode permettant le passage lchellecomposition des spcifications et desdveloppements, vrification incrmentale

applications industrielles et processus mtierAtelierB, Rodin, Leirios test Generator, Bart . . .


SpcificationUne machine abstraite :

un tatune initialisationdes oprationsdes proprits invariantes

Donnes ensemblesinitialisationoprations substitutions gnralisesproprits prdicats du premier ordre


VrificationObligations de preuve :

Les proprits invariantes sont vrifies par ladynamique

Les raffinements prservent la correction totale

Le code est exempt derreur lexcution


Latelier B (ClearSy)AnalyseurGnrateur dobligations de preuveDmonstrateur automatiqueDmonstrateur interactifGnrateur de code (C et Ada)Gestionnaire de projets

AtelierB 4.0 (Windows, Linux, Mac OS, Solaris) :http://www.atelierb.eu/php/telecharger-atelier-b-fr.php


Partie 2 : Modlisation

1. Introduction la mthode B2. Formalisme de modlisation3. Spcification des oprations : substitutions4. Les machines abstraites5. Raffinement et implmentation6. Modularit : raffinement et composition7. Applications industrielles


Formalisme logique :PrdicatsLogique du premier ordre :P Q, P Q, Px P quantification[x := E]P substitution dans un prdicat

Prdicats de base :x S appartenanceE1 = E2 galit

Les autres constructeurs sont drivs :P Q, x P , x 6 S, etc.


Modlisation : Expressions et EnsemblesLes ensembles (typs) :S1 S2 produitP(S) ensemble des parties{ x | P} ensemble en comprhensionBIG un ensemble infini

Les expressions :x variable[x := E1]E2 substitution dans une expression(E1, E2) paire dexpressionschoice(S) fonction de choixS ensemble


Quelques notationsLa substitution :

[x := E]Ples occurrences libres de x sont remplaces par E dans P .

Autre notation :x\P

qui signifie : x nest pas libre dans P .


Axiomes de base

Axiome

SET1 (E,F ) s t E s F tSET2 s P(t) x (x s x t)SET3 E {x | x s P} (E s [x := E]P )SET4 x (x s x t) s = tSET5 x (x s) choice(s) sSET6 infinite(BIG)


Constructions drivesLes autres oprateurs et notations sur les ensembles sont drivs du jeude base donn.Les proprits usuelles sur ces oprateurs peuvent tre dmontres partir des axiomes. Exemples :

s t s P(t)s t {a | a u (a s a t)} s u t us t {a | a u (a s a t)} s u t us t {a | a u (a s a 6 t)} s u t u{E} {a | a u a = E} E u{E,F} {E} {F} E u F u BIG BIG


Construction des relationsRelation entre deux ensembles s t = P(s t)


Construction des relationsRelation entre deux ensembles s t = P(s t)Oprateurs classiques sur les relations :

Condition Expression Dfinition

r s t dom(r) {x | x s y (y t (x, y) r)}

r s t ran(r) {y | y t x (x s (x, y) r)}

r s t r[u] {y | y t u s x (x u (x, y) r)}r s t r1 {(y, x) | (y, x) t s (x, y) r}


Autres oprateurs sur les relations

Condition Expr Dfinition

id(s) {x, y | (x, y) s s x = y}

r1 s t r1 ; r2 {x, z | (x, z) s u r2 t u y (y t (x, y) r1 (y, z) r2)}

r s t r q {x, y | (x, y) s t q s t (((x, y) r x 6 dom(q))

(x, y) q)}


Construction des fonctionsLes fonctions sont un cas particulier de relations :

Signification Notation Dfinition

f. partielles sp t {r | r s t x, y, z (x, y r x, z r

y = z)}f. totales s t {f | f sp t dom(f) = s}injectives part. sp t {f | f sp t f1 tp s}injectives tot. s t sp t s tevaluation f(E) choice(f [{E}])

si f sp t E dom(f)


Construction des ensembles inductifsComment dfinir les ensembles tels que :

les entiers naturels N

les parties finies dun ensemble F(s)

la fermeture rflexive transitive dune relation r

. . . tout en restant dans la thorie de base B. . .


Dfinition par inductionOn dispose dun schma dinduction pour caractriser un sous-ensembleE de s :

un lment de base a Eune rgle x E f(x) Eune clause de fermeture : E est le plus petit sous-ensemble de sfiniment engendr par la rgle partir de la base.


Dfinition par inductionOn dispose dun schma dinduction pour caractriser un sous-ensembleE de s :

un lment de base a Eune rgle x E f(x) Eune clause de fermeture : E est le plus petit sous-ensemble de sfiniment engendr par la rgle partir de la base.

Soit g tel que g : e 7 {a} f [e]La fonction g est monotone :

e1 e2 g(e1) g(e2)


Plus petit point fixeDaprs le thorme de Tarski :

Si g est monotone, la plus petite solution de X = g(X) est le plus petitpoint fixe de g, qui est dfini par :

fix(g) ={e | e P(s) g(e) e}





Avec E = fix(g), E satisfait les axiomes :

g[E] E S (S P(s) g[S] S E S)





Avec E = fix(g), E satisfait les axiomes :

g[E] E S (S P(s) g[S] S E S)

Schma dinduction : x (x E P (x))g[{x | x E P (x)}] {x | x E P (x)} E {x | x E P (x)}{a} f [{x | x E P (x)}] {x | x E P (x)} . . .{a} {f(x) | x E P (x)} {x | x E P (x)} . . .P (a) x (x E P (x) P (f(x))) x (x E P (x))


Exemple : dfinition de r

On a une relation r s s

r est rflexive id(s) relle contient r r ret est ferme par composition v r (r ; v) r

La fonction g de gnration de r est :

g : e 7 id(s) (r ; e)


Exemple : dfinition de NOn doit avoir (axiomes de Peano):

1- 0 N2- n N succ(n) N3- 0 6= succ(n)4- succ(n) = succ(m) n = m5- [n := 0]P n (n N P [n := succ(n)]P )

n (n N P )


Exemple : dfinition de NOn doit avoir (axiomes de Peano):

1- 0 N2- n N succ(n) N3- 0 6= succ(n)4- succ(n) = succ(m) n = m5- [n := 0]P n (n N P [n := succ(n)]P )

n (n N P )

Codage des oprateurs :0 = succ = n (n F(BIG) | n {choice(BIG n)})

La fonction g de gnration de N est :g : e 7 {} succ[e]

Et on a N = fix(g)


Les ensembles offerts par le langage

Notations densembles prdfinis en B avec, pour chacun, un jeudoprateurs usuels. Ce sont :

les ensembles donns : ce sont des ensembles finis, non vides

les ensembles finis numrs

les entiers relatifs Z (avec les sous-ensembles N et N1)les entiers relatifs borns INT (avec le sous-ensemble NAT )les squences de s (fonctions de 1..n s)les arbres n-aires (avec le sous-ensemble des arbres binaires)

INT = 2147483647..214748364 (modifiable)


Exercice de modlisationSoit un ensemble personne PERSONNE :

R1 : toute personne est soit un homme, soit une femme

R2 : une personne ne peut tre la fois un homme et une femme

R3 : seules les femmes peuvent avoir un mari qui est un homme

R4 : les femmes ont au plus un mari

R5 : les hommes ne peuvent tre maris qu au plus une femme

R6 : les mres dune personne sont des femmes maries


SolutionR1 : toute personne est soit un homme, soit une femme








homme personnefemme personnehomme femme = personne









R2 : une personne ne peut tre la fois un homme et une femmehomme femme =









R3 : seules les femmes peuvent avoir un mari qui est un hommemari femme homme









R4 : les femmes ont au plus un marimari femmep homme









R5 : les hommes ne peuvent tre maris qu au plus une femmemari1 hommep femmemari femmep homme








R5 : les hommes ne peuvent tre maris qu au plus une femmemari1 hommep femmemari femmep homme

R6 : les mres dune personne sont des femmes mariesmere personnep dom(mari)


Exercice de modlisation (suite)A laide des dfinitions prcdentes, dfinir les notions de :

R7 : pre

R8 : parent

R9 : enfant

R10 : grand-parent et anctre

R11 : frre-sur

R12 : Dmontrer mere = pere ; mari1


Solution des exercices (suite)R7 : pre

R8 : parent

R9 : enfant


R11 : frre-sur




pere = mere ; mari

R8 : parent

R9 : enfant


R11 : frre-sur




pere = mere ; mari

R8 : parentparent = mere pere

R9 : enfant


R11 : frre-sur




pere = mere ; mari


R9 : enfantenfant = parent1


R11 : frre-sur




pere = mere ; mari



R10 : grand-parent et anctregrand_parent = parent ; parentancetre = parent ; parent

R11 : frre-sur




pere = mere ; mari




R11 : frre-surfrere_soeur = (mere ; mere1) id(personne)




pere = mere ; mari




R11 : frre-surfrere_soeur = (mere ; mere1) id(personne)


= (mere ; mari) ; mari1 = mere ; (mari ; mari1)

= mere ; id(dom(mari)) = mereEcole des Jeunes Chercheurs en Programmation - mai 2010 p.30/108

Partie 3 : Les substitutions gnralises



Substitutions primitives

x := E substitution simple

x, y := E,F substitution multiple simple

skip substitution sans effet

P | S substitution prconditionneP = S substitution gardeS [] T substitution de choix born

@z S substitution de choix non bornS ; T squencement de substitutions

W(P, S, J, V ) substitution ditration


Spcification des instructionsLogique des programmes : correction partielle

P{S}QSi ltat satisfait P avant S et si S termine,

alors ltat satisfait Q aprs.





Plus faible prcondition : correction totalewp(S,Q)

Si ltat satisfait wp(S,Q) avant Salors S termine et ltat satisfait Q aprs.

Remarque : P{S}Q en correction totale est quivalent P wp(S,Q)





Plus faible prcondition : correction totalewp(S,Q)

Si ltat satisfait wp(S,Q) avant Salors S termine et ltat satisfait Q aprs.

Remarque : P{S}Q en correction totale est quivalent P wp(S,Q)

En B, la plus faible prcondition wp(S,Q) est note sous la formedune substitution [S]Q


WP des substitutions primitives

Cas de substitution Rduction Condition

[x := E]R [x := E]R

[x, y := E,F ]R [z := F ][x := E][y := z]R z\E,F,R[skip]R R

[P | S]R P [S]R[P = S]R P [S]R[S [] T ]R [S]R [T ]R[@z S]R z [S]R z\R[S ; T ]R [S] ([T ]R)


La notationDans les programmes B, les substitutions scrivent avec des motsrservs :

Substitution Notation

P | S PRE P THEN S END

P = S SELECT P THEN S END

S [] T CHOICE S OR T END

@z S VAR z IN S END

W(P, S, J, V ) WHILE P DO S INVARIANT J VARIANT V END


La notation (suite)

x := E || y := F x, y := E,F

BEGIN S END (S)

IF P THEN S ELSE T END (P = S) [] ( P = T )CHOICE S OR T . . . OR U END S [] T [] [] U

ANY z WHERE P THEN S END @z (P = S)

x : E ANY x WHERE x E THEN x := x END

x := bool((P ) x := IF P THEN TRUE ELSE FALSE END

f(x) := E f := f {(x,E)}


Exemples de calcul

[x := z + 1; y := x+ z](y 0..5) = [x := z + 1]([y := x+ z](y 0..5))= [x := z + 1](x+ z 0..5) = (z + 1 + z 0..5)


Exemples de calcul


[ IF P THEN S ELSE T END]R= [(P = S) [] ( P = T )]R= [P = S]R [ P = T ]R= (P [S]R) ( P [T ]R)


Exemples de calcul


[ IF P THEN S ELSE T END]R= [(P = S) [] ( P = T )]R= [P = S]R [ P = T ]R= (P [S]R) ( P [T ]R)

[x : E]R= [ ANY x WHERE x E THEN x := x END]R= x (x E [x := x]R)


Un exemple de modlisationProblme :On veut spcifier une opration qui alloue un mot dans une mmoire etretourne ladresse de lemplacement allou, sil y a de la place enmmoire.

Quelques prliminaires de modlisation :

ADRESSES ensemble abstrait dadressesmemoire ADRESSES les adresses de la mmoire allouerlibres memoire lensemble des adresses libresnull ADRESSES une adresse particulirenull 6 memoire ladresse null nest pas en mmoire


Solution 1

Cas 1 : Lopration allouer ne peut agir que sil reste des adresses libres.Premire modlisation : une prcondition assure quil reste de la place.

r allouer = entte de loprationPRE libres 6= THEN prcondition

ANY v WHERE

v libres choix dune adresse libreTHEN

libres := libres {v} || modification de ltatr := v retour de ladresse alloue

END

END


Solution 1 (suite)

Cas 1 : Dans la mthode B, lorsquon appelle une opration, il y a uneobligation de preuve qui permet dassurer que la prcondition est vrifie lappel.

Dun point de mthode de spcification, il faut, dans ce cas, fournir lutilisateur des oprations pour tester de lextrieur si une prconditionest vrifie. On aura ici :

b n_est_pas_pleine = b := bool(libres 6= )


Solution 2Cas 2 : Autre manire de spcifier : lutilisateur na pas tester laprcondition. Si ladresse de retour est null, cela signifie lutilisateur quela mmoire est pleine et que lallocation na pas t possible

r allouer = entte de loprationIF libres 6= THEN test dynamique

ANY v WHERE

v libres choix dune adresse libreTHEN


END

ELSE il ny a plus dadresse librer := null retour de la valeur de non allocation

END


Solution 3Cas 3 : On pourrait simplement spcifier avec les deux cas possibles deretour de valeur de r :

r allouer = entte de loprationCHOICE choix interne

ANY v WHERE

v libresTHEN


END

OR autre possibilitr := null retour de la valeur de non allocation

END

Comparez cette solution avec la prcdente. Que peut-on dire ?


Caractrisation des substitutionsLe langage des substitutions gnralises est conu pour dcrire deschangement dtats.

Il y a une grande varit de substitutions.

Que peut-on dire de commun toutes les substitutions ?

Peut-on reprsenter les substitutions par leffet quelle produisentcomme une relation entre les tats ?


Terminaison dune substitution

La terminaison est un prdicat trm(S) qui caractrise la terminaison de lasubstitution S. Dfinition :

trm(S) = [S] true

Quelques rsultats :

trm(x := E) truetrm(skip) truetrm(P | S) P trm(S)trm(P = S) P trm(S)trm(S [] T ) trm(S) trm(T )trm(@z S) z trm(S)


Prdicat avant-aprsLe prdicat avant-aprs prdx(S) donne la relation entre les valeurs avantet aprs la substitution S pour les variables x. Dfinition :

prdx(S) = [S] (x 6= x) (et fis(S) x prdx(S))

prdx(x := E) x = Eprdx,y(x := E) x, y = E, yprdx(skip) x = xprdx(P | S) P prdx(S)prdx(P = S) P prdx(S)prdx(S [] T ) prdx(S) prdx(T )prdx(@z S) z prdx(S) si z\xprdx(@y T ) (y, y) prdx,y(T ) si y\x


Forme normaliseToute substitution peut se mettre sous la forme :

S = trm(S) | @x (prdx(S) = x := x)

Deux substitutions sont gales si elles ont le mme effet sur tout prdicat :S = T = [S]R [T ]R pour tout prdicat R

Les substitutions gnralises satisfont les proprits :

[S] (R Q) [S]R [S]Q Distributivitx (R Q) ([S]R [S]Q) Monotonie

On particulier on a (terminaison) : (R true) ([S]R trm(S))


Substitutions gnralises vs prdicatsOn a vu que lon peut passer des substitutions gnralisesaux prdicats avant-aprs et terminaison et vice-versa.Pourquoi choisir les SG pour spcifier, plutt que lesprdicats comme en Z, OCL, JML,. . . ?

le style dcriture est plus proche de la programmationpar dfaut, les variables ne sont pas modifies (y = y)lutilisation des substitutions est plus efficace pour lespreuves :

[x := 1 ; x := x+ 1] (x > 0) > 2 > 0avec les prdicats : x2 (x2 = 1 x = x2 + 1) x > 0Il y a un continuum entre les spcifications et lesprogrammes laide du raffinement.


Extension : langage avec exceptions

On tend le langage B avec une notion dexceptions EXC . Valeurprdfinie : no EXC (non utilisable dans le langage)Nouvelles constructions :

RAISE e dclenchement dune exception eBEGIN bloc avec rcupration

S le corps du blocCATCH

WHEN e1 THEN S1 squence de traitement des exceptions. . .

WHEN en THEN SnEND

Extension du calcul de plus faible prcondition : wpe(S, F )

avec : F EXC p PostConditionEcole des Jeunes Chercheurs en Programmation - mai 2010 p.48/108

Axiomatisation de wpe

wpe(skip, F ) = F (no)

wpe(x := v, F ) = [x := v]F (no)

wpe(raise e, F ) = F (e)

wpe(S1 [] S2, F ) = wpe(S1, F ) wpe(S2, F )

wpe(S1 ; S2, F ) = wpe(S1, F {no 7 wpe(S2, F )})

wpe(BEGIN

S = wpe(S,CATCH F {e1 7 wpe(S1, F ),

WHEN e1 THEN S1 . . .. . . en 7 wpe(Sn, F )}WHEN en THEN Sn )

END, F )


Exemple de calculBEGIN

x := 1

; IF y > 0 THEN RAISE stop

END

; x := 2

END

{no 7 x = 2, stop 7 x = 1}



x := 1


END

; x := 2{no 7 x = 2, stop 7 x = 1}

END

{no 7 x = 2, stop 7 x = 1}



x := 1


END

{no 7 true, stop 7 x = 1}; x := 2

{no 7 x = 2, stop 7 x = 1}END

{no 7 x = 2, stop 7 x = 1}



x := 1

; IF y > 0 THEN RAISE stopELSE skip

END

{no 7 true, stop 7 x = 1}; x := 2

{no 7 x = 2, stop 7 x = 1}END

{no 7 x = 2, stop 7 x = 1}



x := 1

; IF y > 0 THEN x = 1 RAISE stopELSE true skip

END

{no 7 true, stop 7 x = 1}; x := 2

{no 7 x = 2, stop 7 x = 1}END

{no 7 x = 2, stop 7 x = 1}



x := 1{no 7 (y > 0 x = 1) ((y > 0) true),stop 7 x = 1}


END

{no 7 true, stop 7 x = 1}; x := 2

{no 7 x = 2, stop 7 x = 1}END

{no 7 x = 2, stop 7 x = 1}



(y > 0 true) ((y > 0) true)x := 1

{no 7 (y > 0 x = 1) ((y > 0) true),stop 7 x = 1}


END

{no 7 true, stop 7 x = 1}; x := 2

{no 7 x = 2, stop 7 x = 1}END

{no 7 x = 2, stop 7 x = 1}



true

x := 1{no 7 (y > 0 x = 1) ((y > 0) true),stop 7 x = 1}


END

{no 7 true, stop 7 x = 1}; x := 2

{no 7 x = 2, stop 7 x = 1}END

{no 7 x = 2, stop 7 x = 1}


Justification de la smantiqueEquivalence de smantique entre un programme avec exceptions et unprogramme sans exception : ajout dune variable exc qui simulelexception courante .

Dfinition de C(S) :

C(x := v) = x := v ; exc := noC(skip) = exc := noC(RAISE e) = exc := eC(S1 ; S2) = C(S1) ; IF exc = no THEN C(S2) END. . .

Quelle postcondition R pour que wp(S, F ) wpe(C(S), R) ?


Justification de la smantiqueEquivalence de smantique entre un programme avec exceptions et unprogramme sans exception : ajout dune variable exc qui simulelexception courante .

Dfinition de C(S) :

C(x := v) = x := v ; exc := noC(skip) = exc := noC(RAISE e) = exc := eC(S1 ; S2) = C(S1) ; IF exc = no THEN C(S2) END. . .

Quelle postcondition R pour que wp(S, F ) wpe(C(S), R) ?

wpe(S, F ) [C(S)] (eidom(F )(exc = ei F (ei)))Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.51/108

Exemple de preuve

wpe(S, F ) [C(S)] (eidom(F )(exc = ei F (ei))) ?Affectation (wpe(x := v, F ) = F (no)) :


Exemple de preuve

wpe(S, F ) [C(S)] (eidom(F )(exc = ei F (ei))) ?Affectation (wpe(x := v, F ) = F (no)) :[x := v ; exc := no]

eidom(F )(exc = ei F (ei))

= [x := v][exc := no]eidom(F )(exc = ei F (ei))

= [x := v]eidom(F )(no = ei F (ei))

= [x := v]F (no) eidom(F ){no}(no = ei F (ei))= [x := v]F (no)


Exemple de preuve (2)wpe(S, F ) [C(S)] (eidom(F )(exc = ei F (ei))) ?

Squencement (wpe(S1, F {no 7 wpe(S2, F )})) :



Squencement (wpe(S1, F {no 7 wpe(S2, F )})) :[C(S1) ; IF exc = no THEN C(S2) END]eidom(F )(exc = ei F (ei))= [C(S1)][IF exc = no THEN C(S2) END]eidom(F )(exc = ei F (ei))= [C(S1)] (exc = no ([C(S2)]eidom(F )(exc = ei F (ei))))

(exc 6= no eidom(F )(exc = ei F (ei)))



Squencement (wpe(S1, F {no 7 wpe(S2, F )})) :[C(S1) ; IF exc = no THEN C(S2) END]eidom(F )(exc = ei F (ei))= [C(S1)][IF exc = no THEN C(S2) END]eidom(F )(exc = ei F (ei))= [C(S1)] (exc = no ([C(S2)]eidom(F )(exc = ei F (ei))))

(exc 6= no eidom(F )(exc = ei F (ei)))= [C(S1)](exc = no wpe(S2, F ))

eidom(F ){no}(exc = ei F (ei))= [C(S1)]eidom(F )(exc = ei F {no 7 wpe(S2, F )}(ei))= wpe(S1, F {no 7 wpe(S2, F )})


Partie 4 : Les machines abstraites

1. Introduction la mthode B2. Formalisme de modlisation3. Spcification des oprations : substitutions4. Composants B : les machines abstraites5. Raffinement et implmentation6. Modularit : raffinement et composition7. Applications industrielles


Composant machine

MACHINE

Partie entte :nom de la machine

Partie statique :dclaration densembles et de constantesproprits des constantesvariables (tat)invariant (caractrisation de ltat)

Partie dynamique :initialisation de ltatoprations

END


Rubriques dune machine

MACHINE M

SETS S; /* ensembles donns */T = {a, b} /* ensembles numrs */

CONSTANTS c /* liste de constantes (concrtes) */PROPERTIES C /* spcification des constantes */VARIABLES x /* liste de variables (abstraites) */INVARIANT I /* spcification des variables */INITIALISATION U /* substitution dinitialisation */OPERATIONS /* liste des oprations */

r nom_op(p) = PRE P THEN K END; . . .END


Obligations de preuves dune machineLinitialisation tablit linvariant :B : ensembles dclars sont finis et non vides et les constantesnumres sont distinctes.

B C [U ]I

Chaque opration prserve linvariant :

B C I P [K]I

Par la proprit de terminaison, on assure que K termine :B C I P trm(K)

Atelier B : production des obligations de preuve (initialisation et unensemble dOPs par opration), preuve automatique ou interactive.


Exemple de lascenseur

exprimer des propritspar des spcificationspar des invariants

utiliser la preuve pour dtecter des problmesincohrence entre invariant et comportementinvariant non inductif

exemple dutilisation de latelier B


AscenseurOn souhaite spcifier le fonctionnement simplifi dun ascenseur.

une porte chaque tagelappel intrieur et lappel extrieur ne sont pas distingusil ny a pas de panneune constante donne le nombre dtages : max_etage (> 0)

Les oprations sont :

ouvrir, fermer une porteappeler lascenseurdplacement de lascenseur


Proprits de lascenseur

lascenseur reste dans la limite des tages

si une porte est ouverte lascenseur est arrt ltagecorrespondant

chaque appel est trait en un temps raisonnable

si lascenseur est arrt un tage, lappel cet tage est considrcomme trait

. . .


Modlisation de lascenseur

MACHINE ASCENSEUR

SETS MODE = {arret,mouv}CONSTANTS max_etage, ETAGES

PROPERTIES max_etage NAT1 ETAGES = 0..max_etageVARIABLES appels, ouvertes, pos,mode

INVARIANT

ouvertes ETAGES appels ETAGES pos ETAGES mode MODE


Modlisation de lascenseur

MACHINE ASCENSEUR

SETS MODE = {arret,mouv}CONSTANTS max_etage, ETAGES

PROPERTIES max_etage NAT1 ETAGES = 0..max_etageVARIABLES appels, ouvertes, pos,mode

INVARIANT

ouvertes ETAGES appels ETAGES pos ETAGES mode MODE (ouvertes 6= ouvertes = {pos} mode = arret) (mode = arret pos 6 appels)


Plan de la dmo

spcification des invariantsspcification des oprationsobligations de preuve (appeler, fermer)preuveerreur de spcification (ASCENSEUR_FAUX)dtection des erreurs partir des obligations de preuve


Opration : dclaration et appelUne dclaration dopration est de la forme :

r op(p) = PRE P THEN K ENDavec r affect dans S (plus formellement r\prdx,r(S))

Un appel dopration se prsente sous la forme v op(e) avec :e un n-uplet dexpressionsv un n-uplet de variables ne contient pas de doublon ;les variables v sont disjointes des variables de la machine danslaquelle lopration est dfinie

utilisation encapsule des machines.


Opration : dclaration et appelUne dclaration dopration est de la forme :

r op(p) = PRE P THEN K ENDavec r affect dans S (plus formellement r\prdx,r(S))

Un appel dopration se prsente sous la forme v op(e) avec :e un n-uplet dexpressionsv un n-uplet de variables ne contient pas de doublon ;les variables v sont disjointes des variables de la machine danslaquelle lopration est dfinie

utilisation encapsule des machines.On veut montrer que si la prservation de linvariant esttablie sur la dfinition alors il est prserv par les appels.


Smantique par copieSoit r op(p) = PRE P THEN S END la dfinition duneopration de nom op et soit lappel v op(e). Sa dfinitionest :

PRE ([p := e]P )

THEN VAR p, r IN p := e ; S; v := r END

END

et on a :r, p (I P [S]I)

(I [p := e]P [VAR p, r IN p := e ; S; v := r END]I)


PreuveOn dduit de p, r (I P [S]I) :

r (I [p := e]P [p := e][S]I) (1)par instanciation de p par e et p non libre dans I.

De plus [var p, r in p := e ; S; v := r end]I devient, par dfinition ducalcul de plus faible prcondition :

p, r [p := e][S][v := r]I (2)qui se rduit, puisque v est non libre dans I, p, r [p := e][S]I.

Or p napparait pas dans [p := e][S]I puisque p napparat pas dans e.Donc I [p := e]P (2) se dduit de p, r (I P [S]I).


Smantique par rfrence

Lappel par rfrence (le remplacement) ne permet pas deprserver les proprits.

Soit par exemple lopration suivante :op(y)=

PRE pair(y)

THEN x := x+ 1;x := x+ y + 1

END

Cette opration prserve linvariant pair(x). Par contrelappel op(x) devient x := x+ 1;x := x+ x+ 1 qui neprserve pas linvariant.


Partie 5 : Raffinement

1. Introduction la mthode B2. Formalisme de modlisation3. Spcification des oprations : substitutions4. Les machines abstraites5. RAFFINEMENT6. Modularit : raffinement et composition7. Applications industrielles


Raffinement : principe

Le raffinement est le fait de transformer une spcification abstraite enun texte plus proche de la programmation, pour finalement obtenir unprogramme

Leffet des appels doprations de la machine abstraite doit treprserv, vu de lutilisateur

Le raffinement de machine se fait opration par opration

Il y a (ventuellement) raffinement de ltatPour chaque opration :

reformulation en fonction du changement dtataffaiblissement des prconditionsrduction du non-dterminisme


Exemple : une machine

MACHINE RAFF_EX1VARIABLES yy

INVARIANT yy NAT1INITIALISATION yy := OPERATIONS

ajouter(nn) = PRE nn NAT1THEN yy := yy {nn}END;

vv choix = PRE yy 6= THEN vv : yyEND

END


Un raffinementUne machine qui fait presque la mme chose :

MACHINE RAFF_EX2VARIABLES zz

INVARIANT zz NATINITIALISATION zz := 0OPERATIONS

ajouter(nn) = PRE nn NAT1THEN zz := nnEND;

vv choix = vv := zzEND


Un raffinementUne machine qui fait presque la mme chose :

MACHINE RAFF_EX2VARIABLES zz

INVARIANT zz NATINITIALISATION zz := 0OPERATIONS

ajouter(nn) = PRE nn NAT1THEN zz := nnEND;

vv choix = vv := zzEND

Relation de simulation : zz yy yy = Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.70/108

Raffinement de substitutionSans changement de reprsentation :

Dfinition du raffinement de S par T :

S T R ([S]R [T ]R)

Si S prserve linvariant, alors le raffinement le prserve.


Raffinement de substitutionSans changement de reprsentation :

Dfinition du raffinement de S par T :

S T R ([S]R [T ]R)

Si S prserve linvariant, alors le raffinement le prserve.

Autre dfinition :

trm(S) trm(T )S T

trm(S) prdx(T ) prdx(S)


Avec changement de reprsentationDfinition :

L trm(S) trm(T )S L T

L prdy(T ) x (prdx(S) [x, y := x, y]L)

Commutation de diagramme :

S

TY

XX

Y

L L


Obligations de preuveDfinition de S L T :

L trm(S) trm(T )L prdy(T ) x (prdx(S) [x, y := x, y]L)




Formulation utilise pour la preuve :

L trm(S) [T ][S]L




Formulation utilise pour la preuve :

L trm(S) [T ][S]L

Exemple : x : e ze x := zz e [x1 := z] v (v e [x2 := v](x1 = x2))z e [x1 := z] v (v e (x1 = v))z e v (v e z = v)


Equivalence des deux formulations

L trm(S) [T ][S]L

forme normale de T : trm(T ) | @y (prdy(T ) = y := y)(a) L trm(S) trm(T )(b) L trm(S) prdy(T ) [y := y]([S]L)

forme normale de S : trm(S) | @y (prdx(S) = x := x)[S]L (trm(S) x (prdx(S) [x := x]L))

(b) L trm(S) prdy(T ) x (prdx(S) [x, y := x, y]L)

on peut montrer :L trm(S) x (prdx(S) [x, y := x, y]L)

Do le rsultat.


Raffinement de machines : Syntaxe

MACHINE MVARIABLES xINVARIANT IINITIALISATION UOPERATIONSr nom_op(w) =

PRE P THEN K ENDEND

REFINEMENT N REFINES MVARIABLES yINVARIANT JINITIALISATION VOPERATIONSr nom_op(w) =

PRE Q THEN L ENDEND


Raffinement de machines : Syntaxe

MACHINE MVARIABLES xINVARIANT IINITIALISATION UOPERATIONSr nom_op(w) =

PRE P THEN K ENDEND

REFINEMENT N REFINES MVARIABLES yINVARIANT JINITIALISATION VOPERATIONSr nom_op(w) =

PRE Q THEN L ENDEND

Pour chaque opration InitialisationI J P Q [V ] [U ] JI J P [L] [K] JI J P [[r := r]L] [K] (J r = r)


Raffinement : un exemple (1)MACHINE ATTENTE

VARIABLES attente, nb_elem

INVARIANT attente INT nb_elem NAT nb_elem = card(attente)INITIALISATION nb_elem := 0 || attente := OPERATIONS

nb nb_elem= BEGIN nb := nb_elem END ;

ajouter(v)= PRE v INT v 6 attente nb_elem < MAXINTTHEN attente := attente {v} || nb_elem := nb_elem+ 1 END ;

v traiter= PRE attente 6= THENANY val WHERE val INT val attenteTHEN v := val || attente := attente val|| nb_elem := nb_elem 1 END

END

END


Raffinement : un exemple (2)REFINEMENT ATTENTE_R1REFINES ATTENTE

VARIABLES file, b1, b2

INVARIANT file : NAT p INT b1 NAT b2 NAT . . .

INITIALISATION b1 := 1 || b2 := 1 || file := OPERATIONS

nb nb_elem= BEGIN nb := b2 b1 END ;ajouter(v)= BEGIN file(b2) := v || b2 := b2 + 1 END ;v traiter= BEGIN v := file(b1) || b1 := b1 + 1 END

END


Raffinement : un exemple (2)REFINEMENT ATTENTE_R1REFINES ATTENTE

VARIABLES file, b1, b2

INVARIANT file : NAT p INT b1 NAT b2 NAT file[b1..b2 1] = attente b2 b1 = nb_elem

INITIALISATION b1 := 1 || b2 := 0 || file := OPERATIONS

nb nb_elem= BEGIN nb := b2 b1 + 1 END ;ajouter(v)= BEGIN file(b2 + 1) := v || b2 := b2 + 1 END ;v traiter= BEGIN v := file(b1) || b1 := b1 + 1 END

END


Partie 6 : rsultats gnraux et raffinement



Raffinement et SimulationSoit M un composant raffin par R. Une substitution U est dite externepour M et R si elle ne contient aucune rfrence directe aux variables vMou vR.

Le principe de substitution de M par R peut de dfinir par :

R offre les mmes oprations que M avec les mmes signaturesToute substitution externe U pour M et R est telle que :

Cette dfinition nest pas oprationnelle : on raisonne sur toutes lesutilisations possibles dune interface.

Simulation = le raffinement opration par opration (imposant donc un in-variant de reprsentation). Est-il correct ? Complet ?


Principe

Mthode effective :1. une relation dabstraction qui lie les valeurs abstraites

et les valeurs concrtes2. Une notion de commutativit du raffinement ()

A

CY

XX

Y

11

plusieurs faons de faire commuter le diagramme.


L et L1 simulationsA

CY

XX

Y

11

L-simulation (forward ou downward simulation) :1 ; C A ; 1

i.e : a, c (c ( C) a(A ))

L1-simulation (backward ou upward simulation) :C ; ; A

i.e : c, a (c (C ) a ( A))


CorrectionSil existe tel que :

initM initRS T pour chaque opration

alors pour chaque utilisation externe U pour M et R :@ vM . initM ; UM id @ vR . initR ; UR

correction des L et L1 simulations


CompltudePour chaque utilisation externe U pour M et R :

@ vM . initM ; UM id @ vR . initR ; URalors il existe tel que :

initM initRS T pour chaque opration

incompltude de chaque simulation compltude des deux simulations L et L1


Exemple

MACHINE CASINO1

VARIABLES i

INVARIANT i 0..36INITIALISATION i : 0..36OPERATIONS

r1 spin= r1 := i || i : 0..36END

MACHINE CASINO2

OPERATIONS

r2 spin= r2 : 0..36END

Mme interface produisant les mmes rsultats :

CASINO1 : @ i . init ; v1 spin ; . . . ; vn spinCASINO2 : v1 spin ; . . . ; vn spin


Exemple (2) casino2 L casino1 :

i 0..36 [r1 := i || i : 0..36][r2 : 0..36](r1 = r2)i 0..36 [r1 := i || i : 0..36]r2(r2 0..36 r1 = r2)i 0..36 [r1 := i || i : 0..36]r1 0..36i 0..36 i 0..36

casino1 6L casino2 :i 0..36 [r2 : 0..36][r1 := i || ii : 0..36](r1 = r2)i 0..36 r2(r2 0..36 i = r2)i 0..36 r2 0..36 i = r2false

S. Dunne, ZB 2003


Exemple (3) casino1 L1 casino2 :

r1(r2(r2 0..36 r1 = r2) i(i 0..36 r1 = i))r1(r1 0..36 i(i 0..36 r1 = i))r1(r1 0..36 r1 0..36)true

Rappel : c, a (c (C ) a ( A))


Autres simulationsA

CY

XX

Y

11

U -simulation : 1 ; C ; AU1-simulation : C ;A;1

U simulation correcte si est totale (idC ; 1)U1 simulation correcte si est fonctionnelle ( ; 1 idA) Si est une fonction totale alors quivalence de cesdiffrentes notions.


Proprits importantesLa transitivit (raffinements successifs)

S 1 T T 2 U S 1 ; 2 U

La monotonie (raffinement par partie)

S T (P | S) (P | T )

(U V ) (S T ) (U [] S) (V [] T )

S T (P = S) (P = T )

z (S T ) @z S @z T

(U V ) (S T ) (U ; S) (V ; T )


Monotonie de lappel dopration

Prservation des preuves de raffinement

dfinition abstraite : r op(p) = S1dfinition concrte : r op(p) = S2appel : v op(e) et e ne contient aucune occurrence des variablesde la machine (ni de son raffinement)

alors :

[r := r1]S1 Jr1=r2 [r := r2]S2

[v := v1][p, r := e, v]S1 Jv1=v2 [v := v2][p, r := e, v2]S2

Preuve base sur les formes normalises.


Partie 6 : Implmentation

1. Introduction la mthode B2. Formalisme de modlisation3. Spcification des oprations : substitutions4. Les machines abstraites5. RAFFINEMENT6. IMPLMENTATION7. Modularit : raffinement et composition8. Applications industrielles


Implmentation (1)Dernier raffinement dun dveloppementLangage de programmation squentielRestriction sur les substitutions

substitutions dterministes (:=, IF, CASE, skip, ;)plus de prconditionprdicats des conditions = calcul boolen

Ajout dinstructions de programmation :substitution VARsubstitution ditration

Un programme est un tmoin : la faisabilit ( x prd(x, x))est garantie par construction.


Implmentation (2)Restrictions de typage :

les ensembles de valeurs sont finis (ex: entiers borns NAT etINT)constantes et variables sont de type concret: entiers, numrs,ensembles donns, tableaux (fonctions totales domaine fini)

Les ensembles donns et les constantes sont valus.Obligations de preuve pour labsence derreur lexcution

x := e devient PRE e type(x) THEN x := e ENDordre dvaluation impos : x+ y + z dcoup en temp := x+ yet y + temp

le niveau B0 est translatable en un programme (C, Ada, . . . ) qui estcorrect vis--vis de la spcification initiale, termine et est sans erreur lexcution.


Plus faible prcondition de litrationEn correction totale, il faut assurer que la boucle se terminedans ltat de la postcondition :

[ WHILE P DO SINVARIANT J

VARIANT V END ]R

J invariantx ((J P ) [S] J) prservation de linvariantx (J V N) variantx ((J P ) [n := V ][S](V < n)) dcroissance du variantx ((J P ) R) sortie de boucle


Programme de la division entire

MACHINE

DIVISIONOPERATIONS /* qq et rr sont le quotient et le reste */

qq, rr divi(aa, bb) = /* de la division entire de aa par bb */PRE

aa NAT bb NAT1THEN

ANY ss, tt WHEREss NAT tt NAT aa = bb ss+ tt tt < bb

THENqq, rr := ss, tt

ENDEND

END


Implmentation de la division entire

IMPLEMENTATION DIVISION_I REFINES DIVISIONOPERATIONS

qq, rr divi(aa, bb) =VAR ss, tt IN /* variables locales auxiliaires */

ss := 0 ; /* initialisations */tt := aa ;WHILE tt bb DO

ss := ss+ 1 ; /* corps de la boucle */tt := tt bb

INVARIANT /* conditions invariantes */. . .

VARIANT /* valeur entire qui dcrot */. . .

END ;qq := ss ; rr := tt /* retour du rsultat */

ENDEND


Solution ... tester !

qq, rr divi(aa, bb) =VAR ss, tt IN

ss := 0 ; /* initialisations */tt := aa ;WHILE tt bb DO

ss := ss+ 1 ;tt := tt bb

INVARIANTss NAT tt NAT aa = bb ss+ tt

VARIANTtt

END ;qq := ss ; rr := tt

END

Suffisant pour garantir labsence derreur lexcution ?Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.97/108

Un exemple plus compliquPrcondition : tab1{[FALSE]} 6= Postcondition : tab0(place) = FALSE tab = tab0 {place 7 TRUE}avec tab : 1..tailleMax BOOL

var ind inind:=1;while tab(ind)=TRUE do

ind:=ind+1end;tab(ind):=TRUE ;place:=ind

end

Quel variant ? Quel invariant ? Quelles conditions sur tailleMax ?la postcondition devient place = min(tab1{[FALSE]}). Quelinvariant ?


Mtor : ligne 14


Projet MtorLogiciel non scuritaire : 1 million de lignes Ada

Logiciel scuritaire : 86 000 lignes Ada (1 000composants)

115 000 lignes B27 800 obligations de preuve

81 % de preuve automatique92% aprs ajout de rgles (550)2 254 prouver interactivement


Mtor (2)Des spcifications sres (validation fonctionnelle)

modlisation dynamiquecarts rsultats attendus / rsultats obtenus

Des logiciels exempts derreurs (mthode B)guides mthodologiquesvrification des preuves et des rglestraabilit des proprits de scuritidentification des limites de la preuve

Une protection contre les erreurs lexcutionProcesseur Scuritaire Cod (PSC) : se garantir contre lesperburbations electromagntiquesredondance lexcution et vrification dynamique


Depuis Mtor chez SiemensTSAutomatisation de la preuve

base de rgles propresrgles valides

Raffinement automatiqueschmas de raffinement de donnesschmas de raffinement algorithmique

Rutilisationparamtrer les spcifications et les dveloppementsmthodologie outille de construction dapplications


Autre projet phare: Val de Roissy CDG

Calculateur l. ADA ns l. ADA s lignes B POPADS 30 632 186 440 256 653 62 056UCA 11 662 50 085 65 722 12 811


Projet Ouragan

Remise niveau du rseau de la RATP

Portes palires

Automatisation des rames

Dbut des travaux sur la ligne 1


Les projets ferroviaires B dans le monde


Autres approches

peu dautres approches globales bases sur leraffinementdes approches preuve de programmes annots (ESCJava, Spec#, Caduceus et Krakatoa) avecventuellement un langage plus abstrait pour lesassertions.des plate-formes de vrification de programmes faisantcollaborer diffrentes analyses (vrificationautomatique mais approche, preuve . . . ) Exemple : laplate-forme Frama-C.

Autres outils danalyse: bug checkers (pour la vrificationou la mise au point)


Des points de recherche

automatisation de lactivit de preuveprocdure de dcision, explication des preuves

analyse de programmes avec allocation dynamiqueanalyses dalias, classes de proprits

analyse compositionnellemodules et classes, programmes concurrents

analyse au niveau des excutablesretrouver les informations (data et control flow)


Et maintenant . . . A VOUS !Division euclidienne

trouver linvariant et le variantgarantir labsence derreur lexcution

Rechercheun exemple plus complexe dinvariant

Eclusemodliserdvelopper par raffinement

potet/ECJP-PageB (home page Vrimag)La preuve au premier ordre est indcidable ! Il faut essayer les diffrents prouveursautomatiques : pr le prouveur gnral, pp0 et pp1 des prouveurs combinatoires (i le niveaude profondeur dutilisation des hypothses).


Documents

presentation.pdf