TL;DR
This paper introduces a formal definition of causality for violations of general Linear Temporal Logic (LTL) properties, extending previous work on safety properties. It tackles the challenge of identifying "actual causes" within infinite, "lasso-shaped" execution traces that characterize LTL property violations, going beyond simple finite counterexamples.
What Problem Does This Paper Address?
In safety-critical systems, software failures can have severe consequences. Model checking is a crucial technique for verifying system correctness against temporal properties. When a property is violated, model checkers provide counterexamples – execution traces that demonstrate the violation. However, these counterexamples can be long, noisy, and numerous. For simple safety properties, counterexamples are finite traces. But for more general LTL properties, counterexamples are infinite "lasso-shaped" traces (an initial path followed by a repeating loop). Identifying the actual causes of these violations, i.e., the indispensable sequences of events leading to the failure, is challenging. This paper addresses this by extending causality definitions to handle these complex, infinite counterexamples for general LTL properties.
Methods
The core of the paper is the extension of Event Order Logic (EOL) to handle infinite, lasso-shaped counterexamples. EOL is a logic designed to express causality classes, which are generalized counterexamples representing a set of similar counterexamples.
Key methodological contributions include:
- Infinite EOL Formulae: The authors introduce "infinite EOL formulae" of the form $\theta \wedge^\omega \psi$, where $\theta$ is a G-complex EOL formula and $\psi$ is an I-complex EOL formula. This allows expressing causal relationships within infinite execution traces, specifically addressing the looping behavior.
- Causality Definition for LTL: A new definition of causality for general LTL properties is proposed, based on four conditions (AC1-AC3) adapted from existing work on structural equation models. These conditions ensure that a proposed cause:
- Occurs with the property violation (AC1).
- Is necessary for the violation (AC2(1)).
- Is sufficient to guarantee the violation (AC2(2)).
- Is minimal, meaning no subset of the cause is sufficient (AC3).
- Order Condition (OC): An additional condition is introduced to check if the order of events within a cause is itself causal.
- Generalization Procedure: A method is described to generalize EOL formulae derived from specific counterexamples to encompass a broader set of causal scenarios, ensuring the resulting cause is in its "most general form."
Datasets
Not discussed in the paper. The paper focuses on a formal framework and theoretical definitions, using an elevator system as a running example for illustration.
Key Insights and Ideas
- Lasso-shaped counterexamples are the norm for general LTL: Unlike safety properties with finite counterexamples, liveness and other general LTL properties often manifest violations through infinite, repeating execution patterns. This necessitates a richer formalism than previously used.
- Causality needs to account for infinite behavior: Simply analyzing finite prefixes of counterexamples is insufficient. The looping part of a lasso-shaped trace can be crucial for understanding the cause of a violation.
- EOL is extended to capture infinite causal relationships: The introduction of infinite EOL formulae provides a way to formally express and reason about causes that involve repeating sequences of events.
- Minimality and sufficiency are key to "actual" causes: The AC1-AC3 conditions, particularly AC2(2) (sufficiency) and AC3 (minimality), are critical for distinguishing true causes from mere correlated events.
- Order matters: The Order Condition (OC) highlights that not only the presence but also the sequence of events can be causal for a property violation.
Key Results
The paper formally defines causality for general LTL-definable properties by extending the Event Order Logic (EOL) to handle infinite, lasso-shaped counterexamples. It presents a set of causality conditions (AC1-AC3) and an Order Condition (OC) that an EOL formula must satisfy to be considered a cause for a property violation. The authors also establish theoretical results on the completeness and soundness of their causality checking approach. Specifically, they prove that for any trace violating an LTL property, there exists a causality class (defined by a causal EOL formula) that contains it (completeness), and that any trace within a causality class is indeed a violating trace (soundness).
Limitations and Future Work
- LTL-definable properties: The current framework is limited to LTL-definable properties. The authors express interest in extending this to more general $\omega$-regular linear-time properties and Büchi automata.
- Implementation and Scalability: A significant future direction is the implementation of this causality checking approach in tools like QuantUM. A key challenge identified is efficiently determining all lasso-shaped counterexamples, potentially through on-the-fly methods.
- Case Studies: The authors plan to conduct significant case studies to assess the scalability of their approach.
- Contingency: The current definition of causality does not explicitly employ a notion of "contingency" (as found in some structural equation models), as their approach relies on complete trace exploration. This might be an area for future exploration.
Summary updated