Communications of the ACM
Can Randomly Generated Code Fix Software Bugs?
CACM Senior Editor Jack Rosenberger
Can the principles of evolution be applied to software code and used to improve it? Stephanie Forrest thinks so—and has some encouraging data to prove it.
Forrest, who is chair of the computer science department at the University of New Mexico (UNM) in Albuquerque, is best known for her work with adaptive systems, including genetic algorithms, biological modeling, and computer security. She kicked off SPLASH 2010 with a keynote speech, titled "The Case for Evolvable Software," during which she presented early research, conducted with Westley Weimer at the University of Virginia, on incorporating the principles of evolutionary biology into the software process.
During her speech, Forrest demonstrated how evolvable software has been successfully applied to automated bug repair; optimizing and improving code, including assembly level code; and creating new combinations of existing software functionality.
When Forrest speaks of evolution, she is talking about applying the basic principles of evolution—specifically, random variation, selection, and inheritance--to software code. While this idea might strike some as radical, Forrest noted that the idea of applying the principles of evolution to software code can be traced back to John Holland, who wrote his seminal book on genetic algorithms, Adaptation in Natural and Artificial Systems, in 1975. (Holland’s thesis: "Computer programs that 'evolve' in ways that resemble natural selection can solve complex problems even their creators do not fully understand.") Likewise, other researchers are presently working with evolvable software, and Forrest briefly noted the work of three computer scientists: Andrea Arcuri, Michael Orlov, and Moshe Sipper.
One of Forrest’s projects at UNM is Evolutionary Program Repair in which genetic programming is used to evolve program variants until one is found that retains both the required functionality and repairs the bug in question. (This project deals with C software.) To date, Forrest, Weimer, and colleagues have applied evolvable software to approximately 25 bug-infested programs and fixed all of them. The faulty software has ranged in complexity from 22 lines of code to more than 35,000. In the 22-line code, the bug was an infinite loop. In the larger example, the problem involved FTP server code beset by stack overflow.
Forrest believes the approach of using evolvable software to fix small bugs shows promise because most bugs are small. She cited some research of Weimer, who studied 20,000 patches for Eclipse and found that 10% of the patches were 2 lines or less, 20% were 5 lines or less, and 53% are 25 lines or less.
Another favorable aspect of evolvable software is that not only can it automatically fix bugs, but it does so in a timely matter. Microsoft’s Zune 30 music player, for instance, was plagued by a bug that caused an infinite loop when the input was the last day of a leap year, which occurred on Dec. 31, 2008. In the case of the Zune bug, which involved 28 lines of code, the evolvable software fix took only 42 seconds. According to Forrest’s research, evolvable software can locate and repair a bug in an average of six minutes.
Evolvable software can also be applied to more complicated software. Eric Schulte, a graduate student of Forrest’s, has used evolvable software to repair directly compiled assembly code in multiple languages, including Java. Schulte’s research will be presented at ASE 2010.
In addition, Forrest, Weimer, and colleagues have applied evolvable software to existing software programs to remove unnecessary code and make them cleaner. In his research, Weimer found that evolvable software could reduce the instruction count of software programs by up to 40% with little discernible impact on quality, Forrest said.
While all of these results are encouraging, Forrest noted that one important question concerns robustness: Does applying mutations to an original program cause unwelcome mutations? The answer, she said, is sometimes yes, sometimes no. Forrest cited “Mutational Robustness and Automatic Program Repair,” a paper by Ethan Fast, an undergraduate student at the University of Virginia, which found that 30% of random one-step mutations are neutral.
In conclusion, Forrest argued that “software evolution is an achievable goal.” Based on her keynote at SPLASH 2010, and the audience’s encouraging response and the ensuing discussions, Forrest might well be right.
Jack Rosenberger is a senior editor, news, of Communications of the ACM.
Comments
Anonymous
I've been writing software for 35 years and would like to say, no, random code is not helpful! Never has been, in BASIC, Cobol, Fortran, WatFiv, dBase, Clipper, C++ or SQL and never will be - GIGO.
Evolvable software is clearly written on intelligent lines - deciding that an infinite loop is a bad thing, and knowing what to look for to fix it, and in what order, and how to fix it too. This is not random. The random approach would be to insert random letters and numbers at random
places at random times, for no particular reason, and see what happens.
Without intelligence somewhere along the line, you have a heck of a mess!
Displaying 1 comment