現(xiàn)實環(huán)境中基于虛擬用戶的LBS位置隱匿方法*

陳 思，趙 明，張錦健

(中南大學(xué)軟件學(xué)院，湖南 長沙410075)

1 引言

全球定位系統(tǒng)GPS(Global Positioning System)精度和性能的不斷提高，推動了基于位置服務(wù)LBS(Location-Based Service)應(yīng)用程序的發(fā)展，給人們的生活提供了許多便利。然而，位置信息共享如果被人惡意利用，則會帶來一系列的問題(比如頻繁出入的場所和常規(guī)的出行路線，可能暴露用戶的身份和家庭住址)，這讓針對個人的跟蹤及詐騙難度降低。根據(jù)Busic等[1]調(diào)查，大量商業(yè)的LBS要求用戶每隔幾分鐘更新一次當(dāng)前位置。這種收集用戶位置的系統(tǒng)，不僅潛在地侵犯了用戶位置隱私，并且存在泄露用戶位置信息的巨大隱患，最終嚴(yán)重影響用戶體驗及位置服務(wù)的發(fā)展。

為了保護(hù)用戶的位置隱私，眾多學(xué)者針對這一問題進(jìn)行研究，目前已提出了大量可行的方法。其中，基于泛化的技術(shù)[2]提供了一個很好的解決方案：通過把用戶的位置與其他k個用戶的位置混合，使真實用戶位置被確定的概率小于或等于1/k。然而，這種方法需要一個第三方服務(wù)器來承擔(dān)用戶和LBS提供者之間的相互作用。實際上，部署一個絕對安全的第三方服務(wù)器難度極大，而且，如果沒有足夠數(shù)量的用戶，這種方法也不可行。

針對車輛密度較低的區(qū)域，基于模糊的技術(shù)從很大程度上保護(hù)了個人位置隱私，尤其是替換位置對泛化位置的補(bǔ)充。Hong等[3]提出了利用圓形區(qū)域代替用戶真實位置的模糊法。但是，這種模糊技術(shù)不能對LBS返回結(jié)果進(jìn)行處理，往往產(chǎn)生較粗糙的LBS結(jié)果，無法滿足用戶需求。

基于掩蓋法的技術(shù)指在特定或全部場景下，用戶通過不對外發(fā)布位置來達(dá)到保護(hù)位置隱私的目的。文獻(xiàn)[4]是最為典型的代表。但是，Mix zones位置往往相對固定，且覆蓋區(qū)的大小和隱私的強(qiáng)弱往往很難權(quán)衡。

綜合以往研究，基于虛擬用戶的方法是滿足上述要求的有效途徑[5 - 7]。該方法不必依賴于受信任的服務(wù)器，也不必收集周邊用戶的位置信息，系統(tǒng)可以自行生成虛擬用戶并將自己位置連同虛擬用戶位置一并發(fā)送給LBS提供商，使LBS提供商無法確定真實用戶的位置。但是，過去基于虛擬用戶的保護(hù)方法并沒有考慮現(xiàn)實環(huán)境中的物理約束，實際隱私保護(hù)的魯棒性值得商榷。因為基于虛擬用戶隱私保護(hù)方法的魯棒性強(qiáng)弱程度是依靠虛擬用戶的行為是否自然而決定的，如圖1所示。

Figure 1 Moving trajectories of user and dummies圖1 真實用戶與虛擬用戶的移動軌跡

在圖1中，實線表示真實用戶的移動軌跡(記為T)，虛線軌跡為虛擬用戶(記為d1和d2)。由于真實用戶通常表現(xiàn)出一定的社會移動行為，所以構(gòu)造逼真的虛擬用戶運動對保護(hù)位置隱私極為重要。如圖1a所示，如果在同一時間，攻擊者收集到同一用戶的三條運動軌跡，真實軌跡T將被識別的概率為100%，因為d1和d2顯然不符合人們?nèi)粘Ｐ袆右?guī)律。因此，生成難以被攻擊者輕松辨別且符合現(xiàn)實環(huán)境的虛擬用戶至關(guān)重要，如圖1b所示。

另外，真實環(huán)境中，軌跡的可溯性也是一個關(guān)鍵性因素。假設(shè)，一個用戶頻繁地請求LBS，則他發(fā)送的位置數(shù)據(jù)將構(gòu)造一條清晰的運動軌跡，然而這樣的運動軌跡容易泄露用戶的位置隱私。因為一旦用戶某一時刻的位置意外地被攻擊者通過特殊的手段檢測到，該用戶以前全部的(也可能是未來的)位置將變得明顯，即用戶的運動軌跡是可溯的，如圖2a所示。

Figure 2 Traceability圖2 可追溯性

為了降低可溯性，一個簡單而有效的方法就是將虛擬用戶和真實用戶的軌跡進(jìn)行交叉。因為交叉的軌跡讓攻擊者無法準(zhǔn)確地獲取用戶過去的位置。如圖2b所示，假設(shè)有兩條軌跡，即使攻擊者獲取了某一時刻的一個位置，但由于軌跡的交叉，他是無法確定用戶的起始位置是m1還是m2。

針對上述問題，本文提出一種Dummy-Ex方法，創(chuàng)新點是利用交叉來保護(hù)用戶的隱私。其余部分組織如下：第2節(jié)介紹概念與動機(jī)；第3節(jié)說明方案構(gòu)造；第4節(jié)就提出的方法進(jìn)行實驗評估；第5節(jié)進(jìn)行總結(jié)以及對未來工作進(jìn)行展望。

2 概念與動機(jī)

2.1 基本概念

(1)最小覆蓋區(qū)：由Lu等[6]所提出，隱匿面積定義為一次LBS請求中覆蓋所有用戶的最小面積。位置的隱匿性與最小覆蓋面積有很強(qiáng)的關(guān)聯(lián)。比如圖3a中所描述的隱匿性相對圖3b更弱，因為覆蓋區(qū)域過小，攻擊者則不需要猜測用戶的真實位置，他可以直接定位到一個非常小的區(qū)域，如某棟樓房。最小覆蓋區(qū)的提出是為了限制最小的隱形覆蓋區(qū)的面積，因為用戶在每個快照中需構(gòu)建一個覆蓋其它k-1個虛擬用戶的隱形區(qū)域，用于混淆LBS提供商。

Figure 3 Anonymous area圖3 隱形覆蓋區(qū)面積

(2)位置可達(dá)性：對于當(dāng)前的位置在任何一條真實或虛擬的路徑中，依據(jù)用戶當(dāng)前的最大速度，在單位時間內(nèi)的下一個位置應(yīng)是可到達(dá)的。例如，用戶請求LBS，在一定時間后(如3 min)再次請求服務(wù)，如果兩次定位距離超過20 km，那么這個用戶顯然是虛擬的。因此，本文采用限制條件規(guī)范虛擬用戶的運動，讓每個虛擬用戶單位時間內(nèi)的位置在一個可到達(dá)的區(qū)域。

2.2 基本思想

本文所用相關(guān)符號的含義如表1所示。

Table 1 Symbol references表1 符號引用表

Figure 4 Basic plan圖4 本文基本方案

3 Dummy-Ex方案構(gòu)造

3.1 虛擬用戶的運動控制

用戶連續(xù)請求LBS，為了達(dá)到隱私要求，需首先確定每個虛擬用戶的目的地。因為，隨機(jī)選擇虛擬用戶的路由，有可能造成圖2a的位置泄露。為了降低可溯性，選擇虛擬用戶目的地時，本文將對真實路由與虛擬路由實施交叉，這對保持用戶與虛擬用戶的行為一致性來說至關(guān)重要。

在路徑混淆上，本方案將對路由的交叉調(diào)用評估和選擇。若虛擬用戶在真實用戶之后交叉，會導(dǎo)致真實用戶位置過于突出，如圖5所示。長此以往，LBS提供商將會注意到，有一個用戶遙遙領(lǐng)先于其他用戶，這將增加真實用戶被識別的可能性。為了避免這種情況的發(fā)生，本文方法在構(gòu)建用戶路由時，分為以下兩種情況：

情況1用戶前面的虛擬用戶數(shù)量超過總數(shù)的一半時，可隨機(jī)選擇虛擬用戶調(diào)用交叉。

情況2用戶前面的虛擬用戶數(shù)量小于總數(shù)的一半，則不調(diào)用交叉。

Figure 5 Crossing after real user圖5 虛擬用戶在真實用戶之后調(diào)用交叉

3.2 虛擬用戶生成算法(DLG)

本文所提出的虛擬用戶生成算法(DLG)是在用戶設(shè)置的匿名區(qū)域內(nèi)，生成滿足用戶隱私需求的虛擬用戶，如圖6所示。基本思想是：首先，用戶根據(jù)需求定義一個最小的隱形區(qū)域Amin和參數(shù)δi。其中對應(yīng)隱形區(qū)域的最小半徑為：

(1)

Figure 6 Dummy locations generating algorithm圖6 虛擬用戶位置生成算法

(2)

|δi-1|=εi

(3)

其中，εi是一個很小的正數(shù)(如0.05或者0.1)。

3.3 虛擬路徑生成算法(DPC)

DPC算法是在DLG算法的基礎(chǔ)上，將每張快照所產(chǎn)生的虛擬用戶集通過交叉判斷，然后把合適的虛擬用戶填充至虛擬路由中。實施方法如下：考慮每個虛擬用戶的可達(dá)性，本文首先由DLG構(gòu)建出第一張快照中的虛擬用戶，其次定義一個參數(shù)來限制每個虛擬用戶從當(dāng)前位置到下一個位置的最大距離。計算如下：

(4)

其中，vti表示在一個時間戳為ti的快照中，用戶對應(yīng)的速度。

算法1DPC算法

輸出:D2,D3,…,Dk。

開始：Dj=?；

步驟1for(i=2;i

步驟2for(j=2;i

end

end

步驟5

隨機(jī)選擇虛擬用戶調(diào)用交叉；

不調(diào)用交叉;

end

將對應(yīng)位置dm加入到虛擬路徑Dj;

end

4 實驗評估

在實驗中，本文用定量的方法來評估Dummy-Ex方法的魯棒性。首先利用Ultra GPS Logger記錄了5條在長沙運動的真實GPS軌跡。然后用MobiREAL網(wǎng)絡(luò)模擬器模擬真實用戶和虛擬用戶的運動。

4.1 參數(shù)設(shè)置

表2中的參數(shù)和值將用于本文的實驗評估。真實用戶和虛擬用戶的移動速度將基于常規(guī)的平均速度1.30(m/s)，方差為0.22[(m/s)2]。本文選取15 000×15 000 m2的區(qū)域，并將之分為150×150的單元格來收集信息。

虛擬用戶的數(shù)量在本文的方法中是一個非常重要的參數(shù)。因為大量的虛擬用戶可以降低可溯性，但是也將增大通信的開銷。所以，一般情況下，在保證隱私的情況下，用戶會盡可能地降低虛擬用

Table 2 Experimental parameters表2 實驗參數(shù)

戶的數(shù)量。本文將使用不同數(shù)量的虛擬用戶進(jìn)行實驗。

4.2 實驗方法與結(jié)果

在實驗中，本文引用CaSDA和V-circle兩種方法(見表3)，在相同條件下進(jìn)行對比實驗。

Table 3 Methods for comparing experiments表3 用于對比實驗的方法

4.2.1 虛擬用戶對隱私的影響

本文首先評估不同虛擬用戶數(shù)量k對真實路由暴露率的影響。從圖7中可以看出，Dummy-Ex方法在虛擬用戶數(shù)量相同的情況下，隱匿性非常強(qiáng)，且隨著虛擬用戶數(shù)量k的增加，真實用戶曝光幾率越來越小。

相對而言，CaDSA雖然隱匿性也隨著虛擬用戶數(shù)量k的增加變得越來越強(qiáng)，但它需要一個受信任的第三方來緩存用戶的LBS請求，并通過篩選緩存中的歷史足跡形成虛擬用戶，雖然在隱匿性上基本達(dá)到了用戶需求，但由于第三方的建立，無形中增加了真實用戶曝光的可能性。V-circle也有較好的隱匿性，在虛擬用戶的選擇上充分考慮了現(xiàn)實環(huán)境的影響，但由于未考慮軌跡的可溯性，雖然每條虛擬軌跡看起來更真實，但在隱匿性上還不能達(dá)到理想狀態(tài)。

Figure 7 Number of virtual users vs exposure probability圖7 虛擬用戶數(shù)量k與曝露概率

4.2.2 平均混亂時間MTC

在實驗中，為了測試可追溯性，本文引用文獻(xiàn)[11]中的指標(biāo)“MTC(Mean Time to Confusion)”。MTC定義用戶的真實位置被LBS提供商意外泄后到重新隱匿的平均時間。每當(dāng)一個服務(wù)請求發(fā)出后，則需要計算每個位置可能是真實用戶的熵值，計算公式如下：

(5)

對于所有的虛擬用戶數(shù)量來說(N=16，25，32)，他們的MTC所顯示的特征基本上相同，因此實驗中用32個虛擬用戶進(jìn)行討論。當(dāng)用戶數(shù)量(真實和虛擬用戶數(shù)量)為32個時，對于不同匿名面積所產(chǎn)生的MTC值，如圖8所示。由圖8可以看出，在匿名面積很小的情況下，如300內(nèi)，三種方法所需要的時間差不多，這是因為在大多數(shù)情況下，虛擬用戶就分布在真實用戶周圍，如圖3a所示，基本上不需要對虛擬用戶過多處理。

Figure 8 Virtual path generation time圖8 虛擬路徑生成時間

當(dāng)匿名區(qū)域面積較大時，Dummy-Ex方法明顯比其他兩個方法的MTC值要小得多。這表明本文方法在降低可溯性方面非常出色。但是，隨著匿名區(qū)域大于1 500 m2后，用戶重新隱匿將花費越來越多的時間，因為虛擬用戶的密度變得很小，虛擬路線的選擇將花費更多的時間。但是，總體上Dummy-Ex還是保持著很大的優(yōu)勢。CaDSA在降低可溯性方面和本文所提方法相差較小，但由于是利用中間件緩存的用戶LBS請求數(shù)據(jù)，雖然響應(yīng)時間較短，可沒有考慮現(xiàn)實環(huán)境約束，所以在降低可溯性方面表現(xiàn)一般。V-circle考慮了現(xiàn)實環(huán)境的約束，但沒有對虛擬用戶進(jìn)行運動控制，有時會造成真實用戶的意外泄露，且隨著最小覆蓋區(qū)面積的增加,MTC增長較快。

5 結(jié)束語

考慮現(xiàn)有混淆、模糊和掩蓋等方法的不足，本文充分考慮現(xiàn)實環(huán)境和最小匿名區(qū)域大小等因素對位置隱私的影響，提出了一種有效的方法Dummy-Ex。該方法在每個路由快照中生成逼真的虛擬用戶，并基于用戶與虛擬用戶位置關(guān)系采用調(diào)用交叉來創(chuàng)建路由，實現(xiàn)對位置隱私的保護(hù)。實驗結(jié)果表明，本文方法在保護(hù)位置隱私方面卓有成效。

雖然構(gòu)建虛擬用戶是當(dāng)前常用的隱私保護(hù)技術(shù)，有利于個體用戶隱私保護(hù)，但是隨著大數(shù)據(jù)的發(fā)展，面對大數(shù)據(jù)資源的持續(xù)公開，隱私管理將面臨新型的隱私攻擊。在以后的研究中，如何預(yù)防資源數(shù)據(jù)融合帶來的隱私威脅將是一個重要的研究方向。

參考文獻(xiàn):

[1] Busic L,Filjar R.The role of position reporting frequency in LBS QoS establishment mechanisms for location privacy[C]∥Proc of SoftCOM,2006:209-213.

[2] Gruteser M,Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking[C]∥Proc of the 1st International Conference on Mobile Systems,Applications and Services (MOBISYS 2003),2003:31-42.

[3] Hong J I,Landay J A.An architecture for privacy-sensitive ubiquitous computing[C]∥Proc of the 2nd International Conference on Mobile Systems,Applications,and Services(MOBISYS 2004),2004:177-189.

[4] Beresford A R, Stajano F.Mix zones:User privacy in location-aware services[C]∥Proc of the 2nd IEEE Annual Conference on Pervasive Computing and Communications Workshops,2004:127-131.

[5] Kido H,Yanagisawa Y, Satoh T.An anonymous communication technique using dummies for location-based services[C]∥Proc of International Conference on Pervasive Services,2005:88-97.

[6] Lu H,Jensen C S.Privacy-area aware dummy-based location privacy in mobile services[C]∥Proc of the 7th ACM International Workshop on Data Engineering,2008:16-23.

[7] Yanagisawa Y,Kido H.Location traceability of users in location-based services[C]∥Proc of International Conference on Mobile Ubiquitous System,2006:1-8.

[8] Gruteser M,Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking[C]∥Proc of the 1st International Conference on Mobile Systems,Applications an Services(MOBISYS 2003),2003:31-42.

[9] Niu B,Li Q,Zhu X.Enhancing privacy through caching in location-based services[C]∥Proc of the 34th IEEE Conference on Computer Communications,2015:1017-1025.

[10] Niu B, Zhang Z, Li X, et al.Privacy-area aware dummy generation algorithms for location-based services[C]∥Proc of IEEE International Conference on Communications,2014:957-962.

[11] Shokri R,Freudiger J, Jadiwala M, et al.A distortion-based metric for location privacy[C]∥Proc of ACM WPES’09,2009:21-30.