匿名区域层级扩张的位置隐私保护方法

张 磊, 马春光, 印桂生

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

0 引 言

移动通信技术和定位技术的发展和使用,带来了用户对于自身位置隐私的关注[1-3]。由于在获得基于位置服务的同时需要用户提供自身位置给服务提供商,因而很多用户更关心在使用过程中自身位置隐私是否安全[3-5]。位置泛化是当前广泛使用的保护用户位置隐私的有效方法[6-8],该方法通过寻找真实匿名用户或添加虚假用户实现真实用户与k-1个匿名用户之间的不可区分,进而令攻击者无法准确识别真实用户[9-10]。但是,在寻找匿名用户的过程中,现有的隐私保护方法大多以真实用户为中心,通过对当前用户位置向周围扩张的方法寻找匿名用户或添加噪声[11-12]。针对这种情况,Yang等人[13]利用区块链在私有链范围内寻找可协作的匿名用户。Zhang等人[14]利用属性加密随机寻找混合区域内的协作用户来实现同一目的。许明艳等人[15]利用用户邻域分布感知来确定寻找匿名用户。Li等人[10]则利用时空的可翻转性来处理匿名用户的分布问题。Zhang等人[16]同时利用缓存和匿名两种方案来加强连续匿名用户的间隔处理。Peng等人[17]利用希尔伯特曲线和加密手段解决半可信中心服务器处理用户分布的问题。尽管上述方法在很大程度上能够解决真实用户位于匿名区域中心点的问题,但是若当前区域内用户离散间距存在差异,即用户分布较密的情况下很容易在较小区域内完成匿名,进而存在真实用户位于较小范围内甚至同一兴趣点进而暴露用户隐私的问题。

针对这一问题,本文提出了一种匿名区域层级扩张的方法,该方法利用希尔伯特曲线对用户所在区域用户分布程度加以量化,同时将量化结果利用N-阶层级的四叉树进行密度分层,在匿名的过程中利用分层差异实现不以用户为中心的按密度变化的匿名区域扩张。该方法一方面解决了用户位于中心区域的问题,另一方面通过密度分层,解决用户密度较高区域匿名用户过度集中导致的隐私泄露问题。最后,本文通过安全性分析对算法进行了定性分析和成因描述,同时与当前较为常用的几种同类算法在隐私保护能力和算法执行效率两个方面进行了实验比较,其结果进一步证实了本文所提算法的优越性。本文的主要贡献有:① 提出了一种利用希尔伯特曲线扩张匿名区域,实现用户匿名区域内位置不可识别的随机分布隐私保护方法;② 提出了一种利用N-阶位置区域层级四叉树密度处理方法,解决用户分布过密、用户易被识别问题;③ 通过理论分析和实验验证证明了所提方法的优越性。

1 基本思想和算法描述

通常情况下,为保护用户的位置隐私,已有的隐私保护方法一般以用户为中心,向该用户四周扩张式寻找匿名用户或添加噪声用户,以满足至少存在k-1个用户与真实用户相混淆[12, 18-19]。但是,以这种方法建立的匿名区域易被攻击者识破并寻找到用户的真实位置[20-22]。同时由于匿名用户存在分布密度差异等问题,简单地利用随机用户位置或者随机网格并不能有效防止攻击者识别用户[23-24]。因此,需要提供一种方法，不仅使用户不再位于匿名区域中心,而且还要保证参与匿名的用户位于一个用户分布密度合理的可选择分布范围。基于这样一种思想,需要满足两个基本条件:首先,用户的位置应位于攻击者无法利用历史经验或距离计算可分析的位置;其次,用户与匿名用户位置之间应是一种可调节的位置分布状态。基于上述两个基本条件,本文提出了匿名区域层级扩张的隐私保护方法。

该隐私保护方法的基本思想是:通过处理使用户不再位于匿名区域的中心位置,而且是不可猜测的随机位置,同时不会因用户分布密度的不均匀使得匿名区域过小。为实现上述隐私保护思想,一种简单的处理方法是以用户为固定位置,向四周随机扩张匿名区域,使用户位于匿名区域中的不确定位置。但是仅通过随机位置扩张并不能解决匿名用户分布过密的问题,因此在这种随机扩张的同时,还需要考虑用户分布密度,使匿名用户集合内均匀分布,防止匿名用户过度集中导致的真实位置被识别的问题。针对这样两个基本要求,本文利用网格区域的随机扩张来完成用户位置随机性的处理,同时利用层级扩张的密度四叉树来处理用户分布密度问题。

基于上述基本思想,本文所提算法的处理过程可以简要描述如下。首先,用户提交查询信息Q={R,c,k}给匿名服务器,其中R为用户所在区域,c为查询内容,k为匿名值。匿名服务器在收到用户提交的查询信息之后,查询R内用户密度,并添加到四叉树的第0层。若密度过高,则以R为初始区域绘制希尔伯特曲线并扩张一层区域空间,同时将扩张后的4个网格密度添加到四叉树第1层的节点内。在四叉树第1层随机选择一个节点,并与第0层的节点共同计算两个节点区域的用户密度。若密度合适则在上述两个区域内选择匿名用户,否则重复上述操作完成新一轮的区域扩张直至密度合适为止。这种区域扩张的处理如图1(a)所示,完成匿名空间设定后,所选择的匿名用户分布如图1(b)所示。在扩张过程中的密度存储和选择使用的四叉树如图2所示。

图1 匿名区域选择Fig.1 Anonymous region selection

图2 层级扩张的四叉树密度表示Fig.2 Quad tree density representation of hierarchical expansion

在这种层级扩张的情况下,攻击者仅能获得一个用户密度分布均匀的扩张后区域,同时由于真实用户并不位于该区域的中心,攻击者同样无法判定真实用户的具体位置。

由于区域扩张过程需要多次计算用户密度,同时每个扩张后的区域需要保持一种不确定性,因此本文引入四叉树来处理用户密度。假设用户位于图1(a)所示的网格0中,将该网格密度带入图2所示的四叉树,有第0层密度为27,当前密度过高,因此利用希尔伯特曲线进行区域扩张,并将扩张后的4个区域密度添加进四叉树第1层的节点中。在第1层随机选择一个节点(密度为17的节点),计算这两个节点的用户密度。若当前密度仍然过高,需重复上述操作,扩张到第2层和第3层后,用户密度合适,算法完成计算。此时图2所示的四叉树中深色节点表示区域选择时的密度值计算,对应图1(a)中区域编号为0,2,6,8构成的混合区域,在这些区域中寻找匿名用户,则有图1(b)所示的匿名用户分布情况。

最后,在完成层级扩张的匿名用户选择之后,用户的真实位置因希尔伯特曲线方向的差异而可能位于该区域内的任一位置,攻击者很难通过中心位置猜测以及用户密度来计算分析用户的真实位置。

2 算法实现

算法 1 匿名区域层级扩张算法输入:用户初始区域R0,当前区域用户密度D0输出:扩张后区域RN1. 获得R0内用户密度D0;2. Dt=0; 3. while (Dt+D0不满足密度要求)4. 利用希尔伯特曲线扩张区域;5. 计算扩张后每个单元格密度并带入四叉树;6. 随机选择新一层四叉树节点密度带入Dt;7. 选择的节点所表示的区域记为Rt;8. RN=R0+Rt;9. end while10. 获得扩张后区域RN;11. 在RN中执行匿名用户选择算法; 在算法1中嵌套使用了四叉树来处理节点密度,算法2给出了四叉树的密度添加和节点选择的过程。算法 2 四叉树算法输入:扩张后网格内用户密度Dg11,Dg21,…,Dg41输出:密度四叉树1. root=D0;2. for(i=1;i≤4;++i)3. root.child=Dgi;4. end5. root=随机选择root.child;∥随机选择一个叶节点作为新的根节点6. Dt为该节点密度;7. 将D0和Dt反馈给算法1;

经过算法1和算法2的共同处理,一个可以满足用户位置不在中心区域,且匿名区域内用户密度合适的扩张匿名区域形成。但是仅有这样的一个区域仍不能有效保护用户的位置隐私,还需要在该区域内按照密度要求在不同的密度网格空间寻找匿名用户。

由于匿名区域扩张所产生的每个单元格是按照用户所在位置利用希尔伯特曲线连接的,因此在地理位置上较为相近,进而也就造成了用户密度的相似性,这种相似性表现为希尔伯特曲线经过的网格编号越小用户密度越相近,因此可利用网格编号来标识用户密度,进而在匿名用户或者噪声的选择上实现用户密度的均匀分布。匿名用户选择算法给出了在建立好的扩张后的匿名区域中如何选择更具泛化性的匿名用户的处理方法。

算法 3 匿名用户选择算法输入:希尔伯特曲线标记的网格编号N={n0,n1,…,nm},用户设定匿名值k,候选用户集合U={u1,u2,…,ut}输出:匿名用户集合U'1. avg= ∑mi=1ni /m;2. U'.N=0; ∥匿名用户所在区域网格编号初始值3. while(i<=k&&U'.N≤avg)4. U'依次添加每个单元格中的随机用户;5. i=i+1;6. end7. if(U'.N≥avg)8. 用网格编号高的区域内用户替换编号低的用户;9. end10. 输出U';

经过算法3的处理可得到满足密度要求的匿名用户,这些用户均匀分布在扩张后的匿名区间内,同时用户本身也不再位于匿名区域中心位置,而是位于该区域内不确定的任意位置,因而用户的位置隐私得到了保护。

统筹推进，振兴乡村。在做好项目区建设的同时，增加发展要素，努力推进乡村振兴样板区、绿色产业集聚区、生态文明示范区、美好生活共享区建设。

3 安全性分析

通过对本文算法的描述,可知该算法的安全性取决于用户是否位于匿名区域中心以及用户分布密度和不确定性是否均匀两个方面。

对于用户分布密度和不确定性,在不扩张或扩张的情况下,算法的首要条件是满足挑选的匿名用户分布密度的均匀性,因此才要利用希尔伯特曲线编号和四叉树选择节点,所以经过算法处理得到的匿名区域是一个用户密度分布较为均匀、不会产生用户集中于同一有限区域的情况。同时,通过算法3,在扩张后的区域内,所有的匿名用户都具有很强的随机性,这种随机性也加大了攻击者对真实用户的不确定性,因而算法在隐私安全方面能够提供较好的隐私保护服务。

4 实验验证

为了验证本文所提算法能够较好地在一个扩张的区间内有效寻找匿名用户,同时又不会因用户密度分布问题泄露用户的位置隐私,将本文算法与当前一些同类的主流算法进行了实验比较。实验测试的环境为笔记本电脑CORE i7,8 GB内存,测试系统为Windows 10操作系统。实验采用模拟测试,使用Matlab 2017a对收集到的用户位置数据展开测试。测试的数据集合为公共数据集BerlinMOD Data Set在某一时刻的位置定位数据采样,用户密度计算结果均来自该采样数据。参与比较的算法选择了利用属性基加密选择匿名用户的基于同态加密的属性泛化混合区域(homomorphic encryption based attribute generalization mix-zone, HEBAG mix-zone)算法[14],利用范围感知选择匿名用户的个性化范围敏感隐私保护方案(personalized range-sensitive privacy-preserving scheme, PRPS)[25]以及传统的以用户为中心的中心区域扩张算法(简称为传统算法)[26]。实验将从真实用户所处位置的随机性、匿名用户分布密度差异性、攻击者识别真实用户的成功概率、算法执行时间以及匿名区域范围等几个方面加以比较。实验结果比较和简要成因分析将进一步证明本文所提算法的隐私保护能力和算法执行效率。

图3给出了经过各种算法处理后真实用户位置的随机性比较，是对多次请求匿名的用户位置在匿名区域中相对位置的重合概率计算得到的,即重合率越高真实用户位置的随机性越差。

图3 真实用户位置随机性Fig.3 Randomness of real user location

从图3中可以看出,由于传统算法中用户位置一般位于匿名区域中心,因此其相对位置重合率最高。PRPS算法是通过查询概率估算的区域扩张完成匿名的,但是在每个确定区域中,用户所处位置仍以较高概率位于该区域中心,因此当匿名请求次数超过70次时,其相对位置重合率趋于饱和,保持在90%左右。HEBAG mix-zone算法采用的是随机寻找属性相似用户的方法,即使用户的相对位置存在部分变化,但由于是呈扩散性的协作用户参与匿名,因此位于匿名区域中心的概率仍然很高,但要好于传统算法和PRPS算法。最后,本文所提算法主要针对的就是用户的真实位置位于匿名区域中心的问题,经过算法处理后用户的真实位置将会随机分布在匿名区域的任意位置,因此其相对位置重合率最低,在隐私保护能力方面要好于参与比较的其他3种算法。

图4给出了经过各种算法处理后匿名用户在匿名区域中的分布差异,这种差异表现在匿名用户所处匿名区域中的密度差异,因此密度差异比例越大说明当前匿名区域包含更多类型的匿名用户,真实用户的隐私保护级别越高。

图4 匿名用户分布密度差异Fig.4 Distribution density difference of anonymous users

从图4中可以看出,本文算法产生的密度差异比例最大,这是由于该算法经过希尔伯特曲线的刻画,覆盖了更为广阔的匿名区域,同时由于在不同扩张区域中选择匿名用户,参与匿名的用户可来自于不同密度区域中的不同用户,因此其密度差异极大。HEBAG mix-zone算法由于相似属性用户随机分布的特性使得其能够找到部分位于不同密度区域的协作用户参与匿名,但跨越的密度差异区域有限。PRPS算法查询概率估算的区域扩张同样能够包括部分差异密度区域的匿名用户,但单个匿名区域未能产生密度差异。最后,传统算法一般以用户为中心寻找匿名用户,通常选择的都是当前用户最近邻用户参与匿名,其密度差异最低。

图5给出了攻击者通过匿名区域范围以及用户相对位置对不同算法展开攻击从而识别真实用户的概率差异。

图5 攻击者识别真实用户的成功概率Fig.5 Success probability of attacker identifying real user

从图5中可以看出,传统算法仅通过这两项标准被攻击识别的概率最高,且不能随着匿名用户数量的增加而降低,这是由于传统算法一般需真实用户位于匿名区域中心。PRPS算法同样由于真实用户位于扩张的匿名区域中心而导致攻击成功率相对较高。HEBAG mix-zone算法虽然能够通过随机属性降低用户相对位置影响,但是由于HEBAG mix-zone内匿名用户有限,因而其攻击成功率虽然低于PRPS算法,但仍高于本文算法。最后,本文算法一方面解决了用户密度分布的问题,使真实用户可能位于匿名区域中的任意位置；另一方面，采用的四叉树N-阶层级扩张,又将匿名区域进行了扩充,因而其保护下的真实用户被攻击者识别的概率最低。

图6给出了在一般情况下各算法的执行时间。从图6中可以看出,所有算法均随着匿名用户数量的增加导致算法执行时间增长。在众多算法中,HEBAG mix-zone算法的执行时间最高,这是由于该算法需要利用移动设备去完成加解密操作,因此寻找时间相对较高。其次是传统算法,因传统算法主要是在一个受限的匿名区域中寻找匿名用户,当该区域用户数量较少时耗费的寻找时间相对较多。PRPS算法虽然可以通过区域扩张寻找匿名用户,但是这种扩张是在完成查询概率计算之后才被执行,仍存在传统算法的弊端,但要好于传统算法。本文算法由于利用希尔伯特曲线包含了最大匿名用户寻找区间,提升了匿名用户寻找效率,因此其算法执行时间最低。

图6 算法执行时间Fig.6 Algorithm running time

图7给出了不同算法产生的匿名区域范围。从图7中可以看出,传统算法并不因匿名用户数量的变化产生较大的匿名区域变化,这主要是因为传统算法一般在有限的区域内不考虑用户差异以及用户分布,直接选取了大量用户,且这些用户位于同一较小区域的概率极高,因而其匿名区域范围始终保持一种较低状态。HEBAG mix-zone算法虽然随机选择用户,但是HEBAG mix-zone的范围有限,因此该算法虽然好于传统算法,但是仍存在提升空间。PRPS算法利用查询概率计算提升了区域扩张能力,但是在单次查询中其匿名范围仍然有限。本文所提算法主要是一种区域扩张算法,利用希尔伯特曲线建立了最广阔的匿名区域空间,因此在匿名区域上要好于其他算法。

图7 匿名区域范围Fig.7 Anonymous region range

5 结 论

传统的基于位置服务的隐私保护算法在寻找匿名用户时,由于寻找策略问题使得真实用户位于中心位置的概率过高,且当前流行的一些改进方法对这一问题的解决有限。因此,针对这一问题,提出了匿名区域层级扩张的位置隐私保护算法。该算法利用希尔伯特曲线结合N-阶层级四叉树的离散差异计算,建立了最广泛的匿名区域,同时由于通过层级递进扩张匿名区域,使得真实用户位置产生了最大的不确定性,因此相对于传统算法能够更好地保护用户位置隐私。在利用模拟实验对该方法与其他几种同类算法的比较中可以看出,该算法相对于同类算法不仅在隐私保护能力方面具有优势,在算法执行效率方面同样要好于同类算法,因而更具部署优势。