一種基于K匿名技術在軌跡隱私保護方法中的改進

張家磊 鐘伯成 房保綱 丁佳蓉 賈媛媛

摘 要：針對K匿名技術在軌跡隱私保護中存在搜索k-1個匿名用戶耗時過長、甚至搜索不到和易于被連續查詢攻擊所侵襲的現狀，提出了一種改進的方法，方法利用時間截點對搜索時間進行約束，生成假名對用戶發送查詢請求時的真名進行保護，有效解決了上述問題。實驗結果表明該方法的系統運行時間較短且隱私保護程度較高。

關鍵詞： K匿名技術;軌跡隱私;時間截點;假名

【Abstract】 Aiming at the existence of K-anonymity technology in the trajectory privacy protection， the search for k-1 anonymous users is too long， even unsearchable and easy to be attacked by continuous query attacks. An improved method is proposed， which uses time interception pairs. The search time is constrained， and the pseudonym is generated to protect the real name when the user sends the query request. The experimental results show that the system has a shorter running time and a higher degree of privacy protection.

【Key words】 ?K-anonymity technology; trajectory privacy; time cut-off point; kana

0 引 言

隨著智能設備的廣泛普及，越來越多的用戶開始使用基于位置的服務（Location Based Service，LBS）[1]，例如通過騰訊地圖、高德地圖等軟件查詢附近感興趣的地點（酒店、超市、美食）。通過LBS服務，用戶可以得到一條到達目的地路程最短的軌跡，大大方便了用戶的出行需求。只是，一旦用戶的軌跡信息被敵手所捕獲，用戶的家庭住址、工作地址、經常出入的場所等等個人隱私信息也都面臨著泄露的風險，所以如何保護LBS服務中用戶的軌跡信息已然成為學界的研究熱點。

針對LBS服務中用戶的軌跡隱私安全，目前的軌跡隱私保護技術主要有3種[2]：假軌跡法、泛化法、抑制法。這3種方法各有優缺點。其中，假軌跡法通過添加假軌跡來對用戶的真實軌跡進行干擾，起著混淆敵手的作用，從而達到保護效果。這種方法計算簡單，并且計算量相對較小，但是會降低數據的可用性。泛化法對軌跡上的點泛化為相應的匿名區進行保護，從而不能精確地定義用戶位置[3-4]，這種方法采用的都是真實數據，但是其計算量太大。抑制法就是通過不對外發布軌跡上用戶敏感位置或頻繁訪問位置的方式來保護用戶的軌跡隱私安全，這種方法在實現上較為簡單，但是容易造成用戶數據的丟失。

近年來通過研究發現，基于泛化法的軌跡K匿名[5]技術在用戶的隱私保護程度和數據的可用性上取得了一個較好的平衡，是目前軌跡隱私保護中較為常用的方法。其基本思想是：在真實用戶周圍尋找k-1個其它用戶的匿名框，并發送給LBS服務器進行查詢，這樣就能產生出混淆效果，使敵手無法辨別出真實用戶，從而達到保護用戶軌跡隱私的目的。但是傳統K匿名技術在連續查詢攻擊下，敵手可以根據匿名區內一直存在的用戶來推斷出查詢用戶。例如，用戶在3個不同時刻的匿名集分別為{S、A、B、C、D}、{S、A、B、E、F}、{S、G、H、L、J}，那么敵手就能通過對這3個連續的匿名集作分析得到真實的用戶為S。而且在人群比較稀少的區域，k-1個匿名用戶可能面臨較大搜索難度，甚至搜索失敗的情況。

針對上述問題，本文基于傳統的K匿名技術做出了改進，提出了一種新的軌跡隱私保護方案。本文的主要貢獻如下：

（1）提出一個時間截點T，在一定時間截點T內如果搜索不到k-1個匿名用戶，則產生虛假位置來代替剩下難以搜索到的匿名用戶，這樣就大大節省了計算開銷，也防止了在人群稀少的區域無法尋找到k-1個匿名用戶的情況。

（2）每次向LBS發送服務請求時，第三方匿名服務器生成不同假名代替真實用戶發送給LBS服務器進行查詢操作，有效地防止了連續查詢攻擊。

1 系統模型及相關定義

1.1 系統模型

由于軌跡隱私保護方案需要大量的計算資源，讓資源有限的移動設備承擔所有的計算開銷顯然不可能，因此本文采用第三方可信匿名服務器的系統模型，該系統模型包括用戶、第三方可信匿名服務器和LBS服務器三個組成部分。系統結構如圖1所示。由圖1可知，用戶是指攜帶具有無線定位、無線通信功能的移動智能設備，并向服務器連續發送請求的人們。第三方可信匿名服務器建立在可信的服務平臺上，主要由歷史數據庫、匿名模塊和結果處理模塊組成。歷史數據庫保存用戶的歷史軌跡和請求概率;匿名模塊對用戶發送過來的位置和查詢信息進行模糊化操作，根據用戶的隱私保護需求將用戶的真實位置混淆在匿名區域內一起發送給LBS服務器進行查詢;數據處理模塊負責對LBS發送過來的查詢結果進行精確計算，將用戶的查詢結果篩選出來返回給用戶。LBS服務器能夠利用數據庫為用戶搜索到用戶感興趣的點，例如，用戶附近的酒店、電影院等。

2 假軌跡生成算法

2.1 算法思路

算法開始時，用戶首先設置隱私保護參數（β，D，θ，T，k），第三方可信匿名服務器根據用戶的位置和隱私保護參數在用戶的位置周圍尋找k-1個與查詢用戶的請求概率相差小于β匿名用戶，如果在時間T內沒有尋找到，則產生假位置來代替剩下難以尋找到的匿名用戶，同時將生成一個假名代替查詢用戶向LBS服務器發送查詢請求。在接下來的查詢時刻，第三方可信匿名服務器繼續按初始位置的規則生成假位置，只是不同時刻生成的假名要求不同，并且需要按照距離偏差、軌跡局部角度偏差兩個約束，對匿名用戶的位置或生成的假位置進行一定的約束，直到生成滿足條件的k-1條假軌跡。

2.2 算法步驟

輸入：用戶的位置，查詢請求，隱私保護參數：β，D，θ，T，k

輸出：假軌跡集

Step 1 在查詢用戶的初始位置搜索與查詢用戶請求概率差值小于β的k-1個匿名用戶，如果時間T內仍搜索不到，則產生假位置代替剩下n個難以搜索到的匿名用戶。

Step 2 第三方可信匿名服務隨機生成一個假名代替查詢用戶向LBS發送這條查詢信息。

Step 3 當用戶開始移動、即用戶不在初始位置時，將重復Step 1～Step 2的操作過程。

Step 4 計算2個匿名區域內各位置點之間的歐式距離和與真實軌跡片段之間的角度偏差，把滿足這2個約束條件的位置點連接起來生成假軌跡片段。

Step 5 重復Step 3～Step 4，直到在原來的軌跡片段上產生滿足要求的k-1條完整的假軌跡。

3 實驗結果分析

本次實驗中的數據集是由Thomas Brinkhoff移動對象生成器基于德國古登堡市的地圖生成的。本實驗所有的代碼都是由Java編寫的，實驗環境為Windows 10操作系統，內存空間8 GB，其處理器為英特爾 Core i7-7700HQ。編程環境為MyEclipse10。實驗中的參數設置為：β=0.2，D=50 m，θ=15°，T=0.5 s。

3.1 連續查詢攻擊分析

敵手通過分析不同時刻匿名區域內重復出現的匿名用戶，就能得到真實的查詢用戶，但是本方案在不同時刻利用假名來代替真實用戶，使真實用戶不會出現在各個時間點的匿名區域內，從而有效防止了連續查詢攻擊。例如，在傳統的K匿名算法中用戶在3個不同時刻的匿名集分別為{S、A、B、C、D}、{S、A、B、E、F}、{S、G、H、L、J}，敵手可以對這3個匿名集做交集就能得到真實的查詢用戶S，但是在本文提出的算法中，第三方匿名服務器在這3個時刻隨機提供3個不同假名V、M、Z來代替真實的查詢用戶S向LBS服務器發送查詢請求，從而有效避免了連續查詢攻擊。

3.2 運行時間分析

研究可得，不同算法下的系統運行時間的對比繪制結果如圖2所示。由圖2可以看出，隨著匿名區域內數量k的增加，本文算法和傳統的K匿名算法的系統運行時間都在增加。但是在k>15以后，本文算法的系統運行時間明顯優于傳統的K匿名算法，這是因為當需要搜索的匿名用戶數量k達到一定數量時，會擴大服務器的搜索范圍，增加了計算開銷，從而系統的運行時間也會相應地增加。

3.3 隱私保護程度分析

對2種算法在隱私保護程度上進行了對比，對比結果如圖3所示。由圖3可以看出，本文算法在隱私保護程度上優于傳統的K匿名方法，且保護程度較高。

4 結束語

本文針對傳統的K匿名技術在軌跡隱私保護中的不足，提出了一種改進方法，利用時間截點和假名有效解決了傳統K匿名技術人群較少的區域計算開銷過大和不能防止連續查詢攻擊的問題。實驗表明，本文提出的方法安全程度更高，系統運行時間更少。

參考文獻

[1]張少波， 王國軍， 劉琴，等.基于多匿名器的軌跡隱私保護方法[J]. 計算機研究與發展， 2019， 56（3）：576-584.

[2]霍崢， 孟小峰， 黃毅. PrivateCheckIn：一種移動社交網絡中的軌跡隱私保護方法[J]. 計算機學報， 2013， 36（4）：716-726.

[3]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.

[4]楊靜， 張冰， 張健沛，等. 基于圖劃分的個性化軌跡隱私保護方法[J]. 通信學報， 2015，36（3）：1-11.

[5]胡德敏， 鄭霞. 基于連續查詢的用戶軌跡k-匿名隱私保護算法[J]. 計算機應用研究， 2017， 34（11）：3421-3423，3427.