面向關聯攻擊的軌跡匿名方法

張磊，馬春光，楊松濤，李增鵬

（1. 哈爾濱工程大學計算機科學與技術學院，黑龍江 哈爾濱 150001；2. 佳木斯大學信息電子技術學院，黑龍江 佳木斯 154007）

面向關聯攻擊的軌跡匿名方法

張磊1,2，馬春光1，楊松濤1,2，李增鵬1

（1. 哈爾濱工程大學計算機科學與技術學院，黑龍江 哈爾濱 150001；2. 佳木斯大學信息電子技術學院，黑龍江 佳木斯 154007）

針對用戶在申請位置連續查詢服務時，不同移動類型產生的軌跡差異泄露用戶位置隱私的情況，提出一種相似軌跡實時生成方法。該方法實時計算可產生相似軌跡的連續位置，通過在生成的位置上添加虛假用戶與真實用戶建立匿名組，滿足在連續查詢過程中實時軌跡匿名的需求，彌補了當前軌跡隱私保護方法都針對已形成的軌跡進行匿名、無法滿足實時位置更新下用戶位置隱私保護方面的不足。在這種方法下，提出了一種根據用戶移動方向、速度等移動類型一致性計算的軌跡匿名方法，提高了生成軌跡的相似程度。同時，該方法充分考慮生成位置與真實用戶位置之間存在的差異，在保障軌跡相似的基礎上，進行了位置篩選，降低了攻擊者通過生成軌跡的不可到達性辨識出真實軌跡的概率。實驗表明，該方法在有效保護連續查詢用戶位置隱私的前提下，具有很好的執行效率。

隱私保護；連續查詢；位置匿名；相似軌跡

1 引言

隨著移動通信和定位技術的不斷發展與完善，基于位置服務（LBS, location based service）正逐漸深入人們日常生活中。人們在享受這種服務帶來便利的同時，不可避免地要面對隱私泄露問題。在眾多隱私信息泄露問題中，位置隱私最為突出。當前以k-匿名[1]、l-多樣性[2]、用戶協作[3]、錨點[4]和 PIR[5]為代表的基于快照（snapshoot）服務的方法已取得較好的隱私保護效果。然而，在實際使用中，用戶通常會在不同位置提出連續查詢請求，這些位置可被攻擊者通過關聯的方法構成位置軌跡。位置軌跡通常表現出比單個位置更多的時空關聯信息，這些信息又進一步增加了用戶隱私泄露的風險。如何對已產生和即將產生的位置軌跡信息加以保護，降低用戶隱私泄露風險，成為當前研究者關注的重要問題。

位置軌跡隱私保護最早起源于數據發布，基于k-匿名的思想分別從單元抑制[6]、單元泛化[7]、軌跡聚類[8]、轉化泛化[9]和全局軌跡相似[10]等方面被提出。Bonchi等[11,12]詳細分析并總結了這些基于數據發布的隱私保護方法。然而，通過分析可以看出，以上方法并不能保護實時查詢服務下的用戶隱私。因此，針對實時產生位置軌跡的情況，研究者提出了匿名[13～21]和mix-zone[22～26]兩類主要的隱私保護方法[27]。其中，匿名方法較mix-zone更易部署，且易于優化調整，因而被廣泛接受和使用。在實際部署過程中，由于匿名區域的限定，以及查詢次數、查詢距離與服務質量平衡等問題，一般使用連續匿名框進行匿名。這種方法在每個連續的匿名框內尋找至少k?1個相似用戶，使攻擊者無法確定k個用戶中真實用戶的所處位置。這種連續匿名的方法可以確保攻擊者無法將連續的兩次查詢位置相關聯，進而保護用戶的位置隱私。例如，圖1(a)表示的是用戶A、B和C經過匿名后擾亂的位置軌跡，其中，實線表示真實軌跡，虛線表示模糊軌跡。由于匿名用戶可產生多個不確定的后續位置，使攻擊者無法確定用戶產生的真實軌跡，在一定程度上保護了用戶的隱私。然而，這種方法存在被移動類型關聯用戶軌跡的可能。假設攻擊者通過觀察或其他方式獲取用戶的真實移動類型，那么即使經過匿名方法模糊了用戶的位置軌跡，攻擊者仍然可以通過軌跡差異獲得不同用戶的真實位置軌跡如圖1(b)所示。若A是待攻擊用戶，則根據3個用戶不同的移動類型，攻擊者可以正確識別出用戶A。因此，需要建立一種軌跡匿名方法，使用戶能夠產生如圖1(c)所示的位置軌跡，令攻擊者無法分辨出真實的待攻擊用戶，進而保護用戶的軌跡隱私。

全局軌跡相似[10]可以實現如圖1(c)所示的軌跡匿名，但其實時性較差，不適合在時效性要求較高的位置服務中使用。因此，需要針對全局軌跡相似的隱私保護思想，設計一種相似軌跡實時生成方法，最大限度地模糊攻擊者可獲取的用戶位置軌跡，保護連續查詢過程中用戶的位置隱私。

2 相關工作

圖1 用戶軌跡示意

2003年，Gruteser等[1]針對位置隱私保護問題，從數據發布的隱私保護中引入了k-匿名方法，通過與k?1個其他用戶同時提出服務請求，使攻擊者無法從k個用戶中準確分辨出待攻擊用戶所處的真實位置。Bamba等[2]針對可能存在的同質攻擊，提出了l-多樣性的概念，豐富了k-匿名技術。由于在用戶分布稀疏的情況下，尋找足夠的匿名參與用戶需要較大的匿名框，Wang[19]和Jia[20]等分別提出了縮小匿名區域的解決方法，并且通過單一匿名區域實現了連續查詢的位置隱私保護。針對潛在的關聯概率推測方法，張磊等[21]提出了關聯概率相似性的k-匿名方法。針對連續查詢中的假名關聯和內容關聯攻擊，Beresford等[22]提出了mix-zone技術。mix-zone可以看作是一個固定的黑盒區域，用戶駛入該區域時，可以與該區域中其他用戶進行身份交換。由于在該區域中攻擊者無法獲知用戶身份標識的更改過程，從而無法獲知更改后的身份標識與用戶之間的關聯情況。Freudiger等[23]優化了這種技術，使在實際部署中降低了對mix-zone的部署個數要求。同時，Freudiger等[24]又將 mix-zone技術引入路網環境中。針對矩形mix-zone無法有效模糊速度和方向等移動類型的情況，Palanisamy等[25]提出了非矩形mix-zone區域的概念，并針對時間關聯攻擊提出了時空耽擱的mix-zone[26]，以此降低時空關聯特性推測待攻擊用戶位置的概率。同樣針對假名關聯攻擊，潘曉等[13]出于對靜態匿名的方法不足以保護連續查詢位置隱私的考慮，提出了利用移動對象時序相似性計算來保護用戶位置隱私的方法。Hashem等[14]針對連續匿名區域重疊可被攻擊者根據查詢內容關聯用戶真實位置的情況，提出了將連續的匿名區域分離，并對可能的服務請求進行預檢索的方式，降低匿名區域重疊產生的頻率，防止匿名差異導致的位置信息泄露。張磊等[28]針對輪廓關聯問題提出了輪廓泛化的位置隱私保護模型。然而，這些方法只能保護假名關聯和查詢內容關聯攻擊下的位置隱私，并不能有效地防止攻擊者通過時間間隔關聯獲取用戶的位置軌跡。例如，在圖 2中，攻擊者可以根據用戶A在連續查詢過程中的時間間隔差異，辨識出A的連續查詢位置，進而獲得A位置軌跡隱私。

圖2 時間間隔差異導致的位置軌跡泄露

針對這種時間間隔關聯攻擊，Hwang等[15]提出了一種時間模糊的方法。該方法基于匿名服務器中保存的歷史數據，使用歷史查詢數據混淆當前查詢時間，進而模糊潛在的時間間隔關聯特性，以此保護用戶在時間間隔關聯攻擊下的軌跡隱私。但是，該方法存在一定的局限性，其模糊過程需要匿名服務器具有較高的存儲能力和數據計算能力。因此，在提供隱私保護的過程中，可能會出現服務瓶頸問題，同時這種方法并沒有考慮攻擊者根據移動類型進行關聯攻擊的情況。對于潛在的移動類型關聯攻擊，Gao等[16]通過一種用戶協作的方法，實現了用戶軌跡的移動類型相似，其過程是：首先，協作用戶統一使用與基用戶相同的查詢假名；然后，協作用戶選擇與基用戶相同的移動方向；最后，在相同的時間間隔內提出位置服務請求。然而，這種方法僅能保護有限的查詢次數，在多次查詢的情況下，很難保證協作用戶與基用戶產生軌跡的移動類型相似程度。Wang等[17]同樣基于移動類型相似進行隱私保護，但其方法未能有效地對用戶移動方向進行量化，導致所提出的算法存在軌跡差異性的攻擊漏洞。針對這一系列的攻擊問題，本文借鑒文獻[18]關于軌跡相似性計算的思想，通過計算相似軌跡位置的方法，實時地獲取相似軌跡，進而完成軌跡匿名。這種相似軌跡實時生成方法，模糊了用戶產生的位置軌跡，降低了攻擊者獲取用戶位置軌跡隱私的概率，較為有效地保護了用戶的個人隱私。

3 預備知識

本節主要介紹相似軌跡實時生成方法采用的系統架構、基本概念以及潛在的攻擊手段。

3.1 系統架構

基于位置服務隱私保護的系統架構主要分為2種：雙層架構和3層架構。雙層架構由用戶和位置服務提供商（LSP, location service provider）組成。該結構具有簡單、無需可依賴第三方等特點，但存在用戶自身計算負載過重以及協作用戶不可信或協作程度不高等缺點。3層架構是在用戶和LSP之間添加一個可信的第三方匿名服務器（AS, anonymous server）。該架構能夠提供較好的隱私保護效果，同時降低用戶的自身負載。本文所提出的隱私保護方法需要計算產生相似位置軌跡的后續匿名位置，若采用雙層模式，則用戶自身的計算負載過大，不宜在移動終端完成計算。因此，本文采用3層的位置隱私保護系統架構，該架構如圖3所示。

從圖3中可以看出，用戶首先將位置查詢發送給AS。經過AS中的位置計算模塊生成可產生相似軌跡的匿名位置，再由位置匿名模塊完成匿名后發送給LSP。LSP使用查詢模塊進行查詢后，同時將查詢結果保存到歷史數據中，最后將結果返回給AS。AS將獲得的匿名查詢結果加以過濾后發送給用戶，從而完成整個查詢過程。

3.2 基本概念

定義 1 3層系統架構的網絡實體可用三元組（User, AS, LSP）表示。其中，User代表當前網絡中存在的所有移動用戶，這些用戶可通過智能移動設備獲取位置服務，但其通信和計算能力有限；AS代表3層結構中的匿名服務器組，用來計算能夠生成相似軌跡的查詢位置，以此完成位置匿名，AS具有較強的計算和數據處理能力；LSP為不同的位置服務提供商，能夠完成User或AS提出的基于位置服務，同時能夠保存位置服務的歷史數據，其數據分析和處理的能力極強。

在本文中，假設AS是可信的，其部署數量能夠滿足當前所有User的隱私保護需求；而LSP是半可信的，在其服務的過程中，對用戶的位置隱私感興趣，但能夠按照協議完成服務，即LSP是好奇而非惡意的。

定義2 連續查詢服務是指User向LSP發起多次請求，該請求可表示為Q=(ID, Li, t, P)。其中，ID表示用戶的身份標識或假名；Li=(xi, yi)表示當前查詢所處的位置；t表示時間間隔；P表示查詢的興趣點，如餐廳、加油站等。

本文中User首先將Q發送給AS，由AS完成匿名位置計算后，生成滿足軌跡匿名的虛假用戶，將User與虛假用戶建立匿名組，AS將匿名組作為請求用戶發送給LSP。LSP在完成查詢后，將查詢結果返還給AS。AS在過濾掉虛假查詢結果后，將真實的查詢結果返還給User，完成當前查詢。

定義3 位置軌跡匿名是指LSP同時獲得包括真實用戶軌跡T在內的至少r條軌跡，這些軌跡使LSP無法通過軌跡長度和軌跡方向等相似性準確辨識出T的隱私保護過程。

本文中的軌跡由于是在連續查詢過程中產生的，因此與以往的軌跡匿名不同，需要對尚未完全生成的軌跡完成匿名操作，防止攻擊者實時獲取真實用戶的位置隱私。

3.3 攻擊手段

針對連續查詢的位置軌跡隱私，攻擊者主要采用假名關聯、內容關聯、時間間隔關聯和移動類型關聯等攻擊手段。假名關聯就是通過用戶在連續查詢過程中每個位置提交的假名信息，按照相同假名的連續關系，獲取連續查詢的位置，進而關聯分析出用戶的隱私信息；內容關聯是根據用戶所提交的查詢內容，針對每個查詢位置的相同查詢內容關聯具體的用戶；時間間隔關聯是針對連續查詢過程中，User所選擇的查詢時間間隔差異（如每隔2 min返回結果或每隔4 min返回查詢結果），獲取用戶的位置隱私；移動類型關聯（movement types correlation）是指攻擊者通過觀測等手段獲取待攻擊用戶的運動速度和運動方向，以此進行用戶比對，刻畫出用戶的行進軌跡，推測出用戶在后續查詢中所處的位置，進而達到對用戶位置隱私攻擊的目的。下面以假名關聯攻擊為例，通過如圖4所示的二分圖來刻畫這個攻擊過程。

用戶的假名經過泛化處理后存在如圖 4(a)所示的假名與位置的二分圖刻畫，任意一個假名都存在多個位置與之匹配，使攻擊者無法獲得真實用戶假名與位置之間的關聯。由于在連續查詢的過程，同一假名連續出現在可相互連接的位置上，由此攻擊者可以將假名與位置唯一匹配，獲得如圖4(b)所示的真實匹配二分圖刻畫。其他3種關聯攻擊與之相似。

圖4 假名關聯攻擊的二分圖刻畫

若要在這些關聯攻擊下保護用戶的位置隱私，當前主要的方法是模糊這些關聯關系。在二分圖中可表示為擾亂位置與假名、內容、時間間隔和移動類型之間的匹配關系。在實時的位置服務中，針對假名關聯，可以在每次查詢過程中進行假名的隨機更換；針對內容關聯，可以按照 l-多樣性的標準進行查詢興趣點泛化；針對查詢時間間隔關聯，可以通過選擇具有相同時間間隔的其他用戶，或選擇當前正在進行查詢的用戶進行泛化；而針對移動類型的關聯攻擊，則需要使用軌跡匿名的隱私保護技術。

已有的軌跡隱私保護方法主要基于歷史軌跡數據[15]或當前其他用戶產生的軌跡[16]，將這些與基軌跡混合完成匿名，但這些方法均存在一定的不足。前者需要AS具有較好的存儲能力，能保存大量的歷史軌跡數據；后者需要AS具有高速的篩選計算能力，能夠快速地在大量提交數據或候選數據中，查找相似的軌跡數據。因此，這些方法都不適合在連續查詢中進行位置軌跡匿名。基于這個問題，本文設計了一種實時相似軌跡生成方法，通過這種方法計算并找到能夠生成相似軌跡的查詢位置，在AS的協作下構建匿名組并實時完成軌跡匿名，保護連續查詢下的用戶位置隱私。

4 相似軌跡實時生成方法

為實現連續查詢過程中的實時軌跡相似，需要在3個不同階段對真實用戶的查詢信息加以處理。這3個階段分別為：初始位置匿名階段、相似軌跡位置生成階段和生成位置篩選階段。初始位置匿名主要通過AS生成滿足一定條件初始虛假位置，并與基用戶首次查詢的真實位置建立有效的匿名組，在滿足k-匿名的前提下發送給LSP。相似軌跡位置生成階段則要求AS根據初始匿名位置或連續查詢過程中的前次匿名位置，通過與基位置完成軌跡相似計算后，獲取滿足r-匿名的后續位置，并生成位于該位置的虛假用戶，建立覆蓋基用戶當前查詢位置的匿名組。在生成位置篩選階段，AS需要按照基用戶制定的軌跡相似度和軌跡夾角最大閾值，通過相似軌跡位置計算，得出4個不同的位置坐標，將這些坐標相互連接構成四邊形區域，在該區域內根據實際的地理信息情況，剔除掉真實用戶不可到達的位置，并選擇區域中剩余的任意位置生成虛假用戶，進而建立當前查詢的匿名組。

4.1 初始位置匿名階段

滿足軌跡匿名最好的結果，是找到連續查詢位置能夠生成長度相等、方向相同的位置軌跡。然而，由于實際路段等具體地理情況的影響，在生成的軌跡中可能會存在軌跡之間間隔較小的情況，本文稱這種軌跡為伴隨軌跡。伴隨軌跡可認為是相似軌跡中的一種特例，這種軌跡在發布的隱私保護中能達到較好的軌跡匿名效果，但在位置服務尤其是連續的位置查詢服務下，這種伴隨軌跡可能存在共同的查詢位置和興趣點，使攻擊者能夠根據任意其他軌跡獲得基用戶所在的最小區域，進而獲取其位置軌跡隱私。如圖5所示，3條匿名軌跡之間相距較近，虛線構成的方框代表相同查詢位置的最小區域。在連續匿名的過程中，3條軌跡均經過相近或相同的查詢位置，可以按照同一軌跡看待。此時若攻擊者獲知任一用戶的任一查詢位置，則可獲知基用戶的位置隱私。在本文所提方法中，后續階段使用軌跡方向最小閾值的限定，要消除這種伴隨軌跡帶來的隱患，需在初始位置匿名階段，擴大初始匿名虛假用戶與基用戶之間的間隔距離。因此，在初始位置匿名階段，需加入對用戶位置之間的距離限定，以防止后續匿名操作完成后產生軌跡伴隨現象，影響用戶的位置隱私。

4.2 相似軌跡位置生成階段

圖5 伴隨軌跡示意

相似軌跡位置是AS通過前次匿名中所有虛假用戶位置和當前用戶的基位置，按照軌跡相似的思想計算而來。在軌跡相似的思想中，認為 2條軌跡之間的距離越短，則軌跡越相似，這里借用Lee[8]關于相似軌跡區段計算的基本思想，以軌跡距離來量化兩軌跡之間的相似程度。其中，使用平行距離量化軌跡長度之間的差異、夾角距離量化軌跡方向之間的差異這兩者之和來量化軌跡相似程度。

假設用戶A和虛假用戶B分別以pa和pb為初始查詢位置建立匿名組，若要找到B的后續查詢位置pb+1，且連接用戶A、B的相鄰查詢位置能夠產生相似軌跡，需要通過pa、pb和A的后續查詢位置 pa+1使用平行距離和夾角距離建立方程，進而解出pb+1的位置坐標。令La和Lb分別以pa、pa+1和pb、pb+1為兩端位置的軌跡序列，θ表示用戶制定的2條軌跡之間存在的夾角閾值。由于 pa+1已知，通過式(3)、式(4)聯立建立關于pb+1的二元二次方程，從而獲取pb+1的位置坐標，并以該坐標生成虛假用戶B的后續查詢位置，建立連續查詢過程中的后續匿名組。其中，2條軌跡之間存在的相似程度可表示為

其中，0＜Sim(A,B)≤1，2個軌跡區段之間的軌跡距離可表示為

獲取相似軌跡后續位置計算所需要的平行距離和夾角距離公式可分別表示為

式(4)中的dot表示La和Lb的長度之積，軌跡距離計算中的 ω‖、ωθ分別代表平行距離和夾角距離的權重，分別表示用戶A、B在當前方向的移動距離，由于2個距離公式均對軌跡相似程度產生影響，因此其默認值均設定為 1。這種相似軌跡的計算方法按照平行距離和夾角距離的數值確定兩軌跡之間的相似性，可以看出，在完全相似和軌跡平行的情況下，能夠獲取最好的軌跡相似程度，此時匿名程度最好。對于上文的相似軌跡位置計算，可以用如下算法加以描述。

算法1 相似軌跡位置計算

輸入 用戶當前查詢位置 pi+1與前次查詢位置pi，以及生成虛假用戶前次查詢位置pj。

輸出 位置 pj+1集合，該集合中位置滿足軌跡匿名

程序 AS收到用戶提交的查詢請求Q;

算法1對每一個參與前次匿名的位置進行相似軌跡位置計算，所得結果保存在Ps中，連接2次鄰近查詢中的匿名位置，可獲得與真實用戶 2次查詢形成的基軌跡相似的其他r?1條軌跡。由于后續軌跡的生成數量就是首次匿名過程中的匿名用戶數量，此時軌跡數r與位置數k相等。此種情況下，生成的虛假軌跡在方向、長度等方面與用戶真實軌跡相似，攻擊者無法通過移動類型差異準確地在r條軌跡中識別出基軌跡，從而保護用戶的位置隱私。然而，算法1得出的位置是一種理想位置，在實際情況下可能會由于該位置的地理特性，使所生成的虛假位置與前次匿名的虛假位置之間不可連接，進而攻擊者通過位置的可到達性剔除匿名軌跡。針對這一問題，本文根據真實用戶制定的軌跡相似度和軌跡夾角最大閾值，計算獲得滿足最小軌跡相似度的位置區域，并在該區域內根據實際的地理信息情況，剔除用戶不可到達的位置。

4.3 生成位置篩選階段

為防止攻擊者通過真實環境的不可到達性，剔除生成的虛假位置，需要對計算獲取的軌跡相似位置進行篩選。相似軌跡位置區域是一個相似位置的集合，是在軌跡最大方向偏差Max_θ和最小相似度min_Sim(A,B)規定范圍內，通過軌跡相似位置計算生成獲得的4個位置連接后建立的四邊型區域。在這個區域內任一位置都滿足用戶規定的軌跡最小相似程度。由此，將前次查詢的匿名用戶位置與對應的該區域中任意位置相連接，生成的軌跡均滿足最低相似度。在該區域中選擇后續位置，需根據地圖上的實際地理差別和相近查詢位置的無障礙性予以選擇。假設匿名用戶U，經過相似軌跡位置計算后獲得如圖 6所示的由A、B、C這3個用戶所在位置組成的相似位置區域。由于用戶U與A所在位置之間存在建筑物阻擋，而用戶C所在的位置位于河流當中，根據實際可到達情況，AS只能選擇B作為當前匿名用戶的查詢位置，建立匿名組。

圖6 生成位置篩選示意

在進行生成位置篩選前，需要首先計算出相似軌跡位置區域。與完全相似軌跡位置計算的方法類似，需要在最大方向偏差Max_θ和最小相似性min_Sim(A,B)閾值的限定下，計算出該區域。對于軌跡相似性的判定，可以認為在可視范圍下無明顯差別即為相似。通過后續實驗觀測可以認定min_Sim(A,B)=0.9，而Max_θ=5是滿足軌跡相似情況下，可設定的最小相似程度和最大方向偏差。在算法2中將這2個閾值代入到位置計算中，完成對相似軌跡區域的計算，同時對計算獲得的位置進行篩選，進而獲得相似軌跡位置。

算法2 有篩選功能的相似軌跡位置計算

輸入 用戶當前查詢位置 pi+1與前次查詢位置pi以及其他虛假用戶前次查詢位置pj。

程序 AS收到用戶提交的查詢請求Q;

在算法2中對相似位置的求解方式與算法1相同，但由于相似程度和夾角距離限制，產生了二元二次方程的4個不同根，將這些根表示的位置節點連接即可獲得一個可產生相似軌跡的位置區域。在這個區域中的位置節點都可與前次查詢的位置結點連接建立相似軌跡，但該區域中的部分位置可能是不可到達的，篩選掉這些不可到達的位置后，在該區域中任選一位置，即可作為當前匿名位置組建新的匿名組。若所有位置均不可到達，則匿名失敗。

5 性能分析

本節主要針對所提出的相似軌跡實時生成方法，進行安全性和執行效率分析。

5.1 安全性分析

軌跡匿名方法的安全性取決于用戶設定的匿名閾值，本文將其與Hwang[15]提出的r-匿名觀點進行對比分析。r-匿名是指在位置服務的隱私保護數據中，其產生的軌跡數據至少存在r?1條相似的歷史軌跡，使攻擊者無法識別出基用戶的真實軌跡。本文中的方法是在連續查詢的過程中，通過對后續位置的計算，判定能夠與真實用戶產生相似軌跡的匿名位置，通過在該位置生成虛假用戶建立匿名組的方式，實現實時的軌跡匿名。這種實時匿名與以往的軌跡匿名方法相比，在AS提交位置給LSP之前實現軌跡匿名，使攻擊者無法通過實時軌跡差異獲取用戶隱私。若用戶在查詢過程中設定軌跡匿名閾值為 r，并通過該方法生成相似軌跡，則攻擊者在已知真實用戶移動類型的基礎上，通過軌跡方向和長度的差異，正確識別出基用戶軌跡的概率為

另外，在初始位置匿名階段，通過設定用戶間間隔距離，可降低生成的匿名相似軌跡出現伴隨軌跡的情況，阻止因生成軌跡存在伴隨情況導致隱私泄露。同時，根據位置軌跡匿名的實時性，需要考慮生成位置是否可達，本文對生成的相似軌跡位置進行了篩選，通過建立滿足最小相似度和最大軌跡夾角要求的位置區域，在滿足相似性的前提下，有效地阻止了攻擊者利用用戶不可到達性，識別潛在的真實位置攻擊行為。

在相似軌跡實時生成方法的運行過程中，由于使用生成虛假用戶的方式建立匿名組，其用戶假名、查詢內容和查詢時間間隔均與基用戶一致。所以，在滿足軌跡匿名、有效抵抗移動類型關聯攻擊的基礎上，對假名關聯、內容關聯和時間間隔關聯攻擊也存在較好的抵抗能力。可以認為，該方法能夠很好地解決以上4種關聯攻擊對位置隱私的威脅，保護用戶在連續查詢過程中的位置隱私。

5.2 效率分析

積極推動精神文明創建活動，培育和踐行社會主義核心價值觀，推動黃河文化體系建設，大力弘揚“團結、務實、開拓、拼搏、奉獻”的黃河精神。

由于相似軌跡實時生成方法主要應用在 AS端，查詢過程中基用戶只需提交自身的查詢，生成虛假查詢和基用戶信息是在AS與LSP之間傳遞，無需基用戶進行二次通信，因此基用戶所產生的通信量與單純查詢所產生的通信量相同。在AS與LSP之間，可以認為存在高速信息通道，滿足任何數量的通信需求。在整個連續查詢過程中所有對軌跡匿名的計算都是通過AS來完成的，大量的計算過程可能會導致AS出現瓶頸效應。因此，這里通過對相似軌跡位置計算的執行效率加以分析，以驗證執行效率，其運行結果在后面的實驗中進行詳細探討。

在考慮位置可到達性的情況下，為實現位置軌跡匿名，需要執行算法2來尋找匿名位置，從而建立匿名組。按照安全性分析中采用的r-匿名要求，需要每個連續查詢間隔中生成r條相似軌跡，以滿足軌跡r-匿名。假設在特定的連續查詢區域，每次匿名過程均生成可到達的虛假用戶，即在最好的情況下，算法2針對匿名閾值為r的匿名組進行相似軌跡位置計算，其時間復雜度為O(r?1)。針對獲取的相似軌跡進行生成位置篩選，其執行的時間復雜度同樣為O(r?1)，由此可得出進行軌跡匿名的虛假位置并建立匿名組整個過程的時間復雜度為O(sum)=O(r?1)+O(r?1)= 2O(r?1)= O(r?1)。

匿名過程中的最壞情況是所有計算獲得的位置均不可到達，此時算法2需計算相似軌跡位置區域，并在相似軌跡位置區域中尋找匿名位置并建立匿名組。算法2中相似軌跡位置計算的時間復雜度與最好條件下同為O(r?1)，而對參與匿名虛假用戶的查找需要在剔除不可到達位置之后隨機選取，此時的執行時間復雜度為2O(r?1)。若在計算后的相似軌跡位置區域并不真實可達，則可認為軌跡匿名失敗，此時無需計算算法的時間復雜度。由此得出，在最壞的情況下算法2執行的時間復雜度為O(sum)=O(r?1)+2O(r?1)= 3O(r?1)= O(r?1)。

綜上，可以認為，算法2的時間復雜度取決于用戶設定的軌跡匿名閾值和后續相似位置是否可達，由于本文所提出的相似軌跡實時生成方法是基于歐氏空間提出的，可以認為在多數情況下能夠找到可達位置上的匿名用戶。因此，在一般情況下，算法 2的時間復雜度位于最好情況與最壞情況之間，即算法 2的時間復雜度為O(r?1)。

6 實驗驗證

本節主要圍繞相似軌跡實時生成方法產生的軌跡相似程度，以及相似軌跡位置計算方法的執行效率2個方面，通過模擬數據集加以實驗分析，以驗證該方法的可行性。

6.1 環境配置

本實驗中所涉及的各種匿名方法是在Windows 7系統上使用Matlab 7來進行模擬的，運行環境為1.70 GHz Intel Core i5，內存大小為4 GB。實驗數據集采用Thomas Brinkhoff路網數據生成器生成的連續位置數據。表1為實驗中采用的相關參數閾值設定。

表1 實驗參數閾值設定

6.2 生成連續位置軌跡相似性對比

這里通過實驗獲取在連續5次查詢過程中，生成的位置軌跡與基軌跡之間的相似程度對比，來查看相似度閾值與夾角閾值對軌跡匿名所帶來的影響。實驗設定初始參與匿名用戶距離為1，用以避免在相似軌跡計算中形成伴隨軌跡。下面從相似度閾值和夾角閾值變換方面，查看虛假位置參與匿名后所形成軌跡與基軌跡之間的相似程度。

對于生成的相似軌跡，在5次連續查詢、匿名度r=2、生成4段相似軌跡的情況下，分別以min_Sim(A,B)=1，Max_θ=0、min_Sim(A,B)=0.9，Max_θ=0以及min_Sim(A,B)=0.9，Max_θ=5這3種情況運行算法2，獲得如圖7～圖9所示的生成相似軌跡，其中，初始位置距離設定為1。

圖7 相似性為1、夾角為0°時的軌跡對比

圖8 相似性為0.9、夾角為0°時的軌跡對比

圖9 相似性為0.9、夾角為5°時的軌跡對比

通過以上對比可以看出，單獨在相似度要求降低的情況下，生成的相似軌跡會由于隨機選擇的平行距離偏差，造成軌跡整體差異，但軌跡區段之間距離較遠使這種差異并不明顯。而在夾角度數變化的情況下，這種差異不僅體現在軌跡長度方面，更體現在方向偏移上。當查詢次數增加較多時，連續的同向夾角偏差將會加大軌跡偏移，使最后產生的軌跡與真實軌跡之間偏差增大。因此，在連續查詢次數較高的情況下，為保證生成軌跡的相似程度，需盡量選擇較小的軌跡夾角閾值，以免生成軌跡與基軌跡之間差異過大。

6.3 執行效率對比

在執行效率的對比實驗中，本文首先根據匿名參數的取值變化，查看在匿名參數逐漸增大的情況下，該方法與其他匿名方法之間在執行效率上的差異；然后，查看在連續多次執行過程中，在不同匿名值限定下的執行效率。為提高生成軌跡的真實程度，本文以 min_Sim(A,B)=0.9，Max_θ=5進行2次連續查詢，計算隨匿名值增加導致的時間變化情況。為檢測該方法與其他同類方法在執行效率上的差異，本文加入CLAPPINQ[14]、EGCA[19]和LTPPM[16]方法加以對比，其中，只有LTPPM與本文相似，主要針對移動類型關聯攻擊。

從圖10中可以看出，相似軌跡實時生成方法由于需要計算產生軌跡的相似性，因此與直接選擇用戶進行位置匿名的CLAPPINQ、EGCA相比執行效率較差，而CLAPPINQ由于采用預計算的方式，其位置選擇效率更高，但這2種方法均無法抵抗移動類型關聯攻擊。針對移動類型關聯攻擊的保護方法有LTPPM和本文所提方法，LTPPM通過用戶協作建立相似軌跡，這種方法涉及產生相似軌跡的位置計算，同時需要對匿名軌跡進行篩選，因此其時間效率隨匿名值變化較大。本文所提方法由于采用計算后續位置的方法，無需進行大量的軌跡篩選，與LTPPM 相比具有更好的執行效率。通過對比實驗可以看出，本文所提出的方法在執行效率上介于直接位置選取和軌跡判斷選取方法之間，在已有的基于實時軌跡匿名的隱私保護方法中效率較高。

圖10 U=60 000，k(r)值變化時各方法的執行效率

同樣在限定min_Sim(A,B)=0.9，Max_θ=5的情況下，本文以r=10進行連續重復的匿名操作，查看在連續運行過程中的執行效率變化，其中，使用的數據依舊采用Thomas Brinkhoff路網數據生成器生成。

從圖 11中可以看出，在匿名值固定的情況下，各方法進行連續隱私保護時，其執行時間隨重復次數的增加而增大。本文所提方法在計算出匿名的位置之后，需進行相似軌跡位置篩選，其時間效率要低于直接選擇用戶進行匿名的方法，但高于查找相似軌跡的隱私保護方法。

圖11 r=10時，隨重復計算次數變化的各方法的執行效率

從兩組實驗的對比中可以看出，本文所提出的相似軌跡實時生成方法盡管不如直接選擇用戶進行匿名的方法執行效率高，但是能夠模糊因移動類型差異導致的軌跡差異，進而保護在連續查詢過程中用戶的位置隱私，并且與選擇相似軌跡的方法相比，具有更好的執行效率，能夠滿足連續查詢過程中的實時軌跡隱私保護。因此，本文所提方法具有較好的應用前景。

7 結束語

本文針對LBS連續查詢過程中，攻擊者可通過位置軌跡差異獲取用戶隱私的情況，從軌跡的產生方式入手，通過對軌跡方向、軌跡長度的量化，引入軌跡相似性的計算思想，提出了一種相似軌跡實時生成方法。在這種方法下建立通過相似軌跡計算，獲取后續位置的實時位置計算方法，并通過相似軌跡位置篩選提高生成軌跡的相似程度。該方法能夠有效地防止攻擊者通過用戶移動類型獲取連續查詢過程中的用戶軌跡隱私。實驗表明，該方法在確保用戶位置隱私的同時具有很好的執行效率。當然，該方法也存在一定的不足，由于相似軌跡位置是通過解二元二次方程的方式獲得，其執行效率受AS計算能力影響較大。同時，該方法的提出主要基于歐氏空間，不能有效地部署在實際路網中。因此，在下一步的工作中，將對以上2個方面的問題加以分析和研究，尤其是加強在路網問題上的應用研究，使該方法具備更好的實際部署價值。

[1] GRUTESER M, GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking[C]//The 1st International Conference on Mobile Systems, Applications and Services, ACM. 2003: 31-42.

[2] BAMBA B, LIU L, PESTI P, et al. Supporting anonymous location queries in mobile environments with privacygrid[C]//The 17th International Conference on World Wide Web. 2008: 237-246.

[3] REBOLLO-MONEDERO D, FORNE J, SOLANAS A, et al. Private location-based information retrieval through user collaboration[J]. Computer Communications, 2010, 33(6): 762-774.

[4] YIU M L, JENSEN C S, MOLLER J, et al. Design and analysis of a ranking approach to private location-based services[J]. ACM Transactions on Database Systems, 2011, 36(2): 475-486.

[5] GHINITA G, KALNIS P, KHOSHGOZARAN A, et al. Private queries in location based services: anonymizers are not necessary[C]//The 2008 ACM Sigmod International Conference on Management of Data. 2008: 121-132.

[6] AGGARWAL G, FEDER T, KENTHAPADI K, et al. Anonymizing tables[M]. Berlin: Springer, 2005: 246-258.

[7] WONG R C W, LI J, FU A W C, et al. (α, k)-anonymity: an enhanced k-anonymity model for privacy preserving data publishing[C]//The 12th ACM Sigkdd International Conference on Knowledge Discovery and Data Mining. 2006: 754-759.

[8] LEE J G, HAN J, WHANG K Y. Trajectory clustering: a partition-and-group framework[C]//The 2007 ACM Sigmod International Conference on Management of Data. 2007: 593-604.

[9] XU Y, WANG K, FU A W C, et al. Anonymizing transaction databases for publication[C]//The 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2008: 767-775.

[10] ABUL O, BONCHI F, NANNI M, et al. Never walk alone: uncertainty for anonymity in moving objects databases[C]//The 24th IEEE International Conference on Data Engineering, Cancun. 2008: 376-385.

[11] BONCHI F. Privacy preserving publication of moving object data[M]//Privacy in Location-Based Applications. Berlin: Springer, 2009: 190-215.

[12] BONCHI F, LAKSHMANAN L V S, WANG H. Trajectory anonymity in publishing personal mobility data[J]. Sigkdd Explor Newsl, 2011, 13(1): 30-42.

[13] 潘曉, 郝興, 孟小峰. 基于位置服務中的連續查詢隱私保護研究[J]. 計算機研究與發展, 2010, 47(1): 121-129.

PAN X, HAO X, MENG X F. Privacy preserving towards continuous query in location-based services[J]. Journal of Computer Research and Development, 2010, 47(1):121-129.

[14] HASHEM T, KULIK L, ZHANG R. Countering overlapping rectangle privacy attack for moving KNN queries[J]. Information Systems, 2013, 38(3): 430-453.

[15] HWANG R H, HSUEH Y L, CHUNG H W. A novel time- obfuscated algorithm for trajectory privacy protection[J]. IEEE Transactions on Services Computing, 2014, 7(2): 126-139.

[16] GAO S, MA J F, SHI W S, et al. LTPPM: a location and trajectory privacy protection mechanism in participatory sensing[J]. Wireless Communications & Mobile Computing, 2015, 15(1): 155-169.

[17] WANG Y, HE L P, PENG J, et al. Privacy preserving for continuous query in location based services[C]//The IEEE 18th International Conference on Parallel and Distributed System (ICPADS). 2012: 213-220.

[18] SKOUMAS G, SKOUTAS D, VLACHAKI A. Efficient identification and approximation of k-nearest moving neighbors[C]//The 21st ACM Sigspatial International Conference on Advances in Geographic Information Systems. 2013: 264-273.

[19] WANG E K, YE Y. A new privacy-preserving scheme for continuous query in location-based social networking services[J]. The International Journal of Distributed Sensor Networks, 2014(1): 836-839.

[20] JIA J, ZHANG F. Nonexposure accurate location k-anonymity algorithm in LBS[J]. Scientific World Journal, 2014(1): 149-168.

[21] 張磊, 馬春光, 楊松濤. 基于位置關聯相似性的匿名算法[J]. 中國科技論文, 2016(2):197-201.

ZHANG L, MA C G, YANG S T. Anonymous algorithm based on position correlation similarity[J]. China Science and Technology, 2016 (2): 197-201.

[22] BERESFORD A R, STAJANO F. Location privacy in pervasive computing[J]. Pervasive Computing, 2003, 2(1): 46-55.

[23] FREUDIGER J, SHOKRI R, HUBAUX J P. On the optimal placement of mix zones[C]//The Privacy enhancing Technologies. 2009: 216-234.

[24] FREUDIGER J, RAYA M, FéLEGYHáZI M, et al. Mix-zones for location privacy in vehicular networks[C]//The 1st International Workshop on Wireless Networking for Intelligent Transportation Systems (Win-ITS). 2007.

[25] PALANISAMY B, LING L. MobiMix: protecting location privacy with mix-zones over road networks[C]//2011 IEEE 27th International Conference on Data Engineering (ICDE). 2011: 494-505.

[26] PALANISAMY B, LIU L, LEE K, et al. Anonymizing continuous queries with delay-tolerant mix-zones over road networks[J]. Distributed and Parallel Databases, 2014, 32(1): 91-118.

[27] 馬春光, 張磊, 楊松濤. 位置軌跡隱私保護綜述[J]. 信息網絡安全, 2015(10): 24-31.

MA C G, ZHANG L, YANG S T. Track location privacy protection review[J]. Information Network Security, 2015 (10): 24-31.

[28] 張磊, 馬春光, 楊松濤, 等. 基于輪廓泛化的位置隱私保護模型及方法[J]. 系統工程與電子技術, 2016,38(12): 2894-2900.

MA C G, ZHANG L, YANG S T, et al. Location privacy protection model and method based on contour generalization[J]. Journal of Systems Engineering, and Electronics, 2016,38(12): 2894-2900.

Trajectories anonymous algorithm for association attack

ZHANG Lei1,2, MA Chun-guang1, YANG Song-tao1,2, LI Zeng-peng1

(1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001,China; 2. College of Information and Electronic Technology, Jiamusi University, Jiamusi 154007, China)

During the location based service of continuous query, the trajectories which were produced by different movement types may reveal the privacy of user’s location. To solve this problem, a mechanism was proposed to put forward the real-time similar trajectories. With this mechanism, the subsequent position was calculated and which the dummy one was generated to establish an anonymous group, the demands of real-time trajectory anonymity were met, compensating the shortage of real-time trajectories of anonymity in other similar kinds of algorithm. Under this mechanism, a method for calculating subsequent anonymous position was proposed, which used the user's movement patterns, such as mobile direction, speed. The dummy trajectories were made very similar with the trajectory produced by the continuous query user. At the same time, the position of reachable difference in real areas was put forward, and on the basis of position reachable, this mechanism also filtrates out the unreachable candidate locations which had been calculated in the phase of dummy position generates, then decrease the probability of adversary identifies the real trajectory from the location of unreachable. Experimental results show that this method is effective for protecting the location privacy of continuous query user, and provides a good working efficiency.

privacy protection, continuous query, trajectory anonymous, similar trajectories

s: The National Natural Science Foundation of China (No.61472097), Specialized Research Fund for the Doctoral Program of Higher Education (No.20132304110017), The Natural Science Foundation of Heilongjiang Province (No.F2015022)

TP311

A

10.11959/j.issn.2096-109x.2017.00130

張磊（1982-），男，黑龍江綏化人，哈爾濱工程大學博士生，佳木斯大學講師，主要研究方向為信息安全、隱私保護。

馬春光（1974-），男，黑龍江雙城人，博士，哈爾濱工程大學教授、博士生導師，主要研究方向為密碼學、數據安全與隱私保護、無線自組織網絡及安全。

楊松濤（1972-），男，黑龍江鶴崗人，博士，佳木斯大學教授，主要研究方向為信息安全、隱私保護。

李增鵬（1989-），男，山東青島人，哈爾濱工程大學博士生，主要研究方向為密碼學、密碼協議。

2016-11-08；

2017-02-29。通信作者：馬春光，machunguang @ hrbeu.edu.cn

國家自然科學基金資助項目（No.61472097）；高等學校博士學科點專項科研基金資助項目（No.20132304110017）；黑龍江省自然科學基金項目（No.F2015022）