m叉平均樹的差分隱私位置隱私保護方法

胡德敏,廖正佳

(上海理工大學 光電信息與計算機工程學院,上海 200093)

1 引 言

隨著手持設備的日益普及,基于位置的應用程序和服務可以訪問準確和實時的位置信息,在用戶發(fā)送查詢請求過程中難免會存在個人位置隱私泄露的問題.

許多基于k-匿名[1,2]置隱私保護方法已被證明不能充分保護LBS隱私,容易受到人口分布密度、背景知識攻擊等影響.差分隱私[3,4]能使數(shù)據(jù)集的計算結(jié)果對元素的變化不敏感,因此由于數(shù)據(jù)集的加入而導致個別元素隱私泄露的風險被控制在可接受范圍內(nèi).差分隱私具有堅實的數(shù)學基礎;嚴格定義隱私保護并提供定量評估方法,逐漸成為LBS隱私保護領域的熱門話題.但在連續(xù)的位置查詢服務時,容易造成疊加噪聲導致查詢精度下降.

針對以上問題,本文在Hilbert曲線構(gòu)建的k-匿名集的基礎上,提出了基于m叉平均樹的差分隱私位置隱私保護方法(m-Ary Average Tree Differential Privacy,MATDP).該方法通過引入m叉平均樹結(jié)構(gòu)拆分匿名集數(shù)據(jù)以增強數(shù)據(jù)效用,主要提出了經(jīng)過嚴密推導得出的具有較小誤差上界的拉普拉斯隱私預算分配策略.該隱私預算分配策略能有效控制連續(xù)查詢環(huán)境下噪聲疊加問題,在保證隱私保護強度的同時降低連續(xù)查詢誤差.實驗結(jié)果表明,相較于其他位置隱私保護方法,該方法能在一定查詢范圍內(nèi)減小連續(xù)查詢誤差,并且在同類提高查詢精度的差分隱私算法中具有較高運行效率.

2 相關(guān)工作

位置隱私保護主要有三大方面:位置匿名、位置加密、位置擾動.

位置匿名被大量討論和應用,k-匿名機制是位置匿名的典型代表.文獻[5]提出的模型能支持具有上下文敏感的個性化隱私要求的廣泛用戶的位置k-匿名,從而使每個移動節(jié)點能夠指定最低匿名等級以及最大時間和空間分辨率.但該匿名集中位置元素不滿足互惠性[6],攻擊者通過連續(xù)查詢的匿名集求交后得到用戶實際位置.文獻[7]通過細化確定同一匿名集中移動用戶的匿名空間是否相同,并且刪除交集后的兩個匿名空間是否為單一路徑來保證互惠性.由于k-匿名機制容易受限于人口密度的分布,文獻[8,9]以網(wǎng)格模式生成虛擬位置,同時考慮真實環(huán)境中的人口分布密度.總體而言,k-匿名有兩個方面的制約因素,一方面匿名集中需要找代理用戶與匿名服務器間的通訊[10]或用戶間的對等協(xié)作,信任機制在這種模型中發(fā)揮著重的作用,信任的評估和量化變成一大挑戰(zhàn);另一方面k-匿名機制無法應對背景知識攻擊,攻擊者獲得的背景知識是無法量化和建模的.因此單一的位置匿名方法隱私保護強度過低.

位置加密的密碼學技術(shù)在位置隱私問題中得到了廣泛的應用,隱私信息檢索技術(shù)(PIR)[11],保證LSP在無法知曉查詢內(nèi)容和查詢結(jié)果的同時完成查詢工作.密碼技術(shù)在定位隱私保護方面更為徹底和安全,理論上完全消除了攻擊者的威脅,但密碼學方法的缺點是計算復雜度高,對硬件要求較高.

差分隱私位置保護方法因其具有嚴格推理和證明的隱私保證,成為位置擾動中的一個常被應用的方法.在沒有任何關(guān)于攻擊者先前知識的假設情況下,地理不可區(qū)分[12]使用差分隱私來擾亂真正的用戶位置.在LBS應用中,連續(xù)查詢環(huán)境時噪聲會累加到每次查詢上,產(chǎn)生的噪聲量會影響查詢精度和數(shù)據(jù)的可用性.如何在隱私保護和查詢精度之間獲得較好的權(quán)衡,是學者們一直在努力的方向.文獻[13]基于小波變換的差分隱私方法,該方法把數(shù)據(jù)映射成小波樹后添加噪聲,但映射成小波樹后會出現(xiàn)大量為零的值需要進一步壓縮,增加了算法復雜度.文獻[14]提出PriLocation模型,將實際位置劃分到k個集合中,統(tǒng)計集合的訪問頻次,再對k個集合添加噪聲,由于集合數(shù)一定小于單個位置數(shù)量,所以噪聲的添加會減少,但實際查詢準確率不高.文獻[15,16]提出了將樹結(jié)構(gòu)加入差分隱私的方法,缺點是劃分不穩(wěn)定會造成劃分結(jié)構(gòu)不均勻的情況.文獻[17]通過迭代的方式往樹的層次中添加噪聲,雖然降低了查詢誤差,然而在有些層次中不滿足一致性約束[18].如何設計一個適合于移動設備在連續(xù)查詢環(huán)境下的位置隱私保護方法,是本文要解決的關(guān)鍵問題.

單一的k-匿名機制,由于缺乏抵抗背景知識攻擊的能力,需要與其他位置隱私保護方法結(jié)合使用.從另一角度來看,若僅使用差分隱私位置保護方法擾動單個位置,依據(jù)定義可知,LSP查詢數(shù)據(jù)集時會導致對單個記錄的變化敏感度較低,使得LBS服務沒有意義[26].差分隱私更適用于對數(shù)據(jù)集信息的擾動,因此本文將k-匿名機制與差分隱私技術(shù)相結(jié)合.

對于當前差分隱私位置保護方法中存在的噪聲累加導致查詢精度過低的情況,本文在Hilbert曲線劃分的k-匿名機制基礎上,提出基于m叉平均樹的差分隱私位置隱私保護方法.該方法使用m叉平均樹結(jié)構(gòu)來拆分數(shù)據(jù)以增強數(shù)據(jù)效用,并經(jīng)過嚴格數(shù)學推導,使得隱私預算的分配存在較小噪聲方差上界,在相同的隱私水平下提高了數(shù)據(jù)查詢的準確性和數(shù)據(jù)效用.

3 相關(guān)概念

差分隱私

差分隱私保證數(shù)據(jù)的發(fā)布結(jié)果不會因任何特定個體的存在而發(fā)生顯著變化.對于數(shù)據(jù)是數(shù)值類的情況,最普遍的機制是將從拉普拉斯分布中抽取的受控隨機噪聲添加到查詢輸出中.噪音量與隨機函數(shù)的靈敏度相關(guān)聯(lián).

定義1.ε-差分隱私.對于任何兩個數(shù)據(jù)集D和D′,至多包含一個不同的記錄,對任意輸出S?Range(f)滿足:

Pr[f(D)∈S]≤eε×Pr[f(D′)∈S]

則算法f滿足ε-差分隱私.

隱私預算ε影響隱私保護程度,ε越小,f(D)與f(D′)的概率密度函數(shù)相似度越大,隱私強度也越大,數(shù)據(jù)可用性降低(即查詢精度降低).本文目標是通過對隱私預算ε的合理分配,謀求在隱私保護強度與查詢精度之間的平衡.

Δf為f的敏感度,是數(shù)據(jù)集D中任何單個元組變化時f中的最大變化,即:

根據(jù)定義3可知,同一數(shù)據(jù)集下多個差分隱私的組合會導致隱私參數(shù)ε和方差的累加.因此,在連續(xù)查詢情況下,每個興趣點噪聲的累加的確會帶來較大的查詢誤差.

4 基于m叉平均樹的差分隱私位置隱私保護方法

4.1 整體框架

本文提出的位置隱私保護架構(gòu)由客戶端、匿名服務器(Anonymous Server,AS)和位置服務提供商(Location Service Provider,LSP)組成,如圖1所示.

圖1 整體框架圖Fig.1 Overall framework

1)客戶端.客戶發(fā)送實時查詢請求Q=(分別表示用戶身份信息,用戶真實位置,查詢內(nèi)容以及時間戳)給AS進行匿名操作.

2)匿名服務器AS.出于對移動客戶端的計算能力和存儲負載的考慮,引入匿名服務器進行匿名操作.匿名服務器能實現(xiàn)大規(guī)模計算,處理大量用戶頻繁的位置更新操作(特別是在連續(xù)查詢環(huán)境中)以及細化查詢結(jié)果.缺點是匿名服務器掌握了移動用戶相關(guān)的位置信息,成為系統(tǒng)處理的瓶頸,攻擊時會導致用戶隱私泄露.出于對系統(tǒng)安全性考慮,要求AS掌握查詢請求中的loc數(shù)據(jù),而無法獲知真實的查詢內(nèi)容(防止背景知識攻擊).

3)位置服務提供商LSP.LSP負責處理查詢,僅掌握content數(shù)據(jù)以及擾動后的匿名空間區(qū)域(Anonymous Space Region,ASR)數(shù)據(jù),無法獲知相關(guān)身份信息.完成查詢操作后,將候選結(jié)果集R發(fā)送給AS.

具體步驟如下:

1)用戶將查詢請求Q=發(fā)送給AS.

2)AS獲取Q中的位置信息loc,利用初始匿名集生成模塊生成初始k-匿名集;匿名集擾動模塊利用m叉平均樹差分隱私保護方法對k-匿名集中的興趣點進行擾動,最終生成ASR.將擾動后的查詢請求Q′發(fā)送給LSP.

3)LSP獲取Q′中的查詢信息content以及ASR,完成查詢操作后返回給AS候選結(jié)果集R.

4)AS利用結(jié)果篩選模塊篩選出精確結(jié)果集(Exact Result Set,ERS),返回給客戶端.

4.2 生成初始k-匿名集

使用基于密度劃分的Hilbert曲線[21,22]將興趣點映射到一維.Hilbert曲線的優(yōu)勢是,在將二維空間數(shù)據(jù)映射到一維時,在二維空間上鄰近的點在Hilbert曲線上依然保持鄰近.考慮到興趣點分布密度的因素,首先對區(qū)域進行四分樹劃分,使每個單元內(nèi)的興趣點個數(shù)不大于閾值δ,如圖2所示(圖中設δ=1);其次將興趣點依據(jù)Hilbert值(H值)從小到大排序;最后,為了滿足匿名集的互惠性,將排序后的興趣點基于桶的劃分得到k-匿名集.

定義4.互惠性[6].相同匿名集中的任意兩個元素a1,a2,若a1,a2分別構(gòu)造的匿名集Sa1,Sa2,滿足Sa1=Sa2,則稱此匿名集具有互惠性.

圖2 基于密度劃分的Hilbert曲線Fig.2 Hilbert curve based on density division

例如,圖2中離用戶實際位置最近的興趣點為P9,若k=3,Hilbert曲線填充后,興趣點依據(jù)從小到大排序并基于桶的劃分后得到:

P1,P2,P7P8,P9,P4P5,P6,P10P13,P15,P12P11,P14,P3

P9所在匿名集為,陰影部分為匿名區(qū)域.從圖中可以看出形成的匿名區(qū)域較大(包含的單元格較多,后期噪聲累加后會產(chǎn)生較大的查詢誤差),需要進一步優(yōu)化.

為了優(yōu)化Hilbert曲線生成的匿名區(qū)域.通過改變曲線的起始點和方向,生成多種Hilbert曲線(本文只考慮8種Hilbert曲線,即4種起始點×2種方向),篩選出匿名區(qū)域最優(yōu)的匿名集作為最終的匿名集.如圖3所示,由該Hilbert曲線獲得的匿名區(qū)域明顯優(yōu)于原始曲線生成的匿名區(qū).

4.3 匿名集的差分擾動

本文用提出基于m叉平均樹的差分隱私方法,對形成的初始匿名集添加拉普拉斯噪聲擾動.通過引入m叉平均樹的數(shù)據(jù)結(jié)構(gòu),推導出具有較小誤差上界的隱私預算分配方法降低噪聲.

圖3 改變后的Hilbert曲線Fig.3 Changed Hilbert curve

4.3.1 構(gòu)建M叉平均樹

定義5.廣義敏感度[23].設有函數(shù)集F,其中f∈F,W為f的權(quán)重函數(shù),函數(shù)f關(guān)于權(quán)重函數(shù)W的廣義敏感度為滿足以下式子中ρ的最小值:

∑f∈F(W(f)·|f(D)-f(D′)|)≤ρ·‖D-D′‖1

(1)

其中‖D-D′‖1=∑v∈D-D′|v|.

定義6.函數(shù)f關(guān)于權(quán)重函數(shù)W的廣義敏感度為ρ,若算法A在數(shù)據(jù)集D的輸出為{f(D)+X(f)},其中X(f)服從拉普拉斯分布λ/W(f)的隨機噪聲,那么算法A滿足(2ρ/λ)-差分隱私.

定義7.m叉平均樹.m叉平均樹中,除葉子節(jié)點以外,每個節(jié)點有m個孩子,內(nèi)部節(jié)點的值為其孩子節(jié)點的平均值.

例如,當匿名集中興趣點個數(shù)為7(以圖3中Hilbert曲線值為例),給定高度h的值為3,則m=2,生成的平均樹如圖4.

圖4 m叉平均樹Fig.4 M-ary average tree

根據(jù)公式(1)和權(quán)重函數(shù)W(f)=mi計算出m叉平均數(shù)的廣義敏感度.設匿名集D上的元素值被改變了δ,則其葉節(jié)點及該葉節(jié)點的祖先節(jié)點也會被改變,共有h+1個節(jié)點值被改變,深度為i的節(jié)點被改變的大小為δ/mi,將此代入公式(1),得到關(guān)于權(quán)重函數(shù)的廣義敏感度為:

4.3.2 隱私預算分配

4.3.3 查詢誤差上界推導

本文用方差E(Q)表示查詢請求Q的誤差度量.由定義3可知,噪聲是在每個節(jié)點添加的,由此產(chǎn)生的誤差為每層產(chǎn)生的方差之和,即:

(2)

根據(jù)柯西不等式,

(3)

通過整理可得:

(4)

將公式(4)代入公式(3)得到:

(5)

由此得到了每層節(jié)點需要添加噪聲的隱私參數(shù)εi.

因為查詢誤差:

由式(5)可以得出誤差的最大值:

基于m叉平均樹的差分隱私位置保護方法的整體算法如下:

算法.基于m叉平均樹的差分隱私位置保護算法

輸入:用戶u所在的二維空間G,閾值δ,匿名集參數(shù)k

輸出:擾動后的匿名區(qū)域ASR,匿名集u.s

1.if(G.POI.count

2.return ERROR;

3.else

4.G劃分為4個子區(qū)域Gi;

5.for i=1 to 4

6.if(Gi.POI.count>δ)

7.do step 4;

8.else 結(jié)束區(qū)域G的劃分;

9.end for

10.end else

11.end if

12.G中填充Hilbert曲線;

13.order(H(G.POI));//將興趣點的Hilbert值排序

14.基于桶的劃分k-匿名集;

15.ASR=Area(u.s);//記錄下u所在的匿名集形成匿名區(qū)域

16.for i=1 to 8

17.改變Hilbert曲線的起始點或方向;

18.do step 13 to 15;

19.if(Area(u.s′)

20.ASR=Area(u.s′);

21.u.s=u.s′;u.s′=NULL;//保留當前匿名集和匿名區(qū)域

22.end if

23.end for

26.將平均樹中前u.s.count個葉子節(jié)點的值依次賦給u.s中的每個元素.

5 實驗結(jié)果與分析

本文針對查詢誤差和算法運行效率對MATDP算法進行對比分析.基于Hilbert曲線生成匿名集的部分,在匿名服務器離線狀態(tài)下生成,即離線狀態(tài)下根據(jù)既定的閾值δ劃分網(wǎng)格,填充8種Hilbert曲線,并按H值的大小排序興趣點.影響查詢誤差的因素有很多方面,如網(wǎng)格劃分閾值δ、匿名集規(guī)模k、匿名區(qū)域大小、樹高h、隱私預算ε以及興趣點分布密度等.因此實驗不僅從以上幾個因素測試,也要與其他算法比較該算法的查詢誤差和運行效率.

5.1 實驗數(shù)據(jù)與環(huán)境

實驗環(huán)境為Inter?CoreTMi5,windows7操作系統(tǒng),8GB內(nèi)存,算法是Eclipse環(huán)境下基于Java編寫.

實驗選擇兩個數(shù)據(jù)集進行,第一個數(shù)據(jù)集為infochimps大數(shù)據(jù)網(wǎng)站提供的美國48個大陸州的地標位置組成的地標,實驗中簡稱為“l(fā)andmark” 數(shù)據(jù)集,數(shù)據(jù)分布較密集,約有870k個數(shù)據(jù)點.第二數(shù)據(jù)集為美國存儲設施位置數(shù)據(jù),包括國家連鎖存儲設施,以及本地擁有和運營的設施,數(shù)據(jù)集較小,約有9000個數(shù)據(jù)點,簡稱為“storage”數(shù)據(jù).兩個數(shù)據(jù)集的密度和稀疏度是顯而易見的,因此可以用這兩個數(shù)據(jù)集來驗證本文的方法對不同密度環(huán)境因素的影響.

實驗中將平均方差作為查詢誤差的衡量標準:

其中q(D)為真實位置的查詢結(jié)果,q(D′)為加噪后的查詢結(jié)果,|Q|為匿名集大小.用移動對象生成器[25],生成速度為30km/h的300個移動用戶,設查詢總時間為30min,查詢間隔為5min,因此所有用戶一共要發(fā)起1800次的連續(xù)查詢.

5.2 網(wǎng)格劃分閾值δ在不同匿名區(qū)大小中對查詢誤差的影響

該實驗中取k=180,ε=1,h=3.比較不同密度環(huán)境下δ對查詢誤差的影響(實驗中δ的最小取值要使得最小單元格不小于1km2).q1～q8為8種Hilbert曲線形成的匿名區(qū)域從小到大的排序.

從圖5(a)可知,在密度較大的landmark數(shù)據(jù)集中對于同一δ值,q1～q8的誤差波動幅度不大,基本相似.在圖5(b)storage數(shù)據(jù)集中,同一個δ值q1～q8的誤差呈逐漸遞增趨勢,匿名區(qū)面積較小的誤差值較小.這是因為較密環(huán)境中由于k值一定,不同Hilbert曲線所包含的單元格數(shù)相近,噪聲疊加后誤差也基本相似;而在稀疏環(huán)境中,k值一定時,匿名區(qū)越小的Hilbert曲線所包含的單元格也較少,誤差也越小.因此在密集環(huán)境中,k值一定時無論哪種Hilbert曲線,誤差影響都不大;稀疏環(huán)境中,k值一定時要選擇形成匿名區(qū)面積較小的Hilbert曲線.

圖5 閾值δ對查詢誤差的影響Fig.5 Influence of threshold δ on query error

比較圖5(a)和圖5(b)兩圖,δ取值極小和極大時,誤差都較大,δ取值較為適中時誤差最小,且密集環(huán)境中的最優(yōu)閾值大于稀疏環(huán)境的最優(yōu)閾值.這是因為δ過小,劃分的單元格就越細,較多的單元格會使噪聲疊加較多;反之δ過大,查詢精度不夠也會造成誤差過大,所以較適中的δ值會降低查詢誤差.

5.3 樹高h對查詢誤差的影響

該實驗取k=180,根據(jù)上節(jié)的結(jié)論,landmark數(shù)據(jù)集取δ=100,storage數(shù)據(jù)集取δ=60,取q1為匿名區(qū)域(密集環(huán)境q1～q8誤差相差甚小,無論哪個匿名區(qū)都可以;稀疏環(huán)境q1的誤差最小,所以綜合選擇q1為匿名區(qū)).

比較圖6(a)和圖6(b)兩圖,不同h在landmark和storage數(shù)據(jù)集中平均方差相似,表示樹高對不同密度環(huán)境的影響較小.隨著隱私預算ε增大,誤差越小.隨著樹高h的增加,誤差逐漸增加并呈指數(shù)函數(shù)增長,這是因為誤差公式E(Q)與樹高h呈指數(shù)關(guān)系,并且分配較小的h具有較低的誤差.

圖6 樹高h對查詢誤差的影響Fig.6 Influence of tree height h on query error

5.4 匿名集規(guī)模k在不同隱私預算下對查詢誤差的影響

該實驗只在landmark數(shù)據(jù)集中比較,因為storage數(shù)據(jù)集太小而無法從中受益.同時,引入差分隱私最基本的算法(稱Dwork算法)以及對提高差分隱私查詢精度有代表性的哈爾小波零樹壓縮算法(稱EHWT-DP算法),與本文MATDP算法進行誤差的比較.根據(jù)前兩節(jié)的實驗結(jié)論,該實驗取δ=100,h=3,匿名區(qū)q1.

圖7中整體看得出,MATDP算法誤差在ε=0.1時要比ε=1時高出102倍.當k值較小時,Dwork算法誤差要小于其他兩種算法.但隨著k值增大(查詢范圍也逐漸增大),Dwork算法誤差呈線性累加地增大,MATDP算法的誤差較小,且與EHWT-DP算法相比較具有更低的查詢誤差.同時,在圖中可看出,MATDP算法誤差雖然隨著查詢范圍的增加而增加,但會逐漸趨于穩(wěn)定,這是由于該算法的隱私預算分配有誤差上界.

5.5 算法運行效率

該實驗分別對landmark數(shù)據(jù)集取δ=100,storage數(shù)據(jù)集取δ=60,同時h=3,k=180,匿名區(qū)q1(該數(shù)據(jù)的選取參考上述實驗結(jié)論),分別在不同ε值下比較三種算法的運行效率.

圖7 匿名集規(guī)模k對查詢誤差的影響Fig.7 Impact of anonymous set size k on query error

由圖8可知,在相同數(shù)據(jù)集下不同的ε值每種算法的運行時間基本相同,表示隱私預算ε不影響算法效率.Dwork算法運行時間最短,其次MATDP算法相較于EHWT-DP算法運行效率較高.是因為EHWT-DP算法對數(shù)據(jù)轉(zhuǎn)換成小波樹的形式后還需將數(shù)據(jù)壓縮,再添加噪聲,算法復雜度為O(klogk),而MATDP算法復雜度為O(k).整體來看,storage數(shù)據(jù)集下三種算法運行效率高于landmark數(shù)據(jù)集,這是由于δ值和k值一定時,較密環(huán)境生成的匿名區(qū)面積整體要小于稀疏環(huán)境的匿名區(qū),查詢時速度較快.

圖8 算法運行效率Fig.8 Algorithm operating efficiency

6 結(jié)束語

基于位置的服務給生活帶便利的同時位置隱私問題也是不容小覷.本文在Hilbert曲線構(gòu)建的滿足相互性的k匿名集基礎上,通過改進原始差分隱私方法在連續(xù)查詢下噪聲過大的問題,提出了基于m叉平均樹的差分隱私保護方法,該方法使用m叉平均樹結(jié)構(gòu)拆分匿名集數(shù)據(jù)以增強數(shù)據(jù)效用,并通過嚴密推導出具有較小誤差上界的拉普拉斯隱私預算分配策略.從閾值δ、匿名集規(guī)模k、匿名區(qū)域大小、樹高h、隱私預算ε以及興趣點分布密度等方面測試了算法對誤差的影響.并且與同類提高查詢精度的差分隱私方法相比,具有高效的運行效率.但在較小范圍中,查詢精度不太高,在未來的研究中,還要致力于在小范圍中對算法查詢精度的提高.