基于差分隱私保護的數(shù)據(jù)分級融合發(fā)布機制

李萬杰,張 興,曹光輝,李 帥,張青云

(遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院,遼寧 錦州 121001)E-mail:Li_wanjie1014@163.com

1 引 言

隨著大數(shù)據(jù)共享時代的到來,數(shù)據(jù)的融合能夠更好地促進決策分析.例如,人口普查記錄的融合能夠更全面滿足生活情況的調(diào)研,病人醫(yī)療數(shù)據(jù)的融合有利于醫(yī)院分析疾病成因等信息.然而在數(shù)據(jù)共享帶來極大方便的同時,共享的數(shù)據(jù)存在著隱私泄露的問題.不同的用戶對于數(shù)據(jù)的使用需求不同,當(dāng)用戶的信任等級不同、訪問權(quán)限不同時,需要發(fā)布隱私保護程度不同的數(shù)據(jù),這就需要對數(shù)據(jù)進行分級發(fā)布.因此,在數(shù)據(jù)融合的過程中不泄露數(shù)據(jù)隱私的前提下,針對用戶的不同信任等級、不同訪問權(quán)限或?qū)?shù)據(jù)使用的不同需求,對數(shù)據(jù)進行融合分級發(fā)布,以便達到實現(xiàn)不同等級隱私保護的目的.

國內(nèi)外學(xué)者在數(shù)據(jù)融合安全發(fā)布方面展開了廣泛地研究[1-7].K-Anonymity[1]及其改進算法是重要的隱私保護方法.K-Anonymity要求發(fā)布的數(shù)據(jù)記錄中至少存在k-1條記錄,使得攻擊無法識別區(qū)分,從而保護用戶的隱私信息.K-Anonymity在數(shù)據(jù)融合方面的研究也一直備受關(guān)注.Jiang等人[4]提出了一種安全分布式框架實現(xiàn)了滿足K-匿名的數(shù)據(jù)融合,但當(dāng)數(shù)據(jù)量龐大時,該方法花費的時間過長,而且不能實現(xiàn)三表及以上的數(shù)據(jù)融合.Fung等人[5]提出了一種滿足K-匿名的安全融合數(shù)據(jù)的方法,解決了三表及以上的數(shù)據(jù)融合問題,但是在每次進行特殊化處理時要計算兩方安全最大值,使得整個算法花費較大的時間.文獻[6]提出了一種基于K-Anonymity結(jié)合自頂向下分類樹算法的數(shù)據(jù)融合算法,減少融合過程所花費的時間,提高融合數(shù)據(jù)的準(zhǔn)確性.但是,這種模型很難抵制背景知識攻擊等變體攻擊.文獻[7]提出了CDTT算法,該算法在差分隱私保護下,構(gòu)建動態(tài)分類樹,有效地解決了上述問題,但其算法并沒有考慮到用戶分級的情況,使得發(fā)布的數(shù)據(jù)利用率不高.

針對上述文獻中的不足,提出一種基于差分隱私保護的數(shù)據(jù)分級融合發(fā)布方法,解決了當(dāng)前數(shù)據(jù)融合發(fā)布機制無法抵御背景知識攻擊的缺點,并提供個性化服務(wù)的分級發(fā)布,同時減少數(shù)據(jù)融合花費時間并保證了融合發(fā)布后的數(shù)據(jù)具有較好的質(zhì)量和價值.

2 數(shù)據(jù)分級融合發(fā)布保護的基本工作原理

本節(jié)主要闡述一些基本定義及相關(guān)概念,包括差分隱私、實現(xiàn)機制、分類樹、數(shù)據(jù)融合等.

2.1 差分隱私

Dwork[8]等人在2006年提出了差分隱私保護模型,其具有嚴(yán)格的隱私定義且可以抵御任意背景知識的攻擊.近些年來,被眾多研究者應(yīng)用在隱私保護的場景中.差分隱私保護技術(shù)通過向原始數(shù)據(jù)集的轉(zhuǎn)換或其統(tǒng)計結(jié)果添加噪聲來達到隱私保護的目的.該方法確保了在任一數(shù)據(jù)集中更改一條記錄的操作而不影響查詢的輸出結(jié)果.此外,該模型可以抵御攻擊者掌握了除某一記錄外的所有信息的背景知識攻擊.差分隱私的定義[7]描述如下:

定義1.差分隱私

給定兩個數(shù)據(jù)集D和D′,二者完全相同或者至多相差一條記錄,給定隨機算法A,Range(A)表示A的值域,S為Range(A)的子集.如果A滿足式(1),則算法A滿足ε-差分隱私.

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

(1)

其中,概率Pr[·]表示算法的概率,由算法A決定;ε為隱私預(yù)算,表示算法A的隱私保護程度,ε的值越小,A的隱私保護程度越高.

2.2 實現(xiàn)機制

實現(xiàn)差分隱私保護常介入兩種噪聲機制,分別是拉普拉斯機制和指數(shù)機制[9].本文主要采用Laplace噪音機制.

Laplace機制[10]通過將服從Laplace分布的噪聲介入準(zhǔn)確的查詢統(tǒng)計結(jié)果來達到ε-差分隱私保護的目的.設(shè)Laplace分布Lap(b)位置參數(shù)為0的概率密度函數(shù)為p(x),其表示形式為

(2)

定義2.Laplace機制

圖1 Laplace概率密度函數(shù)Fig.1 Laplace probability density function

圖1為Laplace概率密度函數(shù)[12],從不同參數(shù)的Laplace分布可得,當(dāng)ε的值越小,介入的噪聲越大.

2.3 分類樹

分類樹[13]采用泛化技術(shù)作為形成分類樹的核心技術(shù),將給定數(shù)據(jù)集中的項作為葉子結(jié)點,泛化葉子結(jié)點作為分類樹的節(jié)點,樹的根節(jié)點是所有葉子結(jié)點的集合,其具體表現(xiàn)形式為child(v)→v.圖2給出了數(shù)據(jù)集T={T1,T2,T3,T4}的分類樹.

圖2 簡單數(shù)據(jù)集分類樹Fig.2 Simple dataset classification tree

圖中T{1,2,3,4}是分類樹的根結(jié)點,例如T{1}和T{2}是葉子結(jié)點,泛化為T{1,2}作為分類樹的節(jié)點.在數(shù)據(jù)融合時,數(shù)據(jù)擁有者提供數(shù)據(jù)表的屬性分類樹.

2.4 數(shù)據(jù)融合

數(shù)據(jù)融合是指將兩個數(shù)據(jù)集通過記錄中的相同ID合并或?qū)⒉淮嬖诘腎D記錄加入集合,融合形成新的具有更多屬性、更為全面的數(shù)據(jù)集.數(shù)據(jù)的融合有利于數(shù)據(jù)分析者做更好地決策分析.例如,表1為3個用戶A、B、C在超市S1購買啤酒I1、可樂I2、牛奶I3產(chǎn)生的購物數(shù)據(jù),表2為4個用戶A、B、C、D在超市S2購買啤酒I1、可樂I2、牛奶I3、咖啡I4產(chǎn)生的購物數(shù)據(jù),將表1和表2的數(shù)據(jù)融合生成新的融合數(shù)據(jù)表(如表3所示),為統(tǒng)計并挖掘分析用戶的購買行為做好準(zhǔn)備.

表1 超市S1購物數(shù)據(jù)Table 1 Supermarket S1 shopping data

表2 超市S2購物數(shù)據(jù)Table 2 Supermarket S2 shopping data

表3 融合后購物數(shù)據(jù)Table 3 Shopping data after fusion

3 基于差分隱私的數(shù)據(jù)分級融合發(fā)布機制

3.1 問題定義

對多個數(shù)據(jù)擁有者的數(shù)據(jù)表進行融合,每張數(shù)據(jù)表代表完整數(shù)據(jù)集的一部分屬性.由于數(shù)據(jù)使用者的權(quán)限等級、付費情況或?qū)τ诎l(fā)布數(shù)據(jù)的使用需求不同,需要對用戶進行分級處理,利用用戶的等級劃分,對數(shù)據(jù)屬性的重要度進行劃分,按照重要程度設(shè)置不同的隱私預(yù)算,在融合數(shù)據(jù)集中加入與其對應(yīng)的Laplace噪聲.同時保證融合發(fā)布后的數(shù)據(jù)滿足:

1)數(shù)據(jù)具有較好的利用率,可以有效地提供決策分析等操作;

2)數(shù)據(jù)能夠較好地保護數(shù)據(jù)隱私且不會導(dǎo)致隱私預(yù)算耗盡等問題.

3.2 基本框架

數(shù)據(jù)分級融合發(fā)布主要由多個數(shù)據(jù)源、可信代理及查詢用戶組成.

1)多個數(shù)據(jù)源擁有者通過分類融合算法融合數(shù)據(jù);

2)對融合后的數(shù)據(jù)進行個性化的差分隱私處理,在進行差分隱私處理的過程中,根據(jù)用戶的權(quán)限等級或付費情況,設(shè)置合理的隱私預(yù)算參數(shù);

3)在用戶進行查詢時,為保護查詢用戶的身份不被泄露,使用假名機制來實現(xiàn)對用戶的隱私保護.該數(shù)據(jù)分級融合發(fā)布機制的框架如圖3所示.

圖3 滿足差分隱私保護的數(shù)據(jù)融合發(fā)布框架Fig.3 Data fusion publishing framework satisfying differential privacy protection

在系統(tǒng)初始化階段,首先,查詢用戶需要通過可信代理服務(wù)器利用假名機制獲得與其身份對應(yīng)的假名標(biāo)識符(Alias(ID),ID為用戶身份).其次,依據(jù)用戶訪問權(quán)限、付費情況或?qū)τ跀?shù)據(jù)使用的不同需求,進行等級劃分,訪問權(quán)限高或付費多的資源需要分配高等級,反之則分配低等級(相應(yīng)等級記為L).可信代理將用戶等級存儲至查詢服務(wù)器.數(shù)據(jù)融合發(fā)布系統(tǒng)根據(jù)用戶身份對應(yīng)等級,設(shè)置不同的隱私預(yù)算ε,發(fā)布具有相應(yīng)隱私保護程度的數(shù)據(jù)集.身份假名與相應(yīng)隱私預(yù)算等級劃分如表4所示.

表4 身份假名-隱私預(yù)算等級劃分表Table 4 Identity pseudonym-privacy budget breakdown table

3.3 算法的基本思想

在數(shù)據(jù)融合發(fā)布機制中,通過介入不同數(shù)值拉普拉斯噪聲實現(xiàn)敏感數(shù)據(jù)的隱私保護,本算法根據(jù)設(shè)定的用戶不同等級以及與用戶等級相應(yīng)的的隱私預(yù)算ε,實現(xiàn)不同隱私保護程度與查詢用戶級別的對應(yīng)關(guān)系,最終輸出介入不同數(shù)值拉普拉斯噪聲的差分隱私融合算法融合后的數(shù)據(jù),實現(xiàn)對融合的數(shù)據(jù)分級化發(fā)布.

對于數(shù)據(jù)融合而言,首先初始化一個數(shù)據(jù)集D0,選出D0出現(xiàn)一次的記錄,根據(jù)此記錄中任意兩項出現(xiàn)的次數(shù),選擇兩項作為第一個分支,然后選出的次數(shù)出現(xiàn)最少的兩項,選擇在其所在行中的最大的值作為第二個分支,依次迭代地選取其它項集與這兩個分支組合,直至所有的項集被選出,為D0構(gòu)造分類樹C-Tree(0).設(shè)置更新增量H以及與查詢用戶級別對應(yīng)的隱私預(yù)算εi,其中根據(jù)查詢用戶授權(quán)或付費情況等方式來劃分用戶級別,按照支付金額或授權(quán)大小,為用戶分配高級別或低級別,并且相應(yīng)獲得的查詢結(jié)果的準(zhǔn)確性也遵循從高到低的原則.當(dāng)新的數(shù)據(jù)集Di與D0融合時,先將Di中記錄添加到C-Tree(i-1)的根節(jié)點,對Di中的記錄作下列步驟:(1)如果某記錄不為空且被分配到C-Tree(i-1)的非葉子節(jié)點中,就按照C-Tree(i-1)的分類方法分配該記錄;(2)如果某記錄被分配到C-Tree(i-1)的葉子結(jié)點,則分割該節(jié)點并重新分配該節(jié)點的差分隱私預(yù)算;(3)如果某記錄為空,則對下一條記錄做上述步驟,直至所有記錄分配完生成新的分類樹C-Tree(i),根據(jù)分配好的隱私預(yù)算向C-Tree(i)的葉子節(jié)點添加Laplace噪音,最后依次迭代對于不同的隱私預(yù)算參數(shù)ε進行以上步驟即可,最終產(chǎn)生具有不同隱私保護級別的融合后的隱私數(shù)據(jù).

3.4 算法的描述

采用上述思想設(shè)計的算法過程如下.

算法1.

輸入:初始數(shù)據(jù)集D0,D1,D2,…,DH,用戶ID(m),更新增量H

1.用戶ID(m)→Alias(ID(m))→Lm→εm

3.構(gòu)造D0的矩陣A

4. 找到A中出現(xiàn)任意兩項出現(xiàn)次數(shù)最多對應(yīng)的項集Mmax[i,j]

5.Q1=Mmax[i,j]

6. 在i,j所在行找出次數(shù)最小的項集Mmin[t,s]

7. 在t,s所在行找到最大的項集Mmax[a,b]

8.Q2=Mmax[a,b]

9.迭代上述步驟對于Q1,Q2

//**構(gòu)造D0的分類樹C-Tree(0)

10.對D1,D2,…,DH做下列步驟

11.V=D0,D1,D2,…,DH

12.G=Di中的所有記錄

13.g→cut=C-Tree(0)的根結(jié)點

15. 將G添加到C-Tree(i-1)的根結(jié)點

16. 對G中的記錄gi做下列步驟

17. IFgi不為空且不是葉子結(jié)點

按照C-Tree(i-1)的分類方法分配此節(jié)點

20.V=gi∪V

21. IFgi不為空或gi分配到葉子結(jié)點

22. 分割該節(jié)點,執(zhí)行18至20步

23. ELSE IFgi為空

24. 則返回16步

25.返回C-Tree(i)

//**分配Di中的所有記錄

26.發(fā)布融合后的C-Tree(i)中葉子結(jié)點的信息

3.5 算法隱私保護效果分析

1)數(shù)據(jù)的分級融合滿足差分隱私

通過Laplace機制添加噪聲實現(xiàn)了數(shù)據(jù)敏感屬性隱私保護,使用假名機制有效地保護了用戶的身份隱私,將用戶訪問權(quán)限、付費情況或?qū)τ跀?shù)據(jù)使用的不同需求,進行等級劃分,并與隱私預(yù)算εm關(guān)聯(lián)實現(xiàn)數(shù)據(jù)分級融合,根據(jù)差分隱私的串行性質(zhì),分級融合機制滿足εm-差分隱私.實現(xiàn)融合數(shù)據(jù)個性化的隱私保護程度,分級融合數(shù)據(jù)發(fā)布機制使得查詢輸出結(jié)果可控.

2)分級融合發(fā)布機制滿足差分隱私

3.6 正確性與復(fù)雜性分析

正確性:

1)對于數(shù)據(jù)信息需求而言,基于差分隱私的數(shù)據(jù)融合方法融合后的數(shù)據(jù)具有可靠的利用率,可以實現(xiàn)決策分析等操作工作;

2)對于數(shù)據(jù)隱私而言,使用差分隱私保護方法能夠彌補K-匿名不能抵制背景知識攻擊的缺點,而且不會導(dǎo)致隱私預(yù)算耗盡等問題.

復(fù)雜性:算法主要花費表現(xiàn)在以下兩個方面：

1)構(gòu)造分類樹.選出數(shù)據(jù)集出現(xiàn)一次的記錄,根據(jù)此記錄中任意兩項出現(xiàn)的次數(shù),選擇兩項作為第一個分支,然后選出的次數(shù)出現(xiàn)最少的兩項,選擇在其所在行中的最大的值作為第二個分支,依次迭代地選取其它項集與這兩個分支組合,直至所有的項集被選出,在此過程中,需要根據(jù)任意兩項出現(xiàn)的次數(shù)生成關(guān)系矩陣,遍歷整個數(shù)據(jù)集.

2)數(shù)據(jù)融合隱私預(yù)算分配.當(dāng)新的數(shù)據(jù)集Di進行融合時,Di中的記錄被插入到C-Tree(i-1)的根結(jié)點中,迭代地分配到不同的分支中,并且重新分配隱私預(yù)算.在此過程中需要根據(jù)分類樹將融合的數(shù)據(jù)記錄劃分為單個子分割.

其中,構(gòu)造初始分類樹的時間復(fù)雜度為O(|L|·|I|),|L|表示初始數(shù)據(jù)集的長度,數(shù)據(jù)融合的時間復(fù)雜度為O(N·|D|·|I|),N表示融合數(shù)據(jù)集個數(shù),|D|表示融合數(shù)據(jù)集長度.

4 實驗分析

4.1 實驗參數(shù)設(shè)置

本文設(shè)計的算法由Java語言和MyEclipse集成開發(fā)軟件開發(fā)實現(xiàn).實驗硬件環(huán)境為Inter(R)Core I3 4510CPU 3.5GHz處理器,內(nèi)存16G;操作系統(tǒng)為Windows 7.在實驗數(shù)據(jù)方面,采用從Http://ipums.org下載的Income數(shù)據(jù)集,該數(shù)據(jù)集包含Age、Education、Gender、Birthplace、Work-class、Occupation、Income、Race、Marital status等8個屬性,其中Income為敏感屬性,該數(shù)據(jù)集的8個屬性全部為數(shù)值型數(shù)據(jù).

4.2 實驗數(shù)據(jù)分析

圖4反映了隱私預(yù)算參數(shù)ε與采用拉普拉斯機制實現(xiàn)隱私保護的查詢結(jié)果錯誤率的對應(yīng)關(guān)系.

圖4 隱私參數(shù)與查詢結(jié)果錯誤率的對應(yīng)關(guān)系Fig.4 Relationship between privacy parameters and the error rate of query results

對于用戶等級的劃分標(biāo)準(zhǔn),可依據(jù)發(fā)布數(shù)據(jù)錯誤率來衡量.若數(shù)據(jù)使用者期望得到查詢結(jié)果錯誤率小于 1%的數(shù)據(jù),則取ε=0.1;若期望查詢結(jié)果錯誤率在10%～20%之間的數(shù)據(jù),則取ε=0.005.由此可見,可以把ε取自集合(0.001,0.1),按照ε的取值大小來對應(yīng)劃分用戶等級.

實驗主要測試針對不同的差分隱私預(yù)算參數(shù)ε,不同數(shù)量的屬性,不用數(shù)量的數(shù)據(jù)表,完成數(shù)據(jù)融合所花費的時間和得到融合發(fā)布記錄的分類精度.

98765430100200300400融合的數(shù)據(jù)量Ts/CDTTQ3_HDFPMQ3_CDTTQ5_HDFPMQ5_圖5 兩方數(shù)據(jù)融合花費時間Fig.5 Datafusiontakestime98765430100200300400500融合的數(shù)據(jù)量Ts/HDFPMQ3_HDFPMQ5_圖6 三方數(shù)據(jù)融合花費時間Fig.6 Tripartitedatafusiontakestime

為了與CDTT算法[7]的性能進行比較,實驗中取ε=0.005,數(shù)據(jù)集記錄數(shù)為10k～400k,比較二者花費時間.圖5為Income數(shù)據(jù)集分為兩方數(shù)據(jù),比較HDFPM算法與CDTT算法進行數(shù)據(jù)融合時花費的時間,Qi表示融合記錄的屬性數(shù)量.從圖5中可以看出,在相同的隱私預(yù)算參數(shù)ε和相同的Qi下,HDFPM算法進行數(shù)據(jù)融合所花費時間比CDTT算法花費更少.

圖6為HDFPM算法在屬性不同情況下,三方數(shù)據(jù)融合所花費的時間.從圖6中可以看出,融合同一大小的數(shù)據(jù)記錄數(shù),屬性增加時,花費時間會增加;隨著數(shù)據(jù)記錄數(shù)的增加,二者花費時間基本相同.

實驗中分別取ε=0.05、ε=0.5、ε=1.0滿足來分級條件,Qi=5,以此進行實驗,對比提出算法HDFPM與CDTT算法、DiffGen-Max算法融合后數(shù)據(jù)分類的精確度.圖7為不同ε下三種算法的分類精度圖.

從圖7中可以看出,當(dāng)ε值較小時,即用戶等級較低,三種算法分類精度基本一致,但隨著隱私預(yù)算參數(shù)的增加,即用戶等級的增大,HDFPM算法算法相比于CDTT算法、DiffGen-Max算法分類精度相對更高,數(shù)據(jù)質(zhì)量相對更好.

圖7 不同ε時分類精度Fig.7 Classification accuracy at different ε

5 結(jié)束語

本文提出的基于差分隱私的數(shù)據(jù)分級融合發(fā)布機制,在數(shù)據(jù)融合發(fā)布過程中,保持了融合后數(shù)據(jù)的可用性,同時保護了數(shù)據(jù)中的敏感信息.本文方法與基于K-匿名系列方法相比,在融合的過程中,主要有三處改進:第一點是將數(shù)據(jù)融合與差分隱私保護結(jié)合,把差分隱私技術(shù)引用到數(shù)據(jù)融合中,使得融合發(fā)布后的數(shù)據(jù)更具安全性;第二點采用分級方法,使得融合后的數(shù)據(jù)對于隱私保護程度更具針對性;第三點提出的基于分類樹的隱私預(yù)算方法能夠更合理地分配隱私預(yù)算,避免隱私預(yù)算的過早耗盡.實驗表明,本文算法既能在一定程度上減少花費時間實現(xiàn)數(shù)據(jù)的分級融合,又能保持?jǐn)?shù)據(jù)的可用性且能夠有效的保護敏感數(shù)據(jù)的隱私性.未來將繼續(xù)研究差分隱私保護在數(shù)據(jù)融合發(fā)布中的應(yīng)用.