TL;DR
This paper investigates combining Dynamic Slicing (DS) and Spectrum-Based Fault Localization (SFL) for automated bug finding. Their proposed "Tandem-FL" approach significantly improves fault localization accuracy, reducing the search space for developers and showing that the risk of missing actual bugs with this combined method is low.
What Problem Does This Paper Address?
Debugging software is a time-consuming and expensive process. A major bottleneck is fault localization: pinpointing the exact location of a bug within a large codebase. While various automated techniques exist, two popular ones are:
- Spectrum-Based Fault Localization (SFL): This method analyzes the execution traces of passing and failing tests to identify which code components are most likely to be faulty. It essentially ranks components by their "suspiciousness."
- Dynamic Slicing (DS): This technique identifies the subset of program statements that are relevant to a specific program point (e.g., an assertion failure). It helps reduce the code that needs to be examined by eliminating irrelevant parts.
While SFL and DS are often considered complementary, their combined effectiveness hasn't been thoroughly studied, especially with real-world applications. Previous studies have been limited by small datasets or overly optimistic evaluation methods. This paper aims to demystify the combination of DS and SFL by conducting a comprehensive empirical study on a widely-used benchmark.
Methods
The core of this paper is the Tandem-FL approach, which combines Dynamic Slicing (DS) and Spectrum-Based Fault Localization (SFL). Here's how it works:
- Initial SFL Ranking: First, a standard SFL technique is applied to the entire test suite to generate an initial ranking of suspicious program components (e.g., statements or files).
- Dynamic Slicing of Suspicious Components: For the top-ranked components (controlled by a parameter
k), the system performs dynamic slicing. Specifically, it uses Critical Slicing, a language-agnostic technique that simplifies a program by deleting statements while preserving critical observations (like assertion failures). The goal is to create a smaller, "sliced" version of the code that still exhibits the same failure. - Spectra Update and Re-ranking: The original SFL spectrum (coverage information) is updated based on the slices. Statements that are not part of the slice are effectively removed from consideration for the failing tests. This process is repeated for each failing test.
- Improved Ranking: By removing irrelevant statements from the spectrum, the suspiciousness scores of components are adjusted. This often leads to the actual faulty component rising higher in the ranking, making it easier for developers to find.
The paper uses Critical Slicing as its DS method, implemented using the Mozilla Lithium tool. For SFL, they use standard techniques and focus on the Ochiai coefficient for ranking.
Datasets
The study evaluates its approach on subject programs from the Defects4J benchmark. This benchmark is a popular resource for evaluating fault localization techniques, containing real-world bugs from open-source Java projects. The paper lists five projects from Defects4J:
- Apache commons-lang
- Apache commons-math
- JFreechart
- Joda-Time
- Mockito
The authors note that two faults from Apache commons-math were excluded due to reproducibility issues.
Key Insights and Ideas
- DS isn't as risky as feared: A major concern with DS is the potential to "miss" the actual faulty statement if it's deemed irrelevant by the slicing criterion. The study found this happens infrequently (in only 9% of cases), suggesting the risk is manageable.
- Slicing "cleans up" the SFL signal: SFL can be noisy, highlighting many components that aren't the root cause. DS acts as a filter, removing irrelevant code from the analysis, which sharpens the focus on the true culprit.
- The combination is more than the sum of its parts: Tandem-FL consistently outperforms SFL alone, demonstrating that the synergy between reducing the code space (DS) and ranking suspiciousness (SFL) is powerful.
- Focusing on top-ranked files is effective: The parameter
k(number of top-ranked files to analyze) shows that even analyzing a small subset of the most suspicious files (k=5 or k=10) yields significant improvements.
Key Results
- Improved Diagnostic Accuracy: Tandem-FL improves fault localization accuracy by up to 73.7%, with an average improvement of 13.4% across the evaluated faults.
- Low Miss Rate: Dynamic slicing misses faulty statements in only 9% of the 260 analyzed faults.
- Significant Ranking Improvement: For cases where Tandem-FL outperforms SFL, the average improvement in the ranking position of faulty statements is substantial. For
k=5, the mean improvement is 41.1 statements, and fork=10, it's 19 statements. - Practicality: The Tandem-FL tool works "out-of-the-box" with no special requirements, making it readily usable.
Limitations and Future Work
- Threats to Validity:
- External Validity: The study used a specific set of Java projects from Defects4J. While representative, results might differ for other languages or project types. The Closure compiler project was excluded due to high computational cost.
- Construct Validity: The choice of oracle for the Lithium slicer was empirically determined. While effective, more sophisticated oracles could be explored.
- Future Work:
- Improved Oracles: Developing heuristics to handle a wider range of exceptions for slicing.
- Broader Evaluation: Testing Tandem-FL on more Defects4J faults and other datasets.
- Faults of Omission: Further research is needed to address "faults of omission" (where the fix involves adding code rather than changing existing code), as these pose a particular challenge for current techniques.
Summary updated