Automatic software repair of C programs with genetic programming and fix patterns

Abstract

Between 50% and 90% of the software costs are invested in repairing errors. The nature of this activity makes difficult its partial or complete automation through software-intensive systems. Nevertheless, a vast amount of research has been made over the last years in the pursuit of novel, effective, sound and scalable solutions towards the automation of software repair. Works like GenProg, PAR, ASTOR, JAFF, which use Genetic Programming to detect and repair software errors, demonstrate this fact. However, there are still a bunch of challenges to overcome in the field of Search-Based Software Engineering (SBSE) metaheuristics, group to which Genetic Programing belongs [Le Goues et al., 2013]. One of them is to improve the low quality of the software repairs. Since the basic idea of the Genetic Algorithms in automatic software repair is to evolve systematically a set of genotypes (i.e. programs) through a series of mutation operations until an optimal fix is found, nonsensical fixes can be presented as a solution. Thus, generating meaningful and human-like repairs is an essential topic to cover in this area in order to improve the patch quality. Since human knowledge and expertise have played and play currently an important role in the bug fixing process, we must transport this intangibles to the automatic software repair process. In this work, similar to the work made by Kim [Kim et al., 2013] we extract this knowledge from different sources of information and structure them in a set of patterns which, along with the Genetic Programming operators, will transform buggy program systematically to find an optimal patch. To our knowledge, this is the first work which applies fix templates to repair C programs. At the end, we will demonstrate that the use of fix templates not only overcome other approaches to fix C programs, but the generated patches tend to be more similar that the ones made by a human.

Zwischen 50% und 90% der Software-Kosten werden für Bug-Fixing ausgegeben. Aufgrund der Natur dieser Aktivität, erschwert sich die Möglichkeit, sie durch Software-Intensive Systeme durchzufüren. Nichtsdestotrotz ist die Recherche, um neu, effektiv, fundierte und skalierbare Methoden zu finden, in den letzten Jahren stark ausgestiegen. Ansätze wie GenProg, PAR, ASTOR und JAFF, die Genetic Programming verwenden, bestätigen diesen Fakt. Es gibt aber immer noch eine Menge von Herausforderungen bei der Search-Based Software Engineering (Such-bassierte Software Technik SBSE), Kategorie zu der Genetic Programming gehört [Le Goues et al., 2013]. Niedrige Qualität der Sofware Fixes ist eine von diesen Challenges. Da die grundsätzliche Idee genetischer Algorithmen bei der automatischen Software-Reparierung darin besteht, eine bestimmte Menge von Genotypen, also Programmen, durch verschiedene Mutationsoperatoren zu evolvieren bis eine optimale Reparatur gefunden wird, es könnten unsinvolle Fixen vorkommen. Es ist folgendermaßen notwendig, dass die Tools sinnvolle bzw. menschenähnliche Patches generieren, um die Qualität der Reparaturen zu erhöhen. Da menschliche Kenntnisse und Erfahrung hat gespielt bzw. spielt immer noch eine wichtige Rolle bei der Behebung von Software-Fehler, soll man sie in den Software-Reparatur Prozess inkludieren. In dieser Masterarbeit, analog zu dem Ansatz von Kim [Kim et al., 2013], extrahieren wir diese Kenntnise aus verschiedenen Quellen und struktutieren sie im Form von Fix-Muster die, neben den Genetic-Programming Operatoren, transformiren das fehlerhafte Programm, um einen optimalen Patch zu finden. Zu unserem Wissen ist diese die erste Arbeit, die Fix-Muster verwendet für die automatische Reparatur von C Programmen. Zum Schluss werden wir beweisen, nicht nur dass bei der Verwendung eine größere Menge von Bugs repariert werden könne, sondern auch dass solche Reparaturen menschenähnliche sind.