Localisation automatique de bugs

Un article de Wikipédia, l'encyclopédie libre.

La localisation automatisée de bug dans les logiciels informatiques est une activité du génie logiciel consistant à détecter des défauts pouvant provoquer des dysfonctionnements dans un programme. Son objectif est la réduction de l'effort du développeur lors de la phase de correction.

Cette recherche peut être menée à bien par une analyse statique ou dynamique. En ce qui concerne l'analyse dynamique, elle porte sur l'étude de traces d'exécution du programme.

Cette étude consiste à collecter des données lors de l'exécution du programme afin de déterminer la localisation probable du bug.

Localisation sur la base de traces d'exécution[modifier | modifier le code]

La localisation automatique de bug s'intègre au processus de corrections de bug comportant les étapes suivantes :

  1. constater le bug
  2. reproduire le bug via des tests automatisés
  3. localiser automatiquement le bug sur la base de tests automatisés en vue d'en déterminer l'origine. Pour ce faire, lors de l'exécution des tests, les données suivantes sont collectées :
    •  : le nombre de tests exécutant l'entité étudiée qui ont échoué (f pour failed)
    •  : le nombre de tests exécutant l'entité étudiée qui ont réussi (p pour passed)
    •  : le nombre de tests n'exécutant pas l'entité étudiée qui ont échoué (f pour failed)
    •  : le nombre de tests n'exécutant pas l'entité étudiée qui ont réussi (p pour passed)
  4. corriger le bug.

Les données peuvent être collectées à différents niveaux de granularité tels que: la ligne, le bloc, la fonction, la classe, voir le paquet.

Un exemple de collecte de données
Test 1 Test 2 Test 3 Test 4
Ligne 1 Exécutée Exécutée Exécutée 2 1 0 1
Ligne 2 Exécutée Exécutée Exécutée 1 2 1 0
Ligne 3 Exécutée Exécutée 1 1 1 1
...
Résultats des tests Réussi Réussi Échoué Échoué

Dans l'exemple ci-dessus, La ligne 1 est exécutée par les Tests 1, 3 et 4, deux de ces tests ont échoué () et un a réussi (), tous les tests échoués ont exécuté cette ligne () et un test réussi n'exécute pas cette ligne (). La ligne 2 est exécutée par les Tests 1, 2 et 4, un de ces tests a échoué () et deux ont réussi (), un test échoué n'exécute pas cette ligne () et tous les tests réussis exécutent cette ligne ().

Métriques[modifier | modifier le code]

Les métriques permettent de calculer une distance entre une entité du code (la ligne, le bloc, la fonction, la classe) et un bug. Il existe différentes métriques. Les entités peuvent alors être triées en fonction de ces distance, celles les plus proches du bug contiennent plus probablement du bug, celles les plus éloignées ne sont probablement pas la cause du bug. Sur la base de ce tri, le développeur peut ensuite parcourir les différentes entités en commençant par les plus proches jusqu'à ce que l'entité fautive soit trouvée. Ainsi, si la métrique est efficace, le développeur trouvera plus rapidement la source de l'erreur que par une recherche manuelle.

La plus vieille des métriques communément utilisées est Jaccard[1] (1901) qui, destinée à l'origine au domaine de la botanique, est à présent utilisée dans des domaines variés. La botanique a également inspiré de nombreuses métriques telles que Ochiai[2] (1957), Russel and Rao[3] (1940), Sørensen and Dice[4] (1945), Rogers and Tanimoto[5] (1960), Anderberg[6] (1973) et Simple-Matching[7] (2004). La métrique Hamming[8] (1950) a, quant à elle, été créée pour la détection et la correction d'erreur de code et la métrique Goodman and Kruskal[9] dans le domaine de la biométrie. Le domaine des cartes auto adaptatives a introduit les métriques[10] Kulczynski1, Kulczynski2, Hamann et Sokal. Par ailleurs, plusieurs métriques ont été directement créées pour la localisation automatique de bug: Tarantula[11], Ample[12], Zoltar[13] et Wong1-3[14].

Liste des métriques[modifier | modifier le code]

Le tableau ci-après reprend les principales métriques qui utilisent les données présentées ci-dessus pour la localisation de bug.

Nom Formule Nom Formule
Jaccard[1] Ample[12]
Sørensen Dice[4] Dice[15]
Kulczynski1 Kulczynski2
Russell and Rao[3] Tarantula[11]
Simple Matching[7] Hamann
M1[16] M2[16]
Rogers & Tanimoto[5] Sokal
Hamming[8] Goodman[9]
Ochiai[2] Euclid
Ochiai2[17] Anderberg[6]
Wong1[14] Zoltar[13]
Wong3[14] Wong2[14]

Alternative: analyse des prédicats[modifier | modifier le code]

Une approche alternative à la collecte des entités exécutées est proposée par Libit et al.[18], elle consiste à analyser les prédicats à la place des entités exécutées (lignes, blocs, classes...). Un prédicat intéressant peut être une condition, un retour de valeur... Lors de l'exécution des tests sont collectés les prédicats exécutés ainsi que ceux qui ont une valeur vraie. Ces données sont ensuite utilisées dans des métriques qui permettent de trier les prédicats en fonction de leur implication dans les tests échoués.

Voici une des métriques introduites par Libit et al.[18] :

et

.

Combiner les métriques[modifier | modifier le code]

Des études empiriques[17],[19],[20] ont montré qu'aucune métrique n'est parfaite. Une solution possible pour améliorer l'efficacité de la localisation automatique de bug est de combiner les métriques. Wang et al.[21] proposent une approche search-based algorithms (en), Jifeng Xuan et al.[22] proposent une combinaison de métriques générées par apprentissage automatique.

Comparaison des métriques[modifier | modifier le code]

Naish et al.[17] proposent un classement de métriques sur des données standardisées, les comparant sur les performances et la fiabilité. Il en ressort que les algorithmes proposés par Naish et al.[17] sont un meilleur compromis entre les performances et la fiabilité tel que Wong3[14], Zoltar[13], M2[16] et Ochiai[2].

Les résultats expérimentaux de Jifeng Xuan et al.[22] réalisés sur 10 projets open-source montrent que la combinaison des métriques peut améliorer jusqu'à 50% l'efficacité de la localisation des bugs. Cependant ils montrent également que les résultats obtenus grâce à Ochiai[2] et Ample[12] sont bons. Ces résultats contrastent avec ceux de Naish et al.[17] car selon Jifeng Xuan et al.[22] les suppositions de Naish et al.[17] sur les données ne s'appliquent pas aux cas réels.

Outils[modifier | modifier le code]

Les outils permettant la localisation de bug sont disponibles sous forme de logiciel en standalone ou de plugins pour IDE.

Pinpoint[modifier | modifier le code]

Pinpoint[23] est un framework Java EE pour la localisation de bug dans les systèmes distribués.

Son utilisation est destinée à la localisation de bug dans les applications complexes où divers composants, sains ou fautifs, interagissent pour répondre à la requête d'un client. Ce framework a été développé à l'origine pour pallier les faiblesses des systèmes de localisation de bug par analyse statique.

En effet, les besoins de dynamisme dans les applications complexes (équilibrage de charge, passage à l'échelle...) sont difficiles à prévoir lors d'une analyse statique.

Son fonctionnement se déroule en deux phases :

  1. L'observation des requêtes émises par les clients et des composants du système impliqués dans les réponses à ces requêtes,
  2. L'analyse et le recoupement des erreurs trouvées dans les traces obtenues à l'étape précédente par clustering pour identifier les composants à l'origine du bug.

L'analyse permet de mettre en lumière le composant ou les combinaisons de composants susceptibles d'être à l'origine des comportements erronés du système.

Plusieurs limitations peuvent compliquer la localisation des bugs :

  1. En cas de couplage fort entre un composant fautif et un composant sain, Pinpoint considèrera les deux composants comme sources potentielles du bug.
  2. Pinpoint fait la supposition que les bugs apparaissant dans le système ne corrompent pas l'état de ce dernier. Or, il est rarement possible d'être certain qu'un bug apparu lors d'une requête précédente ne puisse influencer les requêtes au système dans le futur. Ainsi, une erreur dans le service de création de comptes pourrait entraîner un bug pour l'utilisateur lors de l'authentification auprès du système.
  3. La qualité des requêtes envoyées par le client n'est pas évaluée. Il est donc impossible pour Pinpoint de savoir si un bug est provoqué par une requête incohérente du client ou par une faute du serveur.
  4. Les erreurs rattrapées au vol par le système durant son exécution ne sont pas enregistrées par Pinpoint et ce même si la performance de la réponse à une requête en est affectée.

Tarantula[modifier | modifier le code]

Tarantula[24] est à la fois une métrique et un outil proposé pour la première fois en 2001 par des chercheurs de Georgia Institute of Technology. Il a été développé dans le but de fournir un programme standalone de visualisation des lignes de code de l'ensemble d'un programme.

Les lignes de codes du programme étudié y sont colorées en suivant une formule indiquant leur degré de soupçons. En plus de la couleur, variant du vert pour les lignes non suspectes au rouge pour les plus suspectes, une teinte renseigne le nombre de fois où la ligne a effectivement été exécutée par la suite de tests.

Ces deux informations sont combinées pour produire un affichage renseignant sur le degré de soupçon associé à chaque ligne.

AMPLE[modifier | modifier le code]

AMPLE (pour Analyzing Method Patterns to Locate Errors) est un outil pour la localisation de bug dans les logiciels écrits en Java développé par des chercheurs de l'Université de la Sarre en 2005. Son approche se veut orientée objet avec la classe comme unité d'étude.

Implémenté sous la forme d'un plugin pour Eclipse, il s'intègre avec des frameworks tels que JUnit pour collecter les résultats d'exécution d'une suite de tests.

Son fonctionnement se base sur l'étude des séquences d'appels entre les méthodes exécutées pendant les tests. En comparant les séquences entre l'exécution d'un test réussi et d'un test échoué, AMPLE oriente le développeur vers la source probable du problème. En effet, les séquences ou morceaux de séquences présents dans les 2 exécutions sont moins susceptibles de porter des erreurs que les méthodes appelées uniquement dans l'exécution fautive.

Les séquences sont comparées sur une longueur k, choisie en fonction du niveau de granularité souhaité. Pour chaque séquence trouvée dans l'exécution échouée et absente dans l'exécution réussie, on extrait la classe matrice de l'objet sur lequel les appels manquants sont faits. À la fin de la comparaison, les classes sont ordonnées par nombre moyen d'apparition unique dans les exécutions échouées.

GZoltar[modifier | modifier le code]

GZoltar[25] est un framework de localisation de bug initialement créé en 2010 et disponible sous la forme d'un plugin Eclipse.

Cet outil apporte une option de visualisation et une meilleure intégration à l'environnement du développeur à Zoltar[26], un framework initialement développé par des chercheurs de l'Université de technologie de Delft.

Le développement avait alors débouché sur un logiciel produisant une sortie textuelle ainsi qu'une interface non intégrée sous la forme de XZoltar[25]. Le code de GZoltar se veut ré-utilisable par les autres développeurs sous la forme d'une bibliothèque[27]. Comme d'autres plugins comme AMPLE, il s'intègre à Eclipse pour exploiter les résultats produits par des frameworks de tests tels que JUnit.

Il se sert principalement de la métrique Ochiai pour évaluer la suspicion des lignes de code et produit ensuite un rendu graphique du résultat. Les calculs de suspicion sont faits par Zoltar en utilisant la métrique Ochiai et le résultat est rendu en 3D à l'aide d'OpenGL.

EzUnit[modifier | modifier le code]

EzUnit[28] est un framework pour la localisation de bug initialement développé en 2007 sous la forme d'un plugin Eclipse.

Il s'intègre à l'environnement du développeur en proposant le lancement des tests écrits à l'aide d'un framework de test tel que JUnit. EzUnit4[29], la version la plus récente offre une option de visualisation des graphes d'appels.

Les nœuds du graphe produit sont alors colorés en fonction du degré du suspicion sur les appels de méthode. La coloration varie du vert au rouge pour indiquer la localisation probable du bug.

Articles connexes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. a et b Paul Jaccard 1901, p. 547--579
  2. a b c et d Akira Ochiai 1957, p. 526–530
  3. a et b Paul F RUSSELL, T Ramachandra Rao et others 1940, p. 153–178
  4. a et b T. Sørensen 1948, p. 1–34
  5. a et b David J. Rogers et Taffee T. Tanimoto 1960, p. 1115–1118
  6. a et b Michael R Anderberg 1973
  7. a et b R. R. Sokal et C. D. Michener 1958, p. 1409-1438
  8. a et b Richard W Hamming 1950, p. 147–160
  9. a et b Leo A Goodman et William H Kruskal 1954, p. 732–764
  10. Fernando Lourenco, Victor Lobo et Fernando Bacao 2004
  11. a et b James A. Jones, Mary Jean Harrold et John T. Stasko 2001, p. 71–75
  12. a b et c Valentin Dallmeier, Christian Lindig et Andreas Zeller 2005, Monterey, California, USA, p. 99--104
  13. a b et c A Gonzalez 2007
  14. a b c d et e W. Eric Wong et al. 2007, Washington, DC, USA, p. 449–456
  15. Lee R Dice 1945, p. 297–302
  16. a b et c Brian Sidney Everitt 1978, New York
  17. a b c d e et f Lee Naish, Hua Jie Lee et Kotagiri Ramamohanarao 2011, New York, NY, USA, p. 11:1–11:32
  18. a et b Ben Liblit et al. 2005, p. 15–26
  19. Rui Abreu et al. 2009, New York, NY, USA, p. 1780–1792
  20. Lucia Lucia et al. 2014, p. 172–219
  21. Shaowei Wang et al. 2011, Washington, DC, USA, p. 556–559
  22. a b et c Jifeng Xuan et Martin Monperrus 2014
  23. M.Y. Chen et al. 2002, p. 595–604
  24. James A. Jones, Mary Jean Harrold et John T. Stasko 2001, p. 71–75
  25. a et b André Riboira et Rui Abreu 2010, p. 215–218
  26. T. Janssen, R. Abreu et A.J.C. van Gemund 2009, p. 662–664
  27. (en) « GZoltar » (consulté le )
  28. (en) « EzUnit » (consulté le )
  29. (en) « EzUnit4 » (consulté le )

Bibliographie[modifier | modifier le code]

  • (en) Rui Abreu, Peter Zoeteweij, Rob Golsteijn et Arjan J. C. van Gemund, « A Practical Evaluation of Spectrum-based Fault Localization », J. Syst. Softw., New York, NY, USA, Elsevier Science Inc., vol. 82, no 11,‎ , p. 1780–1792 (ISSN 0164-1212, DOI 10.1016/j.jss.2009.06.035, lire en ligne)
  • (en) Michael R Anderberg, Cluster analysis for applications,
  • (en) Mike Y. Chen, Emre Kiciman, Eugene Fratkin, Armando Fox et Eric Brewer, « Pinpoint: Problem Determination in Large, Dynamic Internet Services », Proceedings of the 2002 International Conference on Dependable Systems and Networks, Washington, DC, USA, IEEE Computer Society, dSN '02,‎ , p. 595–604 (ISBN 0-7695-1597-5, lire en ligne)
  • (en) Valentin Dallmeier, Christian Lindig et Andreas Zeller, « Lightweight Bug Localization with AMPLE », Proceedings of the Sixth International Symposium on Automated Analysis-driven Debugging, New York, NY, USA, ACM, aADEBUG'05,‎ , p. 99–104 (ISBN 1-59593-050-7, DOI 10.1145/1085130.1085143, lire en ligne)
  • (en) Lee R Dice, « Measures of the amount of ecologic association between species », Ecology, JSTOR, vol. 26, no 3,‎ , p. 297–302
  • (en) Brian Sidney Everitt, Graphical techniques for multivariate data, New York, North-Holland, (ISBN 0-444-19461-4)
  • (en) A Gonzalez, Automatic error detection techniques based on dynamic invariants,
  • (en) Leo A Goodman et William H Kruskal, « Measures of association for cross classifications* », Journal of the American Statistical Association, Taylor \& Francis, vol. 49, no 268,‎ , p. 732–764
  • (en) Richard W Hamming, « Error detecting and error correcting codes », Bell System Technical Journal, Wiley Online Library, vol. 29, no 2,‎ , p. 147–160
  • Paul Jaccard, « Etude comparative de la distribution florale dans une portion des Alpes et des Jura », Bulletin del la Société Vaudoise des Sciences Naturelles, vol. 37,‎ , p. 547–579
  • (en) A. James, Jean Mary et T. John, « Visualization for Fault Localization », Proceedings of the Workshop on Software Visualization (SoftVis), 23rd International Conference on Software Engineering,‎ , p. 71–75
  • (en) T. Janssen, R. Abreu et A.J.C. van Gemund, « Zoltar: A Toolset for Automatic Fault Localization », Automated Software Engineering, 2009. ASE '09. 24th IEEE/ACM International Conference on,‎ , p. 662-664 (ISSN 1938-4300, DOI 10.1109/ASE.2009.27)
  • (en) Ben Liblit, Mayur Naik, Alice X Zheng, Alex Aiken et Michael I Jordan, « Scalable statistical bug isolation », ACM SIGPLAN Notices, ACM, vol. 40, no 6,‎ , p. 15–26
  • (en) Fernando Lourenco, Victor Lobo et Fernando Bacao, « Binary-based similarity measures for categorical data and their application in Self-Organizing Maps », JOCLAD,‎
  • (en) Lucia Lucia, David Lo, Lingxiao Jiang, Ferdian Thung et Aditya Budi, « Extended comprehensive study of association measures for fault localization », Journal of Software: Evolution and Process, vol. 26, no 2,‎ , p. 172–219 (ISSN 2047-7481, DOI 10.1002/smr.1616, lire en ligne)
  • (en) Lee Naish, Hua Jie Lee et Kotagiri Ramamohanarao, « A Model for Spectra-based Software Diagnosis », ACM Trans. Softw. Eng. Methodol., New York, NY, USA, ACM, vol. 20, no 3,‎ , p. 11:1–11:32, article no 11 (ISSN 1049-331X, DOI 10.1145/2000791.2000795, lire en ligne)
  • (ja) Akira Ochiai, « Zoogeographic studies on the soleoid fishes found in Japan and its neighbouring regions », Bull. Jpn. Soc. Sci. Fish, vol. 22, no 9,‎ , p. 526–530
  • (en) Paul F RUSSELL, T Ramachandra Rao et others, « On Habitat and Association of Species of Anopheline Larvae in South-Eastern Madras. », Journal of the Malaria Institute of India, vol. 3, no 1,‎ , p. 153–178
  • (en) André Riboira et Rui Abreu, « The GZoltar Project: A Graphical Debugger Interface », Testing – Practice and Research Techniques, Springer Berlin Heidelberg, lecture Notes in Computer Science, vol. 6303,‎ , p. 215-218 (ISBN 978-3-642-15584-0, DOI 10.1007/978-3-642-15585-7_25, lire en ligne)
  • (en) David J. Rogers et Taffee T. Tanimoto, « A Computer Program for Classifying Plants », Science, American Association for the Advancement of Science, vol. 132, no 3434,‎ , p. 1115–1118 (ISSN 1095-9203, PMID 17790723, DOI 10.1126/science.132.3434.1115, lire en ligne)
  • (en) Wang Shaowei, D. Lo, Jiang Lingxiao, Lucia et Chuin Hoong, « Search-based fault localization », Automated Software Engineering (ASE), 2011 26th IEEE/ACM International Conference on,‎ , p. 556-559 (ISSN 1938-4300, DOI 10.1109/ASE.2011.6100124)
  • (en) R. R. Sokal et C. D. Michener, « A statistical method for evaluating systematic relationships », University of Kansas Science Bulletin, vol. 38,‎ , p. 1409-1438
  • (en) T. Sørensen, « A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on Danish commons », Biol. Skr., vol. 5,‎ , p. 1–34
  • (en) W. Eric Wong, Yu Qi, Lei Zhao et Kai-Yuan Cai, « Effective Fault Localization Using Code Coverage », Proceedings of the 31st Annual International Computer Software and Applications Conference - Volume 01, Washington, DC, USA, IEEE Computer Society, cOMPSAC '07,‎ , p. 449–456 (ISBN 0-7695-2870-8, DOI 10.1109/COMPSAC.2007.109, lire en ligne)
  • (en) Jifeng Xuan et Martin Monperrus, « Learning to Combine Multiple Ranking Metrics for Fault Localization », Proceedings of the 30th International Conference on Software Maintenance and Evolution,‎ (lire en ligne)