《划分子匿名区域的k—匿名位置隐私保护策略研究.docx》由会员分享，可在线阅读，更多相关《划分子匿名区域的k—匿名位置隐私保护策略研究.docx（5页珍藏版）》请在三一文库上搜索。
1、划分子匿名区域的k匿名位置隐私保护策略研究1 引言随着无线技术和移动位置技术的不断发展开拓了新的研究领域基于位置的服务（Location Based Services， LBS），如查询基于当前位置的感兴趣点，此类服务是基于K近邻（K Nearest Neighbors， KNN）查询，即查询距离用户最近的K个可能目标。例如查询离我最近的工商银行;、距离我25米内最近的饭店/加油站;等，相应的，用户在提出此类查询的时候将不得不把自己的精确位置包含在查询中发送给服务提供商，换句话说，就是用户用隐私来换取服务。恶意攻击者通过获取用户的位置信息再结合已有的背景知识，推测出用户的身份信息、健康状况、宗
2、教、爱好等，从而造成隐私泄露。实际上，享受服务与隐私保护是一对矛盾体，近年来许多研究者致力于在高效的位置服务和位置隐私保护之间寻求一个平衡点，即在最少暴露用户位置的前提下，获得最好的位置服务，让暴露的位置处于可控状态。K-匿名是隐私保护方法中最常规的一种，其基本的做法是牺牲服务质量来换取隐私保护。但是K-匿名也存在一些问题，例如在用户稀少的场景下，为了满足K值，可能会出现很大的匿名区域，这时候服务的准确率会急剧下降。针对上面提出的问题，本文采用将整个匿名区域划分为n个子匿名区域，并且提出了一种新的划分子匿名区域的方案，该方案可以更好地保护用户的位置隐私，并且能够提高服务的准确率。2 相关工作在
3、位置匿名处理中，使用最多的是模型是位置K-匿名。K-匿名模型最早由美国Carnegie Mellon 大学的Latanya Sweeney提出，最早使用在关系数据库的数据发布隐私保护，它指一条数据表示的个人信息和其他至少k-1条数据不能区分。Marco Gruteser最先将K-匿名的概念应用到位置隐私上来，提出位置K-匿名，当一个移动用户的位置无法与其他（k-1）个用户的位置相区别时，称此位置满足位置K-匿名，并且提出了一个基于四叉树的具体方案。为了减小匿名区域，提高服务质量，研究者们在Gruteser的基础上提出了新的研究方案。如New Casper、NNC（nearest neighbo
4、r clock）、HC（Hilbert cloak）、ANNC（adaptive nearest neighborhood cloaking）。随着方案的不断进步，使用的数据结构越来越复杂，尤其当移动用户移动的更加频繁，维护数据结构的更新成本也越来越明显。K-匿名的另一个性能指标就是l-diversity， l-diversity可以从两方面来考虑：首先，l-diversity用来确保服务请求者不能从l个不同的物理结构中被区分出来，例如，如果所有的用户都处在同一个医院里面，那么攻击者很容易推测出用户的健康状况存在问题。Bamba et al提出了同时满足K-匿名和位置l-diversity的模
5、型。其次，查询l-diversity用来确保服务请求者不能从l个同质查询中被区分出来，为了抵制查询同质攻击，Liu et al提出了满足查询l-diversity的方案。3 位置隐私模型及算法的设计3.1 系统结构及其工作原理本文采用中心服务器结构，该模型的结构如图1所示。该系统包括终端用户，位置匿名服务器匿名器以及位置访问服务器三个部分。（1）终端用户，即使用移动设备进行位置服务查询的人，移动设备主要包括PDA（Personal Digital Assistant）、GPS（Global Positioning System）、笔记本电脑、手机等，其特点是存储能力和处理能力有限。（2）可信的
6、匿名服务器，主要包括位置匿名、数据存储、共享存储。匿名服务器的主要作用是将用户发送过来的位置信息、查询内容进行匿名，将匿名产生的匿名区域代替用户的真实位置发送给服务提供商，并把服务提供商发送过来的结果进行筛选，选择用户所需的真实信息发送给用户。（3）位置访问服务器，主要是指提供位置服务的Internet服务提供商（Internet Service Provider，ISP）。3.2 隐私攻击模型由于本文的重点是提高匿名位置服务的质量（尤其是在用户稀少的场景下），所以只考虑服务器端的威胁。假定攻击者可以截获位置匿名服务器和位置访问服务器之间的所有通信，但事先不知道移动用户的确切位置，但是攻击者试
7、图用这些截获到的信息推测出用户的隐私。具体模型如图2所示。3.3 问题的提出及解决方案3.3.1 提出问题文献【2】提出，在传统的匿名方法中一个较大的匿名参数k会产生一个较大的匿名区域，尤其是在用户稀少的场景下，从而导致查询的结果精度下降，并且增加服务器的负担，从而首次提出将传统的连续匿名区域分裂成几个分散的子匿名区域，如图3所示，黑色的实心点代表发起查询的用户，用户要求参数为（k = 12，n = 3），其中k表示匿名度，即要求在匿名区域内至少有k个不可区分的用户，n为用户所设子匿名区域的个数，图3（a）所示为传统匿名算法中生成一个连续的匿名区域。图3（b）所示为将连续的匿名区域分裂成3个子
8、匿名区域，其中每个子匿名区域内有k =k / n = 4 个用户。由图中可以很容易的看出匿名区域减小了，同时文献【2】证明了该匿名方案提高了服务质量，同时还减小了匿名器与位置服务器之间的通信量。之后文献对该方法提出了改进，文献在生成子匿名区域之前首先生成一个 k = 12的连续匿名区域，然后再将该匿名区域分裂成3个子匿名区域，子匿名区域内的用户属于连续匿名区域，如图3（c）所示，该方法产生的子匿名区域可能会出现大量重复的区域，很显然，图3（b）会产生更小的匿名区域。3.3.2 解决方案综上所述，本文选择文献【2】中划分子匿名区域的方案，但是在k % n不为零时，文献【2】提出将k % n个用户
9、放在同一个子匿名区域内，当k % n的值较大时会造成该子匿名区域中用户的查询精度与其他子匿名区域的查询精度相差较大，同时也可能会造成该子匿名区域面积过大。文献针对此点不足提出了改进方法，文献中将k % n个用户按照就近原则插入到相应的子匿名区域中，该方法虽然很大程度上缓解了这个问题，但是文献是基于先求出一个连续的匿名区域，然后才划分的子匿名区域，所以将k % n个用户按照就近原则插入到相应的子匿名区域中将不适用于直接划分子匿名区域的方法中。本文针对此种不足提出了一种新的划分子匿名区域的方法。3.4 算法描述符号说明：（id ， （n ， k ， l）， （x ， y） ， M）代表用户查询参数
10、，其中id代表用户的标识符， （n ， k ， l）表示用户自定义参数（n为子匿名区域的个数，k为用户指定的匿名度，l表示位置多样性的参数），（x ， y）为用户的真实位置，M是查询信息；ki（i=1到n）为每个子匿名区域内的匿名度，即单个子匿名区域内的用户数；num是k/n 的余数；（q ， ， M）是位置匿名服务器输出参数，其中q为查询问题，CRr为发送给位置访问服务器的匿名区域。表1 产生个子匿名区域的算法描述输入：服务请求者u，个性化的查询参数（id ， （n ， k ， l）， （x ， y） ， M），存储在匿名服务器的其他移动用户的位置信息步骤：1. Set k1-n = ，l1
11、-n = ， num=2. if num=0goto step 4elsegoto step 33. while num to 0k1-num = +1，l1-num =+1k（num+1）-n = ，l（num+1）-n =end while4. compute CR1 according to k1， l1，and （x，y） with an existent cloaking scheme for anonymous LBS5. while i=2 to nDochoose a user u not yet cloaked from the systemRepeat step 4 for
12、 user u and obtain CR1until area of CR1 satisfies predefined restrictionend while6. randomly generate r∈ & q for u，swap CR1 & CRr输出：（q ， ， M）参照表1里的伪代码，我们来简单地阐述一下匿名操作过程。首先，匿名服务器确定k/n，l/n的值，计算出k/n的余数是多少，并把它存放在num（步骤1）。然后，判断余数的值，如果余数为0，则直接跳转到步骤4，划分子匿名区域，如果余数不为0，则跳转到步骤3（步骤2）。按照余数的个数，在前num个子
13、匿名区域中，将此匿名区域的用户个数加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 ， ， M），并将其发送给位置访问服务器。在表1中，预定义的限制要能够很好地平衡算法的可靠性和查询的准确性
14、之间的关系，例如可以设置一个子匿名区域面积的通用上界，也可以在步骤5中尽量选取用户密集的地区以减少匿名区域的面积，也可以选择离用户所在的匿名区域近的用户以求得更精确的结果，在这里由于篇幅有限，我们省略更进一步的讨论。位置访问服务器最后将查询的候选结果发送回匿名服务器，匿名服务器根据用户u的真实位置筛选出来用户所需的结果，并将其他结果存储在匿名服务器以供下次查询时使用。4 算法的实现及评估4.1 算法的实现根据文中提出的算法并应用matlab编程并仿真了该算法，这里假设在一块长和宽均为5km的矩形地区上进行试验，并且用户在这里提出查询的分布服从均匀分布，假设在这块矩形内共有20个用户，用o表示，
15、矩形的中心为提出查询用户u的真实位置，用*表示，其中k=13，n=3，计算得出k1 =5，k2 =4，k3 =4在下图仿真中连续的子匿名区域的面积为17.9070平方千米，而n个分散的子匿名区域的总面积为5.9631平方千米，如图4所示。4.2 实验结果与分析首先，在用户比较稀疏的场景下运用本方案产生的对比图如图5所示，其中k的值设置为从6到15，n的值为3。图中CR1代表传统的k匿名产生的匿名区域面积（Cloaking Region Area， CRA），CR2代表文献中所表述的先生成连续的匿名区域，然后再划分子匿名区域的方案所生成的匿名区域的面积，CR3是文献【2】中的方案直接生成的子匿名
16、区域的总面积，CR4代表本方案中生成的子匿名区域的总面积，由图5（a）可见，本文中方案可以更有效的减少匿名区域的面积，虽然CR3中所产生的匿名区域的面积和本方案中的相差不大，但当k % n的值较大时会造成相应的子匿名区域中用户的查询精度与其他子匿名区域的查询精度相差较大，同时也可能会造成该子匿名区域面积过大；在k值较小的情况下，本方案的优越性并没有很明显的显现出来，但是随着k值的增大，所减少的面积也逐渐加大。图5（b）为文献【2】，文献与本文中方案所产生的匿名区域面积同传统匿名方案产生的匿名区域面积之比（Cloaking Region Area Ratio， CRAR），即CRAR（i）=CR
17、Ai/CRA1 （其中i=2、3、4）。由图可见，当k值较小时CRAR也较小，即能更有效的减少匿名区域面积，但是随着k值的增大CRAR也趋于稳定，且本方案能够更有效地减少匿名区域的面积并且当k % n的值较大时也能获得稳定高效的服务。5 结束语以往的位置匿名普遍采用连续的匿名区域，当用户要求K值较大且用户稀少时，就会产生较大的匿名区域，从而造成查询精确度下降，此外，大量的候选集还耗费了大量的通信开销，本文采用将整个匿名区域划分为n个子匿名区域，并且提出了一种新的划分子匿名区域的方案，该方法将大大降低匿名区域的面积，可以更好地保护用户的位置隐私，并且能够提高服务的准确率。在此方案中发送给服务提供
18、商的位置中不包含用户的真实位置，因此提高了用户的抗攻击能力。理论分析和实验表明，在用户分布密集的场景下，该方案所产生的匿名区域面积同传统匿名方案中所产生的差别不大，但是在用户稀少的场景下大大降低了匿名区域面积，且用户能在保护自身隐私的同时得出较为精确的查询结果。但本文在产生相邻的子匿名区域时，对下一个子匿名区域的确定并没有采用最优的算法，因此，下一步的工作时优化算法，以进一步降低匿名区域的面积。参考文献【1】 Roussopoulos N， Kelley S， Vincent F. Nearest Neighbor Queries. New York， USA： ACM Press， 1995
19、： 71-79.【2】 Li T C， Zhu W T. Protecting User Anonymity in Location-Based Services with Fragmented Cloaking Region.Washington：IEEE Computer Society， 2012： 227-231.【3】 潘晓，肖珍，孟小峰.位置隐私研究综述.计算机科学与探索，2007，1（3）：268-281.【4】 Shanker P， Ganapathy V， Iftode L. Privately Querying Location Based Services with Sy
20、bilQuery. Orlando， USA： ACM Press， 2009.【5】 Cornelius C， Kapadia A， Kotz D， et al. AnonySence： Privacy Aware People Centric Sensing. .http：/www.cs.indiana.edu/kapadia/papers/ anonysense_mobisys08.pdf.【6】 Yiu M L， Jensen C S， Huang X G， et al. SpaceTwist： Managing the Trade-offs Among Location Privac
21、y， Query Performance， and Query Accuracy in Mobile Services. ： IEEE Press， 2008：366-375.【7】 Meyerowitz J， Choudhury R R. Hiding Stars with Fireworks： Location Privacy Through Camouflage. Beijing， China： ，2009：345-356. Gruteser M， Grunwald D. Anonymous Usages of Location-based Services Through Spatia
22、l and Temporal Cloaking. New York， USA：ACM Press，2003： 163-168. 赵泽茂，李林，张帆等.基于分散子匿名区域的位置隐私保护方法.山东大学学报，2013，48（7）：56-61. Mokbel M F， Chow C Y， Aref W G. The new Casper： Query Processing for Location Services without Compromising Privacy. New York： ACM Press， 2006：763-774. Chow C Y， Mokbel M F. Enablin
23、g Private Continuous Querues for Revealed User Locations. Berlin， Heidelberg： Springer-Verlag， 2007：258-275. Talukder N， Ahamed S I. Preventing Multi-Query Attack in Location-Based Services. New York： ACM Press， 2010：25-36. Bamba B， Liu L， Pesti P， et al. Supporting Anonymous Location Queries in Moblie Environments with Privacygrid. New York：ACM Press， 2008：237-246. Liu F Y， Hua K A， Cai Y. Query l-diversity in Location-Based Services. Washington： IEEE Computer Society， 2009：436-442.