匿名化隱私保護技術研究進展

摘 要:匿名化是目前數據發布環境下實現隱私保護的主要技術之一。闡述了匿名化技術的一般概念和基本原理，并從匿名化原則、匿名化方法和匿名化度量等方面對匿名化技術進行了總結，最后指出匿名化技術的研究難點以及未來的研究方向。

關鍵詞:數據發布; 隱私保護; 匿名化; k-匿名

中圖分類號:TP311文獻標志碼:A

文章編號:1001-3695(2010)06-2016-04

doi:10.3969/j.issn.1001-3695.2010.06.004

Progress of research on anonymization privacy-preserving techniques

WANG Ping-shui1， WANG Jian-dong2

(1. College of Information Engineering， Anhui University of Finance Economics， Bengbu Anhui 233041， China; 2. College of Information Science Technology， Nanjing University of Aeronautics Astronautics， Nanjing 210016， China)

Abstract:Anonymization is one of the primary techniques realizing privacy protection in data dissemination environment. This paper described the general concepts and basal principles of the anonymization techniques， and summarized the anonymization principles， anonymization methods and anonymization measures. Finally discussed the present problems and directions for future research.

Key words:data dissemination; privacy-preserving; anonymization; k-anonymity

0 引言

Internet技術、大容量存儲技術的迅猛發展以及數據共享范圍的逐步擴大使得數據的自動收集和發布越來越方便。然而，在數據發布過程中隱私泄露問題也日益突出，因此隱私保護問題就顯得尤為重要。數據發布中隱私保護對象主要是對用戶敏感數據與個體身份之間的對應關系。一般通過刪除標志符的方法發布數據是無法阻止隱私泄露的，攻擊者可以通過鏈接攻擊獲取個體的隱私數據。匿名化技術可有效地解決鏈接攻擊所帶來的隱私泄露問題。自從1998年Samarati等人[1]首次提出匿名化概念以來，國內外專家學者們對匿名化技術開展了廣泛深入的研究工作以尋求防止或減少隱私泄露的有效方法，取得了一系列相關研究成果[2~22]。然而，目前如何通過匿名化技術高效實現發布數據的隱私保護仍然是業界研究的熱點問題。本文旨在總結和分析數據發布隱私保護中匿名化的基本原理和實現技術現狀，以啟示相關領域研究人員對匿名化技術的進一步深入研究，促進匿名化隱私保護技術的實際應用。

1 相關概念

1.1 屬性劃分

數據發布中微數據集可視為包含n條記錄的數據表文件，其中每條記錄包含個體的m個屬性，屬性按其功能可被分成互不相交的四種[2]:

a)標志符(identifiers)。惟一標志個體身份，如身份證號、社會保險號、姓名等。

b)準標志符(quasi-identifiers)。與其他數據表進行鏈接以標志個體身份，如性別、出生日期、郵政編碼等。準標志符的選擇取決于進行鏈接的外部數據表，如圖1中，準標志符(簡稱QI)={race，birth，sex，zip}。

c)敏感屬性(sensitive attributes)。發布時需要保密的屬性，如薪金、信仰、健康狀況等。

d)非敏感屬性(non-sensitive attributes)?？梢怨_的屬性，又稱普通屬性。

1.2 鏈接攻擊

鏈接攻擊是從發布的數據中獲取隱私數據的常見方法。其基本思想為:攻擊者通過對發布的數據和其他渠道獲取的數據進行鏈接操作，以推理出隱私數據，從而造成隱私泄露。例如[2]，通過將醫療信息表與選民登記表進行鏈接(圖1)，幾乎可以惟一確定就診病人的醫療診斷結果，然而，病人的醫療診斷結果正是需要保護的隱私數據。數據匿名化技術可以在一定程度上解決發布數據的隱私泄露問題，但同時也給發布數據的可用性帶來了限制，即產生一定量的信息損失。

2 匿名化原則

匿名化是用于解決因鏈接攻擊所造成的隱私泄露問題的主要技術之一，以下對目前提出的基本匿名化原則進行分析和總結，并指出其可能存在的問題。

2.1 k-anonymity

為解決鏈接攻擊所帶來的隱私泄露問題，Sweeney等人[1~3]首次提出并發展了k-匿名(k-anonymity)方法。

定義1 k-anonymity。設原始數據表為PT(A1，…，An)，匿名化后數據表為RT(A1，…，An)，QIRT是與其對應的準標志符。稱數據表RT滿足k-匿名，如果RT[QIRT]中的每個序列值在RT[QIRT]中至少出現k次(k>1)。數據表RT中具有相同準標志符的若干記錄稱為一個等價類，即k-匿名實現了同一等價類中記錄之間無法區分(敏感屬性值除外)。如表2是表1的2-匿名化表。

表1 醫療信息表

nameracebirthsexzipdisease

Aliceblack1965-3-18M02141Flu

Bobblack1965-5-1M02142Cancer

Davidblack1966-6-10M02135Obesity

Helenblack1966-7-15M02137Gastritis

Janewhite1968-3-20F02139HIV

Paulwhite1968-4-1F02138Cancer

表2 2-匿名化表，QI={race，birth，sex，zip}

racebirthsexzipdisease

black1965M0214*Flu

black1965M0214*Cancer

black1966M0213*Obesity

black1966M0213*Gastritis

white1968F0213*HIV

white1968F0213*Cancer

k-匿名通?？梢苑乐姑舾袑傩灾档男孤?，因為每個個體身份被準確標志的概率至多為1/k。然而，數據表在匿名化過程中并未對敏感屬性作任何約束，這也可能帶來隱私泄露。如同一等價類內敏感屬性值較為集中，甚至完全相同(可能形式上，也可能語義上)，這樣即使滿足k-匿名要求，也很容易推理出與指定個體相應的敏感屬性值。除此之外，攻擊者也可通過自己掌握的足夠的相關背景知識以很高的概率來確定敏感數據與個體的對應關系，從而導致隱私泄露。因此，k-匿名容易受到同質性攻擊(homogeneity attack)和背景知識攻擊(background knowledge attack) 。

2.2 l-diversity

為解決同質性攻擊和背景知識攻擊所帶來的隱私泄露，Machanavajjhala等人[4]在k-匿名基礎上提出了l-多樣性(l-diversity)原則。

定義2 l-diversity。稱匿名數據表RT(A1，…，An)是l-diversity的，如果RT(A1，…，An)滿足k-匿名，且同一等價類中的記錄至少有l個較好表現(well-represented)的值。其中較好表現有多種解釋，如:

a)Distinct l-diversity。同一等價類中至少出現l個不同的敏感屬性值。

b)Entropy l-diversity。同一等價類中敏感屬性值的信息熵至少為log l。等價類E的敏感屬性的信息熵定義為H(E)=-∑s∈SP(E，s)logP(E，s)。其中S為敏感屬性值域，P(E，s)為敏感屬性值s在等價類E中出現的概率。

c)Recursive (c，l)-diversity。每個等價類均滿足r1

d)Recursive (c1，c2，l)-diversity。除保證等價類中頻率最高的敏感屬性值不至于出現頻度太高，同時還保證了等價類中頻率最低的敏感屬性值不至于出現頻度太低。

2.3 p-sensitive k-anonymity

發布的數據滿足k-匿名化原則的同時(k>1，p≤k)，還要求同一等價類中的記錄至少出現p個不同的敏感屬性值，這與distinct l-diversity具有基本相同的設計思想[5]。該匿名化原則在某些數據集上可能會帶來很大的信息可用性損失，也不足以抵抗敏感屬性值的偏斜性攻擊(skewness attack)和相似性攻擊(similarity attack)。

2.4 (α，k)-anonymity

發布的數據滿足k-匿名化原則的同時，還要求同一等價類中任何一個敏感屬性值出現的概率不大于α(0<α<1)，即|(E，s)|/|E|≤α[6]。偏斜性攻擊和相似性攻擊還可能會發生，匿名化過程中的高信息損失依然存在。

2.5 (k，e)-anonymity

該匿名化原則主要針對數值型敏感屬性[7]，它要求在等價類中敏感屬性值的區間范圍至少為e。(k，e)-anonymity試圖通過最小e值克服針對敏感屬性值的相似性攻擊，但可能會造成高信息損失，也無法抵抗敏感屬性值的偏斜性攻擊。

2.6 t-closeness

發布的數據滿足k-匿名化原則的同時，還要求等價類內敏感屬性值的分布與敏感屬性值在匿名化表中的總體分布的差異不超過t[8]。t-closeness在l-diversity基礎上，考慮了敏感屬性的分布問題，它要求所有等價類中敏感屬性值的分布盡量接近該屬性的全局分布。為度量等價類與匿名化數據表中敏感屬性值的分布差異，文中引入了一種獨特的距離度量方式EMD(earth mover’s distance)，該距離度量方式對數值型敏感屬性值和類別型敏感屬性值均定義了相應的計算方式。t-closeness解決了針對敏感屬性值的偏斜性攻擊和相似性攻擊，但是匿名化的結果是降低了發布數據的可用性，提高發布數據可用性的惟一辦法是增大閾值t。

2.7 個性化匿名

之前的匿名化原則僅提供表級別的保護粒度，對表中所有敏感屬性值提供相同程度的保護，并未考慮其相應的語義關系，造成大量不必要的信息損失。文獻[9]提出了個性化匿名(personalized anonymity)的概念，并給出個性化匿名的一般方法。所謂個性化匿名是指對數據表中不同敏感屬性值提供不同粒度的隱私保護程度，從而減少了因統一匿名化所帶來的信息損失。文獻[10]給出了個性化的(α，k)-anonymity模型，進一步減少了信息損失，并且提高了隱私保護程度。

2.8 動態數據匿名化

目前大部分匿名化原則都是針對靜態數據的，并未考慮數據記錄動態更新后重發布的隱私保護問題。數據的動態更新在現實中是極為常見的，然而如果還按照原有的方法對更新后的數據集進行匿名化并重發布，很可能在多個不同的發布版本間存在推理通道，從而造成隱私泄露。文獻[11]基于推遲發布、新建l-diversity等價類思想提出了一種支持記錄插入操作的動態重發布匿名方案，能夠在一定程度上阻止推理攻擊所造成的隱私泄露。文獻[12]給出了一種同時支持記錄插入和記錄刪除操作的m-invariance匿名方案，通過保證同時出現在不同發布版本中的記錄所在的等價類具有完全相同的敏感屬性值集合，有效解決了不同版本間的推理通道所造成的隱私泄露問題。文獻[13]提出了一種基于劃分的增量數據重發布隱私保護k-匿名算法。文獻[14]提出一種(k，c)匿名方案以支持增量數據的重發布。動態數據重發布所引起的隱私泄露問題已引起了研究者的廣泛關注。

3 匿名化方法

目前提出的匿名化方法的共同特征主要是通過泛化(ge-neralization)和抑制(suppression)操作實現，該技術不同于一般的扭曲、擾亂和隨機化等方法，它們能保持發布前后數據的真實性和一致性。

3.1 泛化

泛化的基本思想是用更一般的值取代原始屬性值[3]。通常，泛化可分為以下兩種類型:

a)域泛化，是指將一個給定的屬性域泛化成一般域。例如，屬性zip原始域Z0={02138， 02139，02141，02142}被泛化成Z1={0213*，0214*}，以便在語義上表達一個較大的范圍，如圖2所示。經過連續多次泛化形成的域泛化層次結構稱為域泛化層，記為DGHA。

b)值泛化，是指原始屬性域中的每個值直接泛化成一般域中的惟一值，如圖3所示。值泛化關系同樣決定了值泛化層的存在，記為VGHA。

給定數據表PT(A1，…，An)，針對每個屬性Ai給定其域泛化層DGHAi，則屬性級上的所有可能的泛化數目為∏mi=1(|DGHAi|+1)，數據單元級上的所有可能的泛化數目為∏mi=1(|DGHAi|+1)n。其中m為數據表中的屬性個數，n為記錄個數。

3.2 抑制

抑制是指用最一般化的值取代原始屬性值。如圖3值泛化層VGHZ0中處于頂層的最大值即為該屬性每個值抑制操作的結果。在k-匿名化過程中，若某些記錄無法滿足k-匿名要求，則一般采取抑制操作，被抑制的相應屬性值所在記錄要么從數據表中刪除，要么相應屬性值用若干“*”填充，以保持有關統計特性。

3.3 其他方法

除通過泛化和抑制進行匿名化外，文獻[15]提出了基于聚類的匿名化方法，將原始數據表先通過聚類技術聚成若干至少包含k條記錄的簇，然后對每個簇再進行匿名化操作。還有基于數據交換的匿名化方法等，在此不再贅述。

關于匿名化方法，文獻[3]給出了最小泛化匿名的概念，文獻[16]證明了基于泛化和抑制的匿名化技術的最優解求解是一個NP難問題。目前文獻中提出的主要是一些啟發式算法，力圖在合理的時間內找到近似最優解，以減少信息損失為首要優化目標。

4 匿名化度量

在實際應用中，沒有一個統一的標準來衡量所有的k-匿名算法。為處理好隱私保護與信息損失之間的關系以及衡量匿名算法的優劣，以下從不同角度給出與匿名化技術度量相關的參考標準，供選擇或設計新的匿名方法時尋求隱私保護和信息損失之間的平衡。

4.1 精度度量

給定原始數據表PT(A1，A2，…，ANa)，匿名化數據表RT(A1，A2，…，ANa)。其中，Na為數據表屬性個數，N為記錄個數，DGHAi是屬性Ai的域泛化層，則匿名化表RT的精度可按如下方式計算[21]:

prec(RT)=1-∑Nai=1∑Nj=1h|DGHAi||PT|#8226;|Na|

其中:h表示屬性Ai泛化后在域泛化層的高度，h|DGHAi|是指每個數據單元匿名化后的信息丟失量。顯然，對于任一屬性Ai，泛化層越高，精度越小，信息損失越大。

4.2 可用性度量

可用性度量又稱可辨別性度量。Bayardo和Agrawal定義了k-匿名的可用性度量方案如下[22]:Bayardo和Agrawal認為可通過泛化和抑制操作所要花費的代價來衡量匿名化表的可用性大小。設等價類E中的每個記錄的泛化代價為該等價類的大小|E|(|E|≥k)，即包含記錄個數，抑制一條記錄的代價為|D|，即數據庫的大小。于是獲取該匿名化表的總代價為

C=∑|E|≥k|E|2+∑|E|

顯然，等價類越大及抑制記錄越多時，匿名化代價越高，相應地，匿名化表的可用性越小。

4.3 距離度量

可以通過距離方式來度量匿名表中等價類中敏感屬性值的分布與其在匿名表中的總體分布的差異。文獻[23]提出了MD(manhattan distance)距離度量方式，文獻[24]提出了KLD(Kullback-Leibler distance)距離度量方式，文獻[8]提出了EMD(earth mover’s distance) 距離度量方式。以下給出MD和KLD兩種分布間距離度量的計算方式，有關EMD距離的具體計算細節參見文獻[8]。

給定敏感屬性值兩個概率分布:P=(p1，p2，…，pn)和Q=(q1，q2，…，qm)，則

MD:D[P，Q]=1m∑mi=112(pi-qi)

KLD:D[P，Q]=∑mi=1pi logpiqi=H(P)-H(P，Q)，

其中:H(P)=∑mi=1pi log pi為分布P的熵，H(P，Q)=∑mi=1pi log qi為分布P和Q的交叉熵。

很顯然，分布距離越大，等價類中敏感屬性值的分布與其在匿名表中的總體分布的差異越大，越容易受到偏斜性攻擊。

5 結束語

匿名化技術由于能夠在數據發布環境下防止用戶敏感數據被泄露，同時又能保證發布數據的真實性，在實際應用領域受到廣泛關注。但由于對該技術的研究起步較晚，其中還存在不少問題值得深入探討。以下給出今后該技術的熱點研究方向:

a)隱私性與可用性間的平衡問題。目前的研究主要集中于減少信息損失，如何找到一個合理的平衡點達到發布數據隱私性和可用性的折中是需要進一步深入研究的問題。

b)匿名化技術的執行效率問題。目前采用的匿名化方法多為貪婪式算法，執行效率不高，因此需要研究高效的匿名化算法以應對日益劇增的超容量數據的發布問題。

c)度量和評價標準問題。目前還沒有統一的匿名化技術度量和評價標準，因此需要致力于該項研究，給匿名化技術一種更為客觀合理的評價。

d)動態重發布數據的匿名化問題。目前研究主要集中于對靜態數據匿名化，動態更新數據發布的匿名化技術研究不多，因此需要多加關注。

e)多維約束匿名問題。目前研究主要針對單一敏感屬性數據表進行匿名化處理，該技術不能通過簡單移植方式來解決多敏感屬性數據表的匿名化問題，否則將會因屬性間存在的函數信賴關系導致敏感信息的泄露。因此需要研究有效的多維約束匿名化算法。

此外，如何高效實現個性化匿名，如何根據實際應用準確選擇數據表的準標志符，如何解決分布式環境下多數據表的匿名化等都是值得深入思考和研究的問題。

參考文獻:

[1]SAMARATI P， SWEENEY L. Generalizing data to provide anonymity when disclosing information[C]//Proc of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. New York: ACM Press，1998:188.

[2]SWEENEY L. K-anonymity:a model for protecting Privacy[J]. International Journal of Uncertainty， Fuzziness and Knowledge-based Systems，2002，10(5):557-570.

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

[4]MACHANAVAJJHALA A， GEHRKE J， KIFER D. L-diversity: privacy beyond k-anonymity[J]. ACM Trans on Knowledge Discove-ry from Data，2007，1(1):3.

[5]TRUTA T， VINAY B. Privacy protection:p-sensitive k-anonymity property[C]//Proc of the 22nd International Conference on Data Engineering Workshops. Washington DC: IEEE Computer Society， 2006:94-103.

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

[7]ZHANG Qing， KOUDAS N， SRIVASTAVA D， et al. Aggregate query answering on anonymized tables[C]//Proc of the 23th International Conference on Data Engineering. Pisctaway，NJ: IEEE Press， 2007:116-125.

[8]LI Ning-hui， LI Tian-cheng. T-closeness: privacy beyond k-anonymity and l-diversity[C]//Proc of the 23rd International Conference on Data Engineering.Pisctaway， NJ: IEEE Press， 2007:106-115.

[9]XIAO Xiao-kui， TAO Yu-fei. Personalized privacy preservation[C]//Proc of ACM SIGMOD Conference on Management of Data.New York: ACM Press，2006:229-240.

[10]YE Xiao-jun， ZHANG Ya-wei， LIU Ming. A personalized (a，k)-anonymity model[C]//Proc of the 9th International Conference on Web-Age Information Management. Piscataway，NJ:IEEE Press，2008:341-348.

[11]BYUN J， SOHN Y， BERTINO E， et al. Secure anonymization for incremental datasets[C]//Proc of the 3rd VLDB Workshop on Secure Data Management.Berlin:Springer-Verlag，2006:48-63.

[12]XIAO Xiao-kui， TAO Yu-fei. M-invariance:towards privacy preserving re-publication of dynamic datasets[C]//Proc of ACM SIGMOD Conference on Management of Data.New York:ACM Press， 2007:689-700.

[13]吳英杰，倪巍偉，張柏禮，等. K-APPRP:一種基于劃分的增量數據重發布隱私保護k-匿名算法[J]. 小型微型計算機系統， 2009，30(8):1581-1587.

[14]BYUNA J， LI Tian-cheng， BERTINO E， et al. Privacy-preserving incremental data dissemination[J]. Journal of Computer Security，2009，17(1):43-68.

[15]AGGARWAL G， FEDER T， KENTHAPADI T， et al. Achieving anonymity via clustering[C]//Proc of Symposium on Principles of Database Systems.New York:ACM Press，2006:153-162.

[16]MEYERSON A， WILLIAMS R. On the complexity of optimal k-anonymity[C]//Proc of the 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.New York:ACM Press，2004:223-228.

[17]LEFEVRE K， DEWITTD J， RAMAKRISHNAN R. Incpgnoto: efficient full-domain k-anonymity[C]//Proc of ACM SIGMOD International Conference on Management of Data.New York:ACM Press，2005:49-60.

[18]FUNG B， WANG Ke， YU P. Top-down specialization for information and privacy preservation[C]//Proc of the 21st IEEE International Conference on Data Engineering. Washington DC: IEEE Computer Society，2005:205-216.

[19]WANG Ke， YU P， CHALRABORTY S. Bottom-up generalization: a data mining solution to privacy protection[C]//Proc of the 4th IEEE International Conference on Data Mining. Washington DC: IEEE Computer Society，2004:249-256.

[20]BYUN J， KAMRA A， BERTINO E， et al. Efficient k-anonymization using clustering techniques[C]//Proc of International Conference on Database Systems for Advanced Applications.Berlin:Springer-Verlag，2007:188-200.

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

[22]KIFER D， GEHRKE J. Injecting utility into anonymized datasets[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press，2006:217-228.

[23]LIN Jian-hua. Divergence measures based on the shannon theory[J]. IEEE Trans on Information Theory，1991，37(1):145-151.

[24]KULLBACK S， LEIBLER R. On information and sufficiency[J]. The Annals of Mathematical Statistics，1951，22(1):79-86.

[25]周水庚，李豐，陶宇飛，等. 面向數據庫應用的隱私保護研究綜述[J]. 計算機學報， 2009，32(5):847-861.