一種新型基于位置服務的隱私保護方案

李 蘭 張才寶 奚舒舒 馬鴻洋

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

0 引 言

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

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

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

1 相關工作

位置隱私保護方法根據標準不同可以分為多種類型。本文通過對國內外研究現狀的分析，將位置隱私保護方法分為三類：空間隱匿法[10-12]、虛擬定位法[13-15]、基于原語的密碼學方法[16-18]。

1.1 空間隱匿法

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

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

1.2 虛擬定位法

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

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

1.3 基于原語的密碼學方法

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

在本文中，BT-RCA利用球樹作為空間索引結構，減少搜索鄰居用戶的時間，保證匿名區域生成過程中不產生冗余空間，并結合用戶的距離權重與請求內容權重，有效提高了服務質量。

2 BT-RCA模型

2.1 基本概念

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

(1)

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

定義2區域劃分：假設Reg是一個半徑為r的區域。

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

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

(2)

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

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

(3)

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

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

(4)

用戶ui在用戶組Ut中的距離權重定義為：

(5)

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

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

(6)

定義4內容權重：用戶組Ut的請求內容的權重用βt表示，定義為：

(7)

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

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

(8)

最后在構建的候選用戶組中選擇熵最大的一組。

(9)

2.2 系統模型

本文系統架構如圖1所示，包括MSN用戶、匿名服務器及LBS服務器，并假設匿名服務器是可信的。

圖1 系統架構

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

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

(10)

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

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

收到用戶查詢請求后，匿名模塊根據請求內容構造球樹，完成最近鄰用戶搜索，并用BT-RCA進行匿名性處理。

LBS服務器的查詢結果到達后，候選結果處理模塊會對查詢結果進行選擇，然后將精確結果返回給用戶。

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

(3) LBS服務器：LBS服務器收到來自匿名服務器的請求內容后，開始進行查詢，然后將結果發送回去。

2.3 球 樹

2.3.1球樹的建立

構造球樹的具體流程為：

(1) 先構建一個可以將所有樣本數據包含進去的超球體。

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

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

2.3.2球樹最近鄰搜索

球樹搜索目標點的最近鄰方法如下：

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

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

2.4 BT-RCA

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

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

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

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

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

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

算法1BT-RCA

輸入：真實用戶ureal，匿名度k，執行輪次m，請求內容閾值MinC。

輸出：匿名區域。

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

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

3.if最近鄰用戶數量小于3kthen

4.重新設置k；

5.else

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

7.fori=1tomdo

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

9.計算HA(T)；

10.endfor

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

12.if|Ndisc(ureal)|

13.重新設置MinC；

14.else

15.返回Umax；

16.endif

17.endif

3 安全性分析

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

3.1 抗用戶合謀攻擊

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

(11)

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

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

(12)

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

3.2 抗LBS推理攻擊

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

(13)

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

4 實驗仿真

4.1 實驗環境描述

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

4.2 仿真結果分析

4.2.1匿名區域面積與k值的關系

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

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

圖2 匿名區域面積與k值的關系

圖3 空間分辨率與k值的關系

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

4.2.2匿名區域面積與用戶數量的關系

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

圖4 匿名區域面積與用戶數量的關系

4.2.3熵與k值的關系

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

圖5 熵與k值的關系

5 結 語

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

算法在用戶數量少時效果不佳，以后會考慮如何在用戶稀少地區優化該算法。且算法以匿名服務器可信任為基礎，因此以后會進行一些有效的策略來約束匿名服務器。