Gordian: Formal Reasoning-based Outlier Detection for Secure Localization

Matthew Weber, Baihong Jin, Gil Lederman, Yasser Shoukry, Edward A Lee, Sanjit A. Seshia, and Alberto L. Sangiovanni-Vincentelli. Gordian: Formal Reasoning-based Outlier Detection for Secure Localization. ACM Transactions on Cyber-Physical Systems, 4(4), 2020.

Download

[HTML] 

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.

BibTeX

@article{weber-tcps20,
  author = {Matthew Weber and Baihong Jin and Gil Lederman and Yasser Shoukry and Edward A Lee and Sanjit A. Seshia and Alberto L. Sangiovanni-Vincentelli},
  title     = {Gordian: Formal Reasoning-based Outlier Detection for Secure Localization},
  journal   = {ACM Transactions on Cyber-Physical Systems},
  volume    = {4},
  number    = {4},
  OPTpages     = {},
  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.},
}

Generated by bib2html.pl (written by Patrick Riley ) on Sun Aug 30, 2020 00:36:48