(De-)Composing Causality in Labeled Transition Systems

Georgiana Caltais, Stefan Leue, Mohammad Reza Mousavi

TL;DR

This paper provides a formal bridge between causal reasoning and concurrent systems by showing how to "decompose" the search for a cause. The authors prove that for non-communicating interleaved systems, identifying the actual cause of a safety violation can be simplified into finding causes within individual components, effectively bypassing the "state space explosion" problem.

What Problem Does This Paper Address?

In safety-critical engineering, simply knowing that a system failed isn't enough; engineers need to know why. This is the domain of "causality checking." However, modern software and hardware are rarely monolithic; they are composed of many smaller, interacting components.

The standard approach to finding a cause involves analyzing the entire system's execution trace. As systems grow more complex, the number of possible execution paths grows exponentially (the state space explosion). This makes finding a "minimal" cause—the specific sequence of events that truly triggered the failure—computationally grueling. The authors address the challenge of whether we can find these causes by looking at individual components in isolation rather than the massive, combined system.

Methods

The authors build their framework using two standard tools in formal methods:

  1. Labeled Transition Systems (LTS): Used to model the step-by-step behavior of a system.
  2. Hennessy Milner Logic (HML): A branch of modal logic used to specify properties (like "the hazard never occurs").

They adapt the famous Halpern and Pearl definition of "actual causation" to this setting. To be considered a cause, a sequence of events must satisfy several conditions:

  • Positive Causality: The sequence actually leads to the hazard.
  • Counterfactual Test: If the sequence hadn't occurred, the hazard wouldn't have happened.
  • Non-occurrence: It accounts for the fact that the absence of an event can sometimes be a cause.
  • Minimality: The cause shouldn't contain any "extra" events that aren't strictly necessary to trigger the failure.

The core of the paper is the development of (de-)compositionality theorems. These mathematical proofs show how causal reasoning for complex logical properties (like "Hazard A or Hazard B") can be broken down into simpler causal reasoning tasks on the system's sub-components.

Datasets

Not discussed in the paper. As a theoretical paper in formal methods, the authors use "canonical examples"—small, hand-crafted LTS diagrams—to prove their theorems and illustrate edge cases (like why minimality is tricky) rather than empirical datasets.

Key Insights and Ideas

  • Causal Projection ($T \downarrow \phi$): The authors introduce the concept of a "causal projection," which is essentially a "trimmed down" version of the system containing only the transitions that contribute to a specific causal violation.
  • The Logic-Structure Duality: One of the most elegant insights is the mapping between logical operators and system structure.
  • Disjunction ($\vee$): Finding the cause of "Hazard A OR Hazard B" in an interleaved system is equivalent to the non-deterministic choice ($+$) between the causes found in the individual components.
  • Conjunction ($\wedge$): Finding the cause of "Hazard A AND Hazard B" is equivalent to the interleaving ($||$) of the individual causes.
  • Order Isn't Always Causal: For non-communicating systems, the specific interleaving order of events between different components often doesn't matter for the cause. This allows causal reasoning to be "pushed" down to the component level.

Key Results

The paper culminates in two main theorems for non-communicating systems:

  1. Theorem 1 (Decomposing Disjunction): $T || T' \downarrow (\phi \vee \psi) \cong T \downarrow \phi + T' \downarrow \psi$. This proves that you can find the cause of a disjunctive hazard by looking at the components separately.
  2. Theorem 2 (Decomposing Conjunction): $T || T' \downarrow (\phi \wedge \psi) = (T \downarrow \phi) || (T' \downarrow \psi)$. This shows that the cause of a conjunctive hazard is simply the interleaving of the causes of its parts.

These results are significant because they provide a mathematical guarantee that local analysis is sufficient for global causal understanding in these types of systems.

Limitations and Future Work

  • Non-communicating Systems: The current proofs only hold for systems where components do not "talk" to each other (i.e., they have disjoint action alphabets). Real-world systems often have shared actions or synchronization.
  • Safety vs. Liveness: The framework currently focuses on safety properties (bad things that shouldn't happen). It does not yet handle "liveness" properties (good things that must eventually happen).
  • Future Directions: The authors suggest extending this to communicating processes (like CCS) and incorporating recursion to handle more complex temporal properties. They also aim to integrate these results into automated tools like SpinCause to improve fault localization in industrial settings.

Summary updated

Abstract

:In this paper we introduce a notion of counterfactual causality in the Halpern and Pearl sense that is compositional with respect to the interleaving of transition systems. The formal framework for reasoning on what caused the violation of a safety property is established in the context of labeled transition systems and Hennessy Milner logic. The compositionality results are devised for non-communicating systems.
BibTeX
@inproceedings{caltais2016de,
  author = {Georgiana Caltais and Stefan Leue and Mohammad Reza Mousavi},
  title = {{(De-)Composing Causality in Labeled Transition Systems}},
  booktitle = {CREST@ETAPS},
  year = {2016},
  url = {https://openreview.net/forum?id=11KKSkG9Ch},
}

Loading related content...

Figure