基于不可信近鄰的位置隱私保護(hù)方法

張海川，趙澤茂

(1.杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州310008;2.麗水學(xué)院工程與設(shè)計學(xué)院，浙江 麗水323000)

0 引 言

伴隨著無線通信網(wǎng)絡(luò)和移動定位技術(shù)的飛速發(fā)展，基于位置的服務(wù)(Location Based Services，LBS)越來越盛行。典型的LBS 應(yīng)用包括尋找資源、導(dǎo)航搜索等。用戶在使用此類服務(wù)時，必須將自己的位置信息提供給服務(wù)提供商，惡意攻擊者通過獲取用戶的位置信息再結(jié)合已有的背景知識，推測出用戶的身份信息、健康狀況、愛好等，這將嚴(yán)重威脅用戶的位置隱私。為了使用戶的位置隱私得到保護(hù)，學(xué)術(shù)界主要提出兩種位置隱私保護(hù)系統(tǒng)結(jié)構(gòu)，分別是基于可信第三方中心匿名服務(wù)器結(jié)構(gòu)和P2P 自組織網(wǎng)絡(luò)結(jié)構(gòu)?；诳尚诺谌街行哪涿?wù)器結(jié)構(gòu)的思想是利用中心匿名器將用戶的具體位置泛化為一個至少包含其他k-1個用戶的區(qū)域，然而使用中心匿名服務(wù)器結(jié)構(gòu)時，中心服務(wù)器本身會成為系統(tǒng)的性能瓶頸和主要攻擊目標(biāo)[1-2]。P2P自組織網(wǎng)絡(luò)結(jié)構(gòu)的思想是在不引入第三方匿名器的情況下假設(shè)用戶之間相互信任并分享位置信息，用戶之間通過P2P 通信收集其他用戶的位置信息[3-4]。但是，在現(xiàn)實(shí)中用戶之間彼此信任的假設(shè)不是成立的。本文提出一種新的位置隱私保護(hù)方法即不可信近鄰算法(Untrusted Nearest Neighborhood Cloak，UNNC)，在P2P 網(wǎng)絡(luò)中用戶之間相互不信任的前提下通過引入第三方驗(yàn)證器實(shí)現(xiàn)位置隱私保護(hù)。

1 研究背景

從系統(tǒng)的結(jié)構(gòu)來看，LBS位置隱私保護(hù)結(jié)構(gòu)主要分為基于中心匿名器的結(jié)構(gòu)和P2P 自組織網(wǎng)絡(luò)結(jié)構(gòu)?；谥行哪涿鹘Y(jié)構(gòu)的位置隱私保護(hù)方法有很多，如間隔匿名(interval cloak)，Casper和PrivacyGrid 等。間隔匿名算法是將空間遞歸劃分為4個相等的矩形，每個矩形對應(yīng)四叉樹結(jié)構(gòu)中的一個節(jié)點(diǎn)，每個節(jié)點(diǎn)中包含當(dāng)前節(jié)點(diǎn)對應(yīng)區(qū)域內(nèi)的用戶數(shù)量，使用由子節(jié)點(diǎn)直接向父節(jié)點(diǎn)搜索的方法計算匿名區(qū)域。Casper 匿名算法是對間隔匿名算法的改進(jìn)，Casper算法直接通過hash表來訪問四叉樹中的節(jié)點(diǎn)并在計算匿名區(qū)域時首先搜索節(jié)點(diǎn)的相鄰兄弟節(jié)點(diǎn)再搜索父節(jié)點(diǎn)。PrivacyGrid算法把空間劃分為網(wǎng)格結(jié)構(gòu)，使用自頂向上的方法計算匿名區(qū)域，同時引入了位置多樣化的概念，增強(qiáng)了位置隱私保護(hù)效果。

文獻(xiàn)[3]提出了P2P空間匿名算法，算法假設(shè)用戶之間相互信任并通過P2P 通信方式分享彼此的位置信息形成匿名組，再計算匿名組內(nèi)用戶形成的最小邊界矩形，需要發(fā)起LBS 查詢請求的用戶請求匿名組中的某一用戶作為代理向LBS位置服務(wù)器發(fā)起服務(wù)請求。文獻(xiàn)[5]提出了CoPrivacy 匿名算法，算法也是通過P2P 通信生成匿名組，匿名組內(nèi)的用戶用該組的密度中心代替真實(shí)位置發(fā)出查詢請求，并采取文獻(xiàn)[6]中提出的SpaceTwist 方法中采用的增量查詢方案。文獻(xiàn)[7]提出了將中心服務(wù)器結(jié)構(gòu)和P2P 自組織網(wǎng)絡(luò)相結(jié)合的方案，是一種新的思路。

2 UNNC算法的系統(tǒng)結(jié)構(gòu)

本文提出的UNNC位置隱私保護(hù)方法的系統(tǒng)結(jié)構(gòu)是在傳統(tǒng)的P2P 結(jié)構(gòu)下引入了第三方驗(yàn)證服務(wù)器，系統(tǒng)模型如圖1所示。UNNC位置隱私保護(hù)方法的系統(tǒng)結(jié)構(gòu)主要包含移動用戶、第三方驗(yàn)證服務(wù)器和位置服務(wù)提供商3個部分。移動用戶的終端支持無線互聯(lián)網(wǎng)通信和P2P 通信兩種通訊方式，其中P2P 通信是用來與其他用戶相互協(xié)作時的自組網(wǎng)通信，而用戶與位置服務(wù)提供商和第三方驗(yàn)證服務(wù)器之間的通信使用的是無線互聯(lián)網(wǎng)通信方式。用戶之間的P2P 通信一般是通過藍(lán)牙或者無線局域網(wǎng)等方式實(shí)現(xiàn)，而無線互聯(lián)網(wǎng)通信則是通過地面基站覆蓋的移動蜂窩網(wǎng)絡(luò)。第三方驗(yàn)證機(jī)構(gòu)是協(xié)助發(fā)起服務(wù)請求的用戶判斷收到的用戶信息是否是真實(shí)可靠的，以防止其他的用戶模擬出一個或多個用戶向發(fā)起請求的用戶發(fā)起惡意攻擊。位置服務(wù)提供商是指提供基于位置服務(wù)的Internet 服務(wù)提供商(Internet Service Provider，ISP)。

圖1 UNNC系統(tǒng)模型圖

3 UNNC位置隱私保護(hù)方法

在上述的位置隱私保護(hù)系統(tǒng)結(jié)構(gòu)下，本文提出了一種P2P 自組織網(wǎng)絡(luò)下移動用戶相互協(xié)作但不相互信任的位置隱私保護(hù)方法UNNC，本節(jié)將對UNNC算法進(jìn)行詳細(xì)描述。

3.1 預(yù)備知識

定義1 VERF 碼。表示用戶真實(shí)存在的驗(yàn)證碼，具有唯一性，并且當(dāng)用戶的當(dāng)前VERF 碼被其他用戶成功驗(yàn)證后會得到驗(yàn)證器重新頒發(fā)的新的VERF 碼以保證其可用性。

定義2 NL表。用戶把收集到的其他用戶的VERF 碼保存在表中，此表即NL表。

3.2 算法描述

UNNC位置隱私保護(hù)算法的實(shí)現(xiàn)一共包括4個階段，實(shí)現(xiàn)過程如下:

1)準(zhǔn)備階段。系統(tǒng)中每個用戶開機(jī)的時候都向驗(yàn)證服務(wù)器發(fā)起登記請求，申請與自己的ID 相對應(yīng)的唯一的VERF 碼，同時驗(yàn)證服務(wù)器將用戶的ID與VERF 碼以鍵值對的方式存儲在內(nèi)存空間內(nèi);

2)查找周圍用戶階段。當(dāng)用戶U 發(fā)起LBS 服務(wù)請求時，向直接鄰居發(fā)起跳數(shù)hop為1的查找請求，hop 參數(shù)是用戶之間點(diǎn)對點(diǎn)通信中的路由跳數(shù)，其間接的反應(yīng)了用戶之間的距離。用戶U的直接鄰居在接受到來自用戶U的查找請求時會將自己的VERF 碼發(fā)送給用戶U，并且向其自身的直接鄰居用戶也發(fā)起hop為1的查找請求并將收集到的VERF 碼存放在自身的NL表中。用戶U 將收集到的VERF 碼存放在自己的NL表中，并比較收集到的VERF 碼的個數(shù)n與k-1 做比較，若n≥k-1，則將NL表發(fā)送給驗(yàn)證服務(wù)器，驗(yàn)證服務(wù)器將來自用戶U的NL表中的VERF 碼與自身存儲的VERF 碼做比較，返回給用戶U真實(shí)的VERF 碼個數(shù)m，否則用戶U 就增加hop值以獲取更多鄰居用戶信息，直到收集到VERF 碼的個數(shù)n 不小于匿名需求參數(shù)k。用戶U 判斷m與k的大小，若m≥k-1，則查找階段結(jié)束，否則用戶U 就增加hop值以獲取更多鄰居用戶信息，直到返回的真實(shí)VERF 碼個數(shù)m 滿足m≥k-1;

3)發(fā)起服務(wù)階段。在查找周圍用戶階段已經(jīng)發(fā)現(xiàn)了至少k-1個可信任的鄰居用戶，用戶U 生成一個隨機(jī)數(shù)x(x∈(0，1))并選擇一個任意方向距離自身x×(hop-1)×200 m的位置作為錨點(diǎn)，向位置服務(wù)提供商發(fā)起LBS 服務(wù)請求。由于移動設(shè)備不同的通訊和計算能力，用戶在點(diǎn)對點(diǎn)網(wǎng)絡(luò)中的通信距離一般在200 300 m 之間，假定通信距離為200 m。用戶U 在接受來來自位置服務(wù)器的返回結(jié)果時，根據(jù)用戶真實(shí)位置和返回的結(jié)果集進(jìn)行計算，從而得到精確的結(jié)果集;

4)在服務(wù)請求結(jié)束后用戶U 向驗(yàn)證服務(wù)器發(fā)送本次請求已結(jié)束的通知，驗(yàn)證服務(wù)器收到通知后就為用戶U 最后一次傳送的NL表中真實(shí)的VERF 碼所對應(yīng)的用戶重新生成VERF 碼。這是為了防止用戶記住其他用戶的VERF 碼而向其他的用戶發(fā)起惡意攻擊。

UNNC算法偽代碼:

4 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)環(huán)境是Windows7 操作系統(tǒng)，內(nèi)存空間為4 GB，實(shí)驗(yàn)數(shù)據(jù)是根據(jù)Thomas Brinkhoff 路網(wǎng)數(shù)據(jù)生成器生成。在模擬實(shí)驗(yàn)數(shù)據(jù)上對UNNC 匿名算法的平均響應(yīng)時間和匿名成功率進(jìn)行測試，并將UNNC算法與文獻(xiàn)[5]中提出的CoPrivacy算法和文獻(xiàn)[3]提出的空間矩形算法中的On-demand算法進(jìn)行比較。模擬實(shí)驗(yàn)數(shù)據(jù)如表1所示。

由表1可知，在上述交通路網(wǎng)中一共生成4 000個移動用戶，實(shí)驗(yàn)統(tǒng)一設(shè)定用戶可接受的其他用戶信息的最大hop值為8。實(shí)驗(yàn)假設(shè)系統(tǒng)中存在2%的用戶是惡意用戶，即在本實(shí)驗(yàn)中共有80個惡意用戶。匿名參數(shù)k的值從5 變到50，比較3種算法的平均匿名成功率和平均匿名響應(yīng)時間。平均匿名成功率和平均匿名響應(yīng)時間是評價位置匿名算法的兩個重要參數(shù)。如圖2所示。

表1 模擬實(shí)驗(yàn)數(shù)據(jù)

圖2 匿名參數(shù)變化對系統(tǒng)性能的影響

圖2(a)表明當(dāng)匿名參數(shù)k 顯著增大的時候，3種算法的匿名成功率也會隨之而下降，UNNC算法相對其他兩種算法具有更高的匿名成功率，這是因?yàn)樵趯?shí)驗(yàn)中假設(shè)有惡意用戶的存在，但是CoPrivacy算法和On-demand算法并不具有抵抗來自網(wǎng)絡(luò)節(jié)點(diǎn)用戶的惡意攻擊。圖2(b)表明，當(dāng)匿名參數(shù)k 顯著上升時兩種算法完成匿名所需的時間會逐漸增加，并且文中所提出的UNNC算法所需的時間比其他兩種算法更長，這是由于UNNC算法中增加了第三方驗(yàn)證器，與第三方驗(yàn)證器的通信需要消耗額外的時間。由上述實(shí)驗(yàn)可知，UNNC算法可以在不假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)中的用戶是相互信任的前提下獲得很高的匿名成功率。

5 結(jié)束語

本文提出了一種新的位置隱私保護(hù)方法UNNC，在P2P 網(wǎng)絡(luò)中用戶之間相互協(xié)作但并不信任的假設(shè)下，通過引入第三方驗(yàn)證機(jī)構(gòu)來實(shí)現(xiàn)位置隱私保護(hù)。UNNC算法可以有效地抵御P2P 網(wǎng)絡(luò)中來自惡意用戶的攻擊，目前國內(nèi)外學(xué)者在這方面的研究并不多。UNNC算法在模擬數(shù)據(jù)上進(jìn)行了充分的模擬實(shí)驗(yàn)，模擬實(shí)驗(yàn)結(jié)果表明UNNC算法是切實(shí)可行的，但是在模擬實(shí)驗(yàn)中也發(fā)現(xiàn)算法在相同匿名度的情況下需要更多的時間來完成匿名，這將是未來工作的重點(diǎn)和難點(diǎn)。

[1]Mokbel M F，Chow C Y，Aref W G.The new Casper:A privacy-aware location-based database server[C]//Data Engineering，2007.ICDE 2007.IEEE 23rd International Conference on.Istanbul:IEEE，2007:1499-1500.

[2]Bamba B，Liu L，Pesti P，et al.Support Anonymous Location Queries in mobile Environments with Privacygrid[C]//Proceeding of the 17th International Conference on World Wide Web.New York:ACM，2008:237-246.

[3]Chow C Y，Mokbel M F，Liu X.A Peer-to-Peer Spatial Cloaking Algorithm for Anonymous Location-based Services[C]//Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems.New York:ACM，2006:171-178.

[4]Che Y，Yang Q，Hong X.A Dual-Active Spatial Cloaking Algorithm for Location Privacy Preserving in Mobile Peer-to-Peer Networks[C]//Wireless Communications and Networking Conference(WCNC)，2012 IEEE.Shanghai:IEEE，2012:2098-2102.

[5]黃毅，霍崢，孟小峰.CoPrivacy:一種用戶協(xié)作無匿名區(qū)域的位置隱私保護(hù)方法[J].計算機(jī)學(xué)報，2011，34(10):1976-1985.

[6]Yiu M L，Jensen C S，Huang X.Space Twist:Managing the trade-offs among location privacy，query performance，and query accuracy in mobile services[C]//Data Engineering，2008.ICDE 2008.IEEE 24th International Conference on.Cancun:IEEE，2008:366-375.

[7]Zhang C，Huang Y.Cloaking locations for anonymous location based services:a hybrid approach[J].GeoInformatica，2009，13(2):159-182.