基于博弈論的個性化LBS用戶位置隱私保護方案

楊少杰 張 輝 彭英杰 張光華,2*

1(河北科技大學信息科學與工程學院 河北 石家莊 050000) 2(西安電子科技大學綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室 陜西 西安 710071) 3(河北省科技管理信息中心 河北 石家莊 050021)

0 引 言

隨著GPS、無線通信等技術的廣泛應用,基于位置服務(Location-Based Service,LBS)[1]極大地便利了用戶的日常生活。在智能定位系統(tǒng)的基礎上,用戶與LBS應用進行交互從而享受諸如興趣點查詢、緊急事故處理和位置分享等基于位置的服務。

然而,享受LBS應用提供的諸多便利時,用戶的位置隱私安全卻難以得到有效的保護[2]。為此,學者們提出k匿名[3]、假位置[4]和密碼學[5]等位置隱私保護方案,基于不同的技術從外部解決用戶的個人隱私泄露問題。此外,用戶在使用基于位置服務的同時往往需要和第三方共享位置,而第三方的惡意行為和用戶對位置隱私的個性化需求勢必影響用戶使用LBS應用的積極性。于是,學者們對現(xiàn)有的隱私安全訪問控制模型進行拓展,制定隱私策略從內(nèi)部對用戶的隱私信息實施保護[6]。然而,現(xiàn)有的方案未考慮當前網(wǎng)絡的綜合環(huán)境以及對惡意第三方懲罰機制的缺失使其難以適應動態(tài)的位置隱私保護場景。

用戶希望控制自己的位置信息,在與第三方共享時個性化地保護位置隱私,雙方是天然的博弈者。因此,在個性化位置隱私保護的前提下,本文方案從行為策略和收益的角度出發(fā),提出基于博弈論的個性化LBS用戶位置隱私保護方案?？紤]了網(wǎng)絡綜合環(huán)境和第三方敵手的歷史行為,基于靜態(tài)博弈理論分析二者的行為策略,通過納什均衡解確立第三方敵手的誠信值。LBS用戶為位置信息共享設置共享閾值,將誠信值和共享閾值比較。當誠信值不小于共享閾值時,第三方敵手將獲取用戶的位置信息;否則,用戶將拒絕第三方敵手的位置請求并對其進行懲罰。

本文的主要貢獻如下:

(1) 考慮位置隱私保護場景網(wǎng)絡環(huán)境的復雜性和LBS用戶對不同位置隱私的重要程度不同,由當前網(wǎng)絡環(huán)境和第三方敵手歷史訪問信息共同構(gòu)建請求值,并與敏感值比較計算獲取位置信息時雙方的收益。

(2) 基于靜態(tài)博弈理論對LBS用戶和第三方敵手行為進行分析,通過混合策略下的納什均衡求解,從收益的角度得出第三方敵手的誠信值。將誠信值和共享閾值進行比較,判定敵手的行為策略,對敵手的惡意行為進行懲罰。

1 相關工作

基于位置的服務豐富了用戶生活,但也給LBS用戶的隱私安全帶來了挑戰(zhàn)?，F(xiàn)有的LBS用戶位置隱私保護方案大都通過k匿名模型的擴展[7-10]使LBS服務商并不知曉提出查詢請求的用戶身份,從而達到位置隱私保護目的。文獻[7]提出了一種基于k匿名的隱私保護技術(k,R,R)-匿名。該方法將用戶的真實位置和查詢目標替換為一個特定的區(qū)域和一組位置類型,用戶可動態(tài)調(diào)整查詢內(nèi)容和匿名區(qū)域大小等參數(shù),與k匿名相比具有更強的匿名性。k匿名通常由中心匿名服務器完成[8],當匿名服務器被攻擊時難以保證用戶的位置隱私安全。文獻[9]提出了一種用戶協(xié)作無匿名區(qū)域的位置隱私保護方法。該方法通過用戶分布式協(xié)作組成匿名區(qū)域來代替用戶的真實位置發(fā)起增量查詢,提高了匿名系統(tǒng)性能和服務質(zhì)量。但該方案假設協(xié)作用戶是可信的,而現(xiàn)實中用戶則會基于利益做出自己的選擇。考慮到用戶的自利行為,文獻[10]提出了一種基于信譽激勵機制的位置隱私保護方案。該方案為用戶設定閾值,僅當用戶信譽達到閾值時,協(xié)作用戶才會協(xié)作其構(gòu)造匿名組。匿名是從外部保護用戶的身份而非用戶位置信息,在背景知識攻擊或真實身份被LBS提供商所泄露的情況下,難以保護用戶的位置隱私,故此類方法并不適用于LBS用戶和第三方位置信息共享時的位置隱私保護。

針對匿名技術的不足,訪問控制從內(nèi)部對隱私信息本身進行保護,被學者廣泛應用于位置隱私保護場景[11]。文獻[12]提出了一種以用戶為中心的位置隱私保護方法。該方法考慮了用戶對自身位置信息的隱私偏好,將敏感的隱私政策與標準的隱私策略分離,使得位置信息共享不會超過自身的隱私泄露容忍范圍。文獻[13]提出了基于策略的位置隱私保護機制。由用戶和LBS服務商交互定義自身的位置隱私策略,使得非法的位置訪問請求者無法獲取用戶的位置信息。上述方案皆未考慮對非法的位置訪問請求者進行懲罰,而在LBS用戶和第三方位置共享策略的制定中,應考慮第三方的歷史行為對當前位置共享請求的影響。位置信息共享策略可看作LBS用戶和第三方敵手的博弈,故本方案運用博弈論對LBS用戶和第三方的行為進行分析,制定適合于LBS用戶和第三方敵手的位置共享策略。博弈論作為一種高級的數(shù)學工具,早有學者將其運用于位置隱私保護場景。文獻[14]提出了一種基于假位置和Stackelberg博弈的匿名算法。該方法假設攻擊者已獲取先驗知識,讓用戶和攻擊者輪流進行博弈,通過博弈分析最優(yōu)化隱私保護水平的同時確保服務質(zhì)量。文獻[15]運用博弈論分析分布式k匿名協(xié)作中請求用戶和協(xié)作用戶的自利行為,對泄露協(xié)作用戶位置的請求用戶和提供虛假位置的協(xié)作用戶進行懲罰,有效保護了用戶的位置隱私。文獻[16]運用博弈論設計第三方訪問者訪問LBS用戶軌跡時的隱私保護模型。在允許其訪問一定位置信息的前提下計算位置隱私信息的疊加性,依據(jù)閾值比較機制拒絕非法第三方訪問者的位置請求。然而,該方案并未考慮當前網(wǎng)絡的綜合環(huán)境對訪客誠實訪問概率的影響,且缺乏對第三方惡意請求的懲處機制。

考慮當前網(wǎng)絡環(huán)境和第三方敵手歷史行為,基于博弈論設計一個LBS用戶位置隱私保護方案,運用博弈論對LBS用戶和發(fā)起位置共享請求的第三方敵手行為進行分析。方案以用戶對不同位置信息的重要程度不同即個性化為原則設立敏感值,計算博弈雙方采取不同策略下的收益,從收益的角度推導出第三方敵手的誠信值。若第三方敵手獲取的位置共享信息超過LBS用戶對位置隱私泄露的忍耐程度,LBS用戶會拒絕與第三方共享位置信息并對其進行懲罰,保護自身的個性化位置信息安全。

2 博弈論預備知識

博弈論(Game Theory)作為一個高級的數(shù)學工具在經(jīng)濟學、生物學及信息安全領域有著廣泛的應用[17]。博弈的基本要素通常包括博弈參與者、博弈的策略選擇、博弈順序和博弈收益四個層面。Nash[18]證明了博弈過程中納什均衡的存在,確立了非合作博弈領域的形式。

靜態(tài)博弈[19]為博弈雙方同時做出策略選擇的博弈。將博弈雙方所有的策略和收益記錄在博弈矩陣中,通過畫線法確定的最優(yōu)策略解稱為納什均衡[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位置隱私保護方案

本節(jié)提出基于博弈論的個性化LBS用戶位置隱私保護方案。首先,給出方案中的基礎概念;其次,給出方案的系統(tǒng)框架;最后,基于靜態(tài)博弈理論對LBS用戶和第三方敵手的行為策略進行博弈分析,推導出第三方敵手的誠信值。對于第三方敵手的惡意請求,LBS用戶將拒絕位置共享請求并對其進行懲罰,從而保護自身的個性化位置信息安全。

3.1 基礎概念

用戶在享受LBS應用提供的便利時,往往需要和不受信任的第三方共享位置信息。當?shù)谌綄τ脩舭l(fā)起獲取位置信息請求時,LBS提供商允許用戶制定自己的隱私策略用于位置共享。在使用博弈論對個性化LBS用戶和第三方敵手的行為策略分析過程中,需要對一些基礎概念進行闡述。具體如下:

敏感值:LBS用戶對位置信息的個性化體現(xiàn)。用戶對不同位置信息的敏感程度不同,分別為其分配取值范圍在[0,1]之間的敏感值。敏感值越高,表示用戶對該位置信息共享的抵觸越大,該位置信息可能推斷用戶的住址、生活習慣等。

信譽等級:第三方敵手歷史行為的體現(xiàn)。該等級由第三方敵手的歷史誠信位置共享請求和惡意位置共享請求次數(shù)所決定。其誠信位置共享請求次數(shù)越多,信譽等級越高,獲取的位置共享資源越多;惡意位置共享請求次數(shù)越多,信譽等級越低,獲取的位置共享資源越少。通過信譽等級來約束第三方敵手的惡意行為,激勵其誠信請求位置共享信息。本文方案設定信譽等級初始為1級,最高為10級。信譽等級可用式(1)表示。

(1)

式中:CRn為本次第三方敵手提出位置共享請求時的信譽等級;t為當前信譽等級下第三方敵手的誠信位置共享請求次數(shù)。當?shù)谌教岢鑫恢霉蚕碚埱髸r,根據(jù)用戶制定的共享策略計算出敵手的誠信值。若誠信值大于等于共享閾值,則第三方敵手是誠信位置共享請求,t的值加1。當t+1

請求值RV:第三方敵手發(fā)起位置共享請求行為的綜合體現(xiàn)。該值由當前的網(wǎng)絡環(huán)境值NE和第三方敵手的歷史行為綜合評定?？捎檬?2)表示。

RV=α1·NE+α2·CRi

(2)

式中:α1和α2為當前網(wǎng)絡環(huán)境和歸一化的信譽等級所分配的權(quán)值,滿足α1+α2=1。CRi為歸一化的信譽等級,設信譽等級最高為k,則CR=CR/k。

誠信值:第三方敵手誠信位置請求的概率,是對其誠信請求的綜合衡量。基于LBS用戶與第三方共享的位置信息集合,計算博弈雙方采取不同策略下的收益。通過博弈分析計算出第三方敵手的誠信值。

共享閾值:LBS用戶在第三方敵手提出位置信息共享請求前設置的閾值。該值的設定建立在用戶對位置信息的隱私偏好上,取值范圍通常為[0,1]。將誠信值和共享閾值比較,若誠信值大于等于共享閾值,表示第三方敵手是誠信的位置共享請求,用戶將與其共享位置信息。相反,則認為第三方敵手是惡意位置共享請求,其獲取的位置信息超過了LBS用戶對位置隱私泄露的忍耐程度,將受到拒絕并遭受懲罰。共享閾值和用戶對隱私泄露的忍耐程度如表1所示。

表1 忍耐度和共享閾值關系表

3.2 系統(tǒng)框架

本節(jié)給出方案的系統(tǒng)框架。用戶在使用基于位置服務進行查詢時,用戶的LBS查詢結(jié)果會在其智能設備上顯示,而查詢所用的位置信息可由第三方通過網(wǎng)絡請求獲取用于一些應用需求。當?shù)谌綄τ脩舭l(fā)起獲取位置信息請求時,LBS提供商允許用戶制定自己的隱私策略用于位置共享。基于靜態(tài)博弈理論分析LBS用戶和第三方敵手的行為策略,制定滿足用戶位置隱私偏好的共享位置隱私保護策略是本文方案的研究重點。本文方案系統(tǒng)框架如圖1所示。

圖1 系統(tǒng)框架

本文方案中,第三方敵手向LBS用戶發(fā)起位置共享請求。首先,系統(tǒng)根據(jù)當前網(wǎng)絡環(huán)境如請求位置信息的時間和網(wǎng)絡對第三方敵手惡意行為的防御能力等得到網(wǎng)絡環(huán)境值NE,并與第三方敵手的歸一化信譽等級在權(quán)重和為1的情況下,依據(jù)式(1)計算出第三方敵手的請求值RV。其次,通過請求值和敏感值的比較,確立了LBS用戶能與第三方共享的位置信息集合。運用博弈論對博弈雙方采取的策略進行分析,其中第三方敵手的策略選擇為誠信位置共享請求和惡意位置共享請求,LBS用戶的策略選擇為共享位置信息集合和拒絕第三方敵手的請求?；诓┺碾p方不同策略下的收益進行博弈分析,計算出第三方敵手的誠信值。最后,將誠信值和共享閾值進行比較,若誠信值大于等于共享閾值,則第三方敵手為誠信位置共享請求。用戶將與第三方共享位置信息,且第三方敵手的信譽等級緩慢上升作為誠信請求的獎勵。若誠信值小于共享閾值,則第三方敵手請求的LBS用戶位置信息集合超過其隱私泄露的忍耐程度,視為惡意位置共享請求。用戶將拒絕第三方敵手的位置共享請求,且第三方敵手的信譽等級迅速下降作為惡意位置請求的懲罰。

3.3 博弈分析

本節(jié)對LBS用戶和第三方敵手的博弈過程進行分析并計算第三方敵手的誠信值。當?shù)谌綌呈职l(fā)起位置信息共享請求時,LBS用戶依據(jù)共享閾值決定是否與第三方共享位置的過程可看作雙方的博弈。雖然博弈方的策略選擇在時間上有著前后順序之分,但二者并不知曉對方所采取的策略,可看作同時決策,屬于靜態(tài)博弈范疇。參與的博弈者為第三方敵手和LBS用戶,第三方敵手的策略集合為誠信位置共享請求和惡意位置共享請求,用戶的策略集合為共享位置信息和拒絕提供位置信息?；诓┺睦碚摲治霾┺碾p方的決策時,還需定義不同策略下的收益。

EU:第三方敵手惡意位置共享請求且用戶拒絕共享位置信息時,LBS用戶的收益。該收益為用戶保護了自身位置信息的安全性,避免了位置信息與惡意第三方共享所帶來的生活、財務上的困擾。

基于上述定義,LBS用戶和第三方敵手的博弈矩陣如表2所示。

表2 LBS用戶和第三方的博弈矩陣

對表2中列出的策略收益分析求解納什均衡。從第三方敵手的角度考慮,當?shù)谌綌呈植扇≌\信位置共享請求時,LBS用戶選擇共享位置信息收益最大;當?shù)谌綌呈植扇阂馕恢谜埱髸r,LBS用戶選擇拒絕共享位置信息收益最大。同理,從LBS用戶的角度考慮,當LBS用戶選擇共享位置信息時,第三方敵手采取惡意位置共享請求收益最大;當LBS用戶選擇拒絕共享位置信息時,第三方敵手采取誠信位置共享請求收益最大?？梢?上述博弈并不存在純策略的納什均衡解,下面將以概率的形式求解混合策略下的納什均衡。

不妨設第三方敵手采取誠信位置請求策略的概率為θ,則第三方敵手采取惡意位置請求策略的概率為1-θ;LBS用戶選擇共享位置信息的概率為ρ,則LBS用戶選擇拒絕共享位置信息的概率為1-ρ。由表2和假設可得出第三方敵手和LBS用戶的收益如下。

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

(3)

為使收益最大化,將IT求θ導并定導數(shù)為0,如式(4)所示。

(4)

(5)

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

(6)

為使收益最大化,將IU求ρ導并定導數(shù)為0,如式(7)所示。

(7)

對式(7)進行求解,得到結(jié)果如式(8)所示。

(8)

上述通過熵計算給出了第三方敵手和LBS用戶的收益,并基于混合策略下的納什均衡求解得到第三方敵手誠信位置請求的概率θ,即第三方敵手的誠信值。僅當誠信值不小于用戶設置的共享閾值時,用戶才會與第三方共享位置信息。

4 仿真實驗與結(jié)果分析

本節(jié)在Intel(R) Core(TM) i5-4210U CPU @ 1.70 GHz 2.40 GHz處理器、4 GB內(nèi)存,Windows 10操作系統(tǒng)下進行本方案實驗仿真。實驗代碼采用Python 3.7編寫并于PyCharm上運行,實驗數(shù)據(jù)來源于用戶近期使用百度地圖所產(chǎn)生的位置數(shù)據(jù),并依據(jù)用戶對不同位置數(shù)據(jù)的敏感程度為其分配敏感值。在實驗過程中,首先,第三方敵手向用戶發(fā)起共享位置數(shù)據(jù)請求,用戶通過第三方敵手的信譽等級和當前網(wǎng)絡環(huán)境計算請求值,并與敏感值比較確定共享位置數(shù)據(jù)集合。其次,通過博弈分析得出第三方敵手的誠信值,判斷其是否誠信發(fā)起共享位置數(shù)據(jù)請求。最后,根據(jù)返回的結(jié)果更新第三方敵手信譽等級。實驗從網(wǎng)絡環(huán)境、信譽等級和有效性三方面進行討論分析,驗證本文方案的合理性和有效性。

4.1 網(wǎng)絡環(huán)境分析

本節(jié)分析網(wǎng)絡環(huán)境對第三方敵手誠信值的影響。網(wǎng)絡環(huán)境應是當前網(wǎng)絡狀況如位置共享請求時間、短時間內(nèi)提出請求的人數(shù)和網(wǎng)絡的抗攻擊能力等因素的綜合考量,本文方案根據(jù)網(wǎng)絡環(huán)境值NE的分布范圍將其劃分三個層次。當0≤NE≤0.3時,當前網(wǎng)絡環(huán)境較差;當0.3

考慮三個第三方敵手TA、TB和TC向用戶發(fā)起位置共享請求,其網(wǎng)絡環(huán)境分別為NEA=0.2,NEB=0.5,NEC=0.8。信譽等級相同即CRA=CRB=CRC=CR,權(quán)重系數(shù)分配為α1=0.4,α2=0.6。控制其他參數(shù)不變分析網(wǎng)絡環(huán)境對第三方誠信值的影響,可得到TA、TB和TC誠信值如圖2所示。

通過圖2可以看到網(wǎng)絡環(huán)境因素對第三方敵手誠信值的影響。本文方案選取網(wǎng)絡環(huán)境值0.2、0.5和0.8分別代表網(wǎng)絡環(huán)境較差、中等和較好這三個狀態(tài)。圖2中隨著網(wǎng)絡環(huán)境值的提高,第三方敵手的誠信值逐漸降低。但存在誠信值交集,以信譽等級CR=6為例,此時TA、TB和TC的誠信值分別為NEA=NEB=0.663 7,NEC=0.641 0。盡管TA、TB的網(wǎng)絡環(huán)境值不同,但其請求LBS用戶位置共享時與用戶敏感值比較所獲的共享位置集合是一致的,故而二者誠信值相同。從實驗和理論分析可看出網(wǎng)絡環(huán)境對誠信值的影響是存在的,而文獻[12]與文獻[16]卻并未考慮。

4.2 信譽等級分析

本節(jié)分析信譽等級對第三方敵手誠信值的影響。考慮兩個第三方敵手T1和T2向用戶發(fā)起位置共享請求,意圖獲取用戶近期使用LBS應用時的位置信息。其中:T1的信譽等級為T1=1;T2的信譽等級為T2=9。網(wǎng)絡環(huán)境NE1=NE2=0.5,α1=α2=0.5。通過本文方案,得出T1和T2的誠信值如圖3所示。

圖3 信譽等級分析

通過圖3中的計算可得到T1的誠信值為0.750 0,的誠信值為0.601 8。此外,圖3還補充了不同信譽等級下的第三方敵手誠信值?？梢钥吹?第三方敵手的誠信值隨著信譽等級的提高逐漸降低。信譽等級是在第三方敵手歷史誠信或惡意位置共享請求行為的基礎上建立的,用來約束第三方敵手的行為。一方面,信譽等級越高,證明其誠信位置共享請求次數(shù)越多,能獲取更多的位置共享資源。另一方面,能獲取的位置共享資源越多,越容易使其行為惡意化。從實驗和理論分析可看出信譽等級對誠信值的影響是存在的,文獻[16]基于博弈論分析了第三方敵手對用戶位置隱私信息的疊加性,通過閾值比較判斷了敵手的合法或非法行為。該方案只對合法的第三方提供位置信息,未考慮設定信譽等級對非法的第三方進行懲罰。

4.3 有效性分析

本節(jié)對方案的有效性進行分析。本方案有效性是指能否保護用戶的個性化位置隱私安全,判斷第三方敵手的誠信或惡意位置共享請求行為并進行懲罰。方案假定第三方敵手的信譽等級為2級,讓其對LBS用戶進行10次位置共享請求。用戶的共享閾值設置為0.6,網(wǎng)絡環(huán)境值NE在0至1之間隨機取值,權(quán)重系數(shù)分配為α1=0.4、α2=0.6。為了實驗的公正性,將實驗重復進行50次,取平均值作為有效性分析實驗的最終結(jié)果。得到第三方敵手的位置共享請求次數(shù)和誠信值的關系如圖4所示。

圖4 位置共享請求和誠信值的關系

可以看出,在第1次到第6次位置共享請求中,隨著請求次數(shù)的增加,第三方敵手的誠信值卻一直降低。這是由于前5次第三方敵手的位置共享請求均大于等于用戶所設置的共享閾值,判定為誠信位置共享請求。隨著信譽等級的增加,所獲取的位置共享資源變多,誠信位置請求的概率下降。而在第7次位置共享請求時,第三方敵手的誠信值有所上升。原因是第6次第三方敵手的請求被判定為惡意請求,未能獲得用戶的位置共享信息集合且遭到信譽等級降低的懲罰,從而使其第7次請求時所獲取的位置共享資源減少。故而當?shù)谌綌呈值?次位置共享請求時,誠信值有所上升。通過上述實驗和分析,本文方案能檢測第三方的惡意行為并進行懲罰,有效保護用戶的位置隱私,促使用戶更加主動地使用基于位置的服務。

5 結(jié) 語

針對第三方和用戶位置共享中存在的隱私保護問題,提出一種基于博弈論的個性化LBS用戶位置隱私保護方案。首先,LBS用戶為位置隱私共享設置共享閾值。其次,當?shù)谌较蛴脩舭l(fā)起位置共享請求后,通過靜態(tài)博弈理論分析第三方敵手和LBS用戶的行為策略,基于混合策略納什均衡的求解確定第三方敵手的誠信值。當誠信值大于等于共享閾值時,第三方才能獲得用戶的位置信息共享資源。否則視為惡意位置共享請求,將其信譽等級降低作為懲罰,影響下一次提出位置共享請求時所獲得的位置信息共享資源。本文方案能有效保護用戶的位置隱私,并對惡意的第三方敵手進行懲罰。下一步的研究工作包括:第一,在Foursquare數(shù)據(jù)集[21]上進一步完善并驗證分析方案的可擴展性;第二,在信譽等級的設計中融入更多的因素,構(gòu)建更加適合LBS用戶個性化位置隱私保護的信譽等級機制。