presentation.pdf
DESCRIPTION
again and againTRANSCRIPT
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.2/108
Particularits du logicielproduit intellectuel
cot de fabrication nulconception complexe
logiciel pour la scuritpas dusureduplication cot nulfonctionnalits complexesrapidit, ractivit
cot Validation/Vrification lev
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.3/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.4/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.5/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.6/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.7/108
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 . . .
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.8/108
-
SpcificationUne machine abstraite :
un tatune initialisationdes oprationsdes proprits invariantes
Donnes ensemblesinitialisationoprations substitutions gnralisesproprits prdicats du premier ordre
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.9/108
VrificationObligations de preuve :
Les proprits invariantes sont vrifies par ladynamique
Les raffinements prservent la correction totale
Le code est exempt derreur lexcution
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.10/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.11/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.12/108
-
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.13/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.14/108
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 .
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.15/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.16/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.17/108
Construction des relationsRelation entre deux ensembles s t = P(s t)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.18/108
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}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.18/108
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)}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.19/108
-
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.20/108
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. . .
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.21/108
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.22/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.22/108
-
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}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.23/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.23/108
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)
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))
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.23/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.24/108
-
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 )
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.25/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.25/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.26/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.27/108
-
SolutionR1 : 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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.28/108
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 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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.28/108
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 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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.28/108
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 mari
R5 : les hommes ne peuvent tre maris qu au plus une femme
R6 : les mres dune personne sont des femmes maries
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.28/108
-
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 femme
R6 : les mres dune personne sont des femmes maries
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.28/108
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
R6 : les mres dune personne sont des femmes maries
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.28/108
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
R6 : les mres dune personne sont des femmes mariesmere personnep dom(mari)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.28/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.29/108
-
Solution des exercices (suite)R7 : pre
R8 : parent
R9 : enfant
R10 : grand-parent et anctre
R11 : frre-sur
R12 : Dmontrer mere = pere ; mari1
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.30/108
Solution des exercices (suite)R7 : pre
pere = mere ; mari
R8 : parent
R9 : enfant
R10 : grand-parent et anctre
R11 : frre-sur
R12 : Dmontrer mere = pere ; mari1
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.30/108
Solution des exercices (suite)R7 : pre
pere = mere ; mari
R8 : parentparent = mere pere
R9 : enfant
R10 : grand-parent et anctre
R11 : frre-sur
R12 : Dmontrer mere = pere ; mari1
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.30/108
Solution des exercices (suite)R7 : pre
pere = mere ; mari
R8 : parentparent = mere pere
R9 : enfantenfant = parent1
R10 : grand-parent et anctre
R11 : frre-sur
R12 : Dmontrer mere = pere ; mari1
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.30/108
-
Solution des exercices (suite)R7 : pre
pere = mere ; mari
R8 : parentparent = mere pere
R9 : enfantenfant = parent1
R10 : grand-parent et anctregrand_parent = parent ; parentancetre = parent ; parent
R11 : frre-sur
R12 : Dmontrer mere = pere ; mari1
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.30/108
Solution des exercices (suite)R7 : pre
pere = mere ; mari
R8 : parentparent = mere pere
R9 : enfantenfant = parent1
R10 : grand-parent et anctregrand_parent = parent ; parentancetre = parent ; parent
R11 : frre-surfrere_soeur = (mere ; mere1) id(personne)
R12 : Dmontrer mere = pere ; mari1
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.30/108
Solution des exercices (suite)R7 : pre
pere = mere ; mari
R8 : parentparent = mere pere
R9 : enfantenfant = parent1
R10 : grand-parent et anctregrand_parent = parent ; parentancetre = parent ; parent
R11 : frre-surfrere_soeur = (mere ; mere1) id(personne)
R12 : Dmontrer mere = pere ; mari1
= (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
1. Introduction la mthode B2. Formalisme de modlisation3. Spcification des oprations : substitutions4. Les machines abstraites5. Raffinement et implmentation6. Modularit : raffinement et composition7. Applications industrielles
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.31/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.32/108
Spcification des instructionsLogique des programmes : correction partielle
P{S}QSi ltat satisfait P avant S et si S termine,
alors ltat satisfait Q aprs.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.33/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.33/108
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)
En B, la plus faible prcondition wp(S,Q) est note sous la formedune substitution [S]Q
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.33/108
-
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.34/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.35/108
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)}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.36/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.37/108
-
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)
[ 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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.37/108
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)
[ 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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.37/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.38/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.39/108
-
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= )
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.40/108
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
libres := libres {v} || modification de ltatr := v retour de ladresse alloue
END
ELSE il ny a plus dadresse librer := null retour de la valeur de non allocation
END
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.41/108
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
libres := libres {v} || modification de ltatr := v retour de ladresse alloue
END
OR autre possibilitr := null retour de la valeur de non allocation
END
Comparez cette solution avec la prcdente. Que peut-on dire ?
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.42/108
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 ?
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.43/108
-
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.44/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.45/108
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))
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.46/108
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.47/108
-
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 )
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.49/108
Exemple de calculBEGIN
x := 1
; IF y > 0 THEN RAISE stop
END
; x := 2
END
{no 7 x = 2, stop 7 x = 1}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.50/108
Exemple de calculBEGIN
x := 1
; IF y > 0 THEN RAISE stop
END
; x := 2{no 7 x = 2, stop 7 x = 1}
END
{no 7 x = 2, stop 7 x = 1}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.50/108
-
Exemple de calculBEGIN
x := 1
; IF y > 0 THEN RAISE stop
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}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.50/108
Exemple de calculBEGIN
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}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.50/108
Exemple de calculBEGIN
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}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.50/108
Exemple de calculBEGIN
x := 1{no 7 (y > 0 x = 1) ((y > 0) true),stop 7 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}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.50/108
-
Exemple de calculBEGIN
(y > 0 true) ((y > 0) true)x := 1
{no 7 (y > 0 x = 1) ((y > 0) true),stop 7 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}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.50/108
Exemple de calculBEGIN
true
x := 1{no 7 (y > 0 x = 1) ((y > 0) true),stop 7 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}
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.50/108
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) ?
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.51/108
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)) :
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.52/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.52/108
Exemple de preuve (2)wpe(S, F ) [C(S)] (eidom(F )(exc = ei F (ei))) ?
Squencement (wpe(S1, F {no 7 wpe(S2, F )})) :
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.53/108
Exemple de preuve (2)wpe(S, F ) [C(S)] (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)))
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.53/108
-
Exemple de preuve (2)wpe(S, F ) [C(S)] (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 )})
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.53/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.54/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.55/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.56/108
-
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.57/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.58/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.59/108
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
. . .
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.60/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.61/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.61/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.62/108
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.63/108
-
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.63/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.64/108
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).
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.65/108
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.66/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.67/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.68/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.69/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.70/108
-
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.71/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.
Autre dfinition :
trm(S) trm(T )S T
trm(S) prdx(T ) prdx(S)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.71/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.72/108
-
Obligations de preuveDfinition de S L T :
L trm(S) trm(T )L prdy(T ) x (prdx(S) [x, y := x, y]L)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.73/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.73/108
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
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.73/108
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.74/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.75/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.75/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.76/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.77/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.78/108
Partie 6 : rsultats gnraux et raffinement
1. Introduction la mthode B2. Formalisme de modlisation3. Spcification des oprations : substitutions4. Les machines abstraites5. Raffinement et implmentation6. Modularit : raffinement et composition7. Applications industrielles
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.79/108
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 ?
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.80/108
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.81/108
-
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))
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.82/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.83/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.84/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.85/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.86/108
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))
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.87/108
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.88/108
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 )
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.89/108
-
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.90/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.91/108
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.92/108
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.
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.93/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.94/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.95/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.96/108
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 ?
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.98/108
Mtor : ligne 14
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.99/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.100/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.101/108
-
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.102/108
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
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.103/108
Projet Ouragan
Remise niveau du rseau de la RATP
Portes palires
Automatisation des rames
Dbut des travaux sur la ligne 1
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.104/108
Les projets ferroviaires B dans le monde
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.105/108
-
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.106/108
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)
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.107/108
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).
Ecole des Jeunes Chercheurs en Programmation - mai 2010 p.108/108