SMT-Based Validation of Timed Failure Propagation Graphs

Marco Bozzano, Alessandro Cimatti, Marco Gario, Andrea MicheliAAAI 2015 · DOI

Abstract

Timed Failure Propagation Graphs (TFPGs) are critical tools in aerospace and other safety-critical industries for diagnosing system faults. However, their manual construction makes them prone to human error. This paper introduces a formal framework that encodes TFPGs into Satisfiability Modulo Theories (SMT) formulas. By leveraging the Z3 solver, the authors enable automated reasoning to ensure these models are accurate, consistent, and capable of identifying faults during the design phase.

The Challenge of Fault Modeling

In complex systems like satellites or aircraft, a single component failure can trigger a chain reaction of discrepancies over time. TFPGs map these failure paths, helping engineers perform real-time diagnosis. Traditionally, these models are built manually by safety engineers based on their expertise, making them susceptible to errors that could lead to catastrophic failures if a diagnosis is incorrect. Validating these models has historically relied on non-exhaustive manual testing, which fails to guarantee correctness in all scenarios.

Formalizing TFPGs with SMT

The core innovation of this work is the translation of TFPG semantics into a logical language that an SMT solver can process. The authors map TFPG nodes (failure modes and discrepancies) and edges (causal links with time delays) into Real Difference Logic (RDL). This allows the model to account for both Boolean states (whether a fault is active) and continuous time (when it occurred).

A Timed Failure Propagation Graph (TFPG) example illustrating failure modes and propagation paths for a sensor system.

Once encoded, several complex validation tasks become simple logical queries:

  • Model Validation: Checking "Possibility" (can this sequence of events occur?) and "Necessity" (must event A precede event B?).
  • Refinement Testing: Ensuring a detailed version of a model still honors the properties of its original abstract version.
  • Diagnosability: Using a "twin-plant" construction to check if two different faults could produce identical observations, which would render the system non-diagnosable.

Performance and Scalability

The approach was evaluated using a Battery-Powered Sensor System (BPSS) and a suite of synthetic benchmarks. The prototype tool successfully handled refinement and diagnosability checks for TFPGs with up to 2,500 nodes, which exceeds the size of typical industrial models.

Scalability results for refinement and diagnosability checks, showing runtime performance across varying node counts.

As shown in the performance data, most queries were answered within a 300-second timeout. While diagnosability checks showed a steeper increase in runtime as node counts grew compared to refinement testing, the performance remains highly practical for design-time engineering workflows. This allows engineers to "debug" safety models before hardware is ever manufactured.

Conclusion

By unifying validation, refinement, and diagnosis under the umbrella of SMT, this framework provides a powerful tool for system safety. While current limitations include handling dynamic mode-switching during propagation, the ability to formally verify large-scale TFPGs marks a significant step forward in ensuring the reliability of complex diagnostic systems.

Summary updated

BibTeX
@inproceedings{bozzano2015smt,
  author = {Marco Bozzano and Alessandro Cimatti and Marco Gario and Andrea Micheli},
  title = {{SMT-Based Validation of Timed Failure Propagation Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9753},
}
Figure