Experimental evaluation of using dynamic slices for fault location

Xiangyu Zhang, Haifeng He, Neelam Gupta, Rajiv GuptaAADEBUG 2005 · DOI

TL;DR

This paper presents an experimental evaluation of three dynamic slicing algorithms (data, full, and relevant) for fault localization in software. The authors found that while data slices are the smallest, they are less effective at capturing faulty statements. Relevant slices, though slightly larger, proved to be the most effective at identifying faulty code, suggesting dynamic slicing is a powerful debugging aid.

What Problem Does This Paper Address?

Debugging complex software is a time-consuming and challenging task. Program slicing, a technique that helps reduce the set of statements a developer needs to examine, has been proposed as a debugging aid. While static slicing considers the entire program, dynamic slicing focuses on the statements executed during a specific program run that are relevant to a particular output. However, despite the theoretical benefits of dynamic slicing, there was a lack of detailed experimental studies evaluating its effectiveness in pinpointing faulty statements. This paper aims to fill that gap by empirically comparing different dynamic slicing algorithms.

Methods

The authors developed a dynamic slicing framework that uses dynamic instrumentation to collect runtime information and reduced ordered Binary Decision Diagrams (roBDDs) for efficient storage. They implemented and evaluated three variants of dynamic slicing algorithms:

  • Data Slicing: Identifies statements that directly or indirectly influence a faulty output value through chains of dynamic data dependencies.
  • Full Slicing: Extends data slicing by also considering dynamic control dependencies.
  • Relevant Slicing: Further enhances full slicing by including predicates that could have affected the output (even if they didn't in the specific execution), along with their direct data dependencies and chains of dynamic data/control dependencies.

The evaluation involved running these algorithms on a suite of benchmark programs with injected faults and analyzing the size of the slices and whether they contained the faulty statement.

Datasets

The paper uses benchmark programs from the Siemens suite and other medium-sized Linux utility programs. Specifically, they mention using versions of print_tokens, print_tokens2, replace, schedule, schedule2, gzip2, gzip5, and flex. They excluded programs like tcas (too small) and tot_info (used floating-point arithmetic, which their tool didn't support at the time). The faulty programs and test cases were sourced from a public repository.

Key Insights and Ideas

  • Data slices are small but often miss faults: While appealing for their brevity, data slices frequently fail to include the actual faulty statement, especially for predicate faults.
  • Full slices are more comprehensive but larger: By incorporating control dependencies, full slices are more likely to capture faults missed by data slices, but at the cost of increased size.
  • Relevant slices offer the best balance: Relevant slicing, by considering potentially influential predicates, proved to be the most effective at capturing faulty statements, often with a slice size comparable to full slices.
  • Dynamic slicing significantly reduces debugging effort: Even the largest slices (relevant slices) were orders of magnitude smaller than the total number of executed statements, demonstrating the practical utility of these techniques.
  • The "potential dependence" concept is crucial: Relevant slicing's ability to capture faults missed by full slicing hinges on its consideration of predicates that could have altered program flow, even if they didn't in the specific execution trace.

Key Results

  • Slice Size: Data slices were consistently the smallest, followed by full slices, and then relevant slices. For example, on the flex benchmark, average slice sizes were 8 (DS), 65 (FS), and 180 (RS) out of approximately 1500 executed statements.
  • Fault Capture:
    • Data slices captured faulty statements for assignment faults in large programs like gzip5 and flex but were less effective for predicate faults.
  • Full slices showed a high chance of capturing both assignment and predicate faults.
  • Relevant slices were found to be the most effective, capturing all faulty statements in the experiments.
  • Efficiency: Data slicing was the fastest, while relevant slicing was the slowest. However, the overhead was generally acceptable, with slowdown factors ranging from 1.04 to 2.81 for relevant slicing on the tested benchmarks. Memory consumption was relatively stable.

Limitations and Future Work

  • Limitations:
    • The study focused on specific types of faults (assignment and predicate faults) and did not consider other types like missing code.
  • The tool's support for floating-point programs was limited.
  • The performance overhead, while acceptable, was higher for relevant slicing.
  • The study primarily examined single-fault scenarios.
  • Future Work:
    • The authors suggest that their technique could be combined with other fault localization methods (e.g., Zeller's cause-effect chains) to further refine fault candidate sets.
  • Exploring the impact of multiple faults on dynamic slicing effectiveness would be a valuable next step.
  • Further optimization of relevant slicing algorithms could reduce performance overhead.

Summary updated

BibTeX
@inproceedings{zhang2005experimental,
  author = {Xiangyu Zhang and Haifeng He and Neelam Gupta and Rajiv Gupta},
  title = {{Experimental evaluation of using dynamic slices for fault location}},
  booktitle = {AADEBUG},
  year = {2005},
  doi = {10.1145/1085130.1085135},
}
Figure