A novel efficient model for testing diagnosability of discrete event systems under sensor attacks

Abstract

The cyber-attack diagnosability (CA-diagnosability) of discrete event systems (DESs) assess the ability to diagnose issues when an attacker interferes with sensor-to-diagnostic communication. This paper introduces a novel cyclic model (CM), which increases the efficiency of checking the system’s CA-diagnosability without constructing the diagnoser. We first initiate an innovative algorithm, the detection of cycles (DC), to get cyclic information for constructing the CM. Subsequently, we expand upon the concept of critical observations to diagnosability checking and propose the getting critical observations (GCO) algorithm. Finally, in the proposal of the CM-based CA-diagnos-ability checking (CMDIC) algorithm, we delineate the sufficient and necessary conditions for CA-diagnosability within the CM framework and offer an analysis of its algorithmic complexity. We demonstrates findings with an example of faults in a power system’s protection relay and circuit breaker. Experimental results on different benchmarks demonstrate that our approach significantly outperforms the state-of-the-art methods in multi-fault systems, with an average improvement of over 95%. In the best-case scenarios, the improvement can reach up to two orders of magnitude.

Graphical abstract

Keywords

discrete event systems / model-based diagnosis / cyber attacks / diagnosability

References

[1] Feldman A, Pill I, Wotawa F, Matei I, de Kleer J. Efficient model-based diagnosis of sequential circuits. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020, 2814−2821

[2] Zhou H, Ouyang D, Zhao X, Zhang L. Two compacted models for efficient model-based diagnosis. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 3885−3893

[3] Stern R, Juba B. Safe partial diagnosis from normal observations. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence. 2019, 3084−3091

[4] Rodler P. Random vs. best-first: impact of sampling strategies on decision making in model-based diagnosis. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 5869−5878

[5] Kalech M, Natan A. Model-based diagnosis of multi-agent systems: a survey. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 12334−12341

[6] Tai R, Ouyang D, Liu W, Jiang L, Zhang L . A novel approach to model-based diagnosis with multiple observations. Engineering Applications of Artificial Intelligence, 2025, 141: 109768

[7] Zhao X, Tong X, Ouyang D, Zhang L, Hou Y . TreeMerge: efficient generation of minimal hitting-sets for conflict sets in tree structure for model-based fault diagnosis. IEEE Transactions on Reliability, 2021, 70( 4): 1596–1610

[8] Shu S, Lin F . Decentralized control of networked discrete event systems with communication delays. Automatica, 2014, 50( 8): 2108–2112

[9] Nunes C E V, Moreira M V, Alves M V S, Carvalho L K, Basilio J C . Codiagnosability of networked discrete event systems subject to communication delays and intermittent loss of observation. Discrete Event Dynamic Systems, 2018, 28( 2): 215–246

[10] Gorinevsky D, Dittmar K, Mylaraswamy D, Nwadiogbu E. Model-based diagnostics for an aircraft auxiliary power unit. In: Proceedings of the International Conference on Control Applications. 2002, 215−220

[11] Sampath M, Sengupta R, Lafortune S, Sinnamohideen K, Teneketzis D . Diagnosability of discrete-event systems. IEEE Transactions on Automatic Control, 1995, 40( 9): 1555–1575

[12] Lamperti G, Trerotola S, Zanella M, Zhao X . Sequence-oriented diagnosis of discrete-event systems. Journal of Artificial Intelligence Research, 2023, 78: 69–141

[13] Boussif A, Ghazel M . Tuning the diagnoser-based approach for diagnosability analysis of finite automata. International Journal of Control, Automation and Systems, 2021, 19( 8): 2842–2858

[14] Jiang S, Huang Z, Chandra V, Kumar R . A polynomial algorithm for testing diagnosability of discrete-event systems. IEEE Transactions on Automatic Control, 2001, 46( 8): 1318–1321

[15] Yoo T S, Lafortune S . Polynomial-time verification of diagnosability of partially observed discrete-event systems. IEEE Transactions on Automatic Control, 2002, 47( 9): 1491–1495

[16] Meira-Góes R, Wintenberg A, Matsui S, Lafortune S . MDESops: an open-source software tool for discrete event systems modeled by automata. IFAC-PapersOnLine, 2023, 56( 2): 6093–6098

[17] Su X, Zanella M, Grastien A. Diagnosability of discrete-event systems with uncertain observations. In: Proceedings of the 35th International Joint Conference on Artificial Intelligence. 2016, 1265−1271

[18] Ibrahim H, Dague P, Grastien A, Ye L, Simon L. Diagnosability planning for controllable discrete event systems. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence. 2017

[19] Christopher C J, Grastien A . Critical observations in model-based diagnosis. Artificial Intelligence, 2024, 331: 104116

[20] Yin X, Chen J, Li Z, Li S . Robust fault diagnosis of stochastic discrete event systems. IEEE Transactions on Automatic Control, 2019, 64( 10): 4237–4244

[21] Grastien A, Anbulagan, Rintanen J, Kelareva E. Diagnosis of discrete-event systems using satisfiability algorithms. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 2007, 305−310

[22] He L, Ye L, Dague P . SMT-based diagnosability analysis of real-time systems. IFAC-PapersOnLine, 2018, 51( 24): 1059–1066

[23] Geng X, Ouyang D, Jiang Z . Pattern diagnosis for stochastic discrete event systems. Engineering Applications of Artificial Intelligence, 2020, 87: 103305

[24] Geng X, Ouyang D, Zhao X, Hao S . Probabilistic logical approach for testing diagnosability of stochastic discrete event systems. Engineering Applications of Artificial Intelligence, 2016, 53: 53–61

[25] Porche III I R. Cyberwarfare: An Introduction to Information-Age Conflict. Norwood: Artech House, 2020

[26] Dibaji S M, Pirani M, Flamholz D B, Annaswamy A M, Johansson K H, Chakrabortty A . A systems and control perspective of CPS security. Annual Reviews in Control, 2019, 47: 394–411

[27] Duo W, Zhou M, Abusorrah A . A survey of cyber attacks on cyber physical systems: recent advances and challenges. IEEE/CAA Journal of Automatica Sinica, 2022, 9( 5): 784–800

[28] Zheng S, Shu S, Lin F . Modeling and control of discrete-event systems under joint sensor-actuator cyberattacks. IEEE Transactions on Control of Network Systems, 2024, 11( 2): 782–794

[29] Lin F, Lafortune S, Wang C . Diagnosability and attack detection for discrete event systems under sensor attacks. Discrete Event Dynamic Systems, 2024, 34( 3): 465–495

[30] Meira-Góes R, Kang E, Kwong R H, Lafortune S . Synthesis of sensor deception attacks at the supervisory layer of Cyber–Physical Systems. Automatica, 2020, 121: 109172

[31] Hadjicostis C N, Lafortune S, Lin F, Su R. Cybersecurity and supervisory control: a tutorial on robust state estimation, attack synthesis, and resilient control. In: Proceedings of the 61st IEEE Conference on Decision and Control. 2022, 3020−3040

[32] Lin F, Lafortune S, Wang C . Diagnosability of discrete event systems under sensor attacks. IFAC-PapersOnLine, 2023, 56( 2): 3572–3578

[33] Gupta A, Suzumura T. Finding all bounded-length simple cycles in a directed graph. 2021, arXiv preprint arXiv: 2105.10094

[34] Johnson D B . Finding all the elementary circuits of a directed graph. SIAM Journal on Computing, 1975, 4( 1): 77–84

[35] Chankate M, Philippot A, Carre-Menetrier V, Marange P. Checking diagnosability on centralized model of the system. In: Proceedings of 2019 International Conference on Control, Automation and Diagnosis. 2019, 1−6

[36] Cassandras C G, Lafortune S. Introduction to Discrete Event Systems. 3rd ed. Cham: Springer, 2021

RIGHTS & PERMISSIONS

Higher Education Press