基于匿名区域的位置隐私保护方法

刘盼

摘要：无线定位技术的进步及移动互联网的迅速发展促进了基于位置服务的广泛应用，但其不可避免地造成用户位置隐私泄露，可能危害人身安全。现有位置隐私保护方法只能做到特定情境下的位置隐私保护，但易受连续查询攻击。提出利用隐私需求度量P和服务质量度量Q构建目标函数，在均衡位置服务与隐私保护之间矛盾的基础上，提高用户请求位置的随机性，从而防止连续查询攻击。实验通过递归计算位置K匿名区域的4个子匿名区域的目标函数值，获得最大值的区域即为用户服务请求的最终位置。实验结果表明，该方法能较好地防止连续查询中的边界信息攻击，保护用户隐私，提高服务质量。

关键词关键词：位置隐私；K匿名；连续查询；隐私保护；服务质量

DOIDOI：10.11907/rjdk.162196

中图分类号：TP309文献标识码：A文章编号文章编号：16727800（2017）001015605

引言

近年来，随着全球定位和移动互联网技术的不断进步，促进了基于位置的服务应用迅猛增长[1]。然而，用户使用位置服务时，位置数据不可避免地在用户和位置服务器间传输，可能造成位置隐私泄露。因此，如何实现位置服务与隐私保护的平衡已成为研究热点[2]。

现有的位置隐私保护方法可分为3类：基于政策法、基于加密法和基于扭曲法的位置隐私保护[3]。基于政策法的位置隐私保护依靠经济、社会和监管压力等约束服务提供商规范行为，具有一定的被动性，不能有效保护用户的位置隐私；基于加密法的位置隐私保护通过加密技术使位置服务提供商无法获知用户的服务请求位置，但其需要较高的计算成本，并且不适用于移动用户[4]；基于扭曲法的位置隐私保护是在查询信息发送至LBS服务器之前，对查询中的时空位置信息进行适当修改或扭曲，使服务提供商无法获得精确的位置信息。因此，基于扭曲法的保护方法已成为重要的研究方向[5]。

位置K匿名中K决定了模型的隐私保护效果，逐渐成为扭曲法中的代表方法，它指查询位置对应一个包含至少K个不同用户的区域，攻击者即使获取用户请求的匿5结语

本文在充分理解AES加密算法原理的基础上，提出了几种对加密算法的优化方案，并且结合实际项目工程需要，将优化的加密算法使用FPGA加以实现，设计了基于AXIStream接口的AES加密IP核。通過实验测试，设计的加密IP核能够很好地与DMA进行数据交互。经过对算法的优化与对整体设计结构的调整，充分利用FPGA的内部资源，使IP核的资源消耗较之前的设计有所减少，其系统加密速率可达到1.12Gb/s，完全可以应用于对速率较高的密保项目中。

基于现有算法的不足，本文设计了一个顾及移动用户隐私需求差异性，使移动用户可自定义位置隐私保护等级，并降低匿名服务器被攻击概率的算法。提出利用四叉树结构实现位置K匿名，综合隐私需求与服务质量度量标准构建目标函数，计算K匿名区域下子匿名区域的目标函数值，将目标函数最优解所在的子匿名区域作为移动用户的最终服务地址，在不影响服务质量的前提下，可有效防止边界信息攻击。1预备知识

1.1位置K匿名

本文采用四叉树结构递归地将地理范围不断分割成4个大小相等的子区域。它的每个节点下至多有4个子节点，每个节点代表一个矩形区域，如图1所示。黑点根节点代表最外围的矩形区域，每个矩形区域又可划分为4个小矩形区域，这4个小矩形区域作为4个子节点代表的矩形区域。

图1四叉树结构

位置K匿名指将目标真实位置泛化为一个包含至少K个不同用户的空间区域，从而达到无法辨别目标真实位置的目的。利用四叉树算法结构保证用户在请求服务时，其位置信息不是当前准确的位置坐标，而是一个包含至少K个近邻用户的匿名区域，从而保证目标用户被识别的概率不超过1/K。如图2所示，五角星点为目标用户L，实心点为同一时刻该区域的其他用户，当目标用户的匿名等级K=3时，通过位置K匿名算法，得到的匿名区域即为右侧包含目标用户的方框区域。为了防止最近邻攻击，位置K匿名算法生成的K匿名区域一定是四叉树满足隐私需求的节点所在区域。

1.2边界信息攻击

位置K匿名算法在保护用户隐私的过程中极易受到边界信息攻击[13]。它是指当用户发送多个连续请求时，攻击者通过分析不同时刻下的用户集，找到出现概率较高的用户即为服务请求用户，从而达到攻击目的。如图3中有A、B、C、D、E、F、H共6个用户，假定用户A在t=t1时刻发送了一个等级K=3的位置服务请求，根据位置K匿名算法得到如图3（a）所示的匿名集ct1={A，B，C}。当用户A向右移动，并在t=t2时刻再次发送服务请求时，假定等级K同样为3，此时得到的匿名集为ct2={A，B，D}，如图3（b）实线矩形区域所示，其与t1时刻的用户集取交为{A，B}。当其在t=t3时刻再次发送服务请求时，形成匿名集c3={A，E，H}。通过对3个时刻的匿名集取交集，可得到服务请求者为用户A，从而暴露用户的位置信息。

如图3所示，图3（a）矩形区域为目标用户u1在t1时刻的匿名区域；图2（b） 实线矩形区域为目标用户u1在t2时刻的匿名区域；图2（c）实线矩形区域为目标用户u1在t3时刻的匿名区域。

1.3隐私需求与服务质量度量

用户的服务质量、隐私需求及攻击者的攻击能力是衡量位置隐私保护算法优劣的三个重要指标[13]。匿名区域大小及其包含的用户个数直接关系到隐私保护的质量和效率。然而想要得到高效的服务，匿名区域范围应尽可能小，且离目标用户尽可能近。因此，算法设计应尽可能保证位置服务与隐私保护的平衡。 1.3.1隐私需求度量P

隐私需求度量P用于将用户的位置隐私保护程度转化为攻击者的攻击难度。匿名区域的人口密度关系到目标用户被识别的概率，隐私保护程度也与匿名区域离用户真实位置的距离有关[1]。因此本文将用户的隐私需求表示为：

为运用最广泛的算法，大多考虑快照查询隐私保护，在连续查询请求时易受边界信息攻击。因此，本文在充分考虑用户的位置隐私与服务质量之间关系的基础上，通过分析影响服务质量与位置隐私的各种因素，定义最优化目标函数，采用用户自定义隐私需求的方法，实现匿名区域选择的随机性。实验结果证明，该方法可较好地防止边界信息攻击。但是该方法得到的结果在匿名区域分布极为不均，即与目标用户的真实距离较远时，对服务质量影响较大，下一步还需要进一步改善。参考文献：

[1]SHOKRI R，THEODORAKOPOULOS G，TRONCOSO C.Protecting location privacy：optimal strategy against localization attacks[C].In ACM CCS12： Proceedings of the 2012 Conference on Computer and Communications Security，2012：617627.

[2]霍峥，孟小峰.轨迹隐私保护技术研究[J].计算机学报，2011，34（10）：18211829.

[3]张学军，桂小林，伍忠东.位置服务隐私保护研究综述[J].软件学报，2015，26（9）：23732395.

[4]韩建民，林 瑜，于 娟等.基于位置k匿名的LBS隐私保护方法的研究[J].小型微型计算机系统，2014（9）：20882093.

[5]SHOKRI R，THEODORAKOPOULOS G，PAPADIMITRATOS P， et al.Hiding in the mobile crowd： locationprivacy through collaboration[J].IEEE Transactions on Dependable & Secure Computing， 2014， 11（3）：266279.

[6]GRUTESER M，GRUNWALD D. Anonymous usage of locationbased services through spatial and temporal cloaking[C].In ACM MobiSys03： Procedings of The 1st International Conference On Mobile Systems， Applications And Services， 2003：3142.

[7]MACHANAVAJJHALA A，KIFER D，GEHRKE J， et al. Ldiversity：privacy beyond kanonymity[J].ACM Transactions on Knowledge Discovery From Data，2007，1（1）：152.

[8]GEDIK B，LIU L.Protecting location privacy with personalized kanonymity： architecture and algorithms[J]. IEEE Transactions on Mobile Computing，2008，7（1）：118.

[9]潘曉，郝兴，孟小峰. 基于位置服务中的连续查询隐私保护研究[J].计算机研究与发展，2010，47（1）： 121129.

[10]WANG Y，XU D，et al， L2P2： locationaware location privacy protection for locationbased services[C].in INFOCOM12：Proceeding of the IEEE International Conference on Computer Communications，2012：19962004.

[11]武艳娜，赵泽茂，孙传林.划分子匿名区域的k匿名位置隐私保护方法[J].信息安全与技术，2014，5（10）：3337.

[12]晏燕，郝晓弘，王万军. 一种隐私保护度量的集对分析方法[J]. 武汉大学学报：工学版， 2015，48（6）：883890.

[13]ZHENG J，TAN X，NIU Y，et al， A cloakingbased approach to protect location privacy in locationbased services[C].In Proceedings of the 33rd Chinese Control Conference （CCC）， 2014：54595464.

[14]谈嵘. 位置隐私保护及其在基于位置的社交网络服务中的应用研究[D].上海：华东师范大学，2013.

[15]ZHANG W，CUI X，LI D，et al.The location privacy protection research in locationbased service[C]. In Proceedings of the 18th International Conference on Geoinformatics，2010：14.

[16]M. Li， S.SALINAS，et al.，NCD：A geometric Approach to preserving location