基于博弈论的个性化LBS用户位置隐私保护方案

杨少杰 张 辉 彭英杰 张光华,2*

1(河北科技大学信息科学与工程学院 河北 石家庄 050000) 2(西安电子科技大学综合业务网理论及关键技术国家重点实验室 陕西 西安 710071) 3(河北省科技管理信息中心 河北 石家庄 050021)

0 引 言

随着GPS、无线通信等技术的广泛应用,基于位置服务(Location-Based Service,LBS)[1]极大地便利了用户的日常生活。在智能定位系统的基础上,用户与LBS应用进行交互从而享受诸如兴趣点查询、紧急事故处理和位置分享等基于位置的服务。

然而,享受LBS应用提供的诸多便利时,用户的位置隐私安全却难以得到有效的保护[2]。为此,学者们提出k匿名[3]、假位置[4]和密码学[5]等位置隐私保护方案,基于不同的技术从外部解决用户的个人隐私泄露问题。此外,用户在使用基于位置服务的同时往往需要和第三方共享位置,而第三方的恶意行为和用户对位置隐私的个性化需求势必影响用户使用LBS应用的积极性。于是,学者们对现有的隐私安全访问控制模型进行拓展,制定隐私策略从内部对用户的隐私信息实施保护[6]。然而,现有的方案未考虑当前网络的综合环境以及对恶意第三方惩罚机制的缺失使其难以适应动态的位置隐私保护场景。

用户希望控制自己的位置信息,在与第三方共享时个性化地保护位置隐私,双方是天然的博弈者。因此,在个性化位置隐私保护的前提下,本文方案从行为策略和收益的角度出发,提出基于博弈论的个性化LBS用户位置隐私保护方案。考虑了网络综合环境和第三方敌手的历史行为,基于静态博弈理论分析二者的行为策略,通过纳什均衡解确立第三方敌手的诚信值。LBS用户为位置信息共享设置共享阈值,将诚信值和共享阈值比较。当诚信值不小于共享阈值时,第三方敌手将获取用户的位置信息;否则,用户将拒绝第三方敌手的位置请求并对其进行惩罚。

本文的主要贡献如下:

(1) 考虑位置隐私保护场景网络环境的复杂性和LBS用户对不同位置隐私的重要程度不同,由当前网络环境和第三方敌手历史访问信息共同构建请求值,并与敏感值比较计算获取位置信息时双方的收益。

(2) 基于静态博弈理论对LBS用户和第三方敌手行为进行分析,通过混合策略下的纳什均衡求解,从收益的角度得出第三方敌手的诚信值。将诚信值和共享阈值进行比较,判定敌手的行为策略,对敌手的恶意行为进行惩罚。

1 相关工作

基于位置的服务丰富了用户生活,但也给LBS用户的隐私安全带来了挑战。现有的LBS用户位置隐私保护方案大都通过k匿名模型的扩展[7-10]使LBS服务商并不知晓提出查询请求的用户身份,从而达到位置隐私保护目的。文献[7]提出了一种基于k匿名的隐私保护技术(k,R,R)-匿名。该方法将用户的真实位置和查询目标替换为一个特定的区域和一组位置类型,用户可动态调整查询内容和匿名区域大小等参数,与k匿名相比具有更强的匿名性。k匿名通常由中心匿名服务器完成[8],当匿名服务器被攻击时难以保证用户的位置隐私安全。文献[9]提出了一种用户协作无匿名区域的位置隐私保护方法。该方法通过用户分布式协作组成匿名区域来代替用户的真实位置发起增量查询,提高了匿名系统性能和服务质量。但该方案假设协作用户是可信的,而现实中用户则会基于利益做出自己的选择。考虑到用户的自利行为,文献[10]提出了一种基于信誉激励机制的位置隐私保护方案。该方案为用户设定阈值,仅当用户信誉达到阈值时,协作用户才会协作其构造匿名组。匿名是从外部保护用户的身份而非用户位置信息,在背景知识攻击或真实身份被LBS提供商所泄露的情况下,难以保护用户的位置隐私,故此类方法并不适用于LBS用户和第三方位置信息共享时的位置隐私保护。

针对匿名技术的不足,访问控制从内部对隐私信息本身进行保护,被学者广泛应用于位置隐私保护场景[11]。文献[12]提出了一种以用户为中心的位置隐私保护方法。该方法考虑了用户对自身位置信息的隐私偏好,将敏感的隐私政策与标准的隐私策略分离,使得位置信息共享不会超过自身的隐私泄露容忍范围。文献[13]提出了基于策略的位置隐私保护机制。由用户和LBS服务商交互定义自身的位置隐私策略,使得非法的位置访问请求者无法获取用户的位置信息。上述方案皆未考虑对非法的位置访问请求者进行惩罚,而在LBS用户和第三方位置共享策略的制定中,应考虑第三方的历史行为对当前位置共享请求的影响。位置信息共享策略可看作LBS用户和第三方敌手的博弈,故本方案运用博弈论对LBS用户和第三方的行为进行分析,制定适合于LBS用户和第三方敌手的位置共享策略。博弈论作为一种高级的数学工具,早有学者将其运用于位置隐私保护场景。文献[14]提出了一种基于假位置和Stackelberg博弈的匿名算法。该方法假设攻击者已获取先验知识,让用户和攻击者轮流进行博弈,通过博弈分析最优化隐私保护水平的同时确保服务质量。文献[15]运用博弈论分析分布式k匿名协作中请求用户和协作用户的自利行为,对泄露协作用户位置的请求用户和提供虚假位置的协作用户进行惩罚,有效保护了用户的位置隐私。文献[16]运用博弈论设计第三方访问者访问LBS用户轨迹时的隐私保护模型。在允许其访问一定位置信息的前提下计算位置隐私信息的叠加性,依据阈值比较机制拒绝非法第三方访问者的位置请求。然而,该方案并未考虑当前网络的综合环境对访客诚实访问概率的影响,且缺乏对第三方恶意请求的惩处机制。

考虑当前网络环境和第三方敌手历史行为,基于博弈论设计一个LBS用户位置隐私保护方案,运用博弈论对LBS用户和发起位置共享请求的第三方敌手行为进行分析。方案以用户对不同位置信息的重要程度不同即个性化为原则设立敏感值,计算博弈双方采取不同策略下的收益,从收益的角度推导出第三方敌手的诚信值。若第三方敌手获取的位置共享信息超过LBS用户对位置隐私泄露的忍耐程度,LBS用户会拒绝与第三方共享位置信息并对其进行惩罚,保护自身的个性化位置信息安全。

2 博弈论预备知识

博弈论(Game Theory)作为一个高级的数学工具在经济学、生物学及信息安全领域有着广泛的应用[17]。博弈的基本要素通常包括博弈参与者、博弈的策略选择、博弈顺序和博弈收益四个层面。Nash[18]证明了博弈过程中纳什均衡的存在,确立了非合作博弈领域的形式。

静态博弈[19]为博弈双方同时做出策略选择的博弈。将博弈双方所有的策略和收益记录在博弈矩阵中,通过画线法确定的最优策略解称为纳什均衡[20]。纳什均衡的定义如下:

运用博弈论对实际问题分析时,基于博弈矩阵可能无法确定纳什解或有多个纳什解。解决此问题的方法往往是将纯策略通过不同的概率归化拓展为混合策略。混合策略的定义如下:

定义2(混合策略)在一场博弈中有n个博弈参与者进行博弈,定义博弈的策略集合空间为S1,S2,…,Sn。对于每个博弈者而言,皆有多个策略选择S1j,S2j,…,Snj,其中Sij∈Si表示第i个博弈参与者的第j个策略。若博弈方i对自身策略S=(Si1,Si2,…,Sik)的概率分配为P=(Pi1,Pi2,…,Pik),且Pi1+Pi2+…+Pik=1,则称此策略为混合策略。

3 基于博弈论的个性化LBS位置隐私保护方案

本节提出基于博弈论的个性化LBS用户位置隐私保护方案。首先,给出方案中的基础概念;其次,给出方案的系统框架;最后,基于静态博弈理论对LBS用户和第三方敌手的行为策略进行博弈分析,推导出第三方敌手的诚信值。对于第三方敌手的恶意请求,LBS用户将拒绝位置共享请求并对其进行惩罚,从而保护自身的个性化位置信息安全。

3.1 基础概念

用户在享受LBS应用提供的便利时,往往需要和不受信任的第三方共享位置信息。当第三方对用户发起获取位置信息请求时,LBS提供商允许用户制定自己的隐私策略用于位置共享。在使用博弈论对个性化LBS用户和第三方敌手的行为策略分析过程中,需要对一些基础概念进行阐述。具体如下:

敏感值:LBS用户对位置信息的个性化体现。用户对不同位置信息的敏感程度不同,分别为其分配取值范围在[0,1]之间的敏感值。敏感值越高,表示用户对该位置信息共享的抵触越大,该位置信息可能推断用户的住址、生活习惯等。

信誉等级:第三方敌手历史行为的体现。该等级由第三方敌手的历史诚信位置共享请求和恶意位置共享请求次数所决定。其诚信位置共享请求次数越多,信誉等级越高,获取的位置共享资源越多;恶意位置共享请求次数越多,信誉等级越低,获取的位置共享资源越少。通过信誉等级来约束第三方敌手的恶意行为,激励其诚信请求位置共享信息。本文方案设定信誉等级初始为1级,最高为10级。信誉等级可用式(1)表示。

(1)

式中:CRn为本次第三方敌手提出位置共享请求时的信誉等级;t为当前信誉等级下第三方敌手的诚信位置共享请求次数。当第三方提出位置共享请求时,根据用户制定的共享策略计算出敌手的诚信值。若诚信值大于等于共享阈值,则第三方敌手是诚信位置共享请求,t的值加1。当t+1

请求值RV:第三方敌手发起位置共享请求行为的综合体现。该值由当前的网络环境值NE和第三方敌手的历史行为综合评定。可用式(2)表示。

RV=α1·NE+α2·CRi

(2)

式中:α1和α2为当前网络环境和归一化的信誉等级所分配的权值,满足α1+α2=1。CRi为归一化的信誉等级,设信誉等级最高为k,则CR=CR/k。

诚信值:第三方敌手诚信位置请求的概率,是对其诚信请求的综合衡量。基于LBS用户与第三方共享的位置信息集合,计算博弈双方采取不同策略下的收益。通过博弈分析计算出第三方敌手的诚信值。

共享阈值:LBS用户在第三方敌手提出位置信息共享请求前设置的阈值。该值的设定建立在用户对位置信息的隐私偏好上,取值范围通常为[0,1]。将诚信值和共享阈值比较,若诚信值大于等于共享阈值,表示第三方敌手是诚信的位置共享请求,用户将与其共享位置信息。相反,则认为第三方敌手是恶意位置共享请求,其获取的位置信息超过了LBS用户对位置隐私泄露的忍耐程度,将受到拒绝并遭受惩罚。共享阈值和用户对隐私泄露的忍耐程度如表1所示。

表1 忍耐度和共享阈值关系表

3.2 系统框架

本节给出方案的系统框架。用户在使用基于位置服务进行查询时,用户的LBS查询结果会在其智能设备上显示,而查询所用的位置信息可由第三方通过网络请求获取用于一些应用需求。当第三方对用户发起获取位置信息请求时,LBS提供商允许用户制定自己的隐私策略用于位置共享。基于静态博弈理论分析LBS用户和第三方敌手的行为策略,制定满足用户位置隐私偏好的共享位置隐私保护策略是本文方案的研究重点。本文方案系统框架如图1所示。

图1 系统框架

本文方案中,第三方敌手向LBS用户发起位置共享请求。首先,系统根据当前网络环境如请求位置信息的时间和网络对第三方敌手恶意行为的防御能力等得到网络环境值NE,并与第三方敌手的归一化信誉等级在权重和为1的情况下,依据式(1)计算出第三方敌手的请求值RV。其次,通过请求值和敏感值的比较,确立了LBS用户能与第三方共享的位置信息集合。运用博弈论对博弈双方采取的策略进行分析,其中第三方敌手的策略选择为诚信位置共享请求和恶意位置共享请求,LBS用户的策略选择为共享位置信息集合和拒绝第三方敌手的请求。基于博弈双方不同策略下的收益进行博弈分析,计算出第三方敌手的诚信值。最后,将诚信值和共享阈值进行比较,若诚信值大于等于共享阈值,则第三方敌手为诚信位置共享请求。用户将与第三方共享位置信息,且第三方敌手的信誉等级缓慢上升作为诚信请求的奖励。若诚信值小于共享阈值,则第三方敌手请求的LBS用户位置信息集合超过其隐私泄露的忍耐程度,视为恶意位置共享请求。用户将拒绝第三方敌手的位置共享请求,且第三方敌手的信誉等级迅速下降作为恶意位置请求的惩罚。

3.3 博弈分析

本节对LBS用户和第三方敌手的博弈过程进行分析并计算第三方敌手的诚信值。当第三方敌手发起位置信息共享请求时,LBS用户依据共享阈值决定是否与第三方共享位置的过程可看作双方的博弈。虽然博弈方的策略选择在时间上有着前后顺序之分,但二者并不知晓对方所采取的策略,可看作同时决策,属于静态博弈范畴。参与的博弈者为第三方敌手和LBS用户,第三方敌手的策略集合为诚信位置共享请求和恶意位置共享请求,用户的策略集合为共享位置信息和拒绝提供位置信息。基于博弈理论分析博弈双方的决策时,还需定义不同策略下的收益。

EU:第三方敌手恶意位置共享请求且用户拒绝共享位置信息时,LBS用户的收益。该收益为用户保护了自身位置信息的安全性,避免了位置信息与恶意第三方共享所带来的生活、财务上的困扰。

基于上述定义,LBS用户和第三方敌手的博弈矩阵如表2所示。

表2 LBS用户和第三方的博弈矩阵

对表2中列出的策略收益分析求解纳什均衡。从第三方敌手的角度考虑,当第三方敌手采取诚信位置共享请求时,LBS用户选择共享位置信息收益最大;当第三方敌手采取恶意位置请求时,LBS用户选择拒绝共享位置信息收益最大。同理,从LBS用户的角度考虑,当LBS用户选择共享位置信息时,第三方敌手采取恶意位置共享请求收益最大;当LBS用户选择拒绝共享位置信息时,第三方敌手采取诚信位置共享请求收益最大。可见,上述博弈并不存在纯策略的纳什均衡解,下面将以概率的形式求解混合策略下的纳什均衡。

不妨设第三方敌手采取诚信位置请求策略的概率为θ,则第三方敌手采取恶意位置请求策略的概率为1-θ;LBS用户选择共享位置信息的概率为ρ,则LBS用户选择拒绝共享位置信息的概率为1-ρ。由表2和假设可得出第三方敌手和LBS用户的收益如下。

第三方敌手的收益IT如式(3)所示。

(3)

为使收益最大化,将IT求θ导并定导数为0,如式(4)所示。

(4)

(5)

同理,可得LBS用户的收益IU如式(6)所示。

(6)

为使收益最大化,将IU求ρ导并定导数为0,如式(7)所示。

(7)

对式(7)进行求解,得到结果如式(8)所示。

(8)

上述通过熵计算给出了第三方敌手和LBS用户的收益,并基于混合策略下的纳什均衡求解得到第三方敌手诚信位置请求的概率θ,即第三方敌手的诚信值。仅当诚信值不小于用户设置的共享阈值时,用户才会与第三方共享位置信息。

4 仿真实验与结果分析

本节在Intel(R) Core(TM) i5-4210U CPU @ 1.70 GHz 2.40 GHz处理器、4 GB内存,Windows 10操作系统下进行本方案实验仿真。实验代码采用Python 3.7编写并于PyCharm上运行,实验数据来源于用户近期使用百度地图所产生的位置数据,并依据用户对不同位置数据的敏感程度为其分配敏感值。在实验过程中,首先,第三方敌手向用户发起共享位置数据请求,用户通过第三方敌手的信誉等级和当前网络环境计算请求值,并与敏感值比较确定共享位置数据集合。其次,通过博弈分析得出第三方敌手的诚信值,判断其是否诚信发起共享位置数据请求。最后,根据返回的结果更新第三方敌手信誉等级。实验从网络环境、信誉等级和有效性三方面进行讨论分析,验证本文方案的合理性和有效性。

4.1 网络环境分析

本节分析网络环境对第三方敌手诚信值的影响。网络环境应是当前网络状况如位置共享请求时间、短时间内提出请求的人数和网络的抗攻击能力等因素的综合考量,本文方案根据网络环境值NE的分布范围将其划分三个层次。当0≤NE≤0.3时,当前网络环境较差;当0.3

考虑三个第三方敌手TA、TB和TC向用户发起位置共享请求,其网络环境分别为NEA=0.2,NEB=0.5,NEC=0.8。信誉等级相同即CRA=CRB=CRC=CR,权重系数分配为α1=0.4,α2=0.6。控制其他参数不变分析网络环境对第三方诚信值的影响,可得到TA、TB和TC诚信值如图2所示。

通过图2可以看到网络环境因素对第三方敌手诚信值的影响。本文方案选取网络环境值0.2、0.5和0.8分别代表网络环境较差、中等和较好这三个状态。图2中随着网络环境值的提高,第三方敌手的诚信值逐渐降低。但存在诚信值交集,以信誉等级CR=6为例,此时TA、TB和TC的诚信值分别为NEA=NEB=0.663 7,NEC=0.641 0。尽管TA、TB的网络环境值不同,但其请求LBS用户位置共享时与用户敏感值比较所获的共享位置集合是一致的,故而二者诚信值相同。从实验和理论分析可看出网络环境对诚信值的影响是存在的,而文献[12]与文献[16]却并未考虑。

4.2 信誉等级分析

本节分析信誉等级对第三方敌手诚信值的影响。考虑两个第三方敌手T1和T2向用户发起位置共享请求,意图获取用户近期使用LBS应用时的位置信息。其中:T1的信誉等级为T1=1;T2的信誉等级为T2=9。网络环境NE1=NE2=0.5,α1=α2=0.5。通过本文方案,得出T1和T2的诚信值如图3所示。

图3 信誉等级分析

通过图3中的计算可得到T1的诚信值为0.750 0,的诚信值为0.601 8。此外,图3还补充了不同信誉等级下的第三方敌手诚信值。可以看到,第三方敌手的诚信值随着信誉等级的提高逐渐降低。信誉等级是在第三方敌手历史诚信或恶意位置共享请求行为的基础上建立的,用来约束第三方敌手的行为。一方面,信誉等级越高,证明其诚信位置共享请求次数越多,能获取更多的位置共享资源。另一方面,能获取的位置共享资源越多,越容易使其行为恶意化。从实验和理论分析可看出信誉等级对诚信值的影响是存在的,文献[16]基于博弈论分析了第三方敌手对用户位置隐私信息的叠加性,通过阈值比较判断了敌手的合法或非法行为。该方案只对合法的第三方提供位置信息,未考虑设定信誉等级对非法的第三方进行惩罚。

4.3 有效性分析

本节对方案的有效性进行分析。本方案有效性是指能否保护用户的个性化位置隐私安全,判断第三方敌手的诚信或恶意位置共享请求行为并进行惩罚。方案假定第三方敌手的信誉等级为2级,让其对LBS用户进行10次位置共享请求。用户的共享阈值设置为0.6,网络环境值NE在0至1之间随机取值,权重系数分配为α1=0.4、α2=0.6。为了实验的公正性,将实验重复进行50次,取平均值作为有效性分析实验的最终结果。得到第三方敌手的位置共享请求次数和诚信值的关系如图4所示。

图4 位置共享请求和诚信值的关系

可以看出,在第1次到第6次位置共享请求中,随着请求次数的增加,第三方敌手的诚信值却一直降低。这是由于前5次第三方敌手的位置共享请求均大于等于用户所设置的共享阈值,判定为诚信位置共享请求。随着信誉等级的增加,所获取的位置共享资源变多,诚信位置请求的概率下降。而在第7次位置共享请求时,第三方敌手的诚信值有所上升。原因是第6次第三方敌手的请求被判定为恶意请求,未能获得用户的位置共享信息集合且遭到信誉等级降低的惩罚,从而使其第7次请求时所获取的位置共享资源减少。故而当第三方敌手第7次位置共享请求时,诚信值有所上升。通过上述实验和分析,本文方案能检测第三方的恶意行为并进行惩罚,有效保护用户的位置隐私,促使用户更加主动地使用基于位置的服务。

5 结 语

针对第三方和用户位置共享中存在的隐私保护问题,提出一种基于博弈论的个性化LBS用户位置隐私保护方案。首先,LBS用户为位置隐私共享设置共享阈值。其次,当第三方向用户发起位置共享请求后,通过静态博弈理论分析第三方敌手和LBS用户的行为策略,基于混合策略纳什均衡的求解确定第三方敌手的诚信值。当诚信值大于等于共享阈值时,第三方才能获得用户的位置信息共享资源。否则视为恶意位置共享请求,将其信誉等级降低作为惩罚,影响下一次提出位置共享请求时所获得的位置信息共享资源。本文方案能有效保护用户的位置隐私,并对恶意的第三方敌手进行惩罚。下一步的研究工作包括:第一,在Foursquare数据集[21]上进一步完善并验证分析方案的可扩展性;第二,在信誉等级的设计中融入更多的因素,构建更加适合LBS用户个性化位置隐私保护的信誉等级机制。