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).
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.
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