唐朝生,李鵬飛,王 輝,王成杰,申自浩

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

1 引 言

得益于移動(dòng)終端設(shè)備的多樣性以及定位服務(wù)系統(tǒng)的迅猛發(fā)展,我們的生活發(fā)生了巨大變革,人們足不出戶便可以獲得想要的服務(wù)[1].穿衣有淘寶、吃飯有美團(tuán)、住宿有飛豬、旅游有攜程,人們能夠通過各式各樣的APP來隨時(shí)隨地獲取服務(wù)[2],這一切都源自于基于位置的服務(wù)(Location Based Services,LBS)的迅猛發(fā)展.據(jù)統(tǒng)計(jì),全球LBS和實(shí)時(shí)定位系統(tǒng)的市場占有率從2015年的113.6億增加到2020年的549.5億美元,年復(fù)合增長率為37.1%.

基于位置服務(wù)[3,4]是指基于移動(dòng)設(shè)備的位置信息以及通信網(wǎng)絡(luò)的信息傳遞,為移動(dòng)用戶提供各種各樣的增值服務(wù).隨著人們對服務(wù)的需求增加,位置服務(wù)提供商(Location Service Providers,LSP)可能會(huì)為了自己的利益而將用戶的隱私泄露給不法分子,威脅到用戶的財(cái)產(chǎn)甚至人身安全[5].因此,在給用戶提供便捷服務(wù)的同時(shí)保證用戶的隱私安全成為一個(gè)亟待解決的問題[6].

2 相關(guān)工作

在面向位置服務(wù)的隱私保護(hù)[7]方面,基于K匿名[8,9]的空間泛化技術(shù)一直是學(xué)者們研究的熱點(diǎn).其核心思想是將用戶的真實(shí)位置泛化,保證匿名區(qū)域(Anonymous Spatial Region,ASR)內(nèi)至少包含K-1個(gè)用戶,使得LSP無法從K個(gè)用戶中區(qū)分出真實(shí)用戶[10].現(xiàn)階段基于K匿名的隱私保護(hù)技術(shù)也有較多研究.例如,賈俊杰等人[11]基于K匿名思想提出一種可抵制相似性攻擊的(p,k,d)-匿名模型,采用基于距離的度量方法劃分等價(jià)類,減少隱私保護(hù)中信息的損失.袁健等人[12]提出了K-Differential-Privacy隱私保護(hù)模型,采用噪聲匿名組的思想,克服了現(xiàn)有算法對隱私預(yù)算過度依賴的弊端.郭敏等人[13]基于K匿名機(jī)制提出了r匿名的概念,引入一種時(shí)間混淆技術(shù),在有限的計(jì)算成本下,增加了查詢結(jié)果的正確性.Zheng等人[14]提出了一種基于K匿名模型的離群值剔除聚類算法,該算法通過以匿名組為中心代替用戶位置的思想優(yōu)化了用戶在匿名組中的分布,但形成的ASR往往大于實(shí)際需要.Wang等人[15]結(jié)合差分隱私和K匿名的概念提出DPkA(Differe-ntially Private k-anonymity)方法,并給出了實(shí)現(xiàn)方式,但是匿名效率不高,在用戶查詢次數(shù)頻繁的情況下容易受到連續(xù)查詢攻擊.文獻(xiàn)[16]提出了一種基于層次分析法的K匿名算法,該方法在聚類過程中,總是選擇距離最小的記錄進(jìn)行添加,并根據(jù)K值對聚類進(jìn)行單獨(dú)控制,實(shí)現(xiàn)等價(jià)類的均衡劃分,但是當(dāng)在用戶密集的地方形成的K匿名區(qū)域較小時(shí),攻擊者依舊可以推斷出用戶的大致位置,安全性不高.

由上述研究方案可知,在生成ASR的過程中,在避免ASR受到攻擊導(dǎo)致用戶隱私泄露的同時(shí),匿名效率與安全性能之間總是得不到很好的平衡.另一方面,現(xiàn)有的研究方法[17]大都將重心放在了位置隱私保護(hù)方面,忽略了用戶的查詢隱私保護(hù).攻擊者有很大的概率可根據(jù)用戶查詢內(nèi)容推斷出用戶的敏感信息造成隱私泄露,甚至不能不考慮很多攻擊者就來自于LSP內(nèi)部人員.所以最好的方法就是用戶在獲取服務(wù)的同時(shí)不對外暴露任何信息.

針對以上問題,本文研究內(nèi)容及所作貢獻(xiàn)如下:

1)提出一種基于K匿名機(jī)制的K-Vretr(K-Voronoi retrieval)隱私保護(hù)方法.采用可信第三方架構(gòu),在減輕客戶端與服務(wù)端負(fù)載壓力的同時(shí)從位置和查詢兩個(gè)方面有效保護(hù)了用戶的隱私.

2)針對匿名過程中構(gòu)造ASR效率不高或安全度不夠的問題,采用基于Voronoi圖模型的K匿名隨機(jī)位置隱藏方法,保證ASR安全性的同時(shí)滿足了位置l-多樣性,使得用戶被攻擊者識別的概率低于1/K.

3)在保護(hù)查詢隱私方面,因LBS的特殊性及不可信性,故本文采用安全性相對較高的基于私有信息檢索技術(shù)[18-21]的二次剩余假設(shè)模型,確?？尚诺谌椒?wù)器(Trusted Third Part server,TTPs)能從不可信的LBS中安全檢索到想要的數(shù)據(jù),有效防范了因LBS被攻擊而造成的用戶隱私泄露問題.

3 預(yù)備知識

3.1 系統(tǒng)架構(gòu)

隨著問題背景的深化和攻擊模型的改變,位置隱私還將繼續(xù)面臨新的挑戰(zhàn),如LBS服務(wù)器容易遭受攻擊,在不可完全信任LBS運(yùn)營商的前提下,造成敏感屬性泄露的風(fēng)險(xiǎn)是客觀存在的.為保證用戶隱私與服務(wù)質(zhì)量,本方法引入TTPs,由用戶端、TTPs以及LBS服務(wù)器構(gòu)成可信第三方中心架構(gòu),如圖1所示.在K-Vretr隱私保護(hù)方法中,TTPs與LBS服務(wù)器共同維護(hù)一份信息點(diǎn)集合.用戶端將服務(wù)請求信息發(fā)送至TTPs,TTPs根據(jù)用戶服務(wù)請求信息及自身緩存的信息點(diǎn)生成Voronoi圖,按既定規(guī)則去選擇K-1個(gè)其他V塊中的虛擬用戶與當(dāng)前用戶的虛假位置組成用戶匿名集發(fā)送給LBS服務(wù)器.得到用戶匿名集之后,LBS服務(wù)器根據(jù)用戶目標(biāo)信息點(diǎn)與K個(gè)用戶之間的鄰近關(guān)系生成關(guān)系矩陣.此后,TTPs從關(guān)系矩陣中檢索目標(biāo)信息并返回給用戶,這是一次完整的服務(wù)請求.在整個(gè)隱私保護(hù)過程中,以TTPs作為總載體,完成了數(shù)據(jù)的集中化,只要保證TTPs的安全即可滿足用戶對隱私安全的要求.

3.2 相關(guān)定義

定義1.信息點(diǎn)(Point Of Information,POI):地理信息系統(tǒng)術(shù)語,泛指一切可以抽象為點(diǎn)的地理對象.例如生活中隨處可見的醫(yī)院、超市、健身房,甚至一個(gè)路燈等.POI的定義如下:

POI(Des,Cat,Coo,Cla)

(1)

其中,Des代表POI的唯一名稱標(biāo)識;Cat代表POI的類別;Coo代表POI的位置信息;Cla代表POI所屬的分類,宏觀分為1級類和2級類.POI的引入是為了增強(qiáng)對用戶位置的查詢和描述能力,并提高查詢效率.

圖1 通信模型Fig.1 Communication model

定義2.Voronoi圖.設(shè)集合D={D1,D2,D3,…,Dn}為平面上n個(gè)POI的集合,滿足

?Di,Dj∈D,Eve∈Vi|S(Eve,Di)

(2)

則為Voronoi圖.其中,S(Eve,Dj)為點(diǎn)Eve到點(diǎn)Dj的歐式距離;Vi為Voronoi圖中任意單個(gè)多邊形,稱為V塊;Eve為V塊中任意一點(diǎn).如圖2所示.

圖2 Voronoi圖中的V塊Fig.2 Block V in Voronoi diagram

Voronoi圖的特點(diǎn)是每個(gè)V塊中有一個(gè)焦點(diǎn)Dj;每個(gè)V塊內(nèi)點(diǎn)到該焦點(diǎn)距離小于到其它V塊內(nèi)焦點(diǎn)的距離,如S(Eve,D1)

定義3.用戶端請求:

R(IDu,Pe,Cat,Utime,d)

(3)

其中,字段IDu代表用戶的唯一標(biāo)識號;字段Pe代表用戶端發(fā)起請求時(shí)的位置;Cat代表POI類別;Utime代表用戶發(fā)送請求時(shí)的時(shí)間點(diǎn);d代表一個(gè)大的奇素?cái)?shù).

定義4.用戶匿名集:

Users(IDc,Cat,Ctime,X,P)

(4)

其中,IDc表示用戶匿名集的唯一標(biāo)識號;Cat表示用戶匿名集的POI類別;Ctime表示用戶匿名集發(fā)出的時(shí)間;用戶私有信息X=(x1,x2,…,xu,…,xK)中有K-1個(gè)模d的二次剩余和一個(gè)模d的二次非剩余xu;位置集合P={P1,P2,…,Pu,…,PK}表示用戶匿名集中K個(gè)用戶的位置,Pu表示真實(shí)用戶所屬V塊中的隨機(jī)虛假位置.位置參數(shù)P需要滿足:

?Pi∈Vi,?Pj?Vi,i≠j

(5)

其中,參數(shù)Vi表示Voronoi圖中V塊.以此限定TTPs在把用戶匿名集發(fā)送給LBS服務(wù)器時(shí)的用戶位置一定是從不同V塊中隨機(jī)挑選出來的.

4 基于K匿名的K-Vretr隱私保護(hù)機(jī)制

在隱私保護(hù)流程開始之前,LBS服務(wù)器將基于同類別POI構(gòu)建的Voronoi圖同步保存在TTPs和LBS服務(wù)器中.如算法1所示,以POI為基點(diǎn),利用Delaunay三角剖分算法生成三角網(wǎng),再找出三角網(wǎng)內(nèi)每一個(gè)三角形的外接圓圓心,最后連接相鄰圓心構(gòu)建出Voronoi圖模型.如圖3所示,每一個(gè)多邊形代表一個(gè)V塊,每個(gè)V塊的焦點(diǎn)為POI.當(dāng)隱私保護(hù)流程開始之后,TTPs接收用戶查詢請求,依據(jù)用戶端請求R中POI類別Cat劃分出相應(yīng)的Voronoi圖.

圖3 Voronoi圖模型(POI=100)Fig.3 Voronoi diagram model(POI=100)

算法1.基于POI的Voronoi構(gòu)建

根據(jù)定義2中集合D={D1,D2,D3,…,Dn}中所有的n個(gè)同類POI,將其位置信息Coo插入POIlist.

輸入:POIlist

輸出:以信息點(diǎn)為焦點(diǎn)的Voronoi圖

1.initialize thetrianglelist

2.initialize theedgebuffer

3.determine the supertriangle

4.add supertriangle vertices to the end of thePOIlist

5.add the supertriangle to thetrianglelist

6.for eachPOIlist

7. for eachtrianglelist

8. calculate the triangle circumcircle center and radius

9. if the point lies in the triangle circumcircle then

10. add the three triangle edges to theedgebuffer

11. remove the triangle from thetrianglelist

12. endif

13. endfor

14. delete all doubly specified edges from theedgebufferthis leaves the edges of the enclosing polygon only

15. add to thetrianglelistall triangle formed between the point and the edges of the enclosing polygon

16.endfor

17.remove any triangles from thetrianglelistthat use the supertriangle vertices

18.remove the supertriangle vertices from thePOIlist

19.connectand get Voronoi

20.end

如算法1所示,輸入POI集合,通過三角剖分算法,得到以POI為焦點(diǎn)的Voronoi圖.其中,算法1-2行初始化三角形表trianglelist與邊緩沖器edgebuffer;第3行確定大的超級三角形;第4行分別將超級三角形的3個(gè)頂點(diǎn)坐標(biāo)插入到POI表POIlist,此處的POIlist是將POI的經(jīng)緯度轉(zhuǎn)換為屏幕坐標(biāo)后的;第5行將超級三角形添加到trianglelist中;算法6-16行分別遍歷POIlist、trianglelist,然后計(jì)算三角形的外接圓圓心和半徑,如果POIlist中點(diǎn)位于三角形外接圓上,那么將三角形的3條邊添加入edgebuffer,然后從trianglelist中刪去此三角形,最后從edgebuffer中刪除所有雙重指定的邊,僅留下封閉多邊形的邊并向trianglelist中添加點(diǎn)和封閉多邊形之間形成的所有三角形;第17-18行從trianglelist中刪除以超級三角形頂點(diǎn)為頂點(diǎn)的三角形并將超級三角形的頂點(diǎn)從POIlist中刪除,得到Delaunay三角網(wǎng);第19行連接所有三角形的外接圓圓心得到以同類POI為焦點(diǎn)的Voronoi圖.

算法1的算法復(fù)雜度計(jì)算共分為4部分.第1部分為構(gòu)造Delaunay三角網(wǎng),復(fù)雜度為O(n2);第2部分計(jì)算三角形外接圓圓心,復(fù)雜度為O(n);第3部分尋找三角形三邊相鄰的三角形,復(fù)雜度為3O(n);第4部分畫出Voronoi圖,復(fù)雜度為O(n).因此生成以同類POI為焦點(diǎn)的Voronoi圖的算法復(fù)雜度為O(n2)+O(n)+3O(n)+O(n)=O(n2).

4.1 基于Voronoi圖模型的位置隱私保護(hù)過程

4.1.1 TTPs對用戶端請求R的處理

當(dāng)TTPs收到用戶請求R時(shí),首先根據(jù)R中的用戶唯一標(biāo)識號IDu判斷此次請求是否由同一用戶再次發(fā)起.如果是第一次發(fā)起,TTPs則按照既定規(guī)則生成用戶匿名集發(fā)送給LBS服務(wù)器;如果不是第1次發(fā)起,TTPs則根據(jù)最新的用戶請求R中的兩次位置Pe進(jìn)行計(jì)算,當(dāng)最新的用戶位置Pe已經(jīng)離開上一次所屬V塊時(shí),就重新生成用戶匿名集發(fā)送給LBS服務(wù)器.及時(shí)更新用戶匿名集可以有效防止聯(lián)合攻擊和位置推斷攻擊.如果用戶多次發(fā)來的位置Pe均屬于同一V塊,那么TTPs將根據(jù)用戶每次查詢請求R的發(fā)送時(shí)間Utime形成一個(gè)時(shí)間序列集合Utime={t1,t2,…,tn},計(jì)算出γ值.

(6)

設(shè)TTPs正常負(fù)載值為?,當(dāng)?≥γ時(shí),TTPs重新生成用戶匿名集發(fā)送給LBS服務(wù)器;反之,直接發(fā)送上一次生成的用戶匿名集.這種方式在某種程度上減輕了TTPs的負(fù)載壓力,同時(shí)在服務(wù)器負(fù)載較低時(shí),高頻率的更新用戶匿名集可以有效抵抗連續(xù)查詢攻擊和關(guān)聯(lián)攻擊,增強(qiáng)匿名性.

4.1.2 TTPs對用戶匿名集Users的生成規(guī)則

TTPs收到用戶請求R后依據(jù)標(biāo)識號IDu保存下R中所有信息.根據(jù)R中的用戶真實(shí)位置Pe與其鄰近POI生成同類POI的Voronoi圖;然后從其所屬的V塊中隨機(jī)選擇一個(gè)虛假位置點(diǎn)替代用戶的真實(shí)位置,并在此Voronoi圖中以全隨機(jī)方式從不同V塊中挑選K-1個(gè)虛假位置點(diǎn),生成共K個(gè)分別屬于不同V塊的虛假用戶,組成用戶匿名集發(fā)送至LBS服務(wù)器.其中,用戶請求R中的POI類別Cat與用戶匿名集Users中的Cat相同.

Voronoi圖模型的應(yīng)用將連續(xù)的匿名空間分割成離散的V塊,相較于傳統(tǒng)K匿名生成的匿名空間,達(dá)到了分割空間的作用.這樣做的好處：1)隨機(jī)分割空間的方法會(huì)增強(qiáng)匿名性,保護(hù)ASR的安全;2)在使用虛假位置代替用戶真實(shí)位置的同時(shí)不會(huì)影響服務(wù)質(zhì)量;3)有效規(guī)避掉了基于添加噪聲的隱私保護(hù)方法中因噪聲位置不實(shí)際所帶來的隱私泄露風(fēng)險(xiǎn).

4.2 基于二次剩余假設(shè)模型的查詢隱私保護(hù)過程

在難解的二次剩余假設(shè)問題模型的私有信息檢索協(xié)議中,將服務(wù)器數(shù)據(jù)庫中數(shù)據(jù)定義為關(guān)系矩陣,TTPs的檢索目標(biāo)是矩陣中二進(jìn)制位中的一位數(shù)據(jù),用戶端根據(jù)自己所持有的私有信息向服務(wù)器發(fā)起查詢,當(dāng)LBS服務(wù)器收到查詢信息后,對矩陣中每一行元素進(jìn)行規(guī)則運(yùn)算得到查詢結(jié)果然后返回給用戶端,完成一次檢索.

LBS服務(wù)器接收到用戶匿名集Users以后,根據(jù)POI類別Cat與位置集合P生成關(guān)系矩陣,這個(gè)關(guān)系矩陣中包含n個(gè)POI與K個(gè)用戶的位置鄰近關(guān)系.

定義5.二次剩余:設(shè)大的奇素?cái)?shù)d>1,a∈Z且1≤a≤d,(a,d)=1,對于二次同余式y(tǒng)2≡a(modd),若存在y∈Z滿足此式,那么稱a是模d的二次剩余,否則稱為二次非剩余.

定義6.d為大的奇素?cái)?shù),(a,d)=1,由二次剩余理論模型中的歐拉判別條件有

1)a是模d的二次剩余的充要條件為:

(7)

2)a是模d的二次非剩余的充要條件為:

(8)

定義7.LBS服務(wù)器中生成的關(guān)系矩陣為

(9)

其中,aij∈{0,1},aij的值代表關(guān)系矩陣中第i個(gè)POI與私有信息X中第j個(gè)用戶的鄰近關(guān)系;1代表鄰近,0代表疏遠(yuǎn);n代表POI數(shù)量;K為用戶匿名集中用戶數(shù)量.

定義8.函數(shù)

g(ω,θ)=xωaθω

(10)

(11)

定義10.d為大的奇素?cái)?shù),(a,d)=1,勒讓德符號定義如下:

(12)

y2≡a(modd),y2≡b(modd)

(13)

由公式(12)可得：

(14)

由公式(7)、公式(14)可得：

(15)

(16)

(17)

由公式(15)-公式(17)可得：

(18)

又因?yàn)槎x10中勒讓德符號取值范圍為±1,且d為大的奇素?cái)?shù),故有:

(19)

由公式(12)、公式(19)可知,當(dāng)d為大的奇素?cái)?shù),且a、b都與d互素時(shí),若a、b均為模d的二次剩余,則ab也為模d的二次剩余;同理,若a、b中一個(gè)為模d的二次剩余,一個(gè)為模d的二次非剩余,則ab為模d的二次非剩余.當(dāng)TTPs收到返回的結(jié)果集M后,已知私有信息X中二次非剩余xu,令ζ=i,1≤i≤n,由定義8和公式(11)即可得到要查詢的用戶與第i個(gè)POI的鄰近關(guān)系:

1)當(dāng)f(i)為模d的二次非剩余時(shí),說明g(u,i)=xu·aiu=xu,即aiu=1,即要查詢的用戶與第i個(gè)POI鄰近;

2)當(dāng)f(i)仍為模d的二次剩余時(shí),說明g(u,i)=xu·aiu=1,即aiu=0,即要查詢的用戶與第i個(gè)POI疏遠(yuǎn).

TTPs通過私有信息檢索關(guān)系矩陣得到結(jié)果集M即可得到用戶與各個(gè)POI的鄰近關(guān)系,確定鄰近關(guān)系之后便可對用戶進(jìn)行下一步指引.

主流的基于獨(dú)立架構(gòu)的隱私保護(hù)策略是將處理過的數(shù)據(jù)信息發(fā)送至LBS服務(wù)器,以保證用戶的隱私信息不會(huì)泄露,但是當(dāng)用戶對服務(wù)質(zhì)量要求較高時(shí),LBS服務(wù)器只能根據(jù)客戶端發(fā)送來的處理過的數(shù)據(jù)提供服務(wù),服務(wù)質(zhì)量是有損失的.應(yīng)用二次剩余假設(shè)模型解決了因網(wǎng)絡(luò)環(huán)境的復(fù)雜、用戶行為的不確定等因素而造成的信息損失等問題.

5 關(guān)于K-Vretr中K值的討論

傳統(tǒng)的K匿名隱私保護(hù)方法中,用戶的隱私保護(hù)程度與服務(wù)質(zhì)量受K值的影響.當(dāng)K取值越大,用戶的隱私保護(hù)程度越高,服務(wù)質(zhì)量越低;當(dāng)K取值越小,用戶的服務(wù)質(zhì)量越高,但用戶很容易遭受鏈接攻擊而導(dǎo)致隱私泄露.所以選取一個(gè)可以平衡用戶服務(wù)質(zhì)量與隱私保護(hù)程度的K值,是傳統(tǒng)K匿名隱私保護(hù)方法的關(guān)鍵.

在K-Vretr方法中,K值的選取略有不同.K取值越大,用戶匿名集越大,用戶的隱私保護(hù)程度越高,但因?yàn)閼?yīng)用二次剩余理論模型來保護(hù)查詢隱私,用戶的每次查詢都需要遍歷整個(gè)關(guān)系矩陣,使得用戶的請求服務(wù)效率會(huì)受影響;K取值越小,用戶匿名集越小,關(guān)系矩陣的遍歷速度更快,提供給用戶的服務(wù)質(zhì)量將會(huì)更高.所以用戶的隱私保護(hù)程度、請求服務(wù)效率和服務(wù)器的計(jì)算負(fù)載都與K的取值有關(guān).隨著計(jì)算機(jī)行業(yè)的快速發(fā)展,計(jì)算機(jī)的運(yùn)算能力得到顯著增強(qiáng),已足夠應(yīng)付K取較大值的計(jì)算量,但如果當(dāng)K取非常大的值或用戶查詢請求并發(fā)量特別高時(shí),服務(wù)器仍然可能會(huì)因?yàn)橛?jì)算能力不足而宕機(jī)或計(jì)算時(shí)長過長而導(dǎo)致此次查詢失敗.

此處假設(shè)計(jì)算機(jī)的計(jì)算能力無限.已知定義5中a、b,當(dāng)a為模d的二次剩余時(shí),a當(dāng)且僅當(dāng)取數(shù)列公式(20)中一項(xiàng):

(20)

取模d的絕對值最小的簡化剩余系:

(21)

因?yàn)?-α)2=α2,所以a取值變?yōu)閿?shù)列公式(22)中一項(xiàng):

(22)

(23)

6 計(jì)算與通信開銷分析

6.1 K-Vretr方法的計(jì)算開銷分析

在K-Vretr方法中,以地理信息系統(tǒng)中POI數(shù)據(jù)為基點(diǎn),將不同類的POI利用Delaunay三角剖分算法生成Voronoi圖.考慮現(xiàn)實(shí)生活中POI數(shù)據(jù)的更新并不頻繁,所以采用以犧牲存儲空間來減少服務(wù)器計(jì)算開銷的策略,將這些以不同種類POI進(jìn)行劃分的Voronoi圖提前存儲在TTPs中,且在對POI數(shù)據(jù)進(jìn)行更新時(shí),只需要對相應(yīng)POI類別生成的Voronoi圖進(jìn)行重新計(jì)算即可,大大減少了TTPs的計(jì)算開銷.在隱私保護(hù)過程中,利用Voronoi圖進(jìn)行分割區(qū)間,TTPs需要遍歷一遍POI與用戶的臨近關(guān)系,復(fù)雜度為O(n),雖然計(jì)算開銷呈線性上升,但是結(jié)合之前對POI的種類劃分,已極大降低了查找基數(shù),在保證安全的前提下提高了TTPs的計(jì)算效率,減少了計(jì)算開銷.在對用戶的虛假位置選取時(shí),計(jì)算開銷與K值的取值有關(guān),因?yàn)閂oronoi圖的特性,不需要進(jìn)行最近鄰計(jì)算,雖然計(jì)算開銷會(huì)隨著K值的增加而增長,但整體不會(huì)產(chǎn)生過大變化.

6.2 K-Vretr方法的通信開銷分析

在K-Vretr方法中,根據(jù)不同種類POI劃分的Voronoi圖由LBS與TTPs共同維護(hù),LBS接受用戶匿名集數(shù)據(jù)包,響應(yīng)著用戶請求,因此通信開銷的大小關(guān)系著LBS處理用戶請求的速度,尤其在面對多用戶、高并發(fā)的情況時(shí),LBS的吞吐量直接影響著用戶的服務(wù)質(zhì)量.在形成匿名集的過程中通信開銷隨著匿名集規(guī)模的增加而增大,由于本文采用二次剩余假設(shè)模型,LBS接受到用戶匿名集生成關(guān)系矩陣后,雖然關(guān)系矩陣中記錄著n個(gè)POI與K個(gè)用戶的鄰近關(guān)系,但是TTPs并不需要索引出所有的鄰近關(guān)系,只需從中檢索一條用戶與POI的鄰近關(guān)系即可,這從一定程度上降低了通信開銷,也保證了通信開銷整體并不會(huì)隨著用戶匿名集規(guī)模的增長而大幅提高.

7 安全性分析

隨著使用LBS服務(wù)的用戶人群增長,不法分子針對用戶隱私的攻擊手段也愈加豐富,本節(jié)將對K-Vretr方法在面臨各種攻擊手段時(shí)的安全性進(jìn)行分析.

7.1 抵抗基于地理位置信息的攻擊

基于地理位置信息的攻擊主要是因?yàn)殡[私保護(hù)技術(shù)的不全面,導(dǎo)致生成的ASR中落入了許多不現(xiàn)實(shí)的虛假位置.當(dāng)不法分子發(fā)現(xiàn)虛假位置大量分布在類似湖泊、斷崖之中時(shí),可以很容易排除這些位置,加大了用戶真實(shí)位置泄漏的概率.K-Vretr方法基于現(xiàn)實(shí)中POI生成的ASR可以抵抗這種攻擊手段,因?yàn)楝F(xiàn)實(shí)中的POI位置不會(huì)處于湖泊、斷崖之中,且基于POI生成的V塊中假如包含有類似湖泊之類時(shí),K-Vretr方法也只會(huì)在該區(qū)域中分布一個(gè)虛假位置,避免大量無效虛假位置的產(chǎn)生,對用戶真實(shí)位置泄漏概率的影響幾乎為零.

7.2 抵抗基于用戶背景知識的推理攻擊

基于用戶信息背景知識的攻擊是指攻擊者在已經(jīng)掌握了用戶的基本信息,例如興趣愛好、生活習(xí)慣等基礎(chǔ)上對用戶發(fā)起的隱私攻擊.K-Vretr方法在對用戶發(fā)起的請求服務(wù)應(yīng)答時(shí),每次都會(huì)對用戶請求進(jìn)行Voronoi圖劃分,且用戶請求類型不同,生成的Voronoi圖也會(huì)不同,在整個(gè)隱私保護(hù)過程中,用戶的基本信息從未暴露,攻擊者無法推斷出用戶的請求服務(wù)信息,K-Vretr方法能很好的抵抗此類攻擊.

7.3 抵抗連續(xù)多查詢攻擊

連續(xù)多查詢攻擊是指當(dāng)用戶一段時(shí)間內(nèi)連續(xù)請求服務(wù)時(shí),攻擊者結(jié)合用戶當(dāng)前的移動(dòng)速度及生成的ASR的結(jié)果推斷出用戶的下一次位置.K-Vretr中當(dāng)用戶進(jìn)行連續(xù)查詢時(shí),TTPs每次都會(huì)對用戶位置進(jìn)行判定,用戶每發(fā)起一次查詢,就會(huì)根據(jù)新的V塊重新生成新的虛假信息,每一次的虛假信息以及ASR的更新使得攻擊者無法及時(shí)分析出用戶的任何信息,因此K-Vretr方法在針對連續(xù)多查詢的攻擊時(shí)有著很好的效果,有效保護(hù)了用戶的隱私安全.

7.4 抵抗攻擊者的監(jiān)聽攻擊

監(jiān)聽攻擊主要針對采用分布式點(diǎn)對點(diǎn)架構(gòu)的隱私保護(hù)方法,在該架構(gòu)中,用戶通過P2P協(xié)議自發(fā)組成匿名組,攻擊者可以冒充普通用戶參與匿名組構(gòu)建,如果攻擊者在匿名組中監(jiān)聽組內(nèi)用戶請求,根據(jù)返回的結(jié)果進(jìn)行分析就可以監(jiān)聽到用戶的隱私信息.不同的是,K-Vretr方法采用可信第三方中心架構(gòu),以TTPs作為總載體,完成數(shù)據(jù)的集中化處理,各個(gè)用戶在請求服務(wù)時(shí)互不通信、互不干擾,攻擊者無法監(jiān)聽到其他用戶的任何請求信息.

8 實(shí) 驗(yàn)

實(shí)驗(yàn)將本文所提出的K-Vretr方法與同樣基于K匿名原理的隱私保護(hù)方法(GRAM)進(jìn)行了多次詳細(xì)的對比.GRAM[22]方法構(gòu)建了滿足(k,l)匿名性要求的保護(hù)圖,在保護(hù)圖中標(biāo)識頂點(diǎn),通過不斷添加頂點(diǎn)與邊的方式來滿足用戶隱私要求,緩解了隱私保護(hù)與服務(wù)質(zhì)量的矛盾,與傳統(tǒng)K匿名方法相比確實(shí)存在一定優(yōu)勢,但因?yàn)镚RAM方法在添加頂點(diǎn)過程中并無法排除所有冗余邊,使其在降低匿名效率的同時(shí)也存在一些缺點(diǎn).本文將通過實(shí)驗(yàn)分析K-Vretr與GRAM的區(qū)別及優(yōu)劣.因?yàn)镚RAM已經(jīng)在安全、效率等方面與傳統(tǒng)K匿名方法進(jìn)行了數(shù)據(jù)實(shí)驗(yàn),故本文將不在數(shù)據(jù)對比中加以贅述,而是在理論分析中進(jìn)行說明.

8.1 匿名方法分析

所有的位置隱私保護(hù)方法初衷都是為了給用戶提供一個(gè)安全的服務(wù)環(huán)境,在保證安全的同時(shí)進(jìn)行不斷優(yōu)化迭代,兼顧實(shí)用性、可行性以及服務(wù)器的運(yùn)算開銷.本文將從以下3方面來闡明K-Vretr隱私保護(hù)技術(shù)的性能.

8.1.1 隱私保護(hù)度

1)位置隱私保護(hù).基于K匿名機(jī)制的K-Vretr方法核心思想是TTPs通過LBS對用戶目標(biāo)POI的Voronoi圖構(gòu)建K匿名集,匿名集選取采用全隨機(jī)方式從不同V塊中選取,由于K匿名集中所有用戶的位置均是虛假位置點(diǎn),故LBS只知道用戶處于V塊中,用戶的真實(shí)位置從未暴露,LBS只能利用Voronoi圖的特性查詢最近點(diǎn).

2)查詢隱私保護(hù).TTPs通過私有信息檢索與LBS服務(wù)器通信,因?yàn)楣粽邿o法區(qū)分私有信息中的二次剩余與二次非剩余,所以即便獲取到用戶私有信息X和關(guān)系矩陣F2n,也無法從中捕獲到有價(jià)值的用戶隱私數(shù)據(jù),保證了用戶查詢隱私的安全.

8.1.2 服務(wù)可行性

基于K匿名機(jī)制的K-Vretr方法引用Voronoi圖模型構(gòu)建用戶匿名集,Voronoi圖是基于同類POI所構(gòu)建的.每個(gè)V塊中存在一個(gè)POI,POI越多,V塊越多,關(guān)系矩陣就越大;同樣的,當(dāng)K取值增大時(shí),關(guān)系矩陣也會(huì)增大,因此POI數(shù)量與K值的增加會(huì)導(dǎo)致服務(wù)查詢時(shí)間變長.但是相較于傳統(tǒng)K匿名方法,K-Vretr有著更高的安全性,且隨著現(xiàn)階段計(jì)算機(jī)運(yùn)算能力的提升,基本保證了效率與安全性之間的平衡.

8.1.3 服務(wù)器開銷

本方法中LBS服務(wù)器的作用是根據(jù)TTPs提供的用戶匿名集與POI類別生成相應(yīng)的關(guān)系矩陣,并且負(fù)責(zé)與TTPs進(jìn)行通信.首先,LBS上存儲著不同種類POI劃分的Voronoi圖,LBS的存儲開銷與POI有關(guān);其次,每次發(fā)起服務(wù)請求時(shí)需要遍歷LBS中的關(guān)系矩陣,所以K的取值也會(huì)影響服務(wù)器的運(yùn)算開銷.但是相較于傳統(tǒng)私有信息檢索技術(shù),K-Vretr方法將Voronoi圖提前緩存在本地的處理方式,以空間換取時(shí)間,對并發(fā)量要求較高時(shí)也不會(huì)造成網(wǎng)絡(luò)堵塞.

8.2 實(shí)驗(yàn)對比分析

實(shí)驗(yàn)采用北京市POI類別為餐飲服務(wù)的數(shù)據(jù)集來驗(yàn)證K-Vretr算法性能,數(shù)據(jù)來自高德地圖的POI集,其中包含約10821個(gè)POI.算法采用Python3.8.3編程實(shí)現(xiàn).環(huán)境配置為處理器Intel(R)Core(TM)i7-4710HQ CPU @ 2.50GHz(8 CPUs),～2.5GHz,內(nèi)存4GB,顯卡NVIDIA GeForce GTX 850M,操作系統(tǒng)Windows 10專業(yè)版.如圖4所示,故宮博物館為圓心,方圓5000米區(qū)域內(nèi),按比例縮小后POI的分布情況.

圖4 基于真實(shí)數(shù)據(jù)集的POI分布圖Fig.4 POI distribution map based on real data set

8.2.1 匿名空間與匿名時(shí)間的比較

如圖5(a)所示,將K-Vretr方法中的POI數(shù)量固定,同時(shí)不斷增大K值,隨著匿名空間的面積變大,用戶的隱私保護(hù)程度將會(huì)更高,但無論K取何值,K-Vretr的匿名空間面積始終大于GRAM,且隨著K取值越來越大,兩種方法相差的匿名空間面積也越大.如圖5(b)所示,將POI數(shù)量與ASR固定,K-Vretr方法利用Voronoi圖模型的特性,不需要通過最近距離的算法判定,LBS服務(wù)器存儲當(dāng)前POI劃分下的Voronoi圖,只在POI進(jìn)行變更的時(shí)候才進(jìn)行更新,而GRAM方法因?yàn)樾枰獫M足(k,l)機(jī)制的原因匿名時(shí)間則顯著增加.由此可見,當(dāng)增加匿名集規(guī)模時(shí),2種方法的匿名時(shí)間會(huì)相差更大.

8.2.2 匿名成功率與通信開銷的比較

如圖6(a)所示,將ASR固定,隨著K值的不斷增大,兩種方法的匿名成功率雖整體都保持在一個(gè)較高水平,但K-Vretr方法的匿名成功率仍然高于GRAM方法.GRAM方法需要不斷在基礎(chǔ)圖中加邊來保護(hù)用戶隱私,每一次加邊都要重新計(jì)算,需要做K次整合,所以在匿名成功率上也會(huì)更低.

圖5 匿名空間與匿名時(shí)間的對比Fig.5 Compare anonymous space and anonymous time

如圖6(b)所示,隨著K值增大兩種方法的平均通信開銷均有增加,K-Vretr方法的增加方式較為平緩,這是因?yàn)镵值的增大使用戶在進(jìn)行請求服務(wù)時(shí)需要更多的位置信息來構(gòu)造匿名區(qū);GRAM方法在增加K值時(shí),當(dāng)K達(dá)到某個(gè)節(jié)點(diǎn)值就會(huì)在保護(hù)圖上添加一個(gè)頂點(diǎn)對應(yīng)添加l條邊,所以GRAM算法的增加有平緩有跳躍.從結(jié)果來看,本方法在平均通信開銷上要低于GRAM方法.

圖6 匿名成功率與通信開銷的對比Fig.6 Average communication overhead

8.2.3 POI、K取值的不同對K-Vretr方法的影響對比

如圖7(a)所示,取POI數(shù)量分別為1500、3000、4500、6000、7500、9000,可以看到匿名時(shí)間隨POI數(shù)量的增加而遞增;同時(shí),將POI值保持不變增加K的取值,匿名時(shí)間也會(huì)略微增加.雖然本方案的匿名時(shí)間會(huì)隨著POI數(shù)量與K值的增加而遞增,但整體匿名效率仍控制在較好水平.聯(lián)系現(xiàn)實(shí)生活中當(dāng)同類POI數(shù)量如此之多時(shí),所覆蓋面積已足夠大,這樣的匿名效率足夠保證用戶的服務(wù)質(zhì)量,這也證明了本方法的優(yōu)越性.如圖7(b)所示,取POI數(shù)量分別為2000、4000、6000、8000、10000對隱私保護(hù)程度進(jìn)行試驗(yàn),從實(shí)驗(yàn)中可以看出,當(dāng)K值相等時(shí),POI數(shù)量越多,所生成的Voronoi圖覆蓋面積就越大,構(gòu)造用戶匿名集時(shí)分散性就更高,用戶的隱私保護(hù)程度越高;當(dāng)POI數(shù)量相等時(shí),K值越大,用戶的隱私保護(hù)程度也會(huì)越高,且整體隱私保護(hù)程度保持在較高水平.

GRAM方法較于傳統(tǒng)的隱私保護(hù)方法已經(jīng)證明了他的優(yōu)越性,實(shí)驗(yàn)結(jié)果表明,本文所提出的K-Vretr方法具有比 GRAM方法更好的安全性能與匿名效率.通過在LBS服務(wù)器上存儲Voronoi圖的方式,以空間換取時(shí)間,避免了因大量用戶請求而導(dǎo)致服務(wù)堵塞的情況,進(jìn)一步提升了用戶的隱私安全度,增加了本方法的實(shí)用性.

圖7 POI、K對本方案的影響對比Fig.7 Comparison of the influence of POI and K on this scheme

9 結(jié)束語

基于位置服務(wù)的隱私保護(hù)方法是目前廣受關(guān)注的熱點(diǎn)研究領(lǐng)域.本文提出一種基于K匿名機(jī)制的K-Vretr方法,該方法通過對Voronoi圖模型和二次剩余假設(shè)模型的應(yīng)用,使得用戶被攻擊者識破的概率低于1/K,保護(hù)了用戶的查詢隱私與位置隱私.下一步工作將針對大數(shù)據(jù)時(shí)代服務(wù)的高并發(fā)性,進(jìn)一步提高用戶的查詢效率.