Verification of $K$-Step Opacity and Analysis of Its Complexity
Verification of $K$-Step Opacity and Analysis of Its Complexity
复制标题
DOI：
10.1109/cdc.2009.5400083
复制
发表时间：
2009-12
影响因子：
5.6
通讯作者：
A. Saboori;C. Hadjicostis
中科院分区：
文献类型：
--
作者：
A. Saboori;C. Hadjicostis
出于安全和隐私的考虑，在各种应用程序的离散事件系统，我们描述和分析所需的计算复杂性验证的概念K步不透明的系统，被建模为非确定性有限自动机与部分观察其过渡。具体地说，如果在最后K个观测值内的任何特定点，系统状态到给定的秘密状态集合的入口对于具有系统模型的完整知识并通过一些自然投影图观察系统活动的入侵者来说仍然是不透明的（不确定的），则系统是K步不透明的。我们提供了两种方法来验证K步不透明性使用两种不同的状态估计器的结构，并分析了两者的计算复杂度。
Motivated by security and privacy considerations in a variety of applications of discrete event systems, we describe and analyze the computational complexity required for verifying the notion of K -step opacity for systems that are modeled as nondeterministic finite automata with partial observation on their transitions. Specifically, a system is K-step opaque if, at any specific point within the last K observations, the entrance of the system state to a given set of secret states remains opaque (uncertain) to an intruder who has complete knowledge of the system model and observes system activity through some natural projection map. We provide two methods for verifying K -step opacity using two different state estimator constructions, and analyze the computational complexity of both.