基于不確定圖的隱私保護(hù)方法研究

胡 靜，史武超，顏 軍，吳振強(qiáng)

(陜西師范大學(xué) 計算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

1 概 述

進(jìn)入大數(shù)據(jù)時代，隨著移動互聯(lián)網(wǎng)的發(fā)展，人們在生活中可以隨時隨地產(chǎn)生數(shù)據(jù)，例如聊微信、轉(zhuǎn)發(fā)微博等。以微信為例，僅在2016年9月份，微信日登錄用戶達(dá)到了7.68億。由于社交網(wǎng)絡(luò)的發(fā)展與應(yīng)用，越來越多的研究轉(zhuǎn)移到社交網(wǎng)絡(luò)，使得社交網(wǎng)絡(luò)分析成為諸多學(xué)科的研究熱點(diǎn)。然而，政府部門、商業(yè)機(jī)構(gòu)對采集到的數(shù)據(jù)進(jìn)行發(fā)布與共享時，會導(dǎo)致用戶個人隱私的泄露。因此，在發(fā)布數(shù)據(jù)的同時保護(hù)用戶的隱私信息就成了大數(shù)據(jù)環(huán)境下面臨的一個重大課題。

近年來，學(xué)者們在隱私保護(hù)方面做了大量的工作，而且取得了豐碩的成果。如Sweeney提出的k-匿名技術(shù)[1]，該技術(shù)要求發(fā)布數(shù)據(jù)對象個體在同一等價類中至少與其他k-1個對象不可區(qū)分，每個個體身份被識別出來的概率至多為1/k，從而降低了隱私泄露的風(fēng)險。然而k-匿名技術(shù)不能抵抗同質(zhì)性攻擊。為了解決這一問題，Machanavajjhala等[2]提出了l-多樣性，Li等[3]提出了t-緊密性等k-匿名技術(shù)的改進(jìn)方法。但是這些方法難以定義攻擊者擁有的所有可能的背景知識，容易遭到背景知識攻擊且不能提供一種嚴(yán)格可證明的隱私保護(hù)程度。2006年Dwork提出的差分隱私技術(shù)解決了攻擊者可能的背景知識問題，并對隱私保護(hù)水平提供了量化評估方法[4]。

現(xiàn)有隱私保護(hù)方法主要適用于關(guān)系數(shù)據(jù)或者統(tǒng)計數(shù)據(jù)。在統(tǒng)計數(shù)據(jù)中，每個個體在統(tǒng)計上是相互獨(dú)立的；在關(guān)系數(shù)據(jù)中，關(guān)系隱私保護(hù)模型僅防范了將實(shí)體屬性值作為背景知識的隱私攻擊。然而，在社交網(wǎng)絡(luò)中，不僅要防止實(shí)體屬性值作為背景知識的攻擊，還要防止實(shí)體屬性值之間的關(guān)聯(lián)攻擊。因此，單純的關(guān)系數(shù)據(jù)或統(tǒng)計數(shù)據(jù)隱私保護(hù)方法不能滿足社交網(wǎng)絡(luò)中數(shù)據(jù)的隱私保護(hù)要求，需要提出與社交網(wǎng)絡(luò)數(shù)據(jù)特點(diǎn)相適應(yīng)的隱私保護(hù)方法。在社交網(wǎng)絡(luò)中，網(wǎng)絡(luò)中個體間的關(guān)系、社交網(wǎng)絡(luò)結(jié)構(gòu)、個體在結(jié)構(gòu)中位置的重要性等均可作為攻擊者的背景知識進(jìn)行隱私攻擊[5]。因此，社交網(wǎng)絡(luò)隱私保護(hù)一直是隱私保護(hù)研究的熱點(diǎn)領(lǐng)域。

社交網(wǎng)絡(luò)的隱私保護(hù)主要保護(hù)個體之間的關(guān)聯(lián)關(guān)系，因此將社交網(wǎng)絡(luò)抽象為網(wǎng)絡(luò)圖來進(jìn)行研究。圖結(jié)構(gòu)下的隱私保護(hù)算法可分為5種。

(1)頂點(diǎn)標(biāo)識符替換方法。BackStrom等[6]提出在發(fā)布真實(shí)圖數(shù)據(jù)之前用合成標(biāo)識符替換可識別屬性的匿名隱私保護(hù)方法，但容易受到背景知識的攻擊，攻擊者可以根據(jù)頂點(diǎn)結(jié)構(gòu)特征推斷出頂點(diǎn)的身份信息。

(2)邊修改方法。該方法主要操作是隨機(jī)增減邊或交換邊，根據(jù)不同條件又分為無約束的邊修改和有約束的邊修改。前者如Hay等利用隨機(jī)添加/刪除邊策略提出隨機(jī)擾動方法來匿名圖[7]，Bonchi等[8]提出基于熵匿名等級量化及Sparsification方法；后者如Liu等[9]提出基于邊修改方法的k-度匿名，龔衛(wèi)華等[10]提出保持網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定的k-度匿名隱私保護(hù)模型。

(3)頂點(diǎn)和邊的聚類方法。該方法將圖中的頂點(diǎn)和邊經(jīng)過泛化或聚類，變?yōu)槌夗旤c(diǎn)和超級邊，從而使某個頂點(diǎn)和邊的信息隱藏在這些超級頂點(diǎn)和超級邊中，如谷勇浩等[11]針對動態(tài)社交網(wǎng)絡(luò)數(shù)據(jù)發(fā)布提出一種基于聚類的動態(tài)圖發(fā)布算法；姜火文等[12]提出一種基于頂點(diǎn)連接結(jié)構(gòu)和屬性值屬性圖聚類匿名化方法。

(4)頂點(diǎn)和邊的差分隱私方法。如Hay等[13]提出節(jié)點(diǎn)差分隱私和邊差分隱私的概念；文獻(xiàn)[14]綜述了社交網(wǎng)絡(luò)中的差分隱私以及差分隱私在社交網(wǎng)絡(luò)中的應(yīng)用發(fā)展；蘭麗輝等[15]提出一種基于差分隱私的隨機(jī)擾動方法實(shí)現(xiàn)邊集邊權(quán)重的保護(hù)。

(5)邊的不確定性方法，即不確定圖方法。該方法通過對原始圖數(shù)據(jù)進(jìn)行處理，將圖中所有邊出現(xiàn)的可能性變成[0，1]區(qū)間內(nèi)的某個概率值，將確定的網(wǎng)絡(luò)圖以不確定圖的方式進(jìn)行數(shù)據(jù)發(fā)布，從而保護(hù)了網(wǎng)絡(luò)圖中用戶的隱私信息。

將不確定圖引入隱私保護(hù)是近年來提出的新的圖結(jié)構(gòu)數(shù)據(jù)隱私保護(hù)方法，該方法存在如下優(yōu)勢：對個體間的關(guān)系進(jìn)行了模糊化，將個體之間的確定關(guān)系變?yōu)椴淮_定關(guān)系；相對于邊修改方法，保護(hù)了圖結(jié)構(gòu)數(shù)據(jù)中實(shí)體之間的關(guān)系；沒有破壞數(shù)據(jù)的效用性，在保護(hù)隱私的基礎(chǔ)上不影響用戶進(jìn)行數(shù)據(jù)挖掘的數(shù)據(jù)效用。

2012年Boldi等[16]提出給原始圖中的邊加入不確定性的方法，所提出的(k,ε)-混淆算法在抗頂點(diǎn)身份攻擊的同時也保證了圖結(jié)構(gòu)數(shù)據(jù)的最小化失真；2013年Mittal等[17]提出了基于隨機(jī)游走的不確定圖數(shù)據(jù)發(fā)布方法，防止了鏈接攻擊；Nguyen等[18]在2014年提出基于方差最大化的方法來衡量隱私與效用之間的關(guān)系；2015年Nguyen等[19]在前期工作的基礎(chǔ)上又提出了基于不確定鄰接矩陣的通用匿名模型UAM，并將UAM引入到方差最大化算法中。綜上，文中主要研究已有的不確定圖隱私保護(hù)算法，通過對每種算法分析和對比，總結(jié)了每種算法的優(yōu)缺點(diǎn)及各自的適用范圍，為隱私保護(hù)方法工程化實(shí)現(xiàn)提供技術(shù)參考[20]。

2 基礎(chǔ)知識

本節(jié)主要介紹不確定圖，(k,ε)-混淆，頂點(diǎn)唯一性和共性，隨機(jī)游走的轉(zhuǎn)移矩陣，不確定鄰接矩陣等概念。

定義1[16]：給定一個圖G(V,E)，如果映射p:V2→[0,1]是邊集中每條邊存在的概率函數(shù)，那么圖G'=(V,p)是關(guān)于圖G的不確定圖，其中V2表示集合V中所有可能的頂點(diǎn)對，即V2={(vi,vj)|1≤i

從定義1可知，確定圖G是不確定圖G'的一種特殊情況，確定圖G中的每條邊存在的概率均為1。

為了描述不確定圖，使用文獻(xiàn)[16]中的概率數(shù)據(jù)庫模型—可能世界模型(possible world model)，將生成的不確定圖G'的所有可能世界表示為W(G')，則對于某一不確定圖W=(V,EW)∈W(G')的概率為：

(1)

其中，E'為引入不確定性的頂點(diǎn)集合，E'?V2；p(e)為邊存在的概率，且不確定圖中不同的邊的概率分布是相互獨(dú)立的。

假定攻擊者知道某些頂點(diǎn)的屬性P，將屬性P的所有取值用ΩP表示。若屬性P是圖中所有頂點(diǎn)的度，則ΩP可以表示為：ΩP={0,1,…,n-1}。

給定一個不確定圖G'和某一個屬性P，對于每一個頂點(diǎn)v∈G'和ω∈ΩP，頂點(diǎn)v∈G且具有屬性P的概率Xv(ω)為：

(2)

對于式2，可以根據(jù)式1得到Pr(W)，而χv,ω(W)是一個[0,1]區(qū)間的變量，用來度量W中的頂點(diǎn)v是否具有屬性P。也就是說，Xv(ω)是所有可能世界模型中頂點(diǎn)v具有屬性P的概率之和。同時可以得到圖G中具有屬性值ω的頂點(diǎn)v在G'中像的概率Yω(v)為：

(3)

定義2[16]((k,ε)-混淆)：已知P是一個頂點(diǎn)屬性，k(k>1)是所需要達(dá)到的混淆級別，ε(0<ε<1)是一個容忍參數(shù)，如果G'中頂點(diǎn)的分布熵大于等于log2k，那么就說不確定圖G'是關(guān)于屬性P在頂點(diǎn)集合v屬于G上的k-混淆，即：H(YP(v))≥log2k。如果圖G'至少在混淆圖G中具有屬性P的(1-ε)n個頂點(diǎn)，那么就說不確定圖G'在屬性P中是(k,ε)-混淆的。

根據(jù)頂點(diǎn)在圖G所處位置及屬性的不同，文獻(xiàn)[17]給出了頂點(diǎn)唯一性和共性的定義，具體見定義3。

定義3[16]：已知P是定義在圖G頂點(diǎn)集合V上的一個屬性，P:V→ΩP，θ是一個大于0的參數(shù)，對于任意屬性值ω∈ΩP，則它的θ共性Cθ(ω)和θ唯一性Uθ(ω)為：

(4)

(5)

在定義3中，距離函數(shù)d為屬性P在ΩP范圍內(nèi)的值。因此，對于每一對ω,ω'∈ΩP，總有d(ω,ω')>0。對于頂點(diǎn)度的屬性P1，距離函數(shù)d的值為P1中兩頂點(diǎn)度的差的絕對值。同時，Φ是高斯分布，見式6：

(6)

在該定義中頂點(diǎn)屬性值的ω的共性是指，ω值在圖中頂點(diǎn)屬性中是否具有代表性的一種測量，唯一性是共性的逆。共性與唯一性的大小取決于θ值的大小，θ越大，不確定性越大，屬性值的取值范圍ΩP越廣，頂點(diǎn)屬性的共性越小，則唯一性越大。

定義4[17]：隨機(jī)游走的轉(zhuǎn)移概率矩陣為：

(7)

其中，deg(i)表示頂點(diǎn)i的度。

定義5[19]不確定鄰接矩陣UAM(uncertain adjacency matrix)：給定原始圖G及其對應(yīng)的不確定圖G'，如果矩陣A滿足以下三點(diǎn)，則稱A為不確定圖G'的鄰接矩陣。

(1)Ai,j=Aj,i；

(2)Ai,j∈[0,1]且Ai,i=0；

3 基于不確定圖的隱私保護(hù)算法

本節(jié)主要對(k,ε)-混淆算法、隨機(jī)游走算法、優(yōu)化的隨機(jī)游走算法和基于UAM模型的方差最大化算法進(jìn)行對比研究。首先從算法的執(zhí)行流程圖、算法功能等角度進(jìn)行分析，然后從保護(hù)程度、數(shù)據(jù)效用性和圖結(jié)構(gòu)失真程度等方面進(jìn)行了對比，最后總結(jié)了四種算法的優(yōu)缺點(diǎn)及其各自的適用場景。

3.1 算法流程分析

3.1.1 (k,ε)-混淆算法

(k,ε)-混淆算法主要包括兩個部分，主算法(見圖1)和子算法(見圖2)。

圖1 (k,ε)-混淆算法流程

主算法的目的是找到符合條件的具有最小不確定性的(k,ε)-混淆圖；子算法是在給定的標(biāo)準(zhǔn)差參數(shù)，即不確定預(yù)算σ的情況下，找到原始數(shù)據(jù)圖G的(k,ε)-混淆圖G'。為了更好地利用不確定預(yù)算σ，需要對圖中的數(shù)據(jù)進(jìn)行預(yù)處理，即選擇唯一性最大的「ε/2|V|?個頂點(diǎn)組成篩選集合H，H作為未加入不確定性頂點(diǎn)集合，因此，該算法不針對圖中所有頂點(diǎn)。

圖2中頂點(diǎn)唯一性的計算見定義3，頂點(diǎn)的唯一性值越大，該頂點(diǎn)中需要引入的不確定性越大，因此與唯一性大的頂點(diǎn)相鄰邊的采樣概率Q(v)就越大。根據(jù)采樣概率Q(v)，按比例縮小集合V中的頂點(diǎn)v的唯一性級別。對于子算法，對于E'中的每條邊e，根據(jù)邊的唯一性σ(e)重新分配不確定性級別。

圖2 子算法流程

對于E'中邊e=(u,v),它的σ-唯一性級別為：

(8)

σ-不確定性集合為：

(9)

對于大多數(shù)頂點(diǎn)對，邊隨機(jī)擾動參數(shù)re服從隨機(jī)分布Rσ(e)(見式10)；對于少數(shù)頂點(diǎn)對，邊隨機(jī)擾動參數(shù)re服從[0,1]均勻分布。

(10)

其中，Φ0,σ為高斯分布的密度函數(shù)，見式6。

3.1.2 隨機(jī)游走算法

隨機(jī)游走算法(RandWalk，RW)是通過對原始數(shù)據(jù)圖中添加噪音，將原始圖結(jié)構(gòu)轉(zhuǎn)化為不確定性的圖結(jié)構(gòu)，即通過隨機(jī)游走方法遍歷圖中的頂點(diǎn)和邊，刪除一些原始數(shù)據(jù)圖中真實(shí)存在的邊和添加某些不存在的邊。在RW算法中，為了避免頂點(diǎn)自環(huán)或者多條重復(fù)邊的出現(xiàn)，該算法設(shè)置了實(shí)驗(yàn)次數(shù)的閾值M。RW的處理流程如圖3所示。

圖3 RW算法流程

RW算法保護(hù)了原始圖中的局部圖特征，防止了惡意攻擊者對網(wǎng)絡(luò)數(shù)據(jù)圖中某個子圖的鏈接攻擊。在真實(shí)數(shù)據(jù)庫中進(jìn)行驗(yàn)證時，該算法對原始數(shù)據(jù)不進(jìn)行預(yù)處理。隨機(jī)游走次數(shù)t越小，社交網(wǎng)絡(luò)上的社團(tuán)結(jié)構(gòu)保護(hù)效果越好，并且與引入噪音的大小無關(guān)。

3.1.3 優(yōu)化的隨機(jī)游走算法

由于RW算法中存在誤差實(shí)驗(yàn)次數(shù)M值的設(shè)置，使得算法難以進(jìn)行對比分析，Nguyen等對RW算法進(jìn)行了優(yōu)化，提出了RandWalk-mod算法(RW-mod)。RW-mod算法通過增加參數(shù)α來消除RW算法中的M參數(shù)，其中α是介于0和1之間的一個值。RW-mod執(zhí)行流程如圖4所示。

3.1.4 方差最大化算法

基于定義5中的UAM矩陣，Nguyen等提出了方差最大化算法，該算法是高隱私保護(hù)算法RW和高數(shù)據(jù)可用性算法(k,ε)-混淆之間的一個均衡。方差最大化方法包括三個階段，該方法可闡述為：先將原始圖G分為s個子圖，每個子圖sG有ns=np/s條與附近頂點(diǎn)(頂點(diǎn)之間的默認(rèn)距離為2)相連的邊數(shù)；在頂點(diǎn)的度不變的條件下，每個子圖sG形成一個有最大邊方差的不確定子圖sG'的二次規(guī)劃；最后將不確定子圖sG'合并成G'，并發(fā)布一些樣本圖。算法流程如圖5所示，在該算法中，可以利用二次規(guī)劃中的目標(biāo)函數(shù)來計算原始數(shù)據(jù)圖的隱私保護(hù)程度。

3.2 算法比較

(1)(k,ε)-混淆算法利用頂點(diǎn)的唯一性和分布熵對圖中的頂點(diǎn)進(jìn)行篩選，然后對篩選后的頂點(diǎn)進(jìn)行邊混淆；RW算法和RW-mod算法利用馬爾可夫過程和轉(zhuǎn)移矩陣對原始圖進(jìn)行邊的不確定化；方差最大化算法先利用圖分割技術(shù)將原始圖劃分為多個子圖，每個子圖對應(yīng)一個二次規(guī)劃。

圖4 RW-mod算法流程

圖5 方差最大化算法流程

(2)(k,ε)-混淆算法的隱私保護(hù)程度最??；RW算法的隱私保護(hù)程度最大；RW-mod算法的隱私保護(hù)程度同RW算法；方差最大化算法的隱私保護(hù)程度介于(k,ε)-混淆算法和RW算法之間。

(3)通過(k,ε)-混淆算法，數(shù)據(jù)的可用性較高；通過RW算法，數(shù)據(jù)的可用性較差；RW-mod算法的數(shù)據(jù)可用性同RW算法；方差最大化算法數(shù)據(jù)可用性介于(k,ε)-混淆算法和RW算法之間。

(4)通過(k,ε)-混淆算法，圖結(jié)構(gòu)失真較??；通過RW算法，保護(hù)了圖中的局部特征；RW-mod算法同RW算法；通過方差最大化算法，圖結(jié)構(gòu)失真較大。

(5)(k,ε)-混淆算法中頂點(diǎn)的度保持不變；RW算法忽視了變換前后頂點(diǎn)度的關(guān)系；RW-mod算法中頂點(diǎn)的度保持不變；方差最大化算法中頂點(diǎn)的度保持不變。

(6)(k,ε)-混淆算法不允許自環(huán)；RW算法不允許自環(huán)，在構(gòu)造不確定圖時造成了邊的丟失；RW-mod算法和方差最大化算法允許自環(huán)。

(7)(k,ε)-混淆算法和RW算法不允許兩頂點(diǎn)之間存在多條邊；RW-mod算法和方差最大化算法允許兩頂點(diǎn)之間存在多條邊。

(8)(k,ε)-混淆算法和RW算法符合定義5中的條件1和條件2；RW-mod算法在條件(1)中α=0.5時，符合定義5中的條件1和條件3；方差最大化算法符合定義5中的條件1～3。

(9)(k,ε)-混淆算法適合低隱私保護(hù)程度，高數(shù)據(jù)可用性的場景；RW算法和RW-mod算法適合高隱私保護(hù)程度，低數(shù)據(jù)可用性的場景；方差最大化算法適合高隱私保護(hù)程度，高數(shù)據(jù)可用性的場景。

在(k,ε)-混淆算法中，存在兩點(diǎn)不足之處：(1)σ最小化帶來的問題。σ越小，邊隨機(jī)擾動參數(shù)re大部分值集中在0附近，原始數(shù)據(jù)圖中真實(shí)存在的邊的概率1-re接近于1，不存在的邊的概率re接近于0，攻擊者可以根據(jù)舍入方法，將發(fā)布的不確定圖還原為原始數(shù)據(jù)圖；(2)該方法選擇頂點(diǎn)對，構(gòu)造原始數(shù)據(jù)圖中不存在的邊時，沒有考慮到頂點(diǎn)的局部性，即頂點(diǎn)在子圖中所處的位置，好的子圖擾動可以減少圖結(jié)構(gòu)的失真。RW算法是為了防止鏈接攻擊而提出的，是一種高隱私保護(hù)模型。但是RW算法中的試驗(yàn)次數(shù)M及M值如何確定，使得算法難以進(jìn)行比較分析。RW-mod算法不適合度為1的頂點(diǎn)，若頂點(diǎn)的度為1，則與該頂點(diǎn)相連的邊在原始數(shù)據(jù)圖上是真實(shí)存在的，在構(gòu)造不確定圖時添加該條真實(shí)存在的邊的概率為1，而在RW-mod算法中，添加該邊的概率為0.5。方差最大化算法在子圖分割時造成了原始圖中邊的丟失，使得圖結(jié)構(gòu)失真較大。

四種算法的比較見表1。

4 結(jié)束語

綜上所述，基于不確定圖的隱私保護(hù)方法在隱私保護(hù)中具有重要的使用價值。通過對(k,ε)-混淆算法、RW算法、RW-mod算法及方差最大化算法進(jìn)行分析和比較，為基于不確定圖的隱私保護(hù)方法的改進(jìn)和應(yīng)用提供了技術(shù)支持。下一步重點(diǎn)研究將以上算法應(yīng)用到有向圖或加權(quán)圖隱私保護(hù)中，同時引入新機(jī)制，如差分隱私，設(shè)計新的基于不確定圖的隱私保護(hù)方法。

表1 四種不確定圖實(shí)現(xiàn)算法的比較