Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3564625.3564628acmotherconferencesArticle/Chapter ViewAbstractPublication PagesacsacConference Proceedingsconference-collections
research-article

Reconstruction Attack on Differential Private Trajectory Protection Mechanisms

Published: 05 December 2022 Publication History

Abstract

Location trajectories collected by smartphones and other devices represent a valuable data source for applications such as location-based services. Likewise, trajectories have the potential to reveal sensitive information about individuals, e.g., religious beliefs or sexual orientations. Accordingly, trajectory datasets require appropriate sanitization. Due to their strong theoretical privacy guarantees, differential private publication mechanisms receive much attention. However, the large amount of noise required to achieve differential privacy yields structural differences, e.g., ship trajectories passing over land. We propose a deep learning-based Reconstruction Attack on Protected Trajectories (RAoPT), that leverages the mentioned differences to partly reconstruct the original trajectory from a differential private release. The evaluation shows that our RAoPT model can reduce the Euclidean and Hausdorff distances between the released and original trajectories by over 68 % on two real-world datasets under protection with ε ≤ 1. In this setting, the attack increases the average Jaccard index of the trajectories’ convex hulls, representing a user’s activity space, by over 180 %. Trained on the GeoLife dataset, the model still reduces the Euclidean and Hausdorff distances by over 60 % for T-Drive trajectories protected with a state-of-the-art mechanism (ε = 0.1). This work highlights shortcomings of current trajectory publication mechanisms, and thus motivates further research on privacy-preserving publication schemes.

References

[1]
Martin Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. https://www.tensorflow.org/
[2]
Osman Abul, Francesco Bonchi, and Mirco Nanni. 2008. Never Walk Alone: Uncertainty for Anonymity in Moving Objects Databases. In 2008 IEEE 24th Int. Conf. Data Eng., Vol. 00. IEEE, 376–385. https://doi.org/10.1109/ICDE.2008.4497446
[3]
Osman Abul, Francesco Bonchi, and Mirco Nanni. 2010. Anonymization of Moving Objects Databases by Clustering and Perturbation. Inf. Syst. 35, 8 (Dec. 2010), 884–910. https://doi.org/10.1016/j.is.2010.05.003
[4]
Hugo Barbosa, Marc Barthelemy, Gourab Ghoshal, Charlotte R. James, Maxime Lenormand, Thomas Louail, Ronaldo Menezes, José J. Ramasco, Filippo Simini, and Marcello Tomasini. 2018. Human Mobility: Models and Applications. Phys. Rep. 734 (March 2018), 1–74. https://doi.org/10.1016/j.physrep.2018.01.001
[5]
Yang Cao, Yonghui Xiao, Li Xiong, Liquan Bai, and Masatoshi Yoshikawa. 2021. Protecting Spatiotemporal Event Privacy in Continuous Location-Based Services. IEEE Trans. Knowl. Data Eng. 33, 8 (Aug. 2021), 3141–3154. https://doi.org/10.1109/TKDE.2019.2963312
[6]
Rui Chen, Benjamin C. M. Fung, and Bipin C. Desai. 2011. Differentially Private Trajectory Data Publication. arXiv abs/1112.2 (Dec. 2011), 1–12. http://arxiv.org/abs/1112.2020
[7]
Si Chen, Anmin Fu, Jian Shen, Shui Yu, Huaqun Wang, and Huaijiang Sun. 2020. RNN-DP: A New Differential Privacy Scheme Base on Recurrent Neural Network for Dynamic Trajectory Privacy Protection. J. Netw. Comput. Appl. 168, February (2020), 102736. https://doi.org/10.1016/j.jnca.2020.102736
[8]
François Chollet 2015. Keras. https://keras.io
[9]
OpenStreetMap Contributors. 2017. OpenStreetMap. https://www.openstreetmap.org/
[10]
Yves-Alexandre de Montjoye, César A. Hidalgo, Michel Verleysen, and Vincent D. Blondel. 2013. Unique in the Crowd: The Privacy Bounds of Human Mobility. Sci. Rep. 3, 1 (Dec. 2013), 1–5. https://doi.org/10.1038/srep01376
[11]
Julien Deniau 2013. Haversine. https://github.com/mapado/haversine/
[12]
Dingqi Yang, Daqing Zhang, Vincent W Zheng, and Zhiyong Yu. 2015. Modeling User Activity Preference by Leveraging User Spatial Temporal Characteristics in LBSNs. IEEE Trans. Syst. Man Cybern. Syst. 45, 1 (Jan. 2015), 129–142. https://doi.org/10.1109/TSMC.2014.2327053
[13]
Cynthia Dwork. 2008. Differential Privacy: A Survey of Results. In Theory and Applications of Models of Computation, Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li (Eds.). Vol. 4978 LNCS. Springer Berlin Heidelberg, Berlin, Heidelberg, 1–19. https://doi.org/10.1007/978-3-540-79228-4_1
[14]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography Conference. Vol. 3876 LNCS. Springer, Berlin, Heidelberg, 265–284. https://doi.org/10.1007/11681878_14
[15]
Cynthia Dwork and Aaron Roth. 2013. The Algorithmic Foundations of Differential Privacy. Found. Trends® Theor. Comput. Sci. 9, 3-4 (2013), 211–407. https://doi.org/10.1561/0400000042
[16]
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In Proc. 2014 ACM SIGSAC Conf. Comput. Commun. Secur.ACM, 1054–1067. https://doi.org/10.1145/2660267.2660348
[17]
Lorenzo Franceschi-Bicchierai. 2015. Redditor Cracks Anonymous Data Trove to Pinpoint Muslim Cab Drivers. https://mashable.com/archive/redditor-muslim-cab-drivers
[18]
Fernanda Oliveira Gomes, Douglas Simoes Silva, Bruno Machado Agostinho, and Jean Everson Martina. 2018. Privacy Preserving on Trajectories Created by Wi-Fi Connections in a University Campus. In 2018 IEEE Int. Conf. Intell. Secur. Inform. ISI. IEEE, 181–186. https://doi.org/10.1109/ISI.2018.8587319
[19]
Google. 2022. Google Maps. https://www.google.com/maps
[20]
Charles R Harris, K Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, 2020. Array Programming with NumPy. Nature 585, 7825 (Sept. 2020), 357–362. https://doi.org/10.1038/s41586-020-2649-2
[21]
Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long Short-Term Memory. Neural Comput. 9, 8 (Nov. 1997), 1735–1780. https://doi.org/10.1162/neco.1997.9.8.1735
[22]
Jingyu Hua, Yue Gao, and Sheng Zhong. 2015. Differentially Private Publication of General Time-Serial Trajectory Data. In 2015 IEEE Conf. Comput. Commun. INFOCOM, Vol. 26. IEEE, 549–557. https://doi.org/10.1109/INFOCOM.2015.7218422
[23]
Kaifeng Jiang, Dongxu Shao, Stéphane Bressan, Thomas Kister, and Kian-Lee Tan. 2013. Publishing Trajectories with Differential Privacy Guarantees. In Proc. 25th Int. Conf. Sci. Stat. Database Manag. - SSDBM. ACM Press, 1. https://doi.org/10.1145/2484838.2484846
[24]
Weiwei Jiang and Jiayun Luo. 2022. Graph Neural Network for Traffic Forecasting: A Survey. Expert Systems with Applications 207 (Nov. 2022), 117921. https://doi.org/10.1016/j.eswa.2022.117921
[25]
Diederik P Kingma and Jimmy Ba. 2014. Adam: A Method for Stochastic Optimization. 3rd Int. Conf. Learn. Represent. ICLR 2015 San Diego CA USA May 7-9 2015 Conf. Track Proc. abs1412.69 (Dec. 2014), 1–15. https://doi.org/10.48550/ARXIV.1412.6980
[26]
Robert A. Kleinman and Colin Merkel. 2020. Digital Contact Tracing for COVID-19. Can. Med. Assoc. J. 192, 24 (June 2020), E653–E656. https://doi.org/10.1503/cmaj.200922
[27]
Jae Hyun Lee, Adam W. Davis, Seo Youn Yoon, and Konstadinos G. Goulias. 2016. Activity Space Estimation with Longitudinal Observations of Social Media Data. Transportation 43, 6 (Nov. 2016), 955–977. https://doi.org/10.1007/s11116-016-9719-1
[28]
Meng Li, Liehuang Zhu, Zijian Zhang, and Rixin Xu. 2017. Achieving Differential Privacy of Trajectory Data Publishing in Participatory Sensing. Inf. Sci. 400–401 (Aug. 2017), 1–13. https://doi.org/10.1016/j.ins.2017.03.015
[29]
Peng Li, Xi Rao, Jennifer Blase, Yue Zhang, Xu Chu, and Ce Zhang. 2021. CleanML: A Study for Evaluating the Impact of Data Cleaning on ML Classification Tasks. In 2021 IEEE 37th Int. Conf. Data Eng. ICDE. IEEE, 13–24. https://doi.org/10.1109/ICDE51399.2021.00009
[30]
Qi Liu, Juan Yu, Jianmin Han, and Xin Yao. 2021. Differentially Private and Utility-Aware Publication of Trajectory Data. Expert Syst. Appl. 180, March 2020 (Oct. 2021), 115120. https://doi.org/10.1016/j.eswa.2021.115120
[31]
Xi Liu, Hanzhou Chen, and Clio Andris. 2018. trajGANs: Using Generative Adversarial Networks for Geo-Privacy Protection of Trajectory Data (Vision Paper). In Locat. Priv. Secur. Workshop. github.io, 1–7.
[32]
Jia Luo and Jinying Huang. 2019. Generative Adversarial Network: An Overview. Yi Qi Yi Biao Xue BaoChinese J. Sci. Instrum. 40, 3 (2019), 74–84. https://doi.org/10.19650/j.cnki.cjsi.J1804413
[33]
Tinghuai Ma and Fagen Song. 2021. A Trajectory Privacy Protection Method Based on Random Sampling Differential Privacy. ISPRS Int. J. Geo-Inf. 10, 7 (July 2021), 454. https://doi.org/10.3390/ijgi10070454
[34]
Lucas May Petry, Camila Leite Da Silva, Andrea Esuli, Chiara Renso, and Vania Bogorny. 2020. MARC: A Robust Method for Multiple-Aspect Trajectory Classification via Space, Time, and Semantic Embeddings. Int. J. Geogr. Inf. Sci. 34, 7 (2020), 1428–1450. https://doi.org/10.1080/13658816.2019.1707835
[35]
Frank McSherry and Kunal Talwar. 2007. Mechanism Design via Differential Privacy. In 48th Annu. IEEE Symp. Found. Comput. Sci. FOCS07. IEEE, 94–103. https://doi.org/10.1109/FOCS.2007.66
[36]
Anna Monreale, Roberto Trasarti, Dino Pedreschi, Chiara Renso, and Vania Bogorny. 2011. C-Safety: A Framework for the Anonymization of Semantic Trajectories. Trans. Data Priv. 4, 2 (2011), 73–101.
[37]
Elham Naghizade, Lars Kulik, Egemen Tanin, and James Bailey. 2020. Privacy- and Context-aware Release of Trajectory Data. ACM Trans. Spat. Algorithms Syst. 6, 1 (Feb. 2020), 1–25. https://doi.org/10.1145/3363449
[38]
Mehmet Ercan Nergiz, Maurizio Atzori, and Yucel Saygin. 2008. Towards Trajectory Anonymization: A Generalization-Based Approach. In Proc. SIGSPATIAL ACM GIS 2008 Int. Workshop Secur. Priv. GIS LBS - SPRINGL 08. ACM Press, 52. https://doi.org/10.1145/1503402.1503413
[39]
Niantic. 2022. Pokemon GO. https://pokemongolive.com/
[40]
Ben Niu, Qinghua Li, Xiaoyan Zhu, Guohong Cao, and Hui Li. 2014. Achieving K-Anonymity in Privacy-Aware Location-Based Services. In IEEE INFOCOM 2014 - IEEE Conf. Comput. Commun.IEEE, 754–762. https://doi.org/10.1109/INFOCOM.2014.6848002
[41]
Xin Niu, Hongyu Huang, and Yantao Li. 2020. A Real-Time Data Collection Mechanism With Trajectory Privacy in Mobile Crowd-Sensing. IEEE Commun. Lett. 24, 10 (Oct. 2020), 2114–2118. https://doi.org/10.1109/LCOMM.2020.3003997
[42]
The pandas development team. 2022. Pandas-Dev/Pandas: Pandas. https://doi.org/10.5281/zenodo.6408044
[43]
Young Joon Park, Young June Choe, Ok Park, Shin Young Park, Young-Man Kim, 2020. Contact Tracing during Coronavirus Disease Outbreak, South Korea, 2020. Emerg. Infect. Dis. 26, 10 (Oct. 2020), 2465–2468. https://doi.org/10.3201/eid2610.201315
[44]
Fabien Petitcolas. 1883. La Cryptographie Militaire. J Sci Mil. 9(1883), 161–191.
[45]
Atul Pokharel, Robert Soulé, and Avi Silberschatz. 2021. A Case for Location Based Contact Tracing. Health Care Manag. Sci. 24, 2 (June 2021), 420–438. https://doi.org/10.1007/s10729-021-09567-z
[46]
Vincent Primault, Sonia Ben Mokhtar, Cedric Lauradoux, and Lionel Brunie. 2015. Time Distortion Anonymization for the Publication of Mobility Data with High Utility. In 2015 IEEE Trust., Vol. 1. IEEE, 539–546. https://doi.org/10.1109/Trustcom.2015.417
[47]
Vincent Primault, Antoine Boutet, Sonia Ben Mokhtar, and Lionel Brunie. 2019. The Long Road to Computational Location Privacy: A Survey. IEEE Commun. Surv. Tutor. 21, 3 (2019), 2772–2793. https://doi.org/10.1109/COMST.2018.2873950
[48]
Youyang Qu, Jingwen Zhang, Ruidong Li, Xiaoning Zhang, Xuemeng Zhai, and Shui Yu. 2020. Generative Adversarial Networks Enhanced Location Privacy in 5G Networks. Sci. China Inf. Sci. 63, 12 (Dec. 2020), 220303. https://doi.org/10.1007/s11432-019-2834-x
[49]
Jinmeng Rao, Song Gao, Yuhao Kang, and Qunying Huang. 2020. LSTM-TrajGAN: A Deep Learning Approach to Trajectory Privacy Protection. Leibniz Int. Proc. Inform. 177, GIScience (2020), 1–16. https://doi.org/10.4230/LIPIcs.GIScience.2021.I.12
[50]
C C Robusto. 1957. The Cosine-Haversine Formula. Am. Math. Mon. 64, 1 (1957), 38–40. https://doi.org/10.2307/2309088
[51]
Sina Shaham, Ming Ding, Bo Liu, Shuping Dang, Zihuai Lin, and Jun Li. 2021. Privacy Preserving Location Data Publishing: A Machine Learning Approach. IEEE Trans. Knowl. Data Eng. 33, 9 (Sept. 2021), 3270–3283. https://doi.org/10.1109/TKDE.2020.2964658
[52]
Minglai Shao, Jianxin Li, Qiben Yan, Feng Chen, Hongyi Huang, and Xunxun Chen. 2020. Structured Sparsity Model Based Trajectory Tracking Using Private Location Data Release. IEEE Trans. Dependable Secure Comput. 18, 6 (2020), 2983–2995. https://doi.org/10.1109/TDSC.2020.2972334
[53]
Xiujin Shi, Junrui Zhang, and Yuan Gong. 2021. A Dummy Location Generation Algorithm Based on the Semantic Quantification of Location. In 2021 IEEE Int. Conf. Artif. Intell. Comput. Appl. ICAICA. IEEE, 172–176. https://doi.org/10.1109/ICAICA52286.2021.9497903
[54]
Dalwinder Singh and Birmohan Singh. 2020. Investigating the Impact of Data Normalization on Classification Performance. Appl. Soft Comput. 97 (Dec. 2020), 105524. https://doi.org/10.1016/j.asoc.2019.105524
[55]
Zhen Tu, Kai Zhao, Fengli Xu, Yong Li, Li Su, and Depeng Jin. 2019. Protecting Trajectory From Semantic Attack Considering K-Anonymity, l-Diversity, and t-Closeness. IEEE Trans. Netw. Serv. Manag. 16, 1 (March 2019), 264–278. https://doi.org/10.1109/TNSM.2018.2877790
[56]
Waze Mobile. 2022. Waze. https://www.waze.com/
[57]
Yu Xin, Zhi-Qiang Xie, and Jing Yang. 2017. The Privacy Preserving Method for Dynamic Trajectory Releasing Based on Adaptive Clustering. Inf. Sci. 378 (Feb. 2017), 131–143. https://doi.org/10.1016/j.ins.2016.10.038
[58]
Heng Xu, Xin (Robert) Luo, John M. Carroll, and Mary Beth Rosson. 2011. The Personalization Privacy Paradox: An Exploratory Study of Decision Making Process for Location-Aware Marketing. Decis. Support Syst. 51, 1 (April 2011), 42–52. https://doi.org/10.1016/j.dss.2010.11.017
[59]
Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, and Yan Huang. 2010. T-Drive. In Proc. 18th SIGSPATIAL Int. Conf. Adv. Geogr. Inf. Syst. - GIS 10. ACM Press, 99. https://doi.org/10.1145/1869790.1869807
[60]
Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma. 2009. Mining Interesting Locations and Travel Sequences from GPS Trajectories. In Proc. 18th Int. Conf. World Wide Web(WWW ’09). Association for Computing Machinery, 791–800. https://doi.org/10.1145/1526709.1526816

Cited By

View all
  • (2024)Federated TimeGAN for Privacy Preserving Synthetic Trajectory Generation2024 25th IEEE International Conference on Mobile Data Management (MDM)10.1109/MDM61037.2024.00062(301-306)Online publication date: 24-Jun-2024
  • (2024)Privacy-preserving generation and publication of synthetic trajectory microdata: A comprehensive surveyJournal of Network and Computer Applications10.1016/j.jnca.2024.103951230(103951)Online publication date: Oct-2024
  • (2024)An overview of proposals towards the privacy-preserving publication of trajectory dataInternational Journal of Information Security10.1007/s10207-024-00894-023:6(3711-3747)Online publication date: 4-Sep-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences
ACSAC '22: Proceedings of the 38th Annual Computer Security Applications Conference
December 2022
1021 pages
ISBN:9781450397599
DOI:10.1145/3564625
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

Publication History

Published: 05 December 2022

Permissions

Request permissions for this article.

Check for updates

Badges

Author Tags

  1. Deep Learning
  2. Differential Privacy
  3. Location Privacy
  4. Trajectory Privacy

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Conference

ACSAC

Acceptance Rates

Overall Acceptance Rate 104 of 497 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)204
  • Downloads (Last 6 weeks)16
Reflects downloads up to 27 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Federated TimeGAN for Privacy Preserving Synthetic Trajectory Generation2024 25th IEEE International Conference on Mobile Data Management (MDM)10.1109/MDM61037.2024.00062(301-306)Online publication date: 24-Jun-2024
  • (2024)Privacy-preserving generation and publication of synthetic trajectory microdata: A comprehensive surveyJournal of Network and Computer Applications10.1016/j.jnca.2024.103951230(103951)Online publication date: Oct-2024
  • (2024)An overview of proposals towards the privacy-preserving publication of trajectory dataInternational Journal of Information Security10.1007/s10207-024-00894-023:6(3711-3747)Online publication date: 4-Sep-2024
  • (2023)Research on differential privacy protection method based on user tendencyPLOS ONE10.1371/journal.pone.028882318:10(e0288823)Online publication date: 26-Oct-2023
  • (2023)Balancing Privacy and Utility of Spatio-Temporal Data for Taxi-Demand Prediction2023 24th IEEE International Conference on Mobile Data Management (MDM)10.1109/MDM58254.2023.00044(215-220)Online publication date: Jul-2023
  • (2023)DEMO: STM - A Privacy-Enhanced Solution for Spatio-Temporal Trajectory Management2023 24th IEEE International Conference on Mobile Data Management (MDM)10.1109/MDM58254.2023.00034(168-171)Online publication date: Jul-2023

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

HTML Format

View this article in HTML Format.

HTML Format

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media