不規(guī)則線段樹的差分隱私位置隱私保護(hù)方法

胡德敏，廖正佳

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

1 引 言

差分隱私[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ù)算.

2 相關(guān)工作

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)境.

3 相關(guān)概念

3.1 差分隱私

定義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)系：

3.2 線段樹

定義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).

4 不規(guī)則線段樹的差分隱私位置隱私保護(hù)方法

4.1 計(jì)算節(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

4.2 不規(guī)則線段樹的估值函數(shù)

根據(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

5 實(shí)驗(yàn)結(jié)果與分析

將不規(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)行效率.

5.1 實(shí)驗(yàn)數(shù)據(jù)與環(huá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ù)查詢.

5.2 不同隱私參數(shù)ε和匿名集規(guī)模下查詢誤差的變化

主要測試的是隱私參數(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

5.3 查詢精度的對比

在該實(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ù)期.

5.4 算法運(yùn)行效率的比較

圖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))要提高了許多.

6 結(jié)束語

本文描述了不規(guī)則線段樹的差分隱私位置保護(hù)方法，詳細(xì)介紹了線段樹的基本概念，將不規(guī)則線段樹引入差分隱私方法中，能有效提高查詢精度，減小連續(xù)查詢時(shí)噪聲疊加帶來的查詢精度下降的問題.實(shí)驗(yàn)驗(yàn)證了該方法對地理環(huán)境密度的影響較小，能適應(yīng)不同密度環(huán)境的LBS位置查詢服務(wù)，并且相對于其他提高差分隱私查詢精度的方法有更小的查詢誤差.