{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T22:54:40Z","timestamp":1740178480629,"version":"3.37.3"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,1,3]],"date-time":"2019-01-03T00:00:00Z","timestamp":1546473600000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ExCAPE: Expeditions in Computer Augmented Program Engineering","award":["1138996 and 1139138"]},{"DOI":"10.13039\/100007245","name":"MARCO","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007245","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-1136174, CNS-1329650, and ECCS-1608880"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","award":["FA8750-12-2-0247"],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Cyber-Phys. Syst."],"published-print":{"date-parts":[[2018,1,31]]},"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.<\/jats:p>","DOI":"10.1145\/3078621","type":"journal-article","created":{"date-parts":[[2018,1,4]],"date-time":"2018-01-04T16:27:31Z","timestamp":1515083251000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["SMT-Based Observer Design for Cyber-Physical Systems under Sensor Attacks"],"prefix":"10.1145","volume":"2","author":[{"given":"Yasser","family":"Shoukry","sequence":"first","affiliation":[{"name":"UC Berkeley and UC Los Angeles, USA"}]},{"given":"Michelle","family":"Chong","sequence":"additional","affiliation":[{"name":"Lund University, Sweden"}]},{"given":"Masashi","family":"Wakaiki","sequence":"additional","affiliation":[{"name":"Kobe University, Japan"}]},{"given":"Pierluigi","family":"Nuzzo","sequence":"additional","affiliation":[{"name":"University of Southern California, USA"}]},{"given":"Alberto","family":"Sangiovanni-Vincentelli","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}]},{"given":"Sanjit A.","family":"Seshia","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}]},{"given":"JO\u00c3o P.","family":"Hespanha","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, USA"}]},{"given":"Paulo","family":"Tabuada","sequence":"additional","affiliation":[{"name":"University of California at Los Angeles, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.3233\/SAT190075"},{"volume-title":"American Control Conference (ACC\u201915)","author":"Chong M. S.","key":"e_1_2_1_2_1","unstructured":"M. S. Chong , M. Wakaiki , and J. P. Hespanha . 2014. Observability of linear systems under adversarial attacks . In American Control Conference (ACC\u201915) . 2439--2444. M. S. Chong, M. Wakaiki, and J. P. Hespanha. 2014. Observability of linear systems under adversarial attacks. In American Control Conference (ACC\u201915). 2439--2444."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00341-1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6911(92)90108-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.618250"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2011.2161300"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2303233"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2011.67"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2013.11.037"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653662.1653666"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536616.1536637"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2010.936020"},{"volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT).","author":"Mishra S.","key":"e_1_2_1_13_1","unstructured":"S. Mishra , Y. Shoukry , N. Karamchandani , S. Diggavi , and P. Tabuada . 2015. Secure state estimation: Optimal guarantees against sensor attacks in the presence of noise . In Proceedings of the IEEE International Symposium on Information Theory (ISIT). S. Mishra, Y. Shoukry, N. Karamchandani, S. Diggavi, and P. Tabuada. 2015. Secure state estimation: Optimal guarantees against sensor attacks in the presence of noise. In Proceedings of the IEEE International Symposium on Information Theory (ISIT)."},{"volume-title":"Proceedings of the 34th Chinese Control Conference (CCC). 4761--4766","author":"Mo Y.","key":"e_1_2_1_14_1","unstructured":"Y. Mo and R. M. Murray . 2015. Multi-dimensional state estimation in adversarial environment . In Proceedings of the 34th Chinese Control Conference (CCC). 4761--4766 . Y. Mo and R. M. Murray. 2015. Multi-dimensional state estimation in adversarial environment. In Proceedings of the 34th Chinese Control Conference (CCC). 4761--4766."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2015.2453253"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCPS.2014.6843720"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2266831"},{"volume-title":"Proceedings of the International Conference on Cyber-Physical Systems. IEEE, 1--10","author":"Shoukry Y.","key":"e_1_2_1_18_1","unstructured":"Y. Shoukry , M. Chong , M. Wakaiki , P. Nuzzo , A. L. Sangiovanni-Vincentelli , S. A. Seshia , J. P. Hespanha , and P. Tabuada . 2016. SMT-Based observer design for cyber-physical systems under sensor attacks . In Proceedings of the International Conference on Cyber-Physical Systems. IEEE, 1--10 . Y. Shoukry, M. Chong, M. Wakaiki, P. Nuzzo, A. L. Sangiovanni-Vincentelli, S. A. Seshia, J. P. Hespanha, and P. Tabuada. 2016. SMT-Based observer design for cyber-physical systems under sensor attacks. In Proceedings of the International Conference on Cyber-Physical Systems. IEEE, 1--10."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40349-1_4"},{"key":"e_1_2_1_20_1","unstructured":"Y. Shoukry P. Nuzzo A. Puggelli A. L. Sangiovanni-Vincentelli S. A. Seshia and P. Tabuada. 2014. Secure state estimation under sensor attacks: A satisfiability modulo theory approach. (2014). arXiv:math.OC\/1412.4324 {online} http:\/\/arxiv.org\/abs\/1412.4324. Y. Shoukry P. Nuzzo A. Puggelli A. L. Sangiovanni-Vincentelli S. A. Seshia and P. Tabuada. 2014. Secure state estimation under sensor attacks: A satisfiability modulo theory approach. (2014). arXiv:math.OC\/1412.4324 {online} http:\/\/arxiv.org\/abs\/1412.4324."},{"volume-title":"Proceedings of the IEEE American Control Conference. 3818--3823","author":"Shoukry Y.","key":"e_1_2_1_21_1","unstructured":"Y. Shoukry , A. Puggelli , P. Nuzzo , A. L. Sangiovanni-Vincentelli , S. A. Seshia , and P. Tabuada . 2015. Sound and complete state estimation for linear dynamical systems under sensor attack using satisfiability modulo theory solving . In Proceedings of the IEEE American Control Conference. 3818--3823 . Y. Shoukry, A. Puggelli, P. Nuzzo, A. L. Sangiovanni-Vincentelli, S. A. Seshia, and P. Tabuada. 2015. Sound and complete state estimation for linear dynamical systems under sensor attack using satisfiability modulo theory solving. In Proceedings of the IEEE American Control Conference. 3818--3823."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2015.2492159"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.3182\/20110828-6-IT-1002.01721"},{"key":"e_1_2_1_24_1","first-page":"1","article-title":"Secure control systems: A quantitative risk management approach","volume":"35","author":"Teixeira A.","year":"2015","unstructured":"A. Teixeira , Kin Cheong Sou , H. Sandberg , and K. H. Johansson . 2015 . Secure control systems: A quantitative risk management approach . IEEE Control Systems Magazine 35 , 1 (Feb. 2015), 24--45. A. Teixeira, Kin Cheong Sou, H. Sandberg, and K. H. Johansson. 2015. Secure control systems: A quantitative risk management approach. IEEE Control Systems Magazine 35, 1 (Feb. 2015), 24--45.","journal-title":"IEEE Control Systems Magazine"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2015.7403027"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2011.6161031"}],"container-title":["ACM Transactions on Cyber-Physical Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3078621","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3078621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T07:32:10Z","timestamp":1672471930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3078621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,3]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1,31]]}},"alternative-id":["10.1145\/3078621"],"URL":"https:\/\/doi.org\/10.1145\/3078621","relation":{},"ISSN":["2378-962X","2378-9638"],"issn-type":[{"type":"print","value":"2378-962X"},{"type":"electronic","value":"2378-9638"}],"subject":[],"published":{"date-parts":[[2018,1,3]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}