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).