基于差分隱私的直方圖發布方法

湯文兵，張偉媛

（安徽理工大學計算機科學與工程學院，淮南 232001）

0 引言

近年來，保護隱私的數據分析受到越來越多的關注。而針對隱私問題所提出的隱私保護模 型 有 很 多，如k-anonymity、l-diversity、t-closeness等，可以解決有著不同知識背景的攻擊者所發起的攻擊。在各種隱私概念中，差分隱私在數學上提供了嚴格的隱私保障，并在本質上防止各種身份攻擊，而不管攻擊者可能獲得的輔助信息是什么。差分隱私要求任何個人數據記錄的存在或不存在都不會對結果產生很大的影響，因此用戶很難從輸出中了解任何個人數據記錄，從而保護個人隱私。

例如，表1是某醫院患者患病信息的原始數據庫表。表1中的“?”表示攻擊者知道該患者之外其他所有病人的患病信息，這個時候稱這個攻擊者有著表1中的最大背景知識。如果數據的擁有者在沒有隱私保護的情況下直接發布數據，那么攻擊者就能夠在通過查詢返回值的情況下執行差分攻擊去推斷Bob的病情信息。此時就稱該病人的隱私發生了泄漏。

表1 病人患HIV情況

針對上述問題，本文將差分隱私應用到直方圖發布技術中，通過在原始直方圖上進行加噪處理來保護數據的隱私信息。在真實數據集進行實驗測試，證明該方法能在滿足差分隱私的同時進行數據發布，即在保護了個人信息的前提下，同時也保證了數據發布的可用性。

1 定義及相關概念

1.1 直方圖

直方圖是許多不同研究領域的基本工具，包括數據挖掘、計算機視覺等。給定數據庫中一組元組，即={,…,x}，假設屬性A上這些元組的值為{,…,x}，則屬性A的直方圖H由一組等寬的單元格（或桶）組成，每個桶的寬度代表一個查詢范圍，高度則代表了該范圍的統計情況。通常，每個桶的范圍不會相互重疊，并且它們的并集應該覆蓋所有的屬性A值。因此，有了這樣一個直方圖，可以實時回答屬性A的一系列范圍查詢。

1.2 差分隱私

假設有兩個數據集和'，兩者的屬性結構相同，當且僅當和'最多有一條記錄不同時，我們稱和'為相鄰數據集。因此我們對差分隱私有如下定義：

對于任意兩個相鄰數據庫和'，以及所有可能的輸出值的集合，有隨機算法，若算法滿足：

則稱算法提供-差分隱私保護，其中參數稱為隱私保護預算。

1.3 隱私保護預算與敏感度

1.3.1 隱私保護預算

算法使用隱私保護預算控制相鄰數據集輸出相同的概率的比值。實際上反映了可以提供的隱私保護水平，其越小表示隱私性越強，同時數據可用性也就越低。因此，通常將的值與特定的要求結合起來，以實現輸出結果的安全性和可用性之間的平衡。

1.3.2 敏感度

敏感度指刪除數據集中任一記錄對查詢結果造成的最大改變，是決定加入噪聲量大小的關鍵因素。在差分隱私中主要分為局部敏感度和全局敏感度。

對于任意函數:→R，全局敏感度為：

對于任意函數:→R，局部敏感度為：

1.4 差分隱私實現機制

拉普拉斯機制。有數據集，設函數:→R，其敏感度為Δ，那么隨機算法

提供－差分隱私保護，其中Lap（）表示服從Laplace分布的隨機噪聲，尺度參數=Δ/。

當敏感數據不是數值的且拉普拉斯機制不適用時，可以采用另一種方法即指數機制實現。指數機制利用打分函數對每個輸出進行評分，并對得分較高的輸出分配指數級更大的概率。選擇的實用函數應具有較低的靈敏度。

指數機制。對于數據庫，（,）為打分函數，設隨機算法的輸入為數據集，輸出為實體對象，且∈Range，R表示算法從Range中選擇并輸出R的概率，若：

則稱算法提供ε－差分隱私保護，Δ為函數（，）的敏感度。

1.5 組合機制

給定個算法，…，M，每個均滿足ε-差分隱私，對于同一個數據集，依次執行，…，M，由這些算法組成的組合算法滿足（∑ε）差分隱私。

給定個算法，…，M，每個都滿足ε-差分隱私，對于個互斥的數據集，…，D，分別執行算法，…，M，則由這些算法組成的組合算法滿足（max{ε}）差分隱私。

2 算法設計

直方圖中包含的個單位桶代表了個獨立的范圍計數查詢。而對于相鄰數據集的直方圖H和H'，H的某個單元桶頻數為，H'的某個單元桶頻數則為'，根據相鄰數據集定義可得|-|=1，所以在直方圖中每個單元桶的敏感度Δ=1。因此，只需要向直方圖的每個桶中加入部分服從拉普拉斯分布的噪聲就可以滿足差分隱私的需求。

輸入：原始數據集H，隱私預算

輸出：滿足差分隱私的直方圖H'

將數據集H按照不同階段分為個桶（H={H，H，H，…，H}）。

For=1 to：

使用拉普拉斯機制對H加噪生成H'，敏感度Δ=1，=隱私預算，將H'寫入H'數據集中。

得到滿足差分隱私的直方圖H'={H',H',H'，…，H'}。

3 實例分析

3.1 實驗設置

實驗所用硬件環境為11th Gen Intel（R）Core（TM）i5 2.40GHz，16 GB內存，使用Python編程語言實現，操作系統平臺為Windows10，實驗采用真實數據集adult和employee salary，均被廣泛應用于數據發布。adult數據集共32560條數據，15個屬性，這里采用age屬性構建直方圖，employee salary共244條記錄，三個屬性值，采用其中的salary屬性構建直方圖。這兩個屬性均為連續類型，實驗中將每個屬性均劃分為5個桶，選擇不同的隱私預算分別對原始直方圖進行加噪，最終可以得到一個擾動的直方圖。

3.2 實驗分析

圖1為在Adult數據集age屬性上分成的五個子集，并在每個子集上添加一個服從拉普拉斯分布的噪聲，可以看出在添加了噪聲的情況下直方圖的桶高發生了變化，也就是該查詢范圍的統計數值發生了改變，然而在此數據集上噪聲的影響并不是很明顯。觀察圖2中Employee Salary數據集中salary屬性的擾動直方圖，可以直觀地發現噪聲在此數據集上的作用比較明顯。同時能夠觀察該數據集中擾動結果在不同隱私預算的作用下也是不同的，在隱私預算等于0.05時擾動直方圖與原始直方圖的差別最大，隱私預算等于5時，加噪的直方圖與原始直方圖的差別比較小。

圖1 關于Adult數據集age屬性的擾動直方圖

圖2 關于Employee Salary數據集salary屬性的擾動直方圖

本文采用KLD（kullback-leibler divergence）來衡量與原始直方圖的誤差，由于每次的實驗結果具有隨機性，所以本次實驗數據取50次實驗結果的平均值。如表2所示，在隱私預算相同的情況下Adult數據集的KLD要小于Employee Salary數據集。而在同一數據集上，KLD會隨著隱私預算的增加而減小。

表2 不同隱私預算下兩個數據集分別的KLD

4 結語

本文從隱私安全出發，提出了基于差分隱私保護的直方圖發布方法。首先在輸出數據前進行加噪，再將加入噪聲的直方圖進行發布，最終達到保護數據信息隱私的目的。通過對比分析實驗，證明了該發布方法在隱私保護的前提下，能夠保證數據發布的可用性。