一種基于博弈的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.