[發(fā)明專利]一種基于隨機鄰居節(jié)點的無標(biāo)度網(wǎng)絡(luò)攻擊方法

有效

• 申請?zhí)枺?/td>: 201310383300.8
• 申請日: 2013-08-28
• 公開（公告）號: CN103457947A
• 公開（公告）日: 2013-12-18
• 發(fā)明（設(shè)計）人: 楊旭華;趙久強;彭朋;汪向飛
• 申請（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號: H04L29/06
• 分類號: H04L29/06
• 代理公司: 杭州天正專利事務(wù)所有限公司 33201
• 代理人: 王兵;王堅敏

技術(shù)領(lǐng)域

本發(fā)明屬于網(wǎng)絡(luò)科學(xué)技術(shù)領(lǐng)域，特別是指一種基于隨機鄰居節(jié)點的無標(biāo)度網(wǎng)絡(luò)攻擊方法。

背景技術(shù)

復(fù)雜網(wǎng)絡(luò)的研究具有重要的現(xiàn)實意義，社會中的很多實際系統(tǒng)都可以被抽象成復(fù)雜網(wǎng)絡(luò)進(jìn)行研究。特別的，網(wǎng)絡(luò)的魯棒性研究得到了極大的關(guān)注。魯棒性表征了網(wǎng)絡(luò)是否健壯和抗干擾。當(dāng)評價一個網(wǎng)絡(luò)具有較好的魯棒性時，該網(wǎng)絡(luò)抗干擾的能力也就越好，對于外界的干擾也就越不敏感。對于復(fù)雜網(wǎng)絡(luò)的魯棒性研究，可以通過網(wǎng)絡(luò)受到攻擊下的行為來表現(xiàn)。主要可以表現(xiàn)為一些參數(shù)的變化，如網(wǎng)絡(luò)平均最短路徑、網(wǎng)絡(luò)連通性等。從網(wǎng)絡(luò)參數(shù)的變化，我們可以很清晰的評判網(wǎng)絡(luò)抵抗攻擊的能力，從而可以進(jìn)行有針對性的網(wǎng)絡(luò)修復(fù)，提出科學(xué)的網(wǎng)絡(luò)預(yù)防策略。

隨著復(fù)雜網(wǎng)絡(luò)理論研究得到不斷的深入，網(wǎng)絡(luò)魯棒性的研究也越來越獲得廣泛的進(jìn)行。從最開始Albert等人針對隨機網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)進(jìn)行隨機故障和蓄意攻擊兩種策略下的網(wǎng)絡(luò)魯棒性研究；An?Zeng等人在惡意攻擊下提出了結(jié)合混合貪婪算法的思想，綜合考慮節(jié)點移除和連邊斷裂的多重攻擊時提高網(wǎng)絡(luò)魯棒性的策略；Cun-Lai?Pu等人針對網(wǎng)絡(luò)可控性的魯棒性分析指出基于度的攻擊策略要比隨意攻擊能更有效的對網(wǎng)絡(luò)可控性起作用。

對于給定的網(wǎng)絡(luò)，每一個時間步進(jìn)行一次網(wǎng)絡(luò)攻擊。每次從該網(wǎng)絡(luò)中移除受攻擊的節(jié)點，同時也移除與該節(jié)點有連接的連邊。網(wǎng)絡(luò)逐步受到攻擊后中斷了其中的一些路徑，某兩個節(jié)點之間的距離也就不斷增大，直到所有的路徑都被中斷，兩個節(jié)點不再連通。

特別的，在無標(biāo)度網(wǎng)絡(luò)中，具有嚴(yán)重的異質(zhì)性，其各節(jié)點之間的連接狀況（度數(shù)）具有嚴(yán)重的不均勻分布性：網(wǎng)絡(luò)中少數(shù)稱之為Hub點的節(jié)點擁有極其多的連接，而大多數(shù)節(jié)點只有很少量的連接。正是由于這種特性，隨機攻擊很難破壞到那些少數(shù)起主導(dǎo)作用的Hub節(jié)點，攻擊效果不明顯；而蓄意攻擊那些Hub節(jié)點則會對網(wǎng)絡(luò)造成毀滅性的破壞，但種蓄意攻擊的前提是需要知道網(wǎng)絡(luò)的全局信息，才能找到那些度數(shù)特別大的節(jié)點進(jìn)行攻擊，這在很多情況下是不可能或者是非常困難的。

發(fā)明內(nèi)容

為了克服現(xiàn)有技術(shù)攻擊效果不好、事先需要知道網(wǎng)絡(luò)的全局信息的缺點，本發(fā)明提出一種基于隨機鄰居節(jié)點的無標(biāo)度網(wǎng)絡(luò)攻擊方法，在不知道網(wǎng)絡(luò)全局信息的基礎(chǔ)上就能得到一個相對有效的網(wǎng)絡(luò)攻擊方法。

本發(fā)明在每一次進(jìn)行網(wǎng)絡(luò)攻擊的時候，先隨機選取網(wǎng)絡(luò)中一個節(jié)點，再隨機選取該節(jié)點的一個鄰居節(jié)點，最后移除該鄰居節(jié)點及其所有連邊。這種攻擊方法可以有效攻擊實際中的任意無標(biāo)度網(wǎng)絡(luò)，在現(xiàn)實中，往往很難甚至不可能知道某個實際網(wǎng)絡(luò)的全局信息，很難找到網(wǎng)絡(luò)中節(jié)點度數(shù)十分大的節(jié)點，對網(wǎng)絡(luò)進(jìn)行蓄意攻擊是很難或者不可能實現(xiàn)的。這種基于隨機鄰居節(jié)點的無標(biāo)度網(wǎng)絡(luò)攻擊方法，只需要知道網(wǎng)絡(luò)的局部信息，就可以得到一個攻擊效果高于隨機選點攻擊的全新的網(wǎng)絡(luò)攻擊方法。

本發(fā)明解決其技術(shù)問題所采用的技術(shù)具體步驟是：

這種基于隨機鄰居節(jié)點的無標(biāo)度網(wǎng)絡(luò)攻擊方法，包括以下步驟：

步驟一：針對待攻擊的無標(biāo)度網(wǎng)絡(luò)，建立該網(wǎng)絡(luò)的鄰接矩陣表示，矩陣中的元素為0或者1,0表示行和列所代表的節(jié)點不相連，1表示行和列所代表的節(jié)點相連，該網(wǎng)絡(luò)的節(jié)點數(shù)為N，最大連通子圖的相對大小為S，設(shè)定攻擊目標(biāo)為網(wǎng)絡(luò)最大連通子圖的相對大小為S_min。

步驟二：隨機選取該網(wǎng)絡(luò)的一個節(jié)點，接著選定該點的任意一個鄰居節(jié)點為待攻擊節(jié)點，攻擊該節(jié)點，即從該網(wǎng)絡(luò)中移除受攻擊的節(jié)點，同時移除與該節(jié)點有連接的連邊。

步驟三：移除節(jié)點數(shù)占原始網(wǎng)絡(luò)總節(jié)點數(shù)的比例為R，S會隨著R的升高而變小，即網(wǎng)絡(luò)受到攻擊后，網(wǎng)絡(luò)的連通性變得越來越差，如果S≤S_min，則停止網(wǎng)絡(luò)攻擊；如果S>S_min，則重復(fù)步驟二。由于無標(biāo)度網(wǎng)絡(luò)為典型的異質(zhì)網(wǎng)絡(luò)，網(wǎng)絡(luò)的度分布具有顯著的非均勻性，網(wǎng)絡(luò)中的任意節(jié)點鄰居的平均度遠(yuǎn)大于該網(wǎng)絡(luò)的平均度，因此該方法比隨機選點的攻擊方法具有更高的攻擊效率，即會以更低的R，實現(xiàn)相同的網(wǎng)絡(luò)攻擊目標(biāo)S_min。

進(jìn)一步，所述步驟一中，S為網(wǎng)絡(luò)最大連通子圖中所包含的節(jié)點數(shù)和節(jié)點總數(shù)N的比值。

再進(jìn)一步，所述步驟三中，無標(biāo)度網(wǎng)絡(luò)的度分布為P(k)～k^-r，其中k為網(wǎng)絡(luò)中節(jié)點的度，γ為一個正的常數(shù)，因此無標(biāo)度網(wǎng)絡(luò)的度分布具有顯著的非均勻性。