PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectrum-based Software Fault Localization: A Survey of Techniques, Advances, and Challenges

Higor A. de Souza, Marcos L. Chaim, Fabio Kon

arXiv:1607.04347v2cs.SE

TL;DR

Debugging is costly and often manual, while SFL techniques remain rarely used in industry. This survey synthesizes SFL research and its challenges, finding no single best ranking metric across scenarios and only small reported gains. It highlights unresolved boundaries in industrial scalability, fault representation, and real-world evaluation.

  • Problem

    SFL techniques remain rarely used in industry, amid limited evaluation in real development scenarios and user studies.

    Source: §2.2 · p. 6, §10.6 · p. 30

  • Method

    The survey synthesizes SFL research on techniques, spectra, faults, programs, testing data, and practical use.

    Source: §12 · p. 32

  • Results

    No ranking metric is best across all scenarios, and the best metrics have achieved only small improvements in ranking faulty program elements.

    Source: Summary of advances and challenges · pp. 30–31

  • Takeaways & Limitations

    Further studies should examine fault interference and evaluate SFL in real development settings, including developers debugging their own code.

    Source: §10.3 · p. 28, §10.6 · p. 30

    Many techniques do not scale to industrial programs or receive in-situ evaluation, and current user studies have not involved developers debugging their own code.

    Source: §2.2 · p. 6, §10.6 · p. 30

Abstract

from arXiv · show

Despite being one of the most basic tasks in software development, debugging is still performed in a mostly manual way, leading to high cost and low performance. To address this problem, researchers have studied promising approaches, such as Spectrum-based Fault Localization (SFL) techniques, which pinpoint program elements more likely to contain faults. This survey discusses the state-of-the-art of SFL, including the different techniques that have been proposed, the type and number of faults they address, the types of spectra they use, the programs they utilize in their validation, the testing data that support them, and their use at industrial settings. Notwithstanding the advances, there are still challenges for the industry to adopt these techniques, which we analyze in this paper. SFL techniques should propose new ways to generate reduced sets of suspicious entities, combine different spectra to fine-tune the fault localization ability, use strategies to collect fine-grained coverage levels from suspicious coarser levels for balancing execution costs and output precision, and propose new techniques to cope with multiple-fault programs. Moreover, additional user studies are needed to understand better how SFL techniques can be used in practice. We conclude by presenting a concept map about topics and challenges for future research in SFL.

1 Introduction

Debugging remains largely manual and costly, motivating automated fault localization. This survey reviews SFL research from 2005 to October 2017, its challenges, and directions for future work.

1 Introduction

  • Manual fault localization can account for up to 75% of development costs and commonly involves searching code around failing tests.Developers use practices such as print statements, breakpoints, stack traces, and checking failing test cases.Source: §1 · pp. 1–2

1.1 Motivation and scope

  • SFL uses testing data to rank program entities more likely to be faulty, often with low overhead because the data are already collected during testing.The survey focuses on dynamic information from test execution, also called coverage-based fault localization.Source: §1.1 · p. 2, §1 · p. 2
  • SFL remains little known in practice, while studies often use small, single-fault programs unlike large programs with unknown and potentially interacting faults.User studies involving developers debugging real faulty programs with SFL are scarce.Source: §1.1 · p. 2
  • The survey reviews SFL techniques, spectra, faults, benchmark programs, testing data, costs, practical use, and challenges, and presents a concept map for future research.It summarizes features and limitations and identifies directions for improving SFL.Source: §1.1 · p. 2

2 Concepts and seminal studies

This section establishes fault-localization terminology and traces seminal approaches, from manual debugging and static techniques to methods informed by program execution. It also notes that many approaches have not scaled to industry or been assessed in real debugging situations.

Faults, errors, and failures

  • A fault is an incorrect program step, an error is an incorrect execution state, and a failure is an observable inability to meet expected requirements.An executed fault can change program state, and an error can lead to a wrong output observed as a failure.Source: Faults, errors, and failures · p. 3

Real and seeded faults

  • Seeded faults are intentionally inserted for experiments, whereas real faults arise naturally during software development.Faults may be seeded manually or through mutation testing.Source: Real and seeded faults · p. 3

Ranking metrics

Spectrum-based fault localization

  • Program spectra are entities covered during test execution; SFL uses this dynamic information to identify entities more likely to be faulty.Program spectra are also called code coverage, testing data, or execution traces.Source: Spectrum-based fault localization · p. 4

2.2 A Brief History of Debugging Techniques

  • Early testing-data approaches ranked executed paths using passing and failing tests, while execution dices contrasted dynamic slices from passing and failing tests.The survey notes that execution dices could still contain many program elements.Source: §2.2 · p. 5
  • Tarantula ranked statements from their frequency in passing and failing tests, while Delta Debugging reduced differences between passing and failing program states.Delta Debugging used program states rather than program elements.Source: §2.2 · p. 6
  • Static approaches included logical diagnosis and bug-pattern warnings, while earlier tools also used assertions, developer queries, and program dependence to guide fault search.MBD generated a logical model and reasoned toward a minimal set of statements explaining faults; PELAS used developer judgments and program dependence.Source: §2.2 · pp. 5–6
  • Many fault-localization techniques have not scaled to industrial programs or been assessed in real debugging situations, where developer behavior may differ from proponents’ expectations.SFL reuses testing data and tends to have lower overhead than other debugging techniques.Source: §2.2 · p. 6

3 Selection of studies and scope

The survey reviews experimentally evaluated SFL research published from 2005 through October 2017. It combines database searches and backward snowballing, then classifies the studies across six research topics.

3 Selection of studies and scope

  • The survey covers studies published from 2005 to October 2017, searched across four digital libraries.The libraries were ACM Digital Library, IEEE Xplore, SpringerLink, and SciVerse Scopus.Source: §3 · p. 6
  • Selection included experimentally evaluated proposals based on program spectrum data, comparisons of existing techniques, spectrum improvements, and assessments of SFL’s practical use.When available, the survey analyzed extended paper versions.Source: §3 · p. 6
  • The survey combined database searches with backward snowballing and read selected studies in full after screening titles and abstracts.Doubtful cases prompted reading additional sections before inclusion decisions.Source: §3 · pp. 6–7
  • The classification organizes studies into SFL techniques, spectra, faults, programs, testing data, and practical use; most studies span multiple topics.Figure 1 presents the taxonomy, and Sections 4–9 discuss studies under these topics.Source: §3 · p. 7, Figure 1 · p. 7

4 Spectrum-based Fault Localization techniques

SFL techniques use execution data to rank suspicious program entities through metrics, statistical and AI methods, execution models, program dependencies, and combinations of approaches. Comparisons show that metric performance depends on fault type and study setting.

4.1 Metric-based techniques

  • Metric-based techniques score entities from execution frequencies; Ochiai and Jaccard outperform Tarantula in the reported comparison.Other metrics are tailored to coverage types or fault settings, including O and Op for single-fault programs and Kulczynski2 and McCon for two simultaneous faults.Source: §4.1 · pp. 7–9

4.2 Statistics-based techniques

  • Statistical techniques assess test information through conditional probabilities, distributions, regression, association measures, or probabilistic cause-effect graphs.Examples include predicate bug relevance, causal effects between dependent entities, and estimated adjustments to suspiciousness lists.Source: §4.2 · pp. 9–10

4.3 Artificial intelligence-based techniques

  • AI-based techniques use spectrum data with methods including graph mining and SVMs, N-gram analysis, feature selection, and Markov Logic Networks.In one assessment, information gain and cosine performed comparably to Ochiai, but none of the 20 association measures significantly improved SFL [91].Source: §4.3 · pp. 10–11

4.4 Execution models

  • Execution models compare failing and passing behavior, including generated passing runs, graph-based suspiciousness propagation, and probabilistic models of state dependency.Some techniques toggle branches or predicates; others model calls, objects, or method patterns.Source: §4.4 · pp. 11–12

4.5 Program dependence-based techniques

  • Program-dependence approaches use graph influence, weighted coverage, or slices to prioritize entities, sometimes combining SFL with slicing or static analysis.Slice size and fault inclusion trade off: data slices can omit the fault, while full slices are larger and relevant slices include the fault in the reported cases.Source: §4.5 · pp. 12–13

4.6 Combination of SFL techniques

  • Combination techniques aggregate rankings, multiply metrics, evolve formulas, cluster metric lists, or combine SFL with information-retrieval results.Six of 30 ranking metrics created using genetic programming outperformed the comparison metrics.Source: §4.6 · pp. 13–14

4.7 Comparison of metric-based techniques

  • Cross-metric comparisons identify equivalences, but theoretical rankings do not always hold on studied programs, and metric groups can have complementary strengths and weaknesses.The survey notes that evaluation settings, including real versus seeded faults, can change which metrics perform better.Source: §4.7 · p. 14
  • Metallaxis and Op perform better for seeded faults, while DStar and Ochiai perform better for real faults.The survey also reports equivalent ranking metrics and comparisons whose findings vary across evaluation settings.Source: §4.7 · p. 14

5 Program spectra

Program spectra represent program structures at different coverage levels, from fine-grained statements to coarser entities and specialized execution information. Studies also combine coverage types or collect finer data selectively to manage costs.

5.1 Types of spectra

  • Statement coverage can point directly to faulty code, but developers may need to inspect many statements; other studies use blocks.Spectra also include predicates, paths, method calls, and other program structures.Source: §5 · pp. 14–15, §5.1 · p. 15
  • Different faults can be best located by different coverage types; averaging statement, branch, and dua suspiciousness achieved better results in one study.That study also approximated dua coverage from branch coverage at lower execution cost; other proposed spectra include time, information flow, key block chains, and mutants.Source: §5.1 · pp. 15–16
  • Selective collection gathers fine-grained coverage only for the most suspicious entities at a coarser level, reducing average fault-localization execution time.Another approach first uses Ochiai to narrow predicates before switching them, avoiding exponential growth in the switching phase.Source: §5.1 · p. 16

6 Faults

The survey treats fault count, interference, and fault characteristics as factors relevant to SFL performance. It describes approaches for multiple faults while noting practical and empirical boundaries in their evaluation.

6.1 Multiple faults

  • Multiple-fault techniques group or model failing tests and entities, but most SFL evaluations use single-fault programs despite unknown fault counts in industrial settings [65, 67, 69, 71].Approaches include clustering failures, voting among predicates, and diagnosis-based groups of statements.Source: §6.1 · pp. 16–17
  • Handling multiple faults often adds complexity; one study found 82.5% of bug-fixing commits had a single fault, though unknown faults may remain.Simultaneous faults can hide or expose other faults, and fault interference was observed in 67% of assessed programs.Source: §6.1 · p. 17, §6.2 · p. 17

6.2 Fault interference

  • Fault interference reduced Ochiai effectiveness by 20% in one study, while effectiveness improved in around 30% of cases; Chi-Square and Odds Ratio showed no difference as fault counts increased.Another study found a 2% decrease for finding the first fault, while localization of later faults worsened as fault counts grew; interference occurred in 80% of assessed programs.Source: §6.2 · pp. 17–18

6.3 Fault classification

  • Evidence on fault types is limited, and reported real faults include multi-line statements, code omission, non-executable code, and faults spread across many lines or files [84].Only 88 of 350 AspectJ bugs were judged identifiable using SFL; concurrency and environment-related bugs can be difficult to reproduce.Source: §6.3 · p. 18

7 Programs

The survey catalogs benchmark programs and their characteristics, then examines how program size and fault counts constrain the representativeness of SFL evaluations.

7.1 Description of the main programs

  • Common SFL benchmarks range from small program suites to medium and large programs, with Table 2 summarizing frequently used examples.The table reports average lines of code, faults, versions, and test cases; these values may vary across studies.Source: §7 · pp. 18–19, §7.1 · p. 19, Table 2 · p. 19
  • The Siemens suite has seven small C programs with one seeded fault per version, while the Unix suite contains small utilities with mutation-seeded faulty versions.Siemens test suites contain thousands of cases; its faults were seeded by ten people.Source: §7.1 · p. 19
  • Larger and more varied benchmarks include Space’s 38 real faults, iBugs’ 390 bugs, and Defects4J’s six Java programs with 395 real faults.Other examples include Flex, grep, gzip, make, NanoXML, Ant, and XML-security.Source: §7.1 · p. 20

7.2 Size

  • Program-size labels are not consistent across studies, although the survey generally treats over 10 KLOC as large, 2–10 KLOC as medium, and under 2 KLOC as small.Some experiments instrument only subsets of very large programs, which can still leave their representativeness open to criticism.Source: §7.2 · p. 20

7.3 Number of faults

  • Multiple-fault evaluation remains constrained because most existing programs have single faults, while generated multi-fault versions can introduce bias and hinder reproducibility.Real simultaneous faults are scarce and time-consuming to identify, though they can improve evaluation of SFL techniques.Source: §7.3 · p. 21

8 Testing data

The survey reviews testing-data strategies that seek to improve fault localization while balancing test-suite quality and execution cost. It covers test selection, coincidental correctness, oracle assessment, and mutation-based techniques.

8 Testing data

  • Testing data quality matters because test suites that exercise distinguishable code can improve localization precision, while large suites can raise execution costs.The section also considers evaluation concerns, coincidental correctness, and mutation testing.Source: §8 · p. 21

8.1 Test suite improvements

  • Six failing runs were optimal in Abreu et al.’s experiments; additional failing cases did not affect localization effectiveness.More failing cases exercising faulty statements improved effectiveness up to that point.Source: §8.1 · p. 21
  • Test-data strategies include splitting multi-assertion failing tests into atomic cases before dynamic slicing, and reducing or prioritizing suites while retaining coverage or diversity.Reduction strategies may still affect SFL effectiveness; other approaches clone failing tests to balance passing and failing cases.Source: §8.1 · p. 22
  • Coincidentally correct tests can lower faulty entities’ suspiciousness, and one approach uses k-means to identify such cases; similar execution traces can also flag divergent test-oracle results.Developer interaction has been used to exclude false-positive coincidental-correctness classifications.Source: §8.1 · p. 22

8.2 Mutation testing

  • Mutation-based SFL approaches use mutants to narrow fault candidates or compare how mutations at faulty and correct statements change failing tests.Mutation testing has also been used to seed experimental faults and suggest program repairs.Source: §8.2 · p. 22

9 Practical use

The survey examines how SFL is evaluated and used by developers, and reviews techniques that add contextual information to suspicious entities. It reports mixed user-study findings and identifies limits in conventional evaluation measures.

9.1 Evaluation metrics

  • EXAM score estimates the percentage of entities inspected before finding a fault, while related measures address predicates, multiple faults, precision, recall, and ranking quality.Ties in suspiciousness rankings can affect metric results, and studies have proposed tie-handling approaches.Source: §9.1 · p. 23
  • Relative ranking measures assume developers immediately understand and fix a fault upon reaching its element, but this assumption may fail and relative positions can be imprecise.Absolute counts of inspected entities may provide a more accurate effort measure regardless of program LOC.Source: §9.1 · p. 24

9.2 User studies

  • Developer studies report varied outcomes: GZoltar users located a fault in seven minutes on average, while 35% of controls found it within 30 minutes.Other studies found SFL sometimes increased debugging time or helped only when faults ranked near the top, while a professional-developer study reported improved effectiveness and efficiency.Source: §9.2 · pp. 24–25
  • The survey concludes that practice studies have divergent outcomes but each found at least some improvement for SFL participants, and calls for more studies in industrial settings.Other user studies observed developers using code knowledge rather than following ranking order, and gathered preferences for contextual debugging information.Source: §9.2 · pp. 24–25

9.3 Contextual information

  • Contextual techniques enrich suspiciousness lists with correlated paths, bug signatures, developer feedback, source-code terms, or hierarchical method-and-block views.Other approaches use call-graph context, generated tests, reliability oracles, and semantic-dynamic analyses to provide explanations or filter results.Source: §9.3 · pp. 25–26

10 Discussion

The discussion reviews SFL techniques and spectra, highlighting limits in ranking effectiveness, computational costs, and the context provided to developers. It identifies opportunities to combine techniques and spectra while balancing localization precision with execution and inspection costs.

10.1 Techniques

  • Ochiai has outperformed other ranking metrics, but the best metrics differ by only around 1% less code to examine in most cases, suggesting a ranking-metric barrier.Ochiai accounts for statement absence in failing runs, whereas Tarantula does not; the metrics also differ in how they treat passing runs.Source: §10.1 · p. 26
  • Artificial-intelligence techniques carry high computational costs, while program-dependence approaches can require costly information-reduction strategies, especially for large programs.These methods may provide contextual information about faults, but further studies are needed to improve their results.Source: §10.1 · p. 27
  • Combining SFL techniques requires understanding how their strengths and weaknesses vary across program characteristics.That understanding can inform ways to improve fault localization.Source: §10.1 · p. 27

10.2 Spectra

  • Spectrum choice affects execution costs, available analysis data, and the outputs developers inspect; coarser spectra may reduce instrumentation costs.Method coverage is an example of a coarser spectrum.Source: §10.2 · p. 27
  • Method spectra can add code-region context, but developers may need to inspect more code than with statement spectra, and studies have not yet compared these approaches.Classes may also help explain faults, although they generally contain substantial code.Source: §10.2 · p. 27
  • Data-flow information can improve fault localization, but collecting and processing it costs more than control-flow data, and relatively few SFL studies have explored it.Strategies that reduce data-flow collection costs could make these approaches more feasible for practical use.Source: §10.2 · p. 27

10.3 Faults

The discussion finds that evidence on multiple-fault localization remains limited and difficult to compare, while fault-type behavior is rarely examined. It also calls for broader, more realistic program benchmarks, including end-user programs and multiple-fault versions.

10.3 Faults

  • Most SFL evaluations use single-fault programs; multiple-fault experiments are often smaller, and proposed multiple-fault techniques have not been compared.Some multiple-fault experiments use fewer programs than single-fault experiments.Source: §10.3 · pp. 27–28
  • Randomly merging single-fault versions creates multiple-fault benchmarks through differing procedures, impairing comparisons between techniques.The absence of programs containing multiple faults makes experiments difficult.Source: §10.3 · p. 28
  • Multiple faults have been associated with an average 2% decrease in effectiveness, but may increase effectiveness when different faults fail on different test cases.For large programs, a 2% decrease may still represent substantial code to inspect.Source: §10.3 · p. 28
  • Simultaneous faults can interfere, and randomly distributed faults do not ensure realistic interference between them.Further study is needed to investigate fault interference's effects on localization.Source: §10.3 · p. 28
  • SFL behavior across fault types is rarely studied; some techniques explicitly do not identify faults caused by code omission.Evaluating techniques by fault type can reveal strengths and weaknesses and inform techniques for particular fault types.Source: §10.3 · p. 28
  • Multi-statement fault localization must locate faults across code regions and provide clues for non-executable statements or sites needing additional code.Examples of useful clues include variable or class names.Source: §10.3 · p. 28

10.4 Programs

  • Evaluations need programs from diverse domains and end-user settings; current real-program benchmarks are often frameworks and libraries.Seeded and real faults can produce different SFL results, and new programs should be available to researchers.Source: §10.4 · p. 29

10.5 Testing data

The discussion treats test-suite distinguishability as a fault-localization quality and highlights trade-offs in test size and ranking-based evaluation. For practical use, it calls for more informative results and user studies in real development settings.

10.5 Testing data

  • Fault-localization-capable test suites should distinguish program elements across test cases, beyond measuring coverage or failure detection alone.Test-suite reduction must balance fewer test cases against preserving that distinguishability.Source: §10.5 · p. 29
  • Test cases covering little code may help highlight suspicious excerpts, whereas cases covering many excerpts may add excessive entities and impair localization.The survey calls for new ways to measure testing-data quality for fault localization.Source: §10.5 · p. 29

10.6 Practical use

  • A faulty statement in the top 1% of a 100 KLOC program can still require inspecting 1 KLOC, so relative ranking may misrepresent debugging effort.The discussion notes that developers tend to abandon SFL lists if the fault is not among their first picks, and recommends focusing on absolute position.Source: §10.6 · p. 29
  • SFL lists may combine unrelated entities, so grouping related code, showing multiple code levels, or adding source and trace information can provide developers more context.Future approaches should reduce non-relevant information and enrich what developers receive.Source: §10.6 · p. 29
  • User studies are needed to test assumptions about developer behavior, but they remain scarce and have divergent results amid participant and sampling difficulties.The discussion identifies a need to assess use, acceptance, and guidance for SFL in industrial settings.Source: §10.6 · pp. 29–30
  • Evaluations in real development scenarios are lacking, and existing user studies have involved participants unfamiliar with the code being debugged.The discussion raises whether SFL improves developers' performance on their own code as a question for future study.Source: §10.6 · p. 30

10.7 Concept map in Spectrum-based Fault Localization

The concept map organizes SFL’s main features and relationships, including challenges to using the techniques in real development settings. The survey’s synthesis highlights advances and open questions spanning ranking, spectra, faults, evaluation, and practical use.

10.7 Concept map in Spectrum-based Fault Localization

  • The concept map represents relationships among SFL’s main features and surfaces challenges to achieving use in real development settings.It is based on the survey’s analysis and is intended to help researchers relate contributions, issues, and future topics.Source: §10.7 · p. 30, Figure 2 · p. 30

Summary of advances and challenges

  • No ranking metric is best across all scenarios, and reported improvements in ranking faulty elements have been small.Some metrics perform better in particular scenarios, while studies have also found equivalent results among metrics.Source: Summary of advances and challenges · pp. 30–31
  • Method-level spectra may provide broader bug context despite lower precision, but spectrum comparisons and richer data-flow spectra need further study.The survey also identifies contextual outputs, such as execution paths and combined-spectrum lists, as open questions for developer use.Source: Summary of advances and challenges · p. 31
  • Fault type, interactions among faults, and program characteristics affect SFL assessment; omission faults and realistic program settings remain challenges.The survey notes that evaluations often differ from practice, where programs may have small test suites, large methods, legacy code, or multiple languages.Source: Summary of advances and challenges · p. 31
  • Absolute inspected-element counts better reflect practice than percentages; tests covering distinguishable code excerpts can improve SFL effectiveness.The survey says percentages help compare techniques but do not evaluate how developers use them, since developers do not seem willing to inspect many excerpts.Source: Summary of advances and challenges · p. 31
  • User studies are rare, and replications and studies with professional developers in real settings are needed to understand practical use.Source: Summary of advances and challenges · p. 31
  • SFL improvement spans test and spectrum selection, suspiciousness calculation, assessment across program and fault characteristics, effectiveness measurement, useful outputs, and practical-use assessment.The survey presents understanding how these concerns relate as a route to proposing improvements.Source: Summary of advances and challenges · p. 31

11 Related work

Earlier surveys covered fault localization broadly or focused on other classifications and time periods. This survey centers on SFL from 2005 to October 2017, adds a historical overview, and addresses practical adoption and related research topics.

11 Related work

  • Alipour’s survey addressed six SFL studies and judged the techniques far from practical use; Agarwal and Agrawal reviewed 30 papers from 2007 to 2013.The former emphasized model checking, while the latter found substantial focus on test-suite improvements and SFL.Source: §11 · pp. 31–32
  • Wong et al.’s survey covered fault-localization techniques from 1977 to November 2014 in eight categories, including spectrum-based methods.Source: §11 · p. 32
  • This survey focuses on SFL work from 2005 to October 2017, adds a history of automated debugging from the 1950s to 2004, and uses snowballing alongside database search.Source: §11 · p. 32
  • Its coverage extends to adoption topics, testing improvements, mutation-based fault localization, and a concept map of field topics and their relationships.Adoption topics include user studies and contextual information intended to improve developer program comprehension.Source: §11 · p. 32

12 Conclusion

The survey synthesizes SFL techniques, spectra, faults, programs, testing data, and practical use. It reports advances alongside challenges and presents a concept map relating the field’s topics and future research challenges.

12 Conclusion

  • The survey provides a broad overview of SFL techniques, spectra, faults, programs, testing data, and practical use.Source: §12 · p. 32
  • Recent SFL studies have evaluated real programs, provided additional information for localization, and increasingly targeted faults among the first suspiciousness-list picks.Source: §12 · p. 32
  • Future work should reduce suspicious-entity sets, combine spectra, balance fine-grained coverage precision against collection costs, and address multiple-fault programs.Large programs from diverse domains, with varied fault types and multiple faults, are proposed as more realistic evaluation scenarios.Source: §12 · pp. 32–33
  • The survey’s concept map represents relationships among SFL topics and challenges for future research.Source: §12 · p. 33
Loading 1607.04347v2…