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 only consider non-metric systems by assuming that the intruder can always distinguish two different outputs precisely. In this paper, we extend the concept of opacity to 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. A new concept called approximate opacity is proposed in order to quantitatively evaluate the security guarantee level with respect to the measurement precision of the intruder. Then we propose a new simulation-type relation, called approximate opacity preserving simulation relation, which characterizes how close two systems are in terms of the satisfaction of approximate opacity. This allows us to verify approximate opacity for large-scale, or even infinite systems, using their abstractions. We also discuss how to construct approximate opacity preserving symbolic models for a class of discrete-time control systems. Our results extend the definitions and analysis techniques for opacity from non-metric systems to metric systems.
Abstraction-based techniques have also been investigated in the literature for the verification and synthesis of opacity; see, e.g., @cite_43 @cite_38 @cite_14 @cite_19 @cite_0 . In particular, in our recent work @cite_43 , we propose several notions of opacity preserving (bi)simulation relations. However, these relations only preserve exact opacity for non-metric systems. Our new relations extend the relations in @cite_43 to metric systems by taking into account how close two systems are. Such an extension is motivated by the definition of approximate (bi)simulation relation originally proposed in @cite_30 . However, the original definition of approximate (bi)simulation relation does not necessarily preserves approximate opacity. Constructing symbolic models for control systems is also an active research area; see, e.g., @cite_28 @cite_39 @cite_36 @cite_16 . However, most of the existing works on the construction of symbolic models only consider the dynamics of the systems and are not taking into account the opacity property. In our approach, we need to consider both the dynamic and the secret of the system while constructing the symbolic model and guarantee the preservation of approximate opacity across related systems.
@cite_30 @cite_38 @cite_14 @cite_28 @cite_36 @cite_39 @cite_0 @cite_19 @cite_43 @cite_16
2011979623 2882998909 2904010205 2165748475 2169289043 2152784531 2914250191 2809079675 2787221116 2952918945
Established system relationships for discrete systems, such as language inclusion, simulation, and bisimulation, require system observations to be identical. When interacting with the physical world, modeled by continuous or hybrid systems, exact relationships are restrictive and not robust. In this paper, we develop the first framework of system approximation that applies to both discrete and continuous systems by developing notions of approximate language inclusion, approximate simulation, and approximate bisimulation relations. We define a hierarchy of approximation pseudo-metrics between two systems that quantify the quality of the approximation, and capture the established exact relationships as zero sections. Our approximation framework is compositional for a synchronous composition operator. Algorithms are developed for computing the proposed pseudo-metrics, both exactly and approximately. The exact algorithms require the generalization of the fixed point algorithms for computing simulation and bisimulation relations, or dually, the solution of a static game whose cost is the so-called branching distance between the systems. Approximations for the pseudo-metrics can be obtained by considering Lyapunov-like functions called simulation and bisimulation functions. We illustrate our approximation framework in reducing the complexity of safety verification problems for both deterministic and nondeterministic continuous systems In this paper, an alternative equivalence based definition of bisimulation is proposed, called visible bisimulation equivalence. It includes both state and transition labels and therefore unifies stuttering and branching bisimulation. Furthermore, it is equivalent to a temporal logic called ECTL*, where CTL* is extended with events. The presented bisimulation abstraction is applied to a set of synchronized submodels, where local events are identified incrementally and abstracted after each synchronization. Since the bisimulation reduction is applied after each synchronization, a significant part of the state space explosion in ordinary synchronization is avoided. This compositional abstraction is used for opacity verification, where it is shown that local observers can be generated before they are synchronized, a key factor to be able to apply compositional opacity verification. The efficiency of this method is illustrated on a modular opacity problem with mutual exclusion of moving agents. With the proliferation of communication networks and mobile devices, the privacy and security concerns on their information flow are raised. Given a critical system that may leak confidential information, the problem consists of verifying and also enforcing opacity by designing supervisors, to conceal confidential information from unauthorized persons. To find out what the intruder sees, it is required to construct an observer of the system. In this paper, we consider incremental observer generation of modular systems, for verification and enforcement of current state opacity. The synchronization of the subsystems generate a large state space. Moreover, the observer generation with exponential complexity adds even larger state space. To tackle the complexity problem, we prove that observer generation can be done locally before synchronizing the subsystems. The incremental local observer generation along with an abstraction method lead to a significant state space reduction compared to traditional monolithic methods. The existence of shared unobservable events is also considered in the incremental approach. Moreover, we present an illustrative example, where the results of verification and enforcement of current state opacity are shown on a modular multiple floor elevator building with an intruder. Furthermore, we extend the current state opacity, current state anonymity, and language based opacity formulations for verification of modular systems. Switched systems constitute an important modeling paradigm faithfully describing many engineering systems in which software interacts with the physical world. Despite considerable progress on stability and stabilization of switched systems, the constant evolution of technology demands that we make similar progress with respect to different, and perhaps more complex, objectives. This paper describes one particular approach to address these different objectives based on the construction of approximately equivalent (bisimilar) symbolic models for switched systems. The main contribution of this paper consists in showing that under standard assumptions ensuring incremental stability of a switched system (i.e., existence of a common Lyapunov function, or multiple Lyapunov functions with dwell time), it is possible to construct a finite symbolic model that is approximately bisimilar to the original switched system with a precision that can be chosen a priori. To support the computational merits of the proposed approach, we use symbolic models to synthesize controllers for two examples of switched systems, including the boost dc-dc converter. Finite-state models of control systems were proposed by several researchers as a convenient mechanism to synthesize controllers enforcing complex specifications. Most techniques for the construction of such symbolic models have two main drawbacks: either they can only be applied to restrictive classes of systems, or they require the exact computation of reachable sets. In this paper, we propose a new abstraction technique that is applicable to any nonlinear sampled-data control system as long as we are only interested in its behavior in a compact set. Moreover, the exact computation of reachable sets is not required. The effectiveness of the proposed results is illustrated by synthesizing a controller to steer a vehicle. Sufficiently accurate finite state models, also called symbolic models or discrete abstractions, allow one to apply fully automated methods, originally developed for purely discrete systems, to formally reason about continuous and hybrid systems and to design finite state controllers that provably enforce predefined specifications. We present a novel algorithm to compute such finite state models for nonlinear discrete-time and sampled systems which depends on quantizing the state space using polyhedral cells, embedding these cells into suitable supersets whose attainable sets are convex, and over-approximating attainable sets by intersections of supporting half-spaces. We prove a novel recursive description of these half-spaces and propose an iterative procedure to compute them efficiently. We also provide new sufficient conditions for the convexity of attainable sets which imply the existence of the aforementioned embeddings of quantizer cells. Our method yields highly accurate abstractions and applies to nonlinear systems under mild assumptions, which reduce to sufficient smoothness in the case of sampled systems. Its practicability in the design of discrete controllers for nonlinear continuous plants under state and control constraints is demonstrated by an example. This paper investigates the synthesis of edit functions for opacity enforcement using abstraction methods to reduce computational complexity. Edit functions are used to alter system outputs by erasing or inserting events in order to prevent violations of opacity. We introduce two abstraction methods, called opaque observation equivalence and opaque bisimulation, that are used to abstract the original system and its observer before calculating edit functions. We present a set of results on abstraction for opacity and its enforcement by edit functions that prove that edit functions synthesized from abstracted models are “equivalent” to ones synthesized from original ones. Our approach leverages the technique of edit function synthesis using the All Edit Structure from prior works. In this paper, we propose several opacity-preserving (bi)simulation relations for general nondeterministic transition systems (NTS) in terms of initial-state opacity, current-state opacity, K-step opacity, and infinite-step opacity. We also show how one can leverage quotient construction to compute such relations. In addition, we use a two-way observer method to verify opacity of nondeterministic finite transition systems (NFTSs). As a result, although the verification of opacity for infinite NTSs is generally undecidable, if one can find such an opacity-preserving relation from an infinite NTS to an NFTS, the (lack of) opacity of the NTS can be easily verified over the NFTS which is decidable. Stochastic switched systems are a relevant class of stochastic hybrid systems with probabilistic evolution over a continuous domain and control-dependent discrete dynamics over a finite set of modes. In the past few years several different techniques have been developed to assist in the stability analysis of stochastic switched systems. However, more complex and challenging objectives related to the verification of and the controller synthesis for logic specifications have not been formally investigated for this class of systems as of yet. With logic specifications we mean properties expressed as formulae in linear temporal logic or as automata on infinite strings. This paper addresses these complex objectives by constructively deriving approximately equivalent (bisimilar) symbolic models of stochastic switched systems. More precisely, this paper provides two different symbolic abstraction techniques: one requires state space discretization, but the other one does not require any space discretization which can be potentially more efficient than the first one when dealing with higher dimensional stochastic switched systems. Both techniques provide finite symbolic models that are approximately bisimilar to stochastic switched systems under some stability assumptions on the concrete model. This allows formally synthesizing controllers (switching signals) that are valid for the concrete system over the finite symbolic model, by means of mature automata-theoretic techniques in the literature. The effectiveness of the results are illustrated by synthesizing switching signals enforcing logic specifications for two case studies including temperature control of a six-room building.