[[375638]]

物聯網會感知大量數據，感知數據通常需要發布和共享。但數據在發布和共享時面臨巨大的隱私泄露風險。隨著數據挖掘技術的不斷提高，經過隱私保護的物聯網數據中的敏感信息也越來越容易被數據挖掘者獲取，因此，如何保護發布數據中的隱私問題，成為了一個新的研究熱點。

從根本上來講，數據發布隱私保護就是在數據發布的同時，盡可能地保護發布數據中的隱私信息。差分隱私作為目前數據發布隱私保護的一個標準，它能夠在數據發布的過程中，對原始數據進行一定的處理，從而達到保護原始數據中敏感信息的目的。簡單來說，差分隱私數據發布就是數據擁有者將數據通過某種形式向外界展示，并利用差分隱私技術對數據中的隱私信息進行保護的過程。

01 差分隱私的概念

差分隱私是目前數據發布隱私保護技術中具有強大理論保證和嚴格數學證明的隱私保護模型。差分隱私保護是對數據添加擾動保護的一種保護技術，它可以不考慮攻擊者的背景知識，通過添加一定規律的噪聲來保證數據集的統計特征不變，同時也對數據集進行了保護，方便研究者在數據進行保護以后對數據進行一些挖掘、統計工作，不泄露用戶的隱私。

差分隱私具有嚴格的數學證明，該機制可以確保在對數據進行保護以后不會影響輸出結果的統計特性，攻擊者無法判斷該用戶是不是在該數據集中，因為使用差分隱私保護以后對于數據的查詢結果在形式上不可區分，所以保證了用戶的個人隱私信息不被泄露。

差分隱私可以增加或刪除數據庫中的一條記錄，使得攻擊者在具有任何知識背景的情況下都無法判斷某條記錄是否存在于正在被分析的數據庫中。假設存在一個數據表，如圖1所示，該數據是某醫院的門診病歷記錄，其中包括病人的姓名、年齡、性別、臨床診斷等信息，圖1（a）是原始數據記錄的直方圖發布形式。如果攻擊者想要知道Cole的診斷情況，并且具有強大的背景知識，如攻擊者已經知道Cole的性別為男、年齡在60~80歲之間，以及其他人的臨床診斷信息，那么攻擊者將能夠推斷出Cole的臨床診斷信息，從而導致Cole的隱私信息被泄露。差分隱私想要解決的也正是這類問題，即在攻擊者具有任何背景知識的情況下，都不會泄露數據集中的隱私信息。

圖1（b）給出了經過差分隱私技術處理過的直方圖發布的結果，從圖中可以看出，即使攻擊者知道年齡在60~80歲之間除了Cole以外所有人的信息，他也沒辦法獲取Cole的診斷信息。

圖1  醫院門診病歷記錄（統計數據直方圖發布）

差分隱私：經典的差分隱私（DP）最初是基于數據集提出的隱私保護概念，它可為數據隱私的保護效果提供嚴格的信息論層次的保證。DP以概率的形式描述原始數據集的微小變化對最終統計輸出的影響，并通過隱私參數￡來約束這一概率變化，達到隱私保護的目的。

假設D是具有n個記錄、d個屬性的數據集，并且假設變量r表示數據集中的一條記錄。兩個數據集D和D′是兄弟數據集，即如果它們有相同的屬性，并且只有一個記錄不同，令ri表示這個記錄，Di表示帶有ri記錄的數據集，D-i表示刪除ri記錄的數據集，則差分隱私定義如下。

ε-差分隱私：對于差別至多為一個記錄的兩個數據集D和D′，Range(A)表示一個隨機函數A的取值范圍，Pr[Es]表示事件Es的披露風險，若隨機函數A提供ε-差分隱私保護，則對于所有的S⊆Range(A)，都滿足如下所示：

如圖2所示，算法通過添加一些規律的噪聲來實現差分隱私，同時保證在刪除或者添加某一條記錄的時候，查詢的一些統計概率不發生變化，從而保護了用戶之間的隱私信息。

圖2  隨機算法在鄰近數據集上的輸出概率

（ε,δ）-差分隱私：對于差別至多為一個記錄的兩個數據集D和D′，Range(A)表示一個隨機函數K的取值范圍，Pr[Es]表示事件Es的披露風險，若隨機函數A提供（ε,δ）差分隱私保護，則對于所有的S⊆Range(A)，都滿足如下所示：

其中，D和D′表示相鄰數據集，根據相鄰數據集的差異，可將差分隱私分為有界差分隱私（Bounded Differential Privacy，BDP）和無界差分隱私（Unbounded Differential Privacy，UDP）。在BDP中，D和D′是相鄰數據集，可以通過替代D′中的一個實體而得到D。在UDP中，D和D′是相鄰數據集，可以通過添加或刪除D′中的一個實體而得到D。BDP中的相鄰數據集具有相同的大小，而UDP中卻沒有這個約束。

（ε,δ）-差分隱私是ε-差分隱私的松弛版本，其允許違反隱私的概率被參數δ控制在一個很小的范圍內。這個定義的隱私保護在ε-差分隱私帶來過量噪聲而導致較低的效用性的場景中，可以展現出明顯的優勢。

差分隱私能通過添加隨機噪聲來實現查詢操作，這個被添加的噪聲是隱私參數ε的一個函數，這個查詢的性質被稱為敏感度。敏感度的類型會隨著兩個相鄰的數據庫的查詢結果而改變，在大多數情況下，我們會將全局敏感度作為決定查詢結果安全性的一個重要的參數。

ε表示隱私預算，是衡量隱私保護強度的參數。由上圖可知，ε值越小，算法的隱私保護程度就越強。反之，隱私保護程度就越弱。差分隱私保證了無論數據庫中任意一條記錄存在與否，對算法的輸出分布幾乎沒有影響。

相鄰數據集：若D與D′為相鄰數據集，則D可通過D′添加、刪除或修改一個數據元組得到。

從上述定義可以看出，對于任意兩個相鄰的數據集，它們輸出同一結果的概率比率差距介于e-ε和eε之間；由此可知，參數ε對控制隱私泄露量起著至關重要的作用。

基于DP的定義，學者們設計出一些滿足要求的隨機化機制；在相同的ε水平下，機制的設計和適用性會極大地影響隱私化數據的可用性。

全局敏感度：對于給定的查詢函數f:Dn→Rd，f的Lp全局敏感度定義為：

GSf=maxD,D′||f(D)-f(D′)||p

數據集D和D′之間最多相差一條數據記錄。

局部敏感度：對于給定的查詢函數f:Dn→Rd，其中D∈Dn，D的Lp局部敏感度定義為：

LSf(D)=maxD′|| f(D)-f(D′)||p

對于一些查詢操作函數f，得到的∆f都是比較小的，對于計數查詢函數來說∆f=1，并且這個屬性和查詢函數有關，和數據集的屬性無關，可以通過這個屬性來對數據集進行發布操作，即進行多種函數操作以使數據集滿足數據保護要求，一般使用拉普拉斯機制和指數機制進行差分隱私保護。

差分隱私算法具有組合特性，即幾個滿足差分隱私的獨立算法通過組合得到的算法仍滿足差分隱私。差分隱私的組合特性保證了一系列差分隱私算法計算的隱私，根據這個特性可得出以下性質。

順序組合（Sequential Composition）：如果一個機制M由多個子機制構成，如M=（M1,M2,…,Mn），其中Mi滿足εi-差分隱私，那么機制M滿足εi-差分隱私，其中

并行組合（Parallel Composition）。如果數據庫中的每個不相交的子集Di在機制Mi下都滿足εi-差分隱私，那么

在機制Mi下也滿足εi-差分隱私。

02 差分隱私保護模型

差分隱私數據發布主要有兩種保護模型：交互式保護模型和非交互式保護模型。如圖3所示，在交互式保護模型下，數據擁有者根據實際需要設計滿足差分隱私的數據發布算法A，當用戶向服務器發出查詢請求Q時，在隱私預算沒有消耗完的情況下，返回給用戶的查詢結果將經過差分隱私算法A添加一定量的噪聲，即用戶獲得的查詢結果是添加噪聲后的答案，而不是真實答案。這種交互式保護模型具有時效性較好的特點，能夠及時更新數據庫并實時返回查詢結果。但該模型存在的問題就是隱私預算消耗過快，需要利用有限的隱私預算盡可能多地對查詢請求進行回答，這其中也涉及如何為每次查詢分配隱私預算的問題。

圖3  交互式保護模型

圖4所示為差分隱私數據發布的非交互式保護模型。數據擁有者首先利用差分隱私算法A對要發布的數據進行隱私保護，然后形成一個新的合成數據庫，合成數據庫與原始數據庫具有相似的統計特征。此時，用戶所有的查詢以及數據挖掘等操作都是在合成數據庫上進行的，以保證原始數據中的隱私信息不被泄露。這種模型的特點就是不限制用戶的查詢次數，但會導致數據發布的可用性較低、數據查詢的時效性較差。

圖4  非交互式保護模型

03 差分隱私數據發布機制

任何滿足差分隱私定義的機制都可以被看作差分隱私數據發布機制，目前很多差分隱私數據發布機制被提出，如拉普拉斯機制、指數機制、中位數機制、矩陣機制等，但拉普拉斯機制和指數機制是在差分隱私數據發布中應用最廣泛的兩種機制。這兩種機制都可以在滿足差分隱私的情況下，對發布的數據進行隱私保護。此外還有敏感數據集發布機制和非敏感數據集發布機制。

（1）拉普拉斯機制

拉普拉斯機制（Laplace Mechanism）適用于輸出結果是數值型的查詢函數。該機制通過在真實的輸出結果中添加合適的拉普拉斯噪聲以獲得差分隱私，噪聲是根據滿足概率分布

的拉普拉斯分布LAP(λ)而產生的，其中λ是分布的規模因子，其值取決于全局敏感度∆f和預期的差分隱私變量ε，該分布的方差為σ2=2λ2。下面的定理與定義具體給出了這些變量之間的關系。

對于任意的f:Dn→Rd，當

時，添加滿足拉普拉斯分布LAP(λ)的機制的輸出結果滿足ε-差分隱私。

拉普拉斯機制：若一個機制M滿足ε-差分隱私，并且在數據集D上存在一個函數f:D→R，則拉普拉斯機制可表示為：

M（D）=f（D）+LAP（∆/ε）

拉普拉斯機制的原理就是向真實的數據中加入獨立的拉普拉斯噪聲，該噪聲由尺度參數為λ的拉普拉斯概率密度函數產生。如果用LAP（λ）表示拉普拉斯噪聲，則拉普拉斯機制有如下定義：

（2）指數機制

對于非數值型數據，差分隱私利用指數機制對結果進行隨機化的處理，并用一個打分函數q（D,Φ）來評估輸出Φ的質量。另外，由于打分函數依賴于實際的應用，因此不同的應用會有不同的打分函數，這導致沒有一個通用的打分函數可以利用。

指數機制（Exponential Mechanism）：令q（D,Φ）表示數據集D的一個打分函數，該函數可以度量輸出Φ的質量。∆q表示輸出Φ的敏感度，當指數機制M滿足下式時，其滿足差分隱私。

在實際應用中，有許多查詢函數的輸出結果是非數值型的，這導致添加拉普拉斯噪聲沒有任何意義。為此，部分學者提出了指數機制以實現非數值型數據的差分隱私保護，并設計了可以獲得更好查詢響應的應用場景。首先定義一個效用函數u:(D×τ)→R，向輸出域R中的輸出r中添加實數值噪聲。這里，數值越大表示效用性越好。然后以滿足

 

的概率選擇一個輸出r∈R，其中，∆u=maxD,D′,∀r|u(D,r)−u(D′,r)|是效用函數的敏感度。由于u值越大越容易被選擇，因此該機制可以看作對u的最優化。此外，效用函數對數據庫中單條記錄的改變是不敏感的。

下面給出一個具體的實例來說明指數機制。假如班級舉辦運動會，需要挑選一個項目來進行比賽，為了保護投票的信息不被泄露，因為最后得到的結果不是數值型的，所以使用指數機制進行保護；對票數進行計數統計時，很顯然函數的∆q=1，因此，按照指數機制的要求對表1中的投票結果進行保護，即可算出各個項目的概率值。

表1  指數機制應用實例

從上表的計算結果可以看出，當隱私保護參數比較大的時候，輸出結果的概率值也比較大，同時，如果隱私保護參數變小的話，則最后的結果會趨于相等。

對于任意的查詢函數u:(D×τ)→R，指數機制以

的概率選擇一個輸出r時可以保證ε-差分隱私。

（3）敏感候選集發布機制

針對敏感候選集，因為里面包含的不僅是群體用戶的行為特征區域，還有用戶之間的關聯位置信息，所以為了重點保護用戶的位置信息不被攻擊者推斷攻擊而泄露用戶的位置關聯信息，針對敏感候選集提出了關聯敏感度差分隱私保護方法，即對差分隱私中的全局敏感度進行改進，進而減少噪聲的引入。然后對敏感候選集中的所有聚類簇進行隱私保護，以保護用戶的關聯位置隱私。上文得到了用戶個體的關聯敏感度，并且根據得到的敏感候選集的關聯屬性的強弱可以合理地分配ε的大小，保證數據保護的隱私預算滿足差分隱私的要求。針對每個敏感候選集中的用戶個體進行個性化重點保護，對于那些關聯信息比較強的用戶，使用比較強的機制進行數據保護；對于那些關聯性比較弱的用戶，使用相對弱的機制進行數據保護，進而把用戶的關聯信息降到一個可接受的范圍之內，這樣攻擊者進行關聯攻擊的時候，可以得到用戶的關聯屬性的個數就會大大減少。

在處理完用戶的敏感候選集以后，得到的數據既保護了用戶的位置信息，又保護了用戶的關聯信息，并且把數據操作轉化到了矩陣上進行，這使得算法的復雜度進一步降低。

（4）非敏感候選集發布機制

針對非敏感候選集的用戶位置數據，主要是對其中的非停留點位置數據進行隱私保護。用戶的非停留點包含了大量的路徑問題，如果不加以保護，則會使用戶的隱私信息泄露。針對用戶軌跡點，雖然其也有一部分的關聯信息，但是并沒有停留區域表現得那么嚴重。如果對用戶的軌跡點單純地使用差分隱私的拉普拉斯噪聲進行處理，則會在現有的軌跡位置上形成毛刺點，這樣很難抵抗攻擊者的濾波攻擊。因此，這里針對這個問題使用了指數機制，并且在極坐標系下結合用戶位置的速度和方向因素來添加相鄰位置點的噪聲，使得噪聲的添加更能保護用戶的隱私，對抗濾波攻擊。算法主要是針對相鄰位置點，計算出下一個點的速度、方向和距離，然后把笛卡爾坐標系轉換成極坐標系進行不同維度的噪聲添加，這樣添加的噪聲更加符合現實生活的要求，并且對于攻擊者有更好的抵抗能力。這樣得到的數據就可以防止攻擊者的濾波攻擊，使得在添加了保護的基礎上還維護了數據集的可用性，還能使得隱私保護和數據集的可用性都有一個很好的平衡。

04 數據發布面臨的挑戰

目前，雖然許多研究人員致力于數據發布隱私保護技術的研究，但隨著信息技術的發展，數據的規模不斷增大，數據種類也變得更加復雜多樣，尤其是隨著數據挖掘技術水平的提高，隱私保護技術在數據發布中的研究意義更加凸顯。差分隱私作為數據發布隱私保護技術的標準，對于解決當前數據發布與隱私保護之間的矛盾至關重要。因此，研究更好的差分隱私數據發布方法有著重要的現實意義。綜上可知，現有差分隱私數據發布主要面臨的挑戰如下。

（1）數據類型的變化

目前由于現實生活中的許多應用都傾向于動態的產生并發布數據，與之前相比，數據類型由靜態轉為了動態，這導致之前提出的許多差分隱私數據發布方法并不適用于當前的動態數據發布。如果用靜態數據的發布方法來發布動態數據，就可能會由隱私預算有限而導致發布數據的可用性極差。即使目前已提出一些適用于動態數據發布的差分隱私方法，但動態數據發布的可用性仍有待提高。

（2）隱私預算的分配

在差分隱私數據發布中，隱私預算的分配和數據的發布效用息息相關，尤其在動態數據的發布過程中，如果不能合理分配有限的隱私預算，就可能會導致動態數據發布的效用變差?，F有差分隱私動態數據發布方法大部分采用了比較樸素的方法來分配隱私預算，如將隱私預算以均勻、遞增或遞減的方式分配到需要發布的采樣點上，而并沒有根據動態數據的特點將有限的隱私預算進行合理的分配，從而導致隱私預算過早耗盡或浪費。因此，如何在動態數據發布中合理分配有限的隱私預算成為了差分隱私動態數據發布面臨的一個挑戰。