王勝和，孫福林

(1.安徽公安職業(yè)學院 公安科技系，安徽 合肥 230088； 2.東南大學 計算機科學與工程學院，江蘇 南京 211189)

?

防止多社區(qū)結構化攻擊的加權社會網絡隱匿方法

王勝和1，孫福林2

(1.安徽公安職業(yè)學院 公安科技系，安徽 合肥 230088； 2.東南大學 計算機科學與工程學院，江蘇 南京 211189)

摘要：傳統(tǒng)面向加權社會網絡的隱私保護技術多數針對用戶個體隱私保護，而對基于權重背景知識引發(fā)集群隱私泄露缺少關注。將權重屬性信息作為額外背景知識，提出一種基于數據擾動的(kα,lβ)-secure社會網絡隱私保護模型，有效防止個體用戶和社區(qū)結構敏感標識的逆推攻擊；并基于此模型設計實現(xiàn)了一種圖匿名化方法，能夠以盡可能小的信息損失構建符合(kα,lβ)-secure模型的匿名圖。理論分析和實驗結果表明，本文方法可以有效避免攻擊者對用戶個體隱私和社區(qū)集群隱私所造成的逆推攻擊，同時最大限度保持權重信息的可用性。

關鍵詞：社區(qū)劃分; 加權社會網絡; (kα,lβ)-secure; 隱私保護

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.011

隨著Facebook、Twitter等社會網絡平臺的日益流行，個體用戶或組織收集并共享大量數據成為可能，對數據共享也帶來了用戶敏感信息的安全保護問題[1-4]。在社會網絡隱私保護方面， Li等提出了直方圖匿名(histogram anonymization)技術，防止加權圖中節(jié)點鄰接權重序列信息導致用戶身份泄露的隱私攻擊[5]；Liu等提出采用k-度匿名圖來防止隱私攻擊的技術[6]；LiuXiangyu等分析了加權社會網絡圖中的節(jié)點識別問題，提出了k-可能匿名模型來防止基于權重的隱私攻擊[7]；Cheng提出k-同構匿名方法，有效防止節(jié)點識別和邊識別等隱私攻擊[8]；Lan提出一種二部圖k-自同構隱私保護策略，保護加權圖的敏感聯(lián)系和結構化模式[9]；Zou提出k-自同構匿名阻止節(jié)點再識別隱私攻擊[10]；楊俊等提出基于圖自同構的AK-Secure隱私模型，有效防止隱私攻擊，同時維持發(fā)布圖數據的高可用性[11]；Das等提出一種基于線性規(guī)劃的隱私模型，根據最短路徑等權重相關屬性表示為權重的線性關系，設計匿名策略來保護權重和最短路徑信息的隱私安全[12]；Liu等提出了高斯隨機乘法擾動和貪心擾動方法，在不增加或刪除邊的情況下擾動權重值，保護最短路徑信息的隱私安全[13]；Wang等研究了加權社會網絡圖中路徑敏感信息隱私泄露問題，針對不同的邊類型，提出適用于有向或無向加權圖的最短路徑匿名化算法[14]。

上述文獻中的研究主要基于k-匿名隱藏、圖同構和數據擾動思想。時下熱門的知識挖掘與個性化推薦系統(tǒng)都是社會網絡社區(qū)劃分的應用，如一個簡單的個性化推薦系統(tǒng)中，多個具有共同購買興趣的用戶組成一個社區(qū)結構。用戶既需要個體敏感標識在發(fā)布的社會網絡中不能被識別，又需要所在推薦社區(qū)的購買興趣不能被攻擊者識別。然而傳統(tǒng)的k-匿名方法多數只能使發(fā)布圖滿足個體用戶隱私安全，并未考慮到社區(qū)集群隱私安全問題，而且會帶來圖數據信息可用性的較大損失。為了解決多社區(qū)結構化的加權社會網絡發(fā)布面臨的個體用戶隱私安全和社區(qū)集群隱私安全威脅，文章提出基于數據擾動的(kα, lβ)-secure社會網絡隱私保護模型，有效防止個體用戶和社區(qū)結構敏感標識的逆推攻擊，同時設計基于貪心選擇的加權圖匿名化算法，在生成滿足隱私要求的匿名圖的同時兼顧權重數據的可用性。

1相關概念和背景知識

將加權社會網絡定義為四元組G(V,E,W,C)，圖G是一個無向連通圖。V(G)為節(jié)點集合，E(G)?V(G)×V(G)為節(jié)點間鄰接邊集合，W(G)={wei|wei為邊ei上的權重值}為圖G的邊權集合。C(G)={Ci(G)∣Ci(G)為圖G的一個劃分子圖，Ci(G)?G，1≤i≤n}為加權社會網絡G所劃分的社區(qū)集合。

定義2(社區(qū)用戶親密度Friendship)給定待發(fā)布的加權社會網絡G，某個社區(qū)結構Ci(G)?C(G)。社區(qū)結構Ci(G)內用戶節(jié)點v的鄰接節(jié)點集合表示為ADJv={vj|(v,vj)∈E(G)}，那么社區(qū)用戶親密度F(v,vj)可以用v與其鄰接好友用戶vj間連接邊權值來衡量，定義如下

F(v,vj)={wej|minF≤wej≤maxF,v與vj間關聯(lián)邊ej}，其中minF和maxF分別標識目標用戶v與好友vj間最小親密度(標識最不親密聯(lián)系)和最大親密度(標識最親密聯(lián)系)。

定義3(權重關聯(lián)攻擊背景Weight-Related Background，WRB)給定加權社會網絡圖G，權重關聯(lián)攻擊背景WRB包括攻擊者藉以發(fā)起對發(fā)布圖G中節(jié)點/邊再識別攻擊的先驗知識：

1) 目標用戶v在發(fā)布社區(qū)中的權威值Av，可能造成節(jié)點再識別攻擊。

2) 目標用戶v與好友間邊界親密度F(v,vj)，可能造成敏感聯(lián)系再識別攻擊。

引入兩個不同隱私安全層級，滿足發(fā)布后加權社會網絡匿名化需求。

定義4(個體用戶隱私安全User Privacy Security，UPS)給定加權社會網絡G，某個社區(qū)結構Ci(G)?C(G)，若攻擊者由所掌握的WRB信息無法對G中用戶v的敏感標識進行猜測，則所發(fā)布的加權社會網絡滿足個體用戶隱私保護要求。

定義5(社區(qū)集群隱私安全Community Privacy Security，CPS)給定社會網絡G，某個社區(qū)結構Ci(G)?C(G)，若攻擊者借助所掌握WRB信息無法對社區(qū)Ci(G)的敏感標識進行逆推猜測，稱所發(fā)布加權社會網絡圖滿足社區(qū)集群隱私保護要求。

2防止多社區(qū)結構化攻擊的(kα,lβ)-secure隱私保護模型

傳統(tǒng)的k-匿名方法多數只能使發(fā)布圖滿足UPS，并未考慮到CPS問題，基于此提出基于數據擾動的(kα,lβ)-secure社會網絡隱私保護模型。

定義6(kα,lβ)-secure隱私保護模型給定待發(fā)布的加權社會網絡G，某個社區(qū)結構Ci(G)?C(G)，隱私偏好參數α，β。對?vi∈V(G)，基于攻擊者掌握的WRB知識信息，社區(qū)Ci(G)內至少存在其余k-1個節(jié)點，這些節(jié)點與vi之間的WRB相似度不大于α；同時社會網絡圖G至少存在其余l(xiāng)-1個社區(qū)，這些社區(qū)內至少存在一個節(jié)點u與vi之間的WRB相似度不大于β。符合上述要求的G滿足(kα,lβ)-secure隱私約束。

定義7(權重信息損失Weight Information Loss,WIL)將加權社會網絡圖G匿名化后得到匿名圖G*，若圖G的邊上權重的最小改變量為Δmin，那么對于?e∈E(G)，邊上的權重相對改變量(Relative Weight Change,RWC) 為RWCe=we/Δmin，則匿名圖的權重信息損失定義為

給定待發(fā)布的加權社會網絡圖G，正整數k、l，隱私偏好參數α、β，需要設計匿名策略使得匿名發(fā)布后的圖G*滿足(kα,lβ)-secure隱私約束，同時權重可用性損失WIL(G,G*)最少。

3多社區(qū)加權社會網絡匿名化算法

根據上述隱私保護模型，提出一種基于數據擾動的圖匿名策略，得到滿足(kα,lβ)-secure隱私保護模型的多社區(qū)劃分加權社會網絡。基于攻擊者所掌握的權重關聯(lián)攻擊背景WRB，設計匿名化算法。

為了滿足UPS和CPS要求，需要將社區(qū)用戶權威值進行匿名化處理，防止通過節(jié)點屬性(node info)進行敏感信息的逆推攻擊。設計實現(xiàn)一種數據擾動算法KLNA(K-user L-community Node Anonymity)，通過貪心選擇，使得擾動后的權威值滿足隱私要求，達到安全保護的目的，算法描述如表1所示。

表1　算法1執(zhí)行過程

考慮為滿足用戶UPS和CPS要求，需進行社區(qū)用戶親密度F的隱藏，進而防止通過邊聯(lián)系屬性(link info)進行敏感信息的逆推攻擊?？梢酝ㄟ^擾動敏感聯(lián)系，使得用戶與好友間的親密度信息不可區(qū)分，達到隱私保護目的。

4實驗分析

實驗環(huán)境為Inter(R) Core(TM)i5 CPU 2.30 GHz，內存3 GB，Windows 7操作系統(tǒng)，所涉及代碼采用Visual C++(6.0)實現(xiàn)。實驗數據集信息見表2。

表2　數據集相關信息

實驗結果如圖1所示。對本文所提出的匿名化方法與K-同構匿名方法KIA得到的匿名圖其聚類系數kcc(Clustering Coefficient)值均隨著參數k，l值的增大而增大，KLNA算法匿名系數差值增幅較為緩慢(增長幅度小于0.05)；而K-同構匿名方法KIA得到的匿名圖其kcc值與原始圖G的差值較大，且匿名系數差值增幅較大(增長幅度大于0.05)。

(a)DBLP數據集

(b)Cond-Mat-2005數據集

實驗測試算法應用到匿名圖G*的執(zhí)行時間隨k、l值增幅變化情況如圖2所示。由圖2可知，隨著k、l值增幅的變化，算法的執(zhí)行時間基本隨之線性增加。因為k、l值越大，匿名復雜度越高，算法執(zhí)行時間越長，說明本文所提出的匿名化算法具有較好的執(zhí)行效率。

圖2　算法執(zhí)行時間

5總結

本文介紹了面向多社區(qū)結構化加權社會網絡圖數據發(fā)布時所面臨的結構化攻擊問題，提出基于數據擾動的(kα,lβ)-secure隱私保護模型，有效防止個體隱私信息泄露和社區(qū)敏感標識泄露等隱私攻擊；基于此模型設計了一種加權圖匿名化算法，在生成滿足隱私要求的匿名圖的同時，能夠兼顧權重數據可用性?；谡鎸崝祿M行了對比實驗分析，驗證了(kα,lβ)-secure隱私保護模型的準確性和有效性。

參考文獻:

[1]AggarwalG,FederT,KenthapadiK,etal.Achievinganonymityviaclustering[C].ProceedingsoftheSymposiumonPrinciplesofDatabaseSystems(PODS),Chicago,USA,2006:153-162.

[2] 劉向宇，王斌，楊曉春. 社會網絡數據發(fā)布隱私保護技術綜述[J]. 軟件學報, 2014, 25(3): 576-590.

[3]SweeneyL.K-anonymity：Amodelforprotectingprivacy[J].InternationalJournalofUncertainty,Fuzziness,andKnowledge-BasedSystems, 2002, 10(5):557-570.

[4] 李陽，王曉巖，王昆，等. 基于社交網絡的安全關系研究[J]. 計算機研究與發(fā)展，2012, 49(S2):124-130.

[5]LiYidong,ShenHong.Anomymizinggraphsagainstweighted-basedattacks[C].Proceedingsofthe2010IEEEInternationalConferenceonDataMiningWorkshops,Sydney,Australia, 2010: 491-498.

[6]LiuK,TerziE.Towardsidentityanonymizationongraphs[C].Proceedingsofthe28thACMSIGMODInternationalConferenceonManagementofData,NewYork,USA, 2008: 93-106.

[7]LiuXiangyu,YangXiaochun.Ageneralizationbasedapproachforanonymizingweightedsocialnetworkgraphs[C].Proceedingsofthe12thInternationalConferenceonWeb-AgeInformationManagement,Wuhan,China, 2011: 118-130.

[8]ChengJ,FuAW,LiuJia.K-isomorphism:Privacypreservingnetworkpublicationagainststructuralattacks[C].Proceedingsofthe2010ACMSIGMODInternationalConferenceonManagementofData,NewYork,USA, 2010: 459-470.

[9]LanLihui,CongBiao.Weightedsocialnetworksanonymizingpublication[C].RecentAdvancesininComputerScienceandInformationEngineering2012, 124: 413-421.

[10]ZouL,ChenL,?zsuMT.K-automorphism:Ageneralframeworkforprivacypreservingnetworkpublication[J].ProceedingsoftheVLDBEndowment, 2009, 2(1): 946-957.

[11] 楊俊，劉向宇，楊曉春. 基于圖自同構的K-Secure社會網絡隱私保護方法[J]. 計算機研究與發(fā)展，2012, 49(增刊): 264-271.

[12]DasS,EgeciogluO,AbbadiA.Anonymizingweightedsocialnetworkgraphs[C].Proceedingsofthe26thIEEEInternationalConferenceonDataEngineering,LongBeach,USA,2010: 904-907.

[13]LiuL,WangJ,LiuJ,etal.Privacypreservinginsocialnetworksagainstsensitiveedgedisclosure[C].Proceedingsofthe2009SIAMInternationalConferenceonDataMining,Sparks,USA, 2009: 954-965.

[14]WangSL,TsaiZZ,HongTP,etal.Anonymizingshortestpathonsocialnetworkgraphs[C]ProceedingsoftheThirdInternationalConferenceonIntelligentInformationandDatabaseSystems,Daegu,Korea,2011：129-136.

Privacy-Preserving Weighted Social Network Anonymization Against Structural Attacks with Multiple Communities

WANG Sheng-he1，SUN Fu-lin2

(1.Department of Public Security Technology, Anhui Public Security Professional College, Hefei, Anhui 230088, China；2. School of Computer Science and Engineering, Southeast University, Nanjing, Jiangsu 211189 ,China)

Abstract:Most existing research concern about personal user privacy security only, while few work focus on the community privacy security with weighted-based background knowledge. The personal user privacy and community clustering privacy issues were investigated in weighted graph, with background knowledge of weight-related attributes. Correspondingly, weighted graph (kα,lβ)-secure anonymity model is proposed to protect against structural re-identification attacks on sensitive personal identity and community identity. Further, a weight perturbation based approach is elaborated to achieve (kα,lβ)-secure anonymity with minimum weight-related information loss. Extensive experiments and results analysis show that the algorithm can efficiently prevent structural privacy attacks and meanwhile it can retain the structural properties of the original graph and increase the utility of the weight information.

Key words:multiple communities; weighted social network; (kα,lβ)-secure; privacy protection

* 收稿日期：2015-12-02

基金項目：安徽省科技攻關計劃項目(1401b042011)。

作者簡介：王勝和，男，安徽肥東人，碩士，安徽公安職業(yè)學院公安科技系副教授，研究方向為網絡安全。 E-mail: 307680622@qq.com

中圖分類號：TP311

文獻標識碼：A

文章編號：1007-4260(2016)02-0039-04

網絡出版時間：2016-06-08 12:57網絡出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.011.html