Article

Preserving privacy in gps traces via uncertainty-aware path cloaking

Authors:

Marco Gruteser,

Ansaf AlrabadyAuthors Info & Claims

CCS '07: Proceedings of the 14th ACM conference on Computer and communications security

Pages 161 - 171

https://doi.org/10.1145/1315245.1315266

Published: 28 October 2007 Publication History

Abstract

Motivated by a probe-vehicle based automotive traffic monitoring system, this paper considers the problem of guaranteed anonymity in a dataset of location traces while maintaining high data accuracy. We find through analysis of a set of GPS traces from 233 vehicles that known privacy algorithms cannot meet accuracy requirements or fail to provide privacy guarantees for drivers in low-density areas. To overcome these challenges, we develop a novel time-to-confusion criterion to characterize privacy in a location dataset and propose an uncertainty-aware path cloaking algorithm that hides location samples in a dataset to provide a time-to-confusion guarantee for all vehicles. We show that this approach effectively guarantees worst case tracking bounds, while achieving significant data accuracy improvements.

References

[1]

TeleNav. http://www.telenav.net/, 2004.

[2]

Inrix. http://www.inrix.com/, 2006.

[3]

Intellione. http://www.intellione.com/, 2006.

[4]

D. Agrawal and C. C. Aggarwal. On the design and quantification of privacy preserving data mining algorithms. In Symposium on Principles of Database Systems, 2001.

Digital Library

[5]

R. Agrawal and R. Srikant. Privacy-preserving data mining. In Proc. of the ACM SIGMOD Conference on Management of Data, pages 439--450. ACM Press, May 2000.

Digital Library

[6]

A. Beresford and F. Stajano. Location privacy in pervasive computing. IEEE Pervasive Computing, 2(1):46--55, 2003.

Digital Library

[7]

A. Beresford and F. Stajano. Mix zones: User privacy in location-aware services. In IEEE PerSec, 2004.

Digital Library

[8]

C. Bettini, X. SeanWang, and S. Jajodia. Protecting privacy against location-based personal identification. In 2nd VLDB Workshop SDM, 2005.

Digital Library

[9]

R. Cayford and T. Johnson. Operational parameters affecting use of anonymous cell phone tracking for generating traffic information. Institute of transportation studies for the 82th TRB Annual Meeting, 1(3):03--3865, Jan 2003.

[10]

D. Chaum. Untraceable electronic, mail return addresses, and digital pseudonyms. Communications of the ACM, 1981.

Digital Library

[11]

A. Civilis and S. Pakalnis. Techniques for efficient road-network-based tracking of moving objects. IEEE TKDE, 17(5):698--712, 2005. Senior Member-Christian S. Jensen.

Digital Library

[12]

T. M. Cover and J. A. Thomas. Elements of information theory. Wiley-Interscience, New York, NY, USA, 1991.

Digital Library

[13]

L. Cranor, M. Langheinrich, M. Marchiori, and J. Reagle. The platform for privacy preferences 1.0 (p3p1.0) specification. W3C Recommendation, Apr. 2002.

[14]

X. Dai, M. Ferman, and R. Roesser. A simulation evaluation of a real-time traffic information system using probe vehicles. In Proceedings of the IEEE Intelligent Transportation Systems, pages 475--480, 2003.

[15]

J. Deng, R. Han, and S. Mishra. Countermeasures against traffic analysis attacks in wireless sensor networks. In Proceedings of the IEEE/Create-Net SecureComm, Athens, Greece, September 2005.

Digital Library

[16]

C. Diaz, S. Seys, J. Claessens, and B. Preneel. Towards measuring anonymity. In 2nd Workshop on Privacy Enhancing Technologies, 2002.

Digital Library

[17]

R. Dingledine, N. Mathewson, and P. F. Syverson. Tor: The second-generation onion router. In USENIX Security Symposium, pages 303--320, 2004.

Digital Library

[18]

A. Escudero-Pascual, T. Holleboom, and S. Fischer-Hubner. Privacy of location data in mobile networks. In Proceedings of the 7th Nordic Workshop on Secure IT Systems (Nordsec 2002), 2002.

[19]

H. Federrath, A. Jerichow, and A. Pfitzmann. Mixes in mobile communication systems: Location management with privacy. In Proceedings of the First International Workshop on Information Hiding, pages 121--135, London, UK, 1996. Springer-Verlag.

Digital Library

[20]

M. Ferman, D. Blumenfeld, and X. Dai. A simple analytical model of a probe-based traffic information system. In Proceedings of the IEEE Intelligent Transportation Systems, pages 263--268, 2003.

[21]

A. Gal and V. Atluri. An authorization model for temporal data. In Proceedings of the 7th ACM CCS, pages 144--153, New York, NY, USA, 2000. ACM Press.

Digital Library

[22]

B. Gedik and L. Liu. Location privacy in mobile systems: A personalized anonymization model. In Proceedings of the 25th IEEE ICDCS 2005, pages 620--629, Washington, DC, USA, 2005.

Digital Library

[23]

D. Goldschlag, M. Reed, and P. Syverson. Onion routing for anonymous and private internet connections. Communications of the ACM (USA), 42(2):39--41, 1999.

Digital Library

[24]

M. Gruteser and D. Grunwald. Anonymous usage of location-based services through spatial and temporal cloaking. In Proceedings of the ACM MobiSys, 2003.

Digital Library

[25]

M. Gruteser and D. Grunwald. Enhancing location privacy in wireless lan through disposable interface identifiers: a quantitative analysis. In Proceedings of the 1st ACM WMASH, pages 46--55. ACM Press, 2003.

Digital Library

[26]

M. Gruteser and B. Hoh. On the anonymity of periodic location samples. In Proceedings of the Second International Conference on Security in Pervasive Computing, 2005.

Digital Library

[27]

B. Hoh and M. Gruteser. Protecting location privacy through path confusion. In Proceedings of IEEE/Create-Net SecureComm, Athens, Greece, September 2005.

Digital Library

[28]

B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady. Enhancing security and privacy in traffic-monitoring systems. IEEE Pervasive Computing, 5(4):38--46, 2006.

Digital Library

[29]

Y.-C. Hu and H. J. Wang. Location privacy in wireless networks. In Proceedings of the ACM SIGCOMM Asia Workshop 2005, April 2005.

[30]

B. Hull, V. Bychkovsky, Y. Zhang, K. Chen, M. Goraczko, A. K. Miu, E. Shih, H. Balakrishnan, and S. Madden. CarTel: A Distributed Mobile Sensor Computing System. In 4th ACM SenSys, Boulder, CO, November 2006.

Digital Library

[31]

T. Jiang, H. Wang, and Y.-C. Hu. Preserving location privacy in wireless lans. In Proceedings of the 5th ACM MobiSys, New York, NY, USA, 2007. ACM Press.

Digital Library

[32]

P. Kamat, Y. Zhang, W. Trappe, and C. Ozturk. Enhancing source-location privacy in sensor network routing. In Proceedings of the 25th IEEE ICDCS '05, pages 599--608, Washington, DC, USA, 2005.

Digital Library

[33]

H. Kargupta, S. Datta, Q. Wang, and K. Sivakumar. Random data perturbation techniques and privacy preserving data mining. In IEEE ICDM. IEEE Press, 2003.

[34]

J. Krumm. Inference attacks on location tracks. In Proceedings of the Pervasive 2007, May 2007.

Digital Library

[35]

J. Krumm and E. Horvitz. Predestination: Inferring destinations from partial trajectories. In Ubicomp, pages 243--260, 2006.

Digital Library

[36]

M. Li, K. Sampigethaya, L. Huang, and R. Poovendran. Swing & swap: user-centric approaches towards maximizing location privacy. In Proceedings of the 5th ACM WPES '06, pages 19--28, New York, NY, USA, 2006. ACM Press.

Digital Library

[37]

M. F. Mokbel, C.-Y. Chow, and W. G. Aref. The new casper: query processing for location services without compromising privacy. In Proceedings of the 32nd VLDB '2006, pages 763--774. VLDB Endowment, 2006.

Digital Library

[38]

P. Samarati and L. Sweeney. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. In Proceedings of IEEE Symposium on Research in Security and Privacy, 1998.

[39]

K. Sampigethaya, L. Huang, M. Li, R. Poovendran, K. Matsuura, and K. Sezaki. Caravan: Providing location privacy for vanet. In 3rd workshop on Embedded Security in Cars (ESCAR 2005), 2005.

[40]

A. Serjantov and G. Danezis. Towards an information theoretic metric for anonymity. In 2nd Workshop on Privacy Enhancing Technologies, 2002.

Digital Library

[41]

E. Snekkenes. Concepts for personal location privacy policies. In EC '01: Proceedings of the 3rd ACM conference on Electronic Commerce, pages 48--57, New York, NY, USA, 2001. ACM Press.

Digital Library

[42]

L. Sweeney. Achieving k-Anonymity Privacy Protection Using Generalization and Suppression. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10(5):571--588, 2002.

Digital Library

[43]

K. P. Tang, P. Keyani, J. Fogarty, and J. I. Hong. Putting people in their place: an anonymous and privacy-sensitive approach to collecting sensed data in location-based applications. In Proceedings of CHI '06, pages 93--102, 2006.

Digital Library

[44]

J. M. Wozencraft and I. M. Jacobs. Principles of Communications Engineering. John Wiley & Sons Inc, 1966.

[45]

M. Youssef, V. Atluri, and N. R. Adam. Preserving mobile customer privacy: an access control system for moving objects and customer profiles. In Proceedings of the 6th MDM '05, pages 67--76, New York, NY, USA, 2005. ACM Press.

Digital Library

Cited By

Li JMoeini BNejati SSabetzadeh MMcCallen M(2024)A Lean Simulation Framework for Stress Testing IoT Cloud SystemsIEEE Transactions on Software Engineering10.1109/TSE.2024.3402157(1-24)Online publication date: 2024
https://doi.org/10.1109/TSE.2024.3402157
Zhang MWei EBerry RHuang J(2024)Age-Dependent Differential PrivacyIEEE Transactions on Information Theory10.1109/TIT.2023.334014770:2(1300-1319)Online publication date: Feb-2024
https://doi.org/10.1109/TIT.2023.3340147
Feng TZhang ZWong WSun SSikdar B(2024)A Framework for Tradeoff Between Location Privacy Preservation and Quality of Experience in Location Based ServicesIEEE Open Journal of Vehicular Technology10.1109/OJVT.2024.33641845(428-439)Online publication date: 2024
https://doi.org/10.1109/OJVT.2024.3364184
Show More Cited By

Index Terms

Preserving privacy in gps traces via uncertainty-aware path cloaking
1. Security and privacy
  1. Human and societal aspects of security and privacy
2. Social and professional topics
  1. Computing / technology policy
    1. Computer crime
    2. Privacy policies

Recommendations

Achieving Guaranteed Anonymity in GPS Traces via Uncertainty-Aware Path Cloaking

The integration of Global Positioning System (GPS) receivers and sensors into mobile devices has enabled collaborative sensing applications, which monitor the dynamics of environments through opportunistic collection of data from many users' devices. ...
Virtual trip lines for distributed privacy-preserving traffic monitoring
MobiSys '08: Proceedings of the 6th international conference on Mobile systems, applications, and services

Automotive traffic monitoring using probe vehicles with Global Positioning System receivers promises significant improvements in cost, coverage, and accuracy. Current approaches, however, raise privacy concerns because they require participants to ...
Enhancing Privacy and Accuracy in Probe Vehicle-Based Traffic Monitoring via Virtual Trip Lines

Traffic monitoring using probe vehicles with GPS receivers promises significant improvements in cost, coverage, and accuracy over dedicated infrastructure systems. Current approaches, however, raise privacy concerns because they require participants to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '07: Proceedings of the 14th ACM conference on Computer and communications security

October 2007

628 pages

ISBN:9781595937032

DOI:10.1145/1315245

General Chair:
Peng Ning
NC State University, USA
,
Program Chairs:
Sabrina De Capitani di Vimercati
University of Milan, Italy
,
Paul Syverson
Naval Research Laboratory, USA

Copyright © 2007 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 ACM 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CCS07

Sponsor:

CCS07: 14th ACM Conference on Computer and Communications Security 2007

November 2 - October 31, 2007

Virginia, Alexandria, USA

Acceptance Rates

CCS '07 Paper Acceptance Rate 55 of 302 submissions, 18%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

224
Total Citations
View Citations
2,091
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)6

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li JMoeini BNejati SSabetzadeh MMcCallen M(2024)A Lean Simulation Framework for Stress Testing IoT Cloud SystemsIEEE Transactions on Software Engineering10.1109/TSE.2024.3402157(1-24)Online publication date: 2024
https://doi.org/10.1109/TSE.2024.3402157
Zhang MWei EBerry RHuang J(2024)Age-Dependent Differential PrivacyIEEE Transactions on Information Theory10.1109/TIT.2023.334014770:2(1300-1319)Online publication date: Feb-2024
https://doi.org/10.1109/TIT.2023.3340147
Feng TZhang ZWong WSun SSikdar B(2024)A Framework for Tradeoff Between Location Privacy Preservation and Quality of Experience in Location Based ServicesIEEE Open Journal of Vehicular Technology10.1109/OJVT.2024.33641845(428-439)Online publication date: 2024
https://doi.org/10.1109/OJVT.2024.3364184
Wu JGan WChao HYu P(2024)Geospatial Big Data: Survey and ChallengesIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing10.1109/JSTARS.2024.343837617(17007-17020)Online publication date: 2024
https://doi.org/10.1109/JSTARS.2024.3438376
Liu YYang ZLiu YYang Z(2024)Location PrivacyLocation, Localization, and Localizability10.1007/978-981-97-3176-3_10(187-202)Online publication date: 12-Jul-2024
https://doi.org/10.1007/978-981-97-3176-3_10
Bocu RBocu DIavich M(2022)An Extended Review Concerning the Relevance of Deep Learning and Privacy Techniques for Data-Driven Soft SensorsSensors10.3390/s2301029423:1(294)Online publication date: 27-Dec-2022
https://doi.org/10.3390/s23010294
Delgado-Santos PStragapede GTolosana RGuest RDeravi FVera-Rodriguez R(2022)A Survey of Privacy Vulnerabilities of Mobile Device SensorsACM Computing Surveys10.1145/351057954:11s(1-30)Online publication date: 9-Sep-2022
https://dl.acm.org/doi/10.1145/3510579
Ye YZhu YMarkos CYu J(2022)CatETA: A Categorical Approximate Approach for Estimating Time of ArrivalIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2022.320789423:12(24389-24400)Online publication date: Dec-2022
https://doi.org/10.1109/TITS.2022.3207894
Zhang CZhu YMarkos CYu SYu J(2022)Toward Crowdsourced Transportation Mode Identification: A Semisupervised Federated Learning ApproachIEEE Internet of Things Journal10.1109/JIOT.2021.31320569:14(11868-11882)Online publication date: 15-Jul-2022
https://doi.org/10.1109/JIOT.2021.3132056
Gao ZSepahi APouryousef SZhou LZhu H(2022)Tradeoff between Privacy and Utility for Location-based Recommendation ServicesICC 2022 - IEEE International Conference on Communications10.1109/ICC45855.2022.9838926(4396-4401)Online publication date: 16-May-2022
https://doi.org/10.1109/ICC45855.2022.9838926
Show More Cited By

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents