Utilisation des Structures Combinatoires

pour le Test Statistique

Sandrine-Dominique GOURAUDÉquipe “Programmation et Génie Logiciel”, L.R.I.

Co-encadrants: M.-C. Gaudel et A. Denise

2

Plan

Contexte Structures combinatoires Test statistique et qualité de test

Nouvelle approche du test statistique Tirer des chemins Optimiser la qualité de test

Validation de l’approche Le prototype AuGuSTe Résultats expérimentaux

Bilan et Perspectives

Contexte

4

Les structures combinatoires décomposables

La spécification de structures combinatoires consiste en un ensemble de règles de production construites à partir: d’objets de base: ε (de taille 0) et atome (de taille 1) d’opérateurs: union(+), produit(x), sequence, etc. de contraintes de cardinalité

Exemples: Arbre binaire complet non vide: A= F+ AxA

où F est l’atome de base représentant une feuille Séquence de 3 à 5 feuilles: S= Sequence(F,Card=3..5)

5

Les structures combinatoires décomposables

Résultats théoriques sur la génération aléatoire uniforme de telles structures [Flajolet,Zimmermann,VanCutsem,1994]

Complexité en n*log n pour des structures combinatoires de taille n

Complexité linéaire dans certains cas particuliers Outils disponibles pour l’environnement MuPAD:

Le package CS [Corteel, Denise,Dutour,Sarron,Zimmermann] Le package MuPAD-Combinat [Thiery & al]

6

Le test de logiciel

Objectif: trouver des fautes/erreurs dans les programmes

Comment? En exécutant le programme sur un ensemble de données qu’on appelle jeu de test.

Les difficultés: Trouver les bons jeux de test Exécution et dépouillement Quand arrêter les tests (critère)?

7

Sélection d’un jeu de test?

Le test fonctionnel (boîte noire): sélection basée sur une spécification du systèmeCe que le système devrait faire…

Le test structurel (boîte de verre): sélection basée sur le programme i.e. on s’intéresse à différents chemins d’exécutionCe que le programme fait et comment

Le test statistique (ou aléatoire): sélection aléatoire (uniforme ou opérationnelle) dans le domaine des entrées du programme

8

Sélection d’un jeu de test structurel/fonctionnel

Pour sélectionner un jeu de tests, on part:D’une modélisation du système/programmeD’un critère de test adapté à cette modélisation

Exemples: Spécification algébriques / Couverture des axiomes Système à transitions étiquetées / Couverture des

arcs Texte du programme / Couverture des instructions

9

Exemple: estTrie(tab,t)

Spécification: le programme prend en entrée un tableau tab d’au plus 6 entiers et un nombre 0≤ t ≤6.

Si les t premières valeurs du tableau tab sont triés en ordre croissant, alors il retourne vrai.

Si les t premières valeurs du tableau tab ne sont pas triés en ordre croissant, alors il retourne faux.

10

Exemple: estTrie

bool estTrie (tab: array 0..5 of int, t: int){ int i:=0; bool rep:=true; if (t≤0) then rep:= true; else{

while ((i<t+1) and rep){ rep:= tab[i]≤tab[i+1]; i:= i+1; } } return rep;}

INIT

EXIT

I0

C1

I2

I5

I4B3

11

Pourquoi le test statistique?

Avantages: Possibilité de faire du test plus intensif qu’avec

les autres méthodes

Inconvénients: Mauvaise couverture des cas particuliers (ex:

cas d’exception)

Solution? Le combiner avec une autre méthode de test

[Thévenod-Fosse,Waeselynck,1991].

12

Qualité d’un test statistique [TF,Wa]

Soit E l’ensemble des éléments à couvrir N le nombre de tests

La qualité de test qN est la probabilité minimale d’un élément de E d’être couvert lors des N tests

qqNN =1-(1- p =1-(1- pminmin))NN

où pmin = min{p(e), eE}

Pour maximiser qN, il faut maximiser pmin

Une solution (pas toujours possible):

Tirage uniforme dans E

13

Relation entre N et qN [TF,Wa]

qqNN =1-(1- p =1-(1- pminmin))NN

Si je choisis de faire N tests, quelle sera ma qualité de test qN?

Si je désire atteindre une qualité de test qN, combien de tests suis-je censé effectuer?

Avec pmin{0,1}

)min1log(

)1log(

p

qNN

14

Le test Statistique Structurel [TF,Wa]

Construction d’une distribution sur le domaine des entrées qui: Maximise la qualité de test donc la probabilité minimale

d’atteindre un élément du critère de couverture structurel considéré

N’écarte aucun point du domaine d’entrée Avantages:

Bons résultats expérimentaux Inconvénients:

Distribution déterminée de manière empirique dans certains cas

15

Objectif de cette thèse

Méthode de test statistique: qui s’applique à différents types de modélisation

représentable sous forme de graphes, qui optimise la qualité de test par rapport à un

critère donné, qui est automatisée

Apport possible des structures combinatoires pour le test

Nouvelle approche pour le Test Statistique

17

Nouvelle approche pour le Test Statistique

Tirage aléatoire de cheminsTirage aléatoire de chemins

L’ensemble des chemins d’un graphe peut se représenter facilement sous forme d’une spécification de structures combinatoires

Génération aléatoire de complexité linéaire

2 étapes:1) Tirer un ensemble de chemins adéquat2) Passer des chemins aux données d’entrée qui

permettent de les parcourir

18

Test et structures combinatoires

Première étape:Tirer un ensemble de chemins

tel que la qualité de test soit optimale

Remarque: Idéalement, tirage parmi tous les chemins du graphe. En pratique, tirage dans un sous-ensemble de chemins:

la présence de circuits dans le graphe implique une infinité de chemins.

En pratique, on limite la longueur n des chemins.

19

Exemple: quel n choisir?

Longueur du chemin élémentaire le plus long: 7

Choix de n pour la suite: 11 Nombre de passages dans la boucle

entre 0 et 3

5 chemins de longueur ≤11 à considérer

INIT

EXIT

I0

C1

I2

I5

I4B3

2

3 5

46

1

7

20

Graphe et structure combinatoire

Atomes= arcs

Séquence d’arcs= chemin

S= v.S + v.e0.C.e7

C= e1.e2 + e3.B.e6

B= e4.I + ε

I= e5.B

INIT

EXIT

I0

C1

I2

I5

I4B3

v

e1

e2

v

e0

e3e5

e4

e6

e7

S C

21

Génération: dénombrement

0 1 2 3 4 5 6 7 8 9 10 11

C 0 0 2 0 1 0 1 0 1 0 1 0

B 1 0 1 0 1 0 1 0 1 0 1 0

I 0 1 0 1 0 1 0 1 0 1 0 1

S 0 0 0 0 0 2 2 3 3 4 4 5

3 chemins issus de S de longueur 7

22

Génération: tirage

Longueur=7

INIT

EXIT

I0

C1

I2

I5

I4B3

v

e1

e2

v

e0

e3e5

e4

e6

e7vvve0e1e2e7 vvve0e3e6e7 ve0e3e4e5e6e7

S7

vS6 ve0C4e7

ve0e3B2e6e7vvS5

vvve0C2e7

S= v.S + v.e0.C.e7

C= e1.e2 + e3.B.e6

B= e4.I + εI= e5.B

vve0C3e7

vvvS3

? ?

1

1

0

0

1

2/3 1/3

1/21/2

23

Si le critère consiste à couvrir un ensemble de chemins : on construit la structure combinatoire correspondante

Exemples: tous les chemins passant par l’arc a,tous les chemins passant par le sommet B3 puis par le sommet I4…

Si le critère consiste à couvrir un ensemble d’éléments quelconque : ???

Exemples:tous les sommets, tous les arcs …

Comment un tirage uniforme parmi des chemins peut-il assurer une bonne qualité de test pour une couverture d’autres éléments?

24

Tirage de chemins

Soit N le nombre de tests à générer.

1. Tirer aléatoirement, selon une distribution adéquate, N éléments e1,…,eN parmi les éléments à couvrir

2. Pour chaque ei, tirer aléatoirement et uniformément un chemin (de longueur ≤ n) parmi ceux qui passent par ei.

25

Exemple:

Critère: tous les sommets carrés S={I2,I0,I4,I5} 5 chemins de longueur 11. Distribution uniforme

p(I2)= 1/4 +1/41/5 +1/40 +1/41/5 =7/20 = 0.35

De même: p(I4)=11/20, p(I0)=1, p(I5)=1

pmin=p(I2)= 0.35

On n’obtient pas le pmin optimal !

INIT

EXIT

I0

C1

I2

I5

I4B3

26

Exemple:

Critère: tous les sommets carrésS={I2,I4}5 chemins de longueur 11.Distribution uniforme

pmin=0.5

Comment pourrais-je maximiser automatiquement le pmin?

INIT

EXIT

I0

C1

I2

I5

I4B3

27

Probabilité d’un élément

La probabilité p(e) d’un élément e d’être atteint lors d’une exécution est:

p(e)=p1(e)+p2(e) Probabilité de tirer l’élément (étape 1): p1(e) Un chemin passant par cet élément a été tiré (étape 2):

où e’ est l’élément qui a été tiré (étape 1),

c(e’) est le nombre de chemins passant par e’

c(e,e’) est le nombre de chemins passant par e et e’

e'e)'(1)'c(

)',c()(2 ep

eee

ep

28

Calcul des c(e,e’): exemple de c(B3,I4)

On en déduit la structure combinatoire puis la fonction de dénombrement

INIT

EXIT

I0

C1

I5

I4B3

v

v

e0

e3

e5

e4

e6

e7

X

INIT

EXIT

I0

C1

I5

I4B3

v

v

e0

e3

e5

e4

e6

e7

B3 I4e5

e4A

A

e4

29

Une manière de définir la distribution

Pour optimiser la qualité de test, il faut maximiser pmin.

Or pour tout e de E,

e'e)'(1)'c(

)',c()(1min ep

eee

epp

30

Maximiser pmin sous les contraintes

On résout ce problème d’optimisation par un simplex et on en déduit les p1(ei).

)(1...)2(1)1(11

)(1)(

),(...)1(1)1(

)1,(min

...

)(1)(

),1(...)1(1)1(

)1,1(min

e Epepep

e Epe Ec

e Ee Ecep

ec

ee Ecp

e Epe Ec

e Eecep

eceec

p

Spmin=

31

Exemple:

Critère: tous les sommets carrés Distribution uniforme pour les

chemins 5 chemins de longueur 11.

21

)4(1

21

)2(1

21

min

Ip

Ip

p

INIT

EXIT

I0

C1

I2

I5

I4B3

32

Des chemins aux entrées

Deuxième étape:

Déterminer les entrées permettant

d’exécuter les chemins tirés

Construction des prédicats associés aux chemins tirés (algorithme classique).

Résolution des prédicats (problème indécidable dans le cas général)

33

Exemple: Spécification: t[0..6] Chemin I0-C1-I2-I5 Prédicat calculé: t≤0

Ce chemin est faisable Entrées possibles:

t=0 tab arbitraires

Chemin I0-C1-B3-I5 Prédicat calculé: (t>0) (t≤-1)

Ce chemin est infaisable

I0

C1

I2

I5

I4B3

I0

C1

I2

I5

I4B3

34

Des chemins aux entrées

Plusieurs cas possibles pour la résolution de chaque prédicat:

1. Le prédicat a une solution: c’est notre donnée de test

2. Le prédicat n’a pas de solution: le chemin associé est infaisable

3. Le prédicat est indéterminé

Le calcul théorique des p1(ei) ne prend pas en compte les chemins infaisables

Validation de l’approche

36

Application au test statistique structurel

Modèle: graphe de contrôle du programme Critères:

Tous les chemins de longueur ≤n Tous les enchaînements Toutes les instructions

Un prototype: AuGuSTe1

Version 1: distribution basée sur les dominances Version 2: distribution basée sur la résolution du

système linéaire

1: Automated Generation of Statistical Tests

37

AuGuSTeÀ partir du programme P, on construit la spécification combinatoire du graphe de contrôleConstruction de l’ensemble des éléments à tirer en fonction de CPour chaque élément, construire l’ensemble des chemins passant par cet élémentDéterminer la distribution sur les éléments

Tirage des N élémentsTirage des N chemins de longueur inférieure ou égale à n

Construction des prédicats associés aux chemins tirésRésolution randomisée des prédicats associés aux chemins

Echec?Oui Non

Ensemble de données de test

P,C,N,n

38

Les expériences

Objectifs: valider l’approche Comparer à l’approche du LAAS Évaluer la stabilité Passage à l’échelle possible?

Comment? En utilisant les programmes et les mutants fournis par le

LAAS Plus de 10000 exécutions réalisées sur plus 2900

mutants

39

Les programmes

Nom #lignes #chemins #blocs #arcs #choix

Fct1 30 17 14 24 5

Fct2 43 9 12 20 4

Fct3 135 33 (14) 19 41 12

Fct4 77 infini 19 41 12

40

Évaluation par mutation des méthodes de test

Principe: détecter le maximum de mutants « non équivalents »

La proportion de mutants détectés est appelée score de mutation

La notion d’équivalence dépend en partie de l’environnement d’exécution des testsExemple: présence de variables non initialisées

Mutants équivalents différents

41

Les programmes et leurs mutants

Nom #mutants #mutants équivalents

Fct1 265 14

Fct2 548 6+9

Fct3 1416 21+30

Fct4 587 9+9

42

Les programmes et leurs mutants

Nom #mutants #mutants équivalents

Fct1 265 14+3

Fct2 548 6+9

Fct3 1416 21+30+16

Fct4 587 9+9+49

43

Critère de couverture, qN et N

Nom Critère choisi #tests

Fct1 Tous les chemins 170

Fct2 Tous les chemins 80

Fct3 Tous les chemins 5x405

Fct4 Tous les enchaînements 5x850

Qualité de test visée: 0.9999 Fct3 et Fct4: pour s’assurer de la stabilité, il y a

5 séries de tests.

44

Résultats pour Fct1, Fct2 et Fct3

Score de mutation

Uniforme LAAS AuGuSTe

Fct1 1 1 1

Fct2 1 1 1

Fct3

Min 0.55 1 0.9951

Moy 0.698 1 0.9989

Max 0.85 1 1

Fct3: Reflète la dépendance vis-à-vis de l’environnement Lié aux variables non initialisées détectables par un bon compilateur

45

Graphe de contrôle de FCT4

Choix de n?n6+1219 soit n234

Soit plus de 1030 chemins à considérerPrésence d’un nombre considérable de chemins infaisables

46

Première expérience avec Fct4… 1020 chemins dont 99,98% de chemins infaisables AuGuSTe (v1):

pmin=0.5 Mais en pratique tous les enchaînements ne

sont pas couverts AuGuSTe (v2):

pmin=0.5 Mais en pratique, tous les enchaînements ne

sont pas couverts Distribution sur les éléments tirage uniforme

parmi les chemins

47

Graphe équilibré

=> Tirage uniforme parmi

les chemins

Deux sous-graphes indépendants mauvaise couverture

Idée: Transformation automatique de la structure combinatoire

pmin

48

Résultats pour Fct4: expérience 2

Environ 1016 chemins de longueur ≤234 Environ 50% de chemins infaisables AuGuSTe (v1): pmin =0.3324

Mais en pratique, tous les enchaînements ne sont pas forcément couverts

AuGuSTe (v2): pmin =0.4923 En pratique, tous les enchaînements sont couverts

Uniforme LAAS AuGuSTe(v1) AuGuSTe(v2)

Min 0.895 0.9898 0.9726 0.9854

Moy Nc 0.9901 0.9773 0.9854

Max 0.915 0.9915 0.9854 0.9854

Sco

re d

e m

utat

ion

Bilan et Perspectives

50

ContributionPremière utilisation des méthodes de tirage

uniforme dans les structures combinatoires pour le test de logiciel Définition une méthode générale et automatisée

pour le test statistique Importante campagne d’expériences

Expériences aux résultats positifs: Efficacité comparable à celle du LAAS et

automatisation Approche stable Passage à l’échelle possible

51

Perspectives (1/2)

Adapter/améliorer la distribution des p1(ei) en fonction des différents problèmes rencontrés: Les chemins infaisables

Méthodes d’apprentissage [Sebag & al]Méthodes probabilistes [Maume & al]

Borner la longueur des chemins peut masquer des erreurs

Méthode Boltzmann [Duchon,Flajolet,Louchard,Schaeffer,2002]

Prendre en compte plus d’aspects sémantiquesExemple: les cas exceptionnels doivent-ils être autant testés que les

cas standards?

52

Perspectives (2/2)

Mieux exploiter les structures combinatoires pour limiter les chemins infaisables Analyse statique

Meilleure distribution

Application à d’autres techniques Test statistique fonctionnel Model checking