Analysis and Control for Resilience of Discrete Event Systems

Topics

Topic 1: Cybersecurity and Information Confidentiality

• Modeling, Analysis, and Synthesis of Attacks on Communication Protocols using Supervisory Control Theory: Two Case Studies

  Abstract: We consider the vulnerability of communication protocols in distributed systems to malicious attacks that attempt to violate safety or liveness properties. We focus on person-in-the-middle attacks and analyze two case studies: the Alternating Bit Protocol and the Transmission Control Protocol. We use supervisory control theory to develop a principled way to study how to synthesize special classes of attacks on these protocols, when the attacker has partial observability and controllability of the system events. We compare our approach to related work in the computer science literature. Finally, we discuss how understanding of the attack space can provide potential mechanisms for resilience. Joint work with Shoma Matsui (Queen's University, Canada).​

• Privacy-Preserving Supervisory Control of Discrete-Event Systems for Opacity Enforcement and Requirement Satisfaction

  Abstract: In the discrete event system community, supervisory control for requirement satisfaction and privacy preservation in terms of opacity enforcement have been extensively studied. However, there is no existing work that combines both research efforts together to ensure requirement satisfaction, while preserving privacy during supervisory control, even though the demand for such technologies has been growing quickly in industry. In this talk we will address this challenge and present a method of co-synthesis of an edit function to enforce opacity against an external intruder, and a supervisor that, although in uenced by the edit function, ensures satisfaction of safety and liveness requirements. We assume that the intruder has perfect knowledge of the plant model, but is unaware of the control law, i.e., the supervisor model, and the existence of an edit function. In addition, to ensure generality of our problem setting, we assume that: 1) the observation capability of the edit function may be different from those of the supervisor and the intruder; 2) the edit function can implement insertion, deletion, and replacement operations; 3) the edit function performs bounded edit operations, i.e., the length of each string output of the edit function is upper bounded by a given value, known only to the system designer; (4) the intruder could observe not only some sensor events but also some control commands. By transforming this co-synthesis problem into a special distributed supervisor synthesis problem with different control goals for the edit function and the supervisor, respectively, we present two different sequential synthesis strategies that require novel information encoding to correctly reflect information availability to different entities at each closed-loop system state. Examples about the enforcement of the location privacy for an autonomous vehicle are used to illustrate the effectiveness of our co-synthesis strategies.

• Verification and Control of Opacity for Large-Scale Cyber-Physical Systems

  Abstract: Opacity is an important information-flow security property in the analysis of cyber physical systems. It captures the plausible deniability of the system's secret behavior in the presence of an intruder that may access the information flow. Existing works on opacity main focus on symbolic systems with finite state spaces. However, real-world cyber-physical systems are in general hybrid with both discrete logic and continuous dynamic. In this talk, we introduce the new concept of approximate opacity for dynamic systems whose output sets are equipped with metrics. Such systems are widely used in the modeling of many real-world systems whose measurements are physical signals. Approximate opacity quantitatively evaluates the security guarantee level with respect to the measurement precision of the intruder. We discuss how to verify and enforce approximate opacity for large-scale, or even infinite systems, using their finite abstractions. We also discuss how to construct approximate opacity preserving symbolic models for a class of discrete-time control systems.

Topic 2: State Estimation and Fault Diagnosis under Attacks

• State Estimation of Partially Observed Discrete Event System under Attack

  Abstract: Partially observed discrete event systems are a general formalism dating back to the definition of nondeterministic automata. The assumption is that the sequence of events generated by a plant is observed through a mask, so that an agent observing the plant may have incomplete information concerning its evolution and, correspondingly, the past and current state. The objective of this talk is to describe the basic principles of partially observable discrete event systems showing how the state estimation problem can be addressed for systems subject to cyberattacks. An operator receives the sensor readings produced by a plant though a communication channel and uses this information to estimate the current state of the plant. 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, namely the operator should not realize that its observation has been corrupted. I will show how to determine an automaton, called attack structure, that describes for each possible observation produced by the plant and for each possible attack, what is the state estimation computed by the operator. Such a structure is obtained by the concurrent composition of two state observers, the attacker observer and the operator observer. The attack structure can be used to determine if there exists a stealthy harmful attack function such that the set of states consistent with the uncorrupted observation computed by the attacker, and the set of states consistent with the corrupted observation computed by the observer, satisfy a given relation.

• Tamper-Tolerant State Estimation and Fault Diagnosis in Discrete Event Systems

  Abstract: This talk discusses tamper-tolerant state estimation and fault diagnosis in discrete event systems. We review basic notions of state estimation and fault diagnosis, primarily focusing on systems that are described by nondeterministic finite automata under partial observation through a natural projection mapping. We then consider a malicious attacker that has (i) knowledge of the underlying system model, (ii) partial access to observations about system activity, and (iii) ability to tamper with the observations that are generated by system sensors, in order to influence the outcome of various state estimation and fault diagnosis tasks. In particular, we consider tampering that include arbitrary deletions, insertions, or substitutions of observed symbols, each of which is assumed to be associated with a bounded (positive) cost. Under a total cost constraint on the sum of the costs of individual tamperings attempted by the malicious attacker, we discuss ecient approaches to describe matching (possible) sequences of observations, as well as their corresponding state estimates and associated total costs. We also develop techniques for verifying tamper-tolerant diagnosability under constraint on the total number of deletions, insertions, and substitutions (or the total cost). Several examples are presented to demonstrate the proposed concepts and methods.

• Fault Diagnosis of Discrete-event Cyber-Physical Systems in the Presence of Denial-of-Service and Deception Attacks

  Abstract: Robust fault diagnosis of discrete-event systems (DES) has been of great interest in the recent years due to its suitability for modeling cyber-physical systems with event driven dynamics. In this regard, several notions of fault diagnosis have been proposed, for example, robust diagnosis in the presence of intermittent or permanent loss of observation, robust diagnosis of multiple channel networked systems subject to communication delays, and robust diagnosis of DES modeled by a class of automata. In this talk, we revisit these notions in the light of system cyber-attacks on the system carried out by malicious agents that cause a temporary or indefinitely long disruption in the communication network after gaining access to some node in the network and inserting valid packets with false information into vulnerable channels. Two types of attacks are considered, denial-of-service (DoS) and deception (D), which flood some communication channels with fake packets that may cause delays, loss of observations and can also insert fake observations, and their implications in decentralized fault diagnosis of networked DES.

Workshop Goals

1. Report and showcase several recent technical progresses related to resiience of discrete event systems.


2. Identify challenges ahead which, although hindering the current research efforts, are critical for developing resilient discrete event systems, in order to arouse more interests and efforts at a broader societal level to ensure R&D sustainability.