段海兵， 韓建民， 魯劍鋒， 唐長(zhǎng)兵， 葉榮華

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

0 引 言

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

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

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

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

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

1 分布式啞元生成機(jī)制及分析

1.1 分布式啞元生成機(jī)制

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

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

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

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

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

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

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

1.2 啞元生成模型分析

接下來(lái)將描述一個(gè)分布式用戶協(xié)作的啞元生成機(jī)制，并從博弈論的角度分析這個(gè)模型的性質(zhì),從而構(gòu)建出一個(gè)基于公共物品博弈的啞元生成博弈(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)

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

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

(5)

式(5)中：

(6)

(7)

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

(8)

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

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

2 帶懲罰機(jī)制的啞元生成方法

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

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

(9)

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

(10)

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

(11)

(12)

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

(13)

3 仿真實(shí)驗(yàn)分析

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

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

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

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

4 結(jié) 語(yǔ)

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

由于每個(gè)用戶對(duì)隱私的需求度不同，所以會(huì)影響用戶生成啞元的意愿.隱私需求度高的用戶顯然更傾向于產(chǎn)生多的啞元，如何將用戶的隱私需求度反映到用戶的成本和收益上，是一個(gè)需要考慮的問(wèn)題.未來(lái)將考慮這些因素,進(jì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ù)隱私保護(hù)研究綜述[J].軟件學(xué)報(bào),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.