優(yōu)秀碩士論文--基于匿名機制的數(shù)據(jù)發(fā)布中隱私泄露控制技術講解

1、基于匿名機制的數(shù)據(jù)發(fā)布中隱私泄露控制技術第一章引言1.1 研究背景數(shù)據(jù)發(fā)布環(huán)境中存在的隱私泄露問題使得數(shù)據(jù)發(fā)布隱私泄露控制技術的研究成為 學術界和工業(yè)界關注的一個焦點。數(shù)據(jù)發(fā)布中的原始數(shù)據(jù)由記錄構成，每個記錄均與一 個個體相對應，數(shù)據(jù)的屬性分為標識符、準標識符、敏感屬性三類。數(shù)據(jù)發(fā)布時直接刪 除標識符以保護個體隱私。但是可能存在攻擊者通過準標識符與外部公開的數(shù)據(jù)源進行 鏈接攻擊（linking attack） 1,導致個體隱私的泄露。研究表明，這種鏈接攻擊可以識別 大量美國公民的身份1o例如，假設一個網(wǎng)站上發(fā)布了一個醫(yī)療信息表，為保護個體隱私，將原始數(shù)據(jù)中能 識別個體身份的標識符（姓名）刪除之

2、后得到數(shù)據(jù)發(fā)布表，如表 1-1所示。表1-1屬性 組（年齡，性別，郵編）為準標識符，敏感屬性為疾病。若攻擊者可以從另一個網(wǎng)站上瀏 覽如表1-2選民登記表的信息，獲知表中法蘭克的年齡屬性值為45,性別屬性值為男，郵編 屬性值為734532。攻擊者很容易從表1-1推出法蘭克患有心臟病，造成了法蘭克 的隱私泄露。為了阻止數(shù)據(jù)發(fā)布中的鏈接攻擊，一個有效的手段是對原始數(shù)據(jù)進行匿名化處理， 從而控制個體隱私信息的泄露。表1-1醫(yī)療信息表年齡性別郵編疾病t141女734562失眠t240女734552心臟病t341男734532失眠t444男734555心臟病t544男734555失眠t645男734532

3、心臟病t741男734561禽流感t842男734533禽流感t943女734553禽流感表1-2選民登記表姓名年齡性別郵編愛麗絲41女734562貝蒂40女734552約翰41男734532比爾44男734555艾迪44男734555法蘭克45男734532凱恩41男734561杰克42男734533珍妮43女7345531.2 國內(nèi)外研究進展分析數(shù)據(jù)發(fā)布要求匿名數(shù)據(jù)既具有安全性又具有可用性， 然而兩者是相互矛盾的。因此, 數(shù)據(jù)匿名化研究的重點是設計高效的匿名保護模型和匿名算法，以使得匿名數(shù)據(jù)在保證安全性的同時，最大限度地提供可用性。目前，國內(nèi)外匿名化技術的研究已經(jīng)取得了許 多的成果。1.2

4、.1 匿名保護模型1.2.1.1 k-匿名模型(k-anonymity)定義1.11 k-匿名 假設ta1,a2,an為一個數(shù)據(jù)集，qit為與之相關的準標識符。 當且僅當數(shù)據(jù)集t中每個記錄的準標識符屬性值在數(shù)據(jù)集中至少出現(xiàn) k次，則該數(shù)據(jù)集 滿足k-匿名。定義1.21等價類 一個等價類即數(shù)據(jù)集ta1,a2,an中一組具有相同準標識符 屬性值的記錄。針對數(shù)據(jù)發(fā)布中的鏈接攻擊，文獻1,2提出了 k-匿名技術。文獻3提出實現(xiàn)k-匿 名的泛化和隱匿方法，泛化是指在數(shù)據(jù)集中用抽象的屬性值來代替原來具體的屬性值， 隱匿是指隱匿是指直接刪除數(shù)據(jù)集中某些屬性值或記錄。k-匿名通過泛化和隱匿使得等價類中每個記錄

5、具有相同的準標識符屬性值，攻擊者無法將個體與某個記錄對應起來， 從而保護個體身份的泄露。例如，表1-3是表1-1的一個滿足3-匿名模型的匿名化表，其中，匿名參數(shù) k=3 , 準標識符為屬性組（年齡，性別，郵編），敏感屬性為疾病。表1-3中生成了 3個等價類 t1, t2, t7, t4, t5, t6, t3, t8, t9。若在網(wǎng)站上用表1-3代替表1.1的醫(yī)療信息 表，那么攻擊者即使知道表1-2選民登記表中某個記錄的信息，也無法推斷出該記錄與 表1-3中某一特定記錄相關聯(lián)。例如假設攻擊者從1-2選民登記表中獲知法蘭克的信息， 與表1-3鏈接時，雖然知道法蘭克在t4, t5, t6等價類中，

6、卻無法將法蘭克與其中的某 個記錄相對應起來，從而避免法蘭克隱私的泄露。表1-3 3 -匿名化表1年齡性別郵編疾病t140-41*7345*失眠t240-41*7345*心臟病t740-41*7345*禽流感t444-45男7345*心臟病t544-45男7345*失眠t644-45男7345*心臟病t341-43*7345*失眠t841-43*7345*禽流感t941-43*7345*禽流感但是，k-匿名模型存在同質(zhì)性攻擊和背景知識攻擊的問題4。k -匿名模型由于忽略了敏感屬性值的多樣性，可能造成個體敏感屬性的隱私泄露，即同質(zhì)性攻擊。例如，假 設表1-4是表1-1的另一個滿足3-匿名模型的匿名

7、化表，表1-4中生成了 3個等價類t1, t2, t3, t4, t5, t6, t7, t8, t9。如果攻擊者從1-2選民登記表中獲知杰克的信息， 與表1-4鏈接起來時，雖然無法確定杰克與表 1-4中具體的某個記錄相對應，但通過準 標識符屬性值可以知道杰克在表1-4的t7, t8, t9等價類中，由于該等價類的敏感屬性 值均為禽流感，攻擊者容易知道杰克患有禽流感，杰克的隱私被泄露。同時，k -匿名還可能遭遇攻擊者利用預先知道的背景知識來進行攻擊。止匕外，k -匿名模型由于通過泛化準標識符屬性達到匿名的目的也導致大量原始信息的損失，降低了匿名數(shù)據(jù)的可用性。表1-4 3-匿名化表2年齡性別郵編

8、疾病t140-41*7345*失眠t240-41*7345*心臟病t340-41*7345*失眠t444-45男7345*心臟病t544-45男7345*失眠t644-45男7345*心臟病t741-43*7345*禽流感t841-43*7345*禽流感t941-43*7345*禽流感1.2.1.2 l-多樣性模型(l-diversity)文獻4提出了 l-多樣性模型(l-diversity)以彌補k-匿名模型的不足。定義184 l-多樣性原則一個等價類如果對于敏感屬性 s至少包含l個不同的敏感屬性值，那么該等價類是l-多樣性的。如果數(shù)據(jù)集t中的每個等價類是l-多樣性的， 則稱該數(shù)據(jù)集滿足l-

9、多樣性。該模型除了要求滿足k-匿名之外，還要求每個等價類的敏感屬性值具有多樣性以防 止敏感屬性的隱私泄露。例如，表 1-5是表1-1的一個滿足3-多樣性模型的匿名化表， 其中，l=3, q 1=(年齡，性別，郵編)。表1-5中生成了 3個等價類t1, t2, t7, t4, t5, t9, t3, t6, t8。每個等價類中的記錄在(年齡，性別,郵編)上具有相同的屬性 值，并且在敏感屬性疾病上具有 3個不同值。因而，表1-5中的數(shù)據(jù)能夠防止鏈接攻擊 所導致的敏感屬性隱私泄露。雖然l-多樣性模型可以提供比k-匿名模型更強的隱私保護，但是，l-多樣性模型依 然存在不足之處，l-多樣性模型同樣采用泛

10、化和隱匿技術對原始數(shù)據(jù)進行匿名處理，因 而也存在信息損失的情況。表1-5 3-多樣性表年齡性別郵編疾病t140-41*7345*失眠t240-41*7345*心臟病t740-41*7345*禽流感t443-44*73455*心臟病t543-44*73455*失眠t943-44*73455*禽流感t341-45男73453*失眠t641-45男73453*心臟病t841-45男73453*禽流感1.2.1.3 anatomy 匿名模型文獻5提出了獨特的匿名方法anatomy,該方法首先將數(shù)據(jù)集按l-多樣性匿名模型 劃分，將劃分結果分成準標識符屬性表和敏感屬性表發(fā)布，兩張數(shù)據(jù)表之間通過group-

11、id關聯(lián)。anatomy匿名模型對等價類的準標識符屬性不作泛化和隱匿處理，直接將準標識符屬性數(shù)據(jù)發(fā)布，因而保留了大量原始數(shù)據(jù)的信息，大大提高了匿名數(shù)據(jù)的可 用性。同時，anatomy將數(shù)據(jù)分成兩張表發(fā)布，使得攻擊者無法將個體的準標識符屬性 和敏感屬性一一對應起來，提高了數(shù)據(jù)的安全性。由于anatomy匿名模型是在l-多樣性 模型的基礎上提出的，l-多樣性模型上存在的一些不足，在 anatomy匿名模型中也依然 存在。例如，表1-6是表1-1的一個滿足anatomy模型的匿名化結果，假設攻擊者知道某 個個體在group-id為1的等價類中。雖然攻擊者可以從準標識符屬性表獲知該個體的 年齡，性別，

12、郵編具體值，但他無法從敏感屬性表中準確獲得敏感屬性疾病的值，由于 group-id為1的疾病值的個數(shù)為3,因此攻擊者只能以1/3的幾率進行猜測。數(shù)據(jù)發(fā)布中，研究出提供更強保護能力的匿名模型依然是匿名保護中的主要工作， 因此，研究者們在k-匿名模型和l-多樣性模型的基礎上，又提出了一些新的匿名模型6-8。表 1-6 anatomy 表(a)準標識符屬性表group-id年齡性別郵編141女734562140女734552142男734561244男734555244男734555243女734553341男734532345男734532342男734533(b)敏感屬性表group-id疾病統(tǒng)

13、計1失眠11心臟病11禽流感12心臟病12失眠12禽流感13失眠13心臟病13禽流感11.2.2 匿名算法采用匿名技術由原始數(shù)據(jù)生成最優(yōu)匿名數(shù)據(jù)是一個np難問題9,10,因此，設計出高效的近似最優(yōu)算法是匿名保護中的重要工作。目前數(shù)據(jù)發(fā)布中采用的匿名技術主要 有：泛化和隱匿、聚類以及交換等技術。采用泛化和隱匿技術的匿名算法主要有：datafly算法11、mingen最小泛化算法網(wǎng)incognito算法12、ga (genetic algorithm)算法13、自底向上的泛化方法14、自頂向 下的泛化方法15、基于多維空間劃分的k-匿名方法16。國內(nèi)研究者也在文獻17-20中對 泛化和隱匿技術進行

14、了研究。泛化和隱匿技術將等價類中不同的準標識符屬性值泛化為 相同值以達到隱私保護的目的，造成了原始數(shù)據(jù)大量信息的損失。同時，基于泛化和隱 匿技術的匿名算法采用基于泛化層次結構的策略會引起不必要的信息損失。為了解決泛化和隱匿技術存在的不足，在數(shù)據(jù)的匿名化中引入聚類技術?；诰垲?的匿名化方法的主要思想是：首先將數(shù)據(jù)劃分為多個聚類，然后分別泛化每個聚類的準 標識符屬性以達到匿名化。文獻21提出模糊c-均值算法。文獻22提出基于k-modes 的算法。文獻23,24提出了基于k-means聚類算法的k-匿名方法。文獻25提出mdav k- 匿名算法。在 mdav算法的基礎上，文獻26提出了 v-md

15、av(variable-mdav)算法。 文獻27,28提出了帶權重的聚類方法。文獻29-32提出了基于聚類的k-匿名算法?；?于聚類的匿名算法不依賴于泛化層次結構，因此生成的匿名數(shù)據(jù)集具有更高可用性。數(shù)據(jù)交換是將數(shù)據(jù)集中某些屬性的值進行互換以防止隱私泄露33-35。文獻5提出了一種不基于泛化和隱匿技術的交換方法anatomy。文獻36-38也提出了基于交換的隱私數(shù)據(jù)發(fā)布算法。采用交換技術的匿名化算法通過交換增加了隱私數(shù)據(jù)的不確定性，從 而保護隱私數(shù)據(jù)的安全。并且交換技術直接發(fā)布準標識符屬性，保留了原始數(shù)據(jù)的大量 信息，極大地提高了匿名數(shù)據(jù)聚集查詢的準確性。1.2.3 匿名質(zhì)量評估匿名化原始數(shù)

16、據(jù)必然會引起信息損失,需要找到適合的評估機制來計算匿名后的信息損失以衡量匿名算法和匿名數(shù)據(jù)集的優(yōu)劣以下是匿名質(zhì)量評估中常用的信息損失評15估機制：定義1.1口1, 32等價類信息損失il(e)。假設等價類er1,rk由準標識符由數(shù)值屬性 (n1,nm)和分類屬性(c1,cn)構成，則等價類信息損失il(e)為：il(e) = e.( i =1,.,m(maxni-minni)nidistinctc十工ii_-)j.nc .-j公式中|e|是e中記錄個數(shù)，|ni|表示數(shù)值屬性的范圍，max和min分別是e中關于屬nin,性ni的最大最小值。|cj|表示分類屬性的不同屬性值個數(shù)，distinct表

17、示e中關于屬 ,disiincic,性cj的不同屬性值個數(shù)。定義1.232總體信息損失total_il。若e e1,em是匿名數(shù)據(jù)集t中所有等價類的 集合，那么t的總體信息損失為：total _ il(at) =e-il(e)?？傮w信息損失能夠反映匿名數(shù)據(jù)集相對原始數(shù)據(jù)集所產(chǎn)生的信息損失。止匕外，文獻 39中定義的可區(qū)分度量機制也可用來衡量匿名化質(zhì)量。定義 1.3網(wǎng) 可區(qū)分度量 dm (discernability metric)定義為 dm =工equivc1asses e e2，其中 |e|表示等價類e中的記錄個數(shù)，dm的值即為數(shù)據(jù)集中每一個等價類大小的平方的和。 可區(qū)分度量的意義在于：等

18、價類越大可區(qū)分度就越小，意味著一個記錄在大的等價類中 難以區(qū)分。定義1.45聚集查詢平均相對錯誤率。一個查詢的相對錯誤率為|act- est|/act, act 是對原始數(shù)據(jù)進行查詢獲得的實際結果，est是對匿名數(shù)據(jù)進行查詢獲得的推測結果。 每個查詢相對錯誤率的和的平均值即為聚集查詢平均相對錯誤率。1.3 論文的組織本文共分為四章，各章節(jié)內(nèi)容組織如下：第一章為引言，闡述研究數(shù)據(jù)發(fā)布中匿名化與敏感信息保護技術的意義，分析與評 述國內(nèi)外有關數(shù)據(jù)發(fā)布中匿名模型、匿名化與敏感信息保護技術方面的研究進展，給出 本文章節(jié)的組織結構。在第二章中，將著重討論基于聚類的敏感屬性l-多樣性匿名化算法的設計與實現(xiàn)。

19、首先，分析提出基于聚類的敏感屬性l-多樣性匿名化算法的動機，然后根據(jù)不同的聚類 種子記錄的選擇方式以及聚類前生成不同的聚類記錄候選集，提出了 2個滿足l-多樣性 模型的聚類算法，并通過對真實數(shù)據(jù)的實驗來評估這兩個算法的性能。第三章將討論基于l-多樣性的多敏感屬性匿名化技術問題。首先分析多個敏感屬性 的數(shù)據(jù)發(fā)布存在的隱私泄露風險，從而提出了一個滿足l-多樣性模型的多敏感屬性匿名化算法，并通過實驗驗證這個算法的有效性。第四章總結本文的工作成果，并對下一步的研究方向做出展望。第二章 基于聚類的匿名化算法2.1問題分析本章討論基于聚類的匿名化。以往的匿名化研究工作中，大多采用泛化和隱匿技術 實現(xiàn)數(shù)據(jù)的

20、匿名化。但是基于泛化和隱匿的匿名化算法由于受到泛化層次結構的限制， 導致一些不必要的信息損失。為了降低信息損失，一些學者將聚類方法應用到數(shù)據(jù)的匿名 化上。事實表明，基于聚類的方法能夠生成高質(zhì)量的匿名數(shù)據(jù)集。但是，基于聚類的匿 名化算法中，大多是基于k-匿名模型的，沒有考慮敏感屬性值的多樣性，存在著隱私泄 露的風險。因此，本章研究提出2個滿足l-多樣性模型的聚類算法 lca-fc( l-diversity clustering algorithm, select furthest seed and compare with centroid開口 lca-rc (l-diversity clust

21、ering algorithm, randomly select seed and compare with centroid)以避免敏感屬性的隱私泄露。 2.2基于聚類的敏感屬性1-多樣性匿名化算法.在基于聚類的匿名化算法中，聚類種子記錄的選擇和尋找信息損失最小記錄的方式 是非常重要的，將會影響到聚類的質(zhì)量。選擇聚類種子記錄時，可以隨機選擇數(shù)據(jù)集的 一個記錄，也可以選擇最遠的記錄作為聚類種子記錄。尋找信息損失最小記錄時，可以 計算整個聚類和每個候選記錄的信息損失來找到信息損失最小記錄，也可以計算聚類代表記錄和每個候選記錄的信息損失來找到信息損失最小記錄。而選擇聚類代表記錄時， 可以選擇聚類質(zhì)

22、心，也可以隨機選擇聚類的一個記錄作為聚類代表記錄。選擇不同的方 式，將會產(chǎn)生不同的聚類效果。大多數(shù)已有的基于聚類的k-匿名算法沒有滿足敏感屬性值l-多樣性的要求，存在著 隱私泄露的風險。因此，根據(jù)不同的聚類種子記錄的選擇方式以及聚類時生成不同的聚 類記錄候選集，本文提出了基于聚類的敏感屬性l-多樣性匿名化算法lca-fc和lca-rc 0它們的主要思想是：給定一個n個記錄的數(shù)據(jù)集t和l-多樣性參數(shù)l,首先計 算數(shù)據(jù)集t不同敏感屬性值個數(shù)，如果該值大于等于l,選擇一個記錄作為種子開始建立一個聚類，然后每次從聚類記錄候選集中選擇一個與聚類信息損失最小的記錄加入該 聚類，直到聚類中記錄個數(shù)為l時結束

23、，從而生成一個聚類(即等價類)。然后，滿足條 件的情況下選擇一個記錄作為新的種子記錄，重復相同的過程建立下一個聚類。最后， 對于剩余的記錄，分別計算它們與已經(jīng)生成的每個聚類之間的信息損失，然后加入到信 息損失最小的聚類中。lca-fc算法在數(shù)據(jù)集中選擇距離上次種子記錄最遠的記錄作為聚類種子記錄， lca-rc算法則在數(shù)據(jù)集中隨機選擇一個記錄作為聚類種子記錄，兩者均通過計算聚類質(zhì)心和聚類記錄候選集的每個記錄的信息損失來找到信息損失最小記錄，但聚類記錄候選集不同。本文算法在計算聚類質(zhì)心時，各個數(shù)值型屬性值采用聚類的各個數(shù)值型屬性 平均值，而各個分類屬性值則采用聚類的各個分類屬性中出現(xiàn)頻率最高的值。

24、算法處理 的數(shù)據(jù)包括數(shù)值屬性和分類屬性，信息損失機制必須既適用于數(shù)值型數(shù)據(jù)又適用于分類 型數(shù)據(jù)的信息損失計算。因此聚類所產(chǎn)生的信息損失采用1.2.3小節(jié)定義的信息損失機制來衡量。下面分別描述基于聚類的敏感屬性l-多樣性匿名化算法lca-fc和lca-rc : 算法2.1 lca-fc 算法 輸入：原始數(shù)據(jù)集 t和1-多樣性模型參數(shù)l;輸出：符合1-多樣性模型要求的匿名數(shù)據(jù)集tablebeginstepl:計算數(shù)據(jù)集t不同敏感屬性值個數(shù)；if （t中不同敏感屬性值個數(shù) =l） do 聚類c=r;聚類質(zhì)心 centroid = r;數(shù)據(jù)集t=t.r;聚類記錄候選集1丁=從數(shù)據(jù)集t中選擇與種子記錄敏

25、感屬性不相同的記錄； while （|c| l） domin = 00;for （i=1,，候選集lt記錄個數(shù)）do record=lt 中第i個記錄；if （record的敏感屬性值與聚類 c中記錄的敏感屬性值相同 ）continue; il= record到聚類 c質(zhì)心的信息損失 il record u centroid;if（ il =2*l-1） then continue;il=記錄r與聚類c質(zhì)心信息損失il r u centroid;if （il min） thenmin=il;minc=i;end if;end for;信息損失最小聚類minc = ru信息損失最小聚類minc;

26、end whilestep4:將匿名數(shù)據(jù)集table中的每個聚類的所有記錄在準標識符上的屬性值用該聚類代表記錄準標識符上的屬性值代替，完成匿名化，得到最后輸出的匿名數(shù)據(jù)集table。end算法2.2 lca-rc算法輸入：原始數(shù)據(jù)集 t和1-多樣性模型參數(shù)l;輸出：符合1-多樣性模型要求的匿名數(shù)據(jù)集tablebeginstepl:計算數(shù)據(jù)集t不同敏感屬性值個數(shù)，種子記錄候選集ls=從數(shù)據(jù)集t中選擇敏感屬性值相同且數(shù)目最多的所有記錄，聚類記錄候選集lt=數(shù)據(jù)集t-種子記錄候選集 ls-敏感屬性值相同且數(shù)目最少的所有記錄；if （ t中不同敏感屬性值個數(shù) =l） do二種子記錄候選集 ls中隨機選

27、取一個記錄；聚類c= r;聚類質(zhì)心 centroid = r;數(shù)據(jù)集t=t- r;while （|c|l） domin = 00;for （i=1,，聚類記錄候選集 lt記錄個數(shù)）dorecord=lt 中第i個記錄；if （record的敏感屬性值與聚類c中記錄的敏感屬性值相同）continue;il= record與聚類 c質(zhì)心的信息損失 il record u centroid;if （il =2* l-1） then continue;il=記錄r與聚類c質(zhì)心信息損失il r u centroid;if （il l,每次總是從最大桶 bk1中取出一個記錄，然后按從大到小的順序在其余桶

28、中選擇尋找1-1個記錄生成記錄數(shù)為l的等價類，要求等價類中每個敏感屬性的l個屬性 值都不同。然后重新對桶排序，重復相同的過程建立下一個等價類。最后，將剩余記錄 分到生成的等價類中，控制加入剩余記錄的等價類的大小介于1和21-1之間，并且也要求加入剩余記錄的類每個敏感屬性滿足最頻繁敏感值出現(xiàn)的次數(shù)與該類記錄數(shù)之比小 于等于1/1。采用文獻5中的方法，將結果分成多張數(shù)據(jù)表發(fā)布，其中一張表包含等價 類id和各準標識符屬性等字段，其余每張表包含等價類id、一個敏感屬性、敏感屬性值計數(shù)等字段，準標識符屬性表與各敏感屬性表之間通過等價類id關聯(lián)。算法中信息損失采用1.2.3小節(jié)定義的信息損失機制來衡量?；?/p>

29、于1-多樣性模型的多敏感屬性匿名化算法msal形式描述如下：算法3.1基于1-多樣性模型的多敏感屬性匿名化算法msal輸入：原始數(shù)據(jù)集 敏感屬性個數(shù)n和1-多樣性模型參數(shù)1; 輸出：符合多個敏感屬性 1-多樣性要求的匿名數(shù)據(jù)集 tab1ebeginstep1:確定數(shù)據(jù)集中n個敏感屬性及n個敏感屬性的主次。 分別計算各敏感屬性的不同敏感屬性值個數(shù)；if （t中各敏感屬性的不同敏感屬性值個數(shù)=1&各敏感屬性的不同敏感屬性值個數(shù)=1） do二從最大桶maxbk中隨機選擇一個記錄； 等價類c=r;最大桶maxbk=最大桶maxbk -r;for (i=1; ibknum;i+) domax=0;for(j=0;j第i個桶的記錄數(shù)目；j+)dorec=第i個桶中第j個記錄；for(k=0; k等價類 c的記錄數(shù)；k+)do如果rec記錄與等價類c所有記錄在n-1個敏感屬性的屬性值完全不相同，則record= rec, record為符合條件的記錄，退出循環(huán)變量為k,j的循環(huán)；否則回到j循環(huán)，繼續(xù)從第i個桶中尋找符合條件的記錄；end forend for;如果不