You Cannot Fix What You Cannot Find! An Investigation of Fault Localization Bias in Benchmarking Automated Program Repair Systems

I Introduction

Automated program repair (APR) holds the promise of reducing manual debugging effort by automatically generating patches for defects identified in a program. In production, APR will drastically reduce time-to-fix delays and limit downtime. In a development cycle, APR can help suggest changes to accelerate debugging. In the literature, there are two distinct repair scenarios: (1) fixing syntactic errors, i.e., cases where code violates some programming language specifications and (2) fixing semantic bugs, i.e., cases where implementation of program behaviour deviates from developer’s intention . The latter requires Fault Localization (FL) through execution of test cases. It is the scope of this paper.

Once a fault is arosen, most recent APR systems follow the same basic pipeline as shown in Figure 1: (1) fault localization (FL), (2) patch candidate generation, and (3) patch validation. The FL step identifies an entity in a program as the potential fault location. In patch generation, given a fault location, the APR system modifies the program, i.e., creates a patch. The last step assesses whether the patch actually fixes the defect. If the patch is not regarded as a valid patch, the second and last steps are repeated until a valid patch is generated or the termination condition is satisfied. To increase the chances of finding a valid patch, the process is iterated over all suspicious code locations ranked by FL tools.

In the repair pipeline, APR systems generally focus on the patch generation step, but tend to use similar strategies for fault localization and patch validation. To the best of our knowledge, most of the current state-of-the-art APR approaches leverage test suites to perform fault localization and patch validation. For fault localization, the systems rely on a testing framework such as GZoltar , and a spectrum-based fault localization formula , such as Ochiai . Eventually, bug fixing performance is measured by counting the number of bugs for which the system can generate a patch that passes all test cases. Such patches are claimed to be valid.

Nevertheless, given the growing interest in APR among software engineers, it is important to ensure that the research outputs are relevant and well assessed in terms of reliable performance for practitioners. In this respect, the APR research community has already started to reflect on the acceptability and correctness of the patches generated by APR tools. Researchers raised the concern of overfitting patches: those are generated patches that can pass the validating test cases, but may actually not be the semantically-correct patches for repairing the defect.

Since then, assessment of APR approaches in the literature attempts to provide information on the number of generated patches that are plausible (i.e., they make the programs pass all the test cases) and the number of patches that are correct (i.e., they are equivalent to the patches that were actually submitted by the program developers). Table I provides an example of assessment results excerpted from the paper describing SimFix , one of the most recent state-of-the-art works on APR that was tested on the Defects4J programs. Based on data reported in this table, researchers explicitly rank the APR systems, and use this ranking as a validation of new achievements in program repair.

Unfortunately, our own experience in developing and assessing APR tools has proven that this comparison is non-trivial, and could further be largely biased due to a non-consideration of important details regarding the FL step. Indeed, recall that an APR technique cannot attempt to generate the correct patch unless the FL step can successfully identify the target buggy code locations in a program. Thus, FL accuracy across repair pipelines can impact, either by boosting or degrading, the performance of an APR system.

For example, SimFix and ACS , although they have been developed by the same research group, are evaluated on different versions of a fault localization technique without discussing the impact of such a change in the experimental configuration. As another example bias, while most APR techniques simply integrate off-the-shelf fault localization tools in the repair pipelines, in some experiments, such as for HDRepair , its authors make the assumption that the buggy method is known. Unfortunately, this assumption gives an important advantage as the list of suspicious code statements is limited and likely to include the buggy statement, thus leading to overestimation of the performance.

Similar to the “overfitting” study, which helped to improve the assessment criteria of APR tools, our work aims at highlighting the potential biases in comparing different APR approaches without any consideration of implementation variations of the FL step. Overall, our investigation into the relationship between fault localization performance and APR tool performance seeks to provide answers to the following research questions (RQs):

How do APR systems leverage FL techniques? We first investigate FL techniques used in APR systems in the literature. This reveals which FL tool and formula are integrated for each APR system. We examine implementation details of each APR system, and/or directly ask the authors of the technique to clarify FL configuration, e.g., which level of detection granularity is considered, and how many suspicious locations are considered.

How many bugs from a common APR benchmark are actually localizable? After aggregating APR performance data reported in the literature, we note that 246 bugs (in benchmark Defects4J) have not yet been fixed by any state-of-the-art APR tool. Given that researchers scarcely discuss the reasons behind repair misses, we assess, with this research question, our intuition that FL is possibly one of the challenging steps in the repair pipeline.

To what extent APR performance can vary by adapting different FL configurations? We implement and make publicly available kPAR, a straightforward fix pattern-based APR system, and record its performance under various configurations to serve as a comparable baseline for future research.

Eventually, we make the following contributions:

We expose a hidden bias throughout the comparison of APR tools in the literature, and present more reliable performance comparisons for current state-of-the-art.

We build and make publicly available an easy-to-configure fault localization toolkit that can be adopted in APR pipelines for Java programs.

We provide a refined benchmark for evaluating the performance of APR systems with respect to those bugs that can actually be localized.

We implement and make publicly available a baseline APR system with its different performance metrics for different FL configurations.

Our replication package, including kPAR, is available at:

II Background

We recall how fault localization is important in an APR pipeline, and describe how current APR systems are assessed.

In APR systems, fault localization (FL) is not only the first step but also seriously affects the performance of the systems. Given a buggy program (with its passing and failing test cases), an FL tool is leveraged during the FL step to identify the suspicious buggy code locations as described in Figure 1. The granularity of suspicious locations can be a file, method, or line. Ideally, the location should be both precise and accurate. If the precision is low (e.g., the granularity is broad such as file), the patch generation step needs to explore a large space of candidate patches. If the accuracy is low (e.g., the FL step provides a wrong fault location), the subsequent step generates patches for the non-faulty program entity.

Spectrum-based fault localization (SBFL, also referred to as coverage-based fault localization) is one of the most popular FL techniques used in APR systems. This technique applies a ranking metric to detect faulty code locations by leveraging the execution traces of test cases to calculate the likelihood (based on suspiciousness scores) of program entities to be faulty. The ranking metric is applied to calculate suspiciousness scores for program entities (such as program statements as well as code lines ).

In the APR literature , Ochiai is widely used as the ranking metric of SBFL. Many empirical studies have indeed shown that Ochiai is one of the most effective techniques in localizing the root cause of faults in object-oriented programs. Ochiai computes suspiciousness score of a given source code statement $s$ following the formula of Equation 1:

where $failed(s)$ and $passed(s)$ denote respectively the number of failing and passing tests that executed statement $s$, while $failed(\neg s)$ is the number of failing tests that do not execute statement $s$. In practice, FL tools eventually report a ranked list of statements associated with the suspiciousness scores.

II-B APR Performance Assessment

The current practice of APR studies often evaluates the performance of APR systems based on the number of successfully fixed bugs . We can determine whether a generated patch is successful by counting the number of passing test cases. If a patch can pass all the given test cases (both passing and failing cases given for the buggy version), it is regarded as a successful patch.

However, the number of passing test cases may not correctly assess the effectiveness of generated patches. Even if a generated patch can pass all test cases, it might break a necessary behavior or introduce other faults, which are not covered by the given test suite . Moreover, a developer may not accept the patch due to several reasons such as coding convention . These patches are often called plausible patches since it needs further investigations to check whether they are correct patches acceptable to developers. In the literature, correctness is assessed manually by comparing the generated against the developer-provided patch available in the benchmark.

Similarly, selecting a FL technique could be another issue since it can make the performance assessment biased. Our investigations will use Table II as a starting point to highlight the problem of FL bias. This table shows the number of fixed bugs out of the bugs in the Defects4J benchmark, which are reported by the authors of the current state-of-the-art APR tools in the literature. The results of jGenProg, jKali and Nopol are extracted from the experimental data reported by Martinez et al. . The results of other tools are collected from data reported by papers’ authors in the literature.

III Experimental Setup

Our experiments are based on common tool-support and processes used in the literature. We clarify the experiment design in this section as the basis for understanding the implementation and the conclusions that we draw.

Although state-of-the-art fault localization tools identify suspicious code lines, this information spans across other code entities such as methods and files, which can be sufficient for APR mutations. Thus, to compute the performance of fault localization techniques on a benchmark, we consider different granularities of fault locality at the file, method and line levels similar to the fault locality defined by Lucia et al. :

File: At this level, we consider that the faulty code is accurately localized if an FL tool reports any line from the buggy code file as suspicious.

Method: At this level, we consider that the faulty code is accurately localized if any code line in the buggy method is reported by an FL tool as suspicious.

Line: At this level, we consider that the faulty code is accurately localized if suspicious code lines reported by an FL tool contain any of the buggy code lines.

III-B Identification of Correct Fault Locality

Our objective is to identify which reported suspicious code position is correct, following the above three levels of fault locality granularity. In practice, FL tools produce a ranked list of suspicious lines while ground truth data include several code lines as buggy lines as well. At a given granularity level, if the bug is localized (i.e., there is a match between the suspicious code line and the ground truth fault locations), we record the associated position of the correct fault locality within the ranked list of suspicious code locations. Since a bug position could span over several lines, methods, and even over several files, the bug is considered to be correctly localized by an FL tool as long as any reported suspicious code line can match the ground truth bug locations with the corresponding granularity.

Concretely, we first use the following defintion of bug locations. The locations of a bug in a faulty program are defined as a bug position set: $BPos$ = {$bPos_{1}$, $bPos_{2}$, …, $bPos_{n}$}, (n $>=$ 1), where $bPos_{i}$ is a tuple of $(fName$, $Methods$, $Lines)$. For each location, $fName$, $Methods$, and $Lines$ are a file name, a set of methods, and a list of line numbers, respectively, of a bug location. $Methods$ could be $\emptyset$ if the bug is not located in any method in a program. This kind of bugs can be related to a Type Declaration or Field Declaration in Java code. Math-12 in the Defects4J dataset is an example, which is fixed by inserting an interface Serializable into the type declaration .

We then check whether a ranked list of suspicious lines by an FL tool can identify bug locations based on the following definition. Let $SuspL=\{suspL_{1},suspL_{2},\ldots,suspL_{m}\}$ be a list of suspicious lines that are reported by an FL tool and ordered by suspiciousness scores. $suspL_{i}$ is a tuple of $(fName$, $lineNum$, $rIdx)$, where $lineNum$ is the line number of the code in a file (i.e., $fName$) that is suspected to be the bug location, and $rIdx$ is the index (i.e., rank) of the line within $SuspL$. If a suspicious line $suspL_{i}$ ($i\in[1,m]$) matches any bug location ($BPos$) at a given granularity before other suspicious lines, it is considered that the FL tool successfully identifies a bug location at the given granularity. Otherwise, if there is no suspicious line matching a bug location at a given granularity, the fault is considered as non-localizable at this fault locality granularity.

III-C Dataset and Automatic Testing Toolset

Our study requires execution of fault localization on a reliable dataset. In this work, we select the Defects4J dataset as it includes test cases for buggy Java programs with the associated developer fixes. This dataset has furthermore been used by all recent state-of-the-art APR systems targeting Java programs. Table III summarizes statistics on the number of bugs and test cases available in the version 1.2.0 of Defects4J that we use in this paper.

Overall, the dataset includes 395 bugs and 22,954 test cases. To automate the execution of these test cases for each bug, we rely on the GZoltar framework for automatic debugging of Java applications. GZoltar executes the test cases and produces coverage matrices providing information on which test cases passed, which failed, which statements were executed when running each test case, etc. Based on this information, FL techniques can be applied for ranking suspicious code locations which are likely to be the faulty code. For the purpose of our study, we have implemented on-top of GZoltar 41 common ranking metrics for fault localization. Given that Gzoltar has been used by several APR tools in the literature, we expect that our easy-to-configure fault localization toolkit will serve the research community to parameterize fault localization in an APR pipeline.

Our experiments further considered two different versions of GZoltar. The first one is the GZoltar version 0.1.1, which is already used in state-of-the-art APR systems, such as Astor , FixMiner , ACS , ssFix and CapGen among others. On the other hand, the GZoltar version 1.6.0 is used in SimFix since it was recently shown to be effective .

III-D Implementation of a Baseline APR System

Ideally, we should consider exploring an existing APR system for drawing our reference performance. Unfortunately, we face several challenges: (1) only a few research groups openly release the code or even implementation details of their APR systems; (2) repair steps are often tightly coupled together in implementation, which requires substantial engineering effort for experimental adaptation; (3) proposed approaches generally mix several contributions which are hard to isolate.

We, therefore, propose to implement and share a baseline repair system based on a state-of-the-art publication on Java program repair. We select PAR for its simplicity and the straightforward replication that can be carried out on the basis of details from the relevant research report. We build kPAR, which leverages patterns that have been learned from the commonalities among 60,000 human-written patches. Six common patterns from the initial version of PAR has been implemented in kPAR. We further record the performance of kPAR in repair scenarios involving four different configurations of the fault localization step.

IV Study Results

We now provide key findings for the related questions that are investigated in this work.

To characterize how FL tools are integrated into APR pipelines, we carefully assess evaluation reports in the literature and investigate the source code (when it is available) of 14 state-of-the-art APR systems which have been evaluated on the Defects4J benchmark. Table IV enumerates the studied tools along with the information collected. We focus on the testing framework that is used and its version, the FL ranking metric that is considered to compute the suspiciousness scores, the granularity of fault locality that authors focused on, and the extra information that authors use to supplement FL.

Among the 14 APR tools that are investigated, 10 leverage GZoltar as the automated testing toolset in the repair pipeline. Except for SimFix, which uses a recent version of the framework, all others use earlier versions (8 tools use version 0.1.1, while Nopol uses an even older version, i.e., 0.0.1). Thus, unless otherwise stated, the experiments in this work are performed on the widely used version 0.1.1 of GZoltar.

Eleven out of the 14 APR tools are explicitly known to rely on Ochiai for computing the suspiciousness scores in the fault localization process. This popularity of Ochiai is backed up by empirical evidence on its effectiveness to help localize faults in object-oriented programs as highlighted by several fault localization studies . A recent work by Pearson et al. has even shown that Ochiai outperforms current state-of-the-art ranking metrics, or at least offers similar performance measures. In the latter part of this study, we replicate their work to ensure that our implementation of the ranking techniques is reliable. It should also be noted that although ELIXIR and SketchFix do not report the test framework that they use, they explicitly mention using Ochiai for fault localization.

With respect to the granularity of fault locality, only LSRepair focuses on the method-level granularity to detect and fix bugs. Other APR systems require information on bugs at the line level to proceed with patch generation. Considering methods as the granularity of fault locations implies that such faults that are located outside methods (e.g., type declaration faults ) will not be addressed. However, this granularity may offer a time advantage: when several statements in a single method are reported as suspicious locations, LSRepair, unlike other APR systems, is not required to iteratively try each location for generating patch candidates. Finally, it should be noted that FL tools do not offer the same accuracy in identifying faulty locations at different granularity levels (cf. Section IV-B), making method level granularity appealing for limiting unnecessary trials on fault positive locations.

It is further noteworthy that four APR systems leverage supplementary information to assist the fault localization step and improve accuracy. The impact of this assistance is unfortunately never discussed when comparing performance among state-of-the-art repair approaches. Typically:

HDRepair assumes that the faulty methods are known: the fault localization step therefore focuses on ranking the lines inside the method, thus leaving out noisy statements that other APR tools are considering. This artificially reduces the probability to produce overfitting patches for HDRepair, and even increases the chance to generate a correct patch before any execution timeout.

ssFix prioritizes statements from the stack trace of crashed programs that are executed before those statements that are ranked by the FL tool.

ACS uses predicate switching and refines the suspicious code locations list since the repair is focused on faulty conditional statements.

SimFix applies a test case purification approach to improve the accuracy of FL step before patch generation.

Although these extra steps, which are taken to supplement FL step, could be justified intuitively, the community needs to clearly investigate their impact, in order to enable fair comparisons among the repair techniques themselves. Indeed, given that APR systems are currently compared with respect to the number of bugs that are correctly fixed, it is important that the research community reflects on what are the key contributions for explaining APR performance: for example, by counting numbers of correct patches, several programs may not be repairable by a given APR system simply because the fault is not accurately localized by the implemented FL step.

IV-B Localizability of Defects4J Bugs

In a recent work, Koyuncu et al. have reported that 136 bugs in total from the Defects4J dataset have already been associated to a plausible patch that was generated by at least one APR system from the literature. Patches for 83 bugs have even been validated as correct patches by researchers. Considering this data that we complement with the performance realized by another recent APR tool, namely LSRepair, we conclude that $\sim$62% (246/395) of Defects4J’s bugs have never seen a plausible patch automatically generated by the state-of-the-art in APR. Although a recent empirical study has suggested that current APR systems cannot repair hard and important bugs, our intuition is that there might be a more practical issue related to the localizability of Defects4J defects:

How many faults in the Defects4J benchmark can actually be localized by current automated fault localization tools?

We consider the most common scenario of fault localization scenario from the APR literature: GZoltar is used for automated test execution, and Ochiai for computing suspiciousness scores. Test execution is performed with the test cases provided in the Defects4J benchmark. Table V provides quantitative details on the localizability of bugs at different levels of fault locality granularity (i.e., file, method and line). Experiments are performed with two distinct versions of GZoltar.

In this experiment, we consider a bug to be localized as long as the faulty code is listed among the suspicious statements reported by this fault localization tools. Considering the most common configuration in the literature (GZoltar version 0.1.1 and “Line” granularity level), up to 132 (= 395 - 263) bugs in Defects4J are not localized. The number of bugs that are not localized decreases to 74 (= 395 - 321) when the coverage matrices are produced with GZoltar version 1.6.0. This result suggests that with GZoltar version 1.6.0, APR systems have an opportunity attempt the fix of 58 more bugs.

RQ2$\blacktriangleright$One third of bugs in the Defects4J dataset cannot be localized by the commonly used automated fault localization tool. Nevertheless, the recent version of GZoltar provides coverage information that helps localize more than 50 bugs, which may have never been considered in validation trials of early APR systems. Besides Ochiai, we have attempted to localize bugs in the Defects4J benchmark by using six other ranking metrics to compute suspiciousness scores. Table VI presents the number of bugs localized by the different ranking metrics. We consider the cases where the actual fault location is reported at the Top-1 position of the suspicious code locations, and among the Top-10 positions. Results for Top-50, Top-100, Top-200 and all localized are also made available in the replication package. The results show that fault localization performance is consistent among the different ranking metrics.

Only 45 bugs can be accurately localized with Ochiai at the first suspicious line location. 140 and 214 bugs can be localized at Top-10 and Top-100 positions. Actually, many APR systems only focus on generating patches iteratively based on a part of the list of suspicious code locations. For example, for SketchFix , authors explicitly declare to consider only the top-50 most suspicious statements in the ranked list, while in ELIXIR , up to the top-200 suspicious locations are considered.

IV-C Impact of Effective Ranking in Fault Localization

Automated fault localization produces a ranked list of suspicious code locations that APR tools must iteratively consider for patch generation. To assess to what extent effective ranking (i.e., placing the actually faulty code locations at the top of the list), we propose to investigate the correlation between the rank of bug localization in the suspicious lists and the ability of state-of-the-art systems to be able to repair it.

Table VII summarizes the list of all bugs, from the Defects4J benchmark, for which a plausible patch has been generated by one of the 14 state-of-the-art APR systems considered in this study. For each bug, we indicate the rank of the bug location within the ranked list of suspicious locations provided by the fault localization for different localization granularities. Experiments are done using the Ochiai ranking metric, but with two versions of GZoltar for computing the test coverage matrices. The raw data, including for other ranking metrics, are available in our replication package.

We propose to compute the distributions of positions across subsets of bugs for checking correlations between the localization ranking positions and the ability of APR systems to fix the bugs. Thus, we normalize bug localization positions by computing reciprocal positions based on the following formula:

where $bug_{pos}$ refers to the position of the actual bug locationIf several lines are concerned by the bugs, we consider the first time any of these lines appear as the bug position (cf. Section II). in the ranked list of suspicious locations reported by the FL step. If the bug location can be found in the higher position of the ranked list, the value of $Reciprocal_{pos}$ is closer to 1. Similarly, the value of $Reciprocal_{pos}$ trends to 0 when the bug location is at lower positions in the list of suspicious locations. This value is set to 0 when the bug cannot be localized by the FL tool (i.e., $bug_{pos}=0$). In addition, for the purpose of our experiments, we consider three sub-classes of bugs:

correctly fixed bugs: these are bugs for which a correct patch has been provided by at least one APR tool.

overfitting-fixed bugs: these are bugs for which one or more plausible patch has been generated, although none has been found to be correct.

unfixed bugs: these are bugs for which no plausible patch has ever been generated by any APR system. Due to space limitation, localization data for these bugs are only available in the replication package.

Figure 2The bug positions before being reciprocated shown in the figure are localized by GZoltar 0.1.1 with Ochiai. shows the distribution of reciprocal positions for the three classes of bugs at the file, method, line granularity of fault locality. It clearly appears that correctly-fixed bugs are more accurately localized than others: i.e., their location precisions are higher in the ranked list of suspicious locations by FL tools. On the other hand, unfixed bugs tend to be those that are poorly localized: even at the file level, FL tool show low performance in localizing such bugs.

RQ2$\blacktriangleright$APR tools are prone to correctly fix the subset of Defects4J bugs that can be accurately localized. We further observe from the data in Table VII that a few APR systems report patches for some bugs even though they cannot be localized (at the line level) with the configuration of Ochiai/GZoltar 0.1.1. There are various justifications to this phenomenon:

Improved version of the fault localization step - Chart-20 cannot be localized with GZoltar 0.1.1 and Ochiai, but is reported to be fixed by tools such as SimFix and ssFix. Our investigations show that SimFix has used a recent version of GZoltar (1.6.0), which is capable of localizing Chart-20 among other bugs that were not localizable. ssFix on the other hand indeed uses GZoltar 0.1.1 but do not consider only the results of the FL tool: statements in the stack trace of crashed programs are also considered as potential fault locations.

Targeted localization - HDRepair can fix Lang-6, which is not localized with Ochiai/GZoltar 0.1.1, because this APR system assumes that the faulty method is known, and thus directly ranks the restricted set of statements in this method.

Coarse-grained repair - LSRepair can fix four bugs which cannot be localized at the line granularity. This is due to the fact that LSRepair requires only fault localization at the method level, which is not a bias per se.

Non-explicit fault localization process - SketchFix, JAID, and ELIXIR correctly fix some bugs that are not localized under the proposed configuration. Unfortunately, besides the lack of details in their associated research reports, the source code of these tools was not made available for further investigation. Chart-8 is another example that is not localizable by using Ochiai/GZoltar 0.1.1. This specific un-localizability problem was recently raised by Yuan and Banzhaf as well as Martinez et al. . Nevertheless, CapGen, ELIXIR and SketchFix are reported to have fixed this bug.

RQ3$\blacktriangleright$APR systems do not fully disclose their fault localization tuning parameters, thus preventing reliable replication and comparisons. Given the bias that can be introduced by unlocalizable bugs being fixed by specific tweaking, which are not clearly outlined by the authors, we propose to count the numbers of bugs that are fixed by APR systems among those bugs that are known to be localizable. Table IX thus represents an updated version of Table II where performance can be compared on the same basis. To illustrate the differences between the two comparison tables, we compute three scores: (1) NPFB: number of plausibly-fixed bugs, (2) NCFB: number of correctly-fixed bugs, and (3) P3C: probability of plausible patch correctness.

Figures 3(a) and 3(b) illustrate the differences in respectively NPFB and NCFB scores when considering all bugs vs only localizable bugs. We note that all tools may produce some plausible patches that are plausible even for non-localizable bugs. This finding suggests that the test cases in Defects4J are insufficient since it is possible for APR systems to change non-faulty code locations and still produce patches that make the faulty program pass all test cases. On the other hand, five APR systems cannot produce any correct patches for bugs that are not localizable. ACS, ELIXIX and SimFix can correctly fix bugs that are not localized with GZoltar 0.1.1, suggesting extra impact with an improved version of the fault localization step. On the other hand, LSRepair can fix bugs that are not localized at the line level because method level fault localization is sufficient for its execution.

Finally, Table VIII establishes the re-ranking of APR systems in terms of the P3C scores when focusing on localizable bugs. When focusing on localizable bugs, state-of-the-art APR systems can correctly overall fix fewer bugs than reported in the literature.

IV-D Evaluating kPAR with Specific FL Configurations

kPAR is an open-source APR system that we have built to provide a baseline for comparisons of different FL configurations. We evaluate its performance against the Defects4J benchmark with the following four different configurations of the fault localization step:

Normal_FL gives a ranked list of suspicious code locations identical as reported by a given FL tool.

File_Assumption assumes that the faulty code files are known. Suspicious code locations from Normal_FL are then filtered accordingly. In other words, locations in the known buggy files are selected and locations in other files are ignored.

Method_Assumption assumes that the faulty methods are known (the same assumption with ). Only locations in the known methods are selected and locations in other methods are ignored.

Line_Assumption assumes that the faulty code lines are known. No fault localization is then used.

These configurations have an order with respect to a potential size of the search space. Conceptually, the relationships between them hold $P(|Normal\_FL|)\leq P(|File\_Assumption|)\leq P(|Method\_Assumption|)\leq P(|Line\_Assumption|)$, if we consider each configuration as producing a set of suspicious locations, where $P(|\ast|)$ is the probability that the relevant fault locations are included in the suspicious list.

To facilitate comparison with existing repair systems, we leverage the standard GZoltar 0.1.1 and Ochiai in the following experiments. For each bug, we apply kPAR at most three hours (wall-clock time); we assume that it fails to fix a given bug if it takes more than three hours. We set this value according to the experimental setup of Astor . Table X summarizes the number of bugs fixed by kPAR with the different FL configurations.

As shown in Table X, kPAR can fix its maximum number of bugs when the accurate fault locations are provided (i.e., with Line_Assumption). With this assumption, kPAR can correctly fix 36 bugs in Defects4J, a record performance in the literature (not accounting for the bias in the fault localization step).

Figure 4 further details which bugs are fixed in the different configurations. First, we note that all bugs fixed with a given localization configuration are also fixed by any of the relatively more accurate fault localization configurations. Thus, with the File_Assumption configuration, kPAR can fix not only all bugs that were already fixed with the Normal_FL configuration but also can now fix four more bugs. By examining the case of those four bugs, we figure out that, in the case of two bugs (i.e., Cl-4 and T-19), the faulty locations were ranked very low in Normal_FL, leading to an execution stop due to timeout. For the remaining two bugs (i.e., C-26 and Moc-29), however, in Normal_FL, kPAR is led to consider first some irrelevant suspicious statements that made kPAR to generate plausible patches that are not correct. Given that the repair process stops when a plausible patch is produced, there is no opportunity with Normal_FL to try all suspicious statements.

When filtering the set of suspicious locations with Method_Assumption, kPAR can fix one more bug (i.e., Cl-10), which could not be fixed by other two less confined FL configurations (i.e., Normal_FL and File_Assumption) before the time-out. Finally, when assuming that the fault locations are known (i.e., Line_Assumption), kPAR can further fix 13 bugs. These could not be fixed in other three less confined configurations. Among the 13 bugs, seven bugs (i.e., C-8, Cl-40, Cl-70, L-6, L-22, L-24, and T-26) are not even localizable using Ochiai/GZoltar 0.1.1; two bugs (i.e., Cl-18 and Cl-70) are not fixed due to execution timeout; one bug (i.e., M-82) is not fixed in other three configurations since the proposed plausible patches are incorrect; three bugs (i.e., C-14, C-19 and M-4) are partially fixed in the other three FL configurations since they have several faulty code fragments.

RQ3$\blacktriangleright$Accuracy of fault localization has a direct and substantial impact on the performance of APR repair pipelines. We examine the bug Chart-14 from the Defects4J dataset, which involves four fault code locations . If we regard those as four sub-bugs, each one can be correctly detected and fixed by kPAR using the Normal_FL configuration. However, if the exact faulty statements are unknown, kPAR (as current APR tools) iteratively mutates suspicious statements one by one in the ranked list. Even if any one of them is correctly fixed, there are still three failed tests, meaning that the generated patch (even if was a correct patch) will not even be considered as a plausible patch.

Considering a patch that partially passes some previously-failing test cases (without introducing new failing test cases) may nevertheless be harmful as it can prevent the generation of a fully correct patch. For example, Chart-4 is a single-location bug that makes 22 test cases fail . Before generating the correct patch, kPAR had generated patches that made the program pass subsets of the test cases.

Other bugs, such as Math-72, on the other hand include multiple faulty locations that fail on the same test case. Although kPAR could generate correct patches for each faulty location, the fix process of kPAR prevents a full fix of this bug. If the test suite can be automatically augmented with differentiating test cases for each fault location, an APR system would be more successful as suggested in .

V Discussion

Our study draws a number of conclusions that we reformulate into guidelines for assessing APR systems. We further enumerate the associated threats to validity before discussing the related work.

Full disclosure of FL parameters. Given that many APR systems do not release their source code, it is important that the experimental reports clearly indicate the protocol used for fault localization. Preferably, authors should strive to assess their performance under a standard and replicable configuration of fault localization.

Qualification of APR performance. To ensure that novel approaches to APR are indeed improving over the state-of-the-art, authors must qualify the performance gain brought by the different ingredients of their approaches.

Patch generation step vs Repair pipeline. There are two distinct directions of repair benchmarking that APR researchers should consider. In the first, a novel contribution to the patch generation problem must be assessed directly by assuming a perfect fault localization. In the second, for ensuring realistic assessment w.r.t. industry adoption, the full pipeline should be tested with no assumptions on fault localization accuracy.

Sensitivity of search space. Given that fault localization produces a ranked list of suspicious locations, it is essential to characterize whether exact locations are strictly necessary for the APR approach to generate the correct patches. For example, an APR system may not focus only on a suspected location but on the context around this location. APR approaches may also use heuristics to curate the FL results.

V-B Threats to Validity

A threat to external validity of our study is that we focus on the localizability of bugs in the Defects4J dataset, which target Java code and may not include sufficient test cases. This threat is however limited given that we investigate performance differences. Threats to internal validation include the use of a single automatic testing framework, namely GZoltar (Not all APR systems in the literature use it to localize faults.), and the selection of the 14 state-of-the-start APR systems. These threats are mitigated by the fact that we ensured that these choices are common among the APR literature.

V-C Related Work

The software development practice is increasingly accepting generated patches . Recently, various directions in the literature have explored to contribute to the advancement of automated program repair . We now discuss the few related studies that attempt to investigate fault localization in relationship with APR.

Qi et al. have evaluated the effectiveness of FL tools by using APR performance as a proxy. Their study proposed the NCP score as the effectiveness metric. The results show that a specific FL ranking metric (Jaccard ) outperforms other metrics. Our study, however, reveals that the common technique used in APR is still Ochiai. Yang et al. studied the usage of FL techniques in APR systems by investigating two different algorithms of how to interpret the results of FL techniques: (1) the rank-first algorithm based on suspiciousness rankings of statements, and (2) the suspiciousness-first algorithm based on suspiciousness scores of statements. They ran Nopol to compare NCP scores, repair time, and patch diversity of the two algorithms. The study concludes that the suspiciousness-first algorithm is more effective for APR systems. The above two studies, however, do not consider whether the patches generated by APR tools are correct or plausible while our study examines how FL techniques affect the quality of patches generated by APR systems.

The literature also includes work on the impact of the fault space, although it does not clarify how FL tools affect the performance of APR systems. Wen et al. investigated the influence of the fault space on the success of finding correct patches by the APR tool. The fault space is defined as a ranked list of suspicious entities in a program. They examined both plausible and correct patches. However, their work is limited to evaluating a single APR tool, GenProg and a single FL technique, Ochiai while our study evaluates and compares 14 different APR systems. Our study further considers the exact location of faults and its correlation with the possibility of generating plausible patches. Finally, our study targets unveiling biases among APR systems.

To the best of our knowledge, our work is the first time to systematically study to what extent FL techniques impact the performance of automated program repair pipeline.

VI Conclusion

The momentum of research in automated program repair is a decisive opportunity for the software engineering research community. Every couple of months, a new APR system is proposed in a race to fix more bugs automatically. Unfortunately, validation of these systems often have only the dataset in common: important parameters such as the fault localization settings are eluded, leading to biased comparisons among the state-of-the-art. Our investigations into these biases call for new guidelines for assessing and reporting on the performance of APR systems. In particular, our replication package includes a full dissection of the Defects4J benchmark in terms of fault localization, a light-weight and tuneable fault localization toolkit, as well as a baseline Java APR system to encourage fair and reproducible experiments.

Acknowledgements

This work is supported by the Fonds National de la Recherche (FNR), Luxembourg, under projects RECOMMEND 15/IS/10449467 and FIXPATTERN C15/IS/9964569.

References