Using Model-Based Diagnosis to Improve Software Testing

Tom Zamir, Roni Tzvi Stern, Meir KalechAAAI 2014 · DOI

Abstract

Software debugging often involves a manual, trial-and-error process to isolate faults after a bug is reported. This paper proposes the Test, Diagnose, and Plan (TDP) paradigm, which integrates Model-Based Diagnosis (MBD) with AI planning to automate the search for software bugs. By modeling the testing process as a Markov Decision Process (MDP), the authors demonstrate that non-myopic planning significantly reduces the number of tests required to pinpoint faulty components compared to traditional greedy heuristics.

Introduction: Bridging the Gap Between Testing and Debugging

A persistent "wall" exists between Quality Assurance (QA) testers and software developers. When a tester identifies a bug, the resulting report often lacks the granular detail needed for immediate root-cause identification. Consequently, developers must engage in a tedious cycle of running additional tests and probes to isolate the faulty function or class.

This manual process is inefficient because testers may lack the internal code knowledge to plan optimal follow-up tests, while developers struggle to reproduce bugs found in complex environments. This research aims to automate the "what to test next" decision, transforming debugging into a systematic, AI-driven search.

The TDP Paradigm

The authors introduce the Test, Diagnose, and Plan (TDP) cycle to bridge this gap. This iterative process automates the transition from bug discovery to fault isolation:

  1. Test: A software test fails.
  2. Diagnose: A Model-Based Diagnosis (MBD) algorithm, specifically Barinel, analyzes the execution trace of the failed test. It identifies which components were involved and suggests a set of possible diagnoses (suspected faulty components).
  3. Plan: A planning algorithm determines the next test that will most effectively differentiate between the current suspects.
  4. Repeat: The tester (or an automated system) executes the suggested test. The result is fed back into the diagnosis engine, refining the list of suspects until a single culprit is identified.
Comparison between the traditional manual debugging process and the proposed AI-driven TDP process.

Planning Strategies: Greedy vs. Non-Myopic

The core innovation of this work lies in the Planning stage. The authors compare several strategies for selecting the next test:

  • Greedy Heuristics: These "myopic" methods choose tests based on immediate metrics, such as the "Best Diagnosis" (BD) or "Highest Probability" (HP) of a component being faulty.
  • Information Theory (Entropy): This approach selects tests that maximize "Information Gain," aiming to shrink the list of suspects as much as possible in the next step.
  • Markov Decision Process (MDP): Unlike greedy methods, the MDP approach looks several steps ahead. It treats the testing process as a sequence of decisions aimed at reaching a terminal state (a single diagnosis) with the minimum total number of tests. To handle the massive state space, the authors utilize Sparse Sampling (SpS) to maintain computational feasibility.

Experimental Evaluation

The TDP approach was evaluated on three distinct benchmarks:

  1. Vending Machine: A proof-of-concept program (19 components, 240 lines of code).
  2. Synthetic Programs: 100 generated programs modeled as graphs with 300 nodes, allowing for controlled testing with 10 to 20 injected bugs.
  3. NUnit Call Graph: A real-world call graph from the open-source NUnit project (302 nodes), representing complex software structure.

Key Results

The experimental results consistently highlighted the superiority of non-myopic planning. In the Vending Machine benchmark and synthetic tests, the MDP-based planner required significantly fewer tests to isolate bugs compared to all greedy heuristics.

Average number of tests required to isolate faults using Greedy vs. MDP strategies across different heuristics.

Key insights include:

  • Efficiency and Scalability: On the 300-node synthetic and NUnit benchmarks, the MDP approach outperformed Entropy and HP strategies. In the NUnit graph, the MDP approach achieved a diagnosis at a cost nearly 10x lower than entropy-based methods.
  • Robustness: The system effectively handles "flaky" tests—where code paths may intermittently pass or fail—by utilizing probabilistic diagnosis scores. Furthermore, the MDP approach proved robust regardless of the default policy used during sampling.

Conclusion and Future Work

By modeling debugging as an AI planning problem, the TDP paradigm offers a path toward more efficient software maintenance. While the MDP solver is computationally more intensive than simple heuristics, its ability to minimize the human effort required for fault isolation provides a significant net benefit. Future work will focus on reducing computational overhead and validating the system against real-world bug-tracking data from industry partners.

Summary updated

BibTeX
@inproceedings{zamir2014using,
  author = {Tom Zamir and Roni Tzvi Stern and Meir Kalech},
  title = {{Using Model-Based Diagnosis to Improve Software Testing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8873},
}
Figure