[[373474]]

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

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

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

圖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ù)上進(jìn)行有效的數(shù)據(jù)挖掘以便于研究和利用。這里講的數(shù)據(jù)挖掘具有廣泛的意義，并不僅限于模式挖掘和模型構(gòu)建。例如，疾病控制中心須收集各醫(yī)療機(jī)構(gòu)的病歷信息，以進(jìn)行疾病的預(yù)防與控制。某醫(yī)療機(jī)構(gòu)從患者那里收集了大量的數(shù)據(jù)，并且把這些數(shù)據(jù)發(fā)布給疾病控制中心。本例中，醫(yī)療機(jī)構(gòu)是數(shù)據(jù)發(fā)布者，患者是數(shù)據(jù)記錄擁有者，疾病控制中心是數(shù)據(jù)接收者。疾病控制中心進(jìn)行的數(shù)據(jù)挖掘可以是從糖尿病患者的簡單計(jì)數(shù)到任何事情的聚類分析。

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

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

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

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

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

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

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

（1）隨機(jī)化

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

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

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

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

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

（2）阻塞與凝聚

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

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

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

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

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

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

（1）安全多方計(jì)算

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

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

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

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

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

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

（2）分布式匿名化

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

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

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

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

過程：

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

② 表T×←NULL。

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

④ 站點(diǎn)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×}并將其傳遞給另一站點(diǎn)；

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

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

⑤ end while。

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

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

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

（4）分布式聚類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

② 面向特定目標(biāo)的匿名化算法

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

③ 基于聚類的匿名化算法

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

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

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

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

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

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

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

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

① 標(biāo)志符屬性

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

② 敏感屬性

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

③ 準(zhǔn)標(biāo)志符屬性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例如，在處理工資信息時(shí)，需要重點(diǎn)關(guān)注的是超高收入人群和超低收入人群，這是因?yàn)橥@兩個(gè)群體會(huì)更加在意他們的工資信息是否被泄露。然而對(duì)于那些工資處于平均水平的人群來說，他們對(duì)個(gè)人工資信息的保護(hù)欲則較低。這種情況下，敏感屬性值就可以設(shè)置得大一些，甚至可以設(shè)為1?？梢岳斫鉃樵撁舾袑傩灾蹬c保護(hù)等級(jí)相關(guān)聯(lián)。通過設(shè)定閾值a，能更加有效地防止隱私信息的泄露，從而提高隱私信息的保護(hù)程度。

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

表6 （0.5,2）-匿名表

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

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

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

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

表7  2-多樣性表

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

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

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

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

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

（6）Anatomy方法

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