楊高明，李敬兆，張順香，朱廣麗

（安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001）

1 引言

隨著信息技術(shù)和數(shù)據(jù)庫(kù)技術(shù)的快速發(fā)展，各行各業(yè)均存儲(chǔ)了海量數(shù)據(jù)，這些數(shù)據(jù)仍然以驚人的速度不斷產(chǎn)生.為有效從數(shù)據(jù)中提出有效知識(shí)而不泄露個(gè)人隱私信息，在數(shù)據(jù)發(fā)布之前需要進(jìn)行隱私保護(hù)，于是隱私保護(hù)的數(shù)據(jù)發(fā)布技術(shù)應(yīng)運(yùn)而生[1].隱私保護(hù)的數(shù)據(jù)發(fā)布目的就是在數(shù)據(jù)發(fā)布給使用者之前，對(duì)數(shù)據(jù)進(jìn)行某種形式的變化，使數(shù)據(jù)包含盡可能多的有用信息并使個(gè)人隱私信息得到保護(hù).

隱私保護(hù)的數(shù)據(jù)發(fā)布包括兩方面的內(nèi)容：一方面為防止私有敏感信息的泄漏提供有力的技術(shù)保障，消除信息擁有者在共享信息時(shí)的顧慮，促進(jìn)信息交流和共享；另一方面還強(qiáng)調(diào)減少實(shí)施隱私保護(hù)所帶來(lái)的非敏感信息損失，保證共享信息的質(zhì)量，提高共享信息的可用性.隱私保護(hù)的數(shù)據(jù)發(fā)布需要考慮兩方面的敵對(duì)攻擊，即連接攻擊和背景知識(shí)攻擊.對(duì)于連接攻擊目前主要采用k-匿名方法予以解決，而對(duì)于背景知識(shí)攻擊主要解決方法較多，如(α,k)-匿名，l-多樣性，t-逼近等方法.這些方法目前都不是完美的解決方案，存在這樣那樣的問(wèn)題，有許多問(wèn)題需要解決.

本課題的預(yù)期研究成果，將有助于指導(dǎo)隱私保護(hù)的數(shù)據(jù)發(fā)布過(guò)程，極大提高發(fā)布的數(shù)據(jù)的隱私保護(hù)度，提高數(shù)據(jù)的效用，減少信息損失，具有重要的現(xiàn)實(shí)意義，有著較高的研究?jī)r(jià)值和良好的應(yīng)用前景.

2 k-匿名發(fā)布技術(shù)的研究

隨著網(wǎng)絡(luò)技術(shù)和數(shù)據(jù)存儲(chǔ)技術(shù)的發(fā)展，產(chǎn)生和存儲(chǔ)了大量的數(shù)據(jù).僅僅從這些數(shù)據(jù)中刪除明確的標(biāo)識(shí)符(如姓名、身份證號(hào)碼)并不能阻止隱私的泄露，通過(guò)與外部數(shù)據(jù)的聯(lián)接(link)依然可以發(fā)現(xiàn)個(gè)體的敏感屬性[1].Samarati和Sweeney[2]為解決隱私發(fā)布提出k-匿名技術(shù).對(duì)數(shù)據(jù)集中泄露信息的準(zhǔn)標(biāo)識(shí)符屬性采用概化和隱匿處理，使每個(gè)記錄都至少與其他k-1個(gè)記錄的準(zhǔn)標(biāo)識(shí)符有相同值.概化處理使得數(shù)據(jù)的精確度有所降低，但是基本保持了原來(lái)的語(yǔ)義信息，但過(guò)度的概化會(huì)造成不必要的信息損失，降低數(shù)據(jù)的效用.隱匿技術(shù)可以看做概化的特殊形式，即所有值均以“*”代替[3].保證發(fā)布的數(shù)據(jù)質(zhì)量并使隱私信息得到保護(hù)是一項(xiàng)挑戰(zhàn)性的工作，隱私保護(hù)的數(shù)據(jù)發(fā)布必須考慮數(shù)據(jù)質(zhì)量和數(shù)據(jù)效用之間的平衡.

圖1 數(shù)據(jù)集屬性分類樹

基于概化的技術(shù)實(shí)現(xiàn)k-匿名[4]模型需要考慮數(shù)據(jù)集的屬性.對(duì)于分類屬性，具體的值被給定的分類樹概化值取代.在圖1中，父節(jié)點(diǎn)Professional比子節(jié)點(diǎn)Engineer和Lawyer更一般.根節(jié)點(diǎn)ANY_Job代表Job的最一般值.如果一個(gè)數(shù)值屬性區(qū)間分類系統(tǒng)給定了，情況與分類屬性相似，更普遍情況是沒(méi)有為數(shù)值屬性預(yù)定義的分類系統(tǒng).

目前學(xué)者提出許多實(shí)現(xiàn)k-匿名的方法，前人已經(jīng)證明采用概化/隱匿技術(shù)實(shí)現(xiàn)最優(yōu)化匿名是NP難度問(wèn)題，于是有人提出基于聚類的[5]方法.基于聚類的方法首先采用某種衡量標(biāo)準(zhǔn)將數(shù)據(jù)集劃分成簇，對(duì)僅包含數(shù)值屬性的數(shù)據(jù)集一般發(fā)布簇的質(zhì)心和簇的記錄數(shù);對(duì)包含數(shù)值屬性和分類屬性的數(shù)據(jù)集，通常概化簇使它們達(dá)到k-匿名[6].相比僅僅使用概化/隱匿技術(shù)的k-匿名需求，基于聚類的方法在匿名可以產(chǎn)生更好的數(shù)據(jù)質(zhì)量.

概化實(shí)現(xiàn)k-匿名模型存在搜索空間過(guò)大問(wèn)題，許多作者提出的啟發(fā)式方法雖然減小了搜索空間，但是存在信息損失過(guò)大，數(shù)據(jù)效用降低的問(wèn)題.另外還有其他一些問(wèn)題，比如文獻(xiàn)[7]對(duì)離群點(diǎn)敏感.由于文中的算法選擇最遠(yuǎn)的點(diǎn)開始構(gòu)造新的簇，如果數(shù)據(jù)集包含遠(yuǎn)距離的離群點(diǎn)，這些離群點(diǎn)就有可能被選擇作為構(gòu)造新簇的種子，結(jié)果會(huì)導(dǎo)致信息損失過(guò)大.

3 (α,k)-匿名的研究

概化/隱匿方法建立在預(yù)定義的域概化層次樹結(jié)構(gòu)和值概化層次樹結(jié)構(gòu)之上，會(huì)帶來(lái)不必要的信息損失.為減少信息損失，G.Aggarwal等提出使用聚類方法實(shí)現(xiàn)k-匿名[8].k-匿名模型可以有效的抵御連接攻擊，但是對(duì)于背景知識(shí)攻擊和同質(zhì)攻擊卻無(wú)能為力[9].為抵御背景知識(shí)攻擊和同質(zhì)攻擊Machanavajjhala A提出l-多樣性模型[9]，它要求每個(gè)簇類的敏感值要滿足l-多樣性約束，以提高敏感值與其所屬個(gè)體的連接難度，該模型使用概化/隱匿方法，王智慧等[6]提出適用聚類方法實(shí)現(xiàn)l-多樣性隱私保護(hù)，他們首先對(duì)數(shù)據(jù)進(jìn)行聚類，然后對(duì)聚類后的簇概化處理;(α,k)-匿名模型[10]也是為了彌補(bǔ)k-匿名模型的不足而提出的隱私模型，它是通過(guò)控制等價(jià)類中敏感值的出現(xiàn)頻率來(lái)實(shí)現(xiàn)敏感值的多樣性.韓建民等[11]針對(duì)(α,k)-匿名模型限制每個(gè)敏感值為固定的α，提出為每個(gè)敏感值設(shè)置一個(gè)敏感值，這種方法對(duì)敏感值數(shù)目較少時(shí)可以很好的提高隱私保護(hù)度，對(duì)于敏感數(shù)值較多的情況就不適用了.

4 連續(xù)數(shù)據(jù)發(fā)布的研究

在連續(xù)數(shù)據(jù)發(fā)布模型中，數(shù)據(jù)發(fā)布者有以前的版本T1,…,Tp-1，現(xiàn)在需要發(fā)布Tp，其中Ti是Ti-1插入或者刪除數(shù)據(jù)以后的更新版本.這個(gè)問(wèn)題假設(shè)同一個(gè)個(gè)體的全部記錄在所有的發(fā)布中不變.即使每個(gè)發(fā)布T1,……,Tp被單獨(dú)匿名，隱私需求可能通過(guò)比較不同的版本和排除一些可能的受害者敏感值而受到損害.這個(gè)問(wèn)題假設(shè)數(shù)據(jù)動(dòng)態(tài)更新，而序列匿名假設(shè)數(shù)據(jù)是靜態(tài)的且在一次發(fā)布中可以全部得到.進(jìn)一步說(shuō)，這個(gè)問(wèn)題假設(shè)所有的發(fā)布共享同一個(gè)數(shù)據(jù)庫(kù)模式，而序列發(fā)布問(wèn)題假設(shè)全部發(fā)布是同一個(gè)基礎(chǔ)表的投影.

連續(xù)的數(shù)據(jù)發(fā)布問(wèn)題假設(shè)攻擊者知道時(shí)間戳和受害者的QID，所以攻擊者確切知道哪個(gè)發(fā)布包含受害者的記錄.Byun等[12]首先提出一種插入新記錄的隱私保護(hù)連續(xù)匿名發(fā)布技術(shù).具體地說(shuō)，它保證每個(gè)版本滿足l-多樣性，這要求每個(gè)qid組包含至少l個(gè)不同敏感值.如果一個(gè)值在qid組內(nèi)發(fā)生的很頻繁，攻擊者可以容易推導(dǎo)出受害者的敏感值.因此這個(gè)實(shí)例不能阻止屬性聯(lián)接攻擊.

數(shù)據(jù)流作為一種新型的數(shù)據(jù)模型，它以不同的更新速率連續(xù)地流進(jìn)和流出計(jì)算機(jī)系統(tǒng)，具有實(shí)時(shí)性、連續(xù)性、無(wú)界性、無(wú)序性等特點(diǎn)，這些特點(diǎn)決定了只能對(duì)數(shù)據(jù)流進(jìn)行單遍掃描.近年越來(lái)越多的學(xué)者關(guān)注數(shù)據(jù)流管理系統(tǒng)[13]和數(shù)據(jù)流挖掘算法的研究，并取得了許多成果.隨著數(shù)據(jù)挖掘工具能力的不斷增強(qiáng)，對(duì)個(gè)人隱私和數(shù)據(jù)安全造成了很大威脅.為了保護(hù)客戶隱私，刪除明確表明客戶身份的信息，比如姓名、地址、電話號(hào)碼等，然而剩余的屬性依然可以被用來(lái)發(fā)動(dòng)鏈接攻擊.如果惡意攻擊者知道顧客的個(gè)別屬性，就很容易定位到某個(gè)具體顧客[2].

目前在對(duì)原始數(shù)據(jù)的保護(hù)主要方法有：擾動(dòng)、數(shù)據(jù)交換、k-匿名等.近來(lái)有學(xué)者研究增量k-匿名方法，該方法在新的元組到來(lái)以后插入舊元組集或者從舊元組集刪除元組，增量數(shù)據(jù)發(fā)布主要研究舊發(fā)布和新發(fā)布之間匿名泄露問(wèn)題[14].匿名數(shù)據(jù)流和匿名增量數(shù)據(jù)集有某些相似性，它們都隨著時(shí)間推移增加數(shù)據(jù)量，但是增量數(shù)據(jù)集和數(shù)據(jù)流中所討論的推理攻擊的假設(shè)條件并不一樣，因此增量更新的數(shù)據(jù)匿名算法并不適合數(shù)據(jù)流.

5 總結(jié)與結(jié)論

傳統(tǒng)數(shù)據(jù)庫(kù)領(lǐng)域面臨隱私泄露的風(fēng)險(xiǎn)，有許多學(xué)者研究如何抵御隱私數(shù)據(jù)的泄露，提出了很多有效的技術(shù)和方法.本文從傳統(tǒng)數(shù)據(jù)庫(kù)的角度對(duì)目前存在的技術(shù)進(jìn)行了梳理.重點(diǎn)探討了k-匿名、l-多樣性、(α,k)-匿名等隱私保護(hù)技術(shù).

〔1〕楊高明，楊靜，張健沛.隱私保護(hù)的數(shù)據(jù)發(fā)布研究[J].計(jì)算機(jī)科學(xué).2011,38(9):11-17.

〔2〕Sweeney L. Achieving k-anonymity privacy protection using generalization and suppression [J]. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems. 2002, 10(5): 571-588.

〔3〕Kisilevich S, Rokach L, Elovici Y, et al. Efficient Multidimensional Suppression for K-Anonymity [J]. IEEE Transactions on Knowledge and Data Engineering. 2010,22(3): 334-347.

〔4〕楊曉春，王雅哲，王斌，等.數(shù)據(jù)發(fā)布中面向多敏感屬性的隱私保護(hù)方法[J].計(jì)算機(jī)學(xué)報(bào)，2008,31(04):574-587.

〔5〕童云海，陶有東，唐世渭，等.隱私保護(hù)數(shù)據(jù)發(fā)布中身份保持的匿名方法[J].軟件學(xué)報(bào)，2010,21(04):771-781.

〔6〕王智慧，許儉，汪衛(wèi)，等.一種基于聚類的數(shù)據(jù)匿名方法[J].軟件學(xué)報(bào)，2010,21(04):680-693.

〔7〕Byun J, Kamra A, Bertino E, et al. Efficient k -anonymization using clustering techniques [C]. Bangkok,Thailand: Springer Verlag, 2007.

〔8〕Aggarwal G, Panigrahy R, Tom, et al. Achieving anonymity via clustering [J]. ACM Trans. Algorithms.2010,6(3):1-19.

〔9〕Machanavajjhala A, Kifer D, Gehrke J, et al. l-diversity:Privacy beyond k-anonymity [J]. ACM Transactions on Knowledge Discovery from Data. 2007, 1(1): 1-52.

〔10〕Wong R, Li J, Fu A, et al. (α, k)-anonymous data publishing[J]. Journal of Intelligent Information Systems.2009, 33(2): 209-234.

〔11〕韓建民，于娟，虞慧群，等.面向敏感值的個(gè)性化隱私保護(hù)[J].電子學(xué)報(bào)，2010,38(7):1723-1728.

〔12〕Byun J, Sohn Y, Bertino E, et al. Secure anonymization for incremental datasets[C]. Seoul, Korea, Republic of: Springer Verlag, 2006.

〔13〕金澈清，錢衛(wèi)寧，周傲英.流數(shù)據(jù)分析與管理綜述[J].軟件學(xué)報(bào)，2004,15(8):1172-1181.

〔14〕Wu Y, Sun Z, Wang X. Privacy Preserving k -Anonymity for Re-publication of Incremental Datasets[C]. IEEE Computer Society, 2009.