一種面向多次發布的隱私保護模型

趙 皎, 沈明玉, 胡學鋼, 王正彬

(合肥工業大學 計算機與信息學院,安徽 合肥 230009)

一種面向多次發布的隱私保護模型

趙 皎, 沈明玉, 胡學鋼, 王正彬

(合肥工業大學 計算機與信息學院,安徽 合肥 230009)

文章提出了一種面向多次發布的數據庫隱私保護模型,通過等價類的動態調整來隱藏數據和等價類間的映射關系,降低隱私泄露的風險。利用偽數據調節數據的多樣性以滿足匿名規則的要求,偽數據亦可作為噪聲數據增加攻擊者的分析難度,提高隱私保護強度。在UCI數據庫上進行的仿真實驗結果表明,該模型能夠有效減少因多次發布帶來的隱私泄露。

隱私保護;匿名規則;多次發布;隱私泄露;限制發布

0 引 言

互聯網大數據背景下利用數據發布提供信息服務的同時,也帶來個體隱私泄露的風險。數據庫隱私保護技術已經成為信息安全領域的研究熱點。

限制發布是常用的3種數據庫隱私保護技術之一,采用數據的匿名化來實現隱私保護[1-7]。近年來,國內外學者圍繞數據匿名化已做了大量研究工作。文獻[5]提出了一種(l,α)-多樣性模型,要求一個等價類中敏感值的權重和不小于α,以避免高敏感度的敏感值出現在同一等價類中,從而實現敏感值的均勻分配;文獻[7]提出了一種基于敏感屬性值語義桶分組的t-closeness隱私模型,該模型根據敏感屬性的層次樹結構對數據表進行語義相似性桶分組劃分,然后采用貪心思想生成滿足要求的最小等價類。該模型在減少信息損失的前提下保護敏感信息不被泄露。

以上對匿名化的研究可以有效實現對單次發布數據的隱私保護,但是對多次發布帶來的隱私泄露問題的解決仍存在不足。目前國內外學者對面向多次發布的數據庫隱私保護問題的研究已取得了一定的成果。文獻[8]引入敏感屬性樹的思想,將敏感屬性逐級排列,確保敏感屬性多樣性，該模型將敏感屬性進行泛化處理,增強了敏感信息的保護強度,但是沒有考慮到攻擊者可能通過分析準標識符與敏感屬性間的關聯關系而得到某些個體的隱私信息;文獻[9]結合局部重編碼泛化方法改進匿名算法,提出了一種數據重發布的隱私保護模型,降低發布數據的信息損失，但是該算法的處理復雜度較高;文獻[10]首先定義了等價類的相容性,允許一個元組同時存在于2個等價類中,增加了數據的多樣性,但這也將增加數據的冗余性，該方法只給出了數據增加時的處理策略,沒有給出因多次發布帶來的隱私泄露問題的解決方法。

針對上述因多次發布可能存在隱私泄露的問題,本文對面向多次發布的隱私保護模型進行研究,模型中引入了動態等價類及偽數據等技術。

1 技術背景

1.1 數據庫隱私保護相關概念

(1) 數據匿名化。數據匿名化是限制發布技術中的一個主要方法,使觀察者通過發布的數據難以確定敏感屬性和個體之間的關聯關系,從而保護個體的隱私信息。數據匿名化一般采用抑制和泛化2種操作實現。抑制即不發布某數據項,泛化即對數據項進行更加概括的描述。

(2) 屬性的劃分。在隱私保護技術中,數據匿名化技術將數據表中的屬性分為標識符、準標識符和敏感屬性3類。標識符是指能夠直接標識個體身份的屬性,如姓名等。準標識符是不能直接標識個體的身份,但是與其他屬性鏈接可以確定個體身份的屬性,如年齡、地址等。敏感屬性即描述個體隱私信息的屬性,如疾病等。

(3) 等價類。數據匿名化需要對元組的準標識符進行泛化處理,使原本精確的值泛化為抽象的范圍或者更為概括的表達。經泛化后的數據表中會出現準標識符值相同的元組,將這些準標識符值完全相同的元組歸為一個等價類。同一個等價類中的元組除敏感屬性外,所有準標識符值完全相同,使得攻擊者難以在準標識符上區分這些元組,保護了個體的隱私信息。

1.2 常用的匿名規則

(1)k-anonymity。文獻[1]首次提出了k-anonymity匿名規則,若數據表T中任意一個元組在準標識符上至少不能和其他k-1個元組區分,則稱該數據表滿足k-anonymity匿名規則通過k個不可區分的個體,使攻擊者不能判別敏感屬性和個體之間的關聯關系。k-anonymity的缺陷是沒有對敏感屬性加以約束,容易受到同質攻擊和背景知識攻擊。

(2)l-diversity。在k-anonymity的基礎上,文獻[2]提出了l-diversity匿名規則,要求每個等價類中不同的敏感屬性值至少有1個。l-diversity在敏感屬性的多樣性上加以約束,克服了同質攻擊。

(3)t-closeness。文獻[3]在k-anonymity和l-diversity的基礎上提出了t-closeness匿名規則,該匿名規則要求,所有等價類中敏感屬性值的分布盡量接近該屬性的全局分布。t-closeness克服了同質攻擊和相似攻擊。

2 面向多次發布的隱私保護模型

2.1 模型的基本思想

本文提出的面向多次發布的隱私保護模型是對傳統隱私保護模型的改進,旨在解決因多次發布帶來的隱私泄露問題。偽數據的運用可以使本模型能夠有效綜合限制發布與數據失真的技術特點,給發布的數據添加噪聲,增加隱私信息的分析難度,調節發布數據的多樣性,提高隱私性。靜態的等價類容易造成更新數據與等價類間映射關系的暴露,本模型引入動態等價類技術,通過等價類的動態調整和維護來隱藏數據與等價類間的映射關系,增強隱私保護強度。

2.2 偽數據

偽數據是一種非真實的數據,在本模型中用于調節數據的多樣性和產生噪聲數據。偽數據的準標識符值與其等價類的準標識符值相同,根據偽數據的添加目的來確定它的敏感屬性的取值。除指定的合法用戶外,其他觀察者均不能區分偽數據與真實數據,現有的數據庫隱私保護模型主要采用偽數據表來對偽數據進行維護。偽數據表是一張用來記錄偽數據信息的數據表,表中包括偽數據所在的表名、偽數據的ID等屬性。

本文采用偽數據表的動態維護,以確保偽數據信息的真實性和實時性。為了提高偽數據ID的保密性,本模型利用Elgamal數字加密算法對其進行加密處理,將加密后的密文存入偽數據表中。

偽數據的數據多樣性調節和數據失真效果增加了攻擊者的分析難度,進一步提高了隱私保護強度。以某一等價類為例,見表1、表2所列。

表1 某等價類中的數據

表2 沒有添加偽數據的等價類

表1為某一個等價類中的數據,若ID為4的元組被刪除,如果不添加偽數據，那么見表2所列。攻擊者通過分析2個表之間的差異可以得出被刪除元組敏感屬性“疾病”的值為“肺炎”,并且獲得該元組準標識符值的取值范圍,結合已獲得的背景知識可能確定該元組對應個體的身份,導致隱私信息泄露。

在本模型中,刪除數據時直接將其轉換為偽數據,此時表1中ID為4的元組已經為偽數據。偽數據的添加使攻擊者不能分析出2次發布的數據之間的差異,從而避免了因多次發布數據間的關聯性帶來的隱私泄露問題。

2.3 動態等價類

在傳統的隱私保護模型中,更新某元組后只相應更新其所在的等價類,不處理其他等價類。數據重發布后,攻擊者通過分析多次發布數據間的差異,可以很容易分析得到某些隱私信息。在本模型中,某個等價類調整時也相應調整其他部分等價類,通過等價類的動態調整隱藏更新數據與等價類間的映射關系。

在數據重發布之前,對所有等價類進行維護,完成維護后判斷各等價類中是否有元組的更新。若某等價類中插入了新的數據,隨機選擇其他部分等價類,添加相應的偽數據;若某等價類的準標識符值被修改,隨機修改部分等價類的準標識符值,則使攻擊者不能準確確定更新數據所在的等價類。

1個簡單的等價類更新過程如圖1所示。

圖1 更新前、更新后(靜態、動態)的等價類

圖1中的數據表有年齡和郵編2個屬性;e1和e22個等價類。更新前的數據表添加一個元組r后,若采用靜態等價類,則更新后的等價類如圖1b所示。攻擊者分析圖1a、圖1b的差異可以很容易地確定添加的元組在等價類e1中,并且可以得出添加的元組r的年齡的值為a2′-a2,元組r的信息遭到泄露。圖1c所示為采用動態等價類更新后的結果,向等價類e1中添加一個元組r時,同時調整等價類e2的匿名范圍。攻擊者分析圖1a、圖1c間的差異,得到2個等價類均被修改,從而不能確定添加的元組所在的等價類,隱藏了元組r和等價類e1間的映射關系。

3 數據更新及等價類維護的策略

原數據表中有元組更新時,選擇相應的處理策略更新等價類,定期對更新后的數據進行重發布。數據重發布前,對所有的等價類進行維護和調整,確保重發布的數據滿足規定的匿名規則。

3.1 數據更新時的處理策略

插入數據時,以數據泛化后信息損失最少為原則,選擇一個等價類插入數據,修改該等價類準標識符的值;刪除數據時,直接將被刪除的數據轉換為偽數據;修改數據時,首先判斷修改后數據的準標識符值是否超出該等價類的最大泛化區間,若沒有超出則修改該等價類的準標識符,若超出最大泛化區間則從該等價類中刪除該數據,選擇一個使其信息損失最少的等價類插入。

3.2 等價類的動態維護

數據多次更新后,可能導致某些等價類中偽數據過多,數據的真實性降低;或者等價類的準標識符匿名范圍過大,導致數據的效用性降低。因此需對等價類進行動態維護,維護的方法包括等價類的分解、取消和合并。

3.2.1 分解等價類

(1) 分解條件。1個等價類中真實數據個數大于2k。

(2) 分解方法。刪除所有的偽數據,將等價類中真實數據按敏感屬性值分組。分別取各個桶中1/2的元組組成一個等價類,另1/2組成1個等價類。

3.2.2 取消等價類

(1) 取消條件。1個等價類中真實數據個數小于k/2或不同敏感屬性值個數小于1/2。

(2) 取消方法。刪除該等價類中偽數據,將真實數據選擇使其信息損失最小的等價類插入。

3.2.3 合并等價類

(1) 合并條件。相鄰的2個等價類均滿足取消等價類的條件。

(2) 合并方法。刪除2個等價類中的偽數據,合并2個等價類中的真實數據,并修改等價類準標識符的值。

在數據重發布之前,首先判斷各個等價類是否需要維護,若滿足上述等價類的分解、取消或合并的條件,對等價類進行相應的維護。在完成等價類的維護后,向不滿足匿名要求的等價類中添加偽數據,確保所有等價類均已滿足規定的匿名規則后重新發布數據。

4 實驗與分析

本實驗采用UCI機器學習數據庫中的Adult數據集,該數據集總共包含32 561行數據,刪除包含缺失值的數據剩余30 725行數據。選取其中7個屬性進行實驗,將marital-status作為敏感屬性,{age,workclass,education,education-num,race,sex}作為準標識符。

本實驗從隱私性和多樣性2個方面將本模型與文獻[7,9]提出的方法進行對比分析。文獻[7]是對t-closeness隱私保護模型的改進,主要是對單次發布的數據進行隱私保護。文獻[9]對局部重編碼泛化算法進行了改進,旨在解決多次發布帶來的隱私泄露問題。

4.1 隱私性分析

本實驗通過計算隱私信息泄露的比例來分析隱私保護的強度。實驗方法如下:① 從Adult數據集選取20 000行數據進行匿名泛化后首次發布;② 分別對已發布的數據進行插入、刪除和修改處理,涉及的數據均為200行;③ 數據重新發布;④ 對多次發布的數據進行人工分析,計算隱私泄露的比例,結果如圖2所示。

圖2 多次插入數據、刪除數據及修改數據后隱私信息被泄露比例

從圖2可以看出,由于文獻[7]沒有給出針對多次發布隱私泄露問題的處理策略,隨著發布次數的增多,隱私泄露比例迅速增大。文獻[9]雖然針對多次發布隱私泄露問題給出了處理策略,但是其采用的是靜態等價類,多次發布后數據間的差異會明顯增多,隱私泄露也會明顯增多。本模型中動態等價類技術可以有效隱藏數據與等價類間的映射關系,增加隱私信息的分析難度;偽數據作為噪聲數據給攻擊者增加干擾,有效減少多次發布帶來的隱私泄露比例。

4.2 多樣性分析

發布數據的多樣性越高,即等價類中數據的相異程度越高,攻擊者分析隱私信息的難度就越大,數據的隱私性越強。對于多樣性的度量,實驗參考了文獻[11]給出的數據表平均多樣性的度量公式,即

(1)

D(Ε)=distinct(Ε)+ωH(Ε)

(2)

其中,distinct(E)為等價類E中敏感屬性值的種類個數;H(E)為等價類E中敏感值的相異程度;ω為發布者自定義的權值;D(E)為等價類E多樣性的大小(下文均簡稱多樣性);DOT(T)為數據表T的多樣性。l的值表示等價類中敏感屬性值的種類個數,l越大,distinct(E)的值越大,數據表的平均多樣性就越大。利用(1)式、(2)式計算l取不同值時使用以上3種方法發布數據的多樣性,計算結果如圖3所示。

圖3 不同l值下數據表多樣性的比較

由圖3可以看出,隨著l的增大發布數據的多樣性均會逐漸增大。在l相同的情況下,由于文獻[7,9]中的方法沒有采用偽數據,發布數據的多樣性比本模型中發布數據的多樣性低。在本模型中,數據更新后會添加相應的偽數據來調節發布數據的多樣性。

5 結 論

為解決多次發布帶來的隱私泄露問題,本文基于限制發布技術提出了一個面向多次發布的數據庫隱私保護模型。模型引入了動態等價類和偽數據等技術,并對數據更新給出相應的處理策略。偽數據不僅調節數據多樣性,還作為噪聲數據給攻擊者增加干擾。等價類的動態調整和維護有效隱藏了數據與等價類間的映射關系,有效降低了多次發布帶來的隱私泄露風險。后續將針對處理開銷及信息損失較大等問題進行進一步研究。

[1] SWEENEY L.Achievingk-anonymity privacy protection using generalization and suppression[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):571-588.

[2] MACHANAVAJJHALA A,KIFER D,GEHRKE J,et al.l-diversity:privacy beyondk-anonymity[J].Acm Transactions on Knowledge Discovery from Data,2007,1(1):24.

[3] LI N,LI T,VENKATASUBRAMANIAN S.t-closeness:privacy beyondk-anonymity andl-diversity[C]//IEEE 23rd International Conference on.Data Engineering,2007.ICDE 2007.[S.l.]:IEEE,2007:106-115.

[4] 周水庚,李豐,陶宇飛,等.面向數據庫應用的隱私保護研究綜述[J].計算機學報,2009,32(5):847-861.

[5] SUN Xiaoxun,LI Min,WANG Hua.A family of enhanced (L,alpha)-diversity models for privacy preserving data publishing.[J].Future Generation Computer Systems the International Journal of Grid Computing Theory Methods & Applications,2011,27(3):348-356.

[6] LIU J,WANG K.On optimal anonymization forl-diversity[C]//2010 IEEE 26th International Conference on.Data Engineering (ICDE).[S.l.]:IEEE,2010:213-224.

[7] 張健沛,謝靜,楊靜,等.基于敏感屬性值語義桶分組的t-closeness隱私模型[J].計算機研究與發展,2014,51(1):126-137.

[8] ZHAO Y,WANG J,ZHU Q S,et al.A novel privacy preserving model for datasets re-publication[J].Advanced Materials Research,2010,108/109/110/111:1433-1438.

[9] 武毅,王丹,蔣宗禮.基于事務型k-anonymity的動態集值屬性數據重發布隱私保護方法[J].計算機研究與發展,2013,50(增刊1):248-256.

[10] BYUN J W,SOHN Y,BERTINO E,et al.Secure anonymization for incremental datasets[J].Third Vldb Workshop on Secure Data Management,2006:48-63.

[11] 韓建民,于娟,虞慧群,等.面向數值型敏感屬性的分級l-多樣性模型[J].計算機研究與發展,2011,48(1):147-158.

Aprivacyprotectionmodelfordatare-publication

ZHAO Jiao, SHEN Mingyu, HU Xuegang, WANG Zhengbin

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

A privacy protection model for data re-publication is put forward. The mapping relations between data and equivalent classes are hidden by adjusting equivalence classes dynamically, which can reduce the risk of privacy leakage. Pseudo data is used to adjust data diversity to meet the diversity requirement of anonymous rules, and to increase the difficulty of analysis for attackers as noise data. The results of the experiments on the UCI database show that under the premise of improving the diversity of the released data, this model can effectively reduce the privacy disclosure risks caused by the multiple releases.

privacy protection; anonymous rule; data re-publication; privacy disclosure; limited release

2016-03-03；

2016-04-20

國家自然科學基金資助項目(61273292)

趙 皎(1990-),女,河北石家莊人,合肥工業大學碩士生; 沈明玉(1962-),男,江蘇興化人,博士,合肥工業大學副教授,碩士生導師,通訊作者,E-mail:shenmy@126.com; 胡學鋼(1961-),男,安徽當涂人,博士,合肥工業大學教授,博士生導師.

10.3969/j.issn.1003-5060.2017.10.008

TP393

A

1003-5060(2017)10-1338-05

(責任編輯 張 镅)