哑元位置隐私博弈机制

牛晓磊,沈 航,白光伟,陈 林

1(南京工业大学 计算机科学与技术学院,南京 211816)

2(南京大学 计算机软件新技术国家重点实验室,南京 210093)

E-mail:niuxiaolei@njtech.edu.cn

1 引 言

基于位置的服务(Location-based Service,LBS)给人们的生活带来了极大的便利[1],但用户在享受LBS带来便捷服务的同时,隐私信息也存在着泄露的风险.在获取服务的同时需要将用户当前的位置信息提供给LBS服务器.LBS服务器获取到用户的各种位置信息,如果这些信息被第三方获取,分析并加以利用,将会对用户造成难以估计的损失.因此如何能在保证服务的同时,对用户的隐私信息加以保护是十分重要的.

目前,很多隐私保护方案采用k匿名模型,一种是由匿名服务器[2,3]产生一个包含用户真实位置与其余k-1个用户位置的匿名区域,攻击者从这k个用户中推测出真实用户的概率为1/k;另一种不依赖可信第三方的方案[4,5]是由移动设备产生k-1个哑元(dummy),将真实用户位置混入其中构成匿名集发送给LBS.由于k匿名没有考虑匿名区域内的语义信息.假设匿名区域正处于某医院的范围内,那么攻击者可能推测出用户可能是患有某种疾病或者是医院的工作人员,攻击者根据用户的一些背景信息,比如某用户经常在上下班时间出入医院,那么这个用户是工作人员的概率便会增大.基于模糊和泛化的用户隐私保护也是一种常见的方法,基于模糊的位置保护方法[6-8]在用户向LBS发起查询请求时,通过提交非精确位置来避免信息泄露,采用的技术主要有位置偏移、位置扩张等.位置偏移指的是在用户真实位置周围,通过某种方法,寻找哑元来代替用户发起位置请求;位置扩张是将用户的真实位置扩大为一个匿名区域,然后通过加入噪声来降低位置精度,提高推测难度.

上述方法大多忽略了攻击者对于用户背景知识的掌握.通过对用户背景知识进行分析,攻击者可以筛选掉一些用户进而提高自己的隐私推测能力.本文提出哑元位置隐私博弈机制,该机制可以在满足服务质量的前提下保证用户的位置隐私,为用户提供更好的位置服务.用户的真实位置经改进的坐标转换方法生成哑元,替代用户的真实位置与其余k-1用户位置构成匿名区域发送给LBS.考虑到掌握用户背景知识的攻击者可以利用匿名区域内所有用户的数据进行更深层次的挖掘分析,并根据用户策略来调整攻击策略.用户在觉察到自己的隐私信息受到威胁后调整保护策略以抵抗攻击者的攻击,用户与攻击者之间展开博弈,在隐私水平与效用代价之间找一个最佳的平衡点.本文在位置暴露概率、隐私水平和位置熵等方面进行实验分析,证明本机制在损失一定程度的服务质量换取了更好的隐私保护效果.

本文各个章节的安排如下,第2节主要介绍常见的位置隐私保护算法;第3节提出哑元位置隐私博弈机制;第4节主要介绍实验的设计以及相关实验结果;第5节对文章进行总结.

2 相关工作

近年来,基于扭曲法的LBS隐私保护技术受到了研究者的关注.它是对LBS查询中用户的原始数据进行必要的扰动,以避免攻击者获得用户的真实信息数据,同时保证不影响用户获得LBS服务.采用的技术主要有假名(删除或者用一个临时标志来替代用户)、随机化(添加哑元)、模糊化(泛化用户查询过程中的时空信息)和隐蔽化(隐蔽用户的整个查询).在文献[9]中将LBS查询中的用户位置用一个临时的假名代替以打破用户身份与查询之间的联系.但仅仅采用假名并不能充分保护查询隐私,为了增强假名的有效性,文献[10]结合了一些复杂的加密方法与假名技术配合使用来保护用户隐私.随机化指在LBS查询中加入随机哑元,并将哑元和真实查询一起发送给LBS提供商.考虑到随意的随机化并不能很好的保护隐私献,文献[11]在使用随机化技术的同时,考虑了普适、拥挤、均匀等指标和与用户真实移动模式相近的哑元位置,使其看起来更为真实.但是由哑元位置组成的数据中可能与真实数据有很大的差别,甚至产生一些无效的位置(如在湖中),很容易被攻击者识别.在文献[12]中提交给LBS服务器的是一个包含k个位置的匿名区域而非精确的位置,服务器需要在该区域选择参考位置来得到准确的结果,这无疑增加了服务器的负载、响应时间等,降低了服务质量,需要在隐私与服务质量之间进行权衡.文献[13]中提出隐蔽化的方法,拥有一些具体信息的用户可以将这些信息传递给附近用户,用户请求不是向LBS发起查询,而是由附近的用户来请求查询信息,实现对LBS隐蔽查询.

在匿名隐私保护算法的研究中,信息熵作为信息度量的有效工具,广泛用于位置隐私保护领域.Chen等[14]人针对LBS查询隐私进行了度量,将随机变量的概率表现为攻击者在无背景知识和有背景知识两种情况下判断用户的真实位置,并使用互信息量来度量隐私水平.文献[15,16]也均采用信息熵来度量LBS系统的隐私水平.Peng等[17]人基于Shannon信息论提出来几种隐私保护信息熵模型,并且初步考虑了含隐私信息主观感受的信息熵模型.

以上方法对攻击者可能掌握用户的背景知识研究有些许不足,攻击者利用收集到的数据对用户的位置信息进行推测分析,进而可以排除某些用户.Shokri[18]提出了基于Stackelberg博弈的保护策略,该策略假设攻击者掌握用户的背景知识,让用户与攻击者轮流进行博弈.用户在确保服务质量损失小于给定阈值的情况下最大化隐私保护水平,而攻击者根据先验知识和偏移位置保证最小化隐私保护水平.通过博弈,该策略可以在最优化隐私保护水平的同时确保服务质量损失小于给定阈值,最后通过解最优化问题,得到用户的最优位置隐私保护策略和攻击者的最优攻击策略.

基于扭曲法的隐私保护技术可以在服务质量与隐私保护上取得较好的平衡,但容易受到掌握用户背景知识攻击者的隐私攻击.基于Stackelberg博弈的保护策略采用不依赖可信第三方的系统结构,但是受移动设备性能的限制且无法获取用户全局信息(如所有用户的历史服务请求分布).针对上述问题,本文采用基于第三方服务器的隐私保护系统结构,并在此基础上设计哑元位置隐私博弈机制,在用户发起请求时将自己真实位置信息转换为哑元位置后,才发送给匿名服务器,即使第三方服务器被攻陷,攻击者也只能获得用户的哑元位置,对自己的真实位置进行了隐藏.

3 哑元的位置隐私博弈机制

在本节中,首先简单介绍本机制的隐私保护结构,然后对于位置隐私保护中的一些度量进行介绍,然后介绍位置隐私攻击算法,最后介绍用户的最佳保护策略、攻击者的最佳攻击者策略以及它们之间的最佳平衡问题.

本文采用基于第三方服务器的隐私保护结构,如图1所示,主要由以下3个部分组成:

·用户:需要LBS服务时发起位置服务请求,并将真实位置信息转换为哑元.

·位置匿名服务器(Location Anonymization Server,LAS):负责将用户的哑元位置转换为匿名区域,并在LBS提供商返回查询结果后,返回对应的服务结果.

·LBS提供商(Location Based Service Provider,LBSP):负责根据位置查询请求,返回对应的查询结果.

图1 基于第三方服务器的隐私保护结构

3.1 隐私度量

定义1.位置暴露概率P.表示匿名区域内哑元被攻击者成功预测的概率,如公式(1)所示:

(1)

其中,k为匿名区域的用户数,k′表示攻击者根据用户背景信息可以过滤掉的用户数.攻击者过滤掉的用户数量越多,P越小,真实用户暴露出来的概率越大,真实用户被推测出来的概率越大.由公式(1)可知,0≤P≤1.

(2)

定义3.服务质量损失Qloss.表示真实用户ui与匿名区域o内所有用户之间距离的数学期望,如公式(3)所示:

(3)

(4)

结合公式(4),可得:

(5)

(6)

(7)

证明:由公式(7)可知:

(8)

3.2 位置隐私攻击算法

攻击者掌握的用户的背景信息包括用户所在地域的实际环境、用户的移动模式及其用户的历史查询请求等,攻击者可以利用这些信息来对用户进行推测分析,可以更加准确的推测出用户的真实位置.

假设P(B|A)表示在B事件发生情况下A事件发生的概率,那贝叶斯法则可表示为：

(9)

(10)

攻击者可以在贝叶斯攻击的过程中根据自己掌握的用户背景信息对用户的位置信息进行更为准确的推测.

(11)

其中Z表示攻击者掌握的用户背景知识(用户所在区域真实环境、用户的移动模式等).

对掌握用户背景知识与无用户背景知识的攻击者的攻击能力进行比较,如公式(12)所示.

(12)

用户掌握自己的背景知识,因此用户的保护策略在有背景知识的情况下选择对自己最佳的匿名区域,则A≥C.相反地,掌握用户背景知识的攻击者会选择最佳的攻击策略,所以B≤D,因此

(13)

3.3 最佳攻击策略

(14)

其中,q是攻击者针对常见的位置隐私方法结合用户的背景知识进行的推断.

3.4 用户的最佳保护策略

哑元位置隐私博弈机制主要分为哑元的生成与匿名区域的构建过程和Stackelberg博弈优化过程.用户的真实位置转换为哑元,将该哑元与其余k-1个用户位置组成匿名区域后,才将匿名区域发送给服务器.LBS服务器接受到匿名区域后,将相应的应答反馈给用户终端,终端接收到反馈之后会从其中找到自己需要的隐私信息.掌握用户背景知识的攻击者可以根据自己掌握的背景知识对用户进行隐私攻击,用户在觉察到自己的位置信息受到威胁后,适当扩大匿名区域来与攻击者展开博弈.

3.4.1 哑元生成与匿名区域构建

哑元替代用户真实位置参与匿名区域的构建.攻击者想要推测出用户的真实位置,不仅需要推测哑元,还需要推测出坐标转换参数,由于坐标转换参数是由用户的个人终端随机产生,只有用户才能反向计算出用户真实位置,提高了保护隐私的能力.然而攻击者可以根据掌握的用户的背景知识推测出坐标转换方法的参数,然后对用户的位置信息进行推测.在本节中,首先是将用户的真实位置经坐标转换方法转换为哑元,然后将哑元与其余k-1个用户位置经k匿名处理构建匿名区域后,才发送给LBS服务器.

Li等[19]引入了一种坐标转换机制对用户真实位置进行处理.从用户的角度来看坐标转换,图2(a)中正方形的4个顶点都有可能成为u′(x′,y′),用户只有4个可选择的位置点.如果用户身处环境较差此方法效果较差甚至失效,比如对用户的真实位置进行坐标转换后的位置处于湖中,那么这个位置肯定是无效的.从攻击者的角度来看坐标转换,u′(x′,y′)是经坐标转换公式转换后的哑元,在图2(b)中位于圆边界上的是用户真实位置转换后的位置u′(x′,y′),其实线圆内任一位置点都可能是用户的真实位置.掌握用户背景知识的攻击者可以根据用户的移动模式等信息对用户进行分析,可以更为准确的推测出用户的真实位置.

图2 坐标转换方法

传统的坐标转换方法中用户的真实位置经坐标转换后的位置点有4个,然而这4个位置点中可能是无效的.在此基础上,本文分别从用户的角度和攻击者的角度对传统的坐标转换方法进行改进.1)从用户的角度来看,增加一个坐标转换参数λ,使得攻击者更加难以推测出坐标转换参数,推测出用户真实位置概率降低,所需要的代价提高.从图2(a)中可以看出,改进后的算法使得用户经坐标转换后的位置点变得更为复杂,出传统算法中的4个位置点外,矩形的两条对角线均可选择;2)从攻击者的角度来看,攻击者对坐标转换的推测具有概率性,由图2(b)可以看出,如果攻击者对于λ的值进行了错误的估计,那么对于攻击者而言者更为致命.

改进后的坐标转换公式如公式(15)所示.

(15)

其中x,y分别代表用户的真实位置横纵坐标,x′,y′分别代表转换后的横纵坐标.α、b和λ是个人终端随机产生的坐标转换参数,其中0<λ≤1,λ是随机生成的.当用户接收到LAS的查询结果后,可以由其坐标逆转换公式得到用户的真实位置,其坐标逆转换公式为:

(16)

从用户的角度出发,图2(a)中除4个顶点外,正方形区域的两条对角线都可能成为u′(x′,y′),极大提高了用户的可选择性,用户可以选择更好位置点来替代用户的真实位置.在保证LBS服务质量的同时,保护自己的位置隐私.从攻击者的角度来看坐标转换,攻击者对于坐标转换参数的推测是有概率的.如果攻击者对于λ的值进行了错误估计,那么会对攻击者的攻击造成更大的阻碍.如图2(b)所示,真实坐标转换参数λ值为1,然而攻击者错误的将其预测为0.5(虚线圆),恰好其真实用户u(x,y)位于虚线圆外侧,那么攻击者则永远不会推测出用户的真实位置.只要知道α、λ、b参数,攻击者就可以得到用户的真实坐标,因此对于用户来说,想要真实位置不被发现,其经过坐标转换后的哑元也要尽量保证不被攻击者获知,若攻击者多次推测出用户经过坐标转换后的位置,那么攻击者也更容易推测出坐标转换参数.

用户的真实位置在经改进的坐标转换方法转换为哑元之后,与其余k-1 个用户位置构成匿名区域被发送给LBS服务器,此过程中匿名区域内必须包含用户的真实位置,但是实际上用户真实位置并不参与匿名.在用户第一次发起查询并且构成匿名区域时,匿名区域恰好将用户真实位置包含在内即可,此时用户的真实位置处于匿名区域的边界.当攻击者准确预测出坐标转换后的位置后,那么攻击者只需要推测位于边界的用户位置即可.尽管这样也可以保护用户的位置隐私,但是本文的目的是尽量提高用户的隐私水平,即当用户的隐私信息可能被攻击者推测的情况下,允许适当增大匿名区域.

3.4.2 最佳匿名区域隐私保护策略

用户的真实位置ui被泛化为匿名区域o,攻击者观测到o且了解用户的隐私保护方法和用户的概率分布函数Ω.攻击者可以得到后验分布,如公式(17)所示.

(17)

(18)

为了表述方便,用x对公式(18)进行了相应的简化,x的定义如公式(19)所示.

(19)

因此,SPMD是寻找最优匿名区域o的过程,如公式(20)所示.

(20)

该公式的含义是,在所有的攻击者策略中,找到一个匿名区域o,使得用户的收益最大化.因此可将公式(19)变为一个约束条件,如公式(21)所示.

(21)

综上所述,可以得出用户的最佳保护策略如公式(22)所示.

(22)

Subject to

(23)

(24)

其中,公式(23)用来让用户收益最大化;公式(24)用来限制最大可容忍位置服务质量损失.

用户的最大隐私期望就是在公式(22)中的约束条件下对目标函数进行求解,得到最优的匿名区域,在满足服务质量的条件下让隐私水平最大化.

3.5 最佳平衡点搜索

如图3所示,a表示用户的真实位置,a′表示其t+1时刻的位置,实线圆表示用户匿名区域,虚线圆为其圆心用户最大移动范围.在t+1时刻,b′为a′在t+1时刻经过坐标转换后的位置,此时a′与以b′为圆心的圆相切(实线),b′出现在b用户的最大移动范围之外,而e用户也不可能参与t+1时刻的匿名过程(不在其最大移动范围内),因此攻击者可以排除掉b用户与e用户,用户位置暴露概率由原来的1/4增加到1/2,保护能力下降.如果我们适当扩大其隐匿范围(虚线)与e用户最大移动范围重叠,此时攻击者不能将e用户排除,用户位置暴露概率增加到1/3(假设c、d一直在其匿名区域且不能被攻击者排除),提高了用户的隐私保护水平.

图3 用户与攻击者博弈过程

(25)

其中Amax、Amin表示用户的最大匿名区域和最小匿名区域,这两个区域可以由用户自行设定.当攻击者的攻击能力大时,用户的匿名区域半径增大幅度较大.反之,当攻击者的攻击能力小时,用户的匿名区域半径增大幅度较小.尽管用户的隐私得到保护,但是代价也随之增大,因此我们要在隐私与代价之间找到一个平衡点,在最小化代价的同时,保证服务质量.假如用户位置暴露概率至少为70%,在经过攻击者隐私攻击之后,如果隐私水平低于70%,那么用户会适当扩大自己的匿名范围,直到满足70%.

4 实验分析

4.1 实验设计

本实验主要采用matlab工具实现.实验使用滴滴打车的订单数据(1)http://research.xiaojukeji.com/competition/detail.actioncompetitionId=DiTech2016(由滴滴大数据比赛发布)进行算法验证.数据集中给出了M市2016年连续三周的900万条数据信息:订单数据包括订单ID、区域ID、司机ID、乘客ID,价格以及订单时间,还有一些天气、POI和路况信息.

图4 最大服务质量损失与服务质量损失、隐私水平对比

本文设定隐私需求k、生成的匿名区域为圆形,其面积是160 000 m2,之后将面积划分网格形式,网格中的每个单元格都代表位置,单元格的大小与位置粒度有关.假设在任意时间点都可以发布位置服务请求,该请求过程可以看作是泊松过程.为了验证机制的有效性,首先采用DLPG与标准的Stackelberg博弈隐私保护算法SG[14]以及PPMD进行对比,其中PPMD为DLPG中不加Stackelberg博弈的过程,即基于哑元的隐私保护(Position Privacy Mechanism based on Dummy,PPMD).之后对DLPG、PPMD和SG中不同k值情况下位置暴露概率、隐私水平、服务质量损失以及位置熵之间的关系进行比较分析.最后分析攻击者是否掌握用户背景知识下,DLPG与SG匿名区域内用户数量k与隐私水平L以及服务质量损失Qloss之间的关系.因为在哑元的选取上具有随机性,因此本文采用多次实验取平均值的方法进行验证,保证效果的一致性与合理性.

4.2 结果分析

图5 k与位置暴露概率、隐私水平、服务质量损失以及位置熵

2)匿名区域内用户数量k与位置暴露概率P、隐私水平L、服务质量损失Qloss以及位置熵H之间的关系.

图6 有、无背景知识下k与隐私水平以及服务质量损失对比

由图5(a)可以看出,随着k的增大,DLPG、PPMD和SG的位置暴露率均有明显的提高,且DLPG优于PPMD、SG.这是因为PPMD只是单纯的匿名过程,无Stackelberg博弈优化过程,一旦k值确定,其匿名区域也就固定;而在DLPG中若用户的位置隐私受到威胁后,便会适当增大匿名区域,使得攻击者更加难以准确推测出用户的真实位置.SG算法中添加Stackelberg博弈优化过程,其位置暴露概率要高于PPMD,但SG本身只提供偏移位置,没有考虑假位置匿名,而DLPG中使用哑元来替代用户真实位置,攻击者必先推测出哑元位置才能对用户的真实位置进行预测,这两个过程只要一个过程出错,攻击者便不会推测出用户的精确位置.在本文中,位置暴露概率越高,其隐私保护效果越好,因此其隐私水平也高,用户与用户之间相似度越高,位置熵也越大,因此图5(b)与图5(d)一样,与图5(a)呈现相同的趋势.DLPG和SG均需要通过攻击者与用户的博弈过程来提高用户的隐私水平,而PPMD无博弈过程.因此图5(c)可以看出,相同k值情况下,DLPG和SG服务质量损失高于PPMD,且随着k值的增大趋势更加明显.DLPG中使用哑元来替代用户真实位置,因此生成哑元的过程导致了DLPG服务质量损失要大于 SG.

3)攻击者是否掌握用户背景知识下,匿名区域内用户数量k与隐私水平L以及服务质量损失Qloss之间的关系.

图6为不同k值情况且攻击者是否掌握用户背景知识情况下,DLPG与SG的隐私水平以及服务质量损失.由实验可以得出,攻击者掌握用户背景知识下,DLPG隐私保护效果好于SG,但其服务质量损失高于SG,这是因为用户损失一定的服务质量来提高自己隐私的安全.在攻击者不掌握掌握用户背景知识下,DLPG中使用哑元来替代用户真实位置,攻击者需要先推测出哑元位置,才能利用哑元与真实位置之间的关系推测用户真实位置,因此DLPG隐私保护效果更好,意味着服务质量损失更高.

综上所述,DLPG在位置暴露率、隐私水平和位置熵等方面有着良好的表现,增大的匿名区域可以对用户进行隐匿,增加了攻击者对用户真实位置的推测难度,同时将服务质量损失限制在可控范围内,在损失一定的服务质量的同时换取更高的隐私保护效果.

5 小 结

本文提出哑元位置隐私博弈机制,解决了服务质量与隐私保护之间权衡问题,将服务质量损失限制在可控范围内,在损失一定的服务质量的同时换取更高的隐私保护效果.该机制首先将用户的真实位置转换为哑元后与其余k-1个用户位置构成匿名区域后,发送给LBS服务器.考虑到掌握用户背景知识的攻击者会根据用户的保护策略调整攻击策略来获得用户的位置信息,该机制基于Stackelberg博弈对匿名结果进行优化来对抗攻击者的推测攻击,尽可能保护用户的位置隐私.本文通过真实数据集进行实验,证明该机制在位置暴露率、隐私水平和位置熵方面表现良好,且在损失一定的服务质量的同时换取更高的隐私保护效果.