基于差分隱私的直方圖發(fā)布方法

湯文兵，張偉媛

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

0 引言

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

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

表1 病人患HIV情況

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

1 定義及相關概念

1.1 直方圖

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

1.2 差分隱私

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

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

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

1.3 隱私保護預算與敏感度

1.3.1 隱私保護預算

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

1.3.2 敏感度

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

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

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

1.4 差分隱私實現(xiàn)機制

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

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

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

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

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

1.5 組合機制

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

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

2 算法設計

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

輸入：原始數(shù)據(jù)集H，隱私預算

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

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

For=1 to：

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

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

3 實例分析

3.1 實驗設置

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

3.2 實驗分析

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

圖1 關于Adult數(shù)據(jù)集age屬性的擾動直方圖

圖2 關于Employee Salary數(shù)據(jù)集salary屬性的擾動直方圖

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

表2 不同隱私預算下兩個數(shù)據(jù)集分別的KLD

4 結語

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