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 (LTS) and Hennessy Milner logic (HML). The compositionality results are devised for non-communicating systems, providing a bridge between causal reasoning and concurrent systems.
The Challenge of Causal Analysis in Concurrent Systems
In safety-critical engineering, identifying that a system failed is only the first step; engineers must determine why it failed. This process, known as "causality checking," becomes increasingly difficult as systems grow in complexity. Modern software and hardware are typically composed of numerous smaller, interacting components.
The standard approach to finding a cause involves analyzing the entire system's execution trace. However, as systems grow, the number of possible execution paths increases exponentially—a phenomenon known as the "state space explosion." This makes finding a "minimal" cause—the specific sequence of events strictly necessary to trigger a failure—computationally expensive. This research addresses whether we can simplify this task by analyzing individual components in isolation rather than the massive, combined system.
Formal Framework and Causal Definitions
The authors build their framework using two standard tools in formal methods: Labeled Transition Systems (LTS) to model step-by-step behavior, and Hennessy Milner Logic (HML) to specify safety properties (e.g., "the hazard never occurs").
They adapt the Halpern and Pearl definition of "actual causation" to this setting. For a sequence of events to be considered a cause, it 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: The absence of an event can sometimes be a cause.
- Minimality: The cause must not contain unnecessary events.
One of the more nuanced aspects of this framework is handling non-occurrence. In some systems, the failure to perform a specific action is what triggers the hazard.
Key Insights: The Logic-Structure Duality
A central contribution of the paper is the development of (de-)compositionality theorems. The authors demonstrate an elegant mapping between logical operators and system structure:
- Disjunction (∨): 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 individual components.
- Conjunction (∧): Finding the cause of "Hazard A AND Hazard B" is equivalent to the interleaving ($||$) of the individual causes.
For non-communicating systems, the specific interleaving order of events between different components often does not affect the causal outcome. This allows causal reasoning to be "pushed" down to the component level, effectively bypassing the state space explosion.
Results and Future Directions
The paper culminates in two main theorems for non-communicating systems:
- Theorem 1 (Decomposing Disjunction): $T || T' \downarrow (\phi \vee \psi) \cong T \downarrow \phi + T' \downarrow \psi$.
- Theorem 2 (Decomposing Conjunction): $T || T' \downarrow (\phi \wedge \psi) = (T \downarrow \phi) || (T' \downarrow \psi)$.
These results provide a mathematical guarantee that local analysis is sufficient for global causal understanding in these types of systems. While currently limited to non-communicating systems and safety properties, future work aims to extend this to communicating processes (like CCS) and liveness properties. The ultimate goal is to integrate these results into automated tools like SpinCause to improve fault localization in industrial settings.
Summary updated