table, such that the repair may not be found by the algorithm in a reasonable amount of time.

To address this issue, some techniques limit edits to only deletion, insertion, or replacement of code at the state-ment- or block-level. For code insertion or replacement, a common approach is to pull code from elsewhere in the same program or module, following the plastic surgery hypothesis (that correct code can be imported from elsewhere in the same program) 6 or the competent programmer hypothesis (that programmers are mostly competent, and while they may make a mistake in one portion of a program, they are likely to have programmed similar logic correctly, elsewhere). Such a technique would therefore only consider moving entire blocks or lines of code around, for example, an entire if condition semantically similar to the one shown in Figure 1. This can often work by virtue of the fact that source code is repetitive. 22

Other techniques have benefited from using more expressive transformation templates, such as guarding a de-reference operation with a null-pointer check. Such transformation templates trade off repair space size for readability and “naturalness” of the resulting patches. Moving from state-ment-level edits to expression-level edits increases the search space, with the amount of increase depending on the transformation templates used to construct the search space.

However, even if the search space is large, the mutation operators may not support the behavioral change needed by the program or may affect the desired change in ways different from what a human might propose. A technique that may modify operators or insert conditions (copied from elsewhere in the program) would still struggle on this small program, since (a == c) never appears verbatim in our example. Such a lack of correct code fragments can result in degenerate behavior on smaller programs that provide little repair material. It also motivates research in intelligently augmenting the search space, for example, by considering past versions of a program.

Test execution. Repair candidates are
evaluated by running the modified pro-
gram on the provided set of test cases.
Test execution is typically the most
expensive step, as test suites can be
large and techniques may need to re-
run them many times. Various strate-
gies have been proposed to reduce this
cost, including test suite selection and
prioritization. Search strategies that
do not require a fitness function, for
example, based on random or deter-
ministic search, can reduce the cost
of testing by simply failing early (at
the first test failure). Moreover, such
techniques may run the test cases in
a heuristic order designed to maxi-
mize the chance that, if a test case is
going to fail, it is run early in the vali-
dation process.
Traversal strategy. Finally, tech-
niques vary in how they choose which
patches to explore, and in what order.
GenProg, 37 an early technique pro-
posed in this domain, implements a
genetic programming algorithm with
a fitness function based on the num-
ber of test cases passed by a patched
program. Subsequent techniques
like PAR9 have followed, varying in
the mutation operators (PAR) or the
fitness function. Other techniques
simply sample randomly typically
restricting themselves to single-edit
patches, 21 or in a heuristic, determin-
istic order as in GenProg AE. 36

Constraint-based repair. In contrast to heuristic repair techniques, constraint-based techniques proceed by constructing a repair constraint that the patched code should satisfy, as illustrated in Figure 3. The patch code to be generated is treated as a function to be synthesized. Symbolic execution or other approaches extract properties about the function to be synthesized; these properties constitute the repair constraint. Solutions to the repair constraint can be obtained by constraint solving or other search techniques. In these approaches, formulation of the repair constraint is the key, not the mechanism for solving it. This class of techniques can be captured via the following schematic:

 

for test t ∈ test-suite T

compute repair constraint ψt synthesize e as solution for Vt ψt

In this case, T is the test suite used
as the correctness criterion to guide
repair. The constraint ψt will be com-
puted via a symbolic execution10 of the
path traversed by test t ∈ T. The con-
straint ψt is often of the form
ψt ≡ πt ∧ output = expected
where πt is the path condition of the
path traversed by test t, output is the
symbolic expression capturing the out-
put variable in the execution of t and ex-
pected captures the oracle or expecta-
tion. The path condition of a program
path is a formula, which is true for
those inputs which traverse the path. 10

Computing repair constraints and angelix values. To illustrate constraint-based repair, reconsider our running example from earlier. SemFix, 18 which is representative for constraint-based techniques, substitutes the faulty condition in line 6 with an abstract function f (a,b,c) on the live variables. In this example, f is a predicate that takes the integer values a,b,c and returns true/ false. Then, the technique symbolically executes the tests in the given test suite to infer properties about the unknown function f. These properties are crucial for synthesizing an appropriate f that can pass all the given test cases.

The first two tests in our test suite do not even reach line 6. Hence, SemFix will not infer any property about the function f from them. From the last four tests, it can infer the repair constraint

 

f ( 2, 2, 3) ∧ f ( 3, 2, 2) ∧ f ( 2, 3, 2) ∧ f ( 2, 3, 4)

 

This is because analysis of the program has revealed that for input exercising line 6 if f is true, the program returns ISOSCELES and otherwise SCALENE.

Inferring detailed constraint specifications can be difficult, sometimes posing significant scalability issues. This motivates more efficient inference of value-based specifications. 16 In particular, angelic values are inferred for patch locations, where an angelic value for a fixed location is one that makes a failing test case pass. Once (collections of) angelic values are identified for each failing test, program synthesis can then be employed to generate patch code meeting such a value-based specification. This is the philosophy embodied in the Angelix tool16 where angelic values are obtained via symbolic execution (instead of producing repair specifications in the form of SMT constraints via symbolic execution directly). This way of dividing the