1

Contribution à la génération automatique

de tests pour les systèmes réactifs

Thierry Jéron

Habilitation à diriger des recherches16 mars 2004

2

Contexte: les systèmes réactifs

Exemples: protocoles télécom, systèmes embarqués, systèmes contrôle/commande, etc.

Complexité, répartition croissante, criticité

Nécessité de fiabilité / maîtrise des coûts

méthodes formelles

P1 P2

Env

3

Env

Spécification comportementale: exemple du protocole du bit alterné

Transmitter Receiver

RQ(data) CNFIND(data)

w

s

d:=0b:=0

?RQ(d)/!DT(d,b)

br ≠ bit?ACK(br) /

!DT(d,b)

br = b?ACK(br) /

!CNFb:=1-b

b:=0

s

br = b?DT(d,br)

!IND(d)!ACK(b)b:=1-b

br ≠ bit?DT(d,br)

!IND(d)!ACK(b)b:=1-b

ACK(bit)

DT(data,bit)

Processus concurrents, communication (interne-externe), structure de contrôle, données. Langages de spécification : SDL, Lotos, UML, etc

4

Sémantique : systèmes de transitions (LTS)

Spécification

comportementale

Spec

état: (localités, val(var), files)

état’: (localités, val(var), files)

action

Explosion combinatoire, voire infinitude (données, files)

Système de

transitions (LTS)

S = [[Spec]]simulation exhaustive

5

Vérification et test

Propriété P (automate, logique)Vérification de modèle

S ⊨ P ?

Test: Imp conforme à S ?I conf S ?

Spécification Spec S = [[Spec]]comportementale

Implémentation Imp

Hyp: Imp modélisable par I

6

Historique

Vérification à la volée

Non bornitudede files de CFSM

Génération de testssymbolique (IOSTS)(E. Zinovieva, 00->)

Modelchecking

Gen.test

(FSM)

Test et contrôle(V.Tschaen, 01->)

88 9291 93 9689 90 94 95 97 98 99 00 01 02 03 04

ADP AAR PAMPA VerTeCS

Véri

fica

tion

Test

de c

onfo

rmit

é &

O

bse

rvati

on

Repr. 3DLTS

Représentationmodel-checkingde syst. infinis

(YM Quemener,93-96)

Observation répartie

Génération de tests à la volée (IOLTS)(P. Morel, 96-00)

Test asynchrone

& réparti

Test et jeux

7

Plan

1. Problématique du test

2. Génération de tests à la volée

3. Test asynchrone et réparti

4. Génération de tests symbolique

5. Bilan et perspectives

8

1. Problématique du test Test = analyse dynamique de programmes pour détecter

des fautes par rapport à une spécification. ≠ vérification de modèle : exhaustivité impossible en pratique

Sélectionner les tests : à partir du code : test boîte blanche/structurel

à partir de la spécification : test boîte noire

Activité coûteuse et souvent artisanaleFormaliser est incontournable pour

Améliorer la qualité des tests Diminuer le coût du test

9

Test de conformité de systèmes réactifsPb: tester qu’une implémentation I (boîte noire) est conforme

à sa spécification S (supposée correcte).

Spécification S

Implémentation I

I conf S ?

Verdict

Cas de testcontrôle

observation

Générateur de tests

Critères desélection

10

2. Génération de tests à la volée[CAV96-99,SCP97-00,IWTCS96,Cfip97, IDPT02,TSI03, …]

Motivations: Éviter l’explosion combinatoire Traiter des systèmes non déterministes

Cadre théorique: Théorie du test des IOTS [Tretmans 95-96]

Origines: LTS [DeNicola-Henessy84, Abramsky87, Philips87, Brinksma88]

Contribution: Formalisation des objectifs de test Sélection de tests à la volée ← vérification à la volée

11

Le modèle: les IOLTSIOLTS (input/output LTS) : ~ IOTS [Tretmans96], IOA [Lynch88]

sémantique de systèmes réactifs non-déterministes spécifications, implémentations, tests, objectifs

?A

?B

! Z

! Y! X

S non-déterminisme observable :Les entrées ne déterminent pas les sorties

non-contrôlabilité

non-déterminisme (au sens des automates)

incertitudesupprimé par déterminisation

?B

! X

12

Comportements visibles par le testLe test permet de contrôler les entrées et

observer sorties et blocages (timers) distinguer les blocages spécifiés dans S des autres

⇒ calculer les blocages sur S

?A

?B

! Z

! Y

! X

S Comportementsvisibles de référence. Base pour définir la conformité

?A

?B

!Z

!Y!X

?B

Vis(S)=det((S))(S)Automate de suspension

13

I

Relation de conformité Plusieurs choix possibles: inclusion, égalité de traces, de sorties, de refus,

etc

ioco [Tretmans96] : après un comportement visible de la spécification, l’implémentation n’est autorisé à produireque les sorties et blocages spécifiées

?A

?B

!Z

!Y!X

?B

! ?

Sorties, blocages non spécifiées ¬ (I ioco S)

Entrées non spécifiées

I ioco S

Spécification partielle

vis(S)

14

Cas de test et exécutions

!A

?Y?X

TC

? Z

! BInconc

Fail

Pass

? otherwise?A

?B

!Z

!Y!X

?B

Vis(S)

Propriétés attendues des algorithmes de génération: Correction : I peut être rejetée par TC ⇒ ¬ (I ioco S)

Exhaustivité: ¬ (I ioco S) ⇒ on peut générer TC qui peut rejeter I

∥

?A

?B

!Z

!Y!X

?B

!X

I

Verdict: Fail, Pass, Inconc

15

Principes de la génération de tests

S

(S)Calcul des blocages !

Déterminisation

Produit: intersectionde comportement

Sélection + Mirroir + Ajout des verdicts

Conflits de contrôlabilité

!z

*

Accept

!x

*

Objectif de test :

automate complet

TracesAccept(TP)TP

CTG

TC

Vis(S)

Vis(S)xTP

TC

Algorithme non-déterministe

[Tretmans96][Lestiennes-Gaudel02]

!A ?

!B!A?

X

16

Étapes de la génération

AcceptPass reach(Init)

Inconc

!z

*

Accept

!x

*TP

?B

?A

?B

!Y

!X

!Z

SélectionVerdictsMirroir

CTG

Conflits de contrôlabilité

TC

reach(Init∩

coreach(Accept)

Init

!Z

?B

?otherwise

Fail

!B

!A

!B

?Y

?X

?Z

?A

?B

!Z

!Y!X

?B

Vis(S)) ?C

!Y

?C!Y

?C

!Y

?C!Y

Produit

Vis(S)xTP

17

Propriétés des tests générés

Correction: possibilité de rejet non conformité

“Exhaustivité”: non-conformité possibilité de rejet

Tests arborescents ⇒ adaptés au non-déterminisme observable

18

Génération à la voléeConstat : S très grand ou infini |S| |TC| ≫Idée: éviter de construire S

construction paresseuse de

S, (S), Vis(S), Vis(S)xTP,CTG

pilotée par TP

utilisation d’une représentation

implicite des IOLTS

algorithmes basés sur DFS

Cal

cul à

la v

olée

TP

CTG

S

(S)

TC

Spec

Vis(S)

19

Implémentation: TGV Expérimentations

dans des domaines

variés.

Distribution: CADP,

Agedis

Transfert:

ObjectGéode

Objectifde test bcg, IF

API de Simulation(primitives parcours de S)

UmlautObjectGéode

Caesar

open

IFopen

SpecificationUML SDL Lotos IF

TGV CA

DP lib

Cas de test (bcg, aut, TTCN, )

20

Résumé de la contribution Algorithmique de la génération de tests sur des

modèles énumérés

Fondée sur une théorie du test bien établie

Implémentation efficace: génération à la volée (TGV)

Largement publié

Transfert industriel (Telelogic)

21

I

3. Test asynchrone et test réparti

testeur

?a !x ?b ?d ?c !y !z

!a ?x!b !d!c ?y?z!e !f

Problèmes : Test asynchrone :

distorsion ⇒ perte d’information Test réparti :

coordination concurrence

Contributions : Inversion de la distorsion

par estampillage [JJTV-FP99]

Distribution de testeur+ consensus [JJKV-FP98]

22

4. Génération de tests symboliques[RBJ-IFM00, CJRZ-Tacas01, CJRZ-Esmart01,CJRZ-Esec01]

Motivations: Éviter l’explosion combinatoire ← données énumérées “Programmes” de test génériques (non instanciés)

Approche Modèle symbolique: IOSTS (~ autres modèles similaires)

Sémantique IOLTS ⇒ théorie du test identique

Génération symbolique:

S , TP ∈ IOSTS TC ∈ IOSTSSélection par utilisation de l’interprétation abstraite [Cousot77]

Exécution : Instanciation des entrées ← résolution de contraintes

23

Modèle IOSTS

Begin

Idle

Pay

Choose

Price >0

Return

Delivery

paid:=0

v > 0Coin?(v)

paid:=paid+v

paid < Price ∧d = paid - Price

Return!(d)

paid ≥ Price ∧d=paid - Price

Return!(d) paid:=Price

p =paid Return!(p)

Cancel?

Cancel?

Choose?(b)vb:=b

b = vbDeliver!(b)

Variable propre/observée

Constantesymbolique

paramètrede communication

Localitésval(l)

S TP

S0

Accept

mb=COFFEEDeliver!(mb)

Reject

paid < Price

Return?(m)

true

conditionInitiale

Empty!(b)

¬(mb=COFFEE)

Deliver!(mb)

Cancel?

24

Sémantique [[.]]: IOSTS IOLTS M [[M]]

(s0,1,0,0)(s0,1,0,1)(s0,1,0,2)(s0,1,0,3)(s0,2,0,0) (s0,2,0,1) (s0,2,0,2) (s0,2,0,3) ⊨

in?(1)

(2,s1,3,1)(2,s1,3,0) (2,s1,3,2) (2,s1,3,3)(2,s1,2,1)(2,s1,2,0) (2,s1,2,2) (2,s1,2,3)

in?(2)

s0

k>0

⌃ v1=0

s1

vo < k ⌃ x > 0 ⌃ (l=s0)in?(x) v1:= vo+ p; (l=s1)

Condition initiale

GardeAction(param.com.)Affectation

25

Opérations syntaxiques dont la sémantique commute avec les opérations sur les IOLTS :

Produit: xs

Calcul des blocages: s

Déterminisation: dets

Vis(PS) = dets(s(S xsTP ))Traces([[ dets(s(S xsTP)) ]]) = Traces(det(([[ S ]] xe [[ TP ]]))

Sélection : reach, coreach non calculables de manière exacte⇒ sur-approximations reach et coreach

Génération symbolique

M

ops(M)

[[M]]

[[ops(M) ]]

[[.]]

[[.]]

opsop

op[[M]]=

26

Conséquences de la sur-approximation

reach(∩

coreach(Accept)

Accept

reach()

?otherwise

Inconc

[[Vis(PS) ]] CTG

Fail

Sur-approximation[[CTG]]

Calcul exact ?

!

?

?

27

Exemple: calcul du produit Begin

Idle

Pay

Choose

Price >0

Return Delivery

paid:=0

v > 0Coin?(v)

paid:=paid+v

paid < Price ∧d = paid - Price

Return!(d)

paid ≥ Price ∧d =paid - Price

Return!(d)paid:=Price

p =paid Return!(p)

Cancel?

Cancel?

Choose?(b)vb:=b

b=vbDeliver!(b)

S

TPS0

Accept

mb=COFFEEDeliver!(mb)

Reject

paid < PriceReturn!(m)

true

¬(mb=COFFEE)Deliver!(mb)

Begin,s0

Idle,s0

Pay,s0

Choose,s0

Price >0

Delivery,s0

paid:=0

v > 0Coin?(v)

paid:=paid+vpaid < Price ∧

d = paid - Price Return!(d)

paid ≥ Price ∧d =paid - Price

Return!(d) paid:=Price

Cancel?

Cancel?

Choose?(b)vb:=b

b=COFFEE∧ b=vb

Deliver!(b)

PS

IdleReject

ReturnReject

BeginAccept

¬(b=COFFEE)∧ b=vb

Deliver!(b)

BeginReject

Cancel?

Empty!(b)

Empty!(b)

28

Sélection du graphe de test

Begin,s0

Pay,s0

Choose,s0

Price >0

Delivery,s0

v > 0Coin?(v) paid:=0+v

paid < Price ∧ d = paid - Price Return!(d)

paid ≥ Price ∧d =paid - PriceReturn!(d) paid:=Price

Cancel?paid:=0

Cancel?

Choose?(b)vb:=b

b=COFFEE∧ b=vbDeliver!(b)

Vis(PS)

IdleReject

ReturnReject

BeginAccept

¬(b=COFFEE)∧ b=vbDeliver!(b)

BeginReject

paid:=0

Idle,s0Cancel?

v > 0Coin?(v) paid:=paid+v

Empty!(b)

Begin,s0

Pay,s0

Choose,s0

Price >0

Delivery,s0

d =paid - PriceReturn?(d)paid:=Price

b=COFFEEChoose!(b)vb:=b

vb=COFFEE ∧ b=vbDeliver?(b)

Pass

paid:=0

Idle,s0

v ≥ PriceCoin!(v) paid:=v

v ≥ PriceCoin!(v) paid:=v

Fail

?otherwise

CTG

Inconc

vb= COFFEE∧ b=vb

Empty!(b)

?otherwise

29

Exécution: instanciation des constantes et résolution des gardes

Begin,s0

Pay,s0

Choose,s0

Price >0

Delivery,s0

d =paid - PriceReturn?(d)

b=COFFEEChoose!(b)vb:=b

vb=COFFEE ∧ b=vbDeliver?(b)

Pass

paid:=0

Idle,s0

v ≥ PriceCoin!(v) paid:=v

v ≥ PriceCoin!(v) paid:=v

Fail

?otherwise

CTG

Inconc

vb= COFFEE∧ b=vb

Empty!(b)

?otherwise

Implémentation IPrice = 40

Coin!(50)

Return? (10) ?otherwise

Fail

Choose!(COFFEE)

Deliver?(COFFEE)

Empty?(COFFEE)

PassInconc

?otherwise

Résolutionv ≥ Price

30

Outillage: STGGé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 : CEPS

Distribution : prévue fin 2004

IUT C++/Java

C++/JavaTest case

Test purposeSpecification

Générationde test

Compilation

dotty

Omegaverdict

NBAC

Test case

31

Contributions à la génération de tests symbolique

Originalité :

Génération de « programmes » de test

Traitement de systèmes non-déterministes

Théorie indépendante de l’approximation

Cadre formel :

⇒ garantie de propriétés des tests : correction, « exhaustivité »

Outillage (STG) : génération et exécution

Publications

32

5. BilanContribution originale à l’algorithmique de la

génération de tests Techniques énumératives à la volée Techniques symboliques Non déterminisme Asynchronisme et répartition

Cadre formel propriétés des tests

Outillage et expérimentations

Passage à l’échelle

33

Travaux connexesModèles voisins :

FSM, EFSM (voir e.g. [Lee-Yannakakis 96]) contrôle et données

Autres techniques à base d’objectifs :

MSC [Grabowski et al 93]Utilisation de model-checkers (e.g. [Engels et al-97, Hong-Lee et al. 01])

limités dans le traitement du non-déterminisme

Autres techniques symboliques :

Simulation symbolique + résolution de contraintes (pb de chemins)

Smile [Eertink94] TVeda [Clatin et al. 95], Agatha [Lugato et al. 02],

Gatel [Marre], BZ-TT [Legeard et al]

+ spec algébriques [Gaudel-James99, Lestiennes-Gaudel02],

Abstractions: EFSM [Petrenko et al 99-04]

34

Défis de la génération automatique de tests pour les systèmes réactifs

Accroître l’usage industriel des méthodes

formelles pour le test : ↗ qualité ↘ coûts

L’automatisation du test est un levier pour une meilleure

introduction des méthodes formelles dans l’industrie.

Passage à l’échelle de l’automatisation

traiter efficacement des systèmes plus complexes en taille

et expressivité

Méthodologies d’utilisation et de combinaison des

méthodes formelles

35

Perspectives

Accroître l’expressivité des modèles :

contrôle, données, concurrence, communication, temps

Améliorer les critères de sélection :

objectifs, couverture, hypothèses de sélection

Combiner les techniques pour la génération de tests :

model-checking, preuve, analyse statique, interprétation abstraite,

résolution de contraintes, ordres partiels,

Combiner les méthodes de validation dans le

processus de développement :

Vérifications statiques, contrôle, test

36

Quelques travaux en coursVérification et test de propriétés de sûreté

Tester violation d’une propriété de sûreté valide sur la spécification [RMTJJ-Testcom04]

Couverture en model-checking et génération de test [Hoskote et al. 99, Chockler et al. 01]

Propriétés couvrantes tests couvrants

Test de robustesse Tester la préservation de propriétés de sûreté en présence d’aléas

Contrôle et test Contrôler la conformité d’une implémentation

[JMRT-MSR03-CDC04-IJPR04]

37

Fin