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

李 蘭 張才寶 奚舒舒 馬鴻洋

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

0 引 言

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

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

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

1 相關(guān)工作

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

1.1 空間隱匿法

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

在文獻(xiàn)[10]基礎(chǔ)上，Mokbel等[12]提出匿名區(qū)域構(gòu)建算法，該算法以Casper模型為基礎(chǔ)，利用匿名服務(wù)器管理空間索引信息，使得到的矩形匿名空間較Interval Cloak算法更小，提高了算法性能。但當(dāng)用戶數(shù)量很少時(shí)，Casper算法會(huì)因?yàn)橐恢闭也坏阶銐虻泥従佑脩魧?dǎo)致匿名區(qū)域構(gòu)建失敗。

1.2 虛擬定位法

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

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

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

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

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

2 BT-RCA模型

2.1 基本概念

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

(1)

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

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

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

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

(2)

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

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

(3)

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

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

(4)

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

(5)

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

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

(6)

定義4內(nèi)容權(quán)重：用戶組Ut的請(qǐng)求內(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ā)送一條查詢請(qǐng)求：

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表示用戶組請(qǐng)求類型多樣性閾值。

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

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

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

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

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

2.3 球 樹

2.3.1球樹的建立

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

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

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

(3) 將得到的每個(gè)子超球體均遞歸執(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)，此時(shí)便可以得出目標(biāo)點(diǎn)與它的最近鄰點(diǎn)的上限的值max，下一步就是對(duì)兄弟節(jié)點(diǎn)進(jìn)行檢查，如果max與兄弟節(jié)點(diǎn)的半徑的和小于目標(biāo)點(diǎn)與兄弟節(jié)點(diǎn)中心的距離，則該兄弟節(jié)點(diǎn)中不會(huì)存在更近的點(diǎn)；否則，必須對(duì)兄弟節(jié)點(diǎn)下的子樹進(jìn)行檢查。

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

2.4 BT-RCA

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

(1) 用球樹搜索算法找到距離ureal最近的3k個(gè)鄰居用戶，存儲(chǔ)在長(zhǎng)度為3k的隊(duì)列中。

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

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

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

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

算法1BT-RCA

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

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

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

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

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

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

5.else

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

7.fori=1tomdo

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

9.計(jì)算HA(T)；

10.endfor

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

12.if|Ndisc(ureal)|

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

14.else

15.返回Umax；

16.endif

17.endif

3 安全性分析

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

3.1 抗用戶合謀攻擊

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

(11)

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

攻擊者又與用戶B合謀，因?yàn)橛脩鬉與用戶B沒(méi)有聯(lián)系，所以推斷成功的概率為：

(12)

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

3.2 抗LBS推理攻擊

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

(13)

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

4 實(shí)驗(yàn)仿真

4.1 實(shí)驗(yàn)環(huán)境描述

算法采用Python編程語(yǔ)言實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為2.4 GHz的雙核CPU，8 GB內(nèi)存，操作系統(tǒng)是Windows 10，在Thomas Brinkhoff[20]上進(jìn)行仿真實(shí)驗(yàn)。在Oldenburg地圖中部，取大約4 km×4 km區(qū)域位置數(shù)據(jù)，區(qū)域劃分塊數(shù)為1 600塊，其中20個(gè)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的增加逐漸增加，空間分辨率逐漸減小。但類四叉樹算法使用四叉樹作為存儲(chǔ)結(jié)構(gòu)，沒(méi)有充分考慮鄰居用戶之間的位置關(guān)系，k由24變化到30的過(guò)程中，該算法產(chǎn)生的匿名區(qū)域面積過(guò)大，算法的空間分辨率不理想。K-DDCA使用kd樹作為存儲(chǔ)結(jié)構(gòu)，雖然k值固定時(shí)構(gòu)造的匿名區(qū)域面積最小，但在隱私保護(hù)中更大的匿名面積意味著更好的隱私保護(hù)效果，該算法構(gòu)造匿名區(qū)域面積過(guò)小，無(wú)法有效保護(hù)用戶隱私安全。

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

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

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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

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