Towards practical program repair with on-demand candidate generation

Effective program repair techniques, which modify faulty programs to fix them with respect to given test suites, can substantially reduce the cost of manual debugging. A common repair approach is to iteratively first generate candidate programs with possible bug fixes and then validate them against the given tests until a candidate that passes all the tests is found. While this approach is conceptually simple, due to the potentially high number of candidates that need to first be generated and then be compiled and tested, existing repair techniques that embody this approach have relatively low effectiveness, especially for faults at a fine granularity. To tackle this limitation, we introduce a novel repair technique, S ketch F ix , which generates candidate fixes on demand (as needed) during the test execution. Instead of iteratively re-compiling and re-executing each actual candidate program, S ketch F ix translates faulty programs to sketches , i.e., partial programs with "holes", and compiles each sketch once which may represent thousands of concrete candidates. With the insight that the space of candidates can be reduced substantially by utilizing the runtime behaviors of the tests, S ketch F ix lazily initializes the candidates of the sketches while validating them against the test execution. We experimentally evaluate S ketch F ix on the D efects4 J benchmark and the experimental results show that S ketch F ix works particularly well in repairing bugs with expression manipulation at the AST node-level granularity compared to other program repair techniques. Specifically, S ketch F ix correctly fixes 19 out of 357 defects in 23 minutes on average using the default setting. In addition, S ketch F ix finds the first repair with 1.6% of re-compilations (#compiled sketches/#candidates) and 3.0% of re-executions out of all repair candidates.