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.
There are also attempts in the literature that extend opacity from discrete systems to continuous systems. For example, in the recent results in @cite_44 @cite_29 @cite_22 , the authors extended the notion of opacity to (switched) linear systems. However, their definition of opacity is more related to an output reachability property rather than an information-flow property. Moreover, their formulation is mostly based on the setting of exact opacity, i.e., we can always distinguish two different outputs precisely no matter how close they are, In @cite_44 , the authors mentioned the direction of using output metric to quantify opacity and a property called strong @math - @math -initial-state opacity was proposed, which is closely related to our notions. However, no systematic study, e.g., verification and abstraction as we consider in this paper, was provided for this property.
@cite_44 @cite_29 @cite_22
2901162916 2601738991 2787221116 1992424076
Abstract Opacity is an important information-flow property that arises in security and privacy analysis of cyber–physical systems. Among many different notions of opacity, K -step opacity requires that the intruder can never determine unambiguously that the system was at a secret state for any specific instant within K steps prior to that particular instant. This notion becomes infinity-step opacity when K goes to infinity. Existing works on the analysis of infinite-step opacity and K -step opacity only provide a binary characterization, i.e., a system is either opaque or non-opaque. To analyze infinite-step and K -step opacity more quantitatively, in this paper, we investigate the verification of infinite-step and K -step opacity in the context of stochastic discrete-event systems. A new notion of opacity, called almost infinite-step opacity (respectively, almost K -step opacity), is proposed to capture whether or not the probability of violating infinite-step opacity (respectively, K -step opacity) is smaller than a given threshold. We also provide effective algorithms for the verification of almost infinite-step opacity and almost K -step opacity. Abstract In the context of security analysis for information flow properties, where a potentially malicious observer (intruder) tracks the observed behavior of a given system, infinite-step opacity (respectively, K -step opacity) holds if the intruder can never determine for sure that the system was in a secret state for any instant within infinite steps (respectively, K steps) prior to that particular instant. We present new algorithms for the verification of the properties of infinite-step opacity and K -step opacity for partially-observed discrete event systems modeled as finite-state automata. Our new algorithms are based on a novel separation principle for state estimates that characterizes the information dependence in opacity verification problems, and they have lower computational complexity than previously-proposed ones in the literature. Specifically, we propose a new information structure, called the two-way observer, that is used for the verification of infinite-step and K -step opacity. Based on the two-way observer, a new upper bound for the delay in K -step opacity is derived, which also improves previously-known results. 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. A system is said to be current-state opaque if the entrance of the system state to a set of secret states remains opaque (uncertain) to an intruder-at least until the system leaves the set of secret states. This notion of opacity has been studied in nondeterministic finite automata settings (where the intruder observes a subset of events, for example, via some natural projection mapping) and has been shown to be useful in characterizing security requirements in many applications (including encryption using pseudorandom generators and coverage properties in sensor networks). One limitation of the majority of existing analysis is that it fails to provide a quantifiable measure of opacity for a given system; instead, it simply provides a binary characterization of the system (being opaque or not opaque). In this paper, we address this limitation by extending current-state opacity formulations to systems that can be modeled as probabilistic finite automata under partial observation. We introduce three notions of opacity, namely: 1) step-based almost current-state opacity; 2) almost current-state opacity; and 3) probabilistic current-state opacity, all of which can be used to provide a measure of a given system's opacity. We also propose verification methods for these probabilistic notions of opacity and characterize their corresponding computational complexities.