Automatically Finding Patches Using Genetic Programming

The automatic repair of programs 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 into a standard patch using structural differencing algorithms and delta debugging; that patch can then be presented to developers.

We describe the proposed method and report results from an initial set of experiments demonstrating that it can successfully repair a dozen different C programs totaling over 140,000 lines in under 300 seconds, on average. We also describe how the automatic repair mechanism can be combined with anomaly intrusion detection to produce a closed-loop repair system, and we measure the effects of repair quality and false positives on server throughput.

Speaker Details

Westley Weimer is an Assistant Professor in the Computer Science Department at the University of Virginia. His research focuses on static and dynamic program analyses, as well as efforts to make software engineering processes, such as defect reporting and repair, more efficient. Professor Weimer received a Ph.D. in Computer Science from Berkeley in 2005.

Stephanie Forrest is Professor and Chairman of the Computer Science Department at the University of New Mexico in Albuquerque. She is also an External Professor and serves on the Science Board of the Santa Fe Institute. Her research studies adaptive systems, including genetic algorithms, computational immunology, biological modeling, and computer security. Professor Forrest received the Ph.D. in Computer and Communication Sciences from the University of Michigan (1985). Before joining UNM in 1990 she worked for Teknowledge Inc. and was a Director’s Fellow at the Center for Nonlinear Studies, Los Alamos National Laboratory.

Date:
Speakers:
Westley Weimer and Stephanie Forrest
Affiliation:
University of New Mexico and University of Virginia