陳 思，趙 明，張錦健

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

1 引言

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

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

針對車輛密度較低的區(qū)域，基于模糊的技術(shù)從很大程度上保護(hù)了個(gè)人位置隱私，尤其是替換位置對泛化位置的補(bǔ)充。Hong等[3]提出了利用圓形區(qū)域代替用戶真實(shí)位置的模糊法。但是，這種模糊技術(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提供商無法確定真實(shí)用戶的位置。但是，過去基于虛擬用戶的保護(hù)方法并沒有考慮現(xiàn)實(shí)環(huán)境中的物理約束，實(shí)際隱私保護(hù)的魯棒性值得商榷。因?yàn)榛谔摂M用戶隱私保護(hù)方法的魯棒性強(qiáng)弱程度是依靠虛擬用戶的行為是否自然而決定的，如圖1所示。

Figure 1 Moving trajectories of user and dummies圖1 真實(shí)用戶與虛擬用戶的移動(dòng)軌跡

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

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

Figure 2 Traceability圖2 可追溯性

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

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

2 概念與動(dòng)機(jī)

2.1 基本概念

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

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

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

2.2 基本思想

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

Table 1 Symbol references表1 符號(hào)引用表

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

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

3.1 虛擬用戶的運(yùn)動(dòng)控制

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

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

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

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

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

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

本文所提出的虛擬用戶生成算法(DLG)是在用戶設(shè)置的匿名區(qū)域內(nèi)，生成滿足用戶隱私需求的虛擬用戶，如圖6所示?；舅枷胧牵菏紫龋脩舾鶕?jù)需求定義一個(gè)最小的隱形區(qū)域Amin和參數(shù)δi。其中對應(yīng)隱形區(qū)域的最小半徑為：

(1)

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

(2)

|δi-1|=εi

(3)

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

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

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

(4)

其中，vti表示在一個(gè)時(shí)間戳為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 實(shí)驗(yàn)評估

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

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

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

虛擬用戶的數(shù)量在本文的方法中是一個(gè)非常重要的參數(shù)。因?yàn)榇罅康奶摂M用戶可以降低可溯性，但是也將增大通信的開銷。所以，一般情況下，在保證隱私的情況下，用戶會(huì)盡可能地降低虛擬用

Table 2 Experimental parameters表2 實(shí)驗(yàn)參數(shù)

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

4.2 實(shí)驗(yàn)方法與結(jié)果

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

Table 3 Methods for comparing experiments表3 用于對比實(shí)驗(yàn)的方法

4.2.1 虛擬用戶對隱私的影響

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

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

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

4.2.2 平均混亂時(shí)間MTC

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

(5)

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

Figure 8 Virtual path generation time圖8 虛擬路徑生成時(shí)間

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

5 結(jié)束語

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

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

參考文獻(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.