Evaluating and improving fault localization - UMass Amherst

1 Evaluating and improving fault localizationSpencer Pearson , Jos Campos , Ren Just , Gordon Fraser , Rui Abreu , Michael D. Ernst , Deric Pang , Benjamin Keller *U. of Washington, USA **U. of Sheffield, UK U. of Massachusetts, USA Palo Alto Research Center, USAU. of Porto/HASLab, Most fault localization techniques take as inputa faulty program, and produce as output a ranked list ofsuspicious code locations at which the program may be researchers propose a new fault localization technique,they typically evaluate it on programs with known faults. Thetechnique is scored based on where in its output list the defectivecode appears. This enables the comparison of multiple faultlocalization techniques to determine which one is research has evaluated fault localization techniquesusing artificial faults, generated either by mutation tools or man-ually.

2 In other words, previous research has determined whichfault localization techniques are best at finding artificial , it is not known which fault localization techniques arebest at finding real faults. It is not obvious that the answer isthe same, given previous work showing that artificial faults haveboth similarities to and differences from real performed a replication study to evaluate 10 claims inthe literature that compared fault localization techniques (fromthe spectrum-based and mutation-based families). We used 2995artificial faults in 6 real-world programs. Our results support 7 ofthe previous claims as statistically significant, but only 3 as havingnon-negligible effect sizes.

3 Then, we evaluated the same 10 claims,using 310realfaults from the 6 programs. Every previous resultwas refuted or was statistically and practically insignificant. Ourexperiments show that artificial faults are not useful for predict-ing which fault localization techniques perform best on real light of these results, we identified a design space thatincludes many previously-studied fault localization techniquesas well as hundreds of new techniques. We experimentallydetermined which factors in the design space are most important,using an overall set of 395realfaults. Then, we extended thisdesign space with new techniques. Several of our novel techniquesoutperform all existing techniques, notably in terms of rankingdefective code in the top-5 or top-10 INTRODUCTIONA fault localization technique (for short, FL technique)directs a programmer s attention to specific parts of a one or more failing test cases and zero or more passingtest cases, a FL technique outputs a (typically, sorted) list ofsuspicious program locations, such as lines, statements, or dec-larations.

4 The FL technique uses heuristics to determine whichprogram locations are mostsuspicious that is, most likely tobe erroneous and associated with the fault . A programmer cansave time during debugging by focusing attention on the mostsuspicious locations [15]. Another use is to focus a defect repairtool on the parts of the code that are most likely to be of fault localization techniques have been proposed[45]. It is desirable to evaluate and compare these techniques,both so that practitioners can choose the ones that help themsolve their debugging problems, and so that researchers canbetter build new fault localization fault localization technique is valuable if it works onreal faults. Although some real faults (mostly 35 faults in thesingle small numerical program space [41]) have been used inprevious comparisons [45] of fault localization techniques, thevast majority of faults used in such comparisons are fake faults,mostly mutants.

5 The artificial faults were mutants automaticallycreated by a tool [26], [27], [49], or mutant-like manually-seeded faults created by students [44], [46] or researchers [16].Artificial faults such as mutants differ from real faultsin many respects, including their size, their distribution incode, and their difficulty of being detected by tests [22].It is possible that an evaluation of FL techniques on realfaults would yield different outcomes than previous evaluationson mutants. If so, previous recommendations would need tobe revised, and practitioners and researchers should choosedifferent techniques to use and improve. It is also possiblethat an evaluation of FL techniques on real faults would yieldthe same recommendations, thus resolving a cloud of doubtthat currently hangs over the field.

6 Either result would be ofsignificant scientific interest. The results also have implicationsbeyond fault localization itself. For instance, it would help toindicate which fault localization approaches, if any, should beused to guide automated program repair techniques [37].This paper compares fault localization techniques on real faults. Techniques that localize artificial faults bestdonotperform best on real faults. Our experiments are basedon 7 previously-studied fault localization techniques from thespectrum-based and mutation-based contributions of this paper include: A replication study that repeats and extends previous exper-iments, comparing 7 fault localization techniques on 2995artificial faults.

7 We mitigated threats to internal validity byre-implementing all the techniques in a single infrastructureand using the same experimental scripts, faults, and other ex-perimental variables. Our results confirm 70% of previously-reported comparisons (such as Ochiai is better thanTarantula [26], [27], [31], [44], [49]) and refute 30%. A new study that compares the 7 fault localization tech-niques on 310realfaults. The ranking does not agreewith any previous results from artificial faults! 40% of theprevious results are reversed; for example, Metallaxis isbetter than Ochiai on artificial faults [33], but Ochiai isbetter than Metallaxis on real faults. The other 60% of theresults are statistically insignificant; for example, DStar isbetter than Tarantula on artificial faults [19], [26], [44], buton real faults there is no significant difference between thetwo techniques.

8 These results indicate that artificial faults( , mutants) are not an adequate substitute for real faults,for the task of Evaluating a fault localization technique. An explication of the design space of fault localizationtechniques. Previous work made different, sometimes undoc-umented, choices for factors other than the formula. We ex-haustively evaluated all these factors. We found that formula,which most papers have exclusively focused on, is one ofthe least important factors. We also added new factors to thedesign space, thereby creating new hybrid fault localizationtechniques that combine the best of previous techniques. An evaluation of all the FL techniques generated by thedesign space, with respect to how well they localize realfaults.

9 We found new techniques that are statisticallysignificantly better than any previous technique, thoughwith small effect sizes. More importantly, they do muchbetter in terms of including the correct answer (the actualfaulty statement) within the top-5 or top-10 statements oftheir output. Our results indicate how to make the mostof current approaches, and they indicate that significantadvances in fault localization will come from focusing ondifferent issues than in the past. Our methodology addresses multi-line faults, faults ofomission, and other real-world issues, both in the designof FL techniques and in the experimental protocol forevaluating technical report [35] has more examples, data, & Evaluating fault LOCALIZATIONMany studies have evaluated and compared FL techniques[2] [5], [18], [19], [26], [27], [30], [31], [33], [38], [44], [49].

10 Table I summarizes these studies. The majority of studiesrevolve around the same set of programs and use largelyartificial faults. This section explains how a fault localizationtechnique s output can be Evaluation metricsA fault localization techniqueTtakes as input a programPand a test suite with at least one failing test, and it producesas output a sorted list of suspicious program locations, such aslines, statements, or declarations. For concreteness, this paperuses statements as the locations, but the ideas also apply toother levels of a fault localization techniqueTand a programPofsizeNwith a single known defective statementd, a numericalmeasure of the quality of the fault localization technique canbe computed as follows [36], [40]: (1) run the FL technique tocompute the sorted list of suspicious statements; (2) letnbe therank ofdin the list; (3) use a metric proposed in the literatureto evaluate the effectiveness of a FL technique, , LIL [30],T-score [28], Expense [18], orEXAM score [43].