PaperlayerView exact revision on arXiv

Source-linked AI summary

Locating Faults with Program Slicing: An Empirical Analysis

Ezekiel Soremekun, Lukas Kirschner, Marcel Böhme, Andreas Zeller

arXiv:2101.03008v1cs.SE

TL;DR

Fault localization must identify code locations associated with a failure, and prior slicing evaluations had not compared its effectiveness with statistical debugging. This paper evaluates statistical debugging, dynamic slicing, and a hybrid that begins with ranked suspicious statements before switching to dependencies. The hybrid performs best across the reported fault counts and error types, while slicing and statistical debugging differ by setting.

  • Problem

    The study addresses the lack of empirical comparisons between program slicing and statistical debugging, techniques used to identify code locations associated with failures.

    Source: §1 · pp. 2–3

  • Method

    The paper compares dynamic slicing with statistical debugging formulas and evaluates a hybrid that checks top-ranked suspicious statements before following dynamic dependencies.

    Source: §1 · pp. 3–4

  • Results

    The hybrid localizes faults within the top 20 statements for 98% of errors, outperforming slicing and statistical debugging regardless of fault count or error type.

    Source: §1 · p. 5

  • Takeaways & Limitations

    Dynamic dependency tracing is the recommended primary method for human debugging, while top-ranked statistical locations remain preferable for automated repair’s small candidate sets.

    Source: §9 · p. 43

    The study flags missing statements in slices as an external-validity threat.

    Source: §6.1 · p. 40

Abstract

from arXiv · show

Statistical fault localization is an easily deployed technique for quickly determining candidates for faulty code locations. If a human programmer has to search the fault beyond the top candidate locations, though, more traditional techniques of following dependencies along dynamic slices may be better suited. In a large study of 457 bugs (369 single faults and 88 multiple faults) in 46 open source C programs, we compare the effectiveness of statistical fault localization against dynamic slicing. For single faults, we find that dynamic slicing was eight percentage points more effective than the best performing statistical debugging formula; for 66% of the bugs, dynamic slicing finds the fault earlier than the best performing statistical debugging formula. In our evaluation, dynamic slicing is more effective for programs with single fault, but statistical debugging performs better on multiple faults. Best results, however, are obtained by a hybrid approach: If programmers first examine at most the top five most suspicious locations from statistical debugging, and then switch to dynamic slices, on average, they will need to examine 15% (30 lines) of the code. These findings hold for 18 most effective statistical debugging formulas and our results are independent of the number of faults (i.e. single or multiple faults) and error type (i.e. artificial or real errors).

1 Introduction

The paper compares statistical fault localization with dynamic slicing, then evaluates a hybrid that starts with suspicious statements and switches to slicing. The findings distinguish the methods’ effectiveness by fault setting and identify the hybrid as the strongest overall approach.

1 Introduction

  • Automated fault localization seeks code locations where faults cause failures, serving as a prerequisite for fixing bugs and a source of candidate locations for automated repair.Source: §1 · p. 2
  • The study compares the most effective statistical debugging formulas with dynamic slicing, addressing a gap left by earlier evaluations of slicing algorithms.It evaluates hundreds of faults in C programs.Source: §1 · p. 3
  • The evaluation covers 457 bugs in 46 programs, comprising 369 single faults and 88 multiple faults.The study reports 707 program faults in total.Source: §1 · p. 3
  • In the top 5% of suspicious locations, statistical debugging localizes faults in twice as many buggy programs as dynamic slicing.The passage reports 6% for statistical debugging versus 3% for slicing.Source: §1 · pp. 3–4
  • Dynamic slicing is more effective for single faults, whereas statistical debugging performs better on multiple faults.The paper also reports that dynamic slicing is 62% more likely to find single-fault locations earlier than statistical debugging.Source: §1 · p. 4
  • For 98% of errors, the hybrid localizes a fault within the top 20 statements, while slicing and statistical debugging require about 100 lines of code for the same coverage.The hybrid is reported as more effective regardless of error type or number of faults.Source: §1 · p. 5

2 Background

The background introduces slicing as backward dependency tracing from a failure symptom and contrasts static, dynamic, and approximate variants with statistical debugging. The distinctions concern which dependencies and execution evidence each technique uses.

2.1 Program Slicing

  • Program slicing traces dependencies backward from the statement where an error is observed to identify statements that influence it.The traversal continues transitively toward the failure’s root cause.Source: §2.1 · pp. 5–6

2.2 Static Slicing

  • A static slice includes every statement reachable from the criterion in the program dependence graph, so it retains statements that may not affect the observed failure.The graph captures control and data dependencies; static slices can be very large.Source: §2.2 · p. 6

2.3 Dynamic, Relevant, and Execution Slicing

  • A dynamic slice uses statement instances from a particular failing execution to capture statements involved in the observed values, while a relevant slice also accounts for alternative paths.The relevant slice adds executed conditionals that could have enabled a different path and value at the criterion.Source: §2.3 · pp. 6–7
  • The approximate dynamic slice consists of executed statements in the static slice and subsumes both dynamic and relevant slices while remaining smaller than the static slice.The evaluation implements approximate dynamic slicing and refers to it as “dynamic slicing.”Source: §2.3 · p. 7

2.4 Statistical Debugging

  • Statistical debugging ranks program elements by how strongly their execution is associated with failure across passing and failing runs.The paper evaluates 18 formulas in four groups: human-generated, popular, genetic-programming evolved, and single-bug optimal measures.Source: §2.4 · pp. 8–9

3 A Hybrid Approach

The hybrid combines statistical debugging’s shortlist with dependency tracing through a dynamic slice. Its two phases reflect the practice of moving to traditional debugging when the highest-ranked locations do not reveal the fault.

3 A Hybrid Approach

  • Statistical debugging can identify a single faulty statement as the top-ranked location for about 40% of errors in IntroClass and SIR.The cited results describe cases where a developer can find the fault after inspecting one suspicious statement.Source: §3 · pp. 9–10
  • A top-five shortlist before switching to slicing matches surveyed practice: three quarters of practitioners would inspect no more than five ranked statements before trying alternatives.Prior observations also report that programmers transition to traditional debugging after failing to locate a fault among the first N ranked statements.Source: §3 · p. 10
  • The hybrid first reports the top N suspicious statements from statistical debugging, then reports uninspected statements in the symptomatic statement’s dynamic backward dependencies.The first phase can use N = 5; the second phase excludes statements already reported.Source: §3 · pp. 10–11

4 Evaluation Setup

The evaluation asks how statistical debugging, dynamic slicing, and their hybrid compare in fault-localization effectiveness, and whether error type or fault count changes those comparisons. It fixes the analysis at statement granularity and evaluates relative wasted effort.

4 Evaluation Setup

  • The evaluation compares statistical debugging, dynamic slicing, and the hybrid, including which approach is most effective and most likely to find faults earlier.The research questions also ask how many suspicious statements to inspect before switching to slicing.Source: §4 · p. 11
  • The study tests whether effectiveness differs between real and artificial errors and between single- and multiple-fault programs.Source: §4 · p. 11
  • The evaluation fixes fault localization at statement level and one-at-a-time mode, except for multiple faults, and measures relative wasted effort from the order of suggested units.Real errors use real test suites that may not execute every program statement.Source: §4 · p. 11

4.1 Implementation

The implementation combines coverage- and dependency-based tools, with a hybrid that starts from statistical debugging’s top-ranked statements and switches to slicing if needed.

4.1 Implementation

  • The implementation section introduces the tools used to realize the paper’s fault-localization techniques.The hybrid combines the statistical debugging and dynamic slicing tools.Source: §4.1 · p. 11, §4.1.3 · p. 12

4.1.1 Dynamic Slicing Implementation

  • Approximate dynamic slices intersect executed statements with static slices computed by Frama-C, using coverage, patch, and debugger information.The pipeline identifies changed statements with git-diff, obtains coverage with gcov, and uses gdb to obtain coverage for crashes and select a slicing criterion.Source: §4.1.1 · p. 12

4.1.2 Statistical Debugging Implementation

  • Statistical debugging ranks executable statements using scores computed from coverage and patch information collected with gcov, git-diff, and gdb.Some errors were excluded when patches only added statements; coverage could also be unavailable for cases such as infinite recursion.Source: §4.1.2 · p. 12

4.1.3 Hybrid Approach Implementation

  • The hybrid first takes the top N suspicious statements, then uses slicing if the fault is not among them, accounting for statements already inspected.Its ranking uses suspiciousness and line numbers; the reported effort combines the initial statements with those inspected in the slice before the first fault.Source: §4.1.3 · pp. 12–13

4.2 Metrics and Measures

The paper uses effect-size and significance measures to compare techniques, and cumulative frequency curves to show how much code inspection localization requires.

Odds Ratio ψ

  • The odds ratio ψ compares the relative success of two techniques; ψ = 1 indicates no difference, while ψ > 1 favors technique A.A positive correction constant ρ avoids problems with zero successes.Source: §4.2 · p. 13

Mann-Whitney U-test

  • The Mann–Whitney U-test assesses whether two techniques differ statistically without requiring normally distributed data.The paper uses it to test whether a performance difference is statistically significant.Source: §4.2 · p. 13

Cumulative frequency curves

  • Cumulative frequency curves show the percentage of errors requiring inspection of up to a given number of locations, with location counts on a log scale.The log scale makes differences at small inspection counts more prominent than equal-sized differences at large counts.Source: §4.2 · p. 14

4.3 Objects of Empirical Analysis

The evaluation draws on four C-program benchmarks containing real and injected faults, with separate curation for single-fault and multiple-fault cases.

Programs and Bugs

  • The benchmarks cover seeded SIR faults, student-written IntroClass programs, Codeflaws competition programs, and real errors from CoREBench open-source projects.CoREBench’s included projects are Coreutils, Grep, and Find; their wider code bases total 83k, 18k, and 11k LoC, respectively.Source: §4.3 · pp. 14, 16

Subject-program selection; Minimal Patches

  • Programs were excluded when Frama-C could not build a dependence graph, coverage was unavailable, or a faulty statement could not be identified; omission faults were also excluded.The study defines faulty statements from changed statements in patches, and notes that omission faults require special handling because their faulty location is unclear.Source: §4.3 · pp. 16–17

Single Faults; Multiple Faults

  • The dataset contained 369 buggy program versions, 368 (99.7%) with a single fault; the multiple-fault dataset comprised 88 programs with 338 injected faults, averaging about four per program.The authors report no known benchmark of real-world programs containing multiple faults.Source: §4.3 · pp. 16–17

Programs and Bugs

  • The corpus spans four benchmarks and 46 programs in 35 tools, with 457 errors comprising 369 single faults and 88 multiple-fault programs.The benchmarks include real-world errors and seeded faults from different sources.Source: §4.3 · pp. 14, 18

4.4 Measure of Localization Effectiveness

Localization effectiveness is measured by how much code a developer must inspect before finding the first fault, using rankings tailored to slicing, statistical debugging, and the hybrid.

4.4 Measure of Localization Effectiveness

  • Effectiveness is the complement of the proportion of statements inspected before the first fault, so 0 is worst and 1 is best.The measure captures effort to find a starting point for fixing, not the complete set of code changes needed.Source: §4.4 · p. 18

4.4.1 General Measures

  • All techniques rank statements for inspection; ties are ordinally broken by line number, and multiple-fault evaluation uses the percentage of executable statements inspected before the first fault.For multiple faults, the measure assumes finding the first fault is sufficient to begin diagnosis.Source: §4.4.1 · p. 19

4.4.2 Dynamic Slicing Effectiveness

  • Dynamic-slicing effectiveness marks slice statements within the minimum backward-dependency distance from the failure location to a fault, then measures their proportion in the slice.The distance starts at the symptomatic statement and follows backward dependency edges.Source: §4.4.2 · pp. 19–20

4.4.3 Statistical Debugging Effectiveness

  • Statistical-debugging effectiveness uses the rank of the highest-ranked faulty statement relative to all program statements, complementing the EXAM-score.The evaluation conservatively assumes a developer may need to inspect other statements tied at the faulty statement’s rank.Source: §4.4.3 · p. 20

4.4.4 Hybrid Approach Effectiveness

  • The hybrid uses the statistical-debugging score when a fault is within the top N suspicious statements; otherwise, it scores slicing while accounting for statements already reported.The top N statements are ordered by suspiciousness and then line number.Source: §4.4.4 · p. 21

4.5 Infrastructure

The experiments ran in a virtual machine with Arch Linux on a Dell Precision 7510.

4.5 Infrastructure

5 Evaluation Results

This section evaluates the hybrid approach, dynamic slicing, and statistical debugging across fault counts, error types, and program sizes. It reports how their relative effectiveness varies across these settings and when to switch from statistical debugging to slicing.

5 Evaluation Results

  • Dynamic slicing ranked single faults within the top 21% of executable statements on average, and within its top 5–10 statements for 62%–78% of errors.For the top 20 statements, it located 55% of artificial errors and 92% of real errors.Source: §5.1 · p. 22

5.2 RQ2: Effectiveness of Statistical Debugging

  • Kulczynski2 was the most effective statistical formula overall (0.737), requiring inspection of 26% of code (51 LoC) on average.It was not significantly better than the best-performing formula in each other statistical debugging family.Source: Table 4 · p. 23, §5.2 · pp. 24–26

5.3 RQ3: Comparing Statistical Debugging and Dynamic Slicing

  • Dynamic slicing was 8 percentage points more effective than Kulczynski2, found faults earlier for 66% of bugs, and was 62% more likely to do so, significantly.Slicing consistently outperformed statistical debugging across benchmarks.Source: Figure 8 · p. 27, §5.3 · pp. 27–28

5.5 RQ5: Effectiveness of the Hybrid Approach

  • Hybrid-2 was 69% more likely than Kulczynski2 to find a fault earlier, and it found faults earlier than both alternatives for 56% of bugs.The odds-ratio comparison favored the hybrid approach across all projects; it was also 42% less likely to find a fault early when using slicing instead of Hybrid-2.Source: Table 7 · p. 28, §5.5 · p. 31

5.4 RQ4: Sensitiveness of the Hybrid Approach

  • Programmers localized more errors by switching after five statistical candidates, while the tool was most effective at N = 2; both settings outperformed slicing and Kulczynski2.The study recommends inspecting at most five candidates before switching to slicing, with N = 2 best for the tool.Source: Figure 9 · p. 29, §5.4 · p. 29

5.5 RQ5: Effectiveness of the Hybrid Approach

  • Hybrid-2 was about 7 percentage points more effective than slicing and 15 points more effective than statistical debugging, requiring 58% and 75% as many statements, respectively.The comparison is against dynamic slicing and Kulczynski2, respectively.Source: Table 8 · p. 30, §5.5 · p. 30
  • The hybrid approach localized 98% of bugs after inspecting no more than 20 statements, while slicing and statistical debugging needed about 100 LoC to reach 98%.At 20 LoC, slicing and statistical debugging localized about 85% and 88% of bugs, respectively.Source: Table 8 · p. 30, §5.5 · p. 30, Figure 10 · p. 31

5.6 RQ6: Real Errors vs. Artificial Errors

  • PattSim 2 is the most effective formula for artificial faults, while Kulczynski2 and Tarantula are most effective for real faults, so artificial-fault results do not predict real-fault effectiveness.The authors recommend evaluating fault-localization techniques on real faults.Source: §5.6 · pp. 32–34
  • Dynamic slicing inspects 21% of the program versus Kulczynski2’s 18% on artificial faults, while on real faults slicing inspects 18% versus statistical debugging’s 25%.The reported comparison reverses by error type: statistical debugging performs better on artificial faults, and dynamic slicing on real faults.Source: §5.6 · p. 33
  • Across artificial and real faults, the hybrid approach inspects 0.3 to 0.7 times as many statements as slicing or statistical debugging.The paper reports this advantage as independent of error type.Source: §5.6 · p. 33
  • Among real faults, Tarantula and Kulczynski2 score 0.76 and 0.70 on small programs, while DStar scores 0.80 versus their 0.79 on large programs.Across program sizes, the overall technique ranking remains hybrid first, slicing second, and statistical debugging third.Source: §5.6 · p. 34

5.7 RQ7: Single Fault vs. Multiple Faults

  • The hybrid approach outperforms dynamic slicing and statistical debugging regardless of whether programs contain single or multiple faults.The comparison is reported for the SIR and IntroClass benchmarks.Source: Table 10 · p. 35, Figure 11 · p. 36, §5.7 · p. 37
  • Tarantula scores 0.8269 versus dynamic slicing’s 0.6922 on multiple faults, whereas slicing scores 0.8269 versus Tarantula’s 0.7186 on single faults.The authors attribute slicing’s difficulty with multiple faults to its use of a slice from only one failing test case.Source: Table 10 · p. 35, §5.7 · p. 37
  • Except for dynamic slicing, techniques improve by 2 to 11 percentage points on multiple faults; Tarantula improves by 11%, while the hybrid approach improves by 2 to 3 percentage points.The paper concludes that statistical debugging is better suited to multiple faults, while slicing is more effective for single faults.Source: §5.7 · p. 38

6 Threats to Validity

The study’s validity is bounded by its open-source C subjects and evaluation choices. It also notes construct-validity risks in its effectiveness measure and implementations.

6.1 External Validity

  • The benchmarks include real developer errors alongside injected faults, whose injection can cause accidental faults or spurious failures.The authors state that benchmark failing tests are guaranteed to fail because of the error.Source: §6.1 · p. 39
  • Results may not generalize beyond maintained open-source C projects; the authors recommend replication on real errors in other languages.They also note that commercially developed software may contain errors of different kinds and complexity.Source: §6.1 · p. 39
  • Supplied test suites range from tens to tens of thousands of cases and were neither expanded nor reduced, approximating typical project debugging.The authors note that test-suite size can affect AFL performance and that test-generation or reduction methods may change it.Source: §6.1 · p. 39
  • Slicing can discard faulty statements, but the study mitigates this by inspecting slice statements first and reports eventually finding every evaluated bug.Prior work found the faulty statement among the ten most suspicious statements in 91% of cases.Source: §6.1 · p. 40

6.2 Construct Validity

  • Effectiveness is measured as ranking-based relative wasted effort, while flaws in the 18 statistical techniques, approximate slicing, or evaluation remain possible.The authors make implementations and results available for public scrutiny.Source: §6.2 · p. 40

7 Future Work

The authors identify unmodeled cognitive load and alternative search strategies as open issues for dependency-based localization. They also point to input reduction, symbolic methods, and combining techniques as directions for further work.

7 Future Work

  • The study did not model the cognitive load of understanding statements in context, though dependency following is expected to stay within more similar contexts.The authors call for human studies to determine which techniques work best for people.Source: §7 · pp. 40–41
  • Alternative dependency traversals—starting from inputs, suspicious or changed locations, or coarse-to-fine code—may improve efficiency and cognitive load.The authors call for further human studies of these strategies.Source: §7 · p. 41
  • Delta debugging can reduce the search space by narrowing the conditions under which failure occurs; prior work reports human-efficiency gains and substantial reductions over dynamic slices.Burger and Zeller reported reducing the search space to 13.7% of the dynamic slice or 0.22% of source code.Source: §7 · p. 41
  • Symbolic execution and constraint solving could narrow possible faults, while the authors suggest combining suspicious locations, dependency tracing, and symbolic analysis.The proposed combination skips influences deemed impossible by symbolic analysis.Source: §7 · p. 41

8 Related Work

Earlier empirical work studied statistical localization and dynamic slicing, but did not compare their effectiveness directly. Related improvements often alter spectra or combine statistical debugging with other methods, without directly using program slicing as fault localization.

8.1 Evaluation of Fault Localization Techniques

  • Earlier evaluations examined statistical debugging effects, including test-case counts and real versus artificial faults, but did not compare slicing with statistical debugging.Prior work found that artificial-fault results did not predict real-fault results, and that a hybrid technique outperformed both evaluated techniques.Source: §8.1 · pp. 41–42
  • Dynamic-slice studies evaluated slicing variants and potential memory-address dependence, but did not empirically compare slicing against statistical debugging.These studies also found that slicing reduced the statements examined to locate faults.Source: §8.1 · p. 42

8.2 Improvements of Statistical Fault Localization

  • Statistical-localization improvements often reduce program spectra using methods such as slicing, test generation, prioritization, or machine learning.Other approaches use page rank or learning to rank to improve statistical debugging.Source: §8.2 · p. 42
  • Other combinations include Bayesian reasoning with model-based diagnosis and search-based test generation with SBFL, but they do not localize faults by following program dependencies.SENDYS combines statistical debugging with slicing hitting set computation, using statistical results as prior fault probabilities for statements.Source: §8.2 · p. 43

9 Conclusion and Consequences

For human debugging, the authors favor dynamic slicing beyond statistical debugging’s top-ranked starting points, while automated repair benefits from a small suspicious-location set. They caution that the evaluated techniques are not necessarily the best available and point to broader combinations and evaluation.

9 Conclusion and Consequences

  • For human debugging, dynamic slicing is recommended beyond statistical debugging’s top-ranked starting points; for automated repair, small sets of top-ranked locations remain the preferred strategy.The authors also say repair tools could benefit from static and dynamic dependencies.Source: §9 · p. 43
  • The evaluated techniques should not be treated as the best possible fault localization methods; reducing inputs or executions may substantially improve localization.The paper also identifies grammar-based and symbolic techniques as potential sources of contextual information or more precise fault localization.Source: §9 · pp. 43–44
  • The authors identify combining available techniques in ways that work across programs and help real programmers as a key challenge.They mention combining statistical suspiciousness, dependency tracing, and symbolic analysis as one possible direction.Source: §9 · p. 44
  • Scripts, tools, benchmarks, and results are freely available to support scrutiny, evaluation, reproduction, and extension.The artifact is presented as additional material.Source: §9 · p. 44
Loading 2101.03008v1…