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

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

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

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

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

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

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

1 引言

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

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

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

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

圖1 軌跡關(guān)系

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

3 預(yù)備知識

3.1 基本概念

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

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

3.2 攻擊模型

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

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

其中，Trajs′?Trajs。

3.3 隱私度量標準

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

那么，軌跡集合Trajs中的軌跡移動方向相似度為

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

那么，用戶真實軌跡的泄露率為

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

4 攻擊方案

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

4.1 時間可達性識別

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

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

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

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

4.2 出入度識別

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

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

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

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

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

4.3 實驗評估

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

4.3.1 時間可達性識別效果評估

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

4.3.2 出入度識別效果評估

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

圖2 時間可達性識別

表1 δout和δin對出入度識別的影響

4.3.3 所提方案的識別效果評估

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

圖3 假軌跡攻擊方案

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

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

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

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

2) 起止假位置的生成

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

這是因為只有保證假軌跡起止點在時間區(qū)間內(nèi)可達，才有可能保證該軌跡中任意相鄰兩位置能在發(fā)布時間間隔內(nèi)可達，并且，移動距離的控制又使假軌跡與真實軌跡具有相似的移動速度。

3) 中間位置的生成

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

圖4 假位置候選集

4) 對完整的假軌跡進行整體方向的檢查

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

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

5) 對假軌跡的每段路徑進行時間可達性和移動距離檢查

對任意第d條假軌跡trajd的第i個位置和第i+1位置形成的路徑進行時間可達性檢查和移動距離檢查，若

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

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

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

輸入軌跡

輸出軌跡集合

5.1 安全性分析

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

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

5.2 實驗分析

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

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

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

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

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

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

圖6 k對軌跡相似度的影響

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

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

圖7 k 對方案運行時間的影響

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

6 結(jié)束語

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

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

[2]霍崢,孟小峰.軌跡隱私保護技術(shù)研究[J].計算機學(xué)報,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]李鳳華,張翠,牛犇,等.高效的軌跡隱私保護方案[J].通信學(xué)報,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]王超,楊靜,張健沛.基于軌跡位置形狀相似性的隱私保護算法[J].通信學(xué)報,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]王爽,周福才,吳麗娜.移動對象不確定軌跡隱私保護算法研究[J].通信學(xué)報,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]趙婧,張淵,李興華,等.基于軌跡頻率抑制的軌跡隱私保護方法[J].計算機學(xué)報,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é)碩士生，主要研究方向為位置隱私保護。

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

劉海（1984-），男，貴州貴陽人，西安電子科技大學(xué)博士生，主要研究方向為位置隱私保護和理性密碼協(xié)議。

裴卓雄（1993-），男，山西運城人，西安電子科技大學(xué)碩士生，主要研究方向為位置隱私保護。

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

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

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

資助項目（No.61372075,No.U1405255,No.61202389,No.61472310）