胡德敏,廖正佳
(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)
差分隱私[1]作為位置擾動(dòng)中一個(gè)常用的方法,具有嚴(yán)格的推理和證明的隱私保證,攻擊者無論是否擁有背景知識(shí)[2]都無法推斷出一條真實(shí)的位置數(shù)據(jù),日漸成為位置保護(hù)中最受歡迎的方法.
基于差分隱私的位置保護(hù)方法會(huì)犧牲數(shù)據(jù)效用,用戶在移動(dòng)環(huán)境下連續(xù)查詢時(shí),單個(gè)位置點(diǎn)或興趣點(diǎn)添加噪聲后,會(huì)出現(xiàn)噪聲疊加導(dǎo)致位置查詢精度和服務(wù)質(zhì)量下降等問題.樹形結(jié)構(gòu)的差分隱私[3,12]方法能拆分位置數(shù)據(jù)集以增強(qiáng)數(shù)據(jù)效用,并能在保護(hù)位置隱私的同時(shí)有效提高移動(dòng)查詢精度.但規(guī)則樹形結(jié)構(gòu)的差分隱私方法會(huì)造成大量無效零節(jié)點(diǎn),數(shù)據(jù)結(jié)構(gòu)過大,在查詢精度上還有進(jìn)一步提高的空間.
因此在規(guī)則樹結(jié)構(gòu)的差分隱私位置保護(hù)的基礎(chǔ)上,提出了不規(guī)則樹結(jié)構(gòu)的差分隱私位置保護(hù)方法(Irregular Segment Tree Differential Privacy,ISTDP).該方法能有效解決差分隱私方法在移動(dòng)環(huán)境下的連續(xù)查詢精度下降的問題,并能適應(yīng)不同密度環(huán)境.將k-匿名機(jī)制[4]與差分隱私相結(jié)合,引入線段樹(Segment Tree)[5]的概念,形成匿名集后,使用不規(guī)則的線段樹結(jié)構(gòu)對數(shù)據(jù)進(jìn)行劃分;并將不規(guī)則線段樹中節(jié)點(diǎn)覆蓋率的差異加入對查詢精度的考量,推導(dǎo)出衡量最優(yōu)不規(guī)則線段樹的估值函數(shù);根據(jù)節(jié)點(diǎn)覆蓋率構(gòu)造子樹的估值函數(shù),從而得出較低的查詢誤差的線段樹作為最終的不規(guī)則線段樹;最后為每個(gè)節(jié)點(diǎn)分配具有較小誤差上界的Laplace隱私預(yù)算.
Dwork[1]最先提出的差分隱私方法,目標(biāo)是對位置數(shù)據(jù)加入拉普拉斯噪聲來模糊真實(shí)位置.現(xiàn)實(shí)中用戶多是處于移動(dòng)環(huán)境中進(jìn)行位置查詢,差分隱私方法免不了會(huì)使疊加的噪聲量影響查詢精度和數(shù)據(jù)的可用性.如何在隱私保護(hù)和查詢精度之間獲得較好的權(quán)衡,是研究者們一直努力的方向.
Hoa Ngo[6]提出了一種基于地理不可分辨性(差分隱私的廣義變體)的隱私定義,通過發(fā)布多個(gè)版本的Hilbert曲線生成最小匿名區(qū).該方法只是優(yōu)化了匿名區(qū),并沒有改進(jìn)差分隱私的噪聲疊加問題.文獻(xiàn)[7]主要思想是將數(shù)據(jù)轉(zhuǎn)換成系數(shù),將位置數(shù)據(jù)映射成小波樹,然后添加拉普拉斯噪聲,缺陷是映射成的小波樹會(huì)產(chǎn)生大量無效節(jié)點(diǎn),需要進(jìn)一步壓縮.在基于樹結(jié)構(gòu)的數(shù)據(jù)轉(zhuǎn)換中,文獻(xiàn)[8]提出了PLDP-TD算法,在底層軌跡數(shù)據(jù)庫上構(gòu)建一棵個(gè)性化的噪聲軌跡樹,并根據(jù)每個(gè)子軌跡分配一個(gè)隱私級,添加隱私參數(shù),但規(guī)則的樹結(jié)構(gòu)造成數(shù)據(jù)結(jié)構(gòu)過大算法效率低.文獻(xiàn)[9]提出了kd-standard方法,在kd-樹上進(jìn)行了改進(jìn),利用差分隱私的指數(shù)機(jī)制和噪聲均值機(jī)制,保證數(shù)據(jù)加噪后查詢誤差最小.但是這些的方法存在的共同問題是,使用樹結(jié)構(gòu)對數(shù)據(jù)進(jìn)行轉(zhuǎn)換時(shí),需要將樹映射成滿n叉樹的結(jié)構(gòu)(如二叉樹,四叉樹等),若興趣點(diǎn)數(shù)據(jù)量不充足的情況下,會(huì)產(chǎn)生大量為零的節(jié)點(diǎn),因此需要進(jìn)一步壓縮,才能保證查詢誤差較小,但是會(huì)造成算法復(fù)雜度較高.規(guī)則的樹形結(jié)構(gòu)會(huì)使數(shù)據(jù)結(jié)構(gòu)較大無用節(jié)點(diǎn)較多,查詢精度有進(jìn)一步提高的空間.
本文以k-匿名機(jī)制為基礎(chǔ)(利用Hilbert曲線[10]形成匿名集),采用不規(guī)則線段樹結(jié)構(gòu)對數(shù)據(jù)進(jìn)行優(yōu)化.將不規(guī)則線段樹中節(jié)點(diǎn)覆蓋率的差異加入對查詢精度的考量,根據(jù)節(jié)點(diǎn)覆蓋率構(gòu)造子樹的估值函數(shù),從而得出較低的查詢誤差的線段樹作為最終的不規(guī)則線段樹,最后為每個(gè)節(jié)點(diǎn)分配具有較小誤差上界的Laplace隱私預(yù)算.提高了差分隱私的位置查詢精度和服務(wù)質(zhì)量,并能適應(yīng)不同密度環(huán)境.
定義1.ε-差分隱私[1].對于任何兩個(gè)數(shù)據(jù)表T和T′,至多包含一個(gè)不同的記錄,對任意輸出S,S滿足S?Range(f),隨機(jī)函數(shù)f滿足:
(1)
則稱算法f滿足ε-差分隱私.
差分隱私的定義規(guī)定了任意兩個(gè)數(shù)據(jù)表經(jīng)過差分?jǐn)_動(dòng)后,差異不超過給定的eε.對數(shù)據(jù)添加噪聲主要由Laplace機(jī)制[1]實(shí)現(xiàn).
(2)
滿足Laplace分布的方差為2λ2,期望為0.由定義3可知,差分隱私的隱私強(qiáng)度與噪聲參數(shù)λ有關(guān),λ越大,噪聲幅度越大,隱私保護(hù)強(qiáng)度就越高,但是數(shù)據(jù)可用性就越低.
定義3.Laplace機(jī)制的敏感度[1].敏感度是數(shù)據(jù)表T中任何單個(gè)元組數(shù)據(jù)變化時(shí)f中的最大變化.
(3)
根據(jù)Laplace機(jī)制的敏感度Δf、噪聲參數(shù)λ、差分隱私參數(shù)ε,可以得出以下三者之間的關(guān)系:
定義5.線段樹[5].線段樹是一種二叉搜索樹,給定一個(gè)數(shù)據(jù)集D,若滿足以下條件的樹,則稱該樹為D所對應(yīng)的線段樹:
2)令x的孩子節(jié)點(diǎn)為child(x),對于孩子節(jié)點(diǎn)child(x)要滿足:
(4)
(5)
若child(x)為空集,則x為葉子節(jié)點(diǎn).
對于普通加噪方式來說,為每條位置數(shù)據(jù)添加噪聲后的敏感度Δf為1,由于查詢會(huì)涉及到O(l)個(gè)數(shù)據(jù),因此噪聲方差和為O(lλ2).對于數(shù)據(jù)進(jìn)行過基于線段樹的劃分后,線段樹的深度為O(logl),根據(jù)廣義敏感度及其推理可知,深度為O(logl)的線段樹的敏感度為Δf=O(logl).對于不規(guī)則線段樹來說,設(shè)每個(gè)節(jié)點(diǎn)的扇出最大為d,因此噪聲方差和為:
∑2λ2=O(2dloglλ2)=O(dloglλ2)
(6)
運(yùn)用不規(guī)則線段樹劃分?jǐn)?shù)據(jù)加噪后的噪聲方差可以有效的減小誤差,提高查詢精度.
定義6[11].對于查詢Q=[left,right],要求滿足一下條件的節(jié)點(diǎn)集合A:
3)|A|最小
目的是要找到覆蓋Q的查詢區(qū)間且最少的不相交的節(jié)點(diǎn).需要注意的是,對于覆蓋節(jié)點(diǎn)x的查詢Q=[left,right],Q不能覆蓋其父節(jié)點(diǎn).
(7)
由于敏感度即為樹高,則可以進(jìn)一步將研究查詢方差改為研究查詢方差的期望,對于查詢Q的方差的期望為:
(8)
利用Hilbert曲線劃分出k-匿名集后,將匿名集映射成不規(guī)則樹結(jié)構(gòu).如圖1,用戶在P9處形成的(k=3)匿名集的H值為<0,1,2,3,4>,將該H值進(jìn)行線段樹的轉(zhuǎn)化后,該線段樹的區(qū)間為[0,4],長度為5.
圖1 Hilbert曲線形成的匿名集Fig.1 Anonymous sets formed by Hilbert curves
區(qū)間左端點(diǎn)不為1,因此,將區(qū)間往左移一個(gè)設(shè)為[1,5](離散化的值要從1開始).假設(shè)構(gòu)造出的兩種不規(guī)則線段樹如圖2所示,分別計(jì)算線段樹節(jié)點(diǎn)的覆蓋率:
圖2 線段樹的節(jié)點(diǎn)覆蓋率Fig.2 Node coverage rate of segment tree
根據(jù)定義6對線段樹的查詢覆蓋區(qū)域的要求可知,根節(jié)點(diǎn)僅有一個(gè)查詢區(qū)域能覆蓋,即為該所在區(qū)域本身;對于非根節(jié)點(diǎn)x,其父節(jié)點(diǎn)為p,要求滿足left(p)≤left(x)≤right(x)≤right(p),由于查詢區(qū)域Q=[left,right]不能覆蓋父節(jié)點(diǎn)p,因此查詢區(qū)域要求滿足以下兩個(gè)條件,見圖3.
圖3 節(jié)點(diǎn)查詢區(qū)域區(qū)間Fig.3 Node query qrea section
P1(x)=
滿足條件②的節(jié)點(diǎn)覆蓋率為:
P2(x)=
滿足條件的查詢區(qū)間Q算了重疊的一段區(qū)間,如圖3(c).重疊區(qū)域?yàn)?left(p)+1≤left≤left(x))∧(right(x)≤right≤right(p)-1),該重疊區(qū)域的節(jié)點(diǎn)覆蓋率為:
根據(jù)容斥定理,非根節(jié)點(diǎn)的節(jié)點(diǎn)覆蓋率為P1(x)+P2(x)-P重(x).結(jié)合查詢方差的期望,定義不規(guī)則線段樹的估值函數(shù)為:
(9)
圖4 節(jié)點(diǎn)b不同區(qū)間分布的線段樹Fig.4 Segment tree with different section distribution of node b
此時(shí)節(jié)點(diǎn)b的估值函數(shù)為16.8,因此可以通過計(jì)算節(jié)點(diǎn)的估值函數(shù),篩選出具有較低估值函數(shù)的線段樹.不規(guī)則線段樹的差分隱私位置保護(hù)方法的整體算法如下:
算法.不規(guī)則線段樹的差分隱私位置保護(hù)算法
輸入:生成的匿名區(qū)ASR,匿名集u.s
輸出:擾動(dòng)后的匿名區(qū)域ASR′
1. order(H(ASR.POI));//將匿名區(qū)ASR中單元格區(qū)域的H值按從小到大排序
2. find Hmax,Hmin in H(ASR.POI);//找到ASR中H值的最大值Hmax和最小值Hmin,形成查詢區(qū)間[Hmin,Hmax]
3. if Hmin==0
4. Hmin =1,Hmax=Hmax+1;//若Hmin為0,將區(qū)間右移,變成[1,Hmax+1](保證左端點(diǎn)大于等于1)
5. end if;
6. if(left(x)!=right(x))//如果左端點(diǎn)不等于右端點(diǎn),則遞歸劃分子線段樹
7. min=V(2,left(x),right(x));
8. m=2;//ary的值2 ary 20,先記錄第一個(gè)值,接下來循環(huán)找出估值函數(shù)V(2,left(x),right(x))最小的子線段樹
9. for(vari=3;i<=20;i++)
10. ary=i;
11. value=V(ary,left(x),right(x));
12. if(value 13. min=value; 14. m=ary;//記錄下最優(yōu)子線段樹的扇出m 15. end if; 16. end for; 17. else break;//如果左右端點(diǎn)相同,則不用繼續(xù)劃分,該節(jié)點(diǎn)為葉子節(jié)點(diǎn),否則重復(fù)步驟6-17 18. end if 將不規(guī)則線段樹的差分隱私位置保護(hù)方法(ISTDP)、m叉平均樹的差分隱私位置保護(hù)方法(MATDP)[12]以及對提高差分隱私查詢精度有代表性的哈爾小波零樹壓縮算法(EHWT-DP)[7]進(jìn)行對比實(shí)驗(yàn).針對不同地理密度的環(huán)境、不同的總隱私預(yù)算ε、不同匿名集規(guī)模等條件下,主要從查詢的誤差(方差)、算法運(yùn)行時(shí)間等方面評價(jià)算法的查詢準(zhǔn)確性以及算法運(yùn)行效率. 實(shí)驗(yàn)環(huán)境為 Inter?CoreTMi5,windows7 操作系統(tǒng),8GB 內(nèi)存,算法是 Eclipse環(huán)境下基于Java 編寫.本章實(shí)驗(yàn)使用了兩個(gè)數(shù)據(jù)集進(jìn)行對比:第一個(gè)是由infochimps大數(shù)據(jù)網(wǎng)站提供的美國48個(gè)大陸州的地標(biāo)位置組成的地標(biāo),數(shù)據(jù)分布較密集,約有870k個(gè)數(shù)據(jù)點(diǎn),實(shí)驗(yàn)中簡稱為“l(fā)andmark”;第二個(gè)為美國存儲(chǔ)設(shè)施位置數(shù)據(jù),包括國家連鎖存儲(chǔ)設(shè)施,以及本地?fù)碛泻瓦\(yùn)營的設(shè)施,數(shù)據(jù)機(jī)較稀疏,約有9000個(gè)數(shù)據(jù)點(diǎn)的,簡稱“storage”. 實(shí)驗(yàn)中將查詢方差的期望作為一項(xiàng)對誤差的衡量標(biāo)準(zhǔn),并且也將會(huì)與第三章中提出的m叉平均樹的差分隱私方法進(jìn)行對比,對比其查詢誤差的大小.實(shí)驗(yàn)中使用移動(dòng)對象生成器,生成30km/h的300個(gè)移動(dòng)用戶,設(shè)查詢總時(shí)間為 30min,查詢間隔為 5min,因此所有用戶一共要發(fā)起約1800次的連續(xù)查詢. 主要測試的是隱私參數(shù)ε對查詢誤差的影響,因此在實(shí)驗(yàn)中僅選擇在storage數(shù)據(jù)集中測試(密度較高的數(shù)據(jù)集實(shí)驗(yàn)效果更明顯),分別取ε在0.5、0.75與1.0,匿名集規(guī)模k取100~200的情況下,觀察ISTDP查詢誤差的變化,如圖5. 圖5 不同隱私參數(shù)ε和匿名集規(guī)模k下誤差的變化Fig.5 Errors in differnet privacy parameters and anonymous set sizes 在該實(shí)驗(yàn)中,ε分別選取0.5、0.75、1.0三個(gè)值,針對兩種不同地理環(huán)境的storage數(shù)據(jù)集與landmark數(shù)據(jù)集,測試ISTDP、MATDP與EHWT-DP三種算法的查詢精度的對比,結(jié)果如圖6. 圖6 不同算法查詢誤差的對比Fig.6 Comparison of query errors between different algorithms 從圖中可以看出,不論在哪種數(shù)據(jù)集下,本文的ISTDP方法的查詢誤差始終小于其他兩種方法,且查詢誤差僅有其他方法的20%.整體看來ISTDP在不同數(shù)據(jù)集中的查詢誤差波動(dòng)幅度不大,基本上呈現(xiàn)緩慢增長的趨勢,這是由于分配的隱私預(yù)算具有最大的誤差上界.MATDP和EHWT-DP兩者受密度環(huán)境的影響較大,有的甚至有一個(gè)數(shù)量級的波動(dòng).可以得出結(jié)論,ISTDP比其他方法能更加不受地理環(huán)境密度分布的影響,且比其他減小查詢誤差的方法中查詢精度更佳,誤差較小,實(shí)驗(yàn)結(jié)果符合理論預(yù)期. 圖7 算法運(yùn)行時(shí)間Fig.7 Algorithm runtime 該實(shí)驗(yàn)在storage數(shù)據(jù)集和landmark數(shù)據(jù)集中進(jìn)行,取匿名集規(guī)模k=120,隱私參數(shù)ε=1.0,對比ISTDP、MATDP和EHWT-DP三種方法的算法運(yùn)行時(shí)間,如圖7所示. 從圖中可以看出,ISTDP與MATDP在兩種數(shù)據(jù)集下的運(yùn)行時(shí)間相差不大,這是因?yàn)檫@兩種算法是基于樹形結(jié)構(gòu)的改進(jìn),僅與匿名集大小k有關(guān),區(qū)域的網(wǎng)格劃分和Hilbert曲線填充都是在離線環(huán)境下進(jìn)行,所以運(yùn)行時(shí)間相較于EHWT-DP方法少.ISTDP的運(yùn)行效率并沒有比MATDP提高多少,在ISTDP中主要時(shí)間復(fù)雜度是遞歸劃分子線段樹,所以該算法的時(shí)間復(fù)雜度為O(logk).ISTDP在MATDP的基礎(chǔ)上沒有對算法復(fù)雜度有大幅度的提高,但相比于EHWT-DP(時(shí)間復(fù)雜度為O(klogk))要提高了許多. 本文描述了不規(guī)則線段樹的差分隱私位置保護(hù)方法,詳細(xì)介紹了線段樹的基本概念,將不規(guī)則線段樹引入差分隱私方法中,能有效提高查詢精度,減小連續(xù)查詢時(shí)噪聲疊加帶來的查詢精度下降的問題.實(shí)驗(yàn)驗(yàn)證了該方法對地理環(huán)境密度的影響較小,能適應(yīng)不同密度環(huán)境的LBS位置查詢服務(wù),并且相對于其他提高差分隱私查詢精度的方法有更小的查詢誤差.5 實(shí)驗(yàn)結(jié)果與分析
5.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境
5.2 不同隱私參數(shù)ε和匿名集規(guī)模下查詢誤差的變化
5.3 查詢精度的對比
5.4 算法運(yùn)行效率的比較
6 結(jié)束語