Error- and Tamper-Tolerant State Estimation for Discrete Event Systems Under Cost Constraints

This article 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 observed symbols) may be vitiated by a malicious attacker. The attacks considered in this article 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). We provide a characterization of the sequences of symbols that match the received sequence of possibly corrupted symbols, and subsequently use them to recursively perform tamper-tolerant state estimation subject to cost constraints. Each step of the recursive state estimation procedure has complexity of
$O(|X||\Sigma |C)$
, where
$|X|$
(
$|\Sigma |$
) is the number of states (events) of the given finite automaton and
$C$
is the maximum total cost that is allowed for all deletions, insertions, and substitutions.