Automated Program Debugging Via Multiple Predicate Switching

Yongmei Liu, Bing LiAAAI 2010 · DOI

Abstract

This paper introduces BMPS (Bounded debugging via Multiple Predicate Switching), an algorithm that automatically locates software bugs by identifying sets of control conditions that, if flipped, would allow a failing program to pass its tests. By formalizing debugging through the lens of mathematical logic (Situation Calculus), the authors provide theoretical guarantees of "quasi-completeness" for a specific class of common programming errors.

Introduction

Program debugging is notoriously time-consuming and often relies on the intuition of developers. While automated debugging tools exist, many are heuristic-based and lack a rigorous theoretical foundation. A promising recent approach was "predicate switching"—the idea that if you change the outcome of a single if statement or while loop condition and the program suddenly works, that condition is likely near the bug. However, single-predicate switching is limited; many bugs require multiple changes to "fix" an execution path. This paper seeks to bridge that gap by generalizing the technique to multiple predicates and providing a formal logical framework.

Methodology

The authors treat C-like "while programs" as logical entities using Situation Calculus and Golog (a high-level logic programming language). The core method is the BMPS Algorithm, which searches for a Critical Predicate Set (CPS)—a group of predicates whose outcomes can be switched at runtime to produce the correct output.

Control flow representation of a simple while-program used for dependency analysis.

Since loops can run infinitely, the algorithm "unwinds" loops to a depth k, similar to bounded model checking. The program and its test cases are converted into a Boolean formula. The authors use CBMC (a bounded model checker for C) to feed this formula into a SAT solver, which efficiently finds the minimal sets of predicates that need to be flipped to satisfy the test requirements. Once a critical predicate set is found, the algorithm uses Backward Data Slices on a Data Dependency Graph (DDG) to narrow down the specific lines of code (assignments or predicates) that are likely faulty.

Evaluation and Results

The authors evaluated their approach using two primary sources: small C programming exercises (e.g., computing GCD, sorting) and the Siemens Suite (TCAS), a classic benchmark in software testing research.

Key results include:

  • Efficiency: For the small C programs, the running time was consistently less than 1 second.
  • TCAS Performance: In the TCAS benchmark, 38 out of 41 faulty versions were identified as "predicate-cut" faults. For many of these, the tool found a critical predicate set of size 1 in less than 0.01 seconds.
  • Accuracy: In a selection sort example with two distinct faults, the algorithm correctly identified the exact true diagnosis by finding a CPS of size 2.

Discussion

The paper focuses on RHS Faults (errors in control predicates or the right side of assignment statements) and Predicate-Cut Faults (where errors propagate only through control flow). A key theoretical contribution is the proof of Quasi-Completeness, meaning the algorithm is guaranteed to return a set of components that contains at least part of the true diagnosis for conditional programs. By focusing only on switching existing predicates rather than searching for arbitrary state changes, the search space is drastically reduced, making the tool much faster.

Conclusion

BMPS offers a rigorous and efficient approach to automated debugging. While currently limited to programs without complex procedure calls or recursion, the method shows great promise for RHS and predicate-cut faults. Future work will extend the BMPS algorithm to accommodate procedures and perform more extensive empirical evaluations on industrial-sized software systems.

Summary updated

BibTeX
@inproceedings{liu2010automated,
  author = {Yongmei Liu and Bing Li},
  title = {{Automated Program Debugging Via Multiple Predicate Switching}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7591},
}
Figure