基于不可信近邻的位置隐私保护方法

张海川，赵泽茂

(1.杭州电子科技大学通信工程学院，浙江 杭州310008;2.丽水学院工程与设计学院，浙江 丽水323000)

0 引 言

伴随着无线通信网络和移动定位技术的飞速发展，基于位置的服务(Location Based Services，LBS)越来越盛行。典型的LBS 应用包括寻找资源、导航搜索等。用户在使用此类服务时，必须将自己的位置信息提供给服务提供商，恶意攻击者通过获取用户的位置信息再结合已有的背景知识，推测出用户的身份信息、健康状况、爱好等，这将严重威胁用户的位置隐私。为了使用户的位置隐私得到保护，学术界主要提出两种位置隐私保护系统结构，分别是基于可信第三方中心匿名服务器结构和P2P 自组织网络结构。基于可信第三方中心匿名服务器结构的思想是利用中心匿名器将用户的具体位置泛化为一个至少包含其他k-1个用户的区域，然而使用中心匿名服务器结构时，中心服务器本身会成为系统的性能瓶颈和主要攻击目标[1-2]。P2P自组织网络结构的思想是在不引入第三方匿名器的情况下假设用户之间相互信任并分享位置信息，用户之间通过P2P 通信收集其他用户的位置信息[3-4]。但是，在现实中用户之间彼此信任的假设不是成立的。本文提出一种新的位置隐私保护方法即不可信近邻算法(Untrusted Nearest Neighborhood Cloak，UNNC)，在P2P 网络中用户之间相互不信任的前提下通过引入第三方验证器实现位置隐私保护。

1 研究背景

从系统的结构来看，LBS位置隐私保护结构主要分为基于中心匿名器的结构和P2P 自组织网络结构。基于中心匿名器结构的位置隐私保护方法有很多，如间隔匿名(interval cloak)，Casper和PrivacyGrid 等。间隔匿名算法是将空间递归划分为4个相等的矩形，每个矩形对应四叉树结构中的一个节点，每个节点中包含当前节点对应区域内的用户数量，使用由子节点直接向父节点搜索的方法计算匿名区域。Casper 匿名算法是对间隔匿名算法的改进，Casper算法直接通过hash表来访问四叉树中的节点并在计算匿名区域时首先搜索节点的相邻兄弟节点再搜索父节点。PrivacyGrid算法把空间划分为网格结构，使用自顶向上的方法计算匿名区域，同时引入了位置多样化的概念，增强了位置隐私保护效果。

文献[3]提出了P2P空间匿名算法，算法假设用户之间相互信任并通过P2P 通信方式分享彼此的位置信息形成匿名组，再计算匿名组内用户形成的最小边界矩形，需要发起LBS 查询请求的用户请求匿名组中的某一用户作为代理向LBS位置服务器发起服务请求。文献[5]提出了CoPrivacy 匿名算法，算法也是通过P2P 通信生成匿名组，匿名组内的用户用该组的密度中心代替真实位置发出查询请求，并采取文献[6]中提出的SpaceTwist 方法中采用的增量查询方案。文献[7]提出了将中心服务器结构和P2P 自组织网络相结合的方案，是一种新的思路。

2 UNNC算法的系统结构

本文提出的UNNC位置隐私保护方法的系统结构是在传统的P2P 结构下引入了第三方验证服务器，系统模型如图1所示。UNNC位置隐私保护方法的系统结构主要包含移动用户、第三方验证服务器和位置服务提供商3个部分。移动用户的终端支持无线互联网通信和P2P 通信两种通讯方式，其中P2P 通信是用来与其他用户相互协作时的自组网通信，而用户与位置服务提供商和第三方验证服务器之间的通信使用的是无线互联网通信方式。用户之间的P2P 通信一般是通过蓝牙或者无线局域网等方式实现，而无线互联网通信则是通过地面基站覆盖的移动蜂窝网络。第三方验证机构是协助发起服务请求的用户判断收到的用户信息是否是真实可靠的，以防止其他的用户模拟出一个或多个用户向发起请求的用户发起恶意攻击。位置服务提供商是指提供基于位置服务的Internet 服务提供商(Internet Service Provider，ISP)。

图1 UNNC系统模型图

3 UNNC位置隐私保护方法

在上述的位置隐私保护系统结构下，本文提出了一种P2P 自组织网络下移动用户相互协作但不相互信任的位置隐私保护方法UNNC，本节将对UNNC算法进行详细描述。

3.1 预备知识

定义1 VERF 码。表示用户真实存在的验证码，具有唯一性，并且当用户的当前VERF 码被其他用户成功验证后会得到验证器重新颁发的新的VERF 码以保证其可用性。

定义2 NL表。用户把收集到的其他用户的VERF 码保存在表中，此表即NL表。

3.2 算法描述

UNNC位置隐私保护算法的实现一共包括4个阶段，实现过程如下:

1)准备阶段。系统中每个用户开机的时候都向验证服务器发起登记请求，申请与自己的ID 相对应的唯一的VERF 码，同时验证服务器将用户的ID与VERF 码以键值对的方式存储在内存空间内;

2)查找周围用户阶段。当用户U 发起LBS 服务请求时，向直接邻居发起跳数hop为1的查找请求，hop 参数是用户之间点对点通信中的路由跳数，其间接的反应了用户之间的距离。用户U的直接邻居在接受到来自用户U的查找请求时会将自己的VERF 码发送给用户U，并且向其自身的直接邻居用户也发起hop为1的查找请求并将收集到的VERF 码存放在自身的NL表中。用户U 将收集到的VERF 码存放在自己的NL表中，并比较收集到的VERF 码的个数n与k-1 做比较，若n≥k-1，则将NL表发送给验证服务器，验证服务器将来自用户U的NL表中的VERF 码与自身存储的VERF 码做比较，返回给用户U真实的VERF 码个数m，否则用户U 就增加hop值以获取更多邻居用户信息，直到收集到VERF 码的个数n 不小于匿名需求参数k。用户U 判断m与k的大小，若m≥k-1，则查找阶段结束，否则用户U 就增加hop值以获取更多邻居用户信息，直到返回的真实VERF 码个数m 满足m≥k-1;

3)发起服务阶段。在查找周围用户阶段已经发现了至少k-1个可信任的邻居用户，用户U 生成一个随机数x(x∈(0，1))并选择一个任意方向距离自身x×(hop-1)×200 m的位置作为锚点，向位置服务提供商发起LBS 服务请求。由于移动设备不同的通讯和计算能力，用户在点对点网络中的通信距离一般在200 300 m 之间，假定通信距离为200 m。用户U 在接受来来自位置服务器的返回结果时，根据用户真实位置和返回的结果集进行计算，从而得到精确的结果集;

4)在服务请求结束后用户U 向验证服务器发送本次请求已结束的通知，验证服务器收到通知后就为用户U 最后一次传送的NL表中真实的VERF 码所对应的用户重新生成VERF 码。这是为了防止用户记住其他用户的VERF 码而向其他的用户发起恶意攻击。

UNNC算法伪代码:

4 实验及结果分析

实验环境是Windows7 操作系统，内存空间为4 GB，实验数据是根据Thomas Brinkhoff 路网数据生成器生成。在模拟实验数据上对UNNC 匿名算法的平均响应时间和匿名成功率进行测试，并将UNNC算法与文献[5]中提出的CoPrivacy算法和文献[3]提出的空间矩形算法中的On-demand算法进行比较。模拟实验数据如表1所示。

由表1可知，在上述交通路网中一共生成4 000个移动用户，实验统一设定用户可接受的其他用户信息的最大hop值为8。实验假设系统中存在2%的用户是恶意用户，即在本实验中共有80个恶意用户。匿名参数k的值从5 变到50，比较3种算法的平均匿名成功率和平均匿名响应时间。平均匿名成功率和平均匿名响应时间是评价位置匿名算法的两个重要参数。如图2所示。

表1 模拟实验数据

图2 匿名参数变化对系统性能的影响

图2(a)表明当匿名参数k 显著增大的时候，3种算法的匿名成功率也会随之而下降，UNNC算法相对其他两种算法具有更高的匿名成功率，这是因为在实验中假设有恶意用户的存在，但是CoPrivacy算法和On-demand算法并不具有抵抗来自网络节点用户的恶意攻击。图2(b)表明，当匿名参数k 显著上升时两种算法完成匿名所需的时间会逐渐增加，并且文中所提出的UNNC算法所需的时间比其他两种算法更长，这是由于UNNC算法中增加了第三方验证器，与第三方验证器的通信需要消耗额外的时间。由上述实验可知，UNNC算法可以在不假设网络节点中的用户是相互信任的前提下获得很高的匿名成功率。

5 结束语

本文提出了一种新的位置隐私保护方法UNNC，在P2P 网络中用户之间相互协作但并不信任的假设下，通过引入第三方验证机构来实现位置隐私保护。UNNC算法可以有效地抵御P2P 网络中来自恶意用户的攻击，目前国内外学者在这方面的研究并不多。UNNC算法在模拟数据上进行了充分的模拟实验，模拟实验结果表明UNNC算法是切实可行的，但是在模拟实验中也发现算法在相同匿名度的情况下需要更多的时间来完成匿名，这将是未来工作的重点和难点。

[1]Mokbel M F，Chow C Y，Aref W G.The new Casper:A privacy-aware location-based database server[C]//Data Engineering，2007.ICDE 2007.IEEE 23rd International Conference on.Istanbul:IEEE，2007:1499-1500.

[2]Bamba B，Liu L，Pesti P，et al.Support Anonymous Location Queries in mobile Environments with Privacygrid[C]//Proceeding of the 17th International Conference on World Wide Web.New York:ACM，2008:237-246.

[3]Chow C Y，Mokbel M F，Liu X.A Peer-to-Peer Spatial Cloaking Algorithm for Anonymous Location-based Services[C]//Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems.New York:ACM，2006:171-178.

[4]Che Y，Yang Q，Hong X.A Dual-Active Spatial Cloaking Algorithm for Location Privacy Preserving in Mobile Peer-to-Peer Networks[C]//Wireless Communications and Networking Conference(WCNC)，2012 IEEE.Shanghai:IEEE，2012:2098-2102.

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

[6]Yiu M L，Jensen C S，Huang X.Space Twist:Managing the trade-offs among location privacy，query performance，and query accuracy in mobile services[C]//Data Engineering，2008.ICDE 2008.IEEE 24th International Conference on.Cancun:IEEE，2008:366-375.

[7]Zhang C，Huang Y.Cloaking locations for anonymous location based services:a hybrid approach[J].GeoInformatica，2009，13(2):159-182.