（ｐ，ａ）－ｓｅｎｓｉｔｉｖｅ ｋ－匿名隱私保護(hù)模型

摘 要：提出了一種(p，a)-sensitive k-匿名模型，將敏感屬性根據(jù)敏感度進(jìn)行分組，然后給各分組設(shè)置不同的約束，并給出了(p，a)-sensitive K-匿名算法。實(shí)驗(yàn)結(jié)果表明該方法可以明顯地減少隱私泄露，增強(qiáng)了數(shù)據(jù)發(fā)布的安全性。

關(guān)鍵詞：數(shù)據(jù)發(fā)布；敏感度；K-匿名；隱私泄露；分組

中圖分類號(hào)：TP309文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)06-2177-03

doi:10.3969/j.issn.1001-3695.2009.06.054

(p， a)-sensitive k-anonymity:privacy protection model

WANG Qian，ZENG Zi-ping

(College of Computer Science， Chongqing University， Chongqing 400044， China)

Abstract:This paper proposed a novel model(p，a)-sensitive k-anonymity.It divided sensitive attributes into groups accor-ding to the sensitivity， and set each group with different restriction.Described the corresponding algorithm to implement the idea.The result of the experiments suggests that the new model is able to reduce privacy disclosure apparently and enforce security of data publishing.

Key words:data publishing; sensitivity; k-anonymity; privacy disclosure; group

隨著網(wǎng)絡(luò)信息技術(shù)的高速發(fā)展， 人類大量個(gè)人信息被政府部門(mén)、商業(yè)機(jī)構(gòu)等存儲(chǔ)、發(fā)布，這極大激發(fā)了各部門(mén)從海量數(shù)據(jù)中挖掘有用信息的需求。但事物往往具有兩面性， 當(dāng)數(shù)據(jù)挖掘用于公開(kāi)分析大量的私人信息(如購(gòu)物習(xí)慣、犯罪記錄、病史、信用記錄等)時(shí)，它在為人們提供強(qiáng)大知識(shí)發(fā)現(xiàn)功能的同時(shí)，也對(duì)個(gè)人隱私帶來(lái)威脅。雖然獨(dú)立的數(shù)據(jù)發(fā)布單位分別會(huì)采取措施隱藏發(fā)布數(shù)據(jù)中的個(gè)人身份標(biāo)志或某些隱私數(shù)據(jù)，但是值得注意的是通過(guò)在多個(gè)公開(kāi)的數(shù)據(jù)源間進(jìn)行連接操作往往會(huì)導(dǎo)致意想不到的隱私信息泄露問(wèn)題。文獻(xiàn)[1]中的研究表明，通過(guò)zip code、sex、data of birth等屬性對(duì)選民登記表和隱匿了個(gè)體標(biāo)志的醫(yī)療信息表進(jìn)行連接操作，超過(guò)87%的美國(guó)公民的身份均可以被惟一標(biāo)志。

Sweeney等人^[1]提出k-匿名模型保護(hù)隱私數(shù)據(jù)不受鏈接攻擊，能夠有效地解決標(biāo)志泄露問(wèn)題，但是對(duì)于敏感屬性泄露問(wèn)題并沒(méi)有相應(yīng)的保護(hù)機(jī)制，并且沒(méi)有過(guò)多地考慮敏感屬性的敏感度問(wèn)題，無(wú)法達(dá)到保護(hù)隱私的目的。

1 相關(guān)工作

敏感數(shù)據(jù)發(fā)布與共享環(huán)境中的個(gè)體隱私信息的安全性問(wèn)題一直是數(shù)據(jù)隱私研究的熱點(diǎn)。k-匿名模型保護(hù)隱私數(shù)據(jù)不受鏈接攻擊，它是指數(shù)據(jù)表中的每條記錄都至少和其他的k-1條記錄具有相同的準(zhǔn)標(biāo)志符屬性取值，但是k-匿名并沒(méi)有考慮敏感屬性的多樣化需求。文獻(xiàn)[2]提出在某些情況下k-匿名并不能保證隱私信息的安全。例如，具有相同準(zhǔn)標(biāo)志符屬性取值的所有或大部分記錄都具有相同的敏感屬性值，惡意的用戶還是能夠輕易地以高概率推斷出隱私信息。 因此文獻(xiàn)[2]提出了l-多樣性的概念，對(duì)匿名化的數(shù)據(jù)記錄中出現(xiàn)頻率最高的敏感屬性值的個(gè)數(shù)作出了約束，要求它不大于1/l。P-sensitive k-匿名模型^[3]是在k-匿名的基礎(chǔ)上，要求每個(gè)等價(jià)組中至少要有p個(gè)不同的敏感屬性值，它雖然在一定程度上解決了k-匿名的敏感屬性泄露問(wèn)題，但是并沒(méi)有控制敏感屬性的出現(xiàn)頻率，當(dāng)k比p大很多時(shí)，就可能出現(xiàn)同一等價(jià)組中一個(gè)敏感屬性的出現(xiàn)頻率遠(yuǎn)大于別的敏感屬性，很容易遭受概率攻擊。(a，k)-匿名模型^[4]通過(guò)約束敏感屬性值在匿名組中出現(xiàn)的頻率小于參數(shù)a來(lái)避免某些敏感值頻率過(guò)高的情況，增加了敏感值的多樣性，防止了一致性攻擊，但是它對(duì)所有敏感屬性都采用同樣的約束，不能滿足實(shí)際要求。文獻(xiàn)[5]提出了一種利用經(jīng)典的空間索引技術(shù)來(lái)實(shí)現(xiàn)k-匿名的技術(shù)，具有很好的擴(kuò)展性且能很好地支持增量的數(shù)據(jù)發(fā)布。當(dāng)數(shù)據(jù)表中準(zhǔn)標(biāo)志符屬性的個(gè)數(shù)較多時(shí)，通過(guò)概括和隱匿的方法對(duì)數(shù)據(jù)進(jìn)行k-匿名化會(huì)損失大量信息^[6] ，因此文獻(xiàn)[6]提出了一種不基于概括和隱匿的新穎的方法——Anatomy。 它通過(guò)將原始關(guān)系的準(zhǔn)標(biāo)志符屬性和敏感屬性以兩個(gè)不同的關(guān)系發(fā)布，利用它們之間的有損連接來(lái)保護(hù)隱私數(shù)據(jù)的安全，并且給出了基本的Anatomy 算法保證發(fā)布的數(shù)據(jù)滿足l-多樣性的要求。

以上提出的敏感數(shù)據(jù)發(fā)布方法在匿名化過(guò)程中均沒(méi)有考慮敏感屬性的敏感度問(wèn)題，在敏感屬性具有不同敏感度的數(shù)據(jù)發(fā)布過(guò)程中，不能達(dá)到有效防止隱私泄露的目的。

2 (p，a)-sensitive k-匿名

2.1 基本概念

假設(shè)T為原始數(shù)據(jù)表，T′為發(fā)布的數(shù)據(jù)表，用于發(fā)布或共享的數(shù)據(jù)表中可以將T中的屬性分為三類：a)個(gè)體身份的標(biāo)志屬性(identifier)，如姓名、社會(huì)保險(xiǎn)號(hào)等，通常在數(shù)據(jù)發(fā)布時(shí)被隱匿；b)與外部數(shù)據(jù)源進(jìn)行連接可標(biāo)志個(gè)體身份的屬性，如age、country、zip code等，叫做準(zhǔn)標(biāo)志符(quasi-identifier，QI);c)包含個(gè)體隱私信息的敏感屬性，如disease等，需要被保護(hù)。

定義1 k-匿名。對(duì)于數(shù)據(jù)表T，經(jīng)過(guò)匿名化處理得到表T′，T′滿足k-匿名當(dāng)且僅當(dāng)在任一等價(jià)組中每一條記錄至少有k-1條記錄與它相對(duì)應(yīng)。

k-匿名可以有效防止標(biāo)志泄露。例如，表1為原始數(shù)據(jù)表，｛age，country， zip code｝為準(zhǔn)標(biāo)志符，health condition為敏感屬性；經(jīng)過(guò)2-匿名化后如表2所示，即使攻擊者知道某條記錄在表2中，他也無(wú)法確定是哪條記錄與它相對(duì)應(yīng)。但是，k-匿名無(wú)法防止屬性泄露問(wèn)題，因?yàn)樗鼪](méi)有考慮敏感屬性的多樣性。例如，對(duì)于表2，假設(shè)攻擊者能夠獲得Rick的age=27，country=Canada，zip code=14207，且在表2中就可以很容易地推斷出Rick得了HIV。雖然無(wú)法確定是第1還是第2條記錄。

為了解決k-匿名的屬性泄露問(wèn)題，文獻(xiàn)[3]提出了p-sensitive k-匿名模型。

定義2 p-sensitive k-匿名。匿名化的數(shù)據(jù)表T′滿足p-sensitive k-匿名，當(dāng)且僅當(dāng)T′滿足k-匿名，且在T′中每個(gè)等價(jià)組內(nèi)至少有p個(gè)不同的敏感屬性值。

p-sensitive k-匿名可以在一定程度上解決k-匿名的屬性泄露問(wèn)題，如表3滿足2-sensitive 4-匿名，每個(gè)等價(jià)組中至少有兩個(gè)不同的敏感屬性值，可以防止一致性攻擊。但是在某些情況下，它還是會(huì)造成隱私泄露。

2.2 問(wèn)題定義

很多時(shí)候敏感屬性值的敏感度強(qiáng)弱都不相同，如表1所示，cancer與HIV的敏感度要遠(yuǎn)遠(yuǎn)大于flu、indigestion的敏感度。往往人們都不介意別人知道自己得了流感、消化不良等疾病，但是對(duì)于cancer或者HIV病人來(lái)說(shuō)，他們卻很怕被人知道，因?yàn)檫@會(huì)嚴(yán)重影響到他們今后的生活以及別人對(duì)他們的看法，所以對(duì)于cancer與HIV等高敏感度的屬性而言，需要提供更強(qiáng)的保護(hù)力度。以前的隱私保護(hù)模型都沒(méi)有考慮到敏感屬性的敏感度的問(wèn)題，把它們都統(tǒng)一對(duì)待，這顯然無(wú)法達(dá)到保護(hù)隱私的目的。可以根據(jù)敏感屬性的敏感度不同將它們進(jìn)行分組，例如可以將表1中敏感屬性health condition根據(jù)敏感度強(qiáng)弱分為四組(表4)，同一敏感屬性組可以包含多個(gè)特定的敏感屬性值。在這種情況下，不單只是考慮特定敏感屬性值，而且要考慮整個(gè)敏感屬性組的保護(hù)，比如，一個(gè)人的疾病信息被攻擊者知道是屬于top secret中，雖然不知道具體是cancer或HIV，這也是不能接受的。例如，表3是在表2的基礎(chǔ)上實(shí)現(xiàn)的2-sensitive 4-匿名表，屬性值｛cancer，cancer，HIV，HIV｝都屬于top secret且在同一個(gè)等價(jià)組中，這顯然也會(huì)造成隱私泄露，并且對(duì)于高敏感度的敏感屬性值而言，它們?cè)谕坏葍r(jià)組中出現(xiàn)的頻率應(yīng)該更低。針對(duì)上述問(wèn)題，本文介紹了一種新的更加有效的隱私保護(hù)模型(p，a)-sensitive k-匿名模型。

2.3 (p，a)-sensitive k-匿名模型

定義S為敏感屬性值的集合，根據(jù)S中敏感值的敏感度把S分成m個(gè)組(S1，S2，…，Sm)。其中S=∪mi=1Si，Si∩Sj=(i≠j)，并且滿足Si≤Sj(1≤i＜j≤m)，表示Si比Sj更敏感。例如，以表1中health condition作為敏感屬性，則S＝{HIV，cancer，phthisis，hepatitis，heart disease，asthma，flu，indigestion }，根據(jù)疾病的敏感度分為了四個(gè)組(表4)。其中S1最敏感而S4最不敏感。

為了對(duì)高敏感度的屬性值提供更強(qiáng)的保護(hù)程度，通過(guò)控制高敏感屬性值在同一等價(jià)組中出現(xiàn)的頻率來(lái)實(shí)現(xiàn)，稱為a非關(guān)聯(lián)約束。

定義3 a非關(guān)聯(lián)約束。對(duì)于匿名等價(jià)組E，敏感屬性值s，用(E， s)表示在E中敏感屬性值為s的記錄數(shù)目，freq(E，s)=(E，s)/|E|，a為一個(gè)用戶指定的參數(shù)，0≤a≤1。組E對(duì)于敏感屬性值s來(lái)說(shuō)是滿足非關(guān)聯(lián)約束的，如果freq(E，s)≤a。其中，a必須滿足兩個(gè)條件:a)a必須不小于敏感屬性值s在整個(gè)數(shù)據(jù)集上的頻率，否則無(wú)法實(shí)行匿名化；b)a不小于每個(gè)等價(jià)組中s的最小頻率。

傳統(tǒng)的匿名模型對(duì)所有敏感屬性值都采用同一約束值a，并沒(méi)有考慮敏感屬性值敏感度強(qiáng)弱的問(wèn)題，顯然不能滿足實(shí)際要求，所以需要定義一個(gè)新的約束：敏感組非關(guān)聯(lián)約束aSi。

定義4 敏感組非關(guān)聯(lián)約束。定義S為敏感屬性值的集合，S1，S2，…，Sm為根據(jù)敏感度的一個(gè)分組，aS1，aS2，…，aSm分別為各個(gè)敏感組a非關(guān)聯(lián)約束。其中aS1＜aS2＜…＜aSm，并且aSi不小于Si中任一敏感屬性值s的出現(xiàn)頻率。

考慮兩種極端情況：

a)aSi=1，必然滿足，表示Si中屬性值不具有敏感性。

b)aSi=0，表示Si中的屬性值不想與個(gè)體有任何相關(guān)，即Si中屬性值是不能發(fā)布的。

定義5 (p， a)-sensitive k-匿名。對(duì)于數(shù)據(jù)表T，經(jīng)過(guò)匿名化得到T′，T′滿足k-匿名且每個(gè)等價(jià)組中有P個(gè)不同的敏感屬性組，并且等價(jià)組內(nèi)任一敏感屬性值滿足敏感組非關(guān)聯(lián)約束，則稱T′滿足(p， a)-sensitive k-匿名。

例如，表5滿足(p， a)-sensitive k-匿名，當(dāng)取k=4，aS1=0.4，aS2=0.6，aS3=0.7，aS4=0.9。相對(duì)于表3，本文的模型可以克服p-sensitive k-匿名的缺點(diǎn)，并能極大地減少隱私泄露的可能性。

2.4 算法

這一節(jié)介紹實(shí)現(xiàn)(p，a)-sensitive k-匿名的算法。首先用文獻(xiàn)[3]使用的最小p-sensitive k-匿名算法產(chǎn)生一個(gè)數(shù)據(jù)表T′；然后判斷T′是否滿足(p，a)-sensitive k-匿名，滿足則直接輸出，如果不滿足，則在等價(jià)組之間交換記錄直到滿足每個(gè)等價(jià)組內(nèi)c≥p(c為不同敏感組的個(gè)數(shù))且freq(E，si)≤aSj，其中si∈Sj；最后概化產(chǎn)生滿足條件的數(shù)據(jù)表T*，輸出。算法描述如下：輸入：數(shù)據(jù)集T，敏感屬性分組D=(S1，S2，…，Sm)，用戶定義aSi，p，k(2≤p≤k)；

輸出：滿足(p，a)-sensitive k-匿名的數(shù)據(jù)集T。

過(guò)程：

產(chǎn)生滿足p-sensitive k-匿名數(shù)據(jù)集T′

while not(c≥p and freq(E，si)≤aSj)

交換等價(jià)組之間的記錄

end while

概化形成新的等價(jià)組

return T

3 實(shí)驗(yàn)

實(shí)驗(yàn)所使用的數(shù)據(jù)集為UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)^[7]中的adult數(shù)據(jù)集，該數(shù)據(jù)集在數(shù)據(jù)匿名化研究中被廣泛使用，已成為該領(lǐng)域事實(shí)上的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集。Adult數(shù)據(jù)集包括部分美國(guó)人口普查數(shù)據(jù)。本文取age、work class、race、gender作為準(zhǔn)標(biāo)志符，并增加一列health condition作為敏感屬性，取值為{HIV， cancer， phthisis， hepatitis， heart disease，asthma， flu， indigestion}，分組如表4所示。隨機(jī)選取500條記錄并把health condition的屬性值隨機(jī)插入表中。不同敏感屬性值的頻率和敏感組約束如表6所示。

用本文提出的模型與p-sensitive k-匿名模型匿名化數(shù)據(jù)集根據(jù)k的不同產(chǎn)生的敏感屬性泄露進(jìn)行對(duì)比。實(shí)驗(yàn)表明本模型可以顯著地減少敏感屬性的泄露，如表7所示。

3.2 執(zhí)行時(shí)間分析

當(dāng)k越小時(shí)(因?yàn)閍S1=0.4，所以k>2)，產(chǎn)生的等價(jià)組數(shù)就越多，在等價(jià)組之間就要進(jìn)行很多的記錄交換，所以消耗的時(shí)間就越多；而當(dāng)k較大時(shí)，需要交換的記錄就會(huì)減少，隨著k的增大，漸漸趨于p-sensitive算法的執(zhí)行時(shí)間，如圖1所示。

4 結(jié)束語(yǔ)

隱私信息的安全性是數(shù)據(jù)發(fā)布與共享環(huán)境中面臨的重要問(wèn)題。現(xiàn)有的隱私數(shù)據(jù)發(fā)布技術(shù)沒(méi)有考慮敏感屬性的敏感度問(wèn)題，在匿名化過(guò)程中將所有敏感屬性值都同等對(duì)待。針對(duì)這一問(wèn)題，本文提出了一種(p，a)-sensitive k-匿名隱私保護(hù)模型，將敏感屬性根據(jù)敏感度不同進(jìn)行分組，并且通過(guò)給各敏感組設(shè)定不同的約束來(lái)提供不同的保護(hù)程度。通過(guò)實(shí)驗(yàn)表明該方法可以有效地防止隱私泄露。

參考文獻(xiàn)：

［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]MACHANAVAJJHALA A， GEHRKE J， KIFER D，et al.L-diversity:privacy beyond k-anonymity[C]//Proc of the 22nd International Conference on Data Engineering.New York:ACM Press，2006:24-35.

[3]TRAIAN T M，BINDU V.Privacy protection:p-sensitive k-anonymity property[C]//Proc of the 22nd International Conference on Data Engineering.New York:ACM Press，2006:94.

[4]WONG R C，LI Jin-yong， FU A W，et al.(a，k)-anonymity:an enhanced k-anonymity model for privacy preserving[C]//Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press，2006:754-759.

[5]LWUCHUKWU T， NAUGHTON J.K-anonymization as spatial indexing:toward scalable and incremental anonymization[C]//Proc of the 33rd International Conference on Very Large Data Bases.[S.l.]:VLDB Endowment，2007:746-757.

[6]XIAO Xiao-kui，TAO Yu-fei.Anatomy:simple and effective privacy preservation[C]//Proc of the 32nd International Conference on Very Large Data Bases.[S.l]:VLDB Endowment，2006:139-150.

[7]HETTICH S， BLAKE C L，MERZ C J.UCI repository of machine learning databases[EB/OL].(1998).http://www.ics.uci.edu/-mlearn/MLRepository.html.

[8]BAYARDO R，AGRAWAL R.Data privacy through optimal k-anonymity[C]//Proc of the 21st International Conference on Data Engineering.Washington DC:IEEE Computer Society，2005:217-228.

[9]LI Ning-hui，LI Tian-cheng，SURESH V.T-closeness:privacy beyond k-anonymity and L-diversity[C]//Proc of the 23rd International Conference on Data Engineering.2007:106-115.

[10]SWEENEY L.Achieving k-anonymity privacy protection using genera-lization and suppression[J]. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems，2002，10(5):571-588.

[11]XU Jian， WANG Wei， PEI Jian，et al.Utility-based anonymization using local recoding[C]//Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press，2006:785-790.

[12]LEFEVRE K， DEWITT D J， RAMAKRISHNAN R. Incognito:efficient full-domain K-anonymity[C]//Proc ofACM SIGMOD International Conference on Management of Data.New York:ACM Press，2005:49-60.