On the computational complexity of the secure state-reconstruction problem
On the computational complexity of the secure state-reconstruction problem
复制标题
关于安全状态重建问题的计算复杂度
DOI：
10.1016/j.automatica.2021.110083
复制
发表时间：
2022
期刊：
影响因子：
6.4
通讯作者：
Tabuada, Paulo
中科院分区：
文献类型：
--
作者：
Mao, Yanwen;Mitra, Aritra;Sundaram, Shreyas;Tabuada, Paulo
在本文中，我们讨论了根据已被对手破坏的传感器测量值重建线性系统状态的计算复杂性。第一个结果表明，该问题在一般情况下是NP难的。然后，我们介绍了特征值可观性的概念，并表明，状态可以在多项式时间内重建时，每个特征值是由至少2 s+ 1传感器和最多s传感器被破坏的对手。然而，有一个差距之间的特征值的可观测性和重建的状态，尽管攻击的可能性，这种差距的特点是在文献中的稀疏可观测性的概念。为了更好地理解这一点，我们表明，当线性系统的A矩阵具有酉几何多重性，差距消失，即特征值可观性与稀疏可观性相一致，并存在一个多项式时间算法来重建的状态提供的状态可以重建。
In this paper, we discuss the computational complexity of reconstructing the state of a linear system from sensor measurements that have been corrupted by an adversary. The first result establishes that the problem is, in general, NP-hard. We then introduce the notion of eigenvalue observability and show that the state can be reconstructed in polynomial time when each eigenvalue is observable by at least 2 s+ 1 sensors and at most s sensors are corrupted by an adversary. However, there is a gap between eigenvalue observability and the possibility of reconstructing the state despite attacks—this gap has been characterized in the literature by the notion of sparse observability. To better understand this, we show that when the A matrix of the linear system has unitary geometric multiplicity, the gap disappears, ie, eigenvalue observability coincides with sparse observability, and there exists a polynomial time algorithm to reconstruct the state provided the state can be reconstructed.