# Are FPGAs Suitable for Edge Computing?

Saman Biookaghazadeh
Arizona State University  Ming Zhao
Arizona State University  Fengbo Ren
Arizona State University

### Abstract

The rapid growth of Internet-of-things (IoT) and artificial intelligence
applications have called forth a new computing paradigm–edge computing. In
this paper, we study the suitability of deploying FPGAs for edge computing
from the perspectives of throughput sensitivity to workload size,
architectural adaptiveness to algorithm characteristics, and energy
efficiency. This goal is accomplished by conducting comparison experiments on
an Intel Arria 10 GX1150 FPGA and an Nvidia Tesla K40m GPU. The experiment
results imply that the key advantages of adopting FPGAs for edge computing
over GPUs are three-fold: 1) FPGAs can provide a consistent throughput
invariant to the size of application workload, which is critical to
aggregating individual service requests from various IoT sensors; (2) FPGAs
offer both spatial and temporal parallelism at a fine granularity and a
massive scale, which guarantees a consistently high performance for
accelerating both high-concurrency and high-dependency algorithms; and (3)
FPGAs feature 3–4 times lower power consumption and up to 30.7 times better
energy efficiency, offering better thermal stability and lower energy cost per
functionality.

##  1 Introduction

The Internet-of-Things (IoT) will connect 50 billion devices and is expected
to generate 400 Zetta Bytes of data per year by 2020. Even considering the
fast-growing size of the cloud infrastructure, the cloud is projected to fall
short by two orders of magnitude to either transfer, store, or process such
vast amount of streaming data [3]. Furthermore, the cloud-based solution will
not be able to provide timely service for many time-sensitive IoT applications
[1] [14]. Consequently, the consensus in the industry is to expand our
computational infrastructure from data centers towards the edge. Over the next
decade, a vast number of edge servers will be deployed to the proximity of IoT
devices; a paradigm that is now referred to as fog/edge computing.

There are fundamental differences between traditional cloud and the emerging
edge infrastructure. The cloud infrastructure is mainly designed for (1)
fulfilling time-insensitive applications in a centralized environment; (2)
serving interactive requests from end users; and (3) processing batches of
static data loaded from memory/storage systems. Differently, the emerging edge
infrastructure has distinct characteristics, as it keeps the promise for (1)
servicing time-sensitive applications in a geographically distributed fashion;
(2) mainly serving requests from IoT devices, and (3) processing streams of
data from various input/output (I/O) channels. Existing IoT workloads often
arrive with considerable variance in data size and require extensive
computation, such as in the applications of artificial intelligence, machine
learning, and natural language processing. Also, the service requests from IoT
devices are usually latency-sensitive. Therefore, having a predictable latency
and throughput performance is critical for edge servers.

Existing edge servers on the market are simply a miniature version of cloud
servers (cloudlet) which are primarily structured based on CPUs with tightly
coupled co-processors (e.g., GPUs) [7] [6] [8] [2]. However, CPUs and GPUs are
optimized towards batch processing of memory data and can hardly provide
consistent nor predictable performance for processing streaming data coming
dynamically from I/O channels. Furthermore, CPUs and GPUs are power hungry and
have limited energy efficiency [4], creating enormous difficulties for
deploying them in energy- or thermal-constrained application scenarios or
locations. Therefore, future edge servers call for a new general-purpose
computing system stack tailored for processing streaming data from various I/O
channels at low power consumption and high energy efficiency.

OpenCL-based field-programmable gate array (FPGA) computing is a promising
technology for addressing the aforementioned challenges. FPGAs are highly
energy-efficient and adaptive to a variety of workloads. Additionally, the
prevalence of high-level synthesis (HLS) has made them more accessible to
existing computing infrastructures. In this paper, we study the suitability of
deploying FPGAs for edge computing through experiments focusing on the
following three perspectives: (1) sensitivity of processing throughput to the
workload size of applications, (2) energy-efficiency, and (3) adaptiveness to
algorithm concurrency and dependency degrees, which are important to edge
workloads as discussed above.

The experiments are conducted on a server node equipped with a Nvidia Tesla
K40m GPU and an Intel Fog Reference Design Unit [9] equipped with two Intel
Arria 10 GX1150 FPGAs. Experiment results show that (1) FPGAs can deliver a
predictable performance invariant to the application workload size, whereas
GPUs are sensitive to workload size; (2) FPGAs can provide 2.5–30 times better
energy efficiency compared to GPUs; and (3) FPGAs can adapt their hardware
architecture to provide consistent throughput across a wide range of
conditional or inter/intra-loop dependencies, while the GPU performance can
drop by up to 14 times from the low- to high-dependency scenarios.

The rest of the paper is organized as follows: Section 2 introduces the
background; Section 3 describes the methodology; Section 4 discusses
experimental results; and Section 5 concludes the paper.

##  2 Background

An FPGA is a farm of logic, computation, and storage resources that can be
reconfigured dynamically to compose either spatial or temporal parallelism at
a fine granularity. Traditional FPGA design requires hardware description
languages, such as VHDL and Verilog, making it out of the reach of application
developers. The advent of HLS technology [5] has opened enormous
opportunities. Today, one can develop FPGA kernel functions in high-level
programming languages (e.g., OpenCL [12]) and deploy the compiled hardware
kernels in a run-time environment for real-time computing [10]. Note that
OpenCL is a universal C-based programming model that can execute on a variety
of computing platforms, including CPUs, GPUs, DSP processors, and FPGAs [13].
The recently-extended support of OpenCL by FPGAs has opened the gate for
integrating FPGAs into heterogeneous HPC, cloud, and edge platforms.

Different from widely adopted CPUs and GPUs in the cloud, FPGAs come with
several unique features rendering them an excellent candidate for edge
computing. First, unlike GPUs and CPUs that are optimized for batch processing
of memory data, FPGAs are inherently efficient for accelerating streaming
applications. A pipelined streaming architecture with data flow control can be
easily built on an FPGA to process streams of data and commands from I/O
channels and generate output results at a constant throughput with reduced
latency.

Second, FPGAs can adapt to any algorithm characteristics due to their hardware
flexibility. Different from CPUs and GPUs that can mostly exploit only spatial
parallelism, FPGAs can exploit both spatial and temporal parallelism at a
finer granularity and on a massive scale. In spatial parallelism, processing
elements (PEs) are replicated in space, while data is being partitioned and
distributed to these PEs in parallel. In temporal parallelism, processing
tasks that have dependency among each other are mapped onto pipelined PEs in
series, while each PE in the pipeline can take data with different timestamps
in parallel. FPGAs can construct both types of parallelism using their
abundant computing resources and pipeline registers [11]. This unique feature
makes FPGAs suitable for accelerating algorithms with a high degree of both
data concurrency and dependency. Therefore, FPGAs keep the promise to
efficiently serve a wider range of IoT applications.

Third, FPGAs consume significantly lower power compared to CPUs and GPU [4]
for delivering the same throughput, allowing for improved thermal stability
and reduced cooling cost. This merit is critically needed for edge servers,
considering their limited form factors.

Figure 1: An Intel Fog Reference Design unit hosting two Nallatech 385A FPGA
Acceleration Cards.

##  3 Methodology

To confirm and quantify the aforementioned benefits of FPGA-based edge
computing, we designed and conducted three sets of experiments to evaluate
FPGAs vs. GPUs from the perspectives of (1) performance sensitivity to
workload size, (2) adaptiveness to algorithm concurrency and dependency
degrees, and (3) energy efficiency.

All the GPU-related experiments were conducted on a server node equipped with
a Nvidia Tesla K40m GPU, dual Intel Xeon E5-2637 v4 CPUs, and 64GB of main
memory. All the FPGA-related experiments were conducted on an Intel Fog
Reference Design unit [9] (see Figure 1) equipped with two Nallatech 385A FPGA
Acceleration Cards (Intel Arria 10 GX1150 FPGA), an Intel Xeon E5-1275 v5 CPU,
and 32GB of main memory. The OpenCL kernels for FPGAs were compiled using
Intel FPGA SDK for OpenCL (version 16.0) with Nallatech p385a_sch_ax115 board
support packages (BSP). The GPU OpenCL kernels were compiled at runtime using
available OpenCL library in CUDA Toolkit 8.0. Results discussed in the next
section will show that the FPGA substantially outperforms the GPU in several
important aspects, despite that the GPU has a much higher theoretical
throughput (4.29TFlops) than the FPGA (1.5TFlops).

##  4 Experiment Results

Figure 2: Multi-stage matrix multiplication on (a) a GPU and (b) an FPGA.

###  4.1 Sensitivity to Workload Size

The purpose of this experiment is to demonstrate the sensitivity of FPGA and
GPU to workload size. IoT devices are usually latency sensitive and expect
predictable latency and throughput from edge servers. We used a two-stage
matrix multiplication ($A\times B\times C$) as the benchmark, to model edge
workloads. This operation is widely used in linear algebraic algorithms and is
generic enough for the purpose of this experiment. All three matrices are of
dimension 32x32 and contain single-precision floating-point random numbers.
Input matrices are provided as a batch, and the batch size represents the
workload size. We varied the batch size between 2 to 2048 in the experiment.
The processing throughput (number of matrices/ms) is defined as the ratio of
the workload size over the total runtime.

Figure 3: Sensitivity of matrix multiplication throughput (number of computed
matrices per millisecond) sensitivity to batch size (number of matrices
received per batch)

Figures 2a and 2b illustrate the difference of execution flow between the GPU
and the FPGA. To exploit spatial parallelism, the GPU must perform $A\times B$
for the entire batch and stores the intermediate results (I) in the global
memory. Once the writing of I is done, the subsequent I$\times$C can be
performed by reading I back from the global memory. Differently, the FPGA can
also exploit temporal parallelism and utilize dedicated pipes (channels) to
transfer the intermediate results from one stage to another without blocking
the execution. The execution of A$\times$B$\times$C is fully pipelined by the
streaming architecture implemented in the FPGA, such that the matrix samples
can flow in and out of the FPGA through I/O channels one after another without
waiting regardless of the batch size.

Figure 3 shows the throughput comparison between the GPU and the FPGA across
different batch sizes. It is shown that the FPGA can deliver a consistently
high throughput by jointly exploiting spatial and temporal parallelism.
Specifically, the FPGA outperforms the GPU for small batch sizes (up to 128)
in spite of its much lower operating frequency. In contrast, the GPU
performance varies largely according to the batch size. GPUs rely on
interleaving a large batch of input data to hide the device initialization and
data communication overheads. When dealing with small batch size, such
overheads will dominate total execution time and degrade the throughput
especially when the operations involved have some levels of dependency.
Overall, the experiment results imply that FPGAs not only are efficient in
handling aggregated service requests coming from individual devices in small
batch sizes but also can guarantee a consistently high throughput with a well-
bounded latency. Therefore, FPGAs are highly suitable for edge computing given
the considerable variance in workload size of various IoT applications.

###  4.2 Adaptiveness

To evaluate how well FPGAs and GPUs adapt to algorithm characteristics, we
designed benchmarks to capture two types of dependencies: data dependency,
which represents the dependency across different iterations of a loop, and
conditional dependency, which represents the dependency on conditional
statements with each iteration of the loop.

Our benchmark resembles an algorithm made of a simple iterative block (for-
loop) where each iteration performs certain number of operations. The
loop_length and ops variables define the total number of iterations and the
total number of operations per iteration (set to 262144 and 512 in the
experiment), respectively. All variables are single-precision in the
experiments. Note that the objective of our experiments is to reveal the
impact of architecture adaptiveness to algorithm characteristics rather than
evaluating the performance for a specific algorithm.

The benchmark captures data dependency by introducing dependency among
different iterations of the loop. When there is no data dependency, every
single iteration is considered as independent and all the iterations can
execute in parallel. With data dependency, the iterations that are dependent
on one another need to be executed sequentially as a group. Therefore, by
varying the data dependency degree, i.e., the average size of the groups, we
can control the data parallelism available in the algorithm using this
benchmark. GPU’s performance is closely tied to the available data
parallelism. In comparison, FPGA can exploit PEs in series and receive
iterations regardless of the dependency. Different iterations can co-exist and
be executed in the pipeline, while traversing down the connected PEs
concurrently.

To introduce conditional dependency, we add if-else statements into the
iterations of the loop in the benchmark. Half of the iterations are in the if
block and the other half are in the else block. Only the iterations that
follow the same branch path can be executed in a data parallel fashion. To
reveal the performance impact of conditional dependency, we vary the number of
operations in each if and else block, which affects the initialization
overhead and consequently the overall performance. GPU is highly sensitive to
conditional dependency, because it can parallelize only the iterations that
take the same path at one time. In comparison, FPGA can configure the hardware
to include all different execution paths, and use a simple lookup table to
direct every thread into the right pipeline and execute all threads at the
same time.

In order to get the best performance out of the FPGA and the GPU, the above
algorithms were deployed using two different methods. For the GPU, we designed
an equivalent OpenCL kernel and deployed it in the NDRange mode to accelerate
concurrent operations by exploiting spatial parallelism. For the FPGA, we
compiled the FPGA kernel in the single-threaded mode to accelerate dependent
operations by exploiting temporal parallelism, in which case loop execution is
initiated sequentially in a pipelined fashion.

Data Depndency. Figures 4a and 4b show the raw and the normalized throughput
(to system frequency $f_{clk}$) for both a low (16) and a high (256) data
dependecy, respectively. In general, computation throughput is linearly
proportional to both $f_{clk}$ and architectural parallelism. The normalized
throughput decouples $f_{clk}$ from the evaluation and measures the pure
impact of architecture parallelism on throughput. For the GPU, the base
frequency of the board is used as $f_{clk}$. For the FPGA, $f_{clk}$ is
extracted from the full compilation report. It is shown that the GPU
performance drops by 14 times from the low to the high data concurrency. As
data concurrency increases from 16 and 256, the available data parallelism
(the number of loop iterations that can be executed in parallel) for the GPU
drops from 16384 to 1024. It is the lack of temporal parallelism that make
GPUs hardly adaptive to such changes in concurrency and dependency degrees. On
the contrary, the FPGA delivers a stable throughput regardless of such
changes. This is because the hardware resources on an FPGA can be reconfigured
dynamically to compose either spatial or temporal parallelism
(interchangeable) at a fine granularity. As a result, FPGA outperforms GPU by
3.32 folds with the high data concurrency, and this gap is expected to grow as
the dependency degree further increases.

(a) Raw Throughput

(b) Normalized Throughput

Figure 4: Comparison of (a) raw and (b) normalized throughput at low and high
data dependency degrees.

Conditional Dependency Figure 5 shows the performance drop with respect to the
conditional dependency introduced by if-else statements, as the number of
operations if and else block from 8 to 1024. It shows that the FPGA
performance is relatively stable as the conditional dependency increases. For
some specific cases, the performance is even increased due to a higher clock
frequency compared to the baseline kernel. In contrast, the GPU experiences up
to 37.12 times performance drop, compared to baseline kernel with no
conditional statements. Branches from the conditional statements cause
different threads in a warp to follow different paths, creating instruction
replay and resulting in reduced throughput. Figure 5 also shows that having
fewer operations in the kernel causes more degradation for the GPU since a
smaller kernel requires less computation and incurs relatively higher
initialization and data transfer overhead.

Figure 5: Performance drop comparison for kernel with conditional statements.

###  4.3 Energy Efficiency

To evaluate energy efficiency, we measured the workload throughput divided by
its average power usage. To project energy efficiency, the power consumptions
of both devices are recorded for all of the experiments. We used the nvidia-
smi command-line utility and the Nallatech memory-mapped device layer API to
query the instant board-level power consumption every 500 milliseconds for the
GPU and FPGA, respectively. We then calculated the average power usage by
averaging all the power numbers recorded across five trials of each
experiment.

Figure 6a and 6b show the power consumption and energy efficiency comparison
for performing the matrix multiplication tasks mentioned in Section 4.1, for
different batch sizes. Running at a much lower frequency, the FPGA
consistently consumes 2.79–3.92 times lower power than the GPU. Taking into
account the performance, it shows that the FPGA can provide 2.6–30.7 times
higher energy efficiency than the GPU for executing matrix multiplication. The
improvement is prominent, especially for small batch sizes. The low power
consumption and the high energy efficiency of the FPGA imply that deploying
FPGAs for edge computing can potentially gain better thermal stability at
lower cooling cost and reduced energy bill.

Figure 6c depicts the energy efficiency comparison for running the workloads
with different dependency degrees (mentioned in Section 4.2). The results show
that the FPGA achieves a similar throughput to the GPU for executing the
kernels with a high data concurrency degree (low data dependency degree of
16). For the high-data-dependency (degree of 256) workload, the FPGA achieves
up to 11.8 times higher energy efficiency than the GPU. Such energy efficiency
improvement is expected to further increase as the dependency degree grows.
The experiment results indicate that the FPGA is almost on par with the GPU
regarding energy efficiency for executing high-concurrency algorithms, while
it can significantly outperform the GPU for executing high-dependency
algorithms.

(a)

(b)

(c)

Figure 6: The caparisons of (a) power consumption and (b) energy-efficiency
for the matrix multiplication tasks and (c) the data dependency benchmark.

##  5 Conclusions and Future work

In this paper, we studied three general requirements of IoT workloads on edge
computing architectures and demonstrated the suitability of FPGA accelerators
for edge servers. Our results confirm the superiority of FPGAs over GPUs with
respect to: (1) providing workload-insensitive throughput; (2) adaptiveness to
both spatial and temporal parallelism at fine granularity; and (3) better
energy efficiency and thermal stability. Based on our observations, we argue
that FPGAs should be considered a replacement or complementary solution for
current processors on edge servers.

Based on these results, we will further study FPGA-based edge computing along
the following possible directions. First, we aim to extend the study of
adaptiveness capabilities of both GPUs and FPGAs by considering other
important types of algorithm characteristics. Second, we plan to improve our
benchmarking kernels to reflect a wider variety of real-world algorithms.
Finally, we will also extend our energy-efficiency study for other types of
workloads and algorithm characteristics.

## References

  * [1] Chiang, M., and Zhang, T. Fog and IoT: An overview of research opportunities.  IEEE Internet of Things Journal 3, 6 (2016), 854–864.
  * [2] Cisco.  Cisco UCS C220.  https://www.optiodata.com/products/servers/cisco-unified-computing-system/ucs-rackmount/c220.
  * [3] Cisco.  Fog Computing and Internet of Things.  Tech. rep., Cisco, 2015.
  * [4] Fowers, J., Brown, G., Cooke, P., and Stitt, G. A performance and energy comparison of fpgas, gpus, and multicores for sliding-window applications.  In Proceedings of the ACM/SIGDA international symposium on Field Programmable Gate Arrays (2012), ACM, pp. 47–56.
  * [5] Gajski, D. D., Dutt, N. D., Wu, A. C., and Lin, S. Y. High—Level Synthesis: Introduction to Chip and System Design.  Springer Science & Business Media, 2012.
  * [6] HPE.  HPE Edge Line EL1000.  https://www.hpe.com/us/en/product-catalog/servers/edgeline-systems/pip.hpe-edgeline-el4000-converged-iot-system.1008670180.html.
  * [7] HPE).  HPE Edge Line EL4000.  https://www.hpe.com/us/en/product-catalog/servers/edgeline-systems/pip.hpe-edgeline-el1000-converged-iot-system.1008670396.html.
  * [8] HPE.  HPE GL10 IoT Gateway.  https://www.hpe.com/us/en/product-catalog/servers/edgeline-systems/pip.edgeline-systems.1008670386.html.
  * [9] Intel.  Fog Reference Unit.  https://www.intel.com/content/www/us/en/internet-of-things/fog-reference-design-overview.html.
  * [10] Intel, FPGA.  SDK for OpenCL, Programming guide (2017).
  * [11] Johnston, C., Gribbon, K., and Bailey, D. Implementing image processing algorithms on fpgas.  In Proceedings of the Eleventh Electronics New Zealand Conference, ENZCon’04 (2004), pp. 118–123.
  * [12] Khronos OpenCL Working Group.  The OpenCL Specification, 11 2012.  Rev. 19.
  * [13] Singh, D., and Engineer, S. P. Higher level programming abstractions for fpgas using opencl.  In Workshop on Design Methods and Tools for FPGA-Based Acceleration of Scientific Computing (2011).
  * [14] Winkler, T., and Rinner, B. Security and privacy protection in visual sensor networks: A survey.  ACM Computing Surveys (CSUR) 47, 1 (2014), 2.


#  FlexiRepair: Transparent Program Repair with Generic Patches

Anil Koyuncu, Tegawendé F. Bissyandé, Jacques Klein, Yves Le Traon
SnT, University of Luxembourg - Luxembourg

###### Abstract

Template-based program repair research is in need for a common ground to
express fix patterns in a standard and reusable manner. We propose to build on
the concept of generic patch (also known as semantic patch), which is widely
used in the Linux community to automate code evolution. We advocate that
generic patches could provide at the same time a unified representation and a
specification for fix patterns. Generic patches are indeed formally defined,
and there exists a robust, industry-adapted, and extensible engine that
processes generic patches to perform control-flow code matching and
automatically generates concretes patches based on the specified change
operations.

In this paper, we present the design and implementation of a repair framework,
FlexiRepair, that explores generic patches as the core concept. In particular,
we show how concretely generic patches can be inferred and applied in a
pipeline of Automated Program Repair (APR). With FlexiRepair, we address an
urgent challenge in the template-based APR community to separate
implementation details from actual scientific contributions by providing an
open, transparent and flexible repair pipeline on top of which all
advancements in terms of efficiency, efficacy and usability can be measured
and assessed rigorously. Furthermore, because the underlying tools and
concepts have already been accepted by a wide practitioner community, we
expect FlexiRepair’s adoption by industry to be facilitated. Preliminary
experiments with a prototype FlexiRepair on the IntroClass and CodeFlaws
benchmarks suggest that it already constitutes a solid baseline with
comparable performance to some of the state of the art.

###### Index Terms:

Generic Patch, Fix Pattern, Fix Template, Program Repair.

##  I Introduction

In the race for achieving the old software engineering dream of automating
program repair, approaches that leverage fix patterns currently have the lead
(in terms of how many benchmark bugs can be fixed) [1]. Unfortunately, despite
the excitement of this momentum in the research community, practitioners
expectations are not met and full integration in industrial settings remain
anecdotical. Initial experimental attempts to large-scale application of
automatic bug fixing suggest however that pattern-based patch generation fits
the current practice of software engineering: ❶ At Facebook, Getafix [2] and
SapFix [3] suggest fixes for in-house software by learning patterns using
“hierarchical clustering to many thousands of past code changes that human
engineers made, looking at both the change itself and also the context around
the code change”. ❷ In the Linux open source ecosystem, the Coccinelle [4]
code transformation engine, which builds on pattern-like specifications
written by developers, has been leveraged to automatically generate over 6 000
patches [5] that were accepted in the kernel code base. ❸ Besides repair,
Ubisoft designed Clever [6] to detect risky commits at commit-time using
patterns of programming mistakes from the code history.

Recently, Liu et al. [7] proposed to revisit the performance of automated
program repair (APR), carefully searching to identify the pattern databases
that were available in the literature. Their experience report suggests that
researchers do not actually share a common definition of what constitutes a
repair pattern: levels of abstraction vary significantly and their immediate
exploitation is often impossible as a transferable ingredient. Koyuncu et al.
[8] and Ueda et al. [9], in two independent works, pointed out that fix
patterns should be made tractable (i.e., they should be a clearly identifiable
artefact in the repair pipeline towards explaining the patch generation
decisions) and editable (i.e., APR users should be enabled to intervene to
correct these patterns manually to take into account project specificities).
On top of these concerns, the full APR pipeline generally suffers from a lack
of:

  * •

Practicality: A large body of the literature in APR present approaches that
target well curated benchmarks with several constraints (e.g., test cases are
readily available for the identified bugs) which may not be the case in
practice. Although recent works [10] have started to investigate the use of
bug reports, their pipelines remain heavily driven by test suites (e.g., for
validation).

  * •

Flexiblity: Regardless of the patch generation process (i.e., heuristic-based,
constraint-based, or template-based following the taxonomy proposed in [11]),
the available change transformations are generally limited to small mutations
operators which are tightly embedded in the proposed algorithms. Seldom, an
approach allows third party members in the community to readily edit and
extend the list of possible code transformations.

  * •

Transparency: The repair approaches suggest patch candidates from a search
space. However, in most of the case, the origins of the patch candidates,
i.e., how they are discovered, is missing. This intraceability remains a big
obstacle for the transparency.

Overall, we note that on the road to automated program repair, the
practitioner community is looking for techniques that can rapidly recommend
patches that may be manually validated by developers. Indeed, these appear to
be acceptable in various industrial settings so far. It may thus be worthwhile
to drain some research effort into building an automatic patch generation
system that is based on robust, agile and tractable techniques for inferring
code transformation strategies.

This paper. We present the core concept behind FlexiRepair, a flexible,
transparent and practical APR pipeline. We have initiated this FlexiRepair and
call for the community to commit on working on its building blocks for
delivering a reliable tool support for practitioners in the context of program
repair. FlexiRepair is built on top of well-accepted software maintenance
concepts in the Linux community, notably the concept of generic patch (more
known as semantic patch in recall for the specification language: the Semantic
Patch Language [12]). We use generic patch specification as the tractable
notation for fix patterns. The main contributions of our work are as follows:

  * •

We propose a critical review of template-based APR steps and suggest the
design of a patch generation system around the concept of generic patch whose
underlying definition and structure is borrowed from the Linux community
toolbox.

  * •

We initialize an open framework for program repair. The proposed pipeline,
FlexiRepair, transparently uses state of the art building blocks that can be
customized.

  * •

We evaluate the prototype pipeline, using available building blocks from the
literature. Performance is measured with $C$ program repair benchmarks.

##  II Related Work

Program repair at a glance. Patch generation is one of the key tasks in
software maintenance since it is time consuming and tedious. If this task is
automated, the cost and time of developers for maintenance will inevitably be
reduced in a dramatic manner. To address this issue, many automated techniques
have been proposed for program repair [11, 13]. Ultimately, program repair is
about traversing a search space of patch candidates that are generated by
applying change operators to the buggy program code. Depending on how a
technique conducts the search and constructs the patches, it can be considered
as heuristics-based [14, 15, 7, 16] or constraint-based [17, 18, 19] following
the taxonomy proposed by Le Goues et al. [11]. If such a technique further
leverages learning mechanisms to infer transformation patterns, or to build
patch models or to even predict patches, it is considered as learning-aided
[20, 21, 22].

In the last decade, most proposed techniques in the literature present repair
pipelines where patch candidates are generated then validated against a
program specification, generally a (weak) test suite. We refer to them as
generate-and-validate test-suite based repair approaches and focus FlexiRepair
framework under this practical repair scheme. The genetic programming-based
approach proposed by Weimer et al. [16], as well as follow-up works, appeared
only valid for hypothetical use cases. Nevertheless, in the last couple of
years, two independent reports have illustrated the use of literature
techniques in actual development flows: in the open source community, the
Repairnator project [23] has successfully demonstrated that automated repair
engines can be reliable: open source maintainers accepted and merged patches
which were suggested by an APR bot. At the premises of Facebook, the SapFix
repair system has been reported to be part of the continuous integration
pipeline [3] while Getafix was used there at large scale [24].

Given fault localization information that pinpoints the code locations in the
program that are the most likely to be buggy, test suite program repair
approaches apply syntactic transformations to generate patches. Early
techniques such as GenProg [25, 16] relied on simple mutation operators to
drive the genetic evolution of the code. More widespread today are approaches
that build on fix patterns [15] (also referred to as fix templates [26] or
program transformation schemas [27]) learned from existing patches. Several
APR systems [15, 28, 29, 26, 27, 8, 30, 31, 32, 33, 31, 7] implement this
strategy by using diverse sets of fix patterns obtained either via manual
generation or automatic mining of bug fix datasets. Unfortunately, whether
they are generated on-the-fly (e.g.. with SimFix [14] and CapGen [34]) or
stored in a database, fix patterns remain an elusive concept.

☞ In this work, our aim is to establish generic patches specified via the
Semantic patch language as the formal notation for abstracting and defining
fix patterns.

Fix patterns inference for program repair. While the literature includes a
large body of work on change patterns [35, 36, 37], and more generally on
change redundancies [38, 39, 40, 41, 42, 43, 44], very few approaches have
actually leveraged again their “discovered” patterns to instantiate repair
patches.

Nevertheless, specific bug patterns have been mined to build fixing engines:
Livshits and Zimmermann [45] discovered application-specific repair templates
by using association rule mining on two Java projects while Hanam et al. [46]
have developed the BugAID technique for discovering most prevalent repair
templates in JavaScript.

DevReplay [9] is a recent static analysis tool that suggests source code
changes based on a project’s git history. The proposed changes can be edited
by users without requiring knowledge about the AST.

FixMiner [8] is an automated approach to mining relevant and actionable fix
patterns based on an iterative clustering strategy applied to atomic changes
within patches. The goal of FixMiner is to infer separate and reusable fix
patterns that can be leveraged in other patch generation systems. This
approach provides an appealing building block in the context of the
FlexiRepair framework. Unfortunately, its patterns are also not immediately
actionable; they must be manually integrated into a repair engine, which
require a tedious an error-prone hard-coding of bug-fixing patterns.
Additionally, FixMiner patterns do not contain any code token information:
they have holes. The donor code should be searched before generating a
concrete patch, which may lead to various non-sensical patches. FixMiner
currently supports only Java and it does not provide any end-to-end
traceability (i.e. we do not know from where the pattern has been inferred).

☞ We borrow some ideas from the FixMiner approach for computing patch
similarity towards inferring patterns. In particular we find their rich AST
edit script to be appealing for building the prototype implementation of
FlexiRepair.

Generic patches in the literature. There have been some work addressing the
problem of considering a set of patches and attempting to find a “generic
patch” that summarizes the change that is common across the patches. Chawathe
et al. proposed a seminal method to detect changes to structured information
based on an ordered tree and its updated version [47]. The goal was to derive
a compact description of the changes with the notion of minimum cost edit
script which has been used in the recent ChangeDistiller and GumTree tools.
Spdiff [48, 49] was then a promising approach that considered inferred change
patterns from a set of patches. It was however found to scale poorly to a
large number of patches, and to have constraints in producing ready-to-use
patterns that can be used (e.g., by the Coccinelle matching and transformation
engine [12]). Recently, Serrano et al. [50] proposed Spinfer as a tool-
supported approach to ease large-scale changes across many source files in
Linux by suggesting transformation rules to developers, inferred automatically
from a collection of examples.

☞ Spinfer builds on the notation of “generic patch” (also referred to as
“semantic patch”), which Linux developers are already familiar with, thanks to
the wide adoption of the Coccinelle [4] transformation engine and the
associated Semantic Patch Language. We will rely on this building block for
the inference of fix patterns in the prototype version of FlexiRepair.

Figure 1: The FlexiRepair pipeline.

##  III The FlexiRepair Framework

FlexiRepair builds on the momentum of template-based program repair, which has
been shown successful in fixing a variety of bugs in APR benchmarks. To date
these approaches are among the most effective (in terms of the number of
benchmark bugs that are fixed) repair tools in the literature. Relevant
approaches in the literature (e.g., TBar [7], AVATAR [31], CapGen [34], SimFiX
[14]) are often provided in a monolithic tooling which prevents extension,
adaptation and even application on real-world code bases beyond those targeted
by initial experimental validations.

In this work, we propose to initiate a community-wide effort to build a
flexible, transparent and practical framework for template-based program
repair to (1) enable better assessment of research advancements, and (2)
facilitate adoption of APR by software maintainers.

FlexiRepair is carefully designed to ensuring that its users have control over
important steps of the patch generation process. In particular, we consider
the following critical questions:

❶ Where should we mine repair transformations? Template-based program repair
systems, whether they leverage specifically pre-defined mutation operators,
infer code transformations on-the-fly or rely on offline-inferred fix
patterns, they generally build on data of existing code bases (preferably with
a large history of code changes). If the source of mining is not appropriate
(e.g., limited recurrent changes or changes associated to domain-specific
bugs), the mined patterns may be irrelevant for the program that is targeted
for repair.

❷ How are fix patterns inferred? A challenge that has been highlighted in two
recent independent studies [8, 9] is that fix patterns discussed in the APR
community are largely intractable artefacts. If the underlying fix patterns
cannot be manipulated (i.e., checked and edited) by practitioners, the
adoption of the integrating APR tool will be largely hindered.

❸ How are patches generated? Besides fault localization information which
generally drives the selection of fix patterns, the application of code
transformations generally follows various ad-hoc recipes and involve empirical
design choices for fix pattern matching and donor code search. If these
activities cannot be ensured to be deterministic, industry adoption of APR
cannot be ensured.

###  III-A Execution steps of FlexiRepair

We propose to build an APR pipeline that addresses the issues raised in the
aforementioned questions. Figure 1 illustrates an overview of the FlexiRepair.

The pipeline takes the code repositories that the maintainer judge to be
relevant for learning code transformations as its input. This set of code
repositories can be constituted by the single source code repository
associated to the program under repair. Then, each of the questions formulated
above are addressed by a major component involved in a specific step of the
FlexiRepair pipeline :

  * •

Miner analyzes the structural similarity between input repository patches and
yields clusters that can be tuned by FlexiRepair users to take into account
the recurrence level of code transformations that will be supported by the
patch generation.

  * •

Inferrer then abstracts fix patterns from each retained cluster and specifies
it in a format that can be inspected (for relevance) and edited (to account
for specific maintenance style requirements).

  * •

Generator finally builds the concrete patches for the given buggy programs,
after attempting to match fix patterns to the appropriate code locations
(i.e., the likely buggy code locations).

Instead of re-inventing new algorithms and prototyping tools that would
require extensive vetting before adoption, we propose to bootstrap the
FlexiRepair pipeline by relying on tried-and-true technologies that software
maintenance are already familiar with. Concretely, we have identified a code
transformation tool that is part of the Linux kernel developer toolbox since
2008 and which is now increasingly used to automate large-scale changes in
kernel code. This tool, Coccinelle [4] builds on a concept of semantic patch
that allows developers to write transformation rules using a diff-like syntax.
In this work, we will use instead the term “generic patch” to refer to the
specification of transformation rules that can be given as input to
Coccinelle. A generic patch is thus an abstraction that uses metavariables to
represent common but unspecified subterms (e.g., any variable) and notation
for reasoning about control flow paths.

Given the standing of Linux development practices in the software development
community, the adoption of a tool such as Coccinelle, and its underlying
concepts, is a strong signal that it fits with industry standards. We
therefore propose to build the FlexiRepair pipeline on top of the Coccinelle
engine.

A fix pattern in FlexiRepair is a generic patch that is specified using the
specification language of Coccinelle, which is now integrated to the Linux
development toolbox.

###  III-B Overview of the SmPL Language

The Coccinelle tool is an example of public research effort that gained
traction in industrial settings, thanks to support from the open source
community. It was initially designed to document and automate collateral
evolutions [4] in the Linux kernel source code, but is now used in a variety
of other code bases as an base engine for performing control-flow-based
program searches and transformations in C code [5]. Coccinelle integrates a
static analysis that is specified using control-flow sensitive concrete syntax
matching rules. Search (i.e., identifying code fragments that match a pattern)
and transformations (i.e., generating patches following the fix pattern) are
specified via the Semantic Patch language (SmPL) language, and executed by a
dedicated transformation engine. Although the Linux community refers to the
SmPL specifications as ”semantic patches”, we will refer to them in
FlexiRepair as ”generic patches” to reflect the idea that they are abstract
patterns that must be ”concretized” into generated patches.

Although SmPL specifications can contain OCaml or Python code, allowing to
perform arbitrary computations, in this work we focus on its pattern matching
and code transformation capabilities. Listing 1 provides an example of generic
patch (as an SmPL specification). The patch goal is :

  * •

(1) to identify all code locations where there is an attempt to access a field
of struct whose pointer has not been safely checked beforehand in the control
flow. Indeed if the pointer ($param$) is NULL, the dereference would lead to a
segmentation fault (and a crash in the case of an operating system code).

  * •

(2) to produce a corrective patch (i.e., adding check and early return
statement) at all places where such an unsafe derefence can take place.

The generic patch is constituted of a single rule named “unsafe_dereference”
which defines five metavariables (lines 2-4): $T$ (type) which represents any
data type; $p$, which represents an arbitrary position in the source program;
$fn$ (function name), $param$ (parameter name) and $fld$ (data structure field
name), which represent arbitrary identifiers. Metavariables are bounded by
matching the code pattern against the source code. For example, the pattern
fragment on line 6 (fn(..., T *param, ...)) will cause fn to be bounded to the
name of a function in its definition, and cause $param$ to be bounded to any
pointer parameter name. The notation $@p$ binds the position metavariable $p$
to information about the position of the match of the preceding token. Once
bounded, a metavariable must maintain the same value within the current
control-flow path; thus, for example, the occurrences of param on lines 6-13
must all match the same expression. The fix pattern (lines 6-15) therefore
consists of essentially C code, mixed with a few operators to raise the level
of abstraction so that a single generic patch can apply to many code sites.

⬇

1@unsafe_dereference exists@

2type T;

3position p;

4identifier fn, param, fld;

5@@

6fn(.., T *param, ...){

7... when != param = new_val

8 when != param == NULL

9 when != param != NULL

10 when != IS_ERR(param)

11\+ if (param == NULL)

12\+ return

13 param->fld@p

14... when any

15}

Listing 1: Example of generic patch

####  III-B1 Sequences abstraction

The main abstraction operator provided by SmPL is ‘…’, representing a sequence
of terms. In line 6, ‘…’ represents the remaining parameters of a function
that appear before and after a given parameter is matched in the parameter
list; in line 7, ‘…’ represents the sequence of statements reachable from the
begin of the definition of a function along any control-flow path. By
default111This default behavior can also be explicitly stated using the
“forall” annotation, such a sequence is quantified over all paths (e.g., over
all branches of a conditional block), but the annotation “exists”, next to the
rule name, indicates that for this “unsafe_dereference” rule, the matching
should be done even for one path. It is also possible to restrict the kinds of
sequences that ‘…’ can match using the keyword when. Lines 9-12 use when to
indicate that there should be no reassignment of param nor any check on the
validity of the param pointer value before reaching the dereference that
consists in accessing a field fld in the corresponding data structure.

A SmPL rule only applies when it matches the code completely. Consider the
example of buggy code in Listing 2. The rule unsafe_dereference matches the
parameter of type struct person * on line 1 and the dereference on line 6 as
it exists a control-flow path where the validity of pers is not checked. The
metavariable fn (cf. Listing 1 )is bound to the identifier get_age, and the
metavariable param is bound to pers. The metavariable p is bound to various
information about the position of the dereference, such as the file name, line
number, character number (on the line).

⬇

1int get_age(int alive, struct person *pers, char *context){

2int age=0;

3if (alive == 1 && pers !=NULL)

4 age=pers->age_death - pers->age;

5else

6 age = pers->age;

7return age;

8}

Listing 2: Example of buggy code with an unsafe dereference

####  III-B2 Disjunctions and Nests

Besides the ‘…’, SmPL provides disjunctions, $(pat_{1}\;|\;...\;|\;pat_{n})$,
and nests, $<...\;pat\;...>$. A nest $<...\;pat\;...>$ in SmPL matches a
sequence of terms, like ‘…’. However, additionally, it can match zero or more
occurrences of pat within the matched sequence. Another form of nest exists
for matching one or more occurrences of pat. By analogy to the + operator of
regular expressions, this form is denoted $<+...\;pat\;...+>$.

The examples discussed above illustrate the abstraction power that generic
patches provide in the activity of propagating fixes. In the next section we
present the steps for:

  * •

Regrouping patches into clusters where bug fix code transformations are made
with similar patterns.

  * •

Automatically generating generic patches from clusters of patches in order to
populate the repair template databases.

  * •

Performing patch generation in practice given an identified buggy code
location (even at a coarse granularity)

###  III-C Patch clustering

The goal of the Miner is to perform patch clustering, i.e., to group together
the code changes that are representing a repeating code context and change
operations. In order to convey the full syntactic and semantic meaning of the
code change and to discover cluster of patches that are sharing a common
representation, we leverage the rich AST edit script representation proposed
by Koyuncu et al. [8].

¡richASTEditScript¿ $\rightarrow$ ¡node¿+

¡node¿ $\rightarrow$ ‘- - -’* ¡move¿ — ‘- - -’* ¡delete¿ — ‘- - -’* ¡insert¿ —
‘- - -’* ¡update¿

¡move¿ $\rightarrow$ ‘MOV’ ¡astNodeType¿ @@ ¡tokens¿ ‘@TO@’ ¡astNodeType¿ ‘@@’
¡tokens¿ ‘@AT@’

¡delete¿ $\rightarrow$ ‘DEL’ ¡astNodeType¿ ‘@@’ ¡tokens¿ ‘@AT@’

¡insert¿ $\rightarrow$ ‘INS’ ¡astNodeType¿ ‘@@’ ¡tokens¿ ‘@TO@’ ¡astNodeType¿
‘@@’ ¡tokens¿ ‘@AT@’

¡update¿ $\rightarrow$ ‘UPD’ ¡astNodeType¿ ‘@@’ ¡tokens¿ ‘@TO@’ ¡tokens¿
‘@AT@’

List of Grammars 1 Notation of rich AST edit script

A rich AST edit script, whose grammar is illustrated in Grammar 1, encodes the
information about the AST node types in a change diff tree, the repair actions
performed, the raw tokens involved as well as the parent-child relation among
the nodes. We consider only code context and change operation presentation
(cf. Figure 2 ) to detect similar changes and group them into clusters of
similar code changes. The objective of this step is to ensure that we can
reduce the noise in pattern inference, regrouping together patches that
perform similar changes actions, and potentially filtering out cases where the
redundancies of changes are limited.

⬇

1UPD expr_stmt

2\--- UPD expr

3\------ UPD call

4\--------- UPD name

5\--------- UPD argument_list

6\------------ DEL argument

7\--------------- DEL expr

8\------------------ DEL literal:string

Figure 2: An example code context and change operation presentation.

###  III-D Generic Patch Inference

The goal of the Inferrer is to derive generic patches from the clusters of
similar concrete patches that have been mined in the previous step. We build
on a recent work by Serrano et al. [50] which showed that it is possible to
automatically generate SmPL transformation rules by learning from examples.
The approach considers both similarity among code fragments and among control
flows associated to the changes to identify change patterns and specify
transformation rules.

In practice, the idea is to abstract over common changes across the examples,
incrementally extending a pattern until obtaining a rule that describes the
complete change, respecting both control-flow and data-flow relationships
between the fragments of the code. To that end, each patch in a cluster is
used to reconstitute the before- and after-change files, then the Inferrer
identifies sets of common removed or added terms across the examples, and
further generalizes these terms in each set into a pattern that matches all of
the terms in the set, and finally integrates these patterns into
transformation rules that respect both control-flow and data constraints
exhibited by the examples.

Figure 3 illustrates an example of inferred generic pattern. It encodes the
information of how to transform code, the locations of where the pattern is
inferred, as well as statistics on the recall (i.e., the percentage of
expected changes in the examples that are obtained by applying the inferred
generic patch), precision (i.e., the percentage of changes obtained by
applying the inferred generic patch that are identical to the expected changes
in the examples). We benefit in FlexiRepair from the SmPL-specified generic
patch notation which is close to C: it makes the patterns understandable to
the user and even allows the user to improve the script or adapt it to other
uses, hence contributing to transparent schema of program repair where
patterns are tractable.

⬇

1@@

2identifier I0;

3@@

4- char I0;

5+ int I0;

6// Infered from:
(MultiMarkdown-6/{prevFiles/prev_626381_73d644_Sources#libMultiMarkdown#aho-
corasick.c,revFiles/626381_73d644_Sources#libMultiMarkdown#aho-corasick.c}:
ac_trie_search)

7// Recall: 0.11, Precision: 1.00, Matching recall: 0.50

Figure 3: An example of generic patch.

###  III-E Code Transformation with Generic Patches

Given that we leverage the SmPL language to specify generic patches, code
transformation is provided for free by the Coccinelle search and
transformation engine. The engine takes as input a generic patch and a source
code file that it parses. Then it performs a control-flow matching to identify
code locations whose shape fit with the structure of the code structure
targeted by the generic patch. Taking the metavariables values bounded at each
matched code location, it then generates the necessary concrete patches. This
engine thus provides two essential advantages over existing generate-and-
validate repair pipelines:

  * •

(1) there is no need for a fine-grained bug localization engine. A coarse-
grained localizer that points to buggy files can be leveraged. Thus, even IR-
based bug localization tools which produce results at file level without
requiring test cases can be relevant (as advocated by recent work [10]).

  * •

(2) the search for donor code is facilitated by the use of metavariables in
the generic patch, allowing for the transformation engine to infer and track
tokens across the control-flow, and thus maximizing the chances of producing
sensical patches (i.e., patches that at least make the program compile).

##  IV Study Design

We now overview some details of our experimental validation. The objective in
this study is not to build a novel state of the art repair tool, but to rather
offer a new perspective into a framework for template-based program repair
with at its core the concept of generic patch for specifying fix patterns (aka
fix templates). Before presenting the results, we discuss the dataset of code
repositories that we build for mining similar patches and further inferring
generic patches. Then, we present the benchmarks used to assess the overall
performance of FlexiRepair as a our prototype implementation. Finally we
overview the implementation choices made for both the patch clustering and
pattern inference steps.

###  IV-A Subjects

FlexiRepair provides a flexible interface to its user, who can decide either
to use a specific code repository to mine the fix patterns, or to use the pre-
constructed fix pattern database shipped with the framework. To build this
database we needed to first collect a large set of the code repositories with
a long history of code changes.

The subjects that are included in our dataset are collected: i) by manual
identification of popular $C$ repositories from gihub, gitlab, savannah with a
large code history and ii) systematically by leveraging the build activities
in Travis CI. For the latter we refer to the data of Durieux et al [51], which
contains all the Travis CI jobs executed between 30 September 2018 and 22
January 2019 by 272 917 projects. From their dataset we identified 2 858 $C$
repositories. We further curates this dataset based on the repository
properties from github (i.e., commit count, watchers count, forks count etc.).
Eventually we select the repositories i) that are not forks, ii) having at
least 200 commits, iii) at least 10 watchers iv) and at least 10 forks. Our
dataset eventually includes 351 repositories. Table I lists some of the major
ones.

TABLE I: Some of selected repositories used in our study.

Systematic identification
---
repository | commitCount | watchers | forks
xqemu/xqemu | 68836 | 462 | 49
git/git | 59910 | 33398 | 19513
greenplum-db/gpdb | 56052 | 4073 | 1171
MonetDB/MonetDBLite-C | 54946 | 26 | 13
panda-re/panda | 54869 | 1640 | 393
Manual identification
repository | commitCount | source
linux | 949406 | git.kernel.org
freebsd | 271000 | github.com
FFmpeg | 98901 | github.com
cmake | 49611 | gitlab.kitware
gtk | 65679 | gitlab.gnome

###  IV-B Assessment Benchmarks

We selected the Introclass [52] and Codeflaws [53] datasets to empirically
assess FlexiRepair.

The Introclass dataset is a benchmark of small $C$ programs collected from
classroom assignments of students. It includes 998 defects, 778 of them being
associated with an instructor constructed black-box test suite and 845 being
associated with a white-box test suite created using KLEE [54] (a symbolic
execution tool that automatically generates tests).

Codeflaws benchmark consists of 3 902 defects collected from C programs
developed during programming contests. The benchmark is associated with two
sets of test-suites: i) a test suite given to repair tools for generating
repair ii) a held-out test suite for validating the correctness of patches.

Table II lists some statistics about the benchmarks.

TABLE II: Basic statistics of Benchmarks.

Benchmark | # of Defects | Size of Test Suite I | Size of Test Suite II | LOCs
---|---|---|---|---
Codeflaws | 3902 | 2-8 | 5-350 | 1-322
Introclass | 998 | 6-9 | 6-10 | 13-24

###  IV-C Implementation Choices

FlexiRepair aims for flexibility and extensibility such that practitioners may
tune parameters and adapt the framework to their requirements. We recall that
we have made the following parameter choices in the FlexiRepair:

  * •

Repository selection is made based on the C programs with a large commit
history and which are actively used.

  * •

Change size in a patch is limited to have at most 50 changed lines.

  * •

Patch spread is limited such that each patch contains at most 3 hunks.

  * •

Timeout for generic patch inference is set to 900 seconds for each patch
cluster.

##  V Assessment

We assess the prototype framework of FlexiRepair via performing experiments
that answer the following research questions.

###  V-A Research Questions

  1. RQ-1:

To what extent can the application of Miner and Inferrer produce generic
patches from the collected code repositories?

  2. RQ-2:

Where did FlexiRepair find relevant redundant changes to mine the generic
patches?

  3. RQ-3:

What is the repairability performance of FlexiRepair?

  4. RQ-4:

What is the efficiency performance of FlexiRepair?

##  VI Results

###  VI-A Generic Patch Inference Capability

We first assess the relevance of the patch clusters yielded by the Miner
component of FlexiRepair. Then, we look at the generic patches yielded by the
Inferrer implementation.

Miner Assessment. Performance of Miner is evaluated through the clusters that
it yields. The objective is to estimate whether it can find enough cases of
recurrent changes within patches collected from project repositories to form
clusters. A given patch cluster will contain all the patches having the
similar code change hunks. Table III overviews the statistics of clusters
yielded by Miner by taking as input the dataset of repositories presented in
Section IV. The implementation choices presented in Section IV are also
followed. Overall, $350\,676$ code hunks have been extracted. Among these
hunks, we noticed that $110\,949$ ($\sim$32%) are unique code hunk, and thus,
they cannot be part of a cluster. For the remaining $239\,727$ code hunks
($\sim$68%), there exists at least one other code hunk, among the $350\,676$
code hunks, which is identical. They can thus form clusters of more than one
patch. Overall, among these $239\,727$ code hunks, we identified $31\,310$
patch clusters (i.e, the code hunks of each patch of a cluster are identical).

TABLE III: Statistics on Patch Clusters .

Total # of | # unique | # hunks which can form a | # clusters
---|---|---|---
hunks | hunks | cluster of at least 2 patches |
$350\,676$ | $110\,949$ | $239\,727$ | $31\,310$

Figure 4 shows the size distribution of the patch clusters. A majority of
clusters, i.e., $16\,081$ ($\sim$51%), are formed by two recurrent code change
hunks only. Conversely, $2\,394$ (249+1 023+875+247, $\sim$7.6%) clusters
contain at least 10 recurrent code change hunks.

Figure 4: Distribution of the patch cluster sizes.

We further investigate how the cluster elements are spread across patches. To
that end, we follow the categorization proposed by Koyuncu et al. [8].

  * •

A vertical cluster is a cluster whose code change hunk is recurrent within a
single patch. Such clusters are generally formed when we have patches that
developers commit to perform a single type of change (e.g., change $kmalloc$
call to $kzalloc$ calls) across several code locations.

  * •

An horizontal cluster is a cluster whose code change hunk is recurrent across
several patches. Such clusters are formed when a code change (e.g., add a
missing NULL check) is implemented by different developers for different code
locations.

Table IV overviews the statistics of clusters yielded. Most of the clusters
(24 230) are horizontal clusters. This suggests that the same code changes are
often spread among different patches, any or all of which may be used to infer
the common generic patch. The vertical clusters can also be useful for
inferring generic patches: they represent large patches making the same
changes at once at several locations (e.g., collateral evolutions in Linux are
applied through vertical patches [4]).

TABLE IV: Statistics on Patch Clusters Spread

Vertical | Horizontal
---|---
# Clusters |  # Patch |  # Hunk |  # Clusters |  # Patch |  # Hunk
3178 | 3178 | 7565 | 24230 | 75691 | 75691

  * *

A generic patch can simultaneously be vertical (when it is associated to
several changes in hunks of the same patch) and horizontal (when it appears as
well within other patches).

RQ-1.1: Miner is practical. It is able to identify patch clusters (i.e.,
recurrent patch sets) of various sizes.

Inferrer Assessment. We assess the ability of Inferrer to analyses changes
within patch clusters and derive a generic patch (i.e., abstract the relevant
fix pattern and specify it with the SmPL notation). Our implementation uses
Spinfer as a backend for matching control-flow similarities. Preliminary
experiments revealed that the approach is sensitive to the noise among
patches. We expect our Miner step to have provided homogeneous patch clusters.

Table V overviews some statistics on the inferred generic patches. From the
$31\,310$ patch clusters obtained with Miner, Inferrer was able to
successfully yield a generic patch for $20\,467$ ($\sim$65%) clusters. The
remaining clusters ($\sim$35%) do not lead to any generic patch either because
of the timeout value of 900 seconds set for analysing each patch cluster, or
because they do not exhibit the necessary data or control-flow dependencies to
satisfy any inference. Note that the initial generic patch inferred from a
given cluster can contain several rules. We consider each transformation rule
as a generic patch on its own. Eventually, we are left with $68\,368$ atomic
generic patches (i.e., generic patches with a single transformation rule).

Note that in the middle column of Table V, we also report the number of code
hunks that have been used to infer the generic patches. Overall, $125\,483$
($\sim$52%) out of $239\,727$ code hunks contributed to a generic patch.

TABLE V: Inferred Generic Patch statistics.

# Patch Clusters |  # Code hunks |  # ”Atomic” Generic Patches
---|---|---
20 467 | 125 483 | 68 368

Table VI lists five of the most frequently observed generic patches in our
dataset. We further manually investigate these generic patches by checking the
corresponding commits in the repositories in order to understand the nature of
the changes described by the developers.

TABLE VI: Frequently observed generic patches.

Frequency | generic patch
---|---
⬇ @block_content_42_0@ identifier I4, I0; expression E1, E2, E3; @@ - struct
resource *I0; ... - I0 = platform_get_resource(E1, IORESOURCE_MEM, E2); -
E3->I4 = devm_ioremap_resource(&E1->dev, I0); + E3->I4 =
devm_platform_ioremap_resource(E1, E2);
⬇ @expr_stmt_4_32@ expression E0; @@ - return (E0); + return E0;
⬇ @block_content_12_25@ expression E0; @@ - free(E0); - E0 = NULL; +
FREE_AND_NULL(E0);
⬇ @block_content_18_3@ expression E2, E1, E0; @@ - memory_region_init_ram(E0,
NULL, E1, E2, &error_abort); - vmstate_register_ram_global(E0); +
memory_region_allocate_system_memory(E0, NULL, E1, E2);
⬇ @if_stmt_8_8@ binary operator B1 = {== ,&& }; expression E0, E2; @@ - if (E0
B1 E2) + if (E2 B1 E0) { ... }

We discover that two generic patches (generic patches #1 and #3 in Table VI)
have been generated from patches that were actually automatically generate to
automate some evolutions at large scale across Linux: the relevant commit logs
even mention the Coccinelle tool being used.

The second generic patch (id expr_stmt_4_32), is spread among 14 projects (as
we can see in the Frequency column of Table VI) and the associated commits are
often described with ”Fix coding style” (indeed, the generic patch simply
removes brackets). The generic patch block_content_18_3 is inferred from 3
different projects. This generic patch fixes a memory mapping issue. Finally,
the generic patch if_stmt_8_8 switches the order of the expressions in the
condition of the if statement, to alter the control flow. A corresponding
commit log summarizes this behaviour as ”Put CONFIG* first in if(). This may
fix build failures with EAC3 disabled and is more consistent”.

To conclude this RQ, we check from which repositories the generic patches have
been inferred. Table VII lists the Top-10 projects which contributed to the
pattern inference. We note that all of these projects have large code
histories. Overall, from the 351 repositories used to mine the clusters and
infer the generic patterns, 301 contributed to pattern inference. It is
possible that the remaining 50 projects do not contribute because of the
filtering constraints imposed in our implementation choices, or simply because
the do not contain enough recurrent code change context from we generic
patches can be inferred.

TABLE VII: Top-10 projects contributed to pattern inference.

projects | freebsd | linux | qemu | wireshark | FFmpeg
---|---|---|---|---|---
occurrences | 11812 | 11419 | 9997 | 9337 | 7187
projects | php-src | xqemu | vlc | panda | gtk
occurrences | 7090 | 6288 | 5249 | 4740 | 4325

RQ-1.2: Inferrer successfully yields generic patches for a large number of
clusters: some generic patches are summarized patterns of changes that spread
across several projects.

###  VI-B Generic Patch traceability

We investigate potential relationships between the distributions of code
change locations and the performance of pattern inference, in order to
estimate the adequate locations for optimizing the search of generic patches.

Generic patches are inferred from hunks in a cluster. Note that, in a cluster,
when the code context and change operation of several hunks are syntactically
identical we consider them as a single same hunk in this research question.
Figure 5 shows the distribution of the generic patches in terms the number of
hunks that were used to infer them. Overall, from the $68\,368$ inferred
generic patches, $40\,529$ ($\sim$60%) is inferred from a single hunk.

Figure 5: Distribution of the generic patches in hunks.

On the one hand, we recall that, Miner regroups patches that are similar in
terms of code context (AST), and repair action, but we do not consider the
similarity among tokens. On the other hand, our current implementation of
Inferrer 222which is based on the algorithm of Spinfer [50] considers also the
similarity of the tokens involved in the change to track a pattern: if the
tokens involved in the set of patches can be abstracted in a single
metavariable then a single transformation rule can be formed. Otherwise, the
generic patch will include multiple transformation rules, each including
specific tokens (e.g., specific method names). Figure 6 illustrates a concrete
example of such case. For both of the code examples, Miner produces the same
AST rich edit script (cf. representation in Fig. 2) leading them to be placed
in the same cluster. However, since they differ in terms of the tokens used
(different method names and different parameters), Inferrer creates two
distinct transformation rules.

⬇

1- scanf("%s", str);

2+ gets(str);

⬇

1- error_setg_errno("%s: stat failed", fname);

2+ error_setg_file_open(fname);

Figure 6: An example of patches sharing the same cluster but having distinct
generic patches .

Note that distributions of generic patches in terms of number of functions and
functions also follow the same long tail shape: for example, we observed that
$\sim$85% (=58 176 /68 368) of the patterns are inferred from a single
function. We postulate that the distribution of locations can be used as an
heuristics for prioritizing pattern selection in program (cf. RQ-4 for more
insights).

RQ-2: Generic patches present a long tail distribution in terms of the number
of code locations that were involved in their inference. FlexiRepair further
provides traceability links to diagnose the code changes set that share
similar transformations leading to a fix pattern.

###  VI-C Repairability

We assess whether the inferred generic patches can be used to automate
generation of patches for real bugs. More specifically, we perform two program
repair experiments by using the generic patches generated by Inferrer as the
main input ingredients. Introclass and Codeflaws are leveraged for
benchmarking.

Table VIII illustrates the comparative results in terms of numbers of
plausible patches (i.e., that make the program pass all the test cases) for
the black-box and white-box test suites. Among the selected 764 defects in
Introclass, FlexiRepair can generate plausible patches for 186 defects using
the black-box test suite and 261 plausible patches using the white-box test
suite. Overall, we generate plausible patches for 288 defects of Introclass
when both scenarios are combined. We compare the repair performance of
FlexiRepair against 3 state-of-the-art APR tools which have been evaluated.
With the white-box test suite, FlexiRepair ranks second in terms of number of
generated plausible patches, and third with the black-box scenario. It is
noteworthy that FlexiRepair fixes significantly more bugs than other APR tools
in some specific projects such as $checksum$, $grade$, and $syllables$.

TABLE VIII: Number of Introclass bugs fixed by APR tools.

| FlexiRepair | GenProg | TrpAutoRepair | AE
---|---|---|---|---
Project | WB | BB | WB | BB | WB | BB | WB | BB
checksum | 23 | 23 | 3 | 8 | 1 | 0 | 1 | 0
digits | 37 | 8 | 99 | 30 | 46 | 19 | 50 | 17
grade | 12 | 8 | 3 | 2 | 2 | 2 | 2 | 2
median | 44 | 27 | 63 | 108 | 36 | 93 | 16 | 58
smallest | 75 | 56 | 118 | 120 | 118 | 119 | 92 | 71
syllables | 70 | 64 | 6 | 19 | 9 | 14 | 5 | 11
Total | 261 | 186 | 292 | 287 | 212 | 247 | 166 | 159

† The data about GenProg [55], TrpAutoRepair [56] and AE [57] are extracted
from the experimental results reported by Le Goues et al. [52]

Table IX lists example generic patches relevant for fixing Introclass defects.
The first generic patch is an example of fix pattern that matches several
locations: it substitutes the $C$ standard library function scanf() with
gets(). According to documentation scanf() reads input until it encounters
whitespace, newline or End Of File (EOF), whereas gets() reads input until it
encounters newline or End Of File (EOF). We notice that _gets()_ does not stop
reading input when it encounters whitespace, but instead it takes whitespace
as a string, avoiding bugs. The other listed patterns are mostly related to
control logic (i.e., wrong operator usage, boundary checks etc.) in if and for
statements.

TABLE IX: Selected generic patches fixing Introclass defects.

pattern | #defects | pattern | #defects
---|---|---|---
⬇ @@ expression E0, E1; @@ - if (E0 || E1) - { ... - } | 14
⬇ @@ expression E3; expression E2; expression E1; expression E0; @@ - if (E0 < E1 && E2 > E3) + if (E0 <= E1 && E2 >= E3) { ... } | 10
⬇ @@ expression E2; expression E0; binary operator B1 = {< ,>= }; @@ - if (E0 B1 E2) + if (E0 > E2) { ... } | 6

TABLE X: Number of Codeflaws bugs fixed by APR tools.

| FlexiRepair | Angelix | Prophet | SPR | GenProg | CoCoNuT
---|---|---|---|---|---|---
Total | 20/83 | 318/591 | 301/839 | 283/783 | [255-369]/1423 | 423/716

† In each column, we provide $x/y$ numbers: $x$ is the number of correctly
fixed bugs; $y$ is the number of bugs for which a plausible patch is generated
by the APR tool. The data about Angelix [17], Prophet [22], SPR [58], GenProg
[55] are extracted from the experimental results reported by CoCoNuT [59].

Our second experiment is performed on the Codeflaws benchmark. For this
experiment, we limit the number of generic patches to Top-$10\,000$ based on
their frequency in code hunks. FlexiRepair can generate plausible patches for
83 defects using the test-suite I. 20 of those 83 defects have been validated
to be correctly fixed using the test-suite II. We compare the repair
performance of FlexiRepair against 5 state-of-the-art APR tools as illustrated
in Table X. There is an important performance gap between FlexiRepair and
other state-of-the-art APR tools. We postulate that the limitation on the
number of generic patches had a significant negative impact. Finding a good
balance between efficiency (i.e., the search space must not explode by
considering all possibilities) and effectiveness can be considered as an
engineering detail. We discuss this in the following research question.

RQ-3: Note that we do not seek to outperform existing APR tools with our
prototype implementation building on the generic patch specifications.
Instead, we propose baseline performance for future research in template-based
program repair that uses the proposed unified representation of fix patterns.
Nevertheless, we note that the baseline is competitive with some state of the
art on IntroClass benchmark.

###  VI-D Efficiency

We assess efficiency of repair in terms of Number of Patch Candidates (NPC)
generated before the first plausible patch is found. NPC represent the invalid
patches that an APR tool has consumed resources to test. NPC score has been
advocated as a less biased metric of performance compared to execution time
[1, 60, 61]. Our evaluation on the IntroClass benchmark distinguishes two
categories:

  1. 1.

Nonsensical patches are patches which cannot even make the patched buggy
program successfully compile [15, 62].

  2. 2.

In-plausible patches are patches which let the patched buggy program
successfully compile, but fail to pass some test cases in the available test
suite.

Figure 7 shows the distribution of the position of the first plausible patch
when considering all sensical patches (i.e., patches that let the program
compile). The median of the position for the black-box scenario is 23, and 31
for the white-box scenario. These represent NPC scores when considering only
in-plausible patches.

Figure 7: NPC of sensical patches.

Figure 8 shows the distribution of the position of the first plausible patch
counting all the patches, i.e., including nonsensical patches). We note that
the mean value of NPC in the black-box scenario is $41\,626$ and in the white-
box scenario $31\,587$. Such high values indicate that the baseline tool
applies first some generic patches that lead to nonsensical patches. Recall
that, we select generic patches to apply first based on their frequency in
code hunks in FlexiRepair. This result therefore suggests that other selection
strategies could improve the overall results, and are thus worth to be
explored extensively as future work.

Figure 8: NPC of all patches.

We investigate a first simple strategy of generic patch selection for repair
based on its recurrence in the mining dataset measured in terms of functions,
files, patches, projects whose hunks contributed to the pattern abstraction.
We experiment with all five cases and focus exclusively on white-box scenario.

Figure 9 shows the corresponding distribution NPCs excluding the nonsensical
patches. The strategy where the selection is driven by the frequencies of the
generic patches among the projects yields the best results: when we prioritize
generic patches inferred from a large number of projects, the NPC score is
lower.

Figure 9: NPC of sensical patches for various selection strategies .

Figure 10 illustrates the NPC considering all patches. Prioritizing generic
patches that have been inferred from a large number of projects or a large
number of files leads to a significant reduction of NPC by $\sim$48% (from 31
587 to 16 501 when ordered by projects) and $\sim$57% (from 31 587 to 13 645
when ordered by files).

Figure 10: NPC of all patches for various selection strategies.

RQ-4: We note that the efficiency of FlexiRepair could be improved by better
prioritizing generic patches. We show that because of the traceability in
pattern inference, we are able to leverage frequency information to improve
the efficiency score by halving the NPC.

##  VII Conclusion

We have presented FlexiRepair, an open framework for template-based program
repair where we build on the concept of generic patch to define a unified
representation/notation for specifying fix patterns (aka templates). We show
that generic patches are powerful for expressing fix patterns in a transparent
and flexible way. FlexiRepair thus offers means, with a baseline, to measure
and assess repair new contributions in template-based program repair (e.g.,
pattern inference, heuristics of candidate search, etc.). We evaluate the
repair performance of a prototype implementation on the IntroClass and
CodeFlaws benchmarks and we show that our baseline provides comparable
performance to the state of the art. We open source FlexiRepair’s code and
release all data of this study to facilitate replication and encourage further
research in this direction: https://github.com/FlexiRepair

## References

  * [1] K. Liu, S. Wang, A. Koyuncu, K. Kim, T. F. Bissyandé, D. Kim, P. Wu, J. Klein, X. Mao, and Y. L. Traon, “On the efficiency of test suite based program repair: A systematic assessment of 16 automated repair systems for java programs,” in _Proceedings of the 42nd International Conference on Software Engineering_. ACM, 2020, pp. 615–627.
  * [2] J. Bader, A. Scott, M. Pradel, and S. Chandra, “Getafix: Learning to fix bugs automatically,” _Proceedings of the ACM on Programming Languages_ , vol. 3, no. OOPSLA, pp. 1–27, 2019.
  * [3] A. Marginean, J. Bader, S. Chandra, M. Harman, Y. Jia, K. Mao, A. Mols, and A. Scott, “Sapfix: Automated end-to-end repair at scale,” in _2019 IEEE/ACM 41st International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP)_. IEEE, 2019, pp. 269–278.
  * [4] Y. Padioleau, J. Lawall, R. R. Hansen, and G. Muller, “Documenting and automating collateral evolutions in linux device drivers,” _Acm sigops operating systems review_ , vol. 42, no. 4, pp. 247–260, 2008.
  * [5] J. Lawall and G. Muller, “Coccinelle: 10 years of automated evolution in the linux kernel,” in _2018 USENIX Annual Technical Conference_ , 2018, pp. 601–614.
  * [6] M. Nayrolles and A. Hamou-Lhadj, “Clever: Combining code metrics with clone detection for just-in-time fault prevention and resolution in large industrial projects,” in _2018 IEEE/ACM 15th International Conference on Mining Software Repositories (MSR)_ , 2018, pp. 153–164.
  * [7] K. Liu, A. Koyuncu, D. Kim, and T. F. Bissyandé, “TBar: Revisiting template-based automated program repair,” in _Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis_. ACM, 2019, pp. 31–42.
  * [8] A. Koyuncu, K. Liu, T. F. Bissyandé, D. Kim, J. Klein, M. Monperrus, and Y. Le Traon, “Fixminer: Mining relevant fix patterns for automated program repair,” _Empirical Software Engineering_ , pp. 1–45, 2020.
  * [9] Y. Ueda, T. Ishio, A. Ihara, and K. Matsumoto, “Devreplay: Automatic repair with editable fix pattern,” _arXiv preprint arXiv:2005.11040_ , 2020.
  * [10] A. Koyuncu, K. Liu, T. F. Bissyandé, D. Kim, M. Monperrus, J. Klein, and Y. Le Traon, “iFixR: Bug report driven program repair,” in _Proceedings of the 27the ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. ACM, 2019.
  * [11] C. Le Goues, M. Pradel, and A. Roychoudhury, “Automated program repair,” _Commun. ACM_ , 2019.
  * [12] J. Brunel, D. Doligez, R. R. Hansen, J. L. Lawall, and G. Muller, “A Foundation for Flow-based Program Matching: Using Temporal Logic and Model Checking,” in _Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ , ser. POPL ’09. New York, NY, USA: ACM, 2009, pp. 114–126.
  * [13] M. Monperrus, “Automatic software repair: A bibliography,” _ACM Computing Surveys_ , vol. 51, no. 1, pp. 17:1–17:24, 2018.
  * [14] J. Jiang, Y. Xiong, H. Zhang, Q. Gao, and X. Chen, “Shaping program repair space with existing patches and similar code,” in _Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis_. ACM, 2018, pp. 298–309.
  * [15] D. Kim, J. Nam, J. Song, and S. Kim, “Automatic patch generation learned from human-written patches,” in _Proceedings of the 35th International Conference on Software Engineering_. IEEE, 2013, pp. 802–811.
  * [16] W. Weimer, T. Nguyen, C. Le Goues, and S. Forrest, “Automatically finding patches using genetic programming,” in _Proceedings of the 31st International Conference on Software Engineering, May 16-24,_. Vancouver, Canada: IEEE, 2009, pp. 364–374.
  * [17] S. Mechtaev, J. Yi, and A. Roychoudhury, “Angelix: Scalable multiline program patch synthesis via symbolic analysis,” in _Proceedings of the 38th International Conference on Software Engineering_. ACM, 2016, pp. 691–701.
  * [18] H. D. T. Nguyen, D. Qi, A. Roychoudhury, and S. Chandra, “Semfix: Program repair via semantic analysis,” in _Proceedings of the 35th International Conference on Software Engineering_. IEEE, 2013, pp. 772–781.
  * [19] Y. Xiong, J. Wang, R. Yan, J. Zhang, S. Han, G. Huang, and L. Zhang, “Precise condition synthesis for program repair,” in _Proceedings of the 39th IEEE/ACM International Conference on Software Engineering_. IEEE, 2017, pp. 416–426.
  * [20] R. Gupta, S. Pal, A. Kanade, and S. Shevade, “Deepfix: Fixing common c language errors by deep learning,” in _Proceedings of the 31st AAAI Conference on Artificial Intelligence_. AAAI, 2017, pp. 1345–1351.
  * [21] F. Long, P. Amidon, and M. Rinard, “Automatic inference of code transforms for patch generation,” in _Proceedings of the 11th Joint Meeting on Foundations of Software Engineering_. ACM, 2017, pp. 727–739.
  * [22] F. Long and M. Rinard, “Automatic patch generation by learning correct code,” in _Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ , vol. 51, no. 1. ACM, 2016, pp. 298–312.
  * [23] S. Urli, Z. Yu, L. Seinturier, and M. Monperrus, “How to design a program repair bot?: insights from the repairnator project,” in _Proceedings of the 40th International Conference on Software Engineering: Software Engineering in Practice_. ACM, 2018, pp. 95–104.
  * [24] A. Scott, J. Bader, and S. Chandra, “Getafix: Learning to fix bugs automatically,” _arXiv preprint arXiv:1902.06111_ , 2019.
  * [25] C. Le Goues, T. Nguyen, S. Forrest, and W. Weimer, “Genprog: A generic method for automatic software repair,” _IEEE Trans. Software Eng._ , vol. 38, no. 1, pp. 54–72, 2012.
  * [26] X. Liu and H. Zhong, “Mining stackoverflow for program repair,” in _Proceedings of the 25th IEEE International Conference on Software Analysis, Evolution and Reengineering_. IEEE, 2018, pp. 118–129.
  * [27] J. Hua, M. Zhang, K. Wang, and S. Khurshid, “Towards practical program repair with on-demand candidate generation,” in _Proceedings of the 40th International Conference on Software Engineering_. ACM, 2018, pp. 12–23.
  * [28] R. K. Saha, Y. Lyu, H. Yoshida, and M. R. Prasad, “Elixir: Effective object-oriented program repair,” in _Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering_. IEEE, 2017, pp. 648–659.
  * [29] T. Durieux, B. Cornu, L. Seinturier, and M. Monperrus, “Dynamic patch generation for null pointer exceptions using metaprogramming,” in _Proceedings of the 24th International Conference on Software Analysis, Evolution and Reengineering_. IEEE, 2017, pp. 349–358.
  * [30] M. Martinez and M. Monperrus, “Ultra-large repair search space with automatically mined templates: the cardumen mode of astor,” in _International Symposium on Search Based Software Engineering_. Springer, 2018, pp. 65–86.
  * [31] K. Liu, A. Koyuncu, D. Kim, and T. F. Bissyandé, “Avatar: Fixing semantic bugs with fix patterns of static analysis violations,” in _Proceedings of the 26th IEEE International Conference on Software Analysis, Evolution and Reengineering_. IEEE, 2019, pp. 456–467.
  * [32] K. Liu, A. Koyuncu, T. F. Bissyandé, D. Kim, J. Klein, and Y. L. Traon, “You cannot fix what you cannot find! an investigation of fault localization bias in benchmarking automated program repair systems,” in _Proceedings of the 12th IEEE International Conference on Software Testing, Verification and Validation_. IEEE, 2019.
  * [33] K. Liu, D. Kim, T. F. Bissyandé, S. Yoo, and Y. Le Traon, “Mining fix patterns for findbugs violations,” _IEEE Transactions on Software Engineering_ , 2018.
  * [34] M. Wen, J. Chen, R. Wu, D. Hao, and S.-C. Cheung, “Context-aware patch generation for better automated program repair,” in _Proceedings of the 40th International Conference on Software Engineering_. ACM, 2018, pp. 1–11.
  * [35] B. Fluri, E. Giger, and H. C. Gall, “Discovering patterns of change types,” in _Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering_. L’Aquila, Italy: IEEE, 2008, pp. 463–466.
  * [36] M. Martinez and M. Monperrus, “Mining software repair models for reasoning on the search space of automated program fixing,” _Empirical Software Engineering_ , vol. 20, no. 1, pp. 176–205, 2015.
  * [37] B. Fluri and H. C. Gall, “Classifying change types for qualifying change couplings,” in _Program Comprehension, 2006. ICPC 2006. 14th IEEE International Conference on_. IEEE, 2006, pp. 35–45.
  * [38] K. Pan, S. Kim, and E. J. Whitehead, “Toward an understanding of bug fix patterns,” _Empirical Software Engineering_ , vol. 14, no. 3, pp. 286–315, 2009.
  * [39] M. Kim and D. Notkin, “Discovering and representing systematic code changes,” in _Proceedings of the 31st International Conference on Software Engineering_. IEEE Computer Society, 2009, pp. 309–319.
  * [40] S. Kim, K. Pan, and E. Whitehead Jr, “Memories of bug fixes,” in _Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering_. ACM, 2006, pp. 35–45.
  * [41] T. Molderez, R. Stevens, and C. De Roover, “Mining change histories for unknown systematic edits,” in _Proceedings of the 14th International Conference on Mining Software Repositories_. IEEE Press, 2017, pp. 248–256.
  * [42] R. Yue, N. Meng, and Q. Wang, “A characterization study of repeated bug fixes,” in _Software Maintenance and Evolution (ICSME), 2017 IEEE International Conference on_. IEEE, 2017, pp. 422–432.
  * [43] T. T. Nguyen, H. A. Nguyen, N. H. Pham, J. Al-Kofahi, and T. N. Nguyen, “Recurring bug fixes in object-oriented programs,” in _Software Engineering, 2010 ACM/IEEE 32nd International Conference on_ , vol. 1. IEEE, 2010, pp. 315–324.
  * [44] K. Liu, D. Kim, A. Koyuncu, L. Li, T. F. Bissyandé, and Y. Le Traon, “A closer look at real-world patches,” in _2018 IEEE International Conference on Software Maintenance and Evolution (ICSME)_. IEEE, 2018, pp. 275–286.
  * [45] B. Livshits and T. Zimmermann, “DynaMine: Finding Common Error Patterns by Mining Software Revision Histories,” in _Proceedings of the 10th European Software Engineering Conference Held Jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering_ , ser. ESEC/FSE-13. New York, NY, USA: ACM, 2005, pp. 296–305.
  * [46] Q. Hanam, F. S. d. M. Brito, and A. Mesbah, “Discovering bug patterns in javascript,” in _Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering_. ACM, 2016, pp. 144–156.
  * [47] S. S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J. Widom, “Change Detection in Hierarchically Structured Information,” in _Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data_ , ser. SIGMOD ’96. New York, NY, USA: ACM, 1996, pp. 493–504.
  * [48] J. Andersen and J. L. Lawall, “Generic patch inference,” _Automated software engineering_ , vol. 17, no. 2, pp. 119–148, 2010.
  * [49] J. Andersen, A. C. Nguyen, D. Lo, J. L. Lawall, and S.-C. Khoo, “Semantic patch inference,” in _Automated Software Engineering (ASE), 2012 Proceedings of the 27th IEEE/ACM International Conference on_. IEEE, 2012, pp. 382–385.
  * [50] L. Serrano, V.-A. Nguyen, F. Thung, L. Jiang, D. Lo, J. Lawall, and G. Muller, “SPINFER: Inferring semantic patches for the linux kernel,” in _2020 USENIX Annual Technical Conference (USENIX ATC 20)_. USENIX Association, Jul. 2020, pp. 235–248. [Online]. Available: https://www.usenix.org/conference/atc20/presentation/serrano
  * [51] T. Durieux, R. Abreu, M. Monperrus, T. F. Bissyandé, and L. Cruz, “An analysis of 35+ million jobs of travis ci,” in _2019 IEEE International Conference on Software Maintenance and Evolution (ICSME)_. IEEE, 2019, pp. 291–295.
  * [52] C. Le Goues, N. Holtschulte, E. K. Smith, Y. Brun, P. Devanbu, S. Forrest, and W. Weimer, “The manybugs and introclass benchmarks for automated repair of c programs,” _IEEE Transactions on Software Engineering_ , vol. 41, no. 12, pp. 1236–1256, 2015.
  * [53] S. H. Tan, J. Yi, S. Mechtaev, A. Roychoudhury _et al._ , “Codeflaws: a programming competition benchmark for evaluating automated program repair tools,” in _Proceedings of the 39th International Conference on Software Engineering Companion_. IEEE Press, 2017, pp. 180–182.
  * [54] C. Cadar, D. Dunbar, D. R. Engler _et al._ , “Klee: unassisted and automatic generation of high-coverage tests for complex systems programs.” in _OSDI_ , vol. 8, 2008, pp. 209–224.
  * [55] C. Le Goues, T. Nguyen, S. Forrest, and W. Weimer, “Genprog: A generic method for automatic software repair,” _Ieee transactions on software engineering_ , vol. 38, no. 1, pp. 54–72, 2011.
  * [56] Y. Qi, X. Mao, and Y. Lei, “Efficient automated program repair through fault-recorded testing prioritization,” in _2013 IEEE International Conference on Software Maintenance_. IEEE, 2013, pp. 180–189.
  * [57] W. Weimer, Z. P. Fry, and S. Forrest, “Leveraging program equivalence for adaptive program repair: Models and first results,” in _Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering_. IEEE, 2013, pp. 356–366.
  * [58] F. Long and M. Rinard, “Staged program repair with condition synthesis,” in _Proceedings of the 10th Joint Meeting on Foundations of Software Engineering_. ACM, 2015, pp. 166–178.
  * [59] T. Lutellier, H. V. Pham, L. Pang, Y. Li, M. Wei, and L. Tan, “Coconut: combining context-aware neural translation models using ensemble for program repair,” in _Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis_ , 2020, pp. 101–114.
  * [60] L. Chen, Y. Pei, and C. A. Furia, “Contract-based program repair without the contracts,” in _Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering_. IEEE, 2017, pp. 637–647.
  * [61] A. Ghanbari, S. Benton, and L. Zhang, “Practical program repair via bytecode mutation,” in _Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis_. ACM, 2019, pp. 19–30.
  * [62] M. Monperrus, “A critical review of automatic patch generation learned from human-written patches: essay on the problem statement and the evaluation of automatic software repair,” in _Proceedings of the 36th International Conference on Software Engineering_. ACM, 2014, pp. 234–242.