劉向宇,劉竹豐,夏秀峰,李佳佳,宗傳玉,朱 睿

(沈陽(yáng)航空航天大學(xué)，計(jì)算機(jī)學(xué)院，沈陽(yáng) 110136)

隨著社交網(wǎng)絡(luò)的蓬勃發(fā)展，帶有簽到服務(wù)的社交應(yīng)用層出不窮，用戶可以在這些應(yīng)用發(fā)布自己訪問(wèn)過(guò)的位置。由于簽到服務(wù)的廣泛使用，用戶的軌跡數(shù)據(jù)不斷地被大量收集。當(dāng)應(yīng)用將軌跡數(shù)據(jù)進(jìn)行公開(kāi)發(fā)布時(shí)，對(duì)用戶的隱私威脅也就隨即產(chǎn)生。

雖然用戶可能在某些敏感位置進(jìn)行位置訪問(wèn)時(shí)避免簽到，但用戶卻難以注意到隱式位置訪問(wèn)隱私的泄露。如圖1(a)所示為用戶u的軌跡集合T，從t1到t5分別是u產(chǎn)生的五條軌跡。而軌跡t1以及各個(gè)位置在地圖上的方位展示在了圖1(b)中，各個(gè)位置的語(yǔ)義信息展示在了圖1(c)中。注意在本文中T都認(rèn)為是一個(gè)特定用戶的軌跡集合，且為了方便表示，每條軌跡都將用位置序列來(lái)表示，序列的每個(gè)元素即是用戶的簽到位置。但一條T中的軌跡可能和它對(duì)應(yīng)的實(shí)際訪問(wèn)軌跡有所不同，例如，給定軌跡t3∈T，其對(duì)應(yīng)的實(shí)際訪問(wèn)軌跡是A→D→G→B→C，而位置B的訪問(wèn)是在軌跡t3中沒(méi)有出現(xiàn)的，這樣的存在過(guò)實(shí)際訪問(wèn)卻不存在于軌跡信息中的位置訪問(wèn)，稱為隱式位置訪問(wèn)。假設(shè)位置B對(duì)于用戶u來(lái)說(shuō)是敏感的，所以用戶拒絕了在軌跡t3中進(jìn)行位置B的簽到。在本文中，一個(gè)位置被考慮為在某個(gè)特定的時(shí)間段對(duì)用戶是敏感的。

圖1 用戶u的歷史軌跡數(shù)據(jù)

為了避免隱私泄露的發(fā)生，本文將采用位置替換技術(shù)來(lái)匿名化特定軌跡從而使泄露概率下降而起到隱私保護(hù)的作用。但是使用位置替換技術(shù)還存在兩個(gè)待解決的問(wèn)題：(1)位置替換后軌跡不符合用戶的行為模式。如果在位置替換后軌跡中出現(xiàn)了新的行為模式，那么攻擊者便很容易辨識(shí)出替換位置。如圖2所示，如果地點(diǎn)B被替換為H，那么就將會(huì)出現(xiàn)兩種新的行為模式且他們的頻度都是1，這樣就很容易被攻擊者識(shí)別出替換位置。(2)位置替換后導(dǎo)致軌跡特征丟失。如圖3所示，虛線即為軌跡t1的軌跡特征，如果地點(diǎn)B被替換為H，軌跡特征將會(huì)被劇烈改變。但是如果將地點(diǎn)B替換為G，這兩個(gè)問(wèn)題都將被有效地解決。

1 相關(guān)工作

伴隨著社交應(yīng)用的使用，用戶數(shù)據(jù)不斷產(chǎn)生，通過(guò)推演技術(shù)能推測(cè)出用戶的重要個(gè)人情報(bào)，也就產(chǎn)生了數(shù)據(jù)中隱含的隱私被泄露風(fēng)險(xiǎn)。而位置隱私保護(hù)則是隱私保護(hù)領(lǐng)域中一個(gè)重點(diǎn)研究方向，目前國(guó)內(nèi)外已經(jīng)提出了多種位置隱私保護(hù)技術(shù)。

圖2 位置替換后行為模式的變化

圖3 位置替換后軌跡特征的變化

第一種使用泛化與失真技術(shù)[2-5]，通過(guò)泛化技術(shù)將位置轉(zhuǎn)換為一個(gè)區(qū)域同樣可以達(dá)到保護(hù)目的。Zheng等[4]人提出一種新的隱形區(qū)域技術(shù)，由用戶位置生成隱藏區(qū)域并選擇其中的子區(qū)域來(lái)代替發(fā)出請(qǐng)求，能夠有效防止攻擊者通過(guò)邊信息進(jìn)行攻擊。通過(guò)考慮一種半可信服務(wù)器框架將移動(dòng)用戶的信息分為三個(gè)部分，再使用基于組合優(yōu)化的隱匿區(qū)域算法將用戶的位置進(jìn)行隱藏[5]。

第二種使用概率預(yù)測(cè)技術(shù)[6-7]。M等[6]人提出一種個(gè)性化隱私保護(hù)系統(tǒng)，針對(duì)用戶自定義的敏感上下文信息進(jìn)行有針對(duì)性的過(guò)濾，這樣整個(gè)系統(tǒng)便可以抑制攻擊者所能增益到的信息，即使攻擊者了解整個(gè)系統(tǒng)且擁有上下文的時(shí)間相關(guān)性。而針對(duì)智能手機(jī)中的上下文感知應(yīng)用激增的情況，通過(guò)考慮和調(diào)整假設(shè)攻擊者的攻擊策略可以通過(guò)學(xué)習(xí)算法來(lái)獲得一種有效防御體系[7]。

第三種使用差分隱私技術(shù)[8-12]。Me等[9]人根據(jù)差分隱私的基本概念提出一種地理不可辨識(shí)性的新概念，通過(guò)對(duì)用戶位置添加雙變量的拉普拉斯函數(shù)的噪音值將其應(yīng)用到LBS服務(wù)中，最終能取得良好的隱私保障?；谶@種地理不可辨識(shí)性，MA等人將差分隱私應(yīng)用到最近鄰查詢中，通過(guò)分類機(jī)制將個(gè)體分為群組，并將質(zhì)心查詢結(jié)果返回給用戶[10]。差分隱私技術(shù)同樣可以應(yīng)用在位置推薦上，且基于空間索引的技術(shù)可以得到優(yōu)質(zhì)的推薦結(jié)果[11]。

第四種使用加密技術(shù)[13-16]。Chen等[13]人構(gòu)建了一種個(gè)性化的排名查詢協(xié)議，不同用戶使用不同密鑰加密位置信息。該協(xié)議可以以不同粒度進(jìn)行查詢，同時(shí)在查詢服務(wù)中模糊化查詢結(jié)果。Maede等[14]人考慮了組內(nèi)成員尋找位置要求聚合距離最小的場(chǎng)景，設(shè)計(jì)了一種組內(nèi)位置隱私協(xié)議，通過(guò)匿名veto網(wǎng)絡(luò)和同態(tài)加密技術(shù)來(lái)保護(hù)所有人的位置隱私。

綜上所述，當(dāng)前位置隱私保護(hù)技術(shù)還存在以下不足：在執(zhí)行保護(hù)處理時(shí)沒(méi)有考慮到軌跡信息含有的用戶行為模式，處理后的新軌跡則很有可能不符合用戶行為模式，而產(chǎn)生這個(gè)問(wèn)題的根本原因則是因?yàn)楫?dāng)前沒(méi)有考慮到各個(gè)位置類別的轉(zhuǎn)移；對(duì)于發(fā)布的軌跡數(shù)據(jù)無(wú)法保證軌跡數(shù)據(jù)可用性，而通過(guò)保持軌跡特征則能有效保證數(shù)據(jù)可用性。

2 預(yù)備知識(shí)和問(wèn)題定義

在本文中，每個(gè)位置li都有其對(duì)應(yīng)的位置名稱和位置類別c(li)，而用戶軌跡集合中曾出現(xiàn)的所有位置類別將組成位置類別集C，其中第i個(gè)類別被表示為C[i]。推演技術(shù)將使用到軌跡數(shù)據(jù)中的移動(dòng)規(guī)則用rule表示。假設(shè)front，back和λ都是用戶曾經(jīng)過(guò)的位置，那么front→back則代表著用戶曾在一條軌跡中先后經(jīng)過(guò)front和back兩個(gè)位置。相似地，front→back?λ代表著用戶曾在一條軌跡中的先后經(jīng)過(guò)front和back的途中還經(jīng)過(guò)了λ這個(gè)位置。已知移動(dòng)規(guī)則rule和軌跡集T，那么T關(guān)于rule的支持軌跡集被表示為ST,rule，它是T的子集，且其中的每條軌跡都滿足移動(dòng)規(guī)則rule，它所包括的所有軌跡總數(shù)為|ST,rule|。

定義1 (隱式位置訪問(wèn))：已知用戶的某條軌跡t和t對(duì)應(yīng)的實(shí)際訪問(wèn)軌跡tTURE，假設(shè)t中滿足移動(dòng)規(guī)則front→back，而tTURE卻還能滿足移動(dòng)規(guī)則front→back?λ，那么此時(shí)就稱軌跡t有移動(dòng)規(guī)則front→back下的隱式位置訪問(wèn)λ[1]。

定義2 (泄露概率)：已知對(duì)用戶敏感的位置λ和關(guān)于該用戶的軌跡集T，那么關(guān)于隱式位置訪問(wèn)λ的泄露概率被表示為[1]：

(1)

公式的分子部分是關(guān)于移動(dòng)規(guī)則front→back?λ的支持軌跡集ST,front→back?λ，稱為推測(cè)軌跡集。公式的分母部分是關(guān)于移動(dòng)規(guī)則front→back的支持軌跡集ST,front→back，稱為條件軌跡集。此公式作為隱式位置隱私推演的基準(zhǔn)公式。推測(cè)軌跡集和條件軌跡集的集合大小，分別稱為推測(cè)軌跡的支持度和條件軌跡的支持度。該公式的求值稱為隱式位置訪問(wèn)λ關(guān)于移動(dòng)規(guī)則front→back的置信度。

定義3 (類別轉(zhuǎn)移概率)：已知關(guān)于用戶u的位置類別集C，和兩個(gè)用戶訪問(wèn)過(guò)的位置li和lj，它們的位置類別分別是c(li)和c(lj)，那么類別從c(li)轉(zhuǎn)移到c(lj)的類別轉(zhuǎn)移概率計(jì)算為：

(2)

其中|c(li)→c(lj)|代表著從位置類別c(li)轉(zhuǎn)移到c(lj)的轉(zhuǎn)移頻度，是指在用戶的軌跡集合中，發(fā)生過(guò)的從屬類別是c(li)的位置轉(zhuǎn)移到從屬類型是c(lj)的位置的轉(zhuǎn)移總次數(shù)，注意li和lj在軌跡中一定具有時(shí)間先后順序和連續(xù)性。同理|c(li)→C|代表著從位置類別c(li)轉(zhuǎn)移到所有類別的轉(zhuǎn)移頻度。

定義4 (特征序列與軌跡特征點(diǎn))：已知軌跡t=l1→…→ln，那么其對(duì)應(yīng)的特征序列為tchar=[lc1,lc2,lc3,…,lcpar-1,lcpar]，其中c1=1,cpar=n且c1

每條軌跡都有其對(duì)應(yīng)的軌跡特征，代表了其主要的運(yùn)動(dòng)特征，如圖4所示，圖中的實(shí)線代表軌跡本身，而虛線則代表其對(duì)應(yīng)的軌跡特征。軌跡特征點(diǎn)是原軌跡中某些特定的能夠代表軌跡運(yùn)動(dòng)特征的點(diǎn)，連接軌跡特征點(diǎn)便形成了軌跡特征，在圖例中，lc1、lc2、lc3和lc4便是原軌跡的特征點(diǎn)，在圖中用空心點(diǎn)來(lái)表示。通過(guò)算法3中的最小描述長(zhǎng)度優(yōu)化原則來(lái)獲得軌跡的特征序列。

圖4 軌跡及其對(duì)應(yīng)軌跡特征

定義5 (軌跡特征保持)：已知一條軌跡t，一個(gè)在t中的位置L的序號(hào)為i以及t對(duì)應(yīng)軌跡特征tchar，那么在替換位置L為L(zhǎng)′后，稱此時(shí)有軌跡特征保持當(dāng)且僅當(dāng)新的軌跡特征tchar′等于：

(3)

問(wèn)題1 (隱式位置訪問(wèn)隱私安全問(wèn)題)：已知特定用戶的軌跡數(shù)據(jù)集T、用戶自定義設(shè)置的敏感位置集SenLoc和泄露概率最大。允許閾值δ，通過(guò)位置替換和位置抑制兩種方法對(duì)軌跡數(shù)據(jù)集的特定軌跡進(jìn)行匿名，使所有泄露概率降低到δ以下，同時(shí)使得匿名軌跡符合用戶行為模式和保持軌跡特征。

3 隱式位置訪問(wèn)隱私保護(hù)

提出一種隱式位置訪問(wèn)隱私保護(hù)算法(Hidden Location Visit Privacy Protection，HLVPP)，具體過(guò)程如算法1所示。算法1基本思想是針對(duì)每條泄露概率的推測(cè)軌跡和條件軌跡的構(gòu)成，對(duì)特定軌跡執(zhí)行位置替換或位置抑制來(lái)匿名化軌跡，最終使泄露概率減小到用戶允許閾值；替換位置時(shí)通過(guò)考慮用戶行為模式，使位置替換后位置類別轉(zhuǎn)移概率最大。同時(shí)關(guān)注原軌跡的軌跡特征是否改變，為提高算法的執(zhí)行效率和合理性，通過(guò)局部軌跡拓展規(guī)則來(lái)檢測(cè)軌跡特征的保持。

算法1隱式位置訪問(wèn)隱私保護(hù)算法(Hidden Location Visit Privacy Protection)

輸入：特定用戶的軌跡數(shù)據(jù)集T,用戶設(shè)置的敏感位置集SenLoc,閾值δ.

輸出：匿名化后的軌跡數(shù)據(jù)集T.

1.Get the Leakage Probability Set PSet;

3.For tinST,front→back?λdo

4.Decrease_Speculation(t,λ,r);

5.frontAround = front.around(r);

6.backAround = back.around(r);

7.For t inST,front→backAround?λor frontAround→back?λdo

8.Add_Condition(t,front,back,frontAround,backAround);

9.For tinST,front→back?λdo

10.t.Suppression(λ);

11.ReturnT;

算法1首先根據(jù)輸入?yún)?shù)執(zhí)行推演攻擊，并返回泄露概率集PSet(1行)。整個(gè)算法的外層循環(huán)中，可以分成三個(gè)子模塊——通過(guò)位置替換來(lái)減小推測(cè)軌跡集(3-4行)、通過(guò)位置替換來(lái)增加條件軌跡(5-8行)、通過(guò)位置抑制來(lái)減小推測(cè)軌跡集(9-10行)，它們的優(yōu)先度依次降低。一旦概率數(shù)值降低到用戶允許閾值δ之下，則退出子模塊所在循環(huán)，并繼續(xù)外層循環(huán)以處理下一條泄露概率。r代表著執(zhí)行位置替換時(shí)原始位置與替換位置之間允許的最大歐式距離，通過(guò)實(shí)驗(yàn)證明當(dāng)r選取300米時(shí)能使尋找替換目標(biāo)時(shí)獲得最大的收益。

在第一個(gè)子模塊中，推測(cè)軌跡集中的每條軌跡會(huì)被循環(huán)遍歷，每當(dāng)成功執(zhí)行一次位置替換，推測(cè)軌跡集大小將減1。Decrease_Speculation函數(shù)的步驟如下：(i)算法2被執(zhí)行以獲得關(guān)于替換位置λ的優(yōu)先位置類別，其中包含各個(gè)位置類別以及對(duì)應(yīng)的類別轉(zhuǎn)移概率；(ii)根據(jù)優(yōu)先位置類別依次搜索屬于特定類別且距離λ小于r的位置集。最后一次搜索則無(wú)類別限制，且位置集中將去掉敏感位置；(iii)依次將(ii)步驟中返回結(jié)果作為替換位置分別執(zhí)行位置替換，并執(zhí)行算法3；(iv)如果(iii)步驟返回結(jié)果為真，那么執(zhí)行當(dāng)前的位置替換并終止函數(shù)，否則(ii)、(iii)和(iv)將重復(fù)執(zhí)行。如圖5所示，將位置B視為被替換位置，第一次搜索過(guò)程中將會(huì)搜索到所屬類別為cinema的位置G作為返回，然后再檢測(cè)若替換位置為G時(shí)是否能使軌跡特征保持。

圖5 對(duì)t_1執(zhí)行Decrease_Speculation函數(shù)

在第二個(gè)子模塊中，front.around(r)將返回距離front小于r的位置集，并將其稱為frontAround，back.around(r)與backAround同理。ST,front→backAround?λ or frontAround→back?λ代表的是類條件軌跡集，其中每條軌跡并不是條件軌跡，并且其中不會(huì)包括敏感位置λ，但通過(guò)替換其中一個(gè)位置為front或者back后就可以成為一個(gè)條件軌跡。執(zhí)行位置替換后條件軌跡集大小加1。

Add_Condition函數(shù)的步驟如下(這里只介紹此函數(shù)處理ST,front→backAround?λ軌跡集中的軌跡時(shí)的步驟，因?yàn)閷?duì)另一種軌跡集ST,frontAround→back?λ的軌跡的處理步驟是完全類似的)：(i)根據(jù)backAround位置集的每個(gè)位置loc，分別替換為back后執(zhí)行算法3；(ii)如果步驟(i)返回結(jié)果為真，且當(dāng)前還沒(méi)有某個(gè)位置將可能會(huì)替換為back的記錄，則將c(back)在算法2返回的優(yōu)先位置類別集中的類別轉(zhuǎn)移概率和當(dāng)前位置loc記錄作record；(iii)如果步驟(i)返回結(jié)果為真，且已有記錄record，則在c(back)的類別轉(zhuǎn)移概率更高的情況更新record，否則不更新；(iv)在遍歷位置集的過(guò)程中，(ii)(iii)將會(huì)被重復(fù)執(zhí)行，遍歷完成后如果record存在，那么記錄的位置loc將會(huì)被替換為back。如圖6所示，在分別將E和I替換為C后，將執(zhí)行算法3判斷二者是否都能使軌跡特征保持。

圖6 對(duì)t_4執(zhí)行Add_Condition函數(shù)

在第三個(gè)子模塊中，Suppression函數(shù)將會(huì)對(duì)一條推測(cè)軌跡中的敏感位置執(zhí)行位置抑制操作，執(zhí)行后，推測(cè)軌跡將會(huì)退化為一個(gè)條件軌跡。此時(shí)，推測(cè)軌跡集大小減1，條件軌跡集大小不變。如圖7所示，t2作為一條推測(cè)軌跡，其中的敏感位置B將會(huì)被刪除，所以t2將不再是一條推測(cè)軌跡。

圖7 對(duì)t2執(zhí)行Suppression函數(shù)

HLVPP算法中將使用到子算法——位置類別優(yōu)先級(jí)算法，具體過(guò)程如算法2所示。算法2基本思想是通過(guò)建立概率轉(zhuǎn)移矩陣返回替換位置的可能類別及其對(duì)應(yīng)的類別轉(zhuǎn)移概率，返回結(jié)果作為替換位置選擇策略。

算法2位置類別優(yōu)先級(jí)算法

輸入：軌跡數(shù)據(jù)集T,位置類別集C,被替換位置L.

輸出：數(shù)組Category-Priority.

1.MN×N,CountNare created;

2.For eachtinTDo

3.Ift.length>= 2

4. Fori←1 tot.length -1 Do

5.Countc(t[i]).index++;

6.Mc(t[i]).index,c(t[i+1]).index++;

7.Get_Probability();

8.Fori←1 toNDo

9.prob=MprevIndex,i×Mi,nextIndex;

10.Category-Priority.add(Category[i] ,prob);

11.Category-Priority.DeleteZero_Sort();

12.Return Category-Priority;

算法2中N為C的大小，概率轉(zhuǎn)移矩陣MN×N和轉(zhuǎn)移計(jì)數(shù)器CountN被初始化(1行)，每個(gè)元素都為0。遍歷軌跡集中的每條軌跡，根據(jù)軌跡中的每次轉(zhuǎn)移對(duì)矩陣和計(jì)數(shù)器進(jìn)行加1操作(2-6行)。Get_Probability函數(shù)將概率轉(zhuǎn)移矩陣元素Mi,j除以Counti得到的數(shù)值賦值給Mi,j(7行)，這樣矩陣的每個(gè)元素就代表著C[i]到C[j]的類別轉(zhuǎn)移概率。prevIndex代表L之前經(jīng)過(guò)prev位置的類別在C中的索引，nextIndex代表L之后經(jīng)過(guò)next位置的類別在C中的索引。prob將計(jì)算出替換位置可能類別的聯(lián)乘類別轉(zhuǎn)移概率。DeleteZero_Sort函數(shù)將刪除數(shù)組中概率為零的位置類別，然后從大到小進(jìn)行排序(11行)。如圖8所示，將t1中的B當(dāng)作被替換位置，那么優(yōu)先搜索類別為cinema的替換位置，以圖1軌跡數(shù)據(jù)執(zhí)行本算法，得到各個(gè)類別轉(zhuǎn)移概率：從restaurant轉(zhuǎn)移到cinema的概率為0.33，從cinema轉(zhuǎn)移到convenience的概率為0.5，再根據(jù)以上數(shù)據(jù)得到從restaurant轉(zhuǎn)移到cinema再到convenience的聯(lián)乘概率為0.33。

圖8 t1中B的替換位置的類別優(yōu)先級(jí)

HLVPP算法中也將使用到子算法——檢測(cè)軌跡特征保持算法，具體過(guò)程如算法3所示。算法3基本思想是通過(guò)最小描述長(zhǎng)度(minimum description length，簡(jiǎn)稱MDL)優(yōu)化的概念獲得位置替換前后的軌跡特征序列，從而檢測(cè)軌跡特征是否能夠保持。MDL由兩組件構(gòu)成[17]:L(H)和L(D|H)，其中H代表某種假設(shè)，而D代表數(shù)據(jù)。而MDL優(yōu)先則是指得到一個(gè)最好的假設(shè)H來(lái)解釋D，使得L(H)和L(D|H)的總數(shù)據(jù)量最小。文獻(xiàn)[18]中使用了MDL規(guī)則得到軌跡的特征序列，其中L(H)對(duì)應(yīng)軌跡的一種特定軌跡特征的長(zhǎng)度，L(D|H)則代表軌跡與軌跡特征之間的總差異量。

算法3檢測(cè)軌跡特征保持算法

輸入：特定軌跡t,被替換位置L,替換位置L′.

輸出：布爾值true或者false.

1.i=t.index(L);

2.range,ChaSe,indexPairs=Part_Traj_Char(t,i);

3.t[i]=L′;

4.indexPairs.Delete_About(i);

5.NewChaSe,MDLCost =Get_ChaSe(t,range,indexPairs);

6.ReturnCheck_Preservation (ChaSe,NewChaSe);

算法3首先獲得了L在軌跡t中的索引i(1行)。Part_Traj_Char函數(shù)將通過(guò)局部軌跡拓展原則來(lái)計(jì)算替換位置周圍局部軌跡的特征序列，返回的range為局部軌跡索引范圍，ChaSe為對(duì)應(yīng)特征序列，indexPairs的每個(gè)元素存儲(chǔ)一個(gè)索引對(duì)形如(j,k)以及從t[j]到t[k]的部分軌跡的MDL消耗(2行)。執(zhí)行位置替換后(3行)，將indexPairs中索引范圍包括了i的索引對(duì)進(jìn)行剔除(4行)，在第5行執(zhí)行Get_ChaSe函數(shù)，將計(jì)算range范圍內(nèi)的t的局部軌跡在最小描述長(zhǎng)度優(yōu)化規(guī)則下求得的軌跡特征序列。Check_Preservation函數(shù)將檢測(cè)位置替換后能否保持軌跡特征，如果符合則返回true，否則返回false。圖9展示了局部軌跡拓展方法，以當(dāng)前隱式位置訪問(wèn)為中心往軌跡的兩端進(jìn)行延伸，每次拓展后進(jìn)行計(jì)算，當(dāng)對(duì)應(yīng)的MDL消耗除以拓展次數(shù)的數(shù)值大于上一次拓展，或者已經(jīng)到達(dá)軌跡兩端時(shí)，拓展停止。

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

本文對(duì)提出的隱式位置訪問(wèn)隱私保護(hù)算法的有效性進(jìn)行評(píng)估。在實(shí)驗(yàn)過(guò)程中，選取兩個(gè)真實(shí)數(shù)據(jù)集Brightkite和Gowalla進(jìn)行實(shí)驗(yàn)和分析。

4.1 實(shí)驗(yàn)設(shè)置

Brightkite和Gowalla是來(lái)自斯坦福大學(xué)公開(kāi)的兩個(gè)軌跡數(shù)據(jù)集，其中包括了用戶的簽到位置信息。在實(shí)驗(yàn)前，對(duì)兩個(gè)數(shù)據(jù)集都進(jìn)行了預(yù)處理，剔除掉美國(guó)加州地區(qū)以外的信息，表1為實(shí)驗(yàn)數(shù)據(jù)集的統(tǒng)計(jì)信息。

圖9 在軌跡t1上的局部軌跡拓展

表1 實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)信息

實(shí)驗(yàn)軟硬件環(huán)境如下：

(1)硬件環(huán)境:Intel Core i5 3.20GHz,4GB DRAM內(nèi)存.

(2) 操作系統(tǒng)平臺(tái):Microsoft Windows 10.

(3) 編程環(huán)境:Python 3.6,Spyder 3.2.6.

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

為了進(jìn)行對(duì)比，本文將文獻(xiàn)[19]中的位置替換算法進(jìn)行了實(shí)現(xiàn)，記作BP。在實(shí)驗(yàn)中為每個(gè)用戶分配隨機(jī)的敏感位置集，并將用戶允許的最大泄露概率設(shè)為0.5，通過(guò)推演泄露概率算法獲所有可能的泄露概率，然后再?gòu)闹刑暨x1000個(gè)泄露概率。根據(jù)每個(gè)用戶關(guān)聯(lián)的所有泄露概率，分別執(zhí)行本文算法后將使所有泄露概率數(shù)值均小于閾值，即用戶的隱式位置訪問(wèn)隱私得到了保護(hù)。

本文采用以下三個(gè)標(biāo)準(zhǔn)衡量保護(hù)結(jié)果。

(3) 運(yùn)行時(shí)間：算法處理運(yùn)行的總時(shí)間。

優(yōu)先類別概率結(jié)果如圖10所示，在兩個(gè)數(shù)據(jù)集上，HLVPP算法的優(yōu)先類別概率都要遠(yuǎn)高于BP算法，這是由于BP算法中簡(jiǎn)單地挑選替換位置的規(guī)則而替換位置根本沒(méi)有考慮到用戶行為模式，HLVPP算法則優(yōu)先搜索屬于優(yōu)先類別的位置候選集。其中HLVPP算法的優(yōu)先類別概率基本穩(wěn)定在90%，而B(niǎo)P算法則在31%左右上下浮動(dòng)。從兩個(gè)數(shù)據(jù)集上的比較來(lái)看，Gowalla數(shù)據(jù)集要略高于Brightkite數(shù)據(jù)集，這是因?yàn)樵贕owalla數(shù)據(jù)集中的位置分布密度要略高于Brightkite數(shù)據(jù)集。

圖10 優(yōu)先類別概率

特征保持概率結(jié)果如圖11所示，在兩個(gè)數(shù)據(jù)集上，HLVPP算法的特征保持概率都要遠(yuǎn)高于BP算法。這是由于BP算法只是從離原始位置一定范圍內(nèi)隨機(jī)選擇替換位置，這樣會(huì)使得替換位置大概率不滿足軌跡特征的保持條件，而HLVPP算法每個(gè)替換位置都經(jīng)過(guò)了特征保持的檢驗(yàn)。其中HLVPP算法的特征保持概率基本穩(wěn)定在91%，而B(niǎo)P算法也是在46%左右穩(wěn)定。

圖11 特征保持概率

運(yùn)行時(shí)間結(jié)果如圖12所示，HLVPP算法在兩個(gè)數(shù)據(jù)集的表現(xiàn)都比較穩(wěn)定，平均運(yùn)行時(shí)間為198ms；而B(niǎo)P算法由于需要執(zhí)行的計(jì)算較少，所以平均運(yùn)行時(shí)間為23ms。

圖12 運(yùn)行時(shí)間

5 結(jié)論

本文針對(duì)隱式位置訪問(wèn)隱私保護(hù)問(wèn)題進(jìn)行研究，提出了一種隱式位置訪問(wèn)隱私保護(hù)算法(HLVPP算法)，通過(guò)位置替換與位置抑制技術(shù)針對(duì)性地對(duì)特定軌跡進(jìn)行匿名化處理。通過(guò)位置類別優(yōu)先級(jí)算法和檢測(cè)軌跡特征保持算法使得匿名軌跡能夠符合用戶行為模式且保持軌跡特征?；谡鎸?shí)軌跡數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果表明HLVPP算法能夠有效保護(hù)隱式位置訪問(wèn)隱私免受推演攻擊，同時(shí)保持軌跡數(shù)據(jù)高可用性。