Untangling Coordinated Ranging and Anchor Attacks with Rigidity for Secure Localization
Accurate localization is a critical enabling technology for context awareness in the Internet of Things. As localization plays an increasingly safety-critical role in applications, engineers must have confidence in the validity of location data. In this paper 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, and prove GORDIAN's lazy SMT solving design is a sound and complete algorithm for attack detection over a class of attack tolerant input. We empirically show in simulation GORDIAN's novel trilateration counterexample generation procedure enables rapid attack detection even for combinatorially difficult problems.