岳 思，吳偉明，谷勇浩

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

數(shù)據(jù)發(fā)布中k-匿名隱私保護技術研究

岳 思，吳偉明，谷勇浩

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

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

數(shù)據(jù)發(fā)布；隱私保護；K-匿名；泛化與隱匿；datafly

0 引言

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

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

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

1 K-匿名的相關概念

1.1 屬性劃分

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

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

（1）標識符（Identifier）

能夠唯一標識個體身份的屬性或?qū)傩约希绫鞹中的身份證號、姓名等，在數(shù)據(jù)發(fā)布前，一般要將這些顯示標識符屬性刪除、屏蔽或者加密，以達到保護這些私有屬性的目的。

表1 數(shù)據(jù)表T實例Tab.1 Ta ble T

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

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

（3）敏感屬性（sensitive attribute）

即敏感信息，數(shù)據(jù)發(fā)布時需要保密，如疾病，薪水，婚姻狀況等。

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

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

1.2 鏈接攻擊

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

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

1.3 K-匿名的定義

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

2 多維屬性泛化K-匿名的基本實現(xiàn)方法

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

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

2.1 隱匿與泛化

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

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

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

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

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

2.2 多維屬性泛化K-匿名的基本實現(xiàn)

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

（1）數(shù)據(jù)持有者標明待發(fā)布數(shù)據(jù)表中可用于發(fā)布的屬性和元組;

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

（3）數(shù)據(jù)持有者根據(jù)需求為待發(fā)布數(shù)據(jù)表指定一個K值。

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

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

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

（1）統(tǒng)計各準標識符屬性的取值個數(shù)即對準表示屬性值域的大小統(tǒng)計。

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

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

（4）最后，經(jīng)泛化后滿足 K-匿名檢驗的數(shù)據(jù)表將會以輸出結(jié)果的形式被輸出。

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

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

3 多維屬性泛化K-匿名的改進與實現(xiàn)

3.1 對K-匿名的改進

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

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

（1）統(tǒng)計給定表中準標識符屬性各值在表中的出現(xiàn)頻次；

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

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

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

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

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

3.2 基于多維屬性泛化的K-匿名的實現(xiàn)

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

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

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

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

（1）對各準標示符屬性的取值個數(shù)進行統(tǒng)計即對準標識符屬性值域大小進行統(tǒng)計。

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

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

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

（5）最后，經(jīng)泛化后滿足K-匿名檢驗的數(shù)據(jù)表將會以輸出結(jié)果的形式被輸出。

4 實驗結(jié)果分析

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

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

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

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

圖3 實驗結(jié)果圖Fig.3 Experimental result chart

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

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

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

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

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

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

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

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

[8] 宋金玲. K-匿名隱私保護模型中與匿名數(shù)據(jù)相關的關鍵問題研究[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

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

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

岳思(1994-)，女，研究生，移動互聯(lián)網(wǎng)。

吳偉明，教授，主要研究方向：現(xiàn)代網(wǎng)絡通信。