溫 閣 顏 軍 胡 靜 吳振強(qiáng)
(陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 西安 710119)
(wenge32@snnu.edu.cn)
社交網(wǎng)絡(luò)是現(xiàn)實(shí)生活中人與人關(guān)系的一種體現(xiàn).在社交網(wǎng)絡(luò)中,用戶可以隨時(shí)隨地分享自己的心情狀態(tài)、生活照片以及日?;顒?dòng)等信息來增強(qiáng)朋友之間的友誼.但當(dāng)其發(fā)布數(shù)據(jù)時(shí),用戶的個(gè)人身份、朋友關(guān)系、習(xí)慣、愛好等會(huì)被泄露.而現(xiàn)在出現(xiàn)的一系列網(wǎng)絡(luò)攻擊事件主要利用的是用戶發(fā)布的某些社交網(wǎng)絡(luò)數(shù)據(jù)來挖掘用戶的隱私信息.比如,2017年10月,南非發(fā)生史上規(guī)模最大的數(shù)據(jù)泄露事件,共有3160萬份用戶的個(gè)人資料被公之于眾,連總統(tǒng)祖馬和多位部長都未能幸免.此次被黑客公布的數(shù)據(jù)來源于Dracore Data Sciences企業(yè)的GoVault平臺,其公司客戶包括南非最大的金融信貸機(jī)構(gòu)——TransUnion.2017年11月22日,美國國防部100 GB的頂級機(jī)密在AWS上曝光,據(jù)外媒報(bào)道稱,美國五角大樓意外暴露了美國國防部的分類數(shù)據(jù)庫,其中包含美國當(dāng)局在全球社交媒體平臺中收集到的18億用戶的個(gè)人信息[1].因此,如何在大家享受社交網(wǎng)絡(luò)便利的同時(shí),保護(hù)個(gè)人的敏感信息不被泄露成了急需解決的問題.
社交網(wǎng)絡(luò)涉及多種角色,并且每個(gè)角色之間的關(guān)系也相當(dāng)復(fù)雜.為了能夠更加詳細(xì)地描述社交網(wǎng)絡(luò)中個(gè)體之間的關(guān)系,可以將社交網(wǎng)絡(luò)抽象成圖結(jié)構(gòu),用節(jié)點(diǎn)表示個(gè)體,用邊來表示節(jié)點(diǎn)之間的關(guān)系.因此,通過對圖結(jié)構(gòu)進(jìn)行研究使我們對社交網(wǎng)絡(luò)的了解能夠更加深入.
由于社交網(wǎng)絡(luò)中包括許多個(gè)人隱私,將其抽象為圖結(jié)構(gòu)后,圖中相應(yīng)的節(jié)點(diǎn)和邊也會(huì)涉及到個(gè)人敏感信息,因此針對社交圖隱私保護(hù),目前研究者提出了很多種隱私保護(hù)的方式,主要分為3類:標(biāo)識符替換法、差分隱私法、圖結(jié)構(gòu)隱私法.1)標(biāo)識符替換法.2007年,BackStrom等人[2]提出可以將真實(shí)圖數(shù)據(jù)匿名化,使用一些無意義的標(biāo)識符來代替保護(hù)用戶的身份信息.2)差分隱私法.2009年,Hay等人[3]提出可以利用差分隱私來實(shí)現(xiàn)對社交圖中的節(jié)點(diǎn)和邊進(jìn)行保護(hù).3)圖結(jié)構(gòu)隱私法.針對圖結(jié)構(gòu)隱私保護(hù),又分為以下3種.①圖聚類方法.2007年,Zheleva和Getoor[4]針對在圖數(shù)據(jù)中出現(xiàn)的鏈接關(guān)系重識別現(xiàn)象,提出了一種基于邊的圖聚類隱私保護(hù)方法.②圖修改技術(shù).Hay等人[5]研究了一個(gè)評估共享數(shù)據(jù)隱私風(fēng)險(xiǎn)的框架并與圖論聯(lián)系起來,提出了一種基于擾動(dòng)的社交圖匿名技術(shù),從而減少了隱私風(fēng)險(xiǎn).③不確定圖.2012年Boldi等人[6]首次提出一種不確定圖的隱私保護(hù)算法,該方法在抗頂點(diǎn)身份攻擊的同時(shí)保證了圖結(jié)構(gòu)數(shù)據(jù)的最小化失真.
目前對隱私保護(hù)方法的評價(jià)都是從隱私的位置、關(guān)系等方面進(jìn)行評價(jià)的.本文中我們借鑒隱私攻擊的方法,從隱私挖掘的角度對隱私保護(hù)的強(qiáng)度進(jìn)行評估.2017年,武漢大學(xué)徐正全等人[7]提出了基于濾波原理的時(shí)間序列差分隱私保護(hù)強(qiáng)度評估,根據(jù)信號處理中濾波的原理,設(shè)計(jì)一個(gè)攻擊模型來濾除部分噪聲,并取得了很好的攻擊效果.
現(xiàn)有的社交網(wǎng)絡(luò)隱私保護(hù)方法大都是使用加噪的方式,借鑒信號處理中濾波的原理,我們在不考慮背景知識的前提下,選擇能夠自動(dòng)抑制噪聲的維納濾波對鄰近圖進(jìn)行去噪來提取有用的信息.另外,我們還提出了一種基于濾波的社交圖隱私保護(hù)強(qiáng)度評估模型,并在該模型下設(shè)計(jì)了隱私保護(hù)強(qiáng)度評估算法PPIE(privacy preserving intensity evaluation).實(shí)驗(yàn)表明,我們的方法能夠?yàn)V除鄰近圖中的部分噪聲,達(dá)到了隱私保護(hù)強(qiáng)度評價(jià)的目的,也為社交網(wǎng)絡(luò)隱私保護(hù)的理論研究提供了指導(dǎo).
在針對社交圖隱私攻擊的研究中,現(xiàn)有的攻擊方式大概有以下幾類:1)節(jié)點(diǎn)重識別攻擊.Narayanan等人[8-9]提出利用種子節(jié)點(diǎn)來實(shí)現(xiàn)對鄰居節(jié)點(diǎn)的識別.Abawajy等人[10]提出使用節(jié)點(diǎn)對屬性進(jìn)行節(jié)點(diǎn)重識別攻擊,此攻擊利用2個(gè)相連頂點(diǎn)的局部區(qū)域的信息來識別目標(biāo)個(gè)體.2)屬性重識別攻擊.Zheleva等人[11]研究發(fā)現(xiàn),參與同一小組的用戶傾向于具有相似的屬性,并可利用用戶的群組標(biāo)簽對用戶可能具有的屬性進(jìn)行預(yù)測.Mislove等人[12]研究發(fā)現(xiàn),用戶可能與其好友具有類似的屬性.可以通過好友公開的信息對用戶未公開的信息進(jìn)行推測.3)連接關(guān)系重識別攻擊.Zhou等人[13]利用朋友間的關(guān)系作為弱連接,而將親戚之間的關(guān)系作為強(qiáng)鏈接,最后發(fā)現(xiàn)兩者有弱連接關(guān)系的人更容易形成朋友關(guān)系.4)位置社交關(guān)系攻擊.Huo等人[14]提出一種以用戶的簽到歷史軌跡、地理位置及各用戶間的關(guān)系作為背景的簽到框架,該系統(tǒng)為了檢驗(yàn)用戶是否真實(shí)簽到,將用戶可能去過的所有位置進(jìn)行預(yù)測,并將預(yù)測到的位置反饋給用戶.孟小峰等人[15]介紹了位置大數(shù)據(jù)的概念以及位置大數(shù)據(jù)的隱私威脅,總結(jié)了針對位置大數(shù)據(jù)隱私統(tǒng)一的基于度量的攻擊模型,對目前位置大數(shù)據(jù)隱私保護(hù)領(lǐng)域已有的研究成果進(jìn)行了歸納.
為了評價(jià)隱私保護(hù)的強(qiáng)度,現(xiàn)有的方法是從隱私的位置、關(guān)系等方面進(jìn)行評價(jià).然而,這些方法缺乏具體的評價(jià)模型和算法來驗(yàn)證其有效性,隱私保護(hù)強(qiáng)度也無法進(jìn)行統(tǒng)一性的評價(jià).因此,本文給出一種針對加噪型的社交網(wǎng)絡(luò)隱私保護(hù)強(qiáng)度評估模型和算法以解決上述問題.
本文我們將社交網(wǎng)絡(luò)抽象成一個(gè)無向無權(quán)圖G(V,E),其中V表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合,E表示網(wǎng)絡(luò)中所有邊的集合.
高斯噪聲是指它的概率密度函數(shù)服從高斯分布的一類噪聲.
高斯分布即正態(tài)分布,若隨機(jī)變量X服從一個(gè)數(shù)學(xué)期望為μ、方差為σ2的正態(tài)分布,記為N(μ,σ2).其概率密度函數(shù)為正態(tài)分布的期望值μ決定了其位置,其標(biāo)準(zhǔn)差σ決定了分布的幅度.當(dāng)μ=0,σ=1時(shí)的正態(tài)分布是標(biāo)準(zhǔn)正態(tài)分布.
1)濾波
從連續(xù)的(或離散的)輸入數(shù)據(jù)中濾除噪聲和干擾,以提取有用信息的過程稱為濾波,這是信號處理中經(jīng)常采用的主要方法之一,具有十分重要的應(yīng)用價(jià)值.
2)維納濾波
維納濾波是一種基于最小均方誤差準(zhǔn)則、對平穩(wěn)過程的最優(yōu)估計(jì)器.這種濾波器的輸出與期望輸出之間的均方誤差為最小,因此,它是一個(gè)最佳濾波系統(tǒng),它可用于提取被平穩(wěn)噪聲所污染的信號.
一個(gè)圖(或網(wǎng)絡(luò))由一些頂點(diǎn)和連接它們的邊構(gòu)成.每個(gè)頂點(diǎn)連出的所有邊的數(shù)量就是這個(gè)頂點(diǎn)的度,即指此節(jié)點(diǎn)的鄰邊數(shù)量.對網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度求平均可得到網(wǎng)絡(luò)的平均度[16].
復(fù)雜網(wǎng)絡(luò)中的聚集系數(shù)是用來衡量網(wǎng)絡(luò)集團(tuán)化程度的重要參數(shù),例如在人際關(guān)系網(wǎng)絡(luò)中你朋友的朋友很可能也是你的朋友,你的2個(gè)朋友彼此也可能是朋友,聚集系數(shù)就是用來度量網(wǎng)絡(luò)的這種性質(zhì)的參數(shù)[16].
1)聚集系數(shù)
聚集系數(shù)是表示一個(gè)圖形中節(jié)點(diǎn)聚集程度的系數(shù).在現(xiàn)實(shí)世界的網(wǎng)絡(luò),這種可能性往往比2個(gè)節(jié)點(diǎn)之間隨機(jī)設(shè)立一個(gè)連接的平均概率更大.
在無向網(wǎng)絡(luò)中,可以用聚集系數(shù)Ci來表示節(jié)點(diǎn)v i的聚集系數(shù),如式(1)[16]:
其中,N表示節(jié)點(diǎn)個(gè)數(shù);Mi表示實(shí)際存在的邊數(shù).
2)平均聚集系數(shù)
將聚集系數(shù)對整個(gè)網(wǎng)絡(luò)作平均,可得到網(wǎng)絡(luò)的平均聚集系數(shù)C,如式(2)[16]:
在一些大型的實(shí)際網(wǎng)絡(luò)中,每個(gè)節(jié)點(diǎn)的地位是不同的.要衡量一個(gè)節(jié)點(diǎn)的重要性其度值可以作為一個(gè)衡量指標(biāo),但有的節(jié)點(diǎn)度雖然小,但它可能是2個(gè)集團(tuán)的中間聯(lián)絡(luò)人,如果去掉該節(jié)點(diǎn),會(huì)導(dǎo)致2個(gè)社團(tuán)的聯(lián)系中斷,因此該節(jié)點(diǎn)在網(wǎng)絡(luò)中起到極其重要的作用.因此引入介數(shù),反映節(jié)點(diǎn)或邊在整個(gè)網(wǎng)絡(luò)中的作用和影響力.
節(jié)點(diǎn)vi的介數(shù)中心性就是節(jié)點(diǎn)v i的歸一化介數(shù),設(shè)節(jié)點(diǎn)vi的介數(shù)為Bi,則其介數(shù)中心性CB(vi)可以定義為式(3)[16]:
度分布是圖論和網(wǎng)絡(luò)理論中的概念,度為k的節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中所占的比例就是度分布P(k).度分布滿足式(4)[16]:
由于現(xiàn)有的社交網(wǎng)絡(luò)隱私保護(hù)方法大都是基于加噪的方式提出的,而在信號處理中可以利用濾波對圖像去噪.而常用的圖像去噪方法有:平滑濾波法、中值濾波法、均值濾波法、維納濾波等.由于維納濾波器能夠自動(dòng)抑制噪聲的放大,對含噪圖像的復(fù)原效果較好,可使具有噪聲干擾圖像的客觀復(fù)原性能達(dá)到全局意義上的最佳[17].因此,本文在不考慮一定的背景知識情況下,采用維納濾波方法從隱私挖掘的角度評價(jià)隱私保護(hù)的強(qiáng)度.
本文首先將社交網(wǎng)絡(luò)隱私保護(hù)強(qiáng)度評估抽象成一個(gè)模型,然后在該模型下提出一種基于社交網(wǎng)絡(luò)隱私保護(hù)強(qiáng)度評估算法PPIE,并對該模型進(jìn)行說明;然后給出PPIE算法的偽代碼并進(jìn)行分析;最后,實(shí)驗(yàn)結(jié)果表明我們的方法能夠?yàn)V除鄰近圖中的部分噪聲,可以達(dá)到對隱私保護(hù)強(qiáng)度評價(jià)的目的.
整體模型(如圖1所示)包括3個(gè)部分:第1部分是原圖;中間部分是鄰近圖,即隱私保護(hù)后的圖,這里加入的是高斯噪聲,研究者可以根據(jù)不同的需求加入不同的噪聲來進(jìn)行隱私保護(hù);第3部分是去噪圖,在得到鄰近圖后,對鄰近圖進(jìn)行濾波得到去噪圖,研究者可以根據(jù)不同的需求提出不同的隱私保護(hù)強(qiáng)度評估算法,具體的隱私保護(hù)強(qiáng)度評估模型如圖2所示.在該模型下,我們提出了一種基于社交網(wǎng)絡(luò)隱私保護(hù)強(qiáng)度評估算法PPIE.
圖1 整體模型
圖2 隱私保護(hù)強(qiáng)度評估模型
PPIE算法是利用維納濾波來實(shí)現(xiàn)社交網(wǎng)絡(luò)隱私保護(hù)強(qiáng)度的評價(jià),實(shí)驗(yàn)步驟主要由以下5步組成:
1)將圖G(V,E)轉(zhuǎn)換成鄰接矩陣Matrix;
2)改變高斯噪聲中的σ值,得到帶高斯噪聲的矩陣NoiseMatrix;
3)采用維納濾波對帶噪矩陣NoiseMatrix中的噪音進(jìn)行濾除,得到矩陣Matrix′;
4)將濾除后的矩陣Matrix′轉(zhuǎn)換成稀疏矩陣S;
5)將稀疏矩陣S轉(zhuǎn)換成圖G′.
詳細(xì)算法如算法1.
算法1.PPIE算法.
輸入:G=(V,E);
輸出:G′=(V′,E′).
為了對隱私保護(hù)的強(qiáng)度進(jìn)行評價(jià),利用維納濾波的方法濾除鄰近圖中的噪聲,并且利用無向圖中的平均度、平均聚集系數(shù)、介數(shù)中心性和度分布等度量指標(biāo)來評價(jià)隱私保護(hù)的強(qiáng)度.若度量指標(biāo)相等或接近,則說明達(dá)到了隱私保護(hù)強(qiáng)度評估的目的.同時(shí)利用Matlab、Python語言及第三方功能包Network X對本文算法進(jìn)行程序編程和仿真實(shí)驗(yàn).實(shí)驗(yàn)數(shù)據(jù)分為2部分:真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集.真實(shí)數(shù)據(jù)集來自于karate和dolphin俱樂部,合成數(shù)據(jù)集分別為300和500個(gè)節(jié)點(diǎn),連接概率是0.3的隨機(jī)網(wǎng)絡(luò)圖.為了減少實(shí)驗(yàn)數(shù)據(jù)的隨機(jī)性,實(shí)驗(yàn)分別進(jìn)行了10次模擬取平均值.其中表1為節(jié)點(diǎn)個(gè)數(shù)N分別為34,61,300,500時(shí),原圖與去噪圖的度量指標(biāo).AD(average degree)表示圖中節(jié)點(diǎn)的平均度,ACC(average clustering cofficient)表示圖中節(jié)點(diǎn)的平均聚集系數(shù),BC(betweenness centrality)表示圖中節(jié)點(diǎn)的介數(shù)中心性.
表1 原圖與去噪圖度量指標(biāo)比較
圖3 N=34,σ=0.1和0.9時(shí)度分布圖
不同的σ值下,節(jié)點(diǎn)個(gè)數(shù)N為34,61,300,500時(shí)對應(yīng)的度分布圖如圖3~6所示;其中t代表原圖,w代表去噪圖.由于度分布圖的大體趨勢一樣,這里只列出了當(dāng)σ=0.1和0.9時(shí)各節(jié)點(diǎn)對應(yīng)的度分布圖.
通過觀察表1中的度量指標(biāo)發(fā)現(xiàn),當(dāng)節(jié)點(diǎn)個(gè)數(shù)較少時(shí),原圖與去噪圖AD的絕對誤差值較小;而無論節(jié)點(diǎn)多少,原圖與去噪圖的ACC,BC的絕對誤差值都較小.由此可以看出,經(jīng)過維納濾波之后得到的去噪圖與原圖的AD,ACC,BC的值與原始圖比較接近;另外,由分布圖可以看出,當(dāng)σ在(0,1)的范圍內(nèi),比較原圖t和去噪圖w,發(fā)現(xiàn)兩者
圖4 N=61,σ=0.1和0.9時(shí)度分布圖
在變化趨勢上非常接近.當(dāng)N=34時(shí),隨著節(jié)點(diǎn)度數(shù)的變化,節(jié)點(diǎn)度分布趨勢都是先升后降;當(dāng)N=61時(shí),隨著節(jié)點(diǎn)度數(shù)的變化,節(jié)點(diǎn)度分布總體趨勢在降;當(dāng)N=300時(shí),隨著節(jié)點(diǎn)度數(shù)的變化,節(jié)點(diǎn)度分布趨勢都是先升后降,但升到最高點(diǎn)后開始下降,不再上升;當(dāng)N=500時(shí),隨著節(jié)點(diǎn)度數(shù)的變化,節(jié)點(diǎn)度分布趨勢都是先升后降,與N=300的變化趨勢很接近;通過比較4個(gè)數(shù)據(jù)集的原圖與去噪圖的度量指標(biāo)發(fā)現(xiàn),經(jīng)過維納濾波時(shí)之后得到的去噪圖與原圖的平均度、平均聚集系數(shù)、介數(shù)中心性和度分布與原始圖比較接近,達(dá)到了隱私保護(hù)強(qiáng)度評估的目的.
圖5 N=300,σ=0.1和0.9時(shí)度分布圖
圖6 N=500,σ=0.1和0.9時(shí)度分布圖
本文針對加噪型的社交網(wǎng)絡(luò)隱私保護(hù)方法缺乏統(tǒng)一性評價(jià)的問題,在不考慮一定背景知識的前提下,從隱私挖掘的角度,借鑒信號處理中能夠自動(dòng)抑制噪聲的維納濾波,提出了一種基于濾波的社交網(wǎng)絡(luò)隱私保護(hù)強(qiáng)度評估模型,并且在該模型下設(shè)計(jì)了隱私保護(hù)強(qiáng)度評估(PPIE)算法.為了驗(yàn)證該算法的可行性,將算法應(yīng)用到2個(gè)合成數(shù)據(jù)集和2個(gè)真實(shí)的數(shù)據(jù)集中,并比較原圖和經(jīng)過維納濾波后的去噪圖的度量指標(biāo).Matlab和Python仿真實(shí)驗(yàn)結(jié)果表明,濾波后的去噪圖和原圖的度量指標(biāo)基本相似,說明我們的方法達(dá)到了評價(jià)隱私保護(hù)強(qiáng)度的目的,為社交網(wǎng)絡(luò)隱私保護(hù)的理論研究提供了指導(dǎo).在接下來的工作中,我們將對濾波的方法再進(jìn)一步地改進(jìn),必要時(shí)可以加入相應(yīng)的背景知識來提高隱私挖掘的效果,從而更好地評價(jià)隱私保護(hù)的強(qiáng)度.
[1]天下數(shù)據(jù)IDC.盤點(diǎn)2017全球十大數(shù)據(jù)泄露事件:一件比一件重量級[EB/OL].[2018-03-20].http://www.sohu.com/a/207652321-99931348
[2]Backstrom L,Dwork C,Kleinberg J.Wherefore art thou r3579x?:Anonymized social networks,hidden patterns,and structural steganography[C]//Proc of the 16th Int Conf on World Wide Web.New York:ACM,2007:181-190
[3]Hay M,Li C,Miklau G,et al.Accurate estimation of the degree distribution of private networks[C]//Proc of IEEE Int Conf on Data Mining.Piscataway,NJ:IEEE,2009:169-178
[4]Zheleva E,Getoor L.Preserving the privacy of sensitive relationships in graph data[C]//Proc of ACM SIGKDD Int Conf on Privacy,Security,and Trust in KDD.Berlin:Springer,2007:153-171
[5]Hay M,Miklau G,Jensen D,et al.Anonymizing social networks[OL].[2018-03-15].https://www.research.gate.net/publication/49250847-Anonymizing-Social-Networks
[6]Boldi P,Bonchi F,Gionis A,et al.Injecting uncertainty in graphs for identity obfuscation[J].Proceeding of the VLDB Endowment,2012,5(11):1376-1387
[7]熊文君,徐正全,王豪.基于濾波原理的時(shí)間序列差分隱私保護(hù)強(qiáng)度評估[J].通信學(xué)報(bào),2017,38(5):172-181
[8]Narayanan A,Shmatikov V.Robust de-anonymization of large sparse datasets[C]//Proc of IEEE Symp on Security and Privacy.Piscataway,NJ:IEEE,2008:111-125
[9]Narayanan A,Shmatikov V.De-anonymizing social networks[C]//Proc of IEEE Symp on Security and Privacy.Piscataway,NJ:IEEE,2009:173-187
[10]Abawajy J,Ninggal M I H,Herawan T.Vertex reidentification attack using neighbourhood-pair properties[J].Concurrency and Computation:Practice and Experience,2016,28(10):2906-2919
[11]Zheleva E,Getoor L.To join or not to join:Theillusion of privacy in social networks with mixed public and private user profiles[C]//Proc of Int Conf on World Wide Web.New York:ACM,2008
[12]Mislove A,Viswanath B,Gummadi K P,et al.You are who you know:Inferring user profiles in online social networks[C]//Proc of the 3rd Int Conf on Web Search and Web Data Mining.New York:DBLP,2010:251-260
[13]Zhou Tao,LüLinyuan,Zhang Yicheng.Predicting missing links via local information[J].European Physical Journal B,2009,71(4):623-630
[14]Huo Zheng,Meng Xiaofeng,Zhang Rui.Feel free to check-in:Privacy alert against hidden location inference attacks in GeoSNs[C]//Proc of Int Conf on Database Systems for Advanced Applications.Berlin:Springer,2013:377-391
[15]王璐,孟小峰.位置大數(shù)據(jù)隱私保護(hù)研究綜述[J].軟件學(xué)報(bào),2014,25(4):693-712
[16]郭世澤,陸哲明.復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論[M].北京:科學(xué)出版社,2012
[17]盧虹冰.醫(yī)學(xué)成像及處理技術(shù)[M].北京:高等教育出版社,2013