一種基于博弈的LBS隱私保護啞元生成機制

段海兵， 韓建民， 魯劍鋒， 唐長兵， 葉榮華

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

0 引 言

基于位置的服務(wù)(Location Based Services，LBS)給人們的生活帶來了極大便捷，但是LBS需要用戶提供個人的時間和位置等敏感數(shù)據(jù)，這會給個人隱私帶來風(fēng)險[1].近年來，相關(guān)學(xué)者在LBS隱私保護方面做了大量的研究工作[2].

LBS位置隱私是指與用戶當(dāng)前位置相關(guān)的隱私及由位置推斷出來的隱私.目前，保護LBS位置隱私的方法可分為加密法和扭曲法.加密法利用空間加密算法[3-4]使得用戶的位置信息對LBS服務(wù)器不可見，防止用戶隱私信息泄漏.這種方法安全性好，但是計算復(fù)雜度過高，實用性不強.扭曲法是指用戶在發(fā)送個人位置之前，將位置信息進行一些擾動處理，避免暴露用戶真實的位置信息.假位置[5]、時空隱形[6]和差分隱私[7]等都是通過位置扭曲來實現(xiàn)LBS位置隱私保護的方法.由于不精確的位置信息會影響服務(wù)質(zhì)量，這類方法需要權(quán)衡服務(wù)質(zhì)量和隱私保護之間的關(guān)系.

2003年，Gruteser等[8]將k-匿名方法引入到LBS隱私保護領(lǐng)域，提出了位置k-匿名.位置k-匿名要求在某一時空范圍內(nèi)，不可區(qū)分用戶個數(shù)不少于k個，使攻擊者標(biāo)識出用戶位置的概率不大于1/k.目前實現(xiàn)位置k-匿名的方法有時空隱形[9]、空間隱形[10]等.但是，這些方法需要泛化或是改變用戶的位置信息，降低用戶的服務(wù)質(zhì)量.為此，文獻[11]提出了通過生成啞元來實現(xiàn)位置k-匿名，此后，如何生成啞元成為LBS隱私保護領(lǐng)域的研究熱點;文獻[12]提出了基于貝葉斯博弈的啞元生成方法，該方法讓隱私需求高的用戶生成k-1個啞元，但該工作沒有考慮用戶協(xié)作，浪費資源;文獻[13]提出了一個協(xié)作緩存機制，利用其他用戶的歷史位置信息實現(xiàn)位置k-匿名，并利用不完全信息博弈方法解決“搭便車”的問題.然而該方法需要一個中心代理處理用戶數(shù)據(jù)，這會成為服務(wù)的瓶頸和隱私安全的薄弱點.

啞元對當(dāng)前區(qū)域的所有用戶都是有益的，并且啞元的生成需要成本，因此,啞元生成問題可以看作公共物品博弈問題[14].經(jīng)典的公共物品博弈的例子是一個投資游戲：設(shè)有一個資金池和N個投資代理，投入到資金池的資本會按一定的倍數(shù)增值(增值的倍數(shù)大于1小于N)；投資代理獨立選擇自己投入的金額，最終的收益由N個投資代理均分.投資代理投入的成本不同，但是收益相同.因此,會存在非合作者不投入成本，卻會收到與其他代理相同收益的現(xiàn)象，這就是“搭便車”行為.“搭便車”行為會造成投資失敗，因此,如何促進公共物品博弈的合作成為該領(lǐng)域的研究熱點[15-17].

本文提出了一種分布式用戶協(xié)作的啞元生成機制，利用公共物品博弈模型和動態(tài)演化的方法，分析該機制下用戶的行為和系統(tǒng)中位置k-匿名的成功率.“搭便車”用戶不生成啞元，卻可以享受啞元帶來的隱私收益.因此,理性自私的用戶會傾向于等待其他用戶生成啞元,在極端的情況下，還會出現(xiàn)沒有人選擇生成啞元的現(xiàn)象，導(dǎo)致實現(xiàn)位置k-匿名失敗.為了促進用戶合作(即生成啞元)，提高實現(xiàn)位置k-匿名的成功率，本文提出一種針對“搭便車”行為的懲罰機制：當(dāng)一個用戶采取“搭便車”行為時，當(dāng)前區(qū)域的用戶會孤立該用戶.這會使該用戶無法利用其他用戶和啞元實現(xiàn)位置k-匿名.最后,本文通過實驗說明所提出的懲罰機制的有效性.

1 分布式啞元生成機制及分析

1.1 分布式啞元生成機制

LBS隱私保護是在假設(shè)LBS服務(wù)提供商(LBS Provider,LBSP)不可信的[18]的情況下，如何保護LBS用戶的隱私.例如，假設(shè)攻擊者知道了Alice在時刻t1出現(xiàn)在位置l1，并且知道只有一個用戶u1(匿名用戶標(biāo)識符)在時刻t1、位置l1向LBSP方發(fā)出了LBS服務(wù)請求.攻擊者就可推斷出u1的真實身份是Alice.此時，攻擊者就可以根據(jù)u1在LBS中的訪問記錄，知道Alice的某些與位置相關(guān)的隱私信息.更進一步，攻擊者可以根據(jù)這些位置信息分析出Alice的移動模式，推斷出Alice在未來可能會出現(xiàn)在哪些地方.在這個攻擊模型里，攻擊者的目標(biāo)是找到真實用戶與LBS服務(wù)記錄里匿名用戶的對應(yīng)關(guān)系.攻擊者已知的信息是LBS服務(wù)器中的所有記錄，以及真實用戶在某個時刻的位置信息.

針對這種攻擊模型，本文提出了一種分布式的、用戶協(xié)作的啞元生成機制，由同一區(qū)域中的用戶協(xié)作生成所需的啞元，實現(xiàn)位置k-匿名.用戶協(xié)作生成啞元需要構(gòu)建局部自治網(wǎng)絡(luò)，協(xié)調(diào)各個用戶的行為，自治網(wǎng)絡(luò)可以利用WiFi或藍牙實現(xiàn)[14].首先，假定LBS服務(wù)區(qū)域自治網(wǎng)絡(luò)內(nèi)的用戶數(shù)量為N，所有的用戶都需要實現(xiàn)k-匿名.當(dāng)N≥k時，區(qū)域內(nèi)用戶已實現(xiàn)k-匿名，不需要生成啞元.當(dāng)N

第1步：生成啞元的用戶向其他用戶發(fā)送同意協(xié)作的信息，組建協(xié)作團體Gcoop，統(tǒng)計Gcoop中用戶的數(shù)量n；

第2步：分配各自需要生成的啞元任務(wù)，令k-N=a5n+b(a≥0,b≥0)，則Gcoop中每個用戶需要生成a個啞元，再從Gcoop中隨機選擇b個用戶，該b個用戶比其他用戶多生成一個啞元；

第3步：用戶同步生成啞元，并且發(fā)送各自的LBS請求.

若Gcoop中的用戶全部采用合作的策略，則所有用戶都可以順利實現(xiàn)位置k-匿名.但是，生成啞元需要代價.例如，在這個網(wǎng)絡(luò)區(qū)域中的某些用戶，可以選擇不加入Gcoop，而是等待其他Gcoop中的用戶通過協(xié)作產(chǎn)生啞元.當(dāng)該區(qū)域內(nèi)已經(jīng)實現(xiàn)了位置k-匿名時，沒有加入Gcoop的用戶不用付出成本就能享受隱私保護.這就是一種典型的“搭便車”行為.這種“搭便車”行為會影響位置k-匿名的實現(xiàn).

用戶是否選擇“搭便車”是公共物品博弈研究的核心問題之一.下面將從博弈論的角度分析用戶的行為，以及這種行為對實現(xiàn)k-匿名的影響.

1.2 啞元生成模型分析

接下來將描述一個分布式用戶協(xié)作的啞元生成機制，并從博弈論的角度分析這個模型的性質(zhì),從而構(gòu)建出一個基于公共物品博弈的啞元生成博弈(Dummy Generation Game,DGG)模型.

博弈參與人：LBS服務(wù)區(qū)域中用戶自治網(wǎng)絡(luò)的所有用戶Uall={ui|i∈{1,2,…,N}}.其中,N表示當(dāng)前自治網(wǎng)絡(luò)中的用戶總數(shù)，并且N

策略集合:1)合作(C)表示用戶選擇與其他用戶協(xié)作產(chǎn)生啞元的行為；2)非合作(D)表示用戶選擇“搭便車”的行為.

(1)

(2)

(3)

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

(4)

下面用動態(tài)演化方法分析這個模型的合作率(合作者在群體中所占的比率).

在一個混合均勻的無限種群中，x表示合作率，則復(fù)制動態(tài)方程可以寫成[20-21]

(5)

式(5)中：

(6)

(7)

令πC-πD=0，可以得到均衡點x*關(guān)于k,N的方程

(8)

式(8)中，令N=5(N為其他值時，結(jié)果相似)，得到均衡點x*關(guān)于k的解，其理論值隨k變化的情況見圖1.從圖 1 可以看出，啞元生成博弈DGG中合作率較低，此時實現(xiàn)k-匿名的概率也會低.為此，本文提出了一種帶懲罰機制的啞元生成方法(Dummy Generation Game with Punishment Mechanism,DGGPM)，提高了系統(tǒng)中的合作率.

圖1 DGG和DGGPM博弈均衡狀態(tài)合作率理論值

2 帶懲罰機制的啞元生成方法

由以上分析可知，系統(tǒng)中存在大量的非合作者，降低了k-匿名的成功率.為此，本文在啞元生成機制中增加一種懲罰機制，通過降低不合作者的收益，促進合作.在用戶移動終端中添加一個狀態(tài)位τ，用來記錄用戶在上一次博弈中的行為，并且這個狀態(tài)位被本地LBS應(yīng)用控制，用戶無法修改.τ只有2個狀態(tài)0和1.“0”表示采用合作策略，即產(chǎn)生啞元，“1”表示采用非合作策略，即不產(chǎn)生啞元.在每次進入LBS服務(wù)區(qū)域，用戶組建自治網(wǎng)絡(luò)時，此狀態(tài)位就會自動添加到請求報文中.其他用戶不會響應(yīng)狀態(tài)位為1的用戶，即上一次選擇非合作行為的用戶被排除在自治網(wǎng)絡(luò)之外.用戶每次被懲罰后，狀態(tài)位τ自動清零，即用戶的不合作行為只會被懲罰一次.

當(dāng)一個用戶被排除到自治網(wǎng)絡(luò)之外時，其他用戶就不會與其合作，無法通過協(xié)作生成啞元實現(xiàn)位置k-匿名.這種情況下，用戶為了實現(xiàn)位置k-匿名，就必須自己生成k-1個啞元，成本較高.將這種情況構(gòu)建成一個帶懲罰機制的啞元生成博弈方法.此時，非合作者的收益為

(9)

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

(10)

僅考慮混合均勻的無限種群的博弈均衡狀態(tài)，可得到動態(tài)演化過程中合作者的期望收益(式(11)和非合作者的期望收益(式(12)),

(11)

(12)

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

(13)

3 仿真實驗分析

考慮當(dāng)前區(qū)域有N個用戶，分別用DGG和DGGPM兩種方法實現(xiàn)位置k-匿名.利用動態(tài)演化分析這些用戶的行為，根據(jù)式(8)和式(13)，可以得到群體中合作者的比率.從圖1可以看出，在添加懲罰機制后，合作率顯著提高.為了驗證這個結(jié)果，本文將用數(shù)值仿真的方式模擬博弈的過程[15].設(shè)置種群數(shù)量為2 000，初始種群個體隨機賦為合作者和非合作者.每次迭代隨機選取2個個體i和j，并分別隨機選取另外N-1個個體組成2個博弈群體.分別計算i和j的收益pi和pj，令p=(pi-pj)/α(k)，則合作者與非合作者之間的轉(zhuǎn)移概率ptrans為

若ptrans>0，則個體i以概率ptrans取代個體j；反之則相反.按照上述方法，對于k的每個取值，每次動態(tài)演化迭代100 000次，得到合作率，實驗重復(fù)100次，取100次合作率的平均值為最終結(jié)果.最終得到的仿真結(jié)果如圖2所示，與理論結(jié)果一致.

圖2 DGG和DGGPM博弈均衡狀態(tài)合作率仿真結(jié)果

在實際情況下，LBS服務(wù)區(qū)域的用戶數(shù)是變化的，即參與博弈的人數(shù)并不是固定的.為了分析在博弈參與人數(shù)N變化時懲罰機制的有效性，將N在2到k-1之間隨機取值，重復(fù)上述仿真過程，仿真實驗結(jié)果的合作率都接近1，這里省略了實驗結(jié)果的展示.由實驗可知，當(dāng)用戶自由進出LBS服務(wù)區(qū)域時，懲罰機制也能有效減少“搭便車”行為.

4 結(jié) 語

本文提出了一種利用分布式啞元生成機制實現(xiàn)k-匿名的方法.該方法讓用戶以一種“協(xié)作”的方式生成啞元，直到滿足k-匿名的要求.由于啞元具有公共物品的屬性，用戶存在“搭便車”的行為，因此，本文提出了一種針對“搭便車”用戶的懲罰機制.分別針對不帶懲罰機制和帶懲罰機制的用戶協(xié)作啞元生成方法建立了N人雪堆博弈模型，并用動態(tài)演化的方法分析這兩種方法的用戶行為.實驗表明:帶懲罰機制的方法可以明顯減少“搭便車”行為，提高k-匿名的成功率.

由于每個用戶對隱私的需求度不同，所以會影響用戶生成啞元的意愿.隱私需求度高的用戶顯然更傾向于產(chǎn)生多的啞元，如何將用戶的隱私需求度反映到用戶的成本和收益上，是一個需要考慮的問題.未來將考慮這些因素,進一步研究基于公共物品博弈的啞元生成模型.

[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]張學(xué)軍,桂小林,伍忠東.位置服務(wù)隱私保護研究綜述[J].軟件學(xué)報,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.