中国综合性科技类核心期刊(北大核心)

中国科学引文数据库来源期刊(CSCD)

美国《化学文摘》(CA)收录

美国《数学评论》(MR)收录

俄罗斯《文摘杂志》收录

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种实时轨迹隐私保护策略

廖春和 华嘉逊 田秀霞 秦波 金澈清

廖春和, 华嘉逊, 田秀霞, 秦波, 金澈清. 一种实时轨迹隐私保护策略[J]. 华东师范大学学报(自然科学版), 2018, (4): 59-69, 108. doi: 10.3969/j.issn.1000-5641.2018.04.006
引用本文: 廖春和, 华嘉逊, 田秀霞, 秦波, 金澈清. 一种实时轨迹隐私保护策略[J]. 华东师范大学学报(自然科学版), 2018, (4): 59-69, 108. doi: 10.3969/j.issn.1000-5641.2018.04.006
LIAO Chun-he, HUA Jia-xun, TIAN Xiu-xia, QIN Bo, JIN Che-qing. A strategy for real-time trajectory privacy protection[J]. Journal of East China Normal University (Natural Sciences), 2018, (4): 59-69, 108. doi: 10.3969/j.issn.1000-5641.2018.04.006
Citation: LIAO Chun-he, HUA Jia-xun, TIAN Xiu-xia, QIN Bo, JIN Che-qing. A strategy for real-time trajectory privacy protection[J]. Journal of East China Normal University (Natural Sciences), 2018, (4): 59-69, 108. doi: 10.3969/j.issn.1000-5641.2018.04.006

一种实时轨迹隐私保护策略

doi: 10.3969/j.issn.1000-5641.2018.04.006
基金项目: 

国家重点研发计划项目 2016YFB1000905

国家自然科学基金 61370101

国家自然科学基金 61532021

国家自然科学基金 61702423

国家自然科学基金 U1501252

国家自然科学基金 U1401256

国家自然科学基金 61402180

详细信息
    作者简介:

    廖春和, 男, 硕士研究生, 研究方向为基于位置的服务.E-mail:liaochunhe@stu.ecnu.edu.cn

    通讯作者:

    金澈清, 男, 教授, 博士生导师, 研究方向为基于位置的服务.E-mail:cqjin@sei.ecnu.edu.cn

  • 中图分类号: TP391

A strategy for real-time trajectory privacy protection

  • 摘要: 实时轨迹隐私问题是LBS(Location-Based Services)领域的一个重要问题.虚假轨迹技术是一种流行的隐私保护技术,它产生多条与真实轨迹相似的虚假轨迹.然而,已有的虚假轨迹保护技术并未考虑用户所处的实际环境以及相邻时刻的位置关系等约束,从而使得攻击者很容易借助其他背景知识推测出用户的真实轨迹.因此,本文在所提出的两种全新隐私保护算法中应用了信息熵和位置可达性约束,这两种算法分别为虚假轨迹生成DTG(Dummy-Based Trajectory Generating)算法、增强型虚假轨迹生成EnDTG(Enhanced-DTG)算法.实验结果表明,相比于现有方案,本文所提的方案能有效保护用户的轨迹隐私.
  • 图  1  虚假轨迹的例子

    Fig.  1  An example of dummy trajectories

    图  2  系统架构

    Fig.  2  System architecture

    图  3  DTG算法的一个运行实例分析

    Fig.  3  A running instance of DTG algorithm

    图  4  算法的一个运行实例分析

    Fig.  4  A running instance of the EnDTG algorithm

    图  5  $k$与隐私保护程度的关系

    Fig.  5  Relationship between $k$ and privacy protection metrics

    图  6  $k$与距离之和的关系

    Fig.  6  Relationship between $k$ and sum of distance

    图  7  $k$与位置可达性$LR$数量的关系

    Fig.  7  Relationship between $k$ and location reachalility

    算法1  虚假轨迹生成算法
    输入:  最小匿名区域面积$A_{\min}$, 用户位置$U^{t_i }$, 用户隐私偏好$k$, 单元格边长$m$
    输出:  虚假位置集DummyList
      1:生成一个随机整数$d$, $d\in [1, k]$;
      2: $N\leftarrow d+\left\lceil {\frac{A_{\min } }{m^2}} \right\rceil $;
      3: $a\leftarrow \sqrt N $, $b\leftarrow \left\lceil {N/a} \right\rceil $;
      4:生成两个随机整数$\alpha $和$\beta $, $\alpha \in [0, a]$, $\beta \in [0, b]$;
      5:构造匿名区域$CR$, 其长为$a\times m$, 宽度为$b\times m$; 左下角在长轴距离$U^{t_i}$为$\alpha \times m$, 在宽轴距离$U^{t_i}$为$\beta \times m$;
      6:构造概率集$Q=\{q_{1}, q_{2}, \cdots, q_{a\times b}\}$, 其中$q_{i}$是$CR$中第$i$个单元格所对应的查询概率;
      7: CellListCR中$4k$个查询概率最接近$U^{t_i}$所处单元格的查询概率的单元格;
      8: return GenerateResult (CellList, $U^{t_i}$, $k$, $s)$.
    下载: 导出CSV
    算法2  生成结果集GenerateResult
    输入:  单元格列表CellList, 当前时刻用户位置$U^{t_i }$, 用户隐私偏好$k$, 组数$s$
    输出:   $t_{i}$时刻的虚假位置集DummyList
      1: for $j=1$ to $s$ do
      2:   TempList$_{j}\longleftarrow U^{t_i}$; 以及从CellList中随机选出的$(2k-1)$个单元格$D^{t_i}$;
      3:   通过公式(2)计算TempList$_{j}$的匿名集信息熵$H_{j}$;
      4: end for
      5: CandidateList$\longleftarrow$argmax$_ {\rm{Templist}_j}H_j$;
      6: for $j=1$ to $ s$ do
      7:   DistanceList$_{j}\longleftarrow U^{t_i}$以及从CandidateList中随机选出的$(k-1)$个单元格;
      8:   $DS_j \longleftarrow \sum\nolimits_{c_i , c_l \in \rm {Dis\!\tan \!ceList}_j , i<l} {\rm {dis}(c_i , c_l )} $;
      9: end for
      10: DummyList$\longleftarrow\rm {argmax}_ {\rm{DistanceList}j} DS_{j}$;
      11: return DummyList;
    下载: 导出CSV
    算法3  增强型虚假轨迹生成算法EnDTG
    输入: 在$t_{i}$和$t_{i-1}$时刻的用户位置$U^{t_i }$和$U^{t_{i-1} }$, $t_{i}$时刻的匿名区域CR$_{i}$, 用户隐私偏好$k$, 组数$s$, $t_{i-1}$时刻的虚假位置$D_j^{t_{i-1}}(j\in [1, k-1]), \beta$
    输出: $t_{i}$时刻的虚假位置集DummyList
    1: Dis$_{U}\longleftarrow$dis($U^{t_{i-1}}, U^{t_i}$);
    2: foreach $c\in $CR do
    3:  for $ j=1$ to $(k-1)$ do
    4:     if $\frac{|\rm {dis}(D_{j}^{t-1}, c)-\rm {Dis}_U|}{\rm {Dis}_U}\leq \beta$ then
    5:       LRList$\longleftarrow$LRList$\cup\{c\}$;
    6:     end if
    7:   end for
    8: end for
    9: CellList$\longleftarrow$LRList中4$k$个查询概率最接近$U^{t_i}$所处单元格的查询概率的单元格;
    10: return GenerateResult(CellList, $U^{t_i}$, $k$, $s)$;
    下载: 导出CSV
  • [1] LEI P R, PENG W C, SU I J, et al. Dummy-based schemes for protecting movement trajectories[J]. Journal of Information Science & Engineering, 2012, 28(2):335-350. http://cn.bing.com/academic/profile?id=4099e960408bf5c20108bc40139436f5&encoded=0&v=paper_preview&mkt=zh-cn
    [2] NIU B, LI Q, ZHU X, et al. Achieving k-anonymity in privacy-aware location-based services[C]//IEEE Infocom 2014-IEEE Conference on Computer. IEEE, 2014: 754-762. DOI: 10.1109/INFOCOM.2014.6848002.
    [3] CHOW C Y, MOKBEL M F. Trajectory privacy in location-based services and data publication[J]. ACM SIGKDD Explorations Newsletter, 2011, 13(1):19-29. doi:  10.1145/2031331
    [4] CHOW C Y, MOKBEL M F, AREF W G. Casper*: Query processing for location services without compromising privacy[J]. ACM Transactions on Database Systems, 2009, 34(4): Article No 24. DOI: 10.1145/1620585.1620591.
    [5] GRUTESER M, GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking[C]//MobiSys 2003: The 1st International Conference on Mobile Systems, Applications, and Services. USENIX Association, 2003: 31-42. http://dl.acm.org/citation.cfm?id=1189037
    [6] MOKBEL M F, CHOW C Y, AREF W G. The new Casper: Query processing for location services without compromising privacy[C]//Proceedings of the 32nd International Conference on Very Large Data Bases. 2006: 763-774. http://dl.acm.org/citation.cfm?id=1164193
    [7] FREUDIGER J, SHOKRI R, HUBAUX J P. On the optimal placement of mix-zones[C]//International Symposium on Privacy Enhancing Technologies. Berlin: Springer, 2009: 216-234. http://dl.acm.org/citation.cfm?id=1614521
    [8] PALANISAMY B, LIU L. Attack-resilient mix-zones over road networks:Architecture and algorithms[J]. IEEE Transactions on Mobile Computing, 2015, 14(3):495-508. doi:  10.1109/TMC.2014.2321747
    [9] GHINITA G, DAMIANI M L, SILVESTRI C, et al. Preventing velocity-based linkage attacks in location-aware applications[C]//ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2009: 246-255. http://dl.acm.org/citation.cfm?id=1653807
    [10] GHINITA G, KALNIS P, KHOSHGOZARAN A, et al. Private queries in location based services: Anonymizers are not necessary[C]//Proceeding the 2008 ACM SIGMOD International Conference on Management of Data. ACM, 2008: 121-132. http://dl.acm.org/citation.cfm?id=1376631
    [11] LU R X, LIN X D, SHI Z G, et al. PLAM: A privacy-preserving framework for local-area mobile social networks[C]//IEEE INFOCOM 2014-IEEE Conference on Computer Communications. IEEE, 2014: 763-771. http://ieeexplore.ieee.org/document/6848003/
    [12] DAHL M, DELAUNE S, STEEL G. Formal analysis of privacy for vehicular mix-zones[C]//Proceedings of the Computer Security-ESORICS 2010, European Symposium on Research in Computer Security. DBLP, 2010: 55-70.
    [13] OLUMOFIN F, GOLDBERG I. Revisiting the computational practicality of private information retrieval[C]//International Conference on Financial Cryptography and Data Security. Berlin: Springer, 2011: 158-172.
    [14] XU T, CAI Y. Location anonymity in continuous location-based services[C]//Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems. ACM, 2007: Article No 39. DOI: 10.1145/1341012.1341062.
    [15] ABUL O, BONCHI F, NANNI M. Never walk alone: Uncertainty for anonymity in moving objects databases[C]//Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. IEEE, 2008: 376-385. DOI: 10.1109/ICDE.2008.4497446.
    [16] LIM N, MAJUMDAR S, SRIVASTAVA V. Security sieve:A technique for enhancing the performance of secure sockets layer-based distributed systems[J]. International Journal of Parallel Emergent and Distributed Systems, 2015, 31(5):1-23. https://www.researchgate.net/publication/281123530_Security_sieve_a_technique_for_enhancing_the_performance_of_secure_sockets_layer-based_distributed_systems
    [17] KIDO H, YANAGISAWA Y, SATOH T. An anonymous communication technique using dummies for locationbased services[C]//International Conference on Pervasive Services. IEEE, 2005: 88-97. doi:  10.1109/PERSER.2005.1506394
    [18] XU T, CAI Y. Exploring Historical Location Data for Anonymity Preservation in Location-Based Services[C]//IEEE INFOCOM 2008-IEEE Conference on Computer Communications. IEEE, 2007: 547-555. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=4509698
    [19] NIU B, LI Q, ZHU X, et al. Enhancing privacy through caching in location-based services[C]//IEEE Conference on Computer Communications. IEEE, 2015: 1017-1025.
  • 加载中
图(7) / 表(3)
计量
  • 文章访问数:  143
  • HTML全文浏览量:  57
  • PDF下载量:  354
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-06-19
  • 刊出日期:  2018-07-25

目录

    /

    返回文章
    返回