TL;DR
This paper introduces TD-SB-TemPsy, a novel approach for automatically diagnosing violations of signal-based temporal properties in Cyber-Physical Systems (CPS). It addresses the challenge of understanding why a system fails by pinpointing the root cause of property violations, making debugging more efficient for engineers.
What Problem Does This Paper Address?
Developing complex Cyber-Physical Systems (CPS) requires rigorous verification to ensure they meet their requirements. A common technique is trace checking, where system execution logs (traces) are analyzed against formal properties. While trace-checking tools can tell us if a property is violated, they often provide only a binary "yes/no" answer. When a violation occurs, engineers must manually inspect lengthy traces to understand the cause, a process that is time-consuming and prone to errors. Existing diagnostic approaches either offer low-level explanations or struggle with the complex, signal-based temporal properties common in CPS, which are often expressed using specialized domain-specific languages like SB-TemPsy-DSL. This paper aims to bridge this gap by providing a system that automatically diagnoses the root cause of violations for these complex properties.
Methods
The core of TD-SB-TemPsy lies in its approach to identifying "violation causes" and "diagnoses." A violation cause is a specific system behavior that can lead to a property violation. A diagnosis provides additional, actionable information to help engineers understand that violation cause.
The authors propose a language-agnostic methodology for defining these causes and diagnoses. This methodology involves:
- Behavior Analysis: Identifying relevant system behaviors that violate a specific temporal property construct.
- Definition of Violation Causes: Formalizing these behaviors into logical formulas that, if true, imply the property is violated.
- Definition of Diagnoses: Creating concise, informative explanations associated with each violation cause, often by identifying specific data points or intervals in the trace.
TD-SB-TemPsy is implemented as a plugin for the SB-TemPsy-Check tool. It works by:
- Decomposing a violated property into its constituent atoms.
- For each violated atom, identifying potential violation causes.
- Checking which of these causes actually hold on the given trace.
- If a cause holds, generating the corresponding diagnosis.
Datasets
The authors evaluated TD-SB-TemPsy on two main datasets:
- PROP-SAT Dataset: This dataset consists of 361 traces from a satellite domain, provided by an industrial partner. It includes 98 properties expressed in SB-TemPsy-DSL, derived from real-world requirements. This dataset represents a complex, industrial case study.
- AFC Dataset: This dataset is derived from the Fuel Control of an Automotive Powertrain benchmark model, used in the ARCH competition. It includes 10 trace-property combinations for a property expressed in SB-TemPsy-DSL, generated to falsify the property.
Additionally, two derived datasets, MD1 and MD2, were created from the PROP-SAT data to specifically test different aspects of the methodology (e.g., by modifying property scopes or focusing on specific pattern types).
Key Insights and Ideas
- Bridging the Gap Between Verification and Debugging: The paper highlights that simply knowing a property is violated isn't enough; engineers need to know why. TD-SB-TemPsy directly addresses this by providing actionable diagnostic information.
- Language-Agnostic Methodology: The core methodology for defining violation causes and diagnoses is designed to be independent of the specific property specification language, making it potentially adaptable to other DSLs.
- Catalog of Violation Causes and Diagnoses: The creation of a comprehensive catalog (34 violation causes) tailored to SB-TemPsy-DSL, validated with industrial engineers, is a significant contribution. This catalog provides a structured way to understand common failure modes.
- Formal Guarantees of Soundness: The methodology includes formal checks to ensure that a detected violation cause indeed implies a property violation, increasing confidence in the diagnostic results.
Key Results
- High Applicability: TD-SB-TemPsy demonstrated high applicability across datasets. In the PROP-SAT dataset, it finished within a 1-minute timeout for approximately 83.66% of trace-property combinations.
- Near-Perfect Diagnosis Rate: For the combinations that completed within the timeout, TD-SB-TemPsy yielded a diagnosis in approximately 99.84% of cases for the PROP-SAT dataset and 100% for the AFC dataset.
- Efficiency: The tool processed all 10 trace-property combinations in the AFC dataset well below the 1-minute timeout.
- Coverage: While not exhaustive, the catalog of violation causes covered a significant portion of observed violations in the tested datasets.
Limitations and Future Work
- Timeout Issues: For a subset of trace-property combinations (around 16.34% in PROP-SAT), TD-SB-TemPsy exceeded the 1-minute timeout. The authors suggest that longer timeouts in practical scenarios would improve applicability.
- Dataset Limitations: The authors acknowledge that the PROP-SAT dataset might not be fully representative of all CPS domains, and that the AFC dataset, while useful, is simpler. They also note that their catalog of violation causes is not exhaustive.
- Future Work: The authors plan to:
- Conduct a large-scale evaluation to assess scalability with respect to trace size and coverage of more violation causes.
- Apply the tool to a wider range of CPS case studies.
- Improve the integration between TD-SB-TemPsy and SB-TemPsy-Check for tighter coupling.
- Conduct a user study to assess the usefulness of the diagnoses for fault localization.
- Extend the catalog of violation causes and diagnoses based on specific domain needs.
Summary updated