位置轨迹隐私保护综述

doi:10.3969/j.issn.1671-1122.2015.10.004

摘要/Abstract

摘要：

基于位置服务在为用户的日常生活带来极大便利的同时,又不可避免地导致一定程度上用户隐私信息的泄露。在隐私泄露问题上,当前较为关注的是用户在使用位置服务时位置隐私的泄露。大量的位置数据存在着相互关联进而有形成位置轨迹的可能,而位置轨迹数据含有比单纯的位置数据更为丰富的时空关联,这些关联使得攻击者更容易获取用户的隐私信息。针对这一问题,研究者们提出了大量针对位置轨迹数据的隐私保护方法。在众多的位置轨迹隐私保护方法中,如何找到同类方法,有针对性地进行位置轨迹隐私保护研究成为研究者不得不面对的问题。文章在借鉴已有分类方法的基础上,针对近年来提出的和由原有算法改进而来的位置轨迹隐私保护算法,基于攻击者所掌握的背景知识,从位置轨迹追踪和位置轨迹重构两种攻击方法的角度对这些算法加以分类,总结并分析其优缺点。最后,文章针对当前潜在的数据挖掘攻击技术,提出了研究展望。

关键词: 位置轨迹, 隐私保护, 轨迹追踪, 轨迹重构

Abstract:

Location based service brings great convenience for users in daily life, but at the same time it inevitably leads to a certain degree of users’ private information exposure. On issues of privacy, the focus of current research is protection of users’ location privacy. Due to the relationships between locations, scattered locations could be constituted into location trajectory, and that location trajectory contains more spatio-temporal correlations, with comparison of solo location. The attacker could be more accessible to user’s privacy with the help of these correlations. In order to solve this problem, researchers put forward a lot of methods to protect the location trajectory privacy. But how to find the similar methods for study or imitation has puzzled the researcher, because there is no specific classification. In this article, based on the attack techniques of location trajectory tracking and reconstruction, we propose a new classification. With this classification, we analyze these protection methods and summarize the advantages and disadvantages of them. Finally, we put forward in the research prospects for the potential attacks of data mining technology.

Key words: location trajectory, privacy protection, trajectory tracking, trajectory reconstruction

中图分类号:

TP309

马春光, 张磊, 杨松涛. 位置轨迹隐私保护综述[J]. 信息网络安全, 2015, 15(10): 24-31.

MA Chun-guang, ZHANG Lei, YANG Song-tao. Review on Location Trajectory Privacy Protection[J]. Netinfo Security, 2015, 15(10): 24-31.

图/表 3

参考文献 62

[1]	王勇,高诗梦,聂肖,等. 基于速度动态差异的位置服务匿名算法[J]. 信息网络安全,2015,(4):28-35.
[2]	FUYU L, HUA K A, YING C.Query l-diversity in Location-Based Services[C]//Proceedings of the Mobile Data Management: Systems, Services and Middleware, 2009 MDM '09 Tenth International Conference on, 2009: 436-442.
[3]	王家波,赵泽茂,李林. 位置服务中一种基于假轨迹的轨迹隐私保护方法[J]. 信息网络安全,2014,(3):62-67.
[4]	KHOSHGOZARAN A, SHAHABI C, SHIRANI-MEHR H.Location privacy: going beyond K-anonymity, cloaking and anonymizers[J]. Knowledge and Information Systems, 2011, 26(3): 435-465.
[5]	REBOLLO-MONEDERO D, FORNE J, Solanas A, et al.Private location-based information retrieval through user collaboration[J]. Computer Communications, 2010, 33(6): 762-774.
[6]	车浩然,何永忠,刘吉强. 基于P2P和网格ID的位置匿名算法研究[J]. 信息网络安全,2015,(3):28-32.
[7]	BONCHI F.Privacy Preserving Publication of Moving Object Data[M]. Springer-Verlag, 2009: 190-215.
[8]	BONCHI F, LAKSHMANAN L V S, WANG H. Trajectory anonymity in publishing personal mobility data[J]. SIGKDD Explor Newsl, 2011, 13(1): 30-42.
[9]	霍峥,孟小峰. 轨迹隐私保护技术研究[J]. 计算机学报,2011,34(10):1820-1830.
[10]	CHOW C Y, MOKBEL M F.Trajectory privacy in location-based services and data publication[J]. SIGKDD Explor Newsl, 2011, 13(1): 19-29.
[11]	BERESFORD A R, STAJANO F.Location privacy in pervasive computing[J]. Pervasive Computing, IEEE, 2003, 2(1): 46-55.
[12]	FREUDIGER J, SHOKRI R, HUBAUX J P.On the optimal placement of mix zones[C]//9th International Symposium, PETS 2009, Seattle, WA, USA, 2009: 216-234.
[13]	FREUDIGER J, RAYA M, FÉLEGYHÁZI M, et al. Mix-zones for location privacy in vehicular networks[C]//first international workshop on wireless networking for intelligent transportation systems (Win-ITS), Canada, 2007: 216-234.
[14]	PALANISAMY B, LING L.MobiMix: Protecting location privacy with mix-zones over road networks[C]//the Data Engineering (ICDE), 2011 IEEE 27th International Conference on, , Hannover, 2011: 494-505.
[15]	PALANISAMY B, LIU L, LEE K, et al.Anonymizing continuous queries with delay-tolerant mix-zones over road networks[J]. Distributed and Parallel Databases, 2014, 32(1): 91-118.
[16]	GAO S, MA J, SHI W, et al.TrPF: A Trajectory Privacy-Preserving Framework for Participatory Sensing[J]. Ieee Transactions on Information Forensics and Security, 2013, 8(6): 874-887.
[17]	XUE A Y, ZHANG R, ZHENG Y, et al.Destination Prediction by Sub-Trajectory Synthesis and Privacy Protection Against Such Prediction[C]//29th IEEE International Conference on Data Engineering (ICDE), Brisbane, AUSTRALIA, 2013: 254-265.
[18]	WANG C, LIU H, WRIGHT K L, et al.A privacy mechanism for mobile-based urban traffic monitoring[J]. Pervasive and Mobile Computing, 2015, 20(7): 1-12.
[19]	MOHAMMED N, FUNG B, DEBBABI M.Walking in the crowd: anonymizing trajectory data for pattern analysis[C]//18th ACM conference on Information and knowledge management, ACM, 2009: 1441-1444.
[20]	WONG R, LI J Y, FU A, et al.(alpha, k)-anonymous data publishing[J]. Journal of Intelligent Information Systems, 2009, 33(2): 209-234.
[21]	CHEN R, FUNG B C M, Mohammed N, et al. Privacy-preserving trajectory data publishing by local suppression[J]. Information Sciences, 2013, 231(9): 83-97.
[22]	MOHAMMED N, FUNG B C M, DEBBABI M. Walking in the crowd: anonymizing trajectory data for pattern analysis[C]//18th ACM conference on Information and knowledge management, Hong Kong, 2009: 1441-1444.
[23]	GHASEMZADEH M, FUNG B C M, CHEN R, et al. Anonymizing trajectory data for passenger flow analysis[J]. Transportation Research Part C-Emerging Technologies, 2014, 39(2): 63-79.
[24]	AL-HUSSAENI K, FUNG B C M, CHEUNG W K. Privacy-preserving trajectory stream publishing[J]. Data & Knowledge Engineering, 2014, 94(11): 89-109.
[25]	CICEK A E, NERGIZ M E, SAYGIN Y.Ensuring location diversity in privacy-preserving spatio-temporal data publishing[J]. Vldb Journal, 2014, 23(4): 609-625.
[26]	CHENG R, ZHANG Y, BERTINO E, et al.Preserving user location privacy in mobile data management infrastructures[C]//6th International Workshop, PET 2006, Cambridge, UK, 2006: 393-412.
[27]	XU T, CAI Y.Location anonymity in continuous location-based services[C]//15th annual ACM international symposium on Advances in geographic information systems, ACM, New York, 2007: 39.
[28]	CHOW C Y, MOKBEL M F.Enabling private continuous queries for revealed user locations[C]//10th International Symposium, SSTD 2007, Boston, MA, USA, 2007: 258-275.
[29]	GHINITA G, DAMIANI M L, SILVESTRI C, et al.Preventing velocity-based linkage attacks in location-aware applications[C]//17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM, New York, 2009: 246-255.
[30]	XU J, TANG X, HU H, et al.Privacy-conscious location-based queries in mobile environments[J]. Parallel and Distributed Systems, IEEE Transactions on, 2010, 21(3): 313-326.
[31]	武艳娜,赵泽茂. 基于连续位置服务请求的位置匿名方法的研究[J]. 信息网络安全,2015,(1):39-44.
[32]	WANG E K, YE Y.A New Privacy-Preserving Scheme for Continuous Query in Location-Based Social Networking Services[J]. International Journal of Distributed Sensor Networks, 2014, (1): 836-839.
[33]	HWANG R H, HSUEH Y L, CHUNG H W.A Novel Time-Obfuscated Algorithm for Trajectory Privacy Protection[J]. IEEE Transactions on Services Computing, 2014, 7(2): 126-139.
[34]	HASHEM T, KULIK L, ZHANG R.Countering overlapping rectangle privacy attack for moving kNN queries[J]. Information Systems, 2013, 38(3): 430-453.
[35]	GAO S, MA J F, SHI W S, et al.LTPPM: a location and trajectory privacy protection mechanism in participatory sensing[J]. Wireless Communications & Mobile Computing, 2015, 15(1): 155-169.
[36]	WANG Y, HE L P, PENG J, et al.Privacy Preserving for Continuous Query in Location Based Services[C]//Parallel and Distributed Systems (ICPADS), 2012 IEEE 18th International Conference on, Singapore, 2012: 213-220.
[37]	MA C G, ZHOU C L, YANG S T.A Voronoi-Based Location Privacy-Preserving Method for Continuous Query in LBS[J]. International Journal of Distributed Sensor Networks, 2015: 1-17.
[38]	SWEENEY L.Achieving k-anonymity privacy protection using generalization and suppression[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(05): 571-588.
[39]	AGGARWAL G, FEDER T, KENTHAPADI K, et al.Anonymizing tables[C]//Database Theory-ICDT 2005, Berlin, 2005: 246-258.
[40]	WONG R C W, LI J, FU A W C, et al. (α, k)-anonymity: an enhanced k-anonymity model for privacy preserving data publishing[C]//12th ACM SIGKDD international conference on Knowledge discovery and data mining, Philadelphia, 2006: 754-759.
[41]	AGGARWAL G, PANIGRAHY R, FEDER T, et al.Achieving anonymity via clustering[J]. Acm Transactions on Algorithms, 2010, 6(3): 153-162.
[42]	LI J, WONG R C W, FU A W C, et al. Achieving k-anonymity by clustering in attribute hierarchical structures[C]//8th International Conference, DaWaK 2006, Krakow, Poland, 2006: 405-416.
[43]	BYUN J W, KAMRA A, BERTINO E, et al.Efficient k-anonymization using clustering techniques[C]//12th International Conference on Database Systems for Advanced Applications, DASFAA 2007, Bangkok, Thailand, 2007: 188-200.
[44]	ABUL O, BONCHI F, NANNI M, et al.Never Walk Alone: Uncertainty for anonymity in moving objects databases[C]//24th IEEE International Conference on Data Engineering, Cancun, MEXICO, 2008: 376-385.
[45]	PELEKIS N, KOPANAKIS I, MARKETOS G, et al.Similarity Search in Trajectory Databases[C]//14th International Symposium on Temporal Representation and Reasoning, Alicante, Spain, 2007: 129-140.
[46]	GAO S, MA J, SUN C, et al.Balancing trajectory privacy and data utility using a personalized anonymization model[J]. Journal of Network and Computer Applications, 2014, 38(1): 125-134.
[47]	LEE J G, HAN J, WHANG K Y.Trajectory clustering: a partition-and-group framework[C]//2007 ACM SIGMOD international conference on Management of data, ACM, New York, 2007: 593-604.
[48]	SKOUMAS G, SKOUTAS D, VLACHAKI A.Efficient identification and approximation of k-nearest moving neighbors[C]//21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM, New York, 2013: 264-273.
[49]	SHERKAT R, LI J, MAMOULIS N.Efficient time-stamped event sequence anonymization[J]. ACM Transactions on the Web (TWEB), 2013, 8(1): 405-416.
[50]	KATO R, IWATA M, HARA T, et al.A dummy-based anonymization method based on user trajectory with pauses[C]//20th International Conference on Advances in Geographic Information Systems, ACM, New York, 2012: 249-258.
[51]	王超,杨静,张健沛. 基于轨迹位置形状相似性的隐私保护算法[J]. 通信学报,2015,36(2):148-161.
[52]	王超,杨静,张健沛. 基于轨迹特征及动态邻近性的轨迹匿名方法研究[J]. 自动化学报,2015,41(2):330-341.
[53]	SU H, ZHENG K, WANG H, et al.Calibrating trajectory data for similarity-based analysis[C]//2013 ACM SIGMOD International Conference on Management of Data, ACM, New York, 2013: 833-844.
[54]	LARUSSO N D, SINGH A.Efficient Tracking and Querying for Coordinated Uncertain Mobile Objects[C]//29th IEEE International Conference on Data Engineering (ICDE), Brisbane, AUSTRALIA, 2013: 182-193.
[55]	ZHENG K, ZHENG Y, YUAN N J, et al.On Discovery of Gathering Patterns from Trajectories[C]//29th IEEE International Conference on Data Engineering (ICDE), Brisbane, AUSTRALIA, 2013: 242-253.
[56]	BILOGREVIC I, JADLIWALA M, JONEJA V, et al.Privacy-Preserving Optimal Meeting Location Determination on Mobile Devices[J]. IEEE Transactions on Information Forensics and Security, 2014, 9(7): 1141-1156.
[57]	ASHOURI-TALOUKI M, BARAANI-DASTJERDI A, SELCUK A A.GLP: A cryptographic approach for group location privacy[J]. Computer Communications, 2012, 35(12): 1527-1533.
[58]	YANG B, GUO C, JENSEN C S.Travel cost inference from sparse, spatio temporally correlated time series using Markov models[J]. Proc VLDB Endow, 2013, 6(9): 769-780.
[59]	CHIANG Y H, DOAN A, NAUGHTON J F.Tracking entities in the dynamic world: a fast algorithm for matching temporal records[J]. Proc VLDB Endow, 2014, 7(6): 469-480.
[60]	张啸剑,孟小峰. 面向数据发布和分析的差分隐私保护[J]. 计算机学报,2014,37(4):927-949.
[61]	ANDRÉS M E, BORDENABE N E, CHATZIKOKOLAKIS K, et al. Geo-indistinguishability: Differential privacy for location-based systems[C]//2013 ACM SIGSAC conference on Computer & communications security, ACM, New York, 2013: 901-914.
[62]	BORDENABE N E, CHATZIKOKOLAKIS K, PALAMIDESSI C.Optimal geo-indistinguishable mechanisms for location privacy[C]//2014 ACM SIGSAC Conference on Computer and Communications Security, ACM, New York, 2014: 251-262.