Automatic bug fixing

Automatic bug-fixing is the automatic repair of software bugs without the intervention of a human programmer . It is also commonly referred to as automatic bug repair or automatic patch generation.

Techniques for automatic bug-fixing are still in their infancy, but are broadly divided into two camps depending on the way the proposed repair is evaluated: those based on formal analysis, and those that use a generate-and-validate approach. The former uses formal methods to prove properties of a repair, whilst the latter relies on the availability of a high-quality test suite or similar artifact to validate the outcome of the repair process.

Techniques using Formal Verification

Verification-based program repair combines techniques from formal verification, program synthesis, and fault-localisation. Industrial application of these techniques is limited due to the computation cost involved; it is not clear how potentially scalable such methods are. To reduce the number of possible repairs and hence the computational cost, often only a small pre-defined class of bugs is considered. Examples of bug classes include off-by-one errors and memory leaks .

Test-and-Validate Techniques

In Test-and-Validate approaches, program repair is performed with respect to an oracle, encompassing the desired functionality of the program, which is used for validation of the generated fix. A simple example is a test-suite - the input/output pairs specify the functionality of the program, possibly captured in assertions. This oracle can in fact be divided between the bug oracle that detects faulty behaviour, and the regression oracle, which encapsulates the functionality any program repair method must preserve.

A variety of tools are employed to generate a candidate repair, typically either deterministic approaches using solvers for Satisfiability Modulo Theories (SMT) , or stochastic algorithms such as Genetic Programming. Research on the application of Genetic Programming to repair bugs is part of a subfield known as Genetic improvement. Current automatic repair systems using Genetic Improvement are able to repair real bugs in C, C++, and Java .

Repair Operators

Repair operators manipulate the original program, potentially via its abstract syntax tree representation, or a more coarse-grained representation such as operating at the line or block-level.

Typically, Genetic Improvement approaches operate at the line level and carry out simple delete/replace operations similar to those found in standard software patches. Verification-based methods are more likely to rely on template-based operators that match known patterns and have well-understood affects on program semantics.

Example Tools

Arguably the most well-known Genetic Improvement software repair tool is GenProg . Examples of verification-based repair techniques are: the Semfix tool , which relies on symbolic execution, and Gopinath et al.'s work that relies on Alloy specifications .

Limitations of Automatic Repair

State-of-the-art approaches can currently repair only a very small proportion of bugs. Although Genetic Improvement methods have arguably been shown to scale best, they usually do not provide correctness guarantees.