基于差分隱私的數據匿名化隱私保護方法

陳曉宇，韓 斌，黃樹成

(江蘇科技大學 計算機學院，江蘇 鎮江 212000)

0 引 言

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

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

在現有隱私保護方法的基礎上了，提出了一種新的匿名化隱私保護方法。該方法通過引入差分隱私技術，有效地防止了匿名隱私保護中存在的背景知識攻擊。同時，該方法設計了新的數據匿名化過程，經過構造具有單調性的泛化層次結構、壓縮泛化后的數據等一系列措施獲取到局部最優泛化過程，并通過實驗驗證該方法的性能。

1 理論基礎

1.1 差分隱私保護

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

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

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

(1)

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

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

(2)

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

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

(3)

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

1.2 k-匿名

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

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

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

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

表1 k-匿名實例表

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

表2 泛化等級

2 基于差分隱私的數據匿名化保護方法

2.1 隱私保護方法

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

2.2 算法設計與實現

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

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

輸出：隱私保護下的數據集T[O']。

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

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

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

步驟4：轉換T[D]中T[A]的存儲方式，將T[A]中T[S]轉換后的結果記作T[S']，同時壓縮數據得到數據集T[D']。

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

步驟6：返回數據集T[O']。

2.2.1 優化數據匿名化過程

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

每一個轉換過程都可以由低一級別的轉換過程得到。整個轉換過程中的任意一條由底端最低泛化節點到頂端最高泛化節點的路徑都具有單調性。

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

圖1 單調泛化層次結構

2.2.2 轉換和壓縮數據

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

2.2.3 添加拉普拉斯噪聲

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

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

|p-0.5|)

(4)

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

2.3 性能分析

2.3.1 可用性分析

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

2.3.2 安全性分析

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

3 實驗與分析

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

3.1 直方圖發布

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

圖2 各年齡段有配偶人數統計結果發布對比圖

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

3.2 安全風險分析

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

表3 風險評估 %

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

4 結束語

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