差分扰动的均衡增量近邻查询位置隐私保护方法

胡德敏，詹 涵

(上海理工大学 光电信息与计算机工程学院，上海 200093)

1 引 言

具有定位能力移动设备的日益普及和无线通信技术的快速发展，大大增加了基于位置服务(location-based service，LBS)的使用.基于位置服务是指移动终端利用各种定位技术获得自己当前的位置，并提出与用户位置有关的服务.虽然这种服务已经证明可以为社会和个人提供巨大的便利，但同时也引起了严重的隐私问题，泄露用户私人生活的敏感信息，如家庭住址、兴趣爱好、健康状况等.因此如何保护用户位置隐私而又不妨碍服务的可用性是一个重要挑战[1].基于LBS的用户隐私保护研究得到了越来越多学者的重视，目前，这方面的研究主要有k-匿名、假位置、位置扰乱、空间加密等方法[2].

大部分k-匿名方法采用可信第三方(trusted third party，TTP)服务器将用户的真实位置替换为包含k个用户的匿名区域，发送给位置服务商(location-based service provider，LSP)，使得LSP无法分辨出查询用户的真实位置.一种方法[3，4]是向真实位置中添加假位置，另一种方法[5，6]是加入附近k-1个真实用户位置.然而，当TTP不是完全可信时，用户的位置和查询信息等隐私将面临风险，而且TTP容易成为系统性能瓶颈和集中攻击点.为了避免TTP，Chow等人[7]基于无中心服务器思想提出了P2P结构，仍然需要使用匿名区，且要求用户相互通信以获取额外信息.Yiu等人提出了SpaceTwist隐私保护算法[8]，采用客户—服务器结构，移动用户随机选择用户真实位置附近的一个锚点，代替用户真实位置向LSP发送请求，进行增量近邻查询.由于随机选择锚点，所获得的查询结果无法得到保证.文献[9]参照路网密度和兴趣点密度，构造匿名区和获取锚点，将其发送给代理用户进行查询，但无法保证查询结果围绕真实位置均匀分布.

这些方法都假定对手没有用户的背景信息，然而，当有背景信息的对手存在时，上述方法的隐私保护强度显然不够.在已知匿名区的情况下，对手利用匿名区和用户的背景信息，缩小用户位置范围，并且当用户分布稀疏时，很难在一个合理的匿名区中发现足够的用户.近年来，开始采用差分隐私[10]来保护用户在LBS中的位置.差分隐私是统计数据库领域的隐私概念，具有两大优点，一方面，差分隐私具有可证明的隐私保障；另一方面，差分隐私能应对具有不同背景信息的对手.差分隐私模型比k-匿名模型具有更严格的隐私保障.文献[11]采用差分隐私和有k个位置的匿名集计算干扰位置，可以抵御有背景信息对手的攻击，但匿名集选择严重影响隐私保障.文献[12]提出基于差分隐私的δ-位置集合来保护用户在时间相关性下每个时间点的真实位置，移动模型的选择是一个难点.文献[13]通过使用隐式马尔可夫模型和差分隐私解决多个用户之间位置相关性泄露问题，但只考虑了恒定时间和两个用户之间的位置相关性.

本文提出一个能抵挡背景信息攻击且无需任何TTP的差分扰动位置隐私保护方法.按照期望的隐私水平向用户真实位置添加可控的拉普拉斯噪声产生扰动，该扰动位置在一定范围内和用户真实位置不可区分，然后用该扰动位置代替用户真实位置请求LSP.同时采用改进的增量近邻查询算法，需求空间再次扩大使得返回的兴趣点既满足用户期望的k近邻结果，又使兴趣点围绕真实位置均匀分布，提高查询准确率.

本文的组织结构如下：第1节介绍位置隐私保护的背景和研究现状；第2节描述差分扰动的均衡增量近邻查询位置隐私保护方法；第3节进行安全性分析；第4节进行实验以及实验结果分析；第5节对全文进行了总结.

2 差分扰动的均衡增量近邻查询位置隐私保护方法

2.1 相关定义

定义1.用户位置loc.用户在某一时刻的位置可以用loc={x，y，t}表示，其中x表示经度，y表示纬度，t表示用户所处当前位置的时间.

定义2.位置隐私需求Qc.用户位置隐私需求Qc={e，r}，其中r表示需要隐私保护区域的半径，表示区域内各个点之间的差异水平.

定义3.查询请求Qa.用户以Qa={id，s，con，kresult}的形式向LSP发出查询请求.其中id表示该用户的标识符，s表示锚点位置，con表示用户的查询请求内容，kresult表示用户期望的k近邻查询结果.

定义4.差分隐私.对于任意两个数据集D1和D2，他们两者之间最多相差一条数据，一个随机函数k提供ε-差分隐私，ε表示隐私预算参数，即隐私保护程度，Range(k)表示随机函数的取值范围，如果对所有的S∈Range(k)，则有，

Pr(k(D1)∈S)≤eεPr(k(D2)∈S)

(1)

定义5.地理不可区分性[14].标准差分隐私可以成功应用于有多个用户的聚合信息发布情况，但不适合单个用户场景.地理不可区分性是标准差分隐私的变体，适合单个用户情况.在以用户真实位置为圆心，r为半径的区域内，用户享有隐私水平，ε=/r表示单位距离隐私水平.通过向用户的真实位置添加平面拉普拉斯噪声生成干扰位置，有背景信息的对手可以观察到干扰位置，但不能以高准确率判断用户的真实位置.定义如下，机制K满足ε-地理不可区分性，对于x，x′⊂X，z⊆Z，X表示输入点集合，Z表示干扰位置集合，d(x，x′)≤r，则有，

K(x)(z)≤eεd(x，x′)K(x′)(z)

(2)

其中d(，)是两点之间的欧几里得距离，K(x)(z)是x经过机制K生成的扰动位置z的概率.

2.2 系统结构

本文采用客户—服务器结构，如图1所示.移动终端具备基本的定位能力，通过手机设备和位置服务器直接通信，不需要TTP.另外，由于集中关注用户提交位置信息给LBS服务器带来的位置隐私泄露问题，因此假设用户只将位置信息传递给LBS服务器，不传递如用户id和网络地址等更多信息.查询过程主要如下：a)在移动终端执行扰动机制(具体算法见2.3节)，生成干扰位置z，此过程不需要进行大量的计算和额外的带宽使用；b)移动终端发出一个查询请求Qa给LBS服务器；c)移动终端接受LBS服务器返回的查询结果并进行过滤.

图1 体系结构图Fig.1 System architecture

2.3 移动终端的锚点计算

以一定的方式向真实位置添加拉普拉斯噪声，生成干扰位置，将其作为锚点，进行增量近邻查询，锚点和真实位置在以loc为圆心，r为半径的区域内，满足地理不可区分性.把位置区域建模成欧几里得平面模型，该模型可以看作地球表面一个良好近似.首先，在连续平面上定义地理不可区分性连续机制；其次，由于位置坐标是有限的点，因此需要向获得的连续点进行离散化；此外，在现实生活中，我们通常只对一定区域感兴趣，如果用户知道真实位置位于特定区域内，则希望生成的干扰位置也在同一区域，因此需要截取有限区域.

a)地理不可区分性的连续机制

在连续平面上定义地理不可区分性机制是构成我们方法的基础，需要保证的属性是当真实位置分别是x和x′时，在一定区域内生成干扰位置z的概率，最多相差因子e-εd(x，x′).如果噪声函数使得在z周围生成干扰位置的概率随着距真实位置x的距离而呈指数下降，该属性满足.在线性空间，这刚好是拉普拉斯分布的特性，概率密度函数为：

(3)

f(x)已被证明满足1/b-差分隐私[15]，但该函数不能直接使用，因为该函数定义在线性空间，我们需要的是定义在平面空间的概率密度函数.于是把拉普拉斯分布从一维空间延伸到二维空间，如下：

(4)

其中，ε2/2π是标准化因子，真实位置x∈R2，经过噪声机制生成的干扰位置z∈R2.该函数叫做以x为中心的平面拉普拉斯分布，满足ε-地理不可区分性，证明如下：

Dε(x)(z)≤eεd(x，x)Dε(x′)(z)

K(x)(t)≤eεd(x，x′)K(x′)(t)

b)生成干扰位置

平面拉普拉斯的概率密度函数仅和干扰位置z与x的距离有关，因此，把笛卡尔坐标系转化为以x为原点的极坐标系更方便计算干扰位置.点z表示成点(r，θ)，r是z到x的距离，θ是射线xz与x轴的夹角.以x为原点的极性拉普拉斯概率密度函数，如下：

(5)

两个随机变量半径和角度相互独立，该概率密度函数可以表示为两个函数的乘积，如下：

Dε(r，θ)=Dε，R(r)Dε，Θ(θ)

(6)

两个函数分别为：

(7)

(8)

Dε，R(r)是伽马分布的概率密度函数，Dε，Θ(θ)是恒定常量1/2π.根据Dε(r，θ)计算点(r，θ)可以从Dε，R(r)，Dε，Θ(θ)分别计算r和θ.因Dε，Θ(θ)是常量，生成θ较容易：以均匀概率1/2π在[0，2π)之间随机生成一个数θ.然后考虑Dε，R(r)的积分函数Cε(r)，如下：

(9)

给定笛卡尔坐标系中真实位置x=(m，n)，根据如上所述生成噪声(r，θ)，干扰位置点z=(m+rcosθ，n+rsinθ).

c)离散化

在现实生活中，通常用离散坐标表示一个位置，比如，位置坐标的经纬度达到某个精度.然而，前面部分描述的拉普拉斯机制可以在平面上任意位置生成干扰位置，则需要将上述生成的干扰位置重新定义在离散的笛卡尔坐标系网格G上最接近x的点，网格G的单元网格划分方式取决于位置坐标精度.

d)截取有限区域

假设用户可接受干扰位置的指定区域是以loc为圆心，ra为半径的圆型区域A，则把由极坐标系下生成的干扰位置点重新映射到Α∩G中近似的点.

算法1.干扰位置生成算法.

输入：用户位置loc，隐私需求Qc，用户所在区域area，位置坐标精度δ，可接受区域半径ra.

输出：干扰位置z.

1.z←0；

3.calculate angelθuniformly in[0，2π)；//计算θ

4.calculatez=(x+rcosθ，y+rsinθ)；

5.divide area intoGaccording toδ；

6.getz′ by remappingzto the closest pointzonG；

7.ifra≤rand ifz′∉A

8.getz′′ onA∩G

9.z←z′′；

10.returnz；

2.4 均衡增量近邻查询算法

本文在用户端执行均衡增量近邻查询算法，在第一次供应空间包含需求空间后继续进行增量近邻查询，直到用户找到围绕自身均匀分布的k个兴趣点.

算法2.均衡增量近邻查询算法.

输入：用户真实位置loc，隐私需求半径r，锚点位置s，查询内容con，目标数kresult.

输出：查询结果集.

1.wn←；//初始化小顶堆

2.γ←r；//初始化需求空间半径

3.τ←0；//初始化供应空间半径

4.count←0；//初始化查询兴趣点个数

5.send an INN query to the LBS server；

6.while(γ+dist(loc，s)>τ)do

7.for each p

8.count++；wn←p；τ←dist(s，p)；

9.if(dist(loc，p)<γ) then

10.γ←dist(loc，p)；

11.end if

12.end while

13.if(count

14.further for each p

15.count++；wn←p；τ←dist(s，p)；

16.end if

17.γ←dist(loc，pkresult)；

18.while(γ+dist(loc，s)>τ) do

19.further for each p

20.wn←p；τ←dist(s，p)；

21.end while

22.return the k points of interest inwn；

在算法2中，锚点s首先应该通过算法1计算得出.初始化需求空间半径γ、供应空间半径τ、查询兴趣点个数count、小顶堆wn.用户使用锚点s发起k近邻查询，根据LBS服务器返回的兴趣点，更新需求空间和供应空间，直到供应空间完全包含需求空间.然后查询count是否不小于目标数kresult，如果count小于目标数kresult，查询继续，直到返回的兴趣点数等于kresult.如图2所示，是kresult=3时的增量近邻查询过程，图2(a)为第一次供应空间包含需求空间，按照SpaceTwist算法描述，此时查询结束，查询结果为{p2，p3，p1}，但此时3个兴趣点主要围绕锚点分布，查询不准确.为了让用户获取围绕自身分布的兴趣点，继续进行查询.首先扩大需求空间半径为dist(loc，kresult)，如图2(b)，继续查询，如图2(c)，直到供应空间再一次完全包含需求空间，查询停止，如图2(d).此时用户获取的查询结果为{p2，p3，p6}，围绕用户当前位置均匀分布，查询结果更准确.

图2 均衡增量近邻查询过程Fig.2 Process of homogeneous incremental nearest neighbor query method

3 安全性分析

考虑两种类型的对手：主动对手和被动对手.被动对手总是窃听无线信道里的消息，进行修改，这种类型的攻击可以通过使用一些成熟的加密技术来避免.因此，本文主要关注主动对手的共谋攻击和推理攻击，这两种类型的攻击会引发严重的隐私泄露问题.

我们的方法是抗共谋攻击的.共谋攻击经常发生在一组用户之间，由于本文方法不存在和其他用户交互，所以抗共谋攻击.

我们的方法是抗推理攻击的.隐藏函数f用来隐藏用户真实位置，σ表示对手观察干扰位置之后得到的结论.

理论1.如果对于f：x→f(x)，输入集合X上的辅助信息π，干扰位置z⊆Z，机制K满足ε-地理不可区分性，则：

dp(σ1，σ2)≤2εd(x，f(x))

其中σ1=Bayes(π，K，z)，σ2=Bayes(π，K·f，z)

此理论的解释在文献[16]中给出，这是标准差分隐私能应对有不同辅助信息的对手特点的使用，指出对手在观察干扰位置之后得到的结论仍然相似，不管对手之前拥有何种辅助信息，查询中用户的真实位置是否使用，对手都不能以高概率猜测出用户真实位置.本文通过在一定区域内向用户真实位置添加拉普拉斯噪声，使得生成的干扰位置和真实位置在这个区域内不可区分，满足ε-地理不可区分性，有效抵挡有背景信息对手的推理攻击.

4 实 验

实验在Windows7系统上用Java语言实现，运行环境为Intel Core i5、CPU3.2 GHz、4GB内存.实验数据是Thomas Brinkhoff路网数据生成器生成的模拟数据并以Oldenburg城市的交通路网产生移动对象.本文采用以下4个指标来评价算法的有效性：

1)接近度.用户设置隐私需求Qc实现ε-地理不可区分性时也要保证生成的干扰位置以尽可能大的概率落在这个区域内，接近度表示干扰位置和真实位置不同距离的比例.

2)数据通信量.查询期间发送的消息数量.

4)响应时间.用户发出查询请求到LBS服务器返回的检索结果满足用户需求的时间.

对于接近度，记扰动位置和真实位置的距离为d，图3为r=0.5km，为不同值时对应不同d值时的比率.当=0.8时，超过97%的扰动位置在距真实位置1km范围内，超过90%的扰动位置在距真实位置500m范围内，超过70%的扰动位置在距真实位置300范围内.随着的增加，生成的扰动位置也越来越接近真实位置，但是较高的值会降低方法的实际意义，例如，当=0.2时，意味着必须接受7倍的概率(e2=7.39)差异的结果.

图3 r=0.5 km时对应不同d值时的分布Fig.3 Distribution of different d value when r=0.5 km

对于数据通信量，如图4所示，两种方法的数据通信量均随着用户查询兴趣点个数k增加，但本文方法略高，这是由于需求空间再次扩大，查询了更多的兴趣点.虽然本文方法扩大了查找范围，但查询结果更准确，可以达到与SpaceTwist方法近似的数据通信量.

图4 与SpaceTwist方法的数据通信量对比Fig.4 Comparison of the data traffic of the SpaceTwist method

图5 与SpaceTwist方法的查询相似度对比Fig.5 Comparison of query similarity of SpaceTwist method

由图5可以看出，用户通过本文方法得到的查询结果和实际k近邻查询结果基本相符，查询相似度达到了90%左右；而SpaceTwist方法的相似度随着查询点距离真实位置距离的增加逐渐上升并趋于一个稳定值，但始终达不到本文方法的相似度.这是因为SpaceTwist方法的查询范围无法覆盖用户期望的k近邻结果的范围，而本文方法不仅满足用户期望的k近邻结果，同时解决了查询兴趣点围绕锚点中心分布导致查询结果不均衡的问题，提高了查询相似度.

图6 与SpaceTwist方法的响应时间对比Fig.6 Comparison of response time of SpaceTwist method

由图6可以看出，SpaceTwist方法在查询点距用户位置距离增加时，返回的兴趣点数越来越多，以至于响应时间也越来越长.本文方法相对于SpaceTwist方法增加了生成干扰位置过程和检查LBS服务器返回的兴趣点数满足用户期望的k近邻结果，同时也使返回的兴趣点数围绕用户真实位置均衡分布，所以在返回相同结果数时的响应时间比SpaceTwist方法更久，但响应时间也相对稳定，且在用户可接受的范围内.

5 结束语

本文提出一种位置扰动的隐私保护方法，相对于k-匿名方法，不再依赖TTP，同时介绍了一种新的隐私保护概念，地理不可区分性，向真实位置添加平面拉普拉斯噪声生成干扰位置，能有效阻止有背景信息对手的攻击，具有很强的隐私保护强度.采用均衡增量近邻查询算法进行查询处理，使兴趣点围绕用户真实位置均匀分布，提高了查询准确性.后期工作中，如何排除一些不良扰动将是本文研究重点方向.