概率系統(tǒng)差分隱私研究綜述

(北京大學(xué) 信息科學(xué)技術(shù)學(xué)院 高可信軟件技術(shù)教育部重點實驗室， 北京 100871)

當今社會，互聯(lián)網(wǎng)技術(shù)正在日益深入人們的生活.隨著網(wǎng)絡(luò)和信息化產(chǎn)業(yè)的迅猛發(fā)展，數(shù)據(jù)以前所未有的速度不斷地增長和累積，大數(shù)據(jù)已經(jīng)成為學(xué)術(shù)界和產(chǎn)業(yè)界的熱點，同時改變著人們的日常生活[1-3].在大數(shù)據(jù)背景下，不但數(shù)據(jù)體量相對于以往有了質(zhì)的飛躍，而且人們對信息處理的速度，信息來源的多樣性，信息處理的價值都有了更高的要求[4-6].然而，隨著從大數(shù)據(jù)中挖掘出各種各樣的敏感信息，數(shù)據(jù)參與者的隱私受到了嚴重威脅，這迫使人們加強對數(shù)據(jù)的隱私保護[1, 6-10].

雖然學(xué)術(shù)界并沒有通用的隱私概念，但一般意義下，用戶會將一部分信息認為是自身敏感并且不愿意公開的，通常將這部分信息稱為隱私.然而，如果直接將這部分信息屏蔽，數(shù)據(jù)的價值就會大打折扣.可以說，完善地保護敏感信息，同時又有效地釋放對公眾有益的信息，這本身就是一對矛盾的事情[11].在社會學(xué)方面，可以制定保護個人信息的法律，對惡意窺探他人隱私的行為進行懲罰，但是這種方法實施起來需要大量的人力資源，效果也不甚理想[2，12].因此，從技術(shù)上解決這個問題變得更加實際，通常的做法是通過“去識別”的方式使部分數(shù)據(jù)匿名.但不幸的是，隨著數(shù)據(jù)量的增長，數(shù)據(jù)之間的關(guān)聯(lián)度日益增強，一些經(jīng)過“去識別”處理的匿名數(shù)據(jù)，仍然能夠通過互相之間的聯(lián)系得到辨認，使得預(yù)防用戶身份再識別的難度與日俱增.2006年，Dwork提出了差分隱私(differential privacy)的概念[13].差分隱私是迄今為止針對攻擊者的先驗知識進行普遍保護的最有效的技術(shù).作為有望解決大數(shù)據(jù)中隱私保護問題的一個重要研究方向，最近十余年差分隱私在學(xué)術(shù)界[3, 14-26]和工業(yè)界[27-29]均受到了廣泛關(guān)注.

盡管如此，現(xiàn)有差分隱私的研究主要基于靜態(tài)數(shù)據(jù)集，在給定數(shù)據(jù)集上設(shè)計滿足差分隱私的算法，而在現(xiàn)實中數(shù)據(jù)模式和數(shù)據(jù)內(nèi)容時刻都在發(fā)生著變化，實現(xiàn)對動態(tài)數(shù)據(jù)的利用和隱私保護將更有意義，也更具挑戰(zhàn)性.一個值得注意的事實是，差分隱私的相關(guān)算法大多在數(shù)據(jù)管理系統(tǒng)中實現(xiàn).例如，管理分布式數(shù)據(jù)的Airavat系統(tǒng)在云計算環(huán)境中執(zhí)行MapReduce計算時，在強制訪問控制框架下利用差分隱私發(fā)布數(shù)據(jù)[30].問題是，即使這類系統(tǒng)的相關(guān)構(gòu)件正確實現(xiàn)了差分隱私的有關(guān)算法，但是因為無法確保系統(tǒng)在整個過程中妥善處理了敏感數(shù)據(jù)且沒有給攻擊者提供可以推斷出敏感信息的渠道，所以仍然無法確保整個系統(tǒng)具有差分隱私性.另外，早在2010年，Dwork等[31]就注意到一些實際應(yīng)用中(例如，流感的發(fā)病率監(jiān)測)需要反復(fù)計算，從而研究了在連續(xù)觀察(連續(xù)處理輸入數(shù)據(jù)產(chǎn)生輸出數(shù)據(jù))時，如何設(shè)計高效的隱私性算法.因為不同的數(shù)據(jù)可能屬于同一用戶，所以，在用戶層面保護隱私，而不是針對每個輸入保護隱私，就顯得非常必要.可見在傳統(tǒng)差分隱私算法設(shè)計方面也出現(xiàn)了動態(tài)處理數(shù)據(jù)的要求.

可喜的是，近幾年國內(nèi)外一些學(xué)者開始在系統(tǒng)層面研究差分隱私，即將差分隱私的思想用于系統(tǒng)在多次輸入和輸出情況下的整體隱私性研究.在系統(tǒng)層面考慮隱私性，除了上面提及的因素之外，另一個動機是，最近幾年學(xué)者們在系統(tǒng)層面研究匿名性[32-34]、信息泄漏[35-36]和可靠性[37-38]等安全屬性方面，取得了一些突出的成果，這激勵著學(xué)術(shù)界進一步從系統(tǒng)層面研究隱私性.粗略地說，系統(tǒng)層面差分隱私的研究一般采用概率自動機、概率進程代數(shù)、概率標號遷移系統(tǒng)或馬爾可夫鏈等建模系統(tǒng)，在此之上量化系統(tǒng)的跡(trace)、概率分布等行為隨系統(tǒng)輸入的改變情況.如果系統(tǒng)輸入的微小改變，不會引起系統(tǒng)行為的較大變化，那么這個系統(tǒng)被認為是保護差分隱私的.本文旨在簡要綜述概率系統(tǒng)差分隱私的最新研究進展和研究方向，以期促進該領(lǐng)域的進一步研究.

本文簡要闡述了傳統(tǒng)差分隱私概念提出的背景、定義及相關(guān)擴展；較詳細地介紹了概率系統(tǒng)差分隱私方面的研究進展；討論了概率系統(tǒng)差分隱私保護研究所面臨的挑戰(zhàn)和未來的可能發(fā)展方向.

1 傳統(tǒng)差分隱私

目前，大數(shù)據(jù)分析被廣泛應(yīng)用于科學(xué)、醫(yī)藥、商業(yè)、農(nóng)業(yè)等諸多領(lǐng)域，幫助人們獲取知識和預(yù)測趨勢.然而，大數(shù)據(jù)的興起也給數(shù)據(jù)分析的各個階段，如數(shù)據(jù)收集、數(shù)據(jù)保護、數(shù)據(jù)處理、數(shù)據(jù)修復(fù)，帶來了新的挑戰(zhàn)[39-40].大量事實表明，如果大數(shù)據(jù)未被妥善處理和保護，那么它們可能會對用戶的隱私造成極大的侵害[39, 41].即使許多看似無害的數(shù)據(jù)，被攻擊者大量收集后，也可能會因為這些數(shù)據(jù)彼此之間的聯(lián)系而暴露用戶隱私[42].因此，不可能單純通過法律條款實現(xiàn)用戶隱私保護，這迫使人們尋求新的技術(shù)手段來解決隱私保護這一難題.

在數(shù)據(jù)庫領(lǐng)域，隱私保護一直就是一個備受關(guān)注的研究方向.對于數(shù)據(jù)發(fā)布者來說，如何將有用的信息發(fā)布出去，同時還要保護數(shù)據(jù)參與者的隱私不被泄漏，一直是一個兩難的問題[11，43-45].在大數(shù)據(jù)應(yīng)用環(huán)境下，數(shù)據(jù)之間存在著復(fù)雜的關(guān)聯(lián)和敏感性，數(shù)據(jù)呈現(xiàn)出動態(tài)特征，而大部分基于靜態(tài)數(shù)據(jù)集的傳統(tǒng)數(shù)據(jù)隱私保護模型和算法無法直接移植到大數(shù)據(jù)應(yīng)用中[39].以典型的k匿名方案為例，早期的方案及其優(yōu)化方案通過元組泛化、抑制等數(shù)據(jù)處理[46-48]，將準標識符分組，使得發(fā)布的數(shù)據(jù)中至少包含一定數(shù)量無法用準標識符區(qū)分的條目，這樣攻擊者就不能判斷出隱私信息所屬的具體個體.然而，這些工作是針對靜態(tài)及一次性數(shù)據(jù)發(fā)布情形的.在大數(shù)據(jù)背景下，情況更加復(fù)雜，攻擊者既可以持續(xù)地收集用戶的歷史數(shù)據(jù)，從而具備學(xué)習(xí)用戶背景知識的能力，又可以從多種渠道獲得數(shù)據(jù)，對多次發(fā)布的數(shù)據(jù)進行聯(lián)合分析，破壞數(shù)據(jù)原有的匿名特性.

大數(shù)據(jù)時代的隱私性主要體現(xiàn)在不暴露用戶敏感信息的前提下進行有效的數(shù)據(jù)挖掘[49].因此，保護隱私的數(shù)據(jù)挖掘方面的研究，近年來逐漸成為相關(guān)領(lǐng)域的研究熱點，并主要集中于研究新型的數(shù)據(jù)發(fā)布技術(shù)，嘗試在盡可能少損失數(shù)據(jù)信息的同時最大化地隱藏用戶隱私[1, 6, 50].這方面標志性的工作，是Dwork于2006年提出的差分隱私概念[13]：

定義1[13](差分隱私).設(shè)是一個隨機算法，其值域為Range().給定ε≥0，對于任意兩個僅相差一條記錄的相鄰數(shù)據(jù)集D和D′，以及Range()的任意子集S，如果算法滿足

差分隱私成功的原因之一是它的上述定義不依賴于秘密信息的先驗知識，使得它對于多種信息資源組合的攻擊具有魯棒性.具體而言，差分隱私要求當一個函數(shù)(查詢)作用在兩個僅僅相差一個條目的數(shù)據(jù)庫上時，得到的結(jié)果應(yīng)該在概率上不可區(qū)分.也就是說，對于給定的結(jié)果，兩種情況下得到這個結(jié)果概率的比值不會超過一個給定的參數(shù)[13].這樣，差分隱私就可以有效地保護單個參與者，因為即使一個調(diào)查者對于被調(diào)查的數(shù)據(jù)庫有一些預(yù)先的了解，他也不可能通過滿足差分隱私的函數(shù)，來獲取針對某個參與者更為詳盡的信息.

為了實現(xiàn)查詢結(jié)果的隱私性，一個常見方法是在精確查詢結(jié)果的基礎(chǔ)上，人為地再增加一個噪音量，這樣可使得查詢結(jié)果具有隨機性.但問題是，如果噪音的特點比較明顯，分布比較集中，那么加入了噪音的查詢結(jié)果還是能夠反映出一些特征，從而被進一步利用.針對差分隱私，最常見增加的噪音是拉普拉斯噪音，這種噪音在早期差分隱私方面的研究中就已出現(xiàn)[51]，并且一直保持著長久的生命力.拉普拉斯噪音依賴于查詢的敏感度(即查詢函數(shù)在兩個僅相差一個元素的數(shù)據(jù)集上查詢結(jié)果之差的最大值)，并以此為基礎(chǔ)構(gòu)造出滿足拉普拉斯分布的隨機變量，將它作為噪音添加到查詢結(jié)果中.Geng等[52-53]優(yōu)化了拉普拉斯噪音，提出了一種概率密度函數(shù)滿足階梯性質(zhì)的噪音，可以在同等程度的隱私保護下，取得更好的有效性.

雖然差分隱私最初是為了保護統(tǒng)計數(shù)據(jù)庫隱私安全而提出的概念，但是差分隱私的思想已被廣泛應(yīng)用到其他諸多領(lǐng)域，包括程序語言[40, 54-55]、推薦系統(tǒng)[56-57]、地理位置[58]、社交網(wǎng)絡(luò)[59]、疾病發(fā)現(xiàn)[60]、智能運輸系統(tǒng)[61]、人類活動[62]、聚合監(jiān)測[63]和濾波[64]等.現(xiàn)階段，差分隱私理論方面的工作主要集中在算法設(shè)計和模型擴展上.算法設(shè)計包括如何設(shè)計滿足更強隱私性或更高效率的算法，以及如何在數(shù)據(jù)的可用性和隱私性之間達到更加優(yōu)異的平衡[14，65-67].模型擴展方面，Li等[68]在此基礎(chǔ)上給出了隱私定義的一個統(tǒng)一框架——隸屬隱私(membership privacy)的概念；Duchi等[69]細化了對個人敏感信息的保護，提出了局部差分隱私(local differential privacy)的概念[24]；Chatzikokolakis等[70]考慮了使用一般度量代替數(shù)據(jù)庫條目間差別的漢明距離；最近，Dwork等[71]考慮了傳統(tǒng)差分隱私的一個松弛版本——中心化差分隱私(concentrated differential privacy)，該隱私性具有較好的精度和群體性質(zhì)；為了更好地保證數(shù)據(jù)的可用性，Soria-Comas等[72]擴展了傳統(tǒng)差分隱私，提出了個體隱私性(individual differential privacy)的概念.

2 概率系統(tǒng)的差分隱私

系統(tǒng)層面差分隱私的研究起源于2009年卡內(nèi)基梅隆大學(xué)CyLab網(wǎng)絡(luò)安全實驗室Datta教授課題組的工作“Differential Privacy for Probabilistic Systems”[73].隨后，該課題組和國際上其他研究團隊繼續(xù)推進了這方面的研究，分別以概率輸入輸出自動機、概率進程代數(shù)、概率標號遷移系統(tǒng)和馬爾可夫鏈等為模型，擴展了傳統(tǒng)差分隱私概念，并研究了相關(guān)性質(zhì)，得到了一些好的結(jié)果.本節(jié)根據(jù)概率系統(tǒng)的不同建模方式，分別介紹這些研究進展.

2.1 基于概率輸入輸出自動機的差分隱私研究

如定義1，傳統(tǒng)的差分隱私保護的是以數(shù)據(jù)集為輸入的概率函數(shù)的隱私性.該概念提出后不久，Tschantz等便注意到這種差分隱私無法保證數(shù)據(jù)庫系統(tǒng)和分布式系統(tǒng)的隱私性[73]，進而考慮將差分隱私定義從保護函數(shù)的隱私性擴展到保護系統(tǒng)的隱私性.基于確定型概率輸入輸出自動機，他們形式化定義了跡差分隱私(trace differential privacy)，并考慮了強和弱兩個版本.直觀上該定義要求，當使用概率自動機實現(xiàn)差分隱私函數(shù)時，對于僅僅相差一個數(shù)據(jù)點的不同輸入，自動機生成的跡的概率分布大致相同.強跡差分隱私和弱跡差分隱私之間的區(qū)別在于前者要求隱私誤差上界必須是固定常量，而后者則允許誤差的上界可根據(jù)查詢的數(shù)量和類型改變.他們揭示了這些定義與傳統(tǒng)差分隱私概念間的關(guān)系，利用展開關(guān)系(unwinding relation)發(fā)展了一種證明技術(shù)，用于驗證給定系統(tǒng)是否滿足跡差分隱私，并在代表性示例中闡明了該技術(shù).需要指出的是，文獻[73]中考慮的是異步系統(tǒng)，即回答查詢的順序未必與提出查詢的順序一致，這種額外的靈活性會對差分隱私產(chǎn)生微妙的影響.基于從函數(shù)隱私性到系統(tǒng)隱私性擴展的類似動機，Tschantz等[74]在交互式系統(tǒng)(interactive systems)中擴展了差分隱私，提出了差分非干擾(differential noninterference)的概念.他們以概率輸入輸出自動機的一種簡單版本——概率輸入輸出遷移系統(tǒng)作為模型，將輸入分為數(shù)據(jù)和查詢，輸出分為可觀測和不可觀測兩部分，基于自動機運行產(chǎn)生的跡，擴展了傳統(tǒng)的差分隱私概念.上述工作[73-74]的完整版本，以及合成推理和差分隱私源代碼的自動驗證等，被寫入長達65頁的技術(shù)報告[75]中.

2.2 基于概率進程代數(shù)的差分隱私研究

許麗麗等[76-79]深入、系統(tǒng)地研究了概率行為和非確定性行為共存的并發(fā)系統(tǒng)隱私保護問題，提出了一些驗證概率并發(fā)系統(tǒng)差分隱私性質(zhì)的新技術(shù).他們以概率CCS為模型，模塊化分析了概率并發(fā)系統(tǒng)的差分隱私性，證明了非確定性選擇、概率選擇和限制等算子是保隱私算子，進而利用并發(fā)理論中的互模擬技術(shù)，重新形式化、改進和發(fā)展了基于概率互模擬和Kantorovich距離的衡量差分隱私的三種偽度量及其性質(zhì)，并利用這些偽度量驗證了概率并發(fā)系統(tǒng)的差分隱私性.另外，他們分別構(gòu)造了分攤互模擬和分攤觀察同余的公理化系統(tǒng)，證明了其可靠性和完備性，這兩個證明系統(tǒng)使得人們能夠僅通過語法層面的操作推導(dǎo)出可觀察的差分隱私行為.眾所周知，概率互相似(即最大的概率互模擬)或近似概率互相似[80]是區(qū)分概率并發(fā)系統(tǒng)行為的有力工具，這里“行為”通常包括系統(tǒng)可執(zhí)行的動作以及能夠到達的狀態(tài)集上的分布，不涉及任何隱私方面的要素.如何將系統(tǒng)的隱私性與經(jīng)典的概率互相似研究相結(jié)合，還有待深入探究.最近，Gruska[81]在一種特殊的概率CCS中，利用傳統(tǒng)差分隱私性概念，給出了幾個基于信息流的量化安全性概念.這些工作與Tschantz等工作的一個共同特點是，將差分隱私定義在概率語言上.這無疑使得實際應(yīng)用中的計算變得極其困難，同時，也難以處理并發(fā)系統(tǒng)中普遍存在的無限長路徑.

2.3 基于概率標號遷移系統(tǒng)的差分隱私研究

受Tschantz等[73-74]和許麗麗[76]工作的啟發(fā)，基于傳統(tǒng)差分隱私和概率互相似的思想，楊建楠等[82-83]進一步研究了概率系統(tǒng)中差分隱私的驗證問題.研究采用一般概率標號遷移系統(tǒng)作為模型，該模型包括確定型概率自動機和概率CCS作為特例.不同于文獻[73-75]中將輸入當作需要保護隱私的數(shù)據(jù)，文獻[82-83]中需要保護隱私的數(shù)據(jù)是系統(tǒng)狀態(tài)，為此，他們在系統(tǒng)狀態(tài)集上預(yù)設(shè)了一個度量，用以刻畫數(shù)據(jù)間的相鄰性，進而通過計算兩個相鄰狀態(tài)在經(jīng)過同一標號遷移之后狀態(tài)分布之間的差別，定義了概率系統(tǒng)中的差分隱私概念.為了量化在不違背差分隱私的前提下，兩個狀態(tài)之間能達到距離的下界，他們給出了下確界度量的概念，定義的下確界度量被證明確實是一個度量，并且這個度量是概率系統(tǒng)中差分隱私的一個度量實例，從而確立了下確界度量的關(guān)鍵性.在此基礎(chǔ)上，借鑒CCS中傳統(tǒng)的Hennessy-Milner邏輯，提出了一個新的二層邏輯，并證明了這個二層邏輯不僅具備刻畫概率互相似的能力，而且能刻畫他們所提出的概率系統(tǒng)中的差分隱私.作為應(yīng)用，他們研究了隱私通信協(xié)議——Crowds協(xié)議的一個變體，并驗證了Crowds協(xié)議滿足他們所提出的差分隱私概念.另外，利用文獻[82]中差分隱私的相關(guān)性質(zhì)，在文獻[83]中給出了一個計算下確界度量的算法.基于給定的概率標號遷移系統(tǒng)和隱私參數(shù)，該算法可計算出下確界度量，得到系統(tǒng)狀態(tài)間的具體距離.

2.4 基于馬爾可夫鏈的差分隱私研究

最近，張立軍課題組[84]和Castiglioni等[85]分別利用馬爾可夫鏈、馬爾可夫決策過程和標號馬爾可夫鏈研究了差分隱私.根據(jù)差分隱私模型是否與環(huán)境交互，文獻[84]分別使用馬爾可夫鏈和馬爾可夫決策過程，形式化描述了傳統(tǒng)差分隱私定義中的隨機機制.在新介紹了一種用于描述差分隱私性質(zhì)的時態(tài)邏輯基礎(chǔ)上，研究了相應(yīng)的模型檢測問題，并討論了模型檢測算法的復(fù)雜性，為數(shù)據(jù)分析師自動化驗證其設(shè)計及實現(xiàn)提供了可能.文獻[85]則基于標號馬爾可夫鏈和經(jīng)典Hennessy-Milner邏輯的一種概率變體，通過在公式上定義語法距離來量化語法差異，從而建立了差分隱私的邏輯刻畫.值得注意的是，這里的差分隱私實際上是傳統(tǒng)差分隱私和局部差分隱私的一種基于度量的推廣[70].在利用行為度量刻畫差分隱私的同時，該文也通過公式上定義的語法距離，分別給出了弱匿名性和廣義互相似度量的邏輯刻畫.需要指出的是，文獻[85]中的標號馬爾可夫鏈也是一種特殊的概率標號遷移系統(tǒng)，其特殊性在于，從每個狀態(tài)出發(fā)，至多只可能有一個遷移.另外，Huang等[86]利用馬爾科夫鏈建模了分布式控制系統(tǒng)，定義了隨機控制機制的差分隱私概念，研究了系統(tǒng)中個體分享信息時差分隱私的代價問題；也有學(xué)者利用隱馬爾可夫模型，發(fā)展了基于概率推測的位置大數(shù)據(jù)隱私保護技術(shù)[9].

3 總結(jié)與展望

當下，數(shù)據(jù)迅速膨脹，大數(shù)據(jù)的應(yīng)用越來越彰顯其優(yōu)勢，然而隱私保護變得越來越困難.差分隱私作為一種重要的隱私保護技術(shù)，在過去十余年受到了廣泛關(guān)注.本文簡要回顧了傳統(tǒng)差分隱私概念提出的背景、定義及其擴展，從形式化方法的視角，介紹了概率系統(tǒng)差分隱私方面的研究進展.更多差分隱私形式化驗證方面的工作，例如，基于類型系統(tǒng)、邏輯公式或Coq證明等方法，可參見文獻[25，84-85，87-88]及其參考文獻.

差分隱私自身的蓬勃發(fā)展以及匿名性、信息泄漏和可靠性等安全屬性在系統(tǒng)層面的研究進展表明，系統(tǒng)的隱私性是大數(shù)據(jù)背景下一個極具前景的研究方向，有著重要的理論意義和潛在的應(yīng)用價值.目前，這方面的研究雖已起步，但仍處于初期探索階段，尚有大量關(guān)鍵問題需要深入而細致地研究.例如，目前考慮的系統(tǒng)模型比較特殊，缺乏統(tǒng)一的一般模型；目前模型的提取主要依賴于手工，未來希望能從軟件系統(tǒng)的源代碼中自動提取系統(tǒng)模型；模塊化驗證和自動化驗證技術(shù)還有待發(fā)展；在系統(tǒng)層面，隱私保護預(yù)算和可用性方面的探討較少；缺少豐富和具體的應(yīng)用實例.