面向LBS的结合k-匿名和本地差分隐私的位置隐私保护

汤文兵,张伟媛

(安徽理工大学 计算机科学与工程学院,安徽 淮南 232001)

随着传感技术的进步,基于位置的应用程序普及度越来越高,位置数据的应用越来越广泛。保护用户的位置信息安全,建立安全有效的位置信息保护模型已经成为当前研究的重点。近年来,为了防止移动终端用户的位置信息泄露,国内外学者做了大量的研究工作。Yin等人[1]使用假名方法改进k-匿名,根据k的最值选择合适的匿名方法,从而实现对位置的有效保护。为了解决难以抵抗背景知识攻击这一缺陷,差分隐私理论[2]于2006 年被提出,其定义了严格的攻击模型,即使攻击者知道除原始数据外的所有信息,也无法通过使用关联分析和其他攻击方法攻击差分隐私保护模型来了解用户的信息。Zhang 等人[3]基于差分隐私提出了一种位置隐私保护方法,其中包含了均值算法和匿名算法,并通过指数机制保证用户的查询隐私,LapLace机制保证用户的位置隐私。差分隐私需要依靠受信任的第三方(TTP)数据收集器来保护敏感信息,然而在现实世界中,第三方服务器并不一定是完全可信的。因此,本地差分隐私(local differential privacy , LDP)的概念被提出。Wang等[4]针对连续位置上传隐私保护中的问题,基于用户位置数量以Hilbert曲线的方式动态的将区域进行分割,采用LDP对对区域内位置进行干扰,服务端接收到干扰后的位置,但这种方法会降低数据的可用性。

为了最大化查询结果的准确性,提高算法的效率,本文提出一种结合k-匿名与本地差分隐私的位置隐私算法。将RAPPOR与k-匿名相结合,选取匿名集的兴趣点,使用本地差分隐私对其进行处理得到扰动位置集,并使用扰动位置集代替原始位置上传以获得LBS服务。

1 定义及相关概念

1.1 差分隐私

定义1(ε-差分隐私[5]算法M满足ε-差分隐私(ε-DP),其中ε>0,当且仅当对于任意2两个相邻的数据集D和D′,有

∀O⊆Range(M):Pr[M(D)∈O]≤exp(ε)×Pr[M(D′)∈O],

(1)

式中:Range(M)表示算法M的所有可能输出的集合。

本文将2个数据集D和D′视为相邻数据集,当且仅当D=D′+L或D′=D+L时记为D≈D′,其中D+L表示向数据集D中添加一位置点L得到的数据集。

1.2 本地差分隐私

定义2(ε-本地化差分隐私[5]如果对于任何2个数值l和l′,一个算法M满足ε-差分隐私(ε-DP),其中ε>0,且满足

∀O⊆Range(M):Pr[M(l)∈O]≤exp(ε)×Pr[M(l′)∈O],

(2)

则称算法M满足ε-LDP。在实施LDP时,随机响应是如今最常用的扰动机制,以降低受访者对敏感问题的错误回答所造成的误差。

1.3 k-匿名模型

定义3(k-匿名模型[6]假设记录A具有n个属性a1,…,an。准标识符Qa={ai,…,aj}⊆{a1,…,an}。Ak是A的第k条记录,r[Qa](r∈A)表示记录r对Qa的投影,只有当准标识符中的每个唯一值序列在A中至少出现k次时,A才满足k-匿名,即

∀s∈{r[Qa]|r∈A},|{i∈N|di[Qa]=s}|≥k.

(3)

1.4 Voronoi图

定义4(Voronoi图[7]) 设点集L={l1,l2,…,ln}(2≤n≤∞)中的任意点li(i∈{1,2,…,n}) 所对应的Voronoi多边形V(li)为

(4)

式中:H为Voronoi多边形的边的集合。

由点集L生成的Voronoi图称为Vor(L)={V(l1),V(l2),…,V(ln)},如图1所示。

图1 Voronoi图局部

2 算法设计

本文模型系统结构如图2所示,主要包含3个组件: 服务器端、扰动(客户端)和位置服务商(仅当用户需要私有查询分析结果时,客户端和服务器都可以进行检索)。用户通过移动设备提出请求,当请求被应答时,LBS存在着泄露数据的风险。当用户发送请求时,本文提出的算法利用用户移动设备上的本地差分隐私机制对用户的地理位置进行扰动处理,并将扰动后的位置传送给LSP。当LSP响应用户并将请求结果转发给用户时,攻击者无法通过结合用户的一些背景信息确定用户的真实地理位置,达到有效保护用户位置隐私的目的。

图2 系统结构模型

2.1 k-匿名候选位置集生成

在创建k-匿名集时,首先根据用户在城市兴趣点中提出查询请求的历史概率来过滤兴趣点,生成一个概率表D,将其存储在本地以方便用户的后续查询,并定期更新以避免数据滞后。当位置数接近2k-2时,匿名集的熵接近最大值,在此之前熵随着位置数的增加而增长。对于背景知识攻击来说,应使匿名集的熵尽可能高。位置点数量同样影响到计算成本,为了在效率和隐私保护之间取得平衡,匿名候选区Rano中的位置数被设定为2k-2。生成Rano的步骤如下:

输入:选取区域包含的位置集合Lloc, 历史查询概率之差dq,k;

输出:匿名候选区Rano;

1) 构造大顶堆,将位置集中的前2k-2 个兴趣点依次添加到候选集Rano中;

2) 从最低的双亲节点开始,根据各位置查询真实位置的历史概率之差,构造初始大顶堆;

3) 从根节点开始,从上到下修改堆,小于请求位置历史概率的候选点被移到顶部;

4) 最后得到请求真实用户位置概率差最小的匿名候选区Rano。

2.2 Voronoi图划分

k-匿名集中的位置点应尽可能分散,以保证匿名域的范围。当通过多次随机分配选择具有最分散位置点的匿名集时,攻击者从匿名集发现用户真实位置的机会接近1/k。为了进一步降低攻击者得知真实位置的概率,使用Voronoi地图来划分候选区域的兴趣点,然后使用RAPPOR来扰动地图。

文献[8]使用逐点加入法来构建一个新的Voronoi图,通过局部修改用Voronoi网格划定道路网。逐点加入法构造简单,但存储困难。在Voronoi网格中划分兴趣点时,兴趣点的分布不均匀,生成计算复杂,因此本文采用基于距离变换的算法在Voronoi网格中进行划分。候选集L中兴趣点的坐标位置集表示为L={l1,l2,…,ln},作为Voronoi图的生成元素,以保证每个兴趣点的扰动位置与用户在分区后所属Voronoi网格中的真实位置之间的距离小于其他所有兴趣点所在的距离。2个位置点l1(lon1,lat1)和l2(lon2,lat2)之间的欧氏距离定义为

(5)

计算每个兴趣点li((1≤i≤n)与其相邻兴趣点之间的欧氏距离,并将兴趣点Lk((1≤k≤n)的从属代码定义为其所在的Voronoi网格的代码。重复上述步骤,直到检索完候选区域的所有POI,并为每个POI创建一个Voronoi网格,最后得到空间位置分布的Voronoi图。

2.3 基于RAPPOR的扰动机制

RAPPOR[9]能够对来自终端用户的众包数据进行匿名化处理,并在不依赖受信任的第三方的情况下提供有效的隐私和效用。对于由Voronoi图划定的候选匿名兴趣点,使用RAPPOR进行随机扰动可以实现强大的隐私保护。假设A={a1,a2,…,an}是地图被服务器划分后的区域ID,n是区域总数。用户在从服务器获得区域ID后,定位当前位置所属的ID。设ai(1≤i≤n)为当前位置的ID,那么一个n维的向量L(表示选中兴趣点所处区域)可以被定义为

(6)

式中:Lj表示向量L中第j位的值。

然后使用RAPPOR中描述的技术对移动用户的位置向量L进行扰动,其中对位置向量L中的每项使用以下随机响应机制,即

(7)

(8)

因此,系统参数q(或p)值表示将S(在RAPPOR 中称为瞬时性随机响应)的第k位变为1的可能性。瞬时随机响应S将被传送到收集数据的服务器。

根据RAPPOR的实现过程,用f,p,q来表示最初选择的区域在受到干扰后保持选择的可能性,即

(1-f)q.

(9)

最初选择的区域在受到干扰后未被选择的可能性为

(1-f)p.

(10)

当服务器得到用户发送的数据时,它可以使用户本地计算的瞬时随机响应S和f,q,p的预定值为每个区域生成汇总统计数据。当用户只发送一次数据时,试图确定用户精确位置的攻击者只能从用户上传扰动后的瞬时随机响应进行推断,而该响应是两次随机的,这将使得攻击者几乎不可能确定用户的精确位置。

2.4 匿名集获取算法

经过RAPPOR扰动后,对Voronoi图解码得到地理位置集G,通过G进行查询,保证了用户的位置隐私。分布在各地的不同兴趣点被记录下来,并计算位置点间的距离进行过滤。在候选位置点和用户的位置P之间,距离d可由欧几里得距离公式将其计算出。

1组k-匿名集被扰动,用户的实际位置可能因扰动而丢失。如果实际位置不包括在G中,则与用户实际位置综合距离最小的n个位置点的查询结果将从LBS服务器返回的匿名集中确定,并将所得位置信息合并为用户查询信息。

3 实验分析

3.1 实验设置

实验所用硬件环境为11th Gen Intel(R) Core(TM) i5 2.40 GHz,16 GB内存,使用Python编程语言实现,操作系统平台为Windows10。用户查询的历史可以由LBS服务器检索。如果无查询数据,可以用地图上的POI数量作为用户搜索的替代。在本实验中,旧金山数据集的POI被用作用户查询数据集。

3.2 实验分析

为了更好地验证本文方案的性能,实验中将本文方案与DLP[10]和K-DLS[11]在位置熵和位置识别率这2个评价指标下进行了对比。DLP是基于熵贪婪地选择虚拟位置,以保护用户的位置隐私。K-DLS是基于熵度量选择扰动位置,并根据位置偏移距离优化匿名结果,增加匿名集的位置离散度。这2个算法都是基于历史查询概率进行选择匿名集,均具有很好的代表性。

3.2.1 位置熵对比

位置熵用来预测匿名位置集的隐私强度。熵值与隐私保护水平呈正比,即

(11)

式中:qi表示用户i的真实位置被识别的可能性。

位置熵结果对比如图3所示,可以看出:生成的k-匿名集的位置熵随着k的增加而增加,二者呈正相关趋势,从而使得匿名集的安全性也得到加强。根据上述实验结果,可以明显看出本文提出的算法在位置熵这一评价指标下优于上述基线模型。这是因为本文模型可以产生地理上分散的匿名位置集,能够有效的应对具有背景知识攻击者的威胁,在保护用户隐私和位置安全的前提下,能够同时获得安全且有质量的服务。

图3 位置熵结果对比

3.2.2 位置识别率对比

如图4所示,在位置识别率上与其他两种基线方法相比,本文产生的匿名集泄露用户精确位置的可能性较小。这是因为与K-DLS和DLP相比,本文加入RAPPOR扰动,在用户的真实位置不包括在匿名集中的情况下,可以提高匿名集的随机性。本模型方案的匿名范围随着k值的增加而增加,因此,攻击者能够通过语义信息进行攻击的机会就会减少,从而降低用户位置被发现的概率,有效提高了对用户位置的保护。

图4 位置识别率结果对比

4 结语

本文针对位置数据中的隐私问题提出了一种新的解决方案,设计了一个融合k-匿名与本地差分隐私的算法来干扰用户的位置数据。并分别从位置熵、位置识别率2个维度将本文提出的算法与另外几种位置隐私保护方案进行比较,证明了本文提出的算法能在很大程度上满足用户的位置隐私保护需求。