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

鄧博允

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

關(guān)鍵詞：隱私保護(hù);個(gè)性化;相似性攻擊;（α，k）-匿名模型;（α，k，m，d）-匿名模型

中圖分類號(hào)：TP393? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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 引言

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

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

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

對(duì)于（α，k）-匿名模型而言，它無(wú)法抵制相似性攻擊，本文利用這一特點(diǎn)，在保證實(shí)現(xiàn)個(gè)性化保護(hù)的前提下，構(gòu)建出了（α，k，m，d）-匿名模型，它能夠抵制相似性攻擊。它通過(guò)限制敏感屬性值在等價(jià)類中出現(xiàn)的頻率以及基于敏感屬性的語(yǔ)義分層樹(shù)并定義了敏感屬性相異性的度量方法控制語(yǔ)義相近的敏感屬性個(gè)數(shù)來(lái)實(shí)現(xiàn)個(gè)性化保護(hù)和防止相似性攻擊。

2 基本概念和相關(guān)技術(shù)

2.1 基本概念

將原始數(shù)據(jù)表1屬性分為三類：

（1）標(biāo)識(shí)符：即唯一能夠反映個(gè)體屬性的標(biāo)志，比如：身份證、姓名等。在進(jìn)行數(shù)據(jù)處理工作時(shí)，一般先刪除掉這些屬性。

（2）準(zhǔn)標(biāo)識(shí)符：無(wú)法直接分辨出個(gè)體，但是能夠利用外部表鏈接識(shí)別個(gè)體的屬性。比如說(shuō)：性別、生日等。

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

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

定義6：所謂敏感屬性語(yǔ)義層次樹(shù)，指的是利用h高的樹(shù)來(lái)反映不同敏感屬性之間的語(yǔ)義關(guān)系，其中，1，2，...，h-1，h依次代表的是根節(jié)點(diǎn)到葉節(jié)點(diǎn)。根節(jié)點(diǎn)屬于全集泛化，父節(jié)點(diǎn)屬于子節(jié)點(diǎn)的泛化，此外，子節(jié)點(diǎn)屬于父節(jié)點(diǎn)中的子類，葉子節(jié)點(diǎn)代表一定的屬性值。

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

3.1 α-約束

對(duì)于敏感值的個(gè)性化α-約束而言，需要按照以下兩個(gè)原則來(lái)實(shí)施：（1）如果屬性值具有較低的敏感性，就把α數(shù)值設(shè)定得大一些，如果屬性值的敏感程度較高，就把α數(shù)值設(shè)定得小一點(diǎn);（2）對(duì)于任一敏感值的頻率約束α，都必須大于原始數(shù)據(jù)對(duì)應(yīng)的頻率。

3.2 距離度量

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

3.3 算法描述

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

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

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

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

實(shí)驗(yàn)環(huán)境：操作系統(tǒng)為 Windows 操作系統(tǒng)，具體型號(hào)為Intel Core i5-7500 CPU， 3.40GHz ，8.0GB RAM 。在實(shí)驗(yàn)過(guò)程中，應(yīng)用的是人口普查adult數(shù)據(jù)集，存儲(chǔ)于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中。實(shí)驗(yàn)中我們采用了其中的7個(gè)屬性，其中準(zhǔn)表識(shí)符6個(gè)，敏感屬性一個(gè)：occupation。表4為根據(jù)敏感屬性值的敏感程度個(gè)性化設(shè)置的頻率約束α的參數(shù)表。

4.2 執(zhí)行效率對(duì)比

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

4.3 數(shù)據(jù)信息保護(hù)程度分析

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

5 結(jié)束語(yǔ)

敏感屬性值需要進(jìn)行個(gè)性化保護(hù)，而傳統(tǒng)模型并不能防止相似攻擊，為此本文構(gòu)建了一個(gè)個(gè)性化（α，k，m，d）-匿名模型，它能夠抵制相似攻擊，主要原理是等價(jià)類中存在不同的個(gè)性化約束敏感值，從而進(jìn)行個(gè)性化保護(hù)，此外，還能夠根據(jù)不同的敏感屬性語(yǔ)義層次樹(shù)，來(lái)調(diào)控敏感值的出現(xiàn)次數(shù)，從而抵制相似攻擊。對(duì)于該算法而言，它充分發(fā)揮了聚類的思想，使數(shù)據(jù)信息損失最小化。通過(guò)大量研究發(fā)現(xiàn)，雖然個(gè)性化（α，k）-匿名與其執(zhí)行時(shí)間基本一致，但是該算法對(duì)數(shù)據(jù)的保護(hù)效果更好。

本文主要研究的是如何保護(hù)單一的敏感屬性，怎樣保護(hù)多敏感屬性的個(gè)性化隱私將是未來(lái)重要的研究方向。

參考文獻(xiàn)：

[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] 韓建民，于娟，虞慧群，賈泂.面向敏感值的個(gè)性化隱私保護(hù)[J].電子學(xué)報(bào)，2010，38（07）：1723-1728.

[10] 賈俊杰， 閆國(guó)蕾. 一種個(gè)性化 （P， k） 匿名隱私保護(hù)算法[J]. 計(jì)算機(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.

【通聯(lián)編輯：代影】