張海川，趙澤茂

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

0 引 言

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

1 研究背景

從系統(tǒng)的結(jié)構(gòu)來(lái)看，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個(gè)相等的矩形，每個(gè)矩形對(duì)應(yīng)四叉樹結(jié)構(gòu)中的一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)中包含當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)區(qū)域內(nèi)的用戶數(shù)量，使用由子節(jié)點(diǎn)直接向父節(jié)點(diǎn)搜索的方法計(jì)算匿名區(qū)域。Casper 匿名算法是對(duì)間隔匿名算法的改進(jìn)，Casper算法直接通過(guò)hash表來(lái)訪問(wèn)四叉樹中的節(jié)點(diǎn)并在計(jì)算匿名區(qū)域時(shí)首先搜索節(jié)點(diǎn)的相鄰兄弟節(jié)點(diǎn)再搜索父節(jié)點(diǎn)。PrivacyGrid算法把空間劃分為網(wǎng)格結(jié)構(gòu)，使用自頂向上的方法計(jì)算匿名區(qū)域，同時(shí)引入了位置多樣化的概念，增強(qiáng)了位置隱私保護(hù)效果。

文獻(xiàn)[3]提出了P2P空間匿名算法，算法假設(shè)用戶之間相互信任并通過(guò)P2P 通信方式分享彼此的位置信息形成匿名組，再計(jì)算匿名組內(nèi)用戶形成的最小邊界矩形，需要發(fā)起LBS 查詢請(qǐng)求的用戶請(qǐng)求匿名組中的某一用戶作為代理向LBS位置服務(wù)器發(fā)起服務(wù)請(qǐng)求。文獻(xiàn)[5]提出了CoPrivacy 匿名算法，算法也是通過(guò)P2P 通信生成匿名組，匿名組內(nèi)的用戶用該組的密度中心代替真實(shí)位置發(fā)出查詢請(qǐng)求，并采取文獻(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)主要包含移動(dòng)用戶、第三方驗(yàn)證服務(wù)器和位置服務(wù)提供商3個(gè)部分。移動(dòng)用戶的終端支持無(wú)線互聯(lián)網(wǎng)通信和P2P 通信兩種通訊方式，其中P2P 通信是用來(lái)與其他用戶相互協(xié)作時(shí)的自組網(wǎng)通信，而用戶與位置服務(wù)提供商和第三方驗(yàn)證服務(wù)器之間的通信使用的是無(wú)線互聯(lián)網(wǎng)通信方式。用戶之間的P2P 通信一般是通過(guò)藍(lán)牙或者無(wú)線局域網(wǎng)等方式實(shí)現(xiàn)，而無(wú)線互聯(lián)網(wǎng)通信則是通過(guò)地面基站覆蓋的移動(dòng)蜂窩網(wǎng)絡(luò)。第三方驗(yàn)證機(jī)構(gòu)是協(xié)助發(fā)起服務(wù)請(qǐng)求的用戶判斷收到的用戶信息是否是真實(shí)可靠的，以防止其他的用戶模擬出一個(gè)或多個(gè)用戶向發(fā)起請(qǐng)求的用戶發(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ò)下移動(dòng)用戶相互協(xié)作但不相互信任的位置隱私保護(hù)方法UNNC，本節(jié)將對(duì)UNNC算法進(jìn)行詳細(xì)描述。

3.1 預(yù)備知識(shí)

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

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

3.2 算法描述

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

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

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

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

4)在服務(wù)請(qǐng)求結(jié)束后用戶U 向驗(yàn)證服務(wù)器發(fā)送本次請(qǐng)求已結(jié)束的通知，驗(yàn)證服務(wù)器收到通知后就為用戶U 最后一次傳送的NL表中真實(shí)的VERF 碼所對(duì)應(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ù)上對(duì)UNNC 匿名算法的平均響應(yīng)時(shí)間和匿名成功率進(jìn)行測(cè)試，并將UNNC算法與文獻(xiàn)[5]中提出的CoPrivacy算法和文獻(xiàn)[3]提出的空間矩形算法中的On-demand算法進(jìn)行比較。模擬實(shí)驗(yàn)數(shù)據(jù)如表1所示。

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

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

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

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

5 結(jié)束語(yǔ)

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