雷凱躍，李興華，劉海，裴卓雄，馬建峰，李暉

（西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071）

軌跡發(fā)布中基于時(shí)空關(guān)聯(lián)性的假軌跡隱私保護(hù)方案

雷凱躍，李興華，劉海，裴卓雄，馬建峰，李暉

（西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071）

從軌跡的整體方向、軌跡中相鄰位置的時(shí)間可達(dá)及移動(dòng)距離對(duì)單條軌跡中相鄰位置間的時(shí)空關(guān)聯(lián)性和軌跡間的相似性進(jìn)行分析，提出了一種基于時(shí)空關(guān)聯(lián)性的假軌跡隱私保護(hù)方案。安全性分析表明所提方案能有效混淆假軌跡與真實(shí)軌跡，避免攻擊者識(shí)別出假軌跡。大量實(shí)驗(yàn)表明，所提方案在僅需較少計(jì)算時(shí)間的同時(shí)，能確保生成的假軌跡與真實(shí)軌跡具有相似性，從而有效保護(hù)軌跡發(fā)布中用戶的軌跡隱私。

軌跡發(fā)布；隱私保護(hù)；假軌跡；時(shí)空關(guān)聯(lián)性；軌跡泄露

1 引言

基于位置的服務(wù)(LBS,location-based service)[1,2]是指與用戶指定地理位置密切相關(guān)的信息服務(wù)，如用戶可利用Google Latitude等應(yīng)用查詢指定位置的美食、酒店等信息。隨著LBS的廣泛應(yīng)用，用戶不再局限于享受實(shí)時(shí)的查詢服務(wù)，而是更廣泛地應(yīng)用由位置序列構(gòu)成的軌跡發(fā)布[3,4]，如物流公司保存自己的運(yùn)輸軌跡，用于分析其運(yùn)輸路線是否合理；市政部門收集出租車運(yùn)行軌跡用于路網(wǎng)建設(shè)或交通管理。

然而，人們?cè)谙硎鼙憬莸腖BS的同時(shí)，也面臨著隱私被竊取的風(fēng)險(xiǎn)。用戶發(fā)布的軌跡中往往包含大量的時(shí)空信息。這就使惡意攻擊者可通過(guò)分析這些時(shí)空信息，結(jié)合自己掌握的背景知識(shí)，非法獲取用戶的興趣愛好、宗教信仰、身體狀況、家庭及工作地址等個(gè)人隱私，甚至給用戶帶來(lái)經(jīng)濟(jì)損失或威脅用戶的人身安全。因此，軌跡發(fā)布中的隱私保護(hù)受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。

現(xiàn)有的軌跡發(fā)布隱私保護(hù)方法可分為3種：假軌跡[5～8]、軌跡k-匿名[9～11]和軌跡抑制[12,13]。與后2種方法相比，假軌跡隱私保護(hù)方法無(wú)需可信第三方，且能保留完整的軌跡信息，因此，常被用于保護(hù)軌跡發(fā)布中的用戶軌跡隱私。

然而，現(xiàn)有的假軌跡隱私保護(hù)方案在假軌跡的生成過(guò)程中，不僅未結(jié)合實(shí)際的地貌、路況等因素考慮單條軌跡中相鄰位置間的時(shí)空關(guān)聯(lián)性，也忽略了軌跡之間的時(shí)空關(guān)聯(lián)性。因此，若用戶采用現(xiàn)有假軌跡方案保護(hù)自己的真實(shí)軌跡，攻擊者就能利用單條軌跡中相鄰位置間的時(shí)空關(guān)聯(lián)性和軌跡之間的時(shí)空關(guān)聯(lián)性，識(shí)別出某些假軌跡，甚至直接獲取用戶的真實(shí)軌跡。如圖1所示，若在請(qǐng)求時(shí)間間隔內(nèi)不可達(dá)，則攻擊者就能以較大概率識(shí)別出軌跡1是假軌跡；軌跡3的整體移動(dòng)方向與軌跡1和軌跡2相反，攻擊者也會(huì)以較大概率推測(cè)出軌跡3是假軌跡。此外，由于C1的出入度為4，攻擊者就可能會(huì)將C1作為移動(dòng)樞紐，從而將軌跡2識(shí)別為用戶的真實(shí)軌跡。本文也通過(guò)大量的實(shí)驗(yàn)證明了現(xiàn)有假軌跡隱私保護(hù)方案僅能以不高于15%的成功率保護(hù)用戶的真實(shí)軌跡。

圖1 軌跡關(guān)系

針對(duì)上述問題，本文從軌跡的整體方向、軌跡中相鄰位置的時(shí)間可達(dá)及移動(dòng)距離對(duì)單條軌跡中相鄰位置間的時(shí)空關(guān)聯(lián)性和軌跡間的時(shí)空關(guān)聯(lián)性進(jìn)行分析，提出了一個(gè)假軌跡隱私保護(hù)方案。本文的主要貢獻(xiàn)如下。

1) 針對(duì)現(xiàn)有的假軌跡隱私保護(hù)方法，利用時(shí)間可達(dá)性和出入度提出了一個(gè)假軌跡識(shí)別方案。大量實(shí)驗(yàn)表明，所提假軌跡識(shí)別方案在誤判率僅為23%的情況下，能夠識(shí)別出85%的假軌跡。這證明了現(xiàn)有假軌跡方案并不能有效保護(hù)用戶的軌跡隱私。

2) 從整體和局部的角度考慮了單條軌跡中相鄰位置間的時(shí)空關(guān)聯(lián)性以及軌跡之間的時(shí)空關(guān)聯(lián)性，提出了一個(gè)假軌跡隱私保護(hù)方案。安全性分析表明，所提方案能混淆真實(shí)軌跡和假軌跡。

3) 大量的實(shí)驗(yàn)表明，本方案在具有較低計(jì)算開銷的同時(shí)，與現(xiàn)有假軌跡隱私保護(hù)方法相比，具有更低的真實(shí)軌跡隱私泄露率，有效保護(hù)軌跡發(fā)布中的用戶軌跡隱私。

2 相關(guān)工作

軌跡k-匿名方法是指在軌跡發(fā)布前由匿名服務(wù)器挑選出k–1條與用戶真實(shí)軌跡無(wú)法區(qū)分的軌跡，通過(guò)將k條軌跡中對(duì)應(yīng)時(shí)刻的位置泛化為相應(yīng)的匿名區(qū)域形成路徑來(lái)實(shí)現(xiàn)軌跡隱私保護(hù)。Xu等[9]提出利用其他用戶的歷史足跡選擇k–1條軌跡，并形成相應(yīng)的匿名區(qū)。隨后，王超等[10]針對(duì)現(xiàn)有的軌跡匿名算法在計(jì)算軌跡相似性時(shí)忽略軌跡形狀因素，產(chǎn)生的匿名軌跡集合可用性相對(duì)較低這一問題，不僅考慮軌跡的時(shí)間和空間要素，更加入了軌跡的形狀因素，提出一個(gè)基于軌跡位置形狀相似性的隱私保護(hù)方案。王爽等[11]將線性軌跡轉(zhuǎn)化為不確定區(qū)域的思想引入軌跡數(shù)據(jù)的隱私處理，提出了不確定軌跡隱私保護(hù)方案。該方案利用布朗運(yùn)動(dòng)模型，將軌跡泛化成一個(gè)更為真實(shí)的軌跡區(qū)域，并將相似度高的軌跡域聚合成等價(jià)類進(jìn)行數(shù)據(jù)的隱匿和發(fā)布。

但是，軌跡k-匿名隱私保護(hù)方法需要引入一個(gè)可信的第三方作為匿名服務(wù)器，而在現(xiàn)實(shí)環(huán)境中完全可信的第三方難以找到。這就使軌跡k-匿名隱私保護(hù)方法具有較低的實(shí)用性。

軌跡抑制方法是指對(duì)在軌跡發(fā)布前去除某些敏感或被頻繁訪問的位置。Terrovitis等[12]假設(shè)攻擊者擁有部分真實(shí)軌跡，提出在軌跡發(fā)布時(shí)抑制處于敏感區(qū)域的位置，使軌跡泄露的風(fēng)險(xiǎn)不高于用戶設(shè)置的隱私保護(hù)閾值。其中，區(qū)域的敏感度是根據(jù)區(qū)域內(nèi)用戶數(shù)量與總用戶數(shù)量的比值進(jìn)行計(jì)算。趙婧等[13]基于軌跡頻率，通過(guò)對(duì)有問題的軌跡添加假數(shù)據(jù)和利用隱私關(guān)聯(lián)度和數(shù)據(jù)效用之間的關(guān)系對(duì)軌跡數(shù)據(jù)進(jìn)行局部處理的方法，提出了2種軌跡抑制隱私保護(hù)方案。

然而，如何找到合理抑制的位置信息仍是軌跡抑制隱私保護(hù)方法有待解決的關(guān)鍵問題，并且，如果抑制的位置過(guò)多會(huì)造成信息損失。這也限制了軌跡抑制隱私保護(hù)方法的可用性。

假軌跡方法是指由用戶自己生成k–1條與真實(shí)軌跡相似的假軌跡，并與真實(shí)軌跡構(gòu)成含有k條軌跡的集合進(jìn)行發(fā)布，其基本思想最早是由Kido等[14,15]提出的。在他們的方案中，用戶可利用其前后兩次請(qǐng)求產(chǎn)生的假位置[15～17]形成假軌跡來(lái)保護(hù)自己的真實(shí)軌跡。You等[15]針對(duì)某一時(shí)刻對(duì)應(yīng)的位置數(shù)量和軌跡集合總的軌跡數(shù)量，提出了2種假軌跡生成方案。在第一種方案中，用戶首先決定假軌跡的起點(diǎn)和終點(diǎn)，然后在起點(diǎn)和終點(diǎn)之間隨機(jī)生成與真實(shí)軌跡運(yùn)行模式相似的假軌跡；第二種方案則是以用戶真實(shí)軌跡為基準(zhǔn)，通過(guò)選取真實(shí)軌跡上的位置點(diǎn)作為旋轉(zhuǎn)軸點(diǎn)，對(duì)真實(shí)軌跡進(jìn)行旋轉(zhuǎn)生成假軌跡；Lei等[6]提出在旋轉(zhuǎn)后得到的軌跡上增加交叉點(diǎn)的方法來(lái)增加假軌跡數(shù)量，從而提高用戶真實(shí)軌跡的隱私保護(hù)等級(jí)。Wu等[7]不僅考慮了真實(shí)軌跡與假軌跡之間的距離，還考慮了假軌跡之間的距離。它們通過(guò)擾動(dòng)[5]生成的假軌跡，使最終形成的軌跡集合能滿足用戶的隱私保護(hù)需求。李鳳華等[8]對(duì)用戶行動(dòng)模式和軌跡相似性等特征可能被敵手獲取情形下的軌跡隱私保護(hù)方案進(jìn)行研究，以用戶真實(shí)軌跡為基礎(chǔ)，通過(guò)軌跡旋轉(zhuǎn)保證用戶行動(dòng)軌跡的相似性，最后將該軌跡上的各個(gè)點(diǎn)偏移至附近的最接近真實(shí)的服務(wù)請(qǐng)求概率[18]的位置，生成假軌跡。

然而，現(xiàn)有的假軌跡隱私保護(hù)方法不僅未考慮單條軌跡中相鄰位置間的時(shí)空關(guān)聯(lián)性，也忽略了軌跡之間的時(shí)空關(guān)聯(lián)性，使攻擊者在誤判率僅為23%的情況下，能以85%的概率識(shí)別出假軌跡，甚至直接獲取到用戶的真實(shí)軌跡。

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

3.1 基本概念

軌跡由用戶的不斷移動(dòng)而產(chǎn)生由時(shí)間和位置組成時(shí)空序列。本文將軌跡表示為：traj= {＜loc1(x1,y1),time1＞,＜loc2(x2,y2),time2〉,… ＜locn(xn,yn),timen＞},其中，loci(xi,yi)表示在timei時(shí)刻的位置坐標(biāo)，1≤i≤n。當(dāng)軌跡發(fā)布時(shí)，由用戶生成k?1條假軌跡與真實(shí)軌跡trajreal組成的軌跡集合為Trajs={traj1,traj2,…,tarjk?1,trajreal}；表示集合Trajs中的元素個(gè)數(shù)。

本文借用圖論中出入度的概念來(lái)表示軌跡集合中以各位置為起點(diǎn)或終點(diǎn)的路徑數(shù)量。即出度表示在軌跡集合中，以第i條軌跡traji的第j個(gè)位置為起點(diǎn)的路徑數(shù)量；入度則表示在軌跡集合中，以第i條軌跡traji的第j個(gè)位置為終點(diǎn)的路徑數(shù)量。

3.2 攻擊模型

在軌跡發(fā)布中，攻擊者的目的是推測(cè)出某些假軌跡，降低用戶的軌跡隱私保護(hù)需求，甚至直接識(shí)別出用戶的真實(shí)軌跡，從而非法獲取用戶的個(gè)人隱私信息。本文假設(shè)攻擊者可以獲取用戶發(fā)布的所有軌跡移動(dòng)完整路徑，掌握地圖知識(shí)，且能夠利用地圖接口計(jì)算軌跡中前后相鄰位置的移動(dòng)距離和到達(dá)時(shí)間。攻擊者識(shí)別假軌跡的能力可從以下2個(gè)方面進(jìn)行度量。

1) 誤判率τ。表示攻擊者將用戶的真實(shí)軌跡識(shí)別為假軌跡的概率。樣本空間由軌跡集合Trajs表示，用E表示樣本容量。若用E′表示將用戶真實(shí)軌跡識(shí)別為假軌跡的樣本數(shù)，那么

其中，Trajs′?Trajs。

3.3 隱私度量標(biāo)準(zhǔn)

定義1軌跡移動(dòng)方向相似性。假設(shè)loci?1、loci和loci+1是任意一條軌跡traj中相鄰的3個(gè)位置，令表示它們形成的2個(gè)方向向量。此時(shí)，這2個(gè)方向向量形成的方向夾角θ滿足

那么，軌跡集合Trajs中的軌跡移動(dòng)方向相似度為

定義2軌跡泄露率。假設(shè)用戶發(fā)布的軌跡集合為Trajs，當(dāng)攻擊者利用其具有的軌跡識(shí)別能力對(duì)軌跡集合Trajs識(shí)別后，用戶真實(shí)位置在任意時(shí)刻（timei）的泄露概率為

那么，用戶真實(shí)軌跡的泄露率為

其中，m表示真實(shí)軌跡中方向夾角的個(gè)數(shù)。

4 攻擊方案

為了證明現(xiàn)有假軌跡隱私保護(hù)方案忽略了單條軌跡中相鄰位置間的時(shí)空關(guān)聯(lián)性以及軌跡之間的時(shí)空關(guān)聯(lián)性，本文利用相鄰位置間的可達(dá)時(shí)間和各位置的出入度提出一個(gè)假軌跡識(shí)別方案。該方案包含時(shí)間可達(dá)性識(shí)別和出入度識(shí)別2個(gè)步驟。

4.1 時(shí)間可達(dá)性識(shí)別

針對(duì)軌跡集中的每條軌跡，依次檢查該條軌跡中相鄰位置是否滿足時(shí)間可達(dá)性。即將該軌跡中相鄰位置坐標(biāo)發(fā)送至地圖接口，從地圖接口分別獲取相鄰位置間的可達(dá)時(shí)間mapTime。隨后利用公布時(shí)間間隔pubTime（對(duì)于具有n個(gè)點(diǎn)的軌跡traj，可被劃分為n?1段路徑，即每相鄰兩點(diǎn)構(gòu)成一段路徑，那么每條軌跡最多進(jìn)行n?1次比較)。最終根據(jù)對(duì)比結(jié)果，判斷該條軌跡是否為假軌跡。對(duì)于任意一條軌跡traji∈Trajs，其時(shí)間可達(dá)性識(shí)別步驟如下。

Step1若mapTime＞＞pubTime，即用戶在實(shí)際環(huán)境中，形成該段路徑所需的時(shí)間較長(zhǎng)（如相鄰2個(gè)位置分別位于河的兩岸）。此時(shí)，將該條路徑判定為假軌跡；否則，進(jìn)入Step 2。

Step2設(shè)定識(shí)別閾值δt。當(dāng)時(shí)，就判定該段路徑為可疑路徑。分別統(tǒng)計(jì)每條軌跡中可疑軌跡的段數(shù)numi。

Step3計(jì)算可疑軌跡的段數(shù)numi占該條軌跡中總路徑段數(shù)的比例。當(dāng)時(shí)，該條軌跡被識(shí)別為假軌跡。其中，δt_all為閾值。

4.2 出入度識(shí)別

出入度識(shí)別是利用發(fā)布的軌跡集合中各位置的出入度值，對(duì)假軌跡進(jìn)行識(shí)別。其基本步驟如下。

Step1統(tǒng)計(jì)軌跡集合中每條軌跡上各個(gè)點(diǎn)的出入度。用Di和Ci分別表示軌跡traji∈Trajs上各個(gè)位置的出度總和以及入度總和，即

其中，n表示軌跡traji上位置的數(shù)量。

Step2計(jì)算軌跡集合的平均出度DaverageOut和平均入度DaverageIn，即

Step3當(dāng)，Ci＜δin·DaverageIn時(shí)，就將該軌跡識(shí)別為假軌跡。其中，δout和δin表示出入度識(shí)別閾值。

4.3 實(shí)驗(yàn)評(píng)估

這部分實(shí)驗(yàn)所用的軌跡數(shù)據(jù)來(lái)自Wikiloc網(wǎng)站注1：http://www.wikiloc.com。，本文首先在該數(shù)據(jù)集中挑選用戶在城市中形成的軌跡數(shù)據(jù)，然后選用文獻(xiàn)[17]提出的假軌跡生成算法——ADTGA生成假軌跡，從而得到軌跡集合。ADTGA生成算法是目前最好的假軌跡生成算法，它在假軌跡生成過(guò)程中不僅考慮了真實(shí)軌跡與假軌跡之間的距離，還考慮了假軌跡之間的距離。最后，本文再利用上述假軌跡識(shí)別方案對(duì)生成的軌跡集進(jìn)行識(shí)別。實(shí)驗(yàn)環(huán)境為：Intel(R) Core(TM) i5-3470@ 3.20 GHz，4 GB內(nèi)存。算法由C++編程實(shí)現(xiàn)，程序運(yùn)行在 Windows 7環(huán)境下。

4.3.1 時(shí)間可達(dá)性識(shí)別效果評(píng)估

由圖2可知，隨著δt和δt_all的增大，誤判率和識(shí)別率均呈下降狀態(tài)。這是由于隨著δt和δt_all的不斷增大，使越來(lái)越多假軌跡能滿足時(shí)間可達(dá)性識(shí)別條件，它們不會(huì)被識(shí)別成假軌跡，這就導(dǎo)致了識(shí)別率的降低。相應(yīng)地，誤判率也會(huì)隨著被判斷為假軌跡的軌跡數(shù)量減少而降低。

4.3.2 出入度識(shí)別效果評(píng)估

出入度識(shí)別閾值δout和δin對(duì)出入度識(shí)別效果的影響情況如表1所示。在這部分實(shí)驗(yàn)，本文設(shè)置。這是因?yàn)樵贏DTGA算法生成的假軌跡集合中，各位置具有相同的出度和入度。由于ADTGA算法在生成假軌跡的過(guò)程中，每條假軌跡是由真實(shí)軌跡旋轉(zhuǎn)得到的。這就使生成的每條假軌跡均與真實(shí)軌跡相交。顯然，每個(gè)交點(diǎn)均會(huì)造成出入度的增加。這就導(dǎo)致真實(shí)軌跡的出入度總是大于軌跡集合的平均出入度。因此，當(dāng)出入度識(shí)別閾值時(shí)，誤判率為0。當(dāng)時(shí)，平均出入度與一個(gè)大于1的值相乘，得到的結(jié)果變大。此時(shí)出現(xiàn)真實(shí)軌跡出入度小于平均出入度的情況，因此存在誤判。

圖2 時(shí)間可達(dá)性識(shí)別

表1 δout和δin對(duì)出入度識(shí)別的影響

4.3.3 所提方案的識(shí)別效果評(píng)估

本文將時(shí)間可達(dá)性識(shí)別和出入度識(shí)別同時(shí)用于識(shí)別假軌跡，其結(jié)果如圖3所示。通過(guò)表1可知，當(dāng)δout=δin=1時(shí)，出入度攻擊具有較高的識(shí)別率且誤判率為0。因此，此處將出入度閾值設(shè)為1。當(dāng)時(shí)，所提假軌跡識(shí)別方案的誤判率僅為23%，而識(shí)別率高達(dá)85%。即現(xiàn)有的假軌跡隱私保護(hù)方案僅能以15%的成功率保護(hù)用戶的真實(shí)軌跡。

圖3 假軌跡攻擊方案

5 基于時(shí)空關(guān)聯(lián)性的假軌跡隱私保護(hù)方案

基于上述假軌跡識(shí)別原理，本文還提出了一種基于時(shí)空關(guān)聯(lián)性的假軌跡隱私保護(hù)方案，在假軌跡生成過(guò)程中不僅考慮了每段路徑的時(shí)間可達(dá)性及移動(dòng)距離，還對(duì)軌跡的整體移動(dòng)方向進(jìn)行限制。最后還保證在生成的軌跡集合中，每個(gè)位置具有相同的出入度。具體過(guò)程如下所示。

1) 擬合真實(shí)軌跡的整體方向

本文利用最小二乘法擬合真實(shí)軌跡的整體方向，從而保證隨后生成的假軌跡的移動(dòng)方向與用戶真實(shí)軌跡的移動(dòng)方向相似，使攻擊者難以通過(guò)移動(dòng)方向識(shí)別出假軌跡。其中，用戶真實(shí)軌跡的移動(dòng)方向的斜率為

2) 起止假位置的生成

利用現(xiàn)有的假位置生成方案，分別以真實(shí)軌跡的起點(diǎn)和終點(diǎn)為保護(hù)點(diǎn)生成假位置集合，并分別從LocSet1和LocSetn中選擇假位置，使真實(shí)軌跡整體移動(dòng)方向的斜率l與假軌跡起止點(diǎn)構(gòu)成的斜率lslope相近且起止點(diǎn)未在已有軌跡中出現(xiàn)。這不僅能限制假軌跡的整體運(yùn)動(dòng)方向，還能保證起止位置的出入度均為1。此外，起止位置還需要滿足下列條件

這是因?yàn)橹挥斜ＷC假軌跡起止點(diǎn)在時(shí)間區(qū)間內(nèi)可達(dá)，才有可能保證該軌跡中任意相鄰兩位置能在發(fā)布時(shí)間間隔內(nèi)可達(dá)，并且，移動(dòng)距離的控制又使假軌跡與真實(shí)軌跡具有相似的移動(dòng)速度。

3) 中間位置的生成

逐一為每條假軌跡生成其第2個(gè)到第n–1個(gè)位置。在生成假軌跡的第個(gè)位置時(shí)，以真實(shí)軌跡的第i–1和i個(gè)位置之間的歐式距離r+random為半徑(random表示隨機(jī)數(shù))，以假軌跡第i–1個(gè)位置為圓心作圓。在lslope所在直線的兩側(cè)，每間隔θ°選擇一個(gè)候選位置，構(gòu)成假位置候選集合，直至網(wǎng)格邊界與lslope所在直線的夾角達(dá)到閾值，如圖4所示。假位置候選集為圖4中陰影部分。然后再在候選集合LocSet′中隨機(jī)選擇假位置。這樣不僅保證生成的假位置具有隨機(jī)性，而且不能避免出現(xiàn)中間位置突然遠(yuǎn)離整體軌跡的情況。其中，，d是網(wǎng)格的邊長(zhǎng)。

圖4 假位置候選集

4) 對(duì)完整的假軌跡進(jìn)行整體方向的檢查

在生成完整的假軌跡后，擬合假軌跡的整體移動(dòng)方向的斜率為

隨后，將假軌跡的整體移動(dòng)方向的斜率ldummy與真實(shí)軌跡的整體移動(dòng)方向的斜率l進(jìn)行對(duì)比。如果斜率相近，則進(jìn)行時(shí)間及移動(dòng)距離的判斷。如果不滿足，則重新生成假軌跡。

5) 對(duì)假軌跡的每段路徑進(jìn)行時(shí)間可達(dá)性和移動(dòng)距離檢查

對(duì)任意第d條假軌跡trajd的第i個(gè)位置和第i+1位置形成的路徑進(jìn)行時(shí)間可達(dá)性檢查和移動(dòng)距離檢查，若

不成立，則記錄下不滿足要求的路徑段數(shù)num。如果num＞δ(n?1)，則表示不滿足要求的軌跡數(shù)過(guò)多，此時(shí)重新生成假軌跡；否則，該條軌跡即為所生成假軌跡。其中，δd、δt和δ為檢查閾值。

利用上述方案，直到生成k–1條假軌跡。綜上所示，本文所提的基于時(shí)空關(guān)聯(lián)性的假軌跡生成算法如下。

算法1基于時(shí)空關(guān)聯(lián)性的假軌跡生成算法

輸入軌跡

輸出軌跡集合

5.1 安全性分析

當(dāng)用戶采用本方案生成假軌跡時(shí)，本文首先擬合用戶真實(shí)軌跡的整體移動(dòng)方向，計(jì)算其斜率。隨后在假軌跡起止位置的生成過(guò)程中，本文通過(guò)計(jì)算斜率比，避免出現(xiàn)假軌跡與真實(shí)軌跡移動(dòng)方向相反的情況。當(dāng)斜率比不斷接近1時(shí)，就能保證虛假移動(dòng)路徑的整體方向與用戶真實(shí)路徑的移動(dòng)方向平行，使攻擊者難以利用移動(dòng)方向識(shí)別出假軌跡。并且，本方案還能保證起止位置構(gòu)成的路徑能在發(fā)布時(shí)間間隔內(nèi)可達(dá)，并利用移動(dòng)距離使用戶在假軌跡與真實(shí)軌跡上具有相近的移動(dòng)速度。這樣可避免攻擊者在獲知用戶采用某種交通工具時(shí)，利用該類交通工具的移動(dòng)速度通過(guò)計(jì)算可達(dá)時(shí)間識(shí)別出假軌跡。當(dāng)為每條假軌跡生成中間位置時(shí)，本文首先生成候選假位置時(shí)，還保證任意2條軌跡不會(huì)相交。在遵循上述同樣的原則對(duì)假軌跡進(jìn)行合理軌跡段比例檢查。攻擊者從每個(gè)時(shí)刻觀察到的位置數(shù)目即為軌跡的數(shù)量k。此時(shí)，用戶真實(shí)軌跡的泄露率為

滿足用戶的隱私保護(hù)需求。綜上所述，當(dāng)攻擊者與用戶具有相同的假軌跡識(shí)別能力時(shí)，用戶采用本方案能有效保護(hù)自己的真實(shí)軌跡。

5.2 實(shí)驗(yàn)分析

為了便于進(jìn)行有效性分析，本部分實(shí)驗(yàn)仍采用4.3節(jié)中介紹的實(shí)驗(yàn)數(shù)據(jù)與實(shí)驗(yàn)環(huán)境。本文從實(shí)驗(yàn)數(shù)據(jù)集中隨機(jī)選擇不同的軌跡作為用戶真實(shí)移動(dòng)軌跡，隨后采用本文提出的基于時(shí)空關(guān)聯(lián)性的假軌跡生成算法生成假軌跡，形成軌跡集合。最后，再利用第4節(jié)提出的假軌跡識(shí)別方案對(duì)生成的軌跡進(jìn)行識(shí)別，從而表明所提的基于時(shí)空關(guān)聯(lián)性的假軌跡隱私保護(hù)方案能有效保護(hù)用戶的真實(shí)軌跡。

5.2.1 軌跡數(shù)量k對(duì)軌跡泄露概率的影響

本文利用第4節(jié)提出的假軌跡識(shí)別方法對(duì)本方案生成的軌跡集合進(jìn)行識(shí)別，從而說(shuō)明本文方案能有效保護(hù)用戶的軌跡隱私。在這部分實(shí)驗(yàn)中本文設(shè)置，實(shí)驗(yàn)如圖5所示。當(dāng)攻擊者利用單條軌跡中的時(shí)空關(guān)聯(lián)性以及軌跡間的時(shí)空關(guān)聯(lián)性對(duì)生成軌跡集合進(jìn)行識(shí)別后，并不能識(shí)別出假軌跡。此時(shí)用戶的真實(shí)軌跡隱私保護(hù)等級(jí)仍為，滿足用戶隱私保護(hù)需求。而攻擊者利用上述時(shí)空關(guān)聯(lián)性對(duì)由ADTGA算法生成的軌跡集合進(jìn)行識(shí)別時(shí)，最好的情況是k=15和k=18時(shí)，還剩下2條假軌跡未被識(shí)別出。此時(shí)，用戶的真實(shí)軌跡隱私保護(hù)等級(jí)僅為，遠(yuǎn)大于。這就說(shuō)明了本文方案能有效保護(hù)用戶的軌跡隱私。

圖5 利用時(shí)空關(guān)聯(lián)性識(shí)別后剩下的軌跡數(shù)量

5.2.2 軌跡數(shù)量k對(duì)軌跡相似度的影響

軌跡的移動(dòng)方向相似度表現(xiàn)了假軌跡與真實(shí)軌跡的輪廓相似程度，能在一定程度上反映用戶真實(shí)軌跡的隱私保護(hù)等級(jí)。具體實(shí)驗(yàn)結(jié)果如圖6所示?？傮w來(lái)說(shuō)，隨著k的改變，本文方案生成的軌跡集合的相似度σ保持不變，且均在0.5以下。從3.3節(jié)中可知，σ越低，表明生成的軌跡集合中各軌跡間的運(yùn)動(dòng)方向就越相似。這也說(shuō)明了本方案能預(yù)防攻擊者利用各軌跡的移動(dòng)方向識(shí)別出虛假移動(dòng)路徑。

圖6 k對(duì)軌跡相似度的影響

5.2.3 軌跡數(shù)量k對(duì)方案執(zhí)行時(shí)間的影響

本文簡(jiǎn)要分析軌跡數(shù)量k對(duì)本文所提出的假軌跡生成方案在計(jì)算開銷上的影響，實(shí)驗(yàn)結(jié)果如圖7所示。由于生成的假軌跡數(shù)量隨著k的增大而增多，這就使本方案所需的計(jì)算時(shí)間也隨之增加。然而當(dāng)k=20時(shí)，本方案成功為用戶生成假軌跡所需的計(jì)算時(shí)間僅僅需要0.38 s。這說(shuō)明本文方案具有良好的實(shí)用性。

圖7 k 對(duì)方案運(yùn)行時(shí)間的影響

綜上所述，本方案在具有較低計(jì)算開銷的同時(shí)，與現(xiàn)有假軌跡隱私保護(hù)方案相比，還能混淆真實(shí)軌跡與假軌跡間的時(shí)空關(guān)聯(lián)性，從而有效保護(hù)軌跡發(fā)布中用戶的軌跡隱私。

6 結(jié)束語(yǔ)

本文通過(guò)大量實(shí)驗(yàn)首先證明現(xiàn)有假軌跡隱私保護(hù)方案僅能以不高于15%的成功率保護(hù)用戶的真實(shí)軌跡。而造成上述問題的原因是現(xiàn)有假軌跡隱私保護(hù)方案不僅未考慮單條軌跡中相鄰位置間的時(shí)空關(guān)聯(lián)性，也忽略了軌跡之間的時(shí)空關(guān)聯(lián)性，使攻擊者能正確識(shí)別出某些假軌跡，乃至推測(cè)出用戶的真實(shí)軌跡。針對(duì)上述問題，本文從軌跡的整體方向、軌跡中相鄰位置的時(shí)間可達(dá)及移動(dòng)距離對(duì)單條軌跡中相鄰位置間的時(shí)空關(guān)聯(lián)性和軌跡之間的時(shí)空關(guān)聯(lián)性進(jìn)行分析，提出了一個(gè)假軌跡隱私保護(hù)方案。安全性分析表明，所提方案能混淆真實(shí)軌跡和假軌跡間的時(shí)空關(guān)聯(lián)性，使攻擊者難以識(shí)別出假軌跡。大量實(shí)驗(yàn)也表明，本文方案在具有較低計(jì)算開銷的同時(shí)，與現(xiàn)有假軌跡隱私保護(hù)方法相比，能降低用戶真實(shí)軌跡的隱私泄露率，有效保護(hù)軌跡發(fā)布中的用戶軌跡隱私。

[1]KRUMM J.A survey of computational location privacy[J].Personal and Ubiquitous Computing,2009,13(6):391-399.

[2]霍崢,孟小峰.軌跡隱私保護(hù)技術(shù)研究[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1820-1830.ZHENG H,MENG X F.A survey of trajectory privacy-preserving techniques[J].Chinese Journal of Computers,2011,34(10):1820-1830.

[3]CHOW C Y,MOKBEL M F.Trajectory privacy in location-based services and data publication[J].ACM SIGKDD Explorations Newsletter,2011,13(1):19-29.

[4]ZHANG Z,SUN Y,XIE X,et al.An efficient method on trajectory privacy preservation[C]//International Conference on Big Data Computing and Communications.Springer International Publishing,2015:231-240.

[5]YOU T H,PENG W C,LEE W C.Protecting moving trajectories with dummies[C]//2007 International Conference on Mobile Data Management.IEEE,2007:278-282.

[6]LEI P R,PENG W C,SU I J,et al.Dummy-based schemes for protecting movement trajectories[J].Journal of Information Science and Engineering,2012,28(2):335-350.

[7]WU X,SUN G.A novel dummy-based mechanism to protect privacy on trajectories[C]//2014 IEEE International Conference on Data Mining Workshop (ICDMW).IEEE,2014:1120-1125.

[8]李鳳華,張翠,牛犇,等.高效的軌跡隱私保護(hù)方案[J].通信學(xué)報(bào),2015.36(12):114-123.LI F H,ZHANG C,NUI B,et al.Efficient scheme for user’s trajectory privacy[J].Journal on Communications,2015,36(12):114-123.

[9]XU T,CAI Y.Exploring historical location data for anonymity preservation in location-based services[C]//The 27th Conference on Computer Communications.IEEE,2008.

[10]王超,楊靜,張健沛.基于軌跡位置形狀相似性的隱私保護(hù)算法[J].通信學(xué)報(bào),2015,36(2):144-157.WANG C,YANG J,ZHANG J P.Privacy preserving algorithm based on trajectory location and shape similarity[J].Journal on Communications,2015,36(2):144-157.

[11]王爽,周福才,吳麗娜.移動(dòng)對(duì)象不確定軌跡隱私保護(hù)算法研究[J].通信學(xué)報(bào),2015,36(Z1):94-102.WANG S,ZHOU F C,WU L N.Uncertain trajectory privacypreserving method of moving object[J].Journal on Communications,2015,36(Z1):94-102.

[12]TERROVITIS M,MAMOULIS N.Privacy preservation in the publication of trajectories[C]//9th International Conference on Mobile Data Management.IEEE,2008:65-72.

[13]趙婧,張淵,李興華,等.基于軌跡頻率抑制的軌跡隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(10):2096-2106.ZHAO J,ZHANG Y,LI X H,et al.A trajectory privacy protection approach via trajectory frequency suppression[J].Chinese Journal of Computers,2014,37(10):2096-2106.

[14]KIDO H,YANAGISAWA Y,SATOH T.An anonymous communication technique using dummies for location-based services[C]//International Conference on Pervasive Services.IEEE,2005:88-97.

[15]KIDO H,YANAGISAWA Y,SATOH T.Protection of location privacy using dummies for location-based services[C]//21st International Conference on Data Engineering Workshops.IEEE,2005:1248-1248.

[16]LU H,JENSEN C S,YIU M L.Pad:privacy-area aware,dummybased location privacy in mobile services[C]//The Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access.ACM,2008:16-23.

[17]NIU B,LI Q,ZHU X,et al.Achieving k-anonymity in privacy-aware location-based services[C]//IEEE INFOCOM 2014-IEEE Conference on Computer Communications.IEEE,2014:754-762.

[18]HUO Z,HUANG Y,MENG X.History trajectory privacy-preserving through graph partition[C]//The 1st International Workshop on Mobile Location-Based Service.ACM,2011:71-78.

雷凱躍（1990-），女，天津人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)槲恢秒[私保護(hù)。

李興華（1978-），男，河南南陽(yáng)人，博士，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)殡[私保護(hù)、網(wǎng)絡(luò)與信息安全。

劉海（1984-），男，貴州貴陽(yáng)人，西安電子科技大學(xué)博士生，主要研究方向?yàn)槲恢秒[私保護(hù)和理性密碼協(xié)議。

裴卓雄（1993-），男，山西運(yùn)城人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)槲恢秒[私保護(hù)。

馬建峰（1963-），男，陜西西安人，博士，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾诺谰幋a、網(wǎng)絡(luò)與信息安全、密碼學(xué)。

李暉（1968-），男，河南靈寶人，博士，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)、無(wú)線網(wǎng)絡(luò)安全、云計(jì)算安全、信息論與編碼理論。

Dummy trajectory privacy protection scheme for trajectory publishing based on the spatiotemporal correlation

LEI Kai-yue,LI Xing-hua,LIU Hai,PEI Zhuo-xiong,MA Jian-feng,LI Hui
（School of Cyber Engineering,Xidian University,Xi’an 710071,China）

The spatiotemporal correlation was analyzed between neighboring locations and the trajectories similarity from the movement direction,the reachable time between neighboring locations and the movement distance,and a dummy trajectory privacy protection scheme based on the spatiotemporal correlation was proposed.Security analysis shows that the presented scheme successfully confuses the user’s real trajectory with dummy trajectories,thereby protecting the user’s trajectory privacy.Furthermore,extensive experiments indicate that the presented scheme not only has the limited computation cost,but also ensures that the generated dummy trajectories are similar to the user’s real trajectory.

trajectory publishing,privacy protection,dummy trajectory,spatiotemporal correlation,trajectory leakage

The National Natural Science Foundation of China (No.61372075,No.U1405255,No.61202389,No.61472310)

TP309

A

10.11959/j.issn.1000-436x.2016281

2016-08-16；

2016-09-30

李興華，xhli1@mail.xidian.edu.cn

資助項(xiàng)目（No.61372075,No.U1405255,No.61202389,No.61472310）