high-quality set of positive test cases that encode program
requirements. In other work, we experimented with held-out indicative workloads, fuzz testing, and held-out exploits
to demonstrate that our server repairs address the causes of
problems without being fragile memorizations of the negative
input and without failing common requests (i.e., because of
the positive tests). Much remains to be done in this area, however, such as automatically documenting or proving properties
of the generated repairs.
Future work. Beyond these immediate steps, there are other
more ambitious areas for future work. For example, we plan
to develop a generic set of repair templates so the GP has an
additional source of new code to use in mutation, beyond those
statements that happen to be in the program. Our AST program
representation could be extended in various ways, for example,
by including data structure definitions and variable declarations. Similarly, we are currently experimenting with assem-bly- and bytecode-level repairs. Finally, we are interested in
testing the method on more sophisticated errors, such as race
conditions, and in learning more about bugs that need to be
repaired, such as their size and distribution, and how we might
identify which ones are good candidates for the GP technique.
We credit much of the success of this technique to design
decisions that limit the search space. Restricting attention to
statements, focusing genetic operations along the weighted
path, reusing existing statements rather than inventing new
ones, and repairing existing programs rather than creating
new ones, all help to make automatic repair of errors using
GP tractable in practice.
The dream of automatic programming has eluded computer scientists for at least 50 years. The methods described
in this paper do not fulfill that dream by evolving new programs from scratch. However, they do show how to evolve
legacy software in a limited setting, providing at least a small
down payment on the dream. We believe that our success
in evolving automatic repairs may say as much about the
state of today’s software as it says about the efficacy of our
method. In modern environments, it is exceedingly difficult
to understand an entire software package, test it adequately,
or localize the source of an error. In this context, it should
not be surprising that human programming often has a
large trial and error component, and that many bugs can be
repaired by copying code from another location and pasting
it in to another. Such debugging is not so different from the
approach we have described in this paper.
1. al-ekram, r., adma, a., baysal, o.
diffX: an algorithm to detect changes
in multi-version Xml documents.
in Conference of the Centre for
Advanced Studies on Collaborative
Research. ibm Press,
2. arcuri, a., yao, X. a novel
co-evolutionary approach to
automatic software bug fixing. in
IEEE Congress on Evolutionary
Computation (2008), 162–168.
3. ball, t., rajamani, s.k. automatically
validating temporal safety properties
of interfaces. in SPIN Workshop on
Model Checking of Software (may
4. dallmeier, v., Zeller, a., meyer,
b. generating fixes from object
behavior anomalies. in International
Conference on Automated Software
5. demsky, b., ernst, m.d., guo, P. J.,
mccamant, s., Perkins, J.h., rinard,
m. inference and enforcement of data
structure consistency specifications.
in International Symposium on
Software Testing and Analysis (2006),
6. ernst, m.d., Perkins, J.h., guo, P.J.,
mccamant, s., Pacheco, c., tschantz,
m.s., Xiao, c. the daikon system for
dynamic detection of likely invariants.
Sci. Comput. Program (2007).
7. forrest, s., hofmeyr, s.a., somayaji,
a., longstaff, t.a. a sense of self for
unix processes. in IEEE Symposium
on Security and Privacy (1996),
8. forrest, s., Weimer, W., nguyen, t.,
le goues, c. a genetic programming
approach to automated software
repair. in Genetic and Evolutionary
Computing Conference (2009),
9. harman, m. the current state and
future of search based software
engineering. in International
Conference on Software Engineering
10. hovemeyer, d., Pugh, W. finding
bugs is easy. in Object-Oriented
Programming Systems, Languages,
and Applications Companion (2004),
11. Jones, J.a., harrold, m.J. empirical
evaluation of the tarantula automatic
fault-localization technique. in
International Conference on
Automated Software Engineering
12. koza, J.r. Genetic Programming:
on the Programming of Computers
by Means of Natural Selection. mit
13. liblit, b., aiken, a., Zheng, a.X.,
Jordan, m.i. bug isolation via remote
program sampling. in Programming
Language Design and
We thank David E. Evans, Mark Harman, John C. Knight,
Anh Nguyen-Tuong, and Martin Rinard for insightful discussions. This work is directly based on the seminal ideas of
John Holland and John Koza.
This research was supported in part by National Science
Foundation Grants CCF 0621900, CCR-0331580, CNS
0627523, and CNS 0716478, Air Force Office of Scientific
Research grant FA9550-07-1-0532, as well as gifts from Microsoft
Research. No official endorsement should be inferred. The
authors thank Cris Moore for help finding the Zune code.
Westley Weimer ( firstname.lastname@example.org),
university of virginia.
Claire Le Goues ( email@example.com),
university of virginia.
Stephanie Forrest ( firstname.lastname@example.org),
university of new mexico.
ThanhVu nguyen ( email@example.com),
university of new mexico.