[[373474]]

 01 數(shù)據(jù)庫的隱私威脅模型

目前，隱私保護技術(shù)在數(shù)據(jù)庫中的應(yīng)用主要集中在數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布兩個領(lǐng)域。數(shù)據(jù)挖掘中的隱私保護（Privacy Protection Data Mining，PPDM）是指如何在能保護用戶隱私的前提下進行有效的數(shù)據(jù)挖掘；數(shù)據(jù)發(fā)布中的隱私保護（Privacy Protection Data Publish，PPDP）是指如何在保護用戶隱私的前提下發(fā)布用戶的數(shù)據(jù)，以供第三方有效地研究和使用。

圖1描述了數(shù)據(jù)收集和數(shù)據(jù)發(fā)布的一個典型場景。

圖1  數(shù)據(jù)收集和數(shù)據(jù)發(fā)布

在數(shù)據(jù)收集階段，數(shù)據(jù)發(fā)布者從數(shù)據(jù)擁有者（如Alice，Bob等）處收集到了大量的數(shù)據(jù)。在數(shù)據(jù)發(fā)布階段，數(shù)據(jù)發(fā)布者發(fā)布收集到的數(shù)據(jù)給挖掘用戶或公共用戶，這里也將他們稱為數(shù)據(jù)接收者，它能夠在發(fā)布的數(shù)據(jù)上進行有效的數(shù)據(jù)挖掘以便于研究和利用。這里講的數(shù)據(jù)挖掘具有廣泛的意義，并不僅限于模式挖掘和模型構(gòu)建。例如，疾病控制中心須收集各醫(yī)療機構(gòu)的病歷信息，以進行疾病的預(yù)防與控制。某醫(yī)療機構(gòu)從患者那里收集了大量的數(shù)據(jù)，并且把這些數(shù)據(jù)發(fā)布給疾病控制中心。本例中，醫(yī)療機構(gòu)是數(shù)據(jù)發(fā)布者，患者是數(shù)據(jù)記錄擁有者，疾病控制中心是數(shù)據(jù)接收者。疾病控制中心進行的數(shù)據(jù)挖掘可以是從糖尿病患者的簡單計數(shù)到任何事情的聚類分析。

有兩種計算模型針對數(shù)據(jù)發(fā)布者。在不可信計算模型中，數(shù)據(jù)發(fā)布者是不可信的，它可能會嘗試從數(shù)據(jù)擁有者那里識別敏感信息。各種加密方法、匿名通信方法以及統(tǒng)計方法等都可用于從數(shù)據(jù)擁有者那里匿名收集數(shù)據(jù)而不泄露數(shù)據(jù)擁有者的身份標志。在可信計算模式中，數(shù)據(jù)發(fā)布者是可信的，而且數(shù)據(jù)擁有者也愿意提供他們的數(shù)據(jù)給數(shù)據(jù)發(fā)布者。但是，數(shù)據(jù)接收者是不可信的。

數(shù)據(jù)挖掘與知識發(fā)現(xiàn)在各個領(lǐng)域都扮演著非常重要的角色。數(shù)據(jù)挖掘的目的在于從大量的數(shù)據(jù)中抽取出潛在的、有價值的知識（模型或規(guī)則）。傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)在發(fā)現(xiàn)知識的同時會給數(shù)據(jù)的隱私帶來嚴重威脅。例如，疾病控制中心在收集各醫(yī)療機構(gòu)的病歷信息的過程中，傳統(tǒng)數(shù)據(jù)挖掘技術(shù)將不可避免地會暴露患者的敏感數(shù)據(jù)（如所患疾?。@些敏感數(shù)據(jù)是數(shù)據(jù)擁有者（醫(yī)療機構(gòu)、病人）不希望被揭露或被他人知道的。

02 數(shù)據(jù)庫的隱私保護技術(shù)

隱私保護技術(shù)是為了解決數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布中的數(shù)據(jù)隱私暴露問題。隱私保護技術(shù)在具體實施時需要考慮以下兩個方面：① 如何保證數(shù)據(jù)應(yīng)用過程中不泄露數(shù)據(jù)隱私；② 如何更有利于數(shù)據(jù)的應(yīng)用。下面分別對基于數(shù)據(jù)失真的隱私保護技術(shù)、基于數(shù)據(jù)加密的隱私保護技術(shù)、基于限制發(fā)布的隱私保護技術(shù)進行詳細介紹。

1. 基于數(shù)據(jù)失真的隱私保護技術(shù)

數(shù)據(jù)失真技術(shù)是通過擾動原始數(shù)據(jù)來實現(xiàn)隱私保護的，擾動后的數(shù)據(jù)需要滿足：① 攻擊者不能發(fā)現(xiàn)真實的原始數(shù)據(jù)，即攻擊者不能通過發(fā)布的失真數(shù)據(jù)并借助一定的背景知識重構(gòu)出真實的原始數(shù)據(jù)；② 經(jīng)過失真處理后的數(shù)據(jù)要能夠保持某些性質(zhì)不變，即利用失真數(shù)據(jù)得出的某些信息和從原始數(shù)據(jù)中得出的信息要相同，如某些統(tǒng)計特征要一樣，這保證了基于失真數(shù)據(jù)的某些應(yīng)用是可行的。

基于失真的隱私保護技術(shù)主要采用隨機化、阻塞、凝聚等技術(shù)。

（1）隨機化

數(shù)據(jù)隨機化就是在原始數(shù)據(jù)中加入隨機噪聲，然后發(fā)布擾動后的數(shù)據(jù)。隨機化技術(shù)包括隨機擾動和隨機應(yīng)答兩類。

① 隨機擾動。隨機擾動采用隨機化技術(shù)來修改敏感數(shù)據(jù)，達到對數(shù)據(jù)隱私的保護。圖2（a）給出了隨機擾動的過程。攻擊者只能截獲或觀察擾動后的數(shù)據(jù)，這樣就實現(xiàn)了對真實數(shù)據(jù)X的隱藏，但是擾動后的數(shù)據(jù)仍然保留著原始數(shù)據(jù)的分布信息。通過對擾動數(shù)據(jù)進行重構(gòu)，如圖2（b）所示，可以恢復(fù)原始數(shù)據(jù)X的信息，但不能重構(gòu)原始數(shù)據(jù)的精確值x1,x2,…,xn。

圖2  隨機擾動與重構(gòu)過程

隨機擾動技術(shù)可以在不暴露原始數(shù)據(jù)的情況下進行多種數(shù)據(jù)挖掘操作。由于擾動后的數(shù)據(jù)通過重構(gòu)得到的數(shù)據(jù)分布幾乎和原始數(shù)據(jù)的分布相同，因此，利用重構(gòu)數(shù)據(jù)的分布進行決策樹分類器訓(xùn)練后，得到的決策樹能很好地對數(shù)據(jù)進行分類。在關(guān)聯(lián)規(guī)則挖掘中，可以通過在原始數(shù)據(jù)中加入大量偽項來隱藏頻繁項集，再通過在隨機擾動后的數(shù)據(jù)上估計項集的支持度來發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。除此之外，隨機擾動技術(shù)還可以被應(yīng)用到聯(lián)機分析處理（Online Analytical Processing，OLAP）上，實現(xiàn)對隱私的保護。

② 隨機應(yīng)答。隨機應(yīng)答是指數(shù)據(jù)擁有者在擾動原始數(shù)據(jù)后再將其發(fā)布，以使攻擊者不能以高于預(yù)定閾值的概率得出原始數(shù)據(jù)是否包含某些真實信息或偽信息。雖然發(fā)布的數(shù)據(jù)不再真實，但是在數(shù)據(jù)量比較大的情況下，統(tǒng)計信息和匯聚信息仍然可以被較為精確地估計出來。隨機應(yīng)答和隨機擾動的不同之處在于敏感數(shù)據(jù)是通過一種應(yīng)答特定問題的方式提供給外界的。

（2）阻塞與凝聚

隨機化技術(shù)的一個無法避免的缺點是：針對不同的應(yīng)用都需要設(shè)計特定的算法以對轉(zhuǎn)換后的數(shù)據(jù)進行處理，因為所有的應(yīng)用都需要重建數(shù)據(jù)的分布。凝聚技術(shù)可以克服隨機化技術(shù)的這一缺點，它的基本思想是：將原始數(shù)據(jù)分成組，每組內(nèi)存儲著由k條記錄產(chǎn)生的統(tǒng)計信息，包括每個屬性的均值、協(xié)方差等。這樣，只要是采用凝聚技術(shù)處理的數(shù)據(jù)，都可以用通用的重構(gòu)算法進行處理，并且重構(gòu)后的數(shù)據(jù)并不會披露原始數(shù)據(jù)的隱私，因為同一組內(nèi)的k條記錄是兩兩不可區(qū)分的。

與隨機化技術(shù)修改敏感數(shù)據(jù)、提供非真實數(shù)據(jù)的方法不同，阻塞技術(shù)采用的是不發(fā)布某些特定數(shù)據(jù)的方法，因為某些應(yīng)用更希望基于真實數(shù)據(jù)進行研究。例如，可以通過引入代表不確定值的符號“？”來實現(xiàn)對布爾關(guān)聯(lián)規(guī)則的隱藏。由于某些值被“？”代替，所以對某些項集的計數(shù)是一個不確定的值，此值位于一個最小估計值和最大估計值之間。于是，對敏感關(guān)聯(lián)規(guī)則的隱藏就是在數(shù)據(jù)中的阻塞盡量少的情況下，將敏感關(guān)聯(lián)規(guī)則可能的支持度和置信度控制在預(yù)定的閾值以下。另外，利用阻塞技術(shù)還可以實現(xiàn)對分類規(guī)則的隱藏。

2. 基于數(shù)據(jù)加密的隱私保護技術(shù)

基于數(shù)據(jù)加密的隱私保護技術(shù)多用于分布式應(yīng)用中，如分布式數(shù)據(jù)挖掘、安全查詢、幾何計算、科學(xué)計算等。分布式應(yīng)用的功能實現(xiàn)通常會依賴于數(shù)據(jù)的存儲模式和站點的可信度及其行為。

分布式應(yīng)用采用垂直劃分和水平劃分兩種數(shù)據(jù)模式存儲數(shù)據(jù)。垂直劃分數(shù)據(jù)是指分布式環(huán)境中每個站點只存儲部分屬性的數(shù)據(jù)，所有站點存儲的數(shù)據(jù)不重復(fù)；水平劃分數(shù)據(jù)是將數(shù)據(jù)記錄存儲到分布式環(huán)境中的多個站點，所有站點存儲的數(shù)據(jù)不重復(fù)。分布式環(huán)境下的站點，根據(jù)其行為可以分為準誠信攻擊者和惡意攻擊者。準誠信攻擊者是遵守相關(guān)計算協(xié)議但仍試圖進行攻擊的站點；惡意攻擊者是不遵守相關(guān)計算協(xié)議且試圖披露隱私的站點。一般會假設(shè)所有站點為準誠信攻擊者。

基于加密技術(shù)的隱私保護技術(shù)主要有安全多方計算、分布式匿名化、分布式關(guān)聯(lián)規(guī)則挖掘、分布式聚類等。

（1）安全多方計算

安全多方計算協(xié)議是密碼學(xué)中非常活躍的一個學(xué)術(shù)領(lǐng)域，它有很強的理論和實際意義。一個簡單安全多方計算的實例就是著名華人科學(xué)家姚期智提出的百萬富翁問題：兩個百萬富翁Alice和Bob都想知道他倆誰更富有，但他們都不想讓對方知道關(guān)于自己財富的任何信息。

按照常規(guī)的安全協(xié)議運行之后，雙方只知道誰更加富有，而對對方具體有多少財產(chǎn)卻一無所知。

通俗地講，安全多方計算可以被描述為一個計算過程：兩個或多個協(xié)議參與者基于秘密輸入來計算一個函數(shù)。安全多方計算假定參與者愿意共享一些數(shù)據(jù)用于計算。但是，每個參與者都不希望自己的輸入被其他參與者或任何第三方知道。

一般來說，安全多方計算可以看成是在具有n個參與者的分布式網(wǎng)絡(luò)中私密輸入為x1,x2,…,xn的計算函數(shù)f（x1,x2,…,xn），其中參與者i僅知道自己的輸入xi和輸出f（x1,x2,…,xn），再沒有任何其他多余信息。如果假設(shè)有可信第三方存在，則這個問題的解決就會變得十分容易，參與者只需要將自己的輸入通過秘密通道傳送給可信第三方，由可信第三方計算這個函數(shù)，然后將計算結(jié)果廣播給每一個參與者即可。但是在現(xiàn)實中很難找到一個讓所有參與者都信任的可信第三方。因此，安全多方計算協(xié)議主要是針對在無可信第三方的情況下安全計算約定函數(shù)的問題。

眾多分布式環(huán)境下基于隱私保護的數(shù)據(jù)挖掘應(yīng)用都可以抽象成無可信第三方參與的安全多方計算問題，即如何使兩個或多個站點通過某種協(xié)議完成計算后，每一方都只知道自己的輸入和所有數(shù)據(jù)計算后的結(jié)果。

由于安全多方計算基于了“準誠信模型”這一假設(shè)，因此其應(yīng)用范圍有限。

（2）分布式匿名化

匿名化就是隱藏數(shù)據(jù)或數(shù)據(jù)來源，因為大多數(shù)應(yīng)用都需要對原始數(shù)據(jù)進行匿名處理以保證敏感信息的安全，然后在此基礎(chǔ)上進行數(shù)據(jù)挖掘與發(fā)布等操作。分布式下的數(shù)據(jù)匿名化都面臨在通信時如何既保證站點數(shù)據(jù)隱私又能收集到足夠信息以實現(xiàn)利用率盡量大的數(shù)據(jù)匿名這一問題。

以在垂直劃分的數(shù)據(jù)環(huán)境下實現(xiàn)兩方分布式k-匿名為例來說明分布式匿名化。假設(shè)有兩個站點S1、S2，它們擁有的數(shù)據(jù)分別是{ID,A1,A2,…,An}和{ID,B1,B2,…,Bn}，其中，Ai為S1擁有數(shù)據(jù)的第i個屬性。利用可交換加密在通信過程中隱藏原始信息，在構(gòu)建完整的匿名表時判斷是否“滿足k-匿名條件”先實現(xiàn)。分布式k-匿名算法如下所示。

輸入：站點S1、S2，數(shù)據(jù){ID,A1,A2,…,An}、{ID,B1,B2,…,Bn}

輸出：k-匿名數(shù)據(jù)表T×

過程：

① 2個站點分別產(chǎn)生私有密鑰K1和K2，且須滿足：EK1（EK2（D））=EK2（EK1（D）），其中D為任意數(shù)據(jù)。

② 表T×←NULL。

③ while T×中數(shù)據(jù)不滿足k-匿名條件 do。

④ 站點i（i=1或2）

a. 泛化{ID,A1,A2,…,An}為{ID,A1×,A2×,…,An×}，其中A1×表示A1泛化后的值；

b. {ID,A1,A2,…,An}←{ID,A1×,A2×,…,An×}；

c. 用Ki加密{ID,A1×,A2×,…,An×}并將其傳遞給另一站點；

d. 用Ki加密另一站點加密的泛化數(shù)據(jù)并回傳；

e. 根據(jù)兩個站點加密后的ID值對數(shù)據(jù)進行匹配，構(gòu)建經(jīng)K1和K2加密后的數(shù)據(jù)表T×{ID,A1×,A2×,…,An×，ID,B1,B2,…,Bn}。

⑤ end while。

在水平劃分的數(shù)據(jù)環(huán)境中，可以通過引入第三方，利用滿足性質(zhì)的密鑰來實現(xiàn)數(shù)據(jù)的k-匿名化：每個站點加密私有數(shù)據(jù)并將其傳遞給第三方，當且僅當有k條數(shù)據(jù)記錄的準標志符屬性值相同時，第三方的密鑰才能將這k條數(shù)據(jù)記錄進行解密。

（3）分布式關(guān)聯(lián)規(guī)則挖掘

在分布式環(huán)境下，關(guān)聯(lián)規(guī)則挖掘的關(guān)鍵是計算項集的全局計數(shù)，加密技術(shù)能保證在計算項集計數(shù)的同時，不會泄露隱私信息。例如，在數(shù)據(jù)垂直劃分的分布式環(huán)境中，需要解決的問題是：如何利用分布在不同站點的數(shù)據(jù)計算項集計數(shù)，找出支持度大于閾值的頻繁項集。此時，在不同站點之間計數(shù)的問題被簡化為在保護隱私數(shù)據(jù)的同時，在不同站點間計算標量積的問題。

（4）分布式聚類

基于隱私保護的分布式聚類的關(guān)鍵是安全地計算數(shù)據(jù)間的距離，聚類模型有Naïve聚類模型（K-means）和多次聚類模型，兩種模型都利用了加密技術(shù)來實現(xiàn)信息的安全傳輸。

① Naïve聚類模型：各個站點將數(shù)據(jù)加密方式安全地傳遞給可信第三方，由可信第三方進行聚類后返回結(jié)果。

② 多次聚類模型：首先各個站點對本地數(shù)據(jù)進行聚類并發(fā)布結(jié)果，然后通過對各個站點發(fā)布的結(jié)果進行二次處理，實現(xiàn)分布式聚類。

3. 基于限制發(fā)布的隱私保護技術(shù)

限制發(fā)布是指有選擇地發(fā)布原始數(shù)據(jù)、不發(fā)布或者發(fā)布精度較低的敏感數(shù)據(jù)以實現(xiàn)隱私保護。當前基于限制發(fā)布的隱私保護技術(shù)主要采用數(shù)據(jù)匿名化技術(shù)，即在隱私披露風(fēng)險和數(shù)據(jù)精度之間進行折中，有選擇地發(fā)布敏感數(shù)據(jù)及可能披露敏感數(shù)據(jù)的信息，但保證敏感數(shù)據(jù)及隱私的披露風(fēng)險在可容忍的范圍內(nèi)。

數(shù)據(jù)匿名化一般采用兩種基本操作。

① 抑制。抑制某數(shù)據(jù)項，即不發(fā)布該數(shù)據(jù)項。

② 泛化。泛化指對數(shù)據(jù)進行更抽象的和概括性的描述。例如，可把年齡30歲泛化成區(qū)間[20,40]的形式，因為30在區(qū)間[20,40]內(nèi)。

數(shù)據(jù)匿名化處理的原始數(shù)據(jù)一般為數(shù)據(jù)表形式，表中每一行都是一個記錄，對應(yīng)一個人。每條記錄包含多個屬性（數(shù)據(jù)項），這些屬性可分為3類。

① 顯式標志符（explicit identifier），能唯一表示單一個體的屬性，如身份證、姓名等。

② 準標志符（quasi-identifiers），幾個屬性聯(lián)合起來可以唯一標志一個人，如郵編、性別、出生年月等聯(lián)合起來可能就是一個準標志符。

③ 敏感屬性（sensitive attribute），包含用戶隱私數(shù)據(jù)的屬性，如疾病、收入、宗教信仰等。

表1所示為某家醫(yī)院的原始診斷記錄，每一條記錄（行）都對應(yīng)一個唯一的病人，其中{“姓名”}為顯示標志符屬性，{“年齡”“性別”“郵編”}為準標志符屬性，{“疾病”}為敏感屬性。

表1  某醫(yī)院原始診斷記錄

傳統(tǒng)的隱私保護方法是先刪除表1中的顯示標志符“姓名”，然后再將其發(fā)布出去。表2給出了表1的匿名數(shù)據(jù)。假設(shè)攻擊者知道表2中有Betty的診斷記錄，而且攻擊者知道Betty年齡是25歲，性別是女，郵編是12300，則根據(jù)表2，攻擊者可以很容易地確定Betty對應(yīng)表中的第一條記錄。因此，攻擊者可以肯定Betty患了腫瘤。

表2  某醫(yī)院原始診斷記錄（匿名）

顯然，由傳統(tǒng)的數(shù)據(jù)隱私保護算法得到匿名數(shù)據(jù)不能很好地阻止攻擊者根據(jù)準標志符信息推測目標個體的敏感信息。因此，需要有更加嚴格的匿名處理方法以達到保護數(shù)據(jù)隱私的目的。

（1）數(shù)據(jù)匿名化算法

大多數(shù)匿名化算法致力于解決根據(jù)通用匿名原則怎樣更好地發(fā)布匿名數(shù)據(jù)這一問題，另一方面則致力于解決在具體應(yīng)用背景下，如何使發(fā)布的匿名數(shù)據(jù)更有利于應(yīng)用。

① 基于通用原則的匿名化算法

基于通用原則的匿名化算法通常包括泛化空間枚舉、空間修剪、選取最優(yōu)化泛化、結(jié)果判斷與輸出等步驟?；谕ㄓ迷瓌t的匿名化算法大都基于k-匿名算法，不同之處僅在于判斷算法結(jié)束的條件，而泛化策略、空間修剪等都是基本相同的。

② 面向特定目標的匿名化算法

在特定的應(yīng)用場景下，通用的匿名化算法可能不能滿足特定目標的要求。面向特定目標的匿名化算法就是針對特定應(yīng)用場景的隱私化算法。例如，考慮到數(shù)據(jù)應(yīng)用者需要利用發(fā)布的匿名數(shù)據(jù)構(gòu)建分類器，因此設(shè)計匿名化算法時就需要考慮在保護隱私的同時，怎樣使發(fā)布的數(shù)據(jù)更有利于分類器的構(gòu)建，并且采用的度量指標要能直接反映出對分類器構(gòu)建的影響。已有的自底向上的匿名化算法和自頂向下的匿名化算法都將信息增益作為度量。發(fā)布的數(shù)據(jù)信息丟失越少，構(gòu)建的分類器的分類效果越好。自底向上的匿名化算法會在每次搜索泛化空間時，采用使信息丟失最少的泛化方案進行泛化，重復(fù)執(zhí)行以上操作直到數(shù)據(jù)滿足匿名原則的要求為止。自頂向下的匿名化算法的操作過程則與之相反。

③ 基于聚類的匿名化算法

基于聚類的匿名化算法將原始記錄映射到特定的度量空間，再對空間中的點進行聚類以實現(xiàn)數(shù)據(jù)匿名。類似k-匿名，算法保證每個聚類中至少有k個數(shù)據(jù)點。根據(jù)度量的不同，有r-gather和r-cellular兩種聚類算法。在r-gather算法中，以所有聚類中的最大半徑為度量對所有數(shù)據(jù)點進行聚類，在保證每個聚類至少包含k個數(shù)據(jù)點時，所有聚類中的最大半徑越小越好。

基于聚類的匿名化算法主要面臨以下兩個挑戰(zhàn)。

a. 如何對原始數(shù)據(jù)的不同屬性進行加權(quán)（因為對屬性的度量越準確，聚類的效果就越好）？

b. 如何使不同性質(zhì)的屬性同意映射到同一度量空間？

數(shù)據(jù)匿名化由于能處理多種類型的數(shù)據(jù)，并發(fā)布真實的數(shù)據(jù)，因此能滿足眾多實際應(yīng)用的需求。圖3所示是數(shù)據(jù)匿名化的場景及相關(guān)隱私匿名實例?？梢钥吹?，數(shù)據(jù)匿名化是一個復(fù)雜的過程，需要同時權(quán)衡原始數(shù)據(jù)、匿名化技術(shù)、匿名數(shù)據(jù)、背景知識、攻擊者等眾多因素。

圖3  數(shù)據(jù)匿名化場景

（2）k-匿名規(guī)則

基于k-匿名規(guī)則演化的各種數(shù)據(jù)發(fā)布方式將原始數(shù)據(jù)表中的屬性分成了以下3類。

① 標志符屬性

標志符屬性是指唯一標志身份的個體屬性，這種屬性必須在數(shù)據(jù)發(fā)布之前從數(shù)據(jù)表中全部抹掉，如用戶姓名、電話號碼、身份證號碼、聯(lián)系方式等。

② 敏感屬性

通常，包含了個體隱私信息的屬性稱為敏感屬性，如身體健康狀況、收入水平、年齡、籍貫等。

③ 準標志符屬性

通過某些單個屬性的連接來標志個體的唯一身份的屬性，稱為準標志符屬性，其能夠進行共享，也有可能會通過與其他的外部數(shù)據(jù)表進行連接而泄露隱私信息。

k-匿名規(guī)則：是指要求其在所發(fā)布的數(shù)據(jù)表中的每一條記錄，不能區(qū)別于其他k-1（k為正整數(shù)）條記錄，這些不能相互區(qū)分的k條記錄稱為一個等價類。

等價類：就是在準標志符上的投影完全相同的記錄所組成的等價組，它是針對非敏感屬性值而言的，是不能被區(qū)分的。

全局泛化：指對于每一個相同的簇，至少包含k個元組，它們對于簇中準標志符的屬性的取值完全相同，即屬性均被泛化。如表3所示，這是一個對于年齡屬性全局泛化的例子，年齡在所有簇中的取值相同。

表3  年齡屬性全局泛化的k-匿名表

局部泛化：指每個簇中的準標志符屬性相同，并且均大于k，但是簇間的屬性泛化后的值卻不相同。局部泛化的k-匿名表如表4所示。

表4  局部泛化的k-匿名表

在傳統(tǒng)k-匿名的基礎(chǔ)上，人們從多個方面對k-匿名進行了優(yōu)化和改進。改進后的算法主要有多維k-匿名算法、Datefly 算法、Incognito 算法、Classfly 算法、Mingen 算法等。

k-匿名方法通常采用泛化和壓縮技術(shù)對原始數(shù)據(jù)進行匿名化處理以便得到滿足k-匿名規(guī)則的匿名數(shù)據(jù)，從而使得攻擊者不能根據(jù)發(fā)布的匿名數(shù)據(jù)準確地識別出目標個體的記錄。

k-匿名規(guī)則要求每個等價類中至少包含k條記錄，即匿名數(shù)據(jù)中的每條記錄都至少不能和其他k-1條記錄區(qū)分開來，這樣可以防止攻擊者根據(jù)準標志符屬性識別目標個體對應(yīng)的記錄。一般k值越大對隱私的保護效果越好，但丟失的信息越多，數(shù)據(jù)還原越難。

表5給出了使用泛化技術(shù)得到的表2的k=4時的k-匿名數(shù)據(jù)（簡稱4-匿名數(shù)據(jù)）。

表5  4-匿名數(shù)據(jù)

k-匿名規(guī)則切斷了個體與數(shù)據(jù)庫中某條具體記錄的聯(lián)系，可以防止敏感屬性值泄露，而且每個個體身份被準確標志的概率最大為1/k，這在一定程度上保護了個人隱私。然而，數(shù)據(jù)表在匿名化過程中并未對敏感屬性做任何約束，這也可能會導(dǎo)致隱私泄露。k-匿名的泛化技術(shù)的思想是將原始數(shù)據(jù)中的記錄劃分成多個等價類，并用更抽象的值替換同一等價類中記錄的準標志符屬性值，使每個等價類中的記錄都擁有相同的準標志符屬性值。這樣，同一等價類內(nèi)若敏感屬性值較為集中，甚至完全相同（可能在形式上，也可能在語義上），則即使?jié)M足k-匿名要求，也很容易推理出與指定個體相應(yīng)的敏感屬性值。除此之外，攻擊者也可以通過自己掌握的足夠的相關(guān)背景知識以很高的概率來確定敏感數(shù)據(jù)與個體的對應(yīng)關(guān)系，從而導(dǎo)致隱私泄露。因此，攻擊者可以根據(jù)準標志符屬性值來區(qū)分同一等價類的所有記錄。

k-匿名方法的缺點在于并沒有考慮敏感屬性的多樣性問題，攻擊者可以利用一致性攻擊（homogeneity attack）和背景知識攻擊（background knowledge attack）來確認敏感數(shù)據(jù)與個人的聯(lián)系，進而導(dǎo)致隱私泄露。

常見的針對匿名化模型的攻擊方式有以下4種。

① 鏈接攻擊：某些數(shù)據(jù)集存在其自身的安全性，即孤立情況下不會泄露任何隱私信息，但是當惡意攻擊者利用其他存在屬性重疊的數(shù)據(jù)集進行鏈接操作時，便可能唯一識別出特定的個體，從而獲取該個體的隱私信息。將醫(yī)療信息和選舉人信息結(jié)合在一起，能夠發(fā)現(xiàn)兩個數(shù)據(jù)集的共有屬性，這樣，惡意攻擊者通過鏈接攻擊就能夠輕易確定選舉人的醫(yī)療信息情況。因此，該類攻擊手段會造成極其嚴重的隱私泄露。

② 同質(zhì)攻擊：當通過鏈接攻擊仍然無法唯一確認個體時，存在個體對應(yīng)的多條記錄擁有同一條敏感隱私信息，從而造成隱私的泄露，這一過程稱為同質(zhì)攻擊。

③ 相似性攻擊：由于敏感信息往往存在敏感度類似的情況，因此攻擊者雖然無法唯一確定個體，但是如果個體對應(yīng)的多條記錄擁有相似的敏感信息，則可推測出個體的大概隱私情況。例如，某個體患有極其不愿為人所知的疾病，這也屬于一種無法回避的嚴重攻擊。雖然該攻擊類似于同質(zhì)攻擊，并且不如同質(zhì)攻擊泄露得那么直接，但其發(fā)生的可能性極大，給被泄露者造成的心理壓力往往難以預(yù)料，因此需要特別重視此種攻擊手段。

④ 背景知識攻擊：指攻擊者掌握了某個體的某些具體信息，通過鏈接攻擊后即使只能得到某個體對應(yīng)的多條信息記錄，并且記錄間的敏感屬性也完全不同或不相似，也能根據(jù)所掌握的背景知識，從多條信息記錄中找出唯一對應(yīng)的信息記錄，從而獲取到該個體的隱私信息。

（a,k）-匿名規(guī)則、l-多樣性規(guī)則、t-逼近規(guī)則等算法在此基礎(chǔ)之上都進行了相應(yīng)程度的改進。

（3）（a,k）-匿名模型

（a,k）-匿名模型是一種擴展后的k-匿名模型，其目的是保護標志屬性與敏感信息之間的關(guān)聯(lián)關(guān)系不被泄露，從而防止攻擊者根據(jù)已經(jīng)知道的準標志符屬性的信息找到敏感屬性值。該模型要求發(fā)布的數(shù)據(jù)值在滿足k-匿名原則的同時，還需要保證這些數(shù)據(jù)里包含的每個等價類中任意一個敏感屬性值出現(xiàn)的次數(shù)與等價類個數(shù)的百分比小于a。

a表示某個敏感屬性可以接受的最大泄露概率，它所反映的是一個隱私屬性值所應(yīng)該受到的保護程度，因此a的設(shè)置至關(guān)重要，它是根據(jù)每個敏感屬性值的重要程度設(shè)置的。a的數(shù)值越小，該敏感屬性值的泄露概率就越小，隱私保護程度就越高。a的數(shù)值越大，該敏感屬性值的泄露概率就越大。

例如，在處理工資信息時，需要重點關(guān)注的是超高收入人群和超低收入人群，這是因為往往這兩個群體會更加在意他們的工資信息是否被泄露。然而對于那些工資處于平均水平的人群來說，他們對個人工資信息的保護欲則較低。這種情況下，敏感屬性值就可以設(shè)置得大一些，甚至可以設(shè)為1。可以理解為該敏感屬性值與保護等級相關(guān)聯(lián)。通過設(shè)定閾值a，能更加有效地防止隱私信息的泄露，從而提高隱私信息的保護程度。

如表6所示，在外部數(shù)據(jù)表中，姓名為標志符屬性，已經(jīng)將其刪除。年齡、性別、國籍為準標志符屬性，年收入為敏感屬性。給定數(shù)據(jù)表RT（A1,A2,…,An），QI是與RT相關(guān)聯(lián)的準標志符。若僅在RT [QI]中出現(xiàn)的每個值序列，至少在RT[QI]中出現(xiàn)過k次，這里的k=2，則RT就滿足k-匿名。若敏感屬性中的每個取值出現(xiàn)的頻率都小于a，這里a設(shè)置為0.5，則RT就滿足（a,k）-匿名。

表6 （0.5,2）-匿名表

（4）l-多樣性規(guī)則

為了解決同質(zhì)性攻擊和背景知識攻擊所帶來的隱私泄露問題，研究人員在k-匿名規(guī)則的基礎(chǔ)上提出了l-多樣性（l-diversity）規(guī)則。

如果說數(shù)據(jù)表RT′滿足k-匿名規(guī)則，且在同一等價類中的元組至少有l(wèi)個不同的敏感屬性，則稱數(shù)據(jù)表RT′滿足l-多樣性規(guī)則。

l-多樣性規(guī)則建立在k-匿名規(guī)則的基礎(chǔ)之上，其意義在于解決屬性鏈接，降低敏感屬性和準標志屬性之間的相關(guān)聯(lián)程度。該規(guī)則除了要求等價類中的元組數(shù)大于k以外，還要滿足每組元組至少有l(wèi)個不同的敏感屬性。在一定程度上而言，l-多樣性規(guī)則與（a,k）-匿名規(guī)則的意義類似。表7所示是滿足2-多樣性規(guī)則的匿名信息表，在每個等價類中，敏感屬性收入取值均大于或等于2，因此我們可以說表7滿足2-多樣性規(guī)則。

表7  2-多樣性表

同理，表5發(fā)布的數(shù)據(jù)不僅滿足4-匿名規(guī)則，這滿足3-多樣性規(guī)則，即每個等價類中至少有3個不同的敏感屬性。

顯然，l-多樣性規(guī)則仍然將原始數(shù)據(jù)中的記錄劃分成了多個等價類，并利用泛化技術(shù)使每個等價類中的記錄都擁有相同的準標志符屬性，但是l-多樣性規(guī)則要求每個等價類中至少有l(wèi)個不同的敏感屬性。因此，l-多樣性規(guī)則會使得攻擊者最多以1/l的概率確認某個體的敏感信息。

此外，l-多樣性規(guī)則仍然采用泛化技術(shù)來得到滿足隱私要求的匿名數(shù)據(jù)，而泛化技術(shù)的根本缺點在于丟失了原始數(shù)據(jù)中的大量信息。因此l-多樣性規(guī)則仍未解決k-匿名規(guī)則會丟失原始數(shù)據(jù)中的大量信息這一問題。另外，l-多樣性規(guī)則還不能阻止相似攻擊（similarity attack）。

（5）t-逼近規(guī)則

t-逼近（t-closeness）規(guī)則要求匿名數(shù)據(jù)中的每個等價類中敏感屬性值的分布接近于原始數(shù)據(jù)中的敏感屬性值的分布，兩個分布之間的距離不超過閾值t。t-closeness規(guī)則可以保證每個等價類中的敏感屬性值具有多樣性的同時在語義上也不相似，從而使其自身能夠阻止相似攻擊。但是，t-closeness規(guī)則只能防止屬性泄露，卻不能防止身份泄露。因此，t-closeness規(guī)則通常與k-匿名規(guī)則同時使用以防止身份泄露。另外，t-closeness規(guī)則仍是采用泛化技術(shù)的隱私規(guī)則，在很大程度上降低了數(shù)據(jù)發(fā)布的精度。

（6）Anatomy方法

Anatomy是肖小奎等人提出的一種高精度的數(shù)據(jù)發(fā)布隱私保護方法。Anatomy首先利用原始數(shù)據(jù)產(chǎn)生滿足l-多樣性規(guī)則的數(shù)據(jù)劃分，然后將結(jié)果分成兩張數(shù)據(jù)表發(fā)布，一張表包含每個記錄的準標志符屬性值和該記錄的等價類ID，另一張表包含等價類ID、每個等價類的敏感屬性值及其計數(shù)。這種將結(jié)果“切開”發(fā)布的方法，在提高準標志符屬性值的同時，保證了發(fā)布的數(shù)據(jù)滿足l-多樣性規(guī)則，對敏感數(shù)據(jù)提供了較好的保護。