Abstract
This paper introduces an abstraction-free framework to verify if a Cyber-Physical System (CPS) can reliably detect faults within a fixed time window, even in the presence of measurement noise. By combining a specialized finite automaton with hybrid barrier certificates, the authors transform complex diagnosability analysis into a solvable safety verification problem. This approach avoids the computationally expensive state-space discretization typically required by traditional methods, addressing the "curse of dimensionality" in high-dimensional systems.
Introduction
In safety-critical systems such as autonomous vehicles or smart factories, detecting faults like sensor failures or mechanical breaks is a race against time. "Diagnosability" is the property ensuring a fault can be identified within a finite period. While traditionally analyzed using symbolic labels in Discrete Event Systems (DES), real-world CPS involve continuous physical signals and measurement noise. Previous attempts to bridge this gap relied on "discretizing" the continuous space, which leads to exponential complexity. This paper proposes a method to verify $\delta$-approximate $K$-diagnosability—guaranteeing that a fault is distinguishable from a healthy state by at least a margin $\delta$ within $K$ time steps—without gridding the state space.
Methods
The authors propose an "abstraction-free" pipeline consisting of three primary components:
- The $(\delta, K)$-DFA: A specialized Deterministic Finite Automaton (DFA) acts as a monitor, tracking fault occurrences and counting elapsed time steps.
- Product System Construction: A "product system" is created by combining the original physical system with itself (to compare faulty vs. non-faulty runs) and the $(\delta, K)$-DFA. This transforms the temporal property of diagnosability into a spatial reachability problem: can the system reach an "unsafe" state where a fault remains hidden?
- Hybrid Barrier Certificates (HBC): To prove the unreachability of unsafe states, the authors use Barrier Certificates. B-HBCs prove diagnosability, while V-HBCs identify non-diagnosability by finding paths to unsafe regions.
Computational engines like CEGIS (using SMT solvers) and SOS Programming (using semi-definite programming) are employed to synthesize these certificates.
Evaluation and Results
The framework was evaluated on a discrete running example and a continuous two-room temperature model. The running example demonstrates the state transitions and the logic behind the DFA-based monitoring.
In the temperature case study, the authors verified that a heater failure was 0.5-approximate 5-diagnosable (detectable within 5 steps with a 0.5-degree margin). Conversely, when the requirement was tightened to $K=3$, the system was correctly identified as non-diagnosable using the V-HBC method. The paper also provides an algorithm to implement the fault detector online using reachability analysis tools like CORA or JuliaReach.
Conclusion
By mapping temporal requirements to spatial safety constraints, this work provides a powerful tool for CPS verification. The abstraction-free nature of the approach ensures scalability for systems where grid-based methods fail. Future research will focus on extending this framework to more complex non-linear dynamics and sophisticated fault models described by temporal logics.
Summary updated