We formulate notions of opacity for cyberphysical systems modeled as discrete-time linear time-invariant systems. A set of secret states is @math -ISO with respect to a set of nonsecret states if, starting from these sets at time @math , the outputs at time @math are indistinguishable to an adversarial observer. Necessary and sufficient conditions to ensure that a secret specification is @math -ISO are established in terms of sets of reachable states. We also show how to adapt techniques for computing under-approximations and over-approximations of the set of reachable states of dynamical systems in order to soundly approximate k-ISO. Further, we provide a condition for output controllability, if @math -ISO holds, and show that the converse holds under an additional assumption. We extend the theory of opacity for single-adversary systems to the case of multiple adversaries and develop several notions of decentralized opacity. We study the following scenarios: i) the presence or lack of a centralized coordinator, and ii) the presence or absence of collusion among adversaries. In the case of colluding adversaries, we derive a condition for nonopacity that depends on the structure of the directed graph representing the communication between adversaries. Finally, we relax the condition that the outputs be indistinguishable and define a notion of @math -opacity, and also provide an extension to the case of nonlinear systems.
The paper studies the control of a class of discrete event processes, i.e., processes that are discrete, asynchronous and possibly nondeterministic. The controlled process is described as the generator of a formal language, while the controller, or supervisor, is constructed from a recognizer for a specified target language that incorporates the desired closed-loop system behavior. The existence problem for a supervisor is reduced to finding the largest controllable language contained in a given legal language. Two examples are provided. The most studied property, secrecy, is not always sufficient to prove the security of a protocol. Other properties such as anonymity, privacy or opacity could be useful. Here, we give a simple definition of opacity by looking at the possible traces of the protocol. Our approach draws on a new property over messages called similarity. Then, using rewriting methods close to those used in unification, we demonstrate the decidability of our opacity property. This is only achieved in the case of atomic keys using a method called Key Quantification. A discrete event system (DES) is a dynamic system that evolves in accordance with the abrupt occurrence, at possibly unknown irregular intervals, of physical events. Such systems arise in a variety of contexts ranging from computer operating systems to the control of complex multimode processes. A control theory for the logical aspects of such DESs is surveyed. The focus is on the qualitative aspects of control, but computation and the related issue of computational complexity are also considered. Automata and formal language models for DESs are surveyed. > In this thesis we present a technique for the composition of robot control laws in dynamical environments. We propose a challenging robotic task, called Dynamical Pick and Place, in which a robot equipped with merely a soft paddle must capture and contain a ball, safely negotiate it past obstacles, and bring it to rest at a desired location. We develop a composition technique for local controllers that provides a formal guarantee of the stability of the switching behavior required in this task, and provide descriptive statistics of a working implementation. Our robotic system displays unusually dexterous behavior in the face of significant system noise, and recovers gracefully from large unexpected perturbations caused by the experimenters. Our approach to controller composition makes use of the funnel as a metaphor for asymptotic stability, is motivated by the pre-image backchaining techniques developed by Lozano-Perez, Mason and Taylor, and extends their ideas from quasi-static environments to systems with full dynamics. We introduce the concepts of "dynamical obstacle avoidance" and "dynamical safety" for systems with only intermittent control of their environment, and show that it is important not only that the system avoid obstacles directly, but also that the system will never reach an obstacle before getting another chance to effect control. The Dynamical Pick and Place problem addressed by this thesis is a difficult control problem, but an easy planning problem. The system we develop provides a way to engage more powerful AI planning tools without sacrificing access to the stability arguments of dynamical systems theory. Detection and isolation of failures in large, complex systems is a crucial and challenging task. The increasingly stringent requirements on performance and reliability of complex technological systems have necessitated the development of sophisticated and systematic methods for the timely and accurate diagnosis of system failures. We propose a discrete-event systems (DES) approach to the failure diagnosis problem. This approach is applicable to systems that fall naturally in the class of DES; moreover, for the purpose of diagnosis, continuous-variable dynamic systems can often be viewed as DES at a higher level of abstraction. We present a methodology for modeling physical systems in a DES framework and illustrate this method with examples. We discuss the notion of diagnosability, the construction procedure of the diagnoser, and necessary and sufficient conditions for diagnosability. Finally, we illustrate our approach using realistic models of two different heating, ventilation, and air conditioning (HVAC) systems, one diagnosable and the other not diagnosable. While the modeling methodology presented here has been developed for the purpose of failure diagnosis, its scope is not restricted to this problem; it can also be used to develop DES models for other purposes such as control. Modeling of hybrid systems.- Examples of hybrid dynamical systems.- Variable-structure systems.- Complementarity systems.- Analysis of hybrid systems.- Hybrid control design.