Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userError- and Tamper-Tolerant State Estimation for Discrete Event Systems under Cost Constraints
269
0
0.0
(
0
)
Added by
Yuting Li
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper deals with the state estimation problem in discrete-event systems modeled with nondeterministic finite automata, partially observed via a sensor measuring unit whose measurements (reported observations) may be vitiated by a malicious attacker. The attacks considered in this paper include arbitrary deletions, insertions, or substitutions of observed symbols by taking into account a bounded number of attacks or, more generally, a total cost constraint (assuming that each deletion, insertion, or substitution bears a positive cost to the attacker). An efficient approach is proposed to describe possible sequences of observations that match the one received by the measuring unit, as well as their corresponding state estimates and associated total costs. We develop an algorithm to obtain the least-cost matching sequences by reconstructing only a finite number of possible sequences, which we subsequently use to efficiently perform state estimation. We also develop a technique for verifying tamper-tolerant diagnosability under attacks that involve a bounded number of deletions, insertions, and substitutions (or, more generally, under attacks of bounded total cost) by using a novel structure obtained by attaching attacks and costs to the original plant. The overall construction and verification procedure have complexity that is of O(|X|^2 C^2),where |X| is the number of states of the given finite automaton and C is the maximum total cost that is allowed for all the deletions, insertions, and substitutions. We determine the minimum value of C such that the attacker can coordinate its tampering action to keep the observer indefinitely confused while utilizing a finite number of attacks. Several examples are presented to demonstrate the proposed methods.
rate research
Read More
The problem of state estimation in the setting of partially-observed discrete event systems subject to cyber attacks is considered. An operator observes a plant through a natural projection that hides the occurrence of certain events. The objective of the operator is that of estimating the current state of the system. The observation is 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. An automaton, called attack structure, is defined to describe the set of all possible attacks. In more details, first, an unbounded attack structure is obtained by concurrent composition of two state observers, the attacker observer and the operator observer. Then, the attack structure is refined to obtain a supremal stealthy attack substructure. An attack function may be selected from the supremal stealthy attack substructure and it is said harmful when some malicious goal of the attacker is reached, namely if the set of states consistent with the observation produced by the system and the set of states consistent with the corrupted observation belong to a given relation. The proposed approach can be dually used to verify if there exists a harmful attack for the given system: this allows one to establish if the system is safe under attack.
In networked systems, state estimation is hampered by communication limits. Past approaches, which consider scheduling sensors through deterministic event-triggers, reduce communication and maintain estimation quality. However, these approaches destroy the Gaussian property of the state, making it computationally intractable to obtain an exact minimum mean squared error estimate. We propose a stochastic event-triggered sensor schedule for state estimation which preserves the Gaussianity of the system, extending previous results from the single-sensor to the multi-sensor case.
Coexistence by means of shared access is a cognitive radio application. The secondary user models the slotted primary users channel access as a Markov process. The model parameters, i.e, the state transition probabilities (alpha,beta) help secondary user to determine the channel occupancy, thereby enables secondary user to rank the primary user channels. These parameters are unknown and need to be estimated by secondary users for each channel. To do so, the secondary users have to sense all the primary user channels in every time slot, which is unrealistic for a large and sparsely allocated primary user spectrum. With no other choice left, the secondary user has to sense a channel at random time intervals and estimate the parametric information for all the channels using the observed slots.
We consider the problem of estimating Shannons entropy $H$ from discrete data, in cases where the number of possible symbols is unknown or even countably infinite. The Pitman-Yor process, a generalization of Dirichlet process, provides a tractable prior distribution over the space of countably infinite discrete distributions, and has found major applications in Bayesian non-parametric statistics and machine learning. Here we show that it also provides a natural family of priors for Bayesian entropy estimation, due to the fact that moments of the induced posterior distribution over $H$ can be computed analytically. We derive formulas for the posterior mean (Bayes least squares estimate) and variance under Dirichlet and Pitman-Yor process priors. Moreover, we show that a fixed Dirichlet or Pitman-Yor process prior implies a narrow prior distribution over $H$, meaning the prior strongly determines the entropy estimate in the under-sampled regime. We derive a family of continuous mixing measures such that the resulting mixture of Pitman-Yor processes produces an approximately flat prior over $H$. We show that the resulting Pitman-Yor Mixture (PYM) entropy estimator is consistent for a large class of distributions. We explore the theoretical properties of the resulting estimator, and show that it performs well both in simulation and in application to real data.
The goal of combinatorial group testing is to efficiently identify up to $d$ defective items in a large population of $n$ items, where $d ll n$. Defective items satisfy certain properties while the remaining items in the population do not. To efficiently identify defective items, a subset of items is pooled and then tested. In this work, we consider complex group testing (CmplxGT) in which a set of defective items consists of subsets of positive items (called textit{positive complexes}). CmplxGT is classified into two categories: classical CmplxGT (CCmplxGT) and generalized CmplxGT (GCmplxGT). In CCmplxGT, the outcome of a test on a subset of items is positive if the subset contains at least one positive complex, and negative otherwise. In GCmplxGT, the outcome of a test on a subset of items is positive if the subset has a certain number of items of some positive complex, and negative otherwise. For CCmplxGT, we present a scheme that efficiently identifies all positive complexes in time $t times mathrm{poly}(d, ln{n})$ in the presence of erroneous outcomes, where $t$ is a predefined parameter. As $d ll n$, this is significantly better than the currently best time of $mathrm{poly}(t) times O(n ln{n})$. Moreover, in specific cases, the number of tests in our proposed scheme is smaller than previous work. For GCmplxGT, we present a scheme that efficiently identifies all positive complexes. These schemes are directly applicable in various areas such as complex disease genetics, molecular biology, and learning a hidden graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
