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Спасибо