抵制敏感屬性相似攻擊的個性化（α k m d）-匿名模型

鄧博允

摘要：目前，在數據發布領域很少有隱私保護模型滿足對敏感屬性的個性化保護多數隱私保護，同時又能防御相似攻擊。該文針對個性化（α，k）-匿名模型不能抵制敏感屬性相似攻擊的問題，提出了一種可抵制敏感屬性相似攻擊的個性化（α，k，m，d）-匿名模型。該模型為敏感屬性值建立語義層次樹，對敏感屬性之間的相異度進行度量，使每個等價類滿足個性化（α，k）-匿名模型，同時為了防止等價類遭受相似攻擊，要求等價類中滿足相異性度量的敏感屬性個數大于m。實驗數據表明，該文提出的個性化（α，k，m，d）-匿名模型相對于（α，k）-匿名模型在差不多的時間花銷，能防御相似攻擊，更具安全性。

關鍵詞：隱私保護;個性化;相似性攻擊;（α，k）-匿名模型;（α，k，m，d）-匿名模型

中圖分類號：TP393? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2020）16-0038-04

Abstract： At present， there are very few privacy protection models in the field of data publishing that can meet most privacy protections for personalized protection of sensitive attributes， and at the same time can prevent similar attacks. Aiming at the problem that the personalized （α， k） -anonymous model cannot resist similar attacks on sensitive attributes， this paper proposes a personalized （α， k， m， d） -anonymous model that can resist similar attacks on sensitive attributes. This model establishes a semantic hierarchy tree for sensitive attribute values， measures the dissimilarity between sensitive attributes， and enables each equivalent class to meet a personalized （α， k） -anonymous model， while protecting the equivalent classes from similar attacks ， Requires that the number of sensitive attributes in the equivalence class that satisfy the dissimilarity measure is greater than m. The experimental data show that the personalized （α， k， m， d） -anonymous model proposed in this paper costs approximately the same time as the （α， k） -anonymous model and can defend similar attacks and is more secure.

Key words： privacy protection; personalization; similarity attack; （α， k） -anonymous model; （α， k， m， d） -anonymous model

1 引言

公共部門、企業部門和個人等無數部門不斷提供數字信息，促進知識發現和基于信息的決策制造。發布數據進行分析，同時維護個人隱私，已成為當今處理數據的一項艱巨任務。主要目標是將隱私披露風險降低在可接受水平，同時最大限度地提高發布數據的可用性。匿名化的傳統方法是刪除憑證字段，例如：姓名和身份證號碼。通用的匿名方法是泛化，即使屬性在語義上一致。這樣，更多的記錄會具有相同的準表識符集，在某種程度上保護了某個個體不會被發現。

在文獻[1]中講到了k-匿名模型。Sweeney明確指出在匿名表中，所有記錄都必須最少有k個同樣的準標識符集。基于k-匿名還有許多成功的應用[2-4]。但是，盡管k匿名保護數據免受身份泄露，但不足以防止屬性泄露。為了解決k匿名性的這種局限性，Machanavajjhala等人[5]引入了一個新的隱私概念，稱為l-多樣性，它要求每個等價類中至少要有l個不同的敏感屬性值。Li等人[6]提出了t -closeness概念，這是一種全新的隱私概念，對于此種概念，在任一等價類中，它的敏感屬性與整體屬性分布非常接近，也就是每兩個分布閾值相距小于t）。在文獻[7]中講到了（α，k）-匿名模 型，對于該模型而言，在等價類中，所有的敏感屬性值存在頻率都必須小于α; 在文獻[8]中講到了p-Sensitive k-匿名模型，對于該模型，首先要保證為k- 匿名，并且在等價類中，最少有 p 個不一樣的敏感屬性值。通過此種k-匿名模型，可以防止受到背景知識攻擊以及一致性攻擊。

但是在上述研究過程中，沒有考慮不同個體對同一敏感屬性進行不同的隱私保護，也就是個性化的隱私保護。在文獻[9]中講到了（α，k）-匿名模型，對于該模型，需要給不同的敏感值定義不同的敏感約束，從而實現個性化保護;文獻[10]對p-sensitive k匿名模型做出了改進，在進行敏感屬性分級時，參照的是用戶自身不同的敏感程度，從而實現個性化保護。以上模型雖能在有效防御一致性攻擊和背景知識攻擊的情況下實現個性化保護，但不足以防止相似性攻擊。

對于（α，k）-匿名模型而言，它無法抵制相似性攻擊，本文利用這一特點，在保證實現個性化保護的前提下，構建出了（α，k，m，d）-匿名模型，它能夠抵制相似性攻擊。它通過限制敏感屬性值在等價類中出現的頻率以及基于敏感屬性的語義分層樹并定義了敏感屬性相異性的度量方法控制語義相近的敏感屬性個數來實現個性化保護和防止相似性攻擊。

2 基本概念和相關技術

2.1 基本概念

將原始數據表1屬性分為三類：

（1）標識符：即唯一能夠反映個體屬性的標志，比如：身份證、姓名等。在進行數據處理工作時，一般先刪除掉這些屬性。

（2）準標識符：無法直接分辨出個體，但是能夠利用外部表鏈接識別個體的屬性。比如說：性別、生日等。

（3）敏感屬性：人們極力保護的個人隱私信息的屬性，如：疾病、收入等。

2.2 抵制敏感屬性相似攻擊的個性化（α，k，m，d）-匿名模型

定義6：所謂敏感屬性語義層次樹，指的是利用h高的樹來反映不同敏感屬性之間的語義關系，其中，1，2，...，h-1，h依次代表的是根節點到葉節點。根節點屬于全集泛化，父節點屬于子節點的泛化，此外，子節點屬于父節點中的子類，葉子節點代表一定的屬性值。

3 抵制敏感屬性相似攻擊的個性化（α，k，m，d）-匿名算法

3.1 α-約束

對于敏感值的個性化α-約束而言，需要按照以下兩個原則來實施：（1）如果屬性值具有較低的敏感性，就把α數值設定得大一些，如果屬性值的敏感程度較高，就把α數值設定得小一點;（2）對于任一敏感值的頻率約束α，都必須大于原始數據對應的頻率。

3.2 距離度量

定義9（加權層次距離）[11]首先確定一棵泛化樹T，h代表的是樹的高度，1，2，...，h-1，h，依次代表根節點到葉子節點的層次。其中wj，j-1為節點vj與vj-1之間的權重（2≤j≤h），可用公式（1）定義一個屬性從p層泛化到q層（1≤q

3.3 算法描述

個性化（α，k，m，d）-匿名算法思想步驟：（1）基于敏感性度量對各個敏感屬性值個性化分配頻率約束值α，同時對敏感屬性值進行語義分析，生成語義類hash桶，將屬于同一類別的敏感屬性劃分在一個桶里，然后對hash桶按照元組個數進行降序排列;（2）從記錄數最大的hash桶中任選一個記錄作為等價類的初始質心，并根據距離初始質心最近的要求依次選擇k條記錄，每次選擇元組構成新的等價類都要計算等價類中的α約束值，如果滿足就加入等價類，若不滿足，則重新選擇新元組。（3）對初始等價類進行d-相異判斷：若等價類滿足d-相異的元組個數不小于m個，則構建滿足要求的等價類成功。相反，就需要在等價類中加入新的元組;（4）不斷重復（2）、（3）步驟，直到最終不符合個性化（α，k，m，d）-匿名要求;（5）針對符合個性化（α，k，m，d）-匿名約束，實施泛化處理，并且隱藏不符合要求的元組，最終得到一張匿名表。

算法第（1）步是對頻率約束值α進行分配，用O（n）表示時間復雜度，然后對時間復雜度進行降序，用O（n?log n）表示;在步驟（2）中，符合α約束值的是k/n×O（k）=O（n），O（（k-1）×k/2）表示的是d-相異的度量間復雜度;在循環過程中，O（n2）代表的是時間復雜度;在步驟（5）中，O（n）表示的是泛化處理時間復雜度，此外，O（m）表示的是其他元組的時間復雜度，m代表的是其他元組的個數。最終時間開銷為：O（n）+O（n?log n）+O（n）+O（（k-1）×k/2）+O（n2）+O（n）+O（m）=O（n2）。

4 實驗與結果分析

4.1 實驗環境

實驗環境：操作系統為 Windows 操作系統，具體型號為Intel Core i5-7500 CPU， 3.40GHz ，8.0GB RAM 。在實驗過程中，應用的是人口普查adult數據集，存儲于UCI機器學習數據庫中。實驗中我們采用了其中的7個屬性，其中準表識符6個，敏感屬性一個：occupation。表4為根據敏感屬性值的敏感程度個性化設置的頻率約束α的參數表。

4.2 執行效率對比

當|QI|=6，d=1時，對比分析k值的個性化（α，k）-匿名模型、個性化（α，k，m，d）-匿名模型，具體情況如圖2所示。隨著執行時間的不斷增加，算法的k值也會不斷增加，從而使聚類次數越來越多。為使模型能夠防御相似攻擊，尋找滿足d-相異條件的元組，所以個性化（α，k，m，d）-匿名模型得執行時間相對較長。因此（α，k，m，d）-匿名模型也更具安全性，所以花費多點的執行時間也可接受。

4.3 數據信息保護程度分析

圖2為|QI|=6，d=1時兩種算法所遭受攻擊的記錄個數對比。由圖可知，本文提出的算法所遭受的攻擊數更少，更具有安全性。新算法不僅對單個敏感值使用了頻率約束來防御背景知識攻擊和一致性攻擊，同時運用d-相異條件，針對敏感屬性值的語義分析，有效地防御了數據的相似性攻擊。由圖可見，隨著k值的增大，數據被攻擊的個數在減少，受保護程度增加。

5 結束語

敏感屬性值需要進行個性化保護，而傳統模型并不能防止相似攻擊，為此本文構建了一個個性化（α，k，m，d）-匿名模型，它能夠抵制相似攻擊，主要原理是等價類中存在不同的個性化約束敏感值，從而進行個性化保護，此外，還能夠根據不同的敏感屬性語義層次樹，來調控敏感值的出現次數，從而抵制相似攻擊。對于該算法而言，它充分發揮了聚類的思想，使數據信息損失最小化。通過大量研究發現，雖然個性化（α，k）-匿名與其執行時間基本一致，但是該算法對數據的保護效果更好。

本文主要研究的是如何保護單一的敏感屬性，怎樣保護多敏感屬性的個性化隱私將是未來重要的研究方向。

參考文獻：

[1] Sweeney L. k-anonymity： A model for protecting privacy[J]. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2002， 10（05）： 557-570.

[2] Stokes K， Torra V. n-Confusion： a generalization of k-anonymity[C]//Proceedings of the 2012 Joint EDBT/ICDT Workshops，2012： 211-215.

[3] Liu J， Wang K. Enforcing vocabulary k-anonymity by semantic similarity based clustering[C]//2010 IEEE International Conference on Data Mining. IEEE， 2010： 899-904.

[4] Wang C， Liu L Z， Gao L J. Research on k-Anonymity algorithm in privacy protection[C]//Advanced Materials Research. Trans Tech Publications Ltd， 2013， 756： 3471-3475.

[5] Machanavajjhala A， Kifer D， Gehrke J， et al. l-diversity： Privacy beyond k-anonymity[J]. ACM Transactions on Knowledge Discovery from Data （TKDD）， 2007， 1（1）： 3.

[6] Li N， Li T， Venkatasubramanian S. t-closeness： Privacy beyond k-anonymity and l-diversity[C]//2007 IEEE 23rd International Conference on Data Engineering. IEEE， 2007： 106-115.

[7] Wong R C W， Li J， Fu A W C， et al. （α， k）-anonymity： an enhanced k-anonymity model for privacy preserving data publishing[C]//Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. 2006： 754-759.

[8] Truta T M， Vinay B. Privacy protection： p-sensitive k-anonymity property[C]//22nd International Conference on Data Engineering Workshops （ICDEW'06）. IEEE， 2006： 94-94.

[9] 韓建民，于娟，虞慧群，賈泂.面向敏感值的個性化隱私保護[J].電子學報，2010，38（07）：1723-1728.

[10] 賈俊杰， 閆國蕾. 一種個性化 （P， k） 匿名隱私保護算法[J]. 計算機工程， 2018， 44（1）： 176-181.

[11] Li J， Wong R C W， Fu A W C， et al. Achieving k-anonymity by clustering in attribute hierarchical structures[C]//International Conference on Data Warehousing and Knowledge Discovery. Springer， Berlin， Heidelberg， 2006： 405-416.

【通聯編輯：代影】