Utilisation des Structures Combinatoires pour le Test Statistique

Plan Utilisation des Contexte Structures Combinatoires Structures combinatoires Test statistique et qualité de testpour le Test Statistique Nouvelle approche du test statistique Tirer des chemins Optimiser la qualité de test Validation de l’approche Le prototype AuGuSTeSandrine-Dominique GOURAUD Résultats expérimentaux Équipe “Programmation et Génie Logiciel”, L.R.I. Bilan et Perspectives Co-encadrants: M.-C. Gaudel et A. Denise 2 Les structures combinatoires décomposables La spécification de structures combinatoires consiste en un ensemble de règles de production construites à partir:Contexte 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) 4 Les structures combinatoires décomposables Le test de logiciel Résultats théoriques sur la génération aléatoire Objectif: trouver des fautes/erreurs dans uniforme de telles structures [Flajolet,Zimmermann,VanCutsem,1994] les programmes Complexité en n*log n pour des structures Comment? En exécutant le programme combinatoires de taille n sur un ensemble de données qu’on Complexité linéaire dans certains cas particuliers appelle jeu de test. Outils disponibles pour l’environnement MuPAD: Les difficultés: Le package CS [Corteel, Denise,Dutour,Sarron,Zimmermann] Trouver les bons jeux de test Le package MuPAD-Combinat [Thiery & al] Exécution et dépouillement Quand arrêter les tests (critère)? 5 6 1" ˛ Sélection d’un jeu de test? Sélection d’un jeu de test structurel/fonctionnel Pour sélectionner un jeu de tests, on part:Le test fonctionnel (boîte noire): sélection basée sur une spécification du système D’une modélisation du système/programme Ce que le système devrait faire… D’un critère de test adapté à cette modélisation Le test structurel (boîte de verre): sélection basée sur le programme i.e. on s’intéresse à Exemples: différents chemins d’exécution Spécification algébriques / Couverture des axiomes Ce que le programme fait et comment Système à transitions étiquetées / Couverture des arcs Le test statistique (ou aléatoire): sélection Texte du programme / Couverture des instructionsaléatoire (uniforme ou opérationnelle) dans le domaine des entrées du programme 7 8 Exemple: estTrie(tab,t) Exemple: estTrie Spécification: le programme prend en entrée INIT 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 $ EXITretourne faux. 9 10 Qualité d’un test statistique [TF,Wa] Pourquoi le test statistique? Soit E l’ensemble des éléments à couvrir Avantages: N le nombre de tests Possibilité de faire du test plus intensif qu’avec La qualité de test q est la probabilité minimale d’un les autres méthodes N élément de E d’être couvert lors des N tests Inconvénients: Nqq ==11--((11-- pp ))Mauvaise couverture des cas particuliers (ex: NN mmiinn où p = min{p(e), e E}cas d’exception) min Solution? Pour maximiser q , il faut maximiser pN min Le combiner avec une autre méthode de test Une solution (pas toujours possible): [Thévenod-Fosse,Waeselynck,1991]. Tirage uniforme dans E 11 12 2- ‡ ˇ - Relation entre N et q [TF,Wa] Le test Statistique Structurel [TF,Wa]N Construction d’une distribution sur le domaine des Nq =1-(1- p )N min entrées qui: Maximise la qualité de test donc la probabilité minimale d’atteindre un élément du critère de couverture Si je choisis de faire N tests, quelle sera structurel considéréma qualité de test q ?N N’écarte aucun point du domaine d’entrée Si je désire atteindre une qualité de test q , N Avantages: combien de tests suis-je censé effectuer? Bons résultats expérimentaux Inconvénients: & Distribution déterminée de manière empirique dans & % certains cas 13 14Avec p {0,1}min Objectif de cette thèse Nouvelle approche pour le Méthode de test statistique: qui s’applique à différents types de modélisation Test Statistique 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 15 Nouvelle approche pour le Test Statistique Test et structures combinatoires Première étape:Tirage aléatoire de chemins Tirer un ensemble de chemins tel que la qualité de test soit optimaleL’ensemble des chemins d’un graphe peut se représenter facilement sous forme d’une Remarque:spécification de structures combinatoires Idéalement, tirage parmi tous les chemins du graphe.Génération aléatoire de complexité linéaire En pratique, tirage dans un sous-ensemble de chemins: la présence de circuits dans le graphe implique une infinité de chemins. 2 étapes: En pratique, on limite la longueur n des chemins.1) Tirer un ensemble de chemins adéquat 2) Passer des chemins aux données d’entrée qui 17 18permettent de les parcourir 3Exemple: quel n choisir? Graphe et structure combinatoire v INIT INIT Atomes= arcs 1 vLongueur du chemin Séquence d’arcs= chemin élémentaire le plus long: 7 2 e 0 Choix de n pour la suite: 11 S= v.S + v.e .C.e0 73 5 ee e 5Nombre de passages dans la boucle 1 3S CC= e .e + e .B.e1 2 3 6entre 0 et 3 e4 4 B= e .I + 4 e e6 2 6 5 chemins de longueur 11 à I= e .B5considérer 7 e 7 EXIT 19 EXIT 20 Génération: dénombrement Génération: tirage v0 1 2 3 4 5 6 7 8 9 10 11 S= v.S + v.e .C.e INIT0 7 C= e .e + e .B.e1 2 3 6 v B= e .I + 4C 0 0 2 0 1 0 1 0 1 0 1 0 I= e .B S5 72?/3 1?/3 e0 vS ve C eB 1 0 1 0 1 0 1 0 1 0 1 0 6 0 4 7 0 1 1 ee e 5 1 3 vve C e vvS ve e B e e0 3 7 5 0 3 2 6 7I 0 1 0 1 0 1 0 1 0 1 0 1 0 e 41 e e62vvvS vvve C e3 0 2 7S 0 0 0 0 0 2 2 3 3 4 4 5 1/2 1/2 e 7vvve e e e vvve e e e ve e e e e e0 1 2 7 0 3 6 7 0 3 4 5 6 7 21 223 chemins issus de S de longueur 7 EXIT Longueur=7 Tirage de chemins Si le critère consiste à couvrir un ensemble de chemins : on Soit N le nombre de tests à générer. construit la structure combinatoire correspondante Exemples: 1. Tirer aléatoirement, selon une distribution tous les chemins passant par l’arc a, adéquate, N éléments e ,…,e parmi les tous les chemins passant par le sommet B3 puis par le sommet I4 1 N … éléments à couvrir Si le critère consiste à couvrir un ensemble d’éléments quelconque : ??? Exemples: 2. Pour chaque e , tirer aléatoirement et itous les sommets, tous les arcs uniformément un chemin (de longueur n) … parmi ceux qui passent par e . i Comment un tirage uniforme parmi des chemins peut-il assurer une bonne qualité de test pour une couverture d’autres éléments? 23 24 4£ · · · · „ £ · £ £ · £ · · „ · Exemple: Exemple: INIT INIT Critère: tous les sommets carrés Critère: tous les sommets carrés S={I2,I0,I4,I5} S={I2,I4}5 chemins de longueur 11. Distribution uniforme 5 chemins de longueur 11. p(I2)= 1/4 Distribution uniforme+1/4 1/5 +1/4 0 +1/4 1/5 p =0.5=7/20 = 0.35 min De même: p(I4)=11/20, p(I0)=1, p(I5)=1 EXIT EXITComment pourrais-je maximiser p =p(I2)= 0.35 min automatiquement le p ?min 25 26On n’obtient pas le p optimal !min Calcul des c(e,e’): exemple de c(B3,I4)Probabilité d’un élément v v INITINITLa probabilité p(e) d’un élément e d’être atteint lors vv d’une exécution est: p(e)=p (e)+p (e) e1 2 e 00 AProbabilité de tirer l’élément (étape 1): p (e)1 ee 55 eeUn chemin passant par cet élément a été tiré (étape 2): e 33 4X e e4 5 ( ’ ee4 4= ’ A) ( ’ e e6 6 ’ où e’ est l’élément qui a été tiré (étape 1), ee 7 7c(e’) est le nombre de chemins passant par e’ EXIT EXITc(e,e’) est le nombre de chemins passant par e et e’ On en déduit la structure combinatoire puis la fonction 27 28 de dénombrement Une manière de définir la distribution Maximiser p sous les contraintes min Pour optimiser la qualité de test, il faut + +% maximiser pmin. Or pour tout e de E, S =pmin( ’ + ’% + + % ( ’ ’ = + + + ) On résout ce problème d’optimisation par un simplex et on en déduit les p (e ).29 301 i 5˛ £ Exemple: Des chemins aux entrées Critère: tous les sommets carrés Deuxième étape: INIT Distribution uniforme pour les Déterminer les entrées permettant chemins d’exécuter les chemins tirés5 chemins de longueur 11. =% 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)* = ) 31 32EXIT Exemple: Des chemins aux entrées Spécification: t [0..6] Plusieurs cas possibles pour la Chemin I0-C1-I2-I5 Chemin I0-C1-B3-I5 résolution de chaque prédicat:Prédicat calculé: t 0 Prédicat calculé: (t>0) (t -1) Ce chemin est faisable Ce chemin est infaisable 1. Le prédicat a une solution: c’est notre Entrées possibles: donnée de test t=0 2. Le prédicat n’a pas de solution: le chemin tab arbitraires associé est infaisable 3. Le prédicat est indéterminé Le calcul théorique des p (e ) ne prend 1 i pas en compte les chemins infaisables 33 34 Application au test statistique structurel Modèle: graphe de contrôle du programme Critères: Validation de l’approche Tous les chemins de longueur n Tous les enchaînements Toutes les instructions 1Un prototype: AuGuSTe Version 1: distribution basée sur les dominances Version 2: distribution basée sur la résolution du système linéaire 36 1: Automated Generation of Statistical Tests 6,1/ Les expériences + ! & %% , ( -( ( ( % ! & ! ( . Objectifs: valider l’approche Comparer à l’approche du LAAS Évaluer la stabilité Passage à l’échelle possible? & ! /( % ! & - -& 0 Comment? En utilisant les programmes et les mutants fournis par le 1 ( ! -!( ( - 2( % - LAAS 3- !% - ! -!( ( - 2( % Plus de 10000 exécutions réalisées sur plus 2900 mutants 6 / 4( (5 37 38 4 % ! ! - ! Évaluation par mutation des méthodes de testLes programmes Principe: détecter le maximum de mutants Nom #lignes #chemins #blocs