微觀數據發布中匿名隱私保護研究評述

徐 勇，丁忠明，李東勤

（安徽財經大學管理科學與工程學院，安徽 蚌埠233030）

0 引言

實證研究離不開數據，當前許多微觀統計數據日益以公開發布的形式成為一種公共產品，但是由于在微觀統計數據發布之后數據發布者既無法控制數據用戶對數據的使用方式、也不了解用戶掌握的其它背景知識，所以在發布數據之前如果不對微觀數據進行恰當處理將可能會泄露數據主體的敏感信息。微觀數據發布過程如何在不影響數據效用的前提下，防止敏感信息泄露、保護數據主體的隱私成為近年來的研究熱點。目前常用的隱私保護技術有數據擾亂、數據加密、數據限制等；其中Sweeny等（2002）提出的在發布之前對微觀數據進行k-匿名處理是降低數據發布過程隱私泄露概率的有效方法之一[1-3]。k-匿名方法首先將微觀數據中的個體屬性變量分為兩類：直接標識屬性變量和間接標識屬性變量，直接標識屬性變量是指能夠直接標識數據個體身份的屬性變量，如姓名、身份證號等；間接標識屬性變量又稱為準碼屬性，是指多人共有的特征，單個間接標識屬性變量無法精確標識數據個體，但是如果將多個間接標識變量組合起來將可能導致對數據個體的精確識別。k-匿名方法在將能夠直接標識屬性變量移除的基礎上，將微觀數據中記錄分成若干個等價組，每個等價組內記錄在準碼屬性上的取值相同，從而防止攻擊者通過鏈接攻擊獲取敏感信息與統計個體身份間的對應關系、同時又不過度影響數據效用的隱私信息保護方法。

1 k-匿名方法相關研究文獻綜述

Sweeny等提出的k-匿名方法要求發布后數據表中的每一條元組對應至少k個不可區分的數據主體，以使得攻擊者無法推斷出隱私信息對應的具體個體，其形式化定義見文獻[1-3]。在此之后，國內外很多學者從多個不同的角度和層面對微觀數據發布中的k-匿名隱私保護方法展開了研究。

針對滿足k-匿名要求的發布表仍然可能遭遇同質攻擊(homogeneity attack)和背景攻擊(background knowledge attack)而泄露用戶隱私信息的問題，Machanavajjha等（2007）提出了l-多樣模型隱私保護方法，該模型要求發布表中每個等價組內至少有l條“較好表現”(well represented)的記錄。“較好表現”的含義有三種：①每個等價組內敏感屬性至少出現l個不同的屬性值；②每個等價類E的熵(Entropy)要不小于logl，其中熵定義為③設m表示等價類中敏感屬性屬性值的數目，ri表示每個敏感屬性值的頻率，r1≥r2…≥rm，c為一用戶指定的常量，若在發布表的每個等價類中有：r1＜c(rl+rl+1+…+rm)，則稱滿足迭代(c,l)-多樣[4]。Ninghui Li等（2007）針對全局隱私信息和單個統計個體隱私信息的保護問題分析了l-多樣方法的不足，提出了t-closeness隱私保護方法[5]。若發布表每個等價類中敏感屬性值的分布與該敏感屬性值在整個發布表中的分布差異不超過t時，稱該發布表滿足t-closeness匿名要求。(alpha,k)-匿名模型[6]（2006）要求同一個等價組內任何一個敏感屬性值出現的頻率不大于alpha，以避免某些敏感值頻率過高的情況；并且該模型要求alpha值不小于該敏感屬性值在整個數據集上的出現頻率。該模型用于保護發布表統計個體的標識信息、準標識符與敏感屬性之間的關系。因為在某些情況下，盡管通過滿足匿名要求的準標識符無法識別出個體信息，但是由于準標識符和敏感屬性之間的關系是多對一，所以仍然能夠判斷出個體的敏感屬性值，從而造成隱私泄露。

考慮用戶執行聚集查詢操作時，基于置換的匿名表相比基于泛化的匿名表能夠得到更加精確的查詢結果，Nick Koudas等（2007）針對數值型敏感屬性的隱私保護問題，在擴展k-匿名方法的基礎上提出一個針對數值型敏感屬性隱私保護問題的基于置換的匿名保護框架。該方法的基本思想是對數據表T進行分組，然后在保持準碼屬性不變的情況下，交換敏感屬性的值，使得每一個等價組中敏感屬性共有k個不同的取值，并且最小屬性值與最大屬性值之間的差不小于e，以防止攻擊者精確獲得關于個體的敏感屬性值[7]。

針對發布表準碼屬性值相同的泛化組內不同記錄對應數據主體隱私偏好不盡相同的情況，X.Xiao等（2006）提出了根據數據主體隱私保護需求的不同，對發布表中元組在敏感屬性上應用不同程度的個性化隱私保護結點(Node)保持方法[8]，第一步按照常規k-匿名方法對準碼屬性進行泛化匿名，第二步對不同等價組內敏感屬性利用不同的泛化函數進行敏感屬性值泛化。該方法的不足之處在于：(1)需要結合敏感屬性的泛化實現個性化的隱私保護目的，并且在敏感屬性泛化時要求等價組中的任意兩條元組的敏感屬性值不能重疊，即滿足域泛化的定義。這一要求將會造成敏感屬性信息的過度丟失、嚴重影響數據效用。(2)隱私保護違背概率Pbreach(t)的計算依賴攻擊者掌握的背景知識數據庫中相關元組個數n。盡管可以用n的最小可能取值m(泛化表等價組中的元組個數)代替n參與計算，但此時計算得到的概率值是隱私保護程度最嚴格情況下的取值。因此，X.Xiao等提出的匿名方法以元組為單位計算隱私違背概率、并指導泛化過程必然會帶來發布表信息損失過度的后果。Yabo Xu等（2009）研究了個性化Web信息發布服務中的匿名隱私保護方法[9]。

盡管目前已有許多以k-匿名方法為基礎的匿名隱私保護方法出現，但是仍然沒有哪一種方法能夠適用于所有的微觀統計數據發布領域。因此需要數據發布者、政府機構在實際微觀統計數據發布過程中深入分析微觀統計數據的特征和發布數據面向的用戶特征，采用適當的匿名方法以實現發布數據效用和泄露風險的均衡。

2 實現k-匿名方法的常用技術

目前實現微觀數據匿名發布的常用技術有三類：基于Apriori思想的匿名技術、基于聚類的匿名技術和基于交換的匿名技術。

(1)基于Apriori思想的匿名技術。該技術首先按照屬性變量取值的層次結構自底向上迭代，迭代過程中分別判斷準碼屬性變量集在泛化之后是否滿足隱私保護要求，若滿足則停止迭代；否則繼續向上層迭代。Sweeney等結合泛化和限制技術，提出了一個理論上的最小泛化k-匿名實現方法，該算法只需最小數據擾亂即可提供對微觀發布數據的泄露風險保護[2,3,10]。LeFevre等（2005）提出的全域泛化k-匿名方法Incognito使用泛化層結構對每一維屬性變量自底向上進行全域泛化，其維度組合過程則借鑒了Apriori算法思想（1994），通過連接和剪枝處理可以以較小的時間代價獲得元數據的最小全域泛化模式[10]。

(2)基于聚類的匿名技術（2007）[12]。若將含有d個屬性變量微觀數據中的n條記錄看成是d維空間中的n個點，那么基于聚類的匿名化過程即為如何將這n個點聚成若干類，并使其滿足每個類中至少含有k個點，并且這k個點對應的k個記錄在準碼屬性變量上的取值是相同的。這種匿名技術的優點是可以將微觀數據集中最相似的記錄歸為同一個等價組。其缺點是無法根據數據主體不同的隱私保護要求提供個性化的隱私保護策略機制；另外，當針對發布數據表執行聚類操作得到的等價組記錄個數不足k時，只能繼續將不相似的記錄歸入同一個等價組，因而仍然無法避免信息損失過大的問題。

(3)基于交換的匿名技術（2005）[10]。該方法基本思想是首先用與常規k-匿名方法類似的泛化方法對微觀數據集T進行分組，然后在等價組間交換敏感屬性的值，使得每一組中敏感屬性共有k個不同的值，并且最小屬性值與最大屬性值之間的差大于e。基于置換的匿名技術相比基于泛化的匿名技術能夠得到更加精確的查詢結果，但其主要缺點是損害了發布表中準碼屬性變量與敏感屬性之間的聯系信息。

除此之外還有其它一些微觀數據匿名化實現技術，但是無論哪種技術均是以降低數據的效用換取數據泄露風險的降低，而數據效用和泄露風險的最佳平衡點的尋找則是一個NP難題。在實際操作過程，數據發布者可以結合數據發布實際情況尋找一個局部最優均衡點。

3 匿名發布表的質量度量方法

3.1 分類度量方法CM[13]

Iyengar等（2002）提出一種分類度量方法（Classification Metric，CM）來計算信息損失，這種方法往往應用于使用微觀發布數據進行分類分析的場合。該模型為每條記錄分配一個分類標記，經匿名處理后根據數據的分類標記給出一個懲罰因子，如下式：

當記錄被完全泛化、即r的所有參與泛化的屬性值都已經被替換為完全不可用的值或符號，或者當r的分類標記與其所在等價組的主分類不同時，給r一個懲罰值：

這種微觀發布數據信息度量方法的缺陷在于它只考慮屬性變量的分類標記，因此僅僅可以適用于分類分析目的的應用，卻很難將其擴展應用于通用微觀數據分析應用場合的效用評估。

3.2 匿名表效用[14]

Xu等（2006）定義了一個度量匿名表效用的計算方法NCP，該方法考慮為每個屬性分配權重以表示屬性在數據查詢應用中的效用。作者分別針對數值屬性和類別屬性提出了在匿名過程的懲罰(penalty)計算方法：

3.3 泛化距離[15]

Li等（2006）針對屬性變量取值的層次結構提出了一種基于屬性變量層次高度距離的發布數據質量度量方法。該方法首先定義屬性變量取值的層次距離概念、然后用其描述記錄的匿名擾亂程度，在此基礎上進一步定義微觀發布數據集的泛化距離表示其信息損失程度。

①加權層次距離(Weighted Hierarchical Distance)設h為屬性變量的域泛化層次高度，數字1,2,…,h-1,h分別對應屬性變量泛化程度最高的泛化樹根結點至葉子結點所在的各個層次序號。用wj,j-1表示j層和j-1層的權重，其中2≤j≤h。當屬性變量的某個取值從p層泛化至q層(p＞q)，則該加權泛化距離定義為

②記錄的泛化擾亂程度(Distortions of Generalization of Tuples)設 t={v1,v2,…,vm}和其中 t’是 t的泛化元組；level(vj)是屬性變量取值在屬性變量vj層次結構上的層次序號，則記錄泛化距離定義為

③微觀發布數據集的泛化擾亂程度(Distortions of Generalization of Tables)設數據集D’是原始微觀數據集D的泛化數據集；ti、ti’分別是數據集D、D’的第i個記錄，則泛化擾亂程度定義為：

4 結論與展望

隨著人們對隱私信息越來越重視，在微觀數據發布領域，如何保護微觀數據中數據個體的敏感隱私信息不被惡意攻擊者獲取，同時又保證數據接收者能夠獲得充足的數據信息進行有效的探索和數據分析任務變成一個亟待研究、解決的問題、將面臨許多具有挑戰性且有趣的研究點。在下一步的研究工作中，我們課題組將深入研究以下三個方面的問題：

(1)同一來源微觀數據多次發布中的隱私保護問題。目前大多數相關研究工作是針對單次發布場合下的隱私保護問題的，當來自同一數據源的微觀數據需要在時間變化情況下進行多次發布時，現有匿名方法是否能夠提供足夠的隱私保護，需要進行一步進行探討。

(2)多敏感屬性的隱私保護問題。當微觀數據包含多個敏感屬性時，敏感屬性之間可能會存在一定的聯系，如何充分利用這種聯系挖掘敏感屬性集包含的知識，應用于隱私保護過程，達到降低微觀發布數據信息損失程度的目的。

(3)考慮語義一致的匿名方法。已有的匿名方法在對微觀數據中準碼屬性變量進行泛化時，沒有考慮屬性變量泛化域的語義因素。現實世界中字符相同的名詞在不同的應用領域可能會表達不同的概念、代表不同的語義，因此微觀數據發布過程利用匿名技術實現隱私保護目的時，對準碼屬性的處理需要研究考慮語義的用戶隱私偏好描述方法，結合多k值匿名方法設計更加靈活的個性化隱私保護方法。當在泛化過程中考慮語義之后，發布表的隱私保護度和信息損失度將會包含更加豐富的含義，其定義形式也會更加復雜，進一步工作中還將深入研究考慮語義的隱私保護度和信息損失度定義方法。

[1] P.Samarati，L.Sweeney.Generalizing Data to Provide Anonymity when Disclosing Information[C].ProceedingsoftheSeventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems，Seattle，WA，USA，1998.

[2] L.Sweeney.K-anonymity∶a Model for Protecting Privacy[J].Journal on Uncertainty,Fuzziness and Knowledge-based Systems,2002,10(5).

[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).

[4] Machanavajjhal A A，Gehrke J，Kifer D．l-diversity：Privacy Beyond K-anonymity[C].ACM Transactions on Knowledge Discovery from Data(TKDD).New York：ACM Press，2007，1(1)．

[5] N Li,T Li,S Venkatasubramanian.T-Closeness～Privacy beyond K-anonymity and L-diversity[C].Proceedings of IEEE 23RD International Conference on Data Engineering.Istanbul∶IEEE Computer Society,2007.

[6] RCW Wong,J Li,AWC Fu,K Wang．(a，k)-Anonymity：An Enhanced K-anonymity Model for Privacy-preserving Data Publishing[C].Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data mining.New York：ACM Press，2006．

[7] N Koudas,D Srivastava,T Yu,Q Zhang.Aggregate Query Answering on Anonymized Tables[C].2007 IEEE 23rd International Conference on Data Engineering,2007.

[8] X.Xiao,Y.Tao.Personalized Privacy Preservation[C].Proceedings of ACM Conference on Management of Data(SIGMOD).New York∶ACM Press,2006.

[9] Yabo Xu,Ke Wang,Guoliang Yang,Ada W.C.Fu.Online Anonymity for Personalized Web Services[C].Proceeding of the 18th ACM Conference on Information and Knowledge Management,2009.

[10] K.LeFevre,D.DeWitt,R.Ramakrishnan.Incognito：Efficient Full-Domain K-Anonymity[C].In In Proceedings of ACM SIGMOD Conference,Baltimore,MD,June 2005.

[11] A grawal R,Srikant R.Fast Algorithms for Mining Association Rules[C].Proceedings of the 20th International Conference on Very Large Databases.Santiago∶Morgan Kaufmann,1994.

[12] JW Byun,A Kamra,E Bertino,N Li.Efficient K-anonymization Using Clustering Techniques[C].Proceedings of Database Systems for Advanced Applications(DASFAA2007),LNCS4443.Berlin∶Springer-Verlag,2007.

[13] V.S.Iyengar.Transforming Data to Satisfy Privacy Constraints[C].In∶Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD),Edmonton,AB,Canada,2002.

[14] J.Xu,W.Wang,J.Pei,et al.Utility-Based Anonymization Using Local Recoding[C].Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,ACM Press,2006.

[15] Li JY,Wong R,Fu A,Pei J.Achieving K-anonymity by Clustering in Attribute Hierarchical Structures[A].In∶Tjoa AM,Trujillo J,eds.Proc.of the 8th Int’l Conf.on Data Warehousing and Knowledge Discovery[M].Heidelberg∶Springer-Verlag,2006.