基于傳播動力學(xué)的域間路由系統(tǒng)關(guān)鍵節(jié)點識別方法

朱會虎，邱菡，朱俊虎，曾子懿

基于傳播動力學(xué)的域間路由系統(tǒng)關(guān)鍵節(jié)點識別方法

朱會虎1,2，邱菡1,2，朱俊虎1,2，曾子懿1,2

（1. 數(shù)學(xué)工程與先進計算國家重點實驗室，河南 鄭州 450001；2. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450001）

域間路由系統(tǒng)是互聯(lián)網(wǎng)的關(guān)鍵基礎(chǔ)設(shè)施，對域間路由系統(tǒng)中的關(guān)鍵節(jié)點實施保護具有重要意義。針對現(xiàn)有關(guān)鍵節(jié)點識別方法識別出的關(guān)鍵節(jié)點不能反映節(jié)點在失效傳播過程中起到關(guān)鍵作用的問題，提出了基于傳播動力學(xué)的關(guān)鍵節(jié)點識別方法。該方法通過綜合考慮節(jié)點失效后引發(fā)的負載重分配和UPDATE報文傳播對周圍節(jié)點和邊產(chǎn)生的影響，提出了基于DDF-CFM模型的節(jié)點重要性評估模型。實驗結(jié)果表明，該方法相比已有方法識別關(guān)鍵節(jié)點的準確程度至少提高7.3%。同時，在10 000個網(wǎng)絡(luò)的規(guī)模下，僅5個關(guān)鍵節(jié)點失效就將導(dǎo)致大規(guī)模的域間路由系統(tǒng)級聯(lián)失效。

域間路由系統(tǒng)；關(guān)鍵節(jié)點；評估；傳播動力學(xué)

1 引言

域間路由系統(tǒng)是互聯(lián)網(wǎng)的關(guān)鍵基礎(chǔ)設(shè)施，一旦遭受攻擊將對互聯(lián)網(wǎng)造成巨大損失。近年來，研究者提出了一系列針對域間路由系統(tǒng)的攻擊方法，典型的包括CXPST（coordinated cross plane session termination）攻擊[1]、壓力測試攻擊[2]、DNP（distributed network paralyzing）攻擊[3]以及LFA(link-flooding attacks)[4]等，該類攻擊一旦達成將對互聯(lián)網(wǎng)造成不可估量的損傷。此外，報告顯示該類攻擊已經(jīng)逐步出現(xiàn)在現(xiàn)實生活中[5]，因此對該類攻擊的防御迫在眉睫。該類攻擊主要是通過攻擊部分關(guān)鍵節(jié)點，造成域間路由系統(tǒng)級聯(lián)失效，并產(chǎn)生較大范圍的影響。其原因在于域間路由系統(tǒng)中節(jié)點間存在耦合關(guān)系，部分關(guān)鍵節(jié)點的失效會引發(fā)域間路由系統(tǒng)級聯(lián)失效。為了防御該類攻擊，需要找到在域間路由系統(tǒng)發(fā)生級聯(lián)失效時起關(guān)鍵作用的節(jié)點，并對其實施有針對性的保護，從而加大攻擊者攻擊的難度，降低攻擊的損害程度。

2 相關(guān)研究

在復(fù)雜網(wǎng)絡(luò)領(lǐng)域，依據(jù)研究的角度不同，識別關(guān)鍵節(jié)點的方法分為兩類：基于網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)鍵節(jié)點識別方法和基于傳播動力學(xué)的關(guān)鍵節(jié)點識別方法[6]?；诰W(wǎng)絡(luò)結(jié)構(gòu)的關(guān)鍵節(jié)點識別方法主要將結(jié)構(gòu)屬性作為評價節(jié)點重要程度的指標，通過節(jié)點的重要程度來識別關(guān)鍵節(jié)點[7-9]；基于傳播動力學(xué)的關(guān)鍵節(jié)點識別方法主要研究節(jié)點在傳播動力學(xué)過程中產(chǎn)生的影響大小[10]。由于域間路由網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和網(wǎng)絡(luò)流量路徑選擇的方式與一般的復(fù)雜網(wǎng)絡(luò)存在較大差異，導(dǎo)致一般復(fù)雜網(wǎng)絡(luò)中，基于靜態(tài)結(jié)構(gòu)屬性的關(guān)鍵節(jié)點識別方法不能很好地解決域間路由系統(tǒng)關(guān)鍵節(jié)點識別的問題。而且域間路由系統(tǒng)中節(jié)點和邊的失效條件不同，導(dǎo)致節(jié)點失效后產(chǎn)生影響的傳播動力學(xué)機制與一般復(fù)雜網(wǎng)絡(luò)有較大差別，因此復(fù)雜網(wǎng)絡(luò)中基于傳播動力學(xué)的關(guān)鍵節(jié)點識別方法不能直接應(yīng)用在域間路由系統(tǒng)中進行關(guān)鍵節(jié)點識別?，F(xiàn)有針對域間路由系統(tǒng)的關(guān)鍵節(jié)點識別方法研究主要是從網(wǎng)絡(luò)結(jié)構(gòu)的角度出發(fā)，分為兩種思路：一是認為節(jié)點的度越大節(jié)點越重要[11]；二是認為節(jié)點的介數(shù)越大節(jié)點越重要[1]。將度作為評價節(jié)點重要性的指標，認為度越大的節(jié)點其鄰居節(jié)點越多，從而導(dǎo)致經(jīng)過其上的流量越多，因此認為摘除度大的節(jié)點影響更大。度作為網(wǎng)絡(luò)節(jié)點一個比較重要的屬性，能夠在一定程度上反映出節(jié)點的重要性，但用來評估域間路由系統(tǒng)節(jié)點重要性仍然存在較大局限性。域間路由系統(tǒng)中的節(jié)點按照所處的位置不同，可以分為核心節(jié)點和邊緣節(jié)點。核心區(qū)域的節(jié)點與邊緣區(qū)域的節(jié)點在度相同的情況下，重要程度有較大差別。將單一的度作為評價節(jié)點重要性的標準，會造成較大的誤差。將介數(shù)作為節(jié)點選擇的依據(jù)，也很難真實地反映出節(jié)點在域間路由系統(tǒng)中的重要程度。節(jié)點介數(shù)是指網(wǎng)絡(luò)中所有經(jīng)過該節(jié)點的最短路徑占所有最短路徑的比，因此介數(shù)的大小主要與最短路徑相關(guān)。但域間路由系統(tǒng)中路由路徑的選擇并不僅與最短路徑相關(guān)，還與AS（autonomous system）域之間的商業(yè)關(guān)系以及局部優(yōu)先級等因素相關(guān)，因此介數(shù)大的節(jié)點，經(jīng)過其上的流量并不一定多，重要程度也并不一定高。文獻[12]提出了一種基于首選路由的關(guān)鍵AS識別方法（PR-TEAO，technique of evaluating AS importance based on preferred route），其主要思想是認為經(jīng)過最優(yōu)路徑越多的節(jié)點越重要。其本質(zhì)是對介數(shù)中心性的改進，克服了介數(shù)不能表示實際流量的問題，能反映節(jié)點失效后對周圍節(jié)點負載的影響。但節(jié)點失效后不但對負載產(chǎn)生影響，其失效后產(chǎn)生的UPDATE報文對其他節(jié)點在資源消耗上也會產(chǎn)生較大影響。因此，不能完全反映節(jié)點在失效傳播過程中的作用。

本文研究目標是找出在級聯(lián)失效過程中起關(guān)鍵作用的節(jié)點，評價節(jié)點是否關(guān)鍵，需要評估節(jié)點失效后產(chǎn)生的影響大?。划a(chǎn)生的影響越大，其在級聯(lián)失效過程中的作用越關(guān)鍵，這樣的節(jié)點就是關(guān)鍵節(jié)點。域間路由系統(tǒng)單個節(jié)點的失效會造成UPDATE報文傳播和負載重分配兩方面影響，UPDATE報文傳播導(dǎo)致新的節(jié)點失效，負載重分配又導(dǎo)致邊失效，如此反復(fù)造成整個域間路由系統(tǒng)級聯(lián)失效。因此，評估節(jié)點的重要性首先需要對節(jié)點失效后產(chǎn)生的兩方面影響進行量化分析，進而提出評估節(jié)點重要性的綜合指標。對節(jié)點失效后產(chǎn)生的影響進行量化分析，首先需要對節(jié)點失效后造成的傳播動力學(xué)過程進行建模分析，之后通過運用該模型進行節(jié)點摘除實驗，采集實驗過程數(shù)據(jù)，基于該數(shù)據(jù)利用綜合評估方法評估節(jié)點重要度，進而依據(jù)重要度的大小識別出關(guān)鍵節(jié)點。

3 域間路由系統(tǒng)級聯(lián)失效傳播動力學(xué)分析

本節(jié)主要分析域間路由系統(tǒng)級聯(lián)失效的傳播動力學(xué)過程，研究影響級聯(lián)失效傳播的關(guān)鍵因素，找出適合描述域間路由系統(tǒng)傳播動力學(xué)過程的傳播模型。

3.1 級聯(lián)失效傳播動力學(xué)過程分析

域間路由系統(tǒng)級聯(lián)失效傳播過程主要包括兩階段[13]，分別是級聯(lián)失效觸發(fā)階段和失效傳播階段。觸發(fā)階段是指節(jié)點（或邊）發(fā)生故障或遭受攻擊，使節(jié)點（或邊）失效；基于節(jié)點間的耦合關(guān)系，部分節(jié)點（或邊）的失效可以觸發(fā)級聯(lián)失效。失效傳播階段是指當(dāng)節(jié)點（或邊）失效時，導(dǎo)致經(jīng)過該節(jié)點（或邊）的負載重新選路，引發(fā)負載重分配；同時，相鄰的節(jié)點向周圍節(jié)點傳播UPDATE報文，通報節(jié)點失效情況，大量節(jié)點（或邊）失效可以導(dǎo)致域間路由系統(tǒng)中產(chǎn)生過量的UPDATE報文。研究表明，負載重分配后，一些新的邊由于業(yè)務(wù)流量急劇增加，導(dǎo)致過載失效[14]；而且，當(dāng)過量的UPDATE報文同時到達某一個節(jié)點時，導(dǎo)致該節(jié)點CPU、內(nèi)存等資源耗盡，引發(fā)節(jié)點失效。新的節(jié)點和邊的失效又導(dǎo)致新一輪的負載重分配和UPDATE報文傳播，從而促進域間路由系統(tǒng)級聯(lián)失效傳播，具體過程如圖1所示。

圖1 級聯(lián)失效過程分析

因此，負載重分配和UPDATE報文是導(dǎo)致域間路由系統(tǒng)級聯(lián)失效傳播的兩個關(guān)鍵因素。為了刻畫域間路由系統(tǒng)級聯(lián)失效傳播動力學(xué)過程，需要對其過程進行建模。文獻[11]給出了CFM（cascading failure model）模型，該模型認為節(jié)點和邊失效是等價的，都是由過載引發(fā)的。文獻[15]和文獻[16]繼承了文獻[11]的思想，認為導(dǎo)致級聯(lián)失效傳播的主要因素是負載重分配。三者均沒有考慮UPDATE報文級聯(lián)失效的促進作用，與事實不相符。文獻[17]同時考慮了負載重分配和UPDATE報文級聯(lián)失效的影響，提出DDF-CFM（double damage factor based inter-domain routing system cascading failure model）模型，與本文分析相同，因此，本文在DDF-CFM模型的基礎(chǔ)上，進一步分析節(jié)點失效后對周圍節(jié)點產(chǎn)生的影響。

3.2 DDF-CFM模型的運行過程

DDF-CFM模型主要模擬了負載重分配和UPDATE報文在域間路由系統(tǒng)的傳播過程，刻畫了節(jié)點和邊的失效過程，還原了級聯(lián)失效在域間路由系統(tǒng)中的傳播過程。利用該模型，可以采集單節(jié)點失效后造成的UPDATE報文傳播和負載重分配對周圍節(jié)點和邊產(chǎn)生影響大小的基礎(chǔ)評估數(shù)據(jù)，基于該數(shù)據(jù)結(jié)合節(jié)點重要性評估模型，可以對節(jié)點的重要性進行量化評估。DDF-CFM模型主要工作流程如下。

步驟1 摘除部分節(jié)點（或邊），觸發(fā)級聯(lián)失效過程。

步驟2 判斷是否存在失效節(jié)點（或邊），若不存在，結(jié)束；若存在，則進行下一步。

步驟3 找出與失效節(jié)點（或邊）相鄰的所有節(jié)點，作為UPDATE報文傳播的初始節(jié)點，將這些初始節(jié)點加入路由轉(zhuǎn)發(fā)集

步驟4 判斷路由轉(zhuǎn)發(fā)集中的節(jié)點是否存在節(jié)點需要向外發(fā)送或轉(zhuǎn)發(fā)UPDATE報文信息，需要則進行下一步，不需要則進行步驟7。

步驟5 將接收到UPDATE報文信息的節(jié)點加入新的路由轉(zhuǎn)發(fā)集1，周圍節(jié)點接收到UPDATE報文信息后，對其進行解析處理，更新自己的路由信息表和路由轉(zhuǎn)發(fā)表。

步驟6 判斷是否有新的節(jié)點因UPDATE報文過量，導(dǎo)致CPU、內(nèi)存等資源耗盡失效，如果有，將與之相鄰的節(jié)點加入新的路由轉(zhuǎn)發(fā)集1，重復(fù)步驟4~步驟6；若沒有，則進行下一步。

步驟7 找出最優(yōu)路徑受到影響的節(jié)點和邊，依據(jù)最優(yōu)路徑選擇方法找出新的最優(yōu)路徑，將原有負載加到新的最優(yōu)路徑上。

步驟8 判斷負載重分配后，各條邊是否過載，過載則失效，將失效邊加入失效集中，回到步驟2。

DDF-CFM模型具體運行過程如圖2所示。

圖2 DDF-CFM模型運行過程

4 基于失效影響的節(jié)點重要性評估模型

域間路由系統(tǒng)中節(jié)點重要性是由該節(jié)點失效后對周圍節(jié)點產(chǎn)生的影響大小來決定的。由3.1節(jié)的分析可知，節(jié)點的失效主要對周圍節(jié)點產(chǎn)生如下兩方面影響：1) 導(dǎo)致負載重分配，使其他邊負載增加；2) 導(dǎo)致相鄰的節(jié)點向其周圍的節(jié)點發(fā)送UPDATE報文信息，消耗周圍節(jié)點的CPU和內(nèi)存等資源。因此，分別從這兩個方面對單個節(jié)點失效后對網(wǎng)絡(luò)的影響程度進行評估。

4.1 負載重分配對邊的影響

4.2 UPDATE報文對節(jié)點的影響

當(dāng)節(jié)點失效時，與該節(jié)點相鄰的節(jié)點向其周圍的節(jié)點發(fā)送UPDATE報文信息，通報節(jié)點失效情況。其他節(jié)點接收到報文信息后，對報文信息進行解析，修改自己的路由信息表和路由轉(zhuǎn)發(fā)表。之后，判斷是否轉(zhuǎn)發(fā)該報文。需要，則轉(zhuǎn)發(fā)；不需要，則不轉(zhuǎn)發(fā)。一個UPDATE報文由節(jié)點檢測到會話斷開而產(chǎn)生，到不再有節(jié)點轉(zhuǎn)發(fā)而停止。報文的傳播過程可以看作節(jié)點失效后整個影響過程。主要和兩個因素相關(guān)，分別是相鄰節(jié)點的數(shù)目以及每個相鄰節(jié)點產(chǎn)生的UPDATE報文的影響范圍。

圖3 域間路由系統(tǒng)局部結(jié)構(gòu)示意

4.3 單節(jié)點失效對域間路由系統(tǒng)整體影響評估

4.4 關(guān)鍵節(jié)點識別方法的評價標準

評價關(guān)鍵節(jié)點識別方法好壞的主要思路是將這些方法識別出的關(guān)鍵節(jié)點集作為研究對象，通過考察這些節(jié)點摘除后對網(wǎng)絡(luò)結(jié)構(gòu)和功能的影響大小[19]。當(dāng)基于網(wǎng)絡(luò)結(jié)構(gòu)屬性識別關(guān)鍵節(jié)點時，主要通過考察摘除部分節(jié)點對整體網(wǎng)絡(luò)結(jié)構(gòu)的影響，用網(wǎng)絡(luò)的頑健性和脆弱性來評價方法的好壞。當(dāng)基于網(wǎng)絡(luò)的傳播動力學(xué)過程研究節(jié)點的重要度時，主要通過考察部分節(jié)點摘除后對失效傳播過程的影響來評估方法的好壞，造成節(jié)點和邊的失效比例越高，說明方法越好。

5 基于傳播動力學(xué)的域間路由系統(tǒng)關(guān)鍵節(jié)點識別過程

5.1 關(guān)鍵節(jié)點識別過程

通過前文的分析可知，域間路由系統(tǒng)關(guān)鍵節(jié)點識別主要包含兩個階段。首先建立域間路由系統(tǒng)級聯(lián)失效傳播動力學(xué)模型，在這個模型的基礎(chǔ)上，采集相關(guān)的網(wǎng)絡(luò)數(shù)據(jù)，利用基于失效影響的節(jié)點重要性評估模型，評價各個節(jié)點的重要程度。之后，綜合比較各個節(jié)點的重要程度選出較為關(guān)鍵的節(jié)點，具體過程如下。

步驟1 利用真實的網(wǎng)絡(luò)數(shù)據(jù)建立基礎(chǔ)的網(wǎng)絡(luò)環(huán)境，作為運行DDF-CFM模型的基礎(chǔ)。

步驟2 從域間路由系統(tǒng)節(jié)點集中選擇一個節(jié)點，作為摘除節(jié)點，輸入DDF-CFM模型中。

步驟3 在模型運行過程中，通過記錄每一次循環(huán)受影響的邊和加入路由轉(zhuǎn)發(fā)集中的節(jié)點以及UPDATE報文，采集負載變化信息和UPDATE報文傳播信息。

步驟5 如果域間路由系統(tǒng)節(jié)點集中仍有節(jié)點沒有被選中，重復(fù)步驟2~步驟4，直到所有節(jié)點都被選中一次。

步驟6 比較各個節(jié)點重要性的大小，輸出較為重要的節(jié)點。

具體過程如圖4所示。

5.2 確定最優(yōu)a值

圖4 域間路由系統(tǒng)關(guān)鍵節(jié)點識別過程

圖5 確定最優(yōu)a值

圖6 節(jié)點影響大小分布情況

6 實驗驗證

為了驗證本文方法的有效性和準確性，將本文方法與現(xiàn)有方法和隨機選擇的方法識別出的關(guān)鍵節(jié)點進行對比分析。

6.1 與現(xiàn)有關(guān)鍵節(jié)點識別方法對比分析

本節(jié)分別選擇2001年、2004年、2007年、2010年、2013年、2016年7月的數(shù)據(jù)集用作對比實驗的基礎(chǔ)網(wǎng)絡(luò)環(huán)境，驗證本文方法與傳統(tǒng)方法的優(yōu)劣。對各年份的數(shù)據(jù)集進行節(jié)點數(shù)目的統(tǒng)計分析，不同時期網(wǎng)絡(luò)中節(jié)點的個數(shù)隨時間的變化關(guān)系如圖7所示。由圖可知，隨著時間的推移，域間路由節(jié)點的數(shù)目不斷增加。

圖7 節(jié)點個數(shù)隨時間的變化情況

用本文SD-KNI（spreading dynamics based key nodes identification in inter-domain routing system）方法與現(xiàn)有方法和隨機選擇的方法作對比，現(xiàn)有較好的方法主要包括度中心性法、基于文獻[16]提出的IRS-CFM模型的方法和PR-TEAI方法。通過大量的實驗發(fā)現(xiàn)，僅需要較少關(guān)鍵的節(jié)點即可造成較大規(guī)模的級聯(lián)失效，因此用以上方法從不同年份的數(shù)據(jù)中分別找出域間路由系統(tǒng)中最關(guān)鍵的20個節(jié)點。為了排除節(jié)點間的組合關(guān)系以及特殊節(jié)點對實驗結(jié)果的影響，從選出的不同關(guān)鍵節(jié)點集中，分別進行摘除前5、前10、前15和前20個關(guān)鍵節(jié)點的域間路由系統(tǒng)級聯(lián)失效實驗，實驗結(jié)果如圖8~圖11所示。

由圖可知，無論摘除多少個節(jié)點，在不同的年份下，本文方法識別出的關(guān)鍵節(jié)點，造成的節(jié)點和邊失效比例比其他方法造成的失效比例高，驗證了本文方法的有效性。由圖8和圖9可知如下結(jié)果。1) 在節(jié)點集規(guī)模不斷增大的情況下，摘除節(jié)點個數(shù)為5和10時，關(guān)鍵節(jié)點失效造成的節(jié)點和邊的失效比隨著年份的增加而降低。主要原因是隨著時間的推移，域間路由系統(tǒng)節(jié)點規(guī)模不斷增加，每個節(jié)點單獨的影響范圍不斷降低。同時，以度中心性作為判斷節(jié)點重要性的依據(jù)相對于其他方法更好，主要原因是度較大的節(jié)點，相對于其他方法，其失效后直接影響的節(jié)點和路徑較多，造成的影響范圍較大。2) 通過摘除隨機選擇的節(jié)點造成的節(jié)點和邊的失效比變化較大，且整體造成的失效比例較低，說明一般的節(jié)點能夠產(chǎn)生的影響較小，更加凸顯關(guān)鍵節(jié)點的重要性。

圖8 摘除5個節(jié)點條件下各方法失效比例分布

圖9 摘除10個節(jié)點條件下各方法失效比例分布

圖11 摘除20個節(jié)點條件下各方法失效比例分布

對比本文方法與度中心性的方法實驗結(jié)果，在摘除20個節(jié)點的條件下，本文方法造成的節(jié)點和邊的失效比例平均高出16.7%，最多高出21.9%。

6.2 摘除節(jié)點個數(shù)對實驗結(jié)果的影響

通過對第6.1節(jié)的數(shù)據(jù)分析發(fā)現(xiàn)，以2001年7月數(shù)據(jù)集為環(huán)境基礎(chǔ)，當(dāng)選擇5個比較關(guān)鍵的節(jié)點時，對域間路由系統(tǒng)進行節(jié)點摘除實驗，可以造成較大范圍的級聯(lián)失效過程。增加失效節(jié)點的個數(shù)不但沒有增加失效節(jié)點和失效邊的比例，反而降低了，實驗數(shù)據(jù)如圖12所示。

圖12 失效比例隨節(jié)點數(shù)目變化情況

通過分析比較這些關(guān)鍵節(jié)點的網(wǎng)絡(luò)基礎(chǔ)結(jié)構(gòu)發(fā)現(xiàn)，當(dāng)摘除重要度靠前的5個節(jié)點時，其分布在域間路由系統(tǒng)的不同區(qū)域，節(jié)點間不存在緊密的連接關(guān)系，造成的級聯(lián)失效過程具有較大的毀傷效果。當(dāng)摘除前10、前15、前20和前25個節(jié)點時，隨著摘除的重要節(jié)點的數(shù)目增加，部分情況下造成的失效比例不但沒有增加，反而有所降低。通過研究后續(xù)增加節(jié)點的位置以及連接關(guān)系發(fā)現(xiàn)，后續(xù)的部分節(jié)點與最初的5個節(jié)點存在直接的連通關(guān)系，連接關(guān)系如圖13所示。

圖13 域間路由節(jié)點連接關(guān)系

通過本次實驗可以發(fā)現(xiàn)，使整個網(wǎng)絡(luò)達到比較嚴重的級聯(lián)失效過程，并不需要大量的節(jié)點失效，極少量的關(guān)鍵節(jié)點同時失效可以造成較嚴重的網(wǎng)絡(luò)癱瘓。因此，找出關(guān)鍵節(jié)點，對其進行有針對性的保護具有重要意義。

7 結(jié)束語

針對傳統(tǒng)關(guān)鍵節(jié)點識別方法的不足，本文提出了基于傳播動力學(xué)的關(guān)鍵節(jié)點識別方法，該方法能夠更加準確地識別出域間路由系統(tǒng)中的關(guān)鍵節(jié)點，為進一步對關(guān)鍵節(jié)點實施有針對性的保護提供了重要理論支撐。通過與現(xiàn)有關(guān)鍵節(jié)點識別方法對比分析，驗證了本文方法的有效性和準確性。實驗結(jié)果表明，僅需要較少的關(guān)鍵節(jié)點就可以造成整個域間路由系統(tǒng)癱瘓。失效節(jié)點間的連接關(guān)系以及組合關(guān)系對級聯(lián)失效產(chǎn)生的影響，是后續(xù)研究工作的重點。

[1] SCHUCHARD M, MOHAISEN A, FOO K D, et al. Losing control of the internet: using the data plane to attack the control plane[C]//The 17th ACM Conference on Computer and Communications Security. ACM, 2010: 726-728.

[2] DENG W, ZHU P, LU X, et al. On evaluating BGP routing stress attack[J]. JCM, 2010, 5(1): 13-22.

[3] LI H S, ZHU J H, QIU H, et al. The new threat to internet: DNP attack with the attacking flows strategizing technology[J]. International Journal of Communication Systems, 2015, 28(6): 1126-1139.

[4] KANG M S, GLIGOR V D, SEKAR V. SPIFFY: inducing cost-detectability tradeoffs for persistent link-flooding attacks[C]//NDSS. 2016.

[5] Zheng J, Li Q, Gu G, et al. Realtime DDoS defense using COTS SDN switches via adaptive correlation analysis[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(7): 1838-1853.

[6] 劉建國, 任卓明, 郭強, 等. 復(fù)雜網(wǎng)絡(luò)中節(jié)點重要性排序的研究進展[J]. 物理學(xué)報, 2013, 62(17): 178901. LIU J G, REN Z M, GUO Q, et al. Node importance ranking of complex networks [J]. Acta Physica Sinica 2013, 62(17): 178901.

[7] ROSSI R A, AHMED N K. Role discovery in networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(4): 1112-1131.

[8] TENG D, CHU D. A fast frequent directions algorithm for low rank approximation:(previous title: sparse frequent directions algorithm for low rank approximation)[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018.

[9] WANG W, TANG M, STANLEY H E, et al. Unification of theoretical approaches for epidemic spreading on complex networks[J]. Reports on Progress in Physics, 2017, 80(3): 036603.

[10] BORGE-HOLTHOEFER J, MORENO Y. Absence of influential spreaders in rumor dynamics[J]. Physical Review E, 2012, 85(2): 026116.

[11] GUO Y, WANG Z, LUO S, et al. A cascading failure model for interdomain routing system[J]. International Journal of Communication Systems, 2012, 25(8): 1068-1076.

[12] 劉紅軍, 胡曉峰, 鄧文平, 等. 基于首選路由的 AS 重要性評估方法[J]. 軟件學(xué)報, 2012, 23(9): 2388-2400. LIU H J, HU XF, DENG W P, et al. Technique of evaluating AS importance based on preferred route[J]. Journal of Software, 2012,23(9):2388-2400.

[13] 邱菡, 李玉峰, 蘭巨龍, 等. 域間路由系統(tǒng)的級聯(lián)失效攻擊及檢測研究[J]. 中國科學(xué): 信息科學(xué), 2017, 47: 1715-1729. QIU H, LI Y F, LAN J L, et al. Research on cascading failure attack and detection of inner-domain routing system[J]. Scientia Sinica Informations, 2017, 47: 1715-1729.

[14] ZHANG Y, MAO Z M, WANG J. Low-rate TCP-targeted DoS attack disrupts internet routing[C]//NDSS. 2007.

[15] LIU Y, PENG W, SU J, et al. Assessing the impact of cascading failures on the inter-domain routing system of the internet[J]. New Generation Computing, 2014, 32(3-4): 237-2552.

[16] YANG B, ZHANG Y, LU Y. A new methods for cascading failures analysis in inter-domain routing system[C]//2015 Fifth International Conference IEEE on Instrumentation and Measurement, Computer, Communication and Control (IMCCC). 2015: 382-385.

[17] 朱會虎, 邱菡, 王清賢, 等. 基于雙毀傷因素的域間路由系統(tǒng)級聯(lián)失效模型[J].計算機工程與應(yīng)用, 2019, 55(2): 92-99.ZHU H H, QIU H, WANG Q X, et al. Double damage factor based inter-domain routing system cascading failure model[J]. Computer Engineering and Applications, 2019, 55(2): 92-99.

[18] MOTTER A E, LAI Y C. Cascade-based attacks on complex networks[J]. Physical Review E, 2002, 66(6): 065102.

[19] 任曉龍, 呂琳媛. 網(wǎng)絡(luò)重要節(jié)點排序方法綜述[J]. 科學(xué)通報, 2014, 59: 1175-1197.REN X L, Lü L Y. Review of ranking nodes in complex networks [J]. Chinese Science Bulletin, 2014, 59: 1175-1197.

Spreading dynamics based key nodes identification in inter-domain routing system

ZHU Huihu1,2, QIU Han1,2, ZHU Junhu1,2, ZENG Ziyi1,2

1. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China 2. National Engineering Technology Research Center of the National Digital Switching System, Zhengzhou 450001, China

The inter-domain routing system is a critical infrastructure of the Internet and it is of great significance to protect the key nodes of inter-domain routing system. The key nodes identified by the existing methods can not reflect the importance of the nodes on the cascading failure process. The method of key nodes identification is proposed basing on spreading dynamics. A node importance evaluation model based on DDF-CFM model is proposed., which could takes the failure effect caused by load redistribution and UPDATE messages propagation into account after node fails. The experiments turn out that the accuracy of this method is at least 7.3% higher than that of existing methods. And the experimental results show that in the scale of 10000 nodes, the failure of only 5 key nodes will lead to large-scale cascade failure of inter-domain routing systems.

inter-domain routing system, key nodes, evaluation, spreading dynamics

朱會虎（1992? ），男，河南商丘人，數(shù)學(xué)工程與先進計算國家重點實驗室博士生，主要研究方向為域間路由系統(tǒng)安全。

邱菡（1981? ），女，湖北隨州人，數(shù)學(xué)工程與先進計算國家重點實驗室副教授，主要研究方向為網(wǎng)絡(luò)空間安全、域間路由系統(tǒng)安全。

朱俊虎（1974? ），男，江蘇鎮(zhèn)江人，數(shù)學(xué)工程與先進計算國家重點實驗室教授，主要研究方向為網(wǎng)絡(luò)空間安全。

曾子懿（1989? ），男，湖南祁東人，數(shù)學(xué)工程與先進計算國家重點實驗室博士生，主要研究方向為域間路由系統(tǒng)安全。

TP393.4

A

10.11959/j.issn.2096?109x.2019046

2018?12?11；

2019?02?13

邱菡，qiuhan410@aliyun.com

國家自然科學(xué)基金資助項目（No. 61502528,No. 61402525）

The National Natural Science Foundation of China (No.61502528, No.61402525)

朱會虎, 邱菡, 朱俊虎, 等. 基于傳播動力學(xué)的域間路由系統(tǒng)關(guān)鍵節(jié)點識別方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 2019, 5(5): 9-20.

ZHU H H, QIU H, ZHU J H, et al. Spreading dynamics based key nodes identification in inter-domain routing system[J]. Chinese Journal of Network and Information Security, 2019, 5(5): 9-20.