王榕, 謝瑋, 廖璇, 豐詩朵, 白琨鵬
(1.中國信息通信研究院 安全研究所 行業(yè)網(wǎng)絡(luò)安全事業(yè)部,北京 100191; 2.中國科學(xué)院 軟件研究所 可信計(jì)算與信息保障實(shí)驗(yàn)室,北京 100190)
現(xiàn)階段配備GPS定位功能的智能設(shè)備已得到普及,這給人們的生活帶來了巨大的便利[1],但同時(shí)也帶來了巨大的用戶隱私泄露風(fēng)險(xiǎn)[2-3]。如通過分析用戶的移動(dòng)軌跡可以推斷出用戶的家庭地址[4],也可以推斷出用戶過去、現(xiàn)在、將來的位置[5-6]以及他們的社交關(guān)系[7]。去匿名攻擊(de-anonymization attack)[7-14]可以根據(jù)用戶移動(dòng)軌跡包含的移動(dòng)模式信息有效地重識(shí)別匿名用戶。但是根據(jù)當(dāng)前研究來看,大多算法均通過著重考慮移動(dòng)軌跡中的空間屬性來進(jìn)行用戶去匿名攻擊,忽略時(shí)間屬性的作用。
本文定量分析了用戶移動(dòng)軌跡包含的空間屬性和時(shí)間屬性,定義了一種時(shí)空感知的用戶隱馬爾可夫模型(spatio-temporal user hidden Markov model,ST-UHMM)來描述用戶的移動(dòng)行為,進(jìn)一步提出了基于ST-UHMM的去匿名攻擊模型以及2種時(shí)空感知的相似度定義。為了評(píng)估本文模型的有效性,我們使用微軟亞洲研究院(MicroSoft Research Asia,MSRA)采集的GeoLife[26]數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,相比已有方法,本文模型的重識(shí)別準(zhǔn)確度有顯著的提高。
用戶移動(dòng)軌跡中的空間屬性在去匿名攻擊中往往發(fā)揮著不可忽視的作用。De Mulder等[15]使用只能描述地理上相鄰2個(gè)位置(GSM基站)ID描述GSM網(wǎng)絡(luò)中用戶的移動(dòng)行為。Xiao等[16]通過定義SLH(semantic location histories)并計(jì)算SLH序列之間的相似度來重識(shí)別匿名用戶。Zang等[17]把GSM網(wǎng)絡(luò)中每個(gè)用戶訪問頻率最高的n個(gè)位置作為一個(gè)準(zhǔn)標(biāo)識(shí)符(quasi-identifier,QI)來重識(shí)別匿名用戶。Gambs等[1]定義了移動(dòng)馬爾可夫鏈(mobility Markov chain,MMC)來描述用戶的移動(dòng)行為,通過計(jì)算MMC之間的相似度來重識(shí)別匿名用戶。Samet等[18]采用隱馬爾可夫模型(hidden Markov model,HMM)描述用戶的行為模式,并根據(jù)地理位置信息生成基于區(qū)域范圍的隱藏態(tài),但對(duì)于大量跨區(qū)域范圍的簽到位置并不能準(zhǔn)確識(shí)別出目標(biāo)用戶。Farid等[19]使用用戶的位置分布柱狀圖來描述用的行為規(guī)則。Takao[20]則考慮小規(guī)模數(shù)據(jù)集的去匿名化問題,計(jì)算匿名數(shù)據(jù)和已知用戶數(shù)據(jù)的地理位置分布的JS(Jensen-Shannon,JS)散值,識(shí)別匿名數(shù)據(jù)。
上述去匿名方法有共同的不足:依賴空間屬性來進(jìn)行去匿名攻擊而忽略了移動(dòng)軌跡中時(shí)間屬性的作用。Freudiger等[21]將用戶的“home”/“work”對(duì)作為準(zhǔn)標(biāo)識(shí)符重識(shí)別匿名用戶,但是如果2個(gè)匿名用戶的“home”/“work”對(duì)相同,這種方法的效果就大打折扣。De Montjoye等[22]提出隨機(jī)選取2個(gè)或4個(gè)時(shí)空位置可以有效地重識(shí)別50%~95%的匿名用戶。但是,他們的方法過于依賴隨機(jī)位置的選擇。Chen[23]提出的DBHMM方法以及Wang[24]提出的UHMM考慮了用戶的時(shí)空信息,但是該方案僅適用于單條或小規(guī)模軌跡識(shí)別。Yuan等[25]提出的PRED方法可以評(píng)估出用戶周期性訪問的區(qū)域,以及訪問區(qū)域的周期性時(shí)間,并利用該方法預(yù)測(cè)用戶未來訪問的地點(diǎn)。
總的來說,為了有效地實(shí)施去匿名攻擊,需要充分地考慮用戶移動(dòng)軌跡包含的空間屬性和時(shí)間屬性。本文在上述從直觀上分析了用戶移動(dòng)軌跡包含的空間屬性和時(shí)間屬性及其在去匿名攻擊中發(fā)揮的作用。使用MSRA采集的GeoLife數(shù)據(jù)集對(duì)用戶移動(dòng)軌跡包含的空間屬性和時(shí)間屬性進(jìn)行定量分析。
為了衡量不同用戶訪問不同位置的喜好程度,本文使用位置熵(location entropy,LE)來度量移動(dòng)軌跡中的空間屬性。給定一個(gè)用戶,其位置熵定義為:
(1)
(2)
位置熵度量用戶移動(dòng)行為的空間傾向性。位置熵越大,用戶移動(dòng)行為越缺少空間傾向性。相反,位置熵越小,意味著用戶會(huì)越有傾向性地頻繁訪問少數(shù)位置,這些少數(shù)位置是對(duì)用戶至關(guān)重要的。
因此,計(jì)算等概位置熵與位置熵的差值,并將之歸一化,以此定義用戶移動(dòng)行為的空間傾向性為:
(3)
從空間傾向性的定義可見,對(duì)于一個(gè)用戶來說,等概位置熵與位置熵差值越大,他的移動(dòng)行為越有空間傾向性。本文對(duì)GeoLife當(dāng)中的數(shù)據(jù)進(jìn)行分析。由圖1可知,GeoLife數(shù)據(jù)集中的絕大多數(shù)用戶的等概位置熵與位置熵并不相等(空間傾向性非零)。特別地,有近80%的用戶的空間傾向性大于0.10,這表明他們的移動(dòng)行為普遍具有較明顯的空間傾向性,每個(gè)用戶的軌跡中存在對(duì)其具有重要意義的位置,空間傾向性極為明顯。
圖1 用戶移動(dòng)行為的空間傾向性Fig.1 Spatial tendency of users′ mobility behaviors
除了空間屬性,用戶移動(dòng)軌跡也常常包含時(shí)間屬性。為了充分度量這種時(shí)間屬性,本文首先定義一種時(shí)間感知的位置熵(time-aware location entropy,TALE)。給定一個(gè)用戶,其TALE定義為:
(4)
式中:T={0,1,…,23}是時(shí)間段的集合,如時(shí)間段13表示下午13:00~14:00這個(gè)時(shí)間段;p(t)是用戶在時(shí)間段t訪問一個(gè)位置的概率;p(l|t)是用戶在時(shí)間段t訪問位置l的概率。
TALE度量用戶移動(dòng)行為的時(shí)間傾向性。對(duì)一個(gè)用戶來說,TALE越大,該用戶在不同時(shí)間段訪問一個(gè)位置的概率分布越均勻,用戶移動(dòng)行為的時(shí)間傾向性越低。當(dāng)用戶在所有時(shí)間段訪問所有位置的概率都相同時(shí),即?t∈T,?l∈L,p(l|t)=p(l),則:
(5)
此時(shí)TALE達(dá)到最大值,與位置熵相等。反之,TALE越小,意味著用戶會(huì)越有傾向性地在少數(shù)時(shí)間段訪問某些位置。
因此,本文將用戶移動(dòng)行為的時(shí)間傾向性定義為:
(6)
式中:I(L;T)是L和T的互信息[21-22],表示時(shí)間段對(duì)位置訪問頻率的影響。根據(jù)互信息的非負(fù)性[21-22],I(L;T)≥0,即TALE的最大值是位置熵。
從時(shí)間傾向性的定義可見,對(duì)于一個(gè)用戶來說,位置熵與TALE差值越大,互信息越大,他的移動(dòng)行為越有時(shí)間傾向性,反之則越?jīng)]有時(shí)間傾向性。本文對(duì)GeoLife數(shù)據(jù)進(jìn)行試驗(yàn),結(jié)果如圖2,GeoLife數(shù)據(jù)集中的絕大多數(shù)用戶的位置熵與TALE并不相等(時(shí)間傾向性非零)。特別地,有近95%的用戶的時(shí)間傾向性大于0.10,這表明用戶訪問不同位置的時(shí)間并不是隨機(jī),他們的移動(dòng)行為普遍具有較明顯的時(shí)間傾向性。
圖2 用戶移動(dòng)行為的時(shí)間傾向性Fig.2 Temporal tendency of users′ mobility behaviors
當(dāng)前針對(duì)用戶的移動(dòng)軌跡主要有2種建模方式,一類是根據(jù)位置的頻繁程度進(jìn)行挖掘建模,另一種就是基于馬爾可夫模型的。Gonzalez[3]和Song[4]分析了用戶的移動(dòng)數(shù)據(jù),并且證明了人類的位置轉(zhuǎn)移具有很高的時(shí)空規(guī)律性。在位置推理過程中,通常使用一階馬爾可夫模型的轉(zhuǎn)移有序性推測(cè)用戶位置。但是一階馬爾可夫模型有一個(gè)嚴(yán)重的問題就是關(guān)注了位置間的轉(zhuǎn)移時(shí)序性。因此本文充分在用戶行為建模時(shí)充分考慮用戶移動(dòng)行為的時(shí)間屬性。利用隱馬爾可夫模型進(jìn)行建模,將用戶的軌跡行為的時(shí)間作為隱藏態(tài),將用戶在不同時(shí)間下出現(xiàn)的位置信息作為輸出態(tài)。
基于上述分析,本文提出一種時(shí)空感知的用戶隱馬爾可夫模型(spatio-temporal user hidden Markov model,ST-UHMM)作為分析用戶移動(dòng)模式和進(jìn)行去匿名攻擊的基礎(chǔ)。
對(duì)于一個(gè)用戶,將其ST-UHMM定義為一個(gè)五元組μ=(S,Π,A,O,E):
1)S={s0,s1,…,s24}是狀態(tài)空間,每個(gè)元素作為一個(gè)隱藏狀態(tài),s24作為終止?fàn)顟B(tài)。除s24外,每個(gè)隱藏狀態(tài)對(duì)應(yīng)一個(gè)時(shí)間段,如s0對(duì)應(yīng)0:00~1:00這個(gè)時(shí)間段,s22對(duì)應(yīng)22:00~23:00這個(gè)時(shí)間段。如果狀態(tài)轉(zhuǎn)移到s24,用戶在這一天不再訪問任何位置。
2)Π是狀態(tài)的初始概率集合。一個(gè)狀態(tài)st(t∈T)的初始概率是每天這個(gè)用戶首先在時(shí)間段t訪問一個(gè)位置的概率,定義為:
(7)
式中αt表示有多少天這個(gè)用戶首先在時(shí)間段t訪問一個(gè)位置。
3)A是狀態(tài)轉(zhuǎn)移概率集合。狀態(tài)st1(t1∈T)到狀態(tài)st2(t2∈T∪{24})的轉(zhuǎn)移概率定義為:
(8)
式中:βt1表示有多少天用戶在時(shí)間段t1訪問一個(gè)位置;βt1,t2表示有多少天這個(gè)用戶在時(shí)間段t1訪問一個(gè)位置,然后在時(shí)間段t2訪問下一個(gè)位置。如βt1,24表示有多少天用戶在時(shí)間段t1訪問一個(gè)位置,然后在當(dāng)天不再訪問任何位置。一個(gè)狀態(tài)到它自身的轉(zhuǎn)移是存在的,這是因?yàn)橐粋€(gè)用戶可能在同一時(shí)間段內(nèi)訪問多個(gè)不同的位置。
4)O={o1,o2,…,on}是觀察集合,集合中的每個(gè)元素是用戶訪問的一個(gè)位置,n是用戶訪問的位置數(shù)。
5)E是狀態(tài)輸出概率集合。當(dāng)前狀態(tài)為st(t∈T)時(shí)輸出觀察為ok(1≤k≤n)的概率是:
(9)
式中:f(st,ok)表示有多少次用戶在時(shí)間段t訪問觀察(位置)ok。
本文提出一種時(shí)空感知的去匿名攻擊模型(spatio-temporal de-anonymization attack model,ST-DAAM)。
如圖3所示,ST-DAAM使用的數(shù)據(jù)集包括訓(xùn)練集和測(cè)試集。訓(xùn)練集由用于構(gòu)建一個(gè)去匿名知識(shí)庫;測(cè)試集是匿名軌跡集合,是ST-DAAM的重識(shí)別對(duì)象。
圖3 時(shí)空感知的去匿名攻擊模型Fig.3 Spatio-temporal de-anonymization attack model
ST-DAAM包括2個(gè)過程,即訓(xùn)練過程和測(cè)試過程。在訓(xùn)練過程中,根據(jù)訓(xùn)練集中的用戶移動(dòng)記錄,使用ST-UHMM描述每個(gè)用戶的移動(dòng)行為,構(gòu)造去匿名知識(shí)庫。在測(cè)試過程中,根據(jù)測(cè)試集的匿名軌跡,使用ST-UHMM描述每個(gè)匿名用戶的移動(dòng)行為。計(jì)算測(cè)試集ST-UHMM與訓(xùn)練集ST-UHMM的相似度,將其相似度最大的訓(xùn)練集ST-UHMM對(duì)應(yīng)的用戶就是重識(shí)別結(jié)果。
本文定義2種時(shí)空感知的ST-UHMM相似度:1)時(shí)空感知的余弦相似度(spatio-temporal cosine similarity,STCS);2)時(shí)空感知的增強(qiáng)相似度(spatio-temporal enhanced similarity,STES)。
首先將同一時(shí)間段不同用戶的位置集合作為不同的向量,衡量同一時(shí)間段不同用戶訪問位置的余弦相似度,然后將不同時(shí)間段的相似度累加。ST-UHMM之間的STCS為:
SimSTC(μ1,μ2)=
(10)
式中:μi=(Si,Πi,Ai,Oi,Ei)(i=1,2)是描述用戶ui的移動(dòng)行為的ST-UHMM;φi(o,t)=1表示用戶ui在時(shí)間段t訪問過觀察位置o;φi(o,t)=0表示用戶ui在時(shí)間段t沒有訪問過觀察位置o。
STCS的定義考慮了ST-UHMM在每個(gè)時(shí)間段的共同位置。直觀上,不同用戶在同一時(shí)間段內(nèi)訪問共同位置的概率(傾向性)越接近。因此,本文將STES定義為:
SimSTE(μ1,μ2)=
(11)
式中:wt為賦給不同時(shí)間段的權(quán)重;Oi,t是用戶ui在時(shí)間段t的觀察集合。STES的定義在考慮用戶在每個(gè)時(shí)間段的共同訪問位置的同時(shí),也考慮了他們?cè)L問共同位置的概率。
為了評(píng)估本文模型的有效性,本節(jié)使用MSRA采集的GeoLife數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),分析已有的去匿名攻擊方法,并將本文模型與之對(duì)比。
GeoLife數(shù)據(jù)集包括北京市178個(gè)用戶的17 621條GPS軌跡數(shù)據(jù),總長度120×104km,總時(shí)長48 000 h。這些數(shù)據(jù)以1~5 s的高頻采集,采集時(shí)間是從2007年4月—2011年10月,記錄了用戶日常的上班、回家、購物、運(yùn)動(dòng)一系列活動(dòng)。
本文首先對(duì)GeoLife數(shù)據(jù)集進(jìn)行預(yù)處理,包括2個(gè)步驟,即地圖劃分和數(shù)據(jù)組織。在地圖劃分過程中,把二維的北京市地圖均勻地劃分成10 000個(gè)格子,然后使用格子ID來表示對(duì)應(yīng)的位置,借以描述所有用戶的移動(dòng)軌跡。數(shù)據(jù)組織過程按天組織每個(gè)用戶的移動(dòng)軌跡,并按小時(shí)組織每天的移動(dòng)軌跡,如表1所示。
表1 用戶軌跡Table 1 User trace
在去匿名攻擊過程中,一個(gè)符合實(shí)際且不失一般性的假設(shè)是,敵手可以通過一段時(shí)間的觀察來獲得一部分用戶移動(dòng)記錄,并可以將其作為訓(xùn)練集。構(gòu)建訓(xùn)練集后,根據(jù)訓(xùn)練集對(duì)匿名軌跡的匿名用戶進(jìn)行重識(shí)別。因此,本文將所有用戶的移動(dòng)數(shù)據(jù)劃分為2個(gè)不相交的軌跡集合:一半數(shù)據(jù)用來構(gòu)建訓(xùn)練集Train1;另一半數(shù)據(jù)用來構(gòu)建測(cè)試集Test1。
Rand方法[22]從訓(xùn)練集中提取測(cè)試集,為了和這種方法做全面的比較,本文也構(gòu)建了訓(xùn)練集Train2和測(cè)試集Test2。其中,Train2由所有用戶的所有移動(dòng)數(shù)據(jù)構(gòu)成;Test2由Train2中隨機(jī)抽取的半數(shù)移動(dòng)數(shù)據(jù)構(gòu)成。
本文構(gòu)建了Train1-Test1和Train2-Test2的2個(gè)對(duì)數(shù)據(jù)集,并用這2個(gè)對(duì)數(shù)據(jù)集對(duì)已有去匿名方法和本文模型做分析。本文的實(shí)驗(yàn)共分析5種去匿名方法,如表2所示。
表2 評(píng)估的去匿名攻擊方法Table 2 Evaluated de-anonymization attack methods
為了公平地比較本文模型與已有去匿名攻擊方法,本文首先分析已有方法,找出他們的最佳參數(shù),然后將本文方法與配置最佳參數(shù)的已有方法進(jìn)行比較。
Rand方法[22]通過隨機(jī)選取2個(gè)或4個(gè)時(shí)空位置作為準(zhǔn)標(biāo)識(shí)符來重識(shí)別匿名用戶。如圖4所示,縱坐標(biāo)表示去匿名方法的重識(shí)別準(zhǔn)確度,本文共比較4種Rand方法:
1) S-Rand-2:考慮空間屬性,選2個(gè)隨機(jī)位置;
2) S-Rand-4:考慮空間屬性,選4個(gè)隨機(jī)位置;
3) ST-Rand-2:考慮時(shí)空屬性,選2個(gè)隨機(jī)位置;
4) ST-Rand-4:考慮時(shí)空屬性,選4個(gè)隨機(jī)位置。
圖4 Rand方法[22]的重識(shí)別準(zhǔn)確度Fig.4 Re-identification accuracies of rand methods[22]
由圖4可以看出,ST-Rand-2和ST-Rand-4的重識(shí)別準(zhǔn)確度分別比S-Rand-2和S-Rand-4高,表明考慮時(shí)空屬性的Rand方法優(yōu)于只考慮空間屬性的Rand方法,這再一次說明了用戶移動(dòng)軌跡中時(shí)空屬性對(duì)用戶移動(dòng)行為分析的作用。此外,S-Rand-4和ST-Rand-4的重識(shí)別準(zhǔn)確度分別比S-Rand-2和ST-Rand-2高,表明Rand方法選取4個(gè)隨機(jī)位置表現(xiàn)更佳。ST-Rand-4方法是4個(gè)方法中表現(xiàn)最優(yōu)的一個(gè),對(duì)于Train1-Test1數(shù)據(jù)集的重識(shí)別準(zhǔn)確度可以達(dá)到13%左右,對(duì)于數(shù)據(jù)集Train2-Test2的重識(shí)別準(zhǔn)確度約為66%。
MMC方法[1]分別為訓(xùn)練集和測(cè)試集中的每個(gè)用戶構(gòu)建MMC描述,然后通過計(jì)算MMC之間的距離來確定用戶相似度,以與測(cè)試集匿名用戶相似度最高的訓(xùn)練集用戶作為重識(shí)別結(jié)果。這種方法可以配置地理距離閾值參數(shù),本文將這個(gè)參數(shù)配置為1、2、3、4 km,并將配置有這4個(gè)參數(shù)的MMC方法分別命名為MMC-1、MMC-2、MMC-3、MMC-4。這4個(gè)方法的重識(shí)別準(zhǔn)確度對(duì)比如圖5所示,可以觀察到MMC-1和MMC-2表現(xiàn)最佳。對(duì)于數(shù)據(jù)集Train1-Test1,這2種方法的重識(shí)別準(zhǔn)確度約為11%;對(duì)于數(shù)據(jù)集Train2-Test2,這2種方法的重識(shí)別準(zhǔn)確度約為14%。MMC方法的準(zhǔn)確度比較低,說明這種方法對(duì)時(shí)間屬性的考慮并不充分。
圖5 MMC方法[1]的重識(shí)別準(zhǔn)確度Fig.5 Re-identification accuracies of MMC methods[1]
為了對(duì)本文方法與已有方法進(jìn)行公平地比較,本文為已有方法配置最佳的參數(shù),即將本文的STCS方法和STES方法與ST-Rand-4方法、MMC-1方法、H/W方法進(jìn)行比較,如圖6所示??梢钥闯?,對(duì)于數(shù)據(jù)集Train1-Test1,STCS方法可以達(dá)到約32%的準(zhǔn)確度,遠(yuǎn)優(yōu)于ST-Rand-4方法和MMC-1方法,但相比H/W方法優(yōu)勢(shì)不大;而STES方法可以達(dá)到約57%的準(zhǔn)確度,遠(yuǎn)優(yōu)于其他方法。對(duì)于數(shù)據(jù)集Train2-Test2,STCS方法的重識(shí)別準(zhǔn)確度約為57%,而STES方法的重識(shí)別準(zhǔn)確度可達(dá)到約98%??偟膩碚f,由于Train1-Test1數(shù)據(jù)集的劃分方式更有實(shí)際意義,而對(duì)于這一對(duì)數(shù)據(jù)集來說,STCS方法相比已有方法有微弱優(yōu)勢(shì)。而無論對(duì)哪一對(duì)數(shù)據(jù)集來說,STES方法都具有極明顯的優(yōu)勢(shì)。這說明:
1) 考慮時(shí)空屬性確實(shí)比只考慮空間屬性更能有效地進(jìn)行匿名用戶重識(shí)別。
2) 相比STCS方法,STES方法對(duì)時(shí)空屬性的考慮更充分,這與第3節(jié)的分析是吻合的。
圖6 本文去匿名攻擊與其他攻擊方法的對(duì)比Fig.6 Comparison between our attack and other ones
從上述實(shí)驗(yàn)可以看到,對(duì)于數(shù)據(jù)集Train1-Test1的重識(shí)別準(zhǔn)確度要低于對(duì)Train2-Test2的重識(shí)別準(zhǔn)確度。這是因?yàn)榍罢哂?xùn)練集與測(cè)試集并無交集,而后者的測(cè)試集就是從訓(xùn)練集中抽取出來的,從直觀上來看,后者的重識(shí)別準(zhǔn)確度也應(yīng)該高于前者。然而,顯然基于前者的假設(shè)是更有實(shí)際意義的,基于后者的比較只是為了與已有方法做更全面的比較(因?yàn)镽and方法是基于后者做的實(shí)驗(yàn))。
1)本文基于信息熵定量分析了用戶移動(dòng)軌跡中時(shí)空傾向性。
2)基于用戶移動(dòng)軌跡中的時(shí)空傾向性,提出了一種時(shí)空感知的用戶隱馬爾可夫模型ST-UHMM以及時(shí)空感知的去匿名攻擊模型ST-DAAM,相應(yīng)定義了2種時(shí)空感知的相似度定義STCS和STES。
3)本文使用MSRA采集的GeoLife數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果說明,本文的STCS方法相比已有方法略有優(yōu)勢(shì),而STES方法則具有明顯的優(yōu)勢(shì)。說明了時(shí)間屬性對(duì)用戶移動(dòng)行為分析的顯著作用,為以后的去匿名攻擊方法設(shè)計(jì)提供了參考。