La lecture en ligne est gratuite
Descargar

Compartir esta publicación

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 #arcs #choix « non équivalents » La proportion de mutants détectés est Fct1 30 17 14 24 5 appelée score de mutation Fct2 43 9 12 20 4 La notion d’équivalence dépend en partie Fct3 135 33 (14) 19 41 12 de l’environnement d’exécution des tests Exemple: présence de variables non initialisées Fct4 77 infini 19 41 12 Mutants équivalents différents 39 40 Les programmes et leurs mutants Les programmes et leurs mutants Nom #mutants #mutants équivalents Nom #mutants #mutants équivalents Fct1 265 14+3Fct1 265 14 Fct2 548 6+9Fct2 548 6+9 Fct3 1416 21+30 Fct3 1416 21+30+16 Fct4 587 9+9 Fct4 587 9+9+49 41 42 7 · ‡ ‡ Critère de couverture, q et N Résultats pour Fct1, Fct2 et Fct3N Score de mutationNom Critère choisi #tests Uniforme LAAS AuGuSTeFct1 Tous les chemins 170 Fct1 1 1 1Fct2 Tous les chemins 80 Fct2 1 1 1Fct3 Tous les chemins 5x405 Fct4 Tous les enchaînements 5x850 Min 0.55 1 0.9951 Fct3 Moy 0.698 1 0.9989Qualité de test visée: 0.9999 Max 0.85 1 1Fct3 et Fct4: pour s’assurer de la stabilité, il y a 5 séries de tests. Fct3: Reflète la dépendance vis-à-vis de l’environnement 43 44 Lié aux variables non initialisées détectables par un bon compilateur Graphe de contrôle de FCT4 Première expérience avec Fct4… 20 10 chemins dont 99,98% de chemins infaisables NB_VOIES=18 AuGuSTe (v1): NUM_VOIE p =0.5 < NB_VOIES min Mais en pratique tous les enchaînements ne NB_VOIES=19 SE_VOIE_EN_TEST=TRUE sont pas couverts EXIT AuGuSTe (v2): Choix de n? p =0.5min n 6+12 19 Mais en pratique, tous les enchaînements ne soit n 234 sont pas couverts Distribution sur les éléments tirage uniforme 30Soit plus de 10 chemins à considérer parmi les chemins Présence d’un nombre considérable de chemins infaisables 45 46 NB_VOIES=18 Résultats pour Fct4: expérience 2pmin NUM_VOIE < NB_VOIES Uniforme LAAS AuGuSTe(v1) AuGuSTe(v2) Min 0.895 0.9898 0.9726 0.9854NB_VOIES=19 SE_VOIE_EN_TEST=TRUE EXIT Moy Nc 0.9901 0.9773 0.9854 Max 0.915 0.9915 0.9854 0.9854 Graphe équilibré => Tirage uniforme parmi 16Environ 10 chemins de longueur 234 les chemins Environ 50% de chemins infaisables AuGuSTe (v1): p =0.3324 min Deux sous-graphes indépendants mauvaise couverture Mais en pratique, tous les enchaînements ne sont pas forcément couverts AuGuSTe (v2): p =0.492347 48minIdée: Transformation automatique de la structure combinatoire En pratique, tous les enchaînements sont couverts 8 INIT INIT S c o r e d e m u t a t i o n Contribution Première utilisation des méthodes de tirage uniforme dans les structures combinatoires pour le test de logiciel Bilan et Perspectives 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 50 Perspectives (1/2) Perspectives (2/2) Adapter/améliorer la distribution des p (e ) en Mieux exploiter les structures combinatoires 1 i fonction des différents problèmes rencontrés: pour limiter les chemins infaisables Les chemins infaisables Analyse statique Méthodes d’apprentissage [Sebag & al] Meilleure distribution Méthodes probabilistes [Maume & al] Borner la longueur des chemins peut masquer des erreurs Application à d’autres techniques Méthode Boltzmann [Duchon,Flajolet,Louchard,Schaeffer,2002] Test statistique fonctionnel Prendre en compte plus d’aspects sémantiques Model checkingExemple: les cas exceptionnels doivent-ils être autant testés que les cas standards? 51 52 Modification de la structure combinatoire Des questions? 53 54 9 Distribution basée sur les dominances (1/2) Distribution basée sur les dominances (2/2) Choisir un représentant des classes I0,C1,I5Classe d’équivalence aux feuilles Une classe A domine une classe B, si tout S={I2,I4} I2 B3 chemin qui passe par les éléments de B Rajouter éventuellement à S un passe par les éléments de A représentant de la classe racine. I4 I0,C1,I5 S={I2,I4,I0} Faire du tirage uniforme dans I2 B3 l’ensemble S. p =0.4min I4 55 56 10