Source-linked AI summary
An Empirical Study of Fault Localization Families and Their Combinations
Daming Zou, Jingjing Liang, Yingfei Xiong, Michael D. Ernst, Lu Zhang
TL;DR
Fault localization must rank defective program elements highly, yet prior empirical evidence covered a limited range of techniques on real-world faults. This paper evaluates eleven techniques from seven families on 357 real-world faults, combines them with learning to rank, and measures execution time. The combined techniques significantly outperform standalone techniques, supporting evaluation and combination across time-cost levels.
Problem
Prior empirical studies mainly evaluated SBFL and MBFL, leaving other fault-localization techniques insufficiently evaluated on real-world faults.
Method
The study evaluates eleven techniques from seven families on 357 real-world Defects4J faults, combines them with learning to rank, and measures execution time.
Results
200/63/51/31% increases in localized faults occur in Top 1/3/5/10, respectively, versus the best standalone technique.
Takeaways & Limitations
The authors recommend combining fault-localization techniques grouped by time-cost levels and evaluating future techniques in this combined setting.
Takeaways & Limitations
The learning-to-rank approach treats techniques as black boxes, uses linear combination, and requires training data whose effectiveness impact remains unknown.
Abstract
from arXiv · showhide
The performance of fault localization techniques is critical to their adoption in practice. This paper reports on an empirical study of a wide range of fault localization techniques on real-world faults. Different from previous studies, this paper (1) considers a wide range of techniques from different families, (2) combines different techniques, and (3) considers the execution time of different techniques. Our results reveal that a combined technique significantly outperforms any individual technique (200% increase in faults localized in Top 1), suggesting that combination may be a desirable way to apply fault localization techniques and that future techniques should also be evaluated in the combined setting. Our implementation is publicly available for evaluating and combining fault localization techniques.
1 INTRODUCTION
This paper empirically evaluates diverse fault-localization families on real-world faults, combining techniques while measuring effectiveness and execution cost. CombineFL substantially improves localization over standalone techniques, with benefits holding across statement and method granularities.
- Study scope: The study evaluates a wide range of fault-localization techniques from different families on 357 real-world Defects4J faults.It compares eleven techniques from seven families and includes statement and method granularities.
- Combination: CombineFL combines techniques using learning to rank, exploiting their weak correlations across families.The approach combines suspiciousness scores linearly and supports techniques using different information sources.
- Results: SBFL is the best family, localizing about 44% of real-world faults in the top 10.All techniques except Bugspots and BugLocator localize more than 6% of faults in the top 10.
- Results: 200/63/51/31% increases in localized faults occur in Top 1/3/5/10, respectively, versus the best standalone technique.CombineFL also outperforms MULTRIC, Savant, FLUCCS, and TraPT by 133%, 167%, 11%, and 18% in Top 1, respectively.
- Efficiency: Time costs form several levels, and adding techniques from preceding levels can improve effectiveness without affecting runtime at the selected level.The study considers usage scenarios to balance localization performance and cost.
- Implications: The findings hold at both statement and method granularities, and the released CombineFL-core infrastructure supports future evaluation and combination.The infrastructure and studied-technique data are publicly available for research and application.
2 BACKGROUND
Fault localization spans seven technique families that use different program information and produce either ranked suspicious elements or unranked suspicious sets. The background introduces the main families, their inputs, and the distinction between spectrum-, mutation-, slicing-, predicate-, stack-trace-, information-retrieval-, and history-based approaches.
- Technique families: Fault localization techniques use different information sources, including test execution, mutation effects, program slices, stack traces, bug reports, and development history.The paper organizes these approaches into seven families and introduces learning to rank for combining them.
- Spectrum-based fault localization: Spectrum-based fault localization ranks elements using execution frequencies in passed and failed tests.Ochiai and DStar calculate suspiciousness from spectrum-derived execution values.
- Mutation-based fault localization: Mutation-based fault localization ranks statements by injecting mutants, measuring test-result changes, and aggregating mutant scores into statement scores.MUSE and Metallaxis are identified as state-of-the-art MBFL techniques, with different definitions of a mutant being killed.
- Program slicing: Dynamic slicing includes executed statements that may affect a criterion for one input, producing smaller slices than static slicing.For the collatz example with x=3, the dynamic slice contains line 5 but not line 3, whereas static slicing includes both branches.
- Predicate switching: Predicate switching identifies critical predicates when forcibly changing a predicate outcome makes a failed test pass.Unlike MBFL, it mutates control-flow evaluations rather than the program itself.
- Information retrieval and history: Information-retrieval techniques rank source files by similarity to bug reports without requiring passed- and failed-test execution information.History-based fault prediction instead ranks elements by their likelihood of being defective based on prior development history.
3 EXPERIMENTAL METHODOLOGY
The methodology evaluates standalone and combined fault localization techniques on Defects4J while examining correlations, runtime cost, granularity, and comparisons with state-of-the-art methods. It uses 357 real-world faults, defines faulty elements from developer patches, and measures both ranking performance and inspection effort.
- Research questions: The experiments evaluate standalone effectiveness, technique correlations, learning-to-rank combinations, runtime cost, granularity, and comparison with state-of-the-art approaches.These objectives correspond to RQ1–RQ6 and include both statement- and method-level analyses.
- Experiment subjects: 357 real-world faults from five open-source Java projects are drawn from Defects4J version v1.0.1.Each fault includes faulty and fixed project versions plus tests containing at least one failing test.
- Techniques: The study includes ranked-list techniques and suspicious-set techniques, covering SBFL, MBFL, stack-trace, history-based, slicing, predicate-switching, and related families.SBFL uses Ochiai and DStar, while MBFL uses MUSE and Metallaxis in the reused infrastructure.
- Technique implementation: Dynamic slicing uses an exception-throwing statement as the criterion for one failed test and union, intersection, or frequency strategies for multiple failed tests.Union and intersection return statement sets, whereas frequency returns a ranked list based on slice inclusion frequency.
- Technique implementation: Bugspots is restricted to Math, Lang, Time, and Closure because Chart uses a private Subversion format that cannot be converted for the Git-only tool.BugLocator and Bugspots file-level scores are mapped to executable statements for statement-granularity analysis.
- Evaluation: Faulty program elements are defined as those modified or deleted in the minimized developer patch that fixes the defect.This patch-based definition establishes which elements count as faulty before ranking performance is measured.
- Evaluation: Einspect measures the expected rank of the first faulty element when tied elements are arbitrarily ordered.EXAM measures the percentage of elements inspected before finding a faulty element, averaged uniformly across all 357 faults; smaller scores are better.
4 EXPERIMENT RESULTS
The study evaluates standalone fault localization techniques on 357 real-world faults, finding substantial differences across technique families and fault types.
- SBFL is the most effective standalone fault localization family in the experiments.
- 156 and 155 faults were localized in the top 10 by Ochiai and DStar, respectively, or about 44% of all faults.
- Bugspots localized no faults in its top-10 statements, while BugLocator localized no faults in its top-5 statements.
- 22% of crash faults were localized at top-1 by stack trace analysis, versus 11% by Metallaxis.The crash-fault subset contains 90 of the 357 faults.
- Predicate switching was not the most effective technique on predicate-related faults, despite modifying predicates similarly to MBFL.Predicate-related faults comprise 32% of the dataset.
4.2 RQ2. Correlation between Techniques
Technique pairs exhibit different correlation patterns, and most pairs are weakly correlated, suggesting that many techniques may provide complementary information for combination.
- Different pairs of fault localization techniques exhibit different correlation patterns.
- Ochiai and DStar have almost identical Einspect values across faults, so each is unlikely to provide much more information than the other.
- Some technique pairs show faults where one technique performs well while the other performs poorly, indicating weak positive correlation.
- Only two of 55 technique pairs were significantly correlated: Ochiai–DStar with r2 = 0.753 and union–frequency with r2 = 0.310.Both pairs had p-value ≪0.01; other pairs were not statistically significant at p < 0.05.
- Strongly correlated techniques occurred within the same family, but not all same-family techniques were strongly correlated.
4.3 RQ3. Effectiveness of Combining Techniques
The study combines fault localization techniques with learning to rank and finds that the combined approach significantly outperforms standalone techniques across validation settings.
- Learning to rank was applied to combine fault localization techniques, evaluated using both 10-fold and cross-project validation.
- The two cross-validation methods produced similar evaluation results, supporting the model’s generalizability across projects.
- 200%, 63%, 46% and 31% improvements were achieved over the former best at Einspect@1, 3, 5 and 10, respectively.At EXAM, the combined technique improved from 0.033 to 0.0173, a 48% improvement from the former best.
- A family’s contribution to the combined result was not determined by its standalone effectiveness, and all families contributed overall.
- Removing any fault localization family decreased all metrics, while even Bugspots slightly improved combined Einspect@n values despite weak standalone performance.
4.4 RQ4. Time Consumption and Combination Strategy
The study measures execution costs and identifies combinations that balance localization effectiveness with runtime across debugging scenarios.
- Learning-to-rank training costs around 10 seconds on average, while combination time is usually less than one second.The combination time reaches 28 seconds for Closure.
- Fault localization families span four runtime levels: fast history-based, stack-trace and IR-based methods; intermediate slicing and SBFL; slower predicate switching; and slowest MBFL.
- Including preceding-level families slightly affects time consumption but always improves results, so all preceding-level techniques should be included.
- Performance improves significantly from level 1 to level 2 and notably from level 3 to level 4, while MBFL adds useful information at high cost.
- Level 2 and Level 4 offer good effectiveness–efficiency balance, while Level 1 is suitable for crash bugs.
4.5 RQ5. Results at Method Granularity
At method granularity, the main findings for technique performance and combination remain valid, while stack trace performs especially well on crash faults.
- The main findings in RQ1 and RQ3 still hold at method granularity.
- Ochiai and DStar have the best performance on all metrics.
- 44% of 88 crash faults are localized at top-1 by stack trace, rising to 83% at top-10.
- The relative performance between techniques has no significant changes.
- Learning to rank significantly improves results over standalone techniques.
4.6 RQ6. Comparison with State-of-the-Art Techniques
The study compares CombineFL with prior learning-to-rank approaches, finding significantly better localization output while leaving runtime comparisons unresolved.
- The compared approaches combine techniques within one family or augment a family with additional information.
- The comparison uses cross-validation results on Defects4J, including a 210-fault subset for comparison with FLUCCS.
- All compared results are reported at method granularity because the compared approaches support only that granularity.
- CombineFL significantly outperforms MULTRIC, Savant, FLUCCS, and TraPT in the comparison.
- Runtime costs are not compared because the existing papers did not report them.
5 RELATED WORK
Prior work largely evaluates SBFL or combines techniques within one family, whereas this paper studies seven families, real-world faults, combination, and cost systematically.
- This paper is the first empirical study on a wide range of fault localization families.
- Learning to Combine: Existing learning-to-rank approaches mainly combine techniques within one family or add information to one family.
- Learning to Combine: The study combines eleven techniques from seven families and analyzes each technique’s contribution and cost.
- Learning to Combine: CombineFL significantly outperforms standalone techniques, while additional information from prior approaches could further improve it.
- Results on artificial faults can differ from results on real-world faults, making real-world evaluation important.
- Earlier studies predominantly evaluate SBFL techniques, including Tarantula, Ochiai, and DStar.
6 IMPLICATIONS
The paper argues for evaluating and using fault localization techniques in combinations under time constraints, while highlighting efficiency and combination-method limitations.
- Users should combine multiple fault localization techniques within a time limit rather than use one technique standalone.
- Researchers should assess a technique’s contribution both to the full combination and to combinations within a specific time limit.
- CombineFL-core provides data and infrastructure for evaluating and combining eleven studied techniques.
- Efficiency: Different techniques have large execution-time differences, and some are infeasible in certain use cases.
- Efficiency: The effect of efficiency on developers’ debugging performance remains unclear and requires future work.
- Methods for Combining Approaches: The black-box linear learning-to-rank combination prevents fine-grained reuse, may be nonoptimal, and depends on training data whose effects are unknown.
7 CONCLUSION
The study evaluates eleven fault localization techniques across seven families and combines them using learning to rank on real-world faults. Combined techniques significantly outperform standalone techniques, while execution times differ substantially across techniques.
- The study evaluates eleven techniques from seven families on 357 real-world faults at statement and method granularities.
- The experiments assess standalone effectiveness, learning-to-rank combinations, and execution time.
- Combined techniques significantly outperform any standalone technique.
- Different techniques have significantly different execution times, motivating grouping combinations by time-cost levels.
- CombineFL-core and fault localization data for the eleven techniques are publicly available for evaluation and combination.