Verification of Diagnosability for Cyber-Physical Systems: A Hybrid Barrier Certificate Approach

Xiang Yin (殷翔), Bingzhuo Zhong, Weijie Dong, Xiang Yin, Majid ZamaniarXiv 2024 · DOI · arXiv

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:

  1. The $(\delta, K)$-DFA: A specialized Deterministic Finite Automaton (DFA) acts as a monitor, tracking fault occurrences and counting elapsed time steps.
  2. 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?
  3. 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.
The $(\delta, K)$-DFA structure used to monitor the system and count time steps $K$ until a fault is formally detected.

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.

A discrete-state running example illustrating the transitions between healthy and faulty states used to validate the DFA construction.

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

Abstract

Diagnosability is a system theoretical property characterizing whether fault occurrences in a system can always be detected within a finite time. In this paper, we investigate the verification of diagnosability for cyber-physical systems with continuous state sets. We develop an abstraction-free and automata-based framework to verify (the lack of) diagnosability, leveraging a notion of hybrid barrier certificates. To this end, we first construct a (delta,K)-deterministic finite automaton that captures the occurrence of faults targeted for diagnosis. Then, the verification of diagnosability property is converted into a safety verification problem over a product system between the automaton and the augmented version of the dynamical system. We demonstrate that this verification problem can be addressed by computing hybrid barrier certificates for the product system. To this end, we introduce two systematic methods, leveraging sum-of-squares programming and counter-example guided inductive synthesis to search for such certificates. Additionally, if the system is found to be diagnosable, we propose methodologies to construct a diagnoser to identify fault occurrences online. Finally, we showcase the effectiveness of our methods through a case study.
BibTeX
@misc{2024verification,
  author = {Xiang Yin (殷翔) and Bingzhuo Zhong and Weijie Dong and Xiang Yin and Majid Zamani},
  title = {{Verification of Diagnosability for Cyber-Physical Systems: A Hybrid Barrier Certificate Approach}},
  year = {2024},
  eprint = {2408.06982},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.06982},
}
Figure