Emerging Research on Automated Program Repair

While most research previously focuses on debugging and fault localization, there has been growing interest in the area of automated program repair.

I will give a brief introduction to automated program repair by answering several common questions that I came across.

Q: What is "Automated Program Repair" or "Automated Patch Generation"?
A: Imagine you are a developer who are assigned to fix a bug in your software. You are given a failing test which shows how to reproduces the bug. The goal is to fix this bug such that this failing test become passing while making sure that all other tests still pass. Firstly, you will need to find the location in which the bug are being manifested, essentially answering the "where to fix?" question.
After that, you will need to think about how to modify the code in order to complete the fix. You will also need to check if the code changes introduced indeed fix the bug by re-running all the tests. You could imagine that such process is both tedious and error prone. Wouldn't it be great if a tool could automatically do all these mentioned tasks for you? These are essentially the promises of automated program repair.

More formally, automated program repair is an approach that automatically generate fix for a buggy program by performing both fault localization and patches generation.

Q: How does it work? It sounds magical to me that a program could fix itself?
A: The idea of having a program fixing its own bugs may sound too good to be true but this is not the case. Most automated program repair techniques share lots of similarities with previous research on debugging and fault localizations. This is because if an automated technique could tell you the exact line and even the name of relevant variable in that line that cause the bug, then it is relatively easy for you to fix the bug itself. 


Q: Is it completely automated?
A: This depends on the techniques itself. From my experience of using a few state-of-the-art automated program repair tools, it is not as simple as clicking a button.
The general requirement is:

• The bugs itself must be reproducible and deterministic
• Test scripts need to be modularized such that each test could be run separately.
• Each test execution should take less than a few minutes
• The compilation of the program should take less than one hour

The last two requirement is important especially for search-based program repair techniques because these techniques spent the majority of the repair process in test execution and compilation.


Q: What is search-based program repair? Do you mean that the repair process basically proceed by trial-and-error?
A: Search-based program repair approaches solves the program repair problem using various local search strategies (e.g., genetic algorithm and random search) with the goal of optimizing the number of passing test cases. Yes, while different repair techniques may introduce some heuristics to reduce the repair time or the search space, the repair process is essentially trying to test each candidate patch until a patch that pass all tests is successfully found. 

To learn more about other relevant papers on automated program repair, refer to http://automated-program-repair.org/