SMT-Based Observer Design for Cyber-Physical Systems under Sensor Attacks
Open Access
- 3 January 2018
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Cyber-Physical Systems
- Vol. 2 (1) , 1-27
Abstract
We introduce a scalable observer architecture, which can efficiently estimate the states of a discrete-time linear-time-invariant system whose sensors are manipulated by an attacker, and is robust to measurement noise. Given an upper bound on the number of attacked sensors, we build on previous results on necessary and sufficient conditions for state estimation, and propose a novel Multi-Modal Luenberger (MML) observer based on efficient Satisfiability Modulo Theory (SMT) solving. We present two techniques to reduce the complexity of the estimation problem. As a first strategy, instead of a bank of distinct observers, we use a family of filters sharing a single dynamical equation for the states, but different output equations, to generate estimates corresponding to different subsets of sensors. Such an architecture can reduce the memory usage of the observer from an exponential to a linear function of the number of sensors. We then develop an efficient SMT-based decision procedure that is able to reason about the estimates of the MML observer to detect at runtime which sets of sensors are attack-free, and use them to obtain a correct state estimate. Finally, we discuss two optimization-based algorithms that can efficiently select the observer parameters with the goal of minimizing the sensitivity of the estimates with respect to sensor noise. We provide proofs of convergence for our estimation algorithm and report simulation results to compare its runtime performance with alternative techniques. We show that our algorithm scales well for large systems (including up to 5,000 sensors) for which many previously proposed algorithms are not implementable due to excessive memory and time requirements. Finally, we illustrate the effectiveness of our approach, both in terms of resiliency to attacks and robustness to noise, on the design of large-scale power distribution networks.Keywords
Funding Information
- ExCAPE: Expeditions in Computer Augmented Program Engineering (1138996 and 1139138)
- MARCO
- NSF (CNS-1136174, CNS-1329650, and ECCS-1608880)
- DARPA (FA8750-12-2-0247)
This publication has 19 references indexed in Scilit:
- A Platform-Based Design Methodology With Contracts and Related Tools for the Design of Cyber-Physical SystemsProceedings of the IEEE, 2015
- Finite data-rate feedback stabilization of switched and hybrid linear systemsAutomatica, 2014
- Secure Estimation and Control for Cyber-Physical Systems Under Adversarial AttacksIEEE Transactions on Automatic Control, 2014
- Attack Detection and Identification in Cyber-Physical SystemsIEEE Transactions on Automatic Control, 2013
- Non-invasive Spoofing Attacks for Anti-lock Braking Systems2013
- A Decoupled Feedback Structure for Covertly Appropriating Networked Control SystemsIFAC Proceedings Volumes, 2011
- Boolean satisfiability from theoretical hardness to practical successCommunications of the ACM, 2009
- Minimal state-space realization in linear system theory: an overviewJournal of Computational and Applied Mathematics, 2000
- A cone complementarity linearization algorithm for static output-feedback and related problemsIEEE Transactions on Automatic Control, 1997
- On the discrete-time bounded real Lemma with application in the characterization of static state feedback controllersSystems & Control Letters, 1992