基于传播动力学的域间路由系统关键节点识别方法

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

基于传播动力学的域间路由系统关键节点识别方法

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

（1. 数学工程与先进计算国家重点实验室，河南 郑州 450001；2. 国家数字交换系统工程技术研究中心，河南 郑州 450001）

域间路由系统是互联网的关键基础设施，对域间路由系统中的关键节点实施保护具有重要意义。针对现有关键节点识别方法识别出的关键节点不能反映节点在失效传播过程中起到关键作用的问题，提出了基于传播动力学的关键节点识别方法。该方法通过综合考虑节点失效后引发的负载重分配和UPDATE报文传播对周围节点和边产生的影响，提出了基于DDF-CFM模型的节点重要性评估模型。实验结果表明，该方法相比已有方法识别关键节点的准确程度至少提高7.3%。同时，在10 000个网络的规模下，仅5个关键节点失效就将导致大规模的域间路由系统级联失效。

域间路由系统；关键节点；评估；传播动力学

1 引言

域间路由系统是互联网的关键基础设施，一旦遭受攻击将对互联网造成巨大损失。近年来，研究者提出了一系列针对域间路由系统的攻击方法，典型的包括CXPST（coordinated cross plane session termination）攻击[1]、压力测试攻击[2]、DNP（distributed network paralyzing）攻击[3]以及LFA(link-flooding attacks)[4]等，该类攻击一旦达成将对互联网造成不可估量的损伤。此外，报告显示该类攻击已经逐步出现在现实生活中[5]，因此对该类攻击的防御迫在眉睫。该类攻击主要是通过攻击部分关键节点，造成域间路由系统级联失效，并产生较大范围的影响。其原因在于域间路由系统中节点间存在耦合关系，部分关键节点的失效会引发域间路由系统级联失效。为了防御该类攻击，需要找到在域间路由系统发生级联失效时起关键作用的节点，并对其实施有针对性的保护，从而加大攻击者攻击的难度，降低攻击的损害程度。

2 相关研究

在复杂网络领域，依据研究的角度不同，识别关键节点的方法分为两类：基于网络结构的关键节点识别方法和基于传播动力学的关键节点识别方法[6]。基于网络结构的关键节点识别方法主要将结构属性作为评价节点重要程度的指标，通过节点的重要程度来识别关键节点[7-9]；基于传播动力学的关键节点识别方法主要研究节点在传播动力学过程中产生的影响大小[10]。由于域间路由网络的拓扑结构和网络流量路径选择的方式与一般的复杂网络存在较大差异，导致一般复杂网络中，基于静态结构属性的关键节点识别方法不能很好地解决域间路由系统关键节点识别的问题。而且域间路由系统中节点和边的失效条件不同，导致节点失效后产生影响的传播动力学机制与一般复杂网络有较大差别，因此复杂网络中基于传播动力学的关键节点识别方法不能直接应用在域间路由系统中进行关键节点识别。现有针对域间路由系统的关键节点识别方法研究主要是从网络结构的角度出发，分为两种思路：一是认为节点的度越大节点越重要[11]；二是认为节点的介数越大节点越重要[1]。将度作为评价节点重要性的指标，认为度越大的节点其邻居节点越多，从而导致经过其上的流量越多，因此认为摘除度大的节点影响更大。度作为网络节点一个比较重要的属性，能够在一定程度上反映出节点的重要性，但用来评估域间路由系统节点重要性仍然存在较大局限性。域间路由系统中的节点按照所处的位置不同，可以分为核心节点和边缘节点。核心区域的节点与边缘区域的节点在度相同的情况下，重要程度有较大差别。将单一的度作为评价节点重要性的标准，会造成较大的误差。将介数作为节点选择的依据，也很难真实地反映出节点在域间路由系统中的重要程度。节点介数是指网络中所有经过该节点的最短路径占所有最短路径的比，因此介数的大小主要与最短路径相关。但域间路由系统中路由路径的选择并不仅与最短路径相关，还与AS（autonomous system）域之间的商业关系以及局部优先级等因素相关，因此介数大的节点，经过其上的流量并不一定多，重要程度也并不一定高。文献[12]提出了一种基于首选路由的关键AS识别方法（PR-TEAO，technique of evaluating AS importance based on preferred route），其主要思想是认为经过最优路径越多的节点越重要。其本质是对介数中心性的改进，克服了介数不能表示实际流量的问题，能反映节点失效后对周围节点负载的影响。但节点失效后不但对负载产生影响，其失效后产生的UPDATE报文对其他节点在资源消耗上也会产生较大影响。因此，不能完全反映节点在失效传播过程中的作用。

本文研究目标是找出在级联失效过程中起关键作用的节点，评价节点是否关键，需要评估节点失效后产生的影响大小；产生的影响越大，其在级联失效过程中的作用越关键，这样的节点就是关键节点。域间路由系统单个节点的失效会造成UPDATE报文传播和负载重分配两方面影响，UPDATE报文传播导致新的节点失效，负载重分配又导致边失效，如此反复造成整个域间路由系统级联失效。因此，评估节点的重要性首先需要对节点失效后产生的两方面影响进行量化分析，进而提出评估节点重要性的综合指标。对节点失效后产生的影响进行量化分析，首先需要对节点失效后造成的传播动力学过程进行建模分析，之后通过运用该模型进行节点摘除实验，采集实验过程数据，基于该数据利用综合评估方法评估节点重要度，进而依据重要度的大小识别出关键节点。

3 域间路由系统级联失效传播动力学分析

本节主要分析域间路由系统级联失效的传播动力学过程，研究影响级联失效传播的关键因素，找出适合描述域间路由系统传播动力学过程的传播模型。

3.1 级联失效传播动力学过程分析

域间路由系统级联失效传播过程主要包括两阶段[13]，分别是级联失效触发阶段和失效传播阶段。触发阶段是指节点（或边）发生故障或遭受攻击，使节点（或边）失效；基于节点间的耦合关系，部分节点（或边）的失效可以触发级联失效。失效传播阶段是指当节点（或边）失效时，导致经过该节点（或边）的负载重新选路，引发负载重分配；同时，相邻的节点向周围节点传播UPDATE报文，通报节点失效情况，大量节点（或边）失效可以导致域间路由系统中产生过量的UPDATE报文。研究表明，负载重分配后，一些新的边由于业务流量急剧增加，导致过载失效[14]；而且，当过量的UPDATE报文同时到达某一个节点时，导致该节点CPU、内存等资源耗尽，引发节点失效。新的节点和边的失效又导致新一轮的负载重分配和UPDATE报文传播，从而促进域间路由系统级联失效传播，具体过程如图1所示。

图1 级联失效过程分析

因此，负载重分配和UPDATE报文是导致域间路由系统级联失效传播的两个关键因素。为了刻画域间路由系统级联失效传播动力学过程，需要对其过程进行建模。文献[11]给出了CFM（cascading failure model）模型，该模型认为节点和边失效是等价的，都是由过载引发的。文献[15]和文献[16]继承了文献[11]的思想，认为导致级联失效传播的主要因素是负载重分配。三者均没有考虑UPDATE报文级联失效的促进作用，与事实不相符。文献[17]同时考虑了负载重分配和UPDATE报文级联失效的影响，提出DDF-CFM（double damage factor based inter-domain routing system cascading failure model）模型，与本文分析相同，因此，本文在DDF-CFM模型的基础上，进一步分析节点失效后对周围节点产生的影响。

3.2 DDF-CFM模型的运行过程

DDF-CFM模型主要模拟了负载重分配和UPDATE报文在域间路由系统的传播过程，刻画了节点和边的失效过程，还原了级联失效在域间路由系统中的传播过程。利用该模型，可以采集单节点失效后造成的UPDATE报文传播和负载重分配对周围节点和边产生影响大小的基础评估数据，基于该数据结合节点重要性评估模型，可以对节点的重要性进行量化评估。DDF-CFM模型主要工作流程如下。

步骤1 摘除部分节点（或边），触发级联失效过程。

步骤2 判断是否存在失效节点（或边），若不存在，结束；若存在，则进行下一步。

步骤3 找出与失效节点（或边）相邻的所有节点，作为UPDATE报文传播的初始节点，将这些初始节点加入路由转发集

步骤4 判断路由转发集中的节点是否存在节点需要向外发送或转发UPDATE报文信息，需要则进行下一步，不需要则进行步骤7。

步骤5 将接收到UPDATE报文信息的节点加入新的路由转发集1，周围节点接收到UPDATE报文信息后，对其进行解析处理，更新自己的路由信息表和路由转发表。

步骤6 判断是否有新的节点因UPDATE报文过量，导致CPU、内存等资源耗尽失效，如果有，将与之相邻的节点加入新的路由转发集1，重复步骤4~步骤6；若没有，则进行下一步。

步骤7 找出最优路径受到影响的节点和边，依据最优路径选择方法找出新的最优路径，将原有负载加到新的最优路径上。

步骤8 判断负载重分配后，各条边是否过载，过载则失效，将失效边加入失效集中，回到步骤2。

DDF-CFM模型具体运行过程如图2所示。

图2 DDF-CFM模型运行过程

4 基于失效影响的节点重要性评估模型

域间路由系统中节点重要性是由该节点失效后对周围节点产生的影响大小来决定的。由3.1节的分析可知，节点的失效主要对周围节点产生如下两方面影响：1) 导致负载重分配，使其他边负载增加；2) 导致相邻的节点向其周围的节点发送UPDATE报文信息，消耗周围节点的CPU和内存等资源。因此，分别从这两个方面对单个节点失效后对网络的影响程度进行评估。

4.1 负载重分配对边的影响

4.2 UPDATE报文对节点的影响

当节点失效时，与该节点相邻的节点向其周围的节点发送UPDATE报文信息，通报节点失效情况。其他节点接收到报文信息后，对报文信息进行解析，修改自己的路由信息表和路由转发表。之后，判断是否转发该报文。需要，则转发；不需要，则不转发。一个UPDATE报文由节点检测到会话断开而产生，到不再有节点转发而停止。报文的传播过程可以看作节点失效后整个影响过程。主要和两个因素相关，分别是相邻节点的数目以及每个相邻节点产生的UPDATE报文的影响范围。

图3 域间路由系统局部结构示意

4.3 单节点失效对域间路由系统整体影响评估

4.4 关键节点识别方法的评价标准

评价关键节点识别方法好坏的主要思路是将这些方法识别出的关键节点集作为研究对象，通过考察这些节点摘除后对网络结构和功能的影响大小[19]。当基于网络结构属性识别关键节点时，主要通过考察摘除部分节点对整体网络结构的影响，用网络的顽健性和脆弱性来评价方法的好坏。当基于网络的传播动力学过程研究节点的重要度时，主要通过考察部分节点摘除后对失效传播过程的影响来评估方法的好坏，造成节点和边的失效比例越高，说明方法越好。

5 基于传播动力学的域间路由系统关键节点识别过程

5.1 关键节点识别过程

通过前文的分析可知，域间路由系统关键节点识别主要包含两个阶段。首先建立域间路由系统级联失效传播动力学模型，在这个模型的基础上，采集相关的网络数据，利用基于失效影响的节点重要性评估模型，评价各个节点的重要程度。之后，综合比较各个节点的重要程度选出较为关键的节点，具体过程如下。

步骤1 利用真实的网络数据建立基础的网络环境，作为运行DDF-CFM模型的基础。

步骤2 从域间路由系统节点集中选择一个节点，作为摘除节点，输入DDF-CFM模型中。

步骤3 在模型运行过程中，通过记录每一次循环受影响的边和加入路由转发集中的节点以及UPDATE报文，采集负载变化信息和UPDATE报文传播信息。

步骤5 如果域间路由系统节点集中仍有节点没有被选中，重复步骤2~步骤4，直到所有节点都被选中一次。

步骤6 比较各个节点重要性的大小，输出较为重要的节点。

具体过程如图4所示。

5.2 确定最优a值

图4 域间路由系统关键节点识别过程

图5 确定最优a值

图6 节点影响大小分布情况

6 实验验证

为了验证本文方法的有效性和准确性，将本文方法与现有方法和随机选择的方法识别出的关键节点进行对比分析。

6.1 与现有关键节点识别方法对比分析

本节分别选择2001年、2004年、2007年、2010年、2013年、2016年7月的数据集用作对比实验的基础网络环境，验证本文方法与传统方法的优劣。对各年份的数据集进行节点数目的统计分析，不同时期网络中节点的个数随时间的变化关系如图7所示。由图可知，随着时间的推移，域间路由节点的数目不断增加。

图7 节点个数随时间的变化情况

用本文SD-KNI（spreading dynamics based key nodes identification in inter-domain routing system）方法与现有方法和随机选择的方法作对比，现有较好的方法主要包括度中心性法、基于文献[16]提出的IRS-CFM模型的方法和PR-TEAI方法。通过大量的实验发现，仅需要较少关键的节点即可造成较大规模的级联失效，因此用以上方法从不同年份的数据中分别找出域间路由系统中最关键的20个节点。为了排除节点间的组合关系以及特殊节点对实验结果的影响，从选出的不同关键节点集中，分别进行摘除前5、前10、前15和前20个关键节点的域间路由系统级联失效实验，实验结果如图8~图11所示。

由图可知，无论摘除多少个节点，在不同的年份下，本文方法识别出的关键节点，造成的节点和边失效比例比其他方法造成的失效比例高，验证了本文方法的有效性。由图8和图9可知如下结果。1) 在节点集规模不断增大的情况下，摘除节点个数为5和10时，关键节点失效造成的节点和边的失效比随着年份的增加而降低。主要原因是随着时间的推移，域间路由系统节点规模不断增加，每个节点单独的影响范围不断降低。同时，以度中心性作为判断节点重要性的依据相对于其他方法更好，主要原因是度较大的节点，相对于其他方法，其失效后直接影响的节点和路径较多，造成的影响范围较大。2) 通过摘除随机选择的节点造成的节点和边的失效比变化较大，且整体造成的失效比例较低，说明一般的节点能够产生的影响较小，更加凸显关键节点的重要性。

图8 摘除5个节点条件下各方法失效比例分布

图9 摘除10个节点条件下各方法失效比例分布

图11 摘除20个节点条件下各方法失效比例分布

对比本文方法与度中心性的方法实验结果，在摘除20个节点的条件下，本文方法造成的节点和边的失效比例平均高出16.7%，最多高出21.9%。

6.2 摘除节点个数对实验结果的影响

通过对第6.1节的数据分析发现，以2001年7月数据集为环境基础，当选择5个比较关键的节点时，对域间路由系统进行节点摘除实验，可以造成较大范围的级联失效过程。增加失效节点的个数不但没有增加失效节点和失效边的比例，反而降低了，实验数据如图12所示。

图12 失效比例随节点数目变化情况

通过分析比较这些关键节点的网络基础结构发现，当摘除重要度靠前的5个节点时，其分布在域间路由系统的不同区域，节点间不存在紧密的连接关系，造成的级联失效过程具有较大的毁伤效果。当摘除前10、前15、前20和前25个节点时，随着摘除的重要节点的数目增加，部分情况下造成的失效比例不但没有增加，反而有所降低。通过研究后续增加节点的位置以及连接关系发现，后续的部分节点与最初的5个节点存在直接的连通关系，连接关系如图13所示。

图13 域间路由节点连接关系

通过本次实验可以发现，使整个网络达到比较严重的级联失效过程，并不需要大量的节点失效，极少量的关键节点同时失效可以造成较严重的网络瘫痪。因此，找出关键节点，对其进行有针对性的保护具有重要意义。

7 结束语

针对传统关键节点识别方法的不足，本文提出了基于传播动力学的关键节点识别方法，该方法能够更加准确地识别出域间路由系统中的关键节点，为进一步对关键节点实施有针对性的保护提供了重要理论支撑。通过与现有关键节点识别方法对比分析，验证了本文方法的有效性和准确性。实验结果表明，仅需要较少的关键节点就可以造成整个域间路由系统瘫痪。失效节点间的连接关系以及组合关系对级联失效产生的影响，是后续研究工作的重点。

[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] 刘建国, 任卓明, 郭强, 等. 复杂网络中节点重要性排序的研究进展[J]. 物理学报, 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]. 软件学报, 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] 邱菡, 李玉峰, 兰巨龙, 等. 域间路由系统的级联失效攻击及检测研究[J]. 中国科学: 信息科学, 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] 朱会虎, 邱菡, 王清贤, 等. 基于双毁伤因素的域间路由系统级联失效模型[J].计算机工程与应用, 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] 任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 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− ），男，河南商丘人，数学工程与先进计算国家重点实验室博士生，主要研究方向为域间路由系统安全。

邱菡（1981− ），女，湖北随州人，数学工程与先进计算国家重点实验室副教授，主要研究方向为网络空间安全、域间路由系统安全。

朱俊虎（1974− ），男，江苏镇江人，数学工程与先进计算国家重点实验室教授，主要研究方向为网络空间安全。

曾子懿（1989− ），男，湖南祁东人，数学工程与先进计算国家重点实验室博士生，主要研究方向为域间路由系统安全。

TP393.4

A

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

2018−12−11；

2019−02−13

邱菡，qiuhan410@aliyun.com

国家自然科学基金资助项目（No. 61502528,No. 61402525）

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

朱会虎, 邱菡, 朱俊虎, 等. 基于传播动力学的域间路由系统关键节点识别方法[J]. 网络与信息安全学报, 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.