一種基于結構及節點特征相似度的社交網絡圖數據去匿名方法

王照永，陳勤，朱宏林，馮世杰

（杭州電子科技大學信息安全部級重點實驗室，杭州 310018）

0 引言

如今，社會網絡在人們的日常生活、工作中扮演著不可或缺的角色。例如像微博、Facebook、Twitter等社會網絡已成為人們獲取信息、分享信息和營銷推廣等的重要途徑。由于其自身的透明性和匿名性，這將導致既不易追蹤網絡中虛假謠言的發布者，又不易追查相關違法犯罪活動的參與者。若攻擊者對用戶位置數據集進行去匿名化可獲得用戶的個人位置信息，則可對其進行監視、跟蹤，這將有助于案件的偵破。若深入分析用戶的位置和運動軌跡等信息，則可能挖掘推斷出用戶的行為模式、興趣愛好，甚至健康和政治傾向等個人隱私信息。因此，無論對分析研究還是案件偵破，社交網絡中匿名數據的再識別都具有重要的經濟和社會價值。例如，大型電商網站通過對網站用戶數據分析，可以推測分析用戶的生活習慣和購物傾向。顯然，用戶的私人的信息將會遭到泄露從而引起安全問題。

近年來，社會網絡數據的隱私安全問題得到了大量關注[1-3]。例如基于k匿名技術的隱私保護[4-5]和基于圖映射的去匿名技術[6-8]研究。然而，先前的去匿名研究仍然存在局限性：（1）先前的大多數攻擊只關注去匿名，即實現匿名用戶集與輔助數據集的映射。而在去匿名后，攻擊者是如何獲取和推斷用戶的隱私信息的卻很少被討論。（2）有些攻擊者通常不考慮圖節點的屬性特征。實際上，攻擊者不僅可以直接從發布的數據中獲取用戶的屬性，還可以根據其他屬性推斷出一些用戶的敏感屬性。以薪資為例，雖與包括教育和職業在內的多種屬性密切相關，但可推測作為程序員或醫生明顯意味著高薪。為了解決這些限制問題，本文構建了去匿名攻擊的圖模型，并使用該模型來描述一些敏感隱私信息的推斷過程。通過去匿名攻擊的圖模型來實現兩個數據集圖節點間的映射。本文提出了一種基于用戶社會網絡圖結構及節點間的特征的去匿名方法，通過對兩個數據集圖的結構特征及節點特征的分析研究，提出了基于節點間相似度的去匿名方法。本文的去匿名的方法，假設攻擊者已獲得了其攻擊對象部分或全部的一些具體的詳細信息（即作為攻擊輔助信息），分別對匿名數據集與輔助數據集的圖的結構及節點間進行相似度特征的匹配，進而盡可能多地成功實現兩個數據集節點間的映射，最終確認匿名對象的所有相關信息。此外，在更新的先驗攻擊圖上進行用戶敏感屬性或行為傾向的推測，以此挖掘出用戶的隱私信息。在兩個真實社會網絡數據集上進行了大量實驗，實驗結果證明，提出的去匿名方法在匿名的準確率及運行時間上效率提高。

1 相關工作

近年來，社會網絡中數據的去匿名研究受到了學術界、工業界的廣泛關注。去匿名研究關注點包括社會網絡用戶的興趣、位置和社交關系等方面。例如：基于位置的社交網絡服務（LBSNS）已經變得流行起來，此服務正在收集大量的地理社交網絡位置數據，從而引發了記錄移動記錄的個人隱私風險的問題。Gam等人[9]提出了一種基于移動馬爾可夫鏈（MMC）的移動性模型來實現這種攻擊。Wei等人[10]提出了一種基于位置的興趣點標識方法，通過提取訪問興趣點的用戶團體的特征描述用戶個體興趣點的特征，將獲得標識的興趣點推薦給有相同興趣的用戶。Davis Jr.等人[11]通過Twitter用戶粉絲中可定位的用戶，運用多數投票方法來推斷其他用戶發布博文的地理位置。

社會網絡數據包含了大量用戶的個人信息。雖國內外對社交網絡數據的隱私保護研究已經取得了不少成果，但仍存在一些局限。如在非交互式社交網絡中，現有的研究工作大多只考慮了單次發布的社交網絡數據。然而對于連續發布的社交網絡數據集，一方面，現有的匿名化方法無法很好地保護用戶隱私，也不能滿足對匿名數據進行演化分析的需要；另一方面，現有的去匿名化方法中固有的不確定性被放大了，因此仍存在較大的改進空間。因此，需對基于社會網絡數據的圖的結構特征進行進一步的研究。

目前，在基于社會網絡數據圖的結構特征的去匿名化攻擊中，假設攻擊者獲取了用戶的詳細信息（即輔助信息），如通過網絡爬蟲等方法獲取不同社交網絡中用戶及用戶間的關系等信息。去匿名化攻擊分為主動攻擊和被動攻擊。主動攻擊是在數據發布之前，攻擊者已創建一定數量的賬號并使他們各自成為固定的關系，這樣就形成了一種極易分辨出來的圖結構，在數據匿名發布后，首先找到這些節點的映射，然后以此為中心對其他節點進行去匿名化操作變的相對容易些。但其顯然不太適用于大數據集，且需要創建大量的偽節點比較麻煩。被動攻擊則是需要獲取其他的相關信息，例如其他一些熱門社會網絡的用戶數據集，以此作為攻擊輔助數據集，無需創建大量偽節點，可通過特征相識度匹配，實現數據集的用戶間的映射以實現社交網絡匿名數據的去匿名化。

此外，已經提出了各種基于圖的結構的方法來對社交網絡數據進行去匿名化[12-14]。給定匿名的社會網絡圖結構和真實信息的輔助用戶圖結構，基于圖的結構的去匿名方法是通過檢查這兩個社會網絡中節點間的相似性來實現節點之間的映射，最終再識別匿名用戶。Narayanan等人[15]提出了完全基于網絡的拓撲結構的去匿名化方法，雖然開始需要對少量節點進行匹配，但并沒有像主動攻擊那樣，通過創建大量用戶偽節點來實現去匿名化。根據少量的輔助數據，尋找相似結構特征完成了種子節點的映射，然后通過不斷擴散進而找出新的節點映射關系，以較小的出錯率成功地識別出1/3的同時擁有Twitter和Flicker的用戶數據。Aston等人[12]提出了一種基于圖節點相似度測量的算法，同時也評估了幾種輕匿名算法的隱私風險。Ji S[8]等人研究了結構化數據去匿名的量化、實踐和意義。文獻[16]利用朋友關系的網絡圖將跨多個不同社會網絡的賬號映射數學建模,來識別屬于同一個用戶的所有賬戶。

然而，綜上文獻在基于社會網絡圖結構的去匿名方法仍存在局限性，本文提出了一種基于社交網絡數據圖的結構及節點特征相似度的去匿名方法，該方法利用社交網絡圖的結構特征與節點屬性的特征之間的相似性差異實現節點間的映射，去匿名正確率會高一些。

2 去匿名模型

針對數據集的匿名隱私保護，在數據發布之前，通常先對用戶的數據集進行匿名化技術處理（如Name&ID的刪除并替換、添加或刪除節點間的鏈接等），然后再發布其匿名后的數據集。對于去匿名化，攻擊者需構建先驗攻擊圖Gu和匿名圖Ga，然后利用去匿名和隱私推理技術來識別匿名用戶并推斷出用戶的一些敏感屬性。

2.1 數據模型

社會網絡數據圖的建模時，通過對其圖的結構的研究，發現由同一組用戶產生的社交網絡數據集圖的結構有很強的相似性。假設：（1）攻擊者不知道攻擊目標用戶的真實身份及兩個數據集節點間的映射關系。攻擊者試圖去匿名某一特定目標或一組用戶集，甚至所有匿名用戶。此外，攻擊者也可能獲取各種背景知識作為攻擊的先驗知識。（2）數據發布者是信任的，無論是數據集的發布前后。

社會網絡數據大多都有結構化的圖結構，因此要把匿名數據集結構化，表示為Ga=（Va，Ea）,Va={i│i是一匿名用戶}即為一匿名用戶集，Ea={e（i,j）│用戶間的關系，i,j∈Va}用戶關系集。實際上，社會網絡數據集往往是有向圖或無向圖的結合。然而，為了圖的構造簡單和不失一般性，假設Ga是一無向圖。注意，本文設計的算法可直接衍生到適用于有向圖場景中。

同樣，輔助數據用于構建攻擊者的先驗攻擊圖Gu。去匿名時兩個數據集通常都會有一些重疊用戶，這有助于匿名用戶的去匿名化。此外，獲取輔助數據方式有很多種，例如數據聚合、在線爬蟲、第三方的應用收集等。輔助數據集可表示為圖Gu=（Vu，Eu）,Vu={i|i是一已知的用戶}和Eu={e（i,j）│用戶間的關系，i,j∈Vu}。

2.2 去匿名概述

在去匿名化過程中，攻擊者試圖盡可能多地將先驗攻擊圖Gu中的節點映射到匿名圖Ga上的節點，本文是基于社會網絡圖結構及節點屬性特征的相似度差異實現節點間的映射。在完成某一映射方案之后，可將匿名節點相關聯的屬性也鏈接到先驗攻擊圖節點上，實現了先驗攻擊圖的更新。重要的是，還可根據新獲取的屬性信息進行用戶隱私信息的推測。過程如圖1。

圖1一去匿名的例子。假設Bill同時存在于匿名數據集和先驗數據集。原始數據集圖1（a）通過匿名處理后，再發布圖1（b）。攻擊者構建先驗攻擊圖1（c）。攻擊者知道用戶Bill有四條鏈接和年齡超過50等特征。攻擊者嘗試將先驗攻擊圖中的Bill節點映射到匿名圖中的一個節點。通過節點間相似度測量，發現節點有B和D與Bill都有很高的相似度，因此B和D都被添加到候選映射集合中。顯然，攻擊者從節點的屬性特征發現用戶B的年齡60而用戶D的年齡40,最后把Bill映射到節點B而不是D。接下來，圖Ga中與節點B鏈接的屬性同樣也與圖Gu的Bill相關聯，在這種情況下，若攻擊者確認Bill是程序員，則該屬性被添加到更新的圖1（d）中。攻擊者可推斷出私人的一些屬性或關系。就像圖1（b）描述的那樣，攻擊者知道程序員有超過5萬美元的薪水,因此攻擊者可以推斷出Bill的薪資等敏感信息狀況。

圖1 去匿名的過程

3 去匿名攻擊

基于兩個數據集的圖Ga和Gu，任意一個DA去匿名攻擊方案都被定義為映射的實現過程即σ：Va→Vu。基于用戶圖的結構及節點特征上的相似差異性盡可能多的實現用戶間的映射。

3.1 結構特征

本節先定義一些結構特征，對于任一數據集節點i∈Va或Vu，定義如下：

度：對于 i∈ Va（Vu）,其節點度表示為 d(i),即 d(i)=|其中是節點i領域的基數。

領域：對于 i∈Va（Vu），其領域特征 n(i)表示為一β維向量，β是一用戶定義的參數（非負的整數）并表示i用戶領域內第k大度節點(1≤k≤β)。

考慮到用戶的全局結構特征，定義了K距離（Top-K reference distance）和抽樣近似距離（sampling close?ness centrality）,從不同的角度來分析用戶圖的結構特征，進而有效的區分節點之間的差異性。定義如下：

Top-K 距離：對于 i∈Va（Vu），Top-K 距離 lK(i)表示一個K維向量，其表示節點i與其領域內的第k大度節點間的最短路徑的長度(1≤λ≤K)。注意，可能出現這種情況：若圖的結構中（Ga或Gu）中不存在邊關系，則=∞。

抽樣近似中心：對于 i∈Va（Vu），定義 C(i)來描述其全局拓撲結構特征，但并未導致多大的計算開銷。實際上，先隨機的從Va節點數據集中抽取 某 一 子集Sa?Va（Su?Vu）。然后其中 h（i,j）是用戶 i與 j之間的距離。

分別從圖的結構的局部和全局不同的角度分析了圖的結構特征。其中度和領域體現了用戶圖的局部結構特征，而Top-K參考距離和抽樣近似距離表現了用戶圖的全局結構特征。本文放棄使用準確近似中心（accurate closeness centrality）特征而引入了抽樣近似距離，也能體現出圖節點的全局結構特征，但并未導致太多的計算開銷。

3.2 相似度

根據上節的相關定義，考慮圖的結構特征，先定義了一個結構相似度如（1）：

其中匿名數據集的用戶i∈Va和輔助數據集的用戶j∈Vu，c1,c2,c3∈[0,1]是帶權重的常數值，且c1+c2+c3=1，d,c(i)=(d(i),c(i)),s(·)表示兩向量間的余弦相似度。而余弦相似度更多的是從方向上區分向量間的差異，對絕對的數值不敏感。這里，引入了調整余弦相似度，如在所有維度上數值減去節點平均度dˉ。從算法分析上，雖然復雜度增加了，但是相比普通余弦相似度結構相似度區別更容易了，這有助于去匿名化。

除了考慮結構上相似性外，又考慮到節點間的屬性相似度§a(i,j)。在圖1中，每個用戶節點i（?i∈Va）都有一些鏈接屬性。給定節點i及其出現的屬性鏈接都有置信分cs（假設在Gu中以100%置信分出現該節點屬性同樣也會在Ga中出現）,節點j（j∈Vu）類似于上定義。因此，節點i與j之間的屬性相似度如（2）所示：

在圖節點映射的實現過程中，為了提高節點間映射的準確率，應分別考慮圖節點的結構及節點屬性特征。最后，給 §s(i,j)，§a(i,j)分配權重，所以節點i和j的相似度表示為 S（i,j）:

3.3 去匿名算法

代碼如下：

該算法中，首先構建了兩個結構化數據集的圖：匿名圖和先驗攻擊圖（Ga與Gu）。實際上，若圖中兩個節點通過相似性匹配實現了映射，則它們領域內節點更有可能實現映射。為了減少映射空間和復雜度，選擇對圖節點進行廣度優先遍歷（BFS），這將會導致比DFS更少的錯誤累積。具體地說，第五步：圖Gu中每個節點 i∈Vu，通過計算相似性 S（i,j）,獲取其 k最相似的候選映射集合，其中k和θ是平衡匿名用戶去匿名的準確率和復雜度而預先定義的參數。此外，初始節點的選取是至關重要的，因為它對節點映射的實現過程有很大的影響。先隨機從圖Gu中選取高節點度的節點，并計算它與所有節點 j∈Ga之間的相似性。若相似度范圍大于閾值θ（默認設置為0.8），則選擇該節點作為初始節點。在這些最可能的候選集c(i)中，移除相似度小于θ的候選節點，通過匹配先驗攻擊圖和匿名圖形節點之間的相似度來實現圖節點之間的映射。當完成圖節點BFS時，就實現了所有節點的映射。

4 實驗與評估

本文對兩個社會網絡數據集進行去匿名攻擊實驗，且對用戶的隱私進行一些隱私推測，從而披露更多的用戶隱私數據。然后對兩個數據集的去匿名性能進行了評估。

表1 數據集的統計信息

4.1 數據集

本文使用社交網絡（Twitter和Google+）的兩個真實數據集進行去匿名化實驗。對于Twitter，從其網絡中獲取數據及他們的個人文件，其中包括81306個節點和1768149鏈接，且具有不完整或無效的錯誤屬性的用戶都被刪除。同樣Google+數據集，包括107614個節點和13673453鏈接。此外，預處理數據集，包括刪除重復的和離散的用戶個人文件。表1顯示了預處理數據集的統計信息。

在數據集去匿名攻擊之前，首先需匿名圖G以生成匿名圖Ga。給定任意原始數據集，用戶的隱私數據通常都包含在節點間鏈接和節點屬性。為了匿名G，鏈接和節點屬性通常受到擾亂等匿名技術處理。具體的來說，匿名圖中鏈接以抽樣概率Sa從圖G鏈接中隨機抽樣，并且圖G中用戶的姓名和ID都被刪除并用假名代替。這里，假設當匿名圖Ga生成時，節點的屬性保持不變。生成先驗攻擊圖Gu時，抽樣的方式略有不同。首先，選取了一些用戶作為攻擊者的目標用戶。注意，圖Gu上的鏈接是以抽樣概率Su從與上邊這些有關的用戶中隨機抽取得到的。同樣，假設節點的屬性保持不變。

4.2 實驗結果分析

為了評估去匿名算法的準確性，本文使用用戶被正確識別的比例和運行時間作為衡量去匿名算法效用和復雜度的標準指標。由于數據集Google+和Twitter上的實驗是相似的，先專注于數據集Google+。默認參數設置為：k=10,θ=0.7,Sa=Su=0.8,WS=0.6。實驗運行在Ubuntu14.04操作系統上，Intel Xeon 2.4GHz*4，內存32G。當對數據集Google+進行去匿名化攻擊時，每次去匿名實驗都會重復多次，實驗結果取平均值。

圖2顯示了參數k和θ是如何影響數據集去匿名化的準確度和時間復雜度。圖2（a），當k≤10,匿名數據集去匿名的準確率隨著k值的增加而提高。但當k＞10時，去匿名準確率具有較小的波動。但隨著k值的增加，運行時間不斷增加。這是因為進行節點映射時需匹配更多的節點。因此，默認設定參數k=10。據圖2（b）顯示，相似度閾值θ的變化對去匿名的準確率和運行時間影響有些差異。這些參數的設置與平衡去匿名的準確率和運行時間有很大的相關性。

此外，一些參數的設置對去匿名化準確率和運行時間也有很大的影響。圖3（a），當0.5≤Ws≤0.8時，去匿名方法的效果更好一些（注意，權值Ws,1-Ws是分配給圖的節點的結構相似性與屬性特性相似性的權重）。因此，這表明上述兩個特征值在測量節點間的相似性時起著重要的作用。但相比節點屬性特征，節點的結構特征對節點的映射的實現影響更重要一些。

圖2 去匿名的準確率和運行時間（k&θ）

圖3 去匿名的準確率和運行時間（Ws）

除了去匿名的準確度稍低一些，Twitter數據集的相關實驗也有類似的結果。本文采用了圖的廣度優先遍歷（BFC）遍歷節點和對節點屬性進行了k匿名處理，因此僅僅通過節點屬性特征的相似性來區分用戶是非常困難的。正如所考慮的，若有更多的基于圖的結構特征（如抽樣近似中心（Sampling closeness centrality）、Top-K 參考距離（Top-K reference distance）、l-hop neighborhood等）納入到的方法中，這將會提高去匿名的準確率。

5 討論

通過對實際數據集的實驗分析，發現對擁有高節點度或高圖密度的用戶組更有可能成功地被去匿名化。這是因為節點度高的用戶包含了更多的圖的結構信息。為了支持本文的想法，對實驗結果進行了深入的分析了解，觀察到具有較低程度的數據集節點很難被去匿名化。

假設圖Gu中每個節點都有相應的匹配節點在圖Ga上，即Vu?Va，且兩個數據集的重疊用戶的比例將直接影響去匿名的準確率。當兩個數據集的共同的節點數很少時，去匿名的準確率將會很低。此外，可能會出現原始數據集中不存在來自先前攻擊圖Gu的某一用戶，因此絕對不存在于匿名圖Ga中。這種情況下，應該稍微做出一些調整，一個用戶將被映射到假的節點或被直接忽略，即在圖Ga上很可能沒有匹配的節點。

6 結語

本文提出了一種基于社會網絡數據的圖的結構及節點特征相似度測量的去匿名攻擊，它綜合考慮了社會網絡圖結構特征和節點屬性特征的差異性，進行用戶節點間的相似性匹配來實現用戶間的映射，有效地推測出一些用戶的敏感信息數據。實驗結果表明，與現有的大多數去匿名方法相比，該方法提高了去匿名化的效率和準確率。未來將著重于研究以下方面：a）由于現有的多數匿名技術易受到基于圖的結構的DA攻擊，建議針對這種攻擊設計出有效的解決方案。b）如何定量分析社會網絡的去匿名風險？還沒有任何理論定量地分析匿名技術數據與去匿名攻擊的相關性。

[1]馮登國,張敏,李昊.大數據安全與隱私保護.計算機學報,2014，37（1）,246-258.

[2]珍富,董曉蕾,周俊等.大數據安全與隱私保護研究進展[J].計算機研究與發展,2016,53（10）:2137-2151.

[3]孟小峰,慈祥.大數據管理:概念、技術與挑戰[J].計算機研究與發展,2013,50（1）:146-169.

[4]Yuan M,Chen L,Yu P S,et al.Protecting Sensitive Labels in Social Network Data Anonymization[J].IEEE Transactions on Knowledge&Data Engineering,2013,25（3）:633-647.

[5]Roberto J.Bayardo,Rakesh Agrawal.Data Privacy through Optimal k-Anonymization[C].International Conference on Data Engineering,2005.ICDE 2005.Proceedings.IEEE,2005:217-228.

[6]Ding X,Zhang L,Wan Z,et al.A Brief Survey on De-Anonymization Attacks in Online Social Networks[C].Computational Aspects of Social Networks（CASoN）,2010 International Conference on.IEEE,2010:611-615.

[7]Fabiana C,Garetto M,Leonardi E.De-Anonymizing Scale-Free Social Networks by Percolation Graph Matching[C].Computer Communications（INFOCOM）,2015 IEEE Conference on.IEEE,2015:1571-1579.

[8]Ji S,Li W,Srivatsa M,et al.Structural Data De-Anonymization:Theory and Practice[J].IEEE/ACM Transactions on Networking,2016,24（6）:3523-3536.

[9]Gambs S,Killijian M O,del Prado Cortez M N.De-Anonymization Attack on Geolocated Data[J].Journal of Computer and System Sci-ences,2014,80（8）:1597-1614.

[10]Wei L Y,Yeh M Y,Lin G,et al.Discovering Point-of-Interest Signatures Based on Group Features from Geo-Social Networking Data[C].Technologies and Applications of Artificial Intelligence（TAAI）,2013 Conference on.IEEE,2013:182-187.

[11]Davis Jr C A,Pappa G L,de Oliveira D R R,et al.Inferring the Location of Twitter Messages Based on User Relationships[J].Transactions in GIS,2011,15（6）:735-751.

[12]Fu H,Zhang A,Xie X.Effective Social Graph De-Anonymization Based on Graph Structure and Descriptive Information[J].ACM Transactions on Intelligent Systems and Technology（TIST）,2015,6（4）:49.

[13]Ji S,Li W,Srivatsa M,et al.Structure Based Data De-Anonymization of Social Networks and Mobility Traces[C].International Conference on Information Security.Springer,Cham,2014:237-254.

[14]Ji S,Li W,Srivatsa M,et al.Structural Data De-Anonymization:Quantification,Practice,and Implications[C].Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security.ACM,2014:1040-1053.

[15]Narayanan A,Shmatikov V.De-Anonymizing Social Networks[C].Security and Privacy,2009 30th IEEE Symposium on.IEEE,2009:173-187.

[16]Korula N,Lattanzi S.An Efficient Reconciliation Algorithm for Social Networks[J].Proceedings of the VLDB Endowment,2014,7（5）:377-388.