差分隱私的查詢一致性約束研究*

2020-03-04 08:15:18賈俊杰馬慧芳牟玉祥

計算機工程與科學 2020年1期

賈俊杰，陳慧，馬慧芳，牟玉祥

(西北師范大學計算機科學與工程學院,甘肅蘭州 730070)

1 引言

隨著互聯網大數據時代的到來，網絡上每時每刻都在產生大量的數據記錄，如購物記錄、Web點擊流等事務信息。這些數據發布后由企業和機構所收集和共享，通過挖掘其中的知識，為用戶提供更精準的服務。但是，數據發布在為企業決策和科學研究工作提供巨大便利的同時，也給數據個體帶來隱私泄露的威脅。隱私保護的數據發布技術作為當前數據安全領域的研究熱點，在為數據分析提供足夠多信息的同時也保護數據個體的隱私安全。目前隱私保護技術主要分為2類[1]：第1類是基于分組的隱私保護模型，如k-匿名[2]、l-多樣性[3]、t-相近[4]等，這類模型都需要特定的攻擊假設和背景知識；第2類是Dwork[5]在2006年針對統計數據提出的差分隱私保護模型，該模型不存在任何攻擊，通過向真實答案中添加噪聲干擾以達到對數據個體的隱私保護。

統計數據的發布主要使用直方圖形式，因直方圖直觀的數據分布形式，其結果可作為統計查詢的直接依據[6]。生成直方圖時，需根據不相交的查詢區間將數據劃分為不同的區間，再分別統計每個區間的計數值，為提供差分隱私的保護，最常用的方法是向每個區間分別添加獨立的符合Laplace分布的噪聲值。這些查詢區間為不相交的子集，所以區間查詢的敏感度為1，這樣的差分隱私直方圖發布保證了數據個體的隱私。但是，對于通用直方圖(即查詢區間子集相交的直方圖)[7]，每個區間是不規則的且與其他區間有重疊部分，若向通用直方圖的區間直接添加Laplace噪聲，可能會出現范圍查詢的不一致性問題。例如，1組查詢序列的結果為A={a1,a2,a3}，存在a1=a2+a3的約束關系，向A中添加Laplace噪聲之后得到的結果：a′1≠a2+a3，違背了原始的約束關系。

因此，本文針對查詢不一致的問題提出一致性調整算法，先將1組子集相交的區間查詢映射到1棵滿k-叉區間樹上，其中同一層節點上的區間值不相交，再向樹中每個節點添加符合Laplace分布的隨機噪聲，得到1棵差分隱私滿k-叉區間樹。將樹進行一致性調整后生成滿足一致性約束的滿k-叉區間樹，遍歷后得到1組調整后的序列，實現差分隱私的一致性約束。實驗結果表明，經過調整后的數據滿足一致性約束且比直接添加噪聲后的數據更接近真實值，實現了隱私保護目的，且時間運行效率優于LBLUE算法的。

2 相關工作介紹

Dwork[5]提出的差分隱私模型不存在任何的隱私攻擊，且該模型具有強大的數學背景知識，致使差分隱私迅速成為了隱私保護研究領域的熱點。直方圖發布作為一種直觀的數據分析方法，將利用差分隱私保護后的數據以直方圖的形式發布，更利于數據研究者分析，因此目前已有大量的文獻提出基于差分隱私保護的直方圖發布算法。2006年，Dwork等人[8]最早提出基于差分隱私模型的直方圖發布，通過向直方圖中的每個區間直接添加噪聲來達到隱私保護的目的。2011年，Xiao等人[9]提出通過小波變換技術實現差分隱私保護的直方圖發布方法Privelet，利用小波變換將直方圖數據轉換為小波樹，再向樹中添加噪聲實現差分隱私，逆轉換小波樹得到需發布的直方圖數據。2012年，Acs等人[10]利用貪心策略將近鄰的查詢區間聚類成1個簇，再根據每個簇的大小不同添加噪聲。在直方圖中直接添加噪聲后進行查詢，會因區間值內噪聲值疊加導致偏差過大的問題。2013年，Xu等人[11]提出StructureFirst算法，利用指數機制確定不同分組間的界限，再向不同組添加噪聲。2016年，張嘯劍等人[12]提出基于差分隱私的直方圖發布方法DiffHR，利用Metropolis-Hastings技術與指數機制對直方圖數據進行排序，排序后使用一種貪心聚類方法提高精確度。2019年，張宇軒等人[13]利用度排序的邊移除方法給出了2種點差分隱私下圖的度分布直方圖發布機制，這2種發布機制在達到隱私保護的前提下，還提高了數據的可用性。

目前關于差分隱私直方圖的發布主要針對精確度的問題做研究，針對不一致現象的研究較少，Hay等人[7]首次提出針對差分隱私直方圖發布的不一致問題，使用約束推理的后處理方法，解決查詢存在的不一致現象，結果證明經過處理后的答案接近真實值且滿足一致性約束。Lee等人[14]為進一步提高一致性約束后直方圖的精確度，將后處理步驟轉換為約束極大似然估計問題，提出一種基于交替方向乘子法ADMM(Alternating Direction Method of Multipliers)的通用方法，該方法適用于各種應用。吳英杰等人[15]通過構造局部的區間樹，實現局部最優線性無偏估計，使用迭代次數以達到全局最優線性無偏估計。因此，本文提出全局的一致性調整CA(Coherence Adjustment)算法，該算法既解決了不一致問題又保證了數據的精確度。

3 相關技術介紹

3.1 差分隱私

差分隱私模型使數據通過某種差分隱私隨機算法K發布并面向用戶提供查詢接口。算法K不依賴于特定的數據表，利用隨機噪聲對輸出數據進行擾亂，數據表中的每1條記錄均得到了完全相同程度的保護，使得在統計意義上攻擊者無論具有何種背景知識，都無法識別任意1條記錄是否在原數據表中。

定義1(兄弟數據集) 2個數據集D和D′，有且僅有1條記錄不同，記為|DΔD′|=1，則稱D與D′為1對兄弟數據集。

定義2[5](ε-差分隱私) 對任意1對兄弟數據集D和D′，存在隨機算法F(D)和F(D′)滿足：

Pr(F(D)∈S)≤exp(ε)×Pr(F(D′)∈S)

(1)

則稱算法F滿足ε-差分隱私。其中S表示任意的輸出集合，ε表示隱私預算，隱私預算越大，隱私保護程度越低，數據可用性越高，通常情況下，ε取[0,1]的實數。

定義3[5](全局敏感度) 有1對兄弟數據集D和D′，對于任意函數f(D)∈R，則其全局敏感度Δf表示為：

Δf=max‖f(D)-f(D′)‖p

(2)

其中，R為函數所映射的實數空間，‖f(D)-f(D′)‖p表示數據集D與D′之間的Lp距離。

差分隱私保護主要通過向真實數據添加噪聲來實現，常見添加噪聲的機制包括Laplace機制和指數機制，其中Laplace機制主要針對數值型數據，指數機制通常用于需要對輸入數據進行復雜操作的算法，例如針對離散型數據的分類操作。本文采用Laplace機制分析計數查詢的一致性約束問題。

定義4[5](Laplace機制) Laplace機制通過向查詢請求結果f(D)中添加隨機擾動噪聲η，得到輸出值f(D)+η實現ε-差分隱私保護，則Laplace分布的概率密度函數為：

(3)

由式(3)可得，Laplace噪聲滿足期望為0、方差為2λ2的Laplace(λ)分布。噪聲尺度參數λ值越大，所添加的噪聲幅度越高，隱私保護程度也越大。對于任意函數f(D)∈Rd，若算法F的輸出結果滿足：

(4)

則F滿足ε-差分隱私保護。其中d為區間查詢長度。由式(4)可得，添加的噪聲尺度參數λ=Δf/ε，λ大小與全局敏感度Δf成正比，與隱私預算ε成反比。

性質1[5]設有算法F1,F2,…,Fn，隱私預算分別為ε1,ε2,…,εn，那么對于不相交的數據集D1,D2,…,Dn，由這些算法構成的組合算法F(F1(D1),F2(D2),…,Fn(Dn))滿足(maxεi)-差分隱私保護，該性質稱為“并行組合性”。

3.2 k-叉區間樹

統計直方圖的發布按數據表不同的屬性進行劃分，形成1個或多個屬性不相交的集合，利用集合的計數值來直觀地表示數據的分布信息。

定義5(計數查詢) 設有n條記錄的數據表T，其中包含屬性x，用戶通過查詢Q訪問數據表T，查詢Q形如Select Count(*) fromTWherexina。若屬性x為數值型數據，該查詢統計屬性x的取值頻數，其中a為屬性x的1個取值。若屬性x為分類屬性，該查詢分別統計屬性x的類別計數，此時a為屬性x的1個類別。

例1統計某購物籃商品A,B,C,D的購買頻數，每個商品的購買屬性取值為0或1，0為沒有購買，1為購買。表1為商品統計結果，表2為對表1的統計結果加噪后的結果。

Table 1 Commodity statistics results表1 商品統計結果

Table 2 Results after adding noise 表2 加噪后的結果

假設用戶對原始表提出查詢Select Count(*) fromTWhereGoodsin (‘A’,‘B’)，即查詢商品A和B的計數和，故該查詢可稱為區間查詢，可利用表1得此查詢的精確結果為4。若利用表2來回答用戶的查詢，查詢區間較大時，即Goods的查詢類別較多時，噪聲的累加使數據的精確度降低。

由敏感度定義可知，1對兄弟表統計差異值為1，此時統計直方圖的敏感度Δf=1，若對原始數據每條記錄都添加噪聲，由于每個元素的Laplace噪聲為方差2λ2，在最壞查詢情況下，區間查詢Q覆蓋了所有的記錄，將由類似表2的加噪查詢結果中的n個元素方差相加而成，可得查詢Q的噪聲方差為O(nλ2)；當查詢的區間較大時，將使添加噪聲后的差分隱私統計直方圖發布結果的方差增大，影響數據發布的有效性。據此，文獻[15]提出將統計直方圖轉化為區間樹，再對區間樹進行差分隱私統計直方圖發布，當進行查詢時，每個父節點的值均為其k個子節點的值之和，其中k為區間樹中每個父節點的子節點數，故查詢Q的噪聲為所覆蓋節點的噪聲總和，且在所添加噪聲為同方差的條件下，查詢Q的噪聲方差為O(kλ2logn)?？梢?，利用區間樹發布統計直方圖可以大幅減少計數查詢的誤差。

定義6(滿k-叉區間樹) 將區間查詢Q的值映射到1棵k-叉樹(k≥2)的各個節點上，生成滿k-叉區間樹H，使得每個節點所對應的查詢區間覆蓋其k個孩子節點的查詢區間，且每個節點的真實區間查詢計數值為其孩子節點的真實計數值之和。其中同一層節點的查詢區間不相交。

例2將表1中的區間查詢構造成1棵滿2-叉區間樹H。假設查詢的區間序列為T=([A],[B],[C],[D],[AB],[CD],[ABCD])，其中區間[AB]表示查詢覆蓋商品A和B的計數和，且每個區間查詢彼此相互獨立，區間數|T|=7，令k=2，則m=3。因區間[AB],[CD],[ABCD]的計數分別為4,24和28，根據映射關系可構造深度為3的滿2-叉區間樹H，如圖1所示。

Figure 1 Full 2-ary range tree H圖1 滿2-叉區間樹H

(5)

4 算法模型

為解決上述的不一致現象，文獻[15]提出局部最優線性無偏估計，但只限定深度為2且有k個子節點的差分隱私區間樹(本文中規定樹的層數l從1開始計數，即定義1個節點所在的層數為葉節點到該節點路徑上的節點數)。本文的目的是在深度大于2的滿k-叉區間樹中找到所有節點值的最優線性無偏估計。

根據文獻[15]，假設任意1棵深度為2的區間樹H，為H中每個節點值隨機添加獨立同方差的Laplace(Δf/ε)噪聲，得到差分隱私區間樹。根據高斯-馬爾科夫定理，求最優線性無偏估計等價于求解1個滿足限定條件的最小二乘解，令第i個子節點原始計數值為真實值Xi，則父節點t和子節點i=Son(t)={i1,i2,…,ik}添加噪聲后的節點值分別為：

(6)

(7)

令z表示節點的無偏估計權值，即得到定理1。

定理1[15](局部最優線性無偏估計) 對于任意1棵深度m=2的差分隱私k-叉區間樹，其節點的最優線性無偏估計為：

(8)

(9)

其中，

(10)

父節點的無偏估計值為父節點噪聲值減去偏差值Δ，葉節點的估計值為葉節點噪聲值加上偏差值Δ。

定理1并不適用深度大于2的差分隱私區間樹，文獻[15]提出迭代定理1得到局部最優線性無偏估計迭代算法LBLUE(Local Best Linear Unbiased Estimation)，但算法隨著樹的深度增加計算量增大，效率也隨之降低。因此,本文提出差分隱私區間樹的一致性查詢算法，對區間樹進行2次遍歷，通過自頂向下的不一致估計調整，再進行自底向上的一致性無偏估計調整，最終得到滿足一致性約束查詢的差分隱私滿k-叉區間樹。

4.1 自頂向下的不一致估計

根據定理1，若要滿足一致性約束查詢，則父節點(根節點)的無偏估計值應等于子節點的無偏估計值之和，即：

(11)

對于任意子節點i(i∈Son(t))，有：

(12)

其中，j指父節點t除了i以外的子節點，此時節點i的無偏估計值為：

(13)

由式(9)可知：

(14)

綜合式(10)、式(13)和式(14)，得到：

(15)

(16)

(17)

即

(18)

因此根據自頂向下策略，可得滿k-叉區間樹各節點不一致有偏估計值的遞歸關系為：

(19)

自頂向下的不一致估計TDICE(Top-Down Inconsistent Estimates)算法如算法1所示。

算法1TDICE

輸出：Z(自頂向下的不一致估計的TDICE滿k-叉區間樹)。

4 返回Z

5 end

4.2 自底向上一致性估計

(20)

(21)

由式(21)可知：

(22)

則

(23)

將式(23)代入式(20)，可得：

(24)

(25)

自底向上一致性估計BUCE(Bottom-Up Consistent Estimates)算法如算法2所示。

算法2BUCE

輸入：Z。

1 將Z自底向上一致性估計；

5 end

4.3 一致性調整

一致性調整算法CA描述如算法3所示。

算法3CA

輸入：Q，隱私預算ε。

1 將Q映射到滿k-叉區間樹上，add 0*to空節點，得到H；

5 刪除所有標記0*的節點；

4.4 一致性分析

在使用CA算法之前，已經對查詢結果添加了符合Laplace分布的噪聲，數據的隱私程度不需要再進行討論，接下來分析CA算法的一致性。

(26)

根據式(21)和式(23)，可得：

(27)

則有

(28)

所以，經過調整后的滿k-叉區間樹對于任一父節點t滿足一致性區間查詢。得證。

□

4.5 算法分析

將區間查詢的值映射到1棵滿k-叉區間樹上，設滿k-叉區間樹的節點總個數為n。算法1是將1棵添加噪聲后的滿k-叉區間樹進行1次自頂向下的遍歷，時間復雜度為O(n)；而算法2是將1棵自頂向下不一致估計后的滿k-叉區間樹進行1次自底向上的一致性估計，時間復雜度也為O(n)。因此，CA算法的總時間復雜度為O(n)。

5 實驗評估

本節主要驗證一致性調整后的直方圖發布滿足一致性且精確度高，以及算法的時間效率高于需迭代的LBLUE算法的。4.4節已證明一致性調整后的數據滿足一致性約束查詢，因此根據精確度和時間效率進行實驗。實驗對比分析對象為在滿k-叉區間樹上添加符合Laplace分布的噪聲值實現差分隱私算法H～,對比算法為文獻[7]Boost-2算法、文獻[15]LBLUE算法和一致性調整算法CA。

實驗采用的數據集為：Amazon[15]和Nettrace[7]。其中Amazon是為期1 894天的用戶對亞馬遜網站發起請求操作的時間數據集,Nettrace是1所大學65 535條內聯網的IP地址軌跡數據。

實驗環境為2.60 GHz Intel(R)Core(TM)i5-3230M CPU，4.00 GB內存，Windows 10專業版64位操作系統，數據分析軟件為IBM SPSS Statistics 22，編程軟件為Eclipse 4.3，繪制結果分析圖軟件為Matlab R2016a。

5.1 區間查詢精確度對比

采用均方誤差MSE[12]度量精確度。在區間查詢精確度對比實驗中，通過改變區間查詢的大小，在每個區間內隨機選取500個查詢，得到這些區間查詢的均方誤差，然后求取均值來確定區間查詢的精確度。隱私預算ε分別取值0.01和1.0進行實驗，分析結果如圖2和圖3所示。

Figure 2 MSE changes of different range queries on Amazon dataset圖2 Amazon數據集下不同的區間查詢MSE變化

Figure 3 MSE changes of different range queries on Nettrace dataset圖3 Nettrace數據集下不同的區間查詢MSE變化

圖2為使用Amazon數據集的分析結果，圖3為使用Nettrace數據集的分析結果?？梢悦黠@看到，即使ε取值不同，相同區間查詢，H～得到的結果誤差最大。在圖2a中ε=0.01時，區間查詢的誤差值約為103，在圖2b中ε=1.0時，區間查詢的誤差值約為101，幾乎接近于真實值。而在圖3a中ε=0.01時，區間查詢的誤差值約為106，在圖3b中ε=1.0時，區間查詢的誤差值約為102。這是因為Nettrace數據集相比Amazon數據集，單位長度區間個數更多，因此誤差值數量級相差更大。

對比分析圖2和圖3可得，同一數據集下，ε取值越大，均方誤差值越小，即數據的可用性越高。因為隨著區間值增大，區間查詢樹的節點個數越多，需要添加噪聲值的節點數越多，導致均方誤差值越大。而H～為直接向滿k-叉區間樹中添加噪聲得到的結果，與其他3種經過調整后的算法對比，均方誤差值明顯更大。Boost-2算法的均方誤差值比LBLUE算法的誤差值小，這與文獻[15]得出的分析結果相同。因CA算法不需要迭代，只需要對區間樹進行2次遍歷，所以噪聲值的疊加也會減小，相比Boost-2算法和LBLUE算法均方誤差值有所減少。

5.2 算法時間效率對比

通過使用Amazon數據集和Nettrace數據集對比Boost-2算法、LBLUE算法、CA算法的運行時間，分別取ε=0.01，0.1，1.0進行實驗。從圖4中可以明顯看到，不論ε取何值，同一數據集下相同算法的運行時間相同，因此得出結論：算法運行時間與ε取值的大小無關。還可以看出，在2個數據集對比圖中，Boost-2算法和CA算法的運行時間基本相同，而LBLUE算法的運行時間明顯較長，這是因為LBLUE算法需要迭代運行，而其他2種算法不需要迭代運行，因此運行時間比LBLUE算法的短。而數據集的大小不同，運行時間也不同，即數據集記錄條數越多，算法的運行時間越大?？傮w而言，在同一數據集下，本文算法的運行效率高于LBLUE算法的運行效率。

Figure 4 Comparison of the average running time of three algorithms with different ε圖4 3種算法在ε不同時平均運行時間的比較

6 結束語

本文針對直方圖發布區間查詢的不一致問題，提出一致性調整算法CA。先將滿k-叉區間樹進行自頂向下的不一致估計TDICE，然后對不一致估計后的結果進行自底向上一致性估計BUCE，得到一致性調整(CA)后的結果。經證明，通過一致性調整后的滿k-叉區間樹滿足一致性約束查詢。使用真實數據集進行實驗對比，得出一致性調整(CA)后的區間查詢精確度較高且時間效率高于LBLUE算法的。此外，當數據集較大時，如何降低區間查詢誤差值是下一步需要進行的工作。