Automatically finding patches using genetic programming
Top Cited Papers
- 1 January 2009
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Automatic program repair has been a longstanding goal in software engineering, yet debugging remains a largely manual process. We introduce a fully automated method for locating and repairing bugs in software. The approach works on off-the-shelf legacy applications and does not require formal specifications, program annotations or special coding practices. Once a program fault is discovered, an extended form of genetic programming is used to evolve program variants until one is found that both retains required functionality and also avoids the defect in question. Standard test cases are used to exercise the fault and to encode program requirements. After a successful repair has been discovered, it is minimized using structural differencing algorithms and delta debugging. We describe the proposed method and report experimental results demonstrating that it can successfully repair ten different C programs totaling 63,000 lines in under 200 seconds, on average.Keywords
This publication has 26 references indexed in Scilit:
- Staffing a software project: A constraint satisfaction and optimization-based approachComputers & Operations Research, 2008
- Problem Difficulty and Code Growth in Genetic ProgrammingGenetic Programming and Evolvable Machines, 2004
- From symptom to causeACM SIGPLAN Notices, 2003
- CIL: Intermediate Language and Tools for Analysis and Transformation of C ProgramsLecture Notes in Computer Science, 2002
- Bugs as deviant behaviorACM SIGOPS Operating Systems Review, 2001
- Prioritizing test cases for regression testingIEEE Transactions on Software Engineering, 2001
- Yesterday, my Program Worked. Today, it Does Not. Why?Lecture Notes in Computer Science, 1999
- Advances in software engineeringComputer, 1996
- Genetic Algorithms: Principles of Natural Selection Applied to ComputationScience, 1993
- An empirical study of the reliability of UNIX utilitiesCommunications of the ACM, 1990