Steven P. Reiss


Automated Bug Repair

Qi Xin worked on using code search techniques to perform automated bug repair. He produced two systems, SSFix and sharpFix, that achieved state of the art results.  We have been following up on his work to produce a system that integrates automated (or semi-automated) bug repair into a development environment.

1. SSFIX and SharpFIX

Automatic bug repair starts with a test suite and a failing test case. It attempts to find a patch to the program that causes the failing test case to succeed while not causing any test cases that currently succeed to fail. The various techniques work by first doing fault localization using the test suite to find likely bug locations. Then, for each location, they apply some technique to suggest possible patches. Some of the techniques sort these patches by likelihood. Finally, the patches are validated by running the test suite on the patched program. The first patch that passes the test suite is then returned. (There are variants, e.g. looking at the number of tests that pass versus fail rather than just looking at the failed test and any tests that previously succeeded but now fail.)

The insight that Qi had was that we could use repositories such as GitHub to suggest patches that were likely to be correct.  The basic idea was to take the buggy line and a context around it, find similar code in the repository, and then use the differences between the buggy and retrieved code to suggest realistic patches.  There are a number of difficulties including defining and finding "similar" code, matching the code (with different names and programming conventions), and suggesting patches.  Morever, the approach worked best when looking at both the repository and the other code in the system being debugged, possibly with different search methods.  Qi addressed all these difficulties and developed the two systems, SSFix initially, and then sharpFix as a refinement, that were able to find repairs for as many or more test cases that existing techniques, and was able to find correct patches more often then these techniques.  Moreover these systems were reasonably fast, with almost all the time being spend on validating the patches.          


2. Current Effort: ROSE

Our work on development environments led us to start this effort that attempts to integerate a practical automatic bug repair system into and IDE. At the same time, we wanted to move away fromm the dependence on a robust and complete test suite for automatic bug repair as such suites are rare (or nonexistant as the overfitting results show), and most programmers will want to do bug repair without them. The result is the system we are currently developing, ROSE.  ROSE is modeled after the Eclipse QuickFix facility.  It is designed to provide suggested repairs to the program that the developer can choose from.   Moreover, it is designed to do this quickly.

ROSE assumes that a developer is debugging their system and has reached a breakpoint where they discover that something is wrong.  The breakpoint might be the result of an exception, might be a  location where the developer didn't expect to be at, it might be while debugging the value of a variable or expression is incorrect, or it might be something else.   When invocated at the breakpoint, ROSE asks the developer to define the problem that should be fixed using a series of simple dialogs.  Then it uses this problem definition as well as the current values available from the debugger to do fault localization, finding potential locations that might need to be changed.  Next it applys a set of repair suggesters for each line.  These are based on the various automatic bug repair techniques and include pattern-based approaches looking for code smells, specialized approaches such as for loop analysis, and, of course, a general approach based on code search.  Once it has a set of repairs, ROSE validates the repairs by examining how they would affect the debugging run.  Potential repairs are assigned a probability and presented to the developer in probability order.