解 瑾,孫小婷

(中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院,青島 266580)

近年來(lái),隨著科技的不斷發(fā)展,基于位置的服務(wù)(Location Based Service,LBS)作為移動(dòng)互聯(lián)網(wǎng)應(yīng)用得到越來(lái)越廣泛的傳播,為人們生活提供了便利.但是由于LBS服務(wù)器是通過(guò)獲取用戶(hù)位置向用戶(hù)發(fā)布相應(yīng)的查詢(xún)信息結(jié)果,這就導(dǎo)致了用戶(hù)在享受位置服務(wù)的同時(shí),也更容易遭受個(gè)人位置隱私信息泄露的風(fēng)險(xiǎn).

現(xiàn)階段位置隱私保護(hù)大致分為兩部分:基于快照LBS的位置隱私保護(hù)和基于連續(xù)LBS的位置隱私保護(hù).快照LBS是指用戶(hù)向位置服務(wù)提供商發(fā)出單次LBS請(qǐng)求,獲取相應(yīng)查詢(xún)結(jié)果.連續(xù)LBS[1]是指用戶(hù)按照一定頻率將自己的位置信息周期性的發(fā)送給LBS服務(wù)器,LBS服務(wù)器通過(guò)用戶(hù)周期性的位置信息和搜索內(nèi)容,實(shí)時(shí)將最新的結(jié)果返回給用戶(hù).然而,在連續(xù)查詢(xún)過(guò)程中某些可以關(guān)聯(lián)推斷出的背景因素結(jié)合特定場(chǎng)景可能會(huì)給用戶(hù)帶來(lái)隱私威脅.如圖1,用戶(hù)A在連續(xù)發(fā)送三次LBS請(qǐng)求時(shí),分別處于三個(gè)不同匿名集{A,B,C,D}{A,E,F,G}{A,H,I,J},攻擊者以根據(jù)用戶(hù)的軌跡關(guān)聯(lián)重構(gòu)用戶(hù)A的過(guò)程軌跡.針對(duì)此類(lèi)問(wèn)題,文獻(xiàn)[2]首次提出了KAA匿名算法,保證匿名用戶(hù)在n次查詢(xún)之后還保持在初始匿名集中.這也就要求在構(gòu)建連續(xù)查詢(xún)匿名集時(shí),需要盡可能的將用戶(hù)附近運(yùn)動(dòng)趨勢(shì)相同的匿名用戶(hù)加入到匿名集中,以避免推斷攻擊.

圖1 連續(xù) LBS 請(qǐng)求軌跡過(guò)程

目前,現(xiàn)有連續(xù)LBS請(qǐng)求中隨機(jī)生成的虛假位置大多忽略攻擊者已知的地理背景信息[3]和真實(shí)用戶(hù)的運(yùn)動(dòng)模式.即使用戶(hù)采用了一定的匿名方法保護(hù)位置隱私,攻擊者還是可以通過(guò)相應(yīng)背景知識(shí)攻擊用戶(hù)位置隱私.針對(duì)現(xiàn)有連續(xù)LBS請(qǐng)求形成虛假軌跡可信性過(guò)低造成的位置隱私泄露問(wèn)題,提出了一種更加真實(shí)的相似路徑形成算法,主要工作如下:

(1)利用網(wǎng)格單元對(duì)歷史用戶(hù)請(qǐng)求密度進(jìn)行劃分,通過(guò)每次采樣時(shí)刻時(shí)真實(shí)用戶(hù)周?chē)臍v史用戶(hù)請(qǐng)求密度計(jì)算相對(duì)請(qǐng)求概率,使匿名組的熵達(dá)到最大,從而切斷請(qǐng)求與位置間的聯(lián)系.

(2)通過(guò)真實(shí)用戶(hù)運(yùn)動(dòng)軌跡的方向、速度對(duì)相似軌跡集合建立約束,關(guān)注用戶(hù)移動(dòng)位置間的時(shí)空相關(guān)性,使其更加貼近真實(shí)用戶(hù)運(yùn)動(dòng)軌跡以達(dá)到位置隱私保護(hù)目的.

本文第1節(jié)講述相關(guān)工作,第2節(jié)講述本文研究的預(yù)備知識(shí),第3節(jié)講述LPBSP位置隱私保護(hù)方法,第4節(jié)分析方法的安全性,第5節(jié)講述本文實(shí)驗(yàn)結(jié)果及分析,最后第6節(jié)總結(jié).

1 相關(guān)工作

1.1 抑制法

基于軌跡數(shù)據(jù)抑制法的隱私保護(hù)技術(shù)是指在真實(shí)用戶(hù)軌跡中抑制某些用戶(hù)的敏感信息,使攻擊者無(wú)法將其與用戶(hù)相關(guān)聯(lián),從而達(dá)到隱私保護(hù)的目的.Gruteser等[4]將地圖上的地理區(qū)域劃分成敏感區(qū)域和非敏感區(qū)域,通過(guò)延遲或抑制敏感區(qū)域中真實(shí)用戶(hù)的位置更新信息來(lái)保護(hù)位置隱私.文獻(xiàn)[5]通過(guò)MASKIT系統(tǒng)通過(guò)過(guò)濾保護(hù)用戶(hù)位置隱私的上下文信息流進(jìn)行隱私檢查,從而限制攻擊者獲得用戶(hù)的敏感位置信息.在匿名過(guò)程中只考慮狀態(tài)的抑制,隱藏會(huì)導(dǎo)致隱私泄露的應(yīng)用程序.然而,單純的抑制法通過(guò)抑制敏感位置或訪(fǎng)問(wèn)頻次高的數(shù)據(jù)進(jìn)行位置隱私保護(hù),實(shí)現(xiàn)簡(jiǎn)單但是信息丟失率較大.

1.2 歷史數(shù)據(jù)泛化法

歷史數(shù)據(jù)泛化法會(huì)引入可信的第三方,將軌跡信息中的采樣點(diǎn)泛化成對(duì)應(yīng)的匿名區(qū)域,以達(dá)到隱私保護(hù)的目的.泛化技術(shù)可分為空間泛化技技術(shù)和時(shí)間泛化技術(shù)[6].空間泛化是指在空間區(qū)域范圍內(nèi)降低真實(shí)用戶(hù)的位置精度,從而增加位置區(qū)域上的不確定性.Wang等[7]為確保用戶(hù)在每次提交LBS請(qǐng)求時(shí)構(gòu)造的匿名區(qū)中包含的匿名用戶(hù)是相同的,提出了一種基于貪心算法的匿名區(qū)構(gòu)造方法,但這樣會(huì)使匿名區(qū)面積隨著查詢(xún)次數(shù)的增加而增加,造成嚴(yán)重的通信和計(jì)算開(kāi)銷(xiāo).Pan X 等[8]提出了一種 ICliqueCloak 的隱身算法,在連續(xù)狀態(tài)中,采用位置k-匿名性和隱身粒度作為隱私度量,劃分區(qū)域候選集合,當(dāng)用戶(hù)發(fā)送請(qǐng)求時(shí),可以快速識(shí)別并生成相應(yīng)隱藏區(qū)域.2013 年 Latha K[9]在 IClique Cloak的基礎(chǔ)上考慮與用戶(hù)位置相關(guān)的處理延遲和匿名化成本,提出KRUPTO算法,增加匿名區(qū)域覆蓋形成最大團(tuán).

時(shí)間泛化是指在增加時(shí)間范圍內(nèi)用戶(hù)精確位置的不確定性.Hwang RH[10]提出r-匿名機(jī)制用來(lái)模糊用戶(hù)真實(shí)軌跡,將k-匿名與s-路段合并,引入時(shí)間混淆技術(shù)打破用戶(hù)進(jìn)行LBS請(qǐng)求提出的時(shí)間序列,運(yùn)用模糊過(guò)程的隨機(jī)性提供軌跡隱私保護(hù).Palanisamy[11]在路網(wǎng)結(jié)構(gòu)中使用mix-zone模型,使k個(gè)用戶(hù)在混合區(qū)等待時(shí)間相等,并打亂用戶(hù)進(jìn)出混合區(qū)的關(guān)聯(lián)順序,以確保隱私保證.歷史數(shù)據(jù)泛化法對(duì)實(shí)時(shí)性要求很高.

1.3 假數(shù)據(jù)法

假數(shù)據(jù)法多指利用k-匿名技術(shù)[12,13]向真實(shí)用戶(hù)運(yùn)動(dòng)軌跡中添加假數(shù)據(jù),通過(guò)生成k–1條假軌跡,將其一起發(fā)送給LBS服務(wù)器,以達(dá)到匿名效果.假數(shù)據(jù)的添加可充分考慮現(xiàn)實(shí)環(huán)境約束,由用戶(hù)定義虛假數(shù)據(jù)產(chǎn)生方式,從而提出更加適用于用戶(hù)的特定需求位置隱私保護(hù)算法.其中,Kido[12]等針對(duì)用戶(hù)在地理環(huán)境的分布情況利用普遍性,擁擠度和分布均勻性三方面設(shè)計(jì)MN和MLN算法,首次提出添加假位置達(dá)到隱私保護(hù)的目的.Gao等[14]提出了用于參與式感知的軌跡隱私保護(hù)框架,從圖論的角度出發(fā),提出考慮時(shí)間因素的理論混合區(qū)模型.Dong等[15]考慮用戶(hù)個(gè)性化隱私需求,通過(guò)短期位置暴露概率、長(zhǎng)期軌跡暴露概率、軌跡偏移距離、軌跡局部相似度和服務(wù)請(qǐng)求概率等五個(gè)參數(shù)讓用戶(hù)進(jìn)行自定義生成虛假軌跡,但此方法沒(méi)有考慮攻擊者背景信息.Ye AY等[16]通過(guò)可信的第三方將偽查詢(xún)插入真實(shí)查詢(xún)中,防止從用戶(hù)標(biāo)識(shí)到查詢(xún)內(nèi)容的反向映射.值得注意的是,在添加假軌跡時(shí)要保證添加的假的干擾數(shù)據(jù)不能對(duì)真實(shí)軌跡產(chǎn)生嚴(yán)重后果.

本文提出的相似軌跡LPBSP方法可以更好地符合真實(shí)用戶(hù)軌跡模式,使相似軌跡在地圖上分布更加合理,在一定程度上避免了推理攻擊和最大移動(dòng)邊界攻擊.

2 預(yù)備知識(shí)

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

本文提出的基于相似路徑的位置隱私保護(hù)方法(LPBSP)系統(tǒng)采用中心式服務(wù)器結(jié)構(gòu),包括移動(dòng)終端、可信第三方匿名服務(wù)器(TTP,Trusted Third Party)以及LBS服務(wù)器三部分組成,系統(tǒng)架構(gòu)如圖2所示.其優(yōu)點(diǎn)在于具有用戶(hù)全局信息,隱私保護(hù)程度高、移動(dòng)終端和TTP間的通信和計(jì)算開(kāi)銷(xiāo)較少.

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

移動(dòng)終端中的GPS模塊獲取移動(dòng)用戶(hù)的自身位置坐標(biāo),將查詢(xún)請(qǐng)求發(fā)送給TTP;經(jīng)過(guò)TTP中的位置匿名模塊做匿名處理生成相似軌跡,并將查詢(xún)請(qǐng)求發(fā)送給LBS服務(wù)器;LBS服務(wù)器根據(jù)查詢(xún)后選結(jié)果將候選集發(fā)送給TTP,通過(guò)TTP的結(jié)果求精模塊過(guò)濾精確結(jié)果并把結(jié)果返回給用戶(hù).

2.2 相關(guān)定義

本文采用基時(shí)空網(wǎng)格劃分方法,將城市地理區(qū)域預(yù)劃分為網(wǎng)格區(qū)域,每個(gè)網(wǎng)格都有自己的唯一標(biāo)識(shí)gidgid.

定義1(保護(hù)的用戶(hù)屬性).P={ID,li,vi,ti,POI},ID為用戶(hù)請(qǐng)求LBS服務(wù)的唯一標(biāo)識(shí)符,li為用戶(hù)所在的位置信息,vi為用戶(hù)歷史速度向量集合,ti為采樣時(shí)間信息,POI為用戶(hù)所請(qǐng)求的興趣點(diǎn).

定義2(k-匿名組).G{u}={k,m},k表示用戶(hù)需要的匿名軌跡數(shù)量,k值隱私保護(hù)效果越好.m表示當(dāng)前匿名組內(nèi)的用戶(hù)數(shù)量.

定義3(整體軌跡方向偏移度).表示采樣時(shí)刻ti真實(shí)軌跡和相似軌跡的偏移情況.假設(shè)用戶(hù)真實(shí)軌跡為,ti表示采樣時(shí)刻,表示用戶(hù)在時(shí)刻所處位置.假設(shè)真實(shí)用戶(hù)在ti時(shí) 刻的位置為li=(xi,yi),則相對(duì)上一位置軌跡偏移向量為.相似的,相似軌跡在ti時(shí)刻的軌跡偏移向量為.則在ti時(shí)刻,真實(shí)軌跡Tr和相似軌跡FTj的余弦相似度可表示為:

所以

在整個(gè)采樣階段相似軌跡FTj相對(duì)真實(shí)軌跡Tr的偏移角度序列為P={△ θ1,△ θ2,···,△ θn}.那么,真實(shí)軌跡Ti和相似軌跡FTj的軌跡方向偏移度d·sim為:

顯而易見(jiàn),d·sim∈[0,1],越趨近于 0,設(shè)置的相似軌跡整體相對(duì)真實(shí)軌跡偏移度越小,整體走向越相似,從而更難被區(qū)分.

定義4(局部速度相似度).受真實(shí)環(huán)境影響,用戶(hù)移動(dòng)速度不是一成不變的.假設(shè)真實(shí)用戶(hù)移動(dòng)速度序列為V={v1,v2,···,vn}在ti時(shí)刻的速度為vi,數(shù)值大小為|vi|,則相應(yīng)的相似軌跡FTj在ti時(shí)刻的速度數(shù)值大小為.那么,在ti時(shí)刻軌跡間的速度相似性v·sim為:

可知v·sim∈(0,1],越趨近于1,相似軌跡在第i個(gè)采樣時(shí)刻的速度相似度越高,在速度上越接近真實(shí)軌跡.

定義5(匿名區(qū)域ASRi).根據(jù)ti時(shí)刻形成的k- 匿名組內(nèi)真實(shí)用戶(hù)ui和k-1個(gè)虛假用戶(hù)坐標(biāo)組成的最小矩形區(qū)域.

3 LPBSP 位置隱私保護(hù)方法

3.1 初始位置生成階段

在連續(xù)請(qǐng)求狀態(tài)下,軌跡方向偏移角度d·sim,生成的虛假軌跡在極端情況下可能會(huì)出現(xiàn)在某個(gè)采樣時(shí)刻集中在一起的情況,從而造成軌跡間距過(guò)小匿名效果不佳,如圖3(a).為保證生成的虛假軌跡在連續(xù)狀態(tài)下更加分散的匿名效果,需要在初始位置生成階段進(jìn)行一定的處理.通過(guò)設(shè)置每個(gè)用戶(hù)之間的距離限定,擴(kuò)大初始匿名區(qū)用戶(hù)之間的間距,使初始匿名位置點(diǎn)更加分散,如圖3(b).

3.2 候選位置篩選階段

若在某個(gè)采樣點(diǎn)時(shí)刻匿名區(qū)域內(nèi)用戶(hù)數(shù)量發(fā)生了很大的變化,則很有可能是真假用戶(hù)的位置數(shù)據(jù)進(jìn)行了某種變化,從而增加真實(shí)用戶(hù)位置泄露風(fēng)險(xiǎn).因此,為避免虛假位置點(diǎn)急劇變化情況,在生成候選位置點(diǎn)時(shí)需要對(duì)其進(jìn)行篩選處理.本文采用歷史位置點(diǎn)和生成虛假位置點(diǎn)相結(jié)合的方式,以用戶(hù)密度為基礎(chǔ),使真實(shí)軌跡和相似軌跡在采樣時(shí)刻更加均勻,提高匿名效果.具體過(guò)程如下:

圖3 初始位置生成狀態(tài)

1)TTP記錄每個(gè)網(wǎng)格內(nèi)用戶(hù)請(qǐng)求密度,并預(yù)先設(shè)置密度閾值 σ.對(duì)用戶(hù)請(qǐng)求密度低于 σ的區(qū)域剔除,因?yàn)檫@些區(qū)域往往代表真實(shí)環(huán)境中不可到達(dá)區(qū)域(如湖泊,森林等).

2)在進(jìn)行候選位置篩選階段前,需要根據(jù)預(yù)設(shè)參數(shù)計(jì)算相似軌跡生成區(qū)域.假設(shè)在ti時(shí)刻真實(shí)用戶(hù)在li=(xi,yi)的速度為vi,根據(jù)TTP預(yù)先設(shè)置的d·sim和v·sim確定生成區(qū)域范圍.以真實(shí)用戶(hù)所在網(wǎng)格的請(qǐng)求密度為標(biāo)準(zhǔn),請(qǐng)求密度大的區(qū)域代表歷史用戶(hù)在該區(qū)域中進(jìn)行頻繁的LBS請(qǐng)求,則在該區(qū)域中發(fā)生請(qǐng)求的概率相對(duì)較大.在ti時(shí)刻根據(jù)用戶(hù)所在位置li=(xi,yi)判斷此網(wǎng)格的歷史請(qǐng)求密度為真實(shí)用戶(hù)所在網(wǎng)格內(nèi)用戶(hù)請(qǐng)求數(shù)量,Sc:網(wǎng)格面積),當(dāng)TTP提交的k-匿名組內(nèi)成員的密度相等時(shí),不易攻擊者發(fā)現(xiàn).因此用戶(hù)需要獲得生成區(qū)域范圍內(nèi)所有網(wǎng)格用戶(hù)請(qǐng)求密度,然后進(jìn)行排序.在排序列表中,選擇與真實(shí)用戶(hù)所在區(qū)域請(qǐng)求密度相似的網(wǎng)格,并在此基礎(chǔ)上隨機(jī)確定數(shù)量為k個(gè)歷史用戶(hù)作為候選對(duì)象集Ci,每個(gè)歷史用戶(hù)代表一個(gè)實(shí)際位置點(diǎn).將這些用戶(hù)的請(qǐng)求密度進(jìn)行歸一化,可得到在ti時(shí)刻候選對(duì)象集Ci相對(duì)請(qǐng)求概率:

真實(shí)用戶(hù)相對(duì)請(qǐng)求概率:

虛假用戶(hù)相對(duì)請(qǐng)求概率:

為使每次采樣時(shí)刻匿名組用戶(hù)所在區(qū)域中請(qǐng)求密度更加均勻,我們需要一個(gè)衡量標(biāo)準(zhǔn),在理想情況下當(dāng)真假用戶(hù)所在區(qū)域密度完全相等時(shí),熵的值最大有:

當(dāng)H的值越趨近于Hc時(shí),歷史用戶(hù)請(qǐng)求分布越均勻,攻擊者越無(wú)法將真實(shí)用戶(hù)從匿名用戶(hù)中分離出來(lái),此時(shí)得到的Hi的匿名組用戶(hù)最佳:

確定此時(shí)候選對(duì)象集Ci的匿名區(qū)域范圍ASRi.

CLS算法如下:

算法 1.CLS 算法輸入:每個(gè)單元格內(nèi)歷史用戶(hù)請(qǐng)求密度,時(shí)刻用戶(hù)位置坐標(biāo)ti tili=(xi,yi)輸出:時(shí)刻 ,候選對(duì)象集 ,匿名區(qū)域HmaxCiASRi初始化 ;1.將區(qū)域中各個(gè)單元格中的用戶(hù)請(qǐng)求密度進(jìn)行排序;2.剔除不可到達(dá)區(qū)域;m=0,H=0 3.從排序列表中選取與真實(shí)用戶(hù)請(qǐng)求區(qū)域密度相似的 個(gè)候選點(diǎn);j≤k-1 3k4.while //隨機(jī)從中選取 個(gè)候選點(diǎn)ti2k5.當(dāng) 時(shí)刻虛假用戶(hù)位置數(shù)量小于k–1時(shí);ti6.計(jì)算 時(shí)刻的 ,和 ;Hi qiqj iHi←-■■■■qil og2qi+k-1∑og2qji qjil■■■■j=1 7.進(jìn)行 更新;8.end while Hmax 9.選取 ;ti10.確定 時(shí)刻熵最大的最佳候選對(duì)象集 ;Ci Ci11.確定候選對(duì)象集 的匿名區(qū)域 ;ASRi ASRi12.輸出 .

3.3 相似軌跡生成階段

LPBSP方法中相似軌跡是TTP根據(jù)真實(shí)用戶(hù)的當(dāng)前位置和前一次匿名區(qū)域內(nèi)所有的匿名用戶(hù)為基礎(chǔ),通過(guò)預(yù)先設(shè)置的參數(shù)對(duì)生成的虛假軌跡進(jìn)行一定約束,使設(shè)置的相似軌跡更加貼近真實(shí)用戶(hù)軌跡狀態(tài).在采樣時(shí)刻,用戶(hù)發(fā)起連續(xù)LBS請(qǐng)求,真實(shí)用戶(hù)u在ti時(shí)刻以位置li=(xi,yi)發(fā)起匿名請(qǐng)求,則在[ti-1,ti]時(shí)間段內(nèi)用戶(hù)u的軌跡距離為s=vi△t,偏移向量為.虛假用戶(hù)uj在ti-1時(shí)刻的位置為T(mén)TP根據(jù)預(yù)先設(shè)置的軌跡方向偏移度d·sim對(duì)要生成的相似軌跡進(jìn)行最大偏移設(shè)置,確定最大偏移角△θi,用戶(hù)ui在ti時(shí)刻的行駛速度 |vi|;根據(jù)局部速度相似度v·sim確定相似軌跡與真實(shí)軌跡的相似速度.在候選位置生成區(qū)域ASRi內(nèi)選擇合適位置作為t時(shí)刻的虛擬位置點(diǎn),TTP獲取此時(shí)虛擬點(diǎn)坐標(biāo)連接作為虛假用戶(hù)在[ti-1,ti]時(shí)間段相對(duì)真實(shí)用戶(hù)ui的相似軌跡.

DVS算法如下:

算法 2.DVS 算法輸入: ,,T={FT1,FT2,··,FTj,··,FTk-1,Tr}P={ID,li,vi,ti,POI}d·simv·sim輸出:相似路徑集合 設(shè)置中間集合U=null ui1.if is fresh //出現(xiàn)用戶(hù)請(qǐng)求 ;ui ui2.將 壓入集合U中;Ci3.從 中挑選 并計(jì)算每一個(gè) 加入后 面積;ASRi uijuijASRi4.If ＜ ω // ω 為預(yù)設(shè)值uij5.將uji加入集合 中;6.end if 7.end if d·sim U8.if (satisfy (,)&& (,)//對(duì)集合U中的每個(gè)虛假用戶(hù) 進(jìn)行 && 期望范圍檢查9.else uiuj iv·simuiuj i uj id·simv·sim10.將不符合的 從集合 中刪除;|U|uj iU12.if 11.計(jì)算U內(nèi)用戶(hù)數(shù)量 ;|U|≥k13.從中隨機(jī)選取 個(gè);14.end if 15.end if ti k16.確定 時(shí)刻真實(shí)用戶(hù) 的用戶(hù)軌跡 和虛假用戶(hù) 的相似軌跡.uiTruj i FTj

重復(fù)步驟2到16直到ui停止進(jìn)行LBS請(qǐng)求.

4 安全性分析

針對(duì)軌跡隱私保護(hù)的攻擊者可以根據(jù)發(fā)起連續(xù)LBS請(qǐng)求的時(shí)間序列歸納用戶(hù)大致行動(dòng)方向,根據(jù)相應(yīng)已知條件發(fā)起推理攻擊、最大移動(dòng)邊界攻擊等攻擊模式.這是由于真實(shí)連續(xù)LBS的請(qǐng)求位置序列有一定的上下文聯(lián)系,攻擊者可以分析真假軌跡的差異性推斷出真實(shí)用戶(hù).

證明:在ti時(shí)刻,真實(shí)用戶(hù)ui被識(shí)別的概率pi{ui∈,此時(shí),根據(jù)公式 (3)可得真實(shí)用戶(hù)相對(duì)請(qǐng)求概率qi,可知qi與ui所在區(qū)域請(qǐng)求密度di有關(guān),有;相似的,ti時(shí)刻虛假用戶(hù)被識(shí)別的概率.若,可保證,此時(shí)Hi=Hc.

針對(duì)最大移動(dòng)邊界攻擊,本文以真實(shí)用戶(hù)運(yùn)動(dòng)方向和速度為基礎(chǔ),由用戶(hù)自定義參數(shù)范圍,充分考慮真實(shí)情況虛假位置的不可到達(dá)性,通過(guò)速度和方向偏移相似程度限制抵抗最大移動(dòng)邊界攻擊.

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

本文在 Windows sever 2008 服務(wù)器下采用 Java 語(yǔ)言開(kāi)展 LPBSP 實(shí)驗(yàn),實(shí)驗(yàn)采取 Thomas Brinkhoff路網(wǎng)生成器生成Oldenburg城市路網(wǎng)中的用戶(hù)及興趣點(diǎn)的實(shí)驗(yàn)數(shù)據(jù),并與文獻(xiàn)[12]做對(duì)比實(shí)驗(yàn),驗(yàn)證本文LPBSP方法在匿名成功率、執(zhí)行時(shí)間、熵三個(gè)維度上具有一定的貢獻(xiàn).LPBSP試驗(yàn)參數(shù)如表1所示.

表1 LPBSP 實(shí)驗(yàn)?zāi)J(rèn)參數(shù)

在匿名成功率方面,如圖4所示文獻(xiàn)[12]基于虛假路徑的設(shè)置,只要有匿名需求便可構(gòu)建虛假用戶(hù)進(jìn)行協(xié)作匿名,沒(méi)有考慮到虛假用戶(hù)的真實(shí)性,假如真實(shí)用戶(hù)在海邊,構(gòu)建的虛假用戶(hù)很可能會(huì)在海里,從而導(dǎo)致匿名效果的損失,而本文LPBSP方法是基于用戶(hù)查詢(xún)的歷史數(shù)據(jù)來(lái)構(gòu)建協(xié)作匿名,在真實(shí)用戶(hù)發(fā)起查詢(xún)時(shí),周?chē)臍v史數(shù)據(jù)可能會(huì)存在不足而導(dǎo)致匿名組構(gòu)建失敗,因而在匿名成功率方面略低于文獻(xiàn)[12],但是本文方法仍然具有較高的匿名成功率.

在方法執(zhí)行時(shí)間方面,本文LPBSP方法由于需要獲得生成區(qū)域范圍內(nèi)所有網(wǎng)格用戶(hù)請(qǐng)求密度,然后進(jìn)行排序,時(shí)間復(fù)雜度為nlogn.如圖5所示,文獻(xiàn)[12]由于不考慮其他因素,僅以構(gòu)建虛假路徑為核心,因而執(zhí)行效率高,執(zhí)行時(shí)間較短.本文方法由于在構(gòu)建協(xié)作用戶(hù)的虛假路徑時(shí)綜合考慮了協(xié)作用戶(hù)真實(shí)性,協(xié)作路徑相似性等諸多因素,因而在執(zhí)行時(shí)間方面略長(zhǎng)與文獻(xiàn)[12],但是總體來(lái)看執(zhí)行時(shí)間仍舊保持在較快的速度,毫秒的差距不影響用戶(hù)體驗(yàn).

圖4 匿名成功率

圖5 執(zhí)行時(shí)間

在探究位置隱私保護(hù)度方面,如圖6所示,本文采用熵的形式與文獻(xiàn)[12]進(jìn)行對(duì)比實(shí)驗(yàn),通過(guò)實(shí)驗(yàn)結(jié)果圖所示,可以發(fā)現(xiàn),熵隨著k值的增大而逐漸增大,本文LPBSP方法相較于文獻(xiàn)[12]中具有一定優(yōu)勢(shì),原因在于本文考慮了真實(shí)用戶(hù)的歷史位置數(shù)據(jù)進(jìn)行匿名,并對(duì)用戶(hù)的軌跡及移動(dòng)速度進(jìn)行了相似度的設(shè)置,相較于文獻(xiàn)[12]單純的構(gòu)建虛假路徑更具有真實(shí)性,使得匿名虛假軌跡與真實(shí)軌跡具有較高的相似性,因而具有較好的隱私保護(hù)度.當(dāng)然相對(duì)于理想狀態(tài)熵的最優(yōu)值log2k還是有一定差距,仍需要進(jìn)行繼續(xù)的優(yōu)化.

圖6 熵

6 結(jié)論與展望

本文針對(duì)連續(xù)查詢(xún)位置隱私保護(hù)問(wèn)題中可能存在的因協(xié)作用戶(hù)交疊而暴露真實(shí)查詢(xún)用戶(hù)的問(wèn)題,提出了基于相似路徑的位置隱私保護(hù)方法(LPBSP),首先采用用戶(hù)歷史數(shù)據(jù)構(gòu)建初始協(xié)作匿名組,然后利用用戶(hù)歷史位置數(shù)據(jù)、速度及軌跡相似度等對(duì)協(xié)作路徑加以約束,使得協(xié)作路徑更具有真實(shí)性,加以迷惑攻擊者,最后通過(guò)實(shí)驗(yàn)驗(yàn)證本文方法雖然在匿名成功率、執(zhí)行時(shí)間上略遜色于文獻(xiàn)[12],但是在位置隱私保護(hù)度方面有了較好的應(yīng)用,在研究位置隱私方面有一定價(jià)值.