基于差分隱私的數(shù)據(jù)匿名化隱私保護方法

陳曉宇，韓 斌，黃樹成

(江蘇科技大學(xué) 計算機學(xué)院，江蘇 鎮(zhèn)江 212000)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，以數(shù)據(jù)發(fā)布[1]和數(shù)據(jù)挖掘[2]為主的數(shù)據(jù)共享模式正逐步成為信息化時代的發(fā)展潮流。但是，數(shù)據(jù)共享帶來便捷的同時也伴隨著個人隱私數(shù)據(jù)泄露[3]的風(fēng)險。如何確保隱私數(shù)據(jù)的安全性同時又不降低數(shù)據(jù)的可利用價值，成為當(dāng)前隱私保護[4]領(lǐng)域研究工作的重點。

目前的隱私保護方法可以分為三種：匿名隱私保護[5-6]，采用隱匿標識符屬性[7](identity attribute，身份證號碼、姓名等可以標識個體信息的屬性)和泛化準標識符屬性(quasi-identifier attribute，年齡、性別、生日、郵編等可以推演出標識個體信息的屬性)的方式達到保護敏感屬性(sensitive attribute，疾病、薪資等用戶不愿透露的屬性)不被泄露的目的；差分隱私保護[8]，顧名思義就是為了防止差分攻擊[9]的隱私保護方法。差分隱私保護通過擾亂、混淆、隨機化等方式給數(shù)據(jù)添加噪聲[10]，使得在查詢統(tǒng)計有且只有一條記錄之差的兩個數(shù)據(jù)集時，獲得相同值的概率非常接近；基于密碼學(xué)的隱私保護，通過數(shù)據(jù)加密達到隱私保護的目的。但是這類方法需要消耗過多的計算資源，所以很少被應(yīng)用于數(shù)據(jù)發(fā)布和數(shù)據(jù)挖掘中。

在現(xiàn)有隱私保護方法的基礎(chǔ)上了，提出了一種新的匿名化隱私保護方法。該方法通過引入差分隱私技術(shù)，有效地防止了匿名隱私保護中存在的背景知識攻擊。同時，該方法設(shè)計了新的數(shù)據(jù)匿名化過程，經(jīng)過構(gòu)造具有單調(diào)性的泛化層次結(jié)構(gòu)、壓縮泛化后的數(shù)據(jù)等一系列措施獲取到局部最優(yōu)泛化過程，并通過實驗驗證該方法的性能。

1 理論基礎(chǔ)

1.1 差分隱私保護

差分隱私保護通過對原始數(shù)據(jù)進行隨機擾動，最終達到攻擊者無法利用已知數(shù)據(jù)推測出更多數(shù)據(jù)內(nèi)容的效果。

定義1：給定只相差一條記錄的兩個數(shù)據(jù)集D1和D2，Range(K)表示隨機算法K的取值范圍，若數(shù)據(jù)集在K中的任意結(jié)果S∈Range(K)都滿足式1，則稱算法K滿足ε-差分隱私[5]。

Pr[K(D1)∈S]≤exp(ε)×Pr[K(D2)∈S]

(1)

其中，K(D1)、K(D2)是以D1、D2為輸入，經(jīng)由K得到的輸出結(jié)果；Pr[K(D1)∈S]表示結(jié)果為S的概率，也稱作隱私被泄露的風(fēng)險[11]；ε表示大于零的任意參數(shù)，由數(shù)據(jù)擁有者公開制定，值越小表示差分隱私保護級別越高。

函數(shù)K滿足定義1時，數(shù)據(jù)的隱私就可以得到保證，與攻擊者掌握的背景知識程度無關(guān)。實現(xiàn)差分隱私保護的主要方法是添加噪聲，常用的兩種噪聲機制分別為拉普拉斯機制和指數(shù)機制。其中拉普拉斯機制適用于對數(shù)值型數(shù)據(jù)的保護。拉普拉斯機制通過向確切的查詢結(jié)果中加入服從拉普拉斯分布的隨機噪聲來實現(xiàn)ε-差分隱私保護。記位置參數(shù)為0，尺度參數(shù)為b的拉普拉斯分布為Lap(b)，那么其概率密度函數(shù)為：

(2)

設(shè)查詢函數(shù)為f，數(shù)據(jù)集為D，真實的查詢結(jié)果為f(D)，函數(shù)K則可以表示為：

K(D)=f(D)+(Lap(Δf/ε))

(3)

其中，Lap(Δf/ε)為隨機噪聲，服從尺度參數(shù)為Δf/ε的拉普拉斯分布；Δf為查詢函數(shù)f的全局敏感度，全局敏感度只與查詢函數(shù)本身有關(guān)，與數(shù)據(jù)集的大小無關(guān)。查詢函數(shù)的敏感度越大，則需要添加更多的噪聲。

1.2 k-匿名

目前的數(shù)據(jù)匿名化方案主要有泛化隱匿技術(shù)[12]和基于微聚集匿名化技術(shù)兩種。其中泛化隱匿技術(shù)被廣泛使用，而k-匿名又是泛化隱匿技術(shù)中最具代表性的方法之一。

定義2：給定數(shù)據(jù)表T(A1,A2,…,An)，QI是與T相關(guān)聯(lián)的準標識符，當(dāng)且僅當(dāng)在T[QI]中出現(xiàn)的每個值序列至少要在T[QI]中出現(xiàn)k次，則T滿足k-匿名。

如表1所示，該實例表中準標識符QI為{Race，Birth，Sex，Zip，Marital status}，T[QI]中出現(xiàn)的任一有序元組值在T[QI]重復(fù)至少兩次以上，t1[QI]=t2[QI]=t3[QI]，t4[QI]=t5[QI]。則該實例表滿足k=2的k-匿名保護，攻擊者利用外部數(shù)據(jù)源推導(dǎo)出的個體元組數(shù)據(jù)不能指向任一特定個體。

k-匿名主要通過泛化技術(shù)實現(xiàn)。表2展示了疾病為皮膚過敏，年齡為29，郵編為212000的這組數(shù)據(jù)的泛化等級。

表1 k-匿名實例表

用三維向量(x,y,z)表示一個轉(zhuǎn)換過程。x,y,z的值分別對應(yīng)著疾病、年齡和郵編的泛化等級。該樣例數(shù)據(jù)最高泛化等級為(2，1，3)。泛化等級越高，表示泛化程度越強，但同時信息丟失量也會跟著變大。

表2 泛化等級

2 基于差分隱私的數(shù)據(jù)匿名化保護方法

2.1 隱私保護方法

提出的匿名化隱私保護方法是一個將數(shù)據(jù)集里的屬性進行劃分，然后區(qū)別處理的過程。對布爾型的敏感屬性添加符合差分隱私的拉普拉斯噪聲[8]的過程，提高了敏感信息的安全性。

2.2 算法設(shè)計與實現(xiàn)

文中提出的基于差分隱私的數(shù)據(jù)匿名化隱私保護算法的步驟如下：

輸入：原始數(shù)據(jù)集T(O1,O2,…,On)=T[O]；

輸出：隱私保護下的數(shù)據(jù)集T[O']。

步驟1：將輸入數(shù)據(jù)集T[O]分為屬性值為布爾型數(shù)據(jù)集T(A1,A2,…,Am)=T[A]及補集T(B1,B2,…,Bn-m)=T[B]。記合并T[A]和T[B]得到的數(shù)據(jù)集為T[A,B]，即有T[O]=T[A,B]。用T[S]表示T[A]中屬性為敏感屬性的數(shù)據(jù)集。

步驟2：采用優(yōu)化后的數(shù)據(jù)匿名化過程處理數(shù)據(jù)集T[B]得到T[B']，使其滿足k-匿名保護的要求。

步驟3：合并T[A]和T[B']得到數(shù)據(jù)集T[D]=T[A,B']。

步驟4：轉(zhuǎn)換T[D]中T[A]的存儲方式，將T[A]中T[S]轉(zhuǎn)換后的結(jié)果記作T[S']，同時壓縮數(shù)據(jù)得到數(shù)據(jù)集T[D']。

步驟5：向T[D']中的T[S']加入符合差分隱私保護要求的拉普拉斯噪聲，得到數(shù)據(jù)集T[O']。

步驟6：返回數(shù)據(jù)集T[O']。

2.2.1 優(yōu)化數(shù)據(jù)匿名化過程

步驟2中提到的數(shù)據(jù)匿名化的對象T[B]是非布爾型的屬性值。T[B]中的數(shù)據(jù)屬性又可以分為準標識符屬性和敏感屬性。對數(shù)據(jù)匿名化過程的優(yōu)化主要體現(xiàn)在以下兩點：設(shè)計具有單調(diào)性的泛化層次結(jié)構(gòu)，采用低級別泛化等級處理敏感屬性。以表2中數(shù)據(jù)為例，具有單調(diào)性的泛化層次結(jié)構(gòu)如圖1所示。

每一個轉(zhuǎn)換過程都可以由低一級別的轉(zhuǎn)換過程得到。整個轉(zhuǎn)換過程中的任意一條由底端最低泛化節(jié)點到頂端最高泛化節(jié)點的路徑都具有單調(diào)性。

圖1(2,1,1)，(1,1,2)，(2,0,2)，(0,1,3)，(1,0,3)這一層次中，當(dāng)疾病屬性，即向量中x屬于敏感屬性時，取x為不為0的最小值，得(1,1,2)，(1,0,3)，去除含有0的非匿名轉(zhuǎn)換(1,0,3)得(1,1,2)。此時(1,1,2)就是這個層級中最優(yōu)的泛化過程。若滿足敏感屬性泛化等級是不為0的最小值、且轉(zhuǎn)換過程對應(yīng)的向量中不含0的泛化過程不唯一，則接著比較這些轉(zhuǎn)換過程的次節(jié)點的個數(shù)。(1,1,2)指向(2,1,2)和(1,1,3)，有兩個次節(jié)點。次節(jié)點個數(shù)越多，表示在該節(jié)點基礎(chǔ)上提高泛化層次的選擇性越多，該節(jié)點對應(yīng)的轉(zhuǎn)換過程將在步驟2中被使用。

圖1 單調(diào)泛化層次結(jié)構(gòu)

2.2.2 轉(zhuǎn)換和壓縮數(shù)據(jù)

步驟4中轉(zhuǎn)換和壓縮處理的對象是數(shù)據(jù)集T[D]=T[A,B']，其中T[B']是符合k-匿名保護的數(shù)據(jù)集。壓縮T[B']，將T[B']中相同的元組只保存一條，在表中添加一個數(shù)量(Number)屬性，用來記錄該相同元組存在的個數(shù)。同時，轉(zhuǎn)換T[A]中的屬性的表達方式。例如關(guān)于是否患有HIV屬性，屬性值是Y和N兩種情況，將該屬性轉(zhuǎn)換為HIV(Y)得到T[D']，HIV(Y)表示對應(yīng)數(shù)量中患有HIV的人數(shù)。結(jié)合數(shù)量屬性，可知在關(guān)于是否患有HIV屬性轉(zhuǎn)換過程中不存在信息丟失。

2.2.3 添加拉普拉斯噪聲

步驟5中利用差分隱私技術(shù)添加拉普拉斯噪聲的對象是T[D']中的T[S']，T[S']中都是轉(zhuǎn)換了存儲方式的敏感屬性。還是以關(guān)于是否患有HIV的屬性為例，T[S']對應(yīng)的數(shù)據(jù)屬性為HIV(Y)。記HIV(Y)屬性對應(yīng)的值為n，則添加噪聲后的輸出數(shù)據(jù)為n+Lap(1/ε)。其中隱私保護預(yù)算ε可以根據(jù)需求所要的保護程度自主設(shè)定，添加噪聲的過程則是對式2進行積分，求得拉普拉斯累積分布函數(shù)，再由累積分布函數(shù)求得噪聲值Lap(1/ε)。

Lap(1/ε)=-b*sgn(p-0.5)*In(1-2*

|p-0.5|)

(4)

其中，p為在0.0到1.0之間均勻分布的隨機數(shù)，尺度參數(shù)b滿足b≥1/ε。

2.3 性能分析

2.3.1 可用性分析

文中提出的匿名化隱私保護方法通過采用低級別泛化過程處理部分敏感屬性，最大可能地降低了這些敏感屬性的信息丟失率[13]。同時，相比較現(xiàn)有匿名化隱私保護方法中直接隱匿布爾型的準標識符屬性(例如：性別)的方式，通過轉(zhuǎn)變存儲方式，有效保障了這類屬性的可用性。

2.3.2 安全性分析

文中提出的方法利用差分隱私技術(shù)，在部分敏感屬性中添加拉普拉斯噪聲，有效地防止了傳統(tǒng)匿名化隱私保護方法中存在的背景知識攻擊。同時，在泛化匿名過程中，采用低級別泛化過程處理敏感屬性，保證了在相同的泛化層級中，準標識符屬性獲得更高泛化級別的保護，降低了被鏈接攻擊的風(fēng)險。

3 實驗與分析

實驗使用Java語言編程，編程環(huán)境為MyEclipse10，實驗的環(huán)境配置為2.40GHz i5-2430M、4 GB內(nèi)存、Windows7 32位操作系統(tǒng)。實驗所采用的數(shù)據(jù)集為“ADULT”，來源于美國成年人口普查。該數(shù)據(jù)集擁有30 162個實例，9個屬性值。為了驗證文中方法在安全性和數(shù)據(jù)可用性方面的優(yōu)勢，下面將直方圖發(fā)布和數(shù)據(jù)安全風(fēng)險評估幾個實驗的結(jié)果進行分析。

3.1 直方圖發(fā)布

快速而準確地獲取數(shù)據(jù)分布[14]的梗概是數(shù)據(jù)分析與查詢的主要任務(wù)，直方圖[15]是近似估計數(shù)據(jù)分布的主要技術(shù)之一。以布爾型的敏感屬性婚姻狀況(Marital-status，取值：Spouse-present或Spouse-not-present)為對象，發(fā)布不同年齡階段中婚姻狀態(tài)為有配偶(Spouse-present)的人數(shù)統(tǒng)計數(shù)據(jù)，實驗分析文中隱私保護方法的發(fā)布精度。圖2展示了原始數(shù)據(jù)與輸出的保護數(shù)據(jù)的直方圖發(fā)布結(jié)果對比。

圖2 各年齡段有配偶人數(shù)統(tǒng)計結(jié)果發(fā)布對比圖

由圖可知，文中提出的隱私保護方法下的數(shù)據(jù)仍具有較高的可用性，直方圖發(fā)布具有很高的精度。

3.2 安全風(fēng)險分析

在安全風(fēng)險分析過程中，為驗證文中方法在安全性方面的優(yōu)勢，假設(shè)兩種攻擊者模型。模型1假設(shè)攻擊者已經(jīng)知道了數(shù)據(jù)集中的準標識符屬性數(shù)據(jù)；模型2則假設(shè)攻擊者沒有任何背景知識。表3展示了這兩種攻擊者模型下，實驗數(shù)據(jù)集在k-匿名、差分隱私保護和提出的隱私保護方法下被攻擊的成功率。

表3 風(fēng)險評估 %

由實驗結(jié)果可知，提出的基于差分隱私的數(shù)據(jù)匿名化隱私保護方法在這兩種攻擊模型下對數(shù)據(jù)集的保護強度優(yōu)于k-匿名、差分隱私保護。

4 結(jié)束語

在現(xiàn)有隱私保護技術(shù)的基礎(chǔ)上設(shè)計了一種新的數(shù)據(jù)匿名化隱私保護方法。該方法結(jié)合了拉普拉斯噪聲機制與泛化匿名機制。優(yōu)化后的數(shù)據(jù)匿名化過程降低了數(shù)據(jù)信息的丟失率，同時該方法通過將拉普拉斯噪聲機制引入到數(shù)據(jù)匿名化過程中，有效防止了背景知識攻擊。實驗結(jié)果表明，提出的基于差分隱私的數(shù)據(jù)匿名化隱私保護方法在提高數(shù)據(jù)安全性的同時，有效保證了數(shù)據(jù)的可用性。