Delayed State Estimation in Discrete Event Systems and Applications to Security Problems

Saboori, Anooshiravan; Hadjicostis, Christoforos N.

Permalink

https://hdl.handle.net/2142/99605 Copy

Description

Title

Delayed State Estimation in Discrete Event Systems and Applications to Security Problems

Author(s)

• Saboori, Anooshiravan
• Hadjicostis, Christoforos N.

Issue Date

2008-03

Keyword(s)

• Discrete event systems
• State estimation
• Automata
• Security

Abstract

Application of discrete event systems in modeling and analyzing security problems has given rise to applications that require keeping track of (part of the) sequence of states that have been visited so far. Specifically, the notion of opacity requires that the truth of a certain predicate on the system state cannot be determined by an outside observer for the duration of a certain time window (or even at all times). Depending on the notion of opacity that is used, this predicate can be defined for states visited in the past (with no bound on how far into the past) or for states which have been visited a fixed number of observations in the past. In this report, motivated by such questions we introduce the problem of delayed estimation in discrete event systems modeled as a finite automaton with a finite number of states, unknown initial state, and partial event observation (but no state observation). Specifically, we consider two estimation problems: (i) initial state estimation which requires the estimate of the initial state following a sequence of observations and, (ii) K- delayed state estimation which requires the estimate of the state the system was in when it generated the Kth to last output (i.e., the state of the system K observations ago). To solve these two problems we construct appropriate state estimators and show that these delay state estimators can be used to verify opacity notions of interest.

Publisher

Coordinated Science Laboratory, University of Illinois at Urbana-Champaign

Series/Report Name or Number

Coordinated Science Laboratory Report no. UILU-ENG-08-2204, DC-234

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/99605

Sponsor(s)/Grant Number(s)

National Science Foundation / NSF ECS 04-26831

Owning Collections