ASU director's paper garners award for positive impact on the field

Maintaining software is costly, and for developers like Facebook and Microsoft, repairing software bugs can be very expensive. Today, most software bugs are repaired by humans — highly trained software engineers. About 10 years ago, a group of researchers, including Stephanie Forrest, director of Arizona State University's Biodesign Center for Biocomputing, Security and Society, looked to biological processes like evolution for ideas about ways to automate debugging. The result was a totally new approach for locating and repairing bugs in software.

The first paper to report a practical demonstration of the approach, “Automatically Finding Patches Using Genetic Programming,” was co-authored by Forrest and published in the proceedings of the 31st International Conference on Software Engineering (ICSE) in 2009. Its groundbreaking impact and importance to the field of software engineering will be recognized with an award for the Ten-Year Most Influential Paper at the organization’s 41st conference in Montreal on May 25–31.

The award is presented at each ICSE meeting to the authors of the paper from the ICSE meeting 10 years prior “that is judged to have had the most influence on the theory or practice of software engineering during the 10 years since its original publication.” Forrest’s paper has been cited more than 553 times.

“Automatically Finding Patches Using Genetic Programming” opened the door to a new way of thinking about debugging and automatic repair. Researchers at the University of Michigan, University of New Mexico and University of Virginia were Forrest’s co-authors.

“The award recognizes the role our paper played in stimulating a decade's worth of research into automated software repair; research that is just now starting to move into commercial use at companies like Facebook,” Forrest said.

Much like mutations occur in nature, “genetic programming” uses a population of programs formed by applying random mutations to the buggy code. The program variants are then tested against existing test suites, and in this way the population is evolved until a program that repairs the bug is found. The test suite ensures that the “repairs” don’t interfere with existing functionality while correcting for the detected issue.

Once a candidate patch for the bug is discovered, developers can go back and refine the automatically generated solutions to improve them. By giving human developers a head start on solving the problem at hand, the amount of time spent on manual debugging can be drastically reduced. Experimental results published in the paper showed that 63,000 lines from 10 different C programs (programming language) were typically repaired in less than 200 seconds, without requiring special program annotations or prior knowledge about the type of bug.

Forrest and her colleagues have continued to find ways to improve upon their original ideas and find new uses for them, such as finding variants of programs that run with reduced energy costs compared with the original. 

“The surprising success of our initial work has led us to ask questions about how software is produced and evolved over time, focusing on the very biology-like properties that software seems to have acquired,” Forrest said.

Forrest, a professor in the School of Computing, Informatics and Decision Systems Engineering, said it is “gratifying to be recognized by the leading conference in software engineering,” especially since the team’s approach to removing the human element from the repair process is considered controversial.

Forrest’s center uses a biological lens to solve a variety of computational problems, including how malicious behavior emerges in many complex systems. For example, viruses and cancer exploit the reproductive mechanisms of host cells to replicate and spread; bullies use intimidation to exert power, violating social norms; investors are duped by numerous schemes to manipulate financial markets; and cybercriminals exploit software vulnerabilities, eroding trust in networked systems. Successful systems develop effective defenses to counter these attacks.

Forrest will accept the award together with with her co-authors, Wes Weimer, ThanhVu Nguyen and Claire Le Goues.

The award is jointly sponsored by the Association for Computing Machinery/SIGSOFT and the Institute of Electrical and Electronics Engineers Technical Council on Software Engineering 

This research was supported in part by National Science Foundation Grants CNS 0627523 and CNS 0716478, Air Force Office of Scientific Research grant FA9550-07-1-0532, as well as gifts from Microsoft Research.