Accelerating Search-based Program Repair

Automatic program repair techniques offer the possibility of reducing, or even eliminating, the substantial manual effort that currently goes into the patching of software defects. However, current repair techniques take minutes or hours, to generate rather simple repairs, severely limiting their practical applicability. Search-based program repair represents a popular class of automatic repair techniques. Patch compilation and test case execution are the dominant contributors to runtime in this class of repair techniques. In this work we propose two complementary techniques, namely Location Selection and Test-Case Pruning, to improve the efficiency of search-based repair techniques. Location Selection reduces the number of repair candidates examined in arriving at a repair, thereby reducing the number of patch compilations as well as the overall number of test case evaluations during the repair process. Test-Case Pruning, on the other hand, optimizes the number of test cases executed per examined candidate. We implement the proposed techniques in the context of SPR, a state-of-the-art search-based repair tool, evaluate them on the GenProg benchmarks and observe that the proposed techniques provide a 3.9X speed-up, on average, without any degradation in repair quality.