# A Survey on Automated Program Repair Techniques

Kai Huang<EMAIL_ADDRESS>Xidian UniversityXi’anChina ,  Zhengzi Xu
<EMAIL_ADDRESS>Nanyang Technological UniversitySingapore ,  Su Yang
<EMAIL_ADDRESS>University of Chinese Academy of SciencesBejingChina ,
Hongyu Sun<EMAIL_ADDRESS>Xidian UniversityXi’anChina ,  Xuejun Li
<EMAIL_ADDRESS>Xidian UniversityXi’anChina ,  Zheng Yan
<EMAIL_ADDRESS>Xidian UniversityXi’anChina Aalto UniversityEspooFinland
and  Yuqing Zhang<EMAIL_ADDRESS>University of Chinese Academy of
SciencesBeijingChina Xidian UniversityXi’anChina Hainan UniversityHaikouChina

(2022)

###### Abstract.

With the rapid development and large-scale popularity of program software,
modern society increasingly relies on software systems. However, the problems
exposed by software have also come to the fore. Software defect has become an
important factor troubling developers. In this context, Automated Program
Repair (APR) techniques have emerged, aiming to automatically fix software
defect problems and reduce manual debugging work. In particular, benefiting
from the advances in deep learning, numerous learning-based APR techniques
have emerged in recent years, which also bring new opportunities for APR
research. To give researchers a quick overview of APR techniques’ complete
development and future opportunities, we revisit the evolution of APR
techniques and discuss in depth the latest advances in APR research. In this
paper, the development of APR techniques is introduced in terms of four
different patch generation schemes: search-based, constraint-based, template-
based, and learning-based. Moreover, we propose a uniform set of criteria to
review and compare each APR tool, summarize the advantages and disadvantages
of APR techniques, and discuss the current state of APR development.
Furthermore, we introduce the research on the related technical areas of APR
that have also provided a strong motivation to advance APR development.
Finally, we analyze current challenges and future directions, especially
highlighting the critical opportunities that large language models bring to
APR research.

Automated program repair

This work was supported in part by the National Natural Science Foundation of
China under Grant 62072351; in part by the Academy of Finland under Grant
345072 and Grant 350464.

††copyright: acmcopyright††journalyear: 2022††doi: XXXXXXX.XXXXXXX††journal:
CSUR††journalvolume: 37††journalnumber: 4††article: 111††publicationmonth:
8††submissionid: CSUR-2022-0516††ccs: Software and its engineering Software
testing and debugging

##  1\. Introduction

The defects in software development, testing, and maintenance processes are a
widespread and costly category of serious problems in the software lifecycle,
making software engineers spend a lot of time fixing software defects to
ensure that the software works properly. Software defects have long caused
significant and persistent harm to various aspects of human activities. For
example, in 2017, attackers exploited the Eternal Blue series of
vulnerabilities to create a widespread WannaCry ransomware incident (Carly
Burdova, 2021). Between 2018 and 2020, software design flaws at Boeing caused
two Boeing 737 Max planes to crash and jeopardized a critical test flight of
the Starliner spacecraft (Morgan McFall-Johnsen, 2020). According to a recent
report by the Consortium for Information & Software Quality (CISQ) (Herb
Krasner, 2021), in 2020, the U.S. spent approximately $2.08 trillion due to
low-quality software, with software failures being the leading cause of the
Cost of Poor Software Quality (CPSQ) (approximately $1.56 trillion). Thus, the
defect problem has attracted much attention. Software defects are mostly
historical problems left over from the development process. Therefore, the
impact of software defects can only be mitigated by testing and patching,
which makes defect repair a tedious and complex task.

Nowadays, the creation and use of automation tools have become a trend in
industrial development. People use automation tools in industry and academia
to promote productivity and research. In this context, Automated Program
Repair (APR) (Monperrus, 2018; Gazzola et al., 2019; Goues et al., 2019)
techniques have emerged to shift the heavy manual software maintenance work to
precise and efficient automated repair work. Over the past decade, APR
techniques have developed rapidly and received much attention from
researchers. Many APR works have been done around this research area in
academia (Monperrus, 2022). APR techniques have a broad impact covering
software engineering (SE), system security (SS), and artificial intelligence
(AI). Besides, APR research is also accompanied by many related research
topics, such as APR evaluation (Liu et al., 2021b), fault localization (Wong
et al., 2016), patch assessment (Wang et al., 2020), etc. These related works
laid the foundation for the further development of APR. In recent years, APR
has also received attention from the industry. Companies such as Meta (Bader
et al., 2019; Marginean et al., 2019), Fujitsu (Saha et al., 2017, 2019; Noda
et al., 2020), and Alibaba (Lou et al., 2020; Zhang et al., 2020) are actively
exploring the deployment of APR techniques in real industrial environments.

As a hot research field, APR techniques have been reviewed by many scholars
(Monperrus, 2018; Gazzola et al., 2019; Goues et al., 2019). Today, APR
techniques are still evolving rapidly, with many data-driven APR efforts
emerging in recent years in particular. However, most prior surveys have not
yet covered these recent technical advances. Therefore, our work aims to
provide a more comprehensive survey to fill this gap. Furthermore, we hope to
revisit the development process of APR techniques to highlight the emerging
trends in the data-driven era of APR. Overall, unlike previous works, we focus
on the latest research advances, particularly the critical role of deep
learning in the APR field. Additionally, we propose a set of metrics to
present and compare the differences between APR tools uniformly in multiple
dimensions, which also reflects the continuous progress in the development of
APR techniques. More importantly, we provide insightful discussions on recent
APR techniques, highlighting potential problems and future technology trends.

Next, the main work and contributions of this paper are shown below.

  * •

Systematic taxonomy and review: We classify APR techniques into four
categories: search-based, constraint-based, template-based, and learning-
based. Importantly, we propose a uniform set of criteria to review and compare
APR tools at a fine-grained level (Section 4). Then, we systematically review
the development of APR techniques in time order (Section 5.1-5.4). Specially,
we review the learning-based techniques in terms of different defect problems
(i.e., bug, error, vulnerability), which were not covered in the previous
works.

  * •

Insightful summary and discussion: We summarize the advantages and
disadvantages of each type of repair solution (Section 5.5.1). More
importantly, we provide an in-depth discussion of advanced APR techniques
(Section 5.5.2). During the detailed discussion, we reveal many potential
problems, such as unfair comparisons of experiments, dataset overlap, and
dataset quality. Additionally, we analyze the latest technology trends, such
as the critical role of large language model (LLM) in future APR research,
exploring new paradigms of program repair, and focusing on both repair quality
and efficiency.

  * •

More forward-looking directional guidance: We analyze the latest research
progress and propose current pressing issues and forward-looking directions
(Section 7). In particular, we analyze the challenges of APR techniques for
industrial applications, and in addition, we highlight future research
opportunities for LLM and the necessity of more empirical studies. These were
also not covered in detail in previous surveys.

The remainder of this article is organized as follows. Section 2 describes the
criteria and process of selecting papers for this survey. Section 3 introduces
the background knowledge of APR techniques. Section 4 proposes a uniform set
of evaluation criteria for reviewing and comparing APR tools. Section 5
provides an all-around review of the development of APR and summarizes and
discusses the progress of APR techniques. Section 6 introduces related
research efforts on APR. Section 7 points out challenges and directions.
Section 8 concludes the whole paper.

##  2\. Paper Selection

Figure 1. The workflow for conducting paper selection.

This section describes the workflow (Fig. 1) for conducting paper selection.
Details are as follows.

Paper Collection. As this survey aims to revisit the development process of
APR techniques, we needed to search for papers covering all phases of APR
works. We would like to thank the APR community and Monperrus for their
comprehensive collection of APR works, which provided us with direct access to
relevant APR works. During the paper collection, we mainly focused on papers
published up to December 2022. According to the statistics provided by the APR
community111http://program-repair.org/, 405 APR papers were published between
2005 and 2022. In the living review by Monperrus (August 2022) (Monperrus,
2022), a total of 401 APR papers were included. Additionally, to follow recent
research progress, we searched articles from Google Scholar, DBLP, and arXiv
for the period of 2022.01-2022.12 using the keyword ”Automated/Automatic
Program Repair.” Finally, we aggregated and removed duplicates from the papers
retrieved by the APR community, Monperrus living review, and our own search,
forming the basis for this survey’s paper selection.

Paper Filtering. Due to page limitations, we cannot review all APR works in
detail, so we need to filter out some representative works for presentation.
In the filtering process, we first excluded short papers of no more than 6
pages, and then we manually reviewed the remaining papers to select a few
typical works. (Please note that the term ”typical works” here refers to those
that represent the characteristics of certain types of techniques in the
development of APR or reflect the development trend of APR techniques. Due to
page limitations and possible omissions from the manual review, it is
impossible to cover all typical works in our survey. However, since our goal
is to review the evolution of APR, it is sufficient to select some
representative works for presentation.) Furthermore, given that traditional
APR techniques have been reviewed in previous works (Monperrus, 2018; Gazzola
et al., 2019; Goues et al., 2019) and that our focus is on data-driven APR
techniques in recent years, we have retained more data-driven works in the
manual selection process. Ultimately, we primarily selected 140 APR works for
this paper, which will form the main part of our survey.

##  3\. APR General Process

The concepts of bug, error, fault, vulnerability, etc., are all referred to as
“defect” in a long study, so we will call them “defects” here for the sake of
unity. After defining the defect problem, the details of APR in the fixing
process still need to be thought about and analyzed. Most APR techniques use a
generic repair framework process (Liu et al., 2021b; Motwani, 2021; Liu et
al., 2020) (shown in Fig. 2): fault localization (FL), patch generation, and
patch validation. In the process of APR, a defective program is usually given,
which can be a piece of code, and then handed over to the APR tool for repair,
resulting in one or more patches. We briefly introduce the general repair
process of typical APR techniques:

Figure 2. APR general process.

Fault Localization: This step aims to find and locate defects in the program
so that the APR tool can make exact fixes. Researchers have developed many FL
tools or methods (Wong et al., 2016), and APR tools often draw on these off-
the-shelf FL techniques to locate potential fault locations.

Patch Generation: After obtaining the specific defect location, APR tools use
patch generation techniques to generate candidate fixes, where the “patch” can
be a program patch in the actual sense or a specific suggestion to guide the
fix.

Patch Validation: A large number of candidate fixes will be generated in the
patch generation stage, but not all candidate fixes can repair defects. Some
candidate fixes may be incorrect or invalid patches. The patch validation
phase aims to detect them (i.e., candidate patches) and find plausible patches
and correct patches (Saha et al., 2019).

Currently, FL techniques (Wong et al., 2016) are known as a separate research
area. While in APR techniques, patch generation and validation (G&V) are
usually the main focus of researchers. In particular, patch generation
techniques are at the core of the APR tool. In view of this, this paper will
adopt the techniques used in the patch generation phase to classify APR
research.

##  4\. Evaluation Criteria for APR Tools

In this section, we propose a uniform set of evaluation criteria for reviewing
and comparing different APR tools (see Table 1). This set of criteria reflects
APR tools in four dimensions: Approach Design, Repair Ability, Repair Quality,
and Repair Efficiency. These four dimensions contain 12 evaluation metrics,
which can reflect the similarities and differences between different APR tools
from different perspectives. It should be noted that the first two dimensions
(i.e., Approach Design and Repair Ability) analyze APR tools from a
qualitative perspective, and the last two dimensions (i.e., Repair Quality and
Repair Efficiency) analyze APR tools from a quantitative perspective. Since
this paper is a survey rather than an empirical study, we analyze the
comparison of APR tools only from a qualitative perspective. Our work is to
summarize these obvious features from the existing literature. In addition,
because APR tools often use different test benchmarks and few APR tools
explore repair efficiency, we are unable to provide a uniform view of these
quantitative metrics. As for the quantitative analysis, this should be done by
dedicated empirical studies. And they should conduct large-scale experiments
to reflect these data details. Also, these quantitative metrics provided in
this paper can provide an important reference for subsequent APR work.

Table 1. A uniform set of evaluation criteria on APR techniques

4 Dimensions | 12 Metrics
---|---
Approach Design. APR techniques aim to automate the resolution of software defects, and APR tools need to have the high level of automation to reduce human workload. The differences in the approach design of each APR tool reflect the degree of advancement in technical details. Therefore, we would like to reflect the superiority of APR tools at the technical level by showing the details of their approach design. Overall, we use three metrics to reflect the differences in the approach design. |  (1) Context-Aware (CA). This metric is used to indicate whether the APR tool employs the context-aware patch generation strategy. Specifically, approaches that are context-aware take into account the contextual information of the source code when generating fixes, which allows them to generate patches that work better with the original code and avoid introducing side effects. This results in higher repair success rate as well as higher repair quality.
(2) Fault Localization (FL). This metric is used to indicate whether the APR
tool is specifically designed and implemented with the FL function. Because
some APR tools integrate FL in their design process, they are specifically
designed or improved for FL, which allows the repair process to be free from
dependency on external FL tools. On the other hand, many APR tools focus only
on the patch G&V process, and they tend to use existing FL tools or directly
use the assumption of perfect fault localization, which makes it difficult for
them to effectively link localization and repair closely. The quality of FL
will also affect the quality of the final fix. Therefore, we use whether the
APR tool integrates a specialized FL function as a factor to reflect
differences in approach design.
(3) Empirical Knowledge (EK). This metric is used to indicate whether the APR
tool is able to automate the acquisition (learning) of empirical knowledge for
defect repair. For traditional heuristics, such as GP-based APR tools that
generate patch spaces by means of mutations, etc., such methods do not
inherently learn the empirical knowledge used for defect repair. Constraint-
based or template-based APR tools may need to manually define a set of
constraint rules or repair templates, which are the empirical knowledge to
guide defect repair. The manual extraction of the empirical knowledge still
means that the tool does not have the ability to automate learning. Other
tools, such as learning-based data-driven APR tools, can automate the learning
of empirical knowledge from a large number of repair samples, which means that
they can continuously enhance the repair potential through automated learning.
Repair Ability. The repair ability of an APR tool is used to indicate the size or applicability of the repair scope of the tool on defect repair problems. APR tools aim to solve defect problems of different types, languages, scales, etc. Different tools may target different repair goals at the beginning of their design, so their repair ability will vary. Here, we reflect the repair ability of APR tools in four aspects. |  (4) Multi-Type (MT) Fixes. This metric reflects whether the APR tool supports generic type (multi-type) defect repair. Some APR tools may be designed for specific defect type fixes, and they do not extend to a wider range of other types of defect fixing problems, so there is a limit to their repair ability. Some APR tools, on the other hand, can address multiple types of defects, or even most of the general defect types. For example, data-driven APR tools can solve a wider range of defects after learning about multiple types of defect fixes, so they have better scalability and generalizability.
(5) Multi-Language (ML) Fixes. This metric reflects whether the APR tool
supports multiple programming languages (PLs). Some APR tools work only on a
single programming language, and they cannot be extended to fix problems in
other languages. Thus, their repair ability is limited by the type of
language. On the other hand, some APR tools support fixes for multiple
programming languages. For example, most data-driven APR tools can be extended
to support multiple programming languages, which will further enhance the
overall repair ability of the tool. Note that since most APR techniques
(approaches) are language agnostic, their specific implementations (APR tools)
can be designed for different PLs. For example, the original implementation of
GenProg (Goues et al., 2012b) was evaluated on C, and its alternative
implementation, jGenProg (Martinez and Monperrus, 2016), supports Java
language. Therefore the multi-language (or multi-lingual) repair ability we
discuss here is explored only for specific APR tools.
(6) Multi-Hunk (MH) Fixes. Also called Multi-Line/Edit/Location/Statement
fixes (Saha et al., 2019; Li et al., 2022b; Mechtaev et al., 2016; Fu et al.,
2022; Chen et al., 2022). This metric reflects whether the APR tool can
resolve more complex multi-hunk defects. Different APR tools differ in their
repair ability. Some APR tools do not scale to large-scale program repair
problems; they only support simple single-line fixes, which limits their
repair ability in real-world environments. Some APR tools can fix more complex
multi-hunk bugs and even handle longer input sequences, which allows them to
scale to complex program repair problems and have greater repair ability.
(7) Multi-Fault (MF) Fixes. This metric reflects whether the APR tool can
effectively handle programs that contain multiple faults at the same time.
Since multiple faults may be contained in the same program at the same time
(Debroy and Wong, 2010), the occurrence of multiple faults may affect each
other, which makes it difficult for some APR tools to address such multiple-
fault program fixes problems. Therefore, APR tools that are well enough to
handle this class of more complex repair problems can be considered to have
stronger repair ability.
Repair Quality. A good APR tool should generate high-quality fixes, which can be understood in several ways. |  (8) Repair Reliability (RR). This metric reflects the likelihood of APR tools introducing new defects during the repair process. Since APR tools are highly susceptible to introducing new defects during the repair process (Assiri and Bieman, 2014), the quality of such a repair is a cause for concern. A high-quality fix should not only fix the current defect, but also avoid introducing new defects (Goues et al., 2012b). Therefore, we can evaluate the repair quality in terms of the number of new defects introduced during the repair process.
(9) Patch Acceptability (PA). (maintainability (Assiri and Bieman, 2014),
understandability (Monperrus, 2014), or interpretability). This metric
reflects the degree to which the patches generated by the APR tool are
accepted by developers (Kim et al., 2013). That is, whether the generated
patches are closer to the quality of human writing or are easily accepted by
developers. The literature (Assiri and Bieman, 2014) describes that program
repairs should resemble those done by humans, and therefore, repairs should
not reduce maintainability. If an APR tool generates a patch that is obscure
and overly complex and redundant, then the patch may have performance
differences from a human-written patch or even be difficult to integrate into
the original system. Instead, a high-quality patch should be more accessible
to developers, work with the entire development process, be easier to
maintain, and even make the generated fixes interpretable.
(10) Patch Effectiveness (PE). This metric reflects the degree to which APR
tools are effective in fixing defects. Currently, test case based APR tools
suffer from patch overfitting. These APR tools produce plausible patches
(patches that pass all test cases, but are not necessarily the correct
patches, and they may be completely ineffective at fixing defects). Developers
need to further sift through these plausible patches to get the correct ones
that actually work. Therefore, the higher the percentage of correct patches /
plausible patches generated by a high-quality APR tool, the more correct
patches are generated. We consider the patches generated by the APR tool to be
relatively high quality. For data-driven APR tools, they tend to evaluate
repair performance on large-scale datasets, which are usually not equipped
with complete test cases, so such tools can use repair accuracy to measure
their effectiveness.
Repair Efficiency. Automated repair should consider the repair cost issue. Here we divide the repair efficiency into time cost and money cost. |  (11) Time Cost (TC). This metric reflects the time cost spent by the APR tool to repair the defect (Goues et al., 2012b). A good APR tool should generate patches in a limited time. We believe that the shorter the time spent by an APR tool to fix a defect, the lower the time cost will be, i.e., the higher the repair efficiency.
(12) Money Cost (MC). This metric reflects the money cost spent by the APR
tool to repair the defect. We propose to deploy these APR tools under a
unified experimental environment to fairly compare the monetary cost behind
fixing defects with these APR tools, e.g., some works deploy APR tools in an
online cloud environment to evaluate the money cost spent on fixing defects
(Goues et al., 2012a; Weimer et al., 2013).

##  5\. APR Techniques Research Progress

Figure 3. A taxonomy of APR techniques.

We use the approach of the patch generation phase as the basis for APR
techniques taxonomy. We combine the latest APR research (Motwani, 2021; Chen
et al., 2021a; Benton et al., 2021; Liu et al., 2020) and classify APR
techniques into four categories: search-based, constraint-based, template-
based, and learning-based. We provide a taxonomy and overview of the
development process of the four types of APR techniques in Fig. 3. Here, we
analyze these APR works based on the qualitative perspective proposed in
Section 4, and Table 2 provides a uniform view to present the differences in
approach design and repair ability of different APR tools. Next, we will
review the development of four types of APR techniques in time order and
finally summarize the pros and cons of these techniques and discuss the
current state of APR development.

Table 2. A summary and comparison of different APR tools

|  | Approach Design | Repair Ability |  |  |  | Approach Design | Repair Ability
---|---|---|---|---|---|---|---|---
APR Tool | Year | CA | FL | EK | MT | ML | MH | MF |  | APR Tool | Year | CA | FL | EK | MT | ML | MH | MF
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
5.1 Search-based
5.1.1 Repair as a Game |  | MUT-APR (Assiri and Bieman, 2014) | 2014 | N.A. | N | N | N | N | N | N.A.
Jobstmann et al. (Jobstmann et al., 2005) | 2005 | N.A. | N.A. | N.A. | N | N | N.A. | N.A |  | CP (Sidiroglou-Douskos et al., 2015) | 2015 | N.A. | N | N | Y | N | N.A. | N.A.
Griesmayer et al. (Griesmayer et al., 2006) | 2006 | N.A. | N.A. | N.A. | N | N | N.A. | N.A. |  | ARJA (Yuan and Banzhaf, 2020a) | 2017 | N.A. | N | N | Y | N | Y | N.A.
5.1.2 Biological Engineering |  | ARJA-e (Yuan and Banzhaf, 2020b) | 2019 | Y | N | N | Y | N | Y | N.A.
Weimer et al. (Weimer et al., 2009) | 2009 | N.A. | Y | N | Y | N | N.A. | N.A. |  | CapGen (Wen et al., 2018) | 2018 | Y | N | N | Y | N | N | N.A.
Forrest et al. (Forrest et al., 2009) | 2009 | N.A. | Y | N | Y | N | N.A. | N.A. |  | CGenProg (Khalilian et al., 2021) | 2021 | N.A. | N | N | N | N | N.A. | N.A.
Weimer et al. (Weimer et al., 2010) | 2010 | N.A. | Y | N | Y | N | N.A. | N.A. |  |  5.1.3 Target Value Search
Fast et al. (Fast et al., 2010) | 2010 | N.A. | Y | N | Y | N | N.A. | N.A. |  | SPR (Long and Rinard, 2015) | 2015 | N.A. | Y | N | Y | N | N.A. | N.A.
Debroy et al. (Debroy and Wong, 2010) | 2010 | N.A. | N | N | Y | Y | N | N |  |  5.1.4 Code Similarity
Schulte et al. (Schulte et al., 2010) | 2010 | N.A. | N | N | Y | Y | N.A. | N.A. |  | SCRepair (Ji et al., 2016) | 2016 | N.A. | N | N | Y | N | N.A. | N.A.
Schulte et al. (Schulte et al., 2013) | 2013 | N.A. | Y | N | Y | Y | N.A. | N.A. |  | CRSearcher (Wang et al., 2017) | 2017 | N.A. | N | N | Y | N | N.A. | N.A.
GenProg (Goues et al., 2012b, c) | 2012 | N.A. | Y | N | Y | N | N.A. | N.A. |  | ssFix (Xin and Reiss, 2017) | 2017 | Y | N | N | Y | N | N.A. | N.A.
AE (Weimer et al., 2013) | 2013 | N.A. | N | N | Y | N | N.A. | N.A. |  | SimFix (Jiang et al., 2018) | 2018 | N.A. | N | N | Y | N | N.A. | N.A.
TrpAutoRepair (Qi et al., 2013) | 2013 | N.A. | N | N | Y | N | N.A. | N.A. |  | sharpFix (Xin and Reiss, 2019) | 2019 | Y | N | N | Y | N | N.A. | N.A.
RSRepair (Qi et al., 2014) | 2014 | N.A. | N | N | Y | N | N.A. | N.A. |  | VarFix (Wong et al., 2021) | 2021 | N.A. | N | N | Y | N | Y | N.A.
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
5.2 Constraint-based
5.2.1 Contract-based |  | Nopol (Xuan et al., 2017) | 2016 | N.A. | N | N | N | N | N | N
AutoFix-E (Wei et al., 2010) | 2010 | N.A. | N | N | N.A. | N | N.A. | N.A. |  | Angelix (Mechtaev et al., 2016) | 2016 | N.A. | N | N | Y | N | Y | N.A.
AutoFix-E2 (Pei et al., 2011) | 2011 | N.A. | N | N | N.A. | N | N.A. | N.A. |  | SOSRepair (Afzal et al., 2021) | 2019 | Y | N | N | Y | N | N.A. | N.A.
AutoFix (Pei et al., 2014) | 2014 | N.A. | N | N | Y | N | N.A. | N.A. |  |  5.2.3 Combination of Syntactic and Semantic Approaches
JAID (Chen et al., 2017, 2021c) | 2017 | N.A. | Y | N | Y | N | Y | N.A. |  | S3 (Le et al., 2017) | 2017 | N.A. | N | N | Y | N | Y | N.A.
5.2.2 Constraint Solvers |  |  5.2.4 New Formal Specifications
SemFix (Nguyen et al., 2013) | 2013 | N.A. | N | N | Y | N | N.A. | N.A. |  | FootPatch (van Tonder and Goues, 2018) | 2018 | N.A. | N | N | Y | Y | Y | N.A.
DirectFix (Mechtaev et al., 2015) | 2015 | N.A. | N.A. | N | Y | N | N.A. | N.A. |  | Maple (Nguyen et al., 2019) | 2019 | N.A. | Y | N | Y | N | N.A. | N.A.
SearchRepair (Ke et al., 2015) | 2015 | N.A. | N | N | Y | N | N.A. | N.A. |  | ExtractFix (Gao et al., 2021) | 2021 | N.A. | Y | N | Y | N | Y | N.A.
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
5.3 Template-based
5.3.1 Manually Extracted Templates |  | AVATAR (Liu et al., 2021a) | 2018 | N.A. | N | Y | Y | N | N.A. | N.A.
PAR (Kim et al., 2013) | 2013 | N.A. | N | N | Y | N | N.A. | N.A. |  | SOFix (Liu and Zhong, 2018) | 2018 | N.A. | N | N | N | N | N | N
relifix (Tan and Roychoudhury, 2015) | 2015 | N.A. | N | N | N | N | N.A. | N.A. |  | FixMiner (Koyuncu et al., 2020) | 2018 | Y | N | Y | Y | N | N.A. | N.A.
kPAR (Liu et al., 2019a) | 2018 | N.A. | N | N | Y | N | N.A. | N.A. |  | iFixR (Koyuncu et al., 2019) | 2019 | Y | N | N | Y | N | N.A. | N.A.
5.3.2 Automatically Mining Templates |  | Tbar (Liu et al., 2019c) | 2019 | Y | N | N | Y | N | N.A. | N.A.
HDRepair (Le et al., 2016b) | 2016 | N.A. | N | N | Y | N | N.A. | N.A. |  | HERCULES (Saha et al., 2019) | 2019 | Y | N | N | Y | N | Y | N.A.
Genesis (Le et al., 2016b) | 2017 | N.A. | Y | Y | Y | N | N.A. | N.A. |  | PraPR (Ghanbari et al., 2019) | 2019 | Y | N | N | Y | Y | N.A. | N.A.
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
5.4 Learning-based
5.4.2 Programming Error Repair |  | Review4Repair (Huq et al., 2022) | 2020 | Y | N | Y | Y | N.A. | N.A. | N.A.
Sk_p (Pu et al., 2016) | 2016 | N.A. | N.A. | Y | N.A. | N.A. | N.A. | N.A. |  | DLFix (Li et al., 2020) | 2020 | Y | N | Y | Y | N.A. | N.A. | N.A.
DeepFix (Gupta et al., 2017) | 2017 | N.A. | Y | Y | N.A. | N.A. | N.A. | Y |  | CoCoNut (Lutellier et al., 2020) | 2020 | Y | N | Y | Y | Y | N.A. | N.A.
SynFix (Bhatia et al., 2018) | 2018 | N.A. | N.A. | Y | N.A. | N.A. | N.A. | Y |  | Tang et al. (Tang et al., 2021) | 2021 | Y | N | Y | Y | N.A. | N.A. | N.A.
RLAssist (Gupta et al., 2019) | 2019 | N.A. | Y | Y | N.A. | N.A. | N.A. | Y |  | Recoder (Zhu et al., 2021) | 2021 | Y | N | Y | Y | N.A. | N.A. | N.A.
SampleFix (Hajipour et al., 2019) | 2019 | N.A. | Y | Y | N.A. | N.A. | N.A. | N.A. |  | CURE (Jiang et al., 2021) | 2021 | Y | N | Y | Y | N.A. | N.A. | N.A.
DrRepair (Yasunaga and Liang, 2020) | 2020 | N.A. | N.A. | Y | N.A. | Y | Y | Y |  | RewardRepair (Ye et al., 2022) | 2021 | Y | N | Y | Y | N.A. | N.A. | N.A.
BIFI (Yasunaga and Liang, 2021) | 2021 | N.A. | N.A. | Y | Y | Y | Y | Y |  | TFix (Berabi et al., 2021) | 2021 | Y | N | Y | Y | N.A. | N.A. | N.A.
RepairNet (Abhinav et al., 2021) | 2021 | N.A. | N.A. | Y | N.A. | N.A. | Y | N.A. |  | DEAE (Li et al., 2022b) | 2022 | Y | Y | Y | Y | N.A. | Y | N.A.
TransRepair (Li et al., 2022a) | 2022 | Y | Y | Y | Y | N.A. | Y | Y |  | AlphaRepair (Xia and Zhang, 2022) | 2022 | Y | N | N | Y | Y | N.A. | N.A.
RING (Joshi et al., 2022) | 2022 | N.A. | N.A. | Y | Y | Y | N.A. | N.A. |  | CIRCLE (Yuan et al., 2022) | 2022 | Y | N | Y | Y | Y | N.A. | N.A.
MMAPR (Zhang et al., 2022) | 2022 | N.A. | N.A. | Y | Y | N.A. | Y | Y |  | TRANSFER(Meng et al., 2022) | 2022 | Y | Y | Y | Y | N.A. | N.A. | N.A.
5.4.1 Software Bug Repair |  |  5.4.3 Security Vulnerability Repair
DeepRepair (White et al., 2019) | 2019 | N.A. | N | Y | Y | N.A. | N.A. | N |  | Vasic et al. (Vasic et al., 2019) | 2019 | N.A. | Y | Y | N | N.A. | N.A. | N.A.
Harer et al. (Harer et al., 2018) | 2019 | N.A. | N.A. | Y | Y | N.A. | N.A. | N.A. |  | SeqTrans (Chi et al., 2022) | 2021 | Y | N | Y | Y | N.A. | N.A. | N.A.
Tufano et al. (Tufano et al., 2019) | 2019 | Y | N | Y | Y | N.A. | N.A. | N.A. |  | VRepair (Chen et al., 2022) | 2021 | Y | N | Y | Y | N.A. | Y | N.A.
SequenceR (Chen et al., 2021a) | 2019 | Y | N | Y | Y | N.A. | N.A. | N.A. |  | VulRepair (Fu et al., 2022) | 2022 | Y | N | Y | Y | N.A. | Y | N.A.
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
| Y: Yes; N: No; N.A.: Not Available or Unknown; CA: Context Aware; FL: Fault
Localization; EK: Empirical Knowledge;
---
MT: Multi-Type; ML: Multi-Language; MH: Multi-Hunk; MF: Multi-Fault.

  * •

Note that the term ”APR Tool” refers to the specific implementation of the APR
technique in the experimental evaluation phase of the cited paper.

###  5.1. Search-based

Search-based methods are also known as heuristics solutions. The core idea of
search-based techniques is to search for the correct patch in a predefined
patch space. The techniques first look in the search space to identify the
most likely locations of buggy code in the program, usually with the help of
heuristics to generate candidate fixes, and then search for suitable fix
patches by means of mutation-selection, test execution, traversal strategies,
and etc. Heuristic methods emerged as early as 2005 (Jobstmann et al., 2005).
Later, the seminal GenProg (Goues et al., 2012b) used genetic programming (GP)
to generate program variants. The recent SimFix (Jiang et al., 2018) used
advanced code search for patch generation. Next, we will categorize and review
these APR works according to the search strategies used.

####  5.1.1. Repair as a Game

In early APR techniques, researchers proposed a heuristic approach to
automatically repair faults in a finite state program by treating the repair
problem as a game. Back in 2005, Jobstmann et al. (Jobstmann et al., 2005)
proposed a method for program repair as a game strategy, which consists of a
modified version of the program and an automaton representing a linear time
logic (LTL) specification. Each winning finite state strategy of the game
corresponds to a successful repair, and the opposite case represents a failure
strategy if the repair is unsuccessful. In 2006, Griesmayer et al. (Griesmayer
et al., 2006) extended the work (Jobstmann et al., 2005) by showing how to
find and repair errors in Boolean programs. This approach has been applied to
fix Windows device drivers by SLAM as an abstraction.

Early APR works treat repair as a game and explore the repair problem from a
novel perspective. But, they revealed shortcomings such as inefficient fixes,
limited types of fixes, and repetitive fixing behavior. Overall, early works
did not focus on the details of the approach design, and they have significant
limitations in repair ability. They do not support multi-type, multi-language
fixes, and it remains unclear whether they can address complex multi-hunk
fixes as well as multi-fault fixes.

####  5.1.2. Biological Engineering

In the history of APR techniques, bioengineering-based ideas have been widely
used in repair work, especially evolutionary computation (EC) (Schulte et al.,
2010) and genetic programming (Weimer et al., 2009; Koza, 1993). EC is a
guided stochastic search method that draws on the mechanisms and terminology
of biological evolutionary processes. GP is a learning algorithm inspired by
biological evolution that mimics the operations of variation and crossover in
biological evolution and selects the most suitable individual program for a
specific task by computing an adaptation function.

In 2012, the representative GP-based work GenProg (Goues et al., 2012b) was
born. GenProg uses a fine-grained abstract syntax tree (AST) level search.
Genetic operators were also localized to statements executed on failed test
cases, alleviating the problem of too large a search space making it difficult
to find the correct fix. In the final experiments, successful fixes were
achieved on 16 C programs and eight types of defects. In short, GenProg
supports multi-type fixes and has designed a weighted path-based FL scheme.
However, this APR tool does not support multi-language fixes, and it also does
not explore the multi-hunk fixes.

By 2014, GP has been widely used in APR (Weimer et al., 2009; Forrest et al.,
2009; Weimer et al., 2010; Fast et al., 2010; Debroy and Wong, 2010; Schulte
et al., 2010, 2013; Goues et al., 2012b, c; Weimer et al., 2013; Qi et al.,
2013). However, the search efficiency of GP methods is still a challenge. In
2014, Qi et al. (Qi et al., 2014) proposed RSRepair. RSRepair uses random
search and discards the failed test cases when it encounters them, which means
it executes fewer test cases to speed up the processing. Final results show
that RSRepair outperforms GenProg in repair effectiveness and efficiency.
Besides, RSRepair supports multi-type fixes. However, this APR tool does not
explore multi-language fixes and multi-hunk fixes, and it uses GenProg’s FL
scheme directly.

In addition to the GP and EC, in 2015, Stelios et al. (Sidiroglou-Douskos et
al., 2015) proposed an approach based on gene transfer - Code Phage (CP). CP
transfers the correct code from donor program to recipient program, thus
eliminating defects in the recipient program. However, it relies on the code
provider, which prevents code migration fixes if a defect lacks correct
representation in other systems. Final results show that it can fix multiple
types of faults but does not support multi-language fixes. It is also not
shown whether it can fix multi-hunk and multi-fault, and no FL scheme is
designed.

In 2017, Yuan et al. (Yuan and Banzhaf, 2020a) proposed ARJA. It improves the
effectiveness of GP repair by improving the search strategy. They viewed APR
as a multi-objective optimization problem, and developed the optimization in
terms of the size of patch-to-code changes and the number of patch tests.
Later, in 2019, they added the template-based idea (see Section 5.3) to ARJA
and proposed ARJA-e (Yuan and Banzhaf, 2020b). ARJA-e takes from PAR (Kim et
al., 2013) which extends seven templates, allowing ARJA-e to show greater
advantages than a single repair approach. Notably, they support multi-line
fixes and multi-type fixes, and ARJA-e employs a light-weight contextual
analysis strategy. However, they do not support multi-language and use
existing FL tools. It is unclear whether they can support multi-fault fixes.

In 2018, Wen et al. (Wen et al., 2018) proposed CapGen, the first context-
aware based patch generation technique. This technique makes it improve search
efficiency and repair quality. CapGen also supports multi-type fixes, but
cannot handle multi-hunk fixes and multi-language fixes. Moreover, it does not
focus on FL design, but directly uses off-the-shelf FL solutions. By 2020, Wen
et al. (Wen et al., 2020) proposed a new repair strategy by learning how bugs
are introduced (bug-inducing commits, BICs). By inferring from a large number
of variation operators and repair components needed to fix the bug, such an
approach outperforms CapGen. This suggests that incorporating bug-inducing
commits is an effective direction to facilitate APR research.

Finally, it should be added that none of the work reviewed in this section has
automated learning capabilities from the approach design perspective. They
cannot automatically learn the empirical knowledge to guide defect repair. In
addition, most works do not explicitly state whether they can support complex
multi-hunk and multi-fault fixes.

####  5.1.3. Target Value Search

In 2015, Long et al. (Long and Rinard, 2015) present the staged program repair
(SPR) strategy. SPR uses three key techniques: parameterized transformation
schemas, target value search, and conditional synthesis. According to these
three techniques, SPR can be classified into template-based, search-based, and
constraint-based, respectively. Since this section focus on the search
strategy, we discuss its target value search. In repairing, given a
parametrized transformation schema, SPR uses the target value search to
quickly determine if there are any parameter values that would allow the
schema to generate a successful fix. Unlike prior works (Goues et al., 2012b;
Weimer et al., 2013), which only reuse statements from the program, SPR
defines a novel set of modification operators that allow SPR to run on a
search space containing meaningful and useful fixes. The contribution of SPR
is the proposal of staged program repair to selectively perform space search,
thus improving the search efficiency. Notably, SPR presents its own FL
algorithm and supports multi-type fixes. However, it does not support multi-
language fixes, nor does it have automated learning capabilities. Its
experimental part does not state whether it supports multi-hunk and multi-
fault fixes.

####  5.1.4. Code Similarity

The code similarity-based (or redundancy-based (White et al., 2019))
techniques emerged to solve the search space problem (Xin and Reiss, 2019). By
reusing these codes, repair techniques can avoid generating a large amount of
code and thus reduce the search space. Among them, both syntactic (e.g., ssFix
(Xin and Reiss, 2017)) and semantic (e.g., SearchRepair (Ke et al., 2015))
search solutions were generated, and we will describe the semantic constraint-
based approach in Section 5.2. Then later, work has also emerged on reasoning
about code similarity through deep learning (e.g., DeepRepair (White et al.,
2019)), which will not be expanded here (see Section 5.4.1). Here, we focus on
heuristic syntactic search methods.

In 2016, Ji et al. (Ji et al., 2016) proposed SCRepair. They proposed a
reusability metric for similar code fragments used for program repair. By
combining similarity at the AST level, the reusability metric can help to
select the most suitable candidate fixes. This work laid the foundation for
later work. In 2017, Wang et al. (Wang et al., 2017) proposed CRSearcher.
CRSearcher uses the token-based code similarity calculation method. It
searches similar code from code repositories and recommends code snippets as
repair suggestions. Specifically, the experimental part of CRSearcher also
analyzes the repair efficiency. The results show that CRSearcher does help to
generate high-quality patches and reduce the repair time (about 50% of the
repair time cost savings). In short, both of the above works can repair
multiple types of defects but do not support multi-language fixes. It is not
clear whether multi-hunk and multi-fault fixes are supported. And they both
directly use existing FL strategies.

In 2017, Xin et al. (Xin and Reiss, 2017) proposed ssFix. Unlike the token-
based CRSearcher, ssFix identifies the bug statement and context as a code
block for similarity search. These improvements reduced search space and
generate high-quality fixes. In terms of repair ability, ssFix is consistent
with the previous SCRepair and CRSearcher. However, it considers code context
to guide code search and patch generation, so it is superior in approach
design.

Previous works help repair by relying on patch information or code
information. Specifically, some works (Kim et al., 2013; Long et al., 2017; Le
et al., 2016b) analyze existing patches to select those most likely
modifications to guide fixes; others (Goues et al., 2012b; Ke et al., 2015)
analyze source code to search for fix components used to generate patches
(more details can refer to (Jiang et al., 2018)). Combining the two may allow
exploring the search space more effectively. In 2018, Jiang et al. (Jiang et
al., 2018) proposed SimFix. They first mined a search space from the patch
information and explored the search space further with the help of code
similarity. Finally, SimFix presents a superior performance than ssFix (Xin
and Reiss, 2017). SimFix fixes 14 more errors than ssFix (Xin and Reiss,
2017). And in terms of repair ability, SimFix shows potential for multi-line
bug fixes. It also supports multi-type fixes but does not extend to multi-
language fixes. And it also does not declare whether it supports multi-fault
fixes. In terms of approach design, it directly uses the existing FL algorithm
and does not emphasize context-awareness.

In 2019, Xin et al. (Xin and Reiss, 2019) proposed sharpFix, which follows the
basic ideas of ssfix (Xin and Reiss, 2017) but with improvements in code
search and code reuse. It uses statement-level code blocks for local search
and method-level comparisons for global search. Besides, it uses token-level
matching compared to the inflexible approach of ssFix, which uses rule and
tree matching. Overall, sharpFix and ssFix are identical in approach design
and repair ability, but the improvements in sharpFix can fix more bugs.

In 2021, Wong et al. (Wong et al., 2021) used similarity information from
patch tests to speed up the search, and they applied variational execution to
propose an APR tool, VarFix. By observing which combinations of edit
operations pass the test, the combinations of edits that satisfy all the test-
passing conditions represent a reasonable patch. Experiments show that VarFix
can fix multi-line and multi-type bugs, and performs well in large-scale
programs. However, it does not support multi-language fixes and has not
explored multi-fault fixing capabilities. In terms of approach design, it
directly uses GenProg’s FL strategy and does not focus on context-aware
capabilities.

Finally, it should be added that while the work reviewed in this section draws
on existing knowledge bases (code bases) to guide the fixes, they do not
automate the learning of empirical knowledge used for defect fixes. They only
make use of this knowledge to help with the repair; the tools themselves do
not have the ability to learn the knowledge.

####  5.1.5. Summary

The search-based methods are an early class of APR techniques, among which
bioengineering ideas have had a profound impact. This class of methods
generates suitable candidate fixes by establishing search spaces and
developing search strategies. In the process, many researchers have proposed a
series of improvements to GP and how to establish efficient patch search
strategies. At the same time, these methods have also exposed some problems,
such as the explosive nature of the search space and the patch overfitting
problem (see Section 7.1.1). Besides, due to the uncertainty of mutation, the
validity of the patches generated is not guaranteed, and the generation of
invalid and incorrect patches will increase the system overhead. These limit
the quality and efficiency of APR. The core of the similarity information-
based approach is how to compute code similarity to find corresponding fixes.
And it has undergone a series of similarity elements in its development from
the token level only to code segment context information to patch information,
which inspired the later template-based (see Section 5.3) approach. It
exhibits a similar problem to the template approach in that if similarity
information cannot be found (no repair pattern can be found), no valid repair
can be generated. In summary, the heuristic search approach has been a great
impetus in the APR process, which has provided preliminaries for the
generation of other repair approaches.

###  5.2. Constraint-based

The core idea of constraint-based (or semantic constraint) approaches guides
the repair process by developing a set of constraint specifications. Such
techniques transform the program repair problem into a constraint solver
problem and use formal specifications to quickly prune infeasible parts to
find expression-level variations that satisfy constraints collected from tests
by program analysis, thus facilitating patch generation. For example, Nopol
(Xuan et al., 2017) and SemFix (Nguyen et al., 2013) use test cases as
implicit program specifications to guide the patch synthesis process. Next, we
will review these APR works according to different forms of constraints.

####  5.2.1. Contract-based

Between 2010 and 2014, the contract-based AutoFix project emerged (Wei et al.,
2010; Pei et al., 2011, 2014). Contracts provide a set of correct behavior
specifications. AutoFix project guides the FL and repair process by using
contracts. AutoFix-E (Wei et al., 2010) uses dynamic execution to build an
abstract model to guide the repair. AutoFix-E2 (Pei et al., 2011) adds static
analysis by analyzing the expressions in the program. AutoFix (Pei et al.,
2014) combines AutoFix-E and AutoFix-E2 to improve flexibility and generality.
Here we discuss the latest AutoFix, which not only combines static and dynamic
analysis to design FL strategy but also supports multi-type fixes. However, it
does not support multi-language fixes, and it is not clear whether it can fix
multi-hunk and multi-fault issues.

Although the contract-based technique has achieved effective fixes, it still
has limitations in flexibility. This method requires developers to write the
correct contract and only works on the Eiffel language. To address the
limitation, in 2017, Chen et al. (Chen et al., 2017, 2021c) proposed JAID.
JAID is able to construct abstract states from the source code, thus replacing
the original contract and supporting the Java. These improvements make JAID
more adaptable than the AutoFix project, eliminating the tedious manual
annotation of contracts and extending the scope of fixes to mainstream
programming languages. In addition, JAID shows the potential for multi-line
fixes compared to AutoFix. However, in terms of approach design, the contract-
based approach cannot automate learning to empirical knowledge and does not
focus on the context-aware patch generation strategy.

####  5.2.2. Constraint Solvers

Boolean satisfiability (SAT) is a problem of checking whether a propositional
logic formula can be evaluated as true. Satisfiability modulo theories (SMT)
generalize Boolean satisfiability. In these theories, SMT solvers are tools
used to determine whether formulas are satisfiable or not. This approach is
also used in APR techniques to perform program constraints.

There are some test-based (test-driven or test case driven) works that use
test cases to generate constraints. In 2013, Hoang et al. (Nguyen et al.,
2013) proposed SemFix to fix single-line bugs. They use symbolic execution to
generate repair constraints. In 2015, the team proposed DirectFix (Mechtaev et
al., 2015). DirectFix optimizes the patch generation process by using
constraint solving and component-based program synthesis. It has the ability
to fix multi-line bugs, but at the expense of some scalability. In 2016, they
proposed another work Angelix (Mechtaev et al., 2016). It uses a novel
lightweight constraint (i.e., angelic forest) that addresses the scalability
issue of DirectFix while retaining the multi-line bug fixing capability, which
allows for scaling to large programs. In general, the above works support
multi-type fixes, but they only work on C programs, and it is not clear if
they can support multi-fault fixes. They are also not concerned with context-
aware strategies in approach design. Note that DirectFix innovatively
integrates fault localization and repair into a single step to provide simple
fixes.

In 2016, Xuan et al. (Xuan et al., 2017) proposed Nopol for fixing if-
conditional bugs using SMT. Nopol builds on SemFix (Nguyen et al., 2013), they
are both test-driven solutions, but they have significant differences. Instead
of symbolic execution, Nopol uses value replacement. Crucially, Nopol shows
potential for large-scale program repair. Note that Nopol does not support
multi-type, multi-language, multi-hunk, and multi-fault fixes; it is designed
for specific bug types. In approach design, while Nopol is not concerned with
context-awareness, it uses value replacement to design the FL function.

Besides, the semantic code similarity scheme has also been widely used. In
2015, SearchRepair (Ke et al., 2015) encoded codebase data into SMT
constraints, and it uses constraint solving and semantic code search to find
potential fixes. It supports multi-type fixes but does not extend to multi-
language fixes, and it is not clear the ability on multi-hunk and multi-fault
fixes. In terms of approach design, it uses spectrum-based FL techniques. In
2019, SOSRepair (Afzal et al., 2021) performed semantic code search at a finer
granularity level and was ahead of prior work (Ke et al., 2015) in repair
effectiveness. Compared to SearchRepair, SOSRepair uses a context-aware patch
generation strategy and can apply it to large real-world programs.

####  5.2.3. Combination of Syntactic and Semantic Approaches

In the development of APR, both heuristic search and semantic constraint
methods have produced effective fixes for defects. Consequently, combining
these two types of approaches to facilitate fixes became a useful research
direction. In 2016, Le et al. (Le et al., 2016a) combined syntactic (GP) and
semantic (deductive verification) approaches. Later in 2017, they presented S3
(Le et al., 2017). It uses syntactic and semantic features to guide patch
generation, which helps generate high-quality patches and mitigate the patch
overfitting problem. S3 supports multi-type and multi-line fixes, but it only
focuses on Java bugs and does not explore multi-fault fixes. In 2021, Campos
et al. (Campos et al., 2021) implemented a VSCode extension pAPRika. It uses a
mutation-based solution (Debroy and Wong, 2010) and uses unit tests as
constraints to restrict these mutations. This work provides a new solution by
developing real-time IDE plug-ins that can quickly generate fixes.

####  5.2.4. New Formal Specifications

Prior works (Xuan et al., 2017; Nguyen et al., 2013; Mechtaev et al., 2015,
2016) used test cases to generate constraints to guide patch generation, and
this solution is known as the test-driven approach. But this approach can
produce overfitting patches and does not apply to bugs that are difficult to
test deterministically. To address this challenge, researchers have proposed
formal specifications to guide repair (Pei et al., 2014; Kneuss et al., 2015;
Logozzo and Ball, 2012; Rothenberg and Grumberg, 2016), which can be
contracts, behavioral specifications, deductive synthesis, etc. In recent
years, some new approaches to formal specification also attracted attention.

In 2018, Rijnard et al. (van Tonder and Goues, 2018) proposed FootPatch. It
uses Separation Logic (O’Hearn, 2019) to build formal specifications. The
significance of this work is that the use of static analysis techniques frees
APR from the constraints of test cases, making it possible to find more
potential defects and fix them. Note that FootPatch is designed to fix faults
related to general pointer safety properties, it supports multi-language and
multi-line fixes. But it is not clear whether it can fix multi-fault programs.
It is also not concerned with context-aware strategies and uses a existing
static analysis-based FL tool.

In 2019, Nguyen et al. (Nguyen et al., 2019) also followed the formal
specification and proposed Maple. It first generates template patches and then
generates constraints for these template fixes and performs constraint
solving. The addition of template-based ideas further improves repair
efficiency. In general, Maple supports multi-type fixes and has designed a
formal verification FL strategy. However, it does not support multi-language
fixes and is not applied in multi-hunk/fault fix scenarios.

In 2021, Gao et al. (Gao et al., 2021) applied constraint-based techniques to
C vulnerability repair by proposing the APR tool ExtractFix. Unlike bug fixing
tasks, vulnerability repair usually lacks complete test suites, so using test
cases to guide fault localization and constraint synthesis is challenging.
Based on this, ExtractFix uses execution information of vulnerability exploits
to synthesize constraints, alleviating the patch overfitting problem caused by
weak test cases. In addition, ExtractFix guides FL by combining control/data
dependency analysis, which provides an effective FL strategy for real fix
scenarios. In addition, it supports multi-hunk fixes, but it does not explore
multi-fault fixes.

####  5.2.5. Summary

Constraint-based approaches improve the repair quality (Mechtaev et al., 2016;
Le et al., 2017; Chen et al., 2017, 2021c; Afzal et al., 2021) by developing
constraint rules to transform the patch generation problem into a constraint
solving problem to reduce search space and generate a single or limited number
of candidate fixes. Through the review, we note that a lot of innovations have
been made in semantic works. Some works proposed syntactic-semantic
combination (Le et al., 2016a, 2017; Campos et al., 2021), some freed APR from
test cases by using formal specifications (van Tonder and Goues, 2018; Nguyen
et al., 2019; Gao et al., 2021), and some proposed real-time APR tools (Campos
et al., 2021). All of which were revolutionary in the APR process and opened
new research approaches. Compared with search-based heuristics, constraint-
based methods do not require extensive search and therefore have much lower
computational resources and costs and higher repair efficiency. However, such
methods rely heavily on the formulated specification constraints to guide the
program repair, so it lacks flexibility. In addition, constraint-based APR
tools still cannot automate the acquisition of empirical knowledge for
software defect repair.

###  5.3. Template-based

In the history of APR, heuristic search methods have developed mature
solutions, but they have huge search spaces that seriously affect the repair
efficiency and make it costly to fix defects. The method of semantic
constraints also suffers shortcomings, usually unable to establish a suitable
constraint specification for each type of bug, and the reliance on constraints
makes it exist many limitations. In order to alleviate these problems,
template-based APR techniques were born. Template-based methods utilize a
predefined program fix template (Kim et al., 2013) (also known as ”fix
pattern” (Liu et al., 2019b) or ”transformation schema” (Hua et al., 2018)) to
generate repair patches. The fix templates may be manually extracted (e.g.,
kPAR (Liu et al., 2019a)) or automatically mined (e.g., HDRepair (Le et al.,
2016b)). After FL, the template-based APR tool will target these defects to
select the corresponding fix templates to generate candidate patches. In a
recent empirical study (Liu et al., 2020), it was shown that template-based
repair tools are the most effective compared to search-based and constraint-
based schemes. Next, we will review these efforts according to different
template extraction schemes.

####  5.3.1. Manually Extracted Templates

In its early development history, templates were almost always summarized
manually. The method was explored by Kim’s team back in 2009 (Pan et al.,
2009). Later in 2013, they presented Pattern-based Automatic program Repair
(PAR) (Kim et al., 2013). They first examined patches in open-source projects,
and created ten repair templates. These templates are used as automatic
program editing scripts to guide specific repair operations. Experimental
results demonstrate that PAR can generate more acceptable patches than GenProg
(Goues et al., 2012b, c). This technique alleviates the problem that GP
solutions may generate nonsensical patches (Kim et al., 2013) and opens up a
new path for APR.

In 2015, Tan et al. (Tan and Roychoudhury, 2015) proposed relifix, a repair
tool using software change history to solve regression errors. They obtained a
set of code transformations from manual inspection of 73 real software
regressions. Here, this set of manually extracted code transformations can be
understood as templates for program repair. Unlike PAR’s approach of
extracting templates from patches, relifix’s templates (code transformations)
are syntax information extracted from program versions and test execution
histories. And they open the history-driven template-based approaches.

The above works are very similar regarding repair ability and solution design;
none of them support multi-language fixes, nor do they explore multi-hunk,
multi-fault repair capabilities. Moreover, relifix is only used to repair
specific defect types. These works use existing FL tools directly and do not
focus on context-aware patch generation strategies. Notably, these early works
relied on manual extraction of repair templates and were not equipped with
automated learning capabilities.

####  5.3.2. Automatically Mining Templates

To improve the efficiency of template generation, automated template mining
started to emerge. In 2016, HDRepair (Le et al., 2016b) used graph mining
techniques to automate the extraction of fix patterns from project histories.
The contribution of HDRepair is to pioneer automated pattern extraction. Note
that while HDRepair claims to fix multi-line bugs, it does not explore multi-
line repair ability.

By 2017, automated pattern generation had entered a phase of further
optimization. Increasing the number of template types will help to fix a
broader range of bug types. Long et al. (Long et al., 2017) proposed Genesis.
Compared to PAR (Kim et al., 2013), which used only ten manually refined
templates, Genesis inferred 108 code transformations from 577 sampled
transformations. In addition, Genesis has designed the FL algorithm and
supports multi-type fixes. However, it does not explore multi-hunk and multi-
fault fixes, nor does it focus on context-aware strategies. Meanwhile, pattern
mining has been explored in the work of Liu et al. (Liu et al., 2021a). They
proposed to use of convolutional neural network (CNN) to learn features and
combine X-means clustering algorithm to generate repair templates. The
significance of this work lies in the use of deep learning techniques to
advance the pattern mining process. Later, their work AVATAR (Liu et al.,
2019b) incorporates this approach into APR tools for automated repair.
Compared to Genesis, AVATAR uses existing FL tools. Although partially fixes
11 bugs that have multiple faulty code fragments, it does not discuss multi-
hunk fixes ability in depth.

In 2018, Koyuncu et al. (Koyuncu et al., 2020) proposed FixMiner, an automated
method for mining repair patterns, and implemented it in an APR tool,
PARFixMiner. It uses a context-aware patch generation strategy and supports
multi-type fixes. The tool does not focus on FL techniques and multi-language
fixes, and it is unclear if it can support multi-hunk and multi-fault fixes.
The method captures code changes and contextual information at the AST level.
Compared with previous works, FixMiner mines richer characterization
information, making PARFixMiner have better performance.

In 2019, Koyuncu et al. (Koyuncu et al., 2019) developed iFixR, an APR tool
driven by bug reports. iFixR builds on kPAR (Liu et al., 2019a) (a template-
based APR tool) and uses its repair templates. Specially, it uses bug reports
as the main input to guide program repair. However, there are shortcomings.
The quality of the bug reports will directly affect patch generation, and low-
quality or even incorrect bug reports may threaten the final fixing results.
Similar to iFixR (Koyuncu et al., 2019), Liu et al. (Liu et al., 2019c) also
summarized 35 repair templates from previous template-based works and proposed
an APR tool TBar. They found that the selection of repair patterns is
important. A single fault may apply to multiple repair templates. It may
generate multiple patches that seem reasonable but have differing performance,
so prioritizing the selected patterns avoids this problem and prevents
overfitting from occurring. In general, iFixR and TBar are similar in approach
design. They both employ the context-aware patch generation strategy and use
existing FL tools directly. In terms of repair ability, they both support
multi-type fixes, work only on Java, and do not explore multi-hunk and multi-
fault repair capabilities.

Note that the repair templates can be viewed as empirical knowledge to guide
repair. It means that the above automated template mining efforts can be
automated to learn empirical knowledge. There are two exceptions, iFixR
(Koyuncu et al., 2019) and TBar (Liu et al., 2019c), as they directly use
templates from other tools. In addition, multi-hunk and multi-language fixes
have received attention in the development of template-based techniques, which
we will describe next.

Given that the above template-based efforts are not specifically designed for
multi-hunk bug fixing scenarios. Therefore, some researchers have launched
targeted research for multi-hunk bug fixing. In 2019, Saha et al. (Saha et
al., 2019) proposed the APR tool HERCULES, a multi-hunk repair solution. They
still followed the template-based technical foundation. The innovation of this
work is that it associates multiple bug locations to achieve simultaneous
fixes, which is a capability not available in the previous multi-hunk repair
tool, Angelix (Mechtaev et al., 2016). In summary, HERCULES has made an
important contribution to APR research by furthering the mitigation of the
multi-hunk repair problem, which will accelerate the process of moving APR
tools from academic research to industrial deployment.

Specifically, multi-language repair has also been investigated in traditional
APR techniques. In 2019, Ghanbari et al. (Ghanbari et al., 2019) proposed
PraPR, a repair tool that supports multiple JVM languages. Unlike previous
works that mostly perform the repair at the source code level, PraPR works at
the bytecode level. This approach allows PraPR to support multiple JVM
languages and has higher scalability. Overall, bytecode-level repair
techniques provide a new way for APR research, which helps to free the repair
behavior from the source code level to explore deeper root causes of defects
and extend to multi-language repair scenarios.

####  5.3.3. Summary

By combing the development of template-based APR techniques, it has evolved
from the early manual extraction to the current automated mining. Different
data sources (such as patch information (Kim et al., 2013), project history
(Le et al., 2016b), defect report (Koyuncu et al., 2019), etc.) are used in
the template generation approach. In patch generation strategy optimization,
factors such as template donor quality and template priority order (Liu et
al., 2019c) are also considered. These are all effective ways to improve the
quality of fixes. Notably, template-based techniques have made great
contributions to the field by alleviating the problems of search space
explosion, invalid patch generation, and patch generation efficiency. However,
template extraction is affected by noisy data, and there are also problems,
such as the trade-off between template granularity and defect type coverage.
Another research dilemma of template-based approaches is that they cannot fix
defects beyond the basic patterns due to the lack of continuous learning
capability. Such approaches tend to focus on fixing more general, repetitive
defect classes. On the other hand, they neglect to focus on complex, special,
non-universal defect classes. Future work can continue to improve template
mining, selecting and matching strategies, and extending the template-based
approach to repair more defect classes.

###  5.4. Learning-based

With the above review, template-based APR techniques show great potential in
that they can automate template mining to obtain empirical knowledge (repair
templates) used to guide defect repair. And early learning-based approaches
are also based on template-based methods. They set up probabilistic models on
the distribution of repair patterns to guide better selective fix patterns,
such as early works by Martinez et al. (Martinez and Monperrus, 2015), Long et
al. (Long and Rinard, 2016), and Saha et al. (Saha et al., 2017). However, the
addition of probabilistic models only optimizes the detailed steps (i.e.,
template selection and matching), and these formalized repair templates do not
mean that template-based methods learn high-level repair knowledge. It is
crucial to advance the automation of the repair process and the learning of
high-level repair knowledge. The emergence of deep learning technologies
provides the possibility of automating the learning and repair implementation.
With the help of neural network models, APR tools can automate the learning of
empirical knowledge from a large number of defect repair samples that can be
used to guide defect repair. For this reason, learning-based APR techniques
are also known as data-driven repair solutions. Learning-based APR techniques
have become the hottest avenue of research today. Unlike traditional APR
techniques (Section 5.1-5.3) that focus more on software bug fixing,
researchers have explored different types of defect problems (e.g., software
bugs, programming errors, and security vulnerabilities) separately in
learning-based techniques. Next, we will review these SOTA works from the
perspective of different defect problems.

####  5.4.1. Software Bug Repair

Software bugs have been a major concern in software engineering for a long
time, and researchers hope to address this class of defects in real-world
software projects with the help of learning-based APR techniques. Software
bugs are mostly logical defect problems that require specific test cases for
defect triggering and patch validation. Therefore, researchers typically use
two metrics to evaluate specific fixes: for test benchmarks with test suites,
”correct patches/plausible patches” is often used to measure fixes; for large-
scale datasets without test suites, the repair accuracy (prediction fix exact
match correct fix) is used to measure the repair results.

The development of data-driven bug-fixing techniques was first inspired by
tasks related to natural language processing (NLP). Researchers viewed repair
tasks as translation tasks, i.e., translating a buggy statement into a correct
statement. Back in 2018, Tufano et al. (Tufano et al., 2019) used Neural
Machine Translation (NMT) techniques to fix bugs. They extracted bug codes and
fix codes to obtain bug-fix pairs (BFPs). Then they build an NMT model to
learn repair knowledge from BFPs. This work had a profound impact as a pioneer
in learning-based bug repair techniques, introducing the NMT task framework
for program repair tasks and laying the foundation for later learning-based
APR works.

In 2019, Chen et al. (Chen et al., 2021a) proposed SequenceR, which still
follows NMT techniques. Specifically, it uses the copy mechanism to overcome
the large vocabulary problem. Moreover, it motivates the model to focus on and
distinguish between bug code and contextual content for targeted fixes by
adding special markers to bug locations. This idea, in turn, opens the door to
context-aware repair techniques. In addition, in 2019, work emerged to address
specific bugs and give birth to hybrid technical solutions. Vasic et al.
(Vasic et al., 2019) proposed a solution for the variable-misuse bug. This
work utilizes a multi-headed pointer network that can be promoted to locate
and fix bugs simultaneously. White et al. (White et al., 2019) proposed
DeepRepair. It relies on deep learning to infer code similarity to select
repair ingredients from code fragments. Overall, all three efforts focus on
bug fixes, but they have many differences. Vasic et al. focus on specific bug
types, while DeepRepair and SequenceR support multi-type fixes. In addition,
Vasic et al. jointly localize and repair, which is an end-to-end solution.
Whereas DeepRepair and SequenceR do not focus on FL, they are a patch
generation strategy. Similarly, all three works are not designed for multi-
hunk and multi-fault fixes.

In 2020, DL techniques continued to fuel the APR, researchers began to explore
the limitations.

Li et al. (Li et al., 2020) found that DL-based APR tools still have
limitations. Strict code structure features can easily be overlooked. So, they
proposed DLFix. Unlike the representational form of sequences used by
SequenceR (Chen et al., 2021a), DLFix uses tree (AST) to record the code
structure. This allows DLFix to work better considering the context and
produces better fixes than previous NMT approaches. Besides, Lutellier et al.
(Lutellier et al., 2020) proposed CoCoNuT, which uses CNNs to extract
hierarchical features, which helps to capture rich (multiple levels of)
semantic information. Moreover, it uses a new context-aware NMT architecture,
which allows it to handle buggy code and context separately, as DLFix does.
CoCoNut also applies ensemble learning, further improving the repair
performance beyond prior works (Chen et al., 2021a; Li et al., 2020). However,
these tools are limited to fixing single-hunk bugs.

Data-driven solutions use many repair samples to drive the repair. Whether
this process can incorporate domain knowledge to better guide the repair, with
this in mind, Huq et al. (Huq et al., 2022) used code review to aid the APR
process and proposed Review4Repair. The input to the model is no longer a
single code, but the code review information is added. By leveraging code
review information, Review4Repair achieves better results than SequenceR (Chen
et al., 2021a).

Overall, in terms of approach design, DLFix, CoCoNut, and Review4Repair all
use context-aware patch generation strategies, especially Review4Repair adds
code review comments as context. But none of them is concerned with FL design,
and they can work together with the help of existing FL tools. In terms of
repair ability, they both support multi-type fixes. Also, none of them explore
the multi-hunk and multi-fault repair capability.

In 2021, researchers began to focus on improving models to further enhance
their ability to capture and understand PL features to better learn PL
knowledge. Further, the idea of using pre-trained PL models also started to
emerge gradually, which ushered in the era of large language models (LLMs) for
APR research.

Most previous works (Tufano et al., 2019; Chen et al., 2021a; Lutellier et
al., 2020) have adopted NLP techniques, such as NMT. However, these models
were not designed for PL scenarios (i.e., previous NMT-based APR tools were
not designed for PLs), the patches they generated contained many uncompilable
or incorrect patches. Therefore, some researchers have started to focus on
improving the models. Tang et al. (Tang et al., 2021) found that previous
Seq2Seq models often suffer from grammar and syntax errors. So they proposed a
grammar-based rule-to-rule model for the characteristics of PL. These grammar
rules are used to ensure the grammatical correctness of model-generated fixes.
It is shown that this model incorporating grammar-constrained outperforms the
previous NMT model (Tufano et al., 2019). Ye et al. (Ye et al., 2022) focused
on the fact that previous NMT approaches were not optimized for patch quality,
so they proposed a model RewardRepair can learn programming knowledge. They
made targeted improvements to the loss function. It adds program compilation
and test execution information to the loss function, rewarding the model for
generating compilable and overfitting-free patches. This method improves the
patch quality, outperforming SequenceR (Chen et al., 2021a), CoCoNut
(Lutellier et al., 2020) and DLFix (Li et al., 2020). Similarly, Zhu et al.
(Zhu et al., 2021) have improved the model architecture. They proposed
Recoder, a syntax-guided edit decoder. Recoder’s improvements allow the
decoder to incorporate knowledge of the syntactic structure of the programming
language to guide the generation of syntactically correct repair patches.
Notably, Recoder is the first DL-based APR approach that has outperformed
traditional APR techniques on the Defects4J benchmark.

Jiang et al. (Jiang et al., 2021) also improved on the shortcomings of
previous NMT-based schemes by proposing an APR tool, CURE. To enable the NMT
model to incorporate PL knowledge, they pre-trained a GPT PL model and
combined it with the NMT model. Besides, they propose a code-aware beam-search
strategy to explore the patch space more efficiently and use byte-pair
encoding (BPE) techniques to address the out-of-vocabulary (OOV) issue. These
improvements make CURE superior to previous APR tools (Lutellier et al., 2020;
Li et al., 2020; Chen et al., 2021a). Besides, TFix (Berabi et al., 2021) took
a different line of thought than CURE (Jiang et al., 2021). TFix uses a pre-
trained natural language model (not a PL model), T5, and fine-tunes it on the
programming language task. It also uses multi-task learning to repair multiple
error types and outperforms SequenceR (Chen et al., 2021a) and CoCoNuT
(Lutellier et al., 2020). Importantly, the above works (Jiang et al., 2021;
Berabi et al., 2021) introduced the workflow of pre-training and fine-tuning
to APR, which also provided inspiration for later solving the small sample
problem of vulnerability repair (Chen et al., 2022; Chi et al., 2022) (see
Section 5.4.3 for details).

Through the above works, we observe that how to make models better capture and
understand PL knowledge becomes a key issue. To better adapt to PL tasks
rather than NL tasks, we believe that using pre-trained PL models for APR
tools will be a direction that can continue to be explored. In summary, these
works (Tang et al., 2021; Ye et al., 2022; Jiang et al., 2021; Berabi et al.,
2021; Zhu et al., 2021) aim to address general bugs and do not focus on FL
research, using existing FL tools or perfect fault localization in the
experimental part. Also, most works considered context-aware strategies. In
terms of repair ability, these works support multi-type fixes, but they are
designed for single-line/hunk fixes.

In 2022, learning-based APR techniques entered the era of LLMs, with
researchers integrating them (LLMs) into APR tools to deeply exploit the
repair potential of LLMs. Additionally, multi-language and multi-hunk repair
have been further investigated, and hybrid techniques have been used to
facilitate traditional APR techniques.

Unlike previous works that train and tune models to gain knowledge of fixes,
LLMs provide an alternative route for APR research that directly draws on the
code understanding and generation capabilities of the LLMs to generate fixes.
This way was explored by Xia et al. (Xia and Zhang, 2022), who proposed
AlaphaRepair. Unlike the NMT approach that treats bug fixing as a translation
task, AlphaRepair directly uses CodeBERT (Feng et al., 2020) to predict
correct fixes by code context. Notably, AlaphaRepair outperforms all previous
APR tools in repair results and is inherently multi-language capable.
Subsequently, researchers have explored the repair capabilities of LLMs in the
zero-shot / few-shot learning paradigm through large-scale empirical studies
(Fan et al., 2022; Xia et al., 2022). This signifies the great potential of
LLMs to facilitate APR research.

In other works, researchers have explored applying hybrid techniques to
enhance APR tools. Li et al. (Li et al., 2022b) have combined the DL with the
traditional FL technique and then proposed a novel FL technique suitable for
multi-hunk repair scenarios. They improved on DLFix to implement the new APR
tool DEAR, which can solve multi-hunk bugs using a divide-and-conquer
strategy. In addition, Meng et al.’s work (Meng et al., 2022) not only uses DL
to improve FL but also guides template selection by training a neural network
model. Their tool, called TRANSFER, brings together learning-based and
template-based techniques to enhance APR tools. In general, combining DL with
other techniques is an effective path to further optimize APR techniques.

At the same time, multi-language repair has also been explored by researchers.
Yuan et al. (Yuan et al., 2022) combined the ideas of continual learning to
train CIRCLE to obtain cross-language repair ability. Notably, CIRCLE
implements ML fixes in a single model, which addresses the limitation of
previous APR tools that require training multiple models to repair multiple
languages.

The above review shows that applying LLMs and developing hybrid techniques
will be the future trend in APR research. The direct use of off-the-shelf LLMs
will reduce the training cost of APR (Xia and Zhang, 2022), while the
development of hybrid techniques will compensate for the shortcomings of a
single technique (Meng et al., 2022). In general, the above works (Xia and
Zhang, 2022; Li et al., 2022b; Meng et al., 2022; Yuan et al., 2022) is
designed for generic bug fixing. In particular, DEAR (Li et al., 2022b) has
multi-hunk repair ability, while the other tools are designed for single-hunk
repair. Moreover, AlphaRepair (Xia and Zhang, 2022) and CIRCLE (Yuan et al.,
2022) can support multi-language fixes with a single model, while other tools
need to train different models for different languages. In terms of FL, DEAR
(Li et al., 2022b) and TRANSFER (Meng et al., 2022) have designed novel FL
techniques, while the other APR tools do not improve on FL. In addition, all
the above tools rely on contextual information to guide patch generation, yet
none explore the ability of multi-fault repair.

####  5.4.2. Programming Error Repair

Unlike real-world software bugs, programming errors are simple types of
defects, usually syntactic or semantic errors, that may prevent a program from
compiling successfully and are therefore known as compilation errors (Li et
al., 2022a). The researchers want to use APR techniques to automate the repair
of such simple errors caused by inexperience in programming. Since programming
errors can be detected by the compiler and therefore do not require special FL
tools and test cases for fault localization, the researchers mainly use repair
accuracy to measure the repair effectiveness. Note that error repair usually
has two evaluation metrics (Li et al., 2022a) when calculating repair
accuracy: First, Single Repair. It is used to evaluate if the generated
statement exactly matches the ground-truth associated with a broken statement.
Second, Full Repair. It is calculated as the percentage of generated programs
that pass the compiler successfully.

Back in 2016, Bhatia et al. (Bhatia and Singh, 2016) and Pu et al. (Pu et al.,
2016) have provided solutions to programming errors by using recurrent neural
networks (RNN). They don’t focus on FL because the compiler can detect these
simple errors. But such a practice is inaccurate. Therefore, Gupta et al.
(Gupta et al., 2017) proposed an end-to-end solution DeepFix, which integrated
the error localization. It uses an attention based RNN model to capture long
term dependencies, which allows it to iteratively fix multiple errors in a
single program. Note that early works (Bhatia and Singh, 2016; Pu et al.,
2016; Bhatia et al., 2018; Gupta et al., 2017) implement repair only for
errors and not software bugs. But they demonstrate the effectiveness of DL for
program repair tasks, which also provides the basis for extending DL to bug
fixing.

In 2019, the researchers began specific optimization of the model training
phase. Gupta et al. (Gupta et al., 2019) presented RLAssist, which employs
deep reinforcement learning to repair syntactic errors. Most previous works
used supervised learning. Instead, they used unsupervised learning. The
approach relies on the number of error messages to design the reward function.
This makes the model more inclined to learn the correct fixes (not incorrect
fixes) during the learning process. Besides, Hajipour et al. (Hajipour et al.,
2019) proposed SampleFix. They argue that given a corrupted program, there are
multiple repair ways. In other words, the problem of program repair is modeled
as a one-to-many problem in which the model learns the distribution of
potential fixes through a generative model conditional on the incorrect input
program. In their experiment, SampleFix achieves up to 45% of error fixes and
generates multiple diverse fixes. In general, these tools focus on syntax
errors and support FL functions by themselves. In particular, RLAssist
considers the code context and can fix multiple errors, but SampleFix does not
describe these.

In 2020, Yasunaga et al. (Yasunaga and Liang, 2020, 2021) began to focus on
the impact that the training process has on the repair effect. In 2020, they
proposed DrRepair (Yasunaga and Liang, 2020). They expanded the training data
by corrupting correctly fixed examples to obtain more code with errors, and
they used a graph neural network (GNN) to record the code dependencies. These
two innovations enabled DrRepair to achieve a repair success rate of 68.2% on
the DeepFix dataset (Gupta et al., 2017). However, this data generated by
adding perturbations differed from real-world errors. So they propose a new
training method Break-It-Fix-It (BIFI) (Yasunaga and Liang, 2021) in 2021.
They train a breaker by using realistic bad code so that the breaker can
generate bad examples close to real-world data. In the experimental part, the
best result on the DeepFix dataset was further improved by combining BIFI with
DrRepair, achieving 71.7% repair accuracy. This suggests that BIFI is an
effective data enhancement to improve repair performance. These works are
dedicated to improving the training process to enhance the repair effect,
which deserves to be explored and applied in-depth in learning-based schemes.

In addition, some works have tried to incorporate some external information to
assist the repair process. Abhinav et al. (Abhinav et al., 2021) proposed
RepairNet. The major contribution of this work is the encoding of error
messages as additional contexts in the model to fix errors. With the combined
compiler error information, RepairNet achieved a 66.4% repair accuracy on the
DeepFix dataset (Gupta et al., 2017). This indicates that the error
information provided by the compiler is a vital feature to guide the repair.

Note that DrRepair (Yasunaga and Liang, 2020, 2021) and RepairNet (Abhinav et
al., 2021) support multi-line fixes. In particular, RepairNet does not use the
FL function but uses the error messages provided by the compiler. DrRepair
divides multiple error types in its experiments, and it supports repairing
multi-errors in a program.

In 2022, error repair began to benefit from bug repair research, and some of
the ideas applied to bug repair are applied to error repair. And error repair
is also ushering in the era of LLMs.

Context-aware repair solutions have previously been widely used in bug repair
(Li et al., 2020; Lutellier et al., 2020; Jiang et al., 2021), and this has
also inspired error repair. Based on this, Li et al. proposed TransRepair (Li
et al., 2022a), a context-aware error repair tool. Similar to the bug repair
task, the erroneous statement and its context are treated as different inputs
to be given to the neural network for processing, which enables the model to
combine rich contextual information for accurate repair. By combining the
advanced Transformer architecture and other technical details, TransRepair
outperforms previous works (Yasunaga and Liang, 2020; Gupta et al., 2017,
2019; Hajipour et al., 2019) of its kind in terms of fixing results. In
particular, TransRepair incorporates MLP to design an FL strategy and supports
multi-type, multi-line, and multi-error repair.

In addition, LLMs are also used for error-fixing tasks. Similarly to
AlphaRepair, Zhang et al. (Zhang et al., 2022) used LLM to fix programming
errors and proposed an APR system MMAPR based on CodeX. MMAPR ensembles multi-
modal prompts to generate complementary repair candidates. Similar work was
proposed by Joshi et al. (Joshi et al., 2022), who implemented a repair tool
RING based on Codex, and it implemented multi-language repair. RING and MMAPR
use similar technical paths (prompt learning (Liu et al., 2023)), and although
multi-hunk and multi-fault fixes have emerged in the MMAPR fixes, their repair
ability has not been discussed in depth.

The above works (Li et al., 2022a; Zhang et al., 2022; Joshi et al., 2022)
show that solutions from different problem domains can be cross-pollinated to
facilitate APR research and that LLMs have great potential for error repair
tasks.

####  5.4.3. Security Vulnerability Repair

Vulnerabilities (security bugs), a subset of software bugs, are more damaging
and require more urgent fixes, making it critical to automate vulnerability
fixes. However, vulnerability repair has not been independently studied in the
previous software engineering APR community, and both security and non-
security bugs have been fixed as the same kind of problem, which makes it hard
to know how effective these APR tools are in fixing vulnerabilities. For this
reason, learning-based vulnerability repair, a major concern in system
security, has received targeted research in recent years.

Early vulnerability repair efforts also received inspiration from NMT
techniques. However, the task framework of NMT requires a large amount of
annotated data to support the training of Seq2Seq models. To mitigate against
this challenge, Harer et al. (Harer et al., 2018) proposed to perform
adversarial learning (ADL) using Generative Adversarial Network (GAN), which
allows training without pairing (BFPs).

Given the many advances that have been made in bug repair problems by
researchers in the field of software engineering, researchers also wish to
draw on this empirical knowledge to further contribute to the vulnerability
repair problem. Among them, recent representative works are VRepair (Chen et
al., 2022) and SeqTrans (Chi et al., 2022), which both rely on the pre-
training + fine-tuning learning paradigm by pre-training on large-scale bug
fixing datasets to gain empirical knowledge on bug fixing and then using
transfer learning to fine-tune on small-sample vulnerability fixing datasets
to improve the vulnerability fixing capability. Unlike VRepair, which improves
the code representation by allowing multiple bug locations to be tagged to
support multi-hunk bug fixing, SeqTrans only works in single-line repair
scenarios. However, SeqTrans adds the program’s data flow dependencies as
features, further improving the model’s ability to capture deep semantic
information for understanding. Overall, these works draw on empirical
knowledge of software bug fixing and use transfer learning to alleviate the
limitations of the small sample problem in the vulnerability repair domain.

Recently, researchers have also explored the capabilities of LLMs for
vulnerability repair through a large-scale empirical study (Pearce et al.,
2022), which signifies the same potential of large language models for
vulnerability repair. In a recent data-driven vulnerability repair effort,
VulRepair (Fu et al., 2022) fine-tuned it with the help of the LLM, CodeT5
(Wang et al., 2021). Thanks to the LLM’s powerful knowledge base and ability
to capture and understand features, VulRepair achieved superior repair results
compared to VRepair. The results demonstrate that LLM fine-tuning is more
efficient and faster than traditional model training and effectively improves
the repair result of APR tools. In the future, vulnerability repair research
will enter the era of LLMs. The powerful code understanding and generation
capabilities of LLMs will further promote the development of the vulnerability
repair community.

From the above review, we observe that vulnerability repair is facilitated by
bug repair, with SeqTrans (Chi et al., 2022), VRepair (Chen et al., 2022), and
VulRepair (Fu et al., 2022) all leveraging context-aware patch generation
strategies and supporting multi-type repair, and VRpair and VulRepair
supporting multi-hunk repair. However, vulnerability repair research has not
yet delved into vulnerability localization, and multi-defect repair has not
been explored in depth. With the advent of LLMs, the use of LLMs to facilitate
FL and further improve repair ability will be a future chance.

####  5.4.4. Summary

The learning-based approaches learn empirical knowledge of program repair from
large amounts of data in open source software (OSS) communities, which
addresses many limitations in previous APR techniques and further facilitates
the automation of APR techniques. DL’s powerful learning capabilities offer
the possibility of multi-language repair. APR tools have even gained the
ability to continuously learn and repair. More importantly, high-quality data,
more advanced models, and better representation methods all provide strong
support for APR studies. However, APR tools are still challenging to apply
these techniques due to some limitations of current AI technologies: For
example, neural networks cannot handle long sequences well (Fu et al., 2022;
Tufano et al., 2019; Chen et al., 2021a; Gupta et al., 2017); the OOV problem
limits the ability of models to generate new tokens(Fu et al., 2022; Chen et
al., 2022); the strict syntactic structural features and complex semantic
dependencies of PLs are difficult to effectively capture and understand by
models (Jiang et al., 2021), and so on. Fortunately, AI is developing rapidly,
and the emergence of LLMs provides new opportunities for APR research.
Therefore, We hope that more efforts in the future will transfer these latest
AI techniques to the APR domain. Moreover, combining DL solutions with
traditional APR techniques is a valuable direction.

###  5.5. APR Development Summary and Discussion

In this section, we will summarize and discuss these APR techniques so that
the reader can quickly learn the pros and cons of these techniques and the
current state of development of APR research.

####  5.5.1. Summary

Here, we summarize the development of four classes of APR techniques. We also
provide a summary of the pros and cons of APR techniques using different
approaches in Table LABEL:tab:table2-3-1.

  * •

The search-based approach was the first repair technique explored, and it
shows extremely many possibilities for program repair, but the huge search
space and high computational resources are important factors that limit its
development.

  * •

The constraint-based approach has advantages in terms of repair efficiency,
but its reliance on correct rule constraints makes it less flexible in repair,
and the formulation of constraints may require manual definition, which
undoubtedly increases labor costs.

  * •

The template-based approach demonstrates efficiency in repairing specific
classes of defects, but it cannot repair defects that are not summarized by
templates.

  * •

The learning-based approach shows great flexibility and scalability in
repairing multiple languages and types of defects. However, its repair
capability is vulnerable to training data and thus benchmark overfitting, and
the patch interpretability remains to be explored.

In general, the development of APR has been a continuous process of
integration. The search-based approach, which first emerged, used various
heuristics to generate and find candidate fixes in the search space. The
constraint-based approach added formal specifications and other constraints to
limit the search space and improve the efficiency of the search-based
approach. The template-based approach adds repair templates to guide patch
generation, solving the shortcomings of the constraint-based approach’s lack
of flexibility and the heuristic approach’s lack of guidance on program
variant generation. The learning-based approach further solves the tedious
work of the template-based approach on template extraction and obtains richer
program syntax and semantic-level features through learning. It also has the
scalability and flexibility of multi-language and multi-type repair, thus
making it possible to automate APR in the true sense. In this process, various
techniques reinforce and complement each other. However, there are still many
limitations. As shown in Table 2, efforts are still needed to design efficient
FL functions and closely link localization and repair; in addition, APR tools
still need efforts in multi-hunk and multi-fault fixes. We believe that the
future trend will be to integrate multiple types of techniques that draw on
each other, compensating for the single technique’s inherent shortcomings and
helping propose new solutions.

Table 3. A summary of the pros and cons of different classes of APR techniques Sec. | Typical Work | Time | Approach | Pros | Cons
---|---|---|---|---|---
5.1 Search-based
5.1.1 |  (Jobstmann et al., 2005; Griesmayer et al., 2006) |  2005-2006 |  Repair as a Game |  Partial fixes do not affect the structure and logic of the source program. |  Repair Efficiency Problem and Generic Fixes Problem: The approach revealed shortcomings such as inefficient fixes, limited types of fixes, and repetitive fixing behavior.
5.1.2 |  (Weimer et al., 2009; Schulte et al., 2010; Goues et al., 2012b; Forrest et al., 2009; Weimer et al., 2010; Fast et al., 2010; Goues et al., 2012c; Weimer et al., 2013; Qi et al., 2013; Kim et al., 2013) |  2009-2014 |  Program repair using EC and GP |  First, GP can be extended to large program repair. Second, the flexible mutation capability of the GP approach allows the implementation of multiple types of defect repair. Third, mutation at multiple locations allows for multi-line bug fixes. |  Repair Efficiency Problem and Repair Quality Problem: The presence of a large search space in the GP strategy leads to inefficient repair. Mutation process may generate a large number of invalid or incorrect fixes.
(Qi et al., 2014) |  2013-2014 |  Program repair using random search |  Random search strategy is simpler and outperforms GP method (GenProg) in repair effectiveness and efficiency. |  Generic Fixes Problem: This work has only explored the case of fixing a program that contains a single bug, and has not explored the case of a program that contains multiple bugs.
(Sidiroglou-Douskos et al., 2015) |  2015 |  Program repair using HGT |  This approach can automatically leverage the combined knowledge integrated across multiple software systems to improve individual applications, and it avoids the resource consumption of the GP method mutation process. |  Repair Quality Problem: It relies on the code knowledge of the code provider, which prevents code migration fixes if a defect lacks correct representation in other systems. In addition, mixed code is more likely to introduce new defects.
(Yuan and Banzhaf, 2020a, b) |  2017-2019 |  Program repair using GP and template-based idea |  This work combines redundancy assumption and repair templates to generate repair statements to further improve repair efficiency, reduce the search space, and alleviate the patch overfitting problem. |  Large-scale Project Bug Fixes: This approach also suffers from template coverage, and the lack of repair templates leads to possible limitations in the repair of large-scale programs.
5.1.3 |  (Long and Rinard, 2015) |  2015 |  Program repair using staged program repair |  Staged program repair can reduce the size of the search space and explore large search spaces more efficiently. |  Generic Fixes Problem: SPR will only apply one transformation each time a candidate fix is generated, and cannot combine multiple transformations. It means that it has limitations when fixing complex bugs that require multiple fix patterns.
5.1.4 |  (Ji et al., 2016; Wang et al., 2017; Xin and Reiss, 2017, 2019) |  2016-2019 |  Program repair using code block similarity |  The code similarity-based approach effectively reduces the search space compared to the GP-based and random search approaches. In addition, using ready-made code from open-source code repositories for fixes helps to obtain high-quality fixes and avoid introducing new bugs. |  Repair Efficiency Problem: Limited by the size of the code base and the search capability of the search algorithm, the APR tool may not be able to search for available similarity codes in all cases.
(Jiang et al., 2018) |  2018 |  Program repair using patches and similar code |  Compared to previous work using only code similarity, adding patch information can further narrow the final search space and help explore the search space more efficiently. |  Repair Quality Problem: The quality of existing patches can easily have an impact on the quality of the final fix, and low quality patches can lead to low quality or incorrect fixes.
(Wong et al., 2021) |  2021 |  Program repair using similarity information from patch tests |  Using variational execution techniques to obtain similarity information from patch tests allows for more efficient exploration of large search spaces. |  Repair Efficiency Problem: The variational execution used in this work is a dynamic analysis technique with a large resource overhead, which leads to a larger repair time cost.
5.2 Constraint-based
5.2.1 |  (Wei et al., 2010; Pei et al., 2011, 2014) |  2010-2014 |  Program repair using contracts |  The approach does not require user-written test cases as compared to the test case based solution. In addition, the approach using a contract requires lower computational resources, resulting in lower repair costs. |  Generic Fixes Problem: It still has limitations in flexibility. This class of methods requires developers to write the correct contract during programming, which does not support current mainstream programming languages.
(Chen et al., 2017, 2021c) |  2017-2021 |  Program repair using contract-based idea without contracts |  The method inherits the advantages of contract-based repair techniques, alleviates the patch overfitting problem, and supports mainstream programming languages. |  Generic Fixes Problem: The fixes generated by this tool tend to be small and unable to generate syntactically complex fixes, which also means that it is not advantageous for fixing multi-line bug tasks that require more changes.
5.2.2 |  (Gopinath et al., 2011) |  2011 |  Program repair using SAT to solve specification constraints |  Using rich behavior specifications can help fix programs with complex structures. |  Repair Quality Problem: The accuracy of the fixes generated by this technique is affected by the completeness and accuracy of the constraints and is limited by the specification-based bounded verification techniques. In addition, it generates only near-accurate repair suggestions, which still need to be verified by the user.
(Nguyen et al., 2013; Mechtaev et al., 2015; Xuan et al., 2017; Mechtaev et al., 2016) |  2013-2016 |  Program repair using test case driven semantic constraint-based approach |  The semantic constraint-based approach has a higher repair success rate and shorter repair time than the syntax search-based approach (such as GenProg) (Nguyen et al., 2013). This is thanks to the fact that they alleviate the huge search space and avoid the uncertainty of the mutation process. |  Repair Quality Problem and Generic Fixes Problem: The test case driven solution lacks flexibility compared to the approach that uses behavioral specifications. Besides, the generation of repair constraints depends on the execution of test cases, and therefore the quality of the test cases affects the quality of the repair. (Note that most generate-and-validate repair techniques are affected by the quality of the test cases (Yang et al., 2017).)
(Ke et al., 2015; Afzal et al., 2021) |  2015-2019 |  Program repair using semantic code search |  Using a human-written code base and semantic code search can provide high-quality fixes. |  Repair Quality Problem: The quality of the artificially constructed code repository will affect repair quality. Especially the artificial nature of the repository construction may bias the repair.
5.2.3 |  (Le et al., 2016a, 2017) |  2016-2017 |  Program repair using syntactic and semantic features |  Combining the two techniques can overcome the shortcomings of using a single technique, can provide high-quality fixes, and mitigate patch overfitting problems. |  Generic Fixes Problem: The semantic-based approach can only modify the expressions and the constraint solving technique still cannot handle some special types of variables. These inherent limitations lead to many types of defects that cannot be repaired, which limits the overall repair capability.
5.2.4 |  (van Tonder and Goues, 2018; Nguyen et al., 2019) |  2018-2020 |  Program repair using formal specifications |  Compared with the test suite based approach, the formal specification based approach provides better coverage of the program input/output relationships and avoids the test case coverage problem. In terms of fixing results, using the formal specification approach mitigates the patch overfitting problem caused by the test case based approach and helps improve the quality of fixes. |  Generic Fixes Problem: Like other constraint-based techniques, the use of formal specifications sacrifices flexibility and scalability, and most of these efforts are designed for specific defect types and cannot be generalized to broad generic defect fixes.
5.3 Template-based
5.3.1 |  (Pan et al., 2009; Kim et al., 2013; Tan and Roychoudhury, 2015) |  2009-2015 |  Program repair using manually extracted repair templates |  Compared with search-based GP techniques, the use of repair templates avoids aimless random mutations and makes the program repair behavior toward a given template, which avoids generating a large number of nonsensical patches and improves repair efficiency and patch quality. |  Repair Efficiency Problem and Generic Fixes Problem: Manual mining is tedious, error-prone, and cannot scale (Koyuncu et al., 2020). First, it requires additional labor costs to summarize the repair templates. In addition, the manual work cannot generate a large number of templates quickly, which suffers from the problem of template coverage, and many defects cannot be fixed due to the lack of corresponding repair templates.
5.3.2 |  (Le et al., 2016b; Long et al., 2017; Liu et al., 2021a, 2019b; Koyuncu et al., 2020, 2019; Liu et al., 2019c) |  2016-2021 |  Program repair using automated template mining method |  Compared to manual extraction of templates, the automated approach improves efficiency and generates more templates to address more defect types. |  Repair Quality Problem: Although the number of templates is improved, the balance of granularity and coverage of templates is an issue. And the automated extraction approach is often not as precise as human work, which may introduce some noise in the repair templates.
5.4 Learning-based
5.4 |  (Tufano et al., 2019; Harer et al., 2018) |  2018-2019 |  Program repair using NMT techniques |  Compared to test-driven techniques, NMT techniques using deep learning do not require the help of test cases to guide patch generation. Compared to other previous techniques, data-driven solutions have higher fixing efficiency and lower fixing cost because the training of the model is a one-time cost. In addition, data-driven solutions can be extended to repair tasks in multiple PLs by replacing components such as lexer, parser, etc., and can repair multiple defect types, solving the generic fixes problem with higher scalability. |  Repair Efficiency Problem and Generic Fixes Problem: NMT systems are indeed data-hungry system. It also requires a significant training time cost, and model training is a time-consuming process. In addition, early works still cannot handle excessively long sentences, making them unable to fix complex bugs with excessively long sentences and thus unable to effectively address large program fixes.
(Chen et al., 2021a) |  2019 |  Program repair using NMT techniques and Seq2Seq learning |  Compared to previous works by Tufano et al. (Tufano et al., 2019), SequenceR uses the copy mechanism to overcome the unlimited vocabulary problem. In addition, it constructs abstract bug contexts, which simplifies the complexity of the input sequence, allowing it to capture long range dependencies that are required for the fix. |  Generic Fixes Probllem and Repair Quality Problem: SequenceR is designed for single-line bug fixing, it does not yet address multi-line bug fixing. The sequence representations and sequence-based DL models are not suitable for capturing code structures, and this could lead to imprecise mappings and eventually incorrect fixes.
(Li et al., 2020) |  2020 |  Program repair using NMT techniques and tree-based RNN |  Compared to previous works by Tufano et al. (Tufano et al., 2019) and SequenceR (Chen et al., 2021a), DLFix uses a tree structure to capture the syntactic structural features of the code and uses the tree RNN to learn code transformations. This helps to make the model generate fixes that conform to the rules of the PL, further improving the repair quality. |  Generic Fixes Problem: While the tree-based feature representation and learning approach is effective, it also poses significant limitations. DLFix can only fix single-line bugs which have the same bug location as the fix location, and it does not handle multiple bugs in a method very well.
(Jiang et al., 2021) |  2021 |  Program repair using NMT techniques and PL model |  Compared to previous NMT models, they have difficulty understanding the strict code syntactic features and thus generate some incorrect or non-compilable patches. Instead, CURE uses a pre-trained PL model, which allows it to incorporate the correct knowledge of the source code and significantly improve the repair quality. |  Generic Fixes Problem: CURE is designed to fix single-hunk bugs. Besides, pre-training PL models is an extremely time-consuming process.
(Fu et al., 2022) |  2022 |  Program repair using NMT techniques and LLM fine-tuning |  Fine-tuning the LLM can speed up model convergence. Importantly, the LLM has already learned about the PL knowledge during the pre-training phase, so fine-tuning on top of it can further improve the repair. For example, VulRepair (Fu et al., 2022) obtains higher repair accuracy than VRepair (Chen et al., 2022). |  Generic Fixes Problem: LLM fine-tuning requires a certain number of bug-fix pairs to support the training process, so the fine-tuning workflow cannot be applied for some scenarios that lack training data.
(Xia and Zhang, 2022; Fan et al., 2022; Xia et al., 2022; Pearce et al., 2022; Zhang et al., 2022; Joshi et al., 2022) |  2022 |  Program repair using LLM prompt learning (zero / few-shot learning) |  Compared to fine-tuning workflows, prompt learning requires only a small amount of training data or no training data to achieve repair predictions. This process aims to emphasize the LLM’s code understanding and generation capabilities. |  Repair Quality Problem: Since the pre-training of LLMs is done in a large amount of source code. Therefore, LLM may generate incorrect repairs due to the pre-training phase learning defective code samples (incorrect repair knowledge).

####  5.5.2. Discussion

Further, while reviewing the APR techniques, we also hope to discuss the
current state of technical development to seek some interesting findings. To
thoroughly survey state-of-the-art techniques and seek valuable findings, we
have added more details on some representative works in Appendix A. In
Appendix A, we selected six representative works for search-based, constraint-
based, and template-based APR, respectively. Given that deep learning
techniques have been widely used in recent years, we focus on learning-based
techniques and present 26 representative works. Next, we discuss some
interesting findings by combining a review of previous works (Table 2) and an
analysis of these details (Appendix A). These findings may reflect current
problems and future research trends, and we will discuss this content.

Finding 1: Java and C are the main research targets supported by APR tools,
and there are differences between learning-based APR techniques and
traditional APR techniques in terms of multi-language repair ability. The
reason for this phenomenon is that Java and C are still the dominant PLs.
Therefore, researchers are also keener to focus on these PLs, which are more
representative. However, this also reflects the lack of current research, and
other PLs also deserve our attention. And it also shows that many APR tools
are deficient in scalability, as they usually support only a single PL. It is
worth noting that some learning-based APR techniques implement support for
multiple PLs in a single APR tool (Yuan et al., 2022; Xia and Zhang, 2022),
while most of the traditional APR techniques need to implement different APR
tools for different PLs. Therefore, it is an interesting direction to combine
DL with traditional APR techniques to improve APR tools’ repair ability.

Finding 2: Looking at the defect scenarios fixed by APR tools, not only
software bugs but also programming errors are included in the scope of
problems.  Because in the early research, bug repair was the initial concern
of software engineering. And later on, researchers found that the essence of
defect repair is a process of code error correction, which means that APR
techniques can also solve some typical programming errors. The researchers who
focus on this aspect are mostly in the field of AI, and they hope to study
deeper code problems with the help of DL. In addition, research on
vulnerability repair appears to be in its infancy. Researchers in security are
leveraging previous APR ideas to address these security bugs. It can be seen
that cross-fertilization of different problem areas is the future trend, and
we emphasize the migratory nature of different techniques. The
multidisciplinary intersection of software engineering, artificial
intelligence, system security, etc., will be a research trend that will
jointly help APR techniques solve various code problems.

Finding 3: In terms of the complexity of fixing defects, single-hunk bugs seem
to be of more concern, and most APR techniques only support the fixing of
single-hunk bugs. This phenomenon reflects that the multi-hunk fixes still is
a challenge. Even though the single-hunk repair tool can iteratively fix
multi-hunk bugs, it may use the context with the bugs, so this is not an
appropriate solution (Li et al., 2022b). In recent years, although HERCULES
(Saha et al., 2019) has emerged, a repair tool designed explicitly for multi-
hunk fixes scenarios, it addresses only a specific class of multi-hunk fixes,
namely ones with substantially similar patches for each hunk. In addition,
while learning-based solutions are now beginning to focus on multi-hunk fixes
(Li et al., 2022b), there are many limitations, which we will discuss in
detail in Finding 18. Overall, the multi-hunk fixes problem is always a
challenge, and the complex dependencies between multiple lines of code make
the repair even more difficult. In the long run, multi-hunk bug fixing is
still a direction for future researchers.

Finding 4: From the benchmark datasets used by each APR tool, Defects4J is the
most widely used benchmark for software bugs, DeepFix dataset is the most
commonly used benchmark for programming errors, CVEfixes and Big-Vul are two
of the latest vulnerability fix datasets. But the amount of data in these
datasets is still limited. Defects4J 2.0 contains only 835 bugs. CVEfixes and
Big-Vul contain only thousands of real CVE vulnerabilities. In addition,
benchmark overfitting may occur when using a single benchmark for APR
performance evaluation (Durieux et al., 2019). We recommend evaluating
multiple benchmarks when possible during experimental evaluation. We believe
that future research should aim to present more diverse and comprehensive
benchmarks. Benchmarks for different PLs and different defect types should be
an ongoing effort in the future. With more datasets, the data basis of the APR
research area will be further enriched.

Table 4. The repair result of APR tools with/without perfect fault
faultlization on Defects4J V1.2.0

Technique Type | Learning-based APR techniques | Traditional APR techniques
---|---|---
APR Tool | AlphaRepair | Recoder | CURE | CoCoNuT | DLFix | TBar | AVATAR | FixMiner | jGenProg
X/Y (with PFL) | 74/109 | 65/112 | 57/104 | 44/85 | 40/68 | 68/95 | 29/50 | 34/62 | 6/16
X/Y (without PFL) | 50/90 | 49/96 | 36/71 | 33/57 | 30/65 | 43/81 | 27/53 | 25/31 | 5/27
P% (with PFL) | 67.89% | 58.04% | 54.81% | 51.76% | 58.82% | 71.58% | 58.00% | 54.83% | 46.15%
P% (without PFL) | 55.56% | 51.04% | 50.70% | 57.89% | 46.15% | 53.09% | 50.94% | 80.65% | 18.52%

  * •

These repair results were extracted from latest works (Xia and Zhang, 2022;
Zhu et al., 2021; Li et al., 2022b). X/Y: correct patches / plausible patches;
P%: the percentage of correct patches.

Finding 5: From the repair results, the patch overfitting problem is prevalent
for either repair technique. Here, an interesting observation is that a more
accurate FL might further alleviate the patch overfitting problem. We observe
that using perfect fault localization (PFL) (Xia and Zhang, 2022) and not
using PFL (using off-the-shelf FL tools) lead to significant differences in
patch overfitting on the same test benchmark. Specifically, to clearly present
the impact of FL on repair quality, we selected the repair results of APR
tools on the most widely used Defects4J V1.2.0 and presented them uniformly.
Table 4 shows that most APR tools based on PFL were better at patch
overfitting (higher percentage of correct patches). This indicates that more
accurate FL is crucial for repair quality, which not only helps to promote APR
tools to repair more defects, but also further alleviates the patch
overfitting. It also points out the way to further optimize the repair
quality, i.e., by optimizing the FL technique to mitigate the patch
overfitting problem. However, limited by the paper’s type, we did not explore
the deeper factors behind how other factors (e.g., patch generation, patch
validation.) affect the repair results. We suggest future work to explore
these topics.

Finding 6: In terms of actual results on Defects4J, the most widely used
current benchmark, the learning-based APR tools outperform previous
traditional APR tools. Next, we attempt to analyze the reasons for the
superior performance of the learning-based solutions. The learning-based APR
technique is a data-driven solution. Its powerful repair ability is due to the
huge amount of open-source project data (e.g., GitHub) available in the world
today. The vast amount of data provides the empirical knowledge that neural
models use to learn, resulting in powerful AI APR tools. But data-driven
techniques have never been as accurate and appropriate as humans. Its
interpretability is still lacking, resulting in actual industrial deployments
that may not work well with developers. However, it is undeniable that we see
powerful potential in data-driven APR tools, and more researchers will devote
themselves to learning-based APR techniques.

Next, we present an in-depth analysis of learning-based APR works and describe
our findings.

Figure 4. Code abstraction example (Tufano et al., 2019).

Finding 7: Pre-processing. Different pre-processing strategies in APR
techniques have yet to be systematically studied. Learning-based APR works use
different code pre-processing approaches. However, these approaches are not
compared under the same benchmark, and it is unclear whether these approaches
can be practical for LLMs-based APR techniques.

We observe that for APR techniques (Chen et al., 2021a; Tufano et al., 2019;
Li et al., 2020, 2022b; Chi et al., 2022; Li et al., 2022a) using traditional
models (not LLMs), they often rename the variable names, method names, etc.,
in the raw source code uniformly. For example, Tufano et al. (Tufano et al.,
2019) call their approach code abstraction, Li et al. (Li et al., 2022b, 2020)
call them alpha-rename, and Chi et al. (Chi et al., 2022) call them
normalization abstraction. For convenience, we refer to these pre-processing
approaches collectively as Code Abs. To better understand the code form of
Code Abs, we show an example in Fig. 4. Early work mainly used Code Abs
approaches to alleviate the OOV problem and facilitate models learning generic
repair patterns. However, in later LLM-based APR works (Fu et al., 2022), Code
Abs has been discontinued. One of the reasons behind this is that LLMs usually
use subword-level tokenizers, alleviating the OOV problem. However, no studies
have explored the impact of Code Abs on LLM repair in-depth, and we do not
know whether Code Abs can further improve the repair result of LLMs. Here, we
have explored this through preliminary experiments. We followed the
implementation of the LLM-based APR work (Fu et al., 2022; Zeng et al., 2022)
and the Code Abs scheme of Tufano et al. (Tufano et al., 2019) and employed
several SOTA LLMs (Zeng et al., 2022) for fine-tuning on the BFP dataset
(Tufano et al., 2019). The result (see Table 5) shows that Code Abs does not
significantly improve the repair performance of most LLMs. We think there are
two main reasons why Code Abs does not work well on LLMs: First, as Chen et
al. (Chen et al., 2022) argue, the code abstraction process may lose some
special semantic information of method names and variable names, which
prevents the models from learning this critical information; Second, LLMs are
pre-trained on a large amount of raw source code, which learns the unprocessed
source code knowledge, so they are better suited to work on unprocessed raw
source code in downstream tasks. Therefore, this also inspires us that no
additional code processing steps need to be used for LLMs repair.

In addition, we observe that different APR efforts employ different code
abstraction details. For example, Tufano et al. (Tufano et al., 2019) rename
variable names, method names and literals, and they preserve idioms; SequenceR
(Chen et al., 2021a) replaces only tokens that do not appear in the
vocabulary; SeqTrans (Chi et al., 2022) renames only variable names and
literals; TransRepair (Li et al., 2022a) replaces the function name, variable
name and self-defined struct with the identifiers ”¡funcN¿”, ”¡varN¿” and
”¡typeN¿” for normalization; DLFix (Li et al., 2020) renames variables but
retains the variable types; and so on. While these different Code Abs
approaches have not been compared under the same benchmark, we cannot know the
impact of these differences in technical details on the same APR tool, which
requires more empirical studies to explore this issue.

Table 5. The repair accuracy of LLM-based APR tools with/without Code Abs

Dataset | Repair Accuracy |  | Dataset | Repair Accuracy
---|---|---|---|---
CodeBERT | GraphCodeBERT | PLBART | CodeT5 |  | CodeBERT | GraphCodeBERT | PLBART | CodeT5
BFP_small with Code Abs | 16.90% | 17.46% | 19.40% | 21.80% |  | BFP_medium with Code Abs | 9.73% | 10.36% | 13.17% | 13.95%
BFP_small without Code Abs | 17.48% | 17.62% | 17.93% | 25.18% |  | BFP_medium without Code Abs | 9.41% | 10.45% | 10.13% | 16.03%

Finding 8: Code Representation. Token Sequence is the most widely used type of
code representation. In addition, Tree (AST), Graph, and other representations
are also used. Token Sequence is widely used because it is one of the most
concise and intuitive ways to represent code. Code elements are treated as
word elements and passed to the neural network to facilitate programming
language processing using NLP approaches without tedious processing steps.
Although the Token Sequence approach is simple, it ignores the strict code
structure and is hard to capture and record the complex dependencies between
code elements. As a result, this input information may limit the model’s
ability to capture comprehensive and rich code features, ultimately impacting
the quality of the generated code. In contrast, representations such as Tree
(Li et al., 2022b, 2020) and Graph (Zhu et al., 2021; Guo et al., 2021;
Yasunaga and Liang, 2020) can record the syntactic structure of the program
code and its dependencies such as data-flow and control-flow, which in
principle can capture a richer representation of the code. It is important to
note that we do not evaluate which code representation is better or worse
here. We think that different code representation approaches can work
effectively on APR tasks, e.g., many works (Yuan et al., 2022; Xia and Zhang,
2022) have shown superior performance on repair tasks considering only the
simple Token Sequence approach. Specifically, we believe that the code
representation approach needs to be suitably improved in conjunction with the
programming language repair scenario to perform well on a given task. In the
future, researchers will continue to focus on research on code representation
approaches suitable for program repair scenarios to capture programming
language features more richly.

Figure 5. Five typical input code representation ways.

Finding 9: Context-aware. Context-aware patch generation strategies are widely
used in learning-based APR techniques. However, the different ways of input
code representation for context-aware strategies have yet to be compared in
depth.

In short, context-aware strategies refer to guiding patch generation by
combining bug code and its contextual information, but different strategies
have significant differences in code representation. Here we focus on the most
widely used code representation in the form of Token Sequence. We depict five
typical code representation ways (Fu et al., 2022; Chen et al., 2022, 2021a;
Lutellier et al., 2020; Jiang et al., 2021; Tufano et al., 2019; Ye et al.,
2022; Yuan et al., 2022; Xia and Zhang, 2022) in Fig. 5, which we abbreviate
as CR1, CR2, CR3, CR4 and CR5. CR1: Contextual information used for fixes as
early as the work of Tufano et al. (Tufano et al., 2019). The model input is
just a piece of source code, but the bug location is not marked. The model
does not distinguish between the bug code and the context when translating.
CR2: Chen et al. (Chen et al., 2022, 2021a) distinguish between bug location
and context by adding markers to the bug line locations. Although the model
input is still token sequences, the special markers help the model identify
the bug locations and thus achieve accurate fixes. CR3: Unlike Chen et al.
treat the context and the bug code as one whole input to the encoder, Jiang et
al. (Lutellier et al., 2020; Jiang et al., 2021) feed the bug code and the
context information as two parts of the input to different encoders for
separate processing. The insight behind this is that these two parts of
information may have different weights in the view of the model. The model
should translate the bug code in conjunction with the contextual information
instead of processing the context and the bug code uniformly. CR4 and CR5: CR4
and CR5 are input forms designed for specific models. CIRCLE (Yuan et al.,
2022) borrows the pre-training task for the T5 model to set up the prompt
template input (CR4) for training. AlphaRepair’s (Xia and Zhang, 2022) input
form (CR5) is designed to accommodate zero-shot learning, so it needs to
incorporate CodeBERT’s masked language modeling (MLM) pre-training task to
design the mask template so that the LLM can directly predict the token at the
mask location. However, these different ways of CR were not compared under a
unified baseline, and we have no way of knowing the impact of the different
CRs on the results. In addition, it is an open issue how to design appropriate