持續(xù)監(jiān)控下差分隱私保護(hù)*

梁文娟 , 陳 紅 , 吳云乘 , 趙 丹 , 李翠平

1(數(shù)據(jù)工程與知識工程國家教育部重點(diǎn)實(shí)驗(yàn)室(中國人民大學(xué)),北京 100872)2(中國人民大學(xué) 信息學(xué)院,北京 100872)3(河南大學(xué) 計算機(jī)與信息工程學(xué)院,河南 開封 475001)

隨著信息技術(shù)的發(fā)展及物聯(lián)網(wǎng)技術(shù)的興起,出現(xiàn)了越來越多的持續(xù)監(jiān)控應(yīng)用場景,如健康管理、交通管理、智能建筑、智能基礎(chǔ)設(shè)施與應(yīng)急響應(yīng)等.在這些場景中,持續(xù)監(jiān)控的成功實(shí)施依賴于對參與者持續(xù)共享的個體信息或大量密集傳感器(例如照相機(jī)、手機(jī)、WiFi 接入點(diǎn)、信標(biāo))傳輸?shù)牧魇綌?shù)據(jù)進(jìn)行實(shí)時監(jiān)控和分析.由于持續(xù)監(jiān)控下持續(xù)共享的數(shù)據(jù)中包含大量個體隱私數(shù)據(jù),如果不對其進(jìn)行隱私保護(hù),會存在隱私泄露的風(fēng)險.用戶對隱私泄露的顧慮會限制參與者分享個體信息的意愿,從而阻礙持續(xù)監(jiān)控應(yīng)用的發(fā)展[1,2].

為保護(hù)用戶數(shù)據(jù)隱私,近兩年,很多國家和企業(yè)針對數(shù)據(jù)保護(hù)和個人信息的隱私保護(hù)問題制定了相關(guān)的法律政策.如:2016 年,歐盟制定的GDPR (general data protection regulation)(https://en.wikipedia.org/wiki/General_Data_Protection_Regulation)中,明確了規(guī)定了用戶對個人信息的知情權(quán)及被遺忘權(quán); 2017 年,我國在《中華人民共和國網(wǎng)絡(luò)安全法》(http://www.spp.gov.cn/xwfbh/wsfbt/201705/t20170509190088.shtml)中,加強(qiáng)了對個人信息保護(hù)的政策規(guī)定.很多信息交流平臺及各種APP,如Facebook、Twitter、美團(tuán)、京東,都制定并發(fā)布了自己的用戶隱私保護(hù)政策.除制定相關(guān)法律政策,隱私保護(hù)問題的相關(guān)技術(shù)研究也逐漸受到重視.

差分隱私是一種定義極為嚴(yán)格的隱私保護(hù)模型,相比于近年來k-匿名[3]、l-多樣性[4]和t-緊密性[5]等需要基于特殊攻擊假設(shè)和背景知識的隱私保護(hù)技術(shù),差分隱私因能夠防止攻擊者擁有任意背景知識下的攻擊并提供有力的隱私保護(hù),受到了極大關(guān)注并被廣泛研究.早期的差分隱私研究[6-10]主要是基于一個可信的管理者持有一個大規(guī)模、靜態(tài)的數(shù)據(jù)集,面向特定查詢?nèi)蝿?wù),研究如何在保證用戶隱私的前提下提高查詢結(jié)果的可用性.由于基于的數(shù)據(jù)集是靜態(tài)的,因此計算都是一次性的.然而,持續(xù)監(jiān)控下差分隱私保護(hù)是一個新的差分隱私應(yīng)用場景.在該場景中,需對動態(tài)數(shù)據(jù)做持續(xù)計算和發(fā)布,如何保護(hù)參與者持續(xù)更新的個體信息面臨重大挑戰(zhàn).下面以幾個具體持續(xù)監(jiān)控下場景示例分析持續(xù)監(jiān)控下差分隱私保護(hù)的必要性及挑戰(zhàn).

在交通實(shí)時監(jiān)控[11,12]中,各種車輛實(shí)時提供位置給Google 等數(shù)據(jù)統(tǒng)計公司,公司統(tǒng)計大量參與者位置信息后,實(shí)時發(fā)布交通區(qū)域圖.基于上述統(tǒng)計結(jié)果,無人駕駛汽車可以進(jìn)行最優(yōu)路線規(guī)劃,城市交通管理部門也可提供實(shí)時事故管理來保證道路通行能力.車輛的一次位置分享,稱為一次事件,如何能提高持續(xù)發(fā)布統(tǒng)計結(jié)果的可用性,同時保護(hù)用戶參與事件不泄露,是隱私保護(hù)目標(biāo).除上述示例,還有很多應(yīng)用場景都需進(jìn)行持續(xù)監(jiān)控下隱私保護(hù).如:在疾病實(shí)時監(jiān)控(https://h1n1.cloudapp.net)中,用戶通過與APP 實(shí)時交互,持續(xù)回答一些關(guān)于癥狀的查詢,可以確定自己是否患有該疾病;APP 通過持續(xù)統(tǒng)計參與用戶的信息,實(shí)時監(jiān)控區(qū)域疾病人數(shù)并提高疾病管理響應(yīng)時間.在能源部門[13-16],智能電網(wǎng)革命根據(jù)對能源供應(yīng)和需求進(jìn)行嚴(yán)格和高粒度的實(shí)時計量,從而提高實(shí)時需求響應(yīng)質(zhì)量,并對不可預(yù)測的能源需求來保證電網(wǎng)的穩(wěn)定性和可靠性.在搜索引擎、在線零售商和社交網(wǎng)絡(luò)中[17],需要持續(xù)統(tǒng)計用戶數(shù)據(jù)來及時發(fā)現(xiàn)有社會價值和經(jīng)濟(jì)價值的信息;在一些政治活動中,網(wǎng)站持續(xù)調(diào)查民眾意見并持續(xù)更新候選人支持率.在上述應(yīng)用中,用戶持續(xù)參與統(tǒng)計,計量設(shè)備持續(xù)輸送流式數(shù)據(jù)都會增加隱私泄露風(fēng)險.如果沒有用戶隱私保護(hù)機(jī)制,參與者分享個體信息的意愿會受到限制.

傳統(tǒng)差分隱私場景下,往往根據(jù)一次參與事件對發(fā)布結(jié)果的最大影響(敏感度)添加噪聲.以簡單計數(shù)任務(wù)為例,一次事件的參與與否所帶來的發(fā)布結(jié)果敏感度為1,添加O(1/ε)的拉普拉斯噪聲即可滿足ε-差分隱私.但在持續(xù)監(jiān)控下(如交通實(shí)時監(jiān)控任務(wù)),一次參與事件不僅對當(dāng)前發(fā)布值有影響,對后續(xù)時刻發(fā)布值都會有影響.假設(shè)時序長度為T,添加O(T/ε)的拉普拉斯噪聲才能實(shí)現(xiàn)一次事件的差分隱私保護(hù).同時,由于時序上往往存在個體的多次參與事件,所帶來的隱私泄露風(fēng)險更大,需添加更多的噪聲才能實(shí)現(xiàn)對多個事件的隱私保護(hù).這就存在以下問題:一是隨著時序長度的增加,發(fā)布結(jié)果可用性變差,如何降低噪聲量對時序長度的依賴面臨較大的挑戰(zhàn);二是為保護(hù)個體的多次參與事件,隱私預(yù)算需在時序上進(jìn)行分配,如何提高時序上隱私預(yù)算利用率也是一個挑戰(zhàn);三是如果面向的是復(fù)雜分析任務(wù)的持續(xù)監(jiān)控保護(hù),因監(jiān)控任務(wù)的發(fā)布敏感度大,所需添加的噪聲量會更大,在這種情況下,如何保證發(fā)布結(jié)果可用性也存在很大挑戰(zhàn).

持續(xù)監(jiān)控下差分隱私保護(hù)研究具有實(shí)際的應(yīng)用背景和重要的研究意義.目前已有一些持續(xù)監(jiān)控下差分隱私保護(hù)的研究成果.本文綜述持續(xù)監(jiān)控下差分隱私保護(hù)的最新研究進(jìn)展和研究方向:一方面對持續(xù)監(jiān)控下差分隱私的定義、實(shí)現(xiàn)機(jī)制和持續(xù)監(jiān)控方案的評估標(biāo)準(zhǔn)進(jìn)行總結(jié);另一方面,對當(dāng)前持續(xù)監(jiān)控下差分隱私保護(hù)的已有研究方案進(jìn)行總結(jié)分析,其中著重總結(jié)滿足event 級、user 級和w-event 級隱私保護(hù)的實(shí)現(xiàn)方案.最后,提出持續(xù)監(jiān)控下差分隱私保護(hù)的未來研究展望.

本文第1 節(jié)總結(jié)持續(xù)監(jiān)控下差分隱私保護(hù)模型.第2 節(jié)總結(jié)主要研究方案分類.第3 節(jié)～第5 節(jié)分別對持續(xù)監(jiān)控下差分隱私保護(hù)的現(xiàn)有研究方案進(jìn)行概括,并對研究方法進(jìn)行對比和分析.第6 節(jié)提出持續(xù)監(jiān)控下差分隱私保護(hù)的未來研究展望.最后,第7 節(jié)總結(jié)全文.

1 持續(xù)監(jiān)控下差分隱私保護(hù)模型

本節(jié)主要對持續(xù)監(jiān)控下的差分隱私定義、實(shí)現(xiàn)機(jī)制及隱私保護(hù)方案評估標(biāo)準(zhǔn)等幾個方面進(jìn)行總結(jié).

1.1 傳統(tǒng)差分隱私定義

設(shè)數(shù)據(jù)集D和D′,D和D′數(shù)據(jù)集屬性結(jié)構(gòu)相同,如果兩者的對稱差|D-D′|=1,則稱D和D′為鄰居數(shù)據(jù)集.也就是說,D和D′相差一條記錄信息.

定義1(差分隱私)[18].給定一個隨機(jī)化的算法M,PM為M的所有可能的輸出集合,如果算法M在任意鄰居數(shù)據(jù)集D和D′上的輸出結(jié)果O(O∈PM)滿足下列不等式,則M滿足ε-差分隱私:

隱私預(yù)算參數(shù)ε表示隱私保護(hù)程度,ε越小,隱私保護(hù)程度越高.

1.2 持續(xù)監(jiān)控下差分隱私定義

直觀地講,持續(xù)監(jiān)控下的數(shù)據(jù)發(fā)布[19]可以看作是在一個離散的時間間隔序列t={t1,t2,…,tn}上,針對每個時間間隔ti,算法重復(fù)接受輸入、計算、然后輸出的過程,而其差分隱私保護(hù)則是對時間序列上這個重復(fù)的過程及發(fā)布結(jié)果序列進(jìn)行差分隱私處理以滿足隱私保護(hù)要求.

在上節(jié)傳統(tǒng)差分隱私定義中,差分隱私要保證基于鄰居數(shù)據(jù)集上統(tǒng)計結(jié)果的概率比值不大于eε,也就意味著在數(shù)據(jù)集中添加或刪除某用戶的參與信息后,發(fā)布結(jié)果變化不大,從而實(shí)現(xiàn)個體在靜態(tài)數(shù)據(jù)集上一次參與事件的隱私保護(hù).在持續(xù)監(jiān)控下,差分隱私也要保證基于鄰居數(shù)據(jù)集的統(tǒng)計結(jié)果滿足上述要求.但該場景中,用戶在不同的時間會有多次的參與事件.隨著參與事件的增加,隱私泄露風(fēng)險往往更大.如何在時序上對用戶多次參與事件進(jìn)行保護(hù),是持續(xù)監(jiān)控下隱私保護(hù)的目標(biāo).如圖1 中持續(xù)監(jiān)控場景示例,在時間序列t={t1,t2,…,tn}上,針對每個ti,監(jiān)控該時刻位置L的人數(shù).

Fig.1 Example of continual monitoring圖1 持續(xù)監(jiān)控場景示例

假設(shè)圖1 中Di代表ti時刻的數(shù)據(jù)集,Di中每行代表一個參與者在該時刻是否在位置L,其值為0 或1:1 表示在,0 表示不在.在持續(xù)監(jiān)控下,數(shù)據(jù)集為一個動態(tài)序列D={D1,D2,…,Dn}.每個時刻ti需要發(fā)布數(shù)據(jù)Di中位置L屬性列上的count 計數(shù)值.用戶在某時刻Di中的一條記錄稱之為一次參與事件.隨著時間的更新,每個Di中都會存在某個參與者的參與事件,也就是說,D中存在用戶的多次參與事件,它們是持續(xù)監(jiān)控下要保護(hù)的用戶隱私.

結(jié)合具體問題的監(jiān)控事件,持續(xù)監(jiān)控下差分隱私保護(hù)需要對基于監(jiān)控事件數(shù)據(jù)流的統(tǒng)計分析做差分隱私保護(hù)處理.假設(shè)用S={x1x2x1x1x3…}表示一個持續(xù)監(jiān)控事件數(shù)據(jù)流,X表示數(shù)據(jù)流S中元素的值域,xi∈X表示某用戶一次參與事件.持續(xù)監(jiān)控下差分隱私保護(hù)是基于鄰居數(shù)據(jù)流進(jìn)行定義.根據(jù)現(xiàn)有方案能提供的差分隱私保護(hù)級別,鄰居數(shù)據(jù)流分為3 種級別:event-級、user-級和w-event 級.3 種隱私保護(hù)級別的鄰居數(shù)據(jù)流及相應(yīng)的差分隱私保護(hù)定義如下.

1.2.1 Event-級差分隱私

Event 級鄰居數(shù)據(jù)流:在持續(xù)監(jiān)控下,如果存在x,x′∈X,從S中任意將某個x替換為x′后變?yōu)镾′,稱S和S′為持續(xù)監(jiān)控下event 級鄰居數(shù)據(jù)流.其含義是從監(jiān)控數(shù)據(jù)流中添加(刪除)某用戶的一次參與事件.

定義2(Event-級差分隱私)[20].給定一個隨機(jī)化的算法M,PM為M的所有可能的輸出集合,對于算法M在任意event 鄰居數(shù)據(jù)流S和S′上任意的輸出結(jié)果O(O∈PM),如果其滿足下列不等式,則M滿足ε-差分隱私:

Event 級差分隱私保護(hù)能保證在持續(xù)監(jiān)控生命期中,用戶的一次事件對整個監(jiān)控結(jié)果影響受隱私預(yù)算ε的控制.ε越小,隱私泄露風(fēng)險越低;反之越高.

1.2.2 User-級差分隱私

User 級鄰居數(shù)據(jù)流:在持續(xù)監(jiān)控下,如果存在x,x′∈X,從S中將某用戶對應(yīng)的所有事件x替換為x′后變?yōu)镾′,稱S和S′為持續(xù)監(jiān)控下的user 級鄰居數(shù)據(jù)流.其含義是,從監(jiān)控數(shù)據(jù)流中添加(刪除)某用戶的所有參與事件.

定義3(User-級差分隱私)[20].給定一個隨機(jī)化的算法M,PM為M的所有可能輸出集合,對于算法M在任意user 級鄰居數(shù)據(jù)流S和S′上的輸出結(jié)果O(O∈PM)滿足下列不等式,則M滿足ε-差分隱私:

User 級差分隱私保護(hù)是對持續(xù)監(jiān)控生命期中某用戶的所有參與事件對整個監(jiān)控結(jié)果的影響進(jìn)行控制,也就是對持續(xù)發(fā)布統(tǒng)計結(jié)果的隱私泄露風(fēng)險進(jìn)行了限制.

1.2.3 w-event 級差分隱私

w-event 級鄰居數(shù)據(jù)流:給定一個正整數(shù)w,如果兩個流前綴St和滿足:(i) 對于每個i∈[t]且都有是相鄰的;(ii) 對于每個,且有i2-i1+1≤W,則稱兩個流前綴St和是w-event 級鄰居數(shù)據(jù)流.

定義4(w-event 級差分隱私)[21].給定一個隨機(jī)化的算法M,PM為M的所有可能的輸出集合,對于算法M在任意w-event 級鄰居數(shù)據(jù)流St和St′上的任意的輸出結(jié)果O(O∈PM)滿足下列不等式,則M滿足ε-差分隱私:

w-event 級隱私可以看作是user 級隱私的拓展,它實(shí)現(xiàn)在任意w滑動窗口內(nèi)用戶的user 級隱私保護(hù).它也是event 和user 級的一個中間級隱私保護(hù),當(dāng)w=1 時,保護(hù)級別下降為event 級;當(dāng)w為T時,則為user 級隱私.

在上述的3 種定義中,event 級所提供的隱私保護(hù)強(qiáng)度最小,user 級隱私保護(hù)強(qiáng)度最大,而w-event 級隱私保護(hù)是上述兩種方案的折衷.隱私預(yù)算參數(shù)ε用來控制對持續(xù)監(jiān)控下基于不同級別鄰居數(shù)據(jù)集的輸出結(jié)果的概率比值,也就是方案的隱私保護(hù)程度,ε越小,隱私保護(hù)程度越高;反之越低.ε的取值往往要結(jié)合監(jiān)控所需要達(dá)到的隱私保護(hù)度和發(fā)布結(jié)果的可用性兩個因素進(jìn)行綜合的衡量.

1.3 噪聲機(jī)制

噪聲機(jī)制是實(shí)現(xiàn)差分隱私保護(hù)的主要技術(shù),常用的噪聲添加機(jī)制分別為拉普拉斯機(jī)制[22]與指數(shù)機(jī)制[23].添加的噪聲量與查詢?nèi)蝿?wù)的全局敏感度和隱私預(yù)算大小密切相關(guān).

定義5(全局敏感度)[22].設(shè)有函數(shù)f:D→Rd,輸入為數(shù)據(jù)集,輸出為d維實(shí)數(shù)向量.對于任意鄰居數(shù)據(jù)D和D′:稱為函數(shù)f的全局敏感度,||f(D)-f(D′)||1指的是f(D)和f(D′)的1-階范數(shù)距離.函數(shù)的全局敏感度由函數(shù)本身決定,不同的函數(shù)有不同的全局敏感度.敏感度越小,所需添加的噪聲越少.

定理1(Laplace 機(jī)制)[22].給定數(shù)據(jù)集D,設(shè)有函數(shù)f:D→Rd,其敏感度為Δf,若算法M的輸出結(jié)果滿足下列不等式,則M滿足ε-差分隱私:

拉普拉斯機(jī)制只適合于數(shù)值型輸出的查詢函數(shù).許多應(yīng)用中查詢輸出為非數(shù)值型.對此,McSherry 等人提出了指數(shù)機(jī)制.其實(shí)現(xiàn)核心是設(shè)計打分函數(shù)u,為輸出域中每個輸出項(xiàng)打分,分值越高,被選擇輸出的概率越大.

定理2(指數(shù)機(jī)制)[23].設(shè)定一個打分函數(shù)u:(D×O)→R,如果算法M滿足下列等式,則M滿足ε-差分隱私:

其中,r∈O,表示從輸出域O中選擇的輸出項(xiàng);Δu為打分函數(shù)u的全局敏感度.

1.4 組合特性

差分隱私保護(hù)具有兩個組合性質(zhì):序列組合性和并行組合性,在持續(xù)監(jiān)控下仍然適用.

性質(zhì)1(序列組合性)[22].設(shè)有算法M1,M2,…,Mn,其隱私預(yù)算分別為ε1,ε2,…,εn.那么對于同一數(shù)據(jù)集D,由這些算法構(gòu)成的組合算法M(M1(D),M2(D),…,Mn(D))提供差分隱私.

性質(zhì) 2(并行組合性)[22].算法M1,M2,…,Mn,其隱私預(yù)算分別為ε1,ε2,…,εn.那么對于不相交的數(shù)據(jù)集D1,D2,…,Dn,由這些算法構(gòu)成的組合算法M(M1(D1),M2(D2),…,Mn(Dn))提供maxεi-差分隱私保護(hù).

序列組合性表示對同一數(shù)據(jù)集多個差分隱私保護(hù)算法的序列組合算法,所提供的保護(hù)水平為全部隱私預(yù)算之和.并行組合性表示對不同數(shù)據(jù)集保護(hù)的多個差分隱私保護(hù)算法的組合算法,所提供的保護(hù)水平為算法中的最低的保護(hù)水平,也就是隱私預(yù)算的最大值.

1.5 持續(xù)監(jiān)控下差分隱私保護(hù)方案評估

滿足差分隱私保護(hù)的方案在實(shí)現(xiàn)隱私保護(hù)同時,也要兼顧發(fā)布結(jié)果的可用性.因此,方案的評估包含以下兩個方面.

(1) 隱私保護(hù)評估:差分隱私處理核心是隱私預(yù)算分配和敏感度計算;隱私預(yù)算ε代表著發(fā)布任務(wù)的隱私保護(hù)程度.隱私預(yù)算一旦耗盡,方案的差分隱私保護(hù)特性將被破壞.評估方案是否能實(shí)現(xiàn)隱私保護(hù),主要是對其差分隱私處理過程中的隱私預(yù)算分配策略進(jìn)行分析,計算發(fā)布過程所分配的隱私預(yù)算是否符合隱私預(yù)算的要求,同時分析敏感度的計算是否正確;

(2) 算法結(jié)果誤差:為評估方案發(fā)布結(jié)果的可用性,往往計算真實(shí)結(jié)果與經(jīng)差分隱私處理后的結(jié)果之間的誤差.根據(jù)持續(xù)監(jiān)控下問題的不同,誤差采用的衡量方法往往不同.如:簡單聚集統(tǒng)計發(fā)布問題中,常對發(fā)布結(jié)果誤差上界進(jìn)行證明,并在實(shí)驗(yàn)評估中采用相對誤差、絕對誤差等度量標(biāo)準(zhǔn);而其他問題會根據(jù)自身問題特點(diǎn)定義不同的標(biāo)準(zhǔn),如軌跡保護(hù)中,采用JS 散度、F-Score 等可用性衡量標(biāo)準(zhǔn).

2 持續(xù)監(jiān)控下差分隱私保護(hù)方案分類

持續(xù)監(jiān)控下差分隱私保護(hù)研究對推動智能信息技術(shù)的發(fā)展具有重要的意義,其隱私保護(hù)問題也是急需解決的問題.本文將現(xiàn)有持續(xù)監(jiān)控下差分隱私保護(hù)方案分為3 類,分別為持續(xù)監(jiān)控下event 級別保護(hù)方案、持續(xù)監(jiān)控下user 級別保護(hù)方案和持續(xù)監(jiān)控下w-event 級別保護(hù)方案.其中:持續(xù)監(jiān)控下event 級別差分隱私保護(hù)方案主要圍繞單值計數(shù)和持續(xù)發(fā)布、直方圖持續(xù)發(fā)布、heavy hitter 持續(xù)監(jiān)控和位置發(fā)布等持續(xù)監(jiān)控問題,針對如何降低持續(xù)發(fā)布的高敏感度提出相應(yīng)的解決方案;持續(xù)監(jiān)控下user 級別和w-event 級別的保護(hù)方案主要圍繞簡單聚集信息持續(xù)發(fā)布、分布式數(shù)據(jù)流閾值函數(shù)持續(xù)監(jiān)控、集值對更新發(fā)布和軌跡發(fā)布問題,針對如何提高時序上隱私預(yù)算的利用率,同時降低發(fā)布任務(wù)的高敏感度提出相應(yīng)的解決方案.每個分類對應(yīng)的方案示例見表1.

Table 1 Existing research on differential privacyunder continual observation表1 持續(xù)監(jiān)控下差分隱私保護(hù)方案分類

3 持續(xù)監(jiān)控下event-級隱私保護(hù)方案

Event-級別持續(xù)監(jiān)控隱私保護(hù)主要基于count 計數(shù)的發(fā)布任務(wù)進(jìn)行研究,主要包括單值計數(shù)和的持續(xù)監(jiān)控保護(hù)、直方圖持續(xù)發(fā)布的隱私保護(hù)、heavy hitter 和位置信息發(fā)布等特定任務(wù)的持續(xù)監(jiān)控保護(hù).

3.1 單值計數(shù)和持續(xù)監(jiān)控保護(hù)

目前,大部分event-級別的持續(xù)監(jiān)控保護(hù)研究都是基于單值計數(shù)和的持續(xù)監(jiān)控保護(hù)問題,如圖2 所示,假設(shè)存在一個隨時間不斷更新的事件(event)數(shù)據(jù)流-基于動態(tài)數(shù)據(jù)抽象得到,其中,0 代表監(jiān)控的事件沒有發(fā)生,1 代表事件發(fā)生.如何能持續(xù)更新發(fā)布數(shù)據(jù)流中1 的計數(shù)和,同時保證持續(xù)發(fā)布滿足差分隱私要求是隱私保護(hù)目標(biāo).該問題形式化如下:時間序列上對應(yīng)的事件數(shù)據(jù)流σ∈{0,1}N,N={1,2,3…,n}為一組正整數(shù)的集合;σt∈{0,1}N代表σ的長度為T的前綴數(shù)據(jù)流;[T]={1,2,3,…,T}表示數(shù)據(jù)流長度;σ(t)∈{0,1}表示時間ti(i∈N)對應(yīng)的數(shù)據(jù)流段中1 的計數(shù)值.表示數(shù)據(jù)流σt中1 的計數(shù)和.針對該問題,持續(xù)監(jiān)控下隱私保護(hù)目標(biāo):對每個時間ti,持續(xù)更新發(fā)布c(t),持續(xù)發(fā)布過程滿足定義2 中event-級差分隱私要求.

Fig.2 Continual release of the running sum圖2 單值計數(shù)和的持續(xù)發(fā)布

單值計數(shù)和問題在很多應(yīng)用場景上都可適用,如特定位置的交通實(shí)時監(jiān)控、特定網(wǎng)頁的用戶點(diǎn)擊行為實(shí)時監(jiān)控、傳感器網(wǎng)絡(luò)中某IP 地址訪問的持續(xù)監(jiān)控、智能基礎(chǔ)設(shè)施的持續(xù)監(jiān)控、疾病控制中心對患某種疾病人數(shù)的持續(xù)監(jiān)控、滿足特定謂詞條件的持續(xù)查詢等等.

3.1.1 基本發(fā)布方案

· 方案1

方案1 是文獻(xiàn)[18,22]中差分隱私實(shí)現(xiàn)機(jī)制的直接應(yīng)用,其基本思想是:根據(jù)已知的數(shù)據(jù)流長度T,在每個發(fā)布時t∈T,對前綴數(shù)據(jù)流σt的真實(shí)計數(shù)和c(t)加上拉普拉斯噪聲后發(fā)布.在該方案中,每個發(fā)布時刻t分配的隱私預(yù)算為ε,發(fā)布任務(wù)的敏感度為T.隨機(jī)化算法M在每個時間t生成一個獨(dú)立隨機(jī)噪聲Lap(T/ε),發(fā)布結(jié)果為c(t)+Lap(T/ε).根據(jù)差分隱私的組合性質(zhì),該方案滿足event 級ε-差分隱私.經(jīng)分析證明,發(fā)布結(jié)果的漸近誤差上界為O(T/ε).方案有如下兩個缺點(diǎn):(1) 由于每個發(fā)布時刻添加的噪聲量與數(shù)據(jù)流長度T成正比,所以數(shù)據(jù)流長度越大,算法發(fā)布結(jié)果的可用性越差;(2) 由于要根據(jù)數(shù)據(jù)流長度來對發(fā)布結(jié)果添加噪聲,該方案只能對長度上限已知的數(shù)據(jù)流進(jìn)行隱私保護(hù),無法對無限數(shù)據(jù)流進(jìn)行差分隱私保護(hù).

· 方案2

方案2 則是差分隱私實(shí)現(xiàn)機(jī)制[22]與文獻(xiàn)[24]思想的結(jié)合應(yīng)用,其基本思想是:在每個時刻t∈T,對t對應(yīng)的數(shù)據(jù)流段中的真實(shí)計數(shù)值σ(t)進(jìn)行噪聲干擾.每個時間t所分配的隱私預(yù)算為ε,由于σ(t)只跟當(dāng)前時間有關(guān),跟前后時間所對應(yīng)的計數(shù)值都無關(guān),所以計數(shù)任務(wù)的敏感度為1.因此在每個時刻,隨機(jī)化算法M都生成一個獨(dú)立隨機(jī)噪聲Lap(1/ε),對σ(t)加上拉普拉斯噪聲為αt=σ(t)+Lap(1/ε).由于監(jiān)控目標(biāo)是每個時刻的計數(shù)和c(t),所以差分隱私保護(hù)機(jī)制M在時刻t的發(fā)布結(jié)果為.經(jīng)分析證明,該方案漸近誤差上界為O(T/ε).該方案雖然發(fā)布結(jié)果可用性比方案1 有所提高,但依然對T有較大依賴關(guān)系.

· Two-level 方案[25]

為降低發(fā)布結(jié)果誤差對T的依賴,Two-level 方案對方案2 進(jìn)行了拓展,核心思想是:對數(shù)據(jù)流進(jìn)行分組,每組是一個連續(xù)的時間區(qū)間.不夠一組的元素采用方案2 進(jìn)行差分隱私保護(hù);分組之上,將每個組計數(shù)和看作一個元素,再次采用方案2 思想對每組計數(shù)進(jìn)行隱私保護(hù).假設(shè)每組大小為B,數(shù)據(jù)流長度為T,在發(fā)布時刻ti,首先將ti拆分為組:ti=qB+r.然后以組為單位,對每個組計數(shù)加上Lap(1/ε)噪聲:.不夠一組的元素(r個),每個元素加Lap(1/ε)噪聲αi=σ(i)+Lap(1/ε).因此,每個時刻ti的發(fā)布結(jié)果為假設(shè)B=3,ti=7,則分組如圖3 所示,β1,β2和α7都被加上拉普拉斯噪聲Lap(1/ε),輸出計數(shù)值為M(7)=β1+β2+α7.

Fig.3 Example of Two-level圖3 Two-level 方案示例

由于每個時刻ti的值σ(ti)只會影響其所在的組或αt,Two-level 滿足event 級2ε-差分隱私.經(jīng)分析證明,該方案發(fā)布結(jié)果漸近誤差上界為.Two-level 方案降低了對T的依賴,但降低了隱私保護(hù)強(qiáng)度.

3.1.2 基于二叉樹的發(fā)布方案

上述 3 種基本方案的發(fā)布結(jié)果誤差對數(shù)據(jù)流長度T都有較大的依賴性,發(fā)布結(jié)果可用性較低.Tree Counter[20,25]方案基于上述問題進(jìn)行了改進(jìn),其核心思想是:將長度為T的數(shù)據(jù)流構(gòu)造成一棵完全二叉樹,樹的葉節(jié)點(diǎn)存儲ti時刻的元素計數(shù)值σ(ti),內(nèi)部節(jié)點(diǎn)Psum則存儲其覆蓋區(qū)間[i,j]的葉節(jié)點(diǎn)的計數(shù)和,其值為Psum=.因此,一個高度為l的Psum節(jié)點(diǎn)對應(yīng)2l個葉節(jié)點(diǎn)的計數(shù)和.如圖4 所示,[1,4]代表的Psum節(jié)點(diǎn)高度為2,代表數(shù)據(jù)流[1,4]區(qū)間內(nèi)元素的計數(shù)和.

Fig.4 Example of Tree Counter[25]圖4 Tree Counter 方案示例[25]

對任意時刻ti,c(ti)都可以表示為一組Psum節(jié)點(diǎn)值的求和.如圖4 中:當(dāng)ti=7 時,c(7)可以由Psum節(jié)點(diǎn)[1,4],[5,6]和σ(7)求和.根據(jù)二叉樹的性質(zhì),ti時刻發(fā)布值的計算中參與求和的Psum節(jié)點(diǎn)數(shù)最多為logT+1.根據(jù)Psum節(jié)點(diǎn)計算c(ti),發(fā)布任務(wù)的敏感度為logT+1.算法為每個參與求和的Psum節(jié)點(diǎn)添加滿足Lap((logT+1)/ε)的噪聲,即可保證發(fā)布結(jié)果滿足event 級ε-差分隱私.可以看出:采用二叉樹的發(fā)布方案,使持續(xù)發(fā)布任務(wù)的敏感度由O(t)降為了O(logT).經(jīng)分析證明,Tree Counter 發(fā)布結(jié)果的漸近誤差上界為O((logT)1.5/ε),進(jìn)一步提高了發(fā)布結(jié)果的可用性.但其有以下兩個缺點(diǎn):(1) 處理的數(shù)據(jù)流必須是有限長度,不能處理無限長的情況;(2) 提供的是event 級別的隱私保護(hù),隱私保護(hù)級別較弱.

針對Tree Counter 第1 個缺點(diǎn),文獻(xiàn)[25]以Tree Counter 和two-level 兩種機(jī)制為基礎(chǔ),提出一種混合機(jī)制Hybrid 機(jī)制,該方案可以實(shí)現(xiàn)對無限數(shù)據(jù)流event 級的差分隱私保護(hù).其主要思想是,將所有待發(fā)布的時間分為兩類:第1 類是可以表示為2 的冪集的時間點(diǎn)集合,第2 類是非2 冪集的時間點(diǎn)集合.對每個發(fā)布時刻ti,隨機(jī)化發(fā)布機(jī)制H根據(jù)ti類別采用不同的保護(hù)機(jī)制.如果ti為2 的冪級,采用L機(jī)制(改進(jìn)的two-level 機(jī)制)發(fā)布;如果ti不為2 的冪級,采用M(Tree Counter 機(jī)制)發(fā)布.L機(jī)制算法思想類似于two-level 機(jī)制,不同的是:two-level 機(jī)制采用定長分組,而L機(jī)制則采用變長分組,只要時間點(diǎn)為2 的冪集(2k(k∈Z)),就把此前的時間區(qū)間分為一組.基于分組,添加Lap(1/ε).對非2 的冪集的時刻ti,如ti∈(2k,2k+1)則采用長度上限為T=2k的M(Tree Counter)機(jī)制發(fā)布方案.假設(shè)τ=ti-T,則ti時刻的發(fā)布為H(ti)=L(T)+MT(τ).Hybrid 機(jī)制提高了發(fā)布結(jié)果可用性,也解決了Tree Counter只能處理有限長數(shù)據(jù)流的問題.

雖然上述方案解決了數(shù)據(jù)流長度受限問題,但還有以下缺點(diǎn):(1) 由于發(fā)布結(jié)果包含噪聲,出現(xiàn)了相鄰時刻發(fā)布結(jié)果不滿足實(shí)際統(tǒng)計約束的不一致問題;(2) 面向數(shù)據(jù)流的數(shù)據(jù)統(tǒng)計涉及到中間統(tǒng)計值的保存,如果中間值被攻擊者捕獲,則不能提供有力的保護(hù).針對缺點(diǎn)(1),文獻(xiàn)[25]對單值計數(shù)和持續(xù)發(fā)布中的一致性問題進(jìn)行了定義.針對缺點(diǎn)(2),文獻(xiàn)[20,25]設(shè)計了可以實(shí)現(xiàn)Pan-privacy 的持續(xù)發(fā)布方案,Pan-privacy 的含義指攻擊者即使獲取了數(shù)據(jù)流處理的中間值,結(jié)合持續(xù)觀察的發(fā)布結(jié)果,也無法判斷個體事件是否發(fā)生,從而實(shí)現(xiàn)了隱私與安全的結(jié)合.

在很多實(shí)時監(jiān)控的應(yīng)用場景中,往往近期發(fā)生的事件對監(jiān)控更有意義,而發(fā)生時間較遠(yuǎn)的事件對監(jiān)控價值較低.針對這個問題,文獻(xiàn)[26]提出了基于衰減的單值計數(shù)和持續(xù)監(jiān)控保護(hù)方案DecayedSum,并分析證明了方案中發(fā)布結(jié)果誤差上界.方案中提出了3 種數(shù)據(jù)衰減模型的差分隱私保護(hù)機(jī)制,分別是基于滑動窗口的保護(hù)、基于指數(shù)機(jī)制衰減和基于多項(xiàng)式衰減的保護(hù).第1 種方案提出了對最近W寬度窗口內(nèi)的單值統(tǒng)計和發(fā)布的event級ε差分隱私方案,發(fā)布結(jié)果誤差上界為O(logW/ε).第2 種方案提出了基于指數(shù)衰減模型單值計數(shù)和持續(xù)發(fā)布的event 級ε-差分隱私方案,發(fā)布結(jié)果誤差上界為O(log(α/(1-α))/ε),其中,α為指數(shù)衰減因子.第3 種方案提出了基于多項(xiàng)式衰減模型單值計數(shù)和持續(xù)發(fā)布的event 級ε-差分隱私保護(hù)方案,發(fā)布結(jié)果誤差上界為

其中,c為多項(xiàng)式衰減因子,β為錯誤控制參數(shù).3 種隱私保護(hù)方案都是基于Tree Counter 方案的拓展.DecayedSum可以實(shí)現(xiàn)對無限長數(shù)據(jù)流的隱私保護(hù),更符合實(shí)時監(jiān)控的場景.

3.1.3 基于分區(qū)的發(fā)布方案

基本方案和二叉樹方案中沒有考慮數(shù)據(jù)流自身特點(diǎn)對發(fā)布結(jié)果的影響.文獻(xiàn)[27]提出了一種適合稀疏數(shù)據(jù)流的自適應(yīng)分區(qū)方案Partition,該方案通過結(jié)合數(shù)據(jù)流的變化特點(diǎn)降低發(fā)布問題的敏感度,提高發(fā)布結(jié)果的可用性.Partition 的基本思想為:按提前設(shè)定的閾值,將長度為T的稀疏數(shù)據(jù)流劃為一組連續(xù)分區(qū)的集合,每個分區(qū)的計數(shù)和基本相同,為接近于閾值的一個統(tǒng)計值.假設(shè)分區(qū)后分區(qū)個數(shù)為m(m<

在發(fā)布某個時刻t的統(tǒng)計值時,結(jié)合Tree Counter 的思想,將每個分區(qū)的統(tǒng)計值作為葉節(jié)點(diǎn),構(gòu)造完全二叉樹,發(fā)布結(jié)果的計算就依賴于每個分區(qū)的結(jié)果統(tǒng)計.經(jīng)分析證明,算法的漸近誤差上界降為O(logT+(log2n)/ε).其中,n是數(shù)據(jù)流中1 的總計數(shù),在稀疏數(shù)據(jù)流中,n<

Fig.5 Example of adaptive partition圖5 Partition 自適應(yīng)分區(qū)示例

文獻(xiàn)[28]提出的PeGaSus 方案同樣采用分區(qū)思想對面向數(shù)據(jù)流的持續(xù)監(jiān)控問題進(jìn)行了研究.PeGaSus 方案由 3 個構(gòu)件組成:Pertuber,Grouper 和 Smoother.為保證ε-差分隱私,隱私預(yù)算ε分為兩部分:ε=εp+εg.εp用于Pertuber,εg用于Grouper,Smoother 是后處理過程,不需要分配隱私預(yù)算(如圖6 所示).

Fig.6 Process of PeGaSus[30]圖6 PeGaSus 過程圖[30]

Pertuber 用來對每個時刻t的計數(shù)進(jìn)行噪聲處理:σ(t)+Lap(1/εp).Grouper 根據(jù)數(shù)據(jù)特點(diǎn)對數(shù)據(jù)進(jìn)行自適應(yīng)的分區(qū),分區(qū)原則是將統(tǒng)計值變化不大的連續(xù)時間分成一個區(qū),數(shù)據(jù)流被分成一組分區(qū)的集合.為了捕捉統(tǒng)計值的變化,方案設(shè)計一個偏差函數(shù)用來獲取分區(qū)值的變化信息;如果變化大于設(shè)定的閾值θ,則當(dāng)前分區(qū)分配完畢;從下個時刻開始,重新開始新分區(qū)的劃分.分區(qū)后,Smoother 結(jié)合分區(qū)結(jié)果和Pertuber 的噪聲統(tǒng)計值,采用分區(qū)平均值、中位數(shù)等平滑處理技術(shù),提高特定查詢?nèi)蝿?wù)發(fā)布結(jié)果可用性.

PeGaSus 與Partition 分區(qū)策略不同點(diǎn)在于:(1) Partition 是將數(shù)據(jù)流分為一組連續(xù)分區(qū),每個分區(qū)內(nèi)的計數(shù)和基本相同;(2) 而PeGaSus 分區(qū)的思想是將計數(shù)值相似的的時間點(diǎn)分到一個分區(qū),不同分區(qū)間計數(shù)和可能變化較大;(3) Partition 基于分區(qū)的計數(shù)和做噪聲處理,而PeGaSus 則是對每個時間點(diǎn)的計數(shù)值做噪聲處理;(4) PeGaSus 采用了偏差函數(shù)幫助Grouper 分區(qū),而Partition 是通過提前設(shè)定的閾值進(jìn)行分區(qū);(5) Partition 只針對單值計數(shù)和發(fā)布問題做隱私保護(hù),但PeGaSus 面向的是多種查詢?nèi)蝿?wù)類型,如多目標(biāo)持續(xù)查詢和多時間跨度的持續(xù)查詢等.

PeGaSus 方案中,因其支持多種查詢類型,提出對具有層次關(guān)系的查詢?nèi)蝿?wù)關(guān)系進(jìn)一步降低查詢?nèi)蝿?wù)的敏感度,提高發(fā)布結(jié)果的可用性.文獻(xiàn)[29]則也利用查詢?nèi)蝿?wù)之間的關(guān)系來降低查詢結(jié)果的噪聲,文中提出了兩種方案.

· SampleDP 是針對查詢?nèi)蝿?wù)的步長滿足一定約束條件(長步長是短步長的整數(shù)倍)的情況下,采用動態(tài)規(guī)劃算法找出能使添加噪聲量最小的步長組合;

· 而SampleEMD 是將第1 種方案擴(kuò)展到更一般的情況:采用EMD 相似性計算方法來選取與原有步長集分布相似的抽樣步長集,達(dá)到降低噪聲、提高查詢結(jié)果可用性的目的.

3.2 直方圖發(fā)布的持續(xù)監(jiān)控保護(hù)

直方圖是一種直觀的數(shù)據(jù)分布表示形式,它按照某屬性或?qū)傩约瘜?shù)據(jù)集信息劃分成不相交的桶,每個桶內(nèi)有一個統(tǒng)計數(shù)字表示其特征.直方圖的持續(xù)發(fā)布是基于時間序列上的動態(tài)數(shù)據(jù),持續(xù)發(fā)布直方圖統(tǒng)計信息.圖7 表示在時間序列上,持續(xù)監(jiān)控位置L1～L7 上人數(shù)的直方圖示例.

文獻(xiàn)[30]針對無限數(shù)據(jù)流中直方圖的持續(xù)發(fā)布問題,提出一種滿足event 級的隱私保護(hù)方案RetroGroup.跟單值計數(shù)和持續(xù)監(jiān)控保護(hù)方案一樣,RetroGroup 在時間序列上每個發(fā)布點(diǎn)所分配的隱私預(yù)算也為ε.但為了提高時序上發(fā)布結(jié)果的可用性,RetroGroup 采用回溯分組來降低持續(xù)發(fā)布任務(wù)的敏感度.其基本思想是:根據(jù)相鄰時間直方圖的相似性,將發(fā)布數(shù)據(jù)相似的連續(xù)時間分為一組,以組為單位對要發(fā)布的直方圖加拉普拉斯噪聲.因此,RetroGroup 方案包含兩個過程:相似性計算和直方圖發(fā)布.為滿足ε差分隱私,相似性計算過程分配的隱私預(yù)算為ε1,發(fā)布過程分配隱私預(yù)算為ε2=ε-ε1.根據(jù)差分隱私的序列組合性質(zhì),該方案滿足ε-差分隱私.

Fig.7 Example of histogram publication under continual monitoring圖7 持續(xù)監(jiān)控下直方圖發(fā)布示例

假設(shè)用Hi代表ti時刻要發(fā)布的直方圖,Hi[j]表示直方圖的第j個桶的統(tǒng)計值.在每個時刻ti,計算直方圖的每個桶Bj的統(tǒng)計值Hi[j]和Hi-1[j]的差異d[j],將d[j]變化不大的連續(xù)時間分為一組G(Bj).為了提高相似性計算效率,方案采用抽樣技術(shù)在提高效率的同時增大隱私預(yù)算的效用,從而會降低拉普拉斯噪聲.但抽樣也會帶來抽樣誤差,因此方案中對抽樣誤差和差分隱私誤差做了定量化分析.基于相似性計算進(jìn)行分組后,每個組包含多個時間點(diǎn),大小為|G(Bj)|.基于分組發(fā)布結(jié)果時,對組內(nèi)的平均計數(shù)值添加的拉普拉斯噪聲量由Lap(1/ε2)降為了Lap(1/(|G(Bj)|ε2)),發(fā)布結(jié)果可用性得到了提高.

RetroGroup 與PeGaSus 分區(qū)有些相似,都是將數(shù)據(jù)變化不大的時間序列分為一組;但RetroGroup 是基于分組平均值做噪聲處理,而PeGaSus 是基于每個時間點(diǎn)值做噪聲處理,而后針對特定查詢?nèi)蝿?wù)進(jìn)行分組平滑處理.

3.3 Heavy hitter的持續(xù)監(jiān)控保護(hù)

Heavy hitter 的持續(xù)監(jiān)控是指對數(shù)據(jù)流中的元素及其頻數(shù)進(jìn)行統(tǒng)計,實(shí)時發(fā)布超出閾值的元素及其頻數(shù),即heavy hitter.在該問題中,heavy hitter 元素及其頻數(shù)都是需要保護(hù)的隱私.文獻(xiàn)[31]針對3 種監(jiān)控場景提出了對應(yīng)的隱私保護(hù)方案:面向單數(shù)據(jù)流heavy hitter 持續(xù)監(jiān)控的隱私保護(hù)方案PMG、面向單數(shù)據(jù)流滑動窗口內(nèi)heavy hitter 持續(xù)監(jiān)控的隱私保護(hù)方案PCC 和面向分布式數(shù)據(jù)流滑動窗口內(nèi)heavy hitter 持續(xù)監(jiān)控的隱私保護(hù)方案PDCH-LU.

PMG 方案基于未做隱私保護(hù)的面向數(shù)據(jù)流中heavy hitter 統(tǒng)計的算法MG[32],采用差分隱私技術(shù)對其進(jìn)行隱私保護(hù).在MG 算法中,給定數(shù)據(jù)流長度T和錯誤控制參數(shù)λ,算法執(zhí)行過程中會持續(xù)維護(hù)一個長度為β=O(1/λ)的計數(shù)器組,通過計數(shù)值可以統(tǒng)計出heavy hitter 及其頻數(shù).為滿足event 級ε-差分隱私,PMG 在每個發(fā)布時刻分配的隱私預(yù)算為ε,由于MG 算法的發(fā)布敏感度為β,因此對發(fā)布結(jié)果添加隱私預(yù)算為ε,敏感度為β的噪聲,即可滿足ε差分隱私保護(hù).

基于PMG,PCC方案按照時間寬度W將整個數(shù)據(jù)流分為了一系列的窗口.在每個窗口內(nèi),采用二叉樹結(jié)構(gòu)統(tǒng)計其窗口內(nèi)的heavy hitter,其中,二叉樹葉節(jié)點(diǎn)代表w0=λw/4 個時間點(diǎn)的統(tǒng)計值,內(nèi)部節(jié)點(diǎn)代表其覆蓋的葉節(jié)點(diǎn)的時間區(qū)間內(nèi)的統(tǒng)計值.如果持續(xù)發(fā)布W滑動窗口內(nèi)的heavy hitter 統(tǒng)計信息,需要基于這組二叉樹進(jìn)行統(tǒng)計.而每次的發(fā)布參與統(tǒng)計的二叉樹的節(jié)點(diǎn)數(shù)最多為logW+1.

根據(jù)二叉樹中參與統(tǒng)計的節(jié)點(diǎn)創(chuàng)建時間,所有節(jié)點(diǎn)可以分為圖8 中所示的4 類:過期、活動、正在創(chuàng)建和即將創(chuàng)建.由于實(shí)時發(fā)布只關(guān)注W寬度的統(tǒng)計值,因此每次發(fā)布時最多只會關(guān)注最近兩個窗口內(nèi)的二叉樹的統(tǒng)計信息.只有活動節(jié)點(diǎn)才需要占用內(nèi)存空間.因此,PCC 的空間代價為O((1/λ)log2(1/λ)),計算性能較快.同時,由于每個節(jié)點(diǎn)記錄w0個時間間隔,每隔w0才需要和分布式系統(tǒng)的中心節(jié)點(diǎn)進(jìn)行通信,因此降低了通信帶寬.

Fig.8 Example of PMG (W=7)[33]圖8 PMG 方案示例(W=7)[33]

PDCH-LU[31]則基于PCC 做了進(jìn)一步的改進(jìn),將其改為面向分布式環(huán)境.為了進(jìn)一步降低通信帶寬,PDCHLU 首先采用Lazy 更新策略降低總的通信代價:只有各分布式節(jié)點(diǎn)的統(tǒng)計值更新夠大的情況下才與中心節(jié)點(diǎn)進(jìn)行統(tǒng)計信息的通信;其次,在每次通信時,采用Bloom Filter 技術(shù)[33]降低每次的通信帶寬.在隱私保護(hù)方面,各分布式節(jié)點(diǎn)的單數(shù)據(jù)流采用PCC 的隱私保護(hù)方案,為了對統(tǒng)計信息來源的各分布式節(jié)點(diǎn)進(jìn)行保護(hù),該方案采用了加密保護(hù)方案.

文獻(xiàn)[34]基于抽樣和隨機(jī)響應(yīng)技術(shù)對數(shù)據(jù)流中heavy hitter 元素頻數(shù)信息的持續(xù)發(fā)布進(jìn)行差分隱私保護(hù).該方案首先對所有元素集合X隨機(jī)抽樣出m個元素,其計數(shù)值存放在數(shù)組M中.統(tǒng)計之前,采用隨機(jī)響應(yīng)技術(shù)對數(shù)組M的每一個計數(shù)值初始化為:bx～D0(ε),D0(ε)指以等概率初始化為‘0’或‘1’;統(tǒng)計中,對數(shù)據(jù)流中出現(xiàn)的每個元素,如果在M中,則其對應(yīng)的統(tǒng)計值做更新:bx～D1(ε),D1(ε)指產(chǎn)生1 的概率為1/2+ε/4,產(chǎn)生0 的概率為1/2-ε/4.基于M,持續(xù)計算并發(fā)布heavy hitter 元素頻數(shù).

文獻(xiàn)[35]同樣對數(shù)據(jù)流中heavy hitter 元素頻數(shù)的持續(xù)發(fā)布進(jìn)行差分隱私保護(hù).主要實(shí)現(xiàn)技術(shù)是數(shù)據(jù)流處理的sketch 技術(shù)和指數(shù)機(jī)制.由于基于sketch 的數(shù)據(jù)流處理會維護(hù)一個記錄中間統(tǒng)計值的sketch 向量sk(a),為實(shí)現(xiàn)差分隱私,先采用服從με=exp(ε/4·q(sk(a),sk(a)priv))的指數(shù)機(jī)制噪聲對sk(a)進(jìn)行初始化,q(sk(a),sk(a)priv)是指數(shù)機(jī)制的效用函數(shù);然后,基于初始化后的sk(a),采用數(shù)據(jù)流統(tǒng)計算法對sk(a)中的元素統(tǒng)計值進(jìn)行更新;最后,再對sk(a)進(jìn)行滿足με指數(shù)機(jī)制的噪聲處理.基于噪聲處理后的sk(a),持續(xù)發(fā)布heavy hitter 元素頻數(shù)信息.

文獻(xiàn)[34,35]都考慮了攻擊者獲取到中間統(tǒng)計值時的隱私保護(hù)處理,所以方案滿足pan-privacy[19],實(shí)現(xiàn)了差分隱私與安全的結(jié)合,其隱私保護(hù)強(qiáng)度更高.兩種方案的區(qū)別是:文獻(xiàn)[34]只能對計數(shù)值增量更新情況下進(jìn)行隱私保護(hù),而文獻(xiàn)[35]卻可以處理全動態(tài)更新情況下(計數(shù)值可以增加,也可以減少)的隱私保護(hù).

3.4 位置發(fā)布的持續(xù)監(jiān)控保護(hù)

文獻(xiàn)[36,37]提出一種基于時序關(guān)聯(lián)的位置持續(xù)發(fā)布的隱私保護(hù)方案PIM.方案中,相鄰時刻用戶位置的關(guān)聯(lián)關(guān)系用馬爾可夫模型建模和預(yù)測.在每個時刻,找出用戶的“δ-位置集”ΔX(t時刻用戶可能會存在的位置及其對應(yīng)的概率).差分隱私發(fā)布機(jī)制保證:在每個時刻t,用戶的真實(shí)位置與ΔX中任一位置出現(xiàn)的概率基本一樣.即使攻擊者能根據(jù)轉(zhuǎn)移概率推測出ΔX,也不能發(fā)現(xiàn)用戶的真實(shí)位置.具體實(shí)現(xiàn)方案是:在每個時刻t,基于t-1 時刻的后驗(yàn)概率和用戶的馬爾可夫轉(zhuǎn)移概率矩陣M,計算用t時刻轉(zhuǎn)移位置的先驗(yàn)概率向量;根據(jù)該向量構(gòu)建t時刻的“δ-位置集”ΔX,然后計算發(fā)布任務(wù)的敏感度K,并產(chǎn)生一個滿足εt的噪聲,對t時刻的用戶位置加噪聲后發(fā)布.為進(jìn)一步提高發(fā)布結(jié)果的可用性,在計算敏感度時,方案采用平面各向同構(gòu)機(jī)制對K進(jìn)行各項(xiàng)同性轉(zhuǎn)換,并利用K-范數(shù)機(jī)制來降低發(fā)布所需噪聲.

文獻(xiàn)[38]則針對位置聚集統(tǒng)計信息持續(xù)發(fā)布的隱私保護(hù)問題,對時序關(guān)聯(lián)所造成的隱私泄露做了定量的分析.用TPL 代表該方案.方案問題場景如下:假設(shè)攻擊目標(biāo)ui在t時刻的位置為,攻擊者已經(jīng)掌握除之外的所有用戶的時序數(shù)據(jù)的關(guān)聯(lián)信息.關(guān)聯(lián)信息采用馬爾可夫鏈建模,分為前向馬爾可夫轉(zhuǎn)移概率矩陣()和后向馬爾可夫轉(zhuǎn)移概率矩陣(),其示例如圖9 所示.

Fig.9 Example of temporal correlations[38]圖9 時序關(guān)聯(lián)關(guān)系示例[38]

基于上述信息,方案中對時序數(shù)據(jù)相關(guān)性所造成的隱私泄露量給出了定量化的計算公式,即為所有用戶中最大的隱私泄露風(fēng)險值.該隱私泄露量的計算包含前向轉(zhuǎn)移關(guān)系隱私泄露的計算和后向轉(zhuǎn)移關(guān)系隱私泄露的計算,為了提高計算效率,方案將隱私泄露量的求解問題轉(zhuǎn)換為一個線性分式規(guī)劃問題,并提出了多項(xiàng)式時間內(nèi)的求解算法.

上述方案都是考慮了時序數(shù)據(jù)相關(guān)性的隱私保護(hù)方案.目前,關(guān)聯(lián)數(shù)據(jù)發(fā)布的隱私保護(hù)研究提出了新的隱私保護(hù)模型Pufferfish[39,40]和Blowfish[41].同時,也有一些面向關(guān)聯(lián)數(shù)據(jù)發(fā)布的差分隱私保護(hù)文獻(xiàn),如文獻(xiàn)[42,43]針對靜態(tài)社交網(wǎng)絡(luò)和關(guān)聯(lián)數(shù)據(jù)集的發(fā)布問題提出了相應(yīng)的解決方案,其主要思想是對數(shù)據(jù)之間的關(guān)聯(lián)進(jìn)行建模,根據(jù)模型確定關(guān)聯(lián)敏感度,基于關(guān)聯(lián)敏感度確定關(guān)聯(lián)數(shù)據(jù)的噪聲添加方案.雖然這些方案不是直接針對時序關(guān)聯(lián)數(shù)據(jù)發(fā)布的隱私保護(hù)方案,但可以拓展到持續(xù)監(jiān)控場景下.

3.5 Event級隱私保護(hù)方案小結(jié)

總結(jié)來說,持續(xù)監(jiān)控下event 級隱私保護(hù)方案核心都是圍繞如何提高時序數(shù)據(jù)發(fā)布的可用性問題進(jìn)行研究,其目標(biāo)都是滿足event 級ε-差分隱私的前提下,如何能降低發(fā)布結(jié)果誤差,提高發(fā)布結(jié)果可用性.本節(jié)從方案優(yōu)缺點(diǎn)、發(fā)布結(jié)果誤差等方面對現(xiàn)有event 級隱私保護(hù)方案進(jìn)行總結(jié)對比分析,詳細(xì)見表2;然后指出現(xiàn)有方案的不足及未來研究趨勢.

(1) 從持續(xù)監(jiān)控生命期上看,所有event 級別持續(xù)監(jiān)控保護(hù)方案中,不需要在時序上進(jìn)行隱私預(yù)算分配.但由于時序發(fā)布任務(wù)的高敏感度,數(shù)據(jù)流的持續(xù)監(jiān)控保護(hù)長度受限.如在方案1 和Tree Counter 中,必須根據(jù)數(shù)據(jù)流長度T添加噪聲,所以只能保護(hù)定長數(shù)據(jù)流;其余方案雖然噪聲添加方案與數(shù)據(jù)流長度無關(guān),但隨著處理數(shù)據(jù)流長度的增加,大部分方案發(fā)布結(jié)果可用性變差.只有Decayed Sum 中隱私保護(hù)方案更符合實(shí)時監(jiān)控特點(diǎn),能實(shí)現(xiàn)對無限長數(shù)據(jù)流的監(jiān)控保護(hù).因此,如何在保證event 級隱私和高可用性的前提下實(shí)現(xiàn)對無限長數(shù)據(jù)流的持續(xù)監(jiān)控保護(hù),值得進(jìn)一步研究;

(2) 從降低敏感度技術(shù)來看,event 發(fā)布方案主要采用分區(qū)技術(shù)或二叉樹技術(shù)來降低發(fā)布敏感度.其中,基于分區(qū)的方案有Two-level,Hybrid,Partition,PeGaSus,RetroGroup.雖然都是分區(qū),但是分區(qū)原則不一樣:Two-level 是定長分區(qū),Hybrid 是非定長分區(qū),Partition 是每個分區(qū)計數(shù)和大致相同,而PeGaSus 和RetroGroup 則是將數(shù)據(jù)變化不大的連續(xù)時間分為一組.基于二叉樹的方案有Tree Counter,Hybrid,Decayed Sum,PDCH-LU.所有的分區(qū)方案和二叉樹方案只適用于簡單計數(shù)統(tǒng)計的查詢?nèi)蝿?wù).雖然采用降低敏感度技術(shù)提高了發(fā)布結(jié)果可用性,但隨著數(shù)據(jù)流的增加,發(fā)布結(jié)果的可用性依然會變差.如何結(jié)合特定持續(xù)發(fā)布任務(wù)設(shè)計更好的降低敏感度方案來提高發(fā)布結(jié)果的可用性,值得進(jìn)一步研究;

(3) 在PeGaSus 和RetroGroup 中的分區(qū)方案采用了平滑技術(shù)提高發(fā)布結(jié)果可用性,如采用分區(qū)內(nèi)平均值或中間值來對發(fā)布結(jié)果進(jìn)行近似處理.分區(qū)技術(shù)是為降低時序上的噪聲誤差的常用技術(shù),如何結(jié)合更好的平滑技術(shù)提高基于分區(qū)的發(fā)布結(jié)果的可用性,值得進(jìn)一步研究;

(4) 從數(shù)據(jù)處理方式上看,根據(jù)時序數(shù)據(jù)的處理方式,方案分為離線處理和在線處理.所有方案都可實(shí)現(xiàn)實(shí)時在線處理.結(jié)合特定持續(xù)發(fā)布任務(wù)實(shí)現(xiàn)在線處理的event 級隱私保護(hù)方案,也值得進(jìn)一步研究.

Table 2 Comparation of schemes on event-level privacy under continual monitoring表2 Event 級別持續(xù)監(jiān)控保護(hù)方案對比

4 持續(xù)監(jiān)控下user-級隱私保護(hù)方案

User 級的持續(xù)監(jiān)控保護(hù)方案主要圍繞簡單聚集統(tǒng)計信息的持續(xù)發(fā)布、分布式數(shù)據(jù)流的閾值函數(shù)持續(xù)監(jiān)控、集值對的增量更新發(fā)布、軌跡數(shù)據(jù)發(fā)布等幾個問題進(jìn)行分析總結(jié).

4.1 簡單聚集統(tǒng)計信息的持續(xù)發(fā)布保護(hù)方案

簡單聚集統(tǒng)計指基于count、sum、average 等聚集函數(shù)的信息統(tǒng)計.實(shí)時發(fā)布簡單聚集統(tǒng)計信息對很多重要的數(shù)據(jù)挖掘應(yīng)用具有很重要的意義.

如圖10 所示:假設(shè)一個GPS 服務(wù)提供商實(shí)時收集用戶位置、速度、活動類型等信息,然后統(tǒng)計出如某時段特定區(qū)域的用戶數(shù)等統(tǒng)計信息,提供給第三方研究機(jī)構(gòu);第三方基于這些信息,可以挖掘用戶的常去區(qū)域、公眾的興趣、路段的交通堵塞等信息.但第三方機(jī)構(gòu)往往是不可信的,因此在簡單聚集統(tǒng)計信息的持續(xù)發(fā)布過程中,有必要對其進(jìn)行隱私保護(hù).本節(jié)主要針對簡單聚集統(tǒng)計信息的持續(xù)發(fā)布問題,對現(xiàn)有的幾種user 級隱私保護(hù)方案進(jìn)行總結(jié)和對比分析.

Fig.10 Contimual release of simple aggregation statistics[46]圖10 簡單聚集統(tǒng)計信息持續(xù)發(fā)布[46]

4.1.1 基本發(fā)布方案

基本發(fā)布方案是差分隱私實(shí)現(xiàn)機(jī)制[22]的直接應(yīng)用,為滿足user 級的差分隱私,基本方案是將隱私預(yù)算ε平均分配到時間序列上每個發(fā)布時間點(diǎn).假設(shè)時間序列長度為T,則每個發(fā)布點(diǎn)所分配的預(yù)算為ε/T.根據(jù)差分隱私的序列組合性質(zhì),則整個時間序列上的持續(xù)發(fā)布滿足ε差分隱私.由于每個發(fā)布點(diǎn)所分配的隱私預(yù)算跟T成反比,發(fā)布結(jié)果誤差為θ(T),發(fā)布結(jié)果可用性較低.為提高可用性,降低誤差,很多文獻(xiàn)基于采樣的方法,選出有代表性的采樣點(diǎn)進(jìn)行發(fā)布,具體方案如下.

4.1.2 基于傅里葉級數(shù)變換的采樣發(fā)布方案

文獻(xiàn)[44]提出一種基于傅里葉級數(shù)變換的采樣發(fā)布方案DFT,該方案滿足user 級隱私.其基本思想是:選取d(d<

4.1.3 基于PID 機(jī)制和濾波技術(shù)的發(fā)布方案

文獻(xiàn)[46]提出了一種基于PID 機(jī)制[45]的自適應(yīng)抽樣發(fā)布方案FAST,該方案滿足user 級隱私保護(hù).與DFT不同,該方案可以處理實(shí)時數(shù)據(jù)流,效率較快.FAST 的核心策略是,采用自適應(yīng)采樣技術(shù)和濾波技術(shù)來提高發(fā)布結(jié)果的可用性.其基本框架如圖11 所示,其中:自適應(yīng)采樣技術(shù)是為了降低時間序列上總的隱私預(yù)算消耗,而濾波技術(shù)是為了提高每個發(fā)布點(diǎn)上發(fā)布結(jié)果的可用性.

Fig.11 Framework of FAST[46]圖11 FAST 框架[46]

自適應(yīng)抽樣機(jī)制的核心思想是:設(shè)定整個時序發(fā)布次數(shù)上限值為M(M<

濾波技術(shù)的核心思想是:建立一個狀態(tài)空間模型,根據(jù)模型預(yù)測值和觀測到的噪聲統(tǒng)計值,采用后驗(yàn)估計對要發(fā)布的結(jié)果進(jìn)行校正,提高發(fā)布結(jié)果的可用性.所建立的狀態(tài)空間模型包括相鄰時刻統(tǒng)計值預(yù)測模型和噪聲處理模型,相鄰時刻處理模型為xk=xk-1+ω,ω～N(0,Q),xk代表k時刻的真實(shí)值;ω為高斯白噪聲,也稱為處理噪聲;Q為方差.噪聲處理模型為zk=xk-1+υ,ν～Lap(0,M/ε),zk為k時刻噪聲統(tǒng)計值,ν是拉普拉斯噪聲.在每個抽樣發(fā)布時刻k,基于狀態(tài)空間模型獲得xk和zk,然后采用卡爾曼濾波的后驗(yàn)估計方法對要發(fā)布的結(jié)果進(jìn)行校正.具體步驟為:根據(jù)先驗(yàn)估計得到的k時刻噪聲值,然后基于和zk的值,采用梯度下降算法調(diào)整卡爾曼收益參數(shù)Kk,目標(biāo)是使得k時刻的后驗(yàn)估計值的方差最小.然后根據(jù)Kk計算出k時刻的最優(yōu)發(fā)布值進(jìn)行發(fā)布.

文獻(xiàn)[47]將FAST 應(yīng)用到了二維空間的區(qū)域?qū)崟r計數(shù)監(jiān)控問題中,文獻(xiàn)提出了兩種估計算法來降低噪聲誤差:一個是時序估計算法,核心思想就是FAST 的應(yīng)用,基于采樣和卡爾曼濾波后驗(yàn)估計方法去降低時序數(shù)據(jù)發(fā)布的總誤差;另一個是空間估計算法,基于quadtree 建立一個空間索引結(jié)構(gòu),基于該結(jié)構(gòu)對具有相似統(tǒng)計值的區(qū)域進(jìn)行分組,然后基于分組添加拉普拉斯噪聲,降低由于數(shù)據(jù)稀疏所造成的添加噪聲過大的問題.

文獻(xiàn)[48]則將FAST 應(yīng)用到了用戶的網(wǎng)頁瀏覽行為的持續(xù)監(jiān)控問題中.文獻(xiàn)將網(wǎng)頁監(jiān)控問題分為了單值持續(xù)監(jiān)控和多值持續(xù)監(jiān)控兩種情況:在單值持續(xù)監(jiān)控方案中,基于FAST 的思想建立狀態(tài)空間模型,采用卡爾曼濾波方法對觀測的噪聲值進(jìn)行校正,提高發(fā)布結(jié)果可用性;在多值目標(biāo)監(jiān)控中,時序處理模型結(jié)合了網(wǎng)頁的馬爾可夫轉(zhuǎn)移矩陣來進(jìn)行預(yù)測.雖然方案滿足user 級隱私保護(hù),也提高了發(fā)布結(jié)果的可用性,但還有一些缺點(diǎn)可進(jìn)一步改進(jìn).如:隨著監(jiān)控的網(wǎng)頁數(shù)目m的增加,多變量的時序空間模型處理的時間復(fù)雜度非常大,達(dá)到O(m3),因此可以考慮采用如稀疏矩陣、矩陣的秩和矩陣分解技術(shù)來進(jìn)一步提高發(fā)布效率.

文獻(xiàn)[49]基于濾波技術(shù)提出了一種時序關(guān)聯(lián)數(shù)據(jù)的發(fā)布方案CTS-DP,保證在數(shù)據(jù)關(guān)聯(lián)的情況下,發(fā)布的結(jié)果序列與添加關(guān)聯(lián)噪聲后的序列滿足差分隱私要求;同時,攻擊者不能通過修正技術(shù)清洗掉添加的噪聲,還原真實(shí)數(shù)據(jù).文獻(xiàn)[50]則將濾波技術(shù)應(yīng)用到多輸入輸出(MIMO)事件數(shù)據(jù)流中,利用濾波降低發(fā)布結(jié)果噪聲.文獻(xiàn)[51-53]將濾波應(yīng)用到監(jiān)控實(shí)例(實(shí)時交通速度估計和建筑物占用情況預(yù)測)中,并提出了噪聲添加的優(yōu)化方案.

上述方案都是面向無限數(shù)據(jù)流實(shí)時發(fā)布方案,文獻(xiàn)[54]借鑒PID 反饋機(jī)制提出一種面向離線動態(tài)數(shù)據(jù)集的直方圖發(fā)布的隱私保護(hù)方案DSAT,該方案實(shí)現(xiàn)user 級隱私保護(hù).方案的基本思想是:基于PID 反饋機(jī)制進(jìn)行動態(tài)調(diào)整抽樣發(fā)布的頻率,反饋公式為Ei=|Ci/i-C/N|.Ci是當(dāng)前已發(fā)布次數(shù),如果在該時間點(diǎn)之前發(fā)布頻率過高,則調(diào)大閾值,降低采樣頻率;反之調(diào)小閾值,增加采樣頻率,以保證在時間序列內(nèi)固定發(fā)布C次數(shù)據(jù).與FAST 方案相同的是,DSAT 也采用PID 機(jī)制進(jìn)行采樣發(fā)布,都能實(shí)現(xiàn)user 級的隱私保護(hù);不同的是,兩者的PID 反饋公式設(shè)計不同;同時,FAST 是一種實(shí)時處理方案,而DSAT 是離線數(shù)據(jù)處理方案.

4.2 分布式數(shù)據(jù)流閾值函數(shù)的持續(xù)監(jiān)控保護(hù)

上述所有方案是基于簡單聚集函數(shù)的持續(xù)監(jiān)控保護(hù)方案.在數(shù)據(jù)流的實(shí)時監(jiān)控任務(wù)中,往往存在一些復(fù)雜的統(tǒng)計分析任務(wù)(如閾值函數(shù)監(jiān)控),也需要對其進(jìn)行隱私保護(hù).文獻(xiàn)[55,56]以分布式數(shù)據(jù)流為應(yīng)用場景,分別對數(shù)據(jù)流中元素信息增益值的閾值函數(shù)和統(tǒng)計值列表中r百分位值的閾值函數(shù)進(jìn)行持續(xù)監(jiān)控保護(hù).問題可以抽象化為f(·)>τ,f(·)表示基于計數(shù)的統(tǒng)計任務(wù),τ表示閾值.在文獻(xiàn)[55]中,f(·)表示某元素的信息增益值的持續(xù)計算;在文獻(xiàn)[56]中,則表示對基于所有分布式站點(diǎn)生成的統(tǒng)計值列表中不小于r%個列表元素的最小值的持續(xù)計算.閾值函數(shù)監(jiān)控就是持續(xù)監(jiān)控上述統(tǒng)計值是否大于提前設(shè)定的閾值τ.

文獻(xiàn)[55]中信息增益閾值函數(shù)的持續(xù)監(jiān)控以垃圾郵件關(guān)鍵詞監(jiān)控場景為例,描述如下:假設(shè)存在k個分布式站點(diǎn),1 個中心節(jié)點(diǎn),持續(xù)監(jiān)控關(guān)鍵詞t在各分布式數(shù)據(jù)流滑動窗口(寬度為W)內(nèi)的郵件中出現(xiàn)的信息增益值,cα,1,cα,2分別表示W(wǎng)滑動窗口內(nèi)包含t的垃圾郵件和非垃圾郵件的比例,c1,β,c2,β則分別代表不包含t的垃圾郵件和非垃圾郵件的比例.根據(jù)t的增益值是否大于某個閾值,判斷t是否可以被用做垃圾郵件監(jiān)控.文獻(xiàn)[56]中的r百分位值的閾值函數(shù)監(jiān)控問題描述為:k個分布式節(jié)點(diǎn),1 個中心節(jié)點(diǎn),各分布式節(jié)點(diǎn)分別執(zhí)行對應(yīng)的統(tǒng)計任務(wù),發(fā)送統(tǒng)計信息給中心節(jié)點(diǎn),中心節(jié)點(diǎn)基于k個聚集統(tǒng)計值列表,找出列表中大于等于r%個列表值的最小列表元素值,判斷該值是否大于閾值.

由于統(tǒng)計過程中涉及到用戶隱私,需設(shè)計隱私保護(hù)方案.兩個方案的核心策略都是采用Safe Zone(安全區(qū)域)局部約束技術(shù)[57]來最大化時間序列上的隱私預(yù)算的利用率,并且降低各分布式節(jié)點(diǎn)與中心節(jié)點(diǎn)的通信代價,延長差分隱私下持續(xù)監(jiān)控生命期.因此,用Safe Zone 代表兩種方案,其基本思想:將中心節(jié)點(diǎn)的整體監(jiān)控條件轉(zhuǎn)換成一組各分布式站點(diǎn)的局部約束條件(被稱為安全區(qū)域).如果每個分布式站點(diǎn)的局部統(tǒng)計值在安全區(qū)域內(nèi),則表示近期的統(tǒng)計值變化不大,不需要中心節(jié)點(diǎn)進(jìn)行通信,節(jié)約了一定的隱私預(yù)算;否則,花費(fèi)一定的隱私預(yù)算將各分布式站點(diǎn)的局部統(tǒng)計值發(fā)送到中間節(jié)點(diǎn),中間結(jié)點(diǎn)計算并進(jìn)行判斷.雖然兩個方案都采用Safe Zone 技術(shù)實(shí)現(xiàn),但文獻(xiàn)[55]采用球狀安全區(qū)域,在每個時間間隔做隱私保護(hù)處理時,對球狀區(qū)域半徑初始化、各分步式站點(diǎn)與中心節(jié)點(diǎn)通信的統(tǒng)計信息和中心節(jié)點(diǎn)的信息增益值判斷這3 個過程都添加了拉普拉斯噪聲對其隱私進(jìn)行保護(hù).文獻(xiàn)[56]則采用設(shè)置一組安全區(qū)間{[li(t1),ri(t1)]}(1≤i≤θ),li和ri對應(yīng)i區(qū)間的左右臨界值.做隱私保護(hù)處理時,對安全區(qū)間的左右臨界值分別加拉普拉斯噪聲,然后采用指數(shù)機(jī)制確定各分布式站點(diǎn)統(tǒng)計值所屬的安全區(qū)間.最后,中心節(jié)點(diǎn)根據(jù)各分布式站點(diǎn)發(fā)送的安全區(qū)間索引號進(jìn)行閾值判斷.

上述兩種方案采用Safe Zone 技術(shù)與拉普拉斯機(jī)制或指數(shù)機(jī)制相結(jié)合,不僅降低了通信量,也延長了持續(xù)監(jiān)控生命期.持續(xù)監(jiān)控保護(hù)方案滿足user 級差分隱私保護(hù).兩個方案的缺點(diǎn)是只能進(jìn)行有限長的持續(xù)監(jiān)控,如何實(shí)現(xiàn)無限長分布式數(shù)據(jù)流的持續(xù)監(jiān)控保護(hù),依然是具有挑戰(zhàn)性的研究問題.

4.3 集值對的增量更新發(fā)布保護(hù)方案

針對集值的持續(xù)發(fā)布問題,文獻(xiàn)[58]提出一種增量更新發(fā)布隱私保護(hù)方案IncBuildTBP,可滿足的user 級隱私保護(hù).方案采用基本隱私預(yù)算分配方案:設(shè)定數(shù)據(jù)庫更新發(fā)布次數(shù)上限為U,每次發(fā)布分配隱私預(yù)算ε/(U+1).由于集值對發(fā)布問題敏感度很高,文獻(xiàn)借助一棵基于劃分的分類樹TBP-Tree 來對龐大的集值對輸出空間進(jìn)行壓縮,以降低集值對發(fā)布問題的高敏感度;同時,由于每次更新可能會產(chǎn)生大量值為0 的空節(jié)點(diǎn),為空節(jié)點(diǎn)分配隱私預(yù)算會影響發(fā)布數(shù)據(jù)的可用性,所以每次更新都對這些節(jié)點(diǎn)進(jìn)行剪枝,以提高發(fā)布數(shù)據(jù)的可用性.文獻(xiàn)雖然實(shí)現(xiàn)了集值數(shù)據(jù)的動態(tài)的差分隱私發(fā)布,但是發(fā)布結(jié)果的可用性比較低,并且只能實(shí)現(xiàn)離線數(shù)據(jù)的處理.

4.4 軌跡發(fā)布的差分隱私保護(hù)方案

軌跡是具有時序關(guān)系的位置序列,攻擊者通過對用戶位置的持續(xù)監(jiān)控(軌跡的監(jiān)控),可以獲取隱私信息.現(xiàn)有軌跡數(shù)據(jù)發(fā)布的差分隱私保護(hù)方案都是針對離線軌跡數(shù)據(jù)集,經(jīng)差分隱私保護(hù)處理后,發(fā)布“凈化版”的軌跡數(shù)據(jù),隱私保護(hù)級別為user 級.攻擊者通過監(jiān)控發(fā)布的軌跡信息,無法獲得個體隱私.在該問題中,假設(shè)所有位置總數(shù)為m,軌跡最大長度為l,則可能生成的軌跡數(shù)目最多為因此,軌跡發(fā)布隱私保護(hù)問題的的輸出空間非常大,發(fā)布任務(wù)的敏感度和復(fù)雜度很高.為了縮小輸出空間,降低敏感度,從而降低所需添加的噪聲量,一些文獻(xiàn)提出了相應(yīng)的解決方案.

文獻(xiàn)[59]提出一種軌跡發(fā)布的隱私保護(hù)方案Perfix,方案采用前綴樹對輸出空間進(jìn)行壓縮并添加噪聲,發(fā)布凈化版的軌跡數(shù)據(jù)集.其基本思想是:假設(shè)很多軌跡數(shù)據(jù)具有相同前綴,將所有具有相同前綴的軌跡分到前綴樹的同一個分支上,從而避免隱私預(yù)算的重復(fù)分配.根據(jù)前綴樹的高度h,隱私預(yù)算ε被平均分配到各層,每層所分配的隱私預(yù)算ε/h,從根節(jié)點(diǎn)到各層每個節(jié)點(diǎn)都對應(yīng)一條軌跡,每個節(jié)點(diǎn)的計數(shù)加上滿足的拉普拉斯噪聲.為了提高發(fā)布效率,方案采用閾值剪枝策略,盡早刪除不能繼續(xù)擴(kuò)展的分支節(jié)點(diǎn).由于噪聲計數(shù)會違背一致性約束,方案利用前綴樹父子節(jié)點(diǎn)之間的約束關(guān)系對計數(shù)值進(jìn)行了一致性處理,進(jìn)一步提高了發(fā)布結(jié)果的可用性.如果位置空間域較小,前綴樹高度較低,Perfix 方案發(fā)布結(jié)果的可用性較好;如果空間域較大,前綴樹高度增加,被劃分到同一分支的軌跡將大幅度減少,因此造成發(fā)布結(jié)果的可用性變低.

為解決Perfix 方案的問題,文獻(xiàn)[60]提出了改進(jìn)的軌跡發(fā)布方案N-Grams,核心思想是:采用變長n-gram 模型和馬爾可夫模型來發(fā)布軌跡數(shù)據(jù)庫.首先,基于軌跡數(shù)據(jù)庫,采用n-gram(n≤nmax)模型統(tǒng)計空間域中位置之間的轉(zhuǎn)移概率,并記錄在自定義的數(shù)據(jù)結(jié)構(gòu)-探索樹中(前綴樹結(jié)構(gòu),高度為nmax).隱私預(yù)算分配方案如下:和Perfix分配方案一樣,探索樹每一層節(jié)點(diǎn)初始化分配的隱私預(yù)算ε/nmax.但由于探索樹很多分支長度不夠nmax,為提高隱私預(yù)算利用率,從第2 層的節(jié)點(diǎn)開始,方案對當(dāng)前節(jié)點(diǎn)所在分支的底層長度hv預(yù)測,根據(jù)預(yù)測值,將剩余隱私預(yù)算平均分配到該分支剩下的幾層節(jié)點(diǎn)中,每層節(jié)點(diǎn)分配到的隱私預(yù)算會有增加,從而能提高了發(fā)布結(jié)果的可用性.在發(fā)布軌跡時,長度不大于nmax的軌跡通過遍歷探索樹進(jìn)行發(fā)布,長度超出nmax的軌跡則采用馬爾可夫模型預(yù)測其計數(shù).由于探索樹的高度遠(yuǎn)遠(yuǎn)小于Perfix 中前綴樹的高度,該方案解決了前綴樹過高帶來的低可用性問題.但由于探索樹只記錄最大長度受限的軌跡的n-gram 信息,造成了一定的信息丟失,影響發(fā)布結(jié)果的可用性.

Prefix 和N-Grams 方案都是基于軌跡中有相同前綴的前提下,采用n-gram 或前綴樹對輸出空間進(jìn)行壓縮,來提高發(fā)布數(shù)據(jù)的可用性.然而,由于軌跡的異質(zhì)性,很少軌跡有相同的前綴,Cluster[61,62]在取消上述假設(shè)的前提下,設(shè)計一種基于聚類的軌跡發(fā)布保護(hù)方案.該方案的核心思想是:首先,采用指數(shù)機(jī)制對同一時間的位置進(jìn)行差分隱私下聚類,每個時間對應(yīng)的位置聚類為k類;然后,基于聚類后的位置發(fā)布軌跡數(shù)據(jù)集.經(jīng)過聚類,軌跡輸出空間大大降低,從而也降低了發(fā)布的敏感度,提高了可用性.

文獻(xiàn)[63-65]則提出:利用二維空間的參照系統(tǒng)來縮小軌跡輸出空間,降低發(fā)布敏感度.Homogeneous[63]采用同質(zhì)參照系統(tǒng)來對用戶軌跡進(jìn)行采樣,降低位置空間中位置之間轉(zhuǎn)移的規(guī)模.參照系統(tǒng)中,如果設(shè)置的粒度越大,軌跡輸出空間就越小;反之越大.如將二維空間劃分為網(wǎng)格,基于網(wǎng)格參照系統(tǒng)抽樣軌跡,網(wǎng)格越大,軌跡就越短,軌跡的輸出空間就越小;反之越大.由于同質(zhì)的參照系統(tǒng)不能很好地反映用戶不同速度的軌跡模式,也會造成一定的信息丟失,對此,Hierarchical[64]提出建立層次參照系統(tǒng)HRS 來捕捉用戶不同速度的軌跡,速度較快的軌跡模式采用粗粒度的參照系統(tǒng)進(jìn)行抽樣,速度較慢的采用細(xì)粒度的參照系統(tǒng).基于HRS 對位置空間域進(jìn)行離散化,對每種參照系統(tǒng)維護(hù)一個軌跡前綴樹模型.為使這組前綴樹更好地體現(xiàn)軌跡特點(diǎn),方案根據(jù)軌跡數(shù)據(jù)庫設(shè)計了滿足隱私保護(hù)的模型選擇機(jī)制,其任務(wù)是從這組前綴樹模型中選擇合適的前綴樹表示不同速度的軌跡;同時,對選擇的前綴樹模型設(shè)計更合適的樹高和節(jié)點(diǎn)間的轉(zhuǎn)移概率,添加拉普拉斯噪聲以滿足隱私保護(hù)要求.最后,方案采用基于方向的權(quán)重抽樣技術(shù)修復(fù)添加噪聲后的軌跡的方向性信息,進(jìn)一步提高了發(fā)布結(jié)果的可用性.Hierarchical 和文獻(xiàn)[63]方案中的參照系統(tǒng)都是基于空間區(qū)域的網(wǎng)格劃分,然后基于網(wǎng)格的關(guān)鍵點(diǎn)(achor)對軌跡進(jìn)行抽樣.兩種方案的參照系統(tǒng)都沒有做隱私保護(hù),對此,PTCP[65]提出對參照系統(tǒng)聚類后,對聚類后的achors 添加拉普拉斯噪聲保護(hù).然后,基于achors 對軌跡抽樣,基于前綴樹結(jié)構(gòu)實(shí)現(xiàn)軌跡數(shù)據(jù)發(fā)布的差分隱私保護(hù).

4.5 User級隱私保護(hù)方案小結(jié)

本小節(jié)對所有user 級隱私保護(hù)方案從其優(yōu)缺點(diǎn)、監(jiān)控任務(wù)類型和面向的發(fā)布任務(wù)等幾個方面進(jìn)行總結(jié)和對比分析(見表3),然后指出現(xiàn)有方案的不足及未來研究趨勢.

(1) 在簡單聚集統(tǒng)計信息的持續(xù)發(fā)布方案中,為最大化時間序列上的隱私預(yù)算利用率,大部分方案采用抽樣技術(shù)來提高發(fā)布結(jié)果的可用性,其原理是結(jié)合時序數(shù)據(jù)的特點(diǎn),選出代表性的發(fā)布點(diǎn)進(jìn)行發(fā)布,降低發(fā)布次數(shù),增大每個發(fā)布點(diǎn)所分配的隱私預(yù)算.但這種方案只是延長持續(xù)監(jiān)控生命期,持續(xù)監(jiān)控數(shù)據(jù)流長度依然有限.如何能實(shí)現(xiàn)對無限長動態(tài)數(shù)據(jù)的持續(xù)監(jiān)控保護(hù),是需要解決的問題;

(2) 在分布式數(shù)據(jù)流持續(xù)監(jiān)控保護(hù)中,現(xiàn)有的持續(xù)監(jiān)控保護(hù)方案為延長持續(xù)監(jiān)控保護(hù)期,采用一系列將全局監(jiān)控條件轉(zhuǎn)換為局部監(jiān)控條件的分解技術(shù).但這些技術(shù)的時間和空間復(fù)雜度很高,極大降低了分布式數(shù)據(jù)流處理效率.可以對分解技術(shù)作進(jìn)一步的改進(jìn)處理,如:基于凸分解或?yàn)V波技術(shù)提高分解效率;也可以基于衰減模型的數(shù)據(jù)流處理模型設(shè)計基于隱私衰減的隱私保護(hù)方案,實(shí)現(xiàn)對無限長數(shù)據(jù)流的處理;

(3) 在軌跡數(shù)據(jù)的發(fā)布問題中,由于發(fā)布任務(wù)的輸出空間太大,對其進(jìn)行隱私保護(hù)的敏感度和復(fù)雜度很高.所以現(xiàn)有軌跡數(shù)據(jù)的發(fā)布方案提出了各種降低輸出空間,降低發(fā)布任務(wù)敏感度的策略,如:基于前綴樹、n-gram 模型和馬爾可夫模型、聚類和參照系統(tǒng)等技術(shù)來縮小輸出空間后,對其進(jìn)行差分隱私處理.現(xiàn)有方案發(fā)布結(jié)果的可用性與實(shí)際應(yīng)用仍有一定的差距,進(jìn)一步提高發(fā)布結(jié)果可用性是值得繼續(xù)研究的問題.同時,所有方案都是離線軌跡數(shù)據(jù)的處理,對于實(shí)時軌跡數(shù)據(jù)的差分隱私發(fā)布是值得下一步研究的問題;

(4) 所有user 級隱私保護(hù)方案也分為實(shí)時在線處理和離線處理兩種方式.除FAST 和SafeZone 可以進(jìn)行在線數(shù)據(jù)流的處理,其余所有方案都為離線數(shù)據(jù)處理.同時,大多數(shù)持續(xù)監(jiān)控任務(wù)還都是基于count 的簡單統(tǒng)計,但實(shí)際應(yīng)用中往往存在一些復(fù)雜的數(shù)據(jù)分析任務(wù).靜態(tài)數(shù)據(jù)集上已有針對這些復(fù)雜分析任務(wù)的差分隱私保護(hù)研究工作[66-70],但持續(xù)監(jiān)控下的相關(guān)工作還很少.因此,持續(xù)監(jiān)控下差分隱私保護(hù)與復(fù)雜監(jiān)控任務(wù)的結(jié)合還有待進(jìn)一步的研究.

Table 3 Comparation of schemes on user-level privacy under continual monitoring表3 持續(xù)監(jiān)控下user 級隱私方案的對比分析

5 持續(xù)監(jiān)控下w-event 隱私保護(hù)方案

從隱私保護(hù)強(qiáng)度上看,w-event 隱私是介于user 級隱私和event 隱私之間的一種隱私保護(hù)方案,本節(jié)對持續(xù)監(jiān)控下w-event 隱私保護(hù)方案進(jìn)行總結(jié)和分析.

5.1 w-event級隱私保護(hù)方案

針對第4.1 節(jié)中的簡單聚集統(tǒng)計信息持續(xù)監(jiān)控保護(hù)問題,文獻(xiàn)[21]提出了兩種滿足w-eventε-差分隱私的保護(hù)方案:BA 和BD.兩種方案都能實(shí)現(xiàn)對無限長數(shù)據(jù)流的持續(xù)監(jiān)控保護(hù).根據(jù)第1.2.3 節(jié)中的w-eventε-差分隱私定義,為保證ε隱私,在時間序列上的任意w滑動窗口內(nèi),分配的隱私預(yù)算都必須小于等于ε.隱私預(yù)算的基本分配方案是將ε平均分配到每個窗口內(nèi)的w個時間點(diǎn)上,每個點(diǎn)的隱私預(yù)算為ε/w.但該分配方案數(shù)據(jù)可用性較低,為提高滑動窗口內(nèi)的隱私預(yù)算利用率,方案也采用了采樣發(fā)布策略,即選出窗口內(nèi)有代表性的時間點(diǎn)(數(shù)據(jù)變化較大)作為主動發(fā)布點(diǎn),只有主動發(fā)布點(diǎn)上才分配隱私預(yù)算;其他時刻做被動發(fā)布,不分配隱私預(yù)算.兩種隱私保護(hù)方案都包含兩個核心過程,分別是相鄰時刻發(fā)布值的相似性計算過程和差分隱私發(fā)布過程.隱私預(yù)算被平均分配到兩個過程:ε=ε1+ε2,ε1=ε/2 用于數(shù)據(jù)相似性計算;ε2=ε-ε1用作差分隱私發(fā)布.

BD(隱私預(yù)算指數(shù)機(jī)制分配)和BA(隱私預(yù)算吸收)都基于上述兩個基本過程實(shí)現(xiàn),不同的是窗口內(nèi)每個采樣點(diǎn)的隱私分配方案有區(qū)別.下面分別介紹兩種方案的具體實(shí)現(xiàn).

BD 方案的特點(diǎn)是將ε1平均分配到每個窗口內(nèi)的w個時間點(diǎn)上,對于每個時間i,用εi,1=ε/(2·w)做相鄰時間數(shù)據(jù)相似性的計算.如果變化夠大,則將ε2按指數(shù)遞減方式分配給采樣點(diǎn),每個采樣點(diǎn)i得到εi,2=εrm/2.計算方法是:先找出當(dāng)前活動窗口[i-w+1,i]內(nèi)還可用的隱私預(yù)算,然后將剩余隱私預(yù)算εrm以指數(shù)方式分配給采樣點(diǎn)i.如果變化不大,則時間i的隱私預(yù)算εi,2=0.如圖12 所示的BD 示例中,早期采樣點(diǎn)的隱私預(yù)算比晚期采樣點(diǎn)的隱私預(yù)算大,所以當(dāng)前活動窗口中越靠后的時間點(diǎn)的發(fā)布結(jié)果所需添加的噪聲越大.BD 方案的隱私預(yù)算會有浪費(fèi),因?yàn)橹笖?shù)分配方式永遠(yuǎn)有一部分預(yù)算不能利用.

而在BA 方案中,用于相似性計算的隱私預(yù)算分配方案與BD 方案相同,窗口內(nèi)每個時間點(diǎn)的εi,1=ε/(2·w);但窗口內(nèi)用于差分隱私發(fā)布的隱私預(yù)算分配方案與BD 不同.BA 將用于發(fā)布的隱私預(yù)算ε2先初始化平均分配到窗口內(nèi)的各時間點(diǎn)上εi,2=ε/(2·w).如果某個時間點(diǎn)i數(shù)據(jù)變化不大,則該時間點(diǎn)的εi,2被節(jié)約下來,重新設(shè)置εi,2=0;節(jié)約下的隱私預(yù)算用于被后續(xù)采樣點(diǎn)吸收,以提高后續(xù)發(fā)布時刻結(jié)果的可用性.如果i數(shù)據(jù)變化大,則計算在該時刻可以吸收的隱私預(yù)算,然后加上i上已有的隱私預(yù)算進(jìn)行發(fā)布.圖12 的BA 方案示例中,時刻2 是被動發(fā)布,所以該時刻的發(fā)布預(yù)算由ε/6 變?yōu)?;時刻3 采樣發(fā)布點(diǎn)吸收了時刻2 的隱私預(yù)算,因此隱私預(yù)算由ε/6 變?yōu)榱甩?3.在BA 方案中,有兩種被動發(fā)布狀態(tài):一是skipped 點(diǎn),表示數(shù)據(jù)變化不大需被動發(fā)布;二是nullified 點(diǎn),表示因窗口內(nèi)隱私預(yù)算用完而被動發(fā)布.如圖12 的BA 示例中,由于時刻3 吸收了時刻2 隱私預(yù)算,所以時刻4 即使數(shù)據(jù)變化較大,但由于沒有可以分配的隱私預(yù)算,也做了被動發(fā)布.BA 方案的缺點(diǎn)是會出現(xiàn)預(yù)算使用完而某些時間點(diǎn)沒有隱私預(yù)算只能做被動發(fā)布的情況.兩個方案共同的缺點(diǎn)是時序上隱私預(yù)算分配不均衡,造成每個發(fā)布時刻發(fā)布結(jié)果添加的噪聲量不一致.

Fig.12 Example of budget allocation under w-event privacy[21]圖12 w-event 隱私預(yù)算分配方案示例[21]

文獻(xiàn)[71]面向無限軌跡流的數(shù)據(jù)發(fā)布提出了一種滿足w-event 的隱私保護(hù)方案GA+MMD.該方案基本思想和BD 基本相同,但對其做出了以下兩個改進(jìn):一是考慮了每個用戶對個體軌跡長度的隱私保護(hù)強(qiáng)度不同,所以提出了個性化軌跡長度li的隱私保護(hù)要求,在窗口內(nèi)的每個時刻,用于相似性計算的隱私預(yù)算為ε1/lmax,lmax是所有用戶中最長的軌跡隱私長度,每個時刻用于發(fā)布的隱私預(yù)算εi,2還是采用指數(shù)遞減的形式進(jìn)行分配;二是與BD 方案中被動發(fā)布時刻采用相鄰時刻的發(fā)布結(jié)果代替不同,GA+MMD 中采用貪心算法找出活動窗口內(nèi)與該時刻發(fā)布結(jié)果最相近的結(jié)果進(jìn)行被動發(fā)布.通過上述兩種策略,GA+MMD 進(jìn)一步提高了發(fā)布結(jié)果的可用性.但方案中對用戶的個性化隱私處理比較簡單,如何結(jié)合現(xiàn)有的個性化差分隱私方案[72-74]實(shí)現(xiàn)真正的持續(xù)監(jiān)控下的個性化的軌跡發(fā)布,值得進(jìn)一步研究.

5.2 w-event級隱私保護(hù)方案的對比分析

本節(jié)先從主要優(yōu)缺點(diǎn)上對持續(xù)監(jiān)控下w-event 隱私保護(hù)方案進(jìn)行對比分析(見表4),然后指出現(xiàn)有方案不足及未來研究趨勢.

目前,w-event 隱私保護(hù)方案相對較少.上述3 種方案都可以實(shí)現(xiàn)對無限長數(shù)據(jù)流的持續(xù)監(jiān)控保護(hù),其保護(hù)強(qiáng)度介于event 級別和user 級別隱私之間.3 種方案的實(shí)現(xiàn)核心都是考慮如何在w滑動窗口內(nèi)提高隱私預(yù)算的利用率,提高發(fā)布結(jié)果的可用性.但都存在以下缺點(diǎn):時序上隱私預(yù)算不能充分利用,如何充分利用隱私預(yù)算,提高持續(xù)發(fā)布結(jié)果可用性,是值得進(jìn)一步研究的問題;同時,這些方案都是面向簡單聚集統(tǒng)計信息的持續(xù)監(jiān)控保護(hù),如何拓展相應(yīng)方案到更復(fù)雜的持續(xù)監(jiān)控任務(wù)中值得進(jìn)一步研究.

Table 4 Comparation of schemes on w-event privacy under continual monitoring表4 持續(xù)監(jiān)控下w-event 隱私保護(hù)方案對比分析

6 未來研究展望

本節(jié)探討持續(xù)監(jiān)控下差分隱私保護(hù)的未來研究展望,主要分為持續(xù)監(jiān)控下面向分布式數(shù)據(jù)流的隱私保護(hù)研究、持續(xù)監(jiān)控下差分隱私算法通用評價標(biāo)準(zhǔn)的研究、持續(xù)監(jiān)控下關(guān)聯(lián)數(shù)據(jù)發(fā)布的隱私保護(hù)研究、持續(xù)監(jiān)控下面向復(fù)雜統(tǒng)計任務(wù)的隱私保護(hù)研究、持續(xù)監(jiān)控下個性化差分隱私保護(hù)研究和持續(xù)監(jiān)控下本地化差分隱私保護(hù)研究.

6.1 持續(xù)監(jiān)控下面向分布式數(shù)據(jù)流的隱私保護(hù)研究

大數(shù)據(jù)環(huán)境下,很多持續(xù)監(jiān)控場景都是基于分布式數(shù)據(jù)流的實(shí)時處理,如Web 網(wǎng)頁的用戶點(diǎn)擊、網(wǎng)絡(luò)入侵檢測、heavy hitter 實(shí)時監(jiān)控和智能基礎(chǔ)設(shè)施的實(shí)時監(jiān)控等.在這些應(yīng)用中,隱私保護(hù)問題非常重要.目前雖然已有一些分布式數(shù)據(jù)流持續(xù)監(jiān)控保護(hù)方案,如垃圾郵件關(guān)鍵詞的持續(xù)監(jiān)控、r百分位值的持續(xù)監(jiān)控等,但方案還很少.持續(xù)監(jiān)控下分布式數(shù)據(jù)流統(tǒng)計的隱私保護(hù)研究應(yīng)考慮了以下問題:一是對局部節(jié)點(diǎn)的統(tǒng)計過程做隱私保護(hù);二是對中心節(jié)點(diǎn)的計算過程做隱私保護(hù);三是要盡量延長持續(xù)監(jiān)控生命期并降低局部站點(diǎn)與中心節(jié)點(diǎn)的總通信量.為解決上述問題,現(xiàn)有方案大多先對局部節(jié)點(diǎn)和中心節(jié)點(diǎn)的計算過程采用噪聲機(jī)制進(jìn)行隱私保護(hù),然后采用安全區(qū)域分解技術(shù)將中心站點(diǎn)的全局監(jiān)控條件轉(zhuǎn)換為各分布式站點(diǎn)的局部監(jiān)控條件,只有違反局部監(jiān)控條件的情況下才分配隱私預(yù)算和中心節(jié)點(diǎn)通信,從而降低總通信量和隱私預(yù)算分配次數(shù).分布式數(shù)據(jù)流持續(xù)監(jiān)控保護(hù)可從以下幾個方面進(jìn)行研究:一是現(xiàn)有方案中分解技術(shù)的時間復(fù)雜度和空間復(fù)雜度很高,可以進(jìn)一步改進(jìn);二是現(xiàn)有方案都是基于對元素精確統(tǒng)計算法做隱私保護(hù)處理,由于數(shù)據(jù)流的處理對時間和空間有嚴(yán)格要求,現(xiàn)有很多數(shù)據(jù)流處理算法都基于近似技術(shù)的統(tǒng)計,如滑動窗口技術(shù)、隨機(jī)采樣技術(shù)和sketch 技術(shù)等,可以考慮基于這些算法做隱私保護(hù)處理,使得持續(xù)監(jiān)控隱私保護(hù)方案更符合實(shí)際監(jiān)控場景要求;三是目前很多分布式數(shù)據(jù)流的持續(xù)監(jiān)控任務(wù)如分布式數(shù)據(jù)流的top-k元素監(jiān)控、網(wǎng)絡(luò)流量的異常檢測、分布式數(shù)據(jù)流的頻繁模式監(jiān)控等,目前都還沒有相關(guān)研究.因此,持續(xù)監(jiān)控下分布式數(shù)據(jù)流統(tǒng)計任務(wù)的隱私保護(hù)是未來的一個研究方向.

6.2 持續(xù)監(jiān)控下差分隱私算法通用評價標(biāo)準(zhǔn)的研究

在對持續(xù)監(jiān)控下差分隱私發(fā)布方案進(jìn)行評價時,現(xiàn)有方案提出了不同的參數(shù)設(shè)置以及評估標(biāo)準(zhǔn).如在面向簡單聚集統(tǒng)計發(fā)布的持續(xù)監(jiān)控保護(hù)方案中,雖然都采用發(fā)布結(jié)果的誤差上界進(jìn)行評估,卻沒有考慮相同的評估條件,如采用的實(shí)驗(yàn)數(shù)據(jù)集是否一樣,設(shè)定的空間約束條件是否一樣、算法中一些通用參數(shù)(如ε)的設(shè)置和調(diào)整是否一致.上述因素都會影響算法的評估性能,目前,這些方案缺乏在統(tǒng)一標(biāo)準(zhǔn)下的相關(guān)評估.在面向復(fù)雜任務(wù)的持續(xù)監(jiān)控保護(hù)方案中,為提高發(fā)布結(jié)果可用性,通常利用數(shù)據(jù)依賴關(guān)系降低噪聲.但數(shù)據(jù)集不同,數(shù)據(jù)依賴關(guān)系也不一樣,導(dǎo)致發(fā)布結(jié)果誤差不同.因此,這類隱私保護(hù)方案都不包含發(fā)布結(jié)果誤差的對比分析.在實(shí)際方案部署時,沒有統(tǒng)一的方案對比分析,如何選擇一個更好的方案面臨重大挑戰(zhàn).開發(fā)通用的評價標(biāo)準(zhǔn)對于這類方案也尤為重要.在通用標(biāo)準(zhǔn)的制定中,不僅應(yīng)考慮通用參數(shù)的調(diào)整與設(shè)置、數(shù)據(jù)集的特點(diǎn)對發(fā)布結(jié)果的影響,同時要考慮多樣化多角度的評估標(biāo)準(zhǔn),考慮各種發(fā)布問題的情況.所以,持續(xù)監(jiān)控下通用差分隱私算法標(biāo)準(zhǔn)的研究是一個未來研究方向.

6.3 持續(xù)監(jiān)控下關(guān)聯(lián)數(shù)據(jù)發(fā)布的隱私保護(hù)研究

現(xiàn)有的持續(xù)監(jiān)控下隱私保護(hù)方案中,已有一些關(guān)聯(lián)數(shù)據(jù)發(fā)布的隱私保護(hù)研究.如在位置發(fā)布的event 級別保護(hù)方案中考慮了時序上用戶位置之間關(guān)聯(lián),并對此進(jìn)行建模,依據(jù)模型對關(guān)聯(lián)關(guān)系所造成的隱私泄露量進(jìn)行分析,降低位置持續(xù)發(fā)布任務(wù)的敏感度.在簡單聚集信息發(fā)布的user 級別保護(hù)方案中,基于時序數(shù)據(jù)關(guān)聯(lián),利用濾波技術(shù)提高了發(fā)布結(jié)果的可用性.在軌跡數(shù)據(jù)發(fā)布問題中,基于時序上用戶位置之間關(guān)系的假設(shè)前提,降低了發(fā)布問題的敏感度.針對實(shí)際問題中數(shù)據(jù)關(guān)聯(lián)關(guān)系建模,根據(jù)模型設(shè)計持續(xù)監(jiān)控下隱私保護(hù)方案.該類方案具有以下優(yōu)點(diǎn):一是更符合真實(shí)的應(yīng)用場景;二是能抵御攻擊者具備這些關(guān)聯(lián)信息的攻擊,隱私保護(hù)更強(qiáng);三是根據(jù)模型的發(fā)布往往可以降低發(fā)布問題的敏感度,可用性更高.目前,持續(xù)監(jiān)控下該類研究工作還較少,方案中對數(shù)據(jù)關(guān)聯(lián)性的建模方法也比較單一.針對相關(guān)數(shù)據(jù)的隱私保護(hù)問題,已有研究工作提出了面向語義的差分隱私保護(hù)模型Pufferfish 和Blowfish.在持續(xù)監(jiān)控場景下,針對特定監(jiān)控問題中的關(guān)聯(lián)數(shù)據(jù),建立多樣化的時序數(shù)據(jù)關(guān)聯(lián)模型,基于面向語義的差分隱私保護(hù)模型,設(shè)計更靈活且具有語義的隱私保護(hù)方案是一個未來的研究方向.

6.4 持續(xù)監(jiān)控下面向復(fù)雜分析任務(wù)的隱私保護(hù)研究

現(xiàn)有的持續(xù)監(jiān)控下差分隱私保護(hù)研究大都是基于count 計數(shù)的簡單統(tǒng)計和分析任務(wù).面向復(fù)雜分析任務(wù)的持續(xù)監(jiān)控保護(hù)研究不僅方案少,發(fā)布結(jié)果可用性也有待進(jìn)一步提高.實(shí)際應(yīng)用場景中往往存在更多的復(fù)雜監(jiān)控任務(wù),如頻繁模式和頻繁序列模式監(jiān)控、持續(xù)分類和聚類監(jiān)控等,這類持續(xù)監(jiān)控任務(wù)暫時沒有相關(guān)研究.持續(xù)監(jiān)控下面向復(fù)雜分析任務(wù)的隱私保護(hù)研究具有以下兩個難題:一是復(fù)雜分析任務(wù)本身輸出結(jié)果空間就比較大,發(fā)布敏感度和復(fù)雜度比較高,如何降低發(fā)布任務(wù)的敏感度,提高發(fā)布結(jié)果的可用性是一個難題;二是在時序上,隨著時間的增加,發(fā)布結(jié)果的噪聲會累積增加,發(fā)布結(jié)果可用性逐漸變差.針對第一個難題,可以對未作隱私保護(hù)的原始算法進(jìn)行分析,根據(jù)算法所采用的數(shù)據(jù)結(jié)構(gòu)及處理過程,計算其敏感度;同時,可改進(jìn)相關(guān)任務(wù)在靜態(tài)數(shù)據(jù)集上已有的降低敏感度技術(shù)[66-70],使其適用于動態(tài)發(fā)布環(huán)境.通過以上策略,提高發(fā)布結(jié)果的可用性.針對第二個難題,可以考慮利用時序上的數(shù)據(jù)依賴關(guān)系,自適應(yīng)分配時序上的隱私預(yù)算,提高隱私預(yù)算的利用率.復(fù)雜分析任務(wù)的持續(xù)監(jiān)控保護(hù)研究是未來的一個研究方向.

6.5 持續(xù)監(jiān)控下個性化差分隱私保護(hù)研究

在持續(xù)監(jiān)控場景中,通常參與者對自己的數(shù)據(jù)有不同的隱私要求,用統(tǒng)一要求來處理所有參與者的信息,可能對一些用戶來說隱私保障太低,而對另外一些用戶又可能要求太高.因此,如何結(jié)合用戶隱私需求,讓用戶定義個人的隱私級別,是一個值得研究的問題[72-74].持續(xù)監(jiān)控下,個性化的隱私保護(hù)研究需要考慮以下問題:一是不同用戶具有不同的隱私保護(hù)要求;二是對同一用戶,不同的項(xiàng)目也會有不同的隱私保護(hù)要求;三是持續(xù)監(jiān)控下,隨著時間的推移,用戶和項(xiàng)目的隱私級別也會有相應(yīng)的變化.個性化差分隱私的隱私保護(hù)級別跟隱私預(yù)算大小相關(guān),隱私預(yù)算越小,隱私保護(hù)強(qiáng)度越高;隱私預(yù)算越大,隱私保護(hù)強(qiáng)度越低.在該類研究中,如何針對多個隱私預(yù)算,采用隨機(jī)響應(yīng)技術(shù)或噪聲機(jī)制等差分隱私實(shí)現(xiàn)技術(shù),設(shè)計滿足所有隱私預(yù)算要求的實(shí)現(xiàn)方案是重點(diǎn)問題.

6.6 持續(xù)監(jiān)控下本地化差分隱私保護(hù)研究

目前,持續(xù)監(jiān)控下的差分隱私保護(hù)都是基于中心化差分隱私保護(hù)技術(shù)實(shí)現(xiàn),該技術(shù)的前提是數(shù)據(jù)收集者必須是可信的第三方.隨著智能基礎(chǔ)設(shè)施的普及和GPS 定位技術(shù)的應(yīng)用,現(xiàn)有持續(xù)監(jiān)控下的應(yīng)用場景多為分布式的應(yīng)用.在這種場景下,數(shù)據(jù)的收集往往類似于問卷調(diào)查,數(shù)據(jù)的管理者往往是不可信的第三方.同時,由于分布式場景中收集的數(shù)據(jù)量特別大并且計算代價非常高,中心化的差分隱私技術(shù)不適合這種場景.目前,一些研究工作[75,76]提出了本地化差分隱私技術(shù)(LDP)方案,通過采用隨機(jī)響應(yīng)技術(shù)對個體數(shù)據(jù)進(jìn)行正向和負(fù)向的擾動,最終通過聚合大量的擾動結(jié)果來抵消添加在其中的正負(fù)向噪聲,從而得到有效的統(tǒng)計結(jié)果.如何將LDP 技術(shù)應(yīng)用到持續(xù)監(jiān)控下的數(shù)據(jù)發(fā)布和分析任務(wù)中,是未來值得研究的一個方向.

7 結(jié)束語

隨著信息技術(shù)的發(fā)展及物聯(lián)網(wǎng)技術(shù)的興起,出現(xiàn)了越來越多的持續(xù)監(jiān)控應(yīng)用場景.在這些場景中,如何對參與者持續(xù)分享的數(shù)據(jù)進(jìn)行隱私保護(hù)面臨重大挑戰(zhàn).本文對持續(xù)監(jiān)控下差分隱私保護(hù)領(lǐng)域已有的研究成果進(jìn)行了總結(jié),首先介紹了持續(xù)監(jiān)控下隱私保護(hù)模型,包括不同保護(hù)級別的差分隱私模型定義、實(shí)現(xiàn)機(jī)制和持續(xù)監(jiān)控下差分隱私保護(hù)方案的評估原則;然后重點(diǎn)對event 級、user 級和w-event 級這3 種隱私保護(hù)級別的方案進(jìn)行總結(jié)和分析.在對已有研究成果深入對比分析的基礎(chǔ)上,指出了持續(xù)監(jiān)控下差分隱私保護(hù)的未來研究方向.持續(xù)監(jiān)控下差分隱私保護(hù)的研究成果還較少,仍有諸多關(guān)鍵問題需要進(jìn)一步的研究.希望本文工作可以為持續(xù)監(jiān)控下差分隱私保護(hù)的相關(guān)研究人員提供參考.