Skip to main content
Journal cover image

An optimal graph-search method for secure state estimation

Publication ,  Journal Article
Luo, X; Pajic, M; Zavlanos, MM
Published in: Automatica
January 1, 2021

The growing complexity of modern Cyber–Physical Systems (CPS) and the frequent communication between their components make them vulnerable to malicious attacks. As a result, secure state estimation is a critical requirement for the control of these systems. Many existing secure state estimation methods suffer from combinatorial complexity which grows with the number of states and sensors in the system. This complexity can be mitigated using optimization-based methods that relax the original state estimation problem, although at the cost of optimality as these methods often identify attack-free sensors as attacked. In this paper, we propose a new optimal graph-search algorithm to correctly identify malicious attacks and to securely estimate the states even in large-scale CPS modeled as linear time-invariant systems The graph consists of layers, each one containing two nodes capturing a truth assignment of any given sensor, and directed edges connecting adjacent layers only. Then, our algorithm searches the layers of this graph incrementally, favoring directions at higher layers with more attack-free assignments, while actively managing a repository of nodes to be expanded at later iterations. The proposed search bias and the ability to revisit nodes in the repository and self-correct, allow our graph-search algorithm to reach the optimal assignment faster and tackle larger problems. We show that our algorithm is complete and optimal provided that process and measurement noises do not dominate the attack signal. Moreover, we provide numerical simulations that demonstrate the ability of our algorithm to correctly identify attacked sensors and securely reconstruct the state. Our simulations show that our method outperforms existing algorithms both in terms of optimality and execution time.

Duke Scholars

Published In

Automatica

DOI

ISSN

0005-1098

Publication Date

January 1, 2021

Volume

123

Related Subject Headings

  • Industrial Engineering & Automation
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 40 Engineering
  • 09 Engineering
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Luo, X., Pajic, M., & Zavlanos, M. M. (2021). An optimal graph-search method for secure state estimation. Automatica, 123. https://doi.org/10.1016/j.automatica.2020.109323
Luo, X., M. Pajic, and M. M. Zavlanos. “An optimal graph-search method for secure state estimation.” Automatica 123 (January 1, 2021). https://doi.org/10.1016/j.automatica.2020.109323.
Luo X, Pajic M, Zavlanos MM. An optimal graph-search method for secure state estimation. Automatica. 2021 Jan 1;123.
Luo, X., et al. “An optimal graph-search method for secure state estimation.” Automatica, vol. 123, Jan. 2021. Scopus, doi:10.1016/j.automatica.2020.109323.
Luo X, Pajic M, Zavlanos MM. An optimal graph-search method for secure state estimation. Automatica. 2021 Jan 1;123.
Journal cover image

Published In

Automatica

DOI

ISSN

0005-1098

Publication Date

January 1, 2021

Volume

123

Related Subject Headings

  • Industrial Engineering & Automation
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 40 Engineering
  • 09 Engineering
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences