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

1.安徽師范大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖241002

2.安徽師范大學(xué) 網(wǎng)絡(luò)與信息安全安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖241002

1 引言

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

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

圖1 用戶運(yùn)動空間

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

綜上所述，路網(wǎng)環(huán)境下，針對語義推斷攻擊的隱私保護(hù)方案主要有以下不足：

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

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

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

2 預(yù)備知識

2.1 語義路網(wǎng)模型

本文將道路網(wǎng)絡(luò)抽象成無向圖，無向圖中的頂點(diǎn)表示道路交叉口，無向圖中的邊表示道路網(wǎng)絡(luò)中的路段。將地圖上的語義位置分布在無向圖中的邊上。

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

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

圖2 語義路網(wǎng)

2.2 相關(guān)定義

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

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

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

圖3 用戶訪問分布

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

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

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

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

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

2.3 系統(tǒng)結(jié)構(gòu)

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

圖4 中心服務(wù)器系統(tǒng)結(jié)構(gòu)

在本文系統(tǒng)中，對攻擊者做出如下假設(shè)：

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

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

（3）攻擊者可以截得匿名服務(wù)器發(fā)送給LBS服務(wù)器的信息。

2.4 攻擊模式

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

圖5 語義推斷攻擊

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

3.1 算法設(shè)計(jì)

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

算法主要步驟為：

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

（2）根據(jù)用戶所在語義位置類型，通過計(jì)算語義位置類型相似度構(gòu)造最優(yōu)語義位置類型集BS。

圖6 算法思想流程

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

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

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

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

算法1 語義多樣性算法

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

輸出：匿名集AS。

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

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

3.根據(jù)sltype和PD(NS)，根據(jù)公式（1）計(jì)算結(jié)果構(gòu)建最優(yōu)語義位置類型集BS；

4.While AS ≠?

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

6.bestedge=OSLTR（AS，CS，BS）；//調(diào)用算法2（OSLTR），選擇最優(yōu)路段

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

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

算法2 基于最優(yōu)語義位置類型比路段選擇算法

輸入：當(dāng)前匿名集AS，候選路段集CS，最優(yōu)語義位置類型集BS。

輸出：最優(yōu)路段bestedge。

1.計(jì)算AS 中不包含的最優(yōu)語義位置類型集BS′AS；

2.if(BS′AS?)

3.for each ei∈CS

5.for each ej∈CS′

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

7.end for

8.將Max 中最大值所對應(yīng)的ej賦給bestedge；

9.end for

10.else

11.for each ei∈CS

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

13.end for

14.將Max 中最大值所對應(yīng)的ei賦給bestedge；

15.end if

16.return bestedge

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

3.2 算法分析

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

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

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

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)設(shè)置

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

本文從相對匿名度、平均匿名時(shí)間、隱私泄露程度和相對空間粒度4個(gè)方面對算法的性能進(jìn)行評估。

表1 實(shí)驗(yàn)參數(shù)設(shè)置

（1）相對匿名度

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

圖7 相對匿名度

（2）平均匿名時(shí)間

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

（3）隱私泄露程度

圖8 平均匿名時(shí)間

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

圖9 隱私泄露程度

（4）相對空間粒度

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

圖10 相對空間粒度

5 結(jié)論

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