# Longitudinal Analysis of the
Applicability of Program Repair on Past Commits

Khashayar Etemadi<EMAIL_ADDRESS>KTH Royal Institute of
TechnologyStockholmSweden ,  Niloofar Tarighat
<EMAIL_ADDRESS>Sharif University of TechnologyTehranIran ,
Siddharth Yadav<EMAIL_ADDRESS>Indraprastha Institute of
Information Technology DelhiNew DelhiIndia ,  Matias Martinez
<EMAIL_ADDRESS>Université Polytechnique Hauts-de-
FranceValenciennesFrance and  Martin Monperrus<EMAIL_ADDRESS>KTH Royal Institute of TechnologyStockholmSweden

(2020)

###### Abstract.

The applicability of program repair in the real world is a little researched
topic. Existing program repair systems tend to only be tested on small bug
datasets, such as Defects4J, that are not fully representative of real world
projects. In this paper, we report on a longitudinal analysis of software
repositories to investigate if past commits are amenable to program repair.
Our key insight is to compute whether or not a commit lies in the search space
of program repair systems. For this purpose, we present RSCommitDetector,
which gets a Git repository as input and after performing a series of static
analyses, it outputs a list of commits whose corresponding source code changes
could likely be generated by notable repair systems. We call these commits the
“repair-space commits”, meaning that they are considered in the search space
of a repair system. Using RSCommitDetector, we conduct a study on $41,612$
commits from the history of $72$ Github repositories. The results of this
study show that $1.77\%$ of these commits are repair-space commits, they lie
in the search space of at least one of the eight repair systems we consider.
We use an original methodology to validate our approach and show that the
precision and recall of RSCommitDetector are $77\%$ and $92\%$, respectively.
To our knowledge, this is the first study of the applicability of program
repair with search space analysis.

††copyright: acmcopyright††journalyear: 2020††doi: ???††ccs: Software and its
engineering Software maintenance tools

##  1\. Introduction

Fixing software bugs is a notoriously time-consuming task for developers (Saha
et al., 2017). To address this issue, automatic program repair systems apply
repair strategies to fix software bugs without human intervention. These
systems have shown promising results on bug datasets, such as Defects4J (Just
et al., 2014) and Bugs.jar (Saha et al., 2018). However, it has been shown
that the performance of program repair on one of such datasets does not
necessarily generalize to other datasets (Durieux et al., 2019). Consequently,
the existing evaluations cannot be taken as fully revealing the applicability
of program repair in real world.

In general, there are two major obstacles to evaluate the applicability of
program repair systems. First, running repair systems to fix a bug requires a
huge computational power (Durieux et al., 2019). Second, most systems do test-
based program repair (Monperrus, 2017), hence require the program under repair
to have a test-suite that fails before the repair. However, it is hard to find
a large number of versions of real world projects with test-suites that can be
compiled and executed (Tufano et al., 2017). For example, after analyzing
$168,772$ Travis CI builds during more than two months, Madeiral et al.
(Madeiral et al., 2019) found that only $251\,(0.14\%)$ of them are real world
bugs that meet all criteria for being used in a sound evaluation for program
repair.

Considering the aforementioned challenges, we propose a novel way for
assessing the applicability of repair systems in real world. Instead of
actually running a repair system on bug datasets, our key idea is to
investigate how often past patches use the same repair strategies as the ones
employed by program repair systems. If a human patch uses the same repair
strategy as a program repair system, it can be assumed that this system would
be able, in theory, to repair the same bug (modulo implementation limitations
and computational power).

In this paper, we propose to specify the repair strategies that repair systems
use to change the source code of a buggy program. This specification is
actionable: given a repair strategy and a patch, we can say that the patch
uses the same repair strategy or not. Based on a set of repair strategy
specifications, we can identify the changes made by human developers that
correspond to known repair systems. We design and implement RSCommitDetector
for this. RSCommitDetector takes a Git repository as input and outputs the
list of commits whose corresponding source code changes could likely be
generated by a repair system. RSCommitDetector enables us to study the
applicability of program repair on past commits.

RSCommitDetector specifies the repair strategies based on the change pattern
specification language of Martinez et al. (Martinez and Monperrus, 2019). To
determine if the source code change of a commit $c$ could be generated by a
repair system $r$, RSCommitDetector statically analyzes the change in two
steps. Firstly, it checks whether the edit script of abstract syntax tree
(AST) follows one of the strategies employed by $r$. Secondly, it checks if
all code fragments used in the source code change can be synthesized by $r$.
If $c$ passes both checks, we say that $c$ lies in the search space of $r$.
The current version of RSCommitDetector specifies the search space of $8$
notable repair systems: Arja (Yuan and Banzhaf, 2018), Cardumen (Martinez and
Monperrus, 2018), Elixir (Saha et al., 2017), GenProg (Le Goues et al.,
2012b), jMutRepair (Martinez and Monperrus, 2016), Kali (Qi et al., 2015),
Nopol (Xuan et al., 2016), and NPEfix (Cornu et al., 2015).

To study the applicability of program repair on past commits, we run
RSCommitDetector on $72$ projects of Bears (Madeiral et al., 2019). We also
conduct two systematic experiments to measure how accurately RSCommitDetector
determines whether a commit lies in the search space of a system. Our results
show that RSCommitDetector has a precision and recall of $77\%$ and $92\%$,
which is arguably high, but there is no other tools doing the same task for
comparing. For perspective, defect prediction over commits is a similar task,
and a state-of-the-art tool reports on a precision and recall of $72\%$ and
$65\%$ (Pascarella et al., 2019).

By analyzing $41,612$ commits, our experiments show that $1.77\%$
($737/41,612$) of all the commits lie in the search space of at least one
repair system. This is a key result for automated repair research. First, it
means that it is possible to create large datasets of commits for program
repair research: since there are millions of commits in open-source
repositories, $1.77\%$ represents a fair number. Such commit datasets are
utilized for different purposes, like data-driven tuning of repair systems
(Long and Rinard, 2016b) and training neural networks to generate commit
messages for program repair patches (Jiang et al., 2017; Monperrus, 2019).
Second, this provides a real-world estimation of the percentage of bugs which
can be automatically repaired, 9.3% (see Section 5.1 for the explanation),
this estimation 1) is consistent with recent results (9.9% for Bears (Durieux
et al., 2019)), and 2) is more realistic than previous estimations (e.g. 52%
(Le Goues et al., 2012a)). We note that among the considered repair systems,
Elixir (Saha et al., 2017) is the system whose search space covers the largest
number of commits $(0.86\%)$, while jMutRepair search space covers the least
($0.01\%$) of all considered commits.

To sum up our contributions are:

  * •

A conceptual framework for specifying the search space of program repair
systems, appropriate to study the applicability of program repair on past
commits of software repositories.

  * •

RSCommitDetector, a publicly available tool that implements the conceptual
framework. Given a Git repository, RSCommitDetector automatically detects the
commits lying in the search space of 8 notable program repair systems.

  * •

A comprehensive series of longitudinal experiments. By analyzing $41,612$
commits from $72$ Github repositories, we show that $1.77\%$ of commits in
this dataset lie in the search space of at least one of the considered repair
systems. This is a major result because it gives practitioners a clear and
intuitive understanding of where a state-of-the-art of program repair lies.

  * •

A systematic measurement of the reliability of RSCommitDetector. Our prototype
system has a precision and recall of $77\%$ and $92\%$, respectively which is
arguably high w.r.t to the difficulty of code change analysis.

The rest of this paper is organized as follows: Section 2 presents the
terminology that we use in this paper. Section 3 describes our approach.
Section 4 and Section 5 explain the methodology and then the results of our
experiments. Discussion of the results appears in Section 6. Section 7 reviews
the related work. Finally, Section 8 concludes this paper.

##  2\. Terminology

We use the following concepts throughout this study:

Automatic Repair System: A software artifact that gets a buggy version of a
program as input and generates patches that fix the bug (Weimer et al., 2009).
To generate the patches, a repair system also requires an oracle that
determines whether a version of a program is buggy or correct. For example,
_test-suite based program repair systems_ use test-suites as the oracle (Le
Goues et al., 2012b).

Repair Operator: A type of atomic change that is applied on the buggy program
to repair the bug. For example, removing a statement from the source code is
an operator used by Kali (Qi et al., 2015).

Repair Strategy: A set of repair operators applied in conjunction by a repair
system to the buggy version of a program. For example, one of the strategies
employed by NPEfix (Cornu et al., 2015) is “skip method” (e.g., see 1). Per
this strategy, an if-statement is added before a suspicious statement. The
corresponding if-condition checks whether a variable used by the suspicious
statement is equal to null. If the if-condition holds, a return statement is
executed.

⬇

1 Set<E> removed = getAllEdges(sourceVertex, targetVertex);

2 + if(removed == null) {

3 + return null;

4 + }

5 removeAllEdges(removed);

Listing 1: Commit 275c6 in Jgrapht, which is in the search space of NPEFix, it
applies repair strategy “skip method”.

Repair Ingredient: An existing source code fragment that is reused by a repair
system to fix the bug (Martinez et al., 2014; White et al., 2019). For
example, in one of its repair strategies, GenProg (Le Goues et al., 2012b)
creates a candidate patch by replacing a suspicious statement by another
existing statement written elsewhere in the program. The latter is the
_ingredient_ of the candidate patch.

Note that ingredients can have different types. For example, in GenProg the
ingredient is a statement, in NPEfix (Cornu et al., 2015) it is a variable,
and in Cardumen (Martinez and Monperrus, 2018) it is a template mined from the
program under repair.

Scope of Ingredients: The scope of ingredients is all the parts of program
that are considered for extracting the ingredient (Martinez et al., 2014;
White et al., 2019). For example, when jGenProg (Martinez and Monperrus, 2016)
(a Java implementation of GenProg) replaces an old statement $s$ (written in
file $f$ from package $p$) with a new one, the new statement can be selected
from three different scopes:  1) same file (i.e., $f$),  2) same package
(i.e., from any file belonging to $p$), and  3) same program.

Search Space of Repair System: Let us assume a repair system $r$ with certain
repair strategies and scope of ingredients. When a program is given as the
input, the search space of $r$ is the set of all patches that $r$ can generate
for the program given the strategies and ingredients (Martinez and Monperrus,
2015).

##  3\. Longitudinal Analysis on Past Commits

###  3.1. Overview

In this paper, our main goal is to mine open-source repositories for detecting
repair-space commits, defined as follows:

Repair-space Commit: Given a commit $c$ that transforms the _old_version_ of a
program into the _new_version_ and a repair system $r$, we say that $c$ is a
“repair-space commit” for $r$ if and only if _new_version_ is in the search
space of $r$ when _old_version_ is given as the input.

For example, 1 is a real commit in project Jgrapht, this code change is in the
search space of NPEfix, hence we say that this commit is a repair-space commit
for NPEfix. In this example, line 1 and line 5 are from the old_version, while
in the new_version lines 2-4 are added. When the old_version is given to
NPEfix as input, new_version is in the search space because NPEfix can
generate it using the “skip method” strategy.

We design and implement RSCommitDetector to detect repair-space commits.
RSCommitDetector encodes the search space of repair systems. In particular, it
encodes each repair strategy $rs$ by specifying  a)  the repair operators from
$rs$, expressed using fine-grained code changes, and  b)  the rules that those
changes must respect (e.g., the code introduced by a change is a valid
ingredient according to a given scope).  If a commit is detected by
RSCommitDetector to lie in the search space of a repair system, we call it a
“detected repair-space commit”.

Figure 1 shows an overview of how RSCommitDetector works. The whole process
consists of four steps.  1) Input preparation: for a given Git repository, the
tool identifies updated files for each commit.  2) Extracting AST actions: for
each updated file, the actions that transform the AST of the old revision into
the new one are extracted.  3) Extracting change pattern instances: the
updated files whose corresponding AST actions match a “repair systems change
pattern” are determined. We design the change patterns to model the repair
strategies employed by repair systems.  4) Final checking: the commits whose
updated files match change patterns are checked to see if the new code
fragments that they use for the update can also be generated by the repair
systems.  The result of the fourth step are the commits that RSCommitDetector
detects as repair-space commits.

In Section 3.2 to Section 3.5, we present each of these steps with more
details.

Figure 1. Overview of RSCommitDetector’s approach.

###  3.2. Input Preparation

Algorithm 1 shows how RSCommitDetector works. It takes as input the path to a
Git repository and a repair system whose search space should be considered.
Then, RSCommitDetector traverses over the history of the repository from the
oldest commit to the most recent one.

For each commit $c$, RSCommitDetector retrieves the updated files (line 9).
For each of those files $f$, it keeps a pair of file <$f_{p}$, $f_{n}$>, where
<$f_{p}$> is the version of $f$ previous to $c$ (retrieved in line 10), and
<$f_{n}$> is the new version obtained after $c$ (retrieved in line 11).

###  3.3. Extracting AST Actions from Updated Files

In the second step, RSCommitDetector computes the differences between the pair
of files <$f_{p}$, $f_{n}$> (line 12). The output of this step is a _diff_ ,
it comes in the form of an _edit script (ES)_ , a list of actions that
transforms $f_{p}$ into $f_{n}$.

RSCommitDetector computes these actions at the AST level using the GumTree
algorithm (Falleri et al., 2014). There are four types of action:  1) update,
which changes the value of an AST node,  2) insert, which inserts a new AST
node,  3) delete, which deletes an existing AST node, and  4) move, which
moves an AST node and makes it child of another node.  These extracted fine-
grained AST actions are passed to the next step.

###  3.4. Extracting Change Pattern Instances

This step determines if the fine-grained AST actions from a diff correspond to
those that can be synthesized by a repair system. For each repair system, we
come up with one or more change pattern specifications that define its search
space.

If a diff corresponds to at least one change pattern we say that the diff is
an _instance_ of the change pattern. We now describe the specification
language and then the matching process.

####  3.4.1. Change Pattern Specification

In RSCommitDetector, each pattern specifies a specific repair strategy of a
program repair system. The patterns are represented in the change pattern
specification language of Martinez et al. (Martinez and Monperrus, 2019),
which we now briefly present. A change pattern consists of a set of actions,
and each action is performed on an entity. The types of actions of pattern
specifications are the same as the types of AST actions that GumTree extracts
(update, insert, delete, and move). In addition to these action types, a
change pattern can also contain an action of unchanged type, which indicates
an entity should not be changed (i.e., not affected by any action). Finally, a
change pattern can also define parenthood relations between entities.

For example, 2 is a change pattern that corresponds to a repair strategy used
by jMutRepair (Martinez and Monperrus, 2016). Due to this strategy, a binary
operator inside an if-condition should be changed to another operator. Line 6
of the 2 represents the update action. As it is stated the “entityId” of the
subject entity is “2”. Therefore, this action is performed on the entity
defined in line 3. As shown in the specification, the type of this entity is
“BinaryOperator” and the id of its parent is “1” (see line 4). Finally, the
parent entity is defined in line 2 and as it is mentioned there its type is
“If”.

⬇

1<pattern name="binary_upd">

2 <entity id="1" type="If"/>

3 <entity id="2" type="BinaryOperator">

4 <parent parentId="1">

5 </entity>

6 <action entityId="2" type="UPD"/>

7</pattern>

Listing 2: One of the change pattern specifications for jMutRepair.

####  3.4.2. Change Pattern Matching

For each change pattern specification $p$ of a repair system, RSCommitDetector
checks if $p$ matches with the AST actions ($ES$) previously computed (line
14). To this end, for each action $A_{p}$ specified in $p$, RSCommitDetector
checks whether there exists an actual action in $ES$ that affects the nodes
specified by $A_{p}$. Moreover, every action in $ES$ should correspond to one
of the actions specified in $p$. In other words, there should be a one-to-one
relationship between actual actions in $ES$ and specified actions in $p$.
Otherwise, the commit $c$ is discarded. The details of the matching process
can be found in (Martinez and Monperrus, 2019).

Algorithm 1 RSCommitDetector Algorithm.

1:Inputs:

2: gitRepo: The given Git repository repairSystem: The repair system whose
search space should be considered

3:Outputs:

4: repairSpaceCommits: The set of detected repair-space commits for
repairSystem

5:$commits\leftarrow getCommits(gitRepo)$

6:$patterns\leftarrow getChangePatterns(repairSystem)$

7:for each commit $c$ in $commits$ do

8: $CPI\leftarrow[]$ /* CPI: changePatternInstances */

9: for each file $f$ in $getUpdatedFiles(c)$ do

10: $f_{p}\leftarrow getPreviousVersion(f)$

11: $f_{n}\leftarrow getNewVersion(f)$

12: $ES\leftarrow GetDiff(f_{p},f_{n})$ /* ES: Edit Script */

13: for each pattern $p$ in $patterns$ do

14: if $instanceOf(ES,p)$ then

15: $CPI.insert(ES)$

16: if $passesPostMatchingRules(CPI,c,repairSystem)$ then

17: $repairSpaceCommits.insert(c)$

###  3.5. Final Checking

After the commits whose edit scripts correspond to change patterns are
identified in the previous step, there is a final step. In order to make sure
that the repair systems are able to generate the source code changes in
identified commits, we also check particular rules that repair systems follow
for generating patches. We call these rules the _post-matching rules_. These
rules determine how a repair system synthesizes new code.

The post-matching rules can be divided into two groups:  1) rules specifying
how the ingredients are extracted, and  2) rules specifying how the
ingredients are merged together to form new code fragments that are used in
the patch.

As an example, Cardumen (Martinez and Monperrus, 2018) considers all the
variables and literals in the scope as the repair ingredients. Next, it takes
an existing expression and replaces its variables and literals with extracted
ingredients of the same type to make a new expression. This new expression is
then used to generate a patch.

The commits given as the input of this step that follow the post-matching
rules are considered as _repair-space commits_ by RSCommitDetector.

###  3.6. Repair Systems Considered

In this paper, we specify the search space of eight repair systems: Arja (Yuan
and Banzhaf, 2018), Cardumen (Martinez and Monperrus, 2018), Elixir (Saha et
al., 2017), GenProg (Le Goues et al., 2012b), jMutRepair (Martinez and
Monperrus, 2016), Kali (Qi et al., 2015), Nopol (Xuan et al., 2016), and
NPEfix (Cornu et al., 2015). We choose these tools because they are considered
in the RepairThemAll experiment (Durieux et al., 2019), which is to our
knowledge, the largest repair experiment done to date.

In Table 1, each row presents a brief overview of the change patterns and the
post-matching rules that we consider to encode the search space of the
corresponding repair system. For instance, three change patterns are
considered to encode the repair strategies employed by Arja, one for inserting
a new statement, one for removing a statement, and one for replacing a
statement. Moreover, in accordance with the process of synthesizing new
statements in Arja, we have a post-matching rule: the new statement should be
a copy of an existing statement, while the variables, literals, and methods
can be replaced by other variables, literals, and methods in the scope.

Table 1. Specification of the Search Space of 8 Notable Repair Systems Name |  Excerpt of Change Patterns |  Excerpt of Post-matching Rules
---|---|---
Arja |  Removing a statement; Inserting a new statement; Replacing a statement with a new one. |  The new statement should be a copy of an existing statement, while the variables, methods, and literals can be replaced by other variables, methods, and literals of the same type in the scope.
Cardumen |  Replacing an expression with a new expression. |  The new expression should be a copy of an existing expression, while the variables, and literals can be replaced by other variables, and literals of the same type in the scope. Moreover, the new expression should have the same return type as the old one.
Elixir |  Replacing the declaration type of a variable with a wider one (e.g float to double); Replacing a return expression with a new expression; Moving a statement into a new if-statement. The condition of the new if-statement checks if one of the variables used in the statement is not null; Mutating a binary operator. e.g., “<” to “>”; Replacing a method invocation with a new one; Inserting a new method invocation; Removing a predicate from the boolean expression of an if-condition or return statement; Adding a predicate to the boolean expression of an if-condition or return statement; Moving a statement into a new if-statement. The condition of the new if-statement checks if an array or collection access is in a range. |  All the code fragments used in a synthesized code should be collected from existing code. Specifically, a new method invocation should call a method that is already called in the scope. The argument list of a new method invocation should also be a list of literals and variables in the scope. For more details, please see the original paper by Saha et al. (Saha et al., 2017).
GenProg |  Removing a statement; Inserting a new statement; Replacing a statement with a new one. |  The new statement should be exactly a copy of an exiting statement in the scope.
jMutRepair |  Changing a unary or binary operator inside an if-condition. |  No post-matching rule.
Kali |  Removing a statement; Changing an if-condition to true/false; Inserting a return statement. |  No post-matching rule.
Nopol |  Replacing an if-condition with a new if-condition; Inserting a new if-statement and moving an existing statement into it. |  The new if-condition should consist of variables, methods, and literals that exist in the scope. We suppose that the repair system is able to generate the complex if-condtions that DynaMoth (Durieux and Monperrus, 2016) (a more advanced version of Nopol) generates.
NPEfix |  Moving a statement into a new if-statement. The if-condition checks if a variable used in the moved statement is not null; Moving a statement into a new if-statement. The if-condition checks if a variable used in the moved statement is not null. Also, add an else-block which returns “null” or a new object or another variable of the desired type; Moving a statement into a new if-statement. The if-condition checks if a variable used in the moved statement is not null. Also, add an else-block which executes the same statement but replaces the checked variable with a new object or another variable of the same type; Inserting a new if-statement before a target statement. The if-condition checks if a variable used in the target statement is null. The corresponding then-statement sets the value of the checked variable to a new object or another variable of the same type. |  The variables used in synthesized code should be from existing code in the scope.

###  3.7. Implementation

RSCommitDetector is built on top of Coming (Martinez and Monperrus, 2019).
Coming is designed to mine instances of code change patterns in Git
repositories. We extend Coming by adding change pattern specifications and
post-matching rules for the considered repair systems. The post-matching rules
are implemented in Java and the patterns are represented in change pattern
specification language (Martinez and Monperrus, 2019) as noted in Section
3.4.1. For all systems based on code reuse, RSCommitDetector considers that
the scope of ingredients is at the same file level. This means a repair-space
commit must utilize ingredients from the same file as the repair location. For
sake of open science, RSCommitDetector is publicly available (Anonymous,
2020).

##  4\. Experimental Methodology

###  4.1. Research Questions

In this paper, we study four research questions: the first one concerns a
longitudinal analysis of the applicability of program repair on past commits,
and the other three are investigations of the complexity and accuracy of
RSCommitDetector.

  * •

RQ1: How common are commits that lie in the search space of program repair
systems? Previous work has shown the strategies introduced by repair systems
are useful for fixing bugs. However, no one has studied to what extent using
those repair strategies is common in real-world programs. In this paper, we
present RSCommitDetector and utilize it to answer this question.

  * •

RQ2: How complex are the commit matching criteria that encode the repair
search space of program repair systems? RSCommitDetector specifies the search
space of eight existing common repair systems. To see to what extent our
approach can be applied to encode future repair systems, we also investigate
the complexity of change patterns and post-matching rules used in
RSCommitDetector.

  * •

RQ3: What is the recall of RSCommitDetector for automated repairability
identification in past commits?

  * •

RQ4: What is the precision of RSCommitDetector for automated repairability
identification in past commits?

###  4.2. Datasets

In this paper we use two datasets:  1) a set of Github repositories, and  2) a
set of patches (i.e., source code changes) that are generated by automatic
program repair systems.  These repositories and patches are collected as
follows.

The dataset of repositories, which we call ProjFromBears, contains all the
projects that are included in Bears (Madeiral et al., 2019). Bears focuses on
72 repositories. We consider projects of Bears since it has the most diverse
set of repositories among existing bug datasets. The median numbers of Java
files and commits are $357$ and $1,323$, respectively. As shown in Figure 2,
the size of the history of projects are diverse, and some projects have even
more than $10,000$ commits.

The second dataset, named Ground-truth, is a benchmark of patches made by
automatic repair systems. This dataset is built by joining data from other
datasets of patches, as follows. First, it includes all patches from DRR (Ye
et al., 2019), DRR contains a collection of patches generated by repair
systems on the Defects4J dataset (Just et al., 2014). Second, the Ground-truth
dataset includes the patches from NPEfix (Durieux et al., 2017). The Ground-
truth dataset contains $1,065$ patches in total. Cardumen has the highest
number of ground-truth patches ($285$) and Elixir has the lowest ($41$).

###  4.3. Protocol for RQ1

We use RSCommitDetector to answer RQ1. We run RSCommitDetector on all
repositories included in the ProjFromBears dataset. This experiment is carried
out in form of a sequence of executions. Each execution is represented by a
pair <repair_system, repository>. In total, we perform 576 (8 tools $\times$
72 projects) executions. In each execution, RSCommitDetector goes through the
commits of repository and checks if the source code changes in each commit are
in the search space of repair_system. The time limit for each execution is set
to $30$ minutes and commits are considered from the oldest one to the most
recent one.

The result of this experiment is a set of repair-space commits for each
<repair_tool, repository> pair. Based on those results, we look at which
systems have the widest applicability, i.e. perform changes that are common in
open source projects.

Figure 2. The distribution of the number of commits in the considered
projects, the median is $1,323$ commits, which shows that the BEARS dataset is
composed of serious open-source projects.

###  4.4. Protocol for RQ2

To answer RQ2, we compute a set of features for change pattern specifications
and post-matching rules (see Section 3.4.1 and Section 3.5). This set of
features consists of the total number of patterns, and actions and entities
inside the patterns. Also, the lines of code (LOC) is the metric that we
consider to measure the complexity of post-matching rules.

###  4.5. Protocol for RQ3

To answer RQ3, we design an experiment to determine how many of the patches
actually generated by a repair system are correctly detected by
RSCommitDetector. For this, we run RSCommitDetector on the Ground-truth
dataset. Ideally, RSCommitDetector should be able to detect all of these
source code changes as instances of corresponding repair systems. However, it
might happen that ground-truth patches cannot be detected by RSCommitDetector
due to the inaccuracy of how we encode the search space of repair systems. We
call these patches the false negatives patches (FN).

Moreover, there are ground-truth patches which do not follow the post-matching
rules. For example, some jGenProg ground-truth patches insert statements
selected from source files other than the changing file. Which means in these
ground-truth patches the scope of ingredients is not at the same file level.
We ignore this set of ground-truth patches in this experiment and call them
the ignored patches (IG). In total, $342$ patches are ignored and $723$
patches are considered.

Finally, the recall of RSCommitDetector can be calculated according to
Equation 1. In this equation GT represents the set of all ground-truth
patches. The right fraction in this equation is a more simplified version of
formula. In that fraction, CGT is the set of considered ground-truth patches:
the set of ground-truth patches excluding the ignored ones. Also, TP is the
set of true positives: the set of considered ground-truth patches that are
detected as repair-space commits by RSCommitDetector.

(1) $\mathit{recall}=\frac{(|GT|-|IG|)-|FN|}{(|GT|-|IG|)}=\frac{|TP|}{|CGT|}$

###  4.6. Protocol for RQ4

We measure the precision of RSCommitDetector as follows: we randomly select 30
of the commits that are detected as repair-space commits of each tool in RQ1
experiment. Next, we carry out a manual analysis to decide if the detected
repair-space commits actually lie of the search space of corresponding repair
systems or not. This manual analysis has seven participants, all of whom are
researchers in the field of automatic program repair: three PhD students, two
postdoctoral researchers, and two professors. Each commit is annotated by two
participants. If the first two annotations conflict with each other, a third
participant annotates to break the tie. All results from this experiment are
publicly available (see (Anonymous, 2020)).

The precision for each repair system is computed due to Equation 2. In this
equation, true positive (TP) represents the set of all detected repair-space
commits that are actual repair-space commits due to the manual investigation.
Moreover, RSCommits is the set of all detected repair-space commits for the
current repair system.

(2) $\mathit{precision}=\frac{|TP|}{|RSCommits|}$

##  5\. Experimental Results

We now present our experimental results on the applicability of program repair
on past commits.

###  5.1. Prevalence of Repair-space Commits in Open-source Repositories

Table 2 shows the results of our first experiment. In this table, each row
represents the data for one repair system. The “#RSC” and “%RSC” columns show
the number and percentage of all commits that RSCommitDetector detects as
repair-space commits of the corresponding system. The “#Unique_RSC” indicates
the number of commits that are detected to lie in the search space of only one
of the systems. Finally, the “AVG Time” column represents how many seconds it
takes on average for RSCommitDetector to check if a commit is in the search
space of the corresponding system. For example, among $41,612$ commits that
are analyzed against the search space of all eight systems, $303\;(0.72\%)$ of
them are detected to be in the search space of Arja. Moreover, $29$ of these
$303$ commits are not detected as repair-space commits for any other systems.

In total, $737\;(1.77\%)$ commits are considered repair-space commits for, at
least, one of the repair systems. Among the considered repair systems, the
search space of three of them cover more than $0.5\%$ of the commits: Arja,
Elixir, and GenProg. Given the change patterns used by these three systems, we
can conclude that adding and replacing statements with other statements from
the same file are common in the open-source Java projects. This result
confirms and strengthens the external validity of (Martinez et al., 2014).

This percentage is over all commits. An interesting related percentage is the
percentage of bug-fix commits that are in the search space of program repair
systems. Soto et al. showed that $19\%$ of commits of their dataset are bug-
fix commits (Soto et al., 2016), consequently, we can estimate that in our
dataset, there are $41,612*0.19=7,906$ bug-fix commits. This yields a
percentage of bug-fix commits that are in program repair search space, of
approximately $737/7,906=9.3\%$ on Bears. Interestingly, this corresponds
nicely with the results of Durieux et al. (Durieux et al., 2019), who showed
that the considered repair systems can fix $9.9\%$ of the bugs in the Bears
benchmark (those numbers are comparable because we consider the same projects
from the same benchmark, see Section 4.2). The consistency between a purely
static approach as RSCommitDetector on past and the actual execution of
program repair systems (Durieux et al., 2019) jointly reinforce the external
validity of both studies.

Now, let us discuss the speed of the analysis. The average time spent to check
if a commit is in the search space of a repair system is $0.81$ second. Elixir
has the slowest patterns and post-matching rules, RSCommitDetector needs
$1.72$ second to analyze if a commit is in the search space of Elixir. On the
contrary, the RSCommitDetector configured for Kali takes only $0.29$ second
per commit. Those numbers indicate that RSCommitDetector can scale to large
repositories: for instance, analyzing $3.3k$ commits (the maximum number of
commits for $99\%$ of Java projects on Github) against the search space of all
tools would take approximately $6$ hours, which is acceptable given that it is
one-short computation task.

Answer to RQ1: How common are commits that lie in the search space of program
repair systems?
According to our analysis, $1.77\%$ ($737/41,612$) of commits in 72 projects
of ProjFromBears dataset are detected as being in the search space of at least
one repair system. Elixir is the system whose search space covers the highest
number of commits $(0.86\%)$, while jMutRepair search space covers the lowest
$(0.01\%)$. RSCommitDetector is fast, it analyzes each commit against the
search space of each tools in $0.81$ seconds on average.
To the best of our knowledge, we are the very first to report on this
percentage, to quantitatively measure the applicability of program repair in
practice. Our results indicate that our approach can be used to collect large
datasets of human-made commits that are amenable to program repair. Such
datasets can then be utilized for different purposes, such as data-driven
tuning of program repair systems (Long and Rinard, 2016b) and training neural
networks to generate commit messages for bug-fix commits (Jiang et al.,
2017)(Monperrus, 2019).

Table 2. RQ1: The presence of repair-space commits in 72 open-source projects

System | #RSCa | %RSC | #Unique_RSC | AVG Time (s)
---|---|---|---|---
Arja | 303 | 0.72 | 29 | 0.76
Cardumen | 193 | 0.46 | 71 | 0.33
Elixir | 362 | 0.86 | 160 | 1.72
GenProg | 226 | 0.54 | 3 | 0.77
jMutRepair | 7 | 0.01 | 1 | 0.87
Kali | 147 | 0.35 | 7 | 0.29
Nopol | 145 | 0.34 | 46 | 1.34
NPEfix | 33 | 0.07 | 14 | 0.46
All | 737b | 1.77 | — | 0.81

  * a

RSC stands for “repair-space commits”. This column shows how many of the
$41,612$ commits that are analyzed against the search space of all tools are
detected as repair-space commits of this system.

  * b

$737$ commits are detected repair-space commits for at least one repair
system. Note that this is not the sum of numbers in this column.

###  5.2. Complexity of Repair Search Space Encoding

The results of the second experiment are shown in Table 3. Columns
“#Patterns”, “#Actions”, and “#Entities” indicate the total number of change
patterns, actions and entities inside them for each repair system that is
implemented in RSCommitDetector (see 2 and the discussion about it in Section
3.4.1 for details). The “LOC” column shows the number of Java code lines for
the post-matching rules implementation.

For instance, three change patterns are designed to encode the repair
strategies employed by Arja. These patterns consist of four actions and five
entities in total. Also, the post-matching rules are implemented in 343 lines
of Java code.

In total, we design $34$ pattern specifications with $51$ actions and $85$
entities to encode the search space of all systems. Among all the repair
systems, Elixir search space has the most complex encoding patterns with $17$
actions and $28$ entities. Moreover, the implementation of post-matching rules
contain $1,806$ lines of code in total. Arja has the largest post-matching
rules with $343$ lines.

Answer to RQ2: How complex are the commit matching criteria that encode the
repair search space of program repair systems?
We are able to encode the search space of eight repair systems using $34$
pattern specifications and $1,806$ lines of code. Elixir is the hardest search
space to encode, while Kali and jMutRepair are the easiest ones.
The biggest advantage of our approach to study the applicability of program
repair is that it is purely static, it only requires to encode the search
space with patterns and post-matching rules. Another way, employed in recent
work (Durieux et al., 2019; Liu et al., 2020), is to actually run the tool,
which has much higher requirements (being able to compile and execute each
commit). Our approach is appropriate for encoding the search space of notable
repair systems.

Table 3. RQ2: Features of Encoding XML Patterns and Filters System | #Patterns | #Actions | #Entities | LOC
---|---|---|---|---
Arja | 3 | 4 | 5 | 343
Cardumen | 3 | 5 | 5 | 273
Elixir | 12 | 17 | 28 | 288
GenProg | 2 | 2 | 3 | 176
jMutRepair | 2 | 4 | 6 | 78
Kali | 4 | 4 | 4 | 79
Nopol | 4 | 6 | 10 | 275
NPEfix | 4 | 9 | 24 | 294
Total | 34 | 51 | 85 | 1,806

###  5.3. Recall of RSCommitDetector

Table 4 studies the recall of RSCommitDetector. Columns “#CGT” and “#TP”
indicate the number of considered ground-truth and true positive patches,
respectively (see Section 4.5 for more details). The recall is computed
according to Equation 1.

For instance, there are $128$ ground-truth patches that are considered for
Arja and RSCommitDetector detects $116$ of them. Consequently, the recall for
Arja is $0.90$. RSCommitDetector has the lowest recall for Elixir ($0.83$) and
the highest one for jMutRepair, a perfect recall of $1$. The total recall is
$0.92$.

Since RSCommitDetector is the first tool of its type, there is no other work
that we can directly compare against. However, a close task is just-in-time
defect prediction, which is about predicting whether or not a code change
introduces new bugs (Pascarella et al., 2019). To give a sense of perspective,
the recall of a state-of-the-art tool in this area is $0.65$ (Pascarella et
al., 2019), which is well below our recall of $0.92$.

1 is an example of a NPEfix ground-truth patch that is detected by
RSCommitDetector. In contrast, 3 shows an example of a GenProg ground-truth
patch that is not detected. In this example, GenProg replaces the statement in
line 2 with the statement in line 3. However, RSCommitDetector finds that the
only change is removing “-index-1” argument. Consequently, this patch is is
not detected as a GenProg repair-space patch. This shows that our pattern
encoding is not perfect, it may miss some cases.

⬇

1 if (this.autoSort) {

2 - this.data.add(-index-1, new XYDataItem(x,y));

3\GHilight+ this.data.add(new XYDataItem(x,y));

4 }

Listing 3: Example of an undetected ground-truth patch.

Answer to RQ3: What is the recall of RSCommitDetector for automated
repairability identification in past commits?
Out of $723$ ground-truth cases, we compute that the recall of
RSCommitDetector is $0.92$, which is arguably high. Moreover, per repair
system, the recall has a minimum $0.83$ and a median of $0.905$. Therefore, we
conclude that RSCommitDetector can be trusted in terms of detecting commits
that actually lie in search spaces of program repair. Researchers in program
repair can rely on RSCommitDetector to perform a longitudinal analysis of
other open-source projects that are not in the considered benchmark.

Table 4. RQ3: Recall for Each Repair Search Space System | #CGT | #TP | Recall
---|---|---|---
Arja | 128 | 116 | 0.90
Cardumen | 124 | 111 | 0.91
Elixir | 37 | 31 | 0.83
GenProg | 116 | 101 | 0.87
jMutRepair | 52 | 52 | 1
Kali | 53 | 47 | 0.88
Nopol | 103 | 101 | 0.98
NPEfix | 110 | 107 | 0.97
Total | 723 | 668 | 0.92

###  5.4. Precision of RSCommitDetector

The computed precision is reported in Table 5. In this table, “#RSCommits” and
“#TP” indicate the number of detected repair-space commits in the sample set
and the number of true positives, respectively (see Section 4.6 for more
details). The precision is computed due to Equation 2.

Recall that for each repair system, 30 detected repair-space commits are
randomly sampled111Except for jMutRepair for which there are only $7$ repair-
space commits in total.. For instance, among the $30$ sampled detected repair-
space commits for Arja, $29$ of them are manually marked as true positives.
Therefore, the precision for Arja is $0.96$.

⬇

1 - if ((union & 0x0800) == 0) {

2 + if ((union & 0x0800) != 0) {

3 position.setLatitude(latitude);

4 position.setLongitude(longitude);

Listing 4: Example of a correctly detected jMutRepair repair-space commits.

⬇

1 - if (v1.equals(v2)) {

2 + if (v1 == null ? v2 == null : v1.equals(v2)) {

3 return options.fn();

4 }

Listing 5: Example of a wrongly detected Nopol repair-space commit. Nopol is
not able to synthesize ternary expressions (conditions with “?” and “:”
signs).

The results show that the precision is above $0.6$ for all the systems. We see
that RSCommitDetector has the best precision for Arja and Kali, where only one
commit is wrongly detected as a repair-space commit. In total, $169$ out of
$217$ sampled commits are true positives and the precision is $0.77$. Similar
to the recall, the precision of RSCommitDetector is much higher than the
precision of a state-of-the-art just-in-time defect prediction tool ($0.72$)
(Pascarella et al., 2019).

4 is an example of a true positive. This commit changes a “==” operator to a
“!=” operator and is correctly detected as a jMutRepair repair-space commit.
On the other hand, 5 presents an example of a false positive for Nopol. This
commit changes the condition of an if statement which in theory is in the
search space of Nopol. However, the Nopol manual analyst concluded that the
new condition is too complex to be synthesized by Nopol, because Nopol does
not support ternary expressions.

Answer to RQ4: What is the precision of RSCommitDetector for automated
repairability identification in past commits?
Thanks to the careful design of the matching criteria, the precision of
RSCommitDetector is $0.77$. It is never lower than $0.60$ for any of the
considered repair tools. This high precision is important for program repair
research: future researchers can rely on RSCommitDetector to create
specifically tailored benchmarks of commits corresponding to a given repair
system.

##  6\. Discussion

###  6.1. Threats to Validity

Complexity of search spaces: Because of the complexity of code change
analysis, there is no perfect encoding of repair search space. The encodings
implemented in RSCommitDetector do not yield a perfect matching. There are
different factors contributing to false positive and false negatives, incl.
noise in the commit, suboptimality of the AST edit script, and corner-cases of
the repair systems not captured in the declarative search space
specifications.

Tangled commits: As explained in Section 3.4.2, we consider a commit $c$ as a
repair-space commit of system $r$ only if all the changes in $c$ correspond to
a repair strategy employed by $r$. However, it is known that repositories
contain tangled commits where different changes are mixed in the same commit
(Herzig and Zeller, 2013). By construction, tangled commits in which only a
subset of the commit changes correspond to a repair strategy are not
considered as repair-space commits. This contributes to under-estimating the
proportion of repair-space commits”.

Multi-location repair: None of our search space encodings capture multi-
location fixes. In theory, certain repair systems (e.g., GenProg) could repair
bugs by modifying multiple locations (inc. multiple files). This means that we
may miss to multi-location repair-space commits. This is a minor issue
because, in practice, repair systems mostly generate single location patches
(Durieux et al., 2019).

Table 5. RQ4: Precision for Detected Repair-space Commits. System | #RSCommit | #TP | Precision
---|---|---|---
Arja | 30 | 29 | 0.96
Cardumen | 30 | 25 | 0.83
Elixir | 30 | 21 | 0.70
GenProg | 30 | 24 | 0.80
jMutRepair | 7 | 5 | 0.71
Kali | 30 | 29 | 0.96
Nopol | 30 | 18 | 0.60
NPEfix | 30 | 18 | 0.60
Total | 217 | 169 | 0.77

###  6.2. Generalizability of the Approach

In this paper, we encode the search space of repair tools for matching commits
in Java programs. We note that our approach is generic enough to identify
repair-space commits written in other programming languages. To implement the
approach for analyzing commits written in a new language, Table 1 provides the
specification to encode the patterns and post-matching rules for matching this
language. We note that the AST differencing library we use, GumTree, works for
all mainstream languages.

##  7\. Related Work

###  7.1. Analysis of the Redundancy Assumption

The key assumption behind GenProg is that the patch reuses some code from
elsewhere in the program, this is called the redundancy assumption. Previous
works have investigated this assumption. Barr et al. (Barr et al., 2014) and
Martinez et al. (Martinez et al., 2014) studied the assumption behind GenProg
(Le Goues et al., 2012b): patches are synthesized using fragments of code
already written in the program under repair. Those works measured the
redundancy of a commit: for each commit, the redundancy is the percentage of
code introduced that was already introduced by a previous commit. Our approach
is different, we verify that a single commit lies in the search space of a
repair system. Note that our post-matching rules also verifies the redundancy
of the introduced code for the repair actions that are based on the redundancy
assumption. For example, the post-matching rule of GenProg verifies whether
the statements included in a patch already exist in the buggy program.

###  7.2. Mining Bug-fix Patterns from Bug Datasets

Sobreira et al. (Sobreira et al., 2018) manually analyzed 395 ground-truth
patches of Defects4J (Just et al., 2014) buggy programs. They first identified
abstractions, called repair patterns, occurring recurrently in patches and
involving compositions of repair actions. They identified nine repair patterns
from the patches in Defects4J, which span 373 patches of the dataset (94.43%).

Madeiral et al. (Madeiral et al., 2018) presented PDD, a detector of repair
patterns in patches. PDD performs source code change analysis at abstract
syntax tree level and is able to detect the patterns found in Defects4J. PDD
and our work have important differences.  • First, they focus on a repair
patterns that capture human-made changes, while we focus on on repair patterns
that characterize automated fixes from program repair systems.  • Second, our
approach checks post-matching rules that are specific to repair systems (as
explained in Section 3.5), while PDD exclusively focuses on analyzing AST
changes.

###  7.3. Mining Instances of Code Changes

There are different works that inspect bug-fix commits and patches with the
goal of characterizing the bug-fixing activity.

Pan et al. (Pan et al., 2009) built a catalog with 27 bug-fix patterns that
they manually identified by inspecting the history of seven open-source Java
projects. Then, they build a tool for detecting instances of such bug-fix
patterns. They finally reported the frequency of each bug-fix pattern.

Other works have mined Pan’s pattern instances from other datasets. Campos and
Maia (Campos and Maia, 2017) measured the prevalence of the five most common
bug-fix patterns from (Pan et al., 2009). For this purpose, they queried the
Boa dataset (Dyer et al., 2015) to find how many of the $4,590,405$ included
commits follow each pattern. Islam and Zibran (Islam and Zibran, 2020) have
mined instances of 21 Pan’s pattern from bug-fix commits done on 5 Java
systems.

Those works have a different goal than ours. First, they focus on mining
instances of change patterns inside commits, while we focus on detecting
repair-space commits. Secondly, they only do AST differencing, while we note
that AST analysis is insufficient to detect repair-space commits. As we
presented in section 3.5, there are important additional rules that must be
verified in order to confirm that a patch can be synthesized by a repair
system.

###  7.4. Data-driven Program Repair

Similar to Pan et al., Kim et al. (Kim et al., 2013) manually inspected
patches of open-source projects and from that inspection they defined 10 fix
templates. Then, they proposed Pattern-based Automatic Program Repair (PAR), a
technique that applies these fix templates on faulty programs. Other works
have analyzed the presence of PAR’s fix templates on bug-fix patches. For
example, Soto et al. (Soto et al., 2016) detected instances of PAR templates
(Kim et al., 2013) from bug-fixes done in Java projects. For that, they
analyzed 4,590,679 bug-fixing revisions queried from the Boa platform (Dyer et
al., 2015). They found that the most frequent PAR template was "add or remove
a branch condition" pattern which appeared in 4.23% of the bug-fixing
revisions. We discuss the differences at the end of this subsection.

Martinez and Monperrus (Martinez and Monperrus, 2015) built a probabilistic
models of repair actions for guiding the navigation of the search space. Soto
and Le Goues (Soto and Le Goues, 2018) created one of such probabilistic
models of edit distributions that was used by a repair system to repair
faster. For that, the authors mined repair operators from bug-fixes done on
the 500 most-starred Java projects on Github. They encoded 19 operators in
total, selected from those defined by GenProg (Le Goues et al., 2012b), PAR
(Kim et al., 2013), SPR (Long and Rinard, 2015) and three additional PAR
templates.

Ghanbari et al. (Ghanbari et al., 2019) have mined real bug-fix patches from
the HDRepair dataset (Le et al., 2016) to measure the frequency of their
repair operators implemented in their approach PraPR. Their goal was to
further confirm the generality of the 18 PraPR mutators. The PraPR’s “ _MR
mutator_ ”, which mutates method invocation instructions, is the most frequent
operator: it appeared in 8.76% of the bug-fix patches for the HDRepair
dataset.

Those works and ours do the identification of _instances_ of bug-fix patterns.
However, none of them identifies repair-space commits. For that, our approach
does advanced detection of change pattern instances, and also checks rules
that are specific to each repair system. Moreover, none of those papers
evaluates the accuracy and precision of their tool as we do in this paper.

###  7.5. Analysis of the Patch Search Space

Weimer et al. (Weimer et al., 2013) presented AE, a repair approach that is
specifically designed for optimizing the search space, using a cost model and
multiple optimizations. For the evaluation of AE, the authors measured the
size of the search spaces of AE and GenProg (Le Goues et al., 2012a). Our
analysis is different, we do not measure the size of search spaces, we measure
the inclusion of real past commits in those search spaces.

Long and Rinard (Long and Rinard, 2016a) presented a systematic analysis of
the SPR (Long and Rinard, 2015) and Prophet (Long and Rinard, 2016b) patch
search spaces. With respect to our paper, the most related contribution of
(Long and Rinard, 2015) are that they analyze the density of correct and
plausible patches in the search space, and they characterize a trade-off
between the size and sophistication of the search space. Our approach has a
different goal, we do not analyze plausibility, we analyze past commits from
repositories to assess applicability of program repair.

Petke et al. (Petke et al., 2019) have surveyed the literature on the search
spaces of genetic improvement, where they consider that program repair is one
subset of such search spaces. Our paper provides a novel methodology for
studying repair search space, which encodes search spaces with patterns and
rules, and it would be helpful for genetic improvement research beyond program
repair.

##  8\. Conclusion

In this paper, we have presented the original concept of measuring the
applicability of program repair systems on past commits. Our approach is based
on static analysis of code changes and is implemented in RSCommitDetector.
Using RSCommitDetector, we conduct an experiment on $41,612$ commits from 72
Github projects. We found that $1.77\%$ of the commits lie in the search space
of at least one of the eight considered program repair systems. Our tool is
reliable, it has a precision and recall of $77\%$ and $92\%$, respectively.

This paves the way to collecting large datasets of human-made commits which
could have likely been made by repair systems. Such datasets are valuable for
important research directions in program repair, such as data-driven tuning of
program repair systems (Long and Rinard, 2016b) or training neural networks to
generate commit messages for program repair patches (Jiang et al., 2017;
Monperrus, 2019).

###### Acknowledgements.

This work was partially supported by the Wallenberg Artificial Intelligence,
Autonomous Systems and Software Program (WASP) funded by Knut and Alice
Wallenberg Foundation and the Swedish Foundation for Strategic Research (SSF).

## References

  * (1)
  * Anonymous (2020) Anonymous. 2020\.  RSCommitDetector tool and dataset.  https://anonymous.4open.science/r/4fc40a8d-fcab-4132-b654-c3110b8495fb/.
  * Barr et al. (2014) Earl T. Barr, Yuriy Brun, Premkumar Devanbu, Mark Harman, and Federica Sarro. 2014.  The Plastic Surgery Hypothesis. In _Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering_ (Hong Kong, China) _(FSE 2014)_. Association for Computing Machinery, New York, NY, USA, 306–317.  https://doi.org/10.1145/2635868.2635898
  * Campos and Maia (2017) Eduardo C. Campos and Marcelo A. Maia. 2017.  Common Bug-Fix Patterns: A Large-Scale Observational Study. In _Proceedings of the 11th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement_ (Markham, Ontario, Canada) _(ESEM ’17)_. IEEE Press, 404–413.  https://doi.org/10.1109/ESEM.2017.55
  * Cornu et al. (2015) Benoit Cornu, Thomas Durieux, Lionel Seinturier, and Martin Monperrus. 2015.  Npefix: Automatic runtime repair of null pointer exceptions in java.  _arXiv preprint arXiv:1512.07423_ (2015).
  * 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)_. IEEE, 349–358.
  * Durieux et al. (2019) Thomas Durieux, Fernanda Madeiral, Matias Martinez, and Rui Abreu. 2019.  Empirical review of Java program repair tools: a large-scale experiment on 2,141 bugs and 23,551 repair attempts. In _Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 302–313.
  * Durieux and Monperrus (2016) Thomas Durieux and Martin Monperrus. 2016.  Dynamoth: dynamic code synthesis for automatic program repair. In _Proceedings of the 11th International Workshop on Automation of Software Test_. 85–91.
  * Dyer et al. (2015) Robert Dyer, Hoan Anh Nguyen, Hridesh Rajan, and Tien N Nguyen. 2015.  Boa: Ultra-large-scale software repository and source-code mining.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 25, 1 (2015), 1–34.
  * Falleri et al. (2014) Jean-Rémy Falleri, Floréal Morandat, Xavier Blanc, Matias Martinez, and Martin Monperrus. 2014\.  Fine-grained and accurate source code differencing. In _Proceedings of the 29th ACM/IEEE international conference on Automated software engineering_. 313–324.
  * 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_ (Beijing, China) _(ISSTA 2019)_. Association for Computing Machinery, New York, NY, USA, 19–30.  https://doi.org/10.1145/3293882.3330559
  * Herzig and Zeller (2013) Kim Herzig and Andreas Zeller. 2013.  The impact of tangled code changes. In _2013 10th Working Conference on Mining Software Repositories (MSR)_. IEEE, 121–130.
  * Islam and Zibran (2020) Md Rakibul Islam and Minhaz F Zibran. 2020.  How bugs are fixed: exposing bug-fix patterns with edits and nesting levels. In _Proceedings of the 35th Annual ACM Symposium on Applied Computing_. 1523–1531.
  * Jiang et al. (2017) Siyuan Jiang, Ameer Armaly, and Collin McMillan. 2017\.  Automatically generating commit messages from diffs using neural machine translation. In _2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 135–146.
  * 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_. 437–440.
  * 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)_. IEEE, 802–811.
  * Le et al. (2016) X. B. D. Le, D. Lo, and C. L. Goues. 2016.  History Driven Program Repair. In _2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER)_ , Vol. 1. 213–224.
  * Le Goues et al. (2012a) C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer. 2012a.  A Systematic Study of Automated Program Repair: Fixing 55 Out of 105 Bugs for $8 Each. In _Proceedings of the International Conference on Software Engineering_. 3–13.
  * Le Goues et al. (2012b) C. Le Goues, T. Nguyen, S. Forrest, and W. Weimer. 2012b.  GenProg: A Generic Method for Automatic Software Repair.  _IEEE Transactions on Software Engineering_ 38, 1 (2012), 54–72.
  * Liu et al. (2020) Kui Liu, Shangwen Wang, Anil Koyuncu, Kisub Kim, Tegawendé François D Assise 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 _42nd ACM/IEEE International Conference on Software Engineering (ICSE)_.
  * Long and Rinard (2015) Fan Long and Martin Rinard. 2015.  Staged Program Repair with Condition Synthesis. In _Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering_ (Bergamo, Italy) _(ESEC/FSE 2015)_. Association for Computing Machinery, New York, NY, USA, 166–178.  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 of the 38th International Conference on Software Engineering_ (Austin, Texas) _(ICSE ’16)_. Association for Computing Machinery, New York, NY, USA, 702–713.  https://doi.org/10.1145/2884781.2884872
  * Long and Rinard (2016b) Fan Long and Martin Rinard. 2016b.  Automatic Patch Generation by Learning Correct Code.  _SIGPLAN Not._ 51, 1 (Jan. 2016), 298–312.  https://doi.org/10.1145/2914770.2837617
  * Madeiral et al. (2018) Fernanda Madeiral, Thomas Durieux, Victor Sobreira, and Marcelo Maia. 2018.  Towards an automated approach for bug fix pattern detection. In _VEM ’18 - Proceedings of the VI Workshop on Software Visualization, Evolution and Maintenance_. São Carlos, Brazil.  https://hal.archives-ouvertes.fr/hal-01851813
  * Madeiral et al. (2019) Fernanda Madeiral, Simon Urli, Marcelo Maia, and Martin Monperrus. 2019.  Bears: An Extensible Java Bug Benchmark for Automatic Program Repair Studies. In _2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER)_. IEEE, 468–478.
  * Martinez and Monperrus (2015) Matias Martinez and Martin Monperrus. 2015.  Mining software repair models for reasoning on the search space of automated program fixing.  _Empirical Software Engineering_ 20, 1 (2015), 176–205.
  * Martinez and Monperrus (2016) Matias Martinez and Martin Monperrus. 2016.  Astor: A program repair library for java. In _Proceedings of the 25th International Symposium on Software Testing and Analysis_. 441–444.
  * 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 _International Symposium on Search Based Software Engineering_. Springer, 65–86.
  * Martinez and Monperrus (2019) Matias Martinez and Martin Monperrus. 2019.  Coming: a tool for mining change pattern instances from git commits. In _2019 IEEE/ACM 41st International Conference on Software Engineering: Companion Proceedings (ICSE-Companion)_. IEEE, 79–82.
  * Martinez et al. (2014) Matias Martinez, Westley Weimer, and Martin Monperrus. 2014\.  Do the fix ingredients already exist? an empirical inquiry into the redundancy assumptions of program repair approaches. In _Companion Proceedings of the 36th International Conference on Software Engineering_. 492–495.
  * Monperrus (2017) Martin Monperrus. 2017\.  Automatic Software Repair: a Bibliography.  _ACM Computing Surveys_ 51 (2017), 1–24.  https://doi.org/10.1145/3105906
  * Monperrus (2019) Martin Monperrus. 2019\.  Explainable software bot contributions: Case study of automated bug fixes. In _2019 IEEE/ACM 1st International Workshop on Bots in Software Engineering (BotSE)_. IEEE, 12–15.
  * Pan et al. (2009) Kai Pan, Sunghun Kim, and E James Whitehead. 2009.  Toward an understanding of bug fix patterns.  _Empirical Software Engineering_ 14, 3 (2009), 286–315.
  * Pascarella et al. (2019) Luca Pascarella, Fabio Palomba, and Alberto Bacchelli. 2019\.  Fine-grained just-in-time defect prediction.  _Journal of Systems and Software_ 150 (2019), 22–36.
  * Petke et al. (2019) Justyna Petke, Brad Alexander, Earl T. Barr, Alexander E. I. Brownlee, Markus Wagner, and David R. White. 2019.  A Survey of Genetic Improvement Search Spaces. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ (Prague, Czech Republic) _(GECCO ’19)_. Association for Computing Machinery, New York, NY, USA, 1715–1721.  https://doi.org/10.1145/3319619.3326870
  * 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. In _Proceedings of the 2015 International Symposium on Software Testing and Analysis_. 24–36.
  * Saha et al. (2018) Ripon K Saha, Yingjun Lyu, Wing Lam, Hiroaki Yoshida, and Mukul R Prasad. 2018.  Bugs. jar: a large-scale, diverse dataset of real-world java bugs. In _Proceedings of the 15th International Conference on Mining Software Repositories_. 10–13.
  * Saha et al. (2017) Ripon K Saha, Yingjun Lyu, Hiroaki Yoshida, and Mukul R Prasad. 2017.  Elixir: Effective object-oriented program repair. In _2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 648–659.
  * Sobreira et al. (2018) Victor Sobreira, Thomas Durieux, Fernanda Madeiral, Martin Monperrus, and Marcelo A. Maia. 2018\.  Dissection of a Bug Dataset: Anatomy of 395 Patches from Defects4J. In _Proceedings of SANER_.
  * Soto and Le Goues (2018) M. Soto and C. Le Goues. 2018.  Using a probabilistic model to predict bug fixes. In _2018 IEEE 25th International Conference on Software Analysis, Evolution and Reengineering (SANER)_. 221–231.
  * Soto et al. (2016) Mauricio Soto, Ferdian Thung, Chu-Pan Wong, Claire Le Goues, and David Lo. 2016.  A Deeper Look into Bug Fixes: Patterns, Replacements, Deletions, and Additions. In _Proceedings of the 13th International Conference on Mining Software Repositories_ (Austin, Texas) _(MSR ’16)_. Association for Computing Machinery, New York, NY, USA, 512–515.  https://doi.org/10.1145/2901739.2903495
  * Tufano et al. (2017) Michele Tufano, Fabio Palomba, Gabriele Bavota, Massimiliano Di Penta, Rocco Oliveto, Andrea De Lucia, and Denys Poshyvanyk. 2017\.  There and back again: Can you compile that snapshot?  _Journal of Software: Evolution and Process_ 29, 4 (2017), e1838.
  * 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 _Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering_. 356–366.
  * Weimer et al. (2009) Westley Weimer, ThanhVu Nguyen, Claire Le Goues, and Stephanie Forrest. 2009.  Automatically finding patches using genetic programming. In _2009 IEEE 31st International Conference on Software Engineering_. IEEE, 364–374.
  * White et al. (2019) Martin White, Michele Tufano, Matias Martinez, Martin Monperrus, and Denys Poshyvanyk. 2019\.  Sorting and transforming program repair ingredients via deep learning code similarities. In _2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER)_. IEEE, 479–490.
  * Xuan et al. (2016) Jifeng Xuan, Matias Martinez, Favio Demarco, Maxime Clement, Sebastian Lamelas Marcote, Thomas Durieux, Daniel Le Berre, and Martin Monperrus. 2016.  Nopol: Automatic repair of conditional statement bugs in java programs.  _IEEE Transactions on Software Engineering_ 43, 1 (2016), 34–55.
  * Ye et al. (2019) He Ye, Matias Martinez, and Martin Monperrus. 2019.  Automated Patch Assessment for Program Repair at Scale.  arXiv:arXiv:1909.13694
  * 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).