一种基于博弈的LBS隐私保护哑元生成机制

段海兵， 韩建民， 鲁剑锋， 唐长兵， 叶荣华

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

0 引 言

基于位置的服务(Location Based Services，LBS)给人们的生活带来了极大便捷，但是LBS需要用户提供个人的时间和位置等敏感数据，这会给个人隐私带来风险[1].近年来，相关学者在LBS隐私保护方面做了大量的研究工作[2].

LBS位置隐私是指与用户当前位置相关的隐私及由位置推断出来的隐私.目前，保护LBS位置隐私的方法可分为加密法和扭曲法.加密法利用空间加密算法[3-4]使得用户的位置信息对LBS服务器不可见，防止用户隐私信息泄漏.这种方法安全性好，但是计算复杂度过高，实用性不强.扭曲法是指用户在发送个人位置之前，将位置信息进行一些扰动处理，避免暴露用户真实的位置信息.假位置[5]、时空隐形[6]和差分隐私[7]等都是通过位置扭曲来实现LBS位置隐私保护的方法.由于不精确的位置信息会影响服务质量，这类方法需要权衡服务质量和隐私保护之间的关系.

2003年，Gruteser等[8]将k-匿名方法引入到LBS隐私保护领域，提出了位置k-匿名.位置k-匿名要求在某一时空范围内，不可区分用户个数不少于k个，使攻击者标识出用户位置的概率不大于1/k.目前实现位置k-匿名的方法有时空隐形[9]、空间隐形[10]等.但是，这些方法需要泛化或是改变用户的位置信息，降低用户的服务质量.为此，文献[11]提出了通过生成哑元来实现位置k-匿名，此后，如何生成哑元成为LBS隐私保护领域的研究热点;文献[12]提出了基于贝叶斯博弈的哑元生成方法，该方法让隐私需求高的用户生成k-1个哑元，但该工作没有考虑用户协作，浪费资源;文献[13]提出了一个协作缓存机制，利用其他用户的历史位置信息实现位置k-匿名，并利用不完全信息博弈方法解决“搭便车”的问题.然而该方法需要一个中心代理处理用户数据，这会成为服务的瓶颈和隐私安全的薄弱点.

哑元对当前区域的所有用户都是有益的，并且哑元的生成需要成本，因此,哑元生成问题可以看作公共物品博弈问题[14].经典的公共物品博弈的例子是一个投资游戏：设有一个资金池和N个投资代理，投入到资金池的资本会按一定的倍数增值(增值的倍数大于1小于N)；投资代理独立选择自己投入的金额，最终的收益由N个投资代理均分.投资代理投入的成本不同，但是收益相同.因此,会存在非合作者不投入成本，却会收到与其他代理相同收益的现象，这就是“搭便车”行为.“搭便车”行为会造成投资失败，因此,如何促进公共物品博弈的合作成为该领域的研究热点[15-17].

本文提出了一种分布式用户协作的哑元生成机制，利用公共物品博弈模型和动态演化的方法，分析该机制下用户的行为和系统中位置k-匿名的成功率.“搭便车”用户不生成哑元，却可以享受哑元带来的隐私收益.因此,理性自私的用户会倾向于等待其他用户生成哑元,在极端的情况下，还会出现没有人选择生成哑元的现象，导致实现位置k-匿名失败.为了促进用户合作(即生成哑元)，提高实现位置k-匿名的成功率，本文提出一种针对“搭便车”行为的惩罚机制：当一个用户采取“搭便车”行为时，当前区域的用户会孤立该用户.这会使该用户无法利用其他用户和哑元实现位置k-匿名.最后,本文通过实验说明所提出的惩罚机制的有效性.

1 分布式哑元生成机制及分析

1.1 分布式哑元生成机制

LBS隐私保护是在假设LBS服务提供商(LBS Provider,LBSP)不可信的[18]的情况下，如何保护LBS用户的隐私.例如，假设攻击者知道了Alice在时刻t1出现在位置l1，并且知道只有一个用户u1(匿名用户标识符)在时刻t1、位置l1向LBSP方发出了LBS服务请求.攻击者就可推断出u1的真实身份是Alice.此时，攻击者就可以根据u1在LBS中的访问记录，知道Alice的某些与位置相关的隐私信息.更进一步，攻击者可以根据这些位置信息分析出Alice的移动模式，推断出Alice在未来可能会出现在哪些地方.在这个攻击模型里，攻击者的目标是找到真实用户与LBS服务记录里匿名用户的对应关系.攻击者已知的信息是LBS服务器中的所有记录，以及真实用户在某个时刻的位置信息.

针对这种攻击模型，本文提出了一种分布式的、用户协作的哑元生成机制，由同一区域中的用户协作生成所需的哑元，实现位置k-匿名.用户协作生成哑元需要构建局部自治网络，协调各个用户的行为，自治网络可以利用WiFi或蓝牙实现[14].首先，假定LBS服务区域自治网络内的用户数量为N，所有的用户都需要实现k-匿名.当N≥k时，区域内用户已实现k-匿名，不需要生成哑元.当N

第1步：生成哑元的用户向其他用户发送同意协作的信息，组建协作团体Gcoop，统计Gcoop中用户的数量n；

第2步：分配各自需要生成的哑元任务，令k-N=a5n+b(a≥0,b≥0)，则Gcoop中每个用户需要生成a个哑元，再从Gcoop中随机选择b个用户，该b个用户比其他用户多生成一个哑元；

第3步：用户同步生成哑元，并且发送各自的LBS请求.

若Gcoop中的用户全部采用合作的策略，则所有用户都可以顺利实现位置k-匿名.但是，生成哑元需要代价.例如，在这个网络区域中的某些用户，可以选择不加入Gcoop，而是等待其他Gcoop中的用户通过协作产生哑元.当该区域内已经实现了位置k-匿名时，没有加入Gcoop的用户不用付出成本就能享受隐私保护.这就是一种典型的“搭便车”行为.这种“搭便车”行为会影响位置k-匿名的实现.

用户是否选择“搭便车”是公共物品博弈研究的核心问题之一.下面将从博弈论的角度分析用户的行为，以及这种行为对实现k-匿名的影响.

1.2 哑元生成模型分析

接下来将描述一个分布式用户协作的哑元生成机制，并从博弈论的角度分析这个模型的性质,从而构建出一个基于公共物品博弈的哑元生成博弈(Dummy Generation Game,DGG)模型.

博弈参与人：LBS服务区域中用户自治网络的所有用户Uall={ui|i∈{1,2,…,N}}.其中,N表示当前自治网络中的用户总数，并且N

策略集合:1)合作(C)表示用户选择与其他用户协作产生哑元的行为；2)非合作(D)表示用户选择“搭便车”的行为.

(1)

(2)

(3)

式(2)和式(3)中，NC表示Uall中合作者的数量.

(4)

下面用动态演化方法分析这个模型的合作率(合作者在群体中所占的比率).

在一个混合均匀的无限种群中，x表示合作率，则复制动态方程可以写成[20-21]

(5)

式(5)中：

(6)

(7)

令πC-πD=0，可以得到均衡点x*关于k,N的方程

(8)

式(8)中，令N=5(N为其他值时，结果相似)，得到均衡点x*关于k的解，其理论值随k变化的情况见图1.从图 1 可以看出，哑元生成博弈DGG中合作率较低，此时实现k-匿名的概率也会低.为此，本文提出了一种带惩罚机制的哑元生成方法(Dummy Generation Game with Punishment Mechanism,DGGPM)，提高了系统中的合作率.

图1 DGG和DGGPM博弈均衡状态合作率理论值

2 带惩罚机制的哑元生成方法

由以上分析可知，系统中存在大量的非合作者，降低了k-匿名的成功率.为此，本文在哑元生成机制中增加一种惩罚机制，通过降低不合作者的收益，促进合作.在用户移动终端中添加一个状态位τ，用来记录用户在上一次博弈中的行为，并且这个状态位被本地LBS应用控制，用户无法修改.τ只有2个状态0和1.“0”表示采用合作策略，即产生哑元，“1”表示采用非合作策略，即不产生哑元.在每次进入LBS服务区域，用户组建自治网络时，此状态位就会自动添加到请求报文中.其他用户不会响应状态位为1的用户，即上一次选择非合作行为的用户被排除在自治网络之外.用户每次被惩罚后，状态位τ自动清零，即用户的不合作行为只会被惩罚一次.

当一个用户被排除到自治网络之外时，其他用户就不会与其合作，无法通过协作生成哑元实现位置k-匿名.这种情况下，用户为了实现位置k-匿名，就必须自己生成k-1个哑元，成本较高.将这种情况构建成一个带惩罚机制的哑元生成博弈方法.此时，非合作者的收益为

(9)

由式(7)和式(9)可以得到非合作者在惩罚机制下的期望收益，即

(10)

仅考虑混合均匀的无限种群的博弈均衡状态，可得到动态演化过程中合作者的期望收益(式(11)和非合作者的期望收益(式(12)),

(11)

(12)

由式(11)和式(12)可得

(13)

3 仿真实验分析

考虑当前区域有N个用户，分别用DGG和DGGPM两种方法实现位置k-匿名.利用动态演化分析这些用户的行为，根据式(8)和式(13)，可以得到群体中合作者的比率.从图1可以看出，在添加惩罚机制后，合作率显著提高.为了验证这个结果，本文将用数值仿真的方式模拟博弈的过程[15].设置种群数量为2 000，初始种群个体随机赋为合作者和非合作者.每次迭代随机选取2个个体i和j，并分别随机选取另外N-1个个体组成2个博弈群体.分别计算i和j的收益pi和pj，令p=(pi-pj)/α(k)，则合作者与非合作者之间的转移概率ptrans为

若ptrans>0，则个体i以概率ptrans取代个体j；反之则相反.按照上述方法，对于k的每个取值，每次动态演化迭代100 000次，得到合作率，实验重复100次，取100次合作率的平均值为最终结果.最终得到的仿真结果如图2所示，与理论结果一致.

图2 DGG和DGGPM博弈均衡状态合作率仿真结果

在实际情况下，LBS服务区域的用户数是变化的，即参与博弈的人数并不是固定的.为了分析在博弈参与人数N变化时惩罚机制的有效性，将N在2到k-1之间随机取值，重复上述仿真过程，仿真实验结果的合作率都接近1，这里省略了实验结果的展示.由实验可知，当用户自由进出LBS服务区域时，惩罚机制也能有效减少“搭便车”行为.

4 结 语

本文提出了一种利用分布式哑元生成机制实现k-匿名的方法.该方法让用户以一种“协作”的方式生成哑元，直到满足k-匿名的要求.由于哑元具有公共物品的属性，用户存在“搭便车”的行为，因此，本文提出了一种针对“搭便车”用户的惩罚机制.分别针对不带惩罚机制和带惩罚机制的用户协作哑元生成方法建立了N人雪堆博弈模型，并用动态演化的方法分析这两种方法的用户行为.实验表明:带惩罚机制的方法可以明显减少“搭便车”行为，提高k-匿名的成功率.

由于每个用户对隐私的需求度不同，所以会影响用户生成哑元的意愿.隐私需求度高的用户显然更倾向于产生多的哑元，如何将用户的隐私需求度反映到用户的成本和收益上，是一个需要考虑的问题.未来将考虑这些因素,进一步研究基于公共物品博弈的哑元生成模型.

[1]Christin D,Reinhardt A,Kanhere S S,et al.A survey on privacy in mobile participatory sensing applications[J].Journal of Systems and Software,2011,84(11):1928-1946.

[2]张学军,桂小林,伍忠东.位置服务隐私保护研究综述[J].软件学报,2015,26(9):2373-2395.

[3]Okamoto T,Uchiyama S.A new public-key cryptosystem as secure as factoring[C]//International Conference on the Theory and Applications of Cryptographic Techniques.Berlin:Springer,1998:308-318.

[4]Ghinita G,Kalnis P,Khoshgozaran A,et al.Private queries in location based services:anonymizers are not necessary[C]// Proceedings of the ACM SIGMOD International Conference on Management of Data.New York:ACM,2008:121-132.

[5]Niu Ben,Zhang Zhengyan,Li Xiaoqing.Privacy-area aware dummy generation algorithms for location-based[C]//IEEE International Conference on Services Communications (ICC).Piscataway:IEEE,2014:957-962.

[6]Pan X,Xu J,Meng X.Protecting location privacy against location-dependent attack in mobile services[C]//ACM Conference on Information and Knowledge Management.New York:ACM,2008:1475-1476.

[7]Andres M E,Bordenabe N E,Chatzikokolakis K,et al.Geo-indistinguishability:differential privacy for location-based systems[C]//Computer and Communications Security.New York:ACM,2013:901-914.

[8]Gruteser M,Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking[C]//International Conference on Mobile Systems,Applications,and Services.New York:ACM,2003:31-42.

[9]Mokbel M F,Chow C Y,Aref W G.The new casper:Query processing for location services without compromising privacy[C]//International Conference on Very Large Data Bases.New York:ACM,2006:763-774.

[10]Guo M,Pissinou N,Iyengar S S.Pseudonym-based anonymity zone generation for mobile service with strong adversary model[C]//Consumer Communications and Networking Conference(CCNC),2015 12th Annual IEEE.Piscataway:IEEE,2015:335-340.

[11]Lu H,Jensen C S,Yiu M L.Pad:Privacy-area aware,dummy-based location privacy in mobile services[C]//Proceedings of the Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access.New York:ACM,2008:16-23.

[12]Liu X,Liu K,Guo L,et al.A game-theoretic approach for achievingk-anonymity in location based services[C]//INFOCOM,2013 Proceedings IEEE.Piscataway:IEEE,2013:2985-2993.

[13]Jung K,Jo S,Park S.A game theoretic approach for collaborative caching techniques in privacy preserving location-based services[C]//International Conference on Big Data and Smart Computing(BigComp).Piscataway:IEEE,2015:59-62.

[15]Santos F C,Santos M D,Pacheco J M.Social diversity promotes the emergence of cooperation in public goods games[J].Nature,2008,454(7201):213-216.

[16]Colman A M.Game theory and its applications in the social and biological sciences[M].Oxford:Butterworth-Heinemann,1995:212-225.

[17]Binmore K.Game theory and the social contract[M].Berlin:Springer,1991:85-163.

[18]Freudiger J,Shokri R,Hubaux J P.On the optimal placement of mix zones[C]//International Symposium on Privacy Enhancing Technologies Symposium.Berlin:Springer,2009:216-234.

[19]Zheng D F,Yin H P,Chan C H,et al.Cooperative behavior in a model of evolutionary snowdrift games withN-person interactions[J].EPL(Euro Physics Letters),2007,80(1):18002.

[20]Sui X,Cong R,Li K,et al.Evolutionary dynamics ofN-person snowdrift game[J].Physics Letters A,2015,379(45/46):2922-2934.