Evaluating data-flow coverage in spectrum-based fault localization
Henrique Lemos Ribeiro Higor Amario de Souza Roberto Paulo de Andrioli Araujo Marcos Lordello Chaim Fabio Kon







Evaluating data-flow coverage in 
spectrum-based fault localization
    

Henrique L. Ribeiro, Roberto P. A. de Araujo, Marcos L. Chaim
Software Analysis and Experimentation Group — SAEG

School of Arts, Sciences and Humanities

University of São Paulo

{henriquelemos,roberto.araujo,chaim}@usp.br

Higor A. de Souza, Fabio Kon
Department of Computer Science

Institute of Mathematics and Statistics

University of São Paulo

{hamario,kon}@ime.usp.br


    Received: date / Revised version: date
================================================================================================================================================================================================================================================================================================================================================================================================




Background: Debugging is a key task during the software development cycle. Spectrum-based Fault Localization (SFL) is a promising technique to improve and automate debugging. SFL techniques use control-flow spectra to pinpoint the most suspicious program elements. However, data-flow spectra provide more detailed information about the program execution, which may be useful for fault localization. Aims: We evaluate the effectiveness and efficiency of ten SFL ranking metrics using data-flow spectra. 
Method: We compare the performance of data- and control-flow spectra for SFL using 163 faults from 5 real-world open source programs, which contain from 468 to 4130 test cases. The data- and control-flow spectra types used in our evaluation are definition-use associations (DUAs) and lines, respectively. 
Results: Using data-flow spectra, up to 50% more faults are ranked in the top-15 positions compared to control-flow spectra. Also, most SFL ranking metrics present better effectiveness using data-flow to inspect up to the top-40 positions. The execution cost of data-flow spectra is higher than control-flow, taking from 22 seconds to less than 9 minutes. Data-flow has an average overhead of 353% for all programs, while the average overhead for control-flow is of 102%. 
Conclusions: The results suggest that SFL techniques can benefit from using data-flow spectra to classify faults in better positions, which may lead developers to inspect less code to find bugs. The execution cost to gather data-flow is higher compared to control-flow, but it is not prohibitive. Moreover, data-flow spectra also provide information about suspicious variables for fault localization, which may improve the developers' performance using SFL.



Fault localization; Spectrum-based; Debugging; Structural testing; Data-flow; Control-flow.





§ INTRODUCTION


Testing and debugging are among the most expensive tasks during the development cycle 
<cit.>. Debugging consists of locating and fixing program bugs (faults). 
These activities are accomplished with the help of static (e.g., 
source code, bug reports) and dynamic information (e.g., variable values, test results). 
Nevertheless, a developer may spend too much time 
trying to understand and  locate a bug, affecting considerably the overall cost
of the software. This is so because fault localization is in general a tedious, time-consuming, 
and error-prone manual task <cit.>. Several fault localization techniques have been 
proposed to improve the developer's productivity during the debugging process <cit.>.

Spectrum-based fault localization (SFL) is a promising debugging technique due to its relative low overhead in test execution time. SFL techniques use data collected 
during a test suite execution, called program spectra, to infer which source code elements are more likely to contain a bug <cit.>. 
Program spectra[Henceforth, we use indistinctly the terms  spectra 
and coverage.] comprise program elements, from fine-grained to coarse ones, that are tracked during a test case execution. They include statements, blocks, predicates, definition-use associations (DUAs), and function or method calls that are associated with each test case.
SFL is based on strategies to pinpoint faulty program elements. Most of them make use of  metrics <cit.> to rank suspicious elements. The rationale is that program elements frequently executed in failing test cases are more likely to be faulty. Thus, the frequency with which elements are executed in passing and failing test cases is used to calculate a suspiciousness score for each element. Subsequently, these suspicious elements are mapped onto lines of code likely to be faulty.

Thus, SFL is built upon two foundations: spectra and ranking metrics. Many studies have been conducted to determine which is the best metric to support SFL <cit.>. Ochiai <cit.> has been suggested as the most effective metric for fault localization <cit.>. However, a very recent study shows that the best metrics are indistinctive for real faults, meaning that there is hardly any difference in which metric one chooses since the results will be very similar <cit.>. 

It remains then to tackle the role of the spectra in SFL. Few studies compared the use of different spectra in fault localization. Santelices et al. <cit.> suggest that DUA spectrum performs better than statements and branches to locate bugs. Masri shows that DIFA (Dynamic Information Flow Analysis) spectrum, along with DUA and branch, performed better than statement spectrum <cit.>. DIFA consists of interactions occurred in an execution, and comprises data and control dependencies from statements and variables. Both DUAs and DIFAs are data-flow spectra.

These  studies, though, used  only small- to medium-sized programs and artificial faults in their assessments. In Santelices et al. <cit.>, most of the programs belongs to the Siemens Suite <cit.>, which is composed of programs with few hundred lines of code (LOC); in Masri <cit.>, two programs with less than 10 KLOC were used in the evaluation. Both studies only utilize artificial faults. Pearson et al. <cit.>, however, show that many claims verified with artificial faults do not hold for real bugs.

There is a reason why most SFL studies <cit.> use only control-flow spectra, namely, statement, predicate, and branch coverage: cost. To obtain the spectra for fault localization, the original source or object code needs to be modified (instrumented) to track the elements executed by each test case. Moreover, test case results (i.e., fail or success) should also be recorded.
The cost to obtain data-flow spectra is higher because definition-use associations (DUAs), for example, comprise all value assignments (variable definition) and their subsequent references (variable uses) in a program  <cit.>. As a result, there are much more DUAs to track at run-time than statements, which implies both execution and memory overheads during test case execution.
Previous studies show that statements and branches can be monitored with a run-time overhead of 9% to 18% while DUAs have a run-time overhead of 66%-127% <cit.>. Recent results, though, show that DUA spectra can be obtained with fairly moderate execution and memory overheads <cit.>. They allow the use of data-flow spectra in fault localization for large and long running programs.

This paper assesses the use of data-flow spectra in fault localization. Because programs have more DUAs than statements or branches, the likelihood of correlating critical DUAs with failing test runs should be higher. Thus, our hypothesis is that data-flow spectra is more effective than control-flow spectra for fault localization.  Moreover, we investigate whether the possible increase on the effectiveness is worth the data-flow extra cost for large programs. We compared data- and control-flow spectra using definition-use associations (DUAs) and statement (line[The term line in this work refers to an executable line or statement.]), respectively. DUAs and lines are two of the least expensive program elements that represent both spectra.

We used the Jaguar SFL tool (JAva coveraGe faUlt locAlization Ranking)[github.com/saeg/jaguar]  <cit.> to compare data- and control-flow spectra in fault localization. Jaguar provides ranking lists for several ranking metrics. It uses JaCoCo[eclemma.org/jacoco] and BA-DUA[github.com/saeg/ba-dua] to collect line and DUA spectra, respectively. JaCoCo has been utilized to assess control coverage of large systems. Moir reports that JaCoCo was run against 37,000 Eclipse JDT core tests with an execution overhead of 2% <cit.>. BA-DUA, in turn, was able to collect DUA spectra with run-time overhead of 38% on average for large programs <cit.>. 

Differently from previous work, we assess both techniques using 163 real faults from five real open-source programs. The program sizes vary from 10 to 96 KLOC, which contains from 468 to 4130 test cases. Additionally, we compare data- and control-flow spectra using ten SFL ranking metrics. The goal is to assess which spectrum is more effective; i.e., the one that locates more bugs by inspecting fewer lines of code. Furthermore, we compare the efficiency (i.e., run-time overhead) of SFL based on data- and control-flow spectra. The following research questions summarize the issues addressed in this paper:



  * Which spectrum is more effective to locate bugs: data- or control-flow?

  * Which spectrum is more efficient to locate bugs: data- or control-flow?


Our results indicate that data-flow spectrum ranks more faults in upper positions compared to control-flow spectrum with statistical significance for all ten ranking metrics. 
DUA outperforms line spectrum, classifying more faults in the range of 7 to 40 most suspicious lines in the SFL ranking lists. By investigating from the top 9 to the top 25 most suspicious lines, a practitioner can reach from one quarter to half of all faults using DUA spectrum and Ochiai. To achieve the same result with line spectrum, one needs to inspect 14 more lines. After the 70th position, control-flow surpass data-flow for most ranking metrics. Since each DUA contains from 2 to 3 lines, its performance worsens for faults that are far from the top positions. 

Data-flow cost is high, but it is not prohibitive. It took from 22 seconds to 8:35 minutes to obtain the suspicious lines. However, control-flow spectrum can also be expensive, up to 4:25 minutes. The average time for all programs using data-flow and control-flow are 2:58 and 1:18 minutes, respectively. Data-flow has an average overhead of 353% for all programs, while the average overhead for control-flow is of 102%. 

The results suggest that data-flow spectrum can leverage SFL; however, practitioners should be educated to inspect more code—from 10 to 25 suspicious lines—to take advantage of SFL.

The remainder of the paper is organized as follows. Section <ref> presents concepts and definitions of control- and data-flow spectra, and Spectrum-based Fault Localization (SFL). Sections <ref>, <ref>, <ref>, and <ref> describe, respectively, the experiment design, the results, the discussion, and the threats to the validity of our experimental assessment. The related work is discussed in Section <ref>. We draw our conclusions and present future work in Section <ref>.



§ BACKGROUND


In what follows, we present an example to illustrate the concepts of control- and 
data-flow spectra, and spectrum-based fault localization. 



 §.§ Running example


Figure <ref> shows the code of a simple function, named max <cit.>. 
The first three columns represent line, statement, and block 
numbers, respectively. The function receives two parameters: the first is an  and 
the second is the array size. It should return the largest number of an array, 
but there is a fault at line 4:  should be ; that is, the 
increment () must come after the variable . This causes 
variable  to be assigned to the second position of the array.





 §.§ Control-flow spectra



Fault localization techniques use different types of control-flow spectra: statements are 
executable lines of code; basic blocks (or simply blocks) are sets of statements that 
are always executed together; branches are statements that transfer the control-flow 
execution among blocks. 






Control-flow information of a program is represented by a graph with nodes and 
edges, in which a node represents a basic block and an edge represents 
a branch. Figure <ref> shows the control-flow graph of the max program.

Table <ref> describes, in the all-nodes and all-edges columns, the 
control-flow spectra that can be tracked during the execution of max's test suite. 
The nodes and edges are also known as the testing requirements of structural testing criteria 
all-nodes and all-edges <cit.>. A node (edge) is considered as covered if there is a 
test case that traverses a path that includes such a node (edge). All-nodes and all-edges 
criteria require that every node and every edge of a program, respectively, must be covered by at 
least one test case to be satisfied.




 §.§ Data-flow spectra



Data-flow spectrum concerns paths in a program between every point in which a value is assigned to a 
variable and its subsequent references. When a variable receives a new value, it is said that 
a definition has occurred; a use of a variable happens when its value is 
referred to. A distinction is made between a variable referred to compute a value and to 
compute a predicate. When referred to in a predicate computation, it is called a p-use 
and is associated with edges; otherwise, it is called a c-use when associated with 
nodes. A definition-clear path with respect to (wrt) a variable X is a path where 
X is not redefined in any node in the path, except possibly in the first and last ones. 
Figure <ref> contains max's control-flow graph annotated with data-flow
information.



Data-flow spectra can be formally defined using the concept of definition-use 
associations (DUAs) <cit.>. The triple D = (d, u, X), called c-use DUA, represents a 
data-flow testing requirement involving a definition in node d and a c-use in node u 
of variable X such that there is a definition-clear path wrt X from d to u. 
Likewise, the triple D = (d, (u', u), X), called  p-use DUA, represents the 
association between a definition and a p-use of a variable X. In this case, a 
definition-clear path (d,…,u',u) wrt X should exist.

The data-flow spectrum is also the testing requirements of the  all-uses  
testing criterion <cit.>. This criterion requires the set of paths executed by the 
test cases of a test set T to include a definition-clear path for each DUA (d, u, X) 
or (d, (u', u), X) of a program P. The DUAs exercised by a test set are said to be 
covered by it. Table <ref> contains the DUAs required for the 
max program.






 §.§ Spectrum-based fault localization



Program spectrum or coverage <cit.> consists of program elements (e.g., 
statements, blocks, predicates, DUAs, methods) covered during a test case execution 
<cit.>. Spectrum-based fault localization techniques use ranking 
metrics to assign suspiciousness scores to these elements. The outcome is a list of elements 
ranked in descending order of suspiciousness. 

Several ranking metrics have been proposed or used to indicate elements most likely to contain faults 
<cit.>. The most effective metrics are characterized by 
identifying suspicious code excerpts from the frequency of elements exercised in passing 
and failing test cases. 
The ranking metrics use four parameters to calculate the suspiciousness of an executed program 
element. These parameters represent the four possible states during a test execution: 
c_ef indicates the number of times a program element (c) is executed (e) in 
failing (f) test cases, c_nf is the number of times an element is not (n) executed 
by failing (f) test cases, c_ep is the number of times an element is executed (e) 
by a passing (p) test case, and c_np represents the number of times an element is 
not (n) executed by passing (p) test cases.



SFL ranking metrics have been studied by different authors, 16 of them are listed by Mao et al. 
<cit.>. In Table <ref>, we present the ten SFL ranking metrics utilized in our 
empirical assessment. Table <ref> shows five test cases (t_1, t_2, t_3, t_4, 
and t_5) of the max program. The test cases t_4 and t_5 fail, while t_1, t_2, 
and t_3 pass. Table <ref> presents the statement and the block spectra 
(indicated by the bullets associated with each statement, block, and test case) of max, 
the number of times whether an element is executed or not by failing and passing test cases, 
and the suspiciousness score assigned using Ochiai in the M_O column. 

The suspiciousness score for block 1 is 0.63, and 0.35 or 0 for the remaining blocks (shown in Table <ref>). For 
Ochiai, the most suspicious elements are  lines 3 and 4 (or statements 1 and 2). In this example, 
control-flow spectra, in particular, blocks, were ranked. These blocks are then mapped onto lines 
3 and 4 to be inspected by the developer. Thus, the top suspicious lines contain the bug. 
Similarly, one could utilize Ochiai to rank DUAs, which can then be mapped onto a list of 
suspicious lines. We describe how we mapped DUAs onto lines in Section <ref>.








§ EXPERIMENT DESIGN



We conducted an experiment[The datasets and results are available at <doi.org/10.5281/zenodo.3258116>] to compare the use of data- and control-flow spectra in fault localization. We applied ten ranking metrics to assess the effectiveness of both spectra. In what follows, we describe the programs and bugs used in the experiment, the data collection procedure, and the analysis criteria used to answer our research questions.




 §.§ Subject programs and faults


We used five real-world programs for the experiment. JFreeChart, Commons Lang, Commons Math, and Joda-Time 
were obtained from the Defects4J database[<github.com/rjust/defects4j>] <cit.>. 
The jsoup's faults were obtained by us from its source code repository[<github.com/jhy/jsoup>] by looking at the commit history. Therefore, all programs used in our experiment are composed of real faults along with their original test cases.

Table <ref> lists our subject programs, their number of lines of code (KLOC), 
the number of test cases (TC), and the number of faulty versions (Faults). Each version contains a single fault that may be spread in several lines. That is, changes in more than one line were required to fix the bug. In this scenario, each line of a multiple-line fault is deemed as the bug. The rationale is that, if a developer reaches at least one of these lines, s/he locates the bug. 



However, in selecting faults for our experiment, we only selected bugs for which data-flow spectra was complete. BA-DUA is unable to collect reliable data-flow spectra in two cases: 1) the fault throws an exception and it is located in a code block with a non-handled exception; and 2) the bug is in a single-block method. The first case happens because BA-DUA marks the exercised DUAs whenever the method is exited; in this case, the method is exited in a non-predictable way so that the BA-DUA library does not mark the exercised DUAs as covered. The second case occurs because BA-DUA does not cover DUAs when the definition and use are in the same block. Hence, we removed faults with incomplete data-flow spectra for a fair comparison between spectra.



 §.§ Data collection procedure


We used Jaguar <cit.> to generate the lists of suspicious DUAs and lines for each fault. Jaguar is an open source SFL tool that utilizes the instrumentation libraries of two testing tools: BA-DUA <cit.> to gather data-flow spectra and JaCoCo to gather control-flow spectra. 
It then calculates the suspiciousness value of each element according to a chosen ranking metric. The cost of determining the suspiciousness values is very low in comparison to the time for test suite execution and spectra data collection. 

We applied this procedure for all ten ranking metrics (see Table <ref>) used in this evaluation: Ochiai, Kulczynski2, McCon, O^p, Tarantula, Jaccard, Zoltar, Minus, DRT, and Wong3. In this work, we did not intend to compare the ranking metrics; thus, we were not exhaustive in the selection of ranking metrics. Instead, we selected  different metrics only to assess whether the spectra's performance is affected by the chosen metric.

We identified the faulty lines of jsoup and the programs from Defects4J by comparing the buggy and fix commits in their repositories. For faults occurred due to missing code, we deemed the previous line of code as the bug site. However, if the previous line contains non-executable code (e.g., comments, blank lines, closing brackets), the line after the change was deemed as the faulty one.
When ties occur, the worst case is considered. It means that if two or more lines have the 
same suspiciousness score, the position of the faulty line includes all tied lines, since 
they have equal chances of being inspected.

As the data-flow spectra are DUAs, we mapped them onto lines to determine their faulty sites. A DUA has always a definition line and a use line, and possibly a source line (for p-use DUAs). To check whether the bug was found, the faulty line is compared to these three lines (definition, use, and source). When the result is false, all these lines are added to the number of lines inspected until finding the fault.

We created a script to check the position of the faults over each respective DUA and line suspiciousness lists generated by Jaguar. It records the number of lines until reaching the faulty line considering the above criteria.



 §.§ Measurement criteria


To answer our research questions, we measured the effectiveness of data- and control-flow to locate the faults by the absolute number of lines inspected until reaching the faults. We restricted the number of lines inspected to 99 lines of code. If a fault is beyond the 99th position we considered that it was not found. Indeed, this is a very large limit since developers in practice inspect only the first picks of the suspiciousness lists <cit.>. 

We also measured the efficiency of data- and control-flow spectra by collecting the time spent to create the suspiciousness lists of each faulty version. The total overhead cost comprehends running all unit tests, storing the spectra data, calculating the suspiciousness of each element, and generating the suspiciousness list.



 §.§ Statistical Analysis


We carried out a statistical analysis to evaluate the results obtained by data- and control-flow spectra with different ranking metrics. First, we applied the Anderson-Darling normality test <cit.> to our data, which follows a non-normal distribution. Then, we used the Wilcoxon signed-rank test <cit.> for the hypothesis test and Cliff's delta <cit.> to measure the effect size. These statistical methods are suitable to use with non-parametric data. The significance level applied was 5%. The Wilcoxon signed-rank test assesses differences in the magnitude of measurements between the compared techniques. The Cliff's delta calculates the amount of difference between the two techniques. We explain our null and alternative hypotheses for each test in Section <ref>.



§ RESULTS



First, we present the effectiveness of data- and control-flow spectra for different ranking metrics and then the run-time overhead to assess the efficiency of the two spectra.



 §.§ Effectiveness of data- and control-flow spectra


We compared the effectiveness of data- and control-flow spectra using the ten ranking metrics described in Table <ref>. The most suspicious DUAs and lines, ranked according to the metrics, are mapped onto lines to be inspected. Figures <ref> and <ref> describe the number of faults located when a developer inspects different amounts of suspicious lines. 

DUA and line spectra have similar behaviors for all ranking metrics, except Wong3. They locate the same number of faults up to 7 investigated lines. After that, and up to 40 lines, DUA spectrum locates more faults. The largest gap is located at 15 lines—for almost all metrics, DUA locates 60 faults whilst line spectrum locates 40 faults. There is no difference between DUA and line spectra for more than 40 lines inspected up to 70 lines. For more than 70 lines, line spectrum performs better.
For Wong3, DUA spectrum performs better after 5 lines, with a constant gap of 20 more faults located. This difference maintains almost constant until the end. However, Wong3 perform poorly locating at most 60 faults when using DUA and 40 with line spectrum. The other metrics locate more than 100 faults inspecting up to 100 lines using line spectrum. DUA spectrum locates about 80 faults by inspecting only 20 lines using Ochiai, Jaccard, Kulczynski2, McCon, O^p, and Minus.








































































































































































































































































Table <ref> presents the results of the statistical analysis. The null 
hypothesis is that there is no difference in the effectiveness of data- and control-flow spectra 
to locate faults. The alternative hypothesis is that data-flow spectrum is more effective than 
control-flow spectrum—i.e., data-flow spectrum requires the examination of less suspicious lines 
to locate faults. 


























The P-value column presents the results of the significance test. For all metrics, 
DUA spectrum locates more faults inspecting less code with statistical significance (p-value ≤ 5%). 
The Effect Size column presents the Cliff's delta results for all metrics, in which 
I means that the size is insignificant and S is a small effect. Except for Wong3, for which the effect size is small, the other metrics effect size is insignificant.

The B-T-W column shows the number of times DUA spectrum was better than (B), tied with (T) or 
worse than (W) line spectrum. It shows that DUA was better than line for near to half of the faults 
(46% or 75 faults for Ochiai and Zoltar). Line spectrum was better for one-quarter of the bugs 
(e.g., Ochiai, Tarantula, Jaccard). 

Table <ref> also presents the minimum number of inspected lines to find a bug (Min), the first (Q1), second (Q2), and third (Q3) quartiles for both 
data-flow (DF) and control-flow (CF). DUA spectrum with Ochiai locates half of the faults by inspecting 
25 lines while line spectrum needs 39 lines to reach the same amount of faults. The difference in Q2 varies 
from 14 (Ochiai) to 9 (DRT). The first quartile also indicates that DUA spectrum is more 
effective to locate one-quarter of the faults. It requires the inspection of 9 lines for almost all 
metrics while it can require 15 lines using line spectrum with Ochiai. Both DF and CF were not able 75% of all faults as shown in the Q3 column.





 §.§ Efficiency of data-flow and control-flow


To understand the costs of using data- and control-flow spectra, we measured the time spent 
to use both spectra for SFL. The time spent for DF and CF comprises: (1) running all tests, (2) collecting the spectra data, (3) calculating suspiciousness of all program elements, and (4) creating the SFL lists. Table <ref> shows the results for the 
efficiency comparison. The JUnit, DF, and CF columns 
show the time spent (in seconds) for executing, respectively, only the JUnit tests, Jaguar 
with data-flow spectra, and Jaguar with control-flow spectra. These values 
consist of the average execution time for all versions of a project for all ten ranking 
metrics.

The DF/JUnit column shows the overhead to collect data-flow spectra compared to 
the execution of JUnit. The CF/JUnit column presents the overhead to collect 
control-flow spectra compared to JUnit. The average overhead for all programs using data-flow 
and control-flow are 353% and 102%, respectively. The DF/CF column shows the ratio 
between the data-flow time and control-flow time. It indicates how much extra time is needed 
to execute Jaguar with data-flow compared to control-flow. For JFreeChart, generating a 
list of suspicious DUAs requires 143% more time than generating a list of suspicious 
statements. However, the total time to generate the list of suspicious DUAs in this case 
is 88 seconds.
























§ DISCUSSION



To better understand the results of Section <ref>, we discuss and analyze the results next. 
The discussion is organized by our research questions.



 §.§ Which spectrum is more effective to locate bugs: data- or control-flow?


The results confirm our hypothesis that data-flow, by providing more detailed information, improves fault localization. DUA spectrum leads the developer to inspect less code than line spectrum with statistical significance for all ranking metrics. 
However, the effect size is insignificant, except for Wong3. DUA spectrum outperforms line spectrum in the range of 7 to 40 investigated lines. After that, there is no difference or line spectrum performs better, which explains the insignificant effect size. For most ranking metrics, control-flow reaches more faults than data-flow after the 70th position. 

Indeed, if the faulty DUA is not the first or second pick, the bug will hardly be located at the top 5 suspicious lines since DUAs are composed of a definition, a use, and possibly a source, if a p-use DUA. Thus, each ranked DUA adds 2 to 3 lines to be investigated. 
Being able to beat line spectrum at the top 10 lines shows that data-flow spectrum singles out specific faulty DUAs to be investigated. Additionally, DUA spectrum demanded less code to be inspected for a large number of faults: 75 out of 163 using Ochiai and Zoltar whilst line spectrum required the inspection of less code only for 40 and 39 faults, respectively, for the same ranking metrics—a difference of 87.5%.

Around 20 out of 163 (12%) faults can be located by investigating only the top 5 lines, using either DUA or line spectra. On the other hand, one can reach 40 faults (25%) by investigating only 9 lines using DUA spectrum and all metrics, excepting Tarantula and Wong3. Furthermore, if the developer investigates up to 25 suspicious lines, s/he will reach half of the faults using Ochiai and DUA spectrum. If the practitioner decides to use line spectrum, s/he will need to inspect 14 more lines to achieve the same result.

Some studies have shown, though, that practitioners may give up on using an SFL technique if the fault is not located at the top 5 picks <cit.>. Since there is no difference between DUA and line spectra up to 7 suspicious lines, the difference is too little to be useful in practice.  
Notwithstanding, sticking to only the first 5 lines is not practical either since too few faults can be located in this short range, in our study, only 12%. Data-flow spectrum can leverage SFL techniques. However, practitioners should be educated to inspect 10 to 25 lines to reach a quarter to half of the faults, respectively. Other recent results have shown that SFL can help developers to locate faults even when the faulty line is not ranked among the top suspicious ones <cit.>.



 §.§ Which spectrum is more efficient to locate bugs: data- or control-flow?


Table <ref> summarized the run-time costs for each project. 
The data-flow suspiciousness lists require from 94% to 245% more time to be generated
than the control-flow lists. This result differs from the 38% overhead presented 
by BA-DUA <cit.>. Such a discrepancy is justified by the extra work needed 
to run an SFL technique.

Data-flow implies more information than control-flow: if on the one hand it
provides detailed data for fault localization; on the other hand, more time is needed to 
compute such data. Thus, control-flow is more efficient, providing fault localization 
information with less overhead.

However, the amount of time needed to generate the lists of suspicious DUAs for the medium- 
and large-sized real programs used in this assessment is not prohibitive. For four out of five subjects, 
the time varies from 22 seconds to 2:45 minutes. Only for Commons-Math, the time jumps 
to 8:35 minutes. For this particular program, line spectrum is also expensive to obtain: 4:25 minutes.
Since DUA spectrum can improve the fault localization effectiveness, the extra time to create the 
suspiciousness lists seems affordable at industrial settings.




§ THREATS TO VALIDITY



The internal validity threats to our experiment are related to the Jaguar tool. To mitigate them, 
we manually checked the Jaguar's output using small programs. Regarding the data-flow efficiency results, it is certainly possible to optimize the Jaguar tool to reduce its run-time overhead for both spectra. Our 
chosen strategy aimed to get a first picture of the performance benefits from the recent 
promising data-flow spectra tool (BA-DUA).
As we explain in Section <ref>, we only selected bugs for which data-flow spectrum was complete. 
Thus, we excluded faults that throws exceptions without handling them and faults in single-block methods. 
Improvements in BA-DUA can allow us to use such faults in future experiments.

All faults were found in their source code repositories. We assumed that each code change between a faulty version and its consecutive fixed version was made to fix the bug. We disregarded changes that do not affect the program behavior such as adding or removing empty lines and line indentation changes. 
For multiple-line faults, we considered the best case scenario. A fault is deemed as found when the top ranked one of its lines is reached. However, this scenario occurs for both spectra. For tie cases, we considered the worst case, in which all lines with the same suspiciousness score of the faulty one are deemed to calculate its position.

Regarding external validity threats, we used five programs from different domains and 
sizes to expose the techniques to different scenarios. Although the programs utilized in 
the experimental assessment are quite heterogeneous, we caution the reader that the 
techniques may present different results for a different set of programs. Also, all programs assessed in this experiment have a single fault per version. The results may differ for programs containing multiple faults.










Regarding construct validity threats, we assessed the techniques using statistical tests and descriptive data. Our experiment was built to evaluate how quickly a technique will reach the fault site. One issue, though, deems the assumption that the ranked elements will be followed as they were presented, which may not actually happen in practice. Another issue is that reaching the bug site does not necessarily mean locating the defect, which is known as perfect bug detection <cit.>.



§ RELATED WORK



Despite the ability to exercise different aspects during a test execution, data-flow 
is rarely used to support SFL. Few initiatives use definition-use 
associations (DUAs) <cit.> while others use program slicing <cit.> or
different types of data and control dependencies <cit.>. All these approaches demand
a costly time overhead to collect data-flow spectra.

Santelices et al. <cit.> proposed a technique, avg-SBD, that combines different 
spectrum types for fault localization: statements, branches, and du-pairs—a variant 
of data-flow information that takes into account only c-use DUAs. They also introduce an 
approximate DUA spectrum, avg-SBD approx, which has lower overhead at run-time. 
The results, assessed using small- to medium-sized programs, showed that their approach 
locates more faults than each spectrum isolated. 
They also showed that different faults are best located by different coverage types. 

Masri <cit.> uses a spectrum called Dynamic Information Flow 
Analysis (DIFA) for fault localization. DIFA is composed of interactions 
performed in an execution, including inter-procedural data- and control-flow 
dependences from statements and variables. The author compared DIFA with statement, branch, 
and DUA spectra using 18 faults of medium-sized programs. DIFA presented better 
performance to locate the bugs. However, the time to generate DIFA spectra 
was 2–10 times slower than DUA and branch spectra.

Hemmati <cit.> assessed the ability of data- and control-flow coverage criteria 
to reveal faults on programs from the Defects4J database. Du-pair criterion covered 79% of faults that 
were not covered by control-flow criteria. He also showed that 15% of all faults were not 
covered by any criterion. The author did not report issues regarding run-time costs.


Yu et al. <cit.> presented the LOUPE technique, which combines data- and 
control-dependencies for fault localization. The output is a list of statements. 
Their experiments using the Siemens suite presented better performance than the compared 
techniques. They also assessed LOUPE in the space program, which took 100 minutes to execute.
Eichinger et al. <cit.> propose the data-flow enabled call graphs (DEC graphs), which is a method 
call graph with data-flow information. DEC graphs register also parameters and method-return 
values. To reduce the number of possible parameter values, they discretize numerical parameter 
and return values using Data Mining approaches. They assessed the technique including ten faults in 
the Weka program—which has 301 KLOC. The authors do not reported the run-time overhead of the technique.

As with the works of Santelices et al. <cit.> and Masri <cit.>, our study compares 
DUA and statement spectra to investigate their effectiveness for fault localization. 
Differently from the previous works, we assessed both spectra using ten different ranking 
metrics. Moreover, we used medium- to large-sized programs containing real faults. 
We also evaluated their performance to locate faults for absolute values and compared the overhead of SFL techniques based on data- and control-flow spectra. Finally, we carried out a statistical analysis in our assessment, 
showing that data-flow spectrum can be useful for fault localization at an affordable cost. 



§ CONCLUSIONS



We carried out an experiment comparing the use of data-flow spectrum (definition-use 
associations—DUAs) and control-flow spectrum (lines) in fault localization. Our
goal was to corroborate the body of evidence with more robust results, showing that data-flow is more
effective than control-flow in fault localization. In addition, we aimed
to verify whether new approaches to collect DUAs would allow the application
of data-flow-based SFL in programs similar to those developed in the industry.
We used 163 real faulty versions of five industry-like programs whose sizes vary from 10 to 96 KLOC. 

DUA spectrum located more bugs inspecting less code for all ranking metrics with statistical significance. DUA spectrum outperforms line spectrum in the range from 7 to 40 inspected lines. By inspecting from 10 to 25 lines, a practitioner will reach the bug site for a quarter to half of the faults. Line spectrum requires to investigate 14 more lines to reach half of the faults. After 70 inspected lines, line spectrum can reach more bugs than DUA spectrum. As each DUA has 2 or 3 lines, its performance is overcome by line spectrum as the number of inspected lines increases.

It is known that practitioners expect the fault to be located in the first 5 most suspicious lines. Nevertheless, such a tight target is successful for only 12% of the faults in our experiment. SFL will hardly be adopted in practice with this small success rate. Data-flow spectrum can help the adoption of SFL techniques at industrial settings, but the practitioners should be educated to inspect a few more code excerpts to take advantage of SFL techniques. 

Our results suggest that from 10 to 25 lines would significantly improve the number of faults hit by SFL techniques using data-flow spectrum. Regarding efficiency, the overall time for the subjects of our experiment varies from 22 seconds to 8:35 minutes using data-flow spectrum, which indicates that its use is feasible for many programs developed by the industry.
Thus, the hypothesis that data-flow generates more detailed information that improves fault localization was verified in our experiment. Although more time is needed to collect such an information, the overhead is affordable for real-world software.

In future work, we will exploit contextual information associated with data-flow spectrum, 
especially the use of variables from the most suspicious DUAs to locate faults. 
We will also carry out user studies to evaluate whether information regarding suspicious variables improves fault localization.






§ ACKNOWLEDGMENT


This research was supported by FAPESP (São Paulo Research Foundation), processes 13/24992-2, 14/23030-5, and 14/50937-1; by CNPq process 311174/2017-5; and by the Research Support Center on Open Source Software (NAPSoL) of the University of São Paulo. 

IEEEtran
 
