面向各類攻擊的差分隱私保護模型

◆黃曉 黃喻先

（1.中國移動通信集團江蘇有限公司 江蘇 210012；2.南京郵電大學 江蘇 210023）

1 引言

約翰●奈斯比在《大趨勢》中提到：“人們正被數據淹沒，卻又饑渴于知識。”數據庫技術的成熟使得數據量以指數規模增長，同時，高帶寬、低延時、高穩定的5G技術使得海量數據得以高速傳輸和集中處理。它們的延伸價值將體現在通信領域的下一個金礦——數據挖掘之中。因此，無論是傳統的零售業還是新興的電子商業，人們都迫切地希望對數據去粗取精，揭示其中的潛在價值。

然而，數據集中通常包含著許多個人的隱私信息。例如，電商企業收集的客戶交易數據集中包含著個人的消費習慣，這些信息會隨著數據的共享和挖掘而泄露。因此，如何在使用數據的同時保護用戶的敏感信息成了當前信息安全領域亟待解決的問題。

為了應對各類攻擊，提出了三種隱私保護的方向：數據失真[1]、數據加密[2]和限制發布[3]。數據失真是在數據中添加噪聲，使敏感數據失真但同時保持其余數據不變的方法。這是以犧牲數據的準確性和真實性為代價，從而達到保護隱私的目的。數據加密通過將數據挖掘算法與加密算法結合起來，保證了數據的機密性，但面對海量數據時加密算法計算開銷極大。限制發布技術則是對原始數據的選擇性發布。當前這類技術的研究集中于數據匿名化，比如隱藏數據中的某些標識符屬性（例如姓名、ID號等），使得敏感信息泄露被控制在一個極小的范圍內。但是，由于新型的網絡攻擊手段層出不窮，傳統的限制發布技術已無法滿足隱私保護的需要。

因此，鑒于傳統隱私保護方法的不足，研究人員試圖尋求一種有效的并且可以被證明的隱私保護模型，能夠抵御當下各種形式的攻擊。差分隱私[4]（Differential Privacy，DP）的提出使得這種設想逐漸成了可能。

2 數據集公開時面臨的隱私攻擊

2.1 數據集的基本概念

數據集[5]可以理解為包含若干個記錄的數據文件，每條記錄均描述了一個實體的多方面屬性。根據特征的不同，我們可以將屬性分為以下四類：

（1）個體標識符：例如姓名、身份證號等可以唯一標識一個個體的屬性。

（2）準標識符：與外部信息鏈接從而可標識個體身份的屬性（單個準標識符不能定位個體，但是多個準標識符鏈接后可用來潛在的識別某個體），如圖1所示，在學生學籍信息數據集和學生體檢信息數據集中，班級、性別、出生日期都不能直接確定學生身份，而它們的鏈接組合可以基本確定某個學生身份。

（3）敏感屬性：數據挖掘時需要被保護的隱私信息，例如是否患病，薪資等信息。

（4）非敏感屬性：可以公開的屬性，又稱為一般屬性。

2.2 鏈接攻擊

知己知彼，百戰不殆。只有深入理解攻擊者的攻擊手段，我們才能提供更有效的隱私保護。鏈接攻擊[6]是目前攻擊者常用的隱私攻擊手段，曾給美國在線公司帶來了巨大的虧損。

圖1學生學籍信息數據集和體檢信息數據集的鏈接

美國在線（American Online AOL）是一家著名的因特網服務提供商。2006年，為了支持學術研究，AOL公開了近三個月，總共2000萬條的匿名搜索記錄。在這些數據中，AOL使用匿名ID來替代用戶的真實姓名。然而，紐約時報發現用戶的查詢記錄中包含著一些可以揭示他們真實身份的潛在信息，將這些潛在信息與其他可獲得的數據相結合，就能找到部分用戶的真實身份。例如，某位用戶的搜索記錄中包含著“孕期的注意事項”、“A醫院的預約方式”、“B地一周內的天氣情況”。那么我們就可以基本確定該用戶是一位生活在B地，最近去過A醫院的孕婦。倘若再結合A醫院的病人數據集，并逐一排查，就能確定該用戶的真實身份。最終由于這次隱私泄露，AOL被起訴，高層集體離職，賠償了500多萬美元。

通過AOL的例子，我們不難發現，倘若在發布數據之前僅僅刪除或匿名用戶的身份屬性（即個體標識符），并不能保護用戶的個人隱私。攻擊者可能將該數據集與其他公共數據信息聯系起來，確定個體的身份。這被稱作數據挖掘中的鏈接攻擊。

3 差分隱私理論的研究背景

3.1 傳統隱私保護理論的缺陷

K-anonymity[7]（k-匿名化）是由Samarati和L.Sweeney于1998年提出的一種數據匿名化方法，它在隱私保護領域有著深遠的影響。K-anonymity的基本思想是對數據集里某些準標識符進行泛化處理，使得所有記錄被劃分到若干個等價類（Equivalence Group）中，每個等價類中的記錄要大于等于K條。例如，學生A的成績為98分，學生B的成績為96分，為了實現成績這一準標識符的泛化，我們可以將具體成績修改為成績區間，即學生A、B都處于[95，100]這一等價類中，從而實現記錄的隱藏。

但是，后續的研究發現，K-anonymity等傳統隱私保護模型存在兩個主要缺陷。其一，這些模型的可靠性受制于攻擊者所掌握的背景知識（攻擊者可獲得的外部信息），而背景知識的大小很難被充分定義。其二，傳統的隱私保護模型無法嚴格地證明其隱私保護水平。所以，當隱私保護模型中的部分參數改變后，我們難以對其隱私保護水平進行定量評估。

3.2 差分隱私理論的提出

差分隱私[8]一詞最初是由Dwork在2006年提出的。Dwork通過嚴格的數學證明對隱私保護進行新的定義。在此定義下，單條記錄的變化對于數據集的整體計算結果是不敏感的，即添加或刪除一條記錄時隱私泄漏的風險被控制在非常小的范圍內。

差分隱私能夠解決傳統隱私保護模型的兩個不足。首先，差分隱私保護是以攻擊者的最大背景知識為前提的。最大背景知識是攻擊者可以獲得的目標個體的所有相關信息。而事實上，攻擊者所掌握的外部信息總是遠小于最大背景知識的。

其次，差分隱私有著堅實的數學基礎。其中涉及的參數，例如隱私預算、全局敏感度等都是可量化的。因此，我們可以通過這些參數進行隱私水平的比較。

如今，通過不斷地發展，差分隱私理論的研究越來越成熟，廣泛應用于數據發布、數據挖掘、人工智能、機器學習等領域。

4 差分隱私保護模型

4.1 基本定義

差分隱私保護[9]就是要確保任何一個記錄無論在不在數據集中，對查詢結果幾乎沒有影響。也就是說，如果有兩個只相差一條記錄的數據集，分別對它們進行相同的查詢操作，那么查詢結果相同的概率為100%。

定義1（鄰近數據集）設數據集D和D'具有相同的屬性結構且，數據集對稱差DΔD'=1，即這兩個“數據集”只相差一條記錄，則稱“數據集”D和D'為鄰近數據集。

定義2（差分隱私）給定鄰近數據集D和D'，設：存在隨機算法A，Range(A)為A所有可能的輸出結果，若算法A在數據集D和D'上任意輸出結果O(O∈Range(A))滿足下列不等式：

則稱算法A滿足 -ε差分隱私。其中Pr[·]為事件發生的概率，參數ε為隱私預算。ε越小，可添加的噪聲越大，隱私保護的水平越高，但數據集的可用性會降低，因此ε的取值要綜合考慮數據的安全性與可用性。

4.2 實現機制

差分隱私保護有兩種常用的實現機制[10]：Laplace機制和指數機制。Laplace機制常用于輸出結果為數值型的數據集的保護，而指數機制適用于非數值型的數據集的保護。

Laplace機制主要是通過向查詢結果中添加服從Laplace分布的隨機噪聲。噪聲的大小由查詢函數的全局敏感度Δf和隱私預算ε共同決定。當添加Laplace噪聲后，用戶查詢得到的結果將不再是一個固定值而是一個不確定的隨機數，這個隨機數的概率密度函數服從Laplace分布。

指數機制的關鍵在于打分函數的設計，根據打分函數對查詢結果進行打分。設算法A的輸入為原始數據集D，r∈Range是所有可能輸出的結果，q為打分函數，q（D,r）表示得到的分數，用來評估輸出值r的優劣程度，Δq為函數q（D,r）的敏感度。若算法A以正比于的概率從Range中選擇并輸出r，則算法A提供-ε差分隱私保護。

4.3 組合性質

倘若要解決一個復雜的隱私保護問題，并且為了保證多次調用后隱私預算仍有效控制在ε之內，我們常常要多次調用差分隱私保護模型。此時，我們可以用差分隱私保護的組合性質[11]，合理地將預算分配到整個算法的各個步驟。

4.3.1 串行組合性質

設有n個隨機算法A1,A2,…,An，它們的隱私預算分別為ε1,ε2,… ,εn，那么對于同一數據集D，它們的組合算法提供差分隱私保護。所以，如果對一個數據集調用多次差分隱私保護時，隱私預算為所有隱私預算的總和。

4.3.2 并行組合性質

設有n個隨機算法A1,A2,…,An，它們的隱私預算分別為ε1,ε2,… ,εn，分別應用于不相交的數據集D1,D2,… ,Dn，它們的組合算法A(A1(D),A2(D),… ,An(D))提供maxεi-差分隱私保護。所以，如果對多個不相交數據集調用差分隱私保護時，隱私預算為其中的最大值。

圖2差分隱私的組合性質

5 差分隱私的應用

（1）差分隱私在GPS軌跡數據上的應用

通過分析用戶的汽車軌跡數據，我們可以獲取到許多有價值的信息。例如，我們可以在軌跡熱區點修建一些加油站和充電樁，既便利了用戶，又能推動相關產業的發展。但是，GPS軌跡數據中包含著用戶的位置信息，倘若不加以處理就將數據發布，攻擊者可以輕易獲取某個個體的行程路線，這會帶來極大的安全隱患。因此，我們可以在GPS軌跡數據中加入符合Lapalce分布的隨機噪聲，使得處理后的數據滿足差分隱私保護的要求，極大地提高了用戶的位置隱私安全。

（2）差分隱私在網絡瀏覽記錄上的應用

隨著互聯網的普及，網絡瀏覽記錄成了人們最為重要的隱私區域之一。如果不加以保護，黑客可以通過對網絡蹤跡的數據挖掘，肆意地侵犯個體的生活隱私。早期的網絡瀏覽記錄的凈化方法是匿名化處理，但是2.2節中AOL的例子告訴我們簡單的匿名化處理不足以維護我們的信息安全，所以我們將差分隱私應用到了其中。數據發布者在數據公開之前可以根據敏感度在數據中加入噪聲，使得單獨刪除每一條網絡瀏覽記錄對整體的統計結果不會產生影響，從而實現了差分隱私保護。

（3）差分隱私在電子購物中的應用

在線支付的成熟促使電子購物在人們生活中所占的比重越來越大。各個電子購物平臺可以通過對用戶購物記錄的數據挖掘，做到商品的精準推薦，以此來擴大購買需求。對于消費者來說，商品推薦能夠讓他們在最短的時間內找到需要的商品。所以，對消費記錄的數據挖掘是一個雙贏的過程。但是，我們務必要重視購物記錄的隱私保護，否則會適得其反。因此，我們可以對推薦系統的輸入進行干擾，向其中加入高斯噪聲，使其滿足差分隱私保護的標準，然后實施常規的推薦算法。

6 總結與展望

差分隱私是一種高效且可以被證明的隱私保護模型，它考慮了攻擊者最大的背景知識，以堅實的數學理論為支撐，通過參數量化隱私保護水平，彌補了傳統隱私保護模型的缺陷，有著廣闊的前景。本文從原理性質和實際應用的角度對差分隱私保護進行了敘述，希望能夠為信息安全領域的學者提供參考價值。