Cite as:

Tim A. D. Henderson. How To Evaluate Statistical Fault Localization. Blog. 2018. https://hackthology.com/how-to-evaluate-statistical-fault-localization.html
PDF. WEB.

Note

This is a conversion from a latex paper I wrote. If you want all formatting correct you should read the pdf version.

Note

I now have a pulished paper on this topic. You probably want to read that as well.

Tim A. D. Henderson, Yiğit Küçük, and Andy Podgurski. Evaluating Automatic Fault Localization Using Markov Processes. SCAM 2019.

Introduction

Automatic fault localization is a software engineering technique to assist a programmer during the debugging process by suggesting suspicious locations that may be related to the root cause of the bug. The big idea behind behind automatic fault localization (or just fault localization) is by pointing the programmer towards the right area of the program the programmer will find the cause of the bug more quickly.

One approach to fault localization is Spectrum Based Fault Localization which is also known as Coverage Based Statistical Fault Localization (CBSFL) [1]-[3]. This approach uses test coverage information to rank the statements from most "suspicious" to least suspicious. To perform CBSFL, test cases are run through an instrumented program. The instrumentation collects coverage profiles which report each statement¹ executed during the test run. A test oracle is used to label each execution profile with whether or not the test passed or failed. Such oracles can be either automatic or manual (i.e. a human). The labeled execution profiles are referred to as the coverage spectra.

CBSFL techniques score each program element (location in the program) by its "statistical suspiciousness" such that the most suspicious element has the highest score. The scores are computed by suspiciousness metrics which attempt to quantify the relationship between the execution each program element and the occurrence of program failure.

There have been a great many statistical fault localization suspiciousness metrics proposed [2] since the idea was first proposed by Jones, Harrold and Stasko in 2002 [1]. The majority of the metrics are computed from just a few values: the number of tests \(n\), the number of passing tests \(p\), the number failing tests \(f\), the number of test runs an element \(e\) was executed in \(n_e\), the number of passing test runs an element was executed in \(p_e\), and the number of failing test runs an element was executed in \(f_e\). For instance, using these simple statistics one can estimate the conditional probability of program failure \(F\) given that a particular element \(e\) was executed: \[\begin{aligned} {\textrm{Pr}\left[{F|e}\right]} &= \frac{{\textrm{Pr}\left[{F \cap e}\right]}}{{\textrm{Pr}\left[{e}\right]}} \approx \frac{\frac{f_{e}}{n}}{\frac{n_{e}}{n}} = \frac{f_e}{n_e}\end{aligned}\] While many of the studies in statistical fault localization use more complex formulas [2], [3] (with various technical motivations) most of the metrics are measures statistical association as in the equation above.

The runtime information used to compute the above statistics is commonly referred to as the coverage spectra of the program. Coverage spectra is a matrix \({\bf C}\) where \({\bf C}_{i,j} > 0\) indicates that the program element \(\mathcal{E}_i\) was executed at least once during test \(\mathcal{T}_j\). Additionally, there is an additional "test status" vector \({\bf S}\) where \({\bf S}_{j} = \text{"F''}\) if test \(\mathcal{T}_j\) failed and \({\bf S}_{j} = \text{"P''}\) if test \(j\) passed.

To collect the coverage spectra the program is instrumented to collect a runtime profile of the executed elements. This instrumentation can be done (in principle) at any granularity including: expression, statement, basic block², function, class, file, or package. The statistical methods which make use of spectra are agnostic to their granularity. While the granularity does not effect the statistical computation it changes how the localization results are perceived by the programmer. In the past, programmers have indicated a desire for finer grained results: at statement, basic block, or function level [5] over very coarse grained results at the class, file, or package level.

Some statistical fault localization techniques use additional information to either improve accuracy or provide more explainable results. For instance, work on Causal Fault Localization uses additional static and dynamic information to control for statistical confounding [6]. In contrast Suspicious Behavior Based Fault Localization (SBBFL) uses runtime control flow information (the behavior) to identify groups of collaborating suspicious elements [7]. These techniques leverage data mining techniques [8] such as frequent [9]-[11] or significant pattern mining [7], [12]. When significant patterns are mined metrics (such as statistical fault localization suspiciousness metrics) are used to identify the most significant patterns [7], [13].

Finally, a variety of non-statistical (or mixed methods) techniques for fault localization have been explored [14]-[17]. These range from delta debugging [18] to nearest neighbor queries [19] to program slicing [20], [21] to information retrieval [22]-[24] to test case generation [25]-[27]. Despite differences in the technical and theoretical approach of these alternate methods they also suggest locations (or groups of locations) for the programmer to consider when debugging.

Evaluation Methods

Some of the earliest papers in fault localization do not provide a quantitative method for evaluating performance (as is seen in later papers [28]). For instance, in the earliest CBSFL paper [1] (by Jones et al.'s) the technique is evaluated using a qualitative visualization. At the time, this was entirely appropriate as Jones was proposing a technique for visualizing test coverage for assisting the debugging process. The test coverage visualization was driven by what is now called a statistical fault localization metric (Tarantula). The evaluation visualization aggregated the visualizations all of the programs included in the study.

While, the evaluation method used in the Jones paper effectively communicated the potential of CBSFL (and got many researchers excited about the idea) it was not good way to compare multiple fault localization techniques. In 2005 Jones and Harrold [29] conducted a study which compared their Tarantula technique to 3 other techniques: Set Union and Intersection [30], Nearest Neighbor [19], and Cause-Transitions [31]. These techniques all took unique approaches toward the fault localization problem and were originally evaluated in different ways. Jones and Harrold re-evaluated all 5 methods under a new common evaluation framework.

In the 2005 paper, Jones and Harrold evaluate the effectiveness of each technique by using the technique to rank the statements in the subject programs. Each technique ranked the statements from most likely to be the cause of the fault to least likely. For Tarantula, the statements are ranked using the Tarantula suspiciousness score:³

Definition. Tarantula Rank Score [29]

Given a set of locations \(L\) with their suspiciousness scores \(s(l)\) for \(l \in L\) the Rank Score for a location \(l \in L\) is: \[\begin{aligned} {{\left|{ \left\{ x ~:~ x \in L \wedge s(x) > s(l) \right\} }\right|}} + {{\left|{ \left\{ x ~:~ x \in L \wedge s(x) = s(l) \right\} }\right|}} \end{aligned}\]

For Set Union and Intersection, Nearest Neighbor and Cause-Transitions the statements are ranked using a System Dependence Graph (SDG) [32] technique from Renieres and Reiss [19] who first suggested the ranking idea. The ranks are then used to calculate the Tarantula Rank Score.

In the Jones and Harrold evaluation the authors do not use the Tarantula Rank Score directly but instead use a version normalized by program size:

Definition. Tarantula Effectiveness Score (Expense) [29]

The percentage of program elements that do not need to be examined to find the fault when the elements are arranged according to their rank. Formally: let \(n\) be the total number of program elements, and let \(r(f)\) be the Tarantula Rank Score of the faulty element \(f\) then the score is: \[\begin{aligned} \frac{n-r(f)}{n} \end{aligned}\]

Using the normalized effectiveness score Jones and Harrold directly compare the fault localization effectiveness of each of the considered methods. They did this in two ways. First, they presented a table (Table 2) which bucketed all the buggy versions form all the programs by the percentage given by the Tarantula Effectiveness Score. Second, they presented a figure (Figure 2) which showed the data in Table 2 as a cumulative curve.

The basic evaluation method presented by Jones and Harrold has become the standard evaluation method. Faulty statements are scored, ranked, rank-scored, normalized, and then aggregated over all versions and programs to provide an overall representation of the fault localization method's performance (a few examples: [2], [3], [33]-[36]). While the basic method has stayed fairly consistent, there has been some innovation in the scoring (both the Rank Score and the Effectiveness Scores).

For instance, Wong et al. [34] introduced the most commonly used Effectiveness Score the \(\mathcal{EXAM}\) score. This score is essentially the same as the Expense score except it gives the percentage of elements which need to be examined rather than those avoided.

Definition. \(\mathcal{EXAM}\) Score [34]

The percentage of program elements that need to be examined to find the fault when the elements are arranged according to their rank. Formally: let \(n\) be the total number of program elements, and let \(r(f)\) be the Tarantula Rank Score of the faulty element \(f\) then the score is: \[\begin{aligned} \frac{r(f)}{n} \end{aligned}\]

Ali et al. [37] identified an important problem with the Jones and Harrold evaluation: some fault localization metrics and algorithms rank statements equally. This is captured in the second term in the definition for the Tarantula Rank Score. However, Ali points out that this introduces bias towards algorithms that always assign unique scores (that are close together) rather than those that would score the same group of statement equally. The fix is to instead compute the expected number of statements the programmer would examine if they chose the next equally scored element at random.

Definition. Rank Score

Gives the expected number of locations a programmer would inspect before finding the bug. Formally, given a set of locations \(L\) with their suspiciousness scores \(s(l)\) for \(l \in L\) the Rank Score for a location \(l \in L\) is [37]: \[\begin{aligned} {{\left|{ \left\{ x ~:~ x \in L \wedge s(x) > s(l) \right\} }\right|}} + \frac{ {{\left|{ \left\{ x ~:~ x \in L \wedge s(x) = s(l) \right\} }\right|}} }{ 2 } \end{aligned}\]

Following Ali, we recommend utilizing the above definition for Rank Score over the Tarantula definition.

Parin and Orso [38] conducted a user study which looked at the programmer experience of using a statistical fault localization tool (Tarantula [1]). Among their findings they found that programmers would not look deeply through the list of locations and would instead only consider the first few items. As a result they encouraged studies to no longer report scores as percentages. While some studies still report the percentages most studies are now reporting the absolute (non-percentage) rank scores. Reporting as absolute scores is important for another reason, if percentage ranks are reported larger programs can have much larger absolute ranks for the same percentage rank. This biases the evaluation toward large programs even when the actual localization result is poor.

Steimann et al. [33] identified a number of threats to validity in CBSFL studies including: heterogeneous subject programs, poor test suites, small sample sizes, unclear sample spaces, flaky tests, total number of faults, and masked faults. For evaluation they used the Rank Score modified to deal with \(k\) faults tied at the same rank.

Definition. Steimann Rank Score

Gives the expected number of locations a programmer would inspect before finding the bug when multiple faulty statements have the same rank. Formally, given a set of locations \(L\) with their suspiciousness scores \(s(l)\) for \(l \in L\) the Rank Score for a location \(l \in L\) is [33]: \[\begin{aligned} & {{\left|{ \left\{ x ~:~ x \in L \wedge s(x) > s(l) \right\} }\right|}}\\ & + \frac{ {{\left|{ \left\{ x ~:~ x \in L \wedge s(x) = s(l) \right\} }\right|}} + 1 }{ {{\left|{ \left\{ x ~:~ x \in L \wedge s(x) = s(l) \wedge x \text{ is a faulty location} \right\}}\right|}} + 1 } \end{aligned}\]

Moon et al. [39] proposed Locality Information Loss (LIL) as an alternative evaluation framework. LIL models the localization result as a probability distribution constructed from the suspiciousness scores:

Definition. LIL Probability Distribution

Let \(\tau\) be a suspicious metric normalized to the \([0,1]\) range of reals. Let \(n\) be the number statements in the program. Let \(S\) be the set of statements. For all \(1 \le i \le n\) let \(s_i \in S\). The constructed probability distribution is: \[\begin{aligned} P_{\tau}(s_i) = \frac{\tau(s_i)}{\sum^{n}_{j=1} \tau(s_j)} \end{aligned}\]

LIL uses a measure of distribution divergence (Kullback-Leibler) to compute a score of how different the constructed distribution is from the "perfect" expected distribution. The advantage of the LIL framework is it does not depend on a list of ranked statements and can be applied to non-statistical methods (using a synthetic \(\tau\)). The disadvantage of LIL is it does not indicate programmer effort (as indicated by the Rank Score). However, it may be a better metric to use when evaluating fault localization systems as a component for automated bug repair systems.

Pearson et al. [28] re-evaluated a number of previous results using new real world subject programs with real defects and test suites. In contrast to previous work they made use of statistical hypothesis testing and confidence intervals to test the significance of the results. To evaluate the performance of each technique under study they used the \(\mathcal{EXAM}\) score reporting best, average, and worst case results for multi-statement faults.

T-Score [40] is designed for non-statistical fault localization methods which produce a small set of suspicious statements in the program. To evaluate how helpful these reports are T-Score uses the Program Dependence Graph (PDG) [32], [41] to compute a set of vertices in the graph that must be examined in order to reach any faulty vertex. This set is computed via a breadth first search from the set of vertices in the report. Finally, the score is computed as the percentage of examined vertices out of the total number of vertices in the graph.

Multiple Fault Evaluations

With the exception of LIL, the evaluation methods discussed so far are generally defined to operate with a single faulty location. However, there may be multiple faults or multiple locations associated with a single fault or both. Multiple faults can interact [42] and interfere with the performance of the fault localizer. For evaluation purposes one of the most popular methods is to take either best result [43], the average result [14], [44], or the worst result [43].

Evaluating Other Techniques

One of the challenges with the methods presented so far is they may not work well for evaluating alternate fault localization methods. For instance, information retrieval based localization methods do not necessarily score and rank every program location. Instead they produce a report of associated regions. Jones and Harrold [29] used a synthetic ranking system [19] based on the SDG [32] which in principle could be used in such situation. However, like the T-Score it uses an arbitrary method (minimal dependence spheres) to compute the number of SDG nodes which must be examined.

The LIL method could also potentially be used to evaluate alternative methods. It does not rely on ranking but instead on the suspiciousness scores which it converts into a probability distribution. To support evaluating report based localization the reports are converted to a probability distribution with all locations in the report set to a equal high probability and all locations not in the report set to a tiny probability.

Suspicious Behavior Based Fault Localization [7] requires particular care. These methods are produce a ranked set of "behaviors" which are structured groups of interacting program locations. The structure could be a call invocation structure [45]-[49], a general control flow structure [7], [13], [50], or even an information flow structure [51]. The structures are scored and ranked similar to CBSFL. However, unlike in CBSFL all program locations are not necessarily included. In the past, studies have used a variety of techniques to evaluated the effectiveness including precision and recall [13] and scores based off of the \(\mathcal{EXAM}\) score [7].

Another subtle special case involves comparing statistical techniques which operate on different granularity levels. As mentioned previously, coverage can be collected at any granularity level: expression, statement, basic block, method or function, class, file, and even non-structural elements such as paths. Any of the CBSFL metrics can be used with any of these granularities. However, a single study using any of the previous evaluation methods must keep the granularity consistent. This makes it impossible to compare across granularity levels. This is makes it particularly difficult to accurately compare method level behavioral approaches [45] to CBSFL.

Assumptions

The biggest assumption that all evaluation models make is so-called perfect bug understanding which assumes programmers will recognize a bug as soon as they "examine" the faulty location. This assumption is obviously false [38]. However, it continues to be a useful simplifying assumption for evaluation purposes of the localization algorithms. From the standpoint of automated fault localization there are really two tasks: 1) finding the fault and 2) explaining the fault. Assuming perfect bug understanding is reasonable for evaluating a tools performance on task 1. However, there is the important caveat that programmers need more assistance at task 2. As a research community we do not currently have a standard method for evaluating our algorithmic performance on task 2.

The second assumption is that programmers will follow the rank list or suspiciousness scores when debugging a program using a fault localization tool. This assumption is obviously false as well [38]. A programmer may follow the list for the very first item and even the second but where they go from there is likely only partially influenced by the list. The bigger influence will be from the conclusions they are drawing from what they learn upon inspecting each location.