徐 勇，丁忠明，李東勤

（安徽財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，安徽 蚌埠233030）

0 引言

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

1 k-匿名方法相關(guān)研究文獻(xiàn)綜述

Sweeny等提出的k-匿名方法要求發(fā)布后數(shù)據(jù)表中的每一條元組對(duì)應(yīng)至少k個(gè)不可區(qū)分的數(shù)據(jù)主體，以使得攻擊者無法推斷出隱私信息對(duì)應(yīng)的具體個(gè)體，其形式化定義見文獻(xiàn)[1-3]。在此之后，國內(nèi)外很多學(xué)者從多個(gè)不同的角度和層面對(duì)微觀數(shù)據(jù)發(fā)布中的k-匿名隱私保護(hù)方法展開了研究。

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

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

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

盡管目前已有許多以k-匿名方法為基礎(chǔ)的匿名隱私保護(hù)方法出現(xiàn)，但是仍然沒有哪一種方法能夠適用于所有的微觀統(tǒng)計(jì)數(shù)據(jù)發(fā)布領(lǐng)域。因此需要數(shù)據(jù)發(fā)布者、政府機(jī)構(gòu)在實(shí)際微觀統(tǒng)計(jì)數(shù)據(jù)發(fā)布過程中深入分析微觀統(tǒng)計(jì)數(shù)據(jù)的特征和發(fā)布數(shù)據(jù)面向的用戶特征，采用適當(dāng)?shù)哪涿椒ㄒ詫?shí)現(xiàn)發(fā)布數(shù)據(jù)效用和泄露風(fēng)險(xiǎn)的均衡。

2 實(shí)現(xiàn)k-匿名方法的常用技術(shù)

目前實(shí)現(xiàn)微觀數(shù)據(jù)匿名發(fā)布的常用技術(shù)有三類：基于Apriori思想的匿名技術(shù)、基于聚類的匿名技術(shù)和基于交換的匿名技術(shù)。

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

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

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

除此之外還有其它一些微觀數(shù)據(jù)匿名化實(shí)現(xiàn)技術(shù)，但是無論哪種技術(shù)均是以降低數(shù)據(jù)的效用換取數(shù)據(jù)泄露風(fēng)險(xiǎn)的降低，而數(shù)據(jù)效用和泄露風(fēng)險(xiǎn)的最佳平衡點(diǎn)的尋找則是一個(gè)NP難題。在實(shí)際操作過程，數(shù)據(jù)發(fā)布者可以結(jié)合數(shù)據(jù)發(fā)布實(shí)際情況尋找一個(gè)局部最優(yōu)均衡點(diǎn)。

3 匿名發(fā)布表的質(zhì)量度量方法

3.1 分類度量方法CM[13]

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

當(dāng)記錄被完全泛化、即r的所有參與泛化的屬性值都已經(jīng)被替換為完全不可用的值或符號(hào)，或者當(dāng)r的分類標(biāo)記與其所在等價(jià)組的主分類不同時(shí)，給r一個(gè)懲罰值：

這種微觀發(fā)布數(shù)據(jù)信息度量方法的缺陷在于它只考慮屬性變量的分類標(biāo)記，因此僅僅可以適用于分類分析目的的應(yīng)用，卻很難將其擴(kuò)展應(yīng)用于通用微觀數(shù)據(jù)分析應(yīng)用場合的效用評(píng)估。

3.2 匿名表效用[14]

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

3.3 泛化距離[15]

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

①加權(quán)層次距離(Weighted Hierarchical Distance)設(shè)h為屬性變量的域泛化層次高度，數(shù)字1,2,…,h-1,h分別對(duì)應(yīng)屬性變量泛化程度最高的泛化樹根結(jié)點(diǎn)至葉子結(jié)點(diǎn)所在的各個(gè)層次序號(hào)。用wj,j-1表示j層和j-1層的權(quán)重，其中2≤j≤h。當(dāng)屬性變量的某個(gè)取值從p層泛化至q層(p＞q)，則該加權(quán)泛化距離定義為

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

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

4 結(jié)論與展望

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

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

(2)多敏感屬性的隱私保護(hù)問題。當(dāng)微觀數(shù)據(jù)包含多個(gè)敏感屬性時(shí)，敏感屬性之間可能會(huì)存在一定的聯(lián)系，如何充分利用這種聯(lián)系挖掘敏感屬性集包含的知識(shí)，應(yīng)用于隱私保護(hù)過程，達(dá)到降低微觀發(fā)布數(shù)據(jù)信息損失程度的目的。

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

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