Upload
alvery-masse
View
104
Download
2
Embed Size (px)
Citation preview
Construction incrémentale 1
Construction Incrémentale de Spécifications de Systèmes Critiques intégrant des Procédures de
Vérification
Présenté par:Jury
Président:Rapporteurs:
Examinateurs:
Directeur de thèse:
Encadrants:
Hong-Viet Luong
ABC - UPSYves LE TRAON – IRISA – Telecom BretagneGuy LEDUC – RUN – Université de Liège Rolan GROZ – LIG - INPG
Christian PERCEBOIS – IRIT – UPS Anne-Lise COURBIS – LGI2P – EMA Thomas LAMBOLAIS – LGI2P – EMA
LGI2P
Construction incrémentale 2
Plan Introduction État de l’art
Raffinement des machines d’états UML Relations de raffinement et
d’implantation Contributions
Implantation des relations de conformité Transformation des machines d’états en
LTS Formalisation d’un cadre de construction
incrémentale Raffinement d’architecture
Conclusion
Construction incrémentale 3
Introduction
Contexte: Aide à la conception de systèmes.
ModélisationUML
MéthodesFormelles
Systèmescritiques,réactifs
Construction incrémentale 4
Introduction
Contexte Systèmes critiques: si une
défaillance peut conduire à des conséquences inacceptables en termes humains, économiques et environnementaux.
Patriot: système de missile sol-air
Une erreur de logiciel => 28 morts
Construction incrémentale 5
Introduction
Contexte Systèmes réactifs: un système
réactif doit réagir à un environnement qui ne peut pas l'attendre, à la différence d'un système interactif qui communique de façon permanente avec son environnement chacun évoluant à sa propre vitesse
Construction incrémentale 6
Introduction
UML langage de modélisation visuelle
unifié machine d’états UML
Machine d’états UML
HarelMachines d’états
BoochMéthode de Booch
RumbaughOMT
JacobsonOOSE
Construction incrémentale 7
Introduction Constat: difficulté de construction
des machines d’états Manque de supports d'analyse,
d'exploitation ou de vérification des modèles UML et des machines d’états
Sémantique des machines d'états UML n'est pas suffisamment documentée et reste ambiguë
Faiblesses du langage: manque de modularité, généricité
Pas de méthodologie de construction des machines d’états
Construction incrémentale 8
Introduction Approche: Aide à la construction de machines d'états
UML par une approche incrémentale. étapes progressives par ajout de détails et de
comportements (approches descendantes et ascendantes) évaluations des modèles possibilité d’obtenir des versions intermédiaires
exploitables
S0 s1
Sn
I1I0
In
Spécification,Abstraite, partielle
complète
détaillée
vérification
implantation
construction, extension
Cahier des
charges
Construction incrémentale 9
Introduction Notre approche: évaluer les modèles
par comparaison. Cadre mono langage, sans expliciter les
propriétés à vérifier Travail antérieur [Gou07] : la pertinence
des relations de conformité dans un cadre incrémental est établie, mais mise en œuvre complexe
Objectifs: Réalisations de ces relations ? Définir un cadre de construction
incrémentale
Construction incrémentale 10
Plan Introduction État de l’art
Raffinement Machines d’états UML
Contributions Implantation des relations de conformité Transformation des machines d’états en
LTS Formalisation d’un cadre de construction
incrémentale Raffinement d’architecture
Conclusion
Construction incrémentale 11
État de l’art Raffinement et vérification des
machines d’états UML Il existe des travaux de vérification de
la cohérence intra-modèles, inter-modèles[SMSJ03]
Il existe des travaux de vérification a posteriori (Model checking) [LLM99,KM02]
Mais pas de travaux relatifs à la construction incrémentale ni au raffinement.
Construction incrémentale 12
État de l’art
Raffinement Notion informelle:
Passage de l’abstrait au concret => ajout de détails + réduction de l’indéterminisme.
Préserver les propriétés de l’abstraction
Notion formelleqraf p) (fr j r imqgµ fr j r impg
Construction incrémentale 13
État de l’art
Raffinement: Toute implantation du modèle raffiné est également une implantation de modèle abstrait (Boiten, Leduc…)
Algèbres de processus (CSP, CCS…) Raffinement en sémantique de
traces (réduction de traces) Raffinement en sémantique
d’échecs stable(réduction de l’indéterminisme)
Raffinement en sémantique d’échecs divergence
Méthode B Affaiblir les
préconditions, renforce les postconditions
Retirer de l’indéterminise dans les opérations.
Ajouter de nouveaux détails, événements
Préservation de l’invariant abstrait
Construction incrémentale 14
État de l’art Déterminisme
Définition: « si l'on effectue la même expérience deux fois sur un système déterminé, en commençant à chaque fois dans son état initial, alors nous nous attendons à obtenir le même résultat, ou comportement, à chaque fois » [Mil89]
Importance de l’indéterminisme dans l’aide à la conception: Indéterminisme est un mécanisme
d’abstration
Construction incrémentale 15
État de l’art Relations d’implantation
Spécification est une description de haut niveau du comportement souhaité d'un système
Implantation est considérée valide si elle satisfait un ensemble de propriétés définies telles que la réduction des blocages, la réduction de l'indéterminisme
Relation de conformité
Construction incrémentale 16
État de l’art
LTS quadruplet P: ensemble non vide d'états (ou
processus) A: ensemble de noms d'actions relation de transitions p: état initial
hP;A;! ;pi
!p2 P
p
p1
p2 p3
a
b c
P = { p,p1,p2,p3 }
A = {a,b,c}
Construction incrémentale 17
État de l’art Relations de conformité
Ensemble de refus
Ensemble d’acceptance
Ref (p;¾) =def
½X j9p2 P after ¾:p
e6) ;8e2 X
¾
p
p1 p2
p3
a
b c
τ
p3
Acc1(p;¾) =def fX j 9p02 p after ¾: X =Out(p0;")g
Ref (p;²) = f fa;bg;f bg;fag;? gRef (p;c) = f fa;b;cg;fb;cg;fa;cg;fa;bg;fag;fbg;f cg;? gRef (p;a) = f f a;cg;f ag;f cg;? gRef (p;ab) = f fa;b;cg;fb;cg;fa;cg;fa;bg;f ag;f bg;f cg;? g
Acc1 (p;²) = f f cg;fa;cggAcc1 (p;c) = f f ? ggAcc1 (p;a) = f fbggAcc1 (p;ab) = f f ? gg
Construction incrémentale 18
État de l’art Relations de conformité
Extension Réduction
p
p1 p2
p3
a
b
c
τ
p4
q
q1
a
r
r1 r2
baconf conf
6conf
qconf psi 8¾2 Tr(p): Acc1(q;¾)½½Acc1(p;¾)qconf psi 8¾2 Tr(p):Ref(q;¾) µ Ref(p;¾)
qext p si Tr(q) ¶ Tr(p) et qconf p
qredp si Tr(q) µ Tr(p) et qconf p
red ext
Construction incrémentale 19
Plan Introduction État de l’art
Raffinement vs construction incrémentale Machines d’états UML
Contributions Implantation des relations de conformité Transformation des machines d’états en
LTS Formalisation d’un cadre de construction
incrémentale Raffinement d’architecture
Conclusion
Construction incrémentale 20
Implantation des relations de conformité Graphes d’acceptance
déterministe obtenu par la déterminisation du LTS p chaque état du graphe contient deux informations:
l’ensemble d’états correspondants l’ensemble d’acceptance après la même trace du LTS p
A(p) =def hT;L ;! T ; ti
p
p1 p2
p3
b
a
c
a
p4 p5
d
p6
τ
t
t1
t2t4
a
b cd
t3
t:acc= f fagg t:states = fpg
t1:acc= f fbg;f c;dg;fdgg
t1:states = fp1;p2;p5g
t2:acc= f? g t2:states = fp3g
t4:acc= f? g t4:states = fp4g
t3:states = fp6gt3:acc= f? g
Construction incrémentale 21
Implantation des relations de conformité
Théorème: Soient p,q deux LTS et leur graphe d’acceptance:
1. .2. .
A(p) = hT;L ;! T ;ti ;A(q) = hU;L;! U ;ui
Soit ¦ = fht;ui j u:acc½½t:accg
qext p , t - ¦ u
qredp , t %¦ u
Construction incrémentale 22
Implantation des relations de conformité
Soient p et q deux LTS, et leur graphe d'acceptance
le graphe fusionné des graphes d'acceptance
Algorithme de fusion est réalisable et linéaire
A(p) = hT;L;! T ;ti A(q) = hU;L;! U ;ui
Merge(A(p);A(q)) = hV;L ;! V ;ht;ui i
Merge(p;q) =Merge(q;p)
Merge(p;q) ext p
Merge(p;q) ext q
Construction incrémentale 23
Implantation des relations de conformité
Théorème: Soient p et q deux LTS
Corollaire: Soient p et q deux LTSqconf p, Merge(A(p);A(q)) %¦ A(q):
q conf p , q red Merge(p;q):
Construction incrémentale 24
Implantation des relations de conformité
Évaluation de la complexité La déterminisation est PSPACE-complet La vérification de simulation est
linéaire La fusion des graphes d’acceptance
est linéaire Amélioration de la performance
La minimisation observationnelle des LTS, nous permet d’avoir un temps de calcul raisonable
Construction incrémentale 25
Comparaison de performanceSans minimisation Avec minimisation
Nb d’états
Nb de transitions
(s) Nb d’états
Nb de transitions
(s)
1318 3962 6,078 152 449 0,125
1924 5830 11,434 225 679 0,391
10617 33696 379 48 130 0,016
23887 77644 1522 93 266 0,047
130047 434156 66265 413 128 0,922
214975 720844 - 657 2069 2,625
Construction incrémentale 26
Formalisation d’un cadre de construction incrémentale
Relation de raffinement – confrestr
Proposition [Led92] Soient p,q deux LTS, q confrestr p ssi
qraf p) (fr j r imqgµ fr j r impg
8¾2Tr(p) ¡ Tr(q), onaL 2Ref(p;¾).
qconf p
Construction incrémentale 27
Exemple de raffinementp
p1 p2
p3
a
b
c
τ
p4
q
q1
a
r
r1 r2
ba
6conf
red ext
p
p1 p2
a
d τ
p3
q
q1 p2
q3
ab
c
conf6red6ext
conf
r
r1 r2
bd ar3
r4
c
Construction incrémentale 28
Implantation de la relation confrestr
Théorème: Soient p,q deux LTS, t,u leur graphe d'acceptance et v le graphe d'acceptance fusionné
Soient p et q deux LTS, la relation red* est définie:
qconfrestr p,v %¦ u
8v02 (V ¡ ª v2(u));8p02 (T (v0)):states; p0= stop
qred¤ p=def qconfrestr p\ qredp
Merge(t;u) = hV;L;! V ;vi .
Construction incrémentale 29
Plan Introduction État de l’art
Raffinement vs construction incrémentale Machines d’états UML
Contributions Implantation des relations de conformité Analyse des machines d’états UML Formalisation d’un cadre de construction
incrémentale Raffinement d’architecture
Conclusion
Construction incrémentale 30
Analyse des machines d’états UML
Transformation des machines d’états en LTS Association d’une sémantique LTS
aux concepts UML Méthodes et signaux des interfaces
fournies ne sont pas masquées. Signaux des interfaces requises du
modèle de référence et du modèle à analyser ainsi que les méthodes privées sont masqués
Construction incrémentale 31
Transformation des machines d’états en LTS
0 event11 event1 event1/action12event1
action1
/action13 i
action1
when(c) after delay
at time
4 iwhen(c)/a after delay/a
at time/a
5a
i
[g]6
S’il n’y a pas de « else »
i iØ 8 [g]/a
S’il n’y a pas de « else »
i
a
i
ae[g]
7 i e
i
e [g]/a
9i
i e
a noeud de composition noeud d’entrée ou sortie
Construction incrémentale 32
Exploitation des relations de conformité
Cadre d’analyseext… ?
Transformation UML -> LTS
Construction des graphes d’acceptance
SM2
Ag(LTS1)
LTS1
Ag(LTS2)
Vérification desrelations de conformité
OK
LTS2
Échec &traces
conf,ext, red…. ?
Analyse &correction
LTS2*
)
SM1
)
SM2*
/
accept stop
τ
τh
τ τS
3
S
6S
7
c
τ
τ τS
4 S
6S
7
Construction incrémentale 33
Étude de casMachine d’états de PhoneSpec Machine d’états de Phone
do / listenNetwork
Idle
Waiting
pickUp
Connection Request
do / checkNumber
Checking
WaitingConnection
dial
[con==err] / error
conRefIn / busy
Busy/Error
conRec / conRefOut
conRec / conRefOut
hangUp / disconReq
hangUp / disconReq
do / checkNetwork
ConnectedconAckIn
hangUp / disconReq
conRec / call
do / ring
Ringing
disconRec
pickUp / conAckOut
disconRec
[else] / conReq
disconReccommIn / commOut
hangUp / disconReq
disconRec
conRec / conRefOut
do / listenNetwork
Idle
Waiting
do / wait
ConnectionRequest
do / ring
Ringing
do / checkNetwork
Connected
Busy/Error
pickUp
hangUp
dial
[conn==busy] / busy
[else] / error
hangUphangUp
when(called) / call
when(disconnected)
pickUp
[conn==ack]
when(disconnected)
commIn / commOut
hangUp
« conf ? »
Construction incrémentale 34
Phone est-il conforme à PhoneSpec?1ère étape : construction des LTS
LTS de PhoneSpec LTS de Phone
conf ?
Construction incrémentale 35
Phone est-il conforme à PhoneSpec? 2e étape : construction & fusion des graphes d’acceptance
Graphe d’acceptance de PhoneSpec Graphe d’acceptance de Phone
Graphe d’acceptance de la fusion
4
0
5
1 6
2
3
pickUp
hangUp
pickUp
pickUp
pickUp
commIn
hangUp
hangUpcommIn
commIn
dial
n
x0
x1
x2
x3
commIn
pickUp
hangUp commIn commI
dial
hangUphangUp
4
0
5
1 62
3 commIn
pickUp
pickUp
pickUp
hangUp
commIn
commIn
hangUp
dial
pickUp
hangUp
La relation de simulation et l’inclusion des ensembles
sont vérifiées
CONFORMITÉ DÉMONTRÉE
Construction incrémentale 36
Phone est-il conforme à PhoneSpec?3e étape : Calcul d’une relation de simulation des graphes d’acceptance
Graphe d’acceptance de PhoneGraphe d’acceptance de la fusion
La relation de simulation et l’inclusion des ensembles
sont vérifiées
CONFORMITÉ DÉMONTRÉE
w4
w0
w5
w1w6
w2
w3
pickUp
hangUp
pickUp
pickUp
pickUp
commIn
hangUp
hangUpcommIn
commIn
dial
y4
y0
y5
y1 y6y2
y3 commIn
pickUp
pickUp
pickUp
hangUp
commIn
commIn
hangUp
dial
pickUp
hangUp
Construction incrémentale 37
DoubleCall est-il une extension de PhoneSpec ?
Machine d’états de PhoneSpec
Machine d’états de DoubleCall
do / listenNetwork
Idle
Waiting
do / wait
ConnectionRequest
do / ring
Ringing
do / checkNetwork
Connected
Busy/Error
pickUp
hangUp
dial
[conn==busy] / busy
[else] / error
hangUphangUp
when(called) / call
when(disconnected)
pickUp
[conn==ack]
when(disconnected)
commIn / commOut
hangUp do / listenNetwork
Idle
Waiting
do / wait
Connection Request
do / ring
Ringing
do / checkNetwork
Connected
Busy/Error
pickUp
hangUp
dial
[conn==busy] / busy
[else] / error
hangUp
hangUp
when(called) / call
when(disconnected)
pickUp
[conn==ack]
when(disconnected)
commIn / commOut
hangUp
do / beep
Beeping
do / checkNetwork
Connected2
when(called) / call
when(disconnected)
accept
hangUp
commIn / commOut
stop
stop
Raffinement ?
Construction incrémentale 38
0
1
2
3
commIn
pickUp
hangUp commIn commIn
dial
hangUphangUp
DoubleCall est-il une extension de PhoneSpec ?
NON
l’inclusion des ensembles
d’acceptance n’est pas vérifiée
LTS de PhoneSpec
Raffinement ?
Ensembles d’acceptance après les traces pickUp,commIn ou pickUp,dial,c
{{stop, accept}, {stop, accept, commIn, hangUp}, {hangUp}}{{commIn, hangUp},{hangUp}}
LTS de DoubleCall
z4
z0
z5
z1
z6
z2
z3
hangUp
pickUp
accept
accept
commIn
stop
stop
hangUp
dial
accept
commIn
stop
hangUp
commIn
accept
hangUp
stop
commIn
hangUp
acceptstop
commIn
hangUp
accept
stop
commIn
Construction incrémentale 39
Correction de la machine d’états DoubleCall
do / listenNetwork
Idle
Waiting
do / wait
Connection Request
do / ring
Ringing
do / checkNetwork
Connected
Busy/Error
pickUp
hangUp
dial
[conn==busy] / busy
[else] / error
hangUp
hangUp
when(called) / call
when(disconnected)
pickUp
[conn==ack]
when(disconnected)
commIn / commOut
hangUp
do / beep
Beeping
do / checkNetwork
Connected2
when(called) / call
when(disconnected)
accept
hangUp
commIn / commOut
stop
stop
after(10s)
do / listenNetwork
Idle
Waiting
do / wait
Connection Request
do / ring
Ringing
do / checkNetwork
Connected
Busy/Error
pickUp
hangUp
dial
[conn==busy] / busy
[else] / error
hangUp
hangUp
when(called) / call
when(disconnected)
pickUp
[conn==ack]
when(disconnected)
commIn / commOut
hangUp
do / beep
Beeping
do / checkNetwork
Connected2
when(called) / call
when(disconnected)
accept
hangUp
commIn / commOut
stop
stop
after(10s)
do / listenNetwork
Idle
Waiting
do / wait
Connection Request
do / ring
Ringing
do / checkNetwork
Connected
Busy/Error
pickUp
hangUp
dial
[conn==busy] / busy
[else] / error
hangUp
hangUp
when(called) / call
when(disconnected)
pickUp
[conn==ack]
when(disconnected)
commIn / commOut
hangUp
do / beep
Beeping
do / checkNetwork
Connected2
when(called) / call
when(disconnected)
accept
hangUp
commIn / commOut
stop
stop
Ancienne versionNouvelle version
Construction incrémentale 40
Plan Introduction État de l’art
Raffinement vs construction incrémentale Machines d’états UML
Contributions Implantation des relations de conformité Analyse des machines d’états UML Formalisation d’un cadre de construction
incrémentale Raffinement d’architecture
Conclusion
Construction incrémentale 41
Formalisation d’un cadre de construction incrémentale Distinction de deux axes de développémént:
L’axe horizontal est lié à l'ajout de nouvelles fonctionnalités en vue d'enrichir des spécifications successives
L'axe vertical représente les niveaux d'abstraction du plus abstrait au plus concret.
Stratégies de raffinement Stratégie h-v (horizontal-vertical) Stratégie v-h (vertical-horizontal) Stratégie mixte :consiste à développer de façon
itérative des raffinements horizontaux et verticaux
Construction incrémentale 42
Formalisation d’un cadre de construction incrémentale
S0,0 S0,1
S1,0
S0,2
S1,2
S0,m
S1,m
Si,0 Si,2 Si,m
Sn,0 Sn,1 Sn,2 Sn,m
S0,m-1
Si,j
Sn,j
Stratégie « v-h »
Stratégie « h-v »
imp0
imp1
rv0
rh0 rh1 rhj
rh0 rh1 rhj rhm-1
rv1
rv0
rv1
rhj
imp
rvi rvi
impi,j
si,j si,j+1
si+1,j si+1,j+1
rhj
rhjv-h
h-v
Construction incrémentale 43
Formalisation d’un cadre de construction incrémentale
Exigences locales pour des relations de raffinement chaque relation de raffinement local est
également une relation d'implantation chaque relation de raffinement local est
une relation de raffinement Raffinement horizontal est l’extension de
traces Raffinement vertical est réduction de
traces
rvi ±rhj = rhj ±rvi = impi ;j
Construction incrémentale 44
Exigences globales pour des relations de raffinement
Équivalence de stratégies
Propositionrvi+1 ±rvi = rv et rhj +1 ±rhj = rh 8i; j ;0 · i < n ¡ 1;0 · j <m¡ 1
impi+1;j +1 ±impi ;j = imp 8i; j ;0 · i < n ¡ 1;0 · j <m¡ 1
rvi ±rhj = rhj ± rvi = impi ;j 8i; j ;0 · i < n;0 · j <m
rv±rh = rh±rv = imp
Construction incrémentale 45
Mise en œuvre des relations de raffinement
Construction incrémentale 46
Exemple
Ready
MoneyBack DrinkDelivery
when(exhausted)
when (exhausted)
do / wait
do / giveChange do / giveDrink
drink
[!money]
OutOfStock
cancel
cancel
Choose
coins [enough]
cancel
coins [!enough]
[money]
Machine Réaliste
MoneyBack
cancel
[!money]
when(exhausted)
when (exhausted)
do / wait
Ready
do / giveChange do / giveGoods
GoodsDelivery
drink
OutOfStock
cancel
Choose
coins [m>=t]
cancel
[money]
cookies
Machine Choix Multiple
do / wait
Ready
do / giveChange
MoneyBack
do / giveDrink
DrinkDelivery
drink
OutOfStock
cancel
when(exhausted)
cancel
Choose
coins
when (exhausted)
cancel
coins
Machine Indéterministe
Ready
cancel
when(exhausted)
when (exhausted)
do / wait
do / giveChange
MoneyBack
do / giveDrink
DrinkDelivery
drink
OutOfStock
cancel
Choose
coins
cancel
coins
do / shutdown
Maintenance
getOpCode
Machine avec Maintenance
coins [enough]
Construction incrémentale 47
Exemple
red*
ext
ext
MachineAvecMaintenance
MachineRéaliste MachineChoixMultiple
MachineIndéterministe
ct
ctct
red* red*
ext
ext
ext
ext
Construction incrémentale 48
Plan Introduction État de l’art
Raffinement vs construction incrémentale Machines d’états UML
Contributions Implantation des relations de conformité Analyse des machines d’états UML Formalisation d’un cadre de construction
incrémentale Raffinement d’architecture
Conclusion
Construction incrémentale 49
Raffinement d’architecture Motivations
Bénéficier de composants réutilisables Facilité de la maintenance du système
Problématique calculer le comportement d'un assemblage
de composants dont les comportements sont spécifiés par des ME?
garantir qu'un assemblage est conforme à une spécification exprimée par une ME
comparer des assemblages ayant même structure ou de structures différentes
Construction incrémentale 50
Étude de cas
JobShopJobReceipt
:SingleJob
:A0
:SingleJob
JobDeposit
« delegate »
« delegate »
inp(job)/
Idle
/outp(job)
SingleJob SM
do/ perform(job)Busy
<<Interface>>JobReceiptinp(job) outp(job)
<<Interface>>JobDeposit
-perform(job)
SingleJob
Construction incrémentale 51
Étude de cas
JobShop
get()
Idle
Tool SM
put()
use()Busy
<<Interface>>UseTool
-put()-get()-use()
Tool
/outp(job) inp(job)
Idle
Jobber SM
do / perform(job)
Busy
inp(job) /tool.get();
Ready
/out(job)
/tool.use()
do / perform(job)exit / tool.put()
BusyWithTool
SingleJob
-perform(job)
Jobber-put()-get()-use()
<<Interface>>
UseTool
« ext »
Construction incrémentale 52
Raffinement d’architecture Analyse architecturale
Sémantique: deux vues architecturales: Vue externe: les signaux de communication
inter-composants sont masqués. Vue interne: aucun signal de communication
inter-composants n'est masqué. opérateur de parallélisme sans
synchronisation ||| pour composer des LTS associés à des composants qui ne sont pas en interaction.
opérateur |[I]| de synchronisation sur l'interface I
Construction incrémentale 53
Étude de cas
ArchitecturesJobReceipt
:Jobber
:A1
:Jobber
JobDeposit
:Tool
UseTool
« delegate »
« delegate »
JobReceipt
:Jobber
:A2
:Jobber
JobDeposit
:Tool
UseTool
:Tool
« delegate »
« delegate »
ext
Construction incrémentale 54
Étude de cas
Nouveau JobberJobReceipt
:Jobber*
:A3
:Jobber
JobDeposit
:Tool
UseTool
:Tool
« delegate »
« delegate »
inp(job)
Idle
Jobber* SM
do / perform(job)Busy
inp(job) /tool.get();
Ready
/outp(job)
use()
do / perform(job)BusyWithTool
EndTask
/tool.put()
/outp(job)
inp(job)
Jobber
-perform(job)
Jobber*
« ext »
JobReceipt
:Jobber
:A2
:Jobber
JobDeposit
:Tool
UseTool
:Tool
« delegate »
« delegate »
ext
Construction incrémentale 55
Raffinement d’architecture
Bilan
A2 =hide(ID [ I T ) in (J jjj J )j[I T ]j(T jjj T)
J ¤ cext J ) A3 ext A2
A3 =hide(ID [ I T ) in (J ¤ jjj J )j[I T ]j(T jjj T)
Construction incrémentale 56
Conclusion Résultats
Implantation des relations de conformité Proposition de la transformation des
machines d’états en LTS Formalisation du cadre de construction
incrémentale Établir un cadre de raffinement
d’architecture Limites
Complexité théorique => Interprétation des résultats
Construction incrémentale 57
Conclusion Perspectives
Réduction de la complexité (algorithme de raffinement de partitions [PT92]
Prise en compte d’autres informations Types de données, OCL, entrées/sorties Définition la conformité intégrant la notion de
séquence interdite Nouvelles conditions assurant la conformité
d’architectures Identifier les fonctionnalités essentielles Rendre la flexibilité de la démarche
incrémentale Couplage avec d’autres modèles comportementaux Définition des patrons de conception
Construction incrémentale 58
Bibliographies
Construction incrémentale 59
Merci pour votre attention
Construction incrémentale 60
État de l’art (1)
Méthodes formelles
Cahier des charges
Réalisation
constructionvalidation de laréalisation réelle
Modèle de laspécification S
Modèle de laréalisation R
Vérification(R||E) satisfait-il S?
Idéesouhait
s
Environnement Modèle de l’envrironnement E
client
Validation du modèle
Validation du modèle
Validation du modèle
Informel FormelVérification de la cohérence interne
Construction incrémentale 61
État de l’art (1)
Raffinement en B
S0s1
Snabstraite, globale
concrète
construction
raffinement
Cahier des
charges
Construction incrémentale 62
État de l’art (1)
Développement incrémental
S0s1
Sn
I1I0
In
Abstraite, partiellecomplète
détaillée
vérification
implantation
construction, extension
Cahier des
charges
Construction incrémentale 63
Implantation des relations de conformité Graphes d’acceptance
est un ensemble de noms d’états est un ensemble de transitions de est l'état initial Pour chaque état et
Pour tout pour tout pour tout il existe un unique
A(p) =def hT;L ;! T ; tiT! T T £ L £ T.t 2 T
t:states = f fpgg" ;
t1x¡! T t2 avec t2:states = ([ s2t1:statesD(s;x))
"
t:states 2 2P
t:acc= fX j X =Out(q;") ^q2 t:statesg;
t:accµ 2L
t1 2 T, X 2 t1:acc, x 2 X ,t2 2 T
Construction incrémentale 64
État de l’art
Ensemble d’acceptance [Hen85]
Convergence s'il n'y a pas séquence
infinie telle que et
si et implique
p
p1
p2
p3
a
b c
τ
p#² hpi i i¸ 0p ¿¡! p0 pi
¿¡! pi+1
p#a:¾0 p #² p a) p0
p0#¾0.
Acc2(p;¾) =def f S(p0) j p¾) p0^p06¿¡! g
Construction incrémentale 65
État de l’art
Préordre Must [Hen85]p@» must
q si 8¾2 A¤:p#¾) (q#¾^Acc2(q;¾) ½½Acc2(p;¾))
p
p1 p2
p3
b
a
c
a
p3
q
q1
q2q3
a
b c
p@» mustq