符精晶 許曉東

（江蘇大學(xué)計(jì)算機(jī)科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）

1 引言

互聯(lián)網(wǎng)的發(fā)展勢(shì)如破竹，帶來了數(shù)據(jù)的海量增長，大數(shù)據(jù)時(shí)代已經(jīng)到來。政府、企業(yè)等機(jī)構(gòu)在信息化過程中累積了大量的個(gè)人數(shù)據(jù)，這些數(shù)據(jù)為大數(shù)據(jù)分析、價(jià)值挖掘及信息共享提供了十分有利的資源條件，成為了一種高價(jià)值的資產(chǎn)。但是這些數(shù)據(jù)資源往往涉及個(gè)人敏感信息，在對(duì)外進(jìn)行數(shù)據(jù)發(fā)布時(shí)，若不經(jīng)處理直接發(fā)布原始數(shù)據(jù)，極易造成隱私泄露。因此，信息安全領(lǐng)域當(dāng)前的一個(gè)研究熱門即是隱私數(shù)據(jù)脫敏技術(shù)，其關(guān)鍵問題在于如何均衡隱私數(shù)據(jù)安全性及數(shù)據(jù)可用性。

經(jīng)過國內(nèi)外學(xué)者的大量研究，目前大致形成了三類隱私保護(hù)技術(shù)［1］：數(shù)據(jù)加密，數(shù)據(jù)失真以及數(shù)據(jù)匿名化。其中，數(shù)據(jù)匿名化的通用性強(qiáng)，且能同時(shí)兼顧數(shù)據(jù)的可用性和隱私性，因此其在數(shù)據(jù)發(fā)布的隱私保護(hù)中應(yīng)用最為廣泛。

Sweeney［2］等在2002年就已經(jīng)提出了經(jīng)典的k-匿名模型，該模型將原始數(shù)據(jù)表進(jìn)行分類匿名化處理，使數(shù)據(jù)表中的每一條記錄至少有k-1條與其在準(zhǔn)標(biāo)識(shí)符上完全相同的記錄，有效地抵制了攻擊者的鏈接攻擊（linking attack）［2］。然而，k-匿名沒有考慮敏感屬性取值的多樣性，無法抵御同質(zhì)攻擊等。2006年，Machanavajjhal［3］等針對(duì)k-匿名的缺陷，提出了l-diversity模型，該模型保證數(shù)據(jù)表中每一個(gè)等價(jià)類的敏感屬性至少有l(wèi)個(gè)不同的取值，從而使得被發(fā)布的數(shù)據(jù)表具備抵御同質(zhì)攻擊的能力。同年，Traian TM，Bindu V［4］提出p-sensitive k-匿名模型，在k匿名的基礎(chǔ)上，要求每個(gè)等價(jià)類中不同的敏感屬性取值至少為p個(gè)，以此確保各等價(jià)類中敏感屬性的多樣化。2007年，Li［5］等提出了t-closeness模型，該模型指定每個(gè)等價(jià)類中敏感屬性值的分布與原始數(shù)據(jù)表中的分布情況要盡可能的接近。2012年，吳英杰［6］等基于k-匿名算法，利用取整劃分函數(shù)來劃分等價(jià)類，減小了等價(jià)類的最大規(guī)模，優(yōu)化了等價(jià)類平均規(guī)模的上界。2017年，王靜［7］等針對(duì)多敏感屬性，為用戶進(jìn)行個(gè)性化的敏感數(shù)據(jù)保護(hù)。

目前基于k匿名模型，研究者從匿名組劃分、個(gè)性化隱私保護(hù)、敏感屬性約束等多個(gè)角度進(jìn)行了優(yōu)化，并在不同的環(huán)境中取得了一定的效果［8］，但仍然存在以下問題：1）對(duì)敏感屬性的約束大多是通過約束其在等價(jià)類中的出現(xiàn)頻率及種類個(gè)數(shù)，沒有考慮到敏感屬性的等級(jí)分類及權(quán)重；2）對(duì)準(zhǔn)標(biāo)識(shí)符和敏感屬性之間可能存在的關(guān)聯(lián)關(guān)系沒有進(jìn)行深入研究。因此，在p-sensitive k-匿名模型的基礎(chǔ)上，本文加入了敏感屬性的等級(jí)分類，并引入互信息量的概念，提出針對(duì)對(duì)等性攻擊的（p，θ）k-匿名模型，以提高數(shù)據(jù)發(fā)布中隱私信息的安全性。

2 p-sensitive k-匿名模型

2.1 相關(guān)概念

給定一個(gè)數(shù)據(jù)表T（ID，QI，SA），ID、QI、SA為三類不同的屬性。

1）顯標(biāo)識(shí)符（Identifier Attribute，ID）：能夠唯一確定個(gè)體身份的屬性，如姓名、身份證號(hào)等［9］；

2）準(zhǔn)標(biāo)識(shí)符（Quasi Identifier Attribute，QI）：可以通過聯(lián)接外部表來推測(cè)出個(gè)體身份的屬性，如年齡、性別等；

3）敏感屬性（Sensitive Attribute，SA）：涉及到個(gè)體不想公開的個(gè)人隱私數(shù)據(jù)的屬性，如薪資、疾病等。

定義1（等價(jià)類）對(duì)于數(shù)據(jù)表T（ID，QI，SA），等價(jià)類是數(shù)據(jù)表T中具有相同QI取值的所有記錄的集合，這些記錄在QI上的屬性值是不可區(qū)分的［10～12］。

定義2（k-匿名）給定數(shù)據(jù)表T，若表T中每一條記錄至少有k-1條與其在QI上完全相同的記錄，則稱該數(shù)據(jù)表滿足k-匿名。

表1是待發(fā)布的原始數(shù)據(jù)，其中姓名為顯標(biāo)識(shí)符，｛年齡，性別，郵編｝為準(zhǔn)標(biāo)識(shí)符，疾病為敏感屬性。

表2為表1進(jìn)行k=2的匿名化后的數(shù)據(jù)表，經(jīng)準(zhǔn)標(biāo)識(shí)符泛化后形成了3個(gè)等價(jià)類，每個(gè)等價(jià)類中除了敏感屬性以外的所有屬性取值均相等。

表1 原始數(shù)據(jù)表

表2 表1經(jīng)過2-匿名處理后的數(shù)據(jù)表

若攻擊者已知奧斯汀的年齡及郵編，即可推斷出他在等價(jià)類1中，又因?yàn)榈葍r(jià)類1中的兩個(gè)元組具有相同的敏感屬性取值，進(jìn)而可以確定奧斯汀患有胃炎，即遭受了同質(zhì)攻擊。為解決此類問題，可使用p-sensitive k-匿名模型。

定義3（p-sensitive k-匿名）［13］若數(shù)據(jù)表T滿足k-匿名，且T中每個(gè)等價(jià)類不相同的敏感屬性值至少有p（p≤k）個(gè)，則稱T滿足p-sensitive k-匿名。

表3為表2進(jìn)行p=2、k=2匿名化后的數(shù)據(jù)表，對(duì)元組進(jìn)行了重新分組和準(zhǔn)標(biāo)識(shí)符的重新泛化，解決了同質(zhì)攻擊的問題。

表3 表2經(jīng)過2-sensitive 2-匿名處理后的數(shù)據(jù)表

2.2 p-sensitive k-匿名模型的缺陷

雖然p-sensitive k-匿名增加了各等價(jià)類中敏感屬性值的多樣性［14］，卻仍易遭受對(duì)等性攻擊。

定義4（對(duì)等性攻擊）［15］經(jīng)k-匿名化處理后的數(shù)據(jù)集T中，某個(gè)等價(jià)類里所有記錄的敏感屬性取值的重要程度相同的情況下所遭受的攻擊行為。

在表3中，若攻擊者已知杰克在等價(jià)類3中，則無論是胃癌還是心絞痛，攻擊者都能推斷出杰克得了比較嚴(yán)重的疾病，即對(duì)等性攻擊。

3 改進(jìn)的（p，θ）k-匿名模型

針對(duì)p-sensitive k-匿名模型易遭受對(duì)等性攻擊的問題，本文事先對(duì)敏感屬性SA進(jìn)行等級(jí)劃分，并引入敏感屬性權(quán)重因子θ對(duì)其進(jìn)行約束，從而減少同種等級(jí)SA的取值在同一等價(jià)類中出現(xiàn)的頻率。此外，本文引入互信息量公式來定量計(jì)算準(zhǔn)標(biāo)識(shí)符與敏感屬性間的關(guān)聯(lián)度，并將其作為對(duì)準(zhǔn)標(biāo)識(shí)符進(jìn)一步泛化的依據(jù)，從而為數(shù)據(jù)發(fā)布的安全性再添一道屏障。

3.1 相關(guān)定義

1）敏感屬性值的等級(jí)分類

將敏感屬性SA按照取值的敏感程度的不同進(jìn)行等級(jí)分類，用D（Lev）表示敏感屬性等級(jí)值的值域。如表4，將八種疾病進(jìn)行等級(jí)分類后，Lev表示敏感等級(jí)，其值越大則敏感級(jí)別越高。此時(shí)，“疾病”屬性所對(duì)應(yīng)的D（Lev）=｛1，2，3，4｝。

表4 敏感屬性等級(jí)值

定義5（敏感屬性層次樹）樹ST是一棵高度為h的樹，從上到下的層次依次為1，2，…，h。葉子結(jié)點(diǎn)代表具體的敏感屬性值，其上的每一層父結(jié)點(diǎn)都是對(duì)子結(jié)點(diǎn)的泛化。同時(shí)規(guī)定第h層的所有葉子結(jié)點(diǎn)按照敏感等級(jí)由小到大排列。如圖1，即為疾病的敏感屬性層次樹。最底層葉子結(jié)點(diǎn)為具體的疾病名稱，往上則是對(duì)不同種類疾病的泛化。

圖1 疾病敏感屬性層次樹

定義6（敏感屬性真子樹）［15］對(duì)于高度為h的敏感屬性層次樹ST，第i層結(jié)點(diǎn)的子結(jié)點(diǎn)本身加上該子結(jié)點(diǎn)的所有子結(jié)點(diǎn)所組成的樹，稱為第i層結(jié)點(diǎn)的真子樹。

2）敏感屬性權(quán)重因子θ

定義7（θ分布約束）給定數(shù)據(jù)集T、敏感屬性SA，若在T中的所有等價(jià)類R中，敏感屬性等級(jí)為Lev的記錄頻率不超過θ，則稱T滿足θ分布約束。θ為敏感屬性權(quán)重因子，由數(shù)據(jù)發(fā)布者指定。

定義8（（p，θ）k-匿名）給定數(shù)據(jù)集T和等價(jià)類R，若T滿足k-匿名，且每個(gè)R中至少存在p（p≤k）個(gè)不同的敏感屬性值，同時(shí)每個(gè)R中所有的敏感屬性取值符合θ分布約束，則稱T滿足（p，θ）k-匿名。

表5為加入了敏感屬性等級(jí)值的原始數(shù)據(jù)表。表6是表5經(jīng)過（p，θ）k-匿名（p=2、θ=0.5、k=2）處理后的數(shù)據(jù)表，表中同一種等級(jí)的敏感屬性值在同一等價(jià)類中出現(xiàn)的頻率不超過50%，很好地抵御了對(duì)等性攻擊。

表5 加入敏感屬性等級(jí)值的原始數(shù)據(jù)表

表6 表5經(jīng)過（2，0.5）2-匿名處理后的數(shù)據(jù)表

3）互信息量

θ分布約束只對(duì)敏感屬性的分組排布進(jìn)行了控制，忽略了準(zhǔn)標(biāo)識(shí)符與敏感屬性之間可能存在的關(guān)聯(lián)關(guān)系，因此本文利用互信息量以定量關(guān)系對(duì)準(zhǔn)標(biāo)識(shí)符進(jìn)一步泛化。

定義9（互信息量）表示兩個(gè)事件之間的相關(guān)性。本文中是指對(duì)于數(shù)據(jù)集T中的兩個(gè)屬性X和Y來說，當(dāng)已知其中一個(gè)屬性的取值集合，另一個(gè)屬性不確定性減小的程度。屬性X與Y的關(guān)聯(lián)度（互信息量）計(jì)算公式為

其中H（X）為X的信息熵，其計(jì)算公式為

H（X|Y）為條件熵，即已知屬性Y的情況下屬性X的不確定性，其計(jì)算公式為

3.2 算法過程描述

1）元組距離計(jì)算公式

（1）數(shù)值型屬性的距離［16］

給定數(shù)據(jù)集T，對(duì)于數(shù)值型屬性A，元組ti、tj在A上的取值分別為ti（A）、tj（A），則ti、tj在屬性A上的距離公式為

其中，MAXA代表T中數(shù)值型屬性A所取得的最大值，MINA代表A所取得的最小值。

（2）分類型屬性的距離

給定數(shù)據(jù)集T，對(duì)于分類型屬性C，元組ti、tj在C上的值分別為ti（C）、tj（C），Tc是分類型屬性C的屬性泛化樹，H（Tc）表示泛化樹的高度，∧(ti(C)，tj(C))表示ti（C）和tj（C）以泛化樹中最小公共祖先為根的子樹［18］，則元組ti、tj在分類型屬性C上的距離公式為

2）敏感屬性等級(jí)差

定義10（敏感屬性等級(jí)差）數(shù)據(jù)表中任意兩個(gè)元組Ai、Aj的敏感屬性等級(jí)差為D Lev=|Lev（Asi）-Lev（Asj）|，其中Lev（Asi）為數(shù)據(jù)表中第i個(gè)元組的敏感屬性值對(duì)應(yīng)的等級(jí)。

3）屬性泛化樹

定義11（屬性泛化樹）對(duì)于準(zhǔn)標(biāo)識(shí)符QI，其值域?yàn)閆（Z為有限集）［17］，則其屬性泛化樹為映射函數(shù)f：TQI→Z。樹中葉子結(jié)點(diǎn)為該屬性在數(shù)據(jù)表中各個(gè)具體的取值，中間結(jié)點(diǎn)為各個(gè)層次的泛化值，根結(jié)點(diǎn)為最終泛化值。圖2是“年齡”屬性的泛化樹。

圖2“年齡”屬性泛化樹

4）（p，θ）k-匿名算法的過程描述

輸入：原始數(shù)據(jù)表T，準(zhǔn)標(biāo)識(shí)符個(gè)數(shù)n，匿名參數(shù)k、p、θ

輸出：滿足（p，θ）k-匿名的最終匿名表T"

步驟：

（1）建立敏感屬性層次樹，將各敏感屬性所對(duì)應(yīng)的元組存儲(chǔ)至相應(yīng)的真子樹中，并將第一層的m棵真子樹按包含敏感屬性值的元組個(gè)數(shù)降序排列，假設(shè)真子樹集合按降序排列為LT=｛LT1，LT2，…LTm｝，初始化等價(jià)類集合R=｛｝；

（2）選取LT第一個(gè)元素的第一條元組A作為初始等價(jià)類的質(zhì)心，按元組個(gè)數(shù)由多到少從其余m-1棵真子樹中，選擇與質(zhì)心按距離升序、D Lev降序（距離為主關(guān)鍵字）排序后的前k-1條元組，與質(zhì)心構(gòu)成初始等價(jià)類r=｛A，A1，A2，…，Ak-1｝（元組距離用式（4）或式（5）計(jì)算，敏感屬性等級(jí)差用定義10中的公式計(jì)算）；

（3）計(jì)算初始等價(jià)類r中各敏感屬性等級(jí)的頻率，若滿足θ約束，則最終劃分為一個(gè)等價(jià)類；反之，繼續(xù)選擇記錄。將劃分好的等價(jià)類并入R中，并將其對(duì)應(yīng)元組在原始數(shù)據(jù)表中刪除；

（4）重復(fù)執(zhí)行上述（2）、（3）兩個(gè)步驟，當(dāng)整個(gè)數(shù)據(jù)表T已不能形成新的滿足（p，θ）k-匿名約束的等價(jià)類時(shí)停止執(zhí)行，并將剩余元組插入到與其距離最近的等價(jià)類中，將等價(jià)類集合R轉(zhuǎn)換成初步匿名數(shù)據(jù)表T'；

（5）對(duì)初步匿名表T'，計(jì)算其所有準(zhǔn)標(biāo)識(shí)符Q1、Q2、…Qn與敏感屬性SA的互信息量（用式（1）計(jì)算）；

（7）準(zhǔn)標(biāo)識(shí)符泛化完成后，生成最終匿名表T''。

3.3 算法度量指標(biāo)

1）信息損失量［18］

（1）數(shù)值型屬性

對(duì)某一數(shù)值泛化后的區(qū)間i，標(biāo)記其左端點(diǎn)為Li，右端點(diǎn)為Ri。標(biāo)記該數(shù)值屬性整個(gè)值域的最小值為L，最大值為R，則該數(shù)值屬性泛化的信息損失量為

（2）分類型屬性

對(duì)于屬性泛化樹TQI，其所有葉子結(jié)點(diǎn)的個(gè)數(shù)記為M，對(duì)于TQI中的任一結(jié)點(diǎn)P，其所有子樹的個(gè)數(shù)記為Mp，則該分類型屬性泛化的信息損失量為

2）數(shù)據(jù)表敏感值的平均識(shí)別率［19］

給定一個(gè)數(shù)據(jù)集T和等價(jià)類E，T中E的個(gè)數(shù)為n，s是E中某條記錄t的敏感屬性值，則T中敏感值的平均識(shí)別率ARRT的計(jì)算公式為

其中，ARRE表示E中敏感值的平均識(shí)別率，其計(jì)算公式為

RRt（s，E）表示一條記錄的敏感屬性值識(shí)別率，其計(jì)算公式為

|（s，E）|是等價(jià)類E中敏感屬性值s的個(gè)數(shù)，|E|是等價(jià)類的大小。

4 實(shí)驗(yàn)結(jié)果和分析

4.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)環(huán)境為Intel Core i5 8265U 1.8GHz CPU，8GB RAM，Windows 10專業(yè)版64位操作系統(tǒng)；實(shí)驗(yàn)所用語言為Java，并用Matlab仿真實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)集：選用UCI的Adult數(shù)據(jù)集，共有48842條記錄，包含14個(gè)屬性［20］，本文將｛age，gender，education，race｝作為準(zhǔn)標(biāo)識(shí)符屬性，并增加一列“disease”作為敏感屬性，將表4中幾種不同等級(jí)的“疾病”屬性取值隨機(jī)添加至數(shù)據(jù)表的每個(gè)元組中。此外增加一列“Lev”屬性，記錄敏感屬性值的等級(jí)，“disease”與“Lev”的對(duì)應(yīng)關(guān)系與表4保持一致。實(shí)驗(yàn)重復(fù)進(jìn)行5次，最終取平均值作為分析對(duì)比的數(shù)據(jù)。

4.2 信息損失量比較

由圖3知，k值相同時(shí)，本文模型較p-sensitive k-匿名模型有更高的信息損失，是因?yàn)楸疚脑黾恿岁P(guān)聯(lián)度計(jì)算來進(jìn)一步泛化準(zhǔn)標(biāo)識(shí)符，但總體上兩者的信息損失量相差不多。

圖3 不同k值下信息損失量對(duì)比

4.3 敏感值識(shí)別率比較

由圖4知，k值相同時(shí)，本文模型較p-sensitive k-匿名模型有更低的敏感值識(shí)別率，即數(shù)據(jù)發(fā)布的安全性更高。這是由于本文模型增加了對(duì)敏感屬性值的頻率約束，同時(shí)降低了準(zhǔn)標(biāo)識(shí)符與敏感屬性間的關(guān)聯(lián)度。

圖4 不同k值下敏感值識(shí)別率對(duì)比

4.4 本文模型的執(zhí)行時(shí)間與θ的關(guān)系

由圖5知，本文算法的執(zhí)行時(shí)間隨θ的增大而減小。因?yàn)轭l率越大，對(duì)敏感屬性的約束越小，所需執(zhí)行時(shí)間會(huì)越少。

圖5 本文模型的執(zhí)行時(shí)間隨θ的變化情況

5 結(jié)語

本文提出了優(yōu)化的（p，θ）k-匿名模型，對(duì)敏感屬性進(jìn)行等級(jí)分類并約束其在等價(jià)類中出現(xiàn)的頻率，利用互信息量為準(zhǔn)標(biāo)識(shí)符的泛化提供依據(jù)，從而阻止對(duì)等性攻擊，有效地減少了個(gè)人隱私泄露的概率。實(shí)驗(yàn)結(jié)果表明，本文的算法雖然損失了部分?jǐn)?shù)據(jù)的精度，但獲得了更好的數(shù)據(jù)保密效果，且信息損失仍在可接受范圍內(nèi)。由于本文只考慮了單個(gè)敏感屬性的情況，因此后續(xù)工作將主要對(duì)如何抵制多敏感屬性的對(duì)等性攻擊進(jìn)行研究。