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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.1 Event-級(jí)差分隱私

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

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

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

1.2.2 User-級(jí)差分隱私

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

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

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

1.2.3 w-event 級(jí)差分隱私

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

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

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

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

1.3 噪聲機(jī)制

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

定義5(全局敏感度)[22].設(shè)有函數(shù)f:D→Rd,輸入為數(shù)據(jù)集,輸出為d維實(shí)數(shù)向量.對(duì)于任意鄰居數(shù)據(jù)D和D′:稱(chēng)為函數(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ǎn)足下列不等式,則M滿(mǎn)足ε-差分隱私:

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

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

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

1.4 組合特性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1.1 基本發(fā)布方案

· 方案1

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

· 方案2

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

· Two-level 方案[25]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Fig.6 Process of PeGaSus[30]圖6 PeGaSus 過(guò)程圖[30]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)二叉樹(shù)中參與統(tǒng)計(jì)的節(jié)點(diǎn)創(chuàng)建時(shí)間,所有節(jié)點(diǎn)可以分為圖8 中所示的4 類(lèi):過(guò)期、活動(dòng)、正在創(chuàng)建和即將創(chuàng)建.由于實(shí)時(shí)發(fā)布只關(guān)注W寬度的統(tǒng)計(jì)值,因此每次發(fā)布時(shí)最多只會(huì)關(guān)注最近兩個(gè)窗口內(nèi)的二叉樹(shù)的統(tǒng)計(jì)信息.只有活動(dòng)節(jié)點(diǎn)才需要占用內(nèi)存空間.因此,PCC 的空間代價(jià)為O((1/λ)log2(1/λ)),計(jì)算性能較快.同時(shí),由于每個(gè)節(jié)點(diǎn)記錄w0個(gè)時(shí)間間隔,每隔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à):只有各分布式節(jié)點(diǎn)的統(tǒng)計(jì)值更新夠大的情況下才與中心節(jié)點(diǎn)進(jìn)行統(tǒng)計(jì)信息的通信;其次,在每次通信時(shí),采用Bloom Filter 技術(shù)[33]降低每次的通信帶寬.在隱私保護(hù)方面,各分布式節(jié)點(diǎn)的單數(shù)據(jù)流采用PCC 的隱私保護(hù)方案,為了對(duì)統(tǒng)計(jì)信息來(lái)源的各分布式節(jié)點(diǎn)進(jìn)行保護(hù),該方案采用了加密保護(hù)方案.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1.1 基本發(fā)布方案

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

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

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

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

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

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

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

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

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

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

文獻(xiàn)[49]基于濾波技術(shù)提出了一種時(shí)序關(guān)聯(lián)數(shù)據(jù)的發(fā)布方案CTS-DP,保證在數(shù)據(jù)關(guān)聯(lián)的情況下,發(fā)布的結(jié)果序列與添加關(guān)聯(lián)噪聲后的序列滿(mǎn)足差分隱私要求;同時(shí),攻擊者不能通過(guò)修正技術(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í)時(shí)交通速度估計(jì)和建筑物占用情況預(yù)測(cè))中,并提出了噪聲添加的優(yōu)化方案.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4) 所有user 級(jí)隱私保護(hù)方案也分為實(shí)時(shí)在線處理和離線處理兩種方式.除FAST 和SafeZone 可以進(jìn)行在線數(shù)據(jù)流的處理,其余所有方案都為離線數(shù)據(jù)處理.同時(shí),大多數(shù)持續(xù)監(jiān)控任務(wù)還都是基于count 的簡(jiǎn)單統(tǒng)計(jì),但實(shí)際應(yīng)用中往往存在一些復(fù)雜的數(shù)據(jù)分析任務(wù).靜態(tài)數(shù)據(jù)集上已有針對(duì)這些復(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 級(jí)隱私方案的對(duì)比分析

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

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

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

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

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

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

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

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

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

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

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

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

6 未來(lái)研究展望

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

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

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

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

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

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

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

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

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

在持續(xù)監(jiān)控場(chǎng)景中,通常參與者對(duì)自己的數(shù)據(jù)有不同的隱私要求,用統(tǒng)一要求來(lái)處理所有參與者的信息,可能對(duì)一些用戶(hù)來(lái)說(shuō)隱私保障太低,而對(duì)另外一些用戶(hù)又可能要求太高.因此,如何結(jié)合用戶(hù)隱私需求,讓用戶(hù)定義個(gè)人的隱私級(jí)別,是一個(gè)值得研究的問(wèn)題[72-74].持續(xù)監(jiān)控下,個(gè)性化的隱私保護(hù)研究需要考慮以下問(wèn)題:一是不同用戶(hù)具有不同的隱私保護(hù)要求;二是對(duì)同一用戶(hù),不同的項(xiàng)目也會(huì)有不同的隱私保護(hù)要求;三是持續(xù)監(jiān)控下,隨著時(shí)間的推移,用戶(hù)和項(xiàng)目的隱私級(jí)別也會(huì)有相應(yīng)的變化.個(gè)性化差分隱私的隱私保護(hù)級(jí)別跟隱私預(yù)算大小相關(guān),隱私預(yù)算越小,隱私保護(hù)強(qiáng)度越高;隱私預(yù)算越大,隱私保護(hù)強(qiáng)度越低.在該類(lèi)研究中,如何針對(duì)多個(gè)隱私預(yù)算,采用隨機(jī)響應(yīng)技術(shù)或噪聲機(jī)制等差分隱私實(shí)現(xiàn)技術(shù),設(shè)計(jì)滿(mǎn)足所有隱私預(yù)算要求的實(shí)現(xiàn)方案是重點(diǎn)問(wè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)用場(chǎng)景多為分布式的應(yīng)用.在這種場(chǎng)景下,數(shù)據(jù)的收集往往類(lèi)似于問(wèn)卷調(diào)查,數(shù)據(jù)的管理者往往是不可信的第三方.同時(shí),由于分布式場(chǎng)景中收集的數(shù)據(jù)量特別大并且計(jì)算代價(jià)非常高,中心化的差分隱私技術(shù)不適合這種場(chǎng)景.目前,一些研究工作[75,76]提出了本地化差分隱私技術(shù)(LDP)方案,通過(guò)采用隨機(jī)響應(yīng)技術(shù)對(duì)個(gè)體數(shù)據(jù)進(jìn)行正向和負(fù)向的擾動(dòng),最終通過(guò)聚合大量的擾動(dòng)結(jié)果來(lái)抵消添加在其中的正負(fù)向噪聲,從而得到有效的統(tǒng)計(jì)結(jié)果.如何將LDP 技術(shù)應(yīng)用到持續(xù)監(jiān)控下的數(shù)據(jù)發(fā)布和分析任務(wù)中,是未來(lái)值得研究的一個(gè)方向.

7 結(jié)束語(yǔ)

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