Skip to Main content Skip to Navigation
Journal articles

How to be sure a faulty system does not always appear healthy?: Fault manifestability analysis for discrete event and timed systems

Philippe Dague 1, 2 Lulu He 3 Lina Ye 2, 3
2 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], Inria Saclay - Ile de France
3 VALS - LRI - Vérification d'Algorithmes, Langages et Systèmes (LRI)
LRI - Laboratoire de Recherche en Informatique
Abstract : Fault diagnosability (allowing one to determine with certainty whether a given fault has effectively occurred based on the available observations) is a crucial and challenging property in complex system automatic control, which generally requires a high number of sensors, increasing the system cost, since it is quite a strong property. In this paper, we analyze a new system property called manifestability, that is a weaker requirement on system observations for having a chance to identify on-line faults: that a faulty system cannot always appear healthy. We propose an algorithm with PSPACE complexity to automatically verify it for finite automata, and prove that the problem of manifestability verification itself is PSPACE-complete. The experimental results show the feasibility of our algorithm from a practical point of view. Then, we extend our approach to verify manifestability of real-time systems modeled by timed automata, proving that it is undecidable in general but under some restricted conditions it becomes PSPACE-complete. Finally, we encode this property into an SMT formula, whose satisfiability witnesses manifestability, before presenting experimental results showing the scalability of our approach.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-02425142
Contributor : Philippe Dague Connect in order to contact the contributor
Submitted on : Monday, June 7, 2021 - 4:24:24 PM
Last modification on : Thursday, July 8, 2021 - 3:47:05 AM
Long-term archiving on: : Wednesday, September 8, 2021 - 7:19:33 PM

File

ISSE.pdf
Files produced by the author(s)

Identifiers

Citation

Philippe Dague, Lulu He, Lina Ye. How to be sure a faulty system does not always appear healthy?: Fault manifestability analysis for discrete event and timed systems. Innovations in Systems and Software Engineering, Springer Verlag, inPress, ⟨10.1007/s11334-019-00357-z⟩. ⟨hal-02425142⟩

Share

Metrics

Record views

197

Files downloads

104