SOBER: statistical model-based bug localization

Chao Liu, Xifeng Yan, Long Fei, Jiawei Han, Samuel P. MidkiffESEC/SIGSOFT FSE 2005 · DOI

TL;DR

This paper introduces SOBER, a novel statistical approach for automatically pinpointing software bugs. Unlike prior methods that focus on simple correlations, SOBER models the patterns of how program conditions are evaluated across correct and incorrect runs, identifying bugs by detecting significant deviations in these patterns. This leads to substantially improved bug localization accuracy, enabling programmers to find bugs by examining significantly less code.

What Problem Does This Paper Address?

Debugging is a time-consuming and critical part of software development. While automated tools exist to help developers find bugs, pinpointing the exact location of a defect within a large codebase remains a significant challenge. Existing statistical debugging techniques often rely on simple correlations between a program's behavior (e.g., a condition being true) and whether a failure occurs. However, these methods can miss subtle bugs where a condition might be evaluated in both correct and incorrect runs, but its pattern of evaluation (how often it's true within a single run) differs significantly. This paper aims to address this limitation by developing a more sophisticated statistical model that captures these nuanced evaluation patterns.

Methods

The core of SOBER is its probabilistic treatment of program predicates (e.g., if (x < 10)). Instead of just noting if a predicate is true or false, SOBER calculates an "evaluation bias" for each predicate within a given program execution. This bias is essentially the probability of the predicate evaluating to true during that run.

SOBER then models these evaluation biases separately for correct (passing) and incorrect (failing) program executions. It assumes that if a predicate is relevant to a bug, its evaluation bias will behave differently in failing runs compared to passing runs. The key innovation is how SOBER quantifies this difference: it uses a hypothesis testing-like approach. It calculates how likely it is that the observed evaluation biases from failing runs could have been generated by the model learned from correct runs. A low likelihood suggests a significant difference, indicating the predicate is bug-relevant. This likelihood is then used to derive a ranking score, with higher scores indicating higher bug relevance.

Datasets

The primary dataset used for evaluation is the Siemens suite, a well-established benchmark for bug localization research. This suite contains seven programs with a total of 130 manually injected bugs across various faulty versions. The authors also conducted a case study on a real-world program, bc 1.06, a Unix calculator utility, using 4,000 generated input cases.

Key Insights and Ideas

  • Beyond Simple Correlation: The paper highlights that focusing solely on whether a predicate is true or false in failing runs is insufficient. The frequency and pattern of a predicate's evaluation within a run are crucial clues.
  • Evaluation Bias as a Feature: The concept of "evaluation bias" provides a rich feature for statistical analysis, capturing more information than binary true/false outcomes.
  • Probabilistic Modeling for Robustness: Modeling the distribution of evaluation biases for correct and incorrect runs allows SOBER to be more robust to variations in test cases and program behavior.
  • Hypothesis Testing for Ranking: Using a hypothesis testing framework to quantify the difference between correct and incorrect evaluation patterns provides a principled way to rank predicates, avoiding ad-hoc parameter tuning.
  • Generalizing Invariants: SOBER's framework naturally encompasses the detection of invariant violations (where a predicate that should always be true is false) and conformations (where a predicate that should always be false is true), assigning them extreme scores.

Key Results

  • Superior Localization Accuracy: On the Siemens suite, SOBER located 68 out of 130 bugs when programmers were expected to examine no more than 10% of the code. This significantly outperforms the previous best result of 52 bugs reported by Liblit et al. [15].
  • Reduced Code Examination: SOBER consistently requires examining less code to locate bugs compared to Liblit05 and CT (Cause Transition). For instance, at 1% code examination, SOBER finds 8.46% of bugs, compared to 7.69% for Liblit05 and 4.65% for CT.
  • Case Study Success: SOBER successfully identified two buffer overflow bugs in the real-world bc 1.06 program. One of these bugs was previously unreported.
  • Optimal k Value: The study found that setting k=5 (considering the top 5 most suspicious predicates) generally yielded the best performance for SOBER.
  • Efficiency: SOBER has a comparable time complexity to Liblit05 and is significantly faster than CT, making it practical for use.

Limitations and Future Work

  • Benchmark Size: The authors acknowledge that the Siemens suite primarily consists of small-scale programs, and the absolute performance figures might not directly generalize to arbitrarily large software systems. However, they argue that the relative performance comparisons are still credible.
  • Test Case Sufficiency: The paper notes that the localization quality might vary with the number of available test cases. Future work could investigate how SOBER performs with insufficient test data.
  • Evaluation Sampling Robustness: The robustness of SOBER to variations in how evaluation biases are sampled is another area for future study.
  • User Study for Comprehensibility: While SOBER provides a ranked list, the paper suggests that future work could explore how easily programmers can understand and utilize these reports, potentially by comparing them with methods like CT that offer more structured output.

Summary updated

BibTeX
@inproceedings{liu2005sober,
  author = {Chao Liu and Xifeng Yan and Long Fei and Jiawei Han and Samuel P. Midkiff},
  title = {{SOBER: statistical model-based bug localization}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2005},
  doi = {10.1145/1081706.1081753},
}
Figure