research-article

Open access

Gordian: Formal Reasoning-based Outlier Detection for Secure Localization

Authors:

Yasser Shoukry,

Alberto Sangiovanni-VincentelliAuthors Info & Claims

ACM Transactions on Cyber-Physical Systems, Volume 4, Issue 4

Article No.: 43, Pages 1 - 27

https://doi.org/10.1145/3386568

Published: 18 June 2020 Publication History

All formats PDF

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.

References

[1]

Farid Alizadeh. 1995. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 1 (Feb. 1995), 13--51.

[2]

Brian D. O. Anderson, Iman Shames, Guoqiang Mao, and BariÅ Fidan. 2010. Formal theory of noisy sensor network localization. SIAM J. Disc. Math. 24, 2 (Jan. 2010), 684--698.

Digital Library

[3]

P. Biswas, T. C. Liang, K. C. Toh, Y. Ye, and T. C. Wang. 2006. Semidefinite programming approaches for sensor network localization with noisy distance measurements. IEEE Trans. Automat. Sci. Eng. 3, 4 (Oct. 2006), 360--371.

[4]

Pratik Biswas and Yinyu Ye. 2004. Semidefinite programming for ad hoc wireless sensor network localization. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN’04). ACM Press, 46.

Digital Library

[5]

Srdjan Capkun and J.-P. Hubaux. 2005. Secure positioning of wireless devices with application to sensor networks. In Proceedings of the IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., Vol. 3. IEEE, 1917--1928.

[6]

Carmelo Di Franco, Amanda Prorok, Nikolay Atanasov, Benjamin Kempke, Prabal Dutta, Vijay Kumar, and George J. Pappas. 2017. Calibration-free network localization using non-line-of-sight ultra-wideband measurements. In Proceedings of the 16th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN’17). ACM Press, 235--246.

[7]

Tolga Eren, O. K. Goldenberg, Walter Whiteley, Yang Richard Yang, A. Stephen Morse, Brian D. O. Anderson, and Peter N. Belhumeur. 2004. Rigidity, computation, and randomization in network localization. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 4. IEEE, 2673--2684.

[8]

Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi. 2014. Secure estimation and control for cyber-physical systems under adversarial attacks. IEEE Trans. Automat. Control 59, 6 (June 2014), 1454--1467.

[9]

Charles Freundlich, Soomin Lee, and Michael M. Zavlanos. 2017. Distributed active state estimation with user-specified accuracy. Arxiv:1706.01576 [cs] (June 2017).

[10]

Steven J. Gortler, Alexander D. Healy, and Dylan P. Thurston. 2010. Characterizing generic global rigidity. Amer. J. Math. 132, 4 (2010), 897--939.

[11]

Tian He, Chengdu Huang, Brian M. Blum, John A. Stankovic, and Tarek Abdelzaher. 2003. Range-free localization schemes for large scale sensor networks. In Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. ACM, 81--95.

Digital Library

[12]

Ville Honkavirta, Tommi Perala, Simo Ali-Loytty, and Robert Piche. 2009. A comparative survey of WLAN location fingerprinting methods. In Proceedings of the 6th Workshop on Positioning, Navigation and Communication (WPNC’09). IEEE, 243--251.

[13]

Todd E. Humphreys, Brent M. Ledvina, Mark L. Psiaki, Brady W. O’Hanlon, and Paul M. Kintner Jr. 2008. Assessing the spoofing threat: Development of a portable GPS civilian spoofer. In Proceedings of the ION GNSS International Technical Meeting of the Satellite Division, Vol. 55. Retrieved from https://gps.mae.cornell.edu/humphreys_etal_iongnss2008.pdf.

[14]

Bill Jackson and Tibor Jordan. 2003. Connected Rigidity Matroids and Unique Realizations of Graphs. Technical Report. Eotvos University, Budapest, Hungary.

[15]

Ke Zhou and S. I. Roumeliotis. 2011. Multirobot active target tracking with combinations of relative observations. IEEE Trans. Rob. 27, 4 (Aug. 2011), 678--695.

[16]

Benjamin Kempke, Pat Pannuto, Bradford Campbell, and Prabal Dutta. 2016. SurePoint: Exploiting ultra wideband flooding and diversity to provide robust, scalable, high-fidelity indoor localization. ACM Press, 137--149.

[17]

J. B. Kruskal. 1964. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika 29, 1 (Mar. 1964), 1--27.

[18]

Richard B. Langley. 1999. Dilution of precision. GPS WORLD (1999). https://www.semanticscholar.org/paper/Dilution-of-Precision-Langley/c04cd3dc971734ebe2ba1aa113e417e8b28b248c.

[19]

Patrick Lazik, Niranjini Rajagopal, Oliver Shih, Bruno Sinopoli, and Anthony Rowe. 2015. ALPS: A Bluetooth and ultrasound platform for mapping and localization. ACM Press, 73--84.

[20]

Loukas Lazos and Radha Poovendran. 2005. SeRLoc: Robust localization for wireless sensor networks. ACM Trans. Sens. Netw. 1, 1 (2005), 73--100.

Digital Library

[21]

D. Le Berre and A. Parrain. 2010. The Sat4j library, release 2.2: System description. SAT 7, 2–3 (2010), 59–64.

[22]

Zang Li, Wade Trappe, Yanyong Zhang, and Badri Nath. 2005. Robust statistical methods for securing wireless localization in sensor networks. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks. IEEE Press, 12.

Digital Library

[23]

Donggang Liu, Peng Ning, and Wenliang Du. 2005. Detecting malicious beacon nodes for secure location discovery in wireless sensor networks. In Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS’05). IEEE, 609--619.

Digital Library

[24]

Donggang Liu, Peng Ning, An Liu, Cliff Wang, and Wenliang Kevin Du. 2008. Attack-resistant location estimation in wireless sensor networks. ACM Trans. Inf. Syst. Secur. 11, 4 (July 2008), 1--39.

Digital Library

[25]

Hui Liu, Houshang Darabi, Pat Banerjee, and Jing Liu. 2007. Survey of wireless indoor positioning techniques and systems. IEEE Trans. Syst., Man Cyber., Part C (Applic. Rev.) 37, 6 (Nov. 2007), 1067--1080.

Digital Library

[26]

Johan Löfberg. 2004. YALMIP: A toolbox for modeling and optimization in MATLAB. In Proceedings of the IEEE International Symposium on Computer Aided Control Systems Design. IEEE, 284--289.

[27]

David Moore, John Leonard, Daniela Rus, and Seth Teller. 2004. Robust distributed network localization with noisy range measurements. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems. ACM, 50--61.

Digital Library

[28]

Mosek. 2011. MOSEK Related Publications. Technical Report. Retrieved from https://download.mosek.com/docs/reports/publications.pdf.

[29]

Fabio Pasqualetti, Florian Dorfler, and Francesco Bullo. 2013. Attack detection and identification in cyber-physical systems. IEEE Trans. Automat. Control 58, 11 (Nov. 2013), 2715--2729.

[30]

Nissanka B. Priyantha, Anit Chakraborty, and Hari Balakrishnan. 2000. The cricket location-support system. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. 32--43.

Digital Library

[31]

Andreas Savvides, Chih-Chieh Han, and Mani B. Srivastava. 2001. Dynamic fine-grained localization in ad-hoc wireless sensor networks. In Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom’01). 166–179. https://doi.org/10.1145/381677.381693

[32]

J. B. Saxe. 1979. Embeddability of Weighted Graphs in K-space is Strongly NP-hard. Carnegie-Mellon University, Dept. of Computer Science. https://books.google.com/books/about/Embeddability_of_Weighted_Graphs_in_K_sp.html?id=vClAGwAACAAJ.

[33]

Yasser Shoukry, Pierluigi Nuzzo, Alberto Puggelli, Alberto L. Sangiovanni-Vincentelli, Sanjit A. Seshia, Mani Srivastava, and Paulo Tabuada. 2015. IMHOTEP-SMT: A satisfiability modulo theory solver for secure state estimation. In Proceedings of the 13th International Workshop on Satisfiability Modulo Theories (SMT’15).

[34]

Yasser Shoukry, Pierluigi Nuzzo, Alberto Sangiovanni-Vincentelli, Sanjit A. Seshia, George J. Pappas, and Paulo Tabuada. 2017. SMC: Satisfiability modulo convex optimization. In Proceedings of the 10th International Conference on Hybrid Systems: Computation and Control (HSCC’17).

Digital Library

[35]

Anthony Man-Cho So and Yinyu Ye. 2007. Theory of semidefinite programming for sensor network localization. Math. Prog. 109, 2--3 (Jan. 2007), 367--384.

[36]

Joshua Vander Hook, Pratap Tokekar, and Volkan Isler. 2015. Algorithms for cooperative active localization of static targets with mobile bearing sensors under communication constraints. IEEE Trans. Rob. 31, 4 (Aug. 2015), 864--876.

[37]

Zizhuo Wang, Song Zheng, Yinyu Ye, and Stephen Boyd. 2008. Further relaxations of the semidefinite programming approach to sensor network localization. SIAM J. Optim. 19, 2 (Jan. 2008), 655--673.

Digital Library

[38]

Zheng Yang, Lirong Jian, Chenshu Wu, and Yunhao Liu. 2013a. Beyond triangle inequality: Sifting noisy and outlier distance measurements for localization. ACM Trans. Sens. Netw. 9, 2 (Mar. 2013), 1--20.

Digital Library

[39]

Zheng Yang, Chenshu Wu, Tao Chen, Yiyang Zhao, Wei Gong, and Yunhao Liu. 2013b. Detecting outlier measurements based on graph rigidity for wireless sensor network localization. IEEE Trans. Vehic. Technol. 62, 1 (Jan. 2013), 374--383.

[40]

Yingpei Zeng, Jiannong Cao, Jue Hong, Shigeng Zhang, and Li Xie. 2013. Secure localization and location verification in wireless sensor networks: a survey. J. Supercomput. 64, 3 (June 2013), 685--701.

Digital Library

[41]

Sheng Zhong, Murtuza Jadliwala, Shambhu Upadhyaya, and Chunming Qiao. 2008. Towards a theory of robust localization against malicious beacon nodes. In Proceedings of the 27th Conference on Computer Communications. IEEE, 1391--1399. Retrieved from http://ieeexplore.ieee.org/abstract/document/4509792/.

Cited By

Shi CYang G(2024)Bearing-Based Reliable Cooperative Localization for Multiagent Networks in the Presence of Malicious MeasurementsIEEE Transactions on Automatic Control10.1109/TAC.2023.330739169:6(3560-3575)Online publication date: Jun-2024
https://doi.org/10.1109/TAC.2023.3307391
Wardega Kvon Hippel MTron RNita-Rotaru CLi WAgmon NAn BRicci AYeoh W(2023)Byzantine Resilience at Swarm Scale: A Decentralized Blocklist Protocol from Inter-robot AccusationsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598795(1430-1438)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598795
Khojasteh MSaucan ALiu ZConti AWin M(2023)Location Secrecy Enhancement in Adversarial Networks via Trajectory ControlIEEE Control Systems Letters10.1109/LCSYS.2022.31899607(601-606)Online publication date: 2023
https://doi.org/10.1109/LCSYS.2022.3189960
Show More Cited By

Index Terms

Gordian: Formal Reasoning-based Outlier Detection for Secure Localization
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
    1. Reliability
  2. Embedded and cyber-physical systems
    1. Sensor networks

Recommendations

Toward attack-resistant localization under infrastructure attacks

Trustworthy location information is important because it is a critical input to a wide variety of location-based applications. However, the localization infrastructure is vulnerable to physical attacks, and consequently, the localization results are ...
SeRLoc: secure range-independent localization for wireless sensor networks
WiSe '04: Proceedings of the 3rd ACM workshop on Wireless security

In many applications of wireless sensor networks (WSN), sensors are deployed un-tethered in hostile environments. For location-aware WSN applications, it is essential to ensure that sensors can determine their location, even in the presence of malicious ...
SeRLoc: Robust localization for wireless sensor networks

Many distributed monitoring applications of Wireless Sensor Networks (WSNs) require the location information of a sensor node. In this article, we address the problem of enabling nodes of Wireless Sensor Networks to determine their location in an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Cyber-Physical Systems

ACM Transactions on Cyber-Physical Systems Volume 4, Issue 4

Special Issue on Self-Awareness in Resource Constrained CPS and Regular Papers

October 2020

293 pages

ISSN:2378-962X

EISSN:2378-9638

DOI:10.1145/3407233

Editor:
Tei-Wei Kuo
City University of Hong Kong and National Taiwan University, Taiwan

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 18 June 2020

Online AM: 07 May 2020

Accepted: 01 January 2020

Revised: 01 August 2019

Received: 01 June 2018

Published in TCPS Volume 4, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Semiconductor Research Corporation
DARPA
Singapore-Berkeley Building Efficiency and Sustainability in the Tropics (SinBerBEST)
Denso
Ford
Industrial Cyber-Physical Systems Research Center (iCyPhy)
Toyota
NSF
TerraSwarm Research Center
MARCO
STARnet phase of the Focus Center Research Program (FCRP)
Siemens

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
410
Total Downloads

Downloads (Last 12 months)148
Downloads (Last 6 weeks)16

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shi CYang G(2024)Bearing-Based Reliable Cooperative Localization for Multiagent Networks in the Presence of Malicious MeasurementsIEEE Transactions on Automatic Control10.1109/TAC.2023.330739169:6(3560-3575)Online publication date: Jun-2024
https://doi.org/10.1109/TAC.2023.3307391
Wardega Kvon Hippel MTron RNita-Rotaru CLi WAgmon NAn BRicci AYeoh W(2023)Byzantine Resilience at Swarm Scale: A Decentralized Blocklist Protocol from Inter-robot AccusationsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598795(1430-1438)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598795
Khojasteh MSaucan ALiu ZConti AWin M(2023)Location Secrecy Enhancement in Adversarial Networks via Trajectory ControlIEEE Control Systems Letters10.1109/LCSYS.2022.31899607(601-606)Online publication date: 2023
https://doi.org/10.1109/LCSYS.2022.3189960
Yuan YHuang YYuan Y(2023)PrSLoc: Sybil attack detection for localization with private observers using differential privacyComputers & Security10.1016/j.cose.2023.103289131(103289)Online publication date: Aug-2023
https://doi.org/10.1016/j.cose.2023.103289
Bakirtzis GGenovese FFleming C(2022)Yoneda Hacking: The Algebra of Attacker ActionsACM Transactions on Cyber-Physical Systems10.1145/35310636:3(1-27)Online publication date: 7-Sep-2022
https://dl.acm.org/doi/10.1145/3531063
Weber MLee E(2021)Semantic Localization for IoTSemantic IoT: Theory and Applications10.1007/978-3-030-64619-6_16(365-383)Online publication date: 13-Apr-2021
https://doi.org/10.1007/978-3-030-64619-6_16

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents