基于K-匿名的隱私保護算法研究

秦曉薇，門愛華，鄒 妍

（赤峰學院 計算機科學與技術系，內蒙古 赤峰 024000）

基于K-匿名的隱私保護算法研究

秦曉薇，門愛華，鄒 妍

（赤峰學院 計算機科學與技術系，內蒙古 赤峰 024000）

隨著數據共享的出現與發展，如何合理地保護隱私數據，同時又保證數據的可用性，成為當今信息安全領域面臨的重大挑戰.K-匿名是數據發布隱私保護的一種重要方法，它能夠有效防止鏈接攻擊所造成的隱私泄露問題.本文闡述了K-匿名模型的基本思想，給出了模型的概念描述，給出了一些典型的實現算法，并對隱私保護的未來研究方向進行了展望.

K-匿名；隱私保護；泛化；數據共享

1 引言

隨著互聯網技術的飛速發展，數據共享為人們發布、檢索和使用數據帶來了極大地便利，然而與此同時也帶來了隱私泄漏的安全隱患.已發布的數據經常會無意識地泄漏個人隱私，這將對隱私數據所有者的利益造成嚴重的損害.因此，如何在數據發布中對個人隱私數據進行合理的保護，又保證數據的可用性，成為當今信息安全領域研究的熱點.

在現實生活中，為了人口統計、醫療、衛生等研究需要，一些機構經常要發布相關數據.雖然，在發布的數據中已經隱匿了個人的標識信息，如姓名、身份證號碼等屬性，但是，用戶仍然可以通過對發布的數據和其他渠道獲得的數據進行鏈接處理，推演出隱私數據，從而造成隱私泄露，這就是鏈接攻擊[1].例如，某些屬性具有較強的辨認性（如性別、出生日期、郵編等），使得鏈接操作的結果只有一條或者幾條，這樣目標信息的范圍就會極大地縮小，從而泄露個人隱私.如果在數據發布之前適當地作一些預處理，那么就可以減少用戶作鏈接操作時候導致這樣信息泄露的可能，或者增加非法用戶猜測的難度.

1998年，Samarati和L.Sweeney提出了K-匿名模型，該模型能夠防止鏈接攻擊所造成的隱私泄露問題，是隱私保護的有效方法.本文闡述了K-匿名模型的基本思想，給出了模型的概念描述，分析和評價了一些典型的實現算法，并對K-匿名模型實現算法的未來研究方向進行了展望.

2 K-匿名模型

2.1 基本思想

表1是某醫院發布的醫療信息數據表，其中，不包含姓名、身份證號碼等能夠唯一標識某個病人的屬性.

如果用戶在獲得了表1的同時，又可以獲得選民登記表，如表2所示.那么，通過兩個表在屬性{Sex，Birthdate，Zipcode}上的鏈接，就可以很容易的確定某個選民的疾病情況.在本例中，可以獲得選民Andre的疾病情況.這就是一個簡單的鏈接攻擊.

表1 醫療信息數據表

表2 選民登記表

我們將表1中的屬性分為敏感屬性和非敏感屬性.敏感屬性指對于相對應的個體來說是不愿意被其他人所知道的，如Disease，稱為隱私屬性.非敏感屬性是那些可以與其他數據表進行鏈接的屬性，如Birthdate，Sex和Zipcode，稱為準標識符.

K-匿名模型的基本思想就是設法切斷準標識符與隱私屬性之間的一對一關系來保護隱私屬性.數據持有者能夠識別出可以與外部信息相連接的準標識符，并通過檢驗原始數據表中在準標識符上相同元組的個數來判斷是否會造成隱私泄漏.即要求所發布的數據表中的每一條記錄r，至少有K?1條記錄與r在準標識符上的投影值相等,稱這樣的數據表符合K-匿名約束.

2.2 概念描述

定義1（屬性） 令B(A1,…,An)是由有限個元組構成的數據表，其中，{A1,…,An}是數據表B的有限屬性集.

給定一個數據表B(A1,…,An)，令{Ai,…,Aj}{A1,…,An}，且元組t∈B，則t[Ai,…,Aj]表示元組t在屬性Ai,…,Aj上的值vi,…,vj的有序序列；B[Ai,…,Aj]表示表B在屬性Ai,…,Aj上的投影.

定義2（準標識符） 給定一個實體集U，一個特定的實體表T(A1,…,An)，fc：U→T以及fg：T→U'，其中U哿U'.則T的準標識符記為QIT，是一組屬性{Ai，…Aj}{A1,…,An}.其中Pi∈U，那么fg(fc(Pi)[QIT])=Pi成立.

定義3（K-匿名）有一個數據表T(A1,…,An)，QI是與數據表T相關的準標識符，當且僅當在T[QI]中出現的每一個有序的值至少要在T[QI]中出現K次，就稱數據表T滿足K-匿名.

推論1 假設一個數據表T(A1,…,An)，QI=（Ai，…Aj）是與表T相關的準標識符，其中{Ai,…,Aj}{A1,…,An}，且T滿足K-匿名，那么，在T[Ax]中出現的每一個值至少要在T[QI]中出現K次，其中x=i,…,j.

表3為匿名化表1中原始數據后的結果，其滿足2-匿名.在采用準標識符Birthdate，Sex和Zipcode進行鏈接攻擊時，在準標識符的投影上至少有兩條相同的記錄，因此，攻擊者獲得真正隱私的概率僅為50%.一般K值越大，對隱私的保護效果更好，但丟失的信息越多.

表32 -匿名

3 K-匿名模型實現算法

當前，K-匿名的研究主要集中在如何對原始數據表進行有效的匿名化，即實現匿名效果最好、數據可用性最高、且時間空間花銷最小.通常，采用泛化和抑制技術來實現K-匿名.泛化是對數據進行更概括、抽象的描述，例如對整數5的一種泛化形式是[3，6]，因為5在區間[3，6]內；而抑制就是直接從數據表中刪除一些屬性值或元組.

本節對一些典型的K-匿名實現算法進行了分析和評價.

3.1 Datafly算法

L.Sweeney在文獻[2]中提出了Datafly算法.該算法將原始數據表在準標識符上的投影作為子表，當子表中不滿足K-匿名約束的元組數目大于K時，將子表中不同屬性值個數最多的屬性進行泛化，并循環上述步驟，當循環結束后，將剩余的不滿足K-匿名約束的元組進行抑制.

在Datafly算法中，盡管某些元組已經滿足了K-匿名約束要求，但還要繼續參與K-匿名化處理，從而造成了過量的信息損失，降低了數據的可用性.

3.2 MinGen(Minimal Generalization)最小泛化算法

L.Sweeney在文獻[3]中提出了MinGen算法，并給出了最小泛化和最小失真的定義.該算法對原始數據表進行泛化，找出所有滿足K匿名約束的表，然后通過計算失真度來確定具有最高精度的K匿名表.

MinGen算法能最大限度地保證泛化后的表滿足K-匿名約束的要求，而且能夠對單元的數據進行泛化，這樣泛化的結果信息損失較小.但是該算法在原始數據表規模比較大的時候，對表的所有可能元組的泛化將會成為NP難題.

3.3 Classfly和Classfly+算法

楊曉春、劉向宇等人在2005年提出了Classfly算法[4]，并于2006年提出了支持多匿名約束的 Classfly+算法[5]. Classfly和Classfly+算法是在Datafly算法的基礎上，引用了過濾的思想，即先將原始數據表在準標識符上的投影表中滿足匿名約束的元組過濾出去，再對剩余元組中不同屬性值個數最多的屬性進行泛化，如有滿足匿名約束的元組再過濾出去，反復執行上述的泛化和過濾操作，直到不滿足K-匿名約束的元組個數小于K為止，最后將不滿足匿名約束的元組抑制.

Classfly和Classfly+算法通過泛化過濾機制，使得符合多約束的元組不參與以后的泛化操作，減少信息損失，保證K-匿名化的數據精度.

3.4 Incognito算法

Incognito算法[6]由K.LeFevre等人提出.該算法首先構建包含所有全域泛化方案的泛化圖（Generalization Graph），然后自底向上的深度優先算法對原始數據進行泛化，每次選取最優泛化方案前，預先對泛化圖進行抑制以縮小搜索范圍，不斷進行以上操作直到數據滿足K-匿名約束.

Incognito算法沒有針對信息損失給出有效解決方法，導致信息損失大，且分布的數據也有泄漏敏感信息的可能.

3.5 多維K-匿名算法

多維K-匿名算法是在多維空間上對所有元組進行劃分，使劃分的每個子集中元組個數至少為K，然后對準標識符上的多個屬性值同時進行泛化，使劃分的每個元組子集具有相同值.

Mondrian算法[7]是一種典型的多維K-匿名劃分方法，它的設計是在簡單滿足K-匿名模型要求的前提下，追求數據劃分精度的最大化.但是該算法只能對連續屬性劃分，對不連續屬性處理能力較差.而實際發布的數據屬性多數是不連續的，如Birthdate，Zipcode等，這樣就使得該算法的實際應用性降低.如果兩組數據分布具有相同數值范圍但數據分布不同，那么數據分布離散程度高的數據安全性高于數據分布相對集中的數據，因此，Mondrian算法不能很好地平衡數據的精確度與數據隱私安全保護之間的矛盾.

基于Mondrian算法的不足，文獻[8]中提出了一種基于熵的多維K-匿名劃分算法.該算法采用自頂向下的貪心方法對準標識符空間不斷地劃分，直至所有的子標識符空間不可再分.在劃分過程中，總是選擇數據離散程度最高的維對數據進行劃分，并采用熵作為劃分原則，每組劃分結果中的數據點分布相對離散，這樣，將會減小競爭對手正確猜測數據點實際值的概率，從而在保證數據劃分精度的同時進一步提高了劃分結果的安全性.

文獻[9]提出了能夠有效降低匿名信息損失的基于多維泛化路徑的完整Filter K-匿名算法和部分Filter K-匿名算法.算法的基本思想類似于Incognito算法，首先對原始數據表進行匿名化處理，構建包含所有全域泛化方案的泛化層次結構圖，在進行路徑選擇之前剔除滿足要求的元組到結果表里，使它們不參與泛化，然后將余下的元組按不同路徑參與不同泛化.這兩種算法根據N維泛化層次結構圖生成的路徑集，在泛化過程中不破壞泛化層次，將滿足要求的元組提前保存在結果數據集里，獲取最優的K-匿名數據集，從而提高匿名數據精度和處理效率.

前面所提到K-匿名算法，都是針對靜態數據而言，未考慮數據動態變化時帶來的挑戰.在動態環境下，數據通常會隨時間的推移增加或減少，數據發布要求亦會不相同.文獻[10]中提出了一種能夠適應動態數據需求的算法——基于R樹多維K-匿名算法.該算法通過將準標識符屬性值轉化為空間的點數據來構造R樹，其中每個元組都是葉子節點，那么用該葉子節點的父親節點的區域代替所有孩子節點，由于每個父親節點的孩子節點數目不小于K，所以算法保證所有替代節點都是至少有K條同樣的記錄.這種算法對于一些經常變更的數據集有較好的響應時間和信息保存完整度.

4 總結與展望

數據共享以及數據獲取渠道的多樣化，使得隱私保護成為人們關注的焦點.K-匿名模型可以有效防止鏈接攻擊所造成的隱私泄露問題.研究表明，采用K-匿名技術在一個原始多屬性數據表基礎上導出最優的匿名數據表是一個NP難題，因此，很大一部分實現k-匿名的算法研究著眼于設計高效的近似算法以有效匿名化原始數據.

大部分現有K-匿名實現算法都是基于靜態數據集的，

而在現實世界中，數據卻是在不斷變化的，包括數據表現形式的改變、屬性的增減、新數據的加入、舊數據的刪除等.并且，數據的變化一般都不是完全隨機、獨立的，數據與數據之間，數據與數據變化之間，都是相互關聯的.因此，怎樣在這種更加復雜的環境下，實現對動態數據的利用和隱私保護，是一個更具挑戰的難題，有待于進一步的研究.

〔1〕Sweeney L.K-anonymity:a model for protecting privacy[J].International Journal of Uncertainty,Fuzziness and Knowledge-based Systems,2002,10(5):557-570.

〔2〕Sweeney L. ComputationalDisclosure Control:A primer on data privacy protection.[Ph.D.Thesis,Massachusetts Institute of Technology],2001:67-82.

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

〔4〕Liu XY,Yang XC,Yu G.A representative class based privacy preserving data publishing approach with high precision[J].Computer Science,2005,32(9A):368?373.

〔5〕楊曉春,劉向宇,王斌,于戈.支持多約束的K-匿名化方法[J].Journal of Software,2006,17(5):1222-1231.

〔6〕LeFevre K,DeWitt D,Ramakrishnan R.Incognito:Efficient Full-domain k-anonymity[Z].In Proc.Of the ACM SIGMOD Int’l Conf on Management of Data, Baltimore,Maryland,USA,2005:49-60.

〔7〕LeFevreK,DeWittD,RamakrishnanR.Mondrian multidimensionalK-anonymity [C]. Proc of22nd ICDE.LosAlamitos,USA:IEEE ComputerSociety Press,2006:25-34.

〔8〕晏華,劉貴松.采用熵的多維K-匿名劃分方法[J].電子科技大學學報，2007,36(6):1228-1231.

〔9〕黃春梅,費耀平,李敏,戴弋,劉嬌.基于多維泛化路徑的K-匿名算法[J].計算機工程，2009,35(2):154-156.

〔10〕鄧京璟,葉曉俊.基于R樹多維K-匿名算法[J].計算機工程，2008,34(1):80-82.

TP311

A

1673-260X（2010）05-0014-03

內蒙古自治區高等學校科學研究項目基金資助（NJzy08152）