一種基于K匿名技術(shù)在軌跡隱私保護(hù)方法中的改進(jìn)

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

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

關(guān)鍵詞： K匿名技術(shù);軌跡隱私;時間截點;假名

【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 引 言

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

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

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

針對上述問題，本文基于傳統(tǒng)的K匿名技術(shù)做出了改進(jìn)，提出了一種新的軌跡隱私保護(hù)方案。本文的主要貢獻(xiàn)如下：

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

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

1 系統(tǒng)模型及相關(guān)定義

1.1 系統(tǒng)模型

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

2 假軌跡生成算法

2.1 算法思路

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

2.2 算法步驟

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

輸出：假軌跡集

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

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

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

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

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

3 實驗結(jié)果分析

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

3.1 連續(xù)查詢攻擊分析

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

3.2 運行時間分析

研究可得，不同算法下的系統(tǒng)運行時間的對比繪制結(jié)果如圖2所示。由圖2可以看出，隨著匿名區(qū)域內(nèi)數(shù)量k的增加，本文算法和傳統(tǒng)的K匿名算法的系統(tǒng)運行時間都在增加。但是在k>15以后，本文算法的系統(tǒng)運行時間明顯優(yōu)于傳統(tǒng)的K匿名算法，這是因為當(dāng)需要搜索的匿名用戶數(shù)量k達(dá)到一定數(shù)量時，會擴(kuò)大服務(wù)器的搜索范圍，增加了計算開銷，從而系統(tǒng)的運行時間也會相應(yīng)地增加。

3.3 隱私保護(hù)程度分析

對2種算法在隱私保護(hù)程度上進(jìn)行了對比，對比結(jié)果如圖3所示。由圖3可以看出，本文算法在隱私保護(hù)程度上優(yōu)于傳統(tǒng)的K匿名方法，且保護(hù)程度較高。

4 結(jié)束語

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

參考文獻(xiàn)

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

[2]霍崢， 孟小峰， 黃毅. PrivateCheckIn：一種移動社交網(wǎng)絡(luò)中的軌跡隱私保護(hù)方法[J]. 計算機(jī)學(xué)報， 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]楊靜， 張冰， 張健沛，等. 基于圖劃分的個性化軌跡隱私保護(hù)方法[J]. 通信學(xué)報， 2015，36（3）：1-11.

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