數據發布中k-匿名隱私保護技術研究

岳 思，吳偉明，谷勇浩

（1. 北京郵電大學計算機學院 智能通信軟件與多媒體北京市重點實驗室，北京 100876；2. 國家電網公司信息通信分公司，北京 100761）

數據發布中k-匿名隱私保護技術研究

岳 思，吳偉明，谷勇浩

（1. 北京郵電大學計算機學院 智能通信軟件與多媒體北京市重點實驗室，北京 100876；2. 國家電網公司信息通信分公司，北京 100761）

隨著互聯網技術的迅猛發展，隱私保護已成為社會以及機構越來越關心的問題，數據挖掘技術的應用使得隱私泄露問題日益突出，隱私保護是目前數據發布中隱私泄露控制技術研究的熱點問題之一，而 K-匿名是近年來隱私保護研究的熱點。本文介紹了K-匿名的基本概念，闡述了泛化與隱匿技術，研究了基于datafly的多維屬性泛化 K-匿名模型，并對該模型的基本原理、缺點進行分析，做出了相應的改進，在數據預處理階段增加泛化層限制并且在準標識符屬性選取時引入近似度分析，并對改進后的 K-匿名進行實驗，實驗結果證明改進有效提高了處理后的數據精度。

數據發布；隱私保護；K-匿名；泛化與隱匿；datafly

0 引言

隨著 Internet技術、大容量存儲技術的迅猛發展以及數據共享范圍的逐步擴大，數據的自動采集和發布越來越頻繁，信息共享較以前來得更為容易和方便；但另一方面，以信息共享與數據挖掘為目的的數據發布過程中隱私泄露問題也日益突出，因此如何在實現信息共享的同時，有效地保護私有敏感信息不被泄漏就顯得尤為重要。數據發布者在發布數據前需要對數據集進行敏感信息的保護處理工作，數據發布中隱私保護對象主要是用戶敏感信息與個體間的關聯關系，因此，破壞這種關聯關系是數據發布過程隱私保護的主要研究問題[1]。

目前解決該問題的方法主要有以下三種（1）匿名。有的機構為了保護個人隱私不被泄露，常常對姓名身份證號等能表示一個用戶的顯示標識符進行刪除或者加密，但是攻擊者可以通過用戶的其他信息，例如生日、性別、年齡等從其他渠道獲取的個人信息進行鏈接，從而推斷出用戶的隱私數據。（2）數據擾亂。對初始數據進行扭曲、擾亂、隨機化之后再進行挖掘，盡管這種方法能夠保證結果的整體統計性，但一般是以破壞數據的真實性和完整性為代價[2]。（3）數據加密。基于密碼的隱私保護技術，主要利用非對稱加密機制形成交互計算的協議，實現無信息泄露的分布式安全計算，以支持分布式環境中隱私保持的挖掘工作，例如安全兩方或多方計算問題，但該方法需要過多的計算資源。

為了彌補以上三種方法的不足，1998年，P.Samarati和L.seweney在PODS國際會議上提出了K-匿名的概念，這一技術得到了廣泛關注。2002年，L.seweney又進一步提出了K-匿名隱私保護模型，同年他又論述了通過泛化和隱匿的方法來實現這一技術。然而，目前如何通過匿名化技術更為高效的實現發布數據的隱私保護，仍然是業界當前研究的重要課題，本文旨在通過分析數據發布隱私保護中匿名化的基本原理和實現技術，在研究K-匿名的傳統實現算法-datafly算法的基礎上，進一步對基于多維屬性泛化的K-匿名隱私保護模型做出了改進，引入近似度分析并通過對不同的準標識符屬性的泛化樹增加限制達到滿足不同數據需求的效果，使數據表能夠盡快的滿足K-匿名，并且提高處理后數據的可用性。

1 K-匿名的相關概念

1.1 屬性劃分

假設數據發布者持有的信息為數據表T（A1，A2，A3…An），表中的每條記錄表示一個用戶的基本信息，如姓名、籍貫、年齡、性別、健康狀況等。如表1所示。

數據表中的屬性按功能可分為互不相交的四種。

（1）標識符（Identifier）

能夠唯一標識個體身份的屬性或屬性集合，如表T中的身份證號、姓名等，在數據發布前，一般要將這些顯示標識符屬性刪除、屏蔽或者加密，以達到保護這些私有屬性的目的。

表1 數據表T實例Tab.1 Ta ble T

（2）準標識符（Quasi- Identifier）

能與其它數據表進行鏈接從而能夠標識一個個體的屬性或者屬性集合。表中的屬性都可以為準標識符，準標識符的選擇取決于外部鏈接的數據表，同一張表對于不同的外部表可能有不同的準標識符[2]。

（3）敏感屬性（sensitive attribute）

即敏感信息，數據發布時需要保密，如疾病，薪水，婚姻狀況等。

（4）非敏感屬性（Non- sensitive attribute）

可公開的屬性，又稱普通屬性，如表中的年齡。

1.2 鏈接攻擊

鏈接攻擊是從發布的數據中獲取隱私數據最常見的方法之一。攻擊人員利用從其他渠道獲取的數據和包含隱私信息的發布的匿名表進行鏈接，從而推斷出隱私數據，造成了隱私泄露[4]。

例如攻擊者獲得選民表如表 2，以及以上去除標識符的個人信息表表 1，這里（sex、age、zip、Provice）可以構成準標識符，攻擊者根據準標識符進行鏈接，就可以推斷出李青患有肺炎這一敏感信息。

1.3 K-匿名的定義

K-匿名隱私模型要求每條記錄（屬于一個個體）在公布的數據中與其他至少K-1條記錄無法被區分開來[6]。因此，知道被攻擊者的準標識符屬性值的攻擊者，是不能夠將這條記錄與其他至少K-1個數據記錄區分開。這被稱為身份攻擊防范。具有相同準標識符值的記錄構成一個等價類，即k-匿名實現了同一等價類內的記錄無法區分開來。

2 多維屬性泛化K-匿名的基本實現方法

K-匿名隱私模型目前主要是通過隱匿和泛化來實現，不同于一般的扭曲、擾亂和隨機化等方法，該方法僅隱藏數據細節，能夠使數據在發布前后保持一致性和真實性。

表2 選民信息表Tab.2 T able voter

2.1 隱匿與泛化

在 K-匿名隱私保護模型中單獨使用隱匿的情況比較少，一般采用泛化技術或者泛化和隱匿相結合使用。在k-匿名過程中，若某些記錄無法滿足匿名要求，一般就會采取隱匿的技術，從而很好的保證發布數據的安全性。隱匿是指把匿名表中的數據直接刪除，采取這樣的方式會直接減少匿名表中的數據，但是在某些情況可以減少需要進行泛化數據的數量，減少泛化的數據損失，達到相對比較好的匿名效果[7]。

泛化指用一個不明確的、更一般的，但是忠實于原值的值來代替原值。泛化可分為兩種：值泛化和域泛化。

域泛化是指將一個給定的屬性域泛化成一般域。如屬性ZIP原始域Z0={100870，100871，100876，100875，101230，101231，101231}被泛化成 Z1={10087*，1012*}，以便在語義上表達一個較大的范圍。經過連續多次泛化形成的域泛化層次結構稱之為域泛化層，記為DGHA。

值泛化是指原始屬性域中的每個值直接泛化成一般域中的惟一值，如圖1所示。值泛化關系同樣決定了值泛化層的存在，記為VGHA。

圖1 Z ip的值泛化圖Fig.1 The generalization of Zip

2.2 多維屬性泛化K-匿名的基本實現

當前K-匿名的主要實現方式是泛化和隱匿，泛化的基本思想是用更一般的值或者模糊的值取代原始屬性值，但語義上與原始值保持一致。目前在k-匿名中常用datafly算法來實現泛化。但在進行泛化之前，對于要進行匿名化的數據表先進行預處理，具體步驟如下。

（1）數據持有者標明待發布數據表中可用于發布的屬性和元組;

（2）數據持有者對待發布數據表中的屬性按照上述的類別劃分標識符、準標識符等。

（3）數據持有者根據需求為待發布數據表指定一個K值。

（4）對表格進行刪除含有空值和非法值的元組等一系列工作。

（5）生成每個準標示符組別中的屬性的泛化樹。

待發布數據表經過上述一系列的預處理之后，K-匿名模型便進入了算法的核心部分:泛化和隱匿，在此我們選取了最為經典的 Datafly算法進行泛化處理。首先，對該數據表進行K-匿名檢測，若該表滿足K-匿名則直接輸出，如不滿足則對該表數據采取以下操作。

（1）統計各準標識符屬性的取值個數即對準表示屬性值域的大小統計。

（2）選取出統計值中最大的準標識符屬性進行一個層級的泛化。

（3）系統對泛化后的表格進行 K-匿名檢測。如果泛化后的數據表符合K-匿名檢測，那么此表將作為輸出結果被系統輸出；如果此表格沒能符合K-匿名檢測，系統將繼續對前面所選取的準標識符屬性進行泛化和K-匿名滿足性的檢驗，直到該表滿足K-匿名模型為止。

（4）最后，經泛化后滿足 K-匿名檢驗的數據表將會以輸出結果的形式被輸出。

至此輸出的數據表就是經過處理后滿足 K-匿名的結果，但根據上述的操作流程不難看出，該方法存在一個比較大的問題，在被泛化屬性的選取方面太過單一，在整個泛化過程中，被泛化的準標識符屬性始終為最初數據表中取值最多的那個，但隨著泛化的進行，幾輪泛化之后該屬性很有可能已經不再是當前表中取值最多的那個準標識符屬性，若繼續對該屬性進行泛化使得該數據表難以盡快滿足K-匿名，同時很容易造成過度泛化降低泛化后的數據表的可用性。

因此，目前最常見的還是基于多維屬性泛化的K-匿名，即為了避免被泛化的準標識符屬性的選取過于單一，將泛化屬性的選取融入到K-匿名的循環檢驗當中。在泛化屬性的選取上，基于多屬性泛化的 K-匿名算法不僅只在泛化起始時對被泛化屬性進行挑選，而是在每次泛化和K-匿名檢驗后，系統都會重新選取被泛化的準標識符屬性，這樣就可以減少數據表在匿名處理的過程中被過度泛化，提高了泛化后數據的可用性。

3 多維屬性泛化K-匿名的改進與實現

3.1 對K-匿名的改進

因在上述K-匿名的實現過程中，我們不難發現，這一算法在進行匿名化的過程中存在以下不足：缺乏對取值最多的屬性不唯一的考慮。為了解決這個問題，當前常用的有以下兩種方法。一種是隨機選取，即在取值最多的屬性之中隨機選取出一個準標識符屬性作為被泛化的屬性，另一種是使用熵的方式來選取被泛化的準標識符屬性。不過，這兩種方式都有其一定的局限性。其中，隨機選取的方式易造成數據表的過度泛化，基于熵的選取方式計算量太大且需要有專業人員對各準標識符屬性進行評估，操作起來十分耗時。

針對上述問題，本文改進了多維屬性泛化的K-匿名算法，在泛化屬性的選取等方面進行了相應的改進，引入了近似度分析。無論是經典的Datafly算法還是多維屬性泛化的K-匿名算法，在選取被泛化的準標識符屬性這一環節，如果數據表包含大量的準標識符屬性，很容易出現取值最多的準標識符屬性不止一個的情況，這種情況下如果不做進一步處理，系統一般都會默認為隨機選取。不過，為了使數據表盡早的滿足 K-匿名且考慮到數據發布環節中可能存在的背景知識攻擊，這里引入了近似度的概念。準標識符屬性的近似度即一準標識符屬性中所包含的值之間的離散程度， 近似度越低，屬性取值分布的越均勻，K-匿名越容易提早完成；反之，近似度越髙，屬性分布的越分散，K-匿名越不好達成，遭到背景知識攻擊等威脅的幾率也會相應增加。而各屬性的近似度可以通過求解各屬性的標準差來進行衡量，具體的計算步驟如下所示:

（1）統計給定表中準標識符屬性各值在表中的出現頻次；

（2）求出該準標識符屬性各取值的出現概率和該屬性取值的平均概率；

（3）求出該準標識符屬性的方差和標準差；

（4）對所得方差開平方，所得的標準差即為該準標識符屬性的近似度。

除此之外，為了滿足不同的需求，在數據預處理階段，構建泛化樹是增加泛化層的限制，。根據上述K-匿名的概念以及實現原理，不難看出，通過對不同的準標識符屬性進行不同層級的泛化，滿足K-匿名要求的處理后的數據表可以有多種，但根據第三方對于數據的要求，不同的處理結果數據的可用性也不盡相同。例如對常見的醫療信息進行匿名處理，若第三方要分析某種疾病與年齡之間存在的聯系，若處理后的數據表將年齡泛化到了非常模糊的層級，而保留了相對準確一些的地域屬性，那么輸出的結果其實并不能滿足該統計的需求。

因此，在進行匿名處理的過程中，根據第三方不同的需求，對于處理后的數據也有著不同程度的要求，對于這一問題，我們可以通過約束各準標識符屬性的泛化層次以保證匿名泛化表能夠滿足特定數據分析任務對匿名泛化表數據質量的要求，主要就是在數據預處理階段，生成各個準標識符屬性的泛化樹之后，根據數據需求對每一顆泛化樹做出泛化層的限制，調整泛化樹。如上述例子中可以要求年齡最高只能泛化到10代、20代等10歲唯一值域區間的層級，而對地域不加以限制，從而提高處理后的數據的可用性。

3.2 基于多維屬性泛化的K-匿名的實現

通過上述對多維屬性泛化K-匿名的改進策略，得到了改進后的基于多維屬性泛化的K-匿名，具體實現如圖2所示。

圖2 基于多維屬性泛化的K-匿名實現流程圖Fig.2 Flow chart of K- anonymous implementation based on multidimensional attribute generalization

首先，在輸入方面，我們需要給定一個數據表PT，一個準標識符屬性集合、一個泛化層度K、各準標識符屬性的泛化層次限制以及各準標識符屬性的域泛化層次樹。此外，我們還需保證給定表 PT中的元組個數是大于等于給定的泛化層度K。

接下來，我們要對給定的數據表PT進行K-匿名檢驗，即計算表中每個等價組中所包含的元組數，檢測該表中是否存在元組個數小于K的等價組。其中，如果給定的數據表PT無小于K個元組的等價組，即表格滿足K-匿名。那么系統會直接將給定的表格輸出。如果給定的數據表沒能通過 K-匿名檢驗，那么系統會對其采取以下操作：

（1）對各準標示符屬性的取值個數進行統計即對準標識符屬性值域大小進行統計。

（2）選取出統計值中最大的準標識符屬性，若值不唯一，對這幾個準標識符進行近似度分析計算，對近似度值較高的準標識符進行泛化。

（3）判斷選取出的值中最大的準標識符屬性當前是否已經泛化到最高層，若沒有泛化到最高層，則對該屬性進行的泛化，若已泛化到最高層則選取次優先級的屬性進行泛化。

（4）系統對泛化后的表格進行K-匿名檢測。如果泛化后的數據表符合K-匿名檢測，那么此表將作為輸出結果被系統輸出；如果此表格沒能符合K-匿名檢測，系統將繼續對前面所選取的準標識符屬性進行泛化和 K-匿名滿足性的檢驗，直到該表滿足K-匿名模型為止。

（5）最后，經泛化后滿足K-匿名檢驗的數據表將會以輸出結果的形式被輸出。

4 實驗結果分析

在前面對于K-匿名的論述中可以看到，在數據發布環節使用 K-匿名對數據進行匿名處理的目的就是既能保護用戶的敏感信息不被泄露，又能保證處理后的數據的可用性。因此在對K-匿名進行評價時，我們習慣采用處理后的數據精度作為衡量的標準，泛化后數據精度的度量也可以說是對于泛化后數據相較于原數據的損失程度的度量。當前較為常用度量方式有三種，他們分別是基于泛化層級的精度度量標準、基于懲罰值的數據辨識度度量標準以及基于熵的度量標準。

本文所采用的度量標準是Precision度量公式：

由K-匿名模型的創始人之一Sweeney L提出并命名，其中，Hi表示準標示符屬i的泛化層級樹的高度，h表示準標示符屬性 i所泛化到的層級，Na表示準表示符屬性的數目。這一度量標準是通過對比泛化后數據表和初始數據表中各準標示符屬性的泛化層次來計算泛化后數據的信息損失程度。

本實驗選用了Adult數據集中的Adult.test文本文件作為數據樣本，分別對基于原始datafly算法的K-匿名以及引入近似度分析、泛化層次限制的改進后的基于多屬性泛化的K-匿名進行了實驗，使用上述Precision度量公式，計算隨著選取K值的不同，分別使用這兩種方法處理后的的數據精度，實驗結果如圖3所示。

圖3 實驗結果圖Fig.3 Experimental result chart

可以看到，這兩種方法隨著K值的增大，處理后數據的數據精度逐漸變低，此外相較于基于datafly的K-匿名，改進后的基于多維屬性泛化的K-匿名在數據精度方面也有了一定的提高，從而在達到對用戶進行隱私保護目的的同時，提高了處理后數據表的可用性，驗證了本文提出的改進的有效性。

[1] 王平水, 王建東. 匿名化隱私保護技術綜述[J]. 小型微型計算機系, 2011(02).

[2] 岑婷婷, 韓建民, 王基一, 李細雨. 隱私保護中K-匿名模型的綜述[J]. 計算機工程與應用. 2008(04).

[3] 李暉, 牛犇, 李維皓.移動互聯網服務中的隱私保護機制[J].中興通訊技術. 2015(03).

[4] 張雪松, 徐勇. K-匿名隱私保護相關技術的研究[J]. 電子世界. 2012(05).

[5] 朱玉, 趙桐, 王珊. 面向查詢服務的數據隱私保護算法[J].計算機學報. 2010(08).

[6] 王波, 楊靜. 數據發布中的個性化隱私匿名技術研究[J].計算機科學. 2012(04).

[7] 何賢芒. 隱私保護中K-匿名算法和匿名技術研究[D]. 復旦大學 2011.

[8] 宋金玲. K-匿名隱私保護模型中與匿名數據相關的關鍵問題研究[D]. 燕山大學 2012.

[9] 任向民. 基于K-匿名的隱私保護方法研究[D]. 哈爾濱工程大學, 2012.

[10] 劉堅. K-匿名隱私保護問題的研究[D]. 東華大學, 2010.

[11] Zakerzadeh H, Aggarwal C C, Barker K. Privacy-preserving big data publishing[C]// International Conference on Scientific and Statistical Database Management. ACM, 2015: 26.

[12] M. Xue, P. Karras, C. Ra_ssi, J. Vaidya, and K.-L.Tan,Anonymizing set-valued data by nonreciprocal recoding,"KDD, 2012.

[13] M. E. Nergiz, M. Atzori, and C. Clifton, Hiding the presence of individuals from shared databases," SIGMOD, 2007.

Research on K-anonymous Privacy Protection Technology in the Data Release

YUE Si, WU Wei-ming, GU Yong-hao
(1. School of Computer Science, Beijing University of Post and Telecommunications, Beijing Key Laboratory of intelligent communication software and multimedia ,Beijing 100876, China; 2. National Power Grid Corp information and communication branch, Beijing 100761, China)

With the rapid development of Internet technology, individuals and institutions are increasingly concerned about the issue of privacy protection. With the application of data mining technology, privacy leakage is becoming more and more serious. Privacy protection is one of the hot topics in the research of privacy leakage control technology in Data Publishing, and K- anonymous is the hotspot of privacy protection research in recent years. This paper introduces the basic concept of K- anonymous, expounds the generalization and hidden technology, introduces the multidimensional attribute generalization K- anonymous model based on Datafly, and the basic principle and the disadvantages of the model are analyzed. In addition, the corresponding improvement is made, the generalization layer is limited in the data preprocessing stage, and the approximation analysis is introduced in the selection of the identifier attribute, and the improved K- anonymity experiment is carried out. The experimental results show that the improved method effectively improves the accuracy of the processed data.

Data release; Privacy protection; K-Anonymous; Generalization and Concealment; Datafly

TP309

A

10.3969/j.issn.1003-6970.2017.11.002

本文著錄格式：岳思，吳偉明，谷勇浩. 數據發布中k-匿名隱私保護技術研究[J]. 軟件，2017，38（11）：12-17

國家自然科學基金項目資助(61173017，61370195)；工信部通信軟科學項目資助(2014-R-42，2015-R-29)；國網科技項目(SGTYHT/15-JS-191)

岳思(1994-)，女，研究生，移動互聯網。

吳偉明，教授，主要研究方向：現代網絡通信。