復雜網絡攻擊與修復策略

崔強 譚敏生 王靜

南華大學計算機科學與技術學院 湖南 421001

0 前言

隨著復雜網絡研究的興起，作為復雜網絡最重要的課題之一，對復雜網絡攻擊與修復策略的研究的重大理論意義和應用價值日益凸顯出來，人們開始關注：這些復雜的網絡到底有多可靠？在網絡遭受攻擊后如何高效快速的修復網絡？例如2008年1月25日，在持續了十多天的冰雪天氣后，湖南、浙江、安徽、江蘇、福建、湖北、四川、重慶、貴州、云南、廣西、廣東等電網的電力設施均遭到不同程度破壞，局部地區由于電力設施毀壞嚴重使電力供應中斷達數天之久。電網和交通的癱瘓使一些縣城、鄉鎮成了孤島，交通癱瘓、電力中斷、供水停止、燃料告急、食物緊張。那么當出現此種情況后如何快速修復我們的生命線網絡就變得尤其重要。

1 攻擊策略

復雜網絡通常面臨兩種攻擊：隨機性攻擊(Random attack)和選擇性攻擊(Selective attack)。所謂隨機性攻擊就是網絡節點(邊)以某種概率被隨機的破壞；而選擇性攻擊是網絡節點(邊)按一定的策略被破壞，一般按照節點的度值大小依次去除節點。一般來說，網絡自身原因引起的故障屬于隨機性攻擊，而蓄意的破壞則屬于選擇性攻擊。例如，敵人在選擇攻擊目標時，總是先選擇重要的軍事目標，而不是隨機破壞。所以研究攻擊策略的效率，時效性就變得很有意義。

1.1 基于不完全網絡拓撲信息的有目的攻擊

有關攻擊策略的仿真研究中，比較全面的要數Holme等的研究工作。他們將攻擊策略分為節點攻擊與邊攻擊兩種方式。每種攻擊又包括四種不同的策略：①ID移除策略。對初始網絡按節點或邊的度大小順序來移除節點或邊；②IB移除策略。對初始網絡按照節點或邊的介數大小順序來移除節點或邊；③RD移除策略。每次移除的節點或邊是當前網絡中節點或邊的度最大的節點；④RB移除策略。每次移除的節點或邊是當前網絡中節點或邊介數最大的節點。ER模型對節點的基于度的攻擊比基于介數的攻擊效果好，使用重新計算的信息比基于原始信息的危害性更強 ；而對邊的攻擊RB遠比其他策略更具破壞性。無尺度網絡對節點移除比ER模型更敏感，在攻擊初期四種策略的差異性不明顯，隨著移除的繼續進行，攻擊對網絡的破壞程度按以下順序排列：RB>RD>ID>IB；而且對邊的攻擊情況同節點攻擊相似。作者還對Internet等真實網絡作了數字分析，驗證了Albert等的結論。

1.2 基于局部網絡拓撲信息的分布式攻擊

分布式攻擊能逐步在網絡上傳播，攻擊已經“淪陷”節點的鄰節點，且下一個攻擊目標的選擇僅僅需要節點的局部信息——被攻擊節點的鄰節點的度值信息。如果一個節點被攻擊，本文稱之為“淪陷”節點，否則稱之為“存活”節點。

本文基于Internet真實子網和BA網絡模型(網絡模型同上)，對以下3種分布式攻擊策略的攻擊效率進行仿真測試：

（1）貪婪順序攻擊：選擇與上一步被攻擊節點相連的最大度值“存活”節點作為攻擊目標。如果沒有這樣的節點存在，則隨機選擇一個“存活”節點作為攻擊目標。

（2）協同攻擊：搜索“淪陷”節點的“存活”鄰節點，在它們中選擇一個最大度值的“存活”節點作為攻擊目標。如果沒有這樣的節點存在，則隨機選擇一個“存活”節點繼續展開攻擊。

（3）限下界平行攻擊：不同于每步只攻擊一個與“淪陷”節點相鄰的最大度值節點，而是攻擊所有滿足以下兩個條件的“存活”節點：與“淪陷”節點鄰接；度值在預先設定的界值之上。

圖1 貪婪順序攻擊和協同攻擊的攻擊效率

圖1比較了貪婪順序攻擊和協同攻擊各自的攻擊效率。結果表明，貪婪順序攻擊并不能高效地擊垮整個網絡，相反，僅利用局部信息的協同攻擊卻能得到與有目的攻擊差不多的崩潰閾值。這個觀察結果可以這樣理解，在貪婪順序攻擊中，因為沒有中心節點與剛剛淪陷的節點相鄰，大量攻擊步驟都不得不攻擊許多小度值的節點。在協同攻擊中，每一步能夠在比較多的節點中選擇下一步的攻擊目標，因此，很少會需要攻擊小度值的節點。協同攻擊最主要的缺點就是，為了找到下一個攻擊目標，在攻擊前要收集所有“淪陷”節點的度值信息。

圖2 平行攻擊的攻擊效率

為了減少攻擊前節點間非常復雜的協作和信息交換，本文提出了限下界的平行攻擊。這種攻擊方式非常類似于現實世界的攻擊。為了避免攻擊許多低度值的節點，本文設定的下界值分別是4和10，也就是說與上一步被攻擊節點鄰接的節點的度值大于4和10時，才會被攻擊。

仿真結果如圖2所示。在Internet模型中，下界值為10的攻擊和有目的攻擊一樣高效，崩潰閾值從3.8%只輕微上升到4.1%。假如設置的下界值是4，在網絡崩潰前，攻擊節點數增多(崩潰閾值變為5.7%)，并且由于每一步攻擊的節點數增多，攻擊的步驟減少。在BA模型中觀察的結果是不同的，如果下界值設定為4，崩潰閾值非常接近于有目的攻擊(崩潰閾值為16%)。當下界值設定為10，攻擊將在17步后終止，因為這時所有“淪陷”節點的存活鄰節點的度值都低于下界值，此時，網絡還存在較大的連通子圖。

可以這樣理解所觀察到的結果，僅僅掌握Internet局部網絡拓撲信息，只攻擊度值相對大的節點，同樣可以摧毀整個網絡。從圖2可以看出，在早期，網絡分解速度較慢，在某些步驟以后，分解的速度急劇加快。因此，為了保護Internet免遭這種分布式攻擊的破壞，關鍵在于盡早識別并阻止攻擊。此外，選擇合適的閾值對攻擊方非常重要：太低的閾值需要攻擊更多度值小的節點，使攻擊速度變慢，攻擊時間延長，這樣一來防御方有機會加強保護，甚至對攻擊者予以反擊；而設定太高的閾值使攻擊的破壞程度降低，甚至不可能摧毀整個網絡。

2 復雜網絡修復策略

目前國際和國內雖然對網絡的修復性有一定研究但對復雜網絡遭到破壞的研究還只局限于研究復雜網絡的魯棒性，即復雜網絡對外界的破壞的承受能力。即使一些文章中涉及到復雜網絡的修復性研究但其修復策略和一般網絡的修復策略也沒什么區別，而我們首次針對復雜網絡的冪率分布特性提出了一種基于馬太效應的復雜網絡修復策略。

2.1 相關研究

（1）在文獻[3]中總結了基于拓撲信息的修復策略，在此種修復策略中分析拓撲圖論與網絡生存性的關系，介紹拓撲圖論算法在網絡修復中的實際應用，對基于網絡分割的故障修復算法、基于拓撲結構的修復路徑選擇算法、用于鏈路故障保護的P-Cycle 算法等進行比較，研究和探討了目前網絡修復中亟待解決的問題。網絡的修復與網絡的生存性密切相關，但從目前的研究成果來看，兩者的結合還不夠，而且大多數研究考慮的拓撲結構簡單、故障種類單一。目前的網絡拓撲研究在物理拓撲和邏輯拓撲上是混淆的。這就導致了基于網絡拓撲結構的修復算法難以用實驗仿真也難于實現，而且從大型實際網絡中測量其全部拓撲也存在一定的難度這就導致了此種修復策略的實用性不高。

（2）以一定的修復幾率重新連接遭到襲擊的節點和網絡中的其它節點。在其修復模型中是以一定的修復幾率來修復網絡的并沒有考慮復雜網絡本身的一些特性這就使得此種修復模型的針對性不強，而我們的修復策略充分考慮了復雜網絡的冪率特性及其在隨機重連時的馬太效應，所以我們的修復策略更具有針對性。

（3）網絡修復過程中的評價標準：最大效率法和Horn算法。對網絡修復算法提出了量化的評價標準。

2.2 基于馬太效應的復雜網絡修復方法

近年來在復雜網絡研究上的一重大發現是許多復雜網絡，包括Internet、WWW以及新陳代謝網絡等的鏈接度分布函數具有冪率形式。BA網絡模型能很好的反映這一特性，BA網絡模型的生成過程很好的考慮了實際網絡的以下兩個特性 ：

（1）增長(growth)特性：即網絡的規模不斷擴大。

（2）優先連接(preferential attachment)特性：即新的節點更傾向于與那些具有較高連接度的“大”節點相連接。這種現象也稱為“馬太效應(Matthew effect)”。

我們從無標度網絡的馬太效應出發研究馬太效應在復雜網絡修復中的應用。我們主要考慮持續攻擊下的隨機刪除節點和有目的刪除節點(比如刪除網絡中的最大度值節點)，在這種攻擊中以比率r優先選擇刪除一個節點的同時把一個節點重新連接到網絡上，我們假設新加入到網絡中的節點選擇網絡中度值最大的節點連接。失去鄰接點的節點不是坐以待斃而是重新連接其他節點來代替丟失的鄰節點；此外，被攻擊的節點作為新節點重新連接到網絡中。這樣，當攻擊網絡的最大度值節點時，補償動力學協議仍然能夠保護密率分布的指數。而且，我們的仿真顯示即使在很高比率的優先攻擊下或攻擊網絡中的大度值節點時，只要新加入的節點擁有m≥2的隨機連接網絡就能夠保持一個很大的連接部分；這樣，失去的連接就不再是這個持續攻擊的損害結果。

我們是把構建BA網絡的思想應用到冪率分布網絡的修復中能得到很好的效果，這不僅能得到很高的修復率而且還能優化網絡的拓撲結構。我們的方針結果顯示在此種修復方法下對internet網絡和BA網絡的修復率可達98%以上，即使攻擊網絡中的最大度值節點修復率也可達到95%以上。

3 結論

本文分別研究了基于不完全網絡拓撲信息的有目的攻擊和局部網絡拓撲信息的分布式攻擊下以及有關復雜網絡修復策略的相關研究并提出了基于馬太效應復雜網絡修復策略，該研究對于制定高效的攻擊策略和修復策略具有重要的意義特別是在軍事領域具有很高的實用價值。

[1] Watts D J,Strogatz S H.Collective dynamics of small-world networks[J].Nature.1998.

[2] Holme P, Kim B J, Yoon C N, et al. Attack vulnerability of complex networks[J]. Phys.Rev.E.2002.

[3] 繆志敏,丁力等.基于拓撲信息的網絡修復[J].計算機工程.2009.