Untangling Coordinated Ranging and Anchor Attacks with Rigidity for Secure Localization

  • Authors:
    Matthew Weber (UC/Berkeley), Baihong Jin (UC/Berkeley), Gil Lederman (UC/Berkeley), Yasser Shoukry (UC/Berkeley), Edward A. Lee (UC/Berkeley), Sanjit Seshia (UC/Berkeley), Alberto Sangiovanni-Vincentelli (UC/Berkeley)
    Publication ID:
    Publication Type:
    Received Date:
    Last Edit Date:
    2386.003 (California Institute of Technology)


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.

4819 Emperor Blvd, Suite 300 Durham, NC 27703 Voice: (919) 941-9400 Fax: (919) 941-9450