Content area
Automated Program Repair (APR) is a vibrant and developing field within software engineering that aims to repair bugs in programs with minimal human involvement. This is an important problem, because fixing bugs is the dominant cost of maintaining software. Progress in APR has been mostly limited to repairing bugs that exist in one location in the program, typically requiring only a few lines of code to be changed. This is not surprising: most APR algorithms make only one mutation (change to a program’s source code), reverting it if it did not work before moving on to the next mutation. This caution is warranted, because it is easier to break a program than to repair it. However, scaling to more complex repairs has been a challenge; about half of the bugs in popular benchmarks have never been repaired by any algorithm.
This dissertation considers how to modify programs more extensively by focusing on neutral mutations: those that on their own do no harm to the program’s behavior. Remarkably, it is possible to apply many neutral mutations to a program without breaking its behavior. The primary contribution of the dissertation is an algorithm for program repair, MWRepair, that is designed to take advantage of this insight. MWRepair searches for repairs to bugs in programs by identifying many neutral mutations, then combining them in large numbers. This offers the potential of fixing bugs that require modification in more than one location and of fixing bugs that require more complex changes.
There are also a set of secondary contributions of this dissertation. I evaluate the search space for program repair, characterizing the tolerance of a variety of programs across different complexity scales to increasing numbers of neutral mutations. I analyze theoretically and measure empirically the performance of three implementations of the Multiplicative Weights Update algorithm (used in MWRepair). I consider the impact of the age structure of software on the likelihood of productive changes. And I review the trajectory of APR as a field.