基于用戶真實軌跡的虛假軌跡生成方法

林鄧偉,

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

0 概述

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

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

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

2.1 背景信息

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

圖1 概率分布攻擊

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

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

2.2 虛假位置的約束條件

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

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

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

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

2.3 用戶行為模式

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

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

3 虛假軌跡生成方法

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

3.1 用戶運動軌跡模型

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

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

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

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

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

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

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

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

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

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

3.3 用戶背景信息

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

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

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

(4)

3.4 軌跡相似性

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

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

定義6設(shè)Y和Z分別為定義在狀態(tài)空間ΩY={yω|ω=0,1,…,nω}和ΩZ={zθ|θ=0,1,…,nθ}的離散型隨機變量。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)計時長τ內(nèi)的軌跡記錄分別為T(U)={r0,r1,…,rnU}、T(V)={r0,r1,…,rnV},且對應的位置概率分布為π(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 軌跡泄露概率

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

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

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

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

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

3.6 軌跡的K-匿名

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

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

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

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

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

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

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

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

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

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

3.6.2 軌跡K-匿名算法

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

算法1虛假軌跡生成算法

輸出C(U)

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

3.if t0=ti

5.else

7.end if

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

9.if t0=ti

11.Γ0←初始時刻所有用戶軌跡

12.else

15.end for

16.end for

17.T(U)←LIST(Di,l),?！洹鸖ET(Γi,l)

18.T′←Γ′∪T(U)

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

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

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

算法1生成的虛假軌跡具有不同的識別難度,需要計算軌跡的相似度。因此,算法2基于算法1輸出結(jié)果C(U)計算虛假軌跡和真實軌跡的相似度。假設(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)合概率列表。其詳細描述如下所示。

算法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)//計算每個表格中分布的歷史

//位置數(shù)目

5.for(H中每一個歷史位置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)中每一個虛假軌跡T(V))//計算每個

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

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

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

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

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

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

16.for(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)中每個虛假軌跡T(V))//計算相似度,計

//算方法見式(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))//計

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

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

//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)格,并計算網(wǎng)格位置分布概率,然后依據(jù)網(wǎng)格位置分布概率計算輸入的各個軌跡的條件轉(zhuǎn)移概率和位置聯(lián)合概率(1行～32行),并計算虛假軌跡和真實軌跡的相似度(33行～40行)。

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

算法3軌跡K-匿名算法

輸入Sim、Δ

輸出L(U)

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

2.for(Sim中每一個相似度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)條軌跡進行K-匿名(10行～12行),并返回成功匿名后的軌跡隱私泄露概率(13行～14行)。

4 實驗結(jié)果與分析

4.1 實驗參數(shù)設(shè)置

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

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

4.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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