Matthew Weber and Baihong Jin and Gil Lederman and Yasser Shoukry and Edward A. Lee and Sanjit A. Seshia and Alberto L. Sangiovanni-Vincentelli

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2017-5

March 17, 2017

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-5.pdf

Accurate localization is a critical enabling technology for sensor networks and 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 sensor network localization problem with noisy distance measurements and propose a method to detect adversarially corrupted values. Our algorithm,Gordian SMT, rapidly finds attacks on distance measurements by identifying geometric inconsistencies at the graph level without requiring assumptions about hardware, ranging mechanisms or cryptographic protocols. We give the necessary and sufficient conditions for which attack detection is guaranteed to be possible in the noiseless case, and present Gordian SMT as a sound and complete algorithm for well-posed noiseless input. We extend Gordian SMT to the case of noisy measurements where our empirical analysis shows good performance at a run-time several orders of magnitude faster than the naive brute force algorithm.

---

BibTeX citation:

@techreport{Weber:EECS-2017-5,
    Author= {Weber, Matthew and Jin, Baihong and Lederman, Gil and Shoukry, Yasser and Lee, Edward A. and Seshia, Sanjit A. and Sangiovanni-Vincentelli, Alberto L.},
    Title= {Gordian SMT: Untangling Ranging Attacks in Noisy Sensor Networks for Secure Localization},
    Year= {2017},
    Month= {Mar},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-5.html},
    Number= {UCB/EECS-2017-5},
    Abstract= {Accurate localization is a critical enabling technology for sensor networks and 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 sensor network localization problem with noisy distance measurements and propose a method to detect adversarially corrupted values. Our algorithm,Gordian SMT, rapidly finds attacks on distance measurements by identifying geometric inconsistencies at the graph level without requiring assumptions about hardware, ranging mechanisms or cryptographic protocols. We give the necessary and sufficient conditions for which attack detection is guaranteed to be possible in the noiseless case, and present Gordian SMT as a sound and complete algorithm for well-posed noiseless input. We extend Gordian SMT to the case of noisy measurements where our empirical analysis shows good performance at a run-time several orders of magnitude faster than the naive brute force algorithm.},
}

EndNote citation:

%0 Report
%A Weber, Matthew 
%A Jin, Baihong 
%A Lederman, Gil 
%A Shoukry, Yasser 
%A Lee, Edward A. 
%A Seshia, Sanjit A. 
%A Sangiovanni-Vincentelli, Alberto L. 
%T Gordian SMT: Untangling Ranging Attacks in Noisy Sensor Networks for Secure Localization
%I EECS Department, University of California, Berkeley
%D 2017
%8 March 17
%@ UCB/EECS-2017-5
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-5.html
%F Weber:EECS-2017-5