劉騰騰 倪巍偉 崇志宏 張 勇

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,南京 210096)

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

2.1 l-SNSA算法

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

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

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

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

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

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

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

表3 將表 1中敏感屬性標(biāo)準(zhǔn)化到[0,100]

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

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

3 實(shí)驗(yàn)與分析

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

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

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

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

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

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

圖2 不同算法運(yùn)行的CPU時(shí)間(l=3)

4 結(jié)語(yǔ)

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

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ā)布中面向多敏感屬性的隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào),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ù)庫(kù)應(yīng)用的隱私保護(hù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào),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.