一種新型基于位置服務(wù)的隱私保護(hù)方案

李 蘭 張才寶 奚舒舒 馬鴻洋

1(青島理工大學(xué)信息與控制工程學(xué)院 山東 青島 266000) 2(青島理工大學(xué)理學(xué)院 山東 青島 266033)

0 引 言

在基于位置服務(wù)[1-2](Location-Based Service,LBS)的移動社交網(wǎng)絡(luò)[3](Mobile Social Networks,MSNs)中，用戶通過位置定位設(shè)備查詢附近的興趣點(diǎn)(Point of Interest,POI)[4]，來滿足生活和工作上的需求[5-6]。然而，用戶必須主動提供位置信息和查詢內(nèi)容才能使用這種服務(wù)，當(dāng)包含用戶隱私信息的日志文件被攻擊者竊取后，用戶的職業(yè)、政治觀點(diǎn)和行為模式等很容易被推斷出來[7-8]。因此，當(dāng)務(wù)之急是要有效地保護(hù)用戶的隱私安全。

區(qū)域k-匿名技術(shù)雖然可以將用戶被識別的概率降低到1/k，但這種技術(shù)存在部分問題。首先，構(gòu)建的匿名區(qū)域中除查詢用戶外，其他用戶可能出現(xiàn)分布集中的情況，并可能集中分布在查詢用戶附近，易造成用戶位置隱私泄露。其次，匿名區(qū)域的構(gòu)造過程中可能產(chǎn)生冗余空間。最后，匿名區(qū)域內(nèi)的查詢請求類型可能過于單一，易造成查詢信息泄露。

基于上述原因，本文提出一種新型的基于位置服務(wù)的隱私保護(hù)方案。首先利用基于球樹[9]的匿名區(qū)域構(gòu)造算法(Balltree-Based Anonymous Region Construction Algorithm,BT-RCA)搜索鄰居用戶，與其他搜索算法相比，球樹算法可以提高搜索鄰居用戶的效率。此外，綜合考慮了用戶組中距離權(quán)重與請求內(nèi)容權(quán)重，在構(gòu)建的多個用戶組中，選擇熵最大的一組，有效地保護(hù)了移動用戶的位置信息和查詢內(nèi)容。最后，通過安全性能分析，進(jìn)一步驗證了該方法在隱私保護(hù)方面的有效性。

1 相關(guān)工作

位置隱私保護(hù)方法根據(jù)標(biāo)準(zhǔn)不同可以分為多種類型。本文通過對國內(nèi)外研究現(xiàn)狀的分析，將位置隱私保護(hù)方法分為三類：空間隱匿法[10-12]、虛擬定位法[13-15]、基于原語的密碼學(xué)方法[16-18]。

1.1 空間隱匿法

Gruteser等[10]提出基于四叉樹結(jié)構(gòu)的Interval Cloak算法，該算法結(jié)合k-anonymity[11]思想，將用戶的具體位置信息替代為一個包含至少k個用戶節(jié)點(diǎn)位置信息的區(qū)域向LBS服務(wù)器請求查詢，將用戶被成功推斷的概率降低到1/k。

在文獻(xiàn)[10]基礎(chǔ)上，Mokbel等[12]提出匿名區(qū)域構(gòu)建算法，該算法以Casper模型為基礎(chǔ)，利用匿名服務(wù)器管理空間索引信息，使得到的矩形匿名空間較Interval Cloak算法更小，提高了算法性能。但當(dāng)用戶數(shù)量很少時，Casper算法會因為一直找不到足夠的鄰居用戶導(dǎo)致匿名區(qū)域構(gòu)建失敗。

1.2 虛擬定位法

Hong等[13]提出一種將用戶真實位置替換為附近路標(biāo)或相近位置的算法。Kido等[14]在文獻(xiàn)[13]的基礎(chǔ)上，提出一種匿名通信技術(shù)，可以生成多個虛擬位置，并將其與用戶的位置信息一并發(fā)送給LBS服務(wù)器，更好地隱藏用戶的位置信息。

Wu等[15]提出了多目標(biāo)優(yōu)化算法，綜合考慮了查詢概率和匿名區(qū)域的面積，通過生成的k-1個假位置來實現(xiàn)k-匿名。該算法降低了虛擬位置被過濾的可能性，但算法計算量較大，對MSN用戶設(shè)備要求較高。

1.3 基于原語的密碼學(xué)方法

基于原語的密碼學(xué)方法[16-18]通過對用戶與LBS服務(wù)器的交互信息加密實現(xiàn)隱私保護(hù)目的，可以提供很好的安全性，但用戶與LBS服務(wù)器通信中計算開銷很大，因此這些方案對MSN用戶隱私保護(hù)可行性較差。

在本文中，BT-RCA利用球樹作為空間索引結(jié)構(gòu)，減少搜索鄰居用戶的時間，保證匿名區(qū)域生成過程中不產(chǎn)生冗余空間，并結(jié)合用戶的距離權(quán)重與請求內(nèi)容權(quán)重，有效提高了服務(wù)質(zhì)量。

2 BT-RCA模型

2.1 基本概念

定義1距離度量：用戶ui和uj之間的距離度量(本文使用歐幾里得距離)，定義為：

(1)

式中：x、y分別表示用戶位置的經(jīng)緯度信息。

定義2區(qū)域劃分：假設(shè)Reg是一個半徑為r的區(qū)域。

如果Reg中的用戶與真實用戶ureal的距離度量小于r，則稱這些用戶為ureal的dis_r-鄰域用戶，表示為：

Ndis_r(ureal)={ui∈Reg|dis(ureal,ui)≤r}

(2)

如果Reg中用戶的查詢請求內(nèi)容與真實用戶ureal的查詢內(nèi)容不同，則稱這些用戶為ureal的dis_c-鄰域用戶，表示為:

Ndis_c(ureal)={ui∈Reg|boolean(ureal,ui)=False}

(3)

式中：boolean()是判斷請求內(nèi)容是否相同的函數(shù)。

定義3距離權(quán)重：用αi表示dis_r-鄰域用戶ui的距離權(quán)重，定義為：

(4)

用戶ui在用戶組Ut中的距離權(quán)重定義為：

(5)

與文獻(xiàn)[19]相比，本文不僅考慮到ui在整個鄰居用戶中的權(quán)重，更考慮到ui在固定用戶組中的權(quán)重。

因此用戶組Ut基于距離的熵為：

(6)

定義4內(nèi)容權(quán)重：用戶組Ut的請求內(nèi)容的權(quán)重用βt表示，定義為：

(7)

由此可得用戶組Ut的熵為：

HA(T)=H(Ut)+βt

(8)

最后在構(gòu)建的候選用戶組中選擇熵最大的一組。

(9)

2.2 系統(tǒng)模型

本文系統(tǒng)架構(gòu)如圖1所示，包括MSN用戶、匿名服務(wù)器及LBS服務(wù)器，并假設(shè)匿名服務(wù)器是可信的。

圖1 系統(tǒng)架構(gòu)

(1) MSN用戶：MSN用戶需要向匿名服務(wù)器發(fā)送一條查詢請求：

EM2C={ID,A,k,c,m,l,Cac,MinC}

(10)

式中：ID表示用戶身份；A表示可接受的匿名區(qū)域的最小范圍；k表示區(qū)域匿名度；c表示查詢內(nèi)容；m表示構(gòu)建候選區(qū)域的輪次；l表示用戶位置(x,y)；Cac表示查詢結(jié)果是否需要緩存；MinC表示用戶組請求類型多樣性閾值。

(2) 匿名服務(wù)器：主要包括匿名模塊、候選結(jié)果處理模塊和緩存處理模塊。

收到用戶查詢請求后，匿名模塊根據(jù)請求內(nèi)容構(gòu)造球樹，完成最近鄰用戶搜索，并用BT-RCA進(jìn)行匿名性處理。

LBS服務(wù)器的查詢結(jié)果到達(dá)后，候選結(jié)果處理模塊會對查詢結(jié)果進(jìn)行選擇，然后將精確結(jié)果返回給用戶。

為了減輕LBS開銷，提出匿名服務(wù)器的緩存方案，在查詢請求EM2C中加入?yún)?shù)Cac，其中Cac={0,1}。當(dāng)Cac=0時，表示用戶不再需要本次查詢結(jié)果，結(jié)果返回給用戶后，匿名服務(wù)器便將之丟棄；否則，就將結(jié)果緩存。下次查詢來臨時，匿名服務(wù)器先將緩存反饋給用戶，用戶檢查反饋結(jié)果，若對結(jié)果不滿意，則重新發(fā)送新的查詢。

(3) LBS服務(wù)器：LBS服務(wù)器收到來自匿名服務(wù)器的請求內(nèi)容后，開始進(jìn)行查詢，然后將結(jié)果發(fā)送回去。

2.3 球 樹

2.3.1球樹的建立

構(gòu)造球樹的具體流程為：

(1) 先構(gòu)建一個可以將所有樣本數(shù)據(jù)包含進(jìn)去的超球體。

(2) 在球中選擇一個點(diǎn)A，A點(diǎn)滿足到球心O的距離大于球內(nèi)其他任何點(diǎn)到點(diǎn)O的距離，再從球內(nèi)選擇一個離A點(diǎn)距離最遠(yuǎn)的點(diǎn)B，然后將球中剩余點(diǎn)以距離最近為原則分配到A、B上，當(dāng)所有數(shù)據(jù)點(diǎn)都正好包含于聚類時，逐個計算聚類的中心和半徑。這樣，便得到了兩個子超球體。

(3) 將得到的每個子超球體均遞歸執(zhí)行上述步驟(2)，直至球樹構(gòu)建完成。

2.3.2球樹最近鄰搜索

球樹搜索目標(biāo)點(diǎn)的最近鄰方法如下：

(1) 從根節(jié)點(diǎn)開始貫穿整棵樹查找包含目標(biāo)點(diǎn)所在的葉子節(jié)點(diǎn)，并找出球中距離目標(biāo)點(diǎn)最鄰近的點(diǎn)，此時便可以得出目標(biāo)點(diǎn)與它的最近鄰點(diǎn)的上限的值max，下一步就是對兄弟節(jié)點(diǎn)進(jìn)行檢查，如果max與兄弟節(jié)點(diǎn)的半徑的和小于目標(biāo)點(diǎn)與兄弟節(jié)點(diǎn)中心的距離，則該兄弟節(jié)點(diǎn)中不會存在更近的點(diǎn)；否則，必須對兄弟節(jié)點(diǎn)下的子樹進(jìn)行檢查。

(2) 為了搜索最小鄰近的值，當(dāng)兄弟節(jié)點(diǎn)的檢查結(jié)束后，還需要向父節(jié)點(diǎn)進(jìn)行回溯，直至到達(dá)根節(jié)點(diǎn)，這時最終的搜索結(jié)果就是最小鄰近值。

2.4 BT-RCA

為了對用戶的位置和查詢內(nèi)容等隱私信息進(jìn)行有效保護(hù)，本文提出BT-RCA，算法的步驟如下：

(1) 用球樹搜索算法找到距離ureal最近的3k個鄰居用戶，存儲在長度為3k的隊列中。

(2) 球樹搜索完成后，如果鄰居用戶達(dá)到3k個，則從3k用戶中隨機(jī)選取k-1個用戶與真實用戶構(gòu)成候選用戶組，循環(huán)執(zhí)行m次。

(3) 對組內(nèi)的距離權(quán)重與內(nèi)容權(quán)重進(jìn)行計算，并在m個用戶組中選擇熵最大的一組。

(4) 如果鄰居用戶數(shù)小于3k或組內(nèi)請求內(nèi)容多樣性小于MinC，提醒用戶重新輸入。

BT-RCA偽代碼描述如算法1所示。

算法1BT-RCA

輸入：真實用戶ureal，匿名度k，執(zhí)行輪次m，請求內(nèi)容閾值MinC。

輸出：匿名區(qū)域。

1.初始化隊列q，并設(shè)置|q|=3k；

2.使用球樹算法搜索ureal的最近鄰用戶；

3.if最近鄰用戶數(shù)量小于3kthen

4.重新設(shè)置k；

5.else

6.將最近鄰用戶設(shè)為3k并存入隊列q；

7.fori=1tomdo

8.隨機(jī)從3k用戶中選擇k-1個用戶與ureal組成用戶組U；

9.計算HA(T)；

10.endfor

11.從m個用戶組選擇熵最大的一組Umax；

12.if|Ndisc(ureal)|

13.重新設(shè)置MinC；

14.else

15.返回Umax；

16.endif

17.endif

3 安全性分析

目前存在的攻擊方式主要為合謀攻擊和推理攻擊，兩種攻擊均無法對本文方案造成威脅，現(xiàn)安全性分析如下。

3.1 抗用戶合謀攻擊

BT-RCA在3k個鄰居用戶中隨機(jī)構(gòu)造用戶組U={U1，U2，…，Um}，每個用戶組包括隨機(jī)k-1個鄰居用戶與真實用戶ureal，且考慮到用戶組的距離權(quán)重與請求內(nèi)容權(quán)重，因此組內(nèi)的任一用戶A無法判斷真實用戶ureal的位置。P(X+A)表示攻擊者X與用戶A合謀時推斷真實用戶的概率，有：

(11)

式中：preal表示真實用戶ureal被識別的概率；pi表示組內(nèi)任一用戶被識別的概率。

攻擊者又與用戶B合謀，因為用戶A與用戶B沒有聯(lián)系，所以推斷成功的概率為：

(12)

因此BT-RCA可以成功抵抗用戶合謀攻擊。

3.2 抗LBS推理攻擊

連續(xù)查詢時，LBS服務(wù)器中有真實用戶的查詢記錄，記為：

(13)

匿名服務(wù)器利用緩存提供服務(wù)，這一過程中，用戶與LBS服務(wù)器沒有聯(lián)系，因而LBS服務(wù)器中的歷史離散位置難以關(guān)聯(lián)，為推斷用戶真實位置方面增加了難度。可以說，緩存的使用成功降低了LBS服務(wù)器推斷真實用戶的概率，有效保護(hù)了用戶的位置隱私。

4 實驗仿真

4.1 實驗環(huán)境描述

算法采用Python編程語言實現(xiàn)，實驗環(huán)境為2.4 GHz的雙核CPU，8 GB內(nèi)存，操作系統(tǒng)是Windows 10，在Thomas Brinkhoff[20]上進(jìn)行仿真實驗。在Oldenburg地圖中部，取大約4 km×4 km區(qū)域位置數(shù)據(jù)，區(qū)域劃分塊數(shù)為1 600塊，其中20個POIs是隨機(jī)生成的，用戶數(shù)量由參數(shù)控制。將BT-RCA與K-DDCA[19]和類四叉樹算法[21]進(jìn)行比較。

4.2 仿真結(jié)果分析

4.2.1匿名區(qū)域面積與k值的關(guān)系

空間分辨率[21]指滿足MSN用戶的匿名要求的最小空間面積與匿名算法最終構(gòu)建得到的匿名區(qū)域面積的比值。

由圖2和圖3可以看出，三種算法的匿名區(qū)域面積隨k的增加逐漸增加，空間分辨率逐漸減小。但類四叉樹算法使用四叉樹作為存儲結(jié)構(gòu)，沒有充分考慮鄰居用戶之間的位置關(guān)系，k由24變化到30的過程中，該算法產(chǎn)生的匿名區(qū)域面積過大，算法的空間分辨率不理想。K-DDCA使用kd樹作為存儲結(jié)構(gòu)，雖然k值固定時構(gòu)造的匿名區(qū)域面積最小，但在隱私保護(hù)中更大的匿名面積意味著更好的隱私保護(hù)效果，該算法構(gòu)造匿名區(qū)域面積過小，無法有效保護(hù)用戶隱私安全。

圖2 匿名區(qū)域面積與k值的關(guān)系

圖3 空間分辨率與k值的關(guān)系

BT-RCA使用球樹進(jìn)行存儲，構(gòu)造匿名區(qū)域的過程中不會產(chǎn)生冗余空間，可以避免不必要的查找。當(dāng)k由20增長到25的過程中，空間分辨率變化很小，性能較優(yōu)。該算法構(gòu)造的匿名區(qū)域面積不會太大或者太小，既保證了效率，又避免用戶隱私信息的泄露。

4.2.2匿名區(qū)域面積與用戶數(shù)量的關(guān)系

圖4表示k分別為10和15時，類四叉樹算法與BT-RCA構(gòu)造匿名域面積與用戶數(shù)量的關(guān)系。匿名區(qū)域面積隨用戶數(shù)量增加而減小，當(dāng)用戶數(shù)量大于1 000時，類四叉樹算法與BT-RCA構(gòu)建的匿名區(qū)域面積都逐漸穩(wěn)定。而BT-RCA利用球樹模型，構(gòu)建匿名區(qū)域時不會產(chǎn)生冗余，所以構(gòu)建的區(qū)域面積要比類四叉樹算法小，避免不必要的消耗，性能更加優(yōu)良。

圖4 匿名區(qū)域面積與用戶數(shù)量的關(guān)系

4.2.3熵與k值的關(guān)系

圖5表示以熵的形式來表示不同匿名區(qū)域構(gòu)造方案的隱私級別。隨著k的增加，類四叉樹算法、K-DDCA和BT-RCA的匿名性也隨之增加，但BT-RCA性能最優(yōu)。因為BT-RCA和K-DDCA形成匿名區(qū)域過程中沒有產(chǎn)生冗余空間，而類四叉樹算法則達(dá)不到這種效果，攻擊者可以根據(jù)已有知識排除大量鄰居用戶，因此在一般情況下，類四叉樹算法并不能達(dá)到真正的k匿名。與本文算法相比，由于K-DDCA構(gòu)造的匿名區(qū)域過小，因此無法達(dá)到最好的隱私保護(hù)效果。

圖5 熵與k值的關(guān)系

5 結(jié) 語

以球樹作為存儲結(jié)構(gòu)，本文提出新型的基于位置服務(wù)的隱私保護(hù)方案。利用BT-RCA構(gòu)造匿名區(qū)域，綜合考慮用戶組中的距離權(quán)重與請求內(nèi)容權(quán)重，在m個候選用戶組中選擇熵最大的一組，保證匿名區(qū)域中用戶分布均勻性和請求內(nèi)容多樣性。最后利用Thomas Brinkhoff進(jìn)行仿真，驗證了算法在用戶隱私保護(hù)方面的有效性。

算法在用戶數(shù)量少時效果不佳，以后會考慮如何在用戶稀少地區(qū)優(yōu)化該算法。且算法以匿名服務(wù)器可信任為基礎(chǔ)，因此以后會進(jìn)行一些有效的策略來約束匿名服務(wù)器。