Utilisateur:Elyfarae/Brouillon

Correction automatique de bugs

La correction automatique de bugs est un outil qui permet de corriger des bugs présent dans le code de manière automatique. En effet, trouver une erreur parmi des milliers, voir des millions, de lignes de code peut être intimidant sans aide d'une assistance automatique. Depuis le début des années 2000, des chercheurs travail sur divers méthodes, capable de reconnaître et de proposer une correction pour un bug. Cela pourrait permettre à terme de gagner un temps de développement important sur les projets de grandes envergures.

Origines

Cela fait longtemps que les développeurs s’intéresse au sujet de la correction automatique de bug. En 2001, Andreas Zeller publie déjà un article sur le sujet. En 2008, Andrea Arcuri et Xin Yao publie une série d'article sur des premiers résultats. GenProg et BugFix font leur apparition en 2009, chacun utilisant des méthodes totalement différentes. BugFix se base sur les échecs au niveau des tests pour trouver les erreurs. GenProg utilise la programmation génétique. En 2012 apparaît R2Fix qui, à son tour, crée une nouvelle approche, utilisant les rapport de bug comme base de travail. Chacun se sert de l'apprentissage automatique (machin learning en anglais) pour que le logiciel progresse de lui-même.

Toutes ces recherches sont tirées d'un constat simple : la majorité du coût de production viens une fois le produit livré au client. Cela est, en partie, dû à l'évolution du logiciel mais surtout au débogage qui peut prendre beaucoup de temps. Par exemple en 2005 un développer de chez Mozilla estimais qu'il était découvert, chaque jour, environ 300 bugs.

Techniques utilisées et résultats obtenus

Apprentissage Automatique

L'automatisation du débogage passe par l'apprentissage automatique pour pouvoir détecter les erreurs en fonction de celles qui ont déjà était commise. Une base de données est formée avec ces erreurs et de leur correction, ce qui permet de pouvoir la corriger si un bug similaire apparaît.

Il est utilisé de manière à ce que chaque corrections, quel soit faite par l'homme où la machine, servent à rendre les corrections suivantes plus fiable et/ou plus rapide. C'est même la base de deux des méthodes suivantes. BugFix se base sur les choix des développeurs pour ordonné la liste des corrections possibles et R2Fix se sert de l'apprentissage comme base pour reconnaître les différents types de bugs et savoir comment les corrigés.

Comparaison des Méthodes

Pour pouvoir comparer les différents outils qui existent, nous allons nous intéresser au taux de réussite des corrections, au temps d’exécution mais aussi aux particularités de leur méthode et ainsi qu'aux contraintes que cela impose.

BugFix

Pour fonctionner, BugFix nécessite un test, qui échoue, pour pouvoir proposer une correction. BugFix, contrairement aux autres, ne génère pas de patch directement, mais une liste priorisé de suggestion pour corriger le bug. Pour générer cette liste, BugFix s'appuie sur l’apprentissage automatique. Il peut, ainsi, maintenir une base de connaissance de règles sur les correspondances de situation de débogage.

BugFix s’exécute en 3 principales étapes :

• Caractérisation la situation de débogage. Cela consiste à déterminer la situation de débogage statique (la structure de instruction) et dynamique (le motif dans les valeurs associés à l'instruction) de l'instruction actuellement en cours de débogage

• Priorisation les suggestions de BugFix et création du rapport. autrement dit, calculer et proposer une liste priorisée de suggestions de correction pour la situation de débogage courante. Le développeur choisira la solution adapté.

• Apprentissage du scénario de débogage après que le bug fut corrigé. Une fois que le bug est corrigé, il faut mettre à jour la base de connaissance avec la situation du débogage et la solution retenue.

Il n'y a pas d'information sur les résultats obtenus par cette méthode. Cela peut s'expliqué du fait que BugFix ne génère pas de patch. Il est donc difficile de quantifier son efficacité.

R2Fix

R2Fix analyse les rapports de bug et quel que soit la forme de ce rapport est capable de générer un patch pour corriger le bug. Il faut tout de même que ce rapport soit suffisamment complet et précis pour que cela fonctionne. Pour le moment, il n'a été configuré que pour quelques types de bugs.

L'analyse des rapports de bug se fait en 3 étapes. La première consiste à analyser syntaxiquement les rapports et à les classer. On ne garde ainsi que les bugs reconnu par R2Fix. La seconde étape consiste à récupérer les paramètres des bugs tels que le type de bug ou le nom du fichier. La dernière étape et la génération du patch sur le fichier concerné. Si il n'y a pas les informations nécessaires le patch n'est, tout simplement, pas généré.

R2Fix fut utilisé sur la base de données des rapports de bug de 3 projets open source pour réparer automatiquement sur trois grands types de bugs : les fuites de mémoires, les débordements de tampon et les pointeurs nulles. On considère qu'un rapport de bug est correctement corrigé, s'il y a au moins un patch généré par R2Fix qui est pareil ou sémantiquement équivalent au patch généré par les développeurs.

Il a, ainsi, généré automatiquement des patchs correctifs correct pour 60 rapports de Linux Kernel, Mozilla et Apache avec une précision de 75% car 20 patchs ne furent pas considérés comme correct. 43 rapports de bug étaient déjà corrigés et 17 rapports étaient ouverts. Sur les 17, 5 patchs étaient nouveau et 4 furent utilisé par les développeurs. En moyenne, R2Fix génère 1.33 patchs par rapport de bug. Il faut noter que moins de 1% des bugs, encore ouvert ou non, furent corrigé. cela s'explique par la limitation sur les types de bugs recherchés mais aussi par la sélection aléatoire qui a était faite sur les candidats potentiels (uniquement 819 sélections sur les 3627 candidats). Il est, en effet, difficile de trouver des patchs réalisé par des développeurs pour le comparer à ceux de R2Fix. Sur les 819 rapports de bug restants, uniquement 88 contenait suffisamment d'information pour être corrigé par R2Fix. Enfin, il reste 8 bugs qui n'ont pas pu être corrigé par un développer, rendant la comparaison impossible. Malgré tout, R2Fix, appliqué sur ces 80 bugs, aurais permis d’économiser, environ 68 jours de développement.

Les résultats montrent que R2Fix est efficace, précis et exacte dans sa génération automatique de patchs. Pour se faire, il a fallu collecter 41 fuites de mémoire, 51 débordements de tampon, et 91 pointeurs nuls pour permettre au programme d'apprendre à le faire.

Le fait de collecter manuellement un bug n'est requis qu'une fois part type de bug, car les résultats montre qu'un Classifieur linéaire entraîné sur quelques logiciel représentatif, comme Mozilla ou Linux Kernel, peut classifier un rapport de bug sur d'autres logiciels, tel qu’Apache, avec une grande précision (96.6%-98.8%) et exactitude (86.0%-90.0%).

Plus de la moitié (4 sur 7) des développeurs ont répondu que R2Fix peux faire gagner du temps sur la compréhension des bugs et sur la réparation de bug. R2Fix peut, seulement, générer des patchs sur une partie des bugs (10.7%, 88/819) des types précédemment cité, car les autres rapports de bug ne contiennent pas assez d'information.

GenProg

GenProg combine, à la fois, des méthodes d'analyse de programme et la programmation génétique pour corriger les bugs dans un logiciel. La programmation génétique s’inspire de l'évolution biologique pour faire évoluer un programme. Dans GenProg, cela permet de corrigé un bug de façon rapide et en minimisant la zone à modifier. Il n'y a pas, ici, de restriction au niveau du type de bugs. GenProg fonctionne sur les programmes développés en C. Il utilise les arbres syntaxiques abstraits (ou AST) pour analyser le code. Les AST permettent, en effet, de représenter, sans perte, l'ensemble d'un programme, mais, en plus, les opérations sur les arbres sont les mieux adaptés à la programmation génétique.

GenProg utilise les trois outils de la programmation génétique pour corriger les bugs:

• La sélection, qui permet de déterminer le meilleur algorithme en fonction de son adaptation par rapport au reste du code.
• La mutation, qui modifie le code à l'endroit le plus adapté. Une instruction qui provoque un ou plusieurs test faux mais aucun test vrai à une probabilité de 100% d'êtres modifié. La mutation permet de supprimer ou d'insérer une instruction ou d'échanger deux instructions.
• L'enjambement, échange toutes les instructions à partir d'un point de croisement choisi le long du chemin.

En 2009

Les résultats sont, déjà, plutôt bons. En effet, sur un programme C de 63 000 lignes de codes, il faut entre 50s et 500s pour corriger 1 bug et la correction fait entre 2 et 11 lignes. Cela limite l’éventuelle ajout de conflit entraînant d’autres bugs. Pour corriger 11 erreurs, il aura fallu 2003s pour modifier un total de 39 lignes de codes. Il y a 4 types de bugs différents qui furent traités ici.

En 2010

En 2010, GenProg a permis de réparer 20 défauts, au total, dans des modules de 186 000 lignes de codes eux même appartenant à 20 programmes totalisant 2.3 millions de lignes de code. Il y a désormais 8 types de bugs différents qui ont été traité.

En 2012

Avant de modifier certains éléments de sa méthode, GenProg obtenait, pour 5.1 millions de lignes de codes, 55 corrections sur 105 bugs confirmés par l'homme. Après quelque modifications, GenProg corrige 60 bugs et gagne entre 17% et 43% de temps comparais à avant.

Les modifications tiennes en 4 points :

• La représentation du code change, passant d'un AST reprenant tout le code à un ensemble de petites listes de modifications. Le taux de succès des réparations. Indépendamment de la représentation, la vérification de la sémantique y contribue de façon importante.
• lors d'un enjambement, il n'est plus utiliser qu'un seul point de croisement, là, où avant un ensemble de points était utilisé. On trouve ainsi les défaut 28% plus rapidement et le taux de réussite de la correction est augmenté de 4%.
• Lors de la mutation la suppression d'une instruction est priorisé par rapport au remplacement lui-même privilégié par rapport à l'ajout d'une instruction. GenProg améliore, ainsi, le taux de réussite de 25% à 33,9% et diminue le temps de réparation de 40%.
• L'hypothèse que les instructions exécutées exclusivement par des cas de test négatif doivent être pondérés beaucoup plus lourdement que ceux exécutés par les deux cas de tests positifs et négatifs est erronée. La modification de cette répartition améliore les taux de réussite et le temps de réparation, en particulier sur les bugs les plus difficiles. on peut gagner jusqu'à 70% de temps de réparation.

Conclusion

La correction automatique de bug est encore un sujet en cours d'étude. Depuis quelque année, les travaux dans ce domaine progressent à grands pas. GenProg et R2Fix suivent des chemins différents mais on chacun, à leur manière de bon résultat. Les améliorations futures de ces deux logiciels sont, en grande partie, une augmentation du périmètre dans lequel ils sont efficaces. R2Fix ne couvre que quelques types de bugs pour le moment et devra augmenter progressivement ce nombre. GenProg est plus avancé. Il n'est, en effet, pas restreins au niveau du type de bugs mais, au niveau du langage, il ne reconnaît que le C. Sachant qu'il n'y a pas vraiment d’information à ce sujet pour R2Fix. Nous n'avons pas trouvé d'information sur BugFix au-delà de 2009. Il est, donc, impossible de dire où en est l'avancé sur ce projet.

Correction de bug et évolution des logiciels

Une autre problématique se pose dans ce domaine, lorsque l'on parle de l'évolution du logiciel. En effet, il a été estimé que 50%-90% du coût de développement d'un logiciel est du à son évolution. Dans l'évolution d'un logiciel, les développeurs effectuent généralement des tests de régression pour s'assurer que les modifications n'engendre pas de nouvelles erreurs. Les modifications dans les logiciels inclus notamment des changement de fonctionnalité, des correction de bugs, de la restructuration de code, etc. Dans l’évolution d'un logiciel, quelques modifications implique d'autre changement au niveau des spécifications du programme. Dans certain cas, le développeur dois modifier les tests correspondant pour refléter les changement attendu sur le comportement du programme. Parfois, quand un test de régression échoue, ça peut être du au fait que ce teste est devenue obsolète et que le test lui-même dois être réparer. Si le développeur ne souhaite pas changer les spécification du programme dans l'évolution de celui-ci, c'est qu'il doit corriger le programme dans modifier le teste. Une étude interne de ABB Corporation indique qu'environ 80% des échec sur les tests de régression sont du a un bug dans le programme a l'endroit d’évaluation du teste et les 20% restant sont due l’obsolescence des tests. De nouvelles recherches commencent à s'intéresser à domaine. Le but ici est de savoir si c'est bien un bug qu'il faut corrigé ou si le problème est du un test obsolète.

Articles

(en) Andreas Zeller, « Automated debugging: Are we close? », Institute of Electrical and Electronics Engineers,‎ 2001 (lire en ligne)

(en) Andrea Arcuri, « On the Automation of Fixing Software Bugs », International Conference on Software Engineering,‎ 2008 (lire en ligne)

(en) Dennis Jeffrey, Min Feng, Neelam Gupta et Rajiv Gupta, « BugFix: A Learning-Based Tool to Assist Developers in Fixing Bugs », ACM International Collegiate Programming Contest,‎ 2009 (lire en ligne)

(en) Stephanie Forrest, ThanhVu Nguyen, Westley Weimer et Claire Le Goues, « Automatically Finding Patches Using Genetic Programming », International Conference on Software Engineering,‎ 2009 (lire en ligne)

(en) Stephanie Forrest, ThanhVu Nguyen, Westley Weimer et Claire Le Goues, « Automatic program repair with evolutionary computation », Communications of the ACM,‎ mai 2010 (lire en ligne)

(en) Stephanie Forrest, ThanhVu Nguyen, Westley Weimer et Claire Le Goues, « Representations and Operators for Improving Evolutionary Software Repair », Genetic and Evolutionary Computation Conference,‎ 2012 (lire en ligne)

(en) Liu Chen, « R2Fix: Automatically Generating Bug Fixes from Bug Reports », International Conference on Software Engineering,‎ 2012 (lire en ligne)

(en) Dan Hao, Tian Lan, Hongyu Zhang, Chao Guo et Lu Zhang, « Is it a Bug or an Obsolete Test ? », European Conference on Object-Oriented Programming,‎ 2013 (lire en ligne)