匿名區(qū)域?qū)蛹墧U張的位置隱私保護方法

張 磊, 馬春光, 印桂生

(1. 哈爾濱工程大學計算機科學與技術(shù)學院, 黑龍江 哈爾濱 150001; (2. 佳木斯大學信息電子技術(shù)學院, 黑龍江 佳木斯 154007; (3. 山東科技大學計算機科學與工程學院, 山東 青島 266590)

0 引 言

移動通信技術(shù)和定位技術(shù)的發(fā)展和使用,帶來了用戶對于自身位置隱私的關(guān)注[1-3]。由于在獲得基于位置服務的同時需要用戶提供自身位置給服務提供商,因而很多用戶更關(guān)心在使用過程中自身位置隱私是否安全[3-5]。位置泛化是當前廣泛使用的保護用戶位置隱私的有效方法[6-8],該方法通過尋找真實匿名用戶或添加虛假用戶實現(xiàn)真實用戶與k-1個匿名用戶之間的不可區(qū)分,進而令攻擊者無法準確識別真實用戶[9-10]。但是,在尋找匿名用戶的過程中,現(xiàn)有的隱私保護方法大多以真實用戶為中心,通過對當前用戶位置向周圍擴張的方法尋找匿名用戶或添加噪聲[11-12]。針對這種情況,Yang等人[13]利用區(qū)塊鏈在私有鏈范圍內(nèi)尋找可協(xié)作的匿名用戶。Zhang等人[14]利用屬性加密隨機尋找混合區(qū)域內(nèi)的協(xié)作用戶來實現(xiàn)同一目的。許明艷等人[15]利用用戶鄰域分布感知來確定尋找匿名用戶。Li等人[10]則利用時空的可翻轉(zhuǎn)性來處理匿名用戶的分布問題。Zhang等人[16]同時利用緩存和匿名兩種方案來加強連續(xù)匿名用戶的間隔處理。Peng等人[17]利用希爾伯特曲線和加密手段解決半可信中心服務器處理用戶分布的問題。盡管上述方法在很大程度上能夠解決真實用戶位于匿名區(qū)域中心點的問題,但是若當前區(qū)域內(nèi)用戶離散間距存在差異,即用戶分布較密的情況下很容易在較小區(qū)域內(nèi)完成匿名,進而存在真實用戶位于較小范圍內(nèi)甚至同一興趣點進而暴露用戶隱私的問題。

針對這一問題,本文提出了一種匿名區(qū)域?qū)蛹墧U張的方法,該方法利用希爾伯特曲線對用戶所在區(qū)域用戶分布程度加以量化,同時將量化結(jié)果利用N-階層級的四叉樹進行密度分層,在匿名的過程中利用分層差異實現(xiàn)不以用戶為中心的按密度變化的匿名區(qū)域擴張。該方法一方面解決了用戶位于中心區(qū)域的問題,另一方面通過密度分層,解決用戶密度較高區(qū)域匿名用戶過度集中導致的隱私泄露問題。最后,本文通過安全性分析對算法進行了定性分析和成因描述,同時與當前較為常用的幾種同類算法在隱私保護能力和算法執(zhí)行效率兩個方面進行了實驗比較,其結(jié)果進一步證實了本文所提算法的優(yōu)越性。本文的主要貢獻有:① 提出了一種利用希爾伯特曲線擴張匿名區(qū)域,實現(xiàn)用戶匿名區(qū)域內(nèi)位置不可識別的隨機分布隱私保護方法;② 提出了一種利用N-階位置區(qū)域?qū)蛹壦牟鏄涿芏忍幚矸椒?解決用戶分布過密、用戶易被識別問題;③ 通過理論分析和實驗驗證證明了所提方法的優(yōu)越性。

1 基本思想和算法描述

通常情況下,為保護用戶的位置隱私,已有的隱私保護方法一般以用戶為中心,向該用戶四周擴張式尋找匿名用戶或添加噪聲用戶,以滿足至少存在k-1個用戶與真實用戶相混淆[12, 18-19]。但是,以這種方法建立的匿名區(qū)域易被攻擊者識破并尋找到用戶的真實位置[20-22]。同時由于匿名用戶存在分布密度差異等問題,簡單地利用隨機用戶位置或者隨機網(wǎng)格并不能有效防止攻擊者識別用戶[23-24]。因此,需要提供一種方法，不僅使用戶不再位于匿名區(qū)域中心,而且還要保證參與匿名的用戶位于一個用戶分布密度合理的可選擇分布范圍?；谶@樣一種思想,需要滿足兩個基本條件:首先,用戶的位置應位于攻擊者無法利用歷史經(jīng)驗或距離計算可分析的位置;其次,用戶與匿名用戶位置之間應是一種可調(diào)節(jié)的位置分布狀態(tài)?；谏鲜鰞蓚€基本條件,本文提出了匿名區(qū)域?qū)蛹墧U張的隱私保護方法。

該隱私保護方法的基本思想是:通過處理使用戶不再位于匿名區(qū)域的中心位置,而且是不可猜測的隨機位置,同時不會因用戶分布密度的不均勻使得匿名區(qū)域過小。為實現(xiàn)上述隱私保護思想,一種簡單的處理方法是以用戶為固定位置,向四周隨機擴張匿名區(qū)域,使用戶位于匿名區(qū)域中的不確定位置。但是僅通過隨機位置擴張并不能解決匿名用戶分布過密的問題,因此在這種隨機擴張的同時,還需要考慮用戶分布密度,使匿名用戶集合內(nèi)均勻分布,防止匿名用戶過度集中導致的真實位置被識別的問題。針對這樣兩個基本要求,本文利用網(wǎng)格區(qū)域的隨機擴張來完成用戶位置隨機性的處理,同時利用層級擴張的密度四叉樹來處理用戶分布密度問題。

基于上述基本思想,本文所提算法的處理過程可以簡要描述如下。首先,用戶提交查詢信息Q={R,c,k}給匿名服務器,其中R為用戶所在區(qū)域,c為查詢內(nèi)容,k為匿名值。匿名服務器在收到用戶提交的查詢信息之后,查詢R內(nèi)用戶密度,并添加到四叉樹的第0層。若密度過高,則以R為初始區(qū)域繪制希爾伯特曲線并擴張一層區(qū)域空間,同時將擴張后的4個網(wǎng)格密度添加到四叉樹第1層的節(jié)點內(nèi)。在四叉樹第1層隨機選擇一個節(jié)點,并與第0層的節(jié)點共同計算兩個節(jié)點區(qū)域的用戶密度。若密度合適則在上述兩個區(qū)域內(nèi)選擇匿名用戶,否則重復上述操作完成新一輪的區(qū)域擴張直至密度合適為止。這種區(qū)域擴張的處理如圖1(a)所示,完成匿名空間設定后,所選擇的匿名用戶分布如圖1(b)所示。在擴張過程中的密度存儲和選擇使用的四叉樹如圖2所示。

圖1 匿名區(qū)域選擇Fig.1 Anonymous region selection

圖2 層級擴張的四叉樹密度表示Fig.2 Quad tree density representation of hierarchical expansion

在這種層級擴張的情況下,攻擊者僅能獲得一個用戶密度分布均勻的擴張后區(qū)域,同時由于真實用戶并不位于該區(qū)域的中心,攻擊者同樣無法判定真實用戶的具體位置。

由于區(qū)域擴張過程需要多次計算用戶密度,同時每個擴張后的區(qū)域需要保持一種不確定性,因此本文引入四叉樹來處理用戶密度。假設用戶位于圖1(a)所示的網(wǎng)格0中,將該網(wǎng)格密度帶入圖2所示的四叉樹,有第0層密度為27,當前密度過高,因此利用希爾伯特曲線進行區(qū)域擴張,并將擴張后的4個區(qū)域密度添加進四叉樹第1層的節(jié)點中。在第1層隨機選擇一個節(jié)點(密度為17的節(jié)點),計算這兩個節(jié)點的用戶密度。若當前密度仍然過高,需重復上述操作,擴張到第2層和第3層后,用戶密度合適,算法完成計算。此時圖2所示的四叉樹中深色節(jié)點表示區(qū)域選擇時的密度值計算,對應圖1(a)中區(qū)域編號為0,2,6,8構(gòu)成的混合區(qū)域,在這些區(qū)域中尋找匿名用戶,則有圖1(b)所示的匿名用戶分布情況。

最后,在完成層級擴張的匿名用戶選擇之后,用戶的真實位置因希爾伯特曲線方向的差異而可能位于該區(qū)域內(nèi)的任一位置,攻擊者很難通過中心位置猜測以及用戶密度來計算分析用戶的真實位置。

2 算法實現(xiàn)

算法 1 匿名區(qū)域?qū)蛹墧U張算法輸入:用戶初始區(qū)域R0,當前區(qū)域用戶密度D0輸出:擴張后區(qū)域RN1. 獲得R0內(nèi)用戶密度D0;2. Dt=0; 3. while (Dt+D0不滿足密度要求)4. 利用希爾伯特曲線擴張區(qū)域;5. 計算擴張后每個單元格密度并帶入四叉樹;6. 隨機選擇新一層四叉樹節(jié)點密度帶入Dt;7. 選擇的節(jié)點所表示的區(qū)域記為Rt;8. RN=R0+Rt;9. end while10. 獲得擴張后區(qū)域RN;11. 在RN中執(zhí)行匿名用戶選擇算法; 在算法1中嵌套使用了四叉樹來處理節(jié)點密度,算法2給出了四叉樹的密度添加和節(jié)點選擇的過程。算法 2 四叉樹算法輸入:擴張后網(wǎng)格內(nèi)用戶密度Dg11,Dg21,…,Dg41輸出:密度四叉樹1. root=D0;2. for(i=1;i≤4;++i)3. root.child=Dgi;4. end5. root=隨機選擇root.child;∥隨機選擇一個葉節(jié)點作為新的根節(jié)點6. Dt為該節(jié)點密度;7. 將D0和Dt反饋給算法1;

經(jīng)過算法1和算法2的共同處理,一個可以滿足用戶位置不在中心區(qū)域,且匿名區(qū)域內(nèi)用戶密度合適的擴張匿名區(qū)域形成。但是僅有這樣的一個區(qū)域仍不能有效保護用戶的位置隱私,還需要在該區(qū)域內(nèi)按照密度要求在不同的密度網(wǎng)格空間尋找匿名用戶。

由于匿名區(qū)域擴張所產(chǎn)生的每個單元格是按照用戶所在位置利用希爾伯特曲線連接的,因此在地理位置上較為相近,進而也就造成了用戶密度的相似性,這種相似性表現(xiàn)為希爾伯特曲線經(jīng)過的網(wǎng)格編號越小用戶密度越相近,因此可利用網(wǎng)格編號來標識用戶密度,進而在匿名用戶或者噪聲的選擇上實現(xiàn)用戶密度的均勻分布。匿名用戶選擇算法給出了在建立好的擴張后的匿名區(qū)域中如何選擇更具泛化性的匿名用戶的處理方法。

算法 3 匿名用戶選擇算法輸入:希爾伯特曲線標記的網(wǎng)格編號N={n0,n1,…,nm},用戶設定匿名值k,候選用戶集合U={u1,u2,…,ut}輸出:匿名用戶集合U'1. avg= ∑mi=1ni /m;2. U'.N=0; ∥匿名用戶所在區(qū)域網(wǎng)格編號初始值3. while(i<=k&&U'.N≤avg)4. U'依次添加每個單元格中的隨機用戶;5. i=i+1;6. end7. if(U'.N≥avg)8. 用網(wǎng)格編號高的區(qū)域內(nèi)用戶替換編號低的用戶;9. end10. 輸出U';

經(jīng)過算法3的處理可得到滿足密度要求的匿名用戶,這些用戶均勻分布在擴張后的匿名區(qū)間內(nèi),同時用戶本身也不再位于匿名區(qū)域中心位置,而是位于該區(qū)域內(nèi)不確定的任意位置,因而用戶的位置隱私得到了保護。

統(tǒng)籌推進，振興鄉(xiāng)村。在做好項目區(qū)建設的同時，增加發(fā)展要素，努力推進鄉(xiāng)村振興樣板區(qū)、綠色產(chǎn)業(yè)集聚區(qū)、生態(tài)文明示范區(qū)、美好生活共享區(qū)建設。

3 安全性分析

通過對本文算法的描述,可知該算法的安全性取決于用戶是否位于匿名區(qū)域中心以及用戶分布密度和不確定性是否均勻兩個方面。

對于用戶分布密度和不確定性,在不擴張或擴張的情況下,算法的首要條件是滿足挑選的匿名用戶分布密度的均勻性,因此才要利用希爾伯特曲線編號和四叉樹選擇節(jié)點,所以經(jīng)過算法處理得到的匿名區(qū)域是一個用戶密度分布較為均勻、不會產(chǎn)生用戶集中于同一有限區(qū)域的情況。同時,通過算法3,在擴張后的區(qū)域內(nèi),所有的匿名用戶都具有很強的隨機性,這種隨機性也加大了攻擊者對真實用戶的不確定性,因而算法在隱私安全方面能夠提供較好的隱私保護服務。

4 實驗驗證

為了驗證本文所提算法能夠較好地在一個擴張的區(qū)間內(nèi)有效尋找匿名用戶,同時又不會因用戶密度分布問題泄露用戶的位置隱私,將本文算法與當前一些同類的主流算法進行了實驗比較。實驗測試的環(huán)境為筆記本電腦CORE i7,8 GB內(nèi)存,測試系統(tǒng)為Windows 10操作系統(tǒng)。實驗采用模擬測試,使用Matlab 2017a對收集到的用戶位置數(shù)據(jù)展開測試。測試的數(shù)據(jù)集合為公共數(shù)據(jù)集BerlinMOD Data Set在某一時刻的位置定位數(shù)據(jù)采樣,用戶密度計算結(jié)果均來自該采樣數(shù)據(jù)。參與比較的算法選擇了利用屬性基加密選擇匿名用戶的基于同態(tài)加密的屬性泛化混合區(qū)域(homomorphic encryption based attribute generalization mix-zone, HEBAG mix-zone)算法[14],利用范圍感知選擇匿名用戶的個性化范圍敏感隱私保護方案(personalized range-sensitive privacy-preserving scheme, PRPS)[25]以及傳統(tǒng)的以用戶為中心的中心區(qū)域擴張算法(簡稱為傳統(tǒng)算法)[26]。實驗將從真實用戶所處位置的隨機性、匿名用戶分布密度差異性、攻擊者識別真實用戶的成功概率、算法執(zhí)行時間以及匿名區(qū)域范圍等幾個方面加以比較。實驗結(jié)果比較和簡要成因分析將進一步證明本文所提算法的隱私保護能力和算法執(zhí)行效率。

圖3給出了經(jīng)過各種算法處理后真實用戶位置的隨機性比較，是對多次請求匿名的用戶位置在匿名區(qū)域中相對位置的重合概率計算得到的,即重合率越高真實用戶位置的隨機性越差。

圖3 真實用戶位置隨機性Fig.3 Randomness of real user location

從圖3中可以看出,由于傳統(tǒng)算法中用戶位置一般位于匿名區(qū)域中心,因此其相對位置重合率最高。PRPS算法是通過查詢概率估算的區(qū)域擴張完成匿名的,但是在每個確定區(qū)域中,用戶所處位置仍以較高概率位于該區(qū)域中心,因此當匿名請求次數(shù)超過70次時,其相對位置重合率趨于飽和,保持在90%左右。HEBAG mix-zone算法采用的是隨機尋找屬性相似用戶的方法,即使用戶的相對位置存在部分變化,但由于是呈擴散性的協(xié)作用戶參與匿名,因此位于匿名區(qū)域中心的概率仍然很高,但要好于傳統(tǒng)算法和PRPS算法。最后,本文所提算法主要針對的就是用戶的真實位置位于匿名區(qū)域中心的問題,經(jīng)過算法處理后用戶的真實位置將會隨機分布在匿名區(qū)域的任意位置,因此其相對位置重合率最低,在隱私保護能力方面要好于參與比較的其他3種算法。

圖4給出了經(jīng)過各種算法處理后匿名用戶在匿名區(qū)域中的分布差異,這種差異表現(xiàn)在匿名用戶所處匿名區(qū)域中的密度差異,因此密度差異比例越大說明當前匿名區(qū)域包含更多類型的匿名用戶,真實用戶的隱私保護級別越高。

圖4 匿名用戶分布密度差異Fig.4 Distribution density difference of anonymous users

從圖4中可以看出,本文算法產(chǎn)生的密度差異比例最大,這是由于該算法經(jīng)過希爾伯特曲線的刻畫,覆蓋了更為廣闊的匿名區(qū)域,同時由于在不同擴張區(qū)域中選擇匿名用戶,參與匿名的用戶可來自于不同密度區(qū)域中的不同用戶,因此其密度差異極大。HEBAG mix-zone算法由于相似屬性用戶隨機分布的特性使得其能夠找到部分位于不同密度區(qū)域的協(xié)作用戶參與匿名,但跨越的密度差異區(qū)域有限。PRPS算法查詢概率估算的區(qū)域擴張同樣能夠包括部分差異密度區(qū)域的匿名用戶,但單個匿名區(qū)域未能產(chǎn)生密度差異。最后,傳統(tǒng)算法一般以用戶為中心尋找匿名用戶,通常選擇的都是當前用戶最近鄰用戶參與匿名,其密度差異最低。

圖5給出了攻擊者通過匿名區(qū)域范圍以及用戶相對位置對不同算法展開攻擊從而識別真實用戶的概率差異。

圖5 攻擊者識別真實用戶的成功概率Fig.5 Success probability of attacker identifying real user

從圖5中可以看出,傳統(tǒng)算法僅通過這兩項標準被攻擊識別的概率最高,且不能隨著匿名用戶數(shù)量的增加而降低,這是由于傳統(tǒng)算法一般需真實用戶位于匿名區(qū)域中心。PRPS算法同樣由于真實用戶位于擴張的匿名區(qū)域中心而導致攻擊成功率相對較高。HEBAG mix-zone算法雖然能夠通過隨機屬性降低用戶相對位置影響,但是由于HEBAG mix-zone內(nèi)匿名用戶有限,因而其攻擊成功率雖然低于PRPS算法,但仍高于本文算法。最后,本文算法一方面解決了用戶密度分布的問題,使真實用戶可能位于匿名區(qū)域中的任意位置；另一方面，采用的四叉樹N-階層級擴張,又將匿名區(qū)域進行了擴充,因而其保護下的真實用戶被攻擊者識別的概率最低。

圖6給出了在一般情況下各算法的執(zhí)行時間。從圖6中可以看出,所有算法均隨著匿名用戶數(shù)量的增加導致算法執(zhí)行時間增長。在眾多算法中,HEBAG mix-zone算法的執(zhí)行時間最高,這是由于該算法需要利用移動設備去完成加解密操作,因此尋找時間相對較高。其次是傳統(tǒng)算法,因傳統(tǒng)算法主要是在一個受限的匿名區(qū)域中尋找匿名用戶,當該區(qū)域用戶數(shù)量較少時耗費的尋找時間相對較多。PRPS算法雖然可以通過區(qū)域擴張尋找匿名用戶,但是這種擴張是在完成查詢概率計算之后才被執(zhí)行,仍存在傳統(tǒng)算法的弊端,但要好于傳統(tǒng)算法。本文算法由于利用希爾伯特曲線包含了最大匿名用戶尋找區(qū)間,提升了匿名用戶尋找效率,因此其算法執(zhí)行時間最低。

圖6 算法執(zhí)行時間Fig.6 Algorithm running time

圖7給出了不同算法產(chǎn)生的匿名區(qū)域范圍。從圖7中可以看出,傳統(tǒng)算法并不因匿名用戶數(shù)量的變化產(chǎn)生較大的匿名區(qū)域變化,這主要是因為傳統(tǒng)算法一般在有限的區(qū)域內(nèi)不考慮用戶差異以及用戶分布,直接選取了大量用戶,且這些用戶位于同一較小區(qū)域的概率極高,因而其匿名區(qū)域范圍始終保持一種較低狀態(tài)。HEBAG mix-zone算法雖然隨機選擇用戶,但是HEBAG mix-zone的范圍有限,因此該算法雖然好于傳統(tǒng)算法,但是仍存在提升空間。PRPS算法利用查詢概率計算提升了區(qū)域擴張能力,但是在單次查詢中其匿名范圍仍然有限。本文所提算法主要是一種區(qū)域擴張算法,利用希爾伯特曲線建立了最廣闊的匿名區(qū)域空間,因此在匿名區(qū)域上要好于其他算法。

圖7 匿名區(qū)域范圍Fig.7 Anonymous region range

5 結(jié) 論

傳統(tǒng)的基于位置服務的隱私保護算法在尋找匿名用戶時,由于尋找策略問題使得真實用戶位于中心位置的概率過高,且當前流行的一些改進方法對這一問題的解決有限。因此,針對這一問題,提出了匿名區(qū)域?qū)蛹墧U張的位置隱私保護算法。該算法利用希爾伯特曲線結(jié)合N-階層級四叉樹的離散差異計算,建立了最廣泛的匿名區(qū)域,同時由于通過層級遞進擴張匿名區(qū)域,使得真實用戶位置產(chǎn)生了最大的不確定性,因此相對于傳統(tǒng)算法能夠更好地保護用戶位置隱私。在利用模擬實驗對該方法與其他幾種同類算法的比較中可以看出,該算法相對于同類算法不僅在隱私保護能力方面具有優(yōu)勢,在算法執(zhí)行效率方面同樣要好于同類算法,因而更具部署優(yōu)勢。