When is the Secure State-Reconstruction Problem Hard

Yanwen Mao; Aritra Mitra; Shreyas Sundaram; Paulo Tabuada

doi:10.1109/CDC40024.2019.9030047

When is the Secure State-Reconstruction Problem Hard

Yanwen Mao
, Aritra Mitra
, Shreyas Sundaram
, Paulo Tabuada

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

13 Citations (Scopus)

Abstract

This paper addresses the problem of reconstructing the state of a linear time-invariant system from malicious sensor measurements. The first result establishes that this problem is, in general, NP-hard. We then identify classes of subproblems that can be solved in polynomial time. When there are at most s malicious sensors, the problem can be solved in polynomial time when each eigenvalue is observable by at least 2s+1 sensors. When each eigenvalue has geometric multiplicity one, this condition is equivalent to the system being 2s-sparse observable. In contrast, the situation becomes more nuanced when each eigenvalue is not observable by at least 2s+1 sensors, as we describe in detail in the paper.

Original language	English
Title of host publication	2019 IEEE 58th Conference on Decision and Control, CDC 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	5368-5373
Number of pages	6
ISBN (Electronic)	9781728113982
DOIs	https://doi.org/10.1109/CDC40024.2019.9030047
Publication status	Published - Dec 2019
Externally published	Yes
Event	58th IEEE Conference on Decision and Control, CDC 2019 - Nice, France Duration: 11 Dec 2019 → 13 Dec 2019

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
Volume	2019-December
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	58th IEEE Conference on Decision and Control, CDC 2019
Country/Territory	France
City	Nice
Period	11/12/19 → 13/12/19

ASJC Scopus subject areas

Control and Systems Engineering
Modelling and Simulation
Control and Optimization

Access to Document

10.1109/CDC40024.2019.9030047

Cite this

Mao, Y., Mitra, A., Sundaram, S., & Tabuada, P. (2019). When is the Secure State-Reconstruction Problem Hard. In 2019 IEEE 58th Conference on Decision and Control, CDC 2019 (pp. 5368-5373). Article 9030047 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2019-December). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC40024.2019.9030047

@inproceedings{c8af9c0a9d3b4b8893edf89541e20cce,

title = "When is the Secure State-Reconstruction Problem Hard",

abstract = "This paper addresses the problem of reconstructing the state of a linear time-invariant system from malicious sensor measurements. The first result establishes that this problem is, in general, NP-hard. We then identify classes of subproblems that can be solved in polynomial time. When there are at most s malicious sensors, the problem can be solved in polynomial time when each eigenvalue is observable by at least 2s+1 sensors. When each eigenvalue has geometric multiplicity one, this condition is equivalent to the system being 2s-sparse observable. In contrast, the situation becomes more nuanced when each eigenvalue is not observable by at least 2s+1 sensors, as we describe in detail in the paper.",

author = "Yanwen Mao and Aritra Mitra and Shreyas Sundaram and Paulo Tabuada",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 58th IEEE Conference on Decision and Control, CDC 2019 ; Conference date: 11-12-2019 Through 13-12-2019",

year = "2019",

month = dec,

doi = "10.1109/CDC40024.2019.9030047",

language = "English",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "5368--5373",

booktitle = "2019 IEEE 58th Conference on Decision and Control, CDC 2019",

address = "United States",

}

Mao, Y, Mitra, A, Sundaram, S & Tabuada, P 2019, When is the Secure State-Reconstruction Problem Hard. in 2019 IEEE 58th Conference on Decision and Control, CDC 2019., 9030047, Proceedings of the IEEE Conference on Decision and Control, vol. 2019-December, Institute of Electrical and Electronics Engineers Inc., pp. 5368-5373, 58th IEEE Conference on Decision and Control, CDC 2019, Nice, France, 11/12/19. https://doi.org/10.1109/CDC40024.2019.9030047

When is the Secure State-Reconstruction Problem Hard. / Mao, Yanwen; Mitra, Aritra; Sundaram, Shreyas et al.
2019 IEEE 58th Conference on Decision and Control, CDC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 5368-5373 9030047 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2019-December).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - When is the Secure State-Reconstruction Problem Hard

AU - Mao, Yanwen

AU - Mitra, Aritra

AU - Sundaram, Shreyas

AU - Tabuada, Paulo

PY - 2019/12

Y1 - 2019/12

N2 - This paper addresses the problem of reconstructing the state of a linear time-invariant system from malicious sensor measurements. The first result establishes that this problem is, in general, NP-hard. We then identify classes of subproblems that can be solved in polynomial time. When there are at most s malicious sensors, the problem can be solved in polynomial time when each eigenvalue is observable by at least 2s+1 sensors. When each eigenvalue has geometric multiplicity one, this condition is equivalent to the system being 2s-sparse observable. In contrast, the situation becomes more nuanced when each eigenvalue is not observable by at least 2s+1 sensors, as we describe in detail in the paper.

AB - This paper addresses the problem of reconstructing the state of a linear time-invariant system from malicious sensor measurements. The first result establishes that this problem is, in general, NP-hard. We then identify classes of subproblems that can be solved in polynomial time. When there are at most s malicious sensors, the problem can be solved in polynomial time when each eigenvalue is observable by at least 2s+1 sensors. When each eigenvalue has geometric multiplicity one, this condition is equivalent to the system being 2s-sparse observable. In contrast, the situation becomes more nuanced when each eigenvalue is not observable by at least 2s+1 sensors, as we describe in detail in the paper.

UR - https://www.scopus.com/pages/publications/85082442375

U2 - 10.1109/CDC40024.2019.9030047

DO - 10.1109/CDC40024.2019.9030047

M3 - Conference contribution

AN - SCOPUS:85082442375

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 5368

EP - 5373

BT - 2019 IEEE 58th Conference on Decision and Control, CDC 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 58th IEEE Conference on Decision and Control, CDC 2019

Y2 - 11 December 2019 through 13 December 2019

ER -

When is the Secure State-Reconstruction Problem Hard

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this