Localisation automatique de bugs

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 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].

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]	${\displaystyle C_{jac}={\frac {e_{f}}{e_{f}+e_{p}+n_{f}}}}$	Ample[15]	${\displaystyle C_{amp}=|{\frac {e_{f}}{e_{f}+n_{f}}}-{\frac {e_{p}}{e_{p}+n_{p}}}|}$
Sørensen Dice[4]	${\displaystyle C_{sdice}={\frac {2e_{f}}{2e_{f}+n_{f}+e_{p}}}}$	Dice[16]	${\displaystyle C_{dice}={\frac {2e_{f}}{e_{f}+n_{f}+e_{p}}}}$
Kulczynski1	${\displaystyle C_{kul1}={\frac {e_{f}}{n_{f}+e_{p}}}}$	Kulczynski2	${\displaystyle C_{kul2}={\frac {1}{2}}({\frac {e_{f}}{e_{f}+n_{f}}}+{\frac {e_{f}}{e_{f}+e_{p}}})}$
Russell and Rao[3]	${\displaystyle C_{rus}={\frac {e_{f}}{e_{f}+e_{p}+n_{f}}}}$	Tarantula[11]	${\displaystyle 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[7]	${\displaystyle C_{sm}={\frac {e_{f}+n_{p}}{e_{f}+e_{p}+n_{f}+n_{p}}}}$	Hamann	${\displaystyle C_{ham}={\frac {e_{f}+n_{p}-e_{p}-n_{f}}{e_{f}+e_{p}+n_{f}+n_{p}}}}$
M1[17]	${\displaystyle C_{m1}={\frac {e_{f}+n_{p}}{n_{f}+e_{p}}}}$	M2[17]	${\displaystyle C_{m2}={\frac {e_{f}}{e_{f}+2n_{p}+n_{f}+2e_{p}}}}$
Rogers & Tanimoto[5]	${\displaystyle C_{oca1}={\frac {e_{f}+n_{p}}{e_{f}+n_{p}+2n_{f}+2e_{p}}}}$	Sokal	${\displaystyle C_{sokal}={\frac {2e_{f}+2n_{p}}{2e_{f}+2n_{p}+n_{f}+e_{p}}}}$
Hamming[8]	${\displaystyle C_{ham}=e_{f}+n_{p}}$	Goodman[9]	${\displaystyle C_{good}={\frac {2e_{f}-n_{f}-e{p}}{2e_{f}+e_{p}+n_{f}}}}$
Ochiai[2]	${\displaystyle C_{oca1}={\frac {e_{f}n_{p}}{\sqrt {(e_{f}+e_{p})(e_{f}+n_{f})}}}}$	Euclid	${\displaystyle C_{euclid}={\sqrt {e_{f}+n_{p}}}}$
Ochiai2[18]	${\displaystyle 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[6]	${\displaystyle C_{anderberg}={\frac {e_{f}}{e_{f}+2e_{p}+2n_{f}}}}$
Wong1[14]	${\displaystyle C_{wong1}=e_{f}}$	Zoltar[13]	${\displaystyle C_{zoltar}={\frac {e_{f}}{e_{f}+e_{p}+n_{f}+{\frac {1000n_{f}e_{p}}{e_{f}}}}}}$
Wong3[14]	${\displaystyle 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[14]	${\displaystyle C_{wong2}=e_{f}-e_{p}}$

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

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

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

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

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

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

Pinpoint[24] 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[25] 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 (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[26] 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[27], 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[26]. Le code de GZoltar se veut ré-utilisable par les autres développeurs sous la forme d'une bibliothèque[28]. 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[29] 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[30], 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.