Restore : retrospective fault localization enhancing automated program repair

Abstract

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 of which no other automated repair tool for Java can fix) 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.