申艷光,閆晶星+,買建英,范永健
(1.河北工程大學(xué) 信息與電氣工程學(xué)院,河北 邯鄲056038;2.解放軍炮兵訓(xùn)練基地,河北 宣化075100)
用戶隱私信息的非法出售、假冒身份欺詐、社會網(wǎng)站本身存在的漏洞及第三方應(yīng)用程序的植入等對用戶的個人隱私造成了嚴(yán)重的威脅。由于社會網(wǎng)絡(luò)的復(fù)雜性,攻擊者可能具有大量的背影知識,同時抵御多種類型攻擊的隱私保護(hù)成為研究熱點。
目前,社會網(wǎng)絡(luò)中節(jié)點間的連接關(guān)系可能導(dǎo)致的隱私泄露問題[1,2]受到了人們的廣泛關(guān)注。Gao等[3]將兩結(jié)點之間的邊連接視為隱私信息,保證在不得知結(jié)點之間邊連接情況的同時準(zhǔn)確地計算任意兩點之間的最短路徑長度。針對節(jié)點連接關(guān)系和社會網(wǎng)絡(luò)圖結(jié)構(gòu)可能造成的隱私信息泄露問題,楊俊等[4]提出了一種基于圖自同構(gòu)的k-Secure社會網(wǎng)絡(luò)隱私保護(hù)模型,從而有效防止節(jié)點識別、邊識別和路徑長度泄露等隱私攻擊。已有的社會網(wǎng)絡(luò)隱私保護(hù)大部分只針對單一關(guān)系的社會網(wǎng)絡(luò),由于社會網(wǎng)絡(luò)的特殊性,多關(guān)系的社會網(wǎng)絡(luò)中多數(shù)據(jù)類型的隱私保護(hù)同樣受到人們的重視。Zhelea等[5]針對單類型節(jié)點多類型邊進(jìn)行了匿名化處理。(k,2)-匿名模型[6]、l-敏感邊匿名模型[7]等都對節(jié)點間的敏感關(guān)系進(jìn)行了隱私保護(hù)。Zheleva等[8]通過現(xiàn)有邊連接間的敏感關(guān)系計算節(jié)點間具有敏感關(guān)系的概率,實現(xiàn)對被刪除敏感邊的恢復(fù)。Campan等[9]提出了p-敏感k-匿名模型。南麗麗等[10]提出了一種基于信息混淆的社會網(wǎng)絡(luò)隱私保護(hù)機制。王小號等[11]針對攻擊者以社會個體領(lǐng)域信息作為背景知識進(jìn)行敏感邊識別的攻擊,提出了基于譜約束的敏感區(qū)劃分隨機擾動方法。張健沛等[12]針對等價類與數(shù)據(jù)表間敏感屬性分布的穩(wěn)定性,提出了一種SABuk tcloseness模型。吳宏偉等[13]提出了一種抗復(fù)合攻擊的 (k,l)-匿名發(fā)布算法,有效解決了抵御復(fù)合攻擊的問題。但是,以上匿名方法并沒有考慮抵御社會網(wǎng)絡(luò)中存在的節(jié)點間敏感關(guān)系和社會網(wǎng)絡(luò)圖結(jié)構(gòu)造成的隱私信息泄露問題。
本文針對社會網(wǎng)絡(luò)中敏感邊攻擊、節(jié)點度攻擊和朋友連接攻擊同時存在的問題,提出了一種面向含敏感關(guān)系的(k2,l)-匿名模型。
為了便于研究,社會網(wǎng)絡(luò)通常被抽象為圖結(jié)構(gòu),利用較為成熟的圖論知識對社會網(wǎng)絡(luò)進(jìn)行研究。實際生活中存在多種不同類型的復(fù)雜的社會網(wǎng)絡(luò),本文針對含敏感關(guān)系的社會網(wǎng)絡(luò)進(jìn)行研究。含敏感關(guān)系的社會網(wǎng)絡(luò)圖定義如下:
定義1 含敏感關(guān)系的社會網(wǎng)絡(luò):社會網(wǎng)絡(luò)圖G=(V,E,T)。其中,V 表示節(jié)點,E 表示節(jié)點間的關(guān)系,T表示邊的類型,若T 為1,則表示E 為敏感關(guān)系;T 為0,則表示E非敏感關(guān)系。
社會網(wǎng)絡(luò)中含敏感邊,首先通過添加非敏感邊構(gòu)建l-敏感邊匿名模型,然后通過添加非敏感邊實現(xiàn) (k2,l)-匿名模型。
定義2 l-敏感邊匿名模型:給定一個圖G= (V,E,T),若節(jié)點v有敏感關(guān)系,至少存在l個節(jié)點與節(jié)點v 有敏感關(guān)系,那么該圖滿足l-敏感邊匿名模型。
定義3 (k2,l)-匿名模型:給定一個圖G=(V,E,T),對圖中任意具有度對為d2= (d1,d2)事件邊的節(jié)點v,至少存在k-1個其它節(jié)點和v具有一個相同度對的事件邊;且若節(jié)點v有敏感關(guān)系,則至少存在l個其它節(jié)點與節(jié)點v有敏感關(guān)系。那么該圖滿足(k2,l)-匿名模型。
分別通過添加敏感邊和非敏感邊構(gòu)建匿名模型,社會網(wǎng)絡(luò)圖的可用性會降低,本文通過節(jié)點的度衡量社會網(wǎng)絡(luò)圖的匿名損失,社會網(wǎng)絡(luò)圖匿名信息損失量定義如下:
定義4 匿名度信息損失量:匿名圖G*與原始圖G 總的度差稱為匿名度信息損失量,定義為式 (1)
式 中:d(G*)(i)—— (k2,l)-匿 名 圖 節(jié) 點i 的 度,G*—— (k2,l)-匿名圖;d(G’)(i)——l-敏感邊匿名圖節(jié)點i的度,G’——l-敏感邊匿名圖;n——圖中的節(jié)點數(shù)。
本節(jié)首先介紹含敏感關(guān)系的 (k2,l)-匿名化方法,然后介紹具體的實現(xiàn)算法。
根據(jù) (k2,l)-匿名化要求。首先,對網(wǎng)絡(luò)中的節(jié)點添加敏感邊,使每個含敏感關(guān)系的節(jié)點至少與l個節(jié)點相連。然后,在滿足l-敏感邊匿名模型的基礎(chǔ)上,提出了基于動態(tài)規(guī)劃的度序列匿名算法 (dynamic programming degree sequence anonymization,DPDSA)和基于貪心算法的度序列匿名算法 (greedy algorithm degree sequence anonymization,GADSA),構(gòu)建 (k2,l)-匿名模型。度序列匿名算法的基本思想如圖1所示。
圖1 度序列匿名算法基本思想
為了降低匿名成本,在添加敏感邊的過程中首先選擇與不滿足l-敏感邊匿名模型且含有敏感關(guān)系的節(jié)點相連,其中l(wèi)的值根據(jù)用戶所需的隱私保護(hù)程度而定。在添加非敏感邊時選擇的節(jié)點應(yīng)遵循以下3個準(zhǔn)則:
(1)一個節(jié)點沒有和另一個組中的任何節(jié)點相連;
(2)兩個節(jié)點分別在各自組中度最??;
(3)在兩組節(jié)點中兩點之間路徑最短的節(jié)點。
本節(jié)介紹具體的 (k2,l)-匿名模型實現(xiàn)算法,分為3個主要模塊進(jìn)行介紹:動態(tài)規(guī)劃分組算法、貪心算法分組算法和構(gòu)建 (k2,l)-匿名模型算法。
2.2.1 動態(tài)規(guī)劃求分組節(jié)點算法
提取每個節(jié)點的度,按節(jié)點的度降序排列。采用動態(tài)規(guī)劃的分組策略根據(jù)度的相似性進(jìn)行分組,每個組至少包含k個節(jié)點并將每個組中節(jié)點最大的度作為本組的目標(biāo)度dx。
算法1:動態(tài)規(guī)劃求分組節(jié)點算法
輸入:滿足l-敏感邊匿名化G’的鄰接矩陣A 和各節(jié)點的度矩陣C;匿名化參數(shù)k;
輸出:分界點矩陣TZ;分組后節(jié)點矩陣TZ
2.2.2 貪心算法求分組節(jié)點算法
在滿足l-敏感邊匿名模型的基礎(chǔ)上,根據(jù)節(jié)點度的大小,按節(jié)點度從大到小進(jìn)行排序,采用貪心策略根據(jù)節(jié)點度進(jìn)行分組,使得每個組至少包含k個節(jié)點。
貪心算法首先將遞減度序列的前k 個節(jié)點劃分為一組,然后依次判斷下一個節(jié)點是否合并到前面已經(jīng)形成的分組或者是否作為一個新組的開頭。判斷的依據(jù)為比較以下兩個匿名度的損失
式中:II(i,j)——將i到j(luò) 的所有節(jié)點均變?yōu)閕節(jié)點度的匿名損失度。若KK<=KKX,則第 (w+k+1)個節(jié)點歸到前面的分組;若相反,則作為一組新的開頭,依次類推,直到處理完所有節(jié)點。具體的貪心算法求分組節(jié)點算法如算法2所示。
算法2:貪心算法求分組節(jié)點算法
輸入:滿足l-敏感邊匿名化G’的鄰接矩陣A 和各節(jié)點的度矩陣C;匿名化參數(shù)k;
1.[x,y]=sort(C,’descend’)
2.計算將所有節(jié)點都變?yōu)槟繕?biāo)度時的度差矩陣II
3.FOR(w= (k+1):length(x)-k-1)%貪心算法求分界點
輸出:分界點矩陣TZ;分組后節(jié)點矩陣TZ
2.2.3 (k2,l)-匿名算法
在滿足l-敏感邊匿名模型的基礎(chǔ)上,首先利用動態(tài)規(guī)劃算法求得分組的分界點。然后,通過添加非敏感邊,使每兩個組之間至少有k 個節(jié)點相連。最后,找到每組中節(jié)點度與目標(biāo)度差最大的節(jié)點,添加非敏感邊,直到每個組中的節(jié)點滿足步驟每組選擇的目標(biāo)度,使分組滿足 (k2,l)-匿名模型?;谏鲜鲇懻?,設(shè)計了基于動態(tài)規(guī)劃的度序列匿名算法構(gòu)建 (k2,l)-匿名模型,具體的算法描述如算法3所示。
算法3:(k2,l)-匿名算法
輸入:含敏感邊的社會網(wǎng)絡(luò)G 的鄰接矩陣result;整數(shù)l;
本實驗運行環(huán)境為:Microsoft Windows 7Professional操作系統(tǒng),2GB 內(nèi)存,2.26GHz CPU,采用Matlab編程實現(xiàn)。
本文采用Pajek 軟件 (http://vlado.fmf.uniljsi/pub/networks/pajek/)生成的包含多類型邊的社會網(wǎng)絡(luò)圖作為本文實驗數(shù)據(jù)集。社會網(wǎng)絡(luò)圖中包含節(jié)點數(shù)|V|=380,邊的數(shù)量|E|=630。邊的類型分別為同學(xué)關(guān)系、朋友關(guān)系、家人關(guān)系3種,本文將家人關(guān)系看作節(jié)點間的敏感關(guān)系。本實驗對實現(xiàn)不同匿名模型的運行時間進(jìn)行了對比分析。通過改變社會網(wǎng)絡(luò)圖的匿名化參數(shù),對通過不同匿名算法實現(xiàn)匿名后的社會網(wǎng)絡(luò)度信息損失和其性能進(jìn)行分析對比。
如圖2為k=5,l=2時基于動態(tài)規(guī)劃和貪心算法實現(xiàn)3種不同匿名模型的運行時間比較。從以下兩圖中均可看出,實現(xiàn) (k2,l)-匿名模型比實現(xiàn)其它兩個匿名模型時間較長,因為 (k2,l)-匿名算法在滿足這兩個匿名模型的基礎(chǔ)上,要求每兩組之間至少有k個節(jié)點相連,若隨機的添加非敏感邊,運行時間會減少,卻以大量的度信息損失為代價。所以在添加邊時通過找到度差最大的節(jié)點添加非敏感邊,以提高匿名圖的可用性。隨著數(shù)據(jù)集的增大、節(jié)點數(shù)的增多,運行時間也會越來越長。圖2 (b)中運行時間比圖2 (a)中運行時間較短,在考慮運行時間的同時還要考慮使用不同算法匿名后社會網(wǎng)絡(luò)圖的可用性。以下通過3個方面根據(jù)不同匿名參數(shù)比較兩種算法的可用性,同時對不同匿名模型匿名后的社會網(wǎng)絡(luò)圖可用性進(jìn)行了分析比較。
圖2 不同匿名算法的CPU 運行時間對比
在本文的算法中,通過匿名圖的度信息損失表示匿名成本。圖3、圖4為分別通過動態(tài)規(guī)劃和貪心算法實現(xiàn)不同匿名模型的匿名成本隨k值變化的情況。圖3、圖4 (a)和(b)中分別給出了當(dāng)l為2和3時,各算法的匿名成本隨k值變化的情況。當(dāng)l一定時,隨著k值的逐漸增大,匿名度信息損失呈上升趨勢,而k-匿名的匿名成本要遠(yuǎn)小于其它兩種匿名算法,但是k-匿名算法只能抵御度的攻擊; (k,l)-匿名算法和(k2,l)-匿名算法的匿名度信息損失在k值較小的情況下不相上下,隨著k值的增大,(k2,l)-匿名度信息損失要略微高于 (k,l)-匿名算法的度信息損失。當(dāng)l=3時,3種匿名算法的匿名成本要大于l為2時的情況。
在圖5 中,對通過動態(tài)規(guī)劃和貪心算法實現(xiàn) (k2,l)-匿名模型的匿名度信息損失進(jìn)行了比較,在k 值小于6時,兩種算法的匿名度信息損失上下相當(dāng)。在k值大于6時,動態(tài)規(guī)劃實現(xiàn)匿名模型的度信息損失要小于貪心算法。并且隨著k值的不斷增大,動態(tài)規(guī)劃的優(yōu)勢越來越明顯。隨著k值和l值的不斷增大,社會網(wǎng)絡(luò)圖的匿名效果會越來越好,而社會網(wǎng)絡(luò)圖的可用性會隨之降低。所以,用戶可以根據(jù)自己不同的需求,調(diào)整l和k 的值,達(dá)到滿意的匿名程度。
圖3 動態(tài)規(guī)劃實現(xiàn)不同匿名模型隨k值變化的度信息損失
圖4 貪心算法實現(xiàn)不同匿名模型隨k值變化的度信息損失
圖5 不同算法的 (k2,l)-匿名模型隨k值變化的度信息損失
圖6、圖7 (a)和 (b),為l分別等于2和3時,平均最短路徑差值隨k值變化的情況。當(dāng)l一定時,k-匿名的平均最短路徑差值要小于其它兩個算法的值,隨著k 值不斷增大,3種匿名社會網(wǎng)絡(luò)圖的差值呈緩慢上升趨勢, (k2,l)-匿名圖的平均最短路徑差值要略大于 (k,l)-匿名圖的平均最短路徑差值。而 (k,l)匿名圖和 (k2,l)-匿名圖的差值都要大于k-匿名圖。
圖8中兩種算法實現(xiàn) (k2,l)-匿名模型的平均路徑差值進(jìn)行了對比。在k 小于6的情況下,兩種算法的平均最短路徑差值基本相同,在k 大于6的情況下,隨著k 值的增大,基于貪心算法的平均路徑差值上升趨勢逐漸加快。
圖9、圖10 (a)和 (b),為l分別等于2和3時,聚類系數(shù)差值隨k值的變化情況。在圖9 (a)和圖9 (b)可以看出,k-匿名模型的聚類系數(shù)差值遠(yuǎn)小于其它兩種匿名模型的差值。在l一定的情況下,隨著k值的不斷增大,聚類系數(shù)差值呈上升趨勢,(k2,l)-匿名圖的聚類系數(shù)差值與 (k,l)-匿名圖差值相差較小,隨著k 值不斷增大,網(wǎng)絡(luò)圖的可用性也隨之降低。
圖6 動態(tài)規(guī)劃實現(xiàn)不同匿名模型隨k值變化的平均路徑差值
圖7 貪心算法實現(xiàn)不同匿名模型隨k值變化的平均路徑差值
圖8 不同算法的(k2,l)-匿名模型隨k值變化的平均路徑差值
圖9 動態(tài)規(guī)劃實現(xiàn)不同匿名模型隨k值變化的聚類系數(shù)差值
圖10 貪心算法實現(xiàn)不同匿名模型隨k值變化的聚類系數(shù)差值
圖11中,k值小于6時,貪心算法聚類系數(shù)差值較小。在k 大于6的情況下,基于動態(tài)規(guī)劃算法的聚類系數(shù)差值要較小。在k小于6的情況下,動態(tài)規(guī)劃算法并沒有太大的優(yōu)勢,隨著k 值得增加,動態(tài)規(guī)劃算法的優(yōu)勢越來越明顯,k值大于6的情況下選擇基于動態(tài)規(guī)劃算法實現(xiàn)較好。
從以上實驗結(jié)果中可看出,在k 值和l 值一定的情況下,k-匿名圖的可用性最好, (k,l)-匿名圖比 (k2,l)-匿名圖的可用性略微要好,然而 (k2,l)-匿名圖可以進(jìn)一步的抵御朋友鏈接攻擊。進(jìn)一步對兩種算法的不同系數(shù)差值進(jìn)行分析對比,在k 值小于6的情況下動態(tài)規(guī)劃和貪心算法均可選擇,隨著k 值不斷增大,動態(tài)規(guī)劃算法的優(yōu)勢越來越明顯。
在本文中,貪心算法先將遞減度序列前k 個節(jié)點劃分為一組,均變?yōu)楸窘M的目標(biāo)節(jié)點,然后考慮后續(xù)節(jié)點,只是保證了在當(dāng)前狀態(tài)下的子序列是最優(yōu)的,而動態(tài)規(guī)劃算法是將所有節(jié)點可能出現(xiàn)的所有分組全部進(jìn)行比較,比較完后自底向上選擇分組節(jié)點,在k 值較小的情況下,由于度序列按降序排列,每個組的節(jié)點變?yōu)楸窘M節(jié)點目標(biāo)度時,每組的度損失相對k 值較大的情況下較小。所以,動態(tài)規(guī)劃算法的優(yōu)勢并不明顯,隨著k 值不斷增大,每個分組的度損失也會相差較多,則優(yōu)勢也會越來越明顯。用戶可以根據(jù)自己的不同需求,根據(jù)k值和l值的不同選擇不同的匿名算法,在保證社會網(wǎng)絡(luò)圖可用性較好的前提下,達(dá)到用戶滿意的匿名程度。
圖11 不同算法的(k2,l)-匿名模型隨k值變化的聚類系數(shù)差值
為了保證含敏感關(guān)系的社會網(wǎng)絡(luò)中用戶的隱私不會被同時存在的多種類型的攻擊者獲得。設(shè)計了 (k2,l)-匿名模型,可同時抵御敏感關(guān)系攻擊、節(jié)點度攻擊和朋友連接攻擊。分別通過動態(tài)規(guī)劃度序列匿名算法和貪心算法度序列匿名算法實現(xiàn) (k2,l)-匿名模型,通過比較不同匿名模型的匿名參數(shù),證明 (k2,l)-匿名模型的可行性,并比較不同算法的匿名參數(shù),用戶可根據(jù)不同參數(shù)選擇不同的匿名算法,實現(xiàn) (k2,l)-匿名模型。該方法不僅能夠同時抵御敏感關(guān)系攻擊、度攻擊和朋友連接攻擊,而且能夠合理地控制信息損失度。下一步的研究方向:社會網(wǎng)絡(luò)是不斷發(fā)展和變化的,可以考慮社會網(wǎng)絡(luò)的動態(tài)性;隨著網(wǎng)絡(luò)技術(shù)的發(fā)展,可以考慮采用并行算法對社會網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析處理,提高數(shù)據(jù)匿名化的有效性。
[1]Bhagat S,Cormode G,Krishnamurthy B,et al.Class-based graph anonymization for social network data[C]//Proc of the 35th Int’l Conf on Very Large Databases,2009:766-777.
[2]LIU Xiangyu,WANG Bin.Survey on privacy preserving tech-niques for publishing social network data [J].Journal of Software,2014,25 (3):142-156 (in Chinese).[劉向宇,王斌.社會網(wǎng)絡(luò)數(shù)據(jù)發(fā)布隱私保護(hù)技術(shù)綜述 [J].軟件學(xué)報,2014,25 (3):142-156.]
[3]Gao J,Xu JY,Jin R,et al.Neighborhood-privacy protected shortest distance computing in cloud [C]//Proc of the ACM SIGMOD Int’l Conf on Management of Data,2011:409-420.
[4]YANG Jun,LIU Xiangyu,YANG Xiaochun,et al.Automorphism based k-secure for privacy preserving in social network [C]//The 29th China Database Academic Conference,2012:264-271 (in Chinese). [楊俊,劉向宇,楊曉春,等.基于圖自同構(gòu)的k-Secure社會網(wǎng)絡(luò)隱私保護(hù)方法 [C]//第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集,2012:264-271.]
[5]Zhelea E,Getdoor L.Preserving the privacy of sensitive relationships in graph data [C]//Proceedings of the 1st ACM SIGKDD Workshop on Privacy,Security,and Trust in KDD,2007.
[6]LAN Lihui,SUN Yinghui.Privacy preservation of sensitive edges in social networks publication [J].Journal of Jilin University,2011,29 (4):324-331 (in Chinese). [蘭麗輝,孫英慧.社會網(wǎng)絡(luò)發(fā)布中敏感邊的隱私保護(hù) [J].吉林大學(xué)學(xué)報,2011,29 (4):324-331.]
[7]Li J,Han J M,Luo F W,et al.K-Sensitive edge anonymity model for sensitive relationship preservation on publishing social network [C]//The 3rd International Conference on Information Technology and Computer Science,2011:146-149.
[8]Zheleva E,Getoor L.Preserving the privacy of sensitive relationships in graph data [C]//Proc of the 1st ACM SIGKDD Workshop on Privacy,Security,and Trust in KDD,2007:153-171.
[9]Campan A,Truta T M,Cooper N.P-sensitive K-anonymity with generalization constraints[J].Transactions on Data Privacy Journal,2010,3 (2):65-89.
[10]NAN Lili,WU Tao.Research on information mixing-based protection mechanism in online social networks[J].Computer Engineering and Design,2011,32 (10):3278-3283 (in Chinese).[南麗麗,吳濤.基于信息混淆的社會網(wǎng)絡(luò)隱私保護(hù) 機 制 [J]. 計 算 機 工 程 與 設(shè) 計,2011,32 (10):3278-3283.]
[11]WANG Xiaohao,GENG Hui.Privacy protection disturbance method of society network based on spectrum constraint and sensitive area division [J].Journal of Computer Applications,2013,33 (6):1608-1611 (in Chinese). [王小號,耿惠.基于譜約束和敏感區(qū)劃分的社會網(wǎng)絡(luò)隱私保護(hù)擾動方法 [J].計算機應(yīng)用,2013,33 (6):1608-1611.]
[12]ZHANG Jianpei,XIE Jing.A t-closeness privacy model based on sensitive attribute values semantics bucketization [J].Journal of Computer Research and Development,2014,51(1):126-137 (in Chinese).[張健沛,謝靜.基于敏感屬性值語義桶分組的t-closeness隱私模型 [J].計算機研究與發(fā)展,2014,51 (1):126-137.]
[13]WU Hongwei,ZHANG Renwei.(k,l)-anonymity for social networks publication against composite attacks [J].Journal of Harbin University of Science and Technology,2013,18(3):47-53 (in Chinese).[吳宏偉,張仁偉.抗復(fù)合攻擊的社會網(wǎng)絡(luò) (k,l)匿名方法 [J].哈爾濱理工大學(xué)學(xué)報,2013,18 (3):47-53.]