亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        本地差分隱私頻率估計研究綜述

        2021-02-04 06:54:00王廣藝
        軟件導刊 2021年1期
        關鍵詞:用戶

        王廣藝,楊 庚

        (1.南京郵電大學計算機學院、軟件學院、網(wǎng)絡空間安全學院;2.江蘇省大數(shù)據(jù)安全與智能處理重點實驗室,江蘇南京 210023)

        0 引言

        頻率估計是數(shù)據(jù)挖掘領域研究的一個基本問題,旨在計算特定數(shù)據(jù)項出現(xiàn)的頻率,有助于云服務運營商了解客戶端軟件最新統(tǒng)計數(shù)據(jù),檢測惡意軟件行為,也可應用于頻繁出現(xiàn)的數(shù)據(jù)項(heavy hitter)查詢、用戶行為預測等。然而,如果直接采集用戶信息,可能存在嚴重的隱私泄露隱患,攻擊者可通過鏈接攻擊、前景知識攻擊等方式推測用戶持有的數(shù)據(jù)項,不可信的第三方數(shù)據(jù)收集者也可能意外泄露用戶敏感信息。如何高效地兼顧隱私保護與頻率估計準確性是數(shù)據(jù)挖掘領域亟需解決的問題。

        差分隱私(Differential Privacy,DP)[1]是一種基于數(shù)據(jù)擾動的隱私保護方法,具有嚴格的數(shù)學定義,可對隱私保護程度進行量化分析;同時,差分隱私無需考慮特殊的攻擊假設,攻擊者無法根據(jù)不同的輸出判斷記錄是否在原數(shù)據(jù)集中。差分隱私分為中心差分隱私(Central Differential Privacy,CDP)和本地差分隱私(Local Differential Privacy,LDP)[2-4],因而針對頻率估計問題的差分隱私算法包括CDP 頻率估計算法和LDP 頻率估計算法。

        在傳統(tǒng)CDP 頻率估計中,數(shù)據(jù)管理員向數(shù)據(jù)庫添加隨機化噪聲,發(fā)布查詢結果。CDP 頻率估計可與機器學習算法深度融合,如頻繁項集挖掘、頻繁序列挖掘、頻繁子圖挖掘等[5]。但是,由于數(shù)據(jù)存儲系統(tǒng)安全性、用戶對數(shù)據(jù)管理員的信任度等因素限制,CDP 頻率估計在實際應用中存在較大局限。

        為了應對CDP 頻率估計存在的問題,Kasiviswanathan等[3]于2011 年正式提出LDP。LDP 直接在用戶端擾動數(shù)據(jù)編碼結果,將其發(fā)送至服務器,之后服務器進行統(tǒng)計查詢。由于真實數(shù)據(jù)一直保留在用戶設備端,服務器不需要承擔隱私泄露的風險。LDP 具有輕量化的優(yōu)勢,在計算能力較弱的設備上也能輕松實現(xiàn)。目前LDP 頻率估計已被應用于微軟Windows10 操作系統(tǒng)[6]、小米MIUI 等以提升軟件質量、改進用戶體驗。

        但是,LDP 頻率估計也存在通信成本較高、添加的噪聲較多、依賴的用戶規(guī)模較大和高維數(shù)據(jù)分析準確性較低等問題。針對這些問題,已有研究聚焦于如何進一步提高LDP 頻率估計的實用性?,F(xiàn)有方法主要分為三類,第一類是單值頻率估計方法,如Rappor 算法[7]、HCMS 算法[8]等;第二類是泛化頻率估計方法,如DE 算法、OUE 算法、OLH算法等[9];第三類是集合數(shù)據(jù)頻率估計方法,如LDPMiner算法[10]、SVSM 算法[11]、PrivSet 算法[12]等。本文著重介紹LDP 在這3 種頻率估計中的應用,深入分析不同算法性能,對下一步研究工作進行展望。

        1 LDP 頻率估計基礎知識

        1.1 本地差分隱私

        LDP 是一種強隱私保護方法,該技術可收集單個隨機答案,給予用戶一定的可否認性,也使數(shù)據(jù)收集者免于隱私泄露的風險。同時,通過分析大量該類隨機數(shù)據(jù),數(shù)據(jù)收集者仍可建立準確的統(tǒng)計模型。

        定義1 ε-本地差分隱私[4]。給定算法M,定義域為Domain(M),值域為Range(M)。M滿足本地差分隱私,當且僅當對任意一對輸入t和t’(t,t’∈Domain(M)),成立不等式為:

        其中,t*?Range(M)。ε(ε>0)稱為隱私預算。ε越小表示隱私性越好、可用性越差。

        差分隱私有3 個重要特性:①序列組合性[13]。給定z個隱私算法{f1,f2,…fz}和數(shù)據(jù)集D,執(zhí)行在D上的fi滿足εi(1≤i≤z)-差分隱私,則z個算法組合算法滿足∑iεi-差分隱私;②并行組合性[13]。將數(shù)據(jù)集D分成z個不相交的子集,D={D1,D2,…Dz},執(zhí)行在每個子數(shù)據(jù)集上的算法滿足εi(1≤i≤z)-差分隱私,則整個算法滿足max{εi}-差分隱私;③后期處理的影響[14]。對差分隱私算法的結果作后期處理,則算法仍滿足差分隱私,且隱私保護水平與原先算法保持一致。

        CDP 具備這3 條性質,LDP 兼具第1、3 條性質。LDP沒有直接的并行組合性,因為每個用戶只有1 條記錄,不能被切分。

        定義2 敏感度[14]。敏感度是差分隱私中的1 個重要概念。對于任意1 個函數(shù)function:D→Rd,敏感度Δ(func?tion)定義為:

        R表示映射的實數(shù)空間,d表示函數(shù)function的查詢維度,D和D’是任意兩個鄰近數(shù)據(jù)集(D和D’差別至多為1個記錄)。

        1.2 LDP 頻率估計

        LDP 頻率估計指為用戶提供LDP 保護的同時確定數(shù)據(jù)項頻率的過程。給定數(shù)據(jù)集D={v1,v2,…vn},對任意元素v∈D,算法f的目標是以滿足LDP 的方式計算v出現(xiàn)的頻率。算法f主要分為3 步:①將用戶值編碼成1 個向量或1 個數(shù);②在用戶端擾動編碼結果;③服務器解碼聚合和校正。隨機響應[15]是算法f采取的主流擾動機制,確保數(shù)據(jù)集在輸出信息時受單條記錄的影響始終低于某個閾值。針對隨機響應舉例如下:當回答1 個二值問題時,回答者秘密地拋擲一枚不均勻的硬幣(正面朝上的概率為Pr,反面朝上的概率為1-Pr,Pr>0.5)。若正面朝上,回答真實答案;若反面朝上,回答相反答案。根據(jù)LDP 定義,eε=Pr(/1-Pr)。

        差分隱私還具有隱私增益性[16]。在設計自適應頻率估計算法時,隱私增益性是否成立是算法選擇的重要指標。隱私增益性表示通過使用更小的采樣率,使算法達到更高的隱私保護水平。具體而言,將差分隱私算法f應用到數(shù)據(jù)集D,利用采樣率β(β<1)從原始數(shù)據(jù)集中獲得D。為滿足ε-LDP,算法f可使用更大的隱私預算ε’(ε’>ε)。ε’與ε的關系如式(3)所示。

        該性質成立與否取決于算法f的內(nèi)部結構。

        1.3 頻繁項集挖掘

        頻繁項集挖掘是數(shù)據(jù)挖掘領域的一項重要技術,旨在找出頻繁出現(xiàn)在事務數(shù)據(jù)集中的項集[17]。設D是事務數(shù)據(jù)集,D={D1,D2,…Dn},D中數(shù)據(jù)項的集合I={item1,item2,…itemsize},Di?I(1≤i≤n)。設非空集合set?I,則稱set為1個項集。set的支持度是D中包含set的事務計數(shù)。若set的支持度大于預定義閾值λ,則稱set為頻繁項集。頻繁項集具有極重要的單調性:頻繁項集子項集一定是頻繁的,非頻繁項集的超集一定是非頻繁的。

        頻繁項集挖掘的經(jīng)典算法包括Apriori 算法[18]、FPGrowth 算法[19]和Eclat 算法[20]。Apriori 算法通過限制產(chǎn)生候選項集挖掘頻繁模式,F(xiàn)P-Growth 算法借助頻繁模式樹發(fā)現(xiàn)頻繁項集,而Eclat 算法采用倒排思想。

        項集填充采樣是頻繁項集挖掘過程中常用方法[10]。首先指定長度參數(shù)len、項集itemset、額外項集合dummy={i1,i2,…ilen},對任意i∈dummy,i?I。額外項在計算頻率時忽略不計。若項集長度|itemset|<len,則從dummy中隨機挑選len-|itemset|個不同的項添加到itemset中;若|itemset|>len,則從itemset中均勻采樣len個項構成新項集,如果itemset無序,可直接截斷。將itemset長度統(tǒng)一轉化為len后,從itemset中均勻采樣單個數(shù)據(jù)項輸出,記輸出項為v。

        2 LDP 頻率估計性能分析

        盡管LDP 頻率估計為用戶和數(shù)據(jù)收集者提供了很強的隱私保證,但是LDP 是以最嚴格的假設為基礎,即假設攻擊者擁有最大背景知識,而這在實際情況中十分罕見。由于LDP 對隱私性的保護過于嚴格,這在很大程度上影響了結果可用性。在許多應用中,LDP 頻率估計也暴露出一些問題,如通信成本較高、隨機化噪聲較多、依賴數(shù)據(jù)量較大和高維數(shù)據(jù)分析準確性較低等,因此,LDP 算法應當再三權衡隱私性、可用性、數(shù)據(jù)量的關系。

        受限于用戶設備的網(wǎng)絡和電量等因素,LDP 頻率估計應當維持合理的通信成本。然而,LDP 在用戶端對數(shù)據(jù)的編碼結果通常為1 個向量,為了提高頻率估計的準確性,用戶端應當發(fā)送盡可能多的坐標。此外,在LDP 頻率估計中,用戶可能需要參與多個查詢?nèi)蝿?,用戶和服務器之間會進行多次通信。上述方式將增加通信成本。當用戶記錄是高維數(shù)據(jù)時,通信代價也較高。

        由于在CDP 中敏感度是常數(shù),所以CDP 噪聲為Ω(1)。然而,在LDP 中,任意兩個用戶不知曉對方的記錄,因此,LDP 不存在全局敏感性的概念。LDP 對每個用戶數(shù)據(jù)都添加噪聲,擾動結果被發(fā)送至服務器。即使每個用戶的隨機化噪聲均為常數(shù),服務器聚合結果的噪聲也會達到Ω(n0.5)(n為用戶個數(shù))。因此,LDP 和CDP 相比,添加的隨機噪聲較多,這導致準確性較差。

        在設計LDP 頻率估計算法時,為了抵消正負向噪聲,服務器需聚合大量的擾動結果,該方法需要較大的數(shù)據(jù)量。然而,在網(wǎng)絡空間安全等領域,用戶規(guī)模較小是常見現(xiàn)象。例如,當一位信息安全工程師正在分析針對特定漏洞的惡意軟件行為時,只有受到惡意軟件感染的用戶的觀察報告才有意義,但由于惡意軟件的針對性,受感染的用戶數(shù)量可能很少。由于用戶規(guī)模無法達到LDP 依賴的數(shù)據(jù)量大小,這會導致統(tǒng)計值與真實結果之間的偏離程度更為明顯。

        當用戶記錄是高維數(shù)據(jù)時,即每條用戶記錄包含多個數(shù)據(jù)項,一個直觀的解決方案是分割隱私預算,多次調用LDP 算法分別采集每個位置數(shù)據(jù)項,利用差分隱私序列組合性使算法滿足LDP。然而,由于數(shù)據(jù)高維性,該方案致使每個數(shù)據(jù)項分配到的隱私預算很少,這降低了查詢準確性和查詢效率。

        3 頻率估計中的本地差分隱私保護方法

        LDP 頻率估計需要解決上述性能分析問題,但是目前LDP 頻率估計方法仍然不能達到這一目的,所以更多的科研人員重點研究怎樣為頻率估計提供更可靠的LDP 保證和更高的查詢準確性。這些研究主要包含3 類方法:單值頻率估計方法、泛化頻率估計方法和集合數(shù)據(jù)頻率估計方法。本文將分別討論這3 種類型的LDP 方法在頻率估計中的應用。

        3.1 單值頻率估計

        單值頻率估計指每個用戶只有一個數(shù)據(jù)項,用戶將自身數(shù)據(jù)編碼加噪后發(fā)送至服務器,服務器會根據(jù)候選項集合分析大量隨機數(shù)據(jù),建立統(tǒng)計模型。單值頻率估計主要采用的技術包括哈希函數(shù)和矩陣變換,這兩種技術可以在降低通信成本的前提下獲得合理的統(tǒng)計準確性。谷歌Rappor 算法[7]、蘋果CMS 算法[8]和HCMS 算法[8]均應用了哈希函數(shù)技術,其中HCMS 算法還應用了矩陣變換技術。

        3.1.1 Rappor 算法

        Rappor 算法將隨機響應與布隆過濾串[21]結合。設布隆過濾串B(也稱比特串)的長度為k,哈希函數(shù)個數(shù)為h。用戶首先使用布隆過濾器將v映射到B,然后使用擾動機制對B添加噪聲。擾動過程分為永久隨機響應和瞬時隨機響應。記永久隨機響應的結果為B’,B’在用戶端被緩存,用戶每次使用真實數(shù)據(jù)時B’會代替B,這樣即使用戶值被報告多次,攻擊者也無法推斷出用戶真實答案。給定概率參數(shù)r,對于B中每個坐標i,有:

        記瞬時隨機響應的結果S=(s1,s2,…sk),初始化S為0,指定概率參數(shù)p、q,則:

        用戶發(fā)送S。

        永久隨機響應滿足ε1-LDP,其中,

        在式(6)中,若不考慮布隆過濾器,如果1 個比特串長度為1,Pr(0|0)=Pr(1|1)=1-0.5r,Pr(1|0)=Pr(0|1)=0.5r,則此時隱私保護程度為ln((1-0.5r)/0.5r)。再經(jīng)過布隆過濾后,每一個原始值被映射到的比特串中最多有h個1,對于兩個原始輸入,它們的比特串最多只有2h位不一樣。因此,式(6)中隱私保護程度需乘以2h。

        瞬時隨機響應的結果依賴p,q,r。

        瞬時隨機響應滿足ε2-LDP,其中,

        為了降低哈希函數(shù)沖突概率,每個用戶被隨機分配到1 個組中。假設有num個組,用戶在發(fā)送數(shù)據(jù)時需說明自己屬于哪個組。由于每個用戶組在布隆過濾器中使用不同的哈希函數(shù),若num太小,則分組很可能造成哈希函數(shù)值碰撞;若num太大,每個組用戶數(shù)會很少,這導致頻率估計中誤差較大。

        現(xiàn)以1 個具體應用案例說明服務器端解碼過程。假設詞庫中只有單詞1、單詞2 和單詞3,對應布隆過濾串分別為10 001 000、01 000 010 和00 010 010。服務器需要統(tǒng)計詞庫中每個單詞出現(xiàn)的次數(shù)。用戶將經(jīng)過永久隨機響應的比特串保存在本地。用戶每使用1 次單詞,就經(jīng)過1次瞬時隨機響應把比特串發(fā)送至服務器。假設單詞1 出現(xiàn)兩次,單詞2 和單詞3 出現(xiàn)1 次,對應比特相加得到比特串bitString=21 012 020。

        服務器的目標是確定bitString,它采集每一個比特上1的總數(shù)(一共有k個比特)。由于每個比特相互獨立,服務器可先只分析1 列。設第i個比特有w個1,n-w個0(n為用戶個數(shù)),服務器平均收到的1 的個數(shù)為count。

        服務器通過式(10)估計原始值中每個比特1 的個數(shù),本例中,服務器計算得到bitString=21 012 020。由于每個用戶組哈希函數(shù)公開,服務器了解每個單詞對應的布隆過濾串,結合bitString計算出單詞1 出現(xiàn)兩次,單詞2 和單詞3 均出現(xiàn)1 次。此外,服務器還需借助假設檢驗、最小二乘法和LASSO 回歸進一步擬合詞頻。Rappor 算法中的哈希函數(shù)導致服務器端復雜的解碼過程,而且哈希函數(shù)值碰撞問題依然存在。

        3.1.2 CMS 算法

        用戶從哈希函數(shù)集合{h1,h2,…h(huán)k}中均勻采樣1 個哈希函數(shù),將項v散列到輸出域中的1 個數(shù),結果用長度為m的向量vector單熱編碼表示(散列結果對應坐標置為1,其余坐標為0)。用戶對向量中的每個坐標以概率Pr作真實回答,以概率1-Pr作相反回答。用戶將哈希函數(shù)索引與向量發(fā)送至服務器。此時vector 只有一個坐標為1,敏感度為2,所以為滿足差分隱私,Pr取值為:

        服務器使用所有來自用戶的向量構建k×m的矩陣Matrix。每當1 個向量到達服務器,服務器將向量添加到Matrix的第j行(j為哈希函數(shù)索引)。服務器取出Matrix[j,hj(v)](1≤j≤k)并計算均值。

        3.1.3 HCMS 算法

        HCMS 算法首先類似CMS 算法,用戶得到向量vector。設H為哈達瑪基變換矩陣,vector’=H·vector。vector’中的每個坐標取1 或-1。用戶從vector’中隨機采樣1 個坐標,對該坐標以概率eε/(1+eε)作真實回答。用戶將哈希函數(shù)索引、vector’采樣索引、坐標值發(fā)送至服務器。

        服務器使用來自用戶的報告值構建矩陣Matrix。Ma?trix的第(j,index)個元素聚合了用戶使用哈希函數(shù)hj與采樣索引index的坐標值。服務器使用哈達瑪矩陣的逆矩陣對Matrix作矩陣變換,最后計算Matrix[j,hj(v)](1≤j≤k)k個元素的均值。

        HCMS 算法中的矩陣變換與Rappor 算法中的哈希函數(shù)功能類似,可降低通信成本,但是在編碼過程中也會造成額外的信息損失。

        3.2 泛化頻率估計

        為了比較同等隱私保護水平下不同單值頻率估計算法計算復雜度、查詢準確性和通信成本,需將單值頻率估計推廣到一般情形。泛化頻率估計的核心問題是設計合適的擾動機制。擾動的目的是保證得到頻率的無偏估計,同時盡可能減小統(tǒng)計值方差。該問題的主要挑戰(zhàn)是減小高維數(shù)據(jù)帶來的影響。

        Wang 等[9]提出了一個泛化頻率估計機制:pure LDP。pure LDP 首先定義函數(shù)Support,Support(y)表示通過y可以確定出現(xiàn)的用戶值構成的集合。定義概率p*、q*為:

        PE是編碼擾動函數(shù),{y|v1∈Support(y)}是v1的支持集合。p*表示任意值v1被映射到v1的支持集合的概率,q*表示任意其他值被映射到v1的支持集合的概率。當且僅當存在概率p*和q*,p*>q*時,機制pure LDP 成立。為了滿足ε-LDP,q*>0,p*/q*≤eε。

        在pure LDP 中,假設共有n個用戶,元素i出現(xiàn)的真實次數(shù)為c(i),可通過式(14)計算c(i)的無偏估計。

        其中yj是用戶j發(fā)送的值。

        文獻[9]得到了3 種效果較好的擾動方法:DE、OUE、OLH,具體描述如下:

        DE 算法:設用戶值為v,項空間大小為|I|。擾動公式為:

        此時Support(i)={i},p*=p,q*=q。

        OUE 算法:用戶項被單熱編碼成向量B。擾動公式為:

        因為eε=(p(1-q))/((1-p)q),所以可作如下變換,ε=ε1+ε2,eε1=p/(1-p),eε2=(1-q)/q。ε1和ε2分別是傳送比特1與比特0 消耗的隱私預算。由于向量中只有1 個坐標為1,因此,用戶在發(fā)送比特0 時應該分配更多的隱私預算。在極端情況下,令ε1=0,ε2=ε,可得到p和q的最優(yōu)值。OUE 的支持函數(shù)Support(B)={i|B[i]=1},p*=p,q*=q。

        OLH 算法:設H為哈希函數(shù)集合,用戶從H中均勻采樣得到函數(shù)function,function將用戶值v映射到[g]={0,1,…g-1}中的一個元素b,其中g≥2。OLH 的信息損失包含兩個方面:編碼階段的信息損失與差分隱私擾動引起的信息損失。當g較大時,LDP 頻率估計算法在編碼階段可保留更多信息,在隨機響應時則損失更多信息。通過對估計值方差求偏微分,OLH 算法得到g的最優(yōu)值為。擾動公式為:

        該方法的支持函數(shù)Support(<function,b’>)={i|function(i)=b’},p*=0.5,q*=1/g。

        DE 在|I|較小時估計更準確。當|I|較大時,OUE 和OLH表現(xiàn)更好且準確性一致。OUE 計算成本低,通信成本高。OLH 通過應用哈希函數(shù)降低了通信成本,但同時增加了計算復雜度。

        為了滿足LDP,添加的噪聲可能導致許多項的估計頻率小于0。此外,LDP 算法可能導致頻率總和不等于1。Wang 等[22]指出服務器可以利用非負性(所有項頻率均大于等于0)和規(guī)范性(頻率總和為1)這一事實提高頻率估計準確性。算法利用先驗分布時,估計會偏向先驗分布。還考慮了多種利用先驗分布的算法,這些算法中有的只要求頻率滿足非負性,有的只要求頻率滿足規(guī)范性,有的要求兩個性質均被滿足。但是引入概率先驗分布又會帶來其它問題。例如,將所有負估計值改為0 可提高個別頻率估計值準確性,然而引入的正偏差會累積到范圍查詢中。

        Jiang 等[23]研究了本地信息隱私(Local Information Pri?vacy,LIP),LIP 對敵手的背景知識建模,利用概率先驗分布設計隱私保護機制。LIP 所需噪聲取決于隱私預算與數(shù)據(jù)先驗分布。LIP 根據(jù)先驗分布計算擾動參數(shù)。當數(shù)據(jù)值相當確定時,翻轉該值概率較小;當數(shù)據(jù)值發(fā)生概率較小時,LIP 通過較大的擾動概率保護其隱私。因此,LIP 得到了比LDP 更高的可用性。其構建了1 個通用機制估計收集到的數(shù)據(jù)項,該機制將估計值均方差最小化,可被視為隨機響應的一般形式。

        現(xiàn)有LDP 機制往往以相同的方式擾動數(shù)據(jù),或對輸入添加相同大小的噪聲。然而,在許多實際場景中,不同的輸入具有不同程度的敏感性,因此,用戶需要不同級別的隱私保護水平。Gu 等[24]設計了輸入判別隱私保護算法,以反映不同輸入的隱私要求,并首次提出輸入判別本地差分隱私(InputDiscriminative Local Differential Privacy,IDLDP)的概念,設計了基于一元編碼的IDUE 算法,通過求解最優(yōu)化問題計算擾動概率。由于輸入判別保護的存在,IDUE 算法實用性更高。

        已有研究主要目標是提高輸出結果可用性,DP 算法安全性被忽略。Cao 等[25]研究了針對LDP 頻率估計的數(shù)據(jù)投毒攻擊。其研究表明為了根據(jù)攻擊者的需要操縱數(shù)據(jù)分析結果,攻擊者可注入虛假用戶,虛假用戶將偽造的數(shù)據(jù)發(fā)送至服務器。不同的LDP 頻率估計算法對投毒攻擊有不同的安全級別。例如,OUE 和OLH 對投毒攻擊具有相似的安全級別;當項數(shù)目大于閾值時,DE 的安全性低于OUE 和OLH。該研究還設計了兩種對策防御投毒攻擊。在第1 個對策中,服務器對項頻率的概率分布建模,要求項估計頻率滿足非負性和規(guī)范性。由于投毒攻擊是通過虛假用戶偽造數(shù)據(jù),所以虛假用戶的數(shù)據(jù)可能遵循與真實用戶數(shù)據(jù)不同的模式,因此,在第2 個對策中,服務器通過分析用戶數(shù)據(jù)統(tǒng)計模式檢測虛假用戶。但該研究未涉及如何將投毒攻擊推廣到LDP 頻繁模式挖掘。

        3.3 集合數(shù)據(jù)頻率估計

        集合數(shù)據(jù)頻率估計研究的是當每條用戶記錄中包含多個數(shù)據(jù)項時如何進行數(shù)據(jù)發(fā)布。集合數(shù)據(jù)頻率估計包括heavy hitter 查詢、頻繁項集挖掘、數(shù)據(jù)項分布估計和高維數(shù)據(jù)分析等。不同于單值頻率估計,集合數(shù)據(jù)頻率估計通常需考慮隱私預算分配問題。

        heavy hitter 查詢目的是發(fā)現(xiàn)頻率高于給定閾值的項。由于每個用戶數(shù)據(jù)項個數(shù)不同,因此,該問題具有挑戰(zhàn)性。針對該問題,Qin 等[10]設計了LDPMiner 算法。LDPMiner使用填充采樣技術,若用戶端不填充項集,則很難計算單個數(shù)據(jù)項被采樣的概率,服務器也很難對頻率進行準確估計。

        設每個用戶ui的數(shù)據(jù)集合為vi,長度參數(shù)為len,用戶數(shù)為n,項空間大小為d,第j個項出現(xiàn)次數(shù)為cj,則

        服務器需確定top-k頻繁項及其對應頻率。

        LDPMiner 包含兩個階段:

        階段一:用戶使用len對事務填充采樣得到v,使用一半的隱私預算對v進行擾動,將擾動結果發(fā)送至服務器。服務器確定估計頻率最高的2k個項,構建候選項集合IC,將IC廣播給用戶。

        階段二:用戶計算IC與事務的交集,使用取值為2k的長度參數(shù)對交集填充采樣得到v,使用一半的隱私預算對v進行隨機響應,將擾動結果發(fā)送至服務器。服務器需將候選項統(tǒng)計計數(shù)乘以2k。

        因為兩個階段均滿足差分隱私,根據(jù)差分隱私的序列組合性,LDPMiner 滿足ε-LDP。LDPMiner 的缺點是只能確定頻繁項,不能挖掘頻繁項集。

        目前已有多篇文獻研究了CDP 頻繁項集挖掘[26-28],但是針對LDP 頻繁模式挖掘問題的研究很少。Wang 等[11]設計了heavy hitter 查詢算法SVIM 與頻繁項集挖掘算法SVSM,發(fā)現(xiàn)GRR 算法(即前文所述的DE 算法)具備隱私增益性,而OUE 算法和OLH 算法不具備該性質。依據(jù)該性質,Wang 等設計了自適應頻率估計機制Adaptive。Adaptive 機制可根據(jù)隱私預算ε、項空間大小d、長度參數(shù)len選擇合適的頻率估計算法。

        其中,GRR 和OUE 括號里的參數(shù)表示算法被調用時實際使用的隱私預算。

        不同于LDPMiner 采取分割隱私預算的策略,SVIM 算法將用戶分成3 組,每組用戶參與1 項查詢?nèi)蝿铡VIM分成3 個階段:

        階段1:第1 組用戶使用取值為1 的長度參數(shù)對事務填充采樣得到v,使用Adaptive 機制報告v。服務器統(tǒng)計頻率最高的2k個項,構建頻繁項候選集合IC,把IC廣播給下一組用戶。

        階段2:第2 組用戶首先計算事務與IC的交集,之后使用Adaptive 機制報告交集大小。服務器計算len(保證90% 的交集長度不大于len),之后將IC和len發(fā)送至下一組用戶。

        階段3:第3 組用戶求事務與IC的交集,使用len對交集填充采樣得到v,通過Adaptive 機制報告v。服務器計算IC中每個項的頻率,得到top-k頻繁項及對應頻率。

        頻繁項集挖掘的挑戰(zhàn)是如何減小頻繁項集候選集合大小。SVSM 算法將用戶分成5 組,對應該算法5 個階段,前3 個階段的算法流程和SVIM 一致。

        階段4:記top-k頻繁項構成的集合為topKS。服務器根據(jù)topKS構建頻繁項集候選集合:生成topKS所有子集,在生成過程中,一旦發(fā)現(xiàn)子集長度大于,則直接丟棄該子集。因為若子集長度大于,該項集非空子集個數(shù)會大于k,而子集支持度大于等于項集支持度,所以該項集不可能是頻繁項集。對topKS的一個子集X而言,服務器使用式(20)估計X頻率。

        其中Φ(x)是項x的頻率。服務器選擇頻率最高的2k個子集構成頻繁項集的候選集合ISC,把ISC發(fā)送至下一組用戶。第4 組用戶尋找同時在事務和ISC中的項集,滿足條件的項集構成集合vs,使用Adaptive 機制報告vs大小。服務器計算len,之后將ISC和len發(fā)送至下一組用戶。

        階段5:第5 組用戶尋找同時在事務和ISC中的項集,滿足條件的項集構成集合vs。vs是集合的集合,但同樣可采用類似填充采樣的方法獲取vs中的項集v。用戶使用Adaptive 機制報告v。服務器對ISC中的每個項集計算頻率,將頻率乘以校正因子以提高估計準確性。由此,服務器得到top-k頻繁項集。

        由于猜測頻率,SVSM 算法統(tǒng)計誤差變大。填充長度的選擇是主觀的,目前沒有理論支持。如何自適應地選擇合理的填充長度依然是一個亟待解決的問題。

        Wang 等[12]設計了一種集合數(shù)據(jù)聚合算法:PrivSet。PrivSet 可幫助服務器統(tǒng)計分析集合數(shù)據(jù)(如數(shù)據(jù)項的分布估計、集合大小的分布估計)。在PrivSet 算法中,每個用戶獨立使用差分隱私指數(shù)機制[29]輸出元素定義域的1 個子集,該過程不需要分割隱私預算。根據(jù)元素定義域大小、集合中的最大項目數(shù)和隱私預算等參數(shù)校準輸出子集的大小及其輸出概率。為了解決集合異構性問題,PrivSet 算法將填充項添加到集合數(shù)據(jù)中。有了這些填充項,服務器可估計用戶集合大小分布,該估計過程不會造成額外的隱私損失。

        Wang 等[30]研究了LDP 高維數(shù)據(jù)分析問題,指出當用戶記錄同時包含數(shù)值屬性和分類屬性時,服務器可分別對集合中的數(shù)值屬性與分類屬性進行均值估計和頻率估計。值得注意的是,一旦用戶端使用單熱編碼將某個分類屬性編碼成長度為total的向量(total為該屬性所有取值情況的個數(shù)),求解頻率估計可以轉化為求解均值估計。提出了分段機制PM 和混合機制HM,并將PM 和HM 擴展到多維數(shù)據(jù)中。該方案可用于傳統(tǒng)機器學習(如線性回歸、邏輯回歸和SVM 分類),但目前尚不清楚如何將其應用于更深層次的數(shù)據(jù)分析任務(如深度神經(jīng)網(wǎng)絡)。

        4 未來挑戰(zhàn)

        當前已有一些綜述性文獻針對LDP 的發(fā)展方向問題進行了研究。如文獻[31-32]主要關注機器學習中的本地差分隱私保護;文獻[33]主要側重于LDP 在安全車聯(lián)網(wǎng)中可能的應用方向;文獻[34]介紹了LDP 空間數(shù)據(jù)采集問題;文獻[35]總結了LDP 頻率估計的主要問題,包括統(tǒng)計準確性問題、數(shù)據(jù)安全性問題、計算復雜度問題和通信成本問題。針對LDP 頻率估計的現(xiàn)有解決方案只能在一定范圍內(nèi)、一定條件下取得理想效果。與CDP 相比,LDP 是一個相對較新的研究領域,而且由于LDP 的性質獨特,科研人員仍面臨不少挑戰(zhàn)。

        (1)融合CDP 和LDP 的優(yōu)勢難度很大?,F(xiàn)有差分隱私文獻通常將CDP 和LDP 分開考慮,但這兩種隱私保護模型并不是對立關系。融合CDP 和LDP 可以允許用戶在本地添加少量噪聲,同時實現(xiàn)較高級別的隱私保護程度。然而,該操作涉及安全混洗和復雜的數(shù)學推導證明。安全混洗通常是黑盒模型,缺乏具體的實現(xiàn)方法。文獻[36]設計了混合差分隱私方案以查詢heavy hitter,計算Web 搜索日志中最流行的記錄。該方案對內(nèi)測用戶和普通用戶分組分別應用不同的隱私保護模型,提高了輸出結果可用性,但需要付出額外的預處理成本以劃分信任關系。

        后續(xù)研究需繼續(xù)關注如何更好地實現(xiàn)CDP 和LDP 的優(yōu)勢互補。例如借助密碼學原語和非串通的服務器,使隱私保護頻率估計能夠提供近似CDP 的準確性保證,同時類似LDP 不依賴可靠的第三方數(shù)據(jù)收集者。

        (2)自適應分配隱私預算方法不足。當用戶記錄是高維數(shù)據(jù)或用戶參與多個查詢?nèi)蝿諘r,算法通常需分配隱私預算。隱私預算分配決定了差分隱私隨機化噪聲,影響隱私保護水平和結果可用性。若隱私預算分配次數(shù)較多,會迅速增加噪聲,導致數(shù)據(jù)可用性急劇下降。因此,LDP 頻率估計需優(yōu)化隱私預算分配。然而,由于許多LDP 算法創(chuàng)新點與隱私預算分配無關,它們通常將隱私預算均勻分配。

        在CDP 中,王璇[37]利用泰勒級數(shù)、p級數(shù)、特殊級數(shù)分配隱私預算,減小了噪聲增量速度,分析比較了不同隱私預算分配方案的優(yōu)缺點。研究人員可以考慮在LDP 中運用級數(shù)知識自適應分配隱私預算,觀察頻率估計算法性能可否進一步提高。

        (3)高維數(shù)據(jù)隱私效用權衡依然困難。LDP 高維數(shù)據(jù)分析取得隱私效用權衡是十分困難的。已有方法主要利用哈希函數(shù)[7,9]、矩陣投影[8,38](如哈達瑪矩陣、正交矩陣)處理該問題,但是現(xiàn)有方法主要聚焦于單值頻率估計。當算法處理集合數(shù)據(jù)時,通常采樣1 個或幾個數(shù)據(jù)項并將數(shù)據(jù)項發(fā)送至服務器。采樣可減小通信代價,但勢必導致統(tǒng)計準確性降低。

        未來可進一步關注LDP 高維數(shù)據(jù)統(tǒng)計方法,主要考慮兩個方面的問題:如何提高集合數(shù)據(jù)采樣效率和統(tǒng)計精度;如何借助數(shù)據(jù)項間的關聯(lián)進行降維,平衡查詢準確性與通信開銷。

        (4)缺乏實時數(shù)據(jù)發(fā)布方法。用戶數(shù)據(jù)可能隨時間發(fā)生變化,需服務器每隔一段時間重新計算統(tǒng)計值?,F(xiàn)有LDP 頻率估計方法主要關注靜態(tài)數(shù)據(jù),而許多現(xiàn)實場景要求數(shù)據(jù)發(fā)布方法具有連續(xù)數(shù)據(jù)發(fā)布能力。在發(fā)布每一次數(shù)據(jù)的過程中,服務器很難預知后續(xù)需發(fā)布的數(shù)據(jù)。每次發(fā)布數(shù)據(jù)均會累加噪聲方差,最終降低了數(shù)據(jù)可用性。因此,服務器需提高LDP 頻率估計連續(xù)數(shù)據(jù)發(fā)布的精確性和效率,滿足大規(guī)模連續(xù)數(shù)據(jù)發(fā)布的要求。在LDP 中,針對該問題的主要方法是緩存技術,然而當數(shù)據(jù)頻繁發(fā)生改變或數(shù)據(jù)變化劇烈時,緩存技術失效。

        LDP 實時數(shù)據(jù)發(fā)布需考慮兩種變化情況:①用戶個數(shù)如何變化;②用戶數(shù)據(jù)如何變化。同時,科研人員可使用滑動窗口模型[39]、自適應隱私預算分配、用戶動態(tài)分組等方法改進擴展LDP 連續(xù)數(shù)據(jù)頻率估計算法。

        5 結語

        隨著移動智能設備計算能力和存儲能力的不斷增強,眾包數(shù)據(jù)采集和數(shù)據(jù)挖掘技術迅速發(fā)展。同時個人隱私問題成為用戶關注焦點,隱私問題極大限制了數(shù)據(jù)挖掘在工業(yè)中的應用。因此,設計保護個人隱私的數(shù)據(jù)發(fā)布框架具有重要意義。

        LDP 作為一種新興的隱私保護模型,可同時保護用戶隱私和服務器隱私,成為信息安全領域研究熱點。由于當前LDP 頻率估計方法依然存在許多問題尚未解決,科研人員需繼續(xù)深入研究本地差分隱私保護,促進數(shù)據(jù)挖掘技術在實際應用中進一步發(fā)展。

        猜你喜歡
        用戶
        雅閣國內(nèi)用戶交付突破300萬輛
        車主之友(2022年4期)2022-08-27 00:58:26
        您撥打的用戶已戀愛,請稍后再哭
        關注用戶
        商用汽車(2016年11期)2016-12-19 01:20:16
        關注用戶
        商用汽車(2016年5期)2016-11-28 09:55:15
        兩新黨建新媒體用戶與全網(wǎng)新媒體用戶之間有何差別
        關注用戶
        商用汽車(2016年6期)2016-06-29 09:18:54
        關注用戶
        商用汽車(2016年4期)2016-05-09 01:23:12
        挖掘用戶需求尖端科技應用
        Camera360:拍出5億用戶
        100萬用戶
        蜜桃av噜噜一区二区三区| 亚洲精选自偷拍一区二| 久爱www人成免费网站| 99热久久精里都是精品6| 免费一区二区三区视频狠狠| 精品午夜中文字幕熟女| 日本不卡高字幕在线2019| 国产二级一片内射视频插放| 免费jjzz在线播放国产| 中文字幕久区久久中文字幕 | 夜夜爽夜夜叫夜夜高潮| 国产97色在线 | 日韩| 欧美日韩区1区2区3区| 国产一区二区美女主播| 每日更新在线观看av| 欧美日韩一区二区三区自拍| 日本a在线天堂| 亚洲成人一区二区三区不卡| 午夜射精日本三级| 最新国产日韩AV线| 偷拍av一区二区三区| 久久国产精品一区二区三区| 精品无码中文字幕在线| 白丝美女被狂躁免费视频网站| 久久综合五月天啪网亚洲精品| 亚洲国产日韩欧美综合a| 亚洲第一成人网站| 一本久道久久综合狠狠操| 日本女优在线一区二区三区| 国产69精品久久久久999小说| 在线观看日本一区二区| 日本一区二区三区四区在线视频| 色婷婷亚洲一区二区三区| 国产精品原创巨作AV女教师| 日韩精品夜色二区91久久久| 51国产偷自视频区视频| 欧美日韩一卡2卡三卡4卡 乱码欧美孕交 | 亚洲另类欧美综合久久图片区| 亚洲中文字幕无码二区在线| 一区二区三区四区午夜视频在线| 免费欧洲毛片a级视频老妇女|