There are more bugs in real-world programs than human programmers can
realistically address. Automatic program repair has been a longstanding
goal in software engineering, yet debugging remains a largely manual
process.
Debugging brings an implementation closer to its specification: we
thus desire to know that specification. We briefly discuss recent advances
in dynamic invariant detection and specification mining. Using techniques
as diverse as polyhedra, equation solving, and software quality metrics, we
can discover critical aspects of what a program “does do” or “should do”
with fewer than 5% false positives.
We then introduce a fully automated approach for crafting patches
that repair bugs in off-the-shelf legacy systems. An extended form of
genetic programming is used to evolve repairs that leverage existing
programmer expertise and preserve required functionality. In a
large-scale, systematic study of high-priority defects from programs
involving over 5 million lines of code and over 10,000 test cases, we
find that our technique can repair 60 of 105 bugs, freeing developer
effort. Publicly-available cloud computing prices allow our results to be
reproduced for $356; a successful repair completes in 88 minutes and
costs $5.92 on average, a result that is strongly human competitive.
