查詢分割的用戶協(xié)作隱私保護(hù)方法

王斌，張國印，張磊

(1.哈爾濱工程大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001；2.佳木斯大學(xué) 信息電子技術(shù)學(xué)院,黑龍江 佳木斯 154007)

基于位置服務(wù)(location-based services，LBS)的普及，帶來了個人的隱私泄露問題。針對該問題，研究者提出了中心服務(wù)器架構(gòu)[1-9]和無中心服務(wù)器架構(gòu)[10-18]2類隱私保護(hù)方法。在中心服務(wù)器架構(gòu)中，一般使用可信的第三方來提供保護(hù)服務(wù)，包括k-匿名[1]、查詢多樣性[2]、語義多樣性[3]和區(qū)域范圍模糊[8]等多種方法。而無中心服務(wù)器模式又存在2種不同類型：一是對信息加密，利用隱私信息檢索(private information retrieval，PIR)獲取查詢結(jié)果[18]；另一種是通過移動設(shè)備，利用協(xié)作實現(xiàn)真實信息泛化[11]，以及基于協(xié)作用戶的查詢迭代[12]、隨機(jī)行走[16]、協(xié)作緩存[14]和協(xié)作軌跡[15]等。但是，中心服務(wù)器架構(gòu)因其獨立性致使該實體易成為攻擊焦點或服務(wù)瓶頸，而加密方式又占用較大系統(tǒng)資源，因而用戶協(xié)作的架構(gòu)更為流行[17]。隨著研究的深入，發(fā)現(xiàn)該架構(gòu)存在個性化的隱私、連續(xù)隱私服務(wù)及協(xié)作用戶可信問題。針對上述問題，本文提出查詢信息分割隨機(jī)交換的緩存隱私保護(hù)方法(query randomly exchange and results cached algorithm,QRERCA)。本文基于協(xié)作用戶的群智感知，利用協(xié)作用戶提供緩存查詢結(jié)果，將真實用戶隱藏到協(xié)作用戶之后。該方法可實現(xiàn)個性化匿名、連續(xù)查詢隱私保護(hù)和抵御不可信協(xié)作用戶等功能。通過安全性分析和實驗驗證進(jìn)一步證明了所提出的方法具有較高的隱私保護(hù)能力和較好的算法執(zhí)行效率。

1 攻擊模型與隱私保護(hù)模型

1.1 系統(tǒng)架構(gòu)與攻擊模型

由于中心服務(wù)器架構(gòu)存在不足，本文使用協(xié)作用戶和緩存的無中心的系統(tǒng)架構(gòu)。該架構(gòu)包含協(xié)作用戶與基于位置服務(wù)(location-based services，LBS)服務(wù)器2個實體如圖1所示。包括申請者在內(nèi)的用戶稱為協(xié)作用戶，可通過短距離通信完成分割加密后的信息交換。同時還可將結(jié)果緩存，并提供給連續(xù)查詢的其他用戶?；谖恢梅?wù)存在2種服務(wù)類型，攻擊者可針對服務(wù)類型提出2種不同的攻擊方法。

圖1 基于用戶協(xié)作的系統(tǒng)架構(gòu)Fig.1 The system architecture based on collaborative users

在快照查詢中，攻擊行為表現(xiàn)為對獲得的位置集合中真實位置的猜測概率。設(shè)p(i)為不確定位置集合中任意位置屬于申請者的概率，通過申請者可能的查詢，準(zhǔn)確識別申請者位置的概率可表示為：

ps=maxp(i|q)

(1)

式中：當(dāng)ps取最大值時，此時i所代表的位置是申請者提出查詢時所處于的真實位置。

在連續(xù)查詢中，攻擊者對連續(xù)位置集合整合后可獲得位置軌跡，設(shè)攻擊者可利用隱私保護(hù)之前的部分軌跡作為背景知識，通過相似查詢獲得某一位置屬于申請者真實軌跡的概率可表示為：

pc=max(p(li∈T|sim(qu,qi)))

(2)

式中：li表示連續(xù)查詢中的不確定位置集合；T為可能的軌跡；qu表示查詢信息；qi表示攻擊者獲得當(dāng)前位置的查詢信息。整個猜測概率在連續(xù)查詢中轉(zhuǎn)變?yōu)閷Ξ?dāng)前查詢和申請者查詢之間相似性比較，進(jìn)而通過最大值確定當(dāng)前位置是否屬于申請者。

1.2 隱私保護(hù)模型和基本思想

針對上述攻擊方法，可采用的隱私保護(hù)思想為泛化攻擊者的條件概率。具體為：針對快照查詢，泛化每一位置與查詢之間的關(guān)聯(lián)關(guān)系，使得每個查詢與當(dāng)前位置之間存在相等關(guān)聯(lián)關(guān)系；針對連續(xù)查詢，泛化每一次連續(xù)查詢所提供查詢信息，同時減少在連續(xù)查詢過程中與不可信服務(wù)提供者之間的信息交互。

基于以上思想，QRERCA算法可概括為：申請者將查詢分割為至少k份，然后與一跳范圍內(nèi)的協(xié)作用戶進(jìn)行隨機(jī)份數(shù)交換，在保留一份信息后再與其他協(xié)作用戶交換，直至保存的任何信息均為一份或達(dá)到提交要求后將查詢信息提交。在獲得反饋結(jié)果后，所有用戶均將全部結(jié)果保存在緩存中，當(dāng)有其他用戶申請查詢結(jié)果時，該用戶將全部結(jié)果發(fā)送給申請者。若執(zhí)行過程中無法找到滿足匿名值數(shù)量協(xié)作用戶時，算法執(zhí)行失敗。

2 查詢信息分割隨機(jī)交換的緩存隱私保護(hù)算法

2.1 查詢分割交換規(guī)則

QRERCA算法提供以下基本規(guī)則：1)最大最小交換次數(shù)：該規(guī)則用于終止查詢分割交換，以保障服務(wù)效率。在未滿足最小交換次數(shù)的情況下，用戶必須與鄰近用戶進(jìn)行查詢分割交換，直到滿足最小交換次數(shù)。如果經(jīng)過多次交換后，仍未能滿足查詢分割僅為一份，但滿足最大交換次數(shù)時，用戶必須提交查詢分割給LBS服務(wù)器。2)交換分割份數(shù)：為保障攻擊者不能通過查詢分割份數(shù)關(guān)聯(lián)用戶，算法規(guī)定在交換過程中，所交換的分割份數(shù)為1～k-1的隨機(jī)數(shù)，增加用戶查詢信息的隨機(jī)性。3)無查詢的協(xié)作用戶：在整個過程中完全作為參與的用戶，本規(guī)則限定在初始交換時，該用戶僅獲取其他用戶發(fā)送的查詢分割而不進(jìn)行交換。

基于上述原則可得到QRERCA算法的執(zhí)行過程，查詢分割交換為:

Input:當(dāng)前用戶的查詢分割Ma,其他用戶的查詢分割Mother,分割數(shù)量n,用戶數(shù)量u_num

Output:交換后的分割集合Mexc

初始化:Mexc=Null;

if(不存在查詢分割)

return;

else

for(i=1;i<=u_num+1;++i)

n=the blocks number ofMi;

if(n>1)

end if

end

end if

與其他用戶交換Mexc with other user;

算法1在執(zhí)行成功的最壞情況時，算法重復(fù)至少m次才能找尋到足夠的協(xié)作用戶參與匿名，此時的時間復(fù)雜度為O(mn)，當(dāng)m有限時，可認(rèn)為算法的時間復(fù)雜度為O(n)。

2.2 匿名組建立與個性化匿名

個性化匿名如圖2所示：設(shè)存在A、B、C、D、E 5個用戶且匿名值為4、3、2、4、0，最小交換次數(shù)為2、2、1、3、2，m為查詢信息。根據(jù)算法規(guī)則，所有用戶將查詢信息分割為4、3、2、4、0塊。為便于對算法的理解設(shè)用戶E為協(xié)作用戶。如圖2(a)所示，用戶A和D同時與B、C交換，得到如圖2(b)所示的結(jié)果。在圖2(b)中，A的分割數(shù)量未滿足提交要求，則發(fā)起新的申請并與C進(jìn)行隨機(jī)交換，結(jié)果如圖2(c)所示。此時用戶A和C均滿足提交要求且滿足最小交換次數(shù)，因此將查詢分割提交給LBS服務(wù)器，而用戶B和D則需要再次交換，在與協(xié)作用戶E交換后，形成如圖2(d)所示的交換結(jié)果。從圖2(d)中可以看到建立了如[A，B，C，E]、[A，B，E]、[C，D]和[A，C，D，E]所表示的4個匿名組，分別代表不同用戶所設(shè)定的匿名要求，由此實現(xiàn)個性化匿名。

圖2 實現(xiàn)個性匿名的步驟Fig.2 The steps of achieving personalized privacy

經(jīng)過隨機(jī)交換建立匿名組后，所有用戶保存LBS服務(wù)器反饋的查詢結(jié)果。當(dāng)其他用戶經(jīng)過時，可從該用戶獲得其緩存的查詢結(jié)果。

3 安全性分析

3.1 快照查詢下的用戶隱私安全

根據(jù)攻擊者可采用的關(guān)聯(lián)概率攻擊方法，使用信息熵對攻擊成功率加以度量。通常，攻擊者對不確定位置集合的猜測成功率可表示為pi，且所有成功率之和為1，由此針對至少k個不確定位置可得到攻擊者猜測的信息熵H為：

(3)

根據(jù)Jaynes最大熵原理，可知在不確定性最大的情況下，即每一位置猜測的概率相等的情況下，信息熵可取最大值。為驗證在快照查詢下算法的安全性，本文將通過一個雙方博弈加以驗證。

挑戰(zhàn)者A準(zhǔn)備確定的查詢(q1，q2)，并發(fā)送給用戶U；U隨機(jī)選擇c∈[1，2]所表示的查詢qc，同時將收到的查詢分割后混合發(fā)送給A；若A能準(zhǔn)確的找到一個c′使p(qc′)≠p(qc)則A獲勝。由此可得出算法滿足定理1時可抵抗這種攻擊。

定理1 若算法可抵抗基于概率ps=maxp(i|q)的關(guān)聯(lián)攻擊行為，當(dāng)且僅當(dāng)

p(qbi∈qc|qc∈U)=p(qbj∈qc|qc∈U),

?(0

(4)

推論1 QRERCA算法可抵抗這種基于概率的關(guān)聯(lián)攻擊。

證明：對于分割后的任一查詢bi，攻擊者通過該查詢分割可準(zhǔn)確識別申請者的概率為：

(5)

同樣，對于任一查詢分割bj，其準(zhǔn)確識別的概率可表示為：

p(qbj∈qc|qc∈U)=pj/p(qc∈U)

(6)

對于這樣一對查詢分割bi和bj，如果存在

pi=pj,?(0

(7)

則滿足定理1，此時該算法可抵抗基于概率的關(guān)聯(lián)攻擊行為。由于QRERCA算法將查詢分割進(jìn)行交換之后，使用戶的每一個查詢分割都可與該匿名組內(nèi)真實用戶的查詢對應(yīng)，因而攻擊者獲得的查詢概率彼此相等，即pi=pj，由此可取得信息熵最大值，攻擊者對當(dāng)前位置集合具有最大不確定性，即用戶的位置隱私可得到最大的安全保障。

3.2 連續(xù)查詢下的用戶隱私安全

對于連續(xù)查詢下的用戶隱私，假設(shè)攻擊者可掌握部分子軌跡，通過子軌跡可獲得以用戶查詢?yōu)榇淼谋尘爸R。因此攻擊行為可表現(xiàn)為相似查詢確定已知軌跡的概率。設(shè)L和Q分別為攻擊者獲得的經(jīng)過算法在快照查詢下的位置和已知軌跡T獲得的查詢集合，則其中任一位置和查詢之間的關(guān)聯(lián)概率可表示為p(l，q)，其邊際概率分別用p(l) 和p(q)表示，此時集合L和Q之間彼此的互信息I(L;Q)可表示為：

(8)

互信息表示2個隨機(jī)變量之間的相互依賴關(guān)系，如果等于0，則表示兩個隨機(jī)變量不存在關(guān)聯(lián)。

定理2 若算法可抵抗基于概率的關(guān)聯(lián)攻擊，當(dāng)且僅當(dāng)

I(L;Q)=0

(9)

推論2 QRERCA算法可抵抗概率的關(guān)聯(lián)攻擊。

證明：在算法泛化后的位置集合中，每一個位置都可與匿名組中其他用戶相關(guān)聯(lián)，同樣每一個查詢也可以與任意位置相關(guān)聯(lián)，可得關(guān)于位置和查詢之間的邊際概率p(l)=p(q)=1/k，且其聯(lián)合概率為p(l,q)=1/k2，集合L和Q之間的互信息為：

(10)

經(jīng)計算可得出式(10)的結(jié)果為0。此時，攻擊者利用掌握的背景知識所表示的查詢很難與當(dāng)前經(jīng)過QRERCA算法保護(hù)后的位置相關(guān)聯(lián)。

對于不可信用戶，在整個交換過程中，協(xié)作用戶僅獲得不確定的分割查詢，這使得協(xié)作用戶很難通過組合獲得真實查詢內(nèi)容，假設(shè)申請者在建立查詢分割時使用加密方法，使得在未獲得全部分割的情況下協(xié)作用戶無法解密。對于協(xié)作用戶提供緩存服務(wù)的情況，其安全性取決于該用戶緩存的查詢結(jié)果份數(shù)，由于每個協(xié)作用戶均可以獲得滿足其匿名值的多個查詢結(jié)果，所以若該協(xié)作用戶為不可信用戶時，其猜測獲得某一結(jié)果為申請者所需結(jié)果的概率為該協(xié)作用戶收到查詢結(jié)果的1/k。另外，在由于協(xié)作用戶是隨機(jī)選擇的，在眾多的協(xié)作用戶中申請者選中攻擊者的概率為1/k。因此，可認(rèn)為不可信的協(xié)作用戶很難獲得申請者所需的真實查詢結(jié)果。

4 實驗標(biāo)準(zhǔn)與比較實驗結(jié)構(gòu)分析

4.1 實驗評價標(biāo)準(zhǔn)

為驗證算法的隱私保護(hù)效力和執(zhí)行效率，使用BerlinMOD Data Set提供的位置數(shù)據(jù)進(jìn)行模擬，以該數(shù)據(jù)集中心部分并根據(jù)用戶信息生成查詢。所有實驗均在處理器為Core i5 1.70 GHz、4 GB內(nèi)存、Windows 7×64為操作系統(tǒng)的筆記本電腦上通過matlab 7模擬。實驗中所涉及到的相關(guān)參數(shù)如表1所示。

表1 實驗參數(shù)閾值設(shè)定表Table 1 Parameters setting in simulation

隱私保護(hù)效力的驗證將通過信息熵、匿名空間以及緩存使用率等加以對比；執(zhí)行效率則通過個性化匿名成功率、平均運行時間和通信量等加以驗證。實驗結(jié)果將分別與針對快照查詢的P2P-CA[11]算法、QE-cloak[13]算法以及R-cloak[16]算法相比較；同時與針對連續(xù)查詢服務(wù)的enhanced-CaDSA[5]算法、MobiCrowd[14]算法以及LTPPM[15]等算法相比較。

在快照查詢中，信息熵可表示為：

(11)

在連續(xù)查詢中，這種不確定性表現(xiàn)在對信息交互所帶來的位置猜測概率上，此時隱私級別可表示為：

(12)

匿名空間表示協(xié)作用戶的分散程度，在本文中使用匿名組所組成的矩形區(qū)域面積。

緩存的使用率表明申請者與LBS服務(wù)器之間的信息交互程度，緩存使用率越高則與LBS服務(wù)器之間的信息交互越低，緩存使用率為：

λ=Rc/(Rc+RL)

(13)

式中：Rc表示從協(xié)作用戶的緩存中獲得，RL表示查詢結(jié)果從LBS服務(wù)器的信息交互獲得。

個性化匿名的成功率為：

CSR=∑|US|/|S|

(14)

式中：US表示成功實現(xiàn)匿名操作的人數(shù)總和，在連續(xù)查詢中表示n次查詢均實現(xiàn)個性化匿名的人數(shù)總和。S表示快照查詢下所有申請人數(shù)總和，在連續(xù)查詢時表示為所有快照查詢中的總次數(shù)。

平均運行時間表示為快照查詢中的匿名組建立時間，連續(xù)查詢中表示為匿名組建立時間和連續(xù)查詢時獲得結(jié)果所消耗時間的平均值。

通信量表示在不考慮協(xié)作用戶彼此之間進(jìn)行短距離通信的情況下，申請者與LBS服務(wù)器之間的總得通信量，可表示為：

(15)

4.2 實驗結(jié)果

圖3為不同算法產(chǎn)生的信息熵。在圖3(a)中，QRERCA和R-cloak算法均達(dá)到最大熵，這是由于這2種算法既能保護(hù)查詢隱私又能保護(hù)位置隱私，因而攻擊者具有最大的不確定性。QE-cloak算法利用順序拓?fù)溥x擇協(xié)作用戶，其信息熵隨用戶位置的差異性而隨機(jī)波動。P2P-CA算法由于申請者具有最小用戶間距離，攻擊者可利用距離差識別位置，因而其信息熵最小。在圖3(b)中，連續(xù)查詢的信息熵取值隨匿名值與查詢次數(shù)之積逐漸上升。在該圖中QRERCA和enhanced-CaDSA算法均可達(dá)最大熵，這是由于這2種算法最大程度的利用緩存提供間接查詢服務(wù)，降低了信息交互。LTPPM算法由于僅利用相似的移動方向和移動速度，致使后續(xù)服務(wù)很難找到足夠協(xié)作用戶。最后，MobiCrowd算法在無法緩存用戶結(jié)果時需要直接提交查詢，因此該算法的信息熵最低。

圖3 快照和連續(xù)查詢下的信息熵Fig.3 The entropy in snapshot and continuous query

圖4給出了不同算法產(chǎn)生的匿名空間。在圖4(a)為QRERCA、QE-cloak和R-cloak算法可取得最大匿名空間。由于協(xié)作用戶在多跳范圍內(nèi)擴(kuò)散，將位置空間泛化為多跳位置空間。而P2P-CA算法由于協(xié)作用戶位于單跳范圍內(nèi)，其位置空間遠(yuǎn)小于其他算法。在圖4(b)給中，MobiCrowd算法由于每次查詢均需從協(xié)作用戶處獲取結(jié)果，其查詢空間與查詢次數(shù)相互關(guān)聯(lián)，可產(chǎn)生較大匿名空間。QRERCA算法在無法獲得緩存結(jié)果的情況下需重建匿名組，但并不影響匿名空間。enhanced-CaDSA算法使用中心服務(wù)器緩存，申請者主要從中心服務(wù)器獲得結(jié)果而不需建立匿名空間，其連續(xù)查詢下的匿名空間較小。LTPPM算法僅利用相似的移動方向和速度進(jìn)行泛化，致使整個連續(xù)查詢過程中協(xié)作用戶變化最低，因此產(chǎn)生的匿名空間最小。

圖4 快照和連續(xù)查詢下的匿名空間Fig.4 The anonymous space in snapshot and continuous query

本文只考慮在連續(xù)查詢下的緩存使用率。在圖5中，enhanced-CaDSA算法的緩存使用率最高，這是由于中心服務(wù)器可提供更多的緩存服務(wù)，可最大程度的獲得緩存后的查詢結(jié)果。由于最大區(qū)域范圍內(nèi)匿名組包含的協(xié)作用戶眾多，并且協(xié)作用可提供緩存結(jié)果。因此QRERCA算法利用率較高。MobiCrowd算法無法確定協(xié)作用戶是否緩存所需的查詢結(jié)果，因此其緩存使用相對較低。最后，由于LTPPM算法沒有使用緩存，其緩存使用率最低。

圖5 連續(xù)查詢下的緩存使用率Fig.5 The cache hit ratio in continuous query

圖6為各算法的個性化匿名成功率。在圖6(a)中，QRERCA算法可實現(xiàn)最大的個性化匿名，這是由于查詢分割交換可建立適應(yīng)每個用戶的個性化匿名組。而R-cloak和P2P-CA算法僅在較小匿名值時可實現(xiàn)預(yù)設(shè)的匿名值。而QE-cloak算法必需所有用戶共享相同的匿名值，其個性化匿名成功率最低。在圖6(b)中，QRERCA算法仍可取得高于其他算法的個性化匿名率。enhanced-CaDSA算法由于中心服務(wù)器匿名調(diào)配，也可獲得相對較好的個性化匿名率。LTPPM算法由于假設(shè)協(xié)作用戶具有相同的匿名值要求，其個性化匿名成功率相對較低，而MobiCrowd算法未考慮協(xié)作用戶的隱私，導(dǎo)致其個性化匿名成功率最低。

圖6 快照和連續(xù)查詢下的個性化匿名率Fig.6 The success ratio of achieving personalized privacy in snapshot and continuous query

從圖7為不同算法的執(zhí)行時間。在該圖中，所有算法均隨匿名值的增加其平均運行時間線性上升，這是由于這幾種基于協(xié)作用戶的算法需要隨著匿名值的變化尋找協(xié)作用戶，且尋找方法基本相似，因此平均運行時間基本相同。而在連續(xù)查詢中，由于不同算法使用緩存的頻率以及中心服務(wù)器和協(xié)作用戶計算能力的差異，導(dǎo)致平均運行時間稍顯不同。

圖8為不同算法在快照和連續(xù)查詢下的通信量。在圖8(a)中，QE-cloak算法的通信量最大，這是由于該算法利用最大信息熵用戶進(jìn)行查詢提交，因而其通信量遠(yuǎn)高于其他幾種算法。在其他算法中，QRERCA算法的通信量相對較高，這是由于申請者具有一定概率獲得大于自身查詢信息的分割集合，導(dǎo)致通信量稍高。其他兩種算法由于僅提交自身查詢，因此其通信量變化較小。在圖8(b)所示的連續(xù)查詢結(jié)果中，MobiCrowd算法由于每次查詢均需要執(zhí)行該算法，因此其通信量最大。QRERCA算法在無法提供緩存的情況下需重新發(fā)起查詢，其通信量隨著查詢次數(shù)的增多而增大。LTPPM算法由于移動過程中協(xié)作用戶逐漸無法滿足相似性，因而需重新運行算法以尋找協(xié)作用戶，因此其通信量較小。enhanced-CaDSA算法由于利用中心服務(wù)器提供隱私服務(wù)，且由中心服務(wù)器提供緩存服務(wù)，其連續(xù)查詢下的通信量最小。

圖8 快照和連續(xù)查詢下的通信量Fig.8 The communication cost in snapshot and continuous query

綜上，可認(rèn)為QRERCA算法盡管在執(zhí)行時間和通信量上稍差，但可提供遠(yuǎn)好于其他算法的隱私保護(hù)能力，同時可提供個性化隱私和連續(xù)隱私保護(hù)。

5 結(jié)論

1)通過安全性分析，相比于當(dāng)前較為流行的其他同類算法，QRERCA算法在隱私保護(hù)能力和算法執(zhí)行效率等方面具有優(yōu)勢。

2)QRERCA算法在提供隱私保護(hù)能力和服務(wù)質(zhì)量的平衡之間具有更好的優(yōu)勢，因此更適于部署在實際的隱私保護(hù)設(shè)施當(dāng)中。

由于基于統(tǒng)計分析和預(yù)測的方法盛行，使得現(xiàn)有k-匿名模型的隱私保護(hù)能力逐漸捉襟見肘，今后的工作將在如何利用基于統(tǒng)計隱私保護(hù)的模型與用戶協(xié)作架構(gòu)結(jié)合等方面展開。