The Experts below are selected from a list of 71418 Experts worldwide ranked by ideXlab platform
Stephane Lafortune - One of the best experts on this subject based on the ideXlab platform.
-
compositional and abstraction based approach for synthesis of edit functions for Opacity enforcement
IEEE Transactions on Automatic Control, 2020Co-Authors: Saha Mohajerani, Stephane LafortuneAbstract:This article develops a novel compositional and abstraction-based approach to synthesize edit functions for Opacity enforcement in modular discrete event systems. Edit functions alter the output of the system by erasing or inserting events in order to obfuscate the outside intruder, whose goal is to infer the secrets of the system from its observation. We synthesize edit functions to solve the Opacity enforcement problem in a modular setting, which significantly reduces the computational complexity compared with the monolithic approach. Two abstraction methods called opaque observation equivalence and opaque bisimulation are first employed to abstract the individual components of the modular system and their observers. Subsequently, we propose a method to transform the synthesis of edit functions to the calculation of modular supremal nonblocking supervisors. We show that the edit functions synthesized in this manner correctly solve the Opacity enforcement problem.
-
transforming Opacity verification to nonblocking verification in modular systems
IEEE Transactions on Automatic Control, 2020Co-Authors: Saha Mohajerani, Stephane LafortuneAbstract:We consider the verification of current-state and $K$ -step Opacity for systems modeled as interacting nondeterministic finite-state automata. We describe a new methodology for compositional Opacity verification that employs abstraction, in the form of a notion called opaque observation equivalence, and that leverages existing compositional nonblocking verification algorithms. The compositional approach is based on a transformation of the system, where the transformed system is nonblocking if and only if the original one is current-state opaque. Furthermore, we prove that $K$ -step Opacity can also be inferred if the transformed system is nonblocking. We provide experimental results where current-state Opacity is verified efficiently for a large scaled-up system.
-
Opacity enforcement using nondeterministic publicly known edit functions
IEEE Transactions on Automatic Control, 2019Co-Authors: Stephane LafortuneAbstract:This note investigates enforcement of Opacity by nondeterministic edit functions. The edit functions alter the system's output by inserting fictitious events or erasing observed events. The edit decisions are randomly made while not known by the outside environment a priori . There is an intruder characterized as a passive observer with malicious goals to infer the secrets of the system. We require that Opacity be enforced when the intruder may or may not know the implementation of edit functions. This requirement is termed as private and public safety. We also restrict the operation of edit functions by defining edit constraints. Then, the Opacity enforcement problem is transformed to a three-player game among the edit function, the environment, and a dummy player, which helps to determine edit decisions. A game structure called the all edit structure (AES) is introduced to characterize the interaction among those players. It embeds all privately safe edit functions and may also embed publicly safe edit functions. Based on the AES, we present an algorithm that provably synthesizes nondeterministic edit functions that satisfy both private safety and public safety.
-
a new approach for the verification of infinite step and k step Opacity using two way observers
Automatica, 2017Co-Authors: Stephane LafortuneAbstract: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.
-
synthesis of insertion functions for enforcement of Opacity security properties
Automatica, 2014Co-Authors: Stephane LafortuneAbstract:Abstract Opacity is a confidentiality property that characterizes whether a “secret” of a system can be inferred by an outside observer called an “intruder”. In this paper, we consider the problem of enforcing Opacity in systems modeled as partially-observed finite-state automata. We propose a novel enforcement mechanism based on the use of insertion functions. An insertion function is a monitoring interface at the output of the system that changes the system’s output behavior by inserting additional observable events. We define the property of “i-enforceability” that an insertion function needs to satisfy in order to enforce Opacity. I-enforceability captures an insertion function’s ability to respond to every system’s observed behavior and to output only modified behaviors that look like existing non-secret behaviors. Given an insertion function, we provide an algorithm that verifies whether it is i-enforcing. More generally, given an Opacity notion, we determine whether it is i-enforceable or not by constructing a structure called the “All Insertion Structure” (AIS). The AIS enumerates all i-enforcing insertion functions in a compact state transition structure. If a given Opacity notion has been verified to be i-enforceable, we show how to use the AIS to synthesize an i-enforcing insertion function.
Christoforos N. Hadjicostis - One of the best experts on this subject based on the ideXlab platform.
-
Current-State Opacity Formulations in Probabilistic Finite Automata
IEEE Transactions on Automatic Control, 2014Co-Authors: Anooshiravan Saboori, Christoforos N. HadjicostisAbstract: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.
-
verification of initial state Opacity in security applications of discrete event systems
Information Sciences, 2013Co-Authors: Anooshiravan Saboori, Christoforos N. HadjicostisAbstract:In this paper, we formulate and analyze methodologies for verifying the notion of initial-state Opacity in discrete event systems that are modeled as non-deterministic finite automata with partial observation on their transitions. A system is initial-state opaque if the membership of its true initial state to a set of secret states remains opaque (i.e., uncertain) to an intruder who observes system activity through some projection map. Initial-state Opacity can be used to characterize security requirements in a variety of applications, including tracking problems in sensor networks. In order to model and analyze the intruder capabilities regarding initial-state Opacity, we first address the initial-state estimation problem in a non-deterministic finite automaton via the construction of an initial-state estimator. We analyze the properties and complexity of the initial-state estimator, and show how the complexity of the verification method can be greatly reduced in the special case when the set of secret states is invariant. We also establish that the verification of initial-state Opacity is a PSPACE-complete problem.
-
verification of infinite step Opacity and complexity considerations
IEEE Transactions on Automatic Control, 2012Co-Authors: Anooshiravan Saboori, Christoforos N. HadjicostisAbstract:We describe and analyze the complexity of verifying the notion of infinite-step Opacity in systems that are modeled as non-deterministic finite automata with partial observation on their transitions. Specifically, a system is infinite-step opaque if the entrance of the system state, at any particular instant, to a set of secret states remains opaque (uncertain), for the length of the system operation, to an intruder who observes system activity through some projection map. Infinite-step Opacity can be used to characterize the security requirements in many applications, including encryption using pseudo-random generators, coverage properties in sensor networks, and anonymity requirements in protocols for web transactions. We show that infinite-step Opacity can be verified via the construction of a set of appropriate initial state estimators and provide illustrative examples. We also establish that the verification of infinite-step Opacity is a PSPACE-hard problem.
-
verification of k step Opacity and analysis of its complexity
Conference on Decision and Control, 2009Co-Authors: Anooshiravan Saboori, Christoforos N. HadjicostisAbstract:In this paper, we analyze the verification of K-step Opacity in discrete event systems that are modeled as (possibly non-deterministic) finite automata with partial observation on their transitions. A system is K-step opaque if the entrance of the system state within the last K observations to a set of secret states remains opaque to an intruder who has complete knowledge of the system model and observes system activity through some projection map. We establish that the verification of K-step Opacity is NP-hard. We also investigate the role of delay K in K-step Opacity and show that there exists a delay K* such that K-step Opacity and K′-step Opacity become equivalent for K′ ≫ K ≥ K*.
-
notions of security and Opacity in discrete event systems
Conference on Decision and Control, 2007Co-Authors: Anooshirava Saboori, Christoforos N. HadjicostisAbstract:In this paper, we follow a state-based approach to extend the notion of Opacity in computer security to discrete event systems. A system is (S, P)-opaque if the evolution of its true state through a set of secret states S remains opaque to an observer who is observing activity in the system through the projection map P. In other words, based on observations through the mapping P, the observer is never certain that the current state of the system is within the set of secret states S. We also introduce the stronger notion of (S,P, K)-Opacity which requires Opacity to remain true for K observations following the departure of the system's state from the set S. We show that the state-based definition of Opacity enables the use of observer constructions for verification purposes. In particular, the verification of (S,P, K)-Opacity is accomplished via an observer with K-delay which is constructed to capture state estimates with K-delay. These are the estimates of the state of the system K observations ago and are consistent with all observations (including the last K observations). We also analyze the properties and complexity of the observer with K- delay.
H. M. Antia - One of the best experts on this subject based on the ideXlab platform.
-
the discrepancy between solar abundances and helioseismology
The Astrophysical Journal, 2005Co-Authors: H. M. Antia, Sarbani BasuAbstract:There have been recent downward revisions of the solar photospheric abundances of oxygen and other heavy elements. These revised abundances along with OPAL opacities are not consistent with seismic constraints. In this work we show that the recently released Opacity Project Opacity tables cannot resolve this discrepancy either. While the revision in opacities does not seem to resolve this conflict, an upward revision of neon abundance in the solar photosphere offers a possible solution to this problem.
-
constraining solar abundances using helioseismology
The Astrophysical Journal, 2004Co-Authors: Sarbani Basu, H. M. AntiaAbstract:Recent analyses of solar photospheric abundances suggest that the oxygen abundance in the solar atmosphere needs to be revised downward. In this study, we investigate the consequence of this revision on helioseismic analyses of the depth of the solar convection zone and the helium abundance in the solar envelope and find no significant effect. We also find that the revised abundances along with the current OPAL Opacity tables are not consistent with seismic data. A significant upward revision of the Opacity tables is required to make solar models with lower oxygen abundance consistent with seismic observations.
-
seismic measurement of the depth of the solar convection zone
Monthly Notices of the Royal Astronomical Society, 1997Co-Authors: Sarbani Basu, H. M. AntiaAbstract:The observed frequencies of solar oscillations have been used to determine the depth of the convection zone. The effect of diffusion of helium and heavy elements on this measurement is studied and it is found that the discontinuity in the composition gradient at the base of the CZ due to diffusion gives rise to some systematic errors in this measurement. Taking into account these systematic errors the base of the CZ is estimated to be at a radial distance of (0.713 ± 0_001) R0 . Further, the estimated Opacity at the base of the CZ is found to be consistent with that calculated from the OPAL Opacity tables using the current value of Z/X. Assuming that the OPAL tables correctly represent the Opacity of solar material the surface Z/X is estimated to be 0.0245 ± 0.0008.
Sarbani Basu - One of the best experts on this subject based on the ideXlab platform.
-
the discrepancy between solar abundances and helioseismology
The Astrophysical Journal, 2005Co-Authors: H. M. Antia, Sarbani BasuAbstract:There have been recent downward revisions of the solar photospheric abundances of oxygen and other heavy elements. These revised abundances along with OPAL opacities are not consistent with seismic constraints. In this work we show that the recently released Opacity Project Opacity tables cannot resolve this discrepancy either. While the revision in opacities does not seem to resolve this conflict, an upward revision of neon abundance in the solar photosphere offers a possible solution to this problem.
-
constraining solar abundances using helioseismology
The Astrophysical Journal, 2004Co-Authors: Sarbani Basu, H. M. AntiaAbstract:Recent analyses of solar photospheric abundances suggest that the oxygen abundance in the solar atmosphere needs to be revised downward. In this study, we investigate the consequence of this revision on helioseismic analyses of the depth of the solar convection zone and the helium abundance in the solar envelope and find no significant effect. We also find that the revised abundances along with the current OPAL Opacity tables are not consistent with seismic data. A significant upward revision of the Opacity tables is required to make solar models with lower oxygen abundance consistent with seismic observations.
-
seismic measurement of the depth of the solar convection zone
Monthly Notices of the Royal Astronomical Society, 1997Co-Authors: Sarbani Basu, H. M. AntiaAbstract:The observed frequencies of solar oscillations have been used to determine the depth of the convection zone. The effect of diffusion of helium and heavy elements on this measurement is studied and it is found that the discontinuity in the composition gradient at the base of the CZ due to diffusion gives rise to some systematic errors in this measurement. Taking into account these systematic errors the base of the CZ is estimated to be at a radial distance of (0.713 ± 0_001) R0 . Further, the estimated Opacity at the base of the CZ is found to be consistent with that calculated from the OPAL Opacity tables using the current value of Z/X. Assuming that the OPAL tables correctly represent the Opacity of solar material the surface Z/X is estimated to be 0.0245 ± 0.0008.
Anooshiravan Saboori - One of the best experts on this subject based on the ideXlab platform.
-
Current-State Opacity Formulations in Probabilistic Finite Automata
IEEE Transactions on Automatic Control, 2014Co-Authors: Anooshiravan Saboori, Christoforos N. HadjicostisAbstract: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.
-
verification of initial state Opacity in security applications of discrete event systems
Information Sciences, 2013Co-Authors: Anooshiravan Saboori, Christoforos N. HadjicostisAbstract:In this paper, we formulate and analyze methodologies for verifying the notion of initial-state Opacity in discrete event systems that are modeled as non-deterministic finite automata with partial observation on their transitions. A system is initial-state opaque if the membership of its true initial state to a set of secret states remains opaque (i.e., uncertain) to an intruder who observes system activity through some projection map. Initial-state Opacity can be used to characterize security requirements in a variety of applications, including tracking problems in sensor networks. In order to model and analyze the intruder capabilities regarding initial-state Opacity, we first address the initial-state estimation problem in a non-deterministic finite automaton via the construction of an initial-state estimator. We analyze the properties and complexity of the initial-state estimator, and show how the complexity of the verification method can be greatly reduced in the special case when the set of secret states is invariant. We also establish that the verification of initial-state Opacity is a PSPACE-complete problem.
-
verification of infinite step Opacity and complexity considerations
IEEE Transactions on Automatic Control, 2012Co-Authors: Anooshiravan Saboori, Christoforos N. HadjicostisAbstract:We describe and analyze the complexity of verifying the notion of infinite-step Opacity in systems that are modeled as non-deterministic finite automata with partial observation on their transitions. Specifically, a system is infinite-step opaque if the entrance of the system state, at any particular instant, to a set of secret states remains opaque (uncertain), for the length of the system operation, to an intruder who observes system activity through some projection map. Infinite-step Opacity can be used to characterize the security requirements in many applications, including encryption using pseudo-random generators, coverage properties in sensor networks, and anonymity requirements in protocols for web transactions. We show that infinite-step Opacity can be verified via the construction of a set of appropriate initial state estimators and provide illustrative examples. We also establish that the verification of infinite-step Opacity is a PSPACE-hard problem.
-
verification of k step Opacity and analysis of its complexity
Conference on Decision and Control, 2009Co-Authors: Anooshiravan Saboori, Christoforos N. HadjicostisAbstract:In this paper, we analyze the verification of K-step Opacity in discrete event systems that are modeled as (possibly non-deterministic) finite automata with partial observation on their transitions. A system is K-step opaque if the entrance of the system state within the last K observations to a set of secret states remains opaque to an intruder who has complete knowledge of the system model and observes system activity through some projection map. We establish that the verification of K-step Opacity is NP-hard. We also investigate the role of delay K in K-step Opacity and show that there exists a delay K* such that K-step Opacity and K′-step Opacity become equivalent for K′ ≫ K ≥ K*.
