林鄧偉,

(1.焦作大學(xué) 信息工程學(xué)院,河南 焦作 454000; 2.北京郵電大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,北京 100876)

0 概述

近年來,基于位置的服務(wù)(Location-based Service,LBS)開始在交通運(yùn)輸、社交網(wǎng)絡(luò)等多個(gè)領(lǐng)域得到應(yīng)用。以LBS應(yīng)用較為廣泛的車載導(dǎo)航和手機(jī)地圖行業(yè)為例,我國2015年第4季度的前裝車載導(dǎo)航市場(chǎng)出貨量達(dá)125.1萬臺(tái),2016年的中國手機(jī)地圖覆蓋用戶規(guī)模則達(dá)到了4.57億,預(yù)計(jì)到2018年將達(dá)到6.42億。用戶可以利用各種LBS應(yīng)用獲取查詢餐飲、地圖導(dǎo)航等多樣化的服務(wù)。

然而,用戶在獲取多樣化的服務(wù)的同時(shí),卻面臨著位置隱私泄露的風(fēng)險(xiǎn)。當(dāng)前,這一問題正隨著位置服務(wù)應(yīng)用的日益廣泛而成為一個(gè)普遍存在的安全隱患,如2012年的蘋果公司擅自收集用戶位置信息事件、2016年上海廣升的預(yù)裝軟件事件等。調(diào)查顯示,約有9%的免費(fèi)Android應(yīng)用會(huì)向第三方廣告商透漏用戶的手機(jī)號(hào),另有15%應(yīng)用則會(huì)將設(shè)備ID信息泄露出去[1]。文獻(xiàn)[2]的分析結(jié)果顯示,一些位置隱私的泄露會(huì)危及用戶的財(cái)產(chǎn)甚至于生命安全。因此,對(duì)位置隱私的保護(hù)刻不容緩。

目前,位置隱私保護(hù)方法致力于避免攻擊者或不可信第三方獲取用戶身份信息和位置信息的關(guān)聯(lián)性等研究。K-匿名技術(shù)[3-4]是應(yīng)用較為廣泛的技術(shù)之一。針對(duì)單個(gè)查詢的K-匿名技術(shù)通過將用戶身份和位置信息的對(duì)應(yīng)關(guān)系由1∶1轉(zhuǎn)化為K∶1,達(dá)到隱匿用戶位置信息的目的。該技術(shù)通過假設(shè)的可信第三方匿名服務(wù)器完成位置信息匿名。該方法雖然能保護(hù)單個(gè)查詢隱私,但無法保護(hù)用戶的軌跡隱私,也無法防御具有背景信息的位置攻擊,如位置鏈接攻擊[5]、身份匹配攻擊[6]等。為此,研究人員提出了軌跡隱私保護(hù)方法[7-8]。這類方法主要通過生成(K-1)條虛假軌跡保護(hù)用戶真實(shí)軌跡不被識(shí)別。相比于前一種技術(shù),這類方法考慮了位置間的關(guān)聯(lián)性,能夠防御針對(duì)單個(gè)位置的攻擊。但是,虛假軌跡上的位置總是隨機(jī)生成,具有隨機(jī)性,往往存在一些與現(xiàn)實(shí)不符合的位置[9]。這導(dǎo)致攻擊者很容易結(jié)合背景信息排除掉虛假軌跡,影響軌跡隱私保護(hù)效果。

本文針對(duì)軌跡隱私保護(hù)方法中攻擊者容易通過背景信息、虛假軌跡的隨機(jī)性獲取軌跡隱私的問題,考慮背景信息、軌跡相似性,提出一種基于用戶真實(shí)軌跡的虛假軌跡生成方法。以用戶的真實(shí)軌跡為基礎(chǔ),通過分析用戶的行為模式,建立由真實(shí)軌跡構(gòu)建的虛假軌跡。虛假軌跡和用戶的真實(shí)軌跡有相同的運(yùn)動(dòng)模式,能夠保證與用戶真實(shí)軌跡的相似性,同時(shí)也能夠應(yīng)對(duì)背景信息攻擊,以實(shí)現(xiàn)對(duì)用戶軌跡的K-匿名保護(hù)。

1 相關(guān)研究

針對(duì)軌跡隱私保護(hù)問題,當(dāng)前研究主要集中在基于可信第三方服務(wù)器構(gòu)建K-匿名空間、合成虛假軌跡、軌跡隱私度量3個(gè)方面。

構(gòu)建K-匿名空間方法的主要思路是可信第三方服務(wù)器根據(jù)需要保護(hù)的用戶軌跡構(gòu)造一個(gè)至少包括K個(gè)用戶的區(qū)域作為匿名區(qū)域,并把匿名區(qū)域發(fā)送給LBS服務(wù)器實(shí)現(xiàn)軌跡隱私保護(hù)。

針對(duì)K-匿名空間構(gòu)建過程中虛假位置的選擇問題,文獻(xiàn)[10]提出了一種DLS算法。算法通過考慮可能被利用的信息,選擇熵作為度量來選擇虛假位置,達(dá)到構(gòu)建匿名區(qū)域的目的,且能夠擴(kuò)大隱藏區(qū)域,從而高效地實(shí)現(xiàn)K-匿名。DLS算法在構(gòu)建匿名區(qū)域時(shí)需要按照時(shí)間構(gòu)建虛假位置,容易遭受計(jì)時(shí)攻擊。文獻(xiàn)[11]提出R-匿名時(shí)間模糊算法。算法引入時(shí)間混淆技術(shù)來打破用戶查詢順序,使得攻擊者無法預(yù)測(cè)用戶軌跡。但是未考慮攻擊者掌握的背景信息,攻擊者能夠利用背景信息區(qū)分匿名區(qū)域的不合理區(qū)域,預(yù)測(cè)用戶的真實(shí)軌跡。文獻(xiàn)[12]提出了基于位置語義的SALS匿名區(qū)域構(gòu)建方法。SALS方法通過對(duì)不同位置語義賦予不同的權(quán)值,使用戶根據(jù)位置語義的權(quán)值計(jì)算MAXDEN來確定自己的匿名區(qū)域。這使得用戶能夠以對(duì)等(P2P)方式相互配合生成隱藏區(qū)域,而不是實(shí)際位置。

文獻(xiàn)[13]提出了一種基于移動(dòng)終端的虛假軌跡生成方法。該方法依據(jù)用戶真實(shí)軌跡中位置的先后順序,依次選擇與對(duì)應(yīng)位置呈一定角度的方向上的一個(gè)點(diǎn)生成虛假位置,直至生成虛假軌跡。方法生成的虛假軌跡避免了與真實(shí)軌跡的重合,起到了保護(hù)軌跡隱私的效果。但是無法防御擁有背景信息的位置隱私攻擊。文獻(xiàn)[14]提出了一種基于車輛移動(dòng)軌跡的虛假軌跡生成方法。該方法在生成虛假軌跡時(shí),綜合考慮了車輛移動(dòng)的軌跡運(yùn)動(dòng)模式,因而能夠生成與真實(shí)軌跡相似的虛假軌跡,能夠在一定程度上防御擁有背景信息的位置隱私攻擊。但是所生成的軌跡會(huì)存在一些現(xiàn)實(shí)中無法到達(dá)的位置,影響軌跡隱私保護(hù)效果。同時(shí),這些方法雖然能夠保護(hù)軌跡隱私,但是由于虛假軌跡上均為虛假位置,容易被攻擊者使用特定的攻擊手段識(shí)別。為此,文獻(xiàn)[15-16]提出基于真實(shí)用戶軌跡的虛假軌跡生成方法。文獻(xiàn)[15]提出使用用戶的歷史軌跡構(gòu)建虛假軌跡,文獻(xiàn)[16]提出使用真實(shí)存在的用戶軌跡構(gòu)建虛假軌跡的方法。這些方法在構(gòu)建虛假軌跡時(shí),只是基于真實(shí)用戶軌跡來構(gòu)建,但是在特定區(qū)域中尋找相似度較高的用戶軌跡存在較高難度,難以達(dá)到K-匿名。

在軌跡隱私保護(hù)效果的衡量方面,使用較為普遍的度量標(biāo)準(zhǔn)是K-匿名度量?，F(xiàn)有的軌跡隱私的K-匿名度量,主要是選取(K-1)條虛擬軌跡和用戶真實(shí)軌跡一起由可信的第三方服務(wù)器發(fā)送到位置服務(wù)器,從而提高用戶真實(shí)軌跡預(yù)測(cè)的不確定性。但是,現(xiàn)有的基于K-匿名度量的度量方法往往忽略了背景信息的影響或者實(shí)現(xiàn)難度較高。因而軌跡隱私的K-匿名度量需要考慮背景信息和實(shí)現(xiàn)的可行性。

針對(duì)上述問題,本文提出一種基于用戶真實(shí)軌跡的虛假軌跡生成方法。方法通過分析用戶行為模式,通過聚類選取與用戶真實(shí)軌跡具有相同行為模式的其他用戶軌跡作為虛擬軌跡,并通過EMD距離計(jì)算所生成的虛擬軌跡中與用戶真實(shí)軌跡具有最大相似性的(K-1)條軌跡,實(shí)現(xiàn)用戶軌跡的K-匿名保護(hù)。相比于上述文獻(xiàn),本文所提方法有以下優(yōu)點(diǎn):

1)生成的虛假軌跡基于真實(shí)用戶位置,能夠防止出現(xiàn)不符合現(xiàn)實(shí)的虛假軌跡。

2)生成的虛假軌跡與真實(shí)軌跡具有相同的行為模式,能夠較為可靠地實(shí)現(xiàn)軌跡的K-匿名。

3)本文方法構(gòu)建的馬爾科夫模型融入了背景信息,能夠防備具有背景信息的攻擊。

2 基于虛假軌跡的隱私保護(hù)問題分析

如前所述,現(xiàn)有基于虛假軌跡的隱私保護(hù)方法存在的一些問題影響了軌跡隱私保護(hù)的效果。本節(jié)則對(duì)這些問題進(jìn)一步剖析,力圖找出影響軌跡隱私保護(hù)的內(nèi)部機(jī)制,并給出解決這些問題的基本思路。

2.1 背景信息

現(xiàn)有面向軌跡隱私的保護(hù)方法主要以位置服務(wù)中的用戶身份信息和位置信息的關(guān)聯(lián)性為研究對(duì)象。然而,在現(xiàn)實(shí)中,用戶使用其他服務(wù)時(shí)仍然會(huì)泄露身份信息。攻擊者也可以通過一些公共信息,如地圖上的實(shí)際路徑、道路限制等推斷用戶身份信息和位置信息間的關(guān)聯(lián)性。類似這些和用戶軌跡信息無直接關(guān)聯(lián),卻有助于攻擊者獲取用戶隱私的信息就是背景信息。在大數(shù)據(jù)時(shí)代,攻擊者能夠通過各種途徑輕易得到各種背景信息,并結(jié)合軌跡信息對(duì)用戶的身份等敏感信息進(jìn)行推測(cè)。圖1概率分布攻擊顯示了攻擊者利用背景信息推測(cè)用戶真實(shí)位置的情況。

圖1 概率分布攻擊

概率分布攻擊指攻擊者根據(jù)用戶在不同位置的分布情況推測(cè)用戶的位置隱私。在圖1中,A、B、C、D為用戶的真實(shí)軌跡。用戶對(duì)位置D進(jìn)行了K=2的匿名保護(hù),E為生成的虛假位置。假設(shè)攻擊者能夠根據(jù)用戶的歷史軌跡推測(cè)其有80%的概率會(huì)從C位置到達(dá)D位置,則攻擊者獲知用戶在C位置后,就能根據(jù)歷史軌跡這一背景信息推測(cè)出用戶的真實(shí)位置,使D位置匿名失敗。

攻擊者利用歷史軌跡的目的是根據(jù)用戶在各個(gè)位置的服務(wù)請(qǐng)求信息得到用戶的行為模式,并最終得到各個(gè)位置間的關(guān)聯(lián)性。因此,本文將圖1所示情況下的攻擊者的背景信息表達(dá)為用戶在某個(gè)位置發(fā)送服務(wù)請(qǐng)求的概率。同時(shí),參考文獻(xiàn)[17],將每個(gè)位置的服務(wù)請(qǐng)求概率表示為網(wǎng)格地圖中每個(gè)網(wǎng)格的服務(wù)請(qǐng)求概率。

2.2 虛假位置的約束條件

在現(xiàn)有的虛假軌跡生成方法中,存在的問題是采用隨機(jī)方法生成的虛假軌跡中經(jīng)常會(huì)存在一些不滿足約束條件的虛假位置,最終導(dǎo)致用戶的真實(shí)軌跡以較高概率被識(shí)別。

圖2是采用隨機(jī)方法生成虛假軌跡的示例。其中T為由A、B、C、D4個(gè)位置組成的真實(shí)軌跡,T′為由A′、B′、C′、D′ 4個(gè)位置組成的虛假軌跡。假設(shè)用戶以允許的最大速度在此區(qū)域內(nèi)唯一的一條高速公路上行駛,則滿足的約束條件為:1)高速公路的唯一性;2)用戶的最大行駛速度。對(duì)比軌跡T和T′上同時(shí)刻的位置,可以發(fā)現(xiàn)在A′→B′和C′→D′這兩段距離,生成的虛擬軌跡不滿足第2個(gè)約束條件,使得T′以極大概率被排除,影響隱私保護(hù)效果。

圖2 虛假位置約束條件示例

本文選取與用戶軌跡相似的其他用戶的真實(shí)軌跡作為虛假軌跡來解決該問題。獲取區(qū)域內(nèi)滿足條件的虛假軌跡后,通過EMD距離公式選取出與真實(shí)軌跡具有最高相似度的K條虛假軌跡,實(shí)現(xiàn)軌跡K-匿名。

2.3 用戶行為模式

目前,利用用戶的真實(shí)軌跡構(gòu)建虛假軌跡是一種有效的軌跡隱私保護(hù)方法。這種選取與用戶軌跡相似的其他用戶的真實(shí)軌跡作為虛假軌跡。由于組成這些虛假軌跡的位置全部為真實(shí)位置,因此能夠避免不合理位置的存在。然而,考慮到一條軌跡上的位置足夠多時(shí),現(xiàn)實(shí)中任意2個(gè)人的軌跡難以完全相似,容易導(dǎo)致匿名失敗。

針對(duì)這一問題,本文采用基于用戶行為模式的方法構(gòu)建虛假軌跡。假設(shè)被保護(hù)用戶a往返于家庭Ha和工作Wa2個(gè)位置,同時(shí)在特定區(qū)域內(nèi)用戶b也往返于家庭Hb和工作Wb2個(gè)位置,則a和b有相同的行為模式。此時(shí)雖然Ha≠Hb,Wa≠Wb,但是仍然可以用Hb和Wb代替a對(duì)應(yīng)的位置?？紤]到具有相同行為模式的兩條軌跡不一定具有數(shù)目相等的位置點(diǎn),則基于被保護(hù)軌跡的行為模式構(gòu)建虛假軌跡。

3 虛假軌跡生成方法

本節(jié)根據(jù)第2節(jié)的問題,擬從攻擊者角度出發(fā),給出虛假軌跡的生成方法。

3.1 用戶運(yùn)動(dòng)軌跡模型

對(duì)用戶的運(yùn)動(dòng)軌跡建模是合成虛假軌跡的基礎(chǔ)。本文擬從攻擊者角度出發(fā),分析用戶軌跡被重構(gòu)的可能性,從而從整體方面為用戶軌跡隱私保護(hù)提供保證。

定義2軌跡T(U)滿足馬爾科夫假設(shè)。

通常,位置語義對(duì)應(yīng)的是由多個(gè)位置點(diǎn)組成的區(qū)域。如圖3所示,軌跡T上存在6個(gè)位置點(diǎn)、2個(gè)位置語義。其中由A、B、C3個(gè)位置組成的區(qū)域表示超市M,由D、E、F3個(gè)位置組成的區(qū)域表示醫(yī)院N。因此,為了簡化用戶軌跡模型,在定義1的基礎(chǔ)上給出用戶運(yùn)動(dòng)軌跡的定義。

圖3 位置語義和區(qū)域

定義3用戶U在統(tǒng)計(jì)時(shí)長τ內(nèi)的軌跡記錄為T(U)={r0,r1,…,rn}。其中,組成軌跡的rj為U在τj時(shí)間段內(nèi)所在的位置區(qū)域。

根據(jù)定義1～定義3所定義的T(U)滿足馬爾科夫假設(shè),即是用戶在下一個(gè)區(qū)域出現(xiàn)的概率只與其前一個(gè)區(qū)域及由前一區(qū)域向該區(qū)域運(yùn)動(dòng)的轉(zhuǎn)移概率有關(guān)。據(jù)此,給出定義4的用戶運(yùn)動(dòng)軌跡的馬爾科夫模型。

定義4用戶U在統(tǒng)計(jì)時(shí)長τ內(nèi)的軌跡記錄T(U)的位置狀態(tài)空間集合{r0,r1,…,rn}則用戶運(yùn)動(dòng)軌跡的馬爾科夫模型定位為?=<ρ(u),π(u)>二元組。其中,ρ(u)為用戶位置運(yùn)動(dòng)的轉(zhuǎn)移概率集合,π(u)為用戶位置的聯(lián)合概率集合,也即:

3.2 基于行為模式的虛假軌跡構(gòu)建

基于真實(shí)用戶軌跡構(gòu)建虛假軌跡,難以找到與匿名軌跡完全匹配的其他用戶軌跡,導(dǎo)致匿名失敗。然而,當(dāng)用戶軌跡數(shù)據(jù)發(fā)布時(shí),通常發(fā)布的是關(guān)鍵的位置,而非全部軌跡數(shù)據(jù)。因而,可以通過用戶行為模式構(gòu)建虛假軌跡。圖4顯示了這種情況下的虛假軌跡構(gòu)建方法。圖4(a)采用完全匹配方法為軌跡1構(gòu)建虛假軌跡2。由于軌跡2中C2位置與C1方向不匹配導(dǎo)致匿名失敗。圖4(b)則選擇與軌跡1具有相同行為模式(Wal超市-麥當(dāng)勞)的軌跡2作為虛假軌跡,成功進(jìn)行匿名。因此,選擇具有同一行為模式的軌跡作為虛假軌跡能夠解決完全匹配匿名方法的不足。

圖4 基于行為模式的虛假軌跡

3.3 用戶背景信息

在概率分布攻擊中,攻擊者推測(cè)用戶位置隱私的依據(jù)是位置分布概率。在圖1中,不考慮背景信息情況下,用戶由C到D位置的概率,即P(D|C)=0.5。假設(shè)存在背景信息“80%的用戶選擇去往D位置”,則此時(shí)P(D|C)=0.8,攻擊者將有80%概率推測(cè)出用戶會(huì)從C位置到達(dá)D位置,極大地增加位置泄露的概率。因此,用戶的歷史軌跡這一背景信息中蘊(yùn)含著用戶的位置分布情況。從而,可以用歷史軌跡作為背景信息。

定義5假設(shè)存在h條歷史軌跡,且分布的位置數(shù)目分別為λ1,λ2,…,λh。這些位置分布于一個(gè)劃分為η×ζ個(gè)網(wǎng)格的區(qū)域中,每個(gè)網(wǎng)格單元分布的位置數(shù)目為ac,d。其中,c、d分別表示沿η、ζ方向的列索引、行索引。則每個(gè)網(wǎng)格單元的位置分布概率為:

假設(shè)軌跡T(U)中的rj區(qū)域包含e個(gè)位置,且這些位置分布于網(wǎng)格單元(c,d)中的數(shù)目為ec,d。則rj區(qū)域的位置分布概率,即用戶由區(qū)域ri移動(dòng)到rj的條件轉(zhuǎn)移概率為:

(4)

3.4 軌跡相似性

對(duì)于不同的虛假軌跡,其區(qū)分難度是不同的。為了衡量這種難度,本文采用相似性度量函數(shù)EMD(Earth Mover’s Distance)度量所合成的虛假軌跡和真實(shí)軌跡的相似程度。

對(duì)于任意2個(gè)分布y、z,EMD(y,z)表示分布y轉(zhuǎn)化為分布z的最小代價(jià)。y和z相似程度越高,EMD(y,z)越小,因而可以度量2個(gè)分布間的相似性。

定義6設(shè)Y和Z分別為定義在狀態(tài)空間ΩY={yω|ω=0,1,…,nω}和ΩZ={zθ|θ=0,1,…,nθ}的離散型隨機(jī)變量。PY、PZ分別是Y和Z位于ΩY、ΩZ上的概率分布,即PY(Y=yω)=ρyω,即PZ(Z=zθ)=ρzθ,f為變量Y和Z的聯(lián)合概率分布,ρ為邊緣概率分布。則分布PY和PZ的EMD距離定義為:

其中,fωθ為Y=yω和Z=zθ的聯(lián)合概率分布,d(yω,zθ)為Y=yω和Z=zθ間的距離,且滿足以下約束條件:

fωθ≥0,0≤ω≤nω,0≤θ≤nθ

(9)

定義7假設(shè)用戶U、V在統(tǒng)計(jì)時(shí)長τ內(nèi)的軌跡記錄分別為T(U)={r0,r1,…,rnU}、T(V)={r0,r1,…,rnV},且對(duì)應(yīng)的位置概率分布為π(u)、π(v)則兩者的EMD距離為:

EMD(π(u),π(v))=

(10)

其中,d(rχ,rj)為位置區(qū)間rχ和rj在定義5所定義的η×ζ網(wǎng)格上的歐氏距離。因此,T(U)和T(V)軌跡的相似度sim(T(V),T(U))為:

3.5 軌跡泄露概率

軌跡泄露概率是通過計(jì)算虛假軌跡和真實(shí)軌跡相似程度來衡量。

假設(shè)用戶U的軌跡T(U)及對(duì)應(yīng)虛假軌跡集合為R={T(U(fakeσ))|σ=0,1,…,nσ},T(U(fakeσ))表示T(U)的第σ條虛假軌跡。為了實(shí)現(xiàn)軌跡K-匿名,必須從R中選擇(K-1)條與T(U)具有足夠相似度的虛假軌跡,最優(yōu)的情況是所選軌跡與T(U)的相似度全部為0,否則U的軌跡隱私將泄露。滿足要求的軌跡相似度sim<Δ,Δ為軌跡相似度閾值,是用戶自定義的常數(shù)。

另外,有效虛假軌跡越多,真實(shí)軌跡的K-匿名效果越好,但是匿名成功率越困難,且真實(shí)軌跡上的位置泄露情況也將越發(fā)嚴(yán)重。如果所有虛假軌跡所有位置中包含全部真實(shí)軌跡上所有的位置,那么真實(shí)軌跡將面臨著全面泄露的風(fēng)險(xiǎn)。

基于上述兩方面因素,軌跡隱私泄露概率表示為:

通常,軌跡隱私泄露概率L(U)越大,用戶隱私保護(hù)效果越差。

3.6 軌跡的K-匿名

3.6.1 系統(tǒng)架構(gòu)

考慮到軌跡的K-匿名對(duì)設(shè)備的計(jì)算能力、存儲(chǔ)能力、實(shí)時(shí)性等有較高的要求,本文提出的軌跡匿名方法采用集中式3層系統(tǒng)架構(gòu),如圖5所示。架構(gòu)在可信的第三方匿名服務(wù)器上完成軌跡的匿名,具有較高的計(jì)算能力、存儲(chǔ)能力、實(shí)時(shí)性等;同時(shí)由于用戶的軌跡隱私數(shù)據(jù)全部保存在匿名服務(wù)器而非LBS服務(wù)器,具有較高的安全性。

圖5 本文系統(tǒng)架構(gòu)

實(shí)施軌跡匿名時(shí)的主要工作流程如下:

1)匿名服務(wù)器接收到用戶的位置查詢請(qǐng)求后,通過歷史數(shù)據(jù)存儲(chǔ)模塊,實(shí)時(shí)地建立用戶軌跡的馬爾科夫模型,并存儲(chǔ)用戶數(shù)據(jù)和位置請(qǐng)求。

2)依據(jù)建立的馬爾科夫模型,通過虛假軌跡合成模塊中的算法合成符合要求的虛假軌跡。

3)依據(jù)相似度計(jì)算模塊中的算法分別計(jì)算虛假軌跡和真實(shí)軌跡的相似度,便于對(duì)軌跡進(jìn)行匿名。

4)依據(jù)相似度選取符合要求的虛假軌跡完成K-匿名,并將虛假軌跡和真實(shí)軌跡發(fā)送給LBS服務(wù)器。

5)LBS服務(wù)器接收到匿名服務(wù)器發(fā)送的匿名位置請(qǐng)求后,將查詢結(jié)果發(fā)送給匿名服務(wù)器。

6)匿名服務(wù)器接收到LBS服務(wù)器的查詢結(jié)果后,依據(jù)所存儲(chǔ)的用戶信息和查詢請(qǐng)求,將查詢結(jié)果返回給對(duì)應(yīng)的用戶。

3.6.2 軌跡K-匿名算法

本文給出了軌跡K-匿名算法。算法能夠根據(jù)接收到的用戶位置查詢請(qǐng)求合成虛假軌跡,并返回符合要求的(K-1)條虛假軌跡,完成軌跡的K-匿名。結(jié)合圖5所示的系統(tǒng)架構(gòu),該算法由3個(gè)算法組成。

算法1虛假軌跡生成算法

輸出C(U)

2.for(初始時(shí)刻t0到ti時(shí)刻的每一時(shí)刻t)

3.if t0=ti

5.else

7.end if

8.for (時(shí)刻ti時(shí)集合E中每一用戶Vm)

9.if t0=ti

11.Γ0←初始時(shí)刻所有用戶軌跡

12.else

15.end for

16.end for

17.T(U)←LIST(Di,l),Γ′←SET(Γi,l)

18.T′←?！洹萒(U)

19.C←K-means(T′)//調(diào)用聚類算法分類T′

20.return C(U)//輸出含有用戶U軌跡的類

算法1通過接收從初始時(shí)刻t0到當(dāng)前時(shí)刻ti時(shí)間段內(nèi)待匿名用戶U和其他位置查詢用戶的位置,生成對(duì)應(yīng)的軌跡Di和軌跡集合V(1行～18行),并依據(jù)K-means算法找出與用戶U同類別軌跡作為T(U)的虛假軌跡(19行)。

算法1生成的虛假軌跡具有不同的識(shí)別難度,需要計(jì)算軌跡的相似度。因此,算法2基于算法1輸出結(jié)果C(U)計(jì)算虛假軌跡和真實(shí)軌跡的相似度。假設(shè)C(U)、T(U)、T(V)、h,分別表示算法1的輸出軌跡集合、C(U)中用戶U軌跡、C(U)中的虛假軌跡和歷史軌跡,Sim表示T(U)及與U同類別的虛假軌跡的相似度集合,map、G、H、C′分別表示軌跡所在地經(jīng)緯度范圍、網(wǎng)格元素列表、歷史軌跡列表、位置聯(lián)合概率列表。其詳細(xì)描述如下所示。

算法2軌跡相似度度量算法

輸入C(U)、T(V)、h

輸出Sim

1.map←?,G←?,H←?,C′←?,Sim←?

2.map←{(LAmin,LAmax),(LOmin,LOmax)}//輸入

//軌跡所在地的經(jīng)緯度范圍

3.G←GridZoom(m,n,l,map)//將經(jīng)緯度范圍依照比

//例l縮放,并創(chuàng)建m×n網(wǎng)格

4.for(G中每一個(gè)表格g)//計(jì)算每個(gè)表格中分布的歷史

//位置數(shù)目

5.for(H中每一個(gè)歷史位置h)

6.if h位于表格g

7.Count(g)=Count(g)+1

8.P(g)=Count(g)/len(H)

9.end for

10.end for

11.for(C(U)中每一個(gè)虛假軌跡T(V))//計(jì)算每個(gè)

//T(V)的轉(zhuǎn)移概率和位置聯(lián)合概率

12.ρ(V)←?,π(V)←?//ρ(V)為T(V)轉(zhuǎn)移概率集合,

//π(V)為T(V)位置聯(lián)合概率集合

13.for(T(V)中每一個(gè)位置區(qū)域r)

14.for(r中每一個(gè)位置(x,y))

15.R←?//R是區(qū)域ri移動(dòng)到rj的條件轉(zhuǎn)移概率集合

16.for(G中每一個(gè)表格g)

17.if(x,y)位于表格g

18.Count(rg)=Count(rg)+1

19.P(rg)=Count(rg)/Count(g)

20.R←R∪{P(rg)}

21.end for

22.end for

23.end for

26.if ri=r0

28.else

30.end for

31.C′←C′∪{π(V)}

32.Sr←?,Sπ←?,//Sr為T(U)和T(V)的位置區(qū)域

//矩陣,Sπ兩者的位置聯(lián)合概率矩陣

33.for(C(U)中每個(gè)虛假軌跡T(V))//計(jì)算相似度,計(jì)

//算方法見式(11)

34.Sr←distmatix(T(U),T(V))//建立Sr矩陣

35.Sπ←flowmatix(T(U),T(V))//建立Sπ矩陣

36.max(T(U),T(V))←EMD(T(U),T(V))//計(jì)

//算T(U)和T(V)最大EMD距離

37.min(T(U),T(V))←EMD(T(U),T(V))//計(jì)算

//T(U)和T(V)最小EMD距離

38.sim(T(U),T(V))←sim(min(T(U),T(V)),max(T(U),T(V)))

39.Sim←Sim∪{sim(T(U),T(V))}

40.end for

41.return Sim

算法2在算法1基礎(chǔ)上,首先創(chuàng)建網(wǎng)格,并計(jì)算網(wǎng)格位置分布概率,然后依據(jù)網(wǎng)格位置分布概率計(jì)算輸入的各個(gè)軌跡的條件轉(zhuǎn)移概率和位置聯(lián)合概率(1行～32行),并計(jì)算虛假軌跡和真實(shí)軌跡的相似度(33行～40行)。

軌跡的K-匿名需要選出(K-1)條符合用戶需求的虛假軌跡。算法3基于算法2計(jì)算用戶的軌跡隱私泄露概率。假設(shè)Sim、Δ、K分別表示算法2輸出的軌跡相似度集合、用戶自定義相似度常數(shù)、匿名等級(jí),L(U)表示軌跡隱私泄露概率,R表示符合用戶自定義相似度閾值Δ的虛假軌跡集合,Sim(K)表示與R中軌跡對(duì)應(yīng)的相似度。則其詳細(xì)描述如下所示。

算法3軌跡K-匿名算法

輸入Sim、Δ

輸出L(U)

1.R←?,Sim(K)←?

2.for(Sim中每一個(gè)相似度sim(T(U),T(V)))

3.if sim(T(U),T(V))<Δ

4.R←R∪{T(V)}

5.R←Sim(K)∪{sim(T(U),T(V))}

6.end for

7.if len(R)

8.return(“本次匿名失敗”)

9.else

10.for(Sim(K)所有相似度sim(T(U),T(V)))

11.SUM←SUM+sim(T(U),T(V))

12.end for

13.L(U)←SUM/K

14.return L(U)

為了選出(K-1)條符合用戶需求的虛假軌跡。算法3從算法2的輸出結(jié)果中,選出與用戶自定義相似度閾值Δ相符的軌跡相似度(1行～9行),然后選出至少(K-1)條軌跡進(jìn)行K-匿名(10行～12行),并返回成功匿名后的軌跡隱私泄露概率(13行～14行)。

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

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

為驗(yàn)證本文方法的有效性和高效性,實(shí)驗(yàn)中用戶移動(dòng)軌跡數(shù)據(jù)由Thomas Brinkhoff生成器模擬產(chǎn)生。模擬數(shù)據(jù)來自于奧爾登堡地區(qū)用戶的真實(shí)移動(dòng)軌跡,所記錄的用戶位置具有持續(xù)性和全面性,已被成功用于多項(xiàng)研究工作的驗(yàn)證。因而可用于本文方法的驗(yàn)證工作。本文選取24 km×27 km區(qū)域內(nèi)2 000個(gè)時(shí)間片內(nèi)的10 004條軌跡共計(jì)299 601個(gè)采樣點(diǎn)構(gòu)成實(shí)驗(yàn)數(shù)據(jù)集,并依照1∶1 000的比例模擬到2 400×2 700個(gè)單元網(wǎng)格中。

實(shí)驗(yàn)環(huán)境為Intel i5 7500 3.4 GHz,4 GB內(nèi)存,Windows8 64 bit操作系統(tǒng),算法在Pycharm環(huán)境下基于Python3.5語言實(shí)現(xiàn)的。

4.2 結(jié)果分析

實(shí)驗(yàn)主要采用3.6.2節(jié)的算法,從3個(gè)方面對(duì)本文方法作對(duì)比分析:不同方法對(duì)生成虛假軌跡數(shù)目的影響、背景信息對(duì)軌跡隱私泄露情況的影響、不同方法對(duì)用戶服務(wù)質(zhì)量的影響。

實(shí)驗(yàn)涉及到的參數(shù)包括:1)K為匿名等級(jí),通常為3≤K≤30;2)m為位置區(qū)域包含的位置數(shù)目,1≤m;3)Δ為虛假軌跡和真實(shí)軌跡相似度的閾值,0≤Δ≤1。參與比較的方法包括軌跡替換方法[16]、軌跡旋轉(zhuǎn)方法[17]、隨機(jī)行走方法[18]。為了保證結(jié)果準(zhǔn)確性,所有實(shí)驗(yàn)結(jié)果均為運(yùn)行500次的平均值。

4.2.1 虛假軌跡生成數(shù)目的對(duì)比

為了驗(yàn)證本文方法生成虛假軌跡的效果,本文設(shè)定在匿名等級(jí)K=3情況下,分別從數(shù)據(jù)集中選取500、700、1 000條軌跡考察生成虛假軌跡數(shù)目隨著位置區(qū)域數(shù)目增加呈現(xiàn)出的變化。由于文獻(xiàn)[17-18]方法隨機(jī)生成虛假軌跡,且虛假軌跡數(shù)目僅和匿名等級(jí)有關(guān),因此本文選取文獻(xiàn)[16]的方法作為對(duì)比。實(shí)驗(yàn)結(jié)果如圖6所示。從圖6可以看出,在不同的軌跡數(shù)目情況下,隨著軌跡上位置區(qū)域數(shù)目的增加,2種方法所生成的虛假軌跡數(shù)目存在3個(gè)共同的變化趨勢(shì):1)位置區(qū)域數(shù)目為1時(shí),軌跡替換方法生成的虛假軌跡數(shù)目多于本文方法;2)2種方法生成的虛假軌跡數(shù)目均呈現(xiàn)出先增加再逐漸減少的趨勢(shì);3)軌跡上位置區(qū)域數(shù)目相同時(shí),本文方法生成的虛假軌跡數(shù)目多于軌跡替換方法。之所以如此,原因在于位置區(qū)域數(shù)目為1時(shí)(初始時(shí)刻),多數(shù)軌跡上均存在唯一的位置區(qū)域數(shù)目。由于軌跡替換方法選取位置區(qū)域數(shù)目相同的軌跡作為虛假軌跡,而本文方法則考慮用戶的行為模式,因此所生成的虛假軌跡數(shù)目小于軌跡替換方法。然而,隨著位置區(qū)域數(shù)目的增加,不同軌跡開始具有不同的位置區(qū)域數(shù)目,由于本文提出的方法基于用戶行為模式生成虛假軌跡,因此保證了對(duì)具有多個(gè)位置的軌跡匿名時(shí),生成虛假軌跡的效果優(yōu)于軌跡替換方法。同時(shí),本文方法構(gòu)建的虛假軌跡均來源于真實(shí)的位置,因而能夠防止軌跡因位置的隨機(jī)性而被識(shí)別。

圖6 不同方法下的虛假軌跡數(shù)目曲線

4.2.2 背景信息對(duì)軌跡隱私泄露概率的影響

軌跡隱私保護(hù)方法的效果體現(xiàn)于軌跡隱私泄露概率。實(shí)驗(yàn)分別使用5×104、10×104、15×104類采樣點(diǎn)作為歷史軌跡數(shù)據(jù)驗(yàn)證背景信息對(duì)軌跡隱私泄露概率的影響,實(shí)驗(yàn)結(jié)果如圖7所示。從圖7可以看出,在不同采樣點(diǎn)情況下,軌跡隱私泄露概率是隨著匿名等級(jí)的增大而降低的。且總體上,在同一匿名等級(jí)下,軌跡隱私泄露概率隨著采樣點(diǎn)增加而減小,即隱私保護(hù)效果越好。

圖7 不同背景信息下的軌跡隱私泄露概率曲線

4.2.3 用戶服務(wù)質(zhì)量的對(duì)比

為評(píng)估不同方法對(duì)用戶服務(wù)質(zhì)量的影響,本文使用用戶隱私保護(hù)效果這一度量對(duì)其評(píng)價(jià)。通常,軌跡隱私泄露概率越大,用戶隱私保護(hù)效果越差。因此,本節(jié)基于上述實(shí)驗(yàn),對(duì)比不同方法的軌跡隱私泄露概率。

實(shí)驗(yàn)選取數(shù)據(jù)集中的10 000條軌跡作為歷史軌跡,相似度閾值Δ為0.3。在參與對(duì)比的方法中,隨機(jī)行走和軌跡旋轉(zhuǎn)方法隨機(jī)生成虛假軌跡,軌跡旋轉(zhuǎn)方法和本文方法具有相同的背景信息,軌跡替換方法和本文方法使用4.2.1節(jié)中軌跡數(shù)目為1 000時(shí),生成的虛假軌跡作為運(yùn)行算法時(shí)的虛假軌跡。實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 不同方法下的軌跡隱私泄露概率曲線

在圖8中,對(duì)于同一匿名等級(jí),隨機(jī)行走方法的軌跡隱私泄露概率最高,軌跡旋轉(zhuǎn)方法次之,本文方法最低。原因在于,隨機(jī)行走方法采用隨機(jī)法生成的軌跡中,存在許多不符合實(shí)際運(yùn)動(dòng)規(guī)律的位置點(diǎn),容易通過背景信息識(shí)別,導(dǎo)致隱私保護(hù)效果較差;軌跡旋轉(zhuǎn)方法雖然考慮了背景信息,但本質(zhì)上仍然采用隨機(jī)法生成軌跡,因而難以兼顧每個(gè)位置的背景信息,導(dǎo)致該方法的隱私保護(hù)效果強(qiáng)于軌跡旋轉(zhuǎn)方法,但是弱于本文方法。軌跡替換方法隱私保護(hù)效果僅次于本文方法,但是隨著匿名等級(jí)的增大,容易匿名失敗。原因在于,該方法本身采用了真實(shí)軌跡構(gòu)建虛假軌跡,避免了隨機(jī)性方法的不足,但是采用的虛假軌跡生成方法效率較低,難以生成符合要求的虛假軌跡數(shù)目,如圖8匿名等級(jí)大于15時(shí),其數(shù)值高于虛假軌跡數(shù)目,導(dǎo)致匿名失敗。因而,該方法的隱私保護(hù)效果難以達(dá)到較高水平。本文方法由于采用基于用戶行為模式的虛假軌跡生成方法,在一定程度上減少了軌跡替換方法容易匿名失敗的不足,同時(shí)基于真實(shí)軌跡和背景信息生成虛假軌跡,使得其難以通過背景信息被識(shí)別,因而降低了隱私泄露概率,具有比上述方法更好的隱私保護(hù)效果。

5 結(jié)束語

本文針對(duì)隨機(jī)性和背景信息導(dǎo)致的虛假軌跡容易被識(shí)別的問題,提出了一種基于用戶真實(shí)軌跡的虛假軌跡生成方法。選擇具有相同行為模式的用戶軌跡構(gòu)建虛假軌跡,并設(shè)計(jì)了用戶運(yùn)動(dòng)軌跡的馬爾科夫模型。由于馬爾科夫模型融入了攻擊者掌握的背景信息,因此能夠用于計(jì)算軌跡的相似性,并從構(gòu)建的虛假軌跡中選擇(K-1)條進(jìn)行K-匿名,通過虛假軌跡和真實(shí)軌跡的相似程度衡量軌跡隱私泄露水平。實(shí)驗(yàn)結(jié)果表明,該方法能獲得較好的隱私保護(hù)效果。