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

符精晶 許曉東

（江蘇大學計算機科學與通信工程學院 鎮江 212013）

1 引言

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

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

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

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

2 p-sensitive k-匿名模型

2.1 相關概念

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

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

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

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

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

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

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

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

表1 原始數據表

表2 表1經過2-匿名處理后的數據表

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

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

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

表3 表2經過2-sensitive 2-匿名處理后的數據表

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

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

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

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

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

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

3.1 相關定義

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

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

表4 敏感屬性等級值

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

圖1 疾病敏感屬性層次樹

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

2）敏感屬性權重因子θ

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

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

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

表5 加入敏感屬性等級值的原始數據表

表6 表5經過（2，0.5）2-匿名處理后的數據表

3）互信息量

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

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

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

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

3.2 算法過程描述

1）元組距離計算公式

（1）數值型屬性的距離［16］

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

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

（2）分類型屬性的距離

給定數據集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（敏感屬性等級差）數據表中任意兩個元組Ai、Aj的敏感屬性等級差為D Lev=|Lev（Asi）-Lev（Asj）|，其中Lev（Asi）為數據表中第i個元組的敏感屬性值對應的等級。

3）屬性泛化樹

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

圖2“年齡”屬性泛化樹

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

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

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

步驟：

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

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

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

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

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

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

3.3 算法度量指標

1）信息損失量［18］

（1）數值型屬性

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

（2）分類型屬性

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

2）數據表敏感值的平均識別率［19］

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

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

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

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

4 實驗結果和分析

4.1 實驗環境

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

4.2 信息損失量比較

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

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

4.3 敏感值識別率比較

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

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

4.4 本文模型的執行時間與θ的關系

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

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

5 結語

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