基于相似路徑的位置隱私保護方法①

解 瑾,孫小婷

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

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

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

圖1 連續(xù) LBS 請求軌跡過程

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

(1)利用網(wǎng)格單元對歷史用戶請求密度進行劃分,通過每次采樣時刻時真實用戶周圍的歷史用戶請求密度計算相對請求概率,使匿名組的熵達到最大,從而切斷請求與位置間的聯(lián)系.

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

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

1 相關(guān)工作

1.1 抑制法

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

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

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

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

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

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

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

2 預(yù)備知識

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

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

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

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

2.2 相關(guān)定義

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

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

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

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

所以

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

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

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

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

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

3 LPBSP 位置隱私保護方法

3.1 初始位置生成階段

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

3.2 候選位置篩選階段

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

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

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

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

真實用戶相對請求概率:

虛假用戶相對請求概率:

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

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

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

CLS算法如下:

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

3.3 相似軌跡生成階段

LPBSP方法中相似軌跡是TTP根據(jù)真實用戶的當(dāng)前位置和前一次匿名區(qū)域內(nèi)所有的匿名用戶為基礎(chǔ),通過預(yù)先設(shè)置的參數(shù)對生成的虛假軌跡進行一定約束,使設(shè)置的相似軌跡更加貼近真實用戶軌跡狀態(tài).在采樣時刻,用戶發(fā)起連續(xù)LBS請求,真實用戶u在ti時刻以位置li=(xi,yi)發(fā)起匿名請求,則在[ti-1,ti]時間段內(nèi)用戶u的軌跡距離為s=vi△t,偏移向量為.虛假用戶uj在ti-1時刻的位置為TTP根據(jù)預(yù)先設(shè)置的軌跡方向偏移度d·sim對要生成的相似軌跡進行最大偏移設(shè)置,確定最大偏移角△θi,用戶ui在ti時刻的行駛速度 |vi|;根據(jù)局部速度相似度v·sim確定相似軌跡與真實軌跡的相似速度.在候選位置生成區(qū)域ASRi內(nèi)選擇合適位置作為t時刻的虛擬位置點,TTP獲取此時虛擬點坐標(biāo)連接作為虛假用戶在[ti-1,ti]時間段相對真實用戶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)用戶請求 ;ui ui2.將 壓入集合U中;Ci3.從 中挑選 并計算每一個 加入后 面積;ASRi uijuijASRi4.If ＜ ω // ω 為預(yù)設(shè)值uij5.將uji加入集合 中;6.end if 7.end if d·sim U8.if (satisfy (,)&& (,)//對集合U中的每個虛假用戶 進行 && 期望范圍檢查9.else uiuj iv·simuiuj i uj id·simv·sim10.將不符合的 從集合 中刪除;|U|uj iU12.if 11.計算U內(nèi)用戶數(shù)量 ;|U|≥k13.從中隨機選取 個;14.end if 15.end if ti k16.確定 時刻真實用戶 的用戶軌跡 和虛假用戶 的相似軌跡.uiTruj i FTj

重復(fù)步驟2到16直到ui停止進行LBS請求.

4 安全性分析

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

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

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

5 實驗結(jié)果及分析

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

表1 LPBSP 實驗?zāi)J參數(shù)

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

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

圖4 匿名成功率

圖5 執(zhí)行時間

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

圖6 熵

6 結(jié)論與展望

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