傳統(tǒng)數(shù)據(jù)庫隱私泄露的研究

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

（安徽理工大學 計算機科學與工程學院，安徽 淮南 232001）

1 引言

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

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

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

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

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

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

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

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

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

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

概化/隱匿方法建立在預定義的域概化層次樹結構和值概化層次樹結構之上，會帶來不必要的信息損失.為減少信息損失，G.Aggarwal等提出使用聚類方法實現(xiàn)k-匿名[8].k-匿名模型可以有效的抵御連接攻擊，但是對于背景知識攻擊和同質攻擊卻無能為力[9].為抵御背景知識攻擊和同質攻擊Machanavajjhala A提出l-多樣性模型[9]，它要求每個簇類的敏感值要滿足l-多樣性約束，以提高敏感值與其所屬個體的連接難度，該模型使用概化/隱匿方法，王智慧等[6]提出適用聚類方法實現(xiàn)l-多樣性隱私保護，他們首先對數(shù)據(jù)進行聚類，然后對聚類后的簇概化處理;(α,k)-匿名模型[10]也是為了彌補k-匿名模型的不足而提出的隱私模型，它是通過控制等價類中敏感值的出現(xiàn)頻率來實現(xiàn)敏感值的多樣性.韓建民等[11]針對(α,k)-匿名模型限制每個敏感值為固定的α，提出為每個敏感值設置一個敏感值，這種方法對敏感值數(shù)目較少時可以很好的提高隱私保護度，對于敏感數(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ù)以后的更新版本.這個問題假設同一個個體的全部記錄在所有的發(fā)布中不變.即使每個發(fā)布T1,……,Tp被單獨匿名，隱私需求可能通過比較不同的版本和排除一些可能的受害者敏感值而受到損害.這個問題假設數(shù)據(jù)動態(tài)更新，而序列匿名假設數(shù)據(jù)是靜態(tài)的且在一次發(fā)布中可以全部得到.進一步說，這個問題假設所有的發(fā)布共享同一個數(shù)據(jù)庫模式，而序列發(fā)布問題假設全部發(fā)布是同一個基礎表的投影.

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

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

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

5 總結與結論

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

〔1〕楊高明，楊靜，張健沛.隱私保護的數(shù)據(jù)發(fā)布研究[J].計算機科學.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ā)布中面向多敏感屬性的隱私保護方法[J].計算機學報，2008,31(04):574-587.

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

〔6〕王智慧，許儉，汪衛(wèi)，等.一種基于聚類的數(shù)據(jù)匿名方法[J].軟件學報，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〕韓建民，于娟，虞慧群，等.面向敏感值的個性化隱私保護[J].電子學報，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].軟件學報，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.