防止暴露位置攻击的轨迹隐私保护

doi:10.11772/j.issn.1001-9081.2019081612

《计算机应用》唯一官方网站 ›› 2020, Vol. 40 ›› Issue (2): 479-485.DOI: 10.11772/j.issn.1001-9081.2019081612

• 第36届CCF中国数据库学术会议(NDBC 2019) • 上一篇下一篇

防止暴露位置攻击的轨迹隐私保护

刘向宇¹^,²(), 陈金梅¹, 夏秀峰¹, Singh Manish², 宗传玉¹, 朱睿¹

^1.沈阳航空航天大学计算机学院，沈阳 110136
^2.惠灵顿理工学院信息与商科学院，新西兰下哈特 5010

收稿日期:2019-08-14 修回日期:2019-08-27 接受日期:2019-10-12 发布日期:2019-11-18 出版日期:2020-02-10
通讯作者: 刘向宇
作者简介:陈金梅（1994—），女，河北张家口人，硕士研究生，主要研究方向：数据隐私保护
夏秀峰（1964—），男，山东胶南人，教授，博士，CCF会员，主要研究方向：数据库、数据仓库、数据挖掘； Manish Singh（1981—），男，尼泊尔人，高级讲师，博士研究生，主要研究方向：并行计算、密码学
宗传玉（1985—），男，山东潍坊人，讲师，博士，CCF会员，主要研究方向：数据清洗、数据溯源、查询处理优化
朱睿（1982—），男，辽宁沈阳人，讲师，博士，CCF会员，主要研究方向：数据流。
基金资助:
辽宁省自然科学基金计划重点项目(20170520321)

Preventing location disclosure attacks through generating dummy trajectories

Xiangyu LIU¹^,²(), Jinmei CHEN¹, Xiufeng XIA¹, Manish Singh², Chuanyu ZONG¹, Rui ZHU¹

^1.College of Computer Science，Shenyang Aerospace University，Shenyang Liaoning 110136，China
^2.School of IT and Business，Wellington Institute of Technology，Lower Hutt 5010，New Zealand

Received:2019-08-14 Revised:2019-08-27 Accepted:2019-10-12 Online:2019-11-18 Published:2020-02-10
Contact: Xiangyu LIU
About author:CHEN Jinmei， born in 1994， M. S. candidate. Her research interests include data privacy protection.
XIA Xiufeng， born in 1964， Ph. D.， professor. His research interests include database， data warehouse， data mining.
Manish Singh， born in 1981， Ph. D. candidate， senior lecturer. His research interests include parallel computing， cryptography.
ZONG Chuanyu， born in 1985， Ph. D.， lecturer. His research interests include data cleaning， tracing the source of data， optimization of query processing.
ZHU Rui， born in 1982， Ph. D.， lecturer. His research interests include data stream.
Supported by:
the Key Projects of Natural Science Foundation of Liaoning Province(20170520321)

摘要/Abstract

摘要：

为解决移动对象轨迹信息被大量收集所导致的轨迹隐私泄露问题，提出了基于假轨迹的轨迹隐私保护算法。在该算法中，考虑了用户的暴露位置，基于轨迹相似性和位置多样性的综合度量，设计了一种启发式规则来选择假轨迹，从而使得生成的假轨迹能有效隐匿真实轨迹和敏感位置。此外，还提出了轨迹有向图策略和基于网格划分的地图策略来优化算法的执行效率。基于真实的轨迹数据进行实验测试和分析，实验结果表明所提算法在保持数据可用性的情况下能有效保护真实轨迹。

关键词: 轨迹隐私保护, 假轨迹, 数据发布, 匿名化, 数据可用性

Abstract:

In order to solve the problem of trajectory privacy leakage caused by the collection of numerous trajectory information of moving objects， a dummy trajectory-based trajectory privacy protection algorithm was proposed. In this algorithm， considering the user’s locations under disclosure， a heuristic rule was designed based on the comprehensive measure of trajectory similarity and location diversity to select the dummy trajectories， so that the generated dummy trajectories were able to effectively hide the real trajectory and sensitive locations. Besides， the trajectory directed graph strategy and the grid-based map strategy were proposed to optimize the execution efficiency of the algorithm. Experimental results on real trajectory datasets demonstrate that the proposed algorithm can effectively protect the real trajectory with high data utility.

Key words: trajectory privacy protection, dummy trajectory, data publishing, anonymization, data utility

中图分类号:

TP309

刘向宇, 陈金梅, 夏秀峰, Singh Manish, 宗传玉, 朱睿. 防止暴露位置攻击的轨迹隐私保护[J]. 计算机应用, 2020, 40(2): 479-485.

Xiangyu LIU, Jinmei CHEN, Xiufeng XIA, Manish Singh, Chuanyu ZONG, Rui ZHU. Preventing location disclosure attacks through generating dummy trajectories[J]. Journal of Computer Applications, 2020, 40(2): 479-485.

图/表 11

图1 真实轨迹tr、随机法生成的tr的假轨迹和tr的匿名轨迹集

Fig. 1 Real trajectory tr， dummy trajectories of tr generated by random algorithm and the anonymized trajectory set TRS of tr

图2 轨迹有向图

Fig. 2 Trajectory directed graph

图3 轨迹有向图的存储结构

Fig. 3 Storage structure of trajectory directed graph

图4 不同敏感位置的查询网格

Fig. 4 Query girds of different sensitive locations

表1 实验数据统计信息

Tab. 1 Statistics of datasets

数据集	位置数	轨迹平均长度	轨迹总耗时/h	轨迹总距离/km	最大的用户速度/（km·min^-1）
Gowalla	42 683	8.536 0	14 734	40 560	1.13
Brightkite	38 916	7.783 2	12 176	37 916	1.22

图5 轨迹相似性、平均位置泄漏率和运行时间随轨迹距离的变化

Fig. 5 Trajectory similarity， average location disclosure rate and running time varying with trajectory distance

图6 轨迹相似性随k的变化

Fig. 6 Trajectory similarity varying with k

图7 轨迹泄漏率随k的变化

Fig. 7 Trajectory disclosure rate varying with k

图8 运行时间随k的变化

Fig. 8 Running time varying with k

图9 暴露位置数|EL|对DTPP的影响

Fig. 9 Effect of |EL| on DTPP

图10 位置匿名阈值p对DTPP的影响

Fig. 10 Effect of p on DTPP

参考文献 15

1	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： 125-134. 10.1016/j.jnca.2013.03.010
2	FECHNER T， KRAY C. Attacking location privacy： exploring human strategies［C］// Proceedings of the 2012 ACM Conference on Ubiquitous Computing. New York： ACM， 2012： 95-98. 10.1145/2370216.2370232
3	KIDO H， YANAGISAWA Y， SATOH T. An anonymous communication technique using dummies for location-based services［C］// Proceedings of the 2005 International Conference on Pervasive Services. Piscataway： IEEE， 2005： 88-97. 10.1109/perser.2005.1506394
4	MONREALE A， ANDRIENKO G， ANDRIENKO N， et al. Movement data anonymity through generalization［J］.Transactions on Data Privacy， 2010， 3（2）：91-121.
5	XU T， CAI Y. Exploring historical location data for anonymity preservation in location-based services［C］// Proceedings of the 27th Conference on Computer Communications. Piscataway： IEEE， 2008： 547-555. 10.1109/infocom.2008.103
6	ABUL O， BONCHI F， NANNI M. Never walk alone： uncertainty for anonymity in moving objects databases［C］// Proceedings of the 24th IEEE International Conference on Data Engineering. Piscataway： IEEE， 2008： 376-385. 10.1109/icde.2008.4497446
7	HUO Z， MENG X， HU H， et al. You can walk alone： trajectory privacy-preserving through significant stays protection［C］// Proceedings of the 17th International Conference on Database Systems for Advanced Applications， LNCS7238. Berlin： Springer， 2012： 351-366.
8	GRUTESER M， LIU X. Protecting privacy in continuous location-tracking applications［J］. IEEE Security and Privacy， 2004， 2（2）： 28-34. 10.1109/msecp.2004.1281242
9	TERROVITIS M， MAMOULIS N. Privacy preservation in the publication of trajectories［C］// Proceedings of the 9th International Conference on Mobile Data Management. Piscataway： IEEE， 2008： 65-72. 10.1109/mdm.2008.29
10	赵婧，张渊，李兴华，等. 基于轨迹频率抑制的轨迹隐私保护方法［J］. 计算机学报， 2014， 37（10）：2096-2106. 10.3724/SP.J.1016.2014.02096
	ZHAO J， ZHANG Y， LI X H， et al. A trajectory privacy protection approach via trajectory frequency suppression ［J］. Chinese Journal of Computers， 2014， 37（10）：2096-2106. 10.3724/SP.J.1016.2014.02096
11	KIDO H， YANAGISAWA Y， SATOH T. Protection of location privacy using dummies for location-based services［C］// Proceedings of the 21st International Conference on Data Engineering Workshops. Piscataway： IEEE， 2005： 1248-1248. 10.1109/icde.2005.269
12	LEI P R， PENG W C， SU I J， et al. Dummy-based schemes for protecting movement trajectories［J］. Journal of Information Science and Engineering， 2012， 28（2）： 335-350.
13	WANG T， ZENG J， BHUIYAN M Z A， et al. Trajectory privacy preservation based on a fog structure for cloud location services［J］. IEEE Access， 2017， 5： 7692-7701. 10.1109/access.2017.2698078
14	雷凯跃，李兴华，刘海，等. 轨迹发布中基于时空关联性的假轨迹隐私保护方案［J］. 通信学报， 2016， 37（12）： 156-164. 10.11959/j.issn.1000-436x.2016281
	LEI K Y， LI X H， LIU H， et al. Dummy trajectory privacy protection scheme for trajectory publishing based on the spatiotemporal correlation［J］. Journal on Communications， 2016， 37（12）： 156-164. 10.11959/j.issn.1000-436x.2016281
15	WU Q， LIU H， ZHANG C， et al. Trajectory protection schemes based on a gravity mobility model in IoT［J］. Electronics， 2019， 8（2）： No.148. 10.3390/electronics8020148

[1]	张治政, 张啸剑, 王俊清, 冯光辉. 结合差分隐私与安全聚集的联邦空间数据发布方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2777-2784.
[2]	刘沛骞, 王水莲, 申自浩, 王辉. 基于轨迹扰动和路网匹配的位置隐私保护算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1546-1554.
[3]	陈学斌, 单丽洋, 郭如敏. 基于差分隐私的直方图发布方法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3114-3121.
[4]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[5]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[6]	刘向宇, 夏国平, 夏秀峰, 宗传玉, 朱睿, 李佳佳. 个性化时空数据隐私保护[J]. 计算机应用, 2021, 41(3): 643-650.
[7]	涂子璇, 刘树波, 熊星星, 赵晶, 蔡朝晖. 可穿戴设备的数值型流数据差分隐私均值发布[J]. 计算机应用, 2020, 40(6): 1692-1697.
[8]	张梅舒, 徐雅斌. 多维数值型敏感属性数据的个性化隐私保护方法[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 491-496.
[9]	郭良敏, 王安鑫, 郑孝遥. 基于区域划分的轨迹隐私保护方法[J]. 计算机应用, 2018, 38(11): 3263-3269.
[10]	王秋月, 葛丽娜, 耿博, 王利娟. 基于多敏感属性分级的(α_ij,k,m)-匿名隐私保护方法[J]. 计算机应用, 2018, 38(1): 67-72.
[11]	孙丹丹, 罗永龙, 范国婷, 郭良敏, 郑孝遥. 基于轨迹形状多样性的隐私保护算法[J]. 计算机应用, 2016, 36(6): 1544-1551.
[12]	桂琼程小辉. 基于聚类的分级匿名方法[J]. 计算机应用, 2013, 33(02): 412-416.
[13]	许黎明强小强宋转. 谱半径和特征显著性约束的随机化社会网络方法[J]. 计算机应用, 2012, 32(02): 485-488.
[14]	刘喻吕大鹏冯建华周立柱 . 数据发布中的匿名化技术研究综述[J]. 计算机应用, 2007, 27(10): 2361-2364.

防止暴露位置攻击的轨迹隐私保护

Preventing location disclosure attacks through generating dummy trajectories

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 15

相关文章 14

编辑推荐

Metrics