Algorithms for Automatically Computing the Causal Paths of Failures

William N. Sumner, Xiangyu ZhangFASE 2009 · DOI

TL;DR

This paper introduces two novel algorithms for automatically identifying the "causal path" of a software failure, tracing it from its root cause to the point of failure. By comparing a failing execution with a "patched" execution (one that produces the correct output), their technique pinpoints the sequence of events and variable states that led to the bug, offering a more insightful explanation than traditional debugging methods.

What Problem Does This Paper Address?

Debugging complex software often involves understanding why a failure occurred, not just where. Developers typically rely on their intuition to compare a failing execution with a mental model of a "correct" execution. This paper tackles the challenge of automating this process. Existing methods often struggle with accurately aligning different program executions and can be misled by semantic differences between a failing run and a separate, but "correct," run. This can lead to identifying irrelevant "faulty" states or missing the true root cause. The authors aim to provide a more precise and automated way to compute a "causal path" – a subsequence of the failing execution that explains the failure.

Methods

The core of the paper's approach is to compare a failing execution with a patched execution. This patched execution is derived from the original failing run by applying a dynamic patch that mutates variable values or control flow to produce the correct output. Using the same input for both the failing and patched runs helps to eliminate noise from input differences.

The key technical contributions are:

  • Execution Alignment: To compare these two executions effectively, they need to be precisely aligned. The paper leverages "execution indexing" (EI), a technique that builds a hierarchical tree of an execution based on program structure. Aligning these trees allows for precise mapping of instruction instances between the two runs.
  • Failure Inducing State (FIS): At each aligned point, they identify "faulty variables" by comparing states. To pinpoint the essential ones, they compute the Failure Inducing State (FIS), which is the minimal set of faulty variables at a given step that causes the failure or the FIS of the next step. This is done by working backward from the failure point.
  • Two Algorithms for Causal Path Computation:
    1. Hierarchical Algorithm: This algorithm computes FISs in a demand-driven, top-down manner along the execution index tree. It exploits a "stability property" of FISs to avoid redundant computations.
  • Shortcutting Algorithm: This algorithm builds upon the hierarchical approach by introducing "shortcuts." It tries to identify the earliest aligned point that is likely to have the same FIS and jumps directly to it, skipping intermediate computations. This significantly speeds up the process but can sometimes degenerate into a hierarchical search if shortcuts are not valid (e.g., due to execution omissions in the failing run).

Datasets

The authors evaluated their approach on a set of real-world bugs found in GNU utilities: grep, gzip, bc, find, diff, and tar. These bugs were collected from their CVS repositories and online bug reports. The paper does not introduce a new benchmark dataset but uses these real-world examples to demonstrate the effectiveness and efficiency of their algorithms.

Key Insights and Ideas

  • Patched Execution as a Superior Oracle: Using a patched version of the same program with the same input as a reference is more effective than using a separate, correct program with potentially different inputs. This minimizes semantic differences and focuses on the causality of the failure.
  • Execution Indexing is Crucial for Alignment: Accurately aligning execution traces is a non-trivial challenge. Execution indexing provides a robust mechanism to create a hierarchical representation of executions, enabling precise alignment.
  • Causal Paths Offer Deeper Understanding: The computed causal paths provide a more informative explanation of failures than traditional fault localization techniques (which often just point to candidate statements) or dynamic slicing (which can produce overly "fat" slices). This is particularly important for requirement bugs where a single root cause might not exist.
  • Shortcutting Algorithm's Efficiency Gains: The shortcutting algorithm demonstrates a significant speedup (orders of magnitude) over the hierarchical approach, highlighting the practical benefits of optimizing the search for causal paths.

Key Results

  • The proposed technique is effective in explaining failures, producing high-quality causal paths that often capture the root cause and the failure point.
  • The shortcutting algorithm is orders of magnitude faster than the hierarchical algorithm, achieving an average of 7% of the time taken by the hierarchical approach across various bugs.
  • The study showed that about 45% of the causal paths computed by their technique capture the root cause.
  • For the evaluated bugs, the time taken by the hierarchical algorithm (Algorithm 1) ranged from 135 seconds to over 4 hours, while the shortcutting algorithm (Algorithm 2) took between 48 seconds and 250 seconds for most cases, with some exceptions where it also approached longer times due to execution omissions.

Limitations and Future Work

  • Execution Omission: The shortcutting algorithm can degenerate into a hierarchical search when the failing run omits executions that should have occurred (e.g., due to a branch not being taken). This can affect the efficiency and sometimes the completeness of the shortcut.
  • Unobserved State: Similar to execution omission, if program state is updated by the OS and not visible to the analysis, it can also impact the validity of shortcuts.
  • Future Work: The authors suggest that presenting the causal path is more informative than pointing at root cause candidates, especially for requirement bugs. Future work could explore how to best present these causal paths to developers for maximum understanding and impact. The paper also implicitly suggests further research into optimizing the shortcutting mechanism and handling cases of execution omission more gracefully.

Summary updated

BibTeX
@inproceedings{sumner2009algorithms,
  author = {William N. Sumner and Xiangyu Zhang},
  title = {{Algorithms for Automatically Computing the Causal Paths of Failures}},
  booktitle = {FASE},
  year = {2009},
  doi = {10.1007/978-3-642-00593-0\_24},
}
Figure