View
104
Download
1
Category
Preview:
Citation preview
Méthodes symboliques pour Méthodes symboliques pour la génération de tests de la génération de tests de
systèmes réactifs comportant systèmes réactifs comportant des donnéesdes données
Eléna Zinovieva LerouxEléna Zinovieva Leroux22 novembre 20042004
Membres du Membres du jury:jury:Prof. Bruno Prof. Bruno Legeard Legeard
Prof. Jan TretmansProf. Jan Tretmans
Dr. Bruno Marre Dr. Bruno Marre
Prof. Olivier Prof. Olivier RidouxRidoux Prof. Claude Jard Prof. Claude Jard
Dr. Vlad RusuDr. Vlad Rusu
(rapporteur)(rapporteur)
(rapporteur)(rapporteur)
(examinateur)(examinateur)(examinateur)(examinateur)
(directeur de (directeur de
thèse)thèse)(encadrant)(encadrant)
2
Systèmes Réactifs
EnvironnementEnvironnement
complexes, critiques.
Doivent être fiables et sans erreur importante.
test, vérification, analyse statique, …
3
Test
Exécution d’une implémentation sous test avec l’intention d’y trouver des erreurs.
« Program testing can be a very effective way to show the presence of bugs, but it is
hopelessly inadequate for showing their absence. »
E.W. Dijkstra
CoffeeButton ?
Coffee !Tea !
Pass
Fail
Cas de test
CoffeeButton ?
Coffee !Tea !
Pass
Fail
bouton de café
thé
café
4
Pourquoi s’intéresser au test?
Le test est largement utilisé dans l’industrie, mais il est coûteux.
La détection d’erreurs graves dans les systèmes réactifs est très importante. « Testing often consume 50% of software
effort. »B. Boehm
Mars Climate Orbiter de la NASA (Octobre 1999)
[Isbell & Savage]Désastre: écrasé sur la planète au lieu d’atteindre une orbite sécurisé.
Pourquoi: erreur logicielle – erreur lors de la conversion des unités de mesure américaines en valeurs métriques.
automatisation du test
Diminution du coût. Identification plus facile des erreurs.
5
Plan
1. Test de conformité boîte noire.2. Cadre formel du test de conformité.3. Génération symbolique de cas de test. 4. Exécution d’un cas de test.5. Outil : STG.6. Conclusion et perspectives.
6
Test de conformité boîte noire
Spécification (et objectif de test)
Cas de test
Implémentation du système
Génération de cas de test
automatique
Exécution du test
?
Fail Inconclusive Pass
conforme à ?
7
Des techniques énumératives aux techniques symboliques
Explosion combinatoire de l’espace d’états; Les cas de test ne sont pas génériques.
Motivations :
Utiliser un nouveau modèle et des techniques symboliques pour produire un cas de test!
Solution :
8
Notre approche
Modèle symbolique : IOSTS.
Génération symbolique de cas de test :• Spec, TP IOSTS TC IOSTS.
Exécution de cas de test : • instanciation des entrées par la résolution de contraintes.
9
Plan
1. Test de conformité boîte noire.2. Cadre formel du test de conformité :
système symbolique de transitions à entrée/sortie (IOSTS),
relation de conformité, cas de test & implémentation sous test, propriétés attendues des cas de test.
3. Génération symbolique de cas de test. 4. Exécution d’un cas de test.5. Outil : STG.6. Conclusion et perspectives.
10
Système symbolique de transitions à entrée/sortie (IOSTS)
Machine à café
Spécification
(vBev = pBev)
Deliver ! (pBev)
Return
Delivery
(pRemVal=vPaid)
Return ! (pRemVal)
Cancel ?
Cancel ?
ChooseBeverage ? (pBev)
vBev := pBev
Begin
Idle
Pay
Choose
vPaid:=0
(vPaid ≥ cPrice) &
(pRemVal=vPaid-cPrice)
Return ! (pRemVal)vPaid:=cPrice
(vPaid<cPrice) & (pRemVal=cPrice-vPaid)Return ! (pRemVal)
pCoinVal > 0 Coin ? (pCoinVal)vPaid:=vPaid+pCoinVal
cPrice>0
Empty !
Objectif de test
Accept
Begin
(vPaid<cPrice) Return ! (pRemValtp) Reject
(pBevtp = COFFEE)
Deliver ! (pBevtp)Cancel ?
Exemple de comportement :
. Coin ? (5) . Return ! (2) . ChooseBererage ? (COFFEE) .
Deliver ! (COFFEE)
visible
Traces(Spec)
11
Relation de conformité
ioc (version faible d’ioco [Tretmans96]) : après un comportement visible de la spécification Spec, l’implémentation sous test IUT n’est autorisée à produire que les sorties spécifiées. Formellement :
IUT Spécification
partielle
Comportements visibles d’une
Spec
IUT ioc Spec = ∀ ∈ Traces(Spec) . [ Out(IUT after ) ⊆ Out(Spec after ) ]
Sorties non spécifiées
!
¬ (IUT ioc Spec)
?
Entrées non
spécifiées(IUT ioc Spec)
12
Cas de test & IUT
……………
BeverageType ChooseBeverage
(BeverageType pBeverage) {
cerr << "ChooseBeverage(";
if(pBeverage == COFFEE) {
cerr << “TEA)"; return TEA;
}
if(pBeverage == TEA) {
cerr << "TEA)"; return TEA;
}
}
……………
Machine à café
<Begin,Begin>
cPrice>0
<Pay,Begin>
<Choose,Begin>
<Delivery,Begin>
(vPaid = cPrice) & (vPaid > 0)
Empty ?
(pCoinVal>0) & (pCpinVal ≥ cPrice)Coin ! (pCoinVal)vPaid:=0+pCoinVal
Inconclusive
(pRemVal = vPaid-cPrice) &(vPaid > 0) & (vPaid ≥ cPrice) Return ? (pRemVal)vPaid:=cPrice
(pBev=COFFEE) &(vPaid = cPrice) & (vPaid > 0)ChooseBeverage ! (pBev)vBev := pBev
(pBev=COFFEE) & (vBev=pBev) &
(vPaid > 0) & (vPaid=cPrice)
Deliver ? (pBev)
Pass Fail
( (pBev=COFFEE) & (vBev=pBev) &
(vPaid > 0) & (vPaid=cPrice) )
Deliver ? (pBev)
13
Propriétés des cas de test
TC est non biaisé s’il ne rejette pas les IUT conformes.
TC est précis s’il produit le verdict Pass lorsque la trace observée de l’IUT est une trace de la Spec sélectionnée par l’objectif de test TP.
TC est concluant s’il produit le verdict Inconclusive quand la trace observée de l’IUT est une trace de la Spec qui finit par une action de sortie mais aucun prolongement de cette trace ne peut produire le verdict Pass.
14
Plan
1. Test de conformité boîte noire.2. Cadre formel du test de conformité.3. Génération symbolique de cas de test. 4. Exécution d’un cas de test.5. Outil : STG.6. Conclusion et perspectives.
15
Génération symbolique de cas de test
Objectif de test TP
Cas de testTC
SpécificationSpec
Génération symbolique de cas de test :
• Calcul du produit SP = Spec TP;• Construction des comportements visibles SPvis;• Sélection et simplification du graphe de test TG;• Complétion de TG en entrée.
16
Exemple : calcul du produit
Spec
(vBev = pBev)
Deliver ! (pBev)
Return
Delivery
(pRemVal=vPaid)
Return ! (pRemVal)
Cancel ?
Cancel ?
ChooseBeverage ? (pBev)
vBev := pBev
Choose
(vPaid ≥ cPrice) &
(pRemVal=vPaid-cPrice)
Return ! (pRemVal)vPaid:=cPrice
(vPaid<cPrice) & (pRemVal=cPrice-vPaid)Return ! (pRemVal)
pCoinVal > 0 Coin ? (pCoinVal)vPaid:=vPaid+pCoinVal
cPrice>0
Begin
tauvPaid:=0
Empty !
Pay
Idle
TP
Accept
Begin
Reject
Cancel ?
(pBevtp = COFFEE)
Deliver ! (pBevtp)
(vPaid<cPrice)
Return ! (pRemValtp)
(pBevtp ≠ COFFEE)
Deliver ! (pBevtp)
otherwise otherwise
otherwise
(vPaid<cPrice) & (pRemVal=cPrice-
vPaid)Return ! (pRemVal)
(vBev=pBev) &
(pBev=COFFEE)
Deliver ! (pBev)
(vPaid ≥ cPrice) & (pRemVal=vPaid-cPrice)Return ! (pRemVal)vPaid:=cPrice
ChooseBeverage ? (pBev)
vBev := pBev
<Begin,Begin>
pCoinVal > 0
Coin ? (pCoinVal)vPaid:=vPaid+pCoinVal
cPrice>0 & true
<Pay,Begin>
<Choose,Begin>
<Delivery,Begin>(vBev=pBev) &
(pBev ≠ COFFEE)
Deliver ! (pBev)
<Idle,Begin>
tauvPaid:=0
SP = Spec TP
<Return,Reject>
Cancel ?
<Idle,Reject>
Cancel ?
<Begin,Accept>
(vPaid<cPrice) &
(vPaid ≥ cPrice) & (pRemVal=cPrice-
vPaid)Return ! (pRemVal)
<Choose,Reject>(vPaid<cPrice) &
(vPaid ≥ cPrice) & (pRemVal=vPaid-
cPrice)Return ! (pRemVal)
vPaid:=cPrice
<Begin,Reject>
Empty !
true
17
Génération symbolique de cas de test
Objectif de test TP
Cas de testTC
SpécificationSpec
Génération symbolique de cas de test :
• Calcul du produit SP = Spec TP;• Construction des comportements visibles SPvis :
• clôture,• déterminisation.
• Sélection et simplification du graphe de test TG;• Complétion de TG en entrée.Résultat après le produit :
Traces(SP) = Traces(Spec) ATraces(SP) Traces(Spec) ATraces(TP)
18
Construction des comportements visibles (1/2)
laln+1l1 l2 ln
G1
1
A1
Gn
n
An
Ga
a()Aa
G1 & (G2◦A1) & … & (Gn◦An-1◦…◦A1) & (Ga◦An◦An-1◦…◦A1)a()
Aa ◦ An ◦ An-1 ◦…◦ A1
l1 la
Clôture :
Exemple :
<Begin,Begin>
(pCoinVal>0) &
(vPaid < max)
Coin ? (pCoinVal)vPaid:=vPaid+pCoinVal
cPrice>0
<Pay,Begin>
<Idle,Begin>
vPaid:=0
SP
<Return,Reject>
Cancel ?
vPaid:=vPaid
<Begin,Begin>
(pCoinVal>0) & (0<max)
Coin ? (pCoinVal)vPaid:=0+pCoinVal
cPrice>0
<Pay,Begin>
clôture(SP)
<Return,Reject>
Cancel ?
vPaid:=0
pas de cycle d’actions internes.
19
Construction des comportements visibles (2/2)
lG1
a()A1
Déterminisation :
l1 l2
G2
a()A2
lb lc
Gb
b(b)Ab
Gc
c(c)Ac
l
(G1 &
¬G2)a()A1
l1 l2
lb lc
Gb
b(b)Ab
Gc
c(c)Ac
(¬G1 & G2)a()A2
l1,2
(G1 & G2)a()
(Gb◦A1)b(b)
(Ab◦A1)
(Gc◦A2)c(c)
(Ac◦A2)
Begin
pCoinVal > 0
Coin ? (pCoinVal)vPaid := pCoinVal
WaitMilk
clôture(SP)
Exemple :
Pay vPaid 3
Coffee ! v := 1
vPaid 3
Coffee ! v := 2
Coffee&Milk
vPaid + v > 10Milk !
vPaid := vPaid + vv := v
Begin
pCoinVal > 0
Coin ? (pCoinVal)vPaid := pCoinVal
Wait1,2
SPvis = det(clôture(SP))
Pay
vPaid = 3
Coffee !
vPaid > 3
Coffee ! v := 2
WaitMilk
vPaid < 3
Coffee ! v := 1
WaitSugar
termine sous une condition syntaxique.
WaitSugar
Coffee&Sugar
vPaid – v > 0Sugar ! vPaid := vPaid
v := v
Coffee&Milk
vPaid + v > 10Milk !
vPaid := vPaid + vv := v
vPaid + 2 > 10Milk !
vPaid := vPaid + 2v := 2
Coffee&Sugar
vPaid – v > 0Sugar ! vPaid :=
vPaidv := v
vPaid – 1 > 0Sugar ! vPaid := vPaid
v := 1
20
Génération symbolique de cas de test
Objectif de test TP
Cas de testTC
SpécificationSpec
Génération symbolique de cas de test :
• Calcul du produit SP = Spec TP;• Construction des comportements visibles SPvis;• Sélection et simplification du graphe de test TG;• Complétion de TG en entrée.
Résultat après construction de SPvis : Traces(SPvis) = Traces(SP) = Traces(Spec) ATraces(SPvis) = ATraces(SP)
21
Sélection du graphe de test
SPvis avec S – ensemble des états,S0 – ensemble des états initiaux, Sbut – ensemble des états buts.
coreach(SPvis,Sbut)
Solution :
S
S0
non calculables de manière exacte
sur-approximation coreach(SPvis,Sbut)
calcul exact
sur-approximation
Problème :
Sélectionner un sous graphe de SPvis menant à la satisfaction de l’objectif de test TP.
TG
Sbut
Coin ? (5)
Return ! (2)
ChooseBeverage ? (COFFEE)Empty
!
Deliver ? (COFFEE)
inconclusive
Cancel ?
22
Exemple : sélection du graphe de test
(vPaid > 0) &
(cPrice > 0) &
(vPaid<cPrice) & (pRemVal=cPrice-
vPaid)Return ! (pRemVal)
Deliver ! (pBev)
Return ! (pRemVal)vPaid:=cPrice
ChooseBeverage ? (pBev)
vBev := pBev
<Begin,Begin>
Coin ? (pCoinVal)vPaid:=0+pCoinVal
cPrice>0
<Pay,Begin>
<Choose,Begin>
<Delivery,Begin>
(vPaid = cPrice) &
(vPaid > 0) & (cPrice > 0) &
(vBev=pBev) & (pBev ≠ COFFEE)
Deliver ! (pBev)
TG’ = coreach(SP’vis,Sacc)
<Return,Reject>
(cPrice > 0)
Cancel ?
vPaid := 0
<Idle,Reject>
(vPaid = cPrice) & (vPaid > 0) & (cPrice > 0)
Cancel ?
<Begin,Accept>
<Begin,Reject>
(vPaid = cPrice) & (vPaid > 0) & (cPrice > 0)
Empty !
SP’vi
s
analyse de analyse de co-co-
accessibilité accessibilité avec NBacavec NBac
pRemVal=vPaid-cPrice
(pBev=COFFEE) & (pBev=vBev)
<Begin,Begin>
(cPrice>0)
<Pay,Begin>(cPrice>0) & (vPaid ≥ cPrice)
<Choose,Begin>(cPrice>0) & (vPaid=cPrice)
<Delivery,Begin>(cPrice>0) & (vPaid=cPrice)
& (vBev=COFFEE)
<Begin,Accept>(cPrice>0) & (vPaid=cPrice)
& (vBev=COFFEE)
pCoinVal>0
true
Résultat de Résultat de l‘analyse de la co-l‘analyse de la co-
accessibilitéaccessibilité(cPrice > 0) &(pCoinVal > 0) &pCoinVal>0 &(cPrice>0) & (vPaid ≥ cPrice) (0+pCoinVal ≥ cPrice)
Inconclusive
Inconclusive
(vPaid > 0) & (cPrice > 0) &(vPaid ≥ cPrice) & (pRemVal=vPaid-cPrice)
&(pRemVal=vPaid-cPrice) & (cPrice>0) & (vPaid=cPrice) (cPrice=cPrice)
(pRemVal = vPaid-cPrice) &¬[ (cPrice>0) & (cPrice = cPrice) ]Return ! (pRemVal)vPaid:=cPrice
(vPaid = cPrice) & (vPaid > 0) &
(cPrice > 0)
(cPrice > 0) & (vPaid = cPrice) &
(vBev = COFFEE)(pBev = COFFEE)
(vPaid = cPrice) & (vPaid > 0) & (cPrice > 0) &
(vBev=pBev) & (pBev=COFFEE)
&(pBev=COFFEE) & (vBev=pBev) &
(cPrice > 0) & (vPaid=cPrice) & (vBev=COFFEE)
(pBev=COFFEE) & (vBev=pBev) &
¬[ (cPrice > 0) & (vPaid=cPrice) &
(vBev=COFFEE) ]
Deliver ! (pBev)Pass
analyse analyse d’accessibilid’accessibili
té avec té avec NBacNBac
+
miroir
TG = miroir(reach(TG,S0))
<Begin,Begin>
cPrice>0
<Pay,Begin>
<Choose,Begin>
<Delivery,Begin>
(vPaid = cPrice) &
(vPaid > 0) & (cPrice > 0)
Empty ?
(pCoinVal>0) &(cPrice>0) & (pCpinVal ≥ cPrice)Coin ! (pCoinVal)vPaid:=0+pCoinVal
Inconclusive
(pRemVal=vPaid-cPrice) &(vPaid > 0) & (cPrice > 0) & (vPaid ≥ cPrice) Return ? (pRemVal)vPaid:=cPrice
(pBev=COFFEE) &
(vPaid = cPrice) & (vPaid > 0) & (cPrice > 0)ChooseBeverage ! (pBev)vBev := pBev
(pBev=COFFEE) & (vBev=pBev) & (vBev=COFFEE)
(cPrice > 0) & (vPaid > 0) & (vPaid=cPrice)
Deliver ? (pBev)
Pass
et simplification
23
Génération symbolique de cas de test
Objectif de test TP
Cas de testTC
SpécificationSpec
Génération symbolique de cas de test :
• Calcul du produit SP = Spec TP;• Construction des comportements visibles SPvis;• Sélection et simplification du graphe de test TG.• Complétion de TG en entrée.Résultat après sélection de TG :
Traces(TG) Traces(SPvis) = Traces(SP) = Traces(Spec)
Tracespass(TG) = ATraces(Spec TP)
Tracesinconc (TG) (Traces(Spec) Traces(Spec).!Spec) \
pref(ATraces(Spec TP))
24
Exemple : complétion de TG en entrée
TG vers TC
<Begin,Begin>
cPrice>0
<Pay,Begin>
<Choose,Begin>
<Delivery,Begin>
(vPaid = cPrice) &
(vPaid > 0) & (cPrice > 0)
Empty ?
(pCoinVal>0) &(cPrice>0) & (pCpinVal ≥ cPrice)Coin ! (pCoinVal)vPaid:=0+pCoinVal
Inconclusive
(pRemVal=vPaid-cPrice) &(vPaid > 0) & (cPrice > 0) & (vPaid ≥ cPrice) Return ? (pRemVal)vPaid:=cPrice
(pBev=COFFEE) &
(vPaid = cPrice) & (vPaid > 0) & (cPrice > 0)ChooseBeverage ! (pBev)vBev := pBev
(pBev=COFFEE) & (vBev=pBev) & (vBev=COFFEE)
(cPrice > 0) & (vPaid > 0) & (vPaid=cPrice)
Deliver ? (pBev)
Pass Fail
otherwise ?
otherwise ?
otherwise ?
otherwise ?
Traces(TC) = Traces(TG) Tracesfail(TC)
Tracesfail(TC) Traces(Spec) . !Spec \ Traces(Spec)
Tracespass(TC) = Tracespass(TG) =
ATraces(Spec TP)
Tracesinconc(TC) = Tracesinconc(TG)
(Traces(Spec) Traces(Spec).!
Spec) \
pref(ATraces(Spec TP))
TC est non biaisé
TC est précis
TC est concluant
25
Plan
1. Test de conformité boîte noire.2. Des techniques énumératives aux
techniques symboliques.3. Génération symbolique de cas de test. 4. Exécution d’un cas de test.5. Outil : STG.6. Conclusion et perspectives.
26
Exécution d’un cas de test
TC
<Begin,Begin>
cPrice>0
<Pay,Begin>
<Choose,Begin>
<Delivery,Begin>
(vPaid = cPrice) &
(vPaid > 0) & (cPrice > 0)
Coin ! (pCoinVal)vPaid:=0+pCoinVal
Inconclusive
(pRemVal=vPaid-cPrice) &(vPaid > 0) & (cPrice > 0) & (vPaid ≥ cPrice)
(pBev=COFFEE) &
(vPaid = cPrice) & (vPaid > 0) & (cPrice > 0)
(pBev=COFFEE) & (vBev=pBev) & (vBev=COFFEE)
(cPrice > 0) & (vPaid > 0) & (vPaid=cPrice)
Pass
Fail
otherwise ?
otherwise ?
otherwise ?
otherwise ?
• instanciation des constantes symboliques,• résolution des gardes.
IUT d’une machine à café cPriceIUT = 3
Coin ? (5)
Return ! (2)
ChooseBeverage ? (COFFEE)
Deliver ! (COFFEE)
Empty !
PassInconclusive
Fail
otherwise !
otherwise !
(pCoinVal>0) &(cPrice>0) & (pCoinVal ≥ cPrice)
Return ? (pRemVal)vPaid:=cPrice
ChooseBeverage ! (pBev)vBev := pBev
Deliver ? (pBev)Empty ?
27
Plan
1. Test de conformité boîte noire.2. Cadre formel du test de conformité.3. Génération symbolique de cas de test. 4. Exécution d’un cas de test.5. Outil : STG.6. Conclusion et perspectives.
28
Outil : STGen collaboration avec D. Clarke et F.-X. Ponscarme
IUT (C++/Java)
Spécification &
Objectif de test
Cas de test abstrait
Génération de
cas de test
Compilation
Cas de test (C++/Java)
STGSTGDotty
Omega
NBac
Pass, Inconclusive, Fail
Génération• opérations symboliques,
• analyse approchée par interprétation abstraite (NBac).Exécution• compilation (C++/Java),
• résolution de contraintes (Omega).Expérimentations• BRP,
• CEPS [CJRZ-Esmart01] : ~30 variables et constantes symboliques, 30 localités et 91 transitions syntaxiques.
29
Plan
1. Test de conformité boîte noire.2. Cadre formel du test de conformité.3. Génération symbolique de cas de test. 4. Exécution d’un cas de test.5. Outil : STG.6. Conclusion et perspectives.
30
Contributions[ CJRZ-Esec01, CJRZ-Esmart01, CJRZ-Tacas02, Z-Movep02, JJRZ-RR04 ]
Originalité : Génération de cas de test génériques. Traitement de systèmes non déterministes. Sélection symbolique de cas de test basée sur
l’analyse approchée et indépendante de l’approximation.
Implémentation :La génération symbolique de tests est complètement automatisée (STG).
31
Perspectives
Améliorer les critères de sélection :• génération automatique d’objectifs de test,• génération de cas de test à partir de spécifications et de
critères de couverture,• …
Combiner des méthodes de validation dans le processus de développement.
Réaliser plus d’études de cas.
MerciThank youСпасибо
Recommended