王勝和，孫福林

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

?

防止多社區(qū)結(jié)構(gòu)化攻擊的加權(quán)社會(huì)網(wǎng)絡(luò)隱匿方法

王勝和1，孫福林2

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

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

關(guān)鍵詞：社區(qū)劃分; 加權(quán)社會(huì)網(wǎng)絡(luò); (kα,lβ)-secure; 隱私保護(hù)

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

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

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

1相關(guān)概念和背景知識(shí)

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

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

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

定義3(權(quán)重關(guān)聯(lián)攻擊背景Weight-Related Background，WRB)給定加權(quán)社會(huì)網(wǎng)絡(luò)圖G，權(quán)重關(guān)聯(lián)攻擊背景WRB包括攻擊者藉以發(fā)起對(duì)發(fā)布圖G中節(jié)點(diǎn)/邊再識(shí)別攻擊的先驗(yàn)知識(shí)：

1) 目標(biāo)用戶v在發(fā)布社區(qū)中的權(quán)威值A(chǔ)v，可能造成節(jié)點(diǎn)再識(shí)別攻擊。

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

引入兩個(gè)不同隱私安全層級(jí)，滿足發(fā)布后加權(quán)社會(huì)網(wǎng)絡(luò)匿名化需求。

定義4(個(gè)體用戶隱私安全User Privacy Security，UPS)給定加權(quán)社會(huì)網(wǎng)絡(luò)G，某個(gè)社區(qū)結(jié)構(gòu)Ci(G)?C(G)，若攻擊者由所掌握的WRB信息無(wú)法對(duì)G中用戶v的敏感標(biāo)識(shí)進(jìn)行猜測(cè)，則所發(fā)布的加權(quán)社會(huì)網(wǎng)絡(luò)滿足個(gè)體用戶隱私保護(hù)要求。

定義5(社區(qū)集群隱私安全Community Privacy Security，CPS)給定社會(huì)網(wǎng)絡(luò)G，某個(gè)社區(qū)結(jié)構(gòu)Ci(G)?C(G)，若攻擊者借助所掌握WRB信息無(wú)法對(duì)社區(qū)Ci(G)的敏感標(biāo)識(shí)進(jìn)行逆推猜測(cè)，稱所發(fā)布加權(quán)社會(huì)網(wǎng)絡(luò)圖滿足社區(qū)集群隱私保護(hù)要求。

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

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

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

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

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

3多社區(qū)加權(quán)社會(huì)網(wǎng)絡(luò)匿名化算法

根據(jù)上述隱私保護(hù)模型，提出一種基于數(shù)據(jù)擾動(dòng)的圖匿名策略，得到滿足(kα,lβ)-secure隱私保護(hù)模型的多社區(qū)劃分加權(quán)社會(huì)網(wǎng)絡(luò)?；诠粽咚莆盏臋?quán)重關(guān)聯(lián)攻擊背景WRB，設(shè)計(jì)匿名化算法。

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

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

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

4實(shí)驗(yàn)分析

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

表2　數(shù)據(jù)集相關(guān)信息

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

(a)DBLP數(shù)據(jù)集

(b)Cond-Mat-2005數(shù)據(jù)集

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

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

5總結(jié)

本文介紹了面向多社區(qū)結(jié)構(gòu)化加權(quán)社會(huì)網(wǎng)絡(luò)圖數(shù)據(jù)發(fā)布時(shí)所面臨的結(jié)構(gòu)化攻擊問(wèn)題，提出基于數(shù)據(jù)擾動(dòng)的(kα,lβ)-secure隱私保護(hù)模型，有效防止個(gè)體隱私信息泄露和社區(qū)敏感標(biāo)識(shí)泄露等隱私攻擊；基于此模型設(shè)計(jì)了一種加權(quán)圖匿名化算法，在生成滿足隱私要求的匿名圖的同時(shí)，能夠兼顧權(quán)重?cái)?shù)據(jù)可用性?；谡鎸?shí)數(shù)據(jù)集進(jìn)行了對(duì)比實(shí)驗(yàn)分析，驗(yàn)證了(kα,lβ)-secure隱私保護(hù)模型的準(zhǔn)確性和有效性。

參考文獻(xiàn):

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

[2] 劉向宇，王斌，楊曉春. 社會(huì)網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私保護(hù)技術(shù)綜述[J]. 軟件學(xué)報(bào), 2014, 25(3): 576-590.

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

[4] 李陽(yáng)，王曉巖，王昆，等. 基于社交網(wǎng)絡(luò)的安全關(guān)系研究[J]. 計(jì)算機(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] 楊俊，劉向宇，楊曉春. 基于圖自同構(gòu)的K-Secure社會(huì)網(wǎng)絡(luò)隱私保護(hù)方法[J]. 計(jì)算機(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

基金項(xiàng)目：安徽省科技攻關(guān)計(jì)劃項(xiàng)目(1401b042011)。

作者簡(jiǎn)介：王勝和，男，安徽肥東人，碩士，安徽公安職業(yè)學(xué)院公安科技系副教授，研究方向?yàn)榫W(wǎng)絡(luò)安全。 E-mail: 307680622@qq.com

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)識(shí)碼：A

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

網(wǎng)絡(luò)出版時(shí)間：2016-06-08 12:57網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.011.html