湯文兵，張偉媛

（安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，淮南 232001）

0 引言

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

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

表1 病人患HIV情況

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

1 定義及相關(guān)概念

1.1 直方圖

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

1.2 差分隱私

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

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

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

1.3 隱私保護(hù)預(yù)算與敏感度

1.3.1 隱私保護(hù)預(yù)算

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

1.3.2 敏感度

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

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

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

1.4 差分隱私實(shí)現(xiàn)機(jī)制

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

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

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

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

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

1.5 組合機(jī)制

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

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

2 算法設(shè)計(jì)

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

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

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

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

For=1 to：

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

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

3 實(shí)例分析

3.1 實(shí)驗(yàn)設(shè)置

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

3.2 實(shí)驗(yàn)分析

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

圖1 關(guān)于Adult數(shù)據(jù)集age屬性的擾動(dòng)直方圖

圖2 關(guān)于Employee Salary數(shù)據(jù)集salary屬性的擾動(dòng)直方圖

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

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

4 結(jié)語(yǔ)

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