semantic anti-patterns aim to avoid generating patches that are likely to be
semantically incorrect. For instance, the anti-duplicate pattern prevents
meaningless patches like $a<a$, $0==0$, etc. Expressions containing semantic
anti-patterns are thus likely to be incorrect. The priority of these patches
is decreased.

  * •

Model Counting Model counting is a technique that counts how many models
satisfy a given constraint. Model counting is used to calculate the
“disagreement” level between $\mathtt{N_{patch}}$ and $\mathtt{N_{buggy}}$.
That is, we say that $\mathtt{N_{patch}}$ and $\mathtt{N_{buggy}}$ disagree
with each other if the value produced by $\mathtt{N_{patch}}$ is different
from the value produced by $\mathtt{N_{buggy}}$. The disagreement level
between $\mathtt{N_{patch}}$ and $\mathtt{N_{buggy}}$ is measured as the
number of inputs that produce different truth values on $\mathtt{N_{patch}}$
and $\mathtt{N_{buggy}}$, which is regarded as their semantic distance. For
instance, assuming that the original expression $\mathtt{N_{buggy}}$ is
$a<10$, a candidate patch $\mathtt{N_{patch1}}="a<=13"$, and another candidate
patch $\mathtt{N_{patch2}}$ is $a<=15$. The semantic distance between
$\mathtt{N_{patch1}}$, $\mathtt{N_{patch2}}$ and $\mathtt{N_{buggy}}$ is 4 and
6 (representing the number of integers on which the original expression and
patch produce different results), respectively. In this case, we would prefer
$\mathtt{N_{patch1}}$ since it changes fewer program behaviors than
$\mathtt{N_{patch2}}$.

  * •

Value Distance The value distance measures the difference between the produced
values by $\mathtt{N_{patch}}$ and $\mathtt{N_{buggy}}$ on certain tests. For
example, assuming that the original expression $\mathtt{N_{buggy}}$ is $a-10$,
and a candidate patch $\mathtt{N_{patch1}}$ is $a-13$, and $a-15$ as another
candidate patch $\mathtt{N_{patch2}}$. Given a test that assign the value of
$a$ as 20, the produced values by $\mathtt{N_{buggy}}$, $\mathtt{N_{patch1}}$
and $\mathtt{N_{patch2}}$ are 10, 7 and 5, respectively. So, under this test,
the value distance between $\mathtt{N_{buggy}}$ with $\mathtt{N_{patch1}}$ and
$\mathtt{N_{patch2}}$ are 3 and 5, respectively. To generate the value
distance, there are three steps: (1) generating a set of inputs $I$ that
produce different results on the candidate patches and original code; (2)
collecting the values of original code and each candidate patch for each
$i_{n}\in I$; (3) calculating the value distance between $\mathtt{N_{buggy}}$
with each candidate patch. Finally, the patch with the shortest distance is
selected.

Similar to syntactic distance, the candidate patches that have a shorter
semantic distance with the original code are preferred. Semantic and syntactic
features are sometimes used together to rank the candidate patches (Le et al.,
2017).

####  5.2.3. Learning to Rank

Apart from ranking algorithms based on syntactic and semantic analysis, the
candidate patches can also be ranked by learning how history patches fixed
similar bugs. This is based on an assumption that history patches often share
some common patterns, and they are similar in nature. Hence, past patches and
their common fix patterns can potentially provide some useful information
about what kinds of candidate patches are likely to be correct. This
assumption is similar to that of learning-based program repair techniques.

The history patches can help assess the quality and fitness of the candidate
patches (Le et al., 2016). To do so, we first mine a dataset of developer-
produced patches that fixed real bugs from version control systems, e.g.,
GitHub. The dataset is then used to mine common patch patterns by generalizing
and combining similar patches. Specifically, the original patches are
generalized by abstracting the project-specific details, such as variable
names, method names and etc. The generalized patches are then grouped
according to their code structures. For instance, assume we have two patches
if (array==null) return; and if (address==null) return; that fixed null
pointer dereferences, by abstracting their identifier names, they are
generalized to if (VAR==null) return; and if (VAR==null) return;,
respectively. Since the generalized patches share the same code structure,
these two patches are grouped together and their patch pattern would be
inserting if (VAR==null) return; before a pointer access. Later, candidate
patches are ranked using the extracted common patterns. The candidate patches
that appear frequently in the mined pattern are prioritized. For instance,
when fixing a null pointer dereferences, a candidate patch that matches the if
(VAR==null) return; pattern would be given higher priority.

Apart from learning common patterns, a probabilistic model can be trained to
rank the candidate patches according to their possibility of being correct
(Long and Rinard, 2016). For a buggy program $\mathtt{prog}$ and a set of
candidate patches, a trained probabilistic model assigns a probability
$P(p|\mathtt{prog},\theta)$ to each candidate patch $p$, indicating how likely
$p$ can correctly fix $\mathtt{prog}$. model parameter $\theta$ is trained in
the training process, which is an offline phase. Once the probabilistic model
is trained offline, it can be used online to rank candidate patches based on
their probability of being correct.

The design of the probabilistic model is based on the main hypothesis: correct
code, even across different applications, shares common correctness
properties. To learn an effective model, it is necessary to keep the important
and common correctness code properties, while abstracting away the unimportant
shallow details (e.g., variable names) that are associated with certain
applications. It is crucial to identify which features to use when training
probabilistic models. Two types of features are considered by existing
techniques: modification features, and program value features.

  * •

Modification features: Modification features express modifications and
interactions between the modified code and the surrounding statements. Two
types of modification features are considered. The first type expresses the
modification types of a patch, such as “inserting control flow”, “adding guard
condition”, “replacing condition”, “inserting statement”, “replacing
statement”, etc. The second type expresses the types of statements near the
patched statement and the modification kind. Specifically, the second type of
the modification features is formalized as a set of pairs (StatementKind,
ModificationKind), where the StatementKind represents the type of the buggy
statement, or the statement before/after the buggy statement.

  * •

Value features: Value features express the similarities and differences about
how variables/constants are used in the original program and in the patch. To
avoid application-specific information introducing noise to the feature space,
it is necessary to abstract away the syntactic details, such as names of
variables and values of constants. For instance, assume a candidate patch
changes an assignment $a=b+c\mapsto b=a+c$, the value feature of $a$ in the
original code and patch would be <=, L> and <=, R>, respectively. Meaning that
variable $a$ is the left value of an assignment in the original code, and
variable $a$ is the right value of the assignment in the patch. Similarly, the
respective value feature of $b$ in the original code and patch would be <=, R>
and <=, L>. Based on the abstraction, value features would model how the
variables/constants are used differently or identically before and after
applying the patch.

The learned probabilistic model is then applied to the candidate patches to
predict the probability of each patch of being correct.

###  5.3. Alleviate Overfitting via Test Generation

Since the test cases driving APR are usually incomplete, the other
straightforward idea to alleviate the overfitting problem is automatically
generating more tests. Overfitted patches pass the given tests, but they still
fail on some tests outside the given tests. Therefore, the goal of
automatically generating more tests is to find such tests that fail the
overfitted patches. There are two main challenges in efficiently generating
useful test cases 1): how to generate inputs that can drive the program
execution to the patch location and fail the overfitted patch 2): how to
define the oracle (i.e., the expected outputs) of the newly generated inputs.
There are quite a lot of existing test generation techniques, e.g., symbolic
execution, grey-box fuzzing, and evolutionary algorithm. These techniques are
designed for the program testing purpose, i.e., maximize code coverage and
maximize bug finding. Because of the fact that they have no knowledge about
the patch semantics, they are not efficient in generating useful tests for
ruling out overfitted patches. Therefore, people designed customized test
generation approaches for alleviating the patch overfitting issue.

####  5.3.1. Encode patch semantics into program

As we mentioned above, existing test generation techniques are not efficient
in ruling out overfitted patches since they are guided by coverage information
and they have no knowledge about the patch semantics. For the purpose of test
patches, one idea is to encode the patches into the original program by
inserting a dummy statement as the coverage goals (Xin and Reiss, 2017).

Let us look at an example program in Figure 12 that converts a string (e.g.,
“Yes”, “True”) into a boolean value.

⬇

1public static boolean toBoolean(String str) {

2 if (str==‘‘true’’) return true;

3 if (str==null) return false;

4 switch (str.length()) {

5 case 2: { ... }

6 case 3: {

7 char ch = str.charAt(0);

8 if (ch==‘y’)

9 return (str.charAt(1)==‘e’||str.charAt(1)==‘E’)

10 && (str.charAt(2)==‘s’||str.charAt(2)==‘S’);

11 if (ch==‘Y’) // Changed to ‘‘if (str!=null)’’ (Overfitting Patch)

12 return (str.charAt(1)==‘e’||str.charAt(1)==‘E’)

13 && (str.charAt(2)==‘s’||str.charAt(2)==‘S’);

14 //Inserted "return false;" (Correct Patch)

15 }

16 case 4: {

17 char ch = str.charAt(0);

18 if (ch==‘t’)

19 return (str.charAt(1)==‘r’||str.charAt(1)==‘R’)

20 && (str.charAt(2)==‘u’||str.charAt(2)==‘U’)

21 && (str.charAt(3)==‘e’||str.charAt(3)==‘E’);

22 if (ch==‘T’) { ... }

23 }

24 return false;

25 }

26}

Figure 12. An IndexOutOfBoundsException from Lang_51 in the Defects4J Bug
Dataset

This program has an IndexOutOfBoundsException bug at line 21 if it is executed
with “tru” as input. With “tru” as input, this program is expected to return
false as the output. This bug happens because the developer forgot to break
the switch statement after executing case 3.

Automatic repair technique NoPol (Xuan et al., 2017) produces a patch at line
11 by modifying the if-condition from $\mathit{ch}==$‘$\mathtt{Y}$’ to
$\mathit{str}!=\mathtt{null}$. The patched program now works correctly on the
input “tru” since it returns false at Line 12. Hence, the patched program
passes the given test suite. However, this bus has not been correctly fixed by
this patch. To efficiently generate a test that can still fail the patched
program, we could encode the patch semantics into the program for the purpose
of guiding test generation. Specifically, we can insert the following dummy
statement before line 11.

⬇

1if (((ch==‘Y’)&&!(str!=null))||(!(ch==‘Y’)&&(str!=null)))

2 int delta_syn_3nz5e_0 = -1; // A dummy statement

Then, test inputs can be generated with the guidance of the newly inserted
control flow. If a test input satisfies the inserted coverage goal, i.e.,
explores the inserted control flow, it will lead to a differential execution
between the original program and the patched program. Such input could find
the divergent behaviors of two programs and has the potential to expose an
overfitting behavior of patched programs. For this example, a new test case
with the input string “@es” could be generated. This new test triggers a new
failure on the patched program, i.e., the patched program returns true but the
expected output is false. So, we will figure out that this patch is an
overfitted patch.

More formally, this approach takes a buggy program $\mathtt{prog_{buggy}}$ and
patched program $\mathtt{prog_{patch}}$ as inputs. It first calculates
syntactic differences $\Delta$ between the $\mathtt{prog_{buggy}}$ and
$\mathtt{prog_{patch}}$. Each $\delta\in\Delta$ is a tuple
¡$\mathtt{stmt_{buggy}}$, $\mathtt{stmt_{patch}}$¿, where
$\mathtt{stmt_{buggy}}$ and $\mathtt{stmt_{patch}}$ are buggy statements and
the corresponding fixed statements, respectively. Based on
$\mathtt{prog_{buggy}}$, $\mathtt{prog_{patch}}$ and $\Delta$, a program
called test program $\mathtt{prog_{test}}$ is generated. To obtain
$\mathtt{prog_{test}}$, a dummy statement is inserted into
$\mathtt{prog_{patch}}$. For each modification $\delta\in\Delta$, the dummy
statement checks whether $\mathtt{stmt_{buggy}}$ and $\mathtt{stmt_{patch}}$
produce the same output. If they produce different outputs, the dummy
statement will lead the program execution to a new control flow. A test input
that covers the new control flow is likely to expose the overfitting behaviors
of plausible patches.

####  5.3.2. Guide test generation via patch partition analysis

Figure 13. Structure of program repair search space, where $S$ is a space of
candidate patches, $P$ is a set of plausible patches, $P_{\mathit{crashfree}}$
is a set of crash-free patches, $C$ is a set of correct patches,
$P_{\mathit{crashing}}=P\setminus P_{\mathit{crashfree}}$ is a set of crashing
patches.. Figure is adapted from (Gao et al., 2019)

Similar to the idea of exposing semantic differences between different program
versions, another idea generates useful tests by analyzing patch equivalence
(Gao et al., 2019). At a high level, the patch candidates can be divided into
different partitions according to their semantic behaviors, i.e., semantically
equivalent patches are put into the same partition. Figure 13 presents the
initial program repair search space. The full search space firstly can be
divided into two partitions: plausible partition (set $P$, the patches that
pass given tests) and incorrect partition(set $S-P$). Just as we mentioned in
Section 5.1, test suite is an incomplete specification. Therefore, only part
of plausible patches may be correct (set $C$), while the remaining patches
merely overfit the tests (set $P-C$). In rare cases, all the plausible patches
are correct. Moreover, when fixing program crashes, the tests outside of the
given test suite may still crash the patched programs that are fixed by
overfitted patches. To solve this problem, one idea is to use test generation
to filter out the plausible patches that still crash the programs (Gao et al.,
2019). The main idea is to separate the set of plausible patches into two
partitions: $P_{\mathit{crashfree}}$ which represents the crash-free plausible
patches, and $P_{\mathit{crashing}}$ which represents the plausible patches
still causing crashes. Crash-free plausible partition is composed of patches
that not only pass given tests, but also not causing crashes on the inputs
outside of the given test suite. Later, the patch should be chosen from the
crash-free plausible patches $P_{\mathit{crashfree}}$.

  * $p1$:

$\mathit{ch}==$‘$\mathtt{Y}$’ $\mapsto\mathit{ch}\ !=$‘$\mathtt{W}$’

  * $p2$:

$\mathit{ch}==$‘$\mathtt{Y}$’ $\mapsto\mathit{ch}\ !=$‘$\mathtt{X}$’

  * $p3$:

$\mathit{ch}==$‘$\mathtt{Y}$’ $\mapsto\mathit{ch}\ $‘$!=\mathtt{Y}$’

  * $p4$:

$\mathit{ch}==$‘$\mathtt{Y}$’ $\mapsto\mathit{ch}\ $‘$!=\mathtt{Z}$’

Figure 14. Four plausible but incorrect patches for fixing the bug in Figure
12

Let us revisit the above example. Suppose we have four plausible patches shown
in Figure 14. For the given failing input “tru”, all of these four patches
make the program pass. All these patches are classified into the same patch
partition since these four patch statements are evaluated as true under input
“tru” (value-based test-equivalent (Mechtaev et al., 2018a)). To filter out
overfitted patches, the test generation goal is then to break this patch
partition, i.e., find out a test input that makes these statements produce
different values. For instance, test input “Wru” can break this partition
because the patch statement in $p1$ is evaluated as false, while other patches
are still evaluated as true. Besides, with “Wru” as input, the patched program
using $p1$ still throws “IndexOutOfBoundException”, hence $p1$ will be put
into the crashing partition $P_{\mathit{crashing}}$.

Relying on an evolutionary algorithm, traditional greybox fuzzing techniques,
e.g., AFL (AFL, 2019), give high priority to the tests that improve code
coverage for further mutation. By mutating the tests that improve code
coverage, greybox fuzzing has a higher chance of further improving code
coverage. Following this idea, we also give the test inputs that break patch
partitions with higher priority The main intuition is by mutating the test
inputs that break patch partitions, we hope to generate more tests that
further break the patch partitions. For instance, by mutating “Wru”, it is
very likely to generate new inputs “Xru”, “Yru”, and “Zru” which can further
distinguish the patch partition and discard more overfitting patches.

Formally, given a buggy program $\mathit{buggyprog}$ and a set of patch
candidates $S$, the patch validation and test generation are fused into a
single process. The test generation produces new tests with the objective of
differentiating patches from $S$ and distinguishing patch partitions
{$P_{1},P_{2},\dots$}, and patch validation maintains the patch partitions
with the reference to all the available tests (including the given test cases
and the newly generated tests). Hence, a test suite is generated with the goal
of (1) covering the functionalities of the original program, (2) covering the
functionality of the program that is modified by candidate patches, and (3)
covering functionality that differs between different candidate patches, i.e.,
breaking patch partitions {$P_{1},P_{2},\dots$}. Since the generated test
suite has a higher chance to find divergences of candidate patches, it has a
higher chance to differentiate $P_{\mathit{crashfree}}$ and
$P_{\mathit{crashing}}$.

####  5.3.3. Oracle of newly generated tests

To determine whether a patched program is semantically correct, it is
necessary to know the expected outputs (test oracle) of the newly generated
tests. However, obtaining test oracles is a notoriously difficult problem in
program testing. One straightforward approach is to ask developers to provide
test oracles, but it is a time-consuming task. In the context of program
repair, fortunately, it is not necessary to query developers for the expected
outputs of all the test inputs. Instead, only if buggyprog and patchedprog
produce different outputs on a test input, the developer is queried to
determine which output is correct (Xin and Reiss, 2017; Böhme et al., 2020).
If the output of patchedprog is incorrect, the corresponding patch will be
discarded as an overfitted patch. Similarly, if multiple plausible patches
drive the program to generate different outputs, the developer’s feedback can
also help to rule out at least one of the plausible patches, since at most one
of the different outputs is correct on a deterministic program.

Although developer feedback can help discard overfitted patches, it also adds
a heavy burden to developers. Existing approaches turn to use some general
oracles (like crash-free (Gao et al., 2019), memory safety (Yang et al.,
2017), etc). Specifically, if a patched program crashes on some test inputs,
the corresponding patch must be overfitted. For the patched program by $p1$
shown in Figure 14, test input “Wru” can still trigger the
IndexOutOfBoundsException. Therefore, patch $p1$ can be determined as an
overfitted patch without developers’ participation. The absence of program
crashes cannot guarantee the correctness of the patched program. To deal with
this problem, Fix2Fit (Gao et al., 2019) proposes to use sanitizers to enhance
patch checking. Sanitizers can detect various vulnerabilities, such as buffer
overflow/underflow, and integer overflow at run-time. Generally, software
vulnerabilities are converted into normal crashes by sanitizers, for instance,
with the help of AddressSanitizer, triggering a buffer overflow would crash
the program execution. By using sanitizers, the patches that introduce
vulnerabilities can be ruled out. Compared to just relying on crashes, more
overfitted patches can be filtered out.

###  5.4. Alleviate Overfitting via Semantic analysis

Test case generation helps discard overfitted patches that introduce crashes
or cause memory errors, but it does not provide formal guarantees. In other
words, test case generation cannot guarantee that there is no unknown test
that can still crash the after-filtering patches. To solve this problem,
approaches based on semantic reasoning are applied to completely fix program
crashes/vulnerabilities.

Figure 15.  The input space of a vulnerable program, where $I_{e}$ represents
one given exploit and $I_{f}$ is the set of inputs that can trigger the same
vulnerability.

####  5.4.1. Guide patch generation via extracted constraints

##### High-level Idea

When a vulnerability is detected, people usually attach a test case that can
trigger this vulnerability along with the bug/vulnerability report. Such a
test case that can trigger vulnerabilities is also called exploit. As
demonstrated in Figure 15, except for the given exploit ($I_{e}$), there could
be many other inputs (called failing inputs $I_{f}$) that can trigger the same
vulnerability. Driven by exploit $I_{e}$, APR system may just fix the
vulnerability on $I_{e}$, but not be able to completely fix the bug on all
failing inputs. To solve this problem, we can consider generalizing $I_{e}$
and inferring a representation of all the failing input space $I_{f}$ (Gao et
al., 2021b). The generalized representation represents not only the given
exploit, but also all the failing inputs. If APR is driven by the generalized
representation, it can then fix all the failing test cases and hence
completely fix this vulnerability.

Figure 16 shows an example bug in Coreutils, which is adapted from (Gao et
al., 2021b). In this example, an undefined behavior bug of `memcpy`
222https://debbugs.gnu.org/cgi/bugreport.cgi?bug=26545 happens at line 7. This
undefined behavior will crash the program on some platforms. This bug will be
triggered when the memory spaces of the source and target overlap with each
other. For instance, if the value of $\mathtt{size}$ is 13, the _for_ -loop at
line 4 will terminate in the second iteration when $\mathit{size}/2{=}6$
(integer division) and $i{=}6$. Hence, the memory space of `memcpy`’s
destination is $[r,r+7)$, while the memory space of `memcpy`’s source is
$[r+6,r+13)$. There is one byte overlap between the memory space of the
destination and source. Taking $\mathtt{size}{=}13$ as input,
UndefinedBehaviorSanitizer (UBSAN) will crash the program.

⬇

1void fillp (char *r, size_t size){

2 ...

3 r[2] = bits \& 255;

4 for (i = 3; i < size / 2; i *= 2)

5 memcpy(r + i, r, i);

6 if (i < size)

7 memcpy(r + i, r, size - i);

8}

Figure 16. An undefined behavior bug from Coreutils adapted from (Gao et al.,
2021b)

Starting with the single crashing input ($\mathtt{size}{=}13$), we first infer
a generalized representation of all the failing inputs in the form of
constraint. According to the specification of memory, the source and
destination region should not overlap. In other words, for memcpy invocation
$\texttt{memcpy}(\texttt{p},\texttt{q},\texttt{s})$, the following constraint
$\texttt{p}{+}\texttt{s}\leq\texttt{q}\lor\texttt{q}{+}\texttt{s}\leq\texttt{p}$
must be satisfied. In this example, the corresponding constraint is

$\displaystyle(\texttt{r}{+}\texttt{i}{+}\texttt{size}{-}\texttt{i}{\leq}\texttt{r}\lor\texttt{r}{+}\texttt{size}{-}\texttt{i}{\leq}\texttt{r}{+}\texttt{i})\equiv(\texttt{size}\leq
0\lor\texttt{size}{\leq}2{\texttt{*}}\texttt{i})$

This constraint is called Crash-free Constraint (CFC). Any input, e.g.,
size=13, that makes program execution violate CFC at line 7, is a failing
input. Accordingly, the negation of CFC represents all the failing test cases.
Then, the repair goal is to correct the program to ensure this constraint is
satisfied on any test input.

Given CFC, a patch should be then introduced at the fix location to ensure CFC
is always true at line 7. Since the fix location (line 4 in this example) is
usually different from the crash location. $\mathit{CFC}$ is first backward
propagated from the crash location to the fix location along with all the
feasible paths.

In the above example, $\mathit{CFC}$ is propagated backward from line 7 to
line 4 along with one path (the truth branch of the if-statement at line 6).
After propagation, the constraint CFC’ at line 4 is
$i{<}\mathit{size}\mapsto(\mathit{size}\leq 0\lor\mathit{size}{\leq}2{*}i)$.
This means that with CFC’ as the precondition at line 4, executing the program
along with $i{<}\mathit{size}$ path will ensure CFC is always satisfied at
line 7. According to the constraint at the fix location, a patch $f$ can be
synthesized to replace the condition of _for_ -loop. In order to completely
fix this bug, it is necessary to ensure CFC’ is always satisfied at line 4
after applying $f$. In this example, $f$=“${i<=size/2}$” is produced by
synthesizer. Finally, this buggy program can be patched by:

    - for (i = 3; i < size / 2; i *= 2)
    + for (i = 3; i <= size / 2; i *= 2)

Fortunately, this patch is semantically equivalent to the patch provided by
developers. On the other hand, just driven by the failing case, it is very
likely that APR generates overfitting patches. For instance, Fix2Fit (Gao et
al., 2019) generates the following patch which fixes the bug when
$\mathtt{size}{=}13$. However, the patched program can still crash on other
inputs, such as $\mathtt{size}{=}7$.

    + for (i = 3; i < size / 2 || i == 6; i *= 2)

##### Formal Treatment

Let us now present the formal patch generation process based on the extracted
constraint. Overall, an exploit is first generalized into a _crash-free
constraint_ (_CFC_), which represents an abstracted constraint that is
violated by the witnessed vulnerability. A crash is broadly defined to be any
program termination caused by violating some properties. A crash could be in
the form of (1) violation of a user-defined assertion (i.e.,
$\mathtt{assert}(C)$), (2) violation of assertion enforced by operating
system, such null pointer dereference, or (3) violation of check inserted by
_sanitizers_ for enforcing safety properties, e.g., AddressSanitizer (ASAN)
333https://clang.llvm.org/docs/AddressSanitizer.html for memory safety checks
and UndefinedBehaviorSanitizer (UBSAN)
444https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html for integer
overflow protection. _The condition that should be satisfied to prevent the
crash_ is represented as CFC at the crashing location. Once a generated patch
ensures $\mathit{CFC}$ is always satisfied at the crash location, then the
crash will not be triggered by any program input. The basic workflow to
generate patches is as follows.

Table 3. Basic crash classes, crash expressions/statements, and the corresponding _Crash-Free Constraint_ $\mathit{CFC}$-template adapted from (Gao et al., 2021b). Seven types of crashse: explicit developer assertion violation, sanitizer-induced crash such as buffer overflows/underflows, integer overflows, API constraint violations. Class | Template ID | Expression |  $\mathit{CFC}$ Template
---|---|---|---
developer | $T_{1}$ | $\mathtt{assert}(C)$ | $C$
sanitizer | $T_{2}$ | *p | $\texttt{p}{+}\texttt{sizeof}(\texttt{*p})\leq\mathit{base}(\texttt{p}){+}\mathit{size}(\texttt{p})$
$\texttt{p}\geq\mathit{base}(\texttt{p})$
2-4 | $T_{3}$ | $\texttt{a}~{}\mathit{op}~{}\texttt{b}$ |  $\texttt{MIN}\leq\mathtt{a}~{}\mathit{op}~{}\mathtt{b}\leq\texttt{MAX}$ (over $\mathbb{Z}$)
2-4 | $T_{4}$ | $\texttt{memcpy}(\texttt{p},\texttt{q},\texttt{s})$ | $\texttt{p}{+}\texttt{s}\leq\texttt{q}\lor\texttt{q}{+}\texttt{s}\leq\texttt{p}$
2-4 | $T_{5}$ |  *p (for $\texttt{p}{=}0$) | $\texttt{p}\neq 0$
2-4 | $T_{6}$ |  $\mathtt{a}~{}/~{}\mathtt{b}$ (for $\mathtt{b}{=}0$) | $\mathtt{b}\neq 0$

  1. (1)

Constraint Extraction. Given a program and an exploit that triggers a crash,
we extract the “crash-free constraint” ($\mathit{CFC}$) according to a
predefined template. Table 3 defines seven types of templates for some common
bugs/vulnerabilities, which formulate the underlying cause of each defect. For
instance, the template for a buffer overflow is
$\mathtt{buffer\\_access}-\mathtt{buffer\\_base}<\mathtt{buffer\\_size}$.

  2. (2)

Fix Localization. Given the crash location and the extracted $\mathit{CFC}$,
_fix localization_ technique is then applied to decide one (or more) fix
location(s). The fix locations can be determined using a dependency-based
approach. The dependency-based fix localization determines statements that
have a _control_ or _data_ -dependency with the statement at the crash
location. The determined statements could affect the truth of $\mathit{CFC}$.

  3. (3)

Constraint Propagation. Given CFC at the crash location, we then propagate it
to a given fix location and calculate $\mathit{CFC}^{\prime}$ by solving the
following Hoare triple:

(CFC-Propagation)
$\displaystyle\\{\mathit{CFC^{\prime}}\\}P\\{\mathit{CFC}\\}$

The program between crash and fix location is donated as $P$. CFC’ is the
weakest (least restrictive) precondition that guarantees postcondition CFC
(Chandra et al., 2009).

  4. (4)

Patch Synthesis. Once CFC’ is calculated, patch candidates are then
synthesized at the fix location. Patch synthesis is to construct expression
$f$ to substitute the expression $\rho$ at the fix location, with the goal of
making the following Hoare triple holds:

(CFC-Repair)
$\displaystyle\\{\mathit{true}\\}~{}[\hbox{\pagecolor{gray}$\displaystyle\rho\mapsto
f$}]~{}\\{CFC^{\prime}\\}~{}P~{}\\{\mathit{CFC}\\}$

The synthesized patch $\rho\mapsto f$ fixes the buggy program by substituting
expression $\rho$ with the synthesized expression $f$. The precondition before
the patch is set as $\mathit{true}$ to ensure the patch fix the bug regardless
of the context. The generated patch ensures that $\mathit{CFC}^{\prime}$ is
satisfied at the fix location. Therefore, in the patched program,
$\mathit{CFC}$ will also be always satisfied at the crash location.

In general, we rely on the extracted constraints to make programs satisfy
safety properties including fixing buffer overflow, integer overflow, null
pointer dereference, and so on. Once the patched program satisfies this
constraint, it is guaranteed that such crashes/vulnerabilities are completely
fixed.

####  5.4.2. Patch exploration via Concolic repair

To tackle the overfitting problem, the concept of Concolic Program Repair
(CPR) (Shariffdeen et al., 2021b) introduces a repair process that (1)
performs the co-exploration of input space and patch space, (2) handles an
abstract patch space, and (3) incorporates additional user-provided
specifications.

Figure 17. Illustrates the concept of co-exploration in Concolic Program
Repair (Shariffdeen et al., 2021b). The left part shows the input space, the
right part shows the patch space. By incrementally covering the input space,
the patch space gets refined gradually.

Figure 17 illustrates the concept of co-exploration. The left side shows the
input space, while the right side shows the patch space. Starting from an
initial failing test case, CPR generates a set of plausible patches.
Therefore, it limits the patch space to patches that can pass the initial
failing test case. CPR further refines the patch space by exploring not only
the single test input but the complete input partition exercised by the test.
In addition to the existing tests, CPR generates new test inputs via
generational search (Godefroid et al., 2012) and uses the user-provided
constraint to reason about the patch within the corresponding input
partitions. Over time, this process will incrementally cover more of the input
space and further refine the patch space, leading to a gradual improvement of
the generated patches. A key insight of this work is that even simple user-
provided constraints can help refine patches regarding newly generated inputs.

##### Overview: Concolic Repair Algorithm

Algorithm 2 Concolic Repair Algorithm (Shariffdeen et al., 2021b)

0: set of initial test cases $I$, buggy locations $L=(patchLoc,bugLoc)$,
budget $b$, specification $\sigma$, language components $C$

0: set of ranked patches $P$

1: $P\leftarrow$ Synthesize(C, I, L)

2: while $P\neq\emptyset$ and CheckBudget(b) do

3: $t$, $\rho\leftarrow$ PickNewInput($P$)

4: if no test $t$ available then

5: return $P$

6: end if

7: $\phi_{t}$, $hit_{patch}$, $hit_{bug}\leftarrow$ ConcolicExec($t$, $\rho$,
$L$)

8: if $hit_{patch}$ then

9: return $P\leftarrow$ Reduce($P$, $\phi_{t}$, $\sigma$, $hit_{bug}$)

10: end if

11: end while

12: return $P$

Algorithm 2 shows the general repair process applied by CPR. It starts with
synthesizing a pool of plausible patches based on the provided test cases and
the given fix location. The remaining process focuses on eliminating and
refining patches based on additional observations with new inputs. These
inputs are generated via generational search (Godefroid et al., 2012), i.e.,
by flipping the terms in the already collected path constraints. Via concolic
execution, CPR determines the path constraint for a new input and whether the
execution touches the relevant patch location. Only if this is the case the
path constraint is used to refine the patch pool. In addition to reducing the
patch space, CPR uses dynamic execution information to rank the remaining
patches. Patches are ranked higher (1) if they are exercised with the
generated input (i.e., there is supporting evidence for their correctness in
terms of generated test cases) and (2) if the input in combination with the
patch exercises the original bug observation location. The patches are
deprioritized if the original control flow is changed significantly.

The construction of a rich search space and its efficient exploration are
general technical challenges of APR techniques. CPR is tackling these
challenges by maintaining an abstract patch space and applying efficient
infeasability checks between the input and patch space to avoid unnecessary
computations.

##### Abstract Patch Space

Concolic program repair uses an abstract patch representation to (1) generate
and maintain a smaller set of patch candidates and (2) enable the refinement
of patches. An abstract patch $\rho$ in this patch space is defined as the
3-tuple $(\theta_{\rho},T_{\rho},\psi_{\rho})$ with the set of program
variables $X_{P}$, the corresponding subset of input variables $X\subseteq
X_{P}$, and the set of template parameters $A$. $\theta_{\rho}(X_{P},A)$ is
the repaired (boolean or integer) expression, $T_{\rho}(A)$ denotes the
conjunction of constraints $\tau_{\rho}(a_{i})$ on the parameters $a_{i}\in A$
included in $\theta_{\rho}$: $T_{\rho}(A)=\bigwedge\limits_{a_{i}\in
A}\tau_{\rho}(a_{i})$, and $\psi_{\rho}(X,A)$ is the patch formula induced by
inserting the expression $\theta_{\rho}$ into the buggy program. For example,
assume the patch $\rho$ is the expression inside a conditional statement.
Assuming that x is an available program variable, concrete patches could be x
> 0, x > 1, x > 2, etc. In the abstract patch space of CPR such a patch would
be represented with a template like $x>a,a\in[0,10]$, and hence, would subsume
a set of concrete patches. With regard to the previously mentioned 3-tuple,
such abstract patch would be described with: $\theta_{\rho}:=x>a$,
$T_{\rho}=tau_{\rho}(a):=(a\geq 0)\land(a\leq 10)$, $\psi_{\rho}:=x>a$.
Abstract patches can be refined by modifying the parameter constraint
$T_{\rho}$, which is part of one of the infeasibility checks discussed in the
next paragraph.

##### Infeasability Checks

The co-exploration concept of concolic program repair includes infeasibility
checks in both directions: (1) from input space to patch space and (2) from
the patch space to the input space. Such infeasibility checks help to further
efficiently limit both spaces.

The check from the input space to the patch space is called patch reduction.
It means that CPR tries to reduce the patch space based on the collected
information from the input space. The formula to check is as follows: $\forall
a_{i}\in A\;\forall x_{j}\in X:\phi(X)\land\psi_{\rho}(X,A)\land
T_{\rho}(A)\implies\sigma(X)$. It describes that if there is an input $x_{i}$
and parameter $a_{i}$ that is feasible under the obtained path constraint
$\phi$ and the patch formula $\psi_{\rho}$ with its parameter constraint
$T_{\rho}$, then it needs to satisfy the user-provided specification $\sigma$.
The formula can be filled with the corresponding values and negated to check
for counterexamples. Each counterexample leads to the refinement of the
parameter constraint $T_{\rho}$, i.e., to a reduction of the patch space.

The check from the patch space to the input space is called path reduction.
Before exploring a partition in the input space, CPR checks whether there is
at least one patch left in the patch space that can exercise the corresponding
path. If no such patch is left, the input partition does not need to be
explored.

###  5.5. Human in the Loop

We presented several approaches to alleviate the patch overfitting issue.
Unfortunately, none of them could perfectly solve this problem. This is
because complete program specification is usually not available and inferring
developers’ intent is error-prone and fundamentally difficult. So, the
ultimate solution is to involve human in the loop: asking developers to
validate the auto-generated patches before applying them in the program. In
this setting, instead of fully replacing developers in fixing bugs, APR
systems play the role of helping developers by generating patch suggestions.

To validate the correctness of patches, developers must understand the bug to
be fixed and fully understand patch’s semantics. Even for expert programmers,
understanding the root cause of bug and its corresponding patch is not easy
and straightforward. To help developers understand the bug and the patches,
people proposed workflows to enable developers to review patches just with a
few clicks (Gao and Roychoudhury, 2020). Technically, the patch semantics are
first translated into a set of questions, e.g., “what is the expected value of
variable index at line 46?”, “whether statement return NULL; should be
executed or not for a test?”. To review patches, developers just need to
select the answers to those questions. Such developers’ feedback can then help
filter overfitted patches and find the correct patch among the plausible
patches.

Let us take a look at the example shown in Listing 5, which is adapted from
(Gao and Roychoudhury, 2020). In this example, incorrect bound checking causes
a buffer overflow vulnerability 555https://bugs.chromium.org/p/oss-
fuzz/issues/detail?id=1345. This buffer overflow write occurs at line 10 when
the value of remaining_space is equal to width at line 3. This is because the
program will illegally rewrite the memory data after frame_end. To correctly
fix this vulnerability, one solution is to modify the assignment from
$\mathtt{frame\\_end-frame}-3$ at line 1 to $\mathtt{frame\\_end-frame}-4$.

⬇

1 int remaining_space = frame_end-frame - 3; //correct patch: ”frame_end-
frame-3” -¿ ”frame_end-frame-4”

2 if (remaining_space < width)

3 return AVERROR_INVALIDDATA;

4 frame[0] = frame[1] = frame[width] =

5 frame[width+1] = bytestream_get_byte(gb);

6 frame += 2;

7 frame[0] = frame[1] = frame[width] = // buffer overflow location

8 frame[width +1] = bytestream_get_byte(gb);

9 frame += 2;

Listing 5: Buffer overflow vulnerability in FFmpeg adapted from (Gao and
Roychoudhury, 2020)

Given a failing test triggering this buffer overflow, current repair systems
could generate several plausible patches. For example, here are four patches
that can fix the failing test by replacing the assignment at line 1.

  * $p1$:

$\mathtt{frame\\_end-frame}-3$ $\mapsto\mathtt{frame\\_end{-}frame{-}4}$

  * $p2$:

$\mathtt{frame\\_end-frame}-3$ $\mapsto\mathtt{frame\\_end{-}frame{-}5}$

  * $p3$:

$\mathtt{frame\\_end-frame}-3$ $\mapsto\mathtt{frame\\_end{-}frame{-}6}$

Among these patches, only one of them is correct and the other two are
overfitted patches. To filter out the overfitted patches, the following
question will be constructed: “What is the correct value of
$\mathtt{remaining_{s}pace}$ at line 1 to pass the failing test?”. Then, a set
of candidate answers to the above question will be generated by this tool and
visually provided to developers. Asking and answering questions in terms of
variable values are designed based on the assumption that developers are
usually better at reasoning about program outputs. This is because program
correctness is usually defined in terms of outputs. For developers, answering
those questions is an analogy with the debugging process. Therefore,
developers should be able to answer those questions without exhaustively
analyzing the program and patch semantics. The candidate answers could be
generated with references to plausible patches. For the example question
above, the candidate answers could be 8, 7, 6, corresponding to the above
three plausible patches $p1$, $p1$, and $p2$ when ($\mathtt{frame\\_end-
frame}=12$). Suppose developer indicates that the expected value is 8, then,
another question will be created: “How to produce the expected value (8) at
line 1?”. The candidate patches are the answers to this question. In the above
example, patch $\mathit{frame\\_end{-}frame{-}4}$ is the only answer as it can
produce the correct value 8. Later, developer determines whether this
candidate patch is correct or not. Instead of directly answering developers to
review candidate patches one by one, the proposed process enables developers
to review via answering questions. Relying on the interactive question-
answering process, the overfitted patches, such as
$\mathit{frame\\_end{-}frame{-}5}$, can be ruled out. Involving human in the
patch generation and review process actually provides a way to alleviate the
over-fitting problem.

##  6\. Program Repair Technology

In this chapter, we detail the program repair tools available, as well as
certain known industrial deployment of program repair technology.

###  6.1. Program Repair Tools

Automated program repair has gained increasing attention from both academia
and industry researchers. Many automated repair tools have been developed or
even deployed in the past few years. Table 4 lists some representative
automated program repair tools. Existing repair tools are mainly designed for
fixing the bugs or vulnerabilities in C/C++ and Java programs. The widely used
benchmarks for evaluating C/C++ repair tools are ManyBugs (Le Goues et al.,
2015), IntroClass (Le Goues et al., 2015), Codeflaws and ExtractFix benchmark
(Gao et al., 2021b). Existing repair tools have shown good performance on
those benchmarks. For instance, according to the study shown in (Mechtaev et
al., 2018a), among 105 bugs in ManyBugs benchmark, GenProg, Prophet, and
Angelix (only evaluated on partial benchmark) automatically generate patches
for 27, 42, and 28 bugs respectively. Among the generated patches, 3, 15, and
10 of them are equivalent to human patches. Besides general bugs, existing
tools also showed great performance in fixing vulnerabilities. For instance,
ExtractFix (Gao et al., 2021b) could automatically fix 16 vulnerabilities out
of 30 subjects in the ExtractFix benchmark. In contrast, the widely used
benchmark for evaluating Java repair is Defects4J (Just et al., 2014), which
includes more than 400 real-world defects. On the Defect4J benchmark, the best
Java repair tools can correctly fix more than 50 bugs. Besides the C/C++ and
Java repair tools, few tools (e.g., Clara, Refactory) are designed for fixing
the bugs in introductory Python programs, which are mainly used for
programming education. For instance, Refactory is designed to generate real-
time patches for student programs with the goal of helping students to learn
programming.

As shown in Table 4, all the repair tools are also classified according to
their underlying technique. The listed tools are search-based, semantic-based,
or learning-based repair. When the automated program repair was proposed,
researchers mainly focused on search-based (e.g., GenProg) and semantic-based
(e.g., SemFix) tools. In recent years, we have seen a trend of tools and
techniques that apply deep learning to the field of program repair. Learning-
based repair tools have gained a lot of attention and achieved great
performance in generating correct patches.

Most repair tools are from academia, while some of them (e.g., SapFix
(Marginean et al., 2019), GetaFix (Bader et al., 2019) and Fixie (Kirbas et
al., 2021)) are from industry and have been deployed to fix real-world bugs.
Note that, Table 4 shows an incomplete set of repair tools, a complete list of
repair tools can be found at http://program-repair.org/tools.html.

Table 4. Representative automated program repair tools Tool |  Language |  Technique |  Short description
---|---|---|---
AllRepair |  C/C++ |  Search |  mutation-based repair tool for C programs equipped with assertions in the code
GenProg |  C/C++ |  Search |  automated program repair tool based on genetic programming
Fix2Fit |  C/C++ |  Search |  Combining patch exploration with greybox fuzzing to alleviate overfitting
Prophet |  C/C++ |  Search & Learning |  automated program repair that learns from correct patches
RSRepair |  C/C++ |  Search |  a modification of GenProg that uses random search
SPR |  C/C++ |  Semantic |  automated program repair tool with condition synthesis
SemFix |  C/C++ |  Semantic |  automated program repair tool based on symbolic analysis
Angelix |  C/C++ |  Semantic |  automated program repair tool based on symbolic analysis
CPR |  C/C++ |  Semantic |  program repair based on concolic execution
DeepFix |  C/C++ |  Learning |  tool for fixing common programming errors based on deep learning
MemFix |  C/C++ |  Static |  static analysis-based repair tool for memory deallocation errors in C programs
ACS |  Java |  Search & Learning |  repair tool with accurate condition synthesis
jGenProg |  Java |  Search |  the Java version of GenProg for bugs in Java programs
NPEFix |  Java |  Search |  generates patches for Null Pointer Exceptions with meta-programming
SapFix |  Java |  Search |  the first deployment at Facebook of automated end-to-end fault fixing
SimFix |  Java |  Search |  fixing Java bugs by leveraging existing patches and similar code
TBar |  Java |  Search |  template-based automated program repair
Nopol |  Java |  Semantic |  automated program repair tool for conditional expressions
Coconut |  Java |  Learning |  tool for fixing bug by learning from history patches
Genesis |  Java |  Learning |  infer code transforms from history patches for automatic patch generation
GetaFix |  Java |  Learning |  automated program repair that learns from history patches
SequenceR |  Java |  Learning |  program repair based on sequence-to-sequence learning
Clara |  Python |  Search |  repair tool for introductory programming assignments
Refactory |  Python |  Search & inference |  tool for generating real-time program repairs of buggy student programs
Fixie |  |  Learning |  a repair tool developed and used at Bloomberg

###  6.2. Industrial Deployment

We now discuss known industrial deployment of program repair.

The ﬁrst end-to-end deployment repair in an industrial context was presented
by SapFix (Marginean et al., 2019) at Facebook and is called SapFix. Its
workflow (see Figure 18) starts with testing the code changes added to the
continuous integration with Sapienz (Mao et al., 2016), a search-based testing
tool deployed at Facebook. It specifically searches for null-dereference
faults. SapFix generates repairs by using template-based and mutation-based
approaches. If no patch can be found, it will revert the code change. All
generated patches are cross-checked using the static analyzer Infer (Calcagno
et al., 2015). After heuristically selecting one patch candidate, it will
notify the software developer to review the patch. SapFix is a repair tool
that is integrated as part of continuous integration, where SapFix monitors
test failures, reproduces them, and automatically looks for patches.

Figure 18. Facebook’s SapFix Workflow adopted from (Marginean et al., 2019).
Figure 19. Bloomberg’s Fixie Architecture adopted from (Kirbas et al., 2021).

After Facebook, other companies like Bloomberg (Kirbas et al., 2021) have
started looking into concrete ways to integrate APR into their development
processes. Their tool Fixie combines three different fix types (see Figure
19). Firstly, they use off-the-shelf linter tools like clang-
tidy666https://releases.llvm.org/10.0.0/tools/clang/tools/extra/docs/clang-
tidy. Such tools are broadly accepted and deployed in practice and can provide
fixes with high confidence for, e.g., style violations and interface misuses.
Secondly, they allow software developers to propose their custom fixes that
can then be proposed for other scenarios as well. Thirdly, they learn fixes
and fix patterns from the version-control history linked with bug/issue
trackers and CI/CD pipelines. Fixie collects and stores patches from these
three sources and proposes fixes by creating pull requests. Fixie (Kirbas et
al., 2021) reports that after some initial backlash by developers and
improvement iterations, they received positive feedback from the users. In
particular, after putting the user in control of reviewing and applying auto-
generated patches. Software developers see Fixie as a development ”assistant”,
which frees up their time to focus on tasks like cleaning up the code, for
which there is usually not much time left.

There exist interest in the industry (e.g. Fujitsu(Bavishi et al., 2019)) on
combining program repair with static analysis systems. Companies which have
shown interest in this line of work, that we are aware of, include Oracle
Labs.

###  6.3. Achieved Results So Far

The research in automated program repair has already created a vast portfolio
of techniques and methods. Community-wide datasets like the Defects4J (Just et
al., 2014), CodeFlaws (Tan et al., 2017), and ManyBugs (Le Goues et al., 2015)
benchmark have been established to foster fair comparisons and to identify
common limitations. Table 4 shows a subset of the created tools, which have
been developed for different programming languages and different application
scenarios. These tools have shown the ability to fix many bugs. Specifically,
out of the 400 bugs from Defects4J benchmark, when the perfect fix location is
given, around 20% of bugs can be correctly fixed by at least one APR tool.
Suppose the perfect fix location is unknown, relying on the realistic fault
localization output, i.e., spectrum-based fault localization, existing tools
correctly fix around 10% of bugs (Liu et al., 2019). Moreover, with the
exception of some tools like Angelix (Mechtaev et al., 2016) which can produce
multi-line fixes, many existing automated repair tools are limited to fixing
simple single-line patches, such as inserting a null-check for fixing null
pointer dereference.

This means that while automated program repair is a promising and emerging
technology - significant engineering and technical challenges remain in
automatically synthesizing large-scale patches. At the same time, the adoption
of automated program repair in the industry has started (Section 6.2) with
first deployments, and companies like Facebook/Meta and Bloomberg shared their
identified benefits and lessons learned with the researchers. In this regard,
we consider the recent development of language model based code generation
(Chen et al., 2021d; cod, 2022)from industry (which nevertheless tends to
generate buggy code) with some satisfaction. We feel that there remain
significant prospects in terms of leveraging automated repair to improve
automatically generated code snippets - which may provide a way to leverage
the research advances in program repair for enhancing programmer productivity.

Apart from enhancing programmer productivity - there remain other possible
areas where automated program repair has shown promising results. One such
area is automated security vulnerability repair. Early on, tools like Angelix
(Mechtaev et al., 2016) have shown promise in this regard, by repairing
complex vulnerabilities like the well-known Heartbleed vulnerability
777http://heartbleed.com. More recently, the works on semantic reasoning (Gao
et al., 2021b; Shariffdeen et al., 2021b; Huang et al., 2019) and inductive
inference based repair (Zhang et al., 2022) have shown further promise in this
domain. Since security vulnerabilities are typically detected via fuzz testing
(Böhme et al., 2021), a security vulnerability repair approach which is
seamlessly integrated with fuzz campaign, would be ideal. We posit that this
is a difficult but achievable goal, and would urge the research community to
work towards this goal.

Last but not the least, program repair approaches are already being used for
programming education via a number of point technologies (Gulwani et al.,
2018; Wang et al., 2018; Hu et al., 2019; Ahmed et al., 2022). This shows the
power of automated program repair for providing feedback to students
struggling to learn to program. In the future, there remains the opportunity
of moving from such point technologies to developing widely-used intelligent
tutoring systems for programming education that rely on program repair. Due to
the wide demand for computer science undergraduate degrees which typically
involves learning programming in the first year, this would indeed be an
impactful research direction to work towards.

##  7\. Applications

The automated program repair techniques discussed in the previous chapters
have many applications and use cases in the context of software development.
First and foremost, they can be applied to repair functional errors, which
would be the most general application of automated program repair techniques.
Existing test suites help pinpoint the buggy locations and guide the repair
process. (Monperrus, 2018b) lists and categorizes the existing research
literature in program repair, which spans various repair scenarios like static
errors, concurrency errors, build errors, etc. A rather prominent topic is the
repair of security vulnerabilities: with 28,695 security vulnerabilities
reported in 2021 (Risk Based Security, 2021) and an average time to fix of 200
days for as critical classified vulnerabilities (NTT Application Security,
2021), program repair has enormous potential for the security domain. Another
exciting application aspect is the integration into development workflows by
accommodating repair features in the Integrated Development Environments (IDE)
and Continuous Integration (CI) workflows. With the rising number of students
in computer science related studies, the need for automated tutoring aids is
rising (Huang et al., 2019). Automated program repair offers solutions to
produce high-level feedback that can scale with the high number of new
students. Furthermore, it is not always necessary to generate a new patch from
scratch but reuse existing human-written patches for similar but different
applications. Automated patch transplantation addresses this matter by
extracting, transforming, and integrating patches between programs. It is not
only interesting from a technical perspective but also can increase the trust
of the developers (Noller et al., 2022). Below we discuss these application
scenarios that go beyond general repair and present specific usage scenarios
and integrations.

###  7.1. Repairing Security Vulnerabilities

The sheer amount of reported and only slowly fixed security vulnerabilities
motivates the application of automated program repair in the security context.
Moreover, targeting security repair has its appeal because the bug search and
repair generation does not need to rely on test suites compared to functional
errors but can take into account general security properties regarding buffer
overﬂows, integer overﬂows, null pointer dereferences, or division by zero
errors.

##### General-purpose repair applied for security

Besides the special use case and its assumptions, it is possible to apply
general-purpose repair tools for repairing security vulnerabilities. For
example, Angelix (Mechtaev et al., 2016) (also see Chapter 3.4), although
relying on a test suite and not explicitly tailored for security repair, can
be applied to repair the popular Heartbleed
vulnerability888http://heartbleed.com. Similarly, concolic program repair
(Shariffdeen et al., 2021b) is not a security-tailored approach; it uses the
available test suite to synthesize plausible patches and later refines them by
test generation and a user-provided constraint (see more details in Chapter
5.4.2). In its evaluation, there are many successfully repaired security
vulnerabilities. As long as the provided specifications (e.g., test cases and
assertions) are sufficient to infer the expected behavior, the general program
transformations included in general-purpose repair approaches might also
successfully repair security vulnerabilities.

##### Security-tailored repair

One of the challenges in security repair is that there is usually only one
failing test, the exploit, that acts as repair input. Based on this exploit,
the APR techniques must find a suitable repair specification to generate a
correct patch. In general, this can be handled by generating (i.e., searching
for) additional test cases to build up a test suite that helps refine patches.
As previously mentioned, techniques like CPR (Shariffdeen et al., 2021b)
refine patches by generating more test inputs while using user-provided
constraints/properties as test oracles.

Given that security properties can be defined across programs, static
analyzers and fuzzers equipped with sanitizers usually search for violations
of such properties without much user intervention. When finding a violation,
these properties are available for further analysis. APR can use that
information and create tailored bug localization and fixing strategies to make
the program adhere to these properties. For example, it can analyze the
violated property by applying symbolic and deductive reasoning. (Lin et al.,
2007) repair out-of-bound vulnerabilities by limiting access to reading and
writing arrays. Suppose p is an array and i is an index that would cause an
out-of-bounds error p[i] when is executed. First, it uses data-flow analysis
to identify vulnerable program statements, and by changing the read statement
to p[i mod size] (where size is the inferred allocated buﬀer size), it avoids
any exploit of this vulnerability. (Huang et al., 2019) use human-specified
safety properties to steer the patching. Their tool Senx takes a
vulnerability-triggering input and executes it concolically to detect
violations of the safety properties tailored for buffer overﬂow, bad cast, and
integer overﬂow vulnerabilities. With the collected information about the
execution trace and the affected variables, Senx generates a predicate
defining the concrete expression necessary to prevent the safety violation and
synthesize a source-level patch. The patch is enforced at the first location
that is applicable. While this avoids the vulnerability, the fix is basically
placed close to the crash location to disable the vulnerability, which may not
address the underlying problem. (Gao et al., 2021b) incorporate sanitizers to
extract a crash-free constraint at the violation location and use dependency
analysis to locate potential fix locations (see more details in Chapter
5.4.1). Due to this fault localization step, they build an analytical
understanding that helps define repair strategies that can go beyond disabling
vulnerabilities at their crash locations. They propagate the crash-free
constraint to the identified fix locations by computing the weakest pre-
condition, which is used to synthesize a minimal fix.

Instead of deductive reasoning, APR techniques can also follow an inductive
reasoning approach that attempts to learn a fix pattern or infer a patch
invariant. For example, (Chen et al., 2021a) apply neural transfer learning to
repair security vulnerabilities. Learning-based program repair (see Chapter 4)
attempts to extract general repair transformations from human-written patches.
Transfer learning means learning from one domain to solve problems in a
different domain. This is interesting in the context of security
vulnerabilities because the available data for security repair is relatively
small, while the data set for general bug fixes is significantly larger.
Therefore, (Chen et al., 2021a) attempt to learn a neural model on general bug
fixes (source domain) and tune it on security vulnerabilities (target domain).
Intuitively, it uses source domain training to understand how general code
modifications and patch generation can be accomplished, while training in the
target domain fine-tunes the model for the specific set of vulnerabilities.
Their empirical evaluation shows that the model trained with transfer learning
performs better than a model only trained on the target domain.

Figure 20. Workflow illustrating inductive inference for security repair
(Zhang et al., 2022).

More recently, (Zhang et al., 2022) presented VulnFix to repair security
vulnerabilities using inductive inference. Figure 20 shows the proposed
workflow. It starts with common input-level fuzzing to build a test suite that
can reach the crash and patch locations. These initial tests are expected to
be diverse; some trigger the vulnerability, and some do not. With these tests,
VulnFix extracts snapshots, i.e., the program states at the given patch
location. Therefore, the initial test suite leads to a pool of initial
snapshots, from which VulnFix infers initial patch invariants by using dynamic
invariant inference systems like Daikon (Ernst et al., 2007) and cvc5 (Barbosa
et al., 2022). One of the key elements of (Zhang et al., 2022)’s work is their
subsequent snapshot fuzzing, which mutates the states instead of inputs to
identify counterexamples that prove the current patch invariants as
insufficient and which guide their refinement. Snapshot fuzzing may lead to
infeasible states. However, the resulting patch invariant is still helpful as
it will hold for both feasible and infeasible states. As a general limitation
of inductive inference techniques, VulnFix may disable benign behavior because
it over-approximates the necessary patch invariant.

##### Static analysis driven security repair

Static analyzers like Infer (Calcagno et al., 2015) are extensively applied in
the industry to detect security vulnerabilities. In particular, Infer uses
separation logic to detect violations of pointer safety properties. For
example, this covers resource leaks and memory leaks potentially caused by
doubly freeing memory and null dereferences. Techniques like Footpatch (van
Tonder and Goues, 2018) and Saver (Hong et al., 2020) use Infer to generate
repairs for the identified vulnerabilities. Depending on the identified bug
type, Footpatch uses pre-defined repair templates to generate a repair
specification, which defines the error heap configuration $F$ and the fixed
heap configuration $F^{\prime}$. Then Footpatch searches for a patch, here
called repair fragment $C$, that allows transforming $F$ to $F^{\prime}$. By
filling in the specifics for the considered scenario, this becomes a Hoare
triple with a hole for $C$. Finally, Footpatch searches over the existing
program fragments to identify the desired semantic change. (van Tonder and
Goues, 2018) decided to only consider additive program transformations based
on their observation that the considered bug type (memory and resource leaks)
typically are caused by missing heap operations like the releasing of
resources, freeing of memory, or null checks. One disadvantage of Footpatch is
that it might introduce new double-free or use-after-free vulnerabilities as
part of their patches because it only focuses on the original error report.
MemFix (Lee et al., 2018) instead focuses on adding deallocation statements to
repair all double-frees and use-after-frees. As a result, they guarantee not
to cause new vulnerabilities with the generated patches but suffer from low
scalability. Saver (Hong et al., 2020) improves on these works and adds
support for conditional deallocation and also relocation of pointer
dereferences. They formulate the memory error repair problem as a graph
labeling problem and thereby can provide a scalable and safe repair technique.

Based on described trends in security vulnerability repair, it does not sound
too futuristic to expect auto-generated security patches during a live
programming session to avoid security vulnerabilities even before the
corresponding program code is submitted. The following section discusses such
integrations into the development workflow in more detail.

###  7.2. Integration in Development Workflow

Integrating APR techniques into the development workflow will be the last
impediment to deploying APR in practice. There are two major possibilities,
the integration into development tools like IDEs, which can give immediate
support during the code writing or during unit testing, and the integration
into CI workflows, where a repair bot can test and repair committed code
changes.

####  7.2.1. IDE Integration

The integration of APR into development tools like IDEs can come in various
variants and degrees. For example, the patches can be generated offline but
illustrated in the IDE. Alternatively, patches can be generated along with a
unit test run and presented as suggestions. However, such interactive and
direct integration would require almost real-time patch generation and is
challenging for current APR techniques. (Campos et al., 2021) investigated the
second variant; their idea is to provide developers with a repair technique
that acts like real-time syntactic code suggestions but for semantic errors.
Therefore, they implemented a Visual Studio Code extension. Figure 21
illustrates their general flowchart.

Figure 21. Flowchart proposing an IDE integration (Campos et al., 2021).

With saving the changed file, the defined workflow triggers unit testing, and
if tests fail, the APR background will attempt to identify faulty locations
and propose patches. Since the patch generation must be fast, (Campos et al.,
2021) deploy a mutation-based approach (Debroy and Wong, 2010). The mutations
are limited to replacing arithmetic, relational, logical, increment/decrement,
and assignment operators with another operator from the same class.
Additionally, they negate decisions in if and while statements. The empirical
evaluation in (Campos et al., 2021) indicates that developers with such an
IDE-integrated APR technique can reach a solution faster than developers
without such support. Having an interactive repair approach can help with
filtering patches by showing them to the developers and letting them decide to
accept or reject them. The interaction can also go beyond that and be more
proactive by sending specific queries and questions to the developers. For
example, instead of showing the generated patches, (Liang et al., 2021)
extract attributes related to the patch location and the affected execution
trace. Then they formulate questions that can filter multiple patches based on
the answers by the developers. Their user study with 30 developers revealed
that questions about the affected variable values help most to distinguish and
filter patches. Furthermore, their technique helps developers’ understanding,
can reduce the debugging time on average by up to 28%, and can increase the
success rate of finding a correct patch by up to 62.5%. Even if no correct
patch can be generated, the information about the fault locations and a
partially correct patch can be helpful for the developers to study the issue
themselves and find a solution. Even deeper integrated, APR can support the
interactive debugging of bugs (Reiss and Xin, 2022). In addition to asking the
developers about the generated patches, it also can help to query information
about the expected behavior as shown in (Böhme et al., 2020) (as discussed in
Chapter 5.5). Overall, integrated into the development tools and debugging
process, e.g., as an IDE plugin, APR can provide valuable insights to support
the developer in understanding and solving the issue.

####  7.2.2. Repair Bots

Instead of direct and integrated support for the developer, APR also can be
deployed with existing CI pipelines of development teams. In fact, in a recent
developer survey (Noller et al., 2022), the integration into these toolchains
was a major requirement for developers to accept the APR technology in
practice.

##### Human-Competitive Repair Bots

To be a real benefit for the developer, who is the user in this scenario, the
integrated repair must fulfill two aspects: it needs to be fast, faster than
other developers, and the repair must be of high quality so that a human
reviewer will accept the patch. These are known challenges in the human-
competitive task (Koza, 2010) and usually appear when designing task
automation, i.e., when automated technologies are applied to solve tasks that
humans usually perform. (Monperrus et al., 2018) investigated APR on its
readiness to tackle the human-competitive task by implementing and deploying a
repair bot on GitHub. The bot is called Repairnator and is specialized in
fixing build errors. (Monperrus et al., 2018) demonstrated that Repairnator
can compete with the human developer and successfully generated patches for
five reported bugs, which the human developers have merged. Although build
failures are just one error type, it showed that successful APR integrations
are possible and within reach.

##### Principles for Program Repair Bots

(van Tonder and Le Goues, 2019) define general requirements and principles for
the engineering of repair bots. They emphasize that a repair bot needs to
generate well-formed syntax for potentially many programming languages, called
syntax generality. Furthermore, generated patches can be syntactically
validated by compiling the modified source code. However, this can become
costly if many compiler toolchains are needed to support a multi-language
setup. Instead of an analytical approach, constructive syntax validation
solutions can be built into mutation operators, e.g., to ensure that general
syntax attributes like parentheses are well-balanced so that no syntactically
invalid code is produced. After passing the syntax check, the patches need to
be validated semantically, e.g., using available test suites and static
analysis checks. All patches should be post-processed with auto-formatting
tools to adhere to organization-specific coding guidelines and maintain
readability. The final ”gatekeeper of program changes” will be humans, even
for automatically generated patches. Therefore, the developer must be
supported for efficiently reviewing the generated patches. Patch explanations
and their easy accessibility via patch rankings (Noller et al., 2022) will be
a key aspect for future repair bot developments.

##### Interactive CI Bots

Interactive program repair that uses user inputs to guide the repair process
applies not only to the IDE scenario but also in the continuous integration
context. For example, (Baudry et al., 2021) show how a repair bot can be
gradually improved by incorporating human patches and feedback on auto-
generated patches. The bot is called R-Hero and Figure 22 shows its approach
overview. It maintains two databases: one for human patches collected via
GitHub Actions and Travis CI and one for auto-generated patches labeled as
correct or incorrect (based on the developers’ feedback). Starting from a
failing build observed in the continuous integration, R-Hero attempts to
localize the error and generates a patch by using a neural network-based
repair technique (Chen et al., 2021b). The collected human patches help to
train and improve the neural network continually. After testing, the patches
are additionally filtered using the overfitting detection system ODS (Ye et
al., 2021). It uses supervised learning leveraging the human patches and the
labeled auto-generated patches to distinguish correct patches from overfitting
patches. Finally, the generated patch is provided to the developer as a pull
request. So far, continual learning with R-Hero has two major limitations: it
is only trained on one-line patches and hence, does not handle complex and
multi-line patches. Further, the prototype implementation does not scale and
needs further optimizations. Nevertheless, the concept shows what an
interactive and integrated program repair approach can look like.

Automated program repair cannot only support developers in their daily work
but also can be integrated into other domains, e.g., programming education.
The following section discusses these opportunities and the existing advances.

Figure 22. Program repair bot based on continual learning (Baudry et al.,
2021)

###  7.3. Support Programming Education

With a rising number of CS students, the need for scalable programming
education is becoming more and more important. Massive Open Online Courses
(MOOCs) (Masters, 2011) will shape the near future of computer science
teaching and students will require feedback for their programming assignments.
Hiring more and more tutors is not scalable, so that eventually the usual
tutor-student interaction will be reduced or completely missing. Providing a
personalized feedback in such an impersonal environment is one of the major
challenges.

##### Goal and Ingredients

APR’s goal is to generate patches for incorrect software, so why not run APR
on students’ solutions for programming tasks? The ingredients for APR are
available: a programming task usually comes with a problem statement, for
which the student submits a solution as source code, the lecturer/tutor has a
private reference implementation, which correctly implements the required
functionality, and furthermore, there usually are test cases to validate the
submitted solution. Additionally, there could be pre and post conditions,
specific performance requirements, a specific error model provided by the
tutor, and historical student submissions that can be labeled as correct and
incorrect solutions. While students can be supported by just providing
information on failing test cases, it would be way more beneficial to show
students how to correct their own code. APR generates patches, i.e.,
instructions on how to change incorrect software to correct software, and
hence, provides a well-fitted basis to support students in their learning
endeavour.

##### Solutions

(Singh et al., 2013) presented initial ideas on how to construct some auto-
grading and auto-feedback mechanisms. They assume to have the reference
implementation and some error model. The error model is expressed in their own
language Eml and contains a set of rewriting rules for typical student
mistakes and their possible corrections. The incorrect student’s solution is
rewritten with these rules, which leads to multiple patch candidates annotated
with the necessary correction costs. By symbolically exploring the patch space
and using counter-example guided synthesis (CEGIS) (Lezama, 2008), it
identifies the solution with the minimal cost. The messages associated with
the error model’s rewriting rules and the affected source line numbers are
used to generate natural language feedback for the student.

For instance, Figure 23 shows an example of a student’s buggy program and
corresponding feedback generated by (Singh et al., 2013). This task requires
students to write a program computing the derivative of a polynomial, whose
coefficients are represented as a list of integers. For example, if the input
list poly is [2, -3, 1, 4] (denoting $f(x)$ = 4$x^{3}$ \+ $x^{2}$ \- 3$x$ \+
2), the computeDeriv function should return [-3, 2, 12] (denoting the
derivative f’($x$) = 12$x^{2}$ \+ 2$x$ \- 3). In this program, student made
several mistakes: 1) the return value at line 5 is wrong, which should be
return[0]; 2) the range at line 6 should be range[1, len(poly)], 3) the
comparison in line 7 should check not-equation. To help student fix this bug,
the right part of Figure 23 presents the auto-generated feedback for students.

⬇

1def computeDeriv(poly):

2 deriv = []

3 zero = 0

4 if (len(poly) == 1):

5 return deriv

6 for expo in range (0, len(poly)):

7 if (poly[expo] == 0):

8 zero += 1

9 else:

10 deriv.append(poly[expo]*expo)

11 return deriv

Generated Feedback:

  * •

In the return statement return deriv in line 5, replace deriv by [0].

  * •

In the comparison expression (poly[expo] == 0) in line 7, change (poly[expo]
== 0) to False.

  * •

In the expression range(0, len(poly)) in line 6, increment 0 by 1.

Figure 23. A student’s program and corresponding auto-generated feedback
(adapted from (Singh et al., 2013))

Going forward, (Gulwani et al., 2018) applies a wisdom of the crowd approach
and builds its repair technique based on collected, correct student solutions.
First, it clusters the existing solutions based on their structural and
variable mapping. Then, it matches the incorrect student submission to find
the best fitting cluster, which is subsequently used to repair the incorrect
solution. The repair starts with generating all possible local repairs that
replace expressions from the incorrect solution with their counterparts in the
collected cluster. Each local repair gets assigned a cost value based on the
tree edit distance between the abstract syntax trees of the involved
expressions. Note that there can be many local repairs, and the goal is to
find a consistent subset of repairs that eventually lead to a correct patch
with minimal total cost. Therefore, (Gulwani et al., 2018) formulate a 0-1 ILP
problem that can be solved with off-the-shelf ILP solvers. After selecting the
subset of local repairs, it generates a textual description of the necessary
repair steps and presents it to the students. A user study with students from
introductory programming courses showed that feedback could be quickly
generated (i.e., within 60 seconds) for most of the assignments and indicated
that the generated feedback is indeed helpful for the students.

##### Related Quality Attributes

Beyond these existing techniques, (Wang et al., 2018) define various quality
attributes crucial for proper student grading and feedback: Ideally, such a
system is fully automated so that it does not require manual efforts like the
provision of patch templates or typical errors. It should provide a minimal
patch to illustrate the minimal effort needed to repair the student’s
submission so that the student can focus on the problematic part. The repair
operators should allow simple and complex repair modifications. Furthermore,
the system should be portable to other programming languages to enable
universal support of programming exercises. (Wang et al., 2018) propose a
high-level data-driven framework that follows three steps: search for closely-
related correct solutions in the pool of available submissions that can be the
basis for repairing an incorrect solution, align the identified programs to
extract the necessary repair transformations, and repair the incorrect
submission by finding a minimal set of transformations. They integrated their
system with the Microsoft-DEV204.1x course, an online programming course for
C#, and deployed it in production. The collected feedback suggests its
practicality and usefulness.

The overfitting issue in APR (see Chapter 5) also applies to APR in
programming education. When techniques rely on high-quality test suites, they
may produce incorrect feedback because large test suites are unavailable or do
not have the required quality. While expert programmers may still use partial
fixes or repair artifacts (Liang et al., 2021), this is not expected from
students (Yi et al., 2017). Instead, students and novice programmers highly
rely on the correctness of the auto-generated feedback. (Ahmed et al., 2022)
is tackling this issue by providing verified repairs. They attempt to verify
the equivalence between the reference solution and the student’s submission,
and with each failed attempt, they retrieve a counterexample that guides the
repair generation. Therefore, they enforce the semantical equivalence between
patch candidate and the reference solution; hence, the finally generated
repair can be trusted by the students. Furthermore, the whole repair process
operates in a reasonable timescale of less than 30 seconds, which shows
potential for a live feedback mechanism.

##### What is good feedback?

While the research and tool development continues, e.g., (Lu et al., 2021)
proposed a lightweight technique that outperforms previous work in generation
speed and number of repaired programs, one main issue remains unsolved, which
is how to provide good student feedback. What makes good student feedback
anyway? Certainly, it is not just reporting failing test cases, and certainly,
it is also not the provision of a fixed solution. While test cases are
helpful, they are not enough to find the correct answer. While the fixed
solution can help understand the problem, it robs the students from solving it
themselves. The key aspect is to guide the students to the correct answer
without revealing the solution upfront. It starts by explaining why something
is wrong in their submission, which can be supported by a failing test case
and a potential fault location. Then, compiler error messages can be
explained, and solution hints can be provided. Step by step, more information
can be revealed. Questions instead of direct information can guide the student
to identify the problem themselves. Eventually, it is not just the technical
aspect of how to quickly generate accurate repairs, but the pedagogical
aspects of the students’ learning experiences that are crucial for deploying
intelligent tutoring techniques.

##### Effect of Introducing Automated Feedback and Grading

While the technical contributions had been partially evaluated with user
studies as well, the evaluation results usually do not report more than an
indication that the generated feedback is helpful. In contrast, (Hagerer et
al., 2021) performed a survey study and examined the effect of introducing
automated grading functionality. Their framework Artemis (Krusche and Seitz,
2018) does not apply automated program repair; however, it provides feedback
on failing test cases and involves static code analysis to measure the code
quality. The study shows that programming courses that use Artemis receive
higher ratings, the students are more satisfied with the tutors, and the
students’ perceived programming learning experience improved. Possible reasons
for these trends are the automated feedback and the reduced correction biases
by the automated grading. Moreover, by introducing the automated platform,
tutors have more time to focus on their student’s needs.

###  7.4. Patch Transplantation

A related but different problem to program repair is automated patch
transplantation. The key motivation is that if there is already a patch, but
for a different, albeit similar, application, one can attempt to transplant
this patch to the current buggy program instead of generating a patch from
scratch. As an early work in this area, (Sidiroglou-Douskos et al., 2015)
developed a code transfer system to transplant missing checks. Their
transplantation process assumes two program inputs, one that triggers the
error and one which does not. Then they use a database of applications to
search for a donor that passes both inputs and includes a check necessary to
reject the error-triggering input. Next, by using symbolic execution, they
extract the corresponding input constraint and translate it into the namespace
of the target application. Subsequently, they identify potential insertion
points in the target application, at which the necessary input fields are
available as program expressions. (Shariffdeen et al., 2021c) systematically
explore the general patch transplantation problem and define it formally as
follows. As illustrated at Figure 24, given a so-called donor program with its
buggy version $P_{a}$ and its fixed version $P^{\prime}_{a}$, the goal is to
modify the buggy host or target program $P_{b}$ to produce a fixed version
$P^{\prime}_{b}$. The two programs $P_{a}$ and $P_{b}$ are assumed to be
“similar”. $P^{\prime}_{b}$ is created by transplanting the patch
$P_{a}\rightarrow P^{\prime}_{a}$ to $P_{b}$., i.e., extract, adapt, and
integrate the patch.

Figure 24. The automated patch transplantation problem (adapted from
(Shariffdeen et al., 2021c))

For instance, Figure 25 presents patch transplantation between LibGD and
Libtiff, two image processing libraries. A bug in Libtiff causes an overflow,
since the maximum LZW bits (represented using variable datasize and c in
Figure 25(a) and 25(b), respectively) allowed in GIF standard is 12, otherwise
a bugger overflow will be triggered. This can be fixed by inserting a check as
shown in Figure 25(a). This vulnerability also exists in LibGD and ImageMagick
libraries which are also image processing software similar to Libtiff. All
three programs are vulnerable to the same exploit because they follow the same
standard for GIF image processing. Therefore, the patch from Libtiff can be
transplanted to LibGD via patch extraction, adaptation, and integration. The
adaptation required for the patch is the namespace mapping from datasize in
Libtiff to c in LibGD.

⬇

1int readraster ( void ) {

2 …

3 datasize = getc(infile);

4+ if (datasize>12)

5+ return 0 ;

6 clear = 1 << datasize;

7 eoi = clear + 1;

8 …

9}

(a) Developer patch for Libtiff 4.0.4

⬇

1static void ReadImage (…) {

2 …

3 if (ReadNotOK(fd, \&c, 1)) {

4 return;

5 }

6+ if ( c > 12)

7+ return;

8 …

9}

(b) Developer patch for LibGD 2.0.34 RC1

Figure 25. Patch transplantation example between two image processing
libraries

##### Transplantation Patch Classes

Shariffdeen et al. (2021c) define a hierarchy of four patch classes; with
increasing levels, it becomes more difficult to transplant the patch
successfully. Class I: Syntactically Equivalent Transplantation represents the
case where no adaption is needed because the same syntactical patch can be
copied from the donor program to the target program. Therefore, class I is the
simplest scenario of patch transplantation. Class II: Syntactically Equivalent
Transplantation with Dependency means a missing dependency like a function
that is not present in the target program. The transplantation process needs
to detect and include it in the patch. Class III: Semantically Equivalent
Transplantation represents the case where it requires the adoption of the
patch to enable the transplantation to the target system because of syntactic
differences between both programs. For example, it could be necessary to
perform a namespace translation. Class IV: Semantically Equivalent
Transplantation with Dependency means the need for adoption and the detection
of missing dependencies.

##### Transplantation Process

The transplantation process starts with patch extraction, which analyzes the
source diff between $P_{a}$ and $P^{\prime}_{a}$ along with the execution
trace. Next step is to identify the appropriate insertion point $P_{b}$ and
adopt the patch accordingly to the context in $P_{b}$. To identify the best
insertion point, one can compare the dynamic execution traces between all
programs $P_{a}$, $P^{\prime}_{a}$, and $P_{b}$, and check which divergence
point in $P_{b}$ matches best the divergence between $P_{a}$ and
$P^{\prime}_{a}$. Concolic execution supports this task by extracting the
symbolic path constraints, which helps identify the program part that handles
the same input partition as the donor program. Furthermore, it collects the
symbolic values for the variables relevant to the patch. With this
information, the various variables in the three programs can be mapped to each
other. It allows us to compare the variable usages and hence, to identify the
candidate function to transplant the patch between the divergence point and
the crash location. After identifying the insertion point, the patch needs to
be translated to the namespace of the target program $P_{b}$. Additionally,
one needs to check the context and dependencies of the patching code, e.g., to
identify functions that are called in the patch but are not present in the
target program. As in general program repair, the program modification must be
followed by validation. For example, the generated $P^{\prime}_{b}$ can first
be syntactically checked, and if successful, a differential fuzzing campaign
can search for differences between the $P_{b}$ and $P^{\prime}_{b}$.

##### Transplantation Use Cases

Two prominent practical use cases are concerned with patch transplantation:
(1) the propagation of patches from a different implementation, e.g., the same
protocol or functionality, and (2) the backporting of patches from a current
version to an older software version. The second use case is studied by
(Shariffdeen et al., 2021a) in the context of security patches in the Linux
Kernel. From 2011 to 2019, 8% of all patches in the Linux Kernel have been
backported to an older version, while for 50% of these patches, it took the
developers more than 46 days until the patch made it to the older version.
Therefore, there is a need for automated techniques to support the developers
in this process. (Shariffdeen et al., 2021a) synthesize the necessary
transformation rules by using a domain-specific language (DSL) tailored to
define transformation rules in the context of patch backporting. Other related
use cases are the transplantation of features (Barr et al., 2015) and test
cases (Zhang and Kim, 2017), which both may require the application of
automated program repair on top of them.

##  8\. Perspectives

After illustrating the state of the art and its achievements in the previous
chapters, we end this article by gauging different future-looking perspectives
on automated program repair. We show the need for repair technology
deployments that fit into existing workflows like the continuous integration
system. To this end, we present the first results of a field study on
developer interest in repair (Noller et al., 2022). This may provide some
perspectives on how the future works on automated program repair can shape up.
Next, we provide a perspective on the recent growth of Language models such as
GPT-3 as embodied in the GitHub Copilot. Such language models support the
automated generation of code, and it would be worth studying how automated
repair can work in tandem with such language models in the future (Fan et al.,
2022). Finally, we provide perspectives on how future work can explore the
synergies between testing and repair to provide a unified quality assurance
component in the development workflow.

We conclude the article by revisiting the challenges in program repair
including those which have been partially addressed by current research. We
provide a forward looking outlook of the field at the end by referring to
recent trends in automated coding.

###  8.1. Human Study with 100+ Software Developers

In Chapter 7 we illustrated many applications and possible (and already
achieved) integrations of automated program repair. However, the eventual
success of these applications and integrations in the software development
practices depends mainly on the acceptance of APR by the software developers.
Therefore, to further explore the general developers’ interest in automated
program repair as their daily development companion and to gauge the
possibilities of more intensified field studies, (Noller et al., 2022)
conducted a survey with 100+ software developers to identify requirements and
trust-related aspects for APR. The survey focused on three core topics: (1)
the general acceptability of APR and how developers envision interacting with
APR techniques, (2) the availability of additional specifications or, more
general, input artifacts that can support the APR process, as well as the
expected impact on the trust of the auto-generated patches given that the
additional specifications are taken into account, and (3) the expected
evidence and explanations for generated patches.

(a) How many auto-generated patches would you be willing to review before
losing trust/interest in the technique?

(b) What is an acceptable timeout for APR?

(c) Which of the following additional artifacts will increase your trust?

(d) Which of the following information (i.e., potential side-products of APR)
would help you to fix the problem yourself (without using generated patches)?

Figure 26. Selected survey responses regarding developers’ expectations and
trust aspects in APR (Noller et al., 2022).

##### Acceptance of APR and the envisioned interaction

As an encouraging first insight, 72% of the surveyed developers are willing to
review auto-generated patches, which shows that developers are generally open
to using APR techniques in their development workflow. However, they would not
completely trust patches per default and require a manual review. As evident
from the numbers in Figures 26(a) and 26(b), APR has only a small margin for
maneuver: most developers would only review up to five patches and would
expect them within a 1-hour timeout. Additionally, developers envision a small
amount of interaction, e.g., only to provide initial search ingredients.
Furthermore, developers expect that APR is fully integrated into existing
development workflows like DevOps pipelines. Therefore, the existing works in
APR integration (see Chapter 7.2) are essential steps in achieving the
developer’s acceptance in practice.

##### Artifacts and their impact on trust

The survey responses showed that software developers can provide additional
artifacts that can support the APR process: test cases, program assertions,
logical constraints, execution logs, and potential fault locations. Moreover,
using these user-provided artifacts can positively impact the trustworthiness
of the generated patches. Figure 26(c) shows that the developers have the
impression that, in particular, test cases bear the potential to establish
trust with APR. On the contrary, developers see less potential in repeated
user queries as it would be necessary for an intensive human-in-the-loop
repair approach (see Section 5.5).

##### Patch Evidence and APR side-products

For software developers, it is essential to see evidence and explanations for
the generated patches. Presenting such evidence for the correctness of the
patch and explaining the targeted fault and the repair itself can enable the
developers to select the best patch candidate efficiently. Additional
information, e.g., the code coverage and the ratio of the input space covered
by the patch validation, can act as supporting material for these decisions.
Even when APR tools cannot generate patches, the APR side-products can help
the developers. Figure 26(c) shows that developers find it helpful to receive
information about the identified fault locations, the generated test cases, or
the inferred repair constraints to patch the bug themselves.

##### How to get closer to trust?

The study results show that developers in practice are willing to include APR
in their daily work but are not (yet) ready to trust APR completely. The
preliminary evaluation by (Noller et al., 2022) shows that the collected
requirements by the developers (i.e., the 1-hour timeout and the 5 to 10
patches to review) are tight constraints and are hardly met by the current APR
solutions. Therefore, the APR community needs to keep improving APR’s general
capabilities to generate high-quality patches. Furthermore, we also need to
incorporate aspects into APR that enable developers to efficiently review the
patches so that APR can effectively be integrated into current development
workflows. This way, software development will evolve by using automated
repair technology. To enable the efficient patch review by the developers, an
APR technique needs to support three key aspects: (1) APR needs to give
insights into why the patch targets the right issue, e.g., by showing the
fault/fix localization results and the inferred repair constraints. (2) APR
needs to show evidence for the correctness of the patch, e.g., additional test
cases, test suite coverage information, or input coverage information. (3) APR
needs to provide easy accessibility of the generated patches, e.g.,
appropriate ranking capabilities and the efficient navigation of patch
candidates in the programming environment. Existing APR side products can
already support some of these items, like fault locations and inferred repair
constraints. However, the study also urges more research for patch
explanations, patch ranking, and the efficient traversal of a possibly
abstract patch space.

Beyond the discussed survey, we will require more user studies to identify
which workflows can work and be accepted in practice. In particular, the
interaction between repair tools and software developers is an area, which
will need more focus in the future.

###  8.2. Language Model based Code Generation

Designing AI-based systems to automatically solve programming tasks has gained
considerable attention in recent years. The most notable of these comes in the
form of transformer-based large-scale language models, which used to transform
natural language text. Large language models, such as Codex (Chen et al.,
2021d) and AlphaCode (Li et al., 2022), have also successfully generated code
for many programming tasks in Python, Java, C, etc.

##### Program Repair for fixing Code Generated by Language Model

Codex and AlphaCode have shown capability in generating correct solutions for
many programming tasks. However, the success rate of existing language models
remains low, especially for complex programming tasks. One of the reasons is
that language models lack awareness of program semantics (e.g., type
information, run-time program states, etc.), resulting in incorrect programs.
A large part of bugs made by Codex are syntax errors or misaligned algorithms,
i.e., uncompiled programs or programs with incorrect algorithms. Meanwhile,
some bugs require small changes, e.g., changing operators, modifying
expressions, or changing statements. For instance, Figure 27 shows an example
program produced by Codex for an programming task in LeetCode
999https://leetcode.com. The comments in Figure 27 are the program
descriptions, which are provided to Codex as prompt, and the code is
automatically generated by Codex. Unfortunately, the produced program has a
bug, causing the program to fail on some test cases. The correct fix is to
change statement $i{-}{=}2$ at line 7 to $i{-}{=}1$. Compared to language
models, typical repair tools generate patches by reasoning about the program
semantics against the given specification. Hence, the repair technique has the
potential to increase the success rate of language models. In the above
example, Recoder (Zhu et al., 2021), a recent program repair tool, could
automatically fix the bug and make it pass all the test cases.

⬇

1//A fancy string is a string where no three consecutive characters are equal.
Given a string s, delete the minimum possible number of characters from s to
make it fancy. Return the final string after the deletion. It can be shown
that the answer will always be unique.

2public String makeFancyString(String s) {

3 StringBuilder sb = new StringBuilder(s);

4 for (int i = 2; i < sb.length(); i++) {

5 if (sb.charAt(i) == sb.charAt(i-1) && sb.charAt(i) == sb.charAt(i-2)) {

6 sb.deleteCharAt(i);

7\- i -= 2;

8\+ i -= 1;

9 }

10 }

11 return sb.toString();

12}

Figure 27. The program for a LeetCode programming task generated by Codex.

##### Language Model for Program Repair

Language models could also be used for fixing software bugs. In March 2022, a
new version of Codex edit mode was released. Instead of just translating
program descriptions to programs 101010https://openai.com/blog/gpt-3-edit-
insert, the Codex edit model can change existing code in a complete program.
This new feature makes it practical to use Codex for program repair. Codex
edit mode requires users to provide instructions to guide the code change,
such as “fix the bug at line 2”, or “fix the index-out-of-bound exception”. To
fix a bug, users need to provide precise and clear instructions.

The repair based on large language models could even produce better
performance in fixing software bugs than learning based repair techniques.
Compared to existing learning-based repair, e.g., SequenceR and Recoder, Codex
is trained on a much larger dataset than Recoder, which helps Codex to learn
more fix patterns (see (Fan et al., 2022) for comparison results). In fact,
large language models learn code edit patterns from huge existing programming
artifacts (including code, commits, comments and etc.). For instance, the
existing search-based approaches like GenProg and TBar, may not be able to fix
bugs that require either (1) additional fix patterns, or (2) a large search
space for fix ingredients (e.g., specific literal). This limitation shows that
a pattern-based APR tool is hard to scale. Instead of manually adding more
patterns to a new APR tool, future APR research on designing fixing operators
should shift to a more scalable way (automatically learn fix patterns from
huge programming artifacts).

We thus postulate that language model based repair approaches could play a
significant role in future, in achieving the capabilities of search-based,
pattern-based and learning-based repair techniques. At the same time, the
relationship of the language model based approach with respect to program
synthesis is not well-understood today (see (Jain et al., 2022) for an initial
work). Since semantic repair approaches (or constraint based repair
approaches) rely on a program synthesis back-end, there exist opportunities in
combining semantic repair approaches with language model based repair in the
future.

###  8.3. Synergies of Testing and Repair

To conclude our perspectives, we want to allude to the integration of repair
into the development workflow by merging testing and repair. In Section 5.4.2,
we already discussed the concept of Concolic Program Repair (CPR) (Shariffdeen
et al., 2021b), which proposes the co-exploration of input and patch space to
prune overfitting patches, and hence, to establish a notion of gradual
improvement. The simultaneous exploration of test inputs and patches hold the
potential to amplify the overall search. Over time, additional tests are
systematically generated, and patch suggestions are systematically refined.
Developing the ability to refine the patches gradually, it will become crucial
to have an efficient representation of patches and sets of patches.
Eventually, such a co-exploration repair system aims at converging to a
correct patch. Throughout the search process, we can start engaging with the
developer. Thus, the developer can guide the search, and the generated
artifacts provide insights to increase patch comprehension.

Figure 28. Fuzzing based co-exploration input space and program edits.

CPR leverages symbolic/concolic execution to generate tests automatically.
However, using symbolic execution requires working with a symbolic execution
engine which is non-trivial. Hence, one can alternatively employ a
(systematic) fuzzing technique such as (Böhme et al., 2017). Thus, finding
inputs exposing vulnerabilities can be viewed as a biased random search over
the space of program inputs. Similarly, the process of automated program
repair has also been cast as a biased random search over the space of program
edits. As a result, these searches can strengthen each other instead of
running as separate processes. As illustrated in Figure 28, the search for
inputs can provide failing test cases that drive the search for program edits.
The search for program edits can identify fix locations (e.g., see (Shen et
al., 2021) for preliminary work) and repair constraints derived from
sanitizers, which further help to concentrate the search for inputs around
these locations. The workflow (of the two searches strengthening each other)
resembles an any-time patching/synthesis method that can be stopped anytime,
where the correctness of the generated code gradually improves over time. More
importantly, it closes an important gap in today’s vulnerability discovery
where software vulnerabilities are detected typically via fuzzing, and then
the software remains exposed to these published vulnerabilities, which remain
unfixed for long. We can view such as program protection mechanism (fuzzing
and patching together) as a new software process, where a program is subject
to fuzzing and patching at the same time.

###  8.4. Revisiting the challenges

Despite the achievements in automated program repair, there are still
challenges left and research work to do. The overfitting issue (discussed in
Chapter 5) can be mitigated by the generation of additional test cases and
patch ranking based on syntactic and semantic distance. However, since the
developer’s intention is rarely completely formalized, it remains a challenge
to identify high-quality patches that are inspired by the provided
specification but are general enough not to overfit. Related to this issue is
the validation of plausible patches. While we can rule out patch candidates
that violate a given specification, it is generally hard to determine a
correct patch. Even a given developer patch from a benchmark might not be the
only way to repair it. To help these issues, one way would be to perform
additionally automated (or semi-automated) specification inference. There has
been significant advancements in this direction as mentioned in this article.
At the same time, it will continue to be an area of interest in automated
program repair

Another challenge remains in complex repairs. Many existing techniques focus
on repairing errors, which can be repaired with a single-line fix. However,
errors can also require the modification of large code chunks or edits at
multiple locations. Again as discussed, there has been significant progress
and repair tools like Angelix can produce multi-line fixes. Because of the
inherent search space explosion involved in navigating/constructing multi-line
fixes, this problem is likely to capture developer’s attention in the future
as well.

Repair techniques will also generally suffer from the scalability issue. Due
to many possible combinations of fix locations, the identification of a
plausible repair would require the exploration of a large search space which
might be infeasible with current exploration and validation strategies and
current patch space abstractions. As an implementation issue, the scalability
challenge is particularly exacerbated due to the need for recompilation, when
a search space of patch candidates is being traversed by a program repair
tool. Solutions via bytecode mutation have been explored for Java programs
(Ghanbari et al., 2019). These approaches avoid repairing at the source code
level. However, to avoid recompilation in C program repair, one would need
capabilities of binary interpretation and binary rewriting. This is because we
will not have bytecode level intermediate representation to work with, for C
program repair.

In the end, the repair technology must be deployed where developers can easily
integrate it into existing workflows like the continuous integration system.
Existing industry deployments have already outlined a path for technology
adoption. However, many questions remain to be answered, like how an efficient
interaction between developers and repair tool can be established and how
repair techniques can produce trustworthy patches.

###  8.5. Future Outlook

Automated program repair (LeGoues et al., 2019) is an emerging technology
which seeks to reduce manual burden via automated fixing of errors and
vulnerabilities. Apart from improving programmer productivity — automated
program repair technology has usage in reducing exposure of software systems
to security vulnerabilities. Automated program repair techniques can also be
used for programming education - where by repairing a student’s programming
attempt automated feedback can be given to students struggling to learn
programming.

In terms of technology, initial attempts at solving program repair were
focused on using meta-heuristic searches (Weimer et al., 2012). By navigating
an explicitly represented search space of program edits - such techniques can
scale up to large programs but not to large search spaces. In other words,
such techniques can work well on large programs which are ”almost correct” -
where the fix could be lifted from elsewhere in the program (or from past
program versions). To scale up to large search spaces, we effectively need
program repair techniques which can generate complex program edits such as
multi-line edits. This is only possible if the search space of program edits
is implicitly represented say as a symbolic repair constraint. Subsequently,
fixes can be obtained by solving the repair constraint either via program
synthesis (which involves a back-end constraint solving) or via an enumerative
search over an implicitly defined search space. Semantic program repair
techniques (Nguyen et al., 2013) divide the task of program repair into such a
repair constraint generation and patch synthesis steps.

Along with the development of search-based and semantic program repair
methods, researchers have studied the role of machine learning in program
repair. One successful usage of machine learning in program repair is in
ranking candidate patches (Long and Rinard, 2016) after the candidates
obtained by a technique such as enumerative search over a well-defined search
space. Subsequently, a host of pattern-based and learning-based techniques
have been proposed for program repair which steadily try to improve the
quality of patches since the techniques want to ensure that the neural repair
techniques can at least produce compilable programs (Chen et al., 2019).

Though deep learning based techniques have seen significant progress, patch
quality has been one concern, as the learning techniques have no significant
understanding of the program semantics, or even simple program properties such
as program dependencies. Thus, instead of continually improving the quality of
patches produced by deep learning methods - one could use learning techniques
in an alternative fashion for automated program repair. Specifically, we note
that language model based code generation (Chen et al., 2021d), as evidenced
by tools like Github Copilot and AWS Codewhisperer, have recently gained
traction. The recent release of Copilot only a few months ago includes an edit
mode (Codex, 2022) which can edit/insert text, apart from completing text.
Such an enhanced language model based code companion engine can also serve as
a program repair tool. As found in most recent results language model based
code repair can even outperform pattern-based and learning based program
repair tools in fixing automatically generated code (see the report in (Fan et
al., 2022)).

Looking forward, it is feasible to envision a role of language model based
code generator/transformers for automated repair. While the exact role remains
to seen and it is up to future research, we can already observe certain trends
which may be worth commenting upon. If the focus shifts in the future on
significant scaffoldings of code being automatically generated, automated
program repair techniques could be employed to automatically improve the
quality of automatically generated code. While this seems like a tall order at
a first glance - we feel this can beyond engineering prompts for an automated
code generator like Codex. In particular, program artifacts/properties can be
integrated into language models. Alternatively, the various program candidates
generated by a language model based generator can be treated by an augmented
semantic program repair tool, to curate, extract and piece together patch
ingredients - with the goal of generating complex patches via program analysis
of automatically generated code. This can be achieved in many possible ways,
e.g., semantic analysis techniques can be used to find equivalence classes
among partial code snippets obtained from various program candidates, and code
from those equivalence classes can be pieced together into a complete program.
We thus feel that the language model based code generation could provide newer
opportunities (rather than threats) to existing (analysis based) program
repair techniques.

## Acknowledgments

This work was partially supported by a Singapore Ministry of Education (MoE)
Tier 3 grant ”Automated Program Repair”, MOE-000332-01, and National Natural
Science Foundation of China under Grant No (62202026).

The authors would like to acknowledge all our collaborators in the area of
program repair. Discussions with the collaborators have helped us gain
perspectives on the research area. Abhik Roychoudhury would like to thank
Sergey Mechtaev, Shin Hwei Tan and Jooyong Yi for past collaborations in the
area of program repair.

Abhik Roychoudhury would like to thank participants at the following meetings
for valuable discussions which have over the years shaped the reflections on
the field — (a) Dagstuhl seminar 17022 on Automated Program Repair (January
2017), and (b) Shonan meeting 160 on Fuzzing and Symbolic Execution (September
2019).

Several colleagues read and commented on parts of the draft to improve its
readability including Luciano Baresi and Shin Hwei Tan. The authors thank them
for their valuable suggestions.

## References

  * (1)
  * cod (2022) 2022\.  AWS CodeWhisperer.  https://aws.amazon.com/codewhisperer/.
  * Abreu et al. (2007) Rui Abreu, Peter Zoeteweij, and Arjan J.C. van Gemund. 2007\.  On the Accuracy of Spectrum-based Fault Localization. In _Testing: Academic and Industrial Conference Practice and Research Techniques - MUTATION (TAICPART-MUTATION 2007)_. IEEE.
  * AFL (2019) AFL. 2019.  American Fuzzy Lop.  http://lcamtuf.coredump.cx/afl.  [Accessed: 2019-04-08].
  * Ahmed et al. (2022) Umair Z. Ahmed, Zhiyu Fan, Jooyong Yi, O Al-Bataineh, and Abhik Roychoudhury. 2022.  Verifix: Verified Repair of Programming Assignments.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 31, 4 (2022).
  * Bader et al. (2019) Johannes Bader, Andrew Scott, Michael Pradel, and Satish Chandra. 2019.  Getafix: Learning to Fix Bugs Automatically.  _Proc. ACM Program. Lang._ OOPSLA (2019).
  * Barbosa et al. (2022) Haniel Barbosa, Clark W. Barrett, Martin Brain, Gereon Kremer, Hanna Lachnitt, Makai Mann, Abdalrhman Mohamed, Mudathir Mohamed, Aina Niemetz, Andres Nötzli, Alex Ozdemir, Mathias Preiner, Andrew Reynolds, Ying Sheng, Cesare Tinelli, and Yoni Zohar. 2022\.  cvc5: A Versatile and Industrial-Strength SMT Solver. In _Tools and Algorithms for the Construction and Analysis of Systems - 28th International Conference_ _(TACAS 2022)_ , Dana Fisman and Grigore Rosu (Eds.). Springer.
  * Barr et al. (2015) Earl T. Barr, Mark Harman, Yue Jia, Alexandru Marginean, and Justyna Petke. 2015.  Automated Software Transplantation. In _Proceedings of the 2015 International Symposium on Software Testing and Analysis_ (Baltimore, MD, USA) _(ISSTA 2015)_. ACM.
  * Baudry et al. (2021) Benoit Baudry, Zimin Chen, Khashayar Etemadi, Han Fu, Davide Ginelli, Steve Kommrusch, Matias Martinez, Martin Monperrus, Javier Ron, He Ye, and Zhongxing Yu. 2021.  A Software-Repair Robot Based on Continual Learning.  _IEEE Software_ 38, 4 (2021), 28–35.
  * Bavishi et al. (2019) R. Bavishi, H. Yoshida, and MR Prasad. 2019.  Phoenix: Automated Data-Driven Synthesis of Repairs for Static Analysis Violations. In _27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)_.
  * Böhme et al. (2021) Marcel Böhme, Cristian Cadar, and Abhik Roychoudhury. 2021\.  Fuzzing: Challenges and Reflections.  _IEEE Software_ 38, 3 (2021).
  * Böhme et al. (2017) Marcel Böhme, Van-Thuan Pham, Manh-Dung Nguyen, and Abhik Roychoudhury. 2017.  Directed Greybox Fuzzing. In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS)_. ACM.
  * Brooks Jr (1995) Frederick P Brooks Jr. 1995\.  _The mythical man-month: essays on software engineering_.  Pearson Education.
  * Böhme et al. (2020) Marcel Böhme, Charaka Geethal, and Van-Thuan Pham. 2020\.  Human-In-The-Loop Automatic Program Repair. In _2020 IEEE 13th International Conference on Software Testing, Validation and Verification_ _(ICST 2020)_.
  * Calcagno et al. (2015) Cristiano Calcagno, Dino Distefano, Jérémy Dubreil, Dominik Gabi, Pieter Hooimeijer, Martino Luca, Peter O’Hearn, Irene Papakonstantinou, Jim Purbrick, and Dulma Rodriguez. 2015.  Moving fast with software verification. In _NASA Formal Methods Symposium_. Springer.
  * Campos et al. (2021) Diogo Campos, André Restivo, Hugo Sereno Ferreira, and Afonso Ramos. 2021.  Automatic Program Repair as Semantic Suggestions: An Empirical Study. In _2021 14th IEEE Conference on Software Testing, Verification and Validation_ _(ICST 2021)_.
  * Chandra et al. (2009) Satish Chandra, Stephen J. Fink, and Manu Sridharan. 2009\.  Snugglebug: A Powerful Approach to Weakest Preconditions. In _Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation_ (Dublin, Ireland) _(PLDI 2009)_. ACM.
  * Chen et al. (2021c) Lingchao Chen, Yicheng Ouyang, and Lingming Zhang. 2021c.  Fast and Precise On-the-Fly Patch Validation for All. In _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_ _(ICSE 2021)_.
  * Chen et al. (2021d) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021d.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ (2021).
  * Chen et al. (2021a) Zimin Chen, Steve Kommrusch, and Martin Monperrus. 2021a.  Neural transfer learning for repairing security vulnerabilities in c code.  _arXiv preprint arXiv:2104.08308_ (2021).
  * Chen et al. (2019) Zimin Chen, Steve Kommrusch, Michele Tufano, Louis-Noël Pouchet, Denys Poshyvanyk, and Martin Monperrus. 2019.  SEQUENCER: Sequence-to-Sequence Learning for End-to-End Program Repair.  _IEEE Transactions on Software Engineering_ 47 (2019).  Issue 9.
  * Chen et al. (2021b) Zimin Chen, Steve Kommrusch, Michele Tufano, Louis-Noël Pouchet, Denys Poshyvanyk, and Martin Monperrus. 2021b.  SequenceR: Sequence-to-Sequence Learning for End-to-End Program Repair.  _IEEE Transactions on Software Engineering_ 47, 9 (2021), 1943–1959.
  * Codex (2022) Codex. 2022.  Codex edit mode.  https://openai.com/blog/gpt-3-edit-insert/.
  * Debroy and Wong (2010) Vidroha Debroy and W. Eric Wong. 2010.  Using Mutation to Automatically Suggest Fixes for Faulty Programs. In _2010 Third International Conference on Software Testing, Verification and Validation_ _(ICST 2010)_.
  * Durieux et al. (2017) Thomas Durieux, Benoit Cornu, Lionel Seinturier, and Martin Monperrus. 2017.  Dynamic patch generation for null pointer exceptions using metaprogramming. In _2017 IEEE 24th International Conference on Software Analysis, Evolution and Reengineering_ _(SANER 2017)_.
  * Ernst et al. (2007) Michael D. Ernst, Jeff H. Perkins, Philip J. Guo, Stephen McCamant, Carlos Pacheco, Matthew S. Tschantz, and Chen Xiao. 2007\.  The Daikon system for dynamic detection of likely invariants.  _Science of Computer Programming_ 69, 1 (2007), 35–45.
  * Fan et al. (2022) Zhiyu Fan, Xiang Gao, Abhik Roychoudhury, and Shin Hwei Tan. 2022\.  Improving automatically generated code from Codex via Automated Program Repair.  _arXiv preprint arXiv:2205.10583_ (2022).
  * Gao et al. (2019) Xiang Gao, Sergey Mechtaev, and Abhik Roychoudhury. 2019\.  Crash-Avoiding Program Repair. In _Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis_ _(ISSTA 2019)_. ACM.
  * Gao et al. (2021a) Xiang Gao, Arjun Radhakrishna, Gustavo Soares, Ridwan Shariffdeen, Sumit Gulwani, and Abhik Roychoudhury. 2021a.  APIfix: output-oriented program synthesis for combating breaking changes in libraries.  _Proc. ACM Program. Lang._ 5, OOPSLA (2021), 1–27.
  * Gao and Roychoudhury (2020) Xiang Gao and Abhik Roychoudhury. 2020.  Interactive Patch Generation and Suggestion. In _Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops_ _(APR ’2020)_. ACM.
  * Gao et al. (2021b) Xiang Gao, Bo Wang, Gregory J. Duck, Ruyi Ji, Yingfei Xiong, and Abhik Roychoudhury. 2021b.  Beyond Tests: Program Vulnerability Repair via Crash Constraint Extraction.  _ACM Trans. Softw. Eng. Methodol. (TOSEM)_ 30, 2, Article 14 (feb 2021), 27 pages.
  * Gazzola et al. (2019) L. Gazzola, D. Micucci, and L. Mariani. 2019.  Automatic Software Repair: A survey.  _IEEE Transactions on Software Engineering_ 45, 1 (2019).
  * Ghanbari et al. (2019) Ali Ghanbari, Samuel Benton, and Lingming Zhang. 2019\.  Practical Program Repair via Bytecode Mutation. In _Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis_ _(ISSTA 2019)_. ACM.
  * Godefroid et al. (2012) Patrice Godefroid, Michael Y. Levin, and David Molnar. 2012\.  SAGE: Whitebox Fuzzing for Security Testing.  _Commun. ACM_ 55, 3 (mar 2012), 40–44.
  * Goues et al. (2019) Claire Le Goues, Michael Pradel, and Abhik Roychoudhury. 2019\.  Automated Program Repair.  _Commun. ACM_ 62, 12 (2019).
  * Gulwani et al. (2018) Sumit Gulwani, Ivan Radiček, and Florian Zuleger. 2018\.  Automated Clustering and Program Repair for Introductory Programming Assignments. In _Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation_ (Philadelphia, PA, USA) _(PLDI 2018)_. ACM.
  * Gupta et al. (2017) Rahul Gupta, Soham Pal, Aditya Kanade, and Shirish Shevade. 2017\.  Deepfix: Fixing common c language errors by deep learning. In _Thirty-First AAAI conference on artificial intelligence_.
  * Hagerer et al. (2021) Gerhard Hagerer, Laura Lahesoo, Miriam Anschütz, Stephan Krusche, and Georg Groh. 2021\.  An Analysis of Programming Course Evaluations Before and After the Introduction of an Autograder. In _2021 19th International Conference on Information Technology Based Higher Education and Training_ _(ITHET 2021)_.
  * Hong et al. (2020) Seongjoon Hong, Junhee Lee, Jeongsoo Lee, and Hakjoo Oh. 2020\.  SAVER: Scalable, Precise, and Safe Memory-Error Repair. In _Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering_ (Seoul, South Korea) _(ICSE 2020)_. ACM, 13 pages.
  * Hu et al. (2019) Yang Hu, Umair Z. Ahmed, Sergey Mechtaev, Ben Leong, and Abhik Roychoudhury. 2019.  Re-Factoring Based Program Repair Applied to Programming Assignments. In _2019 34th IEEE/ACM International Conference on Automated Software Engineering_ _(ASE 2019)_.
  * Huang et al. (2019) Zhen Huang, David Lie, Gang Tan, and Trent Jaeger. 2019\.  Using Safety Properties to Generate Vulnerability Patches. In _2019 IEEE Symposium on Security and Privacy_ _(SP 2019)_.
  * Jain et al. (2022) Naman Jain, Skanda Vaidyanath, Arun Iyer, Nagarajan Natarajan, Suresh Parthasarathy, Sriram Rajamani, and Rahul Sharma. 2022\.  Jigsaw: Large Language Models meet Program Synthesis. In _Proceedings of the 44th ACM/IEEE International Conference on Software Engineering_ (Pittsburgh, PA, USA) _(ICSE 2022)_.
  * Jha et al. (2010) Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. 2010.  Oracle-Guided Component-Based Program Synthesis. In _Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering_ (Cape Town, South Africa) _(ICSE 2010)_. ACM.
  * Jiang et al. (2021) Nan Jiang, Thibaud Lutellier, and Lin Tan. 2021\.  CURE: Code-Aware Neural Machine Translation for Automatic Program Repair. In _2021 IEEE/ACM 43rd International Conference on Software Engineering_ _(ICSE 2021)_.
  * Jones et al. (2002) J.A. Jones, M.J. Harrold, and J. Stasko. 2002.  Visualization of test information to assist fault localization. In _Proceedings of the 24th International Conference on Software Engineering_ _(ICSE 2002)_.
  * Just et al. (2014) René Just, Darioush Jalali, and Michael D. Ernst. 2014\.  Defects4J: A Database of Existing Faults to Enable Controlled Testing Studies for Java Programs. In _Proceedings of the 2014 International Symposium on Software Testing and Analysis_ (San Jose, CA, USA) _(ISSTA 2014)_. ACM.
  * Kim et al. (2013) Dongsun Kim, Jaechang Nam, Jaewoo Song, and Sunghun Kim. 2013\.  Automatic patch generation learned from human-written patches. In _2013 35th International Conference on Software Engineering (ICSE)_ _(ICSE 2013)_.
  * Kirbas et al. (2021) Serkan Kirbas, Etienne Windels, Olayori McBello, Kevin Kells, Matthew Pagano, Rafal Szalanski, Vesna Nowack, Emily Rowan Winter, Steve Counsell, David Bowes, Tracy Hall, Saemundur Haraldsson, and John Woodward. 2021.  On The Introduction of Automatic Program Repair in Bloomberg.  _IEEE Software_ 38 (2021), 43–51.
  * Koza (2010) John R Koza. 2010\.  Human-competitive results produced by genetic programming.  _Genetic programming and evolvable machines_ 11, 3 (2010), 251–284.
  * Krusche and Seitz (2018) Stephan Krusche and Andreas Seitz. 2018.  ArTEMiS: An Automatic Assessment Management System for Interactive Learning. In _Proceedings of the 49th ACM Technical Symposium on Computer Science Education_ (Baltimore, Maryland, USA) _(SIGCSE 2018)_. ACM.
  * Le et al. (2017) Xuan-Bach D. Le, Duc-Hiep Chu, David Lo, Claire Le Goues, and Willem Visser. 2017.  S3: Syntax- and Semantic-Guided Repair Synthesis via Programming by Examples. In _Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering_ (Paderborn, Germany). ACM.
  * Le et al. (2016) Xuan Bach D. Le, David Lo, and Claire Le Goues. 2016\.  History Driven Program Repair. In _2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER)_.