基于随机网格的位置隐私保护方法

杨松涛, 王慧强, 马春光

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

0 引 言

基于位置服务(location-based services, LBS)是移动互联网中的典型应用。通常,LBS系统包括移动设备、定位系统、通信网络和LBS提供商4个主要部分。用户使用移动设备通过定位系统获得位置信息的过程[1-2]可表示为:移动用户按照服务提供商要求生成服务请求,该请求为四元组,其中,u代表用户身份标识,(x,y)代表用户二维平面坐标,c代表查询内容,t代表查询的时间。移动用户在生成该请求以后将其发送给LBS提供商。

但是,在这个服务过程中移动用户的位置信息可能会受到隐私威胁。位置信息可以作为一个重要的因素被定性和定量的分析[3-4]。例如:人们的行动轨迹本身可被追踪,在现有的定位技术下,形成了一个近似轨迹,该轨迹可能包含有移动用户更多的时空关联信息。当这些信息被缺乏职业道德或者出于商业利益的LBS提供商所获得时,极有可能会造成用户个人隐私的泄露,甚至产生可能威胁移动用户个人安全的事件发生。

针对隐私泄露问题,典型的方法是在用户与LBS提供商之间增加一个可信的第三方服务器,由其使用位置k-匿名技术或位置模糊技术为用户提供隐藏保护。近年来,基于这两种技术，研究者提出了大量的[5-10]隐私保护方法。随着研究的深入,人们更关心隐私的个性化问题,进而利用k-匿名模型[11-12]允许用户自由调整个人隐私要求和最大时空容忍度,同时缩小匿名集的势。基于差分隐私模型,相关研究人员又提出了地理空间的限制下的隐私保护模型[13]。

然而,用户即使采用了一定的针对位置的隐私保护方法,攻击者还是可以通过误差轨迹和精确轨迹的相似度拟合的方法,断定用户身份与轨迹的关联关系,进而暴露用户的轨迹以及实时位置隐私。这种关联关系可表现为移动用户公开的查询内容与潜在的位置坐标之间的有效关联性。

针对这种利用关联关系的攻击行为，希尔伯特匿名算法(Hilbert cloak, HC)[14]定义了互质性概念,降低了同一匿名集的用户对于匿名区域的依赖度相同。缓存隐藏[15]借鉴混合区域和路径混淆的优点,采用一阶马尔可夫模型预测路径,进而实现在交叉点处匿名,使得攻击者无法确定用户路径和查询。CoPrivacy[16]扩展了SpaceTwist,设计了一种新的锚点产生策略,通过用户之间协作形成匿名组,利用该组的密度中心代替真实位置发出查询,进一步隐藏了用户的真实位置。基于假数据的轨迹隐私保护方法[17]通过假轨迹对原始数据进行干扰,使攻击者无法区分用户的真实位置。但这些基于空间区域内模糊位置和降低位置信息空间粒度的方法无法保障在用户较少环境下使用。针对这一问题,本文提出了基于随机网格的位置隐私保护方法,该方法利用多网格融合来隐匿移动用户的真实位置,通过网格内兴趣点与用户位置的模糊性,以及网格的不规则变化来切断查询与位置之间的关联关系,保护用户的位置查询隐私。该方法具有较好的隐私保护能力和算法执行效率。

1 系统模型

本文所采用的系统模型包括3个部分,即查询用户(query issuer,QI)、位置匿名服务器(location cloak server,LCS)和LBS服务器(LBS server,LBSs)。各部分之间使用安全通道传输数据(例如SSL)。在如图1所示的系统模型中,攻击者攻击遵循Honest-but-Curious模型,即LBSs在严格执行协议和算法的前提下,同时使用收集到的位置信息和背景知识推断用户的敏感信息。

图1 LBS系统结构Fig.1 System architecture of LBS

依照图1所示的系统模型,可确定以下4个基本假设:

假设1LBSs和LCS是半可信的,即为用户提供服务的同时,但可能直接或间接泄露用户的隐私信息。

假设2攻击者可以从公共数据库(例如:电话黄页、家庭住址等)获得先验知识。同时,攻击者具备统计分析和推理能力,可以利用匿名信息和先验知识形成后验知识。

假设3移动用户可自由选择匿名度,并且其客户端具有一定的计算和通信能力。

假设4匿名过程和算法都是公开的。

为了便于后续描述,本文给出以下定义：

定义1位置轨迹不可追踪性。位置轨迹是按时间排序的位置序列,可以表示为

T={Ti,(x1,y1,t1),…,(xn,yn,tn)}

(1)

式中,Ti表示该位置轨迹的标识符；(xi,yi,ti)(i=1,2,…,n)表示移动对象在ti时刻的位置坐标为(xi,yi),其中ti为采样时间。位置轨迹不可追踪指LBSs利用公共信息库和用户查询样例信息分析出该用户位置轨迹的概率很低。

定义2身份不可关联性。用户集合表示为U={u1,u2,…,uk},查询内容表示为c。匿名集内用户身份不可关联是指LBSs关联ui(i=1,2,…,n)与c之间的概率很低。k-匿名度量是针对位置隐私保护最流行的度量标准,量化的匿名度k可以有效地度量不可关联性,k值越大,不可关联性越好。

2 基于网格的位置隐匿方法

2.1 网格内用户数量的更新过程

如果每个移动用户周期性地向LCS更新位置信息,则会带来巨大的网络负载。而且,LCS获得用户精确的位置更新数据,就可以追踪用户的轨迹,进而暴露了用户的位置轨迹隐私。

如图2所示,本文将LBSs服务区域划分为若干个彼此相邻的正方形网格,每个单元格被赋予一个序号。

图2 网格图Fig.2 Grid chart

鉴于无线传感器网络受到射频芯片通信距离的限制,单个移动节点仅能够知道邻居节点的信息。如图3所示,我们采用洪泛法探测网格中的移动节点数量。网格内每个节点执行如下位置更新算法。

算法1位置更新算法

(1) 初始化状态,所有节点向LCS更新所在网格的信息;

(2) 从离散的整数集合[0,1,…,N]中随机选取一个数n,等待n×t的时间后执行洪泛法;

(3) 计算节点所在的网格;

(4) 通过洪泛方式向网络传播位置树组建消息;

(5) 依据位置树计算网格内的节点数量;

(6) 向LCS更新网格内的移动用户数量。

图3 位置更新Fig.3 Location update

2.2 网格匿名查询过程

本文采用多个随机的、离散的网格实现位置k-匿名、网格l-多样性和位置模糊的目的。

定义3网格查询(Gq)。Gq以四元组形式表示,表达式为

Gq=(uid,gs,k,l,E(c),t)

(2)

式中，uid代表用户身份的假名;gs代表用户所在的网格序号;k代表用户要求的匿名度;l代表用户要求的网格数量;E(c)代表使用LBSs公钥加密的查询内容;t代表当前查询时间。

定义4匿名查询(Cq)。Cq以三元组形式表示,表达式为

Cq=(uid,{gi,…,gi+l},E(c),t)

(3)

式中,{gi,…,gi+l}代表随机网格的集合。

定义5标记查询(Sq)。Sq以三元组形式表示,表达式为

Sq=(uid,s,t)

(4)

式中,s代表用户随机生成的密钥。

根据以上定义可得到随机网格位置匿名算法,该算法在LCS内执行。

算法2随机网格位置匿名算法

(1) 依据Gq,提取gs,k,l,E(c);

(2) 随机选取l-1个网格;

(3) 判断网格gs和随机选取的网格中的用户总数量是否大于k;如果大于k,执行下一步,否则回到第(2)步;

(4) 向LBSs发出匿名查询Cq。

如图4所示,网格匿名查询过程如下:

(1) 用户向LCS发出网格查询Gq,同时向LBSs发出标记查询Sq;

(2) LCS执行网格位置匿名算法;

(3) LBSs对l个网格分别进行最近邻查询,查询结果集为P={pi,…,pi+l},其中,pi代表对序号为gi网格的查询结果集合;

(4) LBSs使用用户提供的密钥加密Es(P)={Es(pi),…,Es(pi+l)},扰乱Es(P)内元素顺序,并计算网络序号与加密数据的对应关系表;

(5) LBSs将扰乱的Es(P)发送给LCS,将对应关系表发送给查询用户;

(6) 用户根据对应关系表计算自身网格对应的数据元素序号j,向LCS检索第j个数据;

(7) LCS向用户发送Es(Pj);

(8) 用户解密后获得最终结果。

图4 网格匿名查询Fig.4 Grid anonymous query

2.3 隐私性分析

匿名性、位置轨迹不可追踪性和身份不可链接性是度量隐私保护水平的主要指标,相关的研究工作都是围绕这3个指标来探讨LBS隐私保护技术的隐私保护能力。在本文方法中,移动用户、LCS和LBSs都是半可信的。首先,用户没有暴露具体的位置数据给LCS和LBSs,满足位置轨迹不可追踪性。其次,LCS通过随机网格匿名实现了位置k-匿名,满足了身份不可链接性。最后,通过非对称加密方法保证了LBSs资源不被LCS恶意窃取。

3 仿真实验

通信量和计算时间是衡量LBS系统可用性的重要性能指标。本文对所提出的方法和基于位置k-匿名的两种经典方法HC[14]和隐私网格(privacy grid,PG)[9]进行比较分析,阐述随机网格匿名方法的可用性。实验使用C#语言编写匿名算法和网格匿名查询,程序在Intel 酷睿i5处理器,4GB内存的Windows7平台上运行。移动对象数据集以城市Oldenburg为例,由网络移动目标生成器(network-based generator of moving objects,NGMO)生成。默认参数值如表1所示。

表1 实验参数表

第1个实验测试网格大小对隐私度的影响。如图5所示,如果网格太小,在连续查询过程中,LCS能够追踪用户的行动轨迹,原因是网格内的移动用户数量无法保证,进而无法保障用户隐私;如果网格过大,虽然可以保证匿名度,但是增加了LBSs的计算量和通信量。

图5 网格对隐私度的影响Fig.5 Effect of grid on privacy

本文采用动态调整网格方式解决以上问题,如图6所示,LCS根据用户位置更新情况,动态合并移动用户数量少的网格,并定期向用户发布。利用动态网格解决当前区域用户数量过少对匿名效果的影响问题。

图6 动态网格Fig.6 Dynamic grid

第2个实验测试匿名网格数量对通信量(候选POIs的数量)和计算量(平均计算时间)的影响。如图7所示,随着匿名网格数量的增加,3种方法的候选POIs的数量和平均计算时间都线性增长,随机网格隐匿(random grid cloak ,RGC)方法所受影响更大。这是符合现实情况的,用户要求的隐私度越高,即匿名网格的数量越多,隐私度提高的同时降低了LBS系统运行的性能。

图7 匿名网格的影响Fig.7 Impact of anonymous grid

第3个实验测试匿名度k对通信量(候选POIs的数量)和计算量(平均计算时间)的影响。如图8所示,随着k值的增加,3种方法的候选POIs的数量和平均计算时间都线性增长,RGC方法变化不大。原因是RGC方法容易实现位置匿名,而且在有大量用户的环境下匿名区域受k值的影响很小。

图8 匿名度的影响Fig.8 Impact of anonymous degree

第4个实验测试用户数量N对通信量(候选POIs的数量)和计算量(平均计算时间)的影响。如图9所示,随着N值增加,3种方法的候选POIs数量和平均计算时间都线性减少,RGC方法变化不大。原因是用户数量远大于用户的匿名度的要求。

图9 用户数量的影响Fig.9 Impact of user number

由此可见,本文所提出的算法通过随机网格较好地解决了当前区域用户数量对匿名效果的影响问题,同时在保护用户隐私的前提下更适合在真实环境中提供较高的服务质量。

4 结 论

当前位置隐私的研究主要基于权衡服务质量和隐私保护能力,这种“零和博弈”的观点促使位置k-匿名和位置模糊技术成为该问题研究的主流。然而,定期更新位置信息逐渐成为中心服务器结构的根本瓶颈,而且在现实情况下假设参与匿名的各方均可信也是不现实的,匿名参与者可能直接或间接泄露精确的位置信息。针对这样的实际问题,本文提出了基于随机网格的位置隐私保护方法,该方法包括位置更新算法、位置匿名算法和匿名查询过程,利用网格化的不确定性实现了连续查询过程中的轨迹不可追踪性和身份不可关联性。同时,本文针对所提出的方法在效率和服务质量方面进行了分析和实验验证,进一步证明了所提出方法的隐私保护能力和实际部署下的算法执行效率。

[1] 周傲英,杨彬,金澈清.基于位置的服务_架构与进展[J].计算机学报,2011,34(7): 1156-1171.

ZHOU A Y,YANG B,JIN C Q.Location-based services: architecture and progress[J]. Chinese Journal of Computers, 2011,34(7): 156-1171.

[2] 王璐,孟小峰.位置大数据隐私保护研究综述[J].软件学报,2014,25(4): 693-712.

WANG L, MENG X F. Location privacy preservation in big data era: a survey[J]. Journal of Software, 2014, 25(4): 693-712.

[3] 冯登国,张敏,李昊.大数据安全与隐私保护[J].计算机学报,2014,37(1): 246-258.

FENG D G, ZHANG M, LI H. Big data security and privacy protection[J].Chinese Journal of Computers, 2014,37(1): 246-258.

[4] ACQUISTI A, BRANDIMARTE L, LOEWENSTEIN G. Privacy and human behavior in the age of information[J].Science,2015,347(6221):509-514.

[5] 张磊, 马春光, 杨松涛, 等. 基于轮廓泛化的位置隐私保护模型及方法[J]. 系统工程与电子技术, 2016, 38(12): 2894-900.

ZHANG L, MA C G, YANG S T, et al. Location privacy protection model and algorithm based on profiles generalization[J]. Systems Engineering and Electronics, 2016, 38(12): 2894-900.

[6] NERGIZ M E, GOK M Z. Hybrid k-anonymity[J]. Computers & Security, 2014,44(2): 51-63.

[7] SCHLEGEL R,CHOW C Y,Huang Q, et al. User-defined privacy grid system for continuous location-based services[J]. IEEE Trans.on Mobile Computing, 2015, 14(10):2158-2172.

[8] NI W, GU M, CHEN X. Location privacy-preserving k nearest neighbor query under user's preference[J]. Knowledge-Based Systems, 2016, 103(2016): 19-27.

[9] MOU L, LBATH A. A grid-based location privacy-preserving method for LBS users[C]∥Proc.of the Acm Sigspatial International Workshop on Privacy in Geographic Information Collection and Analysis,2014:1-4.

[10] HARA T, SUZUKI A, IWATA M, et al. Dummy-based user location anonymization under real-world constraints[J]. IEEE Access, 2016, 4(2016)673-687.

[11] DARGAHI T, AMBROSIN M, CONTI M, et al. ABAKA: a novel attribute-basedk-anonymous collaborative solution for LBSs[J].Computer Communications,2016,85:1-13.

[12] MA C G, ZHANG L, YANG S T, et al. Achieve personalized anonymity through query blocks exchanging[J]. China Communications, 2016, 13(11):106-118.

[13] 吴云乘, 陈红, 赵素云, 等.一种基于时空相关性的差分隐私轨迹保护机制[J]. 计算机学报, 2017.http:∥kns.cnki.net/kcms/detail /11.1826.TP.20170328.2325.004.html.

WU Y C, CHEN H, ZHAO S Y, et al. Differentially private trajectory protection based on spatial and temporal correlation[J]. Chinese Journal of Computers, 2017.http:∥kns.cnki.net/kcms/ detail /11.1826.TP.20170328.2325.004.html.

[14] PENG T, LIU Q, WANG G J. Enhanced location privacy preserving scheme in location-based services[J]. IEEE Systems Journal, 2017, 11(1):219-230.

[15] MEYEROWITZ J, CHOUDHURY R R. Hiding stars with fireworks: location privacy through camouflage[C]∥Proc.of the 15th Annual International Conference on Mobile Computing and Networking, 2009:345-356.

[16] 黄毅,霍峥,孟小峰. CoPrivacy:一种用户协作无匿名区域的位置隐私保护方法[J].计算机学报,2011, 34(10): 1976-1985.

HUANG Y, HUO Z,MENG X F. CoPrivacy: a collaborative location privacy-preserving method without cloaking region[J]. Chinese Journal of Computers, 2011, 34(10): 1976-1985.

[17] LEI P R, PENG W C, SU I J, et al. Dummy-based schemes for protecting movement trajectories[J]. Information Science and Engineering, 2012, 28(2): 335-350.