匿名區域層級擴張的位置隱私保護方法

張 磊, 馬春光, 印桂生

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

0 引 言

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

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

1 基本思想和算法描述

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

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

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

圖1 匿名區域選擇Fig.1 Anonymous region selection

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

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

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

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

2 算法實現

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

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

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

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

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

統籌推進，振興鄉村。在做好項目區建設的同時，增加發展要素，努力推進鄉村振興樣板區、綠色產業集聚區、生態文明示范區、美好生活共享區建設。

3 安全性分析

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

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

4 實驗驗證

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

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

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

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

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

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

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

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

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

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

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

圖6 算法執行時間Fig.6 Algorithm running time

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

圖7 匿名區域范圍Fig.7 Anonymous region range

5 結 論

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