Cyber Security In Discrete Event Systems: From State Estimation To Supervisory Control

Cyber physical systems are large-scale and complex intelligent systems with abilities of computation and communication.The interaction between the cyber and physical worlds renders such systems susceptible to malicious attacks,and the problem of cyber security has attracted much attention.In the framework of supervised discrete event systems,an attacker may corrupt the sensor channels by transmitting erroneous observations to the supervisor.In particular,the attacker may erase the output symbols produced by certain events,and may insert observations corresponding to events that have not occurred(a sensor attack).In addition,the attacker can corrupt the control commands of the supervisor by enabling events that have been disabled by the supervisor(an actuator attack).Both the sensor attack and actuator attack may violate the specification enforced by the supervisor(e.g.,safety and liveness).This dissertation focuses on the problem of state estimation under attack,the problem of supervisor synthesis against sensor and actuator attacks,and the problem of stealthy sensor attacks for plants modeled by bounded labeled Petri nets.The main results are as follows:In the framework of discrete event systems,most of the existing works investigate the problem of cyber security at the supervisory control layer,the problem of state estimation under attack has not been solved.The problem setting is as follows: an operator observes a plant through a natural projection that hides the occurrence of certain events.The objective of the operator is to estimate the current state of the system.The observation may be corrupted by an attacker which can insert and erase some sensor readings with the aim of altering the state estimation of the operator.Furthermore,the attacker wants to remain stealthy,i.e.,the operator should not realize that its observation has been corrupted.An automaton,called joint estimator,is defined to describe the set of all possible attacks.In more details,first,the joint estimator is obtained by the concurrent composition of two state observers,the attacker observer and the operator observer.Then,the joint estimator is refined to obtain a supremal stealthy joint subestimator.An attack,which is defined by a sensor attack function,may be selected from the supremal stealthy joint subestimator and it is said to be harmful when some malicious goal of the attacker is reached,i.e.,if the set of states consistent with the observation produced by the system and that consistent with the corrupted observation belong to a given relation.The proposed approach can be dually used to verify if there exists a harmful attack for a given system: this allows one to establish if the system is safe under attack.In supervised discrete event systems under attack,the goal of the supervisor,who has a partial observation of the system evolution,is to prevent the system from reaching a set of unsafe states.An attacker may act in two different ways: it can corrupt the observation of the supervisor by editing the sensor readings,and it can enable events that have been disabled by the supervisor.This is done with the aim of leading the plant to an unsafe state.A special automaton,called attack structure is constructed as the concurrent composition of two special structures: an attacker observer and a supervisor under attack.Such an automaton can be used by the attacker to select proper actions(if any)to lead the plant to reach the unsafe state.From the viewpoint of defense,a robust supervisor against such attacks can be synthesized by further restricting the behavior of the supervisor under attack.We modify the structure of the classic supervisor so that it can detect the presence of an attacker,and disable all the controllable events after the detection.Finally,we present a real life example to verify the correctness of our approach.In the context of bounded labeled Petri nets,an operator observes the plant to establish if a set of critical markings has been reached.An attacker,which is defined as an augmented function,can corrupt the sensor channels that transmit the sensor readings,making the operator incapable to establish that a critical marking has been reached.A labeled Petri net called joint monitor,which takes into account the real plant evolutions observed by the attacker and the corrupted plant evolutions observed by the operator,is constructed as the concurrent composition of two labeled Petri nets called an attacker monitor and an operator monitor.The effectiveness of an augmented function can be verified by checking if the reachability graph of the joint monitor contains a target marking whose first element is a critical marking and the second element is a noncritical marking.Under the assumption that the implicit subnet of the joint monitor is acyclic,one can exploit basis reachability graph to evaluate if the augmented function is effective.Such an approach can alleviate the problem of state explosion,and significantly reduce the computational complexity.Starting from the reachability graph of the joint monitor,an extended reachability graph,which describes all possible attacks,is defined.The supremal stealthy extended reachability subgraph,which contains all the stealthy attacks,can be obtained by appropriately trimming the extended reachability graph.Finally,one can determine if there exists a stealthy and effective augmented function on the basis of such a subgraph.