Paper Info
Title
Secure State Estimation for Cyber-Physical Systems Under Sensor Attacks: A Satisfiability Modulo Theory Approach.
Abstract
Secure state estimation is the problem of estimating the state of a dynamical system from a set of noisy and adversarially corrupted measurements. Intrinsically a combinatorial problem, secure state estimation has been traditionally addressed either by brute force search, suffering from scalability issues, or via convex relaxations, using algorithms that can terminate in polynomial time but are not necessarily sound. In this paper, we present a novel algorithm that uses a satisfiability modulo theory approach to harness the complexity of secure state estimation. We leverage results from formal methods over real numbers to provide guarantees on the soundness and completeness of our algorithm. Moreover, we discuss its scalability properties, by providing upper bounds on the runtime performance. Numerical simulations support our arguments by showing an order of magnitude decrease in execution time with respect to alternative techniques. Finally, the effectiveness of the proposed algorithm is demonstrated by applying it to the problem of controlling an unmanned ground vehicle.
Year
DOI
Venue
2017
10.1109/TAC.2017.2676679
IEEE Trans. Automat. Contr.
Keywords
Field
DocType
State estimation,Semiconductor device measurement,Process control,Noise measurement,Scalability,Heuristic algorithms,Upper bound
Secure state,Mathematical optimization,Brute-force search,Upper and lower bounds,Modulo,Satisfiability,Theoretical computer science,Soundness,Time complexity,Mathematics,Scalability
Journal
Volume
Issue
ISSN
62
10
0018-9286
Citations 
PageRank 
References 
29
1.03
8
Authors
6
Name
Order
Citations
PageRank
Yasser Shoukry110412.27
Pierluigi Nuzzo230533.35
Alberto Puggelli3291.03
Alberto L. Sangiovanni-Vincentelli4113851881.40
Sanjit A. Seshia52226168.09
Paulo Tabuada64281264.80