一種安全高效的軌跡隱私保護方案

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

(上海工程技術大學 電子電氣工程學院,上海 201620)

0 引 言

全球定位技術、無線通信技術和移動設備的的飛速發(fā)展,基于位置的服務(location-based-service,LBS)[1]獲得了廣泛的關注和使用,LBS服務給人們的生活帶來了極大的便利。例如,用戶在一個完全的陌生的環(huán)境下,可以利用位置服務可以迅速導航[2]到附近感興趣的場所(醫(yī)院、商場、酒店等)。但是,用戶在享受LBS帶來便利的同時,也面臨著一系列的安全隱私問題,例如,攻擊者可以針對軌跡數(shù)據(jù)進行推理,就可能得到用戶的個人的興趣愛好、生活習慣、行為模式等相關隱私信息。因此,如何確保在用戶能獲得高質量位置服務的同時,保護用戶的隱私信息不被泄露成為LBS的關鍵所在。

目前,經(jīng)過國內(nèi)外學者的不懈努力,已經(jīng)提出了許多的隱私保護方法,主要可分為三類[3]：假軌跡法、泛化法、抑制法。與泛化法和抑制法相比,假軌跡法能更好地保留用戶完整的軌跡信息,因此在用戶的軌跡隱私保護中應用廣泛。

1 相關工作

對于移動智能終端的軌跡隱私保護[4]問題,學術界提出了大量的解決方法。Kido H等人[5]提出了兩種方法來保護用戶的軌跡隱私。在方案一中用戶決定假軌跡的起點和終點,然后算法利用這兩點隨機生成與用戶軌跡相似的假軌跡,在方案二中通過旋轉用戶的真實軌跡來生成假軌跡。但這兩種方法都有可能讓敵手利用背景知識進行攻擊。Hua L等人[6]提出了一種基于假位置的軌跡隱私保護方法,當用戶發(fā)出查詢請求時,直接將自己的真實位置和假位置發(fā)送給LBS服務器,最后用戶終端自己對服務器發(fā)送回來的模糊查詢出結果進行精確導航。這種方案忽略了背景知識攻擊且對用戶終端設備的要求較高。Pingley A等人[7]提出了一種新的保護機制,該機制通過構造虛假的查詢內(nèi)容和用戶運動模型實現(xiàn)對查詢內(nèi)容的k匿名,但是該方案沒有考慮到敵手已知的背景信息。Zhang S等人[8]提出了一種基于代理轉發(fā)機制的方法來保護用戶的軌跡隱私,該方法通過可信的服務器尋找與向LBS發(fā)送請求的用戶最匹配用戶作代理,然后由代理向服務器轉發(fā)用戶的查詢請求,從而隱藏了用戶的軌跡與服務器之間的聯(lián)系,實現(xiàn)了用戶軌跡隱私的保護。然而,該方案容易讓敵手通過背景知識區(qū)分出不合理的代理,從而識別出用戶的真實軌跡。軌跡k匿名[9,10]將真實軌跡藏匿于其他虛假軌跡或者歷史軌跡中來混淆敵手,實現(xiàn)軌跡的k匿名,從而起到用戶軌跡隱私保護的目的。然而這種軌跡k匿名的方法大多忽略了背景信息攻擊。

盡管上述方法在用戶的軌跡隱私上保護上取得了一定的效果,但是都存在著某種不足,本文在充分考慮背景信息的前提下,設計了一種基于可信第三方的假軌跡隱私保護算法,大大提高了用戶軌跡隱私的保護程度。

2 隱私保護模型

2.1 系統(tǒng)結構

本文提出的假軌跡算法采用基于第三方可信中心服務器的系統(tǒng)結構。用戶通過移動終端將自己的位置信息和隱私保護參數(shù)一起發(fā)送給第三方可信中心服務器,第三方可信服務器接收到之后,將這些數(shù)據(jù)經(jīng)過軌跡算法進行加密再發(fā)送給LBS服務器,LBS服務器將查詢的結果發(fā)送給中心服務器進行求精,最后中心服務器將精確后的結果發(fā)送給用戶。

2.2 隱私保護度量標準

一個良好的隱私保護模型應該能很好地保護用戶的軌跡隱私安全,為了衡量隱私保護模型的安全程度,本文提出了三個度量標準：

1)請求概率pi(衡量生成的假位置的合理性)

用戶在某一位置或區(qū)域向服務器發(fā)送請求的概率。假設把地圖分成了n×n個網(wǎng)格,用戶在每網(wǎng)格i中向服務器發(fā)送請求的概率表示為

2)距離偏差DD(判斷相鄰兩個位置在時間上是否可達)

3)軌跡方向相似度δ(真假軌跡方向的相似程度)

3 假軌跡生成算法

3.1 虛假軌跡生成的準則

生成虛假位置時,生成的虛假位置需要滿足以下準則：

1)近臨原則：生成的虛假位置不能離用戶的真實位置太近或者太遠,當虛假位置離用戶的真實位置太近時,可能就會暴露真實用戶的真實軌跡,而當虛假位置離用戶的真實位置太遠時,就可能起不到對真實位置良好的保護效果。為了避免這種狀況的發(fā)生,本文以真實位置為圓心,生成一個圓環(huán),在這個圓環(huán)內(nèi)生成虛假位置,如圖1所示。

圖1 虛假位置生成區(qū)域

2)相似原則：假位置不能隨意生成,因為把各個假位置連接起來所生成的假軌跡要和用戶的真實軌跡有一定的相似性,這樣才能更好的保護用戶的軌跡隱私。相似性體現(xiàn)在所生成的假軌跡要和用戶的真實軌跡在速度和方向上有一定的相似程度。本文用距離偏差來衡量假軌跡與用戶真實軌跡在速度上的相似性,用軌跡相似度來衡量在方向上的相似性。

3.2 假軌跡生成算法

當用戶提出位置服務請求時,需根據(jù)自身的要求設置相應的匿名度。匿名度主要包括4個方面：1)假位置生成所在的匿名區(qū)域(Smin,Smax),Smin表示假位置距離用戶位置的最近距離,Smax表示假位置距離用戶的最遠距離；2)衡量真假軌跡相同時刻位置點提出服務請求概率的偏差程度的參數(shù)α；3)軌跡相似度δ；4)假軌跡的數(shù)量k。

假軌跡的生成的具體步驟如下：

第一階段：t=0時即初始時刻生成用戶起點位置的假位置,此時生成的假位置只需要滿足假位置的距離和請求概率這兩個約束。

1)U0=(x0,y0)//t=0時用戶的真實位置

5)if(d0∈(Smin,Smax))

6)else then goto step2

重復步驟(2)～步驟(7),直到生成的假位置的數(shù)量滿足要求為止。

第二階段：t≥時假位置的生成,此時假位置的生成不僅要考慮第一階段的兩個約束條件,還需要考慮生成的軌跡滿足DD,δ的要求。

8)U1(x1,y1)//t1時刻用戶的真實位置

12)計算DD1,δ1的值

15)重復上述步驟,直到生成的假位置滿足這幾個約束條件和要求的生成個數(shù)為止

16)t=i(i=1,2,3,4,…,n)時重復上述的步驟,直到生成假位置滿足條件為止。

4 實驗與分析

本文關于數(shù)據(jù)集的搜集采用的是Thomas Brinkhoff移動對象生成器基于德國古登堡市的地圖生成的。本實驗所有的代碼都是由Java編寫的,實驗環(huán)境為Windows 10操作系統(tǒng),內(nèi)存空間8 GB,其處理器為英特爾 Core i7—7700HQ。編程環(huán)境為MyEclipse10。

為了驗證算法的有效性,將用戶所在的區(qū)域劃分成了100×100個網(wǎng)格,并將本文提出的算法與隨機生成假軌跡算法進行了對比。實驗中各項參數(shù)設置為：(Smin,Smax)=(150 m,250 m),DD=80 m,α=0.3,δ=0.05。

4.1 關于背景知識攻擊的分析

敵手在知道用戶的交通工具的情況下,通過判斷相鄰兩個位置在時間上是否可達或者通過比較相同時刻不同軌跡上位置的發(fā)送查詢請求的概率是否差異過大,從而通過某個位置點的不合理性,來排除掉假軌跡。然而本文利用請求概率、距離偏差、軌跡相似度對生成的假軌跡進行嚴格的約束,使之在單點位置上更具合理性,并且假軌跡的相似度更高,對敵手的背景知識攻擊起到了很好的抵抗效果。

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

假軌跡方向相似于用戶真實軌跡的程度,在一定的程度上反映了用戶的軌跡隱私的安全程度,相似程度越高敵手就越難識別出用戶的真實軌跡。如圖2(a)所示,可以看出本文生成的假軌跡集合的相似度隨著k的增加幾乎保持不變,且相似度δ比較低。說明本文提出的算法能夠較好地防止敵手從軌跡的方向入手,排除掉用戶的假軌跡。

4.3 軌跡數(shù)量k對方案運行時間的影響

本文簡要分析了軌跡的數(shù)量對方案運行的時間的影響。實驗結果如圖2(b)所示,可以看出隨著假軌跡數(shù)量k的增加,系統(tǒng)的運行時間也會隨著增加。但是與隨機生成算法,本文提出的算法在計算開銷上優(yōu)于隨機生成算法,系統(tǒng)運行時間較少。

圖2 兩種算法的性能分析

5 結束語

針對位置服務中用戶軌跡隱私的保護問題,本文提出了一種安全高效的假軌跡方法,在生成假軌跡時,不僅考慮了用戶的速度和方向問題,還考慮了用戶附近假位置的請求概率問題。與傳統(tǒng)的隨機生成法相比,本文所提方法生成的假軌跡與用戶的真實軌跡的方向相似度更高,系統(tǒng)運行時間較少,而且還能抵抗敵手的背景知識攻擊,保護效果更好。