路網環境下的語義多樣性位置隱私保護方法

曾海燕，左開中，王永錄，劉 蕊

1.安徽師范大學 計算機與信息學院，安徽 蕪湖241002

2.安徽師范大學 網絡與信息安全安徽省重點實驗室，安徽 蕪湖241002

1 引言

隨著移動設備和社交網絡的廣泛使用，基于位置的服務（Location Based Service，LBS）已得到了廣泛關注[1]。然而，在用戶提交位置以獲取相關服務的過程中必然會導致隱私泄露問題[2]。因此，如何保護LBS中用戶隱私已成為眾多學者關注的焦點。

現有的LBS隱私保護研究主要針對自由空間[3-6]，但在現實生活中，用戶的移動會受到道路網絡的限制。直接將自由空間中的隱私保護技術應用到路網環境下會造成不同程度的隱私泄露。如圖1（a）所示，將用戶與其他4 個用戶匿名在一起，滿足用戶的5-匿名條件，混淆用戶真實位置。但是在路網環境下，路網結構已知，由于該區域中只包含一條路段，并且該路段上只有一個用戶，因此，該區域不滿足匿名條件，無法滿足用戶的隱私需求，使得攻擊者追蹤到用戶。

圖1 用戶運動空間

現有的針對路網環境下的位置隱私保護方法主要是基于K-匿名和路段L-多樣性，即匿名集中不僅要滿足用戶的位置K-匿名需求，還至少包含L 條不同的路段[7]。文獻[8-11]均采用上述方法構建匿名集，以滿足用戶的隱私要求，但是無法抵御語義推斷攻擊[12]。針對路網環境下的語義推斷攻擊，Yigitoglu等人[13]針對敏感語義位置泄露問題，將整個地圖網絡劃分成若干個不相交的匿名集，實現隱私保護。但該方法構造的匿名集過大。Li 等人[14]提出將路網進行Voronoi 劃分，解決路網環境下語義位置隱私泄露問題。然而，上述方法中語義位置和道路交叉口在路網中均以節點表示，當某處包含多個語義位置時，則無法在路網中表示，且構造的匿名集中語義位置類型差異性較大，易于區分。陳慧等[15]針對路網環境下由位置語義分析造成敏感位置信息泄露問題，充分考慮了位置普及度與敏感度，提出了一種滿足用戶個性化隱私需求的位置隱私保護方法。該方法將語義位置分布在路段上，構建的路網模型符合實際，但是可能造成用戶所處語義位置類型所占比例過大，造成隱私泄露。

綜上所述，路網環境下，針對語義推斷攻擊的隱私保護方案主要有以下不足：

（1）匿名集中包含的語義位置類型差異性較大，攻擊者可根據相關背景知識，縮小匿名集范圍，從而推測出用戶當前所處位置。

（2）匿名集中用戶所處語義位置類型所占比例較大，增加攻擊者推測出用戶所處語義位置的概率。

針對上述問題，提出了一種路網環境下的語義多樣性位置隱私保護方法，通過添加與用戶所處語義位置類型相似的語義位置，提高用戶所處語義位置的不可區分性和不確定性，可更有效地抵御語義推斷攻擊。

2 預備知識

2.1 語義路網模型

本文將道路網絡抽象成無向圖，無向圖中的頂點表示道路交叉口，無向圖中的邊表示道路網絡中的路段。將地圖上的語義位置分布在無向圖中的邊上。

定義1（語義位置（Semantic Location））路段上的語義位置用SL(slid,eid,x,y,sltype,Vsltype)表示，其中：slid表示語義位置編號；eid 表示語義位置所在路段的編號；(x,y)表示語義位置的坐標；sltype表示語義位置所屬的類型，所有語義位置劃分成m 種類型，則SLtype=是所有語義位置類型的集合；Vsltype表示該類型語義位置在不同時間段的用戶訪問數，，其中，表示在tn時間段內該類語義位置的用戶訪問數。

定義2（語義路網）語義路網用無向圖G=(V,E,SL)表示，其中：V 是圖中頂點集合，V={v1, v2,…,vn}，表示道路交叉口；E是圖中邊的集合，E={e1,e2,…,en}，表示路段；SL 是圖中語義位置的集合，SL={sl1,sl2,…,sln}。如圖2所示。

圖2 語義路網

2.2 相關定義

定義3（隱私需求）對一個發出LBS 請求的用戶u，其隱私需求用PD(NU,NS,NE,MAXNE)表示，其中，NU 為匿名集中用戶需求的用戶數；NS 為匿名集中用戶需求的語義位置類型數；NE 為匿名集中用戶需求的路段數；MAXNE 為匿名集中用戶可容忍的最大路段數。

定義4（匿名集）匿名集是由用戶所在路段及其若干條相鄰路段組成，用AS 表示，AS={e1,e2,…,en} 。匿名集滿足用戶定義的各項隱私需求。

為了獲取不同類型語義位置在不同時間段的用戶訪問情況，利用微軟亞洲研究院提供的Geolife 數據集提取用戶的停留點數據。該數據集可通過http：//research.microsoft.com/en-us/projects/geolife/下載獲取。Geolife數據集收集了182位用戶在北京的軌跡數據，將提取的停留點數據與地圖上獲取的興趣點數據進行匹配。不同時間段各類語義位置的用戶訪問分布情況如圖3所示。

圖3 用戶訪問分布

由圖3可以看出，不同類型語義位置一天的用戶訪問數量變化趨勢大體相似，因此采用歐氏距離作為語義位置類型相似度度量方法。

定義5（語義位置類型相似度）假設兩個語義位置類型分別為sltypep和和分別表示類型為sltypep和sltypeq的語義位置在不同時間段的用戶訪問數。根據歐式距離計算公式計算兩個語義位置類型的相似度。

歐式距離越小，兩個語義位置類型的用戶訪問數差距越小，意味著兩個語義位置類型的相似度越高，攻擊者能夠區分的概率越小。

定義6（最優語義位置類型集）最優語義位置類型集BESTsltype是指在所有語義位置類型中，與用戶當前所處語義位置所屬類型相似度較高的前NS個語義位置類型（不包含用戶當前所處語義位置類型），表示為，其中，表示與用戶當前所處語義位置類型相似度較高的語義位置類型。

定義7（最優路段）最優路段是指候選路段中最能滿足用戶隱私需求的路段。通過計算屬于最優語義位置類型的語義位置數占該路段上語義位置總數的比例，選擇比例值最大的路段作為最優路段。該比例由以下公式計算：

2.3 系統結構

LBS 中，現有的隱私保護系統主要分為三種：獨立結構、中心服務器結構和分布式結構。本文采用中心服務器結構[2]。該結構由移動用戶、匿名服務器和LBS服務器三部分組成，如圖4所示。匿名服務器包含匿名模塊、通信模塊和查詢結果求精模塊。其中，匿名模塊是負責對用戶位置進行匿名處理；通信模塊是負責與其他實體進行通信；查詢結果求精模塊是負責對LBS服務器返回的結果進行求精。當用戶發出請求時，將自己的位置、查詢內容和隱私需求發送給匿名服務器。匿名服務器根據隱私保護算法進行匿名處理，并將處理后的信息發送給LBS 服務器。LBS 服務器計算出候選查詢結果集并返回給匿名服務器。匿名服務器對LBS 服務器返回的結果進行篩選，并將精確結果返回給用戶。本系統中，匿名服務器需要保存當前的地圖信息，語義位置信息和不同語義位置類型的用戶訪問分布情況。

圖4 中心服務器系統結構

在本文系統中，對攻擊者做出如下假設：

（1）攻擊者可以獲得地圖數據，了解各類語義位置的詳細信息，包括位置分布情況和用戶訪問分布情況。

（2）攻擊者了解道路上用戶的數量。

（3）攻擊者可以截得匿名服務器發送給LBS服務器的信息。

2.4 攻擊模式

語義推斷攻擊是指通過分析用戶所使用的匿名集中各類語義位置信息，推測用戶所在的精確位置或行為習慣[12]。如圖5 所示，圖中虛線框內的路段構成用戶的匿名集。圖5（a）所示的匿名集S1 中只包含一種語義位置類型，則可認為用戶當前所處位置為醫院，進而推測出用戶的身體狀況可能不佳。圖5（b）所示的匿名集S2中包含兩種語義位置類型，滿足語義多樣性，但是如果用戶在夜里12 點發出LBS 請求，考慮到此時學校人數較少，便可將語義位置類型為學校的用戶排除，進而排除該用戶所在的路段，并推斷用戶當前處于醫院；并且，S2 中醫院面積約占匿名集面積的2/3，則用戶被認為在醫院的可能性更大。

圖5 語義推斷攻擊

3 基于語義位置多樣性算法

3.1 算法設計

根據上述分析，在路網環境下構造匿名集時，不僅要考慮匿名集中的用戶位置數和路段多樣性，還需考慮匿名集中的語義信息。而只考慮語義位置類型多樣性往往并不能保證匿名集的安全性，還需考慮匿名集中語義位置類型相似性，提高用戶語義位置的不可區分性，使得攻擊者在一定背景知識下，無法推斷出用戶所在語義位置信息。因此，本文提出了一種語義多樣性的位置隱私保護算法，既滿足了用戶的K-匿名、路段L-多樣性和語義多樣性需求，又可抵御語義推斷攻擊。該算法的主要思想流程如圖6所示。

算法主要步驟為：

（1）將用戶所在路段加入到匿名集AS 中。

（2）根據用戶所在語義位置類型，通過計算語義位置類型相似度構造最優語義位置類型集BS。

圖6 算法思想流程

（3）將當前匿名集AS 的所有相鄰路段加入到候選路段集CS 中。

（4）從候選路段集CS 中選擇最優路段加入到匿名集AS 中。

（5）匿名集AS 滿足隱私需求，返回AS；否則，重復執行步驟（3）～（5）直至匿名成功。

算法1 給出了語義多樣性算法（Semantic Diversity Algorithm，SDA）的偽代碼。首先對一些變量進行初始化（第1行），將用戶所在路段加入到匿名集AS 中（第2行），并根據用戶當前所屬的語義位置類型sltype和隱私需求PD(NS)，根據公式（1）計算結果構建最優語義位置類型集BS（第3 行）；然后找到當前AS 的所有相鄰路段，加入到候選路段集CS 中，并從CS 中找到最優的一條路段加入到AS 中（第4～7 行）；判斷當前匿名集AS 是否滿足隱私需求。滿足，則返回當前匿名集AS；不滿足，則循環執行（第4～9 行），直至AS 滿足隱私需求。

算法1 語義多樣性算法

輸入：用戶u 位置(x,y)，隱私需求PD。

輸出：匿名集AS。

1.初始化變量：匿名集AS={?}，候選路段集CS={?},最優語義位置類型集BS={?}；

2.根據用戶位置確定所在路段e1，AS={e1}，當前位置所屬的語義類型sltype；

3.根據sltype和PD(NS)，根據公式（1）計算結果構建最優語義位置類型集BS；

4.While AS ≠?

5.將AS 的所有相鄰路段加入候選路段集合CS 中；

6.bestedge=OSLTR（AS，CS，BS）；//調用算法2（OSLTR），選擇最優路段

7.將bestedge 加入AS 中；

8.if（Numberuser（AS）>PD（NU）and

NumberNS（AS）>PD（NS）and

（NumberNE（AS）>PD（NE）

&&NumberNE（AS）

9.return AS

10.break

11.end if

12.end while

在最優路段的選擇問題上本文提出了一種基于最優語義位置類型比（Optimal Semantic Location Type Ratio，OSLTR）路段選擇算法。該算法的主要思想是：計算候選路段集CS中每條路段上屬于最優語義位置類型集的語義位置在該路段上所占的比例，選擇比例值最大的路段作為最優路段，加入匿名集AS中。算法2給出了OSLTR算法的偽代碼。

算法2 基于最優語義位置類型比路段選擇算法

輸入：當前匿名集AS，候選路段集CS，最優語義位置類型集BS。

輸出：最優路段bestedge。

1.計算AS 中不包含的最優語義位置類型集BS′AS；

2.if(BS′AS?)

3.for each ei∈CS

5.for each ej∈CS′

6. 根據公式（2）計算W(ej)，并將結果存入Max 集合中；

7.end for

8.將Max 中最大值所對應的ej賦給bestedge；

9.end for

10.else

11.for each ei∈CS

12.根據公式（2）計算W(ei)，并將結果存入Max 集合中；

13.end for

14.將Max 中最大值所對應的ei賦給bestedge；

15.end if

16.return bestedge

算法2首先將匿名集AS 中不包含的最優語義位置類型加入到BS′AS（第1行）；如果BS′AS不為空，則從候選匿名集CS 中找到包含BS′AS中語義位置類型的路段，加入到CS′，根據公式（2）計算CS′中每條路段上屬于最優語義位置類型集的語義位置所占的比例，并將結果存入Max 集合中，將Max 中最大值所對應的路段賦給bestedge（第2～8 行）；如果BS′AS為空，則根據公式（2）計算CS 中的每條路段上屬于最優語義位置類型集的語義位置所占的比例，并將結果存入Max 集合中，將Max 中最大值所對應的路段賦給bestedge（第11～14行）；最后返回最優路段bestedge。

3.2 算法分析

SDA 算法生成的匿名集采用降低位置信息粒度的方法保護用戶位置隱私。匿名集同時滿足了隱私需求中對位置、路段和語義多樣性要求。隱私需求中NU滿足K-匿名模型，保護用戶身份標識；NS滿足路段L-多樣性，將用戶真實位置隱藏在NS 條的不同路段中；NE 滿足語義多樣性，保護用戶真實語義位置信息。

SDA 算法在考慮K-匿名、路段L-多樣性和語義多樣性的基礎上，還考慮到匿名集中語義位置類型的相似性和不同類型的語義位置在匿名集中占比情況。利用語義位置類型的用戶訪問分布來計算相似性，選擇最優語義位置類型，使得匿名集中語義位置類型不易區分，當攻擊者根據語義位置類型訪問情況進行攻擊時，可以保證用戶語義位置類型被推測出的概率不大于1/NE。每次添加的最優路段是屬于最優語義位置類型的語義位置數最多的路段，增加匿名集中屬于最優語義位置類型的語義位置所占比例，從而降低屬于用戶語義位置類型的語義位置所占比例，使得攻擊者在根據匿名集中語義位置類型分布情況進行攻擊時，減小推測出用戶語義位置類型的概率。

因此，相比K-匿名、路段L-多樣性等方法，SDA 算法能夠針對語義推斷攻擊，提供更有效的隱私保護。

4 實驗及結果分析

4.1 實驗數據及參數設置

本文對比了陳慧等人[15]提出的基于位置語義的路網環境下位置隱私保護算法（LSBASC），LSBASC 算法與本文算法構造匿名集方式相似，都是通過網絡擴張的方式，采用貪心策略，每次選取使匿名集隱私條件最優的路段加入匿名集中。

本文實驗的算法均采用Java 實現，硬件平臺為Intel Core?2 Quad CPU 2.83 GHz，2 GB內存，操作系統為Microsoft Windows 7。實驗數據采用真實數據集，北京市的公路網絡數據，共包括83 884個頂點，109 773條道路。該數據集可通過https：//figshare.com/articles/Urban_Road_Network_Data/2061897下載獲取。并從北京地圖上提取361 916 個語義位置（興趣點）包含10 種類型，假設每個興趣點發送LBS 請求。實驗設置了1 000 個發出查詢請求的用戶。表1 列出了本文實驗參數設置。

4.2 實驗結果分析

本文從相對匿名度、平均匿名時間、隱私泄露程度和相對空間粒度4個方面對算法的性能進行評估。

表1 實驗參數設置

（1）相對匿名度

相對匿名度是指執行算法后匿名集中所包含的用戶數與隱私需求中用戶數的比值。相對匿名度越大，可提供的隱私保護度越高。如圖7 給出了相對匿名度與隱私需求中用戶數的關系。由圖7可以看出，隨著隱私需求中用戶數的增加，相對匿名度逐漸減小，但是相對匿名度都大于1，而SDA算法的相對匿名度一直高于LSBASC 算法。因此，SDA 算法所提供的隱私保護度更高。

圖7 相對匿名度

（2）平均匿名時間

平均匿名時間是指算法成功匿名所用的時間。平均匿名時間越少，算法執行效率越好。如圖8 給出了平均匿名時間與隱私需求中用戶數的關系。由圖8 可以看出，當用戶數小于40 時，SDA 算法的時間要高于LSBASC 算法，大于40 時要低于LSBASC 算法，這是由于LSBASC算法在添加路段時，只要求加入構成區域隱私度最大的路段，這時用戶數少的路段可能構成的隱私度最大，因此需要添加更多的路段來滿足用戶數隱私需求，算法執行次數增加導致匿名時間增加。

（3）隱私泄露程度

圖8 平均匿名時間

本文隱私泄露程度采用匿名集中用戶真實位置所屬類型的語義位置數在匿名集中所占的比例來度量。由圖9 可以看出，SDA 算法的隱私泄露程度一直小于LSBASC 算法，且波動程度小于LSBASC，這是由于SDA算法在生成匿名集時，添加的最優路段是相似語義位置數多的路段，盡量減小真實語義位置類型所占的比例，而LSBASC 算法只考慮的區域的隱私度，并未考慮到該語義位置類型，因此波動較大。所以，由圖可知SDA 算法的隱私泄露程度要低于LSBASC 算法3%，SDA算法的隱私保護效果更好。

圖9 隱私泄露程度

（4）相對空間粒度

相對空間粒度是指隱私需求中可容忍的最大路段數MAXNE 與執行算法后匿名集中路段數的比值[15]。相對空間粒度越大，匿名空間越小，越接近最優解，所提供的服務質量越高。如圖10 給出了相對空間粒度與隱私需求中用戶數的關系。由圖10 可以看出，隨著用戶數的增加，相對空間粒度逐漸下降，這是由于用戶數的增加會導致匿名集中路段數的增加，從而降低相對空間粒度。當用戶數大于20 時，SDA 算法的相對空間粒度一直大于LSBASC 算法，這是由于LSBASC 算法在添加路段時，并沒有考慮到路段上用戶數，每次添加的路段上人數可能較少，導致添加的路段增多，造成匿名空間較大。由圖10 可知，SDA 算法所構建的匿名集空間比LSBASC 算法減小了21%，所提供的服務質量更高。

圖10 相對空間粒度

5 結論

本文針對路網環境下的語義推斷攻擊問題，提出了一種語義多樣性的位置隱私保護方法。該方法針對匿名集中語義位置類型易區分問題，通過計算語義位置類型相似度，選擇相似度較高的語義位置類型構建最優語義類型集，增加用戶所處語義位置類型的不確定性；通過選擇屬于最優語義位置類型集的語義位置占比最大的路段來構造匿名集，降低推測用戶所處語義位置類型的概率。采用真實數據集進行實驗，驗證了本文所提方法的有效性。本文研究是針對快照查詢中的語義位置隱私保護，因此，下一步研究工作是如何保護連續查詢中的語義位置隱私。