Augmenting Automated Spectrum Based Fault Localization for Multiple Faults

Prantik Chatterjee, José Campos, Rui Abreu, Subhajit RoyIJCAI 2023 · DOI

TL;DR

This paper introduces ARTEMIS, a novel "multiverse analysis" approach to improve Spectrum-Based Fault Localization (SBFL) for programs with multiple simultaneous bugs. By simulating the fixing of dominant faults, ARTEMIS effectively "bubbles up" less obvious, "dormant" faults, significantly reducing the effort required for developers to find and fix them.

What Problem Does This Paper Address?

As software systems grow in complexity, debugging becomes a significant bottleneck. Spectrum-Based Fault Localization (SBFL) is a popular automated technique that uses test execution data (spectra) to identify faulty code. However, traditional SBFL methods struggle when a program has multiple bugs. This is because the failures caused by one "dominant" faulty component can overshadow the symptoms of other, "dormant" faulty components, making them difficult to detect. Developers then face a tedious process of fixing one bug at a time, re-running tests, and re-localizing, which is time-consuming and expensive.

Methods

The core innovation of this paper is the "multiverse analysis" approach. Instead of relying on a single spectrum from a single run, ARTEMIS simulates multiple "universes," each representing a scenario where a specific component is assumed to be the dominant fault and is "fixed." This simulation is done by adjusting the error vector of the spectrum.

Here's how it works:

  1. Initial Spectrum Analysis: The process begins with the standard spectrum of a failing program and a chosen SBFL metric (like Ochiai or Tarantula). This generates an initial ranked list of suspicious components.
  2. Multiverse Creation: ARTEMIS then creates multiple "universes." For the top-ranked components (controlled by a hyperparameter μ), it simulates fixing them. This simulation involves re-evaluating test outcomes: if a test executed the "fixed" component and failed, it's now assumed to pass with a certain probability (controlled by hyperparameter p) to account for other potential faults.
  3. Recursive Exploration: This process is applied recursively. For each simulated "fixed" component, new universes are spawned, assuming combinations of faults. This creates a "multiverse tree."
  4. Merging Results: Finally, all the ranked lists generated across all these simulated universes are merged. The merging strategy prioritizes components that consistently appear high in multiple universes, effectively combining evidence from different fault scenarios. This merged list is the augmented output, designed to bring dormant faults to the forefront.

The tool implementing this approach is called ARTEMIS.

Datasets

The experiments were conducted on six real-world Java project repositories from the DEFECTS4J benchmark suite (Chart, Closure, Lang, Math, Mockito, and Time). These projects are described as large, open-source, and have well-defined ground truth for bugs.

Spectra were generated using the EVOSUITE tool, employing state-of-the-art fitness functions (ULYSIS, DDU, COVERAGE) for test generation. The spectra were at the line granularity. A total of 772 spectra were used, and any spectrum without failing tests was discarded.

Key Insights and Ideas

  • Dominant Faults Obscure Dormant Ones: The paper clearly articulates that the primary challenge in multi-fault localization is how a single, highly visible fault can mask others, leading to poor performance of standard SBFL metrics.
  • Simulating Fixes is Key: The core insight is that by simulating the effect of fixing a dominant fault, we can reveal the impact of other faults. This avoids the costly real-world process of actually fixing and re-testing.
  • Multiverse as a Diagnostic Tool: The "multiverse" concept is a clever way to explore various fault hypotheses systematically. Each universe represents a different assumption about which fault is the primary culprit.
  • "Bubbling Up" Dormant Faults: The ultimate goal and achievement is to "bubble up" the ranks of components that are less suspicious in the initial analysis but are indeed faulty. This significantly reduces developer effort.
  • Generalization is Possible: The paper emphasizes that by tuning hyperparameters over multiple projects and using cross-validation, ARTEMIS can generalize well to unknown, unseen software projects.

Key Results

  • Significant Improvement in Developer Effort: ARTEMIS provides an average improvement of approximately 17% mean and 14% median in developer effort (measured by EXAM score) compared to base SBFL metrics.
  • Statistical Significance: A Wilcoxon Signed-rank test confirmed that ARTEMIS is statistically better than all tested base SBFL metrics.
  • Hyperparameter Generalization: The study found that optimal hyperparameter choices (e.g., S=Ochiai, μ=17, β=20, p=1e-5) generalize well across different projects, indicating robustness.
  • Improved Top-N Ranking: ARTEMIS shows a notable improvement in ranking faults within the top-n positions, especially for n > 1. For instance, it places 31% of faults within the top 5 ranks, compared to 26% for Ochiai. This suggests it effectively brings dormant faults into view.

Limitations and Future Work

  • Hyperparameter Tuning: While ARTEMIS generalizes well, the selection of optimal hyperparameters (μ, β, p, and the base SBFL metric S) is still a crucial step. The paper uses grid search and cross-validation for this.
  • Simulation Probability (p): The probability p of a test still failing after a simulated fix is a hyperparameter. The paper acknowledges that in real-world scenarios with multiple faults, this probability can be complex to determine precisely. They tune it as a hyperparameter to maintain generality.
  • Dataset Scope: The experiments were conducted on six specific Java projects from DEFECTS4J. While these are representative, the authors suggest that experiments on other environments and heuristics could be conducted.
  • Future Work: The authors suggest exploring other SBFL heuristics as baselines and conducting experiments on different software environments. They also mention that the multiverse analysis could potentially be applied to other areas beyond fault localization.

Summary updated

BibTeX
@inproceedings{chatterjee2023augmenting,
  author = {Prantik Chatterjee and José Campos and Rui Abreu and Subhajit Roy},
  title = {{Augmenting Automated Spectrum Based Fault Localization for Multiple Faults}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/350},
}
Figure