多維數(shù)值敏感屬性隱私保護數(shù)據(jù)發(fā)布方法

劉騰騰 倪巍偉 崇志宏 張 勇

(東南大學計算機科學與工程學院,南京 210096)

近年來,數(shù)值敏感屬性的隱私保護數(shù)據(jù)發(fā)布得到了研究者的廣泛關(guān)注.在現(xiàn)實應用中,發(fā)布的數(shù)據(jù)中往往涉及多個敏感屬性,而現(xiàn)有的數(shù)值敏感數(shù)據(jù)發(fā)布方法[1-9]大多僅針對單一敏感屬性的情況,直接將現(xiàn)有的方法應用于多敏感屬性的數(shù)據(jù)可能導致隱私信息的大量泄漏.

本文在已有研究工作的基礎(chǔ)上對數(shù)值敏感屬性隱私數(shù)據(jù)發(fā)布問題進行研究.首先提出針對單維數(shù)值敏感屬性的 l-SNSA算法,通過理論分析證明了其有效性和安全性.并對算法進一步研究,提出了較好地解決多維數(shù)值型敏感屬性數(shù)據(jù)發(fā)布問題的 l-MNSA算法,有效避免多維數(shù)值敏感屬性近似猜測攻擊,保證數(shù)值敏感屬性隱私數(shù)據(jù)發(fā)布的安全性.

1 相關(guān)工作

在數(shù)值敏感屬性的隱私保護數(shù)據(jù)發(fā)布中,即使敏感屬性不相同,當敏感屬性相近時也會造成隱私信息的泄露：攻擊者可以很容易獲取敏感屬性在某一較小范圍內(nèi)的信息,即為近似猜測攻擊.

為避免近似猜測攻擊,文獻[7]提出(ε,m)-匿名模型,要求在某一準標識符元組 G中,對任一敏感屬性 x,至多有 1/m的記錄的敏感屬性接近于 x,接近程度取決于 ε,這樣解決了單維數(shù)值敏感屬性的近似猜測問題.但(ε,m)-匿名算法要求用戶輸入 2個參數(shù)(ε和 m),且不同參數(shù)對結(jié)果影響較大,對先驗知識的要求較高.并且,(ε,m)-匿名算法并不適用于多維數(shù)值敏感屬性的情況.如表 1為原始數(shù)據(jù)表,表 2為對工資維(1 000,3)-匿名處理后的發(fā)布結(jié)果,其中 t2記錄被隱匿.工資和獎金是敏感屬性,需要保護以避免攻擊者獲知其確切數(shù)值.年齡和郵編是準標識符屬性,通過聯(lián)合準標識符屬性可以標識個體信息.當攻擊者獲知 t1的年齡為 17及郵編為 120000時,將很容易在表 2中獲知 t1屬于第 1組,其獎金有 75%的概率在 1 000附近,這就造成了數(shù)值敏感屬性的近似泄露.

表1 微數(shù)據(jù)集合

表2 工資維(1000,3)-匿名后的數(shù)據(jù)集合

當數(shù)據(jù)表中準標識符屬性維數(shù)較高時,由于可被用來做推斷攻擊的屬性組合數(shù)會達到指數(shù)級別,損失較少的信息匿名發(fā)布數(shù)據(jù)將會變得非常困難,直接通過概化和隱藏的方法對數(shù)據(jù)進行 k-匿名處理會損失大量信息[10].文獻[6]提出了一種不基于概化和隱藏的方法——分解(anatomy)方法.它將原始數(shù)據(jù)表的準標識符屬性和敏感屬性分別發(fā)布到 2張表中,利用 2張表的有損連接來實現(xiàn)對隱私數(shù)據(jù)的保護,發(fā)布的數(shù)據(jù)滿足 l-多樣性的要求.

以上提出的敏感數(shù)據(jù)發(fā)布方法都是針對單一敏感屬性數(shù)據(jù)情況.在有多個敏感屬性的情況下,上述方法都只能保護一維敏感屬性的安全性,而無法對所有敏感屬性都給予足夠的保護.尤其在發(fā)布多維數(shù)值敏感屬性的數(shù)據(jù)時,需要考慮到避免所有敏感屬性的近似猜測攻擊,而找到均衡所有數(shù)值敏感屬性安全性的分組只能采用窮舉的辦法,這就需要有一個啟發(fā)式的方法,用合理的時空消耗取得盡量好的發(fā)布效果.

2 多維數(shù)值敏感屬性數(shù)據(jù)發(fā)布

假設(shè)用戶要發(fā)布數(shù)據(jù)的模式為 T{A1,…,Aa,S1,…,Sb}.其中 Ai為準標識符屬性,Si為敏感屬性.設(shè) T中含有 n條記錄,即 |T|=n,其中每條記錄記為 ti.另 t.X表示記錄 t的 X屬性值.

本文所提出的算法都要求給定 l,發(fā)布的數(shù)據(jù)都滿足 l多樣性.分組的發(fā)布采用分解的方法,將準標識屬性與敏感屬性分解發(fā)布.發(fā)布數(shù)據(jù)的查詢準確性由每個分組的數(shù)據(jù)數(shù)目 l決定,l越大,準確性越低.

2.1 l-SNSA算法

l-SNSA(l-single numerical sensitive attribute)算法針對敏感屬性為數(shù)值屬性且只有一維的情況.根據(jù)啟發(fā)式的思想,在每次選擇時都選擇當前分組可選的最優(yōu)記錄.具體做法如下：將記錄按敏感屬性值排序,依次選擇第 in/l條記錄,共選擇 l(當n%l=0)或 l+1(當 n%l!=0)條記錄作為 1個分組,這樣能使其滿足 l多樣性且使差異度最大.重復上述過程,直到無法構(gòu)成一個完整的分組為止.可以證明,l-SNSA匿名算法在滿足較好的查詢準確性的條件下,有最大的組內(nèi)最小差異.記一個發(fā)布分組的敏感屬性值間的最小差值為 d,所有發(fā)布分組中最小的 d稱為組內(nèi)最小差異.組內(nèi)最小差異表示了發(fā)布結(jié)果對敏感屬性最小的保護程度,組內(nèi)最小差異越大,發(fā)布結(jié)果的安全性越高.

性質(zhì) 1 l-SNSA匿名算法在盡可能提高查詢準確性的條件下,有最大的組內(nèi)最小差異.

證明 由于發(fā)布數(shù)據(jù)的查詢準確性由每個分組的數(shù)據(jù)數(shù)目 l決定,l越大,準確性越低,因此應盡可能減少每個分組的數(shù)據(jù)數(shù)目,當數(shù)據(jù)數(shù)目為 l時查詢準確性最好.易知 l-SNSA匿名算法發(fā)布的數(shù)據(jù)中,n%l個分組有 l+1條記錄,其他分組均為l條記錄,盡可能提高了查詢準確性.在保證有同等查詢準確性的條件下,假設(shè)有更好的分組方法G′,使得分組后的組內(nèi)最小差異較上述過程得到的分組 G大.設(shè) G中有組內(nèi)最小差異的一組為 g1,且其中 2條記錄 t1與 t2的差值 Ddist(t1,t2)為最小,不妨設(shè) t1的敏感屬性值比 t2小.由于 G′的組內(nèi)最小差異更大,G′中每 2條記錄的差值都應比 Ddist(t1,t2)大 .設(shè) G′中包含 t1記錄的一組為 g′1,為保證組內(nèi)最小差異比 Ddist(t1,t2)大,應選擇 1條大于t2的敏感屬性值的記錄 t3與其分為一組.根據(jù) l-SNSA算法的分組過程可知,t1與 t2間有 n/l-1條記錄,加上 t2共有 n/l條記錄,要使 n/l條記錄都處于不同的分組中,應有 n/l個分組,至少有 n-n%l條記錄,而 G′經(jīng)上述分組后至多還有 n-l條記錄,(n-l)＜(n-n%l),所以這 n/l條記錄必有 2條處于同一分組中,其差值小于 Ddist(t1,t2),即其組內(nèi)最小差異小于分組 G,從而得出矛盾.證畢.

l-SNSA算法描述如下：

2.2 l-MNSA算法

通過對 l-SNSA算法的分析可知,l-SNSA算法總是選擇當前敏感屬性數(shù)值最小的記錄作為一個分組的第 1條記錄.并在選定一條記錄后,在其單調(diào)方向上依次選擇第 in/l條記錄,才能得出最優(yōu)的維敏感屬性上值較小,在其他維上可能較大,無法同時滿足 l-SNSA算法的條件.

為解決多維敏感屬性的發(fā)布問題,本文提出 l-MNSA(l-multi-numerical sensitive attribute)算法,其思想源于 l-SNSA算法.首先把數(shù)據(jù)的每維敏感屬性統(tǒng)一到同一個區(qū)間,針對每維敏感屬性分別排序.對所有敏感屬性 Sj,在 Sj維上第 in/l的記錄 ti,記 t′為 (t1.S1,…,tb.Sb),取距 t′有最小距離 D的記錄 t添加到分組,此處距離 D為 2條記錄在每個敏感屬性值的差的均值,即

由于數(shù)據(jù)在每維敏感屬性都已經(jīng)統(tǒng)一到同一個區(qū)間,t在每一維敏感屬性上的值都與 t′較為接近.與 l-SNSA算法相似,可以選擇 l(當 n%l=0)或 l+1(當 n%l!=0)條記錄作為一個分組.這樣選取的分組在每維敏感屬性上都有近似滿足 l-SNSA匿名算法的性質(zhì),有較好的安全性.如此反復,得到關(guān)系 T上的分組.將每個分組的準標識符發(fā)布為 QI表,將敏感屬性發(fā)布為 S表就完成了隱私數(shù)據(jù)的發(fā)布過程.

以表 1中的數(shù)據(jù)為例,對算法執(zhí)行過程進行說明.按照 l=3為參數(shù)分組.l-MNSA匿名算法首先將敏感屬性標準化到同一個區(qū)間,如表 3所示.分別按工資和獎金的值排序可得工資{t1,t2,t3,t5,t6,t7,t4}和獎金{t2,t1,t3,t5,t7,t6,t4},選擇工資維取值最小的記錄為 t1,獎金維值最小的記錄為 t2,記t′={t1.工資 ,t2.獎金 }={2,10},與 t′距離最小的記錄為 t2,將 t2添加到 G,然后選擇在各個敏感屬性維上第 n/l=7/3=2條記錄,均為 t3,則可把 t3添加到G.繼續(xù)選擇在各個敏感屬性維上第 2n/l=2×(7/3)=4條記錄 t6,t7,記 t′={t6.工資 ,t7.獎金}={48,50},與 t′相距最近的記錄為 t6,將 t6添加到 G.繼續(xù)選擇可以得到的一個分組為{t2,t3,t6,t4}.在向量中刪除這些記錄.進行算法循環(huán),最后發(fā)布的數(shù)據(jù)如表 4所示.

表3 將表 1中敏感屬性標準化到[0,100]

表4 l-MNSA算法發(fā)布結(jié)果

分析 l-MNSA算法可知,當敏感屬性維數(shù)降為1時,即為 l-SNSA算法.在一個分組中,算法所選擇的記錄,在每一維敏感屬性上分布都會比較均勻,因而可以較好地避免近似猜測攻擊.

3 實驗與分析

對所提出的 l-MNSA算法進行性能測試.實驗平臺配置如下：Intel 1.8G/1GB,Windows XP,所用代碼均用 Visual C++(6.0)實現(xiàn).實驗數(shù)據(jù)與文獻[7]相同,均采用實際數(shù)據(jù)集 SAL,對原始數(shù)據(jù)集濾掉不完整記錄及非數(shù)值屬性后,提取1×104條記錄.

算法發(fā)布數(shù)據(jù)的查準率由分解算法決定,已在文獻[1]中得到理論和實驗證明.下面對 2種算法發(fā)布數(shù)據(jù)的組內(nèi)最小差異和運行效率進行實驗分析.

由于敏感屬性 Sj的組內(nèi)最小差異表示發(fā)布結(jié)果在 Sj維上保護程度的最小值,在保證查準率的條件下,l-SNSA算法的發(fā)布結(jié)果有最大的組內(nèi)最小差異.通過比較 l-MNSA算法與 l-SNSA算法發(fā)布結(jié)果在同一敏感屬性維上的組內(nèi)最小差異,可以分析 l-MNSA算法發(fā)布結(jié)果的安全性,兩者越接近,說明 l-MNSA算法的發(fā)布結(jié)果的安全性越好.

圖1 組內(nèi)最小差異度(數(shù)據(jù)量 5×103,l=3)

圖 1給出了 2種算法在數(shù)據(jù)量為 5×103時的組內(nèi)最小差異度,其中 f3,i3,e3分別表示敏感屬性ftotval,inctot,incwage在 l=3時的組內(nèi)最小差異,f4,i4,e4分別表示 ftotval,inctot,incw age在 l=4時組內(nèi)最小差異.可以看出 2種算法不同敏感屬性的組內(nèi)最小差異都很接近,基本控制在 10%左右,說明 l-MNSA算法發(fā)布結(jié)果對每維敏感屬性的保護程度都接近于 l-SNSA算法的發(fā)布結(jié)果,有較好的安全性.

圖 2給出了數(shù)據(jù)量不同時 2種算法的 CPU運行時間對比,其中 l-MSNA算法取 3維敏感屬性.從圖中可以看出,隨著數(shù)據(jù)集的增大,2種算法的運行時間均隨之增大,l-MSNA算法的 CPU時間更大,這是因為針對多維敏感屬性的運算要更多.對算法進行分析可知,2種算法的時間復雜度均為O(nlgn),這與實驗結(jié)果基本吻合.

圖2 不同算法運行的CPU時間(l=3)

4 結(jié)語

研究了多維數(shù)值敏感屬性的發(fā)布問題,并通過研究單維的解決方法 l-SNSA算法,提出了 l-MNSA算法,較好地解決了這個問題.理論分析和實驗結(jié)果表明,本文提出的算法是有效可行的.下一步將針對高維數(shù)值敏感屬性的隱私保護發(fā)布做進一步的研究.

References)

[1]Sweeney L.K-anonym ity：amodel for protecting privacy[J].International Journal on Uncertainty,Fuzziness,and Know ledge-Based Systems,2002,10(5)：557-570.

[2]Samarati P.Protecting respondents'identities in m icrodata release[J].IEEE Transactions on Know ledge and Data Engineering,2001,13(6)：1010-1027.

[3]Li N,Li T.T-closeness：p rivacy beyond k-anonymity and l-diversity[C]//Proceedings of the 23rd International Conference on Data Engineering.Istanbul,Turkey,2007：106-115.

[4]M achanavajjhala A,Gehrke J,Kefer D.l-diversity：privacy beyond k-anonym ity[C]//Proceedings of the 22nd International Conference on Data Engineering.Atlanta,Georgia,USA,2006：24-35.

[5]Zhang Q,Koudas N,Srivastava D,et al.Aggregate query answ ering on anonym ized tables[C]//Proceedings of International Conference on Data Engineering.Istanbul,Turkey,2007：116-125.

[6]Xiao X,Tao Y.Anatomy：sim ple and effective p rivacy preservation[C]//Proceedings of the 32nd International Conference on Very Large Data Bases.Seoul,Korea,2006：139-150.

[7]Li JX,Tao Y F,Xiao X K.Preservation of p roximity privacy in publishing numerical sensitive data[C]//Proceedings of ACM Conferenceon Management of Data.Vancouver,BC,Canada,2008：473-486.

[8]楊曉春,王雅哲,王斌,等.數(shù)據(jù)發(fā)布中面向多敏感屬性的隱私保護方法[J].計算機學報,2008,31(4)：574-587.Yang X iaochun,Wang Yazhe,W ang Bin,etal.Privacy p reserving approaches formultiple sensitive attributes in data publishing[J].Chinese Journal of Computers,2008,31(4)：574-587.(in Chinese)

[9]周水康,李豐,陶宇飛,等.面向數(shù)據(jù)庫應用的隱私保護研究綜述[J].計算機學報,2009,32(5)：847-861.Zhou Shuikang,Li Feng,Tao Yufei,et al.Privacy preservation in database applications：a survey[J].Chinese Journal of Computers,2009,32(5)：847-861.(in Chinese)

[10]Aggarw al C.On k-anonym ity and the curse of dimensionality[C]//Proceedings of the 31st International Conference on Very Large Data Bases.Trondheim,Norway,2005：901-909.