一種抵制對等性攻擊的（p，θ）k-匿名模型*

符精晶 許曉東

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

1 引言

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

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

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

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

2 p-sensitive k-匿名模型

2.1 相關概念

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

1）顯標識符（Identifier Attribute，ID）：能夠唯一確定個體身份的屬性，如姓名、身份證號等［9］；

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

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

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

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

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

表2為表1進行k=2的匿名化后的數(shù)據(jù)表，經準標識符泛化后形成了3個等價類，每個等價類中除了敏感屬性以外的所有屬性取值均相等。

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

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

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

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

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

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

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

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

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

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

3 改進的（p，θ）k-匿名模型

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

3.1 相關定義

1）敏感屬性值的等級分類

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

表4 敏感屬性等級值

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

圖1 疾病敏感屬性層次樹

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

2）敏感屬性權重因子θ

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

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

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

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

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

3）互信息量

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

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

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

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

3.2 算法過程描述

1）元組距離計算公式

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

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

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

（2）分類型屬性的距離

給定數(shù)據(jù)集T，對于分類型屬性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）敏感屬性等級差

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

3）屬性泛化樹

定義11（屬性泛化樹）對于準標識符QI，其值域為Z（Z為有限集）［17］，則其屬性泛化樹為映射函數(shù)f：TQI→Z。樹中葉子結點為該屬性在數(shù)據(jù)表中各個具體的取值，中間結點為各個層次的泛化值，根結點為最終泛化值。圖2是“年齡”屬性的泛化樹。

圖2“年齡”屬性泛化樹

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

輸入：原始數(shù)據(jù)表T，準標識符個數(shù)n，匿名參數(shù)k、p、θ

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

步驟：

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

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

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

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

（5）對初步匿名表T'，計算其所有準標識符Q1、Q2、…Qn與敏感屬性SA的互信息量（用式（1）計算）；

（7）準標識符泛化完成后，生成最終匿名表T''。

3.3 算法度量指標

1）信息損失量［18］

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

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

（2）分類型屬性

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

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

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

其中，ARRE表示E中敏感值的平均識別率，其計算公式為

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

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

4 實驗結果和分析

4.1 實驗環(huán)境

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

4.2 信息損失量比較

由圖3知，k值相同時，本文模型較p-sensitive k-匿名模型有更高的信息損失，是因為本文增加了關聯(lián)度計算來進一步泛化準標識符，但總體上兩者的信息損失量相差不多。

圖3 不同k值下信息損失量對比

4.3 敏感值識別率比較

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

圖4 不同k值下敏感值識別率對比

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

由圖5知，本文算法的執(zhí)行時間隨θ的增大而減小。因為頻率越大，對敏感屬性的約束越小，所需執(zhí)行時間會越少。

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

5 結語

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