{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:33:37Z","timestamp":1767339217799,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T00:00:00Z","timestamp":1592438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000028","name":"Semiconductor Research Corporation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000028","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Singapore-Berkeley Building Efficiency and Sustainability in the Tropics"},{"DOI":"10.13039\/100018146","name":"Denso","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018146","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000010","name":"Ford","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000010","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Industrial Cyber-Physical Systems Research Center"},{"DOI":"10.13039\/501100004405","name":"Toyota","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004405","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["#1845194"],"award-info":[{"award-number":["#1845194"]}]},{"name":"TerraSwarm Research Center"},{"DOI":"10.13039\/100007245","name":"MARCO","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007245","id-type":"DOI","asserted-by":"crossref"}]},{"name":"STARnet phase of the Focus Center Research Program"},{"name":"Siemens"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Cyber-Phys. Syst."],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>\n            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, G\n            <jats:sc>ordian<\/jats:sc>\n            , 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 G\n            <jats:sc>ordian<\/jats:sc>\n            to the noisy case where fewer guarantees are possible. In simulations generated from real-world sensor noise, we empirically show that G\n            <jats:sc>ordian<\/jats:sc>\n            \u2019s trilateration counterexample generation procedure enables rapid attack detection even for combinatorially difficult problems.\n          <\/jats:p>","DOI":"10.1145\/3386568","type":"journal-article","created":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T22:59:32Z","timestamp":1592521172000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Gordian"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7798-9844","authenticated-orcid":false,"given":"Matthew","family":"Weber","sequence":"first","affiliation":[{"name":"University of California, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baihong","family":"Jin","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gil","family":"Lederman","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasser","family":"Shoukry","sequence":"additional","affiliation":[{"name":"University of California, Irvine, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edward A.","family":"Lee","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjit","family":"Seshia","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Sangiovanni-Vincentelli","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0805002"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/100792366"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2006.877401"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/984622.984630"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1498470"},{"volume-title":"Proceedings of the 16th ACM\/IEEE International Conference on Information Processing in Sensor Networks (IPSN\u201917)","author":"Franco Carmelo Di","key":"e_1_2_1_6_1","unstructured":"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\u201917) . ACM Press, 235--246. DOI:https:\/\/doi.org\/10.1145\/3055031.3055091 10.1145\/3055031.3055091 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\u201917). ACM Press, 235--246. DOI:https:\/\/doi.org\/10.1145\/3055031.3055091"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies","volume":"4","author":"Eren Tolga","unstructured":"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. 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."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2303233"},{"key":"e_1_2_1_9_1","volume-title":"Zavlanos","author":"Freundlich Charles","year":"2017","unstructured":"Charles Freundlich , Soomin Lee , and Michael M . Zavlanos . 2017 . Distributed active state estimation with user-specified accuracy. Arxiv :1706.01576 [cs] (June 2017). Charles Freundlich, Soomin Lee, and Michael M. Zavlanos. 2017. Distributed active state estimation with user-specified accuracy. Arxiv:1706.01576 [cs] (June 2017)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1353\/ajm.0.0132"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/938985.938995"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/WPNC.2009.4907834"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the ION GNSS International Technical Meeting of the Satellite Division","volume":"55","author":"Humphreys Todd E.","year":"2008","unstructured":"Todd E. Humphreys , Brent M. Ledvina , Mark L. Psiaki , Brady W. O\u2019Hanlon , 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_iongnss 2008 .pdf. Todd E. Humphreys, Brent M. Ledvina, Mark L. Psiaki, Brady W. O\u2019Hanlon, 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."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/TRO.2011.2114734","article-title":"Multirobot active target tracking with combinations of relative observations","volume":"27","author":"Zhou Ke","year":"2011","unstructured":"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. DOI:https:\/\/doi.org\/10.1109\/TRO.2011.2114734 10.1109\/TRO.2011.2114734 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. DOI:https:\/\/doi.org\/10.1109\/TRO.2011.2114734","journal-title":"IEEE Trans. Rob."},{"volume-title":"SurePoint: Exploiting ultra wideband flooding and diversity to provide robust, scalable, high-fidelity indoor localization","author":"Kempke Benjamin","key":"e_1_2_1_16_1","unstructured":"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. DOI:https:\/\/doi.org\/10.1145\/2994551.2994570 10.1145\/2994551.2994570 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. DOI:https:\/\/doi.org\/10.1145\/2994551.2994570"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289565"},{"key":"e_1_2_1_18_1","volume-title":"Dilution of precision. GPS WORLD","author":"Langley Richard B.","year":"1999","unstructured":"Richard B. Langley . 1999. Dilution of precision. GPS WORLD ( 1999 ). https:\/\/www.semanticscholar.org\/paper\/Dilution-of-Precision-Langley\/c04cd3dc971734ebe2ba1aa113e417e8b28b248c. Richard B. Langley. 1999. Dilution of precision. GPS WORLD (1999). https:\/\/www.semanticscholar.org\/paper\/Dilution-of-Precision-Langley\/c04cd3dc971734ebe2ba1aa113e417e8b28b248c."},{"key":"e_1_2_1_19_1","volume-title":"ALPS: A Bluetooth and ultrasound platform for mapping and localization","author":"Lazik Patrick","year":"2015","unstructured":"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. DOI:https:\/\/doi.org\/10.1145\/2809695.2809727 10.1145\/2809695.2809727 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. DOI:https:\/\/doi.org\/10.1145\/2809695.2809727"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1077391.1077395"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.3233\/SAT190075"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1147685.1147703"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2005.21"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1380564.1380570"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCC.2007.905750"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CACSD.2004.1393890"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031502"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2266831"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/345910.345917"},{"volume-title":"Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom\u201901)","author":"Savvides Andreas","key":"e_1_2_1_31_1","unstructured":"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\u201901) . 166\u2013179. https:\/\/doi.org\/10.1145\/381677.381693 10.1145\/381677.381693 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\u201901). 166\u2013179. https:\/\/doi.org\/10.1145\/381677.381693"},{"volume-title":"Embeddability of Weighted Graphs in K-space is Strongly NP-hard","author":"Saxe J. B.","key":"e_1_2_1_32_1","unstructured":"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. 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."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 13th International Workshop on Satisfiability Modulo Theories (SMT\u201915)","author":"Shoukry Yasser","year":"2015","unstructured":"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\u201915) . 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\u201915)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3049797.3049819"},{"key":"e_1_2_1_35_1","first-page":"2","article-title":"Theory of semidefinite programming for sensor network localization","volume":"109","author":"Man-Cho So Anthony","year":"2007","unstructured":"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. DOI:https:\/\/doi.org\/10.1007\/s10107-006-0040-1 10.1007\/s10107-006-0040-1 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. DOI:https:\/\/doi.org\/10.1007\/s10107-006-0040-1","journal-title":"Math. Prog."},{"key":"e_1_2_1_36_1","first-page":"4","article-title":"Algorithms for cooperative active localization of static targets with mobile bearing sensors under communication constraints","volume":"31","author":"Hook Joshua Vander","year":"2015","unstructured":"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. DOI:https:\/\/doi.org\/10.1109\/TRO.2015.2432612 10.1109\/TRO.2015.2432612 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. DOI:https:\/\/doi.org\/10.1109\/TRO.2015.2432612","journal-title":"IEEE Trans. Rob."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/060669395"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422966.2422983"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2012.2220790"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-010-0501-4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2008.197"}],"container-title":["ACM Transactions on Cyber-Physical Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386568","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3386568","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3386568","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:32:01Z","timestamp":1750195921000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386568"}},"subtitle":["Formal Reasoning-based Outlier Detection for Secure Localization"],"short-title":[],"issued":{"date-parts":[[2020,6,18]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3386568"],"URL":"https:\/\/doi.org\/10.1145\/3386568","relation":{},"ISSN":["2378-962X","2378-9638"],"issn-type":[{"type":"print","value":"2378-962X"},{"type":"electronic","value":"2378-9638"}],"subject":[],"published":{"date-parts":[[2020,6,18]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}