Critical Observability of Finite State Machines Under Attacks

In this paper, a general framework is proposed for the analysis and characterization of critical observability of finite state systems, affected by malicious attacks. Critical observability is defined with respect to a critical set, and corresponds to the property of immediately detecting the belonging of the current state to such critical set, based on the knowledge of the output evolution of the system. This concept, analyzed before for the nominal case, in which the model is known, as well as the function which associates to each state an output symbol, is here extended to the case in which there is an intrusion in the system, which could cause replacement or removal of output symbols, or injection of symbols in the output string. Therefore the problem consists in giving conditions under which critical observability is preserved, despite possible attacks. Different attacker models are considered. The case of attacks where the presence of the attacker cannot be detected is also addressed. The problem is solved in a set membership framework, which guarantees polynomial complexity of the proposed algorithms.