基于轮廓泛化的位置隐私保护模型及方法

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

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



基于轮廓泛化的位置隐私保护模型及方法

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

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

连续位置服务; 隐私保护; 用户轮廓信息; 关联攻击

0 引 言

移动用户在申请连续位置服务时产生的连续位置可按时间序列链接成位置轨迹,位置轨迹含有多种时空信息,可被攻击者利用进而获取用户的个人隐私。这种情况限制了基于快照服务的隐私保护方法[1-4]的保护效力。为有效保护位置轨迹隐私,研究者们提出了大量的隐私保护方法。在现有方法中主要存在两种方案[5]:一种将位置轨迹与其他相似轨迹泛化[6-10]模糊真实轨迹;另一种则在假设攻击者已获得部分子轨迹的前提下,通过扰乱或模糊轨迹后续位置降低攻击者识别出用户的概率[11-16]。其中相似轨迹泛化方案存在历史轨迹的时间差异可用于剔除部分匿名轨迹[7];协作轨迹因分布范围易被识别[8];单一匿名框泛化导致服务质量降低等问题[9-10]。因此,研究更倾向于扰乱或模糊后续位置的方法。

1 隐私保护模型及攻击方法

1.1 系统架构及攻击模型

由于IRDA主要应用于欧氏空间或路网环境下的位置导航以及连续最近邻查询,其移动通信设备计算能力有限,本文采用如图1所示的3层中心服务器架构。该架构包含3个实体:移动用户(mobileuser,U),中心服务器(centralservers,CS),服务提供商(locationserviceprovider,LSP)。U携带定位设备(例如:智能手机、GPS定位器等),能够精确定位并与LSP交互,但其通信和计算能力有限。CS负责轮廓信息计算,具有较强的计算和数据处理能力。LSP为User或CS提供服务,具有极强的数据分析和处理能力。本文假设U和CS是可信的LSP是半可信的,即LSP在严格执行协议和算法的前提下,同时使用收集到的位置和背景知识推断U的敏感信息,甚至LSP可能将U的敏感信息出卖给不友好的第三方。

图1 3层系统架构示意图Fig.1 System structure of three entities

为了后继内容的表述,本文对相关术语给出如下定义。

定义 1 连续位置服务是指用户User向LSP发起的连续基于位置服务申请,可表示为R=(ID, Li, t, C)。其中:ID表示用户的身份标识或假名;Li=(xi, yi)表示当前申请所处的位置;t表示时间间隔;C表示服务申请内容,如:查询最近的餐厅、加油站等。

定义 2 用户轮廓信息是指具有用户特征的唯一标识指定用户的基本信息,n种不同的用户轮廓信息可表示为PRO={pro1, pro2, …, pron}。

定义 3 轮廓关联攻击是指攻击者通过掌握的用户子轨迹L,从中获取当前用户的轮廓信息PRO,并进一步关联后续服务中的不确定位置,获得用户完整轨迹T的攻击方法。

轮廓关联攻击可通过轮廓相似度来描述。对不确定位置集合S中的任一位置l′,其用户轮廓的关联概率p可表示为已知子轨迹L中的位置l与不确定性位置l′之间的相似程度,于是有

(1)

(2)

式中,v表示轮廓信息数值;min和max分别表示最小和最大值。当p=1时表示两个位置属于同一轨迹T。

在实际环境中攻击者计算得到的p可能低于预期,此时,还可以通过排除不确定位置集合S中其他位置与l之间的关联概率较低的位置来识别真实位置。

1.2 隐私保护模型及方法

), 0≤p≤1

(3)

相似度sim可表示为

(4)

算法 1 相似轮廓信息的虚假位置生成

输入 l, l′,k,n,θ

输出 S′∥2k-1个虚假位置集合

1 S=randomchosen4klocation;∥初始位置集

2 i=0;

3while(i<=S.count)

6for(j=1;j<=n;++j)

9end

13end

14 ++i;

15if(S′.count>=2k-1)

16break;

17end

18end

第二阶段,剔除备选位置集合S′中不可到达的位置。筛选过程可按照算法2中所示加以计算。其中对于不可到达位置的判断,采用生成位置与不可到达位置集合Ur的方法。

算法 2 提交位置筛选

输入 Ur,S′∥不可到达位置集合

输出 S″∥筛选后的虚假位置集合

1 i=0;

2while(i<=S′.count)

4for(j=1:j<=Ur.count;++j)

5 c=0;

7break;

8end

9 c=c+1;∥校验所有不可到达位置

10end

11if(c==Ur.count)

13end

14 ++i;

15if(S″.count>=k-1)

16break;

17end

18end

2 性能评估

2.1 隐私度量与性能分析

由式(1)可知,攻击者根据轮廓相似程度判断某一位置是否属于该用户,进而用户轮廓关联概率可用条件概率表示,于是有

p(l′)=p(l′∈T|PROl′=PROT)

(5)

(6)

为验证IRDA能够取得最大熵,假设一个在挑战者A与用户U之间的双方博弈。A指定一个区域给U,U选定一段连续的位置T,将T中前n-1个位置发送给A,同时根据最后一个位置的轮廓信息,生成具有相似轮廓的k-1个虚假位置,U将虚假位置与最后一个位置建立集合S″后发送给A。A在集合S″中识别出T的最后位置,则A获胜。由以上博弈可以得出如下定义。

定义 5 若隐私保护方法可抵抗轮廓关联攻击,当且仅当对于匿名集合中任意两个位置存在

∀0

(7)

(8)

(9)

(10)

证毕

IRDA算法的时间复杂度主要取决于算法1和算法2表示的虚假位置生成和筛选两个阶段。算法1中的计算量取决于用户选择的k值与轮廓信息数量,其时间复杂度为O(4kn)=O(kn)。算法2的计算量取决于不可到达位置和生成位置数量,在最坏的情况下若不可到达位置为m,则该算法的时间复杂度为O(2km)=O(km)。而在最好的情况下无不可到达位置,则该时间复杂度为O(k)。由此可得IRDA的平均时间复杂度位于O(k)与O(kn+km)之间。

2.2 实验设定

为验证IRDA的效力与效率,本文将所涉及的算法在Windows7上使用Matlab7加以模拟。实验运行环境为1.70GHzIntelCorei5,内存大小为4GB。实验数据集采用BerlinMODDataSet1真实数据集中的城市中心区域,以获取较多的申请用户,并假设存在足够的CS提供保护服务。表1为实验中采用的相关参数阈值设定。

表1 实验参数阈值设定表

3 实验结果

图2展示了在攻击者掌握包括用户ID、服务时间间隔、服务内容、运动模式和查询概率等情况下,不同隐私保护方法的隐私保护熵。从该图中可以看出,CLAPPINQ和mix-zone的取值较低,这是由于这两种方法对连续位置服务中的时间间隔和服务内容的隐私保护程度相对较差。enhanced-DLS由于添加了对不同位置查询概率情况的考虑,其隐私保护效果相对较好,但这种方法主要针对快照服务,其抵抗关联攻击的能力在连续服务中表现较差。Snet由于服务时间间隔和内容并不能同时模糊,所以其熵相对较低。LTTPM的协作用户轮廓与真实用户相似度较高,但在连续服务过程中存在部分用户轮廓可被攻击者关联的情况。IRDA由于本身针对用户轮廓信息关联攻击所设计,充分考虑可能存在的用户轮廓信息,具有最好的隐私保护效果。

图2 不同算法的熵比较Fig.2 Entropy of various algorithms

从图3中可以看出各算法的匿名用户识别率。其中,由于真实轨迹被协作轨迹所包围,使得LTTPM方法的识别率最高。CLAPPINQ和Snet算法由于连续查询过程中的匿名用户差异增加识别的概率。enhanced-DLS算法扩大了用户间距,在一定程度上增加了识别难度,但是在连续匿名过程中,仍可以通过用户轮廓加以关联识别。mix-zone通过不可探测区域切断了部分轮廓关联,但是仍存在其他轮廓信息可被使用的情况。最后,IRDA使每个生成的虚假用户具有与真实用户相似的轮廓信息,最大程度地模糊了用户之间的差异,其匿名用户识别概率最低。

图3 随匿名值变化的匿名用户识别率Fig.3 Identification ratio with k

图4 随匿名值变化的隐私保护成功率Fig.4 Success ratio with k

图5 随申请人数变化的隐私保护成功率Fig.5 Success ratio with Sr

为验证隐私保护成功率,本文假设10人同时申请隐私保护,协作用户为当前区域人数的1/2。此时,随用户申请匿名值增加而产生的隐私保护的成功率变化如图4所示。从该图中可看出,由于LTTPM需要依靠协作用户来完成匿名,因此其隐私保护成功率相对较低。CLAPPINQ和mix-zone只需找到对应用户即可完成匿名,其隐私保护成功率好于LTTPM。Snet通过建立模糊路段来保护用户隐私,其隐私保护成功率取决于当前路段是否能抽象为更高层次的路段,当该路段不存在相似路段可进行路段抽象情况下,算法执行失败。最后,enhanced-DLS和IRDA方法由于采用生成虚假位置机制,使得在匿名过程中不受真实用户数量的限制,在隐私保护成功率上具有较好的表现。图5展示了在限定用户匿名度阈值情况下随申请人数变化的隐私保护成功率变化。从该图中可以看出,随申请人数变化的隐私保护成功率逐渐降低,其基本原因与随匿名值变化的隐私保护成功率变化相似。

图6展示了随用户设定的匿名度阈值增长各算法的执行时间变化。其中LTTPM由于不需对匿名用户进行筛选,算法可在最短的时间内完成。Snet和mix-zone不需随匿名值变化而改变模糊区域以及混淆空间,因此其执行时间固定。enhanced-DLS由于需要对每个生成的假位置考虑该位置存在的查询概率,其执行时间随匿名值的增加变化较大。而IRDA由于需要提取用户的轮廓信息,并同时建立虚假生成位置,其执行时间受匿名值变化影响最大。

图6 随匿名值变化的执行时间Fig.6 Execute time with k

图7 随申请人数变化的执行时间Fig.7 Execute time with Sr

图7展示了各算法随申请人数变化的执行时间差异。CLAPPINQ算法的执行时间随着申请人数的增加变化最大,该方法需要预计算所有用户的兴趣点,导致随着申请用户数量的增加,预计算的计算量增长,因此其执行时间随着申请用户数量的变化呈线性增长。其次,mix-zone的执行时间高于Snet的执行时间,这是由于随着申请人数的增加,mix-zone中不同申请用户的时间耽搁选择不同,使得算法需保持所有用户的最大耽搁时间,进而其结果高于直接生成模糊区域的Snet方法。最后,IRDA方法的执行时间相对较低,这是由于生成的部分虚假位置具有与其他申请用户相似的轮廓信息,对于生成虚假位置的复用降低了算法的执行时间。

图8 随轮廓信息变化的执行时间Fig.8 Execute time with n

从图8中可以看出Snet和mix-zone方法并未考虑轮廓信息关联攻击,其执行时间不随轮廓信息的增加而变化。IRDA方法由于考虑到用户的不同轮廓信息,在轮廓数量增加的情况下,其执行时间相应的线性增长。而其他方法由于只针对部分轮廓信息,随着轮廓信息数量的增加,提出的轮廓信息在超过其所能处理的最大数量时,其执行时间不再变化。

4 结 论

[1]GruteserM,GrunwaldD.Anonymoususageoflocation-basedservicesthroughspatialandtemporalcloaking[C]∥Proc.of the International Conference on Mobile Systems,2003:31-42.

[2]LiuF,HuaKA,CaiY.Queryl-diversityinlocation-basedservices[C]∥Proc.of the IEEE Tenth International Conference on Mobile Data Management: Systems, Services and Middleware, 2009:436-442.

[3]KhoshgozaranA,ShahabiC.Privateinformationretrievaltechniquesforenablinglocationprivacyinlocation-basedservices[M]∥Privacy in Location-Based Applications.NewYork:Springer-Verlag, 2009:59-83.

[4]Rebollo-MonederoD,ForneJ,Domingo-FerrerJ.Queryprofileobfuscationbymeansofoptimalqueryexchangebetweenusers[J]. IEEE Trans.on Dependable and Secure Computing, 2012, 9(5): 641-654.

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

[6]KatoR,IwataM,HaraT,etal.Adummy-basedanonymizationmethodbasedonusertrajectorywithpauses[C]∥Proc.of the International Conference on Advances in Geographic Information Systems,2012:249-258.

[7]GaoS,MaJF,ShiWS,etal.LTPPM:alocationandtrajectoryprivacyprotectionmechanisminparticipatorysensing[J]. Wireless Communications & Mobile Computing, 2015, 15(1): 155-169.

[8]HwangRH,HsuehYL,ChungHW.Anoveltime-obfuscatedalgorithmfortrajectoryprivacyprotection[J]. IEEE Trans.on Services Computing, 2014, 7(2): 126-139.

[9]PanX,XuJ,MengX.Protectinglocationprivacyagainstlocation-dependentattacksinmobileservices[J]. IEEE Trans.on Knowledge and Data Engineering, 2012, 24(8): 1506-1519.

[10]XueJ,LiuXY,YangXC,etal.ALocationPrivacyPreservingApproachonRoadNetwork[J]. Chinese Journal of Computers, 2011, 34(5): 865-878. (薛姣, 刘向宇, 杨晓春, 等. 一种面向公路网络的位置隐私保护方法[J]. 计算机学报, 2011, 34(5): 865-878.)

[11]MaCG,ZhouCL,YangST.Avoronoi-basedLocationprivacy-preservingmethodforcontinuousqueryinLBS[J]. International Journal of Distributed Sensor Networks, 2015(1): 1-17.

[12]HashemT,KulikL,ZhangR.CounteringoverlappingrectangleprivacyattackformovingkNNqueries[J]. Information Systems, 2013, 38(3): 430-453.

[13]YangST,MaCG,ZhouCL.LBS-orientedlocationprivacyprotectionmodelandscheme[J]. Journal on Communications, 2014, 35(8): 116-124. (杨松涛, 马春光, 周长利. 面向LBS的隐私保护模型及方案[J]. 通信学报, 2014, 35(8): 116-124.)

[14]PalanisamyB,LiuL,LeeK,etal.Anonymizingcontinuousquerieswithdelay-tolerantmix-zonesoverroadnetworks[J]. Distributed and Parallel Databases, 2014, 32(1): 91-118.

[15]PalanisamyB,LiuL.Attack-resilientmix-zonesoverroadnetworks:architectureandalgorithms[J]. IEEE Trans.on Mobile Computing, 2015, 14(3): 495-508.

[16]WangY,XiaY,HouJ,etal.Afastprivacy-preservingframeworkforcontinuouslocation-basedqueriesinroadnetworks[J].Journal of Network and Computer Applications, 2015, 53: 57-73.

[17]NiuB,LiQ,ZhuX,etal.Enhancingprivacythroughcachinginlocation-basedservices[C]∥Proc.of the IEEE Computer Communications, 2015:1017-1025.

[18]HaraT,SuzukiA,IwataM,etal.Dummy-baseduserlocationanonymizationunderreal-worldconstraints[J]. IEEE Access,2016, 4:673-687.

Location privacy protection model and algorithm based on profiles generalization

ZHANG Lei1,2, MA Chun-guang1, YANG Song-tao1,2, ZHENG Xiao-dong1,3

(1.CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin150001,China;2.CollegeofInformationandElectronicTechnology,JiamusiUniversity,Jiamusi154007,China;3.CollegeofAppliedTechnology,QiqiharUniversity,Qiqihar161006,China)

location-based service; privacy preservation; user profiles; correlation attack

2016-06-01;

2016-08-02;网络优先出版日期:2016-10-21。

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

TP

A

10.3969/j.issn.1001-506X.2016.12.32

张 磊(1982-),男,讲师,博士研究生,主要研究方向为信息安全、位置隐私保护。

E-mail:8213662@163.com

马春光(1974-),男,教授,博士,主要研究方向为密码学、信息安全。

E-mail:machunguang@hrbeu.edu.cn

杨松涛(1974-),男,副教授,博士,主要研究方向为信息安全、隐私保护。

E-mail:songtao_y@163.com

郑晓东(1981-),女,讲师,博士研究生,主要研究方向为信息安全、隐私保护。

E-mail:lnxiaodong@126.com

网络优先出版地址:http:∥www.cnki.net/kcms/detail/11.2422.TN.20161021.1059.010.html