抗轨迹差异识别攻击的相似轨迹实时生成方法

张磊，马春光，杨松涛，郑晓东,3

(1.哈尔滨工程大学 计算机科学与技术学院,黑龙江 哈尔滨 150001； 2.佳木斯大学 信息电子技术学院,黑龙江 佳木斯 154007； 3.齐齐哈尔大学 应用技术学院,黑龙江 齐齐哈尔 1610061)

抗轨迹差异识别攻击的相似轨迹实时生成方法

张磊1,2，马春光1，杨松涛1,2，郑晓东1,3

(1.哈尔滨工程大学 计算机科学与技术学院,黑龙江 哈尔滨 150001； 2.佳木斯大学 信息电子技术学院,黑龙江 佳木斯 154007； 3.齐齐哈尔大学 应用技术学院,黑龙江 齐齐哈尔 1610061)

用户使用基于位置服务进行连续查询产生的移动轨迹可能会遭受轨迹差异识别攻击，进而造成用户个人隐私的泄露问题，本文依据轨迹r-匿名的思想，提出了一种相似轨迹实时生成方法用来保护用户的个人位置隐私。该方法通过匿名服务器对用户提交进行需要匿名的真实位置计算，实时生成、筛选建立虚假位置集合，利用虚假位置形成的位置轨迹与真实轨迹之间的相似性模糊了真实轨迹，降低了生成的虚假轨迹被攻击者识别的概率，实现了连续位置查询中的实时轨迹匿名。通过性能分析和模拟对比实验验证，进一步说明了本文所提出算法的隐私保护效力和算法执行效率。

基于位置服务；连续查询；隐私保护；虚假位置；实时轨迹匿名；相似轨迹

随着移动通信和定位技术的不断发展，基于位置服务(location based services, LBSs)逐渐深入到人们的日常生活。然而人们在享受这种服务带来便利的同时，又不可避免地要面对隐私泄露问题。针对这一问题，研究者提出了以k-匿名[1]、l-多样性[2]、用户协作[3]、锚点[4]和PIR[5]等为主的基于快照服务的隐私保护方法。但是这些方法均不能有效地保护连续位置服务中的轨迹隐私。针对这一情况，研究者分别从单元泛化[6]、轨迹聚类[7]和全局轨迹相似[8]等方面提出轨迹隐私保护方法。Gao等详细分析并总结了这些方法，发现它们更适合对已生成的轨迹加以保护，并不能有效的保护实时连续位置服务中的用户隐私[7]。学者又陆续提出了基于匿名[9-13]和mix-zone[14-16]的隐私保护方法。尽管这些实时的隐私保护方法能够有效保护用户的位置，但是在掌握用户移动方式的情况下，攻击者还是能够通过产生的轨迹差异识别出用户的真实轨迹，进而获得用户隐私。因此，本文基于轨迹匿名和实时连续位置服务隐私保护的特点，提出了一种相似轨迹实时生成方法，通过实时生成相似轨迹完成轨迹匿名，弥补轨迹隐私保护方法无法适应实时服务，以及实时连续服务隐私保护方法无法保障轨迹匿名的不足。

1 隐私保护系统架构

由于移动通信设备计算能力有限，本文采用三层中心服务器架构。如图1所示，该架构包含3个实体：移动用户(mobile user, U)，匿名服务器(anonymous servers, AS)，服务提供商(location service provider, LSP)。U携带定位设备(例如：智能手机、GPS定位模块)，能够精确定位自身位置并与LSP交互，进而享受位置依赖服务。但是，U的通信和计算能力有限。AS负责计算相似轨迹位置，具有较强的计算和数据处理能力。LSP能够为User或AS提供服务，具有极强的数据分析和处理能力。本文假设U和AS是可信的，而LSP是半可信的，即LSP在严格执行协议和算法的前提下，同时使用收集到的位置信息和背景知识推断U的敏感信息，甚至LSP可能将U的敏感信息出卖给不友好的第三方。

图1 三层系统架构示意图Fig.1 The system architecture of three layers

定义1 连续位置服务是指User向LSP发起多次请求，并获得连续服务反馈的过程。这些请求可表示为Q=(ID,Li,I,P)。其中：ID表示用户的身份标识；Li=(xi，yi)表示查询设备所处位置；I表示时间间隔；P表示查询兴趣点，如：餐厅、医院等。

定义2 轨迹差异识别攻击是指攻击者通过获取用户的移动速度、移动方向等移动信息，比较识别出移动用户产生轨迹的攻击方法。其攻击成功概率可表示为

式中：tm为攻击者根据移动信息建立的轨迹，sim表示轨迹相似性。

2 相似轨迹实时生成方法

相似轨迹实时生成方法的基本原理就是通过实时产生相似的虚假轨迹完成轨迹匿名。为实现相似轨迹匿名，需要经过初始匿名位置选择、相似轨迹位置计算和生成位置筛选等3个步骤。其中初始匿名需选择分布在多个兴趣点区域中的位置，以降低产生伴随轨迹的概率。

定义3 轨迹r-匿名是指LSP同时获得包括真实轨迹t在内的至少r条相似轨迹，这些轨迹使得LSP无法通过轨迹长度和轨迹方向之间的差异，识别出t的隐私保护过程。

定义4 伴随轨迹是指用户行进过程中经过共同的兴趣点，这些兴趣点可被校正整合为同一轨迹的r条相似轨迹。

定义5 相似轨迹位置区域是一个相似位置集合，是在方向偏差和相似度阈值内，以二元二次方程4个根为顶点建立的区域。连接前次匿名位置与该区域内任一位置可建立相似轨迹。

定义6 不可到达位置是指生成的虚假位置l′∉T，其中T表示LSP获得的所有历史轨迹集合。

2.1 相似轨迹位置计算

通过计算相似轨迹位置，获得满足生成相似轨迹的位置集合，并经过位置筛选建立相似轨迹。关于相似轨迹位置计算，本文借鉴Gao等关于相似轨迹区段计算的基本思想[7]，利用平行距离量化轨迹长度，夹角距离量化方向，使用两者之和来量化相似程度。在生成位置的过程中，根据初始匿名位置，计算至少r-1个虚假轨迹来完成轨迹匿名。以两条轨迹为例阐述相似轨迹生成方法。

假设用户A和虚假用户B分别以pa和pb为初始位置建立匿名组，若要计算B的虚假位置pb+1，且连接用户A、B的相邻查询位置能够产生相似轨迹，需要通过pa、pb和A的后续查询位置pa+1使用平行距离和夹角距离建立方程，进而计算得出pb+1的位置。令La和Lb是分别以pa、pa+1和pb、pb+1为两端位置的轨迹长度，θ表示用户制定的两条轨迹之间存在的夹角阈值。由于pa+1已知，通过式(1)、(2)联立建立关于pb+1的二元二次方程，从而计算获得pb+1。获取相似轨迹位置区域计算所需要的平行距离和夹角距离公式可分别表示为

(1)

(2)

式中：A,B表示用户A、B的移动向量；ω‖、ωθ分别代表平行距离和夹角距离的权重，由于两个距离公式均对轨迹相似程度产生影响，因此ω‖,、ωθ的默认值设定为1。其中两条轨迹之间的相似程度可表示为

(3)

两个轨迹区段之间的轨迹距离可表示为

(4)

2.2 筛选生成位置

为降低攻击者识别虚假位置的概率，需对生成的轨迹相似位置加以筛选。本文主要针对生成位置的实际可到达性加以描述。如图2所示的虚假用户U，经过计算后可获得由A、B、C3个位置组成的相似轨迹位置区域。由于U与A之间存在建筑物阻挡，U与C之间存在河流阻挡。根据可到达情况，AS只能选择B作为匿名位置，建立匿名组。

图2 生成位置筛选示意图Fig.2 The refine of dummy locations

综合初始匿名、相似轨迹位置计算和筛选生成位置的思想，设计了相似轨迹生成算法。

算法1 相似轨迹生成算法

输入：用户当前查询位置pi+1与前次位置pi以及虚假前次位置pj

输出：pj+1位置集合，该集合中位置满足轨迹匿名

1) Procedure:AS收到请求Q;

2) 随机选择2r-1个位于不同兴趣点的匿名位置构成集合B；

3) hreshold_sim=min_sim(A,B);thresholdθ=Max_θ; //设置相似性和夹角阈值；

4) Ps=null; //目标位置集为空；

5)foreveryB //对于每个虚假位置；

6)Dist(A,B)=(1-threshold_sim)/threshold_sim;

7)A·B=dot(‖pi+1-pi‖,‖pj+1-pjV);

8)dθ=thresholdθ=

9)d‖=Dist(A,B)-thresholdθ=‖pi+1-pi‖-‖pj+1-pj‖;//平行距离；

10) pj+1=solve(d‖,dθ));//解关于pj+1二元二次方程；

11) 使用pj+1建立位置相似区域；

12)if当前区域可从pj到达；

13) 随机选择任一位置作为 pc;

14) S=S+ pc;

15)else

16)break; //匿名失败

17)endif

18)End

19)EndProcedure

算法1根据每一个参与前次匿名的位置，计算所得虚假位置保存在S中，在连续匿名过程中重复3)～19)，计算获得能够产生相似轨迹的位置，连接后获得相似的匿名轨迹，最终实现轨迹r-匿名。

3 性能分析与实验验证

3.1 性能分析

(5)

由此可得ui=uj，即用户ui和uj无法区分，进而可知攻击者通过轨迹差异识别攻击无法在r条相似轨迹中准确识别出待攻击用户。

为实现轨迹r-匿名，需要在每个连续查询间隔内生成r条相似轨迹。在最好的情况下，其时间复杂度为O(r-1)。若每个生成位置均不可到达则需调整相似参数，此时算法的执行时间复杂度为2O(r-1)。由此，可得出算法1的时间复杂度为O(sum)=O(r-1)+2O(r-1)=O(r-1)。综上，可以认为该算法的时间复杂度取决于用户设定的轨迹匿名阈值和后续相似位置的可到达性。由于相似轨迹实时生成方法是基于欧氏空间提出，可认为在多数情况下能够找到可达的相似轨迹位置。因此，在一般情况下，该算法的时间复杂度为O(r)。

3.2 环境配置

本实验中所涉及方法是在Windows 7系统上使用Matlab 7来进行模拟的，运行环境为1.70GHz Intel Core i5，内存4 GB。实验数据采用BerlinMOD Data Set提供的真实位置数据，并随机选择城市中心位置进行实验验证。同时，本文加入以下方法进行对比：LTPPM[10]、EGCA[11]和CLAPPINQ[13]，其中LTPPM主要针对轨迹差异识别攻击。表1为实验中采用的相关参数阈值。

表1 实验参数阈值设定表

3.3 结果比较

如图3所示，本文提出方法所产生的轨迹与基轨迹之间极为相似，可以实现轨迹匿名。

图3 轨迹相似性对比Fig.3 The comparison of trajectories

通常，在轨迹隐私保护中需降低伴随轨迹产生率，以防止攻击者通过共同的兴趣点识别出真实轨迹。从图4中可以看到，随着匿名值增大，各算法产生伴随轨迹的概率逐渐增加。但本文所提出的方法由于对初始位置加以限制，其伴随轨迹产生率要远低于其他算法。其他算法中LTPPM相对较好，这是由于部分相距较远的协作用户降低了伴随轨迹的产生概率。最后，CLAPPINQ和EGCA由于随机选择匿名用户，使得伴随轨迹的产生率明显高于另2种算法。

从图5中可以看到各算法随匿名值增大，匿名用户被攻击者识别的概率逐渐增加。本文所提出的算法由于对生成的虚假位置进行筛选，降低了攻击者成功剔除匿名位置的概率，因而与其他算法相比具有较低的识别率，进一步保护了用户的位置轨迹隐私。EGCA由于随机选择匿名用户，使得其匿名用户识别率最高。CLAPPINQ和LTPPM由于匿名用户变更以及真实轨迹被匿名轨迹所围绕，使得其识别率要高于本文算法。

图4 产生伴随轨迹概率Fig.4 The probability of concomitant trajectories

图5 匿名用户识别率Fig.5 The probability of identification

在执行效率的对比实验中，根据匿名值变化，查看各算法在执行时间上的差异。同时，查看在连续多次执行过程中，相同匿名值限定下的连续执行时间。最后比较各算法的匿名成功率。下面以3次连续查询为例，查看各算法随匿名值增大导致的执行时间变化。

从图6中可以看出，直接选择用户匿名的CLAPPINQ和EGCA方法其执行时间较短，且CLAPPINQ由于采用预计算的方式，其执行时间最短，但这两种方法均无法有效抵抗轨迹差异识别攻击。LTPPM通过用户协作建立相似轨迹来抵抗轨迹差异识别攻击，该方法既涉及到寻找协作用户，又需对匿名轨迹进行筛选，因此其时间效率受匿名值变化影响最大。本文方法仅处理相似轨迹位置，无需寻找协作用户，与LTPPM相比具有更好的执行效率。

在图7中可以看到，相同参数连续运行过程中各算法的执行时间。在这些算法中，本文所提出的算法在计算出匿名位置之后，需进行相似轨迹位置筛选，其执行时间要高于直接选择用户进行匿名的CLAPPINQ和EGCA，但低于查找协作用户建立相似轨迹的隐私保护算法LTPPM。

图6 随匿名值变化的执行时间Fig.6 The performance with r

图7 随重复次数变化的执行时间Fig.7 The performance with running times

从图8中可以看到各算法的匿名成功率。EGCA由于使用单匿名框，其匿名成功率受匿名次数影响较小。LTPPM因需要连续寻找能够参与匿名的协作用户，其匿名成功率急速降低。本文算法同样因为生成位置筛选，使得随连续匿名申请次数增加导致成功率逐渐下降。CLAPPINQ方法由于采用预计算，其成功率要好于LTPPM与本文方法。

图8 匿名成功率Fig.8 The success ratio of anonymity

综上，从两组实验的对比中可以看出，本文所提出的相似轨迹实时生成方法尽管在执行效率上优势并不明显(如图6～8)，但与同类方法相对比该方法能够更好地抵抗轨迹差异识别攻击(如图4、5)。

4 结论

1)本文分析了攻击者通过轨迹差异获取用户隐私的攻击行为，利用攻击成功率量化了这种攻击行为。

2)针对这种攻击行为基于轨迹相似性计算的思想，提出了相似轨迹实时生成方法，利用轨迹方向、轨迹长度的量化以及位置筛选实现了连续位置服务过程中的位置隐私保护。

3)本文通过性能分析和实验结果比较进一步证明该方法在增强用户位置轨迹隐私的同时具有较好的执行效率。今后的工作将在如何降低AS对执行效率的影响以及提高匿名成功率等方面展开。

[1]GRUTESER M, GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking[C]// International Conference on Mobile Systems, Applications, and Services. San Francisco, USA, 2003:31-42.

[2]BAMBA B, LIU L, PESTI P, et al. Supporting anonymous location queries in mobile environments with privacygrid[C]// International Conference on World Wide Web. Beijing, China, 2008:237-246.

[3]REBOLLO-MONEDERO D, FORNÉ J, SOLANAS A, et al. Private location-based information retrieval through user collaboration[J]. Computer communications, 2010, 33(6): 762-774.

[4]MAN L Y, JENSEN C S, M∅LLER J, et al. Design and analysis of a ranking approach to private location-based services[J]. ACM transactions on database systems, 2011, 36(2): 475-486.

[5]GHINITA G, KALNIS P, KHOSHGOZARAN A, et al. Private queries in location based services: anonymizers are not necessary[C]// International Conference on Management of Data. Vancouver, Canada, 2008: 121-132.

[6]AL-HUSSAENI K, FUNG B C M, CHEUNG W K. Privacy-preserving trajectory stream publishing[J]. Data & knowledge engineering, 2014, 94: 89-109.

[7]GAO S, MA J, SUN C, et al. Balancing trajectory privacy and data utility using a personalized anonymization model[J]. Journal of network & computer applications, 2014, 38(1): 125-134.

[8]GURUNG S, LIN D, JIANG W, et al. Traffic information publication with privacy preservation[J]. ACM transactions on intelligent systems & technology, 2014, 5(3): 1-26.

[9]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.

[10]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.

[11]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.

[12]JIA J, ZHANG F. Nonexposure accurate location k-anonymity algorithm in LBS [J]. Scientific world journal, 2014(1): 149-168.

[13]HASHEM T, KULIK L, ZHANG R. Countering overlapping rectangle privacy attack for moving kNN queries [J]. Information systems, 2013, 38(3): 430-453.

[14]PALANISAMY B, LIU L, LEE K, et al. Anonymizing continuous queries with delay-tolerant mix-zones over road networks[J]. Distributed & parallel databases, 2014, 32(1): 91-118.

[15]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.

[16]SUN Y, ZHANG B, ZHAO B, et al. Mix-zones optimal deployment for protecting location privacy in VANET[J]. Peer-to-Peer networking & applications, 2015, 8(6): 1108-1121.

本文引用格式：

张磊，马春光，杨松涛，等. 抗轨迹差异识别攻击的相似轨迹实时生成方法[J]. 哈尔滨工程大学学报， 2017， 38(7): 1173-1178.

ZHANG Lei, MA Chunguang, YANG Songtao, et al. Real-time similar trajectory generation algorithm for resisting trajectory difference identification attack[J]. Journal of Harbin Engineering University， 2017， 38(7): 1173 -1178.

Real-time similar trajectory generation algorithm for resisting trajectory difference identification attack

ZHANG Lei1,2, MA Chunguang1, YANG Songtao1,2, ZHENG Xiaodong1,3

(1.College of Computer Science And Technology, Harbin Engineering University, Harbin 150001, China; 2.College of Information And Electronic Technology, Jiamusi University, Jiamusi 154007, China; 3.College of Applied Technology, Qiqihar University, Qiqihar 161006, China)

To address the problem of a trajectory difference identification attack when a user uses location-based services for continuous queries, this paper provides an algorithm for generating a similar real-time trajectory to protect the user’s personal privacy based on trajectoryr-anonymity. The algorithm utilizes an anonymous server to generate a set of dummy locations in real time with the real location of the user, and these locations are composed of similar trajectories of the real user to make the real trajectory fuzzy. The probability of successful trajectory difference identification attack is then reduced. This algorithm achieves real-time trajectory anonymity in continuous location queries. Performance analysis and simulation with other algorithms further verify the effectiveness of the presented algorithm in protecting a user’s privacy, as well as the efficiency of the algorithm.

location based service; continuous query; privacy preservation; dummy location; real time trajectory anonymity; similar trajectory

2016-05-20.

日期：2017-04-26.

国家自然科学基金项目(61472097);高等学校博士学科点专项科研基金项目(20132304110017);黑龙江省自然科学基金项目(F2015022).

张磊(1982-),男, 讲师,博士研究生； 马春光(1974-),男,教授,博士生导师.

马春光,E-mail：machunguang@hrbeu.edu.cn.

10.11990/jheu.201605070

TP311

A

1006-7043(2017)07-1173-06

网络出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20170426.1802.082.html