technical Perspective
automated Patching
techniques: the fix is in
By Mark harman

oVer The Pas T 40 years, much effort has been devoted to testing software to find bugs. Testing is difficult because the underlying problem involves unde-cidable questions such as statement reachability. However, testing cannot be ignored. The National Institute of Standards and Techniques estimated the cost of software failure to the U.S. economy at $60 billion, indicating that improved software testing could reduce this by at least one-third. 6

If finding bugs is technically demanding and yet economically vital, how much more difficult yet valuable would it be to automatically fix bugs? This question is answered precisely by the work reported in the following paper by Weimer, Forrest, Le Goues, and Nguyen. The authors use evolutionary computation to evolve patches that fix bugs. Their work is the first to show how Genetic Programming can evolve patches that fix real bugs (an idea first proposed by Arcuri and Yao, who experimented on toy programs3).

There is an increasing realization within the software engineering research and development community that evolutionary computation and related search-based optimization can be used to search for solutions to software problems. Software engineers often face problems typified by enormous spaces of possible requirements, designs, test cases, and code. Search-based optimization allows them to deploy optimization algorithms that automatically search these spaces, guided by fitness functions that encode solution desirability.

The search-based optimization
approach has come to be known as
Search Based Software Engineering
(SBSE). 4 This approach is widely ap-
pealing because it is very generic, ap-
plying equally well to many varied
software engineering problems. SBSE
also comfortably handles the mul-
tiple, conflicting, and noisy optimiza-
tion objectives often found in software
engineering scenarios. Using SBSE, it
has proved possible to automate the
search for requirements that balance
cost and benefit, designs that maxi-
mize cohesion and minimize coupling
and to find test cases that balance fault
finding against execution time. 1, 2, 5, 7

ware faults in a manner analogous to the way in which a surgeon might go about healing a wound. In order to localize the wound, they use positive and negative test cases, finding code segments most likely to contain the bug. One important insight employed in the patching process is the use of what might be called “plastic surgery;” rather than evolving a patch from scratch, the authors start their evolution from portions of existing code with similar functionality. The evolved patch is subsequently tidied up using techniques for dead code removal, thereby ensuring neat and effective wound healing.

All of these stages are described in detail in the following paper. The authors illustrate the application of their automated patching techniques and give compelling results to show how it finds and fixes real faults. Given the enormous costs of software faults mentioned earlier, it is surely impossible to overstate the potential impact that this work may have.

 

References

1. afzal, W., torkar, r. and feldt, r. a systematic review
of search-based testing for non-functional system
properties. Info.Softw. Tech. 51, (2009), 957–976.

2. ali, s., briand, l.c., hemmati, h. and Panesar-Walawege, r.k. a systematic review of the application and empirical investigation of search-based test-case generation. IEEE Trans. Softw. Eng. (2010, to appear).

3. arcuri, a. and yao, X. a novel co-evolutionary approach to automatic software bug fixing. in Proceedings of the IEEE Congress on Evolutionary Computation (hong kong, June 1–6, 2008), 162–168.

4. harman, m. the current state and future of search based software engineering. the future of software engineering. l. briand and a. Wolf, eds. IEEE CS Press, alamitos, ca, 342–357.

5. mcminn, P. search-based software test data generation: a survey. Softw. Testing, Verification and Reliability 14, 2 (June 2004), 105–156.

6. national institute of standards and technology. The Economic Impacts of Inadequate Infrastructure for Software Testing. Planning Report 02–3, may 2002.

7. räihä, o. a survey on search based software design.
tech. report technical report d-2009-1, dept. of
computer sciences, university of tampere, 2009.

Mark harman is a professor of software engineering and leads the software engineering group at king’s college, london. he is also director of the centre for research on evolution search and testing (crest).