Utilisateur:Tdurieux/Brouillon

• Gérer mon brouillon
• Demander une relecture (voir les demandes)
• Publier mon brouillon

Cette page est un brouillon appartenant à Tdurieux

Conseils de rédaction

• → N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
• → Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.

Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :

• Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
• Indiquez les éléments démontrant la notoriété du sujet (aide).
• Liez chaque fait présenté à une source de qualité (quelles sources  – comment les insérer).
• Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
• Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).

• → Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.

La recherche 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 base de traces d'exécution

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 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 :
   • $e_{f}$ : le nombre de tests exécutant l'entité étudiée qui ont échoué (f pour failed)
   • $e_{p}$ : le nombre de tests exécutant l'entité étudiée qui ont réussi (p pour passed)
   • $n_{f}$ : le nombre de tests n'exécutant pas l'entité étudiée qui ont échoué (f pour failed)
   • $n_{p}$ : 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		$e_{f}$	$e_{p}$	$n_{f}$	$n_{p}$
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	Echoué	Echoué

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és ($e_{f}$) et un a réussi ($e_{p}$), tous les tests échoués ont exécuté cette ligne ($n_{f}$) et un test réussi n'exécute pas cette ligne ($n_{p}$). La ligne 2 est exécutée par les Tests 1, 2 et 4, un de ces test a échoué ($e_{f}$) et deux ont réussi ($e_{p}$), un test échoué n'exécute pas cette ligne ($n_{f}$) et tous les tests réussis exécutent cette ligne ($n_{p}$).

Métriques

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 proche du bug contiennent plus probablement du bug, celles les plus éloignées ne sont probablement pas la cause du bug. Sur base de ce tri, le développeur peut ensuite parcourir les différentes entités en commençant par les plus proche 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 (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 (1957), Russel and Rao (1940), Sørensen and Dice (1945), Rogers and Tanimoto (1960), Anderberg (1973) et Simple-Matching (2004). La métrique Hamming (1950) a, quant à elle, été créé pour la détection et la correction d'erreur de code et la métrique Goodman and Kruskal dans le domaine de la biométrie. Le domaine des cartes auto adaptatives a introduit les métriques Kulczynski1, Kulczynski2, Hamann et Sokal. Par ailleurs, plusieurs métriques ont été directement créées pour la localisation automatique de bug: Tarantula, Ample, Zoltar et Wong1-3.

Liste des métriques

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	$C_{jac}={\frac {e_{f}}{e_{f}+e_{p}+n_{f}}}$	Ample	$C_{amp}=|{\frac {e_{f}}{e_{f}+n_{f}}}-{\frac {e_{p}}{e_{p}+n_{p}}}|$
Sørensen Dice	$C_{sdice}={\frac {2e_{f}}{2e_{f}+n_{f}+e_{p}}}$	Dice	$C_{dice}={\frac {2e_{f}}{e_{f}+n_{f}+e_{p}}}$
Kulczynski1	$C_{kul1}={\frac {e_{f}}{n_{f}+e_{p}}}$	Kulczynski2	$C_{kul2}={\frac {1}{2}}({\frac {e_{f}}{e_{f}+n_{f}}}+{\frac {e_{f}}{e_{f}+e_{p}}})$
Russell and Rao	$C_{rus}={\frac {e_{f}}{e_{f}+e_{p}+n_{f}}}$	Tarantula	$C_{tar}={\frac {\frac {e_{f}}{e_{f}+n_{f}}}{{\frac {e_{f}}{e_{f}+n_{f}}}+{\frac {e_{p}}{e_{p}+n_{p}}}}}$
Simple Matching	$C_{sm}={\frac {e_{f}+n_{p}}{e_{f}+e_{p}+n_{f}+n_{p}}}$	Hamann	$C_{ham}={\frac {e_{f}+n_{p}-e_{p}-n_{f}}{e_{f}+e_{p}+n_{f}+n_{p}}}$
M1	$C_{m1}={\frac {e_{f}+n_{p}}{n_{f}+e_{p}}}$	M2	$C_{m2}={\frac {e_{f}}{e_{f}+2n_{p}+n_{f}+2e_{p}}}$
Rogers & Tanimoto	$C_{oca1}={\frac {e_{f}+n_{p}}{e_{f}+n_{p}+2n_{f}+2e_{p}}}$	Sokal	$C_{sokal}={\frac {2e_{f}+2n_{p}}{2e_{f}+2n_{p}+n_{f}+e_{p}}}$
Hamming	$C_{ham}=e_{f}+n_{p}$	Goodman	$C_{good}={\frac {2e_{f}-n_{f}-e{p}}{2e_{f}+e_{p}+n_{f}}}$
Ochiai	$C_{oca1}={\frac {e_{f}n_{p}}{\sqrt {(e_{f}+e_{p})(e_{f}+n_{f})}}}$	Euclid	$C_{euclid}={\sqrt {e_{f}+n_{p}}}$
Ochiai2	$C_{oca2}={\frac {e_{f}n_{p}}{\sqrt {(e_{f}+e_{p})(n_{f}+n_{p})(e_{f}+n_{p})(e_{p}+n_{f})}}}$	Anderberg	$C_{anderberg}={\frac {e_{f}}{e_{f}+2e_{p}+2n_{f}}}$
Wong1	$C_{wong1}=e_{f}$	Zoltar	$C_{zoltar}={\frac {e_{f}}{e_{f}+e_{p}+n_{f}+{\frac {1000n_{f}e_{p}}{e_{f}}}}}$
Wong3	$C_{wong3}=e_{f}-h{\text{, where }}h={\begin{cases}e_{p}&{\text{if }}e_{p}{p}<2\\2+0.1(e_{p}-2)&{\text{if }}2<e_{p}{p}<10\\2.8+0.01(e_{p}-10)&{\text{if }}e_{p}{p}>10\\\end{cases}}$	Wong2	$C_{wong2}=e_{f}-e_{p}$

Alternative: analyse des prédicats

Une approche alternative à la collecte des entités exécutées est proposée par Libit et al., 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. : $Increase(B)=Failure(B)-Context(B)$ où

$Failure(B)={\frac {\text{nb de test échoué où B est vrai}}{\text{nb de test où B est vrai}}}$ et

$Context(B)={\frac {\text{nb de test échoué où B est exécuté}}{\text{nb de test où B est exécuté}}}$.

Combiner les métriques

Des études empiriques 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. proposent une approche search-based algorithms, Jifeng Xuan et al. proposent une combinaison de métriques générées par apprentissage automatique.

Comparaison des métriques

Naish et al. 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. sont un meilleur compromis entre les performances et la fiabilité tel que Wong3, Zoltar, M2 et Ochiai.

Les résultats expérimentaux de Jifeng Xuan et al. 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 et Ample sont bons. Ces résultats contrastent avec ceux de Naish et al. car selon Jifeng Xuan et al. les suppositions de Naish et al. sur les données ne s'appliquent pas aux cas réels.

Outils

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

Pinpoint

Pinpoint 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 2 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

Tarantula 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

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

GZoltar 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, 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. Le code de GZoltar se veut ré-utilisable par les autres développeurs sous la forme d'une librairie. 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

EzUnit 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, 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.

Bibliographie

• (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,‎ novembre 2009, 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, 1973
• 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,‎ 2002, 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,‎ 2005, 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,‎ 1945, p. 297–302
• (en) Brian Sidney Everitt, Graphical techniques for multivariate data, New York, North-Holland, 1978 (ISBN 0-444-19461-4)
• (en) A Gonzalez, Automatic error detection techniques based on dynamic invariants, 2007
• (en) Leo A Goodman et William H Kruskal, « Measures of association for cross classifications* », Journal of the American Statistical Association, Taylor \& Francis, vol. 49,‎ 1954, p. 732–764
• (en) Richard W Hamming, « Error detecting and error correcting codes », Bell System technical journal, Wiley Online Library, vol. 29,‎ 1950, 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,‎ 1901, 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,‎ mai 2001, p. 71–75
• 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,‎ novembre 2009, 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, vol. 40,‎ 2005, 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,‎ 2004
• (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,‎ 2014, 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,‎ août 2011, p. 11:1–11:32 (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,‎ 1957, 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,‎ 1940, p. 153–178
• (en) André Riboira et Rui Abreu, « The GZoltar Project: A Graphical Debugger Interface », Testing – Practice and Research Techniques, Springer Berlin Heidelberg, vol. 6303,‎ 2010, 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,‎ 21 octobre 1960, 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,‎ novembre 2011, 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,‎ 1958, 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,‎ 1948, 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,‎ 2007, 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,‎ 2014 (lire en ligne)