張小云

(武警甘肅總隊(duì)，甘肅, 蘭州 730046)

0 引言

社交網(wǎng)絡(luò)[1-2]已成為人們生活不可或缺的一部分。隨著社交網(wǎng)絡(luò)的普及，人們享受著各種社交網(wǎng)絡(luò)的豐富功能和服務(wù)，包括分享狀態(tài)更新、發(fā)布照片、與他人交流和交友。由于不同社交網(wǎng)絡(luò)的功能不同，用戶往往會(huì)出于不同的目的登錄多個(gè)社交網(wǎng)絡(luò)，如微信、微博、QQ等。聚合不同社交網(wǎng)絡(luò)的用戶檔案可以揭示用戶的相關(guān)信息。然而跨網(wǎng)絡(luò)信息是一把雙刃劍：一方面，一旦識(shí)別或映射了用戶在不同社交網(wǎng)絡(luò)中的多個(gè)賬戶，就可以收集這些賬戶的配置文件、偏好和活動(dòng)，從而有利于個(gè)性化、目標(biāo)定位和推薦[3]；另一方面，可利用跨網(wǎng)絡(luò)聚合收集目標(biāo)用戶的各個(gè)方面的信息，這將導(dǎo)致嚴(yán)重的隱私泄露問題[4]。因此，社交網(wǎng)絡(luò)正面臨著去匿名化攻擊的威脅。

社交網(wǎng)絡(luò)去匿名化是近年來的一個(gè)研究熱點(diǎn)。劉家霖等[5]基于社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，提出了一種高效高精度的無種子去匿名化算法RoleMatch識(shí)別個(gè)體身份。胡開先等[6]提出了一種基于社交關(guān)系的多數(shù)投票的身份識(shí)別方法，對(duì)社交關(guān)系中的用戶身份特征進(jìn)行統(tǒng)計(jì)，推測(cè)當(dāng)前用戶的地址信息、實(shí)體信息和用戶興趣。胡光武等[7]將社交網(wǎng)絡(luò)的去匿名問題轉(zhuǎn)化為輔助網(wǎng)絡(luò)與匿名網(wǎng)絡(luò)之間的節(jié)點(diǎn)匹配問題，并提出了一種基于隨機(jī)森林分類器的社交網(wǎng)絡(luò)去匿名方案。王照永等[8]利用社交網(wǎng)絡(luò)圖的結(jié)構(gòu)特征與節(jié)點(diǎn)屬性的特征之間的相似性差異實(shí)現(xiàn)節(jié)點(diǎn)間的映射，并提出一種基于用戶社交網(wǎng)絡(luò)圖的結(jié)構(gòu)和用戶節(jié)點(diǎn)的特征來披露用戶敏感信息的去匿名方法。上述方法大多數(shù)基于同一組用戶的不同社交網(wǎng)絡(luò)應(yīng)該顯示相似的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的假設(shè)。這種方法的觀察結(jié)果導(dǎo)致用戶傾向于在不同的社交網(wǎng)絡(luò)中與他們感興趣或熟悉的相似用戶建立聯(lián)系。然而，在異構(gòu)的社交網(wǎng)絡(luò)中，由于不同社交網(wǎng)絡(luò)的用戶并不總是重疊的，不同社交網(wǎng)絡(luò)使用模式的多樣性將進(jìn)一步導(dǎo)致不同社交網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)不一致。

為了進(jìn)一步研究異構(gòu)的社交網(wǎng)絡(luò)聚合導(dǎo)致的隱私泄露，本文設(shè)計(jì)一種異構(gòu)去匿名化算法。該方法聯(lián)合利用公開的網(wǎng)絡(luò)結(jié)構(gòu)信息和用戶信息，可以顯著提高檢測(cè)精度。

1 相關(guān)概念

1.1 圖論

社交網(wǎng)絡(luò)結(jié)構(gòu)通常表示為一個(gè)圖[9]，其中，每個(gè)用戶是圖中的一個(gè)節(jié)點(diǎn)，一對(duì)用戶之間的連接表示為邊。設(shè)G=(V,E)表示一個(gè)社交網(wǎng)絡(luò)圖，其中，V是一組用戶，E?V×V是用戶之間的一組有向/無向鏈接。e(v1,v2)表示v1和v2是朋友關(guān)系或跟隨關(guān)系，其中：e∈E；v1,v2∈V。鄰域和社區(qū)作為社交網(wǎng)絡(luò)圖中的重要結(jié)構(gòu)，形式化定義如下。

定義1 用戶vi的鄰域集R是一組用戶Ri=[vj]j=1,…,?vj:?e(vj,vi)，他們與vi有直接的朋友關(guān)系或跟隨關(guān)系。進(jìn)一步定義了函數(shù)α表示vi的鄰域集Ri，即α(vi)=Ri。

定義2 社交網(wǎng)絡(luò)圖中的社區(qū)C是G=(V,E)中頂點(diǎn)的不相交劃分。

形式上，本文將圖中的社區(qū)表示為C={C1,C2,…,Ck}，其中Ci≠Φ且Ci∩Ci=Φ(i≠j，i≥1和j≤k)。?Ci∈C，有VCi?V和ECi?VCi×VCi。本文假定社區(qū)由Infomap算法定義，該算法使用網(wǎng)絡(luò)上隨機(jī)游動(dòng)的概率流，并通過壓縮概率流的描述將網(wǎng)絡(luò)分解為模塊。

1.2 輪廓信息模型

作為旨在吸引眼球、提升自我展示、促進(jìn)和維持社會(huì)資本的平臺(tái)，社交網(wǎng)絡(luò)必須允許公眾獲得部分用戶資料信息。根據(jù)平臺(tái)定義和/或用戶定義的隱私設(shè)置，社交網(wǎng)絡(luò)上公開的個(gè)人資料信息量各不相同。為了利用異構(gòu)社交網(wǎng)絡(luò)中的個(gè)人資料信息，本文首先給出一個(gè)統(tǒng)一的定義。

定義3 設(shè)Xi=[xik]k=1,…,d表示與用戶vi∈V相關(guān)聯(lián)的一組屬性(例如用戶名(昵稱)、位置、自我描述等)，其中，d是屬性類型的數(shù)目，xik記錄用戶vi的第k個(gè)屬性的內(nèi)容。如果用戶vi的第j屬性在社交網(wǎng)絡(luò)上不可用(例如，用戶選擇不在微信上顯示其位置信息)，則xij=null。

需注意，一個(gè)用戶可能有幾個(gè)向量來模擬他/她擁有賬戶的社交網(wǎng)絡(luò)中的不同配置文件。兩個(gè)向量之間的公共屬性將用于計(jì)算輪廓相似度。

由于異構(gòu)社交網(wǎng)絡(luò)平臺(tái)包含不同類型的概要信息，并且其中一些包含語義或句法意義，因此從2個(gè)異構(gòu)社交網(wǎng)絡(luò)映射2個(gè)用戶賬戶類似于一個(gè)本體匹配問題。通常，本體匹配確定一對(duì)本體O1和O2的相似度。每個(gè)本體由一組離散的屬性組成，這些屬性通常以表、類、屬性的形式表示，并確定輸出關(guān)系。本文假定輪廓匹配定義如下。

定義4pA={x1,x2,…,xA}和pU={x1,x2,…,xU}為2個(gè)輪廓。如果2個(gè)屬性xi∈pA和xj∈pU，有type(xi)=type(xj)，則2個(gè)屬性之間的相似度定義為

sima=matchScore(xi,xj)

(1)

這里的相似度取決于所考慮的屬性，可以是年齡或性別值的相似度、昵稱名稱的字符串相似度、描述或文本相似度、位置或家鄉(xiāng)的語義相似度等。然后通過式(2)計(jì)算輪廓的相似度，

(2)

其中，wr為賦予屬性的權(quán)重，t為2個(gè)輪廓之間相同類型的屬性對(duì)的數(shù)目。

1.3 攻擊模型

假設(shè)2個(gè)異構(gòu)的社會(huì)網(wǎng)絡(luò)圖為GA和GU，GA表示匿名網(wǎng)絡(luò)圖，GU表示為輔助網(wǎng)絡(luò)圖。注意，這里的圖不一定是社交網(wǎng)絡(luò)的整個(gè)圖，反匿名攻擊可以對(duì)攻擊者收集的部分圖(即子圖)進(jìn)行。也就是說，攻擊者能夠通過發(fā)布的數(shù)據(jù)集或爬網(wǎng)站點(diǎn)獲得子圖G=(V,E)和對(duì)應(yīng)于vi∈V的輪廓屬性Xi。攻擊者的目標(biāo)是通過將GA中的用戶映射到GU中的用戶來了解不同網(wǎng)絡(luò)中用戶的更多信息。為了實(shí)現(xiàn)這一目標(biāo)，攻擊者需要從2個(gè)不同的社交網(wǎng)絡(luò)中大規(guī)模、高置信度地識(shí)別屬于同一個(gè)人的賬戶。因此，攻擊模型可形式化定義為如下問題。

考慮2個(gè)不同的社交網(wǎng)絡(luò)圖GA=(VA,EA)和GU=(VU,EU)，Vi∈VA和Vj∈VU的屬性集合定義為Xi和Xj。通過迭代計(jì)算，用戶映射vi?vj(vi∈VA，vj∈VU)表示屬于同一個(gè)人，則有

(3)

其中，S是計(jì)算Xi和Xj之間相似度的函數(shù)(式(2))。Cand.A和Cand.B分別是GA和GU中由社區(qū)和鄰域結(jié)構(gòu)生成的潛在正確映射的2個(gè)候選集。

2 異構(gòu)去匿名模型

圖1為異構(gòu)去匿名模型結(jié)構(gòu)。該結(jié)構(gòu)有3個(gè)主要步驟：①社區(qū)檢測(cè)，根據(jù)社交網(wǎng)絡(luò)圖結(jié)構(gòu)檢測(cè)網(wǎng)絡(luò)中的社區(qū)；②社區(qū)對(duì)齊，根據(jù)輪廓自動(dòng)識(shí)別種子，并對(duì)齊包含相同種子對(duì)的社區(qū)；③在社區(qū)節(jié)點(diǎn)映射，在每對(duì)對(duì)齊的社區(qū)中計(jì)算具有高相似度得分的節(jié)點(diǎn)，該得分由輪廓相似度計(jì)算，并傳播到其鄰域節(jié)點(diǎn)。算法1為整個(gè)過程執(zhí)行過程。

圖1 異構(gòu)去匿名模型結(jié)構(gòu)

算法1 異構(gòu)去匿名模型執(zhí)行過程輸入:GA,GU,閾值θ;輸出:用戶映射μ′//社區(qū)檢測(cè)CA=Infomap(GA)CU=Infomap(GU)//社區(qū)對(duì)齊μ=SelectSeeds(VA,Vb)CommPairs=AlignCommunities(CA,CU,μ)//社區(qū)內(nèi)節(jié)點(diǎn)映射μ′=InCommunityMapping(CommPairs,μ,θ)Returnμ′

2.1 社區(qū)檢測(cè)

第一步的目標(biāo)是將社交網(wǎng)絡(luò)圖GA和GU劃分為兩組社區(qū)CA={c1,c2,…,cm}和CB={c1,c2,…,cn}。在Infomap算法[10]的基礎(chǔ)上設(shè)計(jì)社區(qū)檢測(cè)算法，該算法具有較低的時(shí)間復(fù)雜度，可以將不相交、不重疊的社區(qū)CA和CU分別劃分為2個(gè)圖。簡言之，Infomap找到了隨機(jī)游走者的最短多級(jí)描述，因此給出了網(wǎng)絡(luò)的最佳分層聚類、每個(gè)層次上的最佳層數(shù)和模塊劃分。因此，使用Infomap算法的另一個(gè)優(yōu)點(diǎn)是它可以在不同的層次上生成不同尺度的CA和CU，這樣就可以選擇相似尺度的社區(qū)進(jìn)行對(duì)齊。社區(qū)檢測(cè)和劃分的算法在算法1中用Infomap(·)函數(shù)表示，且其時(shí)間復(fù)雜度為O(|E|)。

2.2 社區(qū)對(duì)齊

考慮到公共可用的概要信息，社區(qū)可以更容易地對(duì)齊。選擇用戶名(或昵稱)來識(shí)別種子。主要原因如下：首先，用戶名(或昵稱)必須在每個(gè)社交網(wǎng)絡(luò)的網(wǎng)站上都可用，因此攻擊者有足夠的機(jī)會(huì)獲取或爬網(wǎng)它們；其次，具有相同用戶名(或昵稱)的2個(gè)賬戶有較大概率屬于同一用戶。

設(shè)計(jì)應(yīng)用于社交網(wǎng)絡(luò)的社區(qū)對(duì)齊算法，該算法可分為兩步執(zhí)行，并根據(jù)社區(qū)中相同用戶名的個(gè)數(shù)來對(duì)齊CA和CU。

步驟1 找到具有相同用戶名μ={…,(ui,uj)k,…}的所有用戶對(duì)，其中ui∈VA和uj∈VU。使用貪婪搜索會(huì)導(dǎo)致O(|VA||VU|)的高度復(fù)雜性。為降低復(fù)雜度，采用哈希表實(shí)現(xiàn)這一過程，這樣時(shí)間復(fù)雜度就可以降低到O(|VA|+|VU|)。此過程在算法1中表示為SelectSeeds(·)函數(shù)；

步驟2 將每對(duì)社區(qū)(Ci,Cj)的初始置信度csi,j(表明2個(gè)社區(qū)是否應(yīng)對(duì)齊)設(shè)置為0，其中Ci∈CA，1≤i≤m，Cj∈CU，1≤j≤n。對(duì)于每對(duì)(up,uq)∈μ，csi,j逐次累計(jì)加1，且有up∈Ci和uq∈Cj。接著，檢查社區(qū)對(duì)的所有置信度cs，如果csi,j超過閾值θcs，則對(duì)齊Ci和Cj。該過程的時(shí)間復(fù)雜度為O(|μ|)

綜上，社區(qū)對(duì)齊算法的總體復(fù)雜度為O(|VA|+|VU|)。

2.3 社區(qū)內(nèi)節(jié)點(diǎn)映射

算法2描述了社區(qū)內(nèi)節(jié)點(diǎn)映射算法。在每對(duì)對(duì)齊的社區(qū)內(nèi)，依次執(zhí)行傳播和映射算法。

算法2 InCommunityMapping(·)算法執(zhí)行過程輸入:社區(qū)對(duì)CommPairs,種子μ,閾值θ;輸出:用戶映射μ′ For (Ca,Cu)j∈CommPairs do μj=Propagation(Ca,Cu)endreturn μ′=∪j=1,…,len(CommPairs)μjDef Propagation(R1,R2): μj∈μ While exists∈μj do R1=α(v1),R2=α(v2) For r1 in R1 For ri in R2 scores[r1].add(MatchScore(r1,ri)) end if MAX(scores[r1])>θ rmax=r∈MAX(scores[r1]) μj← end end end return μj

該算法以Gc1=(Vc1,Ec1)，Gc2=(Vc2,Ec2)2個(gè)社區(qū)圖和社區(qū)中的種子集μc1,c2作為輸入。算法執(zhí)行時(shí)在μc1,c2的相鄰種子集中迭代地尋找新的映射，并基于圖結(jié)構(gòu)擴(kuò)展映射過程。在每次迭代中，該算法計(jì)算2個(gè)相鄰集Ru=α(u)和Rv=α(v)內(nèi)的相似度得分，且這2個(gè)相鄰集由2個(gè)已映射的用戶u和v生成。進(jìn)一步，?ru∈Ru，計(jì)算與Rv中用戶的相似度得分，并找出得分最高的rv。算法中采用MatchScore(·)函數(shù)計(jì)算相似度，如果得分超過預(yù)先定義的閾值θ，則ru和rv表示成功的映射。如果一個(gè)已經(jīng)映射的節(jié)點(diǎn)被映射到另一個(gè)具有更高相似度分?jǐn)?shù)的節(jié)點(diǎn)，則先前的映射將被具有更高分?jǐn)?shù)的新映射替換。如果沒有發(fā)現(xiàn)新的映射，則該過程將停止，并收集2個(gè)社區(qū)傳播過程中未訪問的節(jié)點(diǎn)進(jìn)行比較以找到剩余的映射。

傳播過程的時(shí)間復(fù)雜度為O(min{|Vc1|,|Vc2|}dc1dc2)，其中dc1和dc2分別是Vc1和Vc2中節(jié)點(diǎn)度的界限。

3 仿真與分析

以2個(gè)異構(gòu)在線社交網(wǎng)絡(luò)的數(shù)據(jù)集(Flickr和Last.fm)驗(yàn)證本文所提方法。數(shù)據(jù)集包括節(jié)點(diǎn)信息、邊緣信息和社交網(wǎng)絡(luò)用戶子集的概要信息。根據(jù)社交網(wǎng)絡(luò)數(shù)據(jù)集中的“朋友”或“跟隨”關(guān)系構(gòu)建無向社交網(wǎng)絡(luò)圖。統(tǒng)計(jì)數(shù)據(jù)信息如表1所示。仿真環(huán)境使用Python語言，程序運(yùn)行在2.4 GHz CPU，內(nèi)存為32 G的服務(wù)器上。此外，選取準(zhǔn)確率及召回率作為性能指標(biāo)驗(yàn)證算法性能。

表1 社交網(wǎng)絡(luò)數(shù)據(jù)集信息統(tǒng)計(jì)

3.1 閾值選取測(cè)試

圖2和圖3為不同閾值θ下本文方法與傳統(tǒng)輪廓匹配方法分別在數(shù)據(jù)集Flickr和Last.fm準(zhǔn)確率和召回率對(duì)比結(jié)果?？梢钥闯?，本文方法結(jié)果明顯優(yōu)于傳統(tǒng)輪廓匹配方法。由前述可知，閾值θ是一個(gè)相似性準(zhǔn)則，本文算法中接受一對(duì)節(jié)點(diǎn)作為映射，即如果2個(gè)節(jié)點(diǎn)之間的相似性得分超過θ，則這2個(gè)節(jié)點(diǎn)表示為潛在映射。因此，θ越高，接受的節(jié)點(diǎn)越相似，因此返回的潛在映射就越少。所以θ實(shí)際上反映了精確性和召回之間的權(quán)衡。實(shí)際情況下，攻擊者可以根據(jù)自己的要求來選擇θ。當(dāng)閾值設(shè)置為0.9時(shí)，本文方法匹配準(zhǔn)確度可達(dá)90%以上，召回率可達(dá)40%。仿真結(jié)果進(jìn)一步驗(yàn)證了該算法可以實(shí)現(xiàn)大規(guī)模精確解匿名。

圖2 Flickr數(shù)據(jù)集仿真結(jié)果

圖3 Last.fm數(shù)據(jù)集仿真結(jié)果

3.2 算法性能測(cè)試

圖4為所提出模型在Flickr數(shù)據(jù)集中與基于節(jié)點(diǎn)匹配[11]、RoleMatch算法[12]的性能曲線,其中閾值設(shè)置為0.9，可以看出，所提模型在40次迭代時(shí)可獲得最佳性能，而其他模型在60次以上迭代時(shí)可獲得最佳性能，且模型準(zhǔn)確率有所提升。由此可見，所提模型收斂速度更快，且模型性能更優(yōu)。

圖4 不同算法性能對(duì)比結(jié)果

4 總結(jié)

本文對(duì)異構(gòu)社交網(wǎng)絡(luò)中去匿名化過程過程進(jìn)行了研究與分析，并提出了一種異構(gòu)去匿名化算法提高模型檢測(cè)精度。

本文在進(jìn)行仿真及實(shí)驗(yàn)驗(yàn)證時(shí)假定用戶信息都為準(zhǔn)確的，未考慮部分用戶可能會(huì)填寫“假信息”或僅有部分信息情況。未來可對(duì)信息獲取條件受限及數(shù)據(jù)存在壞值等情況進(jìn)行研究，引入大數(shù)據(jù)、數(shù)據(jù)挖掘、人工智能等技術(shù)提高用戶相似性匹配度等，進(jìn)一步提升模型適用性范圍。此外，社區(qū)匹配的置信度閾值在實(shí)際狀況下可以自由選擇，未來可引入機(jī)器學(xué)習(xí)模型對(duì)閾值進(jìn)行調(diào)參，選取最優(yōu)閾值。