Gordian: Formal Reasoning-Based Outlier Detection for Secure Localization
Author(s): Matthew Weber, Baihong Jin, Gil Lederman, Yasser Shoukry, Edward A Lee, Sanjit Seshia, and Alberto Sangiovanni-Vincentelli
Citation
Matthew Weber, Baihong Jin, Gil Lederman, Yasser Shoukry, Edward A Lee, Sanjit Seshia, and Alberto Sangiovanni-Vincentelli. "Gordian: Formal Reasoning-Based Outlier Detection for Secure Localization". ACM Transactions on Cyber-Physical Systems (TCPS), 4(4):43, June 2020.
Abstract
Accurate localization from Cyber-Physical Systems (CPS) is a critical enabling technology for context-aware applications and control. As localization plays an increasingly safety-critical role, location systems must be able to identify and eliminate faulty measurements to prevent dangerously inaccurate localization. In this article, we consider the range-based localization problem and propose a method to detect coordinated adversarial corruption on anchor positions and distance measurements. Our algorithm, Gordian, rapidly finds attacks by identifying geometric inconsistencies at the graph level without requiring assumptions about hardware, ranging mechanisms, or cryptographic protocols. We give necessary conditions for which attack detection is guaranteed to be successful in the noiseless case, and we use that intuition to extend Gordian to the noisy case where fewer guarantees are possible. In simulations generated from real-world sensor noise, we empirically show that Gordian’s trilateration counterexample generation procedure enables rapid attack detection even for combinatorially difficult problems.
Citation Formats
-
HTML
Matthew Weber, Baihong Jin, Gil Lederman, Yasser Shoukry, Edward A Lee, Sanjit Seshia, and Alberto Sangiovanni-Vincentelli. "<a href="https://www.icyphy.org/publications/2020_WeberEtAl/">Gordian: Formal Reasoning-Based Outlier Detection for Secure Localization</a>". <i>ACM Transactions on Cyber-Physical Systems (TCPS)</i>, 4(4):43, June 2020. -
Plain Text
Matthew Weber, Baihong Jin, Gil Lederman, Yasser Shoukry, Edward A Lee, Sanjit Seshia, and Alberto Sangiovanni-Vincentelli. "Gordian: Formal Reasoning-Based Outlier Detection for Secure Localization". ACM Transactions on Cyber-Physical Systems (TCPS), 4(4):43, June 2020. -
BibTeX
@article{WeberEtAl:20:Gordian, author = {Matthew Weber, Baihong Jin, Gil Lederman, Yasser Shoukry, Edward A Lee, Sanjit Seshia, and Alberto Sangiovanni-Vincentelli}, title = {Gordian: Formal Reasoning-Based Outlier Detection for Secure Localization},
journal = {ACM Transactions on Cyber-Physical Systems (TCPS)},
volume = {4},
number = {4},
pages = {43},
month = {June},
year = {2020},
abstract = {Accurate localization from Cyber-Physical Systems (CPS) is a critical enabling technology for context-aware applications and control. As localization plays an increasingly safety-critical role, location systems must be able to identify and eliminate faulty measurements to prevent dangerously inaccurate localization. In this article, we consider the range-based localization problem and propose a method to detect coordinated adversarial corruption on anchor positions and distance measurements. Our algorithm, Gordian, rapidly finds attacks by identifying geometric inconsistencies at the graph level without requiring assumptions about hardware, ranging mechanisms, or cryptographic protocols. We give necessary conditions for which attack detection is guaranteed to be successful in the noiseless case, and we use that intuition to extend Gordian to the noisy case where fewer guarantees are possible. In simulations generated from real-world sensor noise, we empirically show that Gordian’s trilateration counterexample generation procedure enables rapid attack detection even for combinatorially difficult problems.}, URL = {https://www.icyphy.org/publications/2020_WeberEtAl/} }