RESTORE: Retrospective Fault Localization Enhancing Automated Program Repair

Fault localization is a crucial step of automated program repair, because accurately identifying program locations that are most closely implicated with a fault greatly affects the effectiveness of the patching process. An ideal fault localization technique would provide precise information while requiring moderate computational resources---to best support an efficient search for correct fixes. In contrast, most automated program repair tools use standard fault localization techniques---which are not tightly integrated with the overall program repair process, and hence deliver only subpar efficiency. In this paper, we present retrospective fault localization: a novel fault localization technique geared to the requirements of automated program repair. A key idea of retrospective fault localization is to reuse the outcome of failed patch validation to support mutation-based dynamic analysis---providing accurate fault localization information without incurring onerous computational costs. We implemented retrospective fault localization in a tool called RESTORE---based on the JAID Java program repair system. Experiments involving faults from the Defects4J standard benchmark indicate that retrospective fault localization can boost automated program repair: RESTORE efficiently explores a large fix space, delivering state-of-the-art effectiveness (41 Defects4J bugs correctly fixed, 8 more than any other automated repair tools for Java) while simultaneously boosting performance (speedup over 3 compared to JAID). Retrospective fault localization is applicable to any automated program repair techniques that rely on fault localization and dynamic validation of patches.