Diagnosing Software Faults Using Multiverse Analysis

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

TL;DR

This paper introduces "Multiverse Analysis," a novel approach to Spectrum-Based Fault Localization (SFL) that directly optimizes for reduced wasted effort in identifying bugs. By considering hypothetical scenarios where each component is faulty, their method generates test suites that significantly improve fault localization efficiency and reduce developer effort compared to existing state-of-the-art techniques like DDU.

What Problem Does This Paper Address?

Spectrum-Based Fault Localization (SFL) is a crucial technique for pinpointing software bugs by analyzing execution traces of test cases. The effectiveness of SFL heavily relies on the quality of the "spectra" – the collected execution patterns and outcomes of tests. While previous methods have focused on improving structural properties of these spectra (like density or uniqueness) to indirectly enhance diagnosability, this paper argues that these proxies don't always translate to better real-world fault localization. The core problem is that existing test generation techniques, even those optimizing for diagnosability metrics, might not effectively reduce the actual effort a developer expends when searching for a bug. This paper aims to bridge this gap by directly optimizing for reduced wasted effort.

Methods

The paper introduces Multiverse Analysis as a new metric for evaluating test-suite quality for SFL. The core idea is to consider a "multiverse" of hypothetical scenarios, where in each scenario, a single component of the program is assumed to be the faulty one. For each hypothetical universe (where component $c_i$ is assumed faulty), the authors calculate the "worst-case wasted effort" ($W_i$). This wasted effort is defined by the size of the "highest ambiguity set" ($L_i$), which includes all components that share the same execution pattern as the assumed faulty component $c_i$. If $c_i$ is faulty, a developer might have to examine all components in $L_i$ before finding $c_i$.

The Ulysis score ($W_{ulysis}$) for a test suite is then defined as the average of these worst-case wasted efforts across all hypothetical universes, assuming each component is equally likely to be faulty. This metric is implemented as a fitness function within the EvoSUITE test generation framework. The goal is to generate test suites that minimize this Ulysis score, thereby directly optimizing for reduced wasted effort in fault localization.

Datasets

The experiments were conducted using the DEFECTS4J benchmark (version 1.4.0). This benchmark contains 395 real-life software faults from six diverse Java project repositories. The authors note that while their study focused on these specific projects, the results should generalize due to the nature of the benchmark.

Key Insights and Ideas

  • Directly Optimizing for Wasted Effort: The most significant insight is the shift from optimizing structural properties of spectra (like density or uniqueness) to directly minimizing the expected worst-case wasted effort. This "multiverse" perspective allows for a more direct and potentially more effective approach to improving fault localization.
  • Ulysis vs. DDU: A Clearer Distinction: The paper demonstrates that existing metrics like DDU can sometimes fail to distinguish between test suites that offer vastly different fault localization performance in worst-case scenarios. Ulysis, by contrast, provides a clearer separation, favoring test suites that offer more consistent and efficient fault localization across all potential fault locations.
  • Implicit Coverage Improvement: While not the primary focus, optimizing for Ulysis appears to implicitly encourage better test coverage. This is because if a faulty component is never executed, the wasted effort to identify it becomes maximal (1), incentivizing test generation to ensure all components are exercised.
  • Interpretability of Ulysis: The Ulysis score offers a degree of interpretability. It can be seen as an estimate of a test suite's fault localization performance before it's even executed, based on its ability to differentiate potential faulty components.

Key Results

  • Reduced Developer Effort: Ulysis reduces developer effort by over 16% compared to DDU for more than 92% of the instances.
  • Statistical Significance: The improvements in fault localization effort achieved by Ulysis over both DDU and coverage are statistically significant, as confirmed by paired Wilcoxon Signed-rank tests.
  • Comparable or Better Test-Suite Quality: Ulysis-generated test suites are comparable to or better than those generated by DDU and coverage in terms of uniqueness, coverage, and size. Specifically, Ulysis beats DDU on uniqueness, coverage, and test-suite size.
  • Outperforming State-of-the-Art: Ulysis outperforms DDU (the current state-of-the-art metric) on all relevant metrics: diagnosability, coverage, and test-suite size.

Limitations and Future Work

  • Single Fault Assumption: The Ulysis metric, like many SFL approaches, assumes a single fault in the program. While the authors note that this is a common and often fair assumption, it might not hold for all real-world scenarios.
  • Perfect Detection Assumption: The model assumes perfect detection, meaning test outcomes are deterministic and not "flaky." Flaky tests can introduce noise and complicate fault localization.
  • Limited Scope of Study: The experiments were conducted on faults from only six Java open-source projects. While the DEFECTS4J benchmark is diverse, generalizing these results to all Java projects or other programming languages would require further investigation.
  • Single Test Generation Tool: The study used EvoSUITE for test generation. Future work could explore how Ulysis performs with other test generation tools.
  • Future Work: The authors suggest exploring how to incorporate knowledge of past failures or repository commit history to inform the prior probabilities of components being faulty, which could further refine the Ulysis metric. They also mention that other approaches orthogonal to test-suite generation, but using SFL, could benefit from their work.

Summary updated

BibTeX
@inproceedings{chatterjee2020diagnosing,
  author = {Prantik Chatterjee and Abhijit Chatterjee and José Campos and Rui Abreu and Subhajit Roy},
  title = {{Diagnosing Software Faults Using Multiverse Analysis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/226},
}
Figure