University of Illinois Urbana-Champaign

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

Saboori, Anooshiravan; Hadjicostis, Christoforos N.

Content Files
UILU-ENG-08-2204_DC-234 assembled.pdf

Permalink

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

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
Date of Ingest
2018-04-04T15:09:04Z
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
Genre of Resource
Technical Report
Language
en
Permalink
http://hdl.handle.net/2142/99605
Sponsor(s)/Grant Number(s)
National Science Foundation / NSF ECS 04-26831

Owning Collections

Report - Coordinated Science Laboratory PRIMARY