A Synthesis of Logical and Probabilistic Reasoning for Program Understanding and Debugging

Lisa J. Burnell, Eric Horvitz

Here is a concise, engaging summary of the paper, tailored for a technically literate audience.

TL;DR

This paper introduces a hybrid debugging framework that combines deterministic logical analysis with Bayesian belief networks to navigate the chaos of legacy software crashes. By reconstructing potential execution paths from a memory dump and ranking them by their probability of containing the root error, the system reduces manual debugging time for complex mainframe systems by an estimated 25% to 50%.

What Problem Does This Paper Address?

Imagine trying to debug a critical, massive software system written in unstructured assembly language, modified by hundreds of engineers over several decades, and lacking comprehensive documentation or test suites. This is the reality of "corporate legacy software," such as American Airlines' SABRE reservation system.

When these systems encounter an abnormal termination (a crash), the operating system outputs a cryptic "memory dumpfile" containing a snapshot of registers and memory states at the exact moment of failure. To find the root cause, engineers must trace execution backward from the crash site. However, because of loops, conditional branches, and missing runtime history, there are often hundreds of potential execution paths that could have led to the error. Sorting through these paths manually is incredibly time-consuming and mentally taxing.

Methods

The authors present DAACS-II (Dump Analysis and Consulting System), which tackles this uncertainty using a two-step pipeline:

  1. Logical Analysis (Path Reconstruction & Pruning): The system treats the program as a directed graph of basic blocks. It backtracks from the error location to reconstruct all theoretically feasible execution paths. It then uses deterministic logic to prune paths that are mathematically or structurally impossible based on the available dump data.
  2. Probabilistic Analysis (Path Prioritization): Because logic alone cannot narrow the choices down to a single path, DAACS-II applies a Bayesian belief network to the remaining candidates.
Figure 1: Overview of logical and uncertain reasoning approach. A memory dumpfile generated at the time of an error is analyzed to generate a graph of feasiable execution paths. Each path is analyzed with a belief network to generate a list of paths prioritized by the likelihood that a path harbors an error.

The belief network evaluates specific clues (evidence) extracted from the path and dump file, such as:

  • Syntactic Structure: Does the path actually contain instructions capable of modifying the corrupted variable?
  • Close Registers (CLOSE REGS): Are there register values suspiciously close to the invalid memory address, indicating a potential off-by-one or initialization error?
  • Negative Registers (NEG REGS): Are there large negative numbers that might indicate an underflow or bad loop adjustment?

The network outputs a prioritized list of paths ranked by their likelihood of harboring the bug, along with a breakdown of the most probable error classes (e.g., BAD SET, BAD LOOP, BAD ADJUST) for each path.

Figure 4: Set of belief networks used to evaluate paths. (a) The belief network for analyzing the probability that a problem lies on a path. (b) Analysis of multiple feasible paths of a program that have been identified by a deterministic analysis of alternative routes to an

Datasets

The system was developed and evaluated using real-world production memory dumps from American Airlines' SABRE reservation system, running under the IBM TPF (Transaction Processing Facility) operating system. No standard synthetic benchmarks were used, as the research specifically targeted the unique complexities of large-scale, real-world mainframe assembly code.

Key Insights and Ideas

  • The Power of "Soft" Evidence: In traditional debugging, a clue is either a smoking gun or useless. This paper shows that weak, probabilistic indicators—like how close a register value is to a memory boundary—can be aggregated via Bayesian inference to provide highly accurate guidance.
  • Complementary Synergy: Deterministic logic is excellent for absolute negation (ruling out impossible paths), while probabilistic reasoning is excellent for ranking possibilities. Combining them prevents the state-space explosion that dooms pure logic, while avoiding the accuracy dilution of pure probability.
  • Explaining the "Why": Instead of just pointing to a line of code, the system provides an "error breakdown" (e.g., a 42% chance the variable was initialized incorrectly vs. a 28% chance the loop index was adjusted incorrectly), which aligns closely with how human experts naturally conceptualize programming mistakes.

Key Results

  • Time Savings: Expert debuggers estimated that the tool reduces the time required to isolate software errors by 25% to 50%.
  • Diagnostic Boost: Preliminary metrics showed that DAACS-II successfully diagnosed 10% more memory dumps than systems relying on logical analysis alone, thanks to its ability to handle incomplete or ambiguous state data.

Limitations and Future Work

Currently, DAACS-II operates under a simplifying assumption: it treats all unpruned execution paths as having an equal prior probability of being executed. In reality, some paths (like standard execution loops) are much more common than rare error-handling branches.

The authors' primary future direction is to interleave probabilistic reasoning directly into the path-identification phase. By calculating $p(\text{path executed} \mid \text{structure of program})$, they hope to leverage historical operating system statistics to assign more realistic prior probabilities to paths. Additionally, they plan to scale the system up to analyze complex interactions between multiple distinct program segments, rather than focusing on isolated segments.

Summary updated

Abstract

We describe the integration of logical and uncertain reasoning methods to identify the likely source and location of software problems. To date, software engineers have had few tools for identifying the sources of error in complex software packages. We describe a method for diagnosing software problems through combining logical and uncertain reasoning analyses. Our preliminary results suggest that such methods can be of value in directing the attention of software engineers to paths of an algorithm that have the highest likelihood of harboring a programming error.
BibTeX
@inproceedings{burnell1993synthesis,
  author = {Lisa J. Burnell and Eric Horvitz},
  title = {{A Synthesis of Logical and Probabilistic Reasoning for Program Understanding and Debugging}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1993},
}
Figure