# Self-Boosted Automated Program Repair

Samuel Benton  The University of Texas at Dallas<EMAIL_ADDRESS>,
Mengshi Zhang  Facebook<EMAIL_ADDRESS>,  Xia Li  Kennesaw State
University<EMAIL_ADDRESS>and  Lingming Zhang  University of Illinois at
Urbana-Champaign<EMAIL_ADDRESS>
###### Abstract.

Program repair is an integral part of every software system’s lifecycle but
can be extremely challenging. To date, researchers have proposed various
automated program repair (APR) techniques to reduce efforts of manual
debugging. However, given a real-world buggy program, a typical APR technique
usually generates a large number of patches, each of which needs to be
validated against the original test suite which incurs extremely high
computation costs. Although existing APR techniques have already leveraged
various static and/or dynamic information to find the desired patches faster,
they are still rather costly. In a recent work, researchers proposed unified
debugging to leverage the patch execution information during APR to help boost
fault localization; in this way, the application scope of APR techniques can
be extended to all possible bugs, e.g., the patch execution information during
APR can help with manual repair of the bugs that cannot be automatically
fixed. Inspired by unified debugging, this work proposes SeAPR (Self-Boosted
Automated Program Repair), the first technique to leverage the earlier patch
execution information during APR to help boost automated repair itself on-the-
fly. Our basic intuition is that patches similar to earlier high-quality/low-
quality patches should be promoted/degraded to speed up the detection of the
desired patches. This experimental study on 12 state-of-the-art APR systems
demonstrates that, overall, SeAPR can substantially reduce the number of patch
executions with negligible overhead. Our study also investigates the impact of
various configurations on SeAPR. Lastly, our study demonstrates that SeAPR can
even leverage the patch execution information from other APR tools from the
same buggy program to further boost APR.

††conference: Arxiv; April 2021; Online Archive††copyright: none

##  1\. Introduction

Software systems persist everywhere in all facets of today’s society; they
drive financial institutions, facilitate communication worldwide, oversee
critical systems, and so forth. Software systems, however, are frequently
distributed with numerous bugs that will eventually lead to severe disasters.
For example, the 5th edition of Tricentis.com’s annual report (2017) shows
that software failures impact half of the world’s population (3.7 billion
people) and $1.7 trillion in assets; it also mentiones that there can be far
more software bugs in the wild than we will likely ever know about (Tri,
2020). Therefore, in practice, it is imperative for developers to fix these
bugs as early as possible with minimal resource consumption. However, manual
bug fixing can be extremely tedious, challenging, and time-consuming since
modern software systems can be extremely complicated (Boulder, 2013).

Fortunately, in lieu of manual bug fixing, researchers have also extensively
studied Automated Program Repair (APR) (Wang et al., 2020; Liu et al., 2019c,
b; Durieux and Monperrus, 2016; Martinez and Monperrus, 2018; Jiang et al.,
2018; Martinez and Monperrus, 2016; Yuan and Banzhaf, 2018; Lou et al., 2019;
Wu et al., 2019; Jiang et al., 2019; Long and Rinard, 2016b; Qi et al., 2015;
Long and Rinard, 2015; Long et al., 2017; Long and Rinard, 2016a), which aims
to automatically fix software bugs to reduce manual debugging efforts. Typical
APR techniques leverage off-the-shelf fault localization (Wong et al., 2016)
techniques (such as Ochiai (Abreu et al., 2007) and Tarantula (Jones and
Harrold, 2005)) to identify potential buggy locations. Then, they leverage
various techniques to generate potential software patches for the potential
buggy locations. Lastly, each generated patch will need to be executed against
the original test suite to find the plausible patches (i.e., the patches that
can pass all the original tests). Note that not all the plausible patches are
the patches that the developers want; thus, developers need to further inspect
the produced plausible patches to derive the final correct ones. To date,
various APR techniques have been proposed, including techniques based on
predefined-templates (Liu et al., 2019c; Ghanbari et al., 2019; Wen et al.,
2018), heuristics (Jiang et al., 2018; Yuan and Banzhaf, 2018; Le Goues et
al., 2012), and constraint solving (Xuan et al., 2017; Xiong et al., 2017;
Martinez and Monperrus, 2018). Furthermore, APR techniques have also drawn
wide attention from the industry, e.g., Facebook (Marginean et al., 2019),
Fujitsu (Saha et al., 2017), and Alibaba (Lou et al., 2020).

Compared with manual bug fixing, APR can automatically fix a number of real-
world bugs within minimal human intervention and can be easily integrated with
the natural workflow of continuous integration lifecycle (e.g., Facebook’s in-
house tool SapFix (Marginean et al., 2019) has been integrated into their
workflow such that any modification to the underlying system are automatically
checked for bugs and fixed if possible). Meanwhile, despite the promising
future of APR, it is not a perfect science and numerous issues still plague
the area. Among the most paramount of these issues are still the time costs
associated with attempting numerous patches for large-scale real-world
systems. Existing studies have demonstrated that the patch validation costs
dominate the APR costs (Chen and Zhang, 2020; Le Goues et al., 2013; Weimer et
al., 2013; Mehne et al., 2018a), since each patch needs to be executed against
the original test suite.

To reduce the APR costs, researchers have proposed various techniques to
reduce the number of patches generated, e.g., based on machine learning (Saha
et al., 2017), code mining (Jiang et al., 2019), and constraint solving (Xuan
et al., 2017). However, prior work has demonstrated that such techniques can
incur the dataset overfitting issue, i.e., the correct patches may be pruned
for many other unstudied cases (Ghanbari et al., 2019). Furthermore,
researchers have also proposed to prioritize all the generated patches to find
the plausible patches earlier. Such existing techniques primarily utilize
static or dynamic information to statically prioritize patches before the
patch validation, e.g., most APR techniques use the suspiciousness values
computed by off-the-shelf fault localization techniques to prioritize the
patch validation. No further reprioritization is employed during the patch
validation process of these tools, leading to limited improvement.

In a recent work, researchers proposed unified debugging (Lou et al., 2020;
Benton et al., 2020) to leverage the patch execution information during APR to
help boost fault localization; in this way, the application scope of APR
techniques can be extended to all possible bugs, e.g., the patch execution
information during APR can help with manual repair of the bugs that cannot be
automatically fixed. Inspired by unified debugging, this work proposes SeAPR
(Self-Boosted Automated Program Repair), the first technique to leverage the
patch-execution information during APR to help boost automated repair itself
on-the-fly. Our basic intuition is that earlier patch execution results can
help better prioritize later patch executions on-the-fly to speed up the
detection of the desired patches (e.g., plausible/correct patches). In this
way, we promote the ranking of the patches similar to the executed high-
quality patches, while degrading the ranking of the patches similar to the
executed low-quality patches. More specifically, we analyze the modified
elements of patches to compute the similarity among patches as patches
modifying similar program elements can exhibit close program behaviors. This
experimental study on 12 state-of-the-art APR systems demonstrates that,
overall, SeAPR can reduce the number of patch validations by up to 78%. Our
study also investigates the impact of various configurations of SeAPR, e.g.,
the formula for patch prioritization, the type of patch-execution matrices
(full or partial), the granularity of modified elements considered for
similarity computation (e.g., packages, classes, methods, or statements), and
additional patch execution information for computing patch similarity. Lastly,
our study demonstrates that SeAPR can even leverage the patch-execution
information from other APR tools for the same buggy program to further boost
the current APR tools.

To summarize, this paper makes the following contributions:

  * •

Direction. This paper opens a new dimension to leverage patch-execution
information to boost automated program repair on-the-fly and can inspire more
future work in this new direction.

  * •

Design. We design the first technique, SeAPR, in this new direction to update
each patch’s priority scores based on its similarity with the executed patches
and the quality of the executed patches.

  * •

Extensive Study. We have performed an extensive study of the proposed
technique on 12 state-of-the-art APR systems for JVM-based languages using the
widely studied real-world bugs from Defects4J.

  * •

Practical Guidelines. The study reveals various practical guidelines,
including (1) SeAPR can substantially speed up the studied APR techniques by
up to 78% with negligible overhead (e.g., less than 0.5 seconds per project),
(2) SeAPR has stable performance when using different formulae for computing
patch priority and different types of patch-execution matrices, (3) finer-
grained modification information and additional fixing pattern information for
patch similarity computation can both further boost SeAPR, and (4) SeAPR can
effectively utilize historical patch-validation results from other APR tools
to boost current APR tools.

##  2\. Related Work

###  2.1. Automated Program Repair

Automated Program Repair (APR) techniques (Wang et al., 2020; Liu et al.,
2019c, b; Durieux and Monperrus, 2016; Martinez and Monperrus, 2018; Jiang et
al., 2018; Martinez and Monperrus, 2016; Yuan and Banzhaf, 2018; Lou et al.,
2019; Wu et al., 2019; Jiang et al., 2019; Long and Rinard, 2016b; Qi et al.,
2015; Long and Rinard, 2015; Long et al., 2017; Long and Rinard, 2016a) aim to
automatically fix software bugs to substantially reduce manual debugging
efforts and have been extensively studied during the last decade. Existing APR
techniques can be categorized into two broad families: (1) techniques that
monitor the dynamic program executions to find runtime violations of certain
specifications and then heal the program via directly modifying the program
runtime state in case of unexpected program behaviors (Long et al., 2014;
Perkins et al., 2009) and (2) techniques that modify program code
representations based on various patch-generation techniques and then validate
each generated patch (e.g., via testing (Le Goues et al., 2012), formal
specification checking (Pei et al., 2014), and static analysis (van Tonder and
Goues, 2018)) to find the final desired patches. In recent years, the code-
representation-level techniques, especially those that leverage testing for
patch validation, have gained popularity as testing is the dominant
methodology for detecting software bugs in practice. Such typical APR
techniques usually include the following phases. (1) Fault localization: APR
techniques first leverage off-the-shelf fault localization techniques
(Martinez and Monperrus, 2018; Yuan and Banzhaf, 2018; Liu et al., 2019b;
Koyuncu et al., 2020; Liu et al., 2019a; Liu et al., 2019c) to localize the
potential buggy locations. (2) Patch generation: APR techniques will leverage
various strategies to generate potential patches for the identified potential
buggy locations. (3) Patch validation: all the generated patches will be
executed against the original test suite to detect the patches that can pass
all the original tests, i.e., plausible patches. Of course, since not all
plausible patches are desirable, patch correctness checking (often done via
manual inspection in practice) needs to be further performed to find the final
correct patches, i.e., the patches equivalent to developer patches.

According to a recent study (Liu et al., 2020), state-of-the-art APR
techniques can be mainly divided into the following categories. (1) Heuristic-
based techniques leverages various heuristics to iteratively explore the
search space of all possible program edits. For example, the seminal GenProg
technique (Le Goues et al., 2012) leverages genetic programming to synthesize
donor code for high-quality patch generation, while the recent SimFix
technique (Jiang et al., 2018) employs advanced code search to obtain donor
code for patch generation. (2) Template-based techniques leverage predefined
fixing templates (e.g., changing “¿” to “¿=”) to perform patch generation.
Such predefined fixing templates can be either manually summarized (e.g., KPar
(Kim et al., 2013)), or automatically inferred (e.g., HDRepair (Le et al.,
2016)) from historical bug fixes. (3) Constraint-based techniques transform
the program repair problem into a constraint-solving problem and leverage
state-of-the-art constraint solvers (e.g., SMT (De Moura and Bjørner, 2008))
for patch generation. For example, Nopol (Xuan et al., 2017) leverages SMT
solvers to encode the bug-correction constraints and further solves the
constraints to synthesize simple expressions to fix buggy conditional
statements. More recently, researchers have also looked into learning-based
techniques (Lutellier et al., 2020; Ding et al., 2020) to directly generate
code patches via learning from historical fixes.

###  2.2. Cost Reduction for APR

Despite the promising future of APR, it can be extremely time consuming due to
the generation and validation of a large number of possible patches. Actually,
the patch validation cost has been shown to dominate the overall APR cost
(Chen and Zhang, 2020; Mehne et al., 2018b). Therefore, researchers have also
looked into various techniques to further speed up APR. To reduce the
validation time spent on each patch, Ghanbari et al. (Ghanbari et al., 2019)
and Chen et al. (Chen and Zhang, 2020) proposed to share the same JVM session
across multiple patch validations; in this way, the patch loading and
execution time can be substantially accelerated for both source-code and
bytecode level APR techniques. In addition, researchers have also proposed to
prioritize and reduce the test executions for each patch to reduce the
validation time for each patch. For example, Qi et al. (Qi et al., 2013)
proposed TrpAutoRepair to prioritize test executions for each patch based on
history information to falsify implausible patches faster; Mehne et al. (Mehne
et al., 2018b) further proposed to reduce the number of test executions for
each patch, since tests not covering the patched location(s) cannot help
validate the patch. To reduce the number of validated patches, almost all
existing APR techniques leverage fault localization and various other
strategies to reduce the possible patch executions. Furthermore, many existing
APR techniques also leverage other available dynamic or static information to
prioritize patch executions to find the desired patches faster (e.g., based on
various fault localization (Wen et al., 2018; Abreu et al., 2007)). Despite
various cost reduction techniques have been proposed, APR techniques are still
rather time consuming for real-world programs (Ghanbari et al., 2019). In this
paper, we propose the first technique to leverage on-the-fly patch execution
information to help better prioritize patch executions. Note that our
technique is orthogonal to all existing patch prioritization techniques and
our experimental results demonstrate that our technique can substantially
speed up state-of-the-art APR techniques with various patch prioritization
strategies.

###  2.3. Unified Debugging

In the past decade, fault localization has been widely used to help APR
identify potential buggy locations for patching. The recent unified debugging
work (Lou et al., 2020; Benton et al., 2020) unifies the traditional process
fault localization and APR in the other direction for the first time. The
basic intuition of unified debugging is that the massive patch execution
information during APR can actually substantially boost fault localization.
For example, if a patch can pass all the tests, it means the patch likely
mutes the impacts of the bug, even though this patch that may not correct; it
can then be inferred that the patched location is highly related to the actual
buggy location, since otherwise the bug impact would not be muted. With
unified debugging, even when APR techniques cannot fix a bug, unified
debugging still analyzes the patch-execution information to provide useful
hints about potential buggy locations to help with manual repair. In this way,
unified debugging can extend the application scope of APR to all possible
bugs, not only the bugs that are automatically fixable.

Inspired by the unified debugging work, we also aim to leverage the wealth of
patch execution information during APR. Meanwhile, there are the following
major differences between our work and unified debugging. First, while unified
debugging aims to leverage patch execution information for manual program
repair, our technique aims to leverage such information to directly boost
automated program repair, i.e., we aim to improve the performance of APR tools
by prioritizing high-quality patches sooner in the validation process. Second,
technique principles are also substantially different. Unified debugging
analyzes the correlation between patch locations and test outcomes to infer
potentially buggy locations, while our work analyzes the correlation among
executed and remaining patches via estimating their behavioral similarities
based on their modified code elements to speed up the detection of desired
patches. In fact, our patch-similarity estimation idea is inspired by an early
work on mutation testing (Zhang et al., 2013), which leverages the
similarities of modified elements of each mutant to perform test
prioritization and reduction for each mutant to speed up mutation testing.

##  3\. Studied Approach

In this section, we first present the necessary preliminaries and basics for
designing our SeAPR approach (Section 3.1). Then, we introduce the detailed
SeAPR approach (Section 3.2). Furthermore, we will also talk about different
variants of SeAPR (Section 3.3). Lastly, we will introduce a further extension
of SeAPR to leverage the patch execution information from other APR tools for
even faster APR (Section 3.4).

###  3.1. Preliminaries

Before further detailed discussion of our approach, we now introduce the key
definitions and concepts in this section.

######  Definition 3.1.

Patch validation matrix: Matrix $\mathbf{M_{v}}$ defines the validation
results of all tests against all patch candidates. In the matrix, each cell
describes the validation result of test $\mathbf{t}$ $\in$ $\mathbf{T}$
against patch $\mathbf{p}$ $\in$ $\mathbf{P}$. Possible values for each cell
are as follows: (1) - if $\mathbf{t}$ remains unvalidated, (2) $\times$ if
$\mathbf{t}$ fails on $\mathbf{p}$ and (3) ✓ if $\mathbf{t}$ passes on
$\mathbf{p}$.

Patch ID | t1 | t2 | t3
---|---|---|---
$\mathbf{p_{b}}$ (buggy ver.) | $\times$ | ✓ | $\times$
$\mathbf{p}$1 | $\times$ | $\times$ | $\times$
$\mathbf{p}$2 | $\times$ | $\times$ | $\times$
$\mathbf{p}$3 | ✓ | $\times$ | ✓
$\mathbf{p}$4 | ✓ | ✓ | ✓

Patch ID | t1 | t2 | t3
---|---|---|---
$\mathbf{p_{b}}$ (buggy ver.) | $\times$ | ✓ | $\times$
$\mathbf{p}$1 | $\times$ | - | -
$\mathbf{p}$2 | $\times$ | - | -
$\mathbf{p}$3 | ✓ | $\times$ | -
$\mathbf{p}$4 | ✓ | ✓ | ✓

Table 1. Example of full and partial patch-validation matrix

Ideally the patch-validation matrix should be full, i.e., every cell should be
✓ or $\times$. In practice, during the APR process, however, most modern APR
tools terminate the test execution for one patch immediately after observing
any failing test on that particular patch, since the primary goal is to find
correct patches and patches which fail any test must not even be plausible. In
this way, the APR process can be largely sped up without sacrificing repair
effectiveness. Meanwhile, not all APR tools employ this strategy so we study
both types of matrices, where some tests remain unexecuted (partial matrices)
versus where all tests always execute (full matrices). Table 1 presents the
example full and partial matrices for four example patches (i.e.,
$\mathbf{p}$1, $\mathbf{p}$2, $\mathbf{p}$3, and $\mathbf{p}$4) on three
example tests (i.e., $t_{1}$, $t_{2}$, and $t_{3}$). Note that the first row
for the patch-validation matrix is always the test execution results of the
original buggy program (i.e., $\mathbf{p_{b}}$).

######  Definition 3.2.

Patch modification matrix: Matrix $\mathbf{M_{m}}$ presents all program
elements modified within each patch. Each cell describes if patch $\mathbf{p}$
$\in$ $\mathbf{P}$ modifies element $\mathbf{e}$ $\in$ $\mathbf{E}$ (i.e., all
possible program elements). Acceptable values for each cell are as follows:
(1) ✓ if $\mathbf{p}$ modifies element $\mathbf{e}$ and (2) - if $\mathbf{p}$
does not modify element $\mathbf{e}$.

Patch ID | $e_{1}$ | $e_{2}$ | $e_{3}$ | $e_{4}$ | Modified Element(s)
---|---|---|---|---|---
$\mathbf{p}$1 | ✓ | ✓ | ✓ | - | {$e_{1}$, $e_{2}$, $e_{3}$}
$\mathbf{p}$2 | ✓ | ✓ | ✓ | ✓ | {$e_{1}$, $e_{2}$, $e_{3}$, $e_{4}$}
$\mathbf{p}$3 | - | ✓ | ✓ | - | {$e_{2}$, $e_{3}$}
$\mathbf{p}$4 | ✓ | - | - | - | {$e_{1}$}

Table 2. Example of patch modification matrix

Note that the patch modification matrix can be defined at different levels
(e.g., at the package, class, method, and statement granularities) depending
on the granularity of considered program elements. For example, at the default
method granularity, the columns will be the methods modified by each program
patch. Table 2 presents an example patch modification matrix for the above
four example patches on four program elements (i.e., $e_{1}$, $e_{2}$,
$e_{3}$, and $e_{4}$). In this way, since $\mathbf{p}$1 patches program
elements {$e_{1}$, $e_{2}$, $e_{3}$}, the first three columns are ✓ for
$\mathbf{p}$1.

###  3.2. Basic SeAPR

Given the above introduced patch-validation matrix and patch-modification
matrix (which are readily available for almost all APR tools) for the already
executed/validated patches, our SeAPR performs on-the-fly patch prioritization
to speed up APR. Our basic intuition is that patches similar to executed high-
quality patches are likely to also be high-quality and should therefore be
prioritized earlier; likewise, patches rather similar to executed low-quality
patches should be deprioritized as they are likely to produce low-quality
patches. In this section, we first introduce our definitions for patch quality
(Section 3.2.1); then, we introduce the detailed strategy to compute patch
similarity with high- or low-quality patches (Section 3.2.2); we introduce our
final priority score computation for all unexecuted patches (Section 3.2.3);
lastly, we present our overall algorithm (Section 3.2.4) with corresponding
examples (Section 3.2.5).

####  3.2.1. Patch Quality

When processing the patches that have been executed/validated, we need to
estimate the patch’s quality by analyzing the patch validation matrix.
Intuitively, the ultimate goal of APR is to produce plausible patches that can
pass all the original tests. Therefore, whether a patch passes some originally
failing tests can be used to estimate the patch quality. Therefore, in this
study, a patch is classified as high-quality (patches we wish to prioritize)
if it can make any originally failing test pass; likewise, a patch is
classified as low-quality (patches we wish to deprioritize) if it cannot make
any originally failing test pass. Formally, the set of high-quality and low-
quality patches can be defined as Equation (1) and (2), respectively.

(1) $\mathbf{P_{h}}$ = { $\mathbf{p}$ — $\exists$ $\mathbf{t}$,
$\mathbf{M_{v}}$[$\mathbf{p}$,$\mathbf{t}$] = ✓ $\wedge{}$
$\mathbf{M_{v}}$[$\mathbf{p_{b}}$,$\mathbf{t}$] = $\times$ }

(2) $\mathbf{P_{l}}$ = { $\mathbf{p}$ — $\forall$ $\mathbf{t}$,
$\mathbf{M_{v}}$[$\mathbf{p_{b}}$,$\mathbf{t}$] = $\times$ $\Rightarrow{}$
$\mathbf{M_{v}}$[$\mathbf{p}$,$\mathbf{t}$] $\neq{}$ ✓ }

Note that we can also easily compute the detailed number of originally failing
tests that now pass on a patch; however, prior work has demonstrated that the
detailed test number can be misleading (Lou et al., 2020). Of course, this is
just the first work in this new direction, and we highly encourage other
researchers to investigate other better ways to estimate patch quality.

####  3.2.2. Patch Similarity

After calculating patch quality for executed patches, we iterate through all
remaining patches within $\mathbf{P}$ to compute their similarity information
with the executed high/low-quality patches. For each patch $\mathbf{p}$ that
has not been validated yet, we compare its patch modification matrix
information against that of each of the validated patches. During the
comparison, we compute the number of elements matching and differing among the
two compared patches (i.e., two rows in the patch modification matrix). We
calculate the number of matching elements by performing the set intersection
on the two patch modification matrix rows representing the two patches.
Likewise, we calculate the number of differing elements by performing a
symmetric set difference (i.e., A $\ominus$ B = (A - B) $\cup{}$ (B - A)) on
the two patch modification matrix rows representing the two patches. It is
important to note that we employ the symmetric but not asymmetric set
difference, since this ensures that the similarity between two patches is
symmetric.

Based on the similarity/dissimilarity with high/low-quality patches, we can
compute the following tuple for each unvalidated patch $\mathbf{p}$ for
prioritization, (ef, nf, ep, np). Our basic idea is that ef should get
increased when $\mathbf{p}$ shares elements with high-quality patches, ep
should get increased when $\mathbf{p}$ shares elements with low-quality
patches, nf should get increased when $\mathbf{p}$ has set difference with
high-quality patches, and np should get increased when $\mathbf{p}$ has set
difference with low-quality patches. Since the detailed number of the
matching/different modified elements between two patches can tell the detailed
similarity/dissimilarity information, the increment should also consider such
detailed information. In this way, the formulae for computing the tuple for
each unvalidated patch $\mathbf{p}$ are shown in the following equations:

(3) ef[$\mathbf{p}$] = $\sum{}_{\mathbf{p}^{\prime}}$ — { $\mathbf{e}$ —
$\mathbf{e}$ $\in$ $\mathbf{M_{m}}$[$\mathbf{p}$] $\cap$
$\mathbf{M_{m}}$[$\mathbf{p}$’] $\wedge$ $\mathbf{p}$’ $\in$ $\mathbf{P_{h}}$
}—

(4) ep[$\mathbf{p}$] = $\sum{}_{\mathbf{p}^{\prime}}$ — { $\mathbf{e}$ —
$\mathbf{e}$ $\in$ $\mathbf{M_{m}}$[$\mathbf{p}$] $\cap$
$\mathbf{M_{m}}$[$\mathbf{p}$’] $\wedge$ $\mathbf{p}$’ $\in$ $\mathbf{P_{l}}$
}—

(5) nf[$\mathbf{p}$] = $\sum{}_{\mathbf{p}^{\prime}}$ — { $\mathbf{e}$ —
$\mathbf{e}$ $\in$ $\mathbf{M_{m}}$[$\mathbf{p}$] $\ominus$
$\mathbf{M_{m}}$[$\mathbf{p}$’] $\wedge$ $\mathbf{p}$’ $\in$ $\mathbf{P_{h}}$
}—

(6) np[$\mathbf{p}$] = $\sum{}_{\mathbf{p}^{\prime}}$ —{ $\mathbf{e}$ —
$\mathbf{e}$ $\in$ $\mathbf{M_{m}}$[$\mathbf{p}$] $\ominus$
$\mathbf{M_{m}}$[$\mathbf{p}$’] $\wedge$ $\mathbf{p}$’ $\in$ $\mathbf{P_{l}}$
}—

Note that $\mathbf{M_{m}}$[$\mathbf{p}$] denotes the set of program elements
modified by patch $\mathbf{p}$. For example, if a validated patch
$\mathbf{p}$’ is high-quality and shares elements with the current
$\mathbf{p}$, the ef of $\mathbf{p}$ is then increased for
—$\mathbf{M_{m}}$[$\mathbf{p}$] $\cap$ $\mathbf{M_{m}}$[$\mathbf{p}$’]—. In
this way, all the other tuple elements can be defined in a similar way.

####  3.2.3. Patch Prioritization

Based on the similarity tuple we computed from the previous step, we can
compute the priority for each unvalidated patch based on the following
intuition: (1) a patch more similar/dissimilar with high-quality patches
should be promoted/degraded, (2) a patch similar/dissimilar with low-quality
patches should be degraded/promoted. Actually, such intuition is quite similar
to traditional spectrum-based fault localization (Jones et al., 2002) where
the intuition is (1) a program element executed/unexecuted by failed tests
should be more/less suspicious, (2) a program elements executed/unexecuted by
passed tests should be less/more suspicious. In this way, all the traditional
fault localization formulae can be directly leveraged here to compute the
patch priority. We use the Ochiai formula, shown in Equation (7), as our
default formula as it is often the default formula for spectrum-based fault
localization techniques (Ghanbari et al., 2019; Wen et al., 2018; Jiang et
al., 2018). In this way, patches will be promoted/demoted if they are
similar/dissimilar with other high-quality patches, consistent with our
intuition.

(7)
$\text{Ochiai}=\dfrac{\textit{e${}_{f}$}{}}{\sqrt{(\textit{e${}_{f}$}{}+\textit{n${}_{f}$}{})*(\textit{e${}_{f}$}{}+\textit{e${}_{p}$}{})}}$

####  3.2.4. Overall Algorithm

Given the above definitions, we can now present the overall SeAPR algorithm.
Shown in Algorithm 1, SeAPR first initializes the similarity tuples for all
patches as 1s (Line 1). Then, SeAPR iterates through all patches and validates
them in order (Lines 3-16). During each iteration, SeAPR first gets the patch
$\mathbf{p}$ with the highest priority and removes that from the patch list
$\mathbf{P}$. Note that for the patches with tied SeAPR priority scores (e.g.,
all patches are tied before the first patch execution), SeAPR prioritizes them
with their original ordering in the corresponding APR tools. Then, SeAPR
executes the patch against the original test suite, and stores the patch
execution results into the patch validation matrix $\mathbf{M_{v}}$ (Line 5).
If $\mathbf{p}$ is a plausible patch, it will be stored in the resulting set
$\mathbf{P_{\checkmark{}{}}}$ for manual inspection (Lines 6-7). To help with
on-the-fly patch prioritization, SeAPR computes the patch quality information
for the current patch following Section 3.2 (Line 8). Next, SeAPR goes through
all the remaining patches to update their similarity tuples following Section
3.2.2 (Lines 9-15). Note that all remaining patches will be compared with the
newly executed patch to incrementally update their corresponding similarity
tuples. Lastly, the priority scores for all remaining patches will be updated
based on the updated similarity tuples following Section 3.2.3 (Line 16). In
this way, the algorithm will proceed until all patches have been validated or
the developers find a high-quality patch.

Note that the time complexity of the SeAPR algorithm is $O(n^{2})$ at first
glance ($n$ denotes the number of patches), since all the remaining patches
need to be updated after each patch execution. Meanwhile, during our
implementation, we realize that the similarity scores do not need to be
updated for each remaining patch; instead, we can cluster all remaining
patches based on the set of program elements they modify, since all patches
with the same set of modified elements will have the same priority. In this
way, the time complexity can be reduced to $O(nm)$, where $m$ denotes the
number of patch clusters with the same modified element sets. Given $m<<n$ in
practice, our actual SeAPR implementation incurs negligible overhead.

Input: The original buggy program $\mathbf{p_{b}}$, test suite $\mathbf{T}$,
the list of candidate patches $\mathbf{P}$, the similarity tuples ef, ep, nf,
np

Output: Plausible patches: $\mathbf{P_{\checkmark{}{}}}$

1 begin

2 Initialize ef, ep, nf, np

3 while  _$\mathbf{P}$ is not empty_ do

$\mathbf{p}$ $\leftarrow$ $\mathtt{pop}$($\mathbf{P}$) ;

// pop the remaining patch with the highest priority

$\mathbf{M_{v}}$ $\leftarrow$ $\mathtt{execute}$($\mathbf{p}$, $\mathbf{T}$);

// get the execution results

4 if  _$\mathbf{p}$ is $\mathtt{PLAUSIBLE}$_ then

$\mathbf{P_{\checkmark{}{}}}$$\leftarrow$ $\mathbf{p}$;

// put $\mathbf{p}$ into the resulting set for manual inspection if it is
plausible

5

6

$\mathbf{r}$ $\leftarrow$ $\mathtt{computePatchQuality}$($\mathbf{p}$,
$\mathbf{p_{b}}$, $\mathbf{M_{v}}$);

// compute the patch quality

7

// Incrementally update the similarity tuples for the remaining patches based
the newly executed patch

8

9 for  _$\mathbf{p}$ ’ $\in$ $\mathbf{P}$_ do

10 if  _$\mathbf{r}$ = $\mathtt{HIGH-QUALITY}$_ then

11 ef[$\mathbf{p}$’] += —$\mathbf{M_{m}}$[$\mathbf{p}$] $\cap$
$\mathbf{M_{m}}$[$\mathbf{p}$’]—

12 nf[$\mathbf{p}$’] += —$\mathbf{M_{m}}$[$\mathbf{p}$] $\ominus$
$\mathbf{M_{m}}$[$\mathbf{p}$’]—

13 if  _$\mathbf{r}$ = $\mathtt{LOW-QUALITY}$_ then

14 ep[$\mathbf{p}$’] += —$\mathbf{M_{m}}$[$\mathbf{p}$] $\cap$
$\mathbf{M_{m}}$[$\mathbf{p}$’]—

15 np[$\mathbf{p}$’] += —$\mathbf{M_{m}}$[$\mathbf{p}$] $\ominus$
$\mathbf{M_{m}}$[$\mathbf{p}$’]—

16

$\mathbf{P}$$\leftarrow$ $\mathtt{computePriorityScore}$($\mathbf{P}$, ef, nf,
ep, np);

// update priority scores for remaining patches

17

18

19

Algorithm 1 SeAPR Algorithm

####  3.2.5. Example

Let us now use the partial patch validation matrix111Note that we use partial
since most APR tools will collect partial matrices, but our idea generalizes
to full matrices (as studied in Section 5.4). shown in Table 1 and its
corresponding patch modification matrix (shown in Table 2) as the example to
illustrate our SeAPR technique. For this example, if we follow the original
patch execution ordering (top-down), we need to execute four patches before
finding the final plausible patch. Now we discuss how our SeAPR can help speed
up this process.

Shown in Tables 3 and 4, Column “Quality” describes the patches’ actual
quality (available after the corresponding patch validation); Column “Match”
describes the number of matching elements against the last executed patch for
each patch; Column “Differ” describes the number of differing elements against
the last executed patch for each patch; Columns “ef”, “nf”, “ep”, and “np”
represent the accumulated similarity tuples per patch;222Note, each tuple is
initialized with ef=1, nf=1, ep=1, and np=1 for numerical stability. lastly,
Column “Score” represents the Ochiai calculated priority score as defined in
Equation (7).

In the first iteration (shown in Table 3), SeAPR will compute the quality of
the executed patch, $\mathbf{p}$1 (marked with gray). We can immediately
determine that the patch is low quality simply because it cannot make any
originally failing tests pass. Note that we also show the quality for all
other unexecuted patches to illustrate the quality computation. Then, given
$\mathbf{p}$1 has been executed, we can update the similarity tuple for each
remaining patch. For example, for $\mathbf{p}$2, the set intersection and
symmetrical set difference with $\mathbf{p}$1 is {$e_{1}$, $e_{2}$, $e_{3}$}
$\cap$ {$e_{1}$, $e_{2}$, $e_{3}$, $e_{4}$} = {$e_{1}$, $e_{2}$, $e_{3}$} and
{$e_{1}$, $e_{2}$, $e_{3}$} $\ominus$ {$e_{1}$, $e_{2}$, $e_{3}$, $e_{4}$} =
{$e_{4}$}, respectively. Therefore, since $\mathbf{p}$1 is a low-quality
patch, ep increments by 3 and np increments by 1, resulting in the tuple
(ef=1+0, nf=1+0, ep=1+3, np=1+1). Similarly, we can compute the similarity
tuples for all the other remaining patches as shown in Table 3. Then, via
applying the default Ochiai formula on the computed tuples, we can compute the
priority scores for all the three remaining patches as shown in Column “Score”
in Table 3. In this way, the patch with the highest priority, $\mathbf{p}$4,
is selected for the next patch execution.

Then, in the second iteration, $\mathbf{p}$4 gets executed (marked in gray) as
shown in Table 4. Note that $\mathbf{p}$4 is a plausible patch that can pass
all system tests. Therefore, the developers can immediately start the patch
inspection to check if $\mathbf{p}$4 is the correct patch. Of course, the
patch execution can still continue if $\mathbf{p}$4 is not the correct patch.
Continuing the algorithm, the remaining patches will be further compared with
the newly executed $\mathbf{p}$4 to update their similarity tuples. For
example, for $\mathbf{p}$2, the set intersection and symmetrical set
difference with $\mathbf{p}$4 is {$e_{1}$, $e_{2}$, $e_{3}$, $e_{4}$} $\cap$
{$e_{1}$} = {$e_{1}$} and {$e_{1}$, $e_{2}$, $e_{3}$, $e_{4}$} $\ominus$
{$e_{1}$} = {$e_{2}$, $e_{3}$, $e_{4}$}, respectively. Since $\mathbf{p}$4 is
a high-quality patch, $\mathbf{p}$2’s tuple is updated by incrementing ef by 1
and nf by 3, resulting in the tuple (ef=1+1, nf=1+3, ep=4+0, np=3+0). In this
way, we can compute the scores for the remaining patches to further continue
with patch validation.

ID | Quality | Match | Differ | ef | nf | ep | np | Score
---|---|---|---|---|---|---|---|---
$\mathbf{p}$1 | Low | - | - | - | - | - | - | -
$\mathbf{p}$2 | Low | {$e_{1}$, $e_{2}$, $e_{3}$} | {$e_{4}$} | 1+0 | 1+0 | 1+3 | 1+1 | 0.32
$\mathbf{p}$3 | High | {$e_{2}$, $e_{3}$} | {$e_{1}$} | 1+0 | 1+0 | 1+2 | 1+1 | 0.35
$\mathbf{p}$4 | Plausible | {$e_{1}$} | {$e_{2}$, $e_{3}$} | 1+0 | 1+0 | 1+1 | 1+2 | 0.50

Table 3. Detailed SeAPR step-by-step when processing $\mathbf{p}$1

ID | Quality | Match | Differ | ef | nf | ep | np | Score
---|---|---|---|---|---|---|---|---
$\mathbf{p}$1 | Low | - | - | - | - | - | - | -
$\mathbf{p}$4 | Plausible | - | - | - | - | - | - | -
$\mathbf{p}$2 | Low | {$e_{1}$} | {$e_{2}$, $e_{3}$, $e_{4}$} | 1+1 | 1+3 | 4+0 | 2+0 | 0.33
$\mathbf{p}$3 | High | {$e_{2}$, $e_{3}$} | {$e_{1}$, $e_{4}$} | 1+2 | 1+2 | 3+0 | 2+0 | 0.50

Table 4. Detailed SeAPR step-by-step when processing $\mathbf{p}$4

For this example, we observe that the original patch execution ordering
requires 4 patch executions to find the first plausible patch, while our SeAPR
reduces the number of required patch executions to only 2, i.e.,
$\frac{4-2}{4}=50\%$ patch reduction. In this way, the developers can start
manual patch inspection as soon as after 2 patch validations, substantially
speeding up the repair process.

###  3.3. SeAPR Variants

Potential SeAPR configurations are described in Table 6 (default configuration
settings bolded):

####  3.3.1. Patch-Prioritization Formulae.

Besides Ochiai, other SBFL formulae can also be applied here. In particular we
study all popular SBFL formulae from prior work (Zhang et al., 2017) in
Section 5.2.

####  3.3.2. Validation-Matrix Types.

Besides the partial patch-validation matrices widely used in practice, we also
consider the impact of full validation matrices on our approach, discussed in
Section 5.4.

####  3.3.3. Modification-Matrix Granularities.

Patch modification matrices are applicable to various granularities with
varying patch similarity results. We examine the impact of such granularities
on SeAPR in Section 5.3.

####  3.3.4. Additional Patch Similarity Information

By default, SeAPR only uses the set of modified program elements to calculate
patch similarity for prioritizing patches on-the-fly. Another SeAPR extension
is to compute the similarity score with additional information in addition to
just the modified elements. Therefore, we further study another SeAPR variant,
SeAPR++, which additionally considers that patches sharing the same fixing
patterns may also share similar program behaviors. In this way, we can promote
patches applying the same fixing patterns with known high-quality patches to
further boost SeAPR.

######  Definition 3.3.

Patch repair pattern matrix: Matrix $\mathbf{M_{p}}$ presents the applied
repair patterns applied to each patch. Each cell describes if patch
$\mathbf{p}$ $\in$ $\mathbf{P}$ applies repair pattern $\mathbf{r}$ $\in$
$\mathbf{R}$ (i.e., all predefined repair patterns). Acceptable values for
each cell are as follows: (1) ✓ if $\mathbf{p}$ applies pattern $\mathbf{r}$
and (2) - if $\mathbf{p}$ does not apply pattern $\mathbf{r}$.

|  |  |  | SeAPR Features
---|---|---|---|---
Patch ID | $r_{1}$ | $r_{2}$ | $r_{3}$ | Modified Element(s) | Pattern(s)
$\mathbf{p}$1 | ✓ | - | - | {$e_{1}$, $e_{2}$, $e_{3}$} | {$r_{1}$}
$\mathbf{p}$2 | - | ✓ | - | {$e_{1}$, $e_{2}$, $e_{3}$, $e_{4}$} | {$r_{2}$}
$\mathbf{p}$3 | - | - | ✓ | {$e_{2}$, $e_{3}$} | {$r_{3}$}
$\mathbf{p}$4 | - | ✓ | - | {$e_{1}$} | {$r_{2}$}

Table 5. Example of patch repair pattern matrix

More specifically, SeAPR++ only slightly differs from the default SeAPR when
computing patch similarity, e.g., SeAPR++ considers both (1) the set of
modified elements and (2) the applied repair patterns. Based on the above
patch-pattern matrix definition, we can recompute the similarity tuples for
further improving SeAPR, e.g., ef[$\mathbf{p}$] in Equation (3) becomes:

(8) $\begin{split}\text{{e${}_{f}$}{}[$\mathbf{p}${}]}=&\text{$\sum{}_{\mathbf{p}^{\prime}}${ | \\{ $\mathbf{e}${} | $\mathbf{e}${} $\in$ $\mathbf{M_{m}}${}[$\mathbf{p}${}] $\cap$ $\mathbf{M_{m}}${}[$\mathbf{p}${}'] $\wedge$ $\mathbf{p}${}' $\in$ $\mathbf{P_{h}}${} \\}|}~{}+}\\\ &\text{$\sum{}_{\mathbf{p}^{\prime}}${ | \\{ $\mathbf{e}${} | $\mathbf{e}${} $\in$ $\mathbf{M_{p}}${}[$\mathbf{p}${}] $\cap$ $\mathbf{M_{p}}${}[$\mathbf{p}${}'] $\wedge$ $\mathbf{p}${}' $\in$ $\mathbf{P_{h}}${} \\}|}}\end{split}$

Parameter |  Variant Settings
---|---
Prioritization Formulae |  Tarantula, Ochiai, Ochiai2, Op2, SBI, Jaccard, Kulczynski, Dstar2
Validation Matrices |  Full Matrix, Partial Matrix
Modification Granularities |  Package, Class, Method, Stmt
Similarity Computation |  Modified Elements, Modified Elements+Patch Patterns

Table 6. Possible configurations for SeAPR

###  3.4. Further Extension Considering APR Results from Other Tools

In practice one repair tool is often insufficient to successfully find a
correct patch. Thus developers often run multiple repair tools, ideally using
the results of previously executed tools to optimize future executed tools.
Similarly, the execution results of other tools on the same subject can be
used to more guide SeAPR towards high-quality patches sooner. In particular,
we use the repair information from all but one repair tool to initialize the
priority score of all patches. For example, when applying SeAPR to TBar +
Chart-1, all other tools with Chart-1 execution results will follow the same
process outlined in Section 3.2.4 to initialize the priority scores of all
TBar + Chart-1 patches. With the priority scores initialized, SeAPR starts
with the most prioritized patch and follows the algorithm outlined in
Algorithm 1, updating the already initialized priority scores of each patch.

##  4\. Experimental Design

###  4.1. Research Questions

In this paper, we aim to study the following research questions to thoroughly
evaluate the performance of our SeAPR:

  * •

RQ1: How does the default SeAPR perform on state-of-the-art APR systems?

  * •

RQ2: How do different formulae affect the effectiveness of SeAPR?

  * •

RQ3: How do different patch-modification-matrix granularities affect the
effectiveness of SeAPR?

  * •

RQ4: How does patch validation matrices impact SeAPR?

  * •

RQ5: How does SeAPR perform when leveraging additional patch similarity
information?

  * •

RQ6: How does SeAPR perform when further leveraging historical repair
information from other APR systems?

Note that we first study our default SeAPR configuration with the Ochiai
formula, method granularity, partial patch validation matrices, modified
elements similarity computation in RQ1. Then, in RQs 2-5, we investigate the
impact of different formulae, granularities, types of patch validation
matrices, as well as the usage of additional patch execution information.
Lastly, in RQ6, we investigate the effectiveness of SeAPR when further
leveraging patch validation information from other APR tools.

###  4.2. Evaluation Dataset

We choose to evaluate the proposed technique against the Defects4J dataset
(V1.2.0), since Defects4J (V1.2.0) is the most widely used APR dataset to
date, and will allow our technique to be easily compared to and replicated in
the future. The details for our adopted dataset are shown in Table 7. In the
table, Column “# Bugs” presents the number of buggy versions studied for each
subject. Column “# Tests” and Column “LOC” presents the number of JUnit tests
and lines of code available within the head (i.e., most recent) version of
each subject, respectively.

Subject | Name | # Bugs | # Tests | LOC
---|---|---|---|---
Chart | JFreeChart | 26 | 2,205 | 96K
Lang | Apache Lang | 65 | 2,245 | 22K
Math | Apache Math | 106 | 3,602 | 85K
Time | Joda-Time | 27 | 4,130 | 28K
Mockito | Mockito framework | 38 | 1,366 | 23K
Closure | Google Closure compiler | 133 | 7,927 | 90K
Total | 395 | 21,475 | 344K

Table 7. Studied bugs from Defects4J v1.2.0

###  4.3. Tools

Following prior work (Liu et al., 2020), we consider all 16 program repair
tools publicly available and applicable to Defects4J in this study, show in
Table 8. Of these tool candidates, we exclude Acs, DynaMoth, and Nopol due to
low patch generation (i.e., $<$500 total patches across all studied Defects4J
projects in total). Evaluating our technique on such tools with small number
of patches will induce noise into our results; in addition, such APR tools do
not need patch prioritization anyhow. We further exclude Simfix since the tool
stops execution after finding the first plausible patch. The validation
results of such tools are undegradable, since the last patch is always the
desirable plausible patch. Results from such tools can only improve, biasing
our findings. With the exclusion of these tools, this leaves us with 12 repair
tools used in this paper.

Tool Category |  Tool(s)
---|---
Constraint-based |  Acs (Xiong et al., 2017), Cardumen (Martinez and Monperrus, 2018), DynaMoth (Durieux and Monperrus, 2016), Nopol (Xuan et al., 2017)
Heuristic-based |  Arja (Yuan and Banzhaf, 2018), GenProg-A (Yuan and Banzhaf, 2018), JGenProg (Martinez and Monperrus, 2016), JKali (Martinez and Monperrus, 2016), JMutRepair (Martinez and Monperrus, 2016), Kali-A (Yuan and Banzhaf, 2018), RSRepair-A (Yuan and Banzhaf, 2018), Simfix (Jiang et al., 2018)
Template-based |  Avatar (Liu et al., 2019b), FixMiner (Koyuncu et al., 2020), KPar (Liu et al., 2019a), TBar (Liu et al., 2019c)

Table 8. Repair tools under consideration

###  4.4. Evaluation Metrics

We have adopted the following two evaluation metrics: the reduction on the
number of patch executions before finding the first (1) plausible patch and
(2) correct patch. We study the number of patches to the first plausible patch
since in practice developers will begin patch inspection after the first
plausible patch is found; in this way, faster plausible patch detection can
enable developers to start patch inspection earlier (and potentially speed up
the APR process). Similarly, we study the number of patches to the first
correct patch since developers will stop the patch validation process once the
correct patch is found; in this way, faster correct patch detection can save
overall APR time. Also note that we leverage the reduction on the number of
patch executions as recommended by prior work (Liu et al., 2020) since time
cost information tends to introduce bias: it is dependent on many factors
(e.g., specific implementations and test execution engines) unrelated to APR
approaches and is often unstable.

To this end, Formula 9 represents our primary evaluation metric. Pbaseline
represents the position of the first desirable (i.e., plausible or correct)
patch, pre-priortization. Pnew represents position of the first desirable
patch, post-prioritization. Note that when multiple desirable patches are
produced, the initial desireable patch and the final desireable patch are not
necessarily the same patch.

(9) $Reduction=\dfrac{P_{baseline}-P_{new}}{P_{baseline}}$

###  4.5. Experimental Procedure

For each studied APR tool, we evaluate the effectiveness of SeAPR on all
patches that can be generated and validated by the tool within its original
time limit. We first analyzed the original execution of each tool on a
subject-by-subject basis to obtain (1) the original patch execution ordering
per repair tool and (2) the position of the earliest plausible/correct patch.

After information collection, we then repeat the patch validation process for
each tool again with our SeAPR on-the-fly patch prioritization. Note that due
to the large effort required to modify all used tools, we choose to simulate
the validation process of each tool instead of modifying each tool directly.
For each given subject, SeAPR initially executes the first patch produced by
the tool. After the first patch execution, SeAPR iterates through all patches
not yet validated, following Algorithm 1, to record the new position for the
first plausible/correct patch.

All our experiments were conducted within the following environment: 36 3.0GHz
Intel Xeon Platinum Processors, 60GBs of memory, and Ubuntu 18.04.4 LTS
operating system.

##  5\. Result Analysis

###  5.1. RQ1: Overall SeAPR Effectiveness

Quantitative Analysis. In this section, we first investigate the overall
effectiveness of our default SeAPR on all 12 studied repair tools against all
the six studied subjects from the Defects4J benchmark. Table 9 shows the patch
reduction in terms of the first plausible patches with the default
configuration settings. In this table, each row and column represent different
Defects4J projects and repair tools, respectively. Note that each cell
presents the overall patch reduction for each tool on the corresponding
project with symbol “—” indicating that the repair tool cannot generate any
plausible patches on the corresponding project. We also present the overall
patch reductions on all projects, shown in the last row. From this table, we
have the following observations. First, SeAPR can improve the overall
effectiveness of patch validations for almost all repair tools. For example,
SeAPR can reduce patch validation by 78.81% on GenProg-A and 54.80% on Avatar.
Meanwhile, SeAPR degrades the performance of Cardumen by 7.32%. The possible
reason is that Cardumen only generate plausible patches for very few buggy
versions, and thus the overall results can have large variance. Second, for
most repair tools, SeAPR can also improve patch validation results for the
majority of Defects4J projects. For example, SeAPR can achieve positive
reductions for Avatar, FixMiner, GenProg-A, JKali, JMutRepair and Kali-A on
all the projects with plausible patches. For other repair tools, SeAPR
degrades the performance of them on at most one or two projects. This finding
shows the applicability of SeAPR on different repair tools and different
projects.

Similarly, Table 10 further shows the patch reduction ratios in terms of the
first correct patch. Note that there exists no information on the number of
correct patches reported in the original or subsequent papers for GenProg-A,
RSRepair-A, and Kali-A (Yuan and Banzhaf, 2018). For JKali and JGenProg, we
cannot generate any correct patches as reported by the tool’s original paper
(Martinez and Monperrus, 2016), likely due to the tool’s nondeterminism and
different execution environments. Therefore, we exclude these five repairs
tools from Table 10. From the table, we can find that SeAPR can also
substantially reduce patch validation (until the first correct patch) for most
repair tools. For example, SeAPR can improve the overall performance of Arja,
Avatar, JMutRepair, KPar and TBar by 72.96%, 80.15%, 53.57%, 64.06% and 48.80%
respectively. Another interesting finding is that SeAPR does not degrade the
performance of any of the studied tools, although it cannot reduce patch
executions for some repair tools (i.e., 0% reduction). The possible reason may
be that the original ranking of correct patches by these tools is good enough,
leaving limited room of improvement for our SeAPR.

Note that since patch reductions in terms of correct patches do not apply to
all studied subjects and are mainly consistent with that in terms of plausible
patches, we use patch reductions in terms of plausible patches for our
following RQs.

| Arja | Avatar | Cardumen | FixMiner | GenProg-A | JGenProg | JKali | JMutRepair | Kali-A | KPar | RSRepair-A | TBar
---|---|---|---|---|---|---|---|---|---|---|---|---
Chart | 80.10% | 79.36% | -15.15% | 48.49% | 44.75% | 3.33% | 0.00% | 11.36% | 14.29% | 21.27% | 32.04% | 48.61%
Closure | — | 60.62% | — | — | — | — | — | — | — | 46.89% | — | 9.26%
Lang | -836.92% | 48.29% | 32.00% | 53.80% | 57.45% | -75.00% | 48.15% | 24.10% | — | -3.47% | -13.00% | -61.49%
Math | 19.62% | — | -37.50% | — | 81.25% | 23.33% | 38.10% | 17.71% | 3.99% | 14.69% | 28.82% | 45.51%
Mockito | — | 25.00% | — | — | — | — | — | — | — | 37.91% | — | 5.13%
Time | — | 40.67% | — | 14.54% | — | — | — | — | — | 17.26% | — | -174.47%
Overall | 40.05% | 54.80% | -7.32% | 43.55% | 78.81% | 7.81% | 37.18% | 20.26% | 6.36% | 17.56% | 21.84% | 10.93%

Table 9. SeAPR default configuration results for plausible patches

| Arja | Avatar | Cardumen | FixMiner | JMutRepair | KPar | TBar
---|---|---|---|---|---|---|---
Chart | — | — | 0.00% | 0.00% | — | 84.97% | 0.00%
Closure | — | 0.00% | — | — | — | 0.00% | 0.00%
Lang | — | 93.86% | — | 0.00% | — | — | 0.00%
Math | 72.96% | — | — | — | 53.57% | 22.09% | 65.16%
Mockito | — | 0.00% | — | — | — | — | 33.33%
Time | — | — | — | — | — | — | —
Overall | 72.96% | 80.15% | 0.00% | 0.00% | 53.57% | 64.06% | 48.80%

Table 10. SeAPR default configuration results for correct patches

Qualitative Analysis. Next, we perform detailed examples to investigate the
performance of SeAPR.

⬇

1// org.jfree.chart.plot.CategoryPlot.java

2@@ -911,7 +911,6 @@

3 * @param axis the axis.

4 */

5 public void setRangeAxis(int index, ValueAxis axis) {

6- setRangeAxis(index, axis, true);

7 }

8

9 /***/

Figure 1. Arja Chart-19 prioritizer patch

⬇

1// org.jfree.chart.uti.AbstractObjectList.java

2@@ -161,7 +161,10 @@

3 return (index);

4 }

5 }

6- return -1;

7+ if (object == null) {

8+ throw new IllegalArgumentException("Null␣’object’␣argument.");

9+ }

10+ return -1;

11 }

12

13 /***/

Figure 2. Arja Chart-19 plausible patch

####  5.1.1. Example 1

Figure 1 shows one of the low-quality patches produced by Arja on Chart-19
while Figure 2 shows one of few generated plausible patches. Note that these
two patches modify different files. In this example, we observe how low-
quality patches can help prioritizing plausible patches. According to our
technique, other patches sharing similar modified elements with these low-
quality patches are deprioritized. Thus as any low-quality patch modifying one
particular set of methods is validated, all other similar patches are
deprioritized. This essentially results in (1) the clustering of patches based
on the set of modified methods and (2) prioritizing / deprioritizing these
clusters. Upon validation of consecutive low-quality patches, this phenomenon
culminates to a breadth-first exploration of the patch clusters, mitigating
the risk of some high-quality patches getting starved. This process repeats
until Arja finds plausible patch from Figure 2. For Arja and Chart-19, we
observe Arja validates the plausible patch 33rd instead of 626th, achieving a
patch reduction of 94.7%.

⬇

1@@ -1621,9 +1621,9 @@ public static double distance(double[] p1, double[] p2)
{

2* @return the L<sub>2</sub> distance between the two points

3*/

4public static double distance(int[] p1, int[] p2) {

5int sum = 0;

6for (int i = 0; i < p1.length; i++) {

7 final int dp = p1[i] - p2[i];

8- sum += dp * dp;

9}

10return Math.sqrt(sum);

Figure 3. TBar Math-79 prioritizer patch

⬇

1@@ -1621,9 +1621,9 @@ public static double distance(double[] p1, double[] p2)
{

2* @return the L<sub>2</sub> distance between the two points

3*/

4public static double distance(int[] p1, int[] p2) {

5- int sum = 0;

6+ double sum = 0;

7 for (int i = 0; i < p1.length; i++) {

8- final int dp = p1[i] - p2[i];

9+ final double dp = p1[i] - p2[i];

10 sum += dp * dp;

11}

12return Math.sqrt(sum);

Figure 4. TBar Math-79 plausible patch

####  5.1.2. Example 2

Figure 3 presents a non-correct high-quality patch produced by TBar which
immediately helps prioritize a plausible patch, shown in Figure 4. From these
figures, it is evident that both patches modify method distance(int[], int[]).
Upon processing the non-correct high-quality patch, the plausible patch in
Figure 4 is immediately prioritized earlier by SeAPR since they share similar
modified program elements. In TBar, the plausible patch shown in Figure 4 is
originally validated at the 125th place without our SeAPR technique, and now
validated at the 33rd position, achieving a reduction of 73.6%.

⬇

1// org.jfree.chart.JFreeChart.java

2@@ -1484,7 +1484,6 @@

3 */

4 public void fireChartChanged() {

5 ChartChangeEvent event = new ChartChangeEvent(this);

6- notifyListeners(event);

7 }

8

9 /***/

Figure 5. Arja Chart-12 prioritizer patch

⬇ 1// org.jfree.data.general.AbstractDataset.java 2@@ -158,7 +158,7 @@ 3 */ 4
public boolean hasListener(EventListener listener) { 5 List list =
Arrays.asList(this.listenerList.getListenerList()); 6- return
list.contains(listener); 7+ return true; 8 } 9 10 /***/
---

⬇ 1// org.jfree.chart.title.LegendTitle.java 2@@ -539,7 +539,9 @@ 3 4 */ 5
public boolean equals(Object obj) { 6 if (obj == this) { 7- return true; 8+ if
(!super.equals(obj)) { 9+ return false; 10+ } 11 } 12 if (!(obj instanceof
LegendTitle)) { 13 return false;
---

⬇ 1// org.jfree.chart.JFreeChart.java 2@@ -641,7 +641,10 @@ 3 4 int seen = 0;
5 Iterator iterator = this.subtitles.iterator(); 6 while (iterator.hasNext())
{ 7- Title subtitle = (Title) iterator.next(); 8+ if (this.title != null) { 9+
this.title.addChangeListener(this); 10+ } 11+ Title subtitle = (Title)
iterator.next(); 12 if (subtitle instanceof LegendTitle) { 13 if (seen ==
index) { 14 return (LegendTitle) subtitle;
---

Figure 6. Arja Chart-12 plausible patch

####  5.1.3. Example 3

We now show the effectiveness of SeAPR on multi-edit APR techniques (e.g.
Arja). Figure 5 presents one of the 60+ low-quality patches generated by Arja
on subject Chart-12 with each patch potentially modifying one or more code
elements. Figure 6 shows the first plausible patch. From the two figures, it
is evident that the plausible patch and this particular low-quality patch do
not modify the same code elements. In fact, despite modifications across
multiple files, SeAPR’s performance does not change. That is, the validation
of these numerous low-quality patches deprioritizes all other patches in the
same cluster. As SeAPR iterates through these clusters, a plausible patch is
quickly found shown in Figure 6. This phenomenon leads SeAPR to prioritize the
first plausible patch of Chart-12 from 616th to 63rd, an improvement of 89.8%.

SeAPR can substantially reduce patch executions before finding the first
plausible/correct patches for almost all studied repair tools, with a maximum
improvement of 78.81%/72.96%.

###  5.2. RQ2: Impact of Different Formulae

| Tarantula | Ochiai | Ochiai2 | Op2 | SBI | Jaccard | Kulczynski | Dstar2
---|---|---|---|---|---|---|---|---
Arja | 46.23% | 40.05% | 38.66% | 33.57% | 53.88% | 39.91% | 39.91% | 40.60%
Avatar | 52.16% | 54.80% | 53.62% | 51.74% | 52.16% | 55.22% | 55.22% | 53.55%
Cardumen | -7.32% | -7.32% | -7.32% | -7.32% | -13.41% | -7.32% | -7.32% | -7.32%
FixMiner | 43.45% | 43.55% | 43.24% | 46.46% | 45.49% | 43.45% | 43.45% | 43.65%
GenProg-A | 60.09% | 78.81% | 80.45% | 78.21% | 73.35% | 78.81% | 78.81% | 78.91%
JGenProg | 7.81% | 7.81% | 7.81% | 7.81% | 7.81% | 7.81% | 7.81% | 7.81%
JKali | 37.18% | 37.18% | 37.18% | 37.20% | 37.20% | 37.18% | 37.18% | 37.18%
JMutRepair | 20.26% | 20.26% | 20.26% | 20.26% | 20.26% | 20.26% | 20.26% | 20.26%
Kali-A | 6.14% | 6.36% | 6.14% | 6.36% | 6.36% | 6.36% | 6.36% | 6.36%
KPar | 17.61% | 17.56% | 17.80% | 14.20% | 16.57% | 17.56% | 17.56% | 17.56%
RSRepair-A | 23.50% | 21.84% | 24.06% | 21.32% | 23.26% | 23.21% | 23.21% | 21.84%
TBar | 9.92% | 10.93% | 9.89% | 6.52% | 8.80% | 10.01% | 10.01% | 11.16%
Overall | 33.55% | 35.54% | 35.54% | 31.30% | 36.63% | 35.54% | 35.54% | 35.61%

Table 11. Impact of formula on patch reduction

In the Section 5.1, we studied SeAPR with the default Ochiai formula. In fact,
SeAPR is a general approach and can leverage any other existing SBFL formula.
Therefore, in this section, we further investigate the impact of different
SBFL formulae on the effectiveness of SeAPR. Table 11 shows the experimental
results of 8 widely studied SBFL formulae (Zhang et al., 2017) on the 12
repair tools in terms of patch reduction. From the result, we have the
following findings. First, we observe that SeAPR can reduce the patch
validations by using all studied SBFL formulae on almost all repair tools. For
example, studied SBFL formulae can achieve patch reduction ranging from 6.14%
(Kali-A - Ochiai2 / Tarantula) to 80.45% (GenProg-A - Ochiai2) patch
reductions for reaching the first plausible patch. Likewise, the studied SBFL
formulae only degrades the performance of the Cardumen repair tool slightly
(within 7.32% to 13.41%) with the same reason as discussed in Section 5.1,
i.e., Cardumen can generate plausible patches for only very few buggy
versions, incurring unstable results. Second, for different SBFL formulae, the
overall patch reduction on all the studied 12 tools is rather stable. For
example, the formula with the best overall improvement is SBI (36.63%) and the
formula with the worst performance is Op2 (31.30%), i.e., the difference of
all studied formulae is only 5 percentage points (pp). Third, for each repair
tool, the range of reductions among different formulae also seems small. For
example, for JGenProg, the improvement for all formulae are the same (7.81%).
For Kali-A, the best formula is SBI (6.36%) while the worst is Ochiai /
Tarantula (6.14%). Such results demonstrate the effectiveness and stability of
SeAPR when using different SBFL formulae.

All formulae under consideration achieve stable performance for SeAPR,
boosting the overall validation results by at least 31.3%. Meanwhile, the SBI
formula performs the best for SeAPR, boosting validation by 36.63%.

###  5.3. RQ3: Impact of Granularity

| Package | Class | Method | Statement
---|---|---|---|---
Arja | 15.09% | 26.19% | 40.05% | 36.28%
Avatar | 0.56% | 10.92% | 54.80% | 72.39%
Cardumen | 6.10% | 1.22% | -7.32% | 43.90%
FixMiner | 2.50% | 3.37% | 43.55% | 77.15%
GenProg-A | 35.08% | 43.42% | 78.81% | 19.39%
JGenProg | 31.25% | 17.19% | 7.81% | -1.56%
JKali | 24.36% | 24.36% | 37.18% | 21.79%
JMutRepair | 16.01% | 16.01% | 20.26% | 28.76%
Kali-A | 27.19% | 32.46% | 6.36% | -20.39%
KPar | 10.02% | 8.63% | 17.56% | 48.36%
RSRepair-A | 21.41% | 18.66% | 21.84% | 31.93%
TBar | 4.99% | 3.34% | 10.93% | 26.26%
Overall | 14.45% | 17.84% | 35.54% | 38.86%

Table 12. Impact of granularity on patch reduction

| Time (seconds)
---|---
| Package | Class | Method | Statement
Arja | 1.371 | 1.336 | 1.356 | 1.333
Avatar | 0.522 | 0.508 | 0.524 | 0.507
Cardumen | 0.291 | 0.286 | 0.285 | 0.280
FixMiner | 0.282 | 0.276 | 0.283 | 0.279
GenProg-A | 0.987 | 0.947 | 0.986 | 0.960
JGenProg | 0.303 | 0.296 | 0.298 | 0.294
JKali | 0.299 | 0.290 | 0.287 | 0.284
JMutRepair | 0.299 | 0.287 | 0.288 | 0.282
Kali-A | 0.359 | 0.347 | 0.354 | 0.349
KPar | 0.447 | 0.437 | 0.449 | 0.434
RSRepair-A | 0.629 | 0.604 | 0.620 | 0.604
TBar | 0.519 | 0.501 | 0.521 | 0.502
Average | 0.526 | 0.510 | 0.521 | 0.509

Table 13. Overhead of SeAPR

We now have studied SeAPR with patch-modification matrices at the default
method level. In this section, we investigate the effectiveness of SeAPR on
modification matrices with different granularities, i.e., prioritizing patches
based on the modified code elements at different granularities (i.e., package,
class, method, and statement levels). Table 12 shows the patch reduction of
SeAPR with modification matrices at the four granularities on the 12 repair
tools. From the table, we can observe that SeAPR with all the four
granularities can reduce patch executions for most studied repair tools. More
specifically, for the package and class levels, SeAPR can reduce patch
executions for all repair tools, e.g., the patch executions for GenProg-A can
be reduced by 35.08% and 43.42% at the package and class levels respectively.
Interestingly, SeAPR tends to become less stable for finer granularities,
e.g., SeAPR degrades the performance of one repair tool (Cardumen) at the
method level and degrades the performance of two repair tools (JGenProg and
Kali-A) at the statement level. We also observe that the overall patch
reductions tend to be larger for finer granularities. For example, the overall
reduction ratios for the package, class, method, and statement levels are
14.45%, 17.84%, 35.54%, and 38.86%, respectively. Also, SeAPR performs better
at the method level than at package and class levels for 9/12 repair tools,
while SeAPR at the statement level performs better than all other levels for
7/12 repair tools. The reason is that patch modification at finer
granularities can capture more precise similarity information among different
patches.

We also demonstrate the execution cost of SeAPR, shown in Table 13 for the
four granularities. From the table, we can find that running SeAPR on all four
granularities is extremely fast (e.g., less than 1 second on average for each
buggy version), showing the practical usage of SeAPR within real-world tools /
systems. An interesting finding is that finer granularities do not cost
obviously more time, e.g., the statement-level granularity cost even less time
than other granularities. The possible reasons are (1) our implementations
have been highly optimized (shown in Section 3.2.4), and (2) SeAPR with finer
granularities often prioritize plausible patches earlier and thus terminates
with fewer iterations.

SeAPR can substantially reduce patch executions for most studied repair tools
with modification matrices at all four granularities; SeAPR with modification
matrices at finer granularities tends to achieve higher overall reductions but
also have larger variances. The SeAPR overhead is negligible at all four
granularities.

###  5.4. RQ4: Impact of Full Validation Matrix

| Partial-matrix | Full-matrix
---|---|---
Arja | 40.05% | -16.27%
Avatar | 54.80% | 54.80%
Cardumen | -7.32% | -10.98%
FixMiner | 43.55% | 43.55%
GenProg-A | 78.81% | 50.05%
JGenProg | 7.81% | -3.13%
JKali | 37.18% | 26.92%
JMutRepair | 20.26% | 7.19%
Kali-A | 6.36% | 10.09%
KPar | 17.56% | 17.56%
RSRepair-A | 21.84% | 19.19%
TBar | 10.93% | 10.93%
Overall | 35.54% | 20.37%

Table 14. Impact of validation matrix on patch reduction

We now have studied SeAPR with the default partial patch-validation matrices.
In this section, we further investigate the performance of SeAPR with full
patch-validation matrices. Table 14 shows the comparison between SeAPR with
partial and full patch-validation matrices. From this table, we see that SeAPR
can achieve significant reductions on both full and partial patch-validation
matrices, indicating the general applicability of SeAPR. More specifically,
the overall reductions by SeAPR with the default partial matrices is even
larger than SeAPR with full matrices (35.54% vs 20.37%). For example, SeAPR
substantially degrades the performance of some repair tools when using full
matrices, e.g., the patch reduction on Arja changes from 40.05% (with partial
matrices) into -16.27% (with full matrices).

SeAPR can effectively reduce patch executions on both partial and full patch-
validation matrices. SeAPR tends to perform even better with partial matrices
than with full matrices.

###  5.5. RQ5: Impact of Additional Patch Similarity Information

In this research question we examine the impact of utilizing additional
information for computing patch similarity. We execute the default
configuration of SeAPR and compute patch similarity using both (1) the set of
modified elements and (2) the applied patch templates or patterns. We achieve
this by looking specifically only at tools which apply predefined repair
patterns, i.e., those tools categorized as template-based. Note that we
collect the applied fix patterns as directly reported by each tool. The
studied template-based tools are TBar, KPar, Avatar, and FixMiner with 18, 13,
19, and 23 distinct repair patterns, respectively.

Table 15 shows the result of this configuration evaluated against four patch-
modification matrix granularities. In this table, each repair tool name
followed by symbol ”++” represents the results for our new SeAPR variant with
additional patch pattern information, i.e., SeAPR++. From the table, we can
clearly find that SeAPR++ with additional patch pattern information performs
much better than SeAPR for all studied repair tools on all four different
granularities. On Avatar for instance, SeAPR++ can achieve a reduction of
63.00% at the package granularity while SeAPR only achieves a reduction of
0.56%; similarly for TBar, SeAPR++ can achieve a reduction of 36.65% at the
package granularity while SeAPR only achieves a reduction of 4.99%. Another
interesting finding is that the improvement achieved by SeAPR++ tends to be
larger when using coarse-grained granularities than when using fine-grained
granularities. The reason is that the original SeAPR computes very coarse-
grained patch similarity information when using coarse-grained granularities,
leaving more room for SeAPR++ with additional fixing pattern information to
further boost the patch reduction.

| Package | Class | Method | Statement
---|---|---|---|---
Avatar | 0.56% | 10.92% | 54.80% | 72.39%
Avatar++ | 63.00% | 63.63% | 80.53% | 78.09%
KPar | 10.02% | 8.63% | 17.56% | 48.36%
KPar++ | 32.91% | 32.75% | 33.33% | 50.39%
TBar | 4.99% | 3.34% | 10.93% | 26.26%
TBar++ | 36.65% | 37.25% | 40.65% | 34.11%

Table 15. SeAPR with additional patch information

Fixing pattern information further boosts SeAPR’s performance on all the
studied repair tools (e.g., by up to 62.44 pp). Fixing pattern information
tends to work better with coarser-grained granularities.

###  5.6. RQ6: Boosting SeAPR with Other APR Tools

| Arja | Avatar | Cardumen | FixMiner | GenProg-A | JGenProg | JKali | JMutRepair | Kali-A | KPar | RSRepair-A | TBar
---|---|---|---|---|---|---|---|---|---|---|---|---
Chart | 87.06% | 28.20% | 24.24% | 57.84% | 85.08% | 90.00% | 0.00% | 27.27% | 55.24% | 45.15% | 84.47% | -8.67%
Closure | — | 67.36% | — | — | — | — | — | — | — | 63.49% | — | -7.38%
Lang | 52.31% | 53.76% | 32.00% | 42.55% | -538.30% | -200.00% | 48.15% | 24.10% | — | 1.94% | 16.25% | -63.06%
Math | 80.03% | — | 37.50% | — | 71.77% | 70.00% | 47.62% | 12.50% | 76.64% | 27.43% | 76.30% | 38.53%
Mockito | — | 25.00% | — | — | — | — | — | — | — | 55.49% | — | 17.95%
Time | — | 94.89% | — | 13.95% | — | — | — | — | — | 68.27% | — | 44.68%
Overall | 83.68% | 62.10% | 30.49% | 47.73% | 63.50% | 62.50% | 42.31% | 20.92% | 71.71% | 38.29% | 67.31% | -1.59%

Table 16. SeAPR historical results

Table 16 shows the impact of historical information for our default
configuration. Note, we filter out all known correct patches from this
historical information, since developers will stop the repair process after
finding any correct patch, thus alleviating the need for SeAPR. Compared to
Table 9, we observe improvements across most repair tools, up to 65.35 pp
(Kali-A). Most notably, the only tool with originally negative performance
(Cardumen) now has 30.49% reduction, i.e., over 37 pp improvement.

Likewise, the only two instances of degradation comes from GenProg-A and TBar,
e.g., GenProg-A degrades from 78.81% to 63.50%, while TBar degrades from
10.93% to -1.59%. Closer inspection reveals that one reason for such
degradation mainly comes from specific projects rather than consistent
degradation over all projects. For example, for TBar, the performance for
Chart drops by over 57 pp. Meanwhile, for TBar, SeAPR can still be massively
effective on other projects, e.g. the average rank on the Time subject over 2
versions decreases from 64.5 to 13.5, a performance increase from -174.47% to
44.68% .

Supplementing SeAPR with patch-execution information from other repair tools
can further boost the overall performance of SeAPR. This extra historical
information, compared to SeAPR’s default configuration, can further boost the
results by 21.43 pp on average and up to 65.35 pp.

##  6\. Conclusion

We have proposed the first self-boosted APR technique, SeAPR, which leverages
the execution information of validated patches during APR to prioritize the
remaining patches on-the-fly for faster APR. In particular, for each remaining
patch, SeAPR infer its similarity with the validated high/low-quality patches
and promotes/degrades it accordingly to speed up plausible/correct patch
generation. We conducted an extensive study to evaluate SeAPR on 12 state-of-
the-art APR systems and the widely used Defects4J benchmark suite. The
experimental results demonstrate that the default SeAPR can overall reduce
35.52% patch validations with negligible overhead (e.g., 0.5s on average). We
further studied the impact of different configurations on SeAPR, and observed
that (1) SeAPR has stable performance when using different SBFL formulae for
patch prioritization, (2) SeAPR can effectively reduce patch executions for
most studied repair tools with patch-modification matrices at all four
granularities (e.g., package, class, method and statement levels) and SeAPR
with finer-grained modification matrices tends to achieve better overall
improvement, (3) SeAPR works for both partial/full patch-validation matrices
and tends to perform better with partial matrices, (4) SeAPR can be further
improved by utilizing additional patch pattern information to compute patch
similarity, and (5) SeAPR can perform even better by leveraging patch-
execution information from other repair tools.

## References

  * (1)
  * Tri (2020) 2020\.  Tricentis reports.  https://www.tricentis.com/resources/software-fail-watch-5th-edition/
  * Abreu et al. (2007) Rui Abreu, Peter Zoeteweij, and Arjan J.C. Van Gemund. 2007\.  On the accuracy of spectrum-based fault localization. In _Proceedings - Testing: Academic and Industrial Conference Practice and Research Techniques, TAIC PART-Mutation 2007_.  https://doi.org/10.1109/TAICPART.2007.4344104
  * Benton et al. (2020) Samuel Benton, Xia Li, Yiling Lou, and Lingming Zhang. 2020\.  On the Effectiveness of Unified Debugging: An Extensive Study on 16 Program Repair Systems. In _ASE 2020 - Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering_. Melborn, Australia.
  * Boulder (2013) CO Boulder. 2013\.  University of Cambridge Study: Failure to Adopt Reverse Debugging Costs Global Economy $41 Billion Annually.  https://www.roguewave.com/company/news/2013/university-of-cambridge-reverse-debugging-study.  Accessed: Jan. 8, 2019.
  * Chen and Zhang (2020) Lingchao Chen and Lingming Zhang. 2020.  Fast and precise on-the-fly patch validation for all.
  * De Moura and Bjørner (2008) Leonardo De Moura and Nikolaj Bjørner. 2008.  Z3: An efficient SMT Solver. In _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , Vol. 4963 LNCS.  https://doi.org/10.1007/978-3-540-78800-3{_}24
  * Ding et al. (2020) Yangruibo Ding, Baishakhi Ray, and Vincent J Hellendoorn. 2020\.  Patching as Translation : the Data and the Metaphor. In _ASE 2020 - Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering_. 327–338.
  * Durieux and Monperrus (2016) Thomas Durieux and Martin Monperrus. 2016.  DynaMoth: Dynamic code synthesis for automatic program repair. In _Proceedings - 11th International Workshop on Automation of Software Test, AST 2016_.  https://doi.org/10.1145/2896921.2896931
  * Ghanbari et al. (2019) A. Ghanbari, S. Benton, and L. Zhang. 2019.  Practical program repair via bytecode mutation. In _ISSTA 2019 - Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis_.  https://doi.org/10.1145/3293882.3330559
  * Jiang et al. (2019) Jiajun Jiang, Luyao Ren, Yingfei Xiong, and Lingming Zhang. 2019\.  Inferring program transformations from singular examples via big code. In _Proceedings - 2019 34th IEEE/ACM International Conference on Automated Software Engineering, ASE 2019_.  https://doi.org/10.1109/ASE.2019.00033
  * Jiang et al. (2018) Jiajun Jiang, Yingfei Xiong, Hongyu Zhang, Qing Gao, and Xiangqun Chen. 2018.  Shaping program repair space with existing patches and similar code. In _ISSTA 2018 - Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis_.  https://doi.org/10.1145/3213846.3213871
  * Jones and Harrold (2005) James A. Jones and Mary Jean Harrold. 2005.  Empirical evaluation of the tarantula automatic fault-localization technique. In _20th IEEE/ACM International Conference on Automated Software Engineering, ASE 2005_.  https://doi.org/10.1145/1101908.1101949
  * Jones et al. (2002) James A. Jones, Mary Jean Harrold, and John Stasko. 2002\.  Visualization of test information to assist fault localization. In _Proceedings - International Conference on Software Engineering_.  https://doi.org/10.1145/581339.581397
  * Kim et al. (2013) Dongsun Kim, Jaechang Nam, Jaewoo Song, and Sunghun Kim. 2013\.  Automatic patch generation learned from human-written patches. In _Proceedings - International Conference on Software Engineering_.  https://doi.org/10.1109/ICSE.2013.6606626
  * Koyuncu et al. (2020) A. Koyuncu, K. Liu, T.F. Bissyandé, D. Kim, J. Klein, M. Monperrus, and Y. LeTraon. 2020.  FixMiner: Mining relevant fix patterns for automated program repair.  _Empirical Software Engineering_ (2020).  https://doi.org/10.1007/s10664-019-09780-z
  * Le et al. (2016) Xuan Bach D. Le, David Lo, and Claire Le Goues. 2016\.  History Driven Program Repair.  https://doi.org/10.1109/saner.2016.76
  * Le Goues et al. (2012) Claire Le Goues, Michael Dewey-Vogt, Stephanie Forrest, and Westley Weimer. 2012.  A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each.  _Proceedings - International Conference on Software Engineering_ (2012), 3–13.  https://doi.org/10.1109/ICSE.2012.6227211
  * Le Goues et al. (2013) Claire Le Goues, Stephanie Forrest, and Westley Weimer. 2013\.  Current challenges in automatic software repair.  _Software quality journal_ 21, 3 (2013), 421–443.
  * Liu et al. (2019a) K. Liu, A. Koyuncu, T. Bissyande, D. Kim, J. Klein, and Y. LeTraon. 2019a.  You cannot fix what you cannot find! an investigation of fault localization bias in benchmarking automated program repair systems.  _Proceedings - 2019 IEEE 12th International Conference on Software Testing, Verification and Validation, ICST 2019_ (2019).  https://doi.org/10.1109/ICST.2019.00020
  * Liu et al. (2019b) Kui Liu, Anil Koyuncu, Dongsun Kim, and Tegawende F. Bissyande. 2019b.  AVATAR: Fixing Semantic Bugs with Fix Patterns of Static Analysis Violations. In _SANER 2019 - Proceedings of the 2019 IEEE 26th International Conference on Software Analysis, Evolution, and Reengineering_.  https://doi.org/10.1109/SANER.2019.8667970
  * Liu et al. (2019c) Kui Liu, Anil Koyuncu, Dongsun Kim, and Tegawendé F. Bissyandé. 2019c.  TBAR: Revisiting template-based automated program repair. In _ISSTA 2019 - Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis_.  https://doi.org/10.1145/3293882.3330577
  * Liu et al. (2020) Kui Liu, Shangwen Wang, Anil Koyuncu, Kisub Kim, Tegawende F. Bissyande, Dongsun Kim, Peng Wu, Jacques Klein, Xiaoguang Mao, and Yves Le Traon. 2020\.  On the efficiency of test suite based program repair a systematic assessment of 16 automated repair systems for java programs. In _Proceedings - International Conference on Software Engineering_.  https://doi.org/10.1145/3377811.3380338
  * Long et al. (2017) Fan Long, Peter Amidon, and Martin Rinard. 2017.  Automatic inference of code transforms for patch generation. In _Proceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering_ , Vol. Part F130154.  https://doi.org/10.1145/3106237.3106253
  * Long and Rinard (2015) Fan Long and Martin Rinard. 2015.  Staged program repair with condition synthesis. In _2015 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2015 - Proceedings_.  https://doi.org/10.1145/2786805.2786811
  * Long and Rinard (2016a) Fan Long and Martin Rinard. 2016a.  An analysis of the search spaces for generate and validate patch generation systems. In _Proceedings \- International Conference on Software Engineering_ , Vol. 14-22-May-2016.  https://doi.org/10.1145/2884781.2884872
  * Long and Rinard (2016b) Fan Long and Martin Rinard. 2016b.  Automatic patch generation by learning correct code.  _ACM SIGPLAN Notices_ 51, 1 (2016).  https://doi.org/10.1145/2837614.2837617
  * Long et al. (2014) Fan Long, Stelios Sidiroglou-Douskos, and Martin Rinard. 2014\.  Automatic runtime error repair and containment via recovery shepherding. In _ACM SIGPLAN Notices_ , Vol. 49.  https://doi.org/10.1145/2594291.2594337
  * Lou et al. (2019) Yiling Lou, Junjie Chen, Lingming Zhang, Dan Hao, and Lu Zhang. 2019.  History-driven build failure fixing: How far are we?. In _ISSTA 2019 - Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis_.  https://doi.org/10.1145/3293882.3330578
  * Lou et al. (2020) Yiling Lou, Ali Ghanbari, Xia Li, Lingming Zhang, Haotian Zhang, Dan Hao, and Lu Zhang. 2020.  Can automated program repair refine fault localization? a unified debugging approach. In _ISSTA 2020 - Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis_.  https://doi.org/10.1145/3395363.3397351
  * Lutellier et al. (2020) Thibaud Lutellier, Hung Viet Pham, Lawrence Pang, Yitong Li, Moshi Wei, and Lin Tan. 2020.  CoCoNuT: Combining context-aware neural translation models using ensemble for program repair.  _ISSTA 2020 - Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis_ (2020), 101–114.  https://doi.org/10.1145/3395363.3397369
  * Marginean et al. (2019) A. Marginean, J. Bader, S. Chandra, M. Harman, Y. Jia, K. Mao, A. Mols, and A. Scott. 2019.  SapFix: Automated End-To-End Repair at Scale.  _Proceedings - 2019 IEEE/ACM 41st International Conference on Software Engineering: Software Engineering in Practice, ICSE-SEIP 2019_ (2019).  https://doi.org/10.1109/ICSE-SEIP.2019.00039
  * Martinez and Monperrus (2016) Matias Martinez and Martin Monperrus. 2016.  ASTOR: A program repair library for Java (Demo). In _ISSTA 2016 - Proceedings of the 25th International Symposium on Software Testing and Analysis_.  https://doi.org/10.1145/2931037.2948705
  * Martinez and Monperrus (2018) Matias Martinez and Martin Monperrus. 2018.  Ultra-large repair search space with automatically mined templates: The cardumen mode of astor. In _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , Vol. 11036 LNCS.  https://doi.org/10.1007/978-3-319-99241-9{_}3
  * Mehne et al. (2018a) Ben Mehne, Hiroaki Yoshida, Mukul R Prasad, Koushik Sen, Divya Gopinath, and Sarfraz Khurshid. 2018a.  Accelerating search-based program repair. In _2018 IEEE 11th International Conference on Software Testing, Verification and Validation (ICST)_. IEEE, 227–238.
  * Mehne et al. (2018b) Ben Mehne, Hiroaki Yoshida, Mukul R. Prasad, Koushik Sen, Divya Gopinath, and Sarfraz Khurshid. 2018b.  Accelerating Search-Based Program Repair. In _Proceedings - 2018 IEEE 11th International Conference on Software Testing, Verification and Validation, ICST 2018_.  https://doi.org/10.1109/ICST.2018.00031
  * Pei et al. (2014) Yu Pei, Carlo A. Furia, Martin Nordio, Yi Wei, Bertrand Meyer, and Andreas Zeller. 2014\.  Automated fixing of programs with contracts.  _IEEE Transactions on Software Engineering_ 40, 5 (2014).  https://doi.org/10.1109/TSE.2014.2312918
  * Perkins et al. (2009) Jeff H. Perkins, Sunghun Kim, Sam Larsen, Saman Amarasinghe, Jonathan Bachrach, Michael Carbin, Carlos Pacheco, Frank Sherwood, Stelios Sidiroglou, Greg Sullivan, Weng Fai Wong, Yoav Zibin, Michael D. Ernst, and Martin Rinard. 2009\.  Automatically patching errors in deployed software. In _SOSP’09 - Proceedings of the 22nd ACM SIGOPS Symposium on Operating Systems Principles_.  https://doi.org/10.1145/1629575.1629585
  * Qi et al. (2013) Yuhua Qi, Xiaoguang Mao, and Yan Lei. 2013.  Efficient automated program repair through fault-recorded testing prioritization. In _IEEE International Conference on Software Maintenance, ICSM_.  https://doi.org/10.1109/ICSM.2013.29
  * Qi et al. (2015) Zichao Qi, Fan Long, Sara Achour, and Martin Rinard. 2015\.  An analysis of patch plausibility and correctness for generate-and-validate patch generation systems.  _2015 International Symposium on Software Testing and Analysis, ISSTA 2015 - Proceedings_ (2015), 24–36.  https://doi.org/10.1145/2771783.2771791
  * Saha et al. (2017) Ripon K Saha, Yingjun Lyu, Hiroaki Yoshida, and Mukul R Prasad. 2017.  ELIXIR : Effective Object-Oriented Program Repair.  (2017), 648–659.
  * van Tonder and Goues (2018) Rijnard van Tonder and Claire Le Goues. 2018.  Static automated program repair for heap properties.  https://doi.org/10.1145/3180155.3180250
  * Wang et al. (2020) Shangwen Wang, Ming Wen, Bo Lin, Xiaoguang Mao, Hongjun Wu, Deqing Zou, Hai Jin, and Yihao Qin. 2020\.  Automated Patch Correctness Assessment: How Far are We?. In _ASE 2020 - Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering_. 1166–1178.  https://doi.org/10.1145/3324884.3416590
  * Weimer et al. (2013) Westley Weimer, Zachary P Fry, and Stephanie Forrest. 2013\.  Leveraging program equivalence for adaptive program repair: Models and first results. In _2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 356–366.
  * Wen et al. (2018) Ming Wen, Junjie Chen, Rongxin Wu, Dan Hao, and Shing Chi Cheung. 2018.  Context-aware patch generation for better automated program repair. In _Proceedings - International Conference on Software Engineering_ , Vol. 2018-January.  https://doi.org/10.1145/3180155.3180233
  * Wong et al. (2016) W. Eric Wong, Ruizhi Gao, Yihao Li, Rui Abreu, and Franz Wotawa. 2016.  A survey on software fault localization.  https://doi.org/10.1109/TSE.2016.2521368
  * Wu et al. (2019) Mingyuan Wu, Lingming Zhang, Cong Liu, Shin Hwei Tan, and Yuqun Zhang. 2019.  Automating CUDA synchronization via program transformation. In _Proceedings - 2019 34th IEEE/ACM International Conference on Automated Software Engineering, ASE 2019_.  https://doi.org/10.1109/ASE.2019.00075
  * Xiong et al. (2017) Y. Xiong, J. Wang, J. Zhang, G. Huang, L. Zhang, R. Yan, and S. Han. 2017\.  Precise condition synthesis for program repair.  (2017).  https://doi.org/10.1109/ICSE.2017.45
  * Xuan et al. (2017) Jifeng Xuan, Matias Martinez, Favio DeMarco, Maxime Clement, Sebastian Lamelas Marcote, Thomas Durieux, Daniel Le Berre, and Martin Monperrus. 2017.  Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs.  _IEEE Transactions on Software Engineering_ 43, 1 (2017).  https://doi.org/10.1109/TSE.2016.2560811
  * Yuan and Banzhaf (2018) Yuan Yuan and Wolfgang Banzhaf. 2018.  ARJA: Automated Repair of Java Programs via Multi-Objective Genetic Programming.  _IEEE Transactions on Software Engineering_ (2018).  https://doi.org/10.1109/TSE.2018.2874648
  * Zhang et al. (2013) Lingming Zhang, Darko Marinov, and Sarfraz Khurshid. 2013\.  Faster mutation testing inspired by test prioritization and reduction. In _2013 International Symposium on Software Testing and Analysis, ISSTA 2013 - Proceedings_.  https://doi.org/10.1145/2483760.2483782
  * Zhang et al. (2017) Mengshi Zhang, Xia Li, Lingming Zhang, and Sarfraz Khurshid. 2017\.  Boosting spectrum-based fault localization using pagerank. In _Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis_. 261–272.