基于節(jié)點蓄意攻擊的因特網(wǎng)魯棒性研究

楊 泉，丁 琳

(南華大學(xué)計算機學(xué)院，湖南 衡陽 421001)

0 引 言

近年來，復(fù)雜網(wǎng)絡(luò)的魯棒性問題引起了許多學(xué)者的極大關(guān)注，特別是，許多研究人員致力于級聯(lián)故障的研究，這已經(jīng)成為網(wǎng)絡(luò)安全中最重要的主題之一。級聯(lián)故障是一種連續(xù)故障，通常由一個或幾個節(jié)點的隨機故障或蓄意攻擊觸發(fā)，并最終導(dǎo)致整個網(wǎng)絡(luò)嚴(yán)重受損。在現(xiàn)實生活中，級聯(lián)故障多發(fā)生于基礎(chǔ)設(shè)施網(wǎng)絡(luò)，并經(jīng)常引發(fā)各種災(zāi)難性事件，造成嚴(yán)重的經(jīng)濟損失。例如，一些國家的大規(guī)模停電[1-3]、一些大城市頻繁的交通癱瘓和互聯(lián)網(wǎng)崩潰[4-5]等。因此，對于現(xiàn)實網(wǎng)絡(luò)抵制級聯(lián)故障的魯棒性研究變得越來越重要。

為了減少或預(yù)防級聯(lián)故障的發(fā)生，許多研究者從不同的角度對級聯(lián)現(xiàn)象進行了研究，得出了許多有價值的結(jié)論，主要集中在級聯(lián)故障的各種建模方法[6-9]、級聯(lián)機制和控制措施[10-12]、保護和攻擊策略[13-15]、相依網(wǎng)絡(luò)的級聯(lián)建模[16-18]等。在以往的級聯(lián)故障研究中，一個關(guān)鍵的問題是如何給節(jié)點或邊分配初始負(fù)載。在早期的研究中，節(jié)點或邊的初始負(fù)載通常定義為該節(jié)點或邊的介數(shù)。應(yīng)用介數(shù)，Motter等人[19]的開創(chuàng)性工作討論了復(fù)雜網(wǎng)絡(luò)上基于級聯(lián)的攻擊，并驗證了對單個重要節(jié)點(高負(fù)載節(jié)點之一)的攻擊可以觸發(fā)大規(guī)模級聯(lián)故障。此后，為了更好地控制和防御復(fù)雜網(wǎng)絡(luò)中的級聯(lián)故障，基于介數(shù)方法，Motter[10]引入并研究了一種無成本的防御策略，該策略在初始攻擊或故障之后，基于有選擇地進一步移除節(jié)點和邊，并發(fā)現(xiàn)有意移除網(wǎng)絡(luò)元素可以大幅度減小級聯(lián)的大小。Crucitti等人[20]提出了一種基于網(wǎng)絡(luò)上流的動態(tài)重新分配的簡單級聯(lián)故障模型，并且表明單個節(jié)點(高負(fù)載節(jié)點之一)的故障足以使整個系統(tǒng)崩潰。雖然在許多實際情況下，通過介數(shù)定義節(jié)點或邊的初始負(fù)載能夠很好地反映物理量的流動，但對于某些大規(guī)模的現(xiàn)實網(wǎng)絡(luò)而言，這可能是不切實際的，因為介數(shù)考慮了網(wǎng)絡(luò)的全局拓?fù)湫畔?，而大?guī)模網(wǎng)絡(luò)的全局拓?fù)湫畔⑹呛茈y獲取的。因此，考慮到局部度的簡單性以及網(wǎng)絡(luò)權(quán)重，基于由邊連接的2個節(jié)點的度的信息，Wang和Chen[6]提出了一種新的定義邊的初始負(fù)載的方法，并提出了一個加權(quán)流局域重分配的級聯(lián)模型。通過分析加權(quán)網(wǎng)絡(luò)上的級聯(lián)現(xiàn)象，他們發(fā)現(xiàn)當(dāng)模型中的權(quán)重參數(shù)為1時，網(wǎng)絡(luò)達到最強魯棒性。在他們的工作的推動下，許多研究者從度的角度定義節(jié)點或邊的初始負(fù)載，構(gòu)造了不同的級聯(lián)模型并應(yīng)用到現(xiàn)實網(wǎng)絡(luò)中。如，Wang等人[21]應(yīng)用加權(quán)流重分配的級聯(lián)模型研究了美國西部電網(wǎng)在2種攻擊下對級聯(lián)故障的響應(yīng)，發(fā)現(xiàn)模型參數(shù)對網(wǎng)絡(luò)的魯棒性有著不同影響；Luo等人[22]應(yīng)用局域負(fù)載重分配的級聯(lián)模型分析了復(fù)雜電網(wǎng)上的級聯(lián)故障，研究表明，與傳統(tǒng)網(wǎng)絡(luò)上的研究結(jié)果相比，電網(wǎng)在模型參數(shù)為1時并沒有達到最強魯棒性，而是模型參數(shù)越大，電網(wǎng)的魯棒性越強。

然而，現(xiàn)有研究大多是關(guān)注電網(wǎng)或通用理論復(fù)雜網(wǎng)絡(luò)的級聯(lián)故障動態(tài)行為及其魯棒性，而對通信網(wǎng)絡(luò)的動態(tài)魯棒性研究仍然相對較少。因此，本文考慮實際的因特網(wǎng)，使用節(jié)點度的函數(shù)形式表示節(jié)點初始負(fù)載，并基于故障節(jié)點的負(fù)載局域重分配原則，構(gòu)建一個具有可調(diào)參數(shù)的級聯(lián)故障模型，探討因特網(wǎng)在蓄意攻擊下的魯棒性，并研究網(wǎng)絡(luò)參數(shù)對因特網(wǎng)魯棒性的影響。為更好地理解不同節(jié)點在級聯(lián)故障中的作用，本文采用2種不同的攻擊策略，即以降序方式來攻擊網(wǎng)絡(luò)中負(fù)載最大的節(jié)點和以升序方式來攻擊網(wǎng)絡(luò)中負(fù)載最小的節(jié)點。通過數(shù)值模擬，發(fā)現(xiàn)級聯(lián)故障模型中的可調(diào)負(fù)載參數(shù)對受到攻擊后的網(wǎng)絡(luò)魯棒性有著重要影響。

1 因特網(wǎng)級聯(lián)故障模型

本文將因特網(wǎng)拓?fù)涑橄蟪梢粋€具有N個節(jié)點和E條邊的無權(quán)無向的簡單圖，記為G=(V,M)。其中，V代表所有節(jié)點(頂點)的集合，M則代表所有邊(鏈路)的集合。并定義一個N×N的鄰接矩陣[aij]來表示節(jié)點之間關(guān)系，如果aij=1，表示節(jié)點i與節(jié)點j之間有邊直接相連；如果aij=0，則沒有直接相連的邊。

Ci=(1+α)Li(0)

(1)

Ci=αLi(0)+β

(2)

其中，α≥0和β≥0為控制節(jié)點容量的可調(diào)參數(shù)。

當(dāng)因特網(wǎng)中的節(jié)點受到攻擊時，該節(jié)點會發(fā)生故障并立即被網(wǎng)絡(luò)刪除，被攻擊節(jié)點的負(fù)載將被重新分配給其他節(jié)點。而在故障節(jié)點負(fù)載的重新分配過程中，采用不同的分配方式將對網(wǎng)絡(luò)的級聯(lián)故障過程有著不同程度的影響。

在以往復(fù)雜網(wǎng)絡(luò)的級聯(lián)故障研究中，節(jié)點負(fù)載的重新分配有2種，一種是將故障節(jié)點負(fù)載分配給網(wǎng)絡(luò)中其他節(jié)點的全局負(fù)載重分配策略；另一種是將故障節(jié)點負(fù)載分配給其相鄰節(jié)點的局域負(fù)載重分配策略。

考慮到負(fù)載的重新分配是一個瞬時行為，故障節(jié)點的負(fù)載必須通過其相鄰節(jié)點，因而故障節(jié)點的鄰居節(jié)點將受到最嚴(yán)重的影響。因此，本文采用局域負(fù)載重分配策略，它分為2種情況：

1)將故障節(jié)點的負(fù)載按其鄰居節(jié)點的初始負(fù)載比例分配到該節(jié)點的所有鄰居節(jié)點。如果節(jié)點i發(fā)生故障了，則它的鄰居節(jié)點j接收的負(fù)載比例為：

(3)

其中，Γi為節(jié)點i的鄰居節(jié)點集合。

2)將故障節(jié)點的負(fù)載根據(jù)其鄰居節(jié)點的剩余容量比例來分配給該節(jié)點的所有鄰居節(jié)點。如果節(jié)點i發(fā)生故障，其鄰居節(jié)點j所接收到的負(fù)載比重為：

(4)

其中，Lj表示節(jié)點j的負(fù)載。

由于級聯(lián)故障的傳播過程非常快，依據(jù)公式(4)的分配原則，需要不斷與故障節(jié)點的鄰居節(jié)點交換當(dāng)前的剩余容量信息，這可能會加劇網(wǎng)絡(luò)的崩潰。因此，本文簡化負(fù)載分配方式，采用公式(3)來分配故障節(jié)點的負(fù)載。于是，故障節(jié)點i的鄰居節(jié)點j所接收到的負(fù)載為：

(5)

如果節(jié)點j的總負(fù)載超過其容量，即Lj+ΔLji>Cj，則節(jié)點j會發(fā)生故障，其負(fù)載會根據(jù)公式(5)重新分配給它的鄰居節(jié)點，這可能會觸發(fā)更多的節(jié)點故障。當(dāng)網(wǎng)絡(luò)中所有節(jié)點的負(fù)載都不超過其容量時，級聯(lián)故障才會終止。

在級聯(lián)故障結(jié)束后，為了量化級聯(lián)故障產(chǎn)生的破壞，本文采用歸一化雪崩規(guī)模來表示網(wǎng)絡(luò)的魯棒性，即：

(6)

其中，Si表示雪崩規(guī)模，定義為由移除節(jié)點i所導(dǎo)致的故障節(jié)點數(shù)量，A和NA分別表示攻擊節(jié)點的集合與數(shù)量。

2 攻擊策略

在本文的級聯(lián)模型中，對于一個給定的θ值，當(dāng)α足夠小，即每個節(jié)點的容量有限時，任意節(jié)點的故障都會導(dǎo)致整個網(wǎng)絡(luò)的崩潰；而當(dāng)α足夠大，即每個節(jié)點都具有較大的額外負(fù)載處理能力時，網(wǎng)絡(luò)不會發(fā)生級聯(lián)故障且保持正常而有效地運行。因此，網(wǎng)絡(luò)存在一個從崩潰狀態(tài)逐漸轉(zhuǎn)為正常狀態(tài)的相變，即關(guān)鍵閾值αc。當(dāng)α≥αc時，每個節(jié)點都具有足夠大的容量來處理額外負(fù)載，網(wǎng)絡(luò)不會發(fā)生級聯(lián)故障并且正常運行；而當(dāng)α<αc時，S迅速從0增長到1，并導(dǎo)致部分或整個網(wǎng)絡(luò)的崩潰。顯然，αc越小，網(wǎng)絡(luò)抵制級聯(lián)故障的魯棒性就越強。

本文的目的是比較不同攻擊策略對網(wǎng)絡(luò)抵制級聯(lián)故障魯棒性的影響。因此，在上述的級聯(lián)模型中采用了2種簡單的攻擊策略:

1)對具有最低負(fù)載的節(jié)點的攻擊(LL):按照網(wǎng)絡(luò)中負(fù)載的升序來選擇節(jié)點，然后從具有最低負(fù)載的節(jié)點開始逐一刪除(如果某些節(jié)點具有相同的最低負(fù)載，將會按順序刪除)。

2)對具有最高負(fù)載的節(jié)點的攻擊(HL):與LL策略相反，這個策略是按照網(wǎng)絡(luò)中負(fù)載的降序來選擇節(jié)點，然后從具有最高負(fù)載的節(jié)點開始逐一刪除(如果某些節(jié)點具有相同的最高負(fù)載，將會按順序刪除)。

3 數(shù)值仿真

在本文的實驗中，考慮了一個具有N=3015和E=5539的AS級因特網(wǎng)(數(shù)據(jù)來源于http://snap.stanford.edu/)。因為在級聯(lián)故障建模過程中考慮了2種不同的負(fù)載-容量模型，因此，在公式(1)下討論了2種攻擊策略對網(wǎng)絡(luò)魯棒性的影響，在公式(2)下研究了初始負(fù)載參數(shù)和容量參數(shù)對網(wǎng)絡(luò)魯棒性的影響。

3.1 2種攻擊策略對網(wǎng)絡(luò)魯棒性的影響

為了對2種攻擊進行對比，本文關(guān)注于臨界閾值αc與級聯(lián)模型參數(shù)之間的關(guān)系。而對于每種攻擊策略，將分別選擇50個節(jié)點作為攻擊目標(biāo)，并且每次的模擬結(jié)果都是對十多個因特網(wǎng)數(shù)據(jù)的結(jié)果取平均所得。由于級聯(lián)模型中參數(shù)θ的作用，本實驗考慮了2種攻擊分別在θ≤0.5和θ>0.5這2種情況下對網(wǎng)絡(luò)魯棒性的影響。

圖1顯示了因特網(wǎng)在θ≤0.5時2種攻擊策略下的歸一化雪崩規(guī)模S與容限參數(shù)α之間的變化關(guān)系?？梢钥吹剑?dāng)θ≤0.5時，與HL策略相比，LL策略所引發(fā)的級聯(lián)范圍更廣，對因特網(wǎng)造成的損害更嚴(yán)重。這種現(xiàn)象可以理解，當(dāng)θ≤0.5時，網(wǎng)絡(luò)中每個節(jié)點的初始負(fù)載都比較小，而且度越小的節(jié)點，其初始負(fù)載越小。由于故障節(jié)點的負(fù)載被重新分配給它的鄰居節(jié)點，低負(fù)載節(jié)點因為其自身度很小，所以它的鄰居節(jié)點就少，這意味著低負(fù)載節(jié)點被分配到更多的額外負(fù)載，因而需要更大的容量來處理額外負(fù)載，否則就會因為過載而發(fā)生故障。而高負(fù)載節(jié)點則相反，高負(fù)載節(jié)點因為其自身度很大，所以它的鄰居節(jié)點很多，這意味著高負(fù)載節(jié)點會被分配到的額外負(fù)載就很小，因而只需要很小的容量就能處理掉額外負(fù)載而不會發(fā)生故障。但前文已表明，節(jié)點的容量是由容限參數(shù)決定的，容量越大，表示αc越大，則網(wǎng)絡(luò)的魯棒性越弱。因此，在這個情況下，LL策略能更有效地破壞因特網(wǎng)。

圖1 θ≤0.5下的2種攻擊策略比較

另外，圖1還顯示了隨著θ的增大，2種攻擊策略的影響差異就越小。可以看到，當(dāng)參數(shù)θ的值逐漸從0.1增加至0.5時，LL策略的αc值慢慢變小，即網(wǎng)絡(luò)的魯棒性在逐漸增強，這表明在LL策略下，網(wǎng)絡(luò)的魯棒性與參數(shù)θ成正相關(guān)關(guān)系；而HL策略的αc值在慢慢增加，即網(wǎng)絡(luò)的魯棒性在逐漸減弱，這說明在HL策略下，網(wǎng)絡(luò)的魯棒性與參數(shù)θ成負(fù)相關(guān)關(guān)系。實驗結(jié)果具有重要的意義，它可以根據(jù)現(xiàn)實網(wǎng)絡(luò)中的不同情況，為保護有效選擇的節(jié)點提供指導(dǎo)，以避免級聯(lián)故障引發(fā)的災(zāi)難。

圖2顯示了因特網(wǎng)在θ>0.5時2種攻擊策略下的歸一化雪崩規(guī)模S與容限參數(shù)α之間的變化關(guān)系?？梢钥吹?，圖2中存在一個特殊的點，即θ=0.7。當(dāng)θ=0.7時，2種攻擊策略下的αc幾乎相同。而當(dāng)θ>0.7時，HL策略能更有效地破壞因特網(wǎng)。這與之前的美國西部電網(wǎng)在2種不同攻擊策略下的研究結(jié)果相同，即攻擊最高負(fù)載節(jié)點和攻擊最低負(fù)載節(jié)點[21]。

圖2 θ>0.5下的2種攻擊策略比較

圖3 2種攻擊策略下的關(guān)鍵閾值αc與參數(shù)θ之間關(guān)系

此外，本文還進一步地研究了在2種攻擊策略下的關(guān)鍵閾值αc與參數(shù)θ之間關(guān)系，如圖3所示?？梢灾庇^地看到，在θ=0.7處呈現(xiàn)出2種攻擊策略的相互轉(zhuǎn)換。這與之前的很多關(guān)于2種不同攻擊策略下網(wǎng)絡(luò)的魯棒性研究結(jié)果一致[21,24-25]，即當(dāng)初始負(fù)載參數(shù)達到某一閾值時，2種攻擊策略會對網(wǎng)絡(luò)的魯棒性產(chǎn)生相同的影響。然而不同的是，文獻[24-25]的閾值為0.5，小于本文的0.7。這是因為文獻[24-25]中使用的是不相關(guān)的無標(biāo)度網(wǎng)絡(luò)，并且網(wǎng)絡(luò)的規(guī)模、平均度與實際的因特網(wǎng)也不相同，因而研究結(jié)果存在差異性。

3.2 參數(shù)對網(wǎng)絡(luò)魯棒性的影響

由于攻擊策略對網(wǎng)絡(luò)魯棒性的影響，本文考慮了初始負(fù)載參數(shù)與容量參數(shù)在LL和HL下對網(wǎng)絡(luò)魯棒性的影響。設(shè)置β=1，這與以往研究中的研究方法是一致的[23]。與上文相同，對于每種攻擊策略，分別選擇50個節(jié)點作為攻擊目標(biāo)，并且每次的模擬結(jié)果都是對十多個因特網(wǎng)數(shù)據(jù)的結(jié)果取平均所得。

圖4顯示了因特網(wǎng)在攻擊最低負(fù)載節(jié)點下，容限參數(shù)α和初始負(fù)載參數(shù)θ與歸一化雪崩規(guī)模S之間的關(guān)系。從前文可知，0≤S≤1，并且S越小，表示網(wǎng)絡(luò)的魯棒性越強。從圖4可以看出，α值越小，網(wǎng)絡(luò)的魯棒性越弱，當(dāng)α=0時，無論節(jié)點負(fù)載如何變化，網(wǎng)絡(luò)始終處于全崩潰狀態(tài)。這是由于α值越小，節(jié)點所能處理的負(fù)載就越小，網(wǎng)絡(luò)的級聯(lián)故障就越嚴(yán)重。但隨著α值的增加，S值不斷減小，并在α=1時(注：這里的α=1是S達到最小時的一個臨界值)，網(wǎng)絡(luò)達到抵制級聯(lián)故障的最強魯棒性。

圖4 LL攻擊策略下,α與θ、S之間關(guān)系

另外，圖4還顯示了隨著θ的增加，S也在不斷增加?？梢钥吹?，當(dāng)α值為0.1和0.6時，它的S從θ=0時的0.04、0逐漸增加至θ=1時的0.73、0.42，這表示在給定的α下，網(wǎng)絡(luò)的魯棒性隨著θ的增加而不斷減弱，說明節(jié)點的初始負(fù)載參數(shù)與網(wǎng)絡(luò)的魯棒性成負(fù)相關(guān)關(guān)系。

圖5顯示了因特網(wǎng)在攻擊最高負(fù)載節(jié)點下，容限參數(shù)α和初始負(fù)載參數(shù)θ與歸一化雪崩規(guī)模S之間的關(guān)系。從圖5可以看出，隨著α值的增加，網(wǎng)絡(luò)的魯棒性不斷增強，并且節(jié)點的初始負(fù)載參數(shù)與網(wǎng)絡(luò)的魯棒性成負(fù)相關(guān)關(guān)系。這驗證了圖4的結(jié)論，也說明在LL或者HL策略下，減小節(jié)點的初始負(fù)載，同時增大節(jié)點的容量，能有效控制網(wǎng)絡(luò)級聯(lián)故障的發(fā)生。

圖5 HL攻擊策略下，α與θ、S之間關(guān)系

4 結(jié)束語