划分子匿名区域的k—匿名位置隐私保护策略研究

　　1 引言
　　随着无线技术和移动位置技术的不断发展开拓了新的研究领域——基于位置的服务（Location Based Services， LBS），如查询基于当前位置的感兴趣点，此类服务是基于K近邻（K Nearest Neighbors， KNN）查询，即查询距离用户最近的K个可能目标。例如查询“离我最近的工商银行”、“距离我25米内最近的饭店/加油站”等，相应的，用户在提出此类查询的时候将不得不把自己的精确位置包含在查询中发送给服务提供商，换句话说，就是用户用隐私来换取服务。恶意攻击者通过获取用户的位置信息再结合已有的背景知识，推测出用户的身份信息、健康状况、宗教、爱好等，从而造成隐私泄露。实际上，享受服务与隐私保护是一对矛盾体，近年来许多研究者致力于在高效的位置服务和位置隐私保护之间寻求一个平衡点，即在最少暴露用户位置的前提下，获得最好的位置服务，让暴露的位置处于可控状态。K-匿名是隐私保护方法中最常规的一种，其基本的做法是牺牲服务质量来换取隐私保护。但是K-匿名也存在一些问题，例如在用户稀少的场景下，为了满足K值，可能会出现很大的匿名区域，这时候服务的准确率会急剧下降。针对上面提出的问题，本文采用将整个匿名区域划分为n个子匿名区域，并且提出了一种新的划分子匿名区域的方案，该方案可以更好地保护用户的位置隐私，并且能够提高服务的准确率。
　　2 相关工作
　　在位置匿名处理中，使用最多的是模型是位置K-匿名。K-匿名模型最早由美国Carnegie Mellon 大学的Latanya Sweeney提出，最早使用在关系数据库的数据发布隐私保护，它指一条数据表示的个人信息和其他至少k-1条数据不能区分。Marco Gruteser最先将K-匿名的概念应用到位置隐私上来，提出位置K-匿名，当一个移动用户的位置无法与其他（k-1）个用户的位置相区别时，称此位置满足位置K-匿名，并且提出了一个基于四叉树的具体方案。为了减小匿名区域，提高服务质量，研究者们在Gruteser的基础上提出了新的研究方案。如New Casper、NNC（nearest neighbor clock）、HC（Hilbert cloak）、ANNC（adaptive nearest neighborhood cloaking）。随着方案的不断进步，使用的数据结构越来越复杂，尤其当移动用户移动的更加频繁，维护数据结构的更新成本也越来越明显。
　　K-匿名的另一个性能指标就是l-diversity， l-diversity可以从两方面来考虑：首先，l-diversity用来确保服务请求者不能从l个不同的物理结构中被区分出来，例如，如果所有的用户都处在同一个医院里面，那么攻击者很容易推测出用户的健康状况存在问题。Bamba et al提出了同时满足K-匿名和位置l-diversity的模型。其次，查询l-diversity用来确保服务请求者不能从l个同质查询中被区分出来，为了抵制查询同质攻击，Liu et al提出了满足查询l-diversity的方案。
　　3 位置隐私模型及算法的设计
　　3.1 系统结构及其工作原理
　　本文采用中心服务器结构，该模型的结构如图1所示。
　　该系统包括终端用户，位置匿名服务器匿名器以及位置访问服务器三个部分。
　　（1）终端用户，即使用移动设备进行位置服务查询的人，移动设备主要包括PDA（Personal Digital Assistant）、GPS（Global Positioning System）、笔记本电脑、手机等，其特点是存储能力和处理能力有限。
　　（2）可信的匿名服务器，主要包括位置匿名、数据存储、共享存储。匿名服务器的主要作用是将用户发送过来的位置信息、查询内容进行匿名，将匿名产生的匿名区域代替用户的真实位置发送给服务提供商，并把服务提供商发送过来的结果进行筛选，选择用户所需的真实信息发送给用户。
　　（3）位置访问服务器，主要是指提供位置服务的Internet服务提供商（Internet Service Provider，ISP）。
　　3.2 隐私攻击模型
　　由于本文的重点是提高匿名位置服务的质量（尤其是在用户稀少的场景下），所以只考虑服务器端的威胁。假定攻击者可以截获位置匿名服务器和位置访问服务器之间的所有通信，但事先不知道移动用户的确切位置，但是攻击者试图用这些截获到的信息推测出用户的隐私。具体模型如图2所示。
　　3.3 问题的提出及解决方案
　　3.3.1 提出问题
　　文献在生成子匿名区域之前首先生成一个 k = 12的连续匿名区域，然后再将该匿名区域分裂成3个子匿名区域，子匿名区域内的用户属于连续匿名区域，如图3（c）所示，该方法产生的子匿名区域可能会出现大量重复的区域，很显然，图3（b）会产生更小的匿名区域。
　3.3.2 解决方案
　　综上所述，本文选择文献[2]中划分子匿名区域的方案，但是在k % n不为零时，文献[2]提出将k % n个用户放在同一个子匿名区域内，当k % n的值较大时会造成该子匿名区域中用户的查询精度与其他子匿名区域的查询精度相差较大，同时也可能会造成该子匿名区域面积过大。文献[9]针对此点不足提出了改进方法，文献[9]中将k % n个用户按照就近原则插入到相应的子匿名区域中，该方法虽然很大程度上缓解了这个问题，但是文献[9]是基于先求出一个连续的匿名区域，然后才划分的子匿名区域，所以将k % n个用户按照就近原则插入到相应的子匿名区域中将不适用于直接划分子匿名区域的方法中。本文针对此 种不足提出了一种新的划分子匿名区域的方法。
　　3.4 算法描述
　　符号说明：
　　（id ， （n ， k ， l）， （x ， y） ， M）代表用户查询参数，其中id代表用户的标识符， （n ， k ， l）表示用户自定义参数（n为子匿名区域的个数，k为用户指定的匿名度，l表示位置多样性的参数），（x ， y）为用户的真实位置，M是查询信息；k'i（i=1到n）为每个子匿名区域内的匿名度，即单个子匿名区域内的用户数；num是k/n 的余数；（q ， [CRr] ， M）是位置匿名服务器输出参数，其中q为查询问题，CRr为发送给位置访问服务器的匿名区域。
　　表1 产生个子匿名区域的算法描述
　　输入：服务请求者u，个性化的查询参数（id ， （n ， k ， l）， （x ， y） ， M），存储在匿名服务器的其他移动用户的位置信息
　　步骤：1. Set k'1-n =[k/n] ，l'1-n =[l/n] ， num=[k % n]
　　2. if num=0
　　goto step 4
　　else
　　goto step 3
　　3. while num to 0
　　k'1-num = [k/n]+1，l'1-num =[l/n]+1
　　k'（num+1）-n = [k/n]，l'（num+1）-n =[l/n]
　　end while
　　4. compute CR1 according to k'1， l'1，and （x，y） with an existent cloaking scheme for anonymous LBS
　　5. while i=2 to n
　　Do
　　choose a user u' not yet cloaked from the system
　　Repeat step 4 for user u' and obtain CR1
　　until area of CR1 satisfies predefined restriction
　　end while
　　6. randomly generate r∈[1，n] & q for u，swap CR1 & CRr
　　输出：（q ， [CRr ] ， M）
　　参照表1里的伪代码，我们来简单地阐述一下匿名操作过程。首先，匿名服务器确定k/n，l/n的值，计算出k/n的余数是多少，并把它存放在num（步骤1）。然后，判断余数的值，如果余数为0，则直接跳转到步骤4，划分子匿名区域，如果余数不为0，则跳转到步骤3（步骤2）。按照余数的个数，在前num个子匿名区域中，将此匿名区域的用户个数加1，即k/n，l/n的值分别加1，n-num之后的子匿名区域的用户个数不变（步骤3）。根据k'，l'和用户u的位置（x，y），利用现有的匿名方案来计算出子匿名区域CR1（步骤4）。在没有进入子匿名区域的用户中选取用户ui，并根据用户ui的信息及之前设置的参数，重复步骤4，直到所求出的子匿名区域达到预定义的限制要求为止（步骤5）。最后，随机从子匿名区域中选取一个匿名区域CRr，用它来代替CR1，在加上CR1的查询问题q（步骤6），最后，匿名器输出匿名查询（q ， [CRr ] ， M），并将其发送给位置访问服务器。
　　在表1中，预定义的限制要能够很好地平衡算法的可靠性和查询的准确性之间的关系，例如可以设置一个子匿名区域面积的通用上界，也可以在步骤5中尽量选取用户密集的地区以减少匿名区域的面积，也可以选择离用户所在的匿名区域近的用户以求得更精确的结果，在这里由于篇幅有限，我们省略更进一步的讨论。
　　位置访问服务器最后将查询的候选结果发送回匿名服务器，匿名服务器根据用户u的真实位置筛选出来用户所需的结果，并将其他结果存储在匿名服务器以供下次查询时使用。
　　4 算法的实现及评估
　　4.1 算法的实现
　　根据文中提出的算法并应用matlab编程并仿真了该算法，这里假设在一块长和宽均为5km的矩形地区上进行试验，并且用户在这里提出查询的分布服从均匀分布，假设在这块矩形内共有20个用户，用‘o’表示，矩形的中心为提出查询用户u的真实位置，用‘*’表示，其中k=13，n=3，计算得出k'1 =5，k'2 =4，k'3 =4在下图仿真中连续的子匿名区域的面积为17.9070平方千米，而n个分散的子匿名区域的总面积为5.9631平方千米，如图4所示。
　　4.2 实验结果与分析
　　首先，在用户比较稀疏的场景下运用本方案产生的对比图如图5所示，其中k的值设置为从6到15，n的值为3。图中CR1代表传统的k匿名产生的匿名区域面积（Cloaking Region Area， CRA），CR2代表文献与本文中方案所产生的匿名区域面积同传统匿名方案产生的匿名区域面积之比（Cloaking Region Area Ratio， CRAR），即CRAR（i）=CRAi/CRA1 （其中i=2、3、4）。由图可见，当k值较小时CRAR也较小，即能更有效的减少匿名区域面积，但是随着k值的增大CRAR也趋于稳定，且本方案能够更有效地减少匿名区域的面积并且当k % n的值较大时也能获得稳定高效的服务。
　　5 结束语
　　以往的位置匿名普遍采用连续的匿名区域，当用户要求K值较大且用户稀少时，就会产生较大的匿名区域，从而造成查询精确度下降，此外，大量的候选集还耗费了大量的通信开销，本文采用将整个匿名区域划分为n个子匿名区域，并且提出了一种新的划分子匿名区域的方案，该方法将大大降低匿名区域的面积，可以更好地保护用户的位置隐私，并且能够提高服务的准确率。在此方案中发送给服务提供商的位置中不包含用户的真实位置，因此提高了用户的抗攻击能力。理论分析和实验表明，在用户分布密集的场景下，该方案所产生的匿名区域面积同传统匿名方案中所产生的差别不大，但是在用户稀少的场景下大大降低了匿名区域面积，且用户能在保护自身隐私的同时得出较为精确的查询结果。但本文在产生相邻的子匿名区域时，对下一个子匿名区域的确定并没有采用最优的算法，因此，下一步的工作时优化算法，以进一步降低匿名区域的面积。
　　参考文献
　　[1] Roussopoulos N， Kell ey S， Vincent F. Nearest Neighbor Queries[C]. New York， USA： ACM Press， 1995： 71-79.
　　.Washington：IEEE Computer Society， 2012： 227-231.
　　[3] 潘晓，肖珍，孟小峰.位置隐私研究综述[J].计算机科学与探索，2007，1（3）：268-281.
　　. Orlando， USA： ACM Press， 2009.
　　.http：//～kapadia/papers/ .
　　： IEEE Press， 2008：366-375.
　　，2009：345-356.
　　. New York， USA：ACM Press，2003： 163-168.
　　[9] 赵泽茂，李林，张帆等.基于分散子匿名区域的位置隐私保护方法[J].山东大学学报，2013，48（7）：56-61.
　　. New York： ACM Press， 2006：763-774.
　　. Berlin， Heidelberg： Springer-Verlag， 2007：258-275.
　　[12] Talukder N， Ahamed S I. Preventing Multi-Query Attack in Location-Based Services[C]. New York： ACM Press， 2010：25-36.
　　. New York：ACM Press， 2008：237-246.
　　[14] Liu F Y， Hua K A， Cai Y. Query l-diversity in Location-Based Services[C]. Washington： IEEE Computer Society， 2009：436-442.
　　作者简介：
　　武艳娜（1987-），女，在读研究生。