Chinese  |  English

Journal of Tsinghua University(Science and Technology) >

2025 , Vol. 65 >Issue 11: 2221 - 2235

DOI: https://doi.org/10.16511/j.cnki.qhdxxb.2025.27.051

Cybersecurity

SimBlock: Global internet route blocking simulation and detection system

  • Yizhi LI 1 ,
  • Jiang LI 2 ,
  • Jiahao CAO , 1, * ,
  • Yangyang WANG 1 ,
  • Mingwei XU , 1, 2, *
Expand
  • 1. Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing 100084, China
  • 2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

Received date: 2025-04-03

  Online published: 2025-11-07

Copyright

All rights reserved. Unauthorized reproduction is prohibited.
Fold

Abstract

Objective: Route blocking is a newly emerged category of routing threats following the Russia-Ukraine conflict. Unlike conventional routing threats, route blocking constitutes targeted, large-scale network-layer obstruction between regions or even nations, typically affecting extensive areas at regional or national levels. The damage caused by route blocking extends beyond economic losses, potentially triggering political or social instability, thus necessitating effective security measures. However, the vast scope of route blocking poses a challenge to comprehensively analyzing its impact on the real-world Internet. Furthermore, conducting route blocking experiments on the real-world Internet incurs prohibitively high costs and raises a series of ethical concerns. Consequently, conducting an in-depth security analysis becomes difficult, and validating the effectiveness of designed defense measures becomes even more challenging. Methods: To design and validate effective countermeasures against route blocking, this paper proposes SimBlock, a fine-grained global Internet route blocking simulation and detection system that analyzes the characteristic patterns of route blocking through simulation to provide a foundation for security measure design and validation. SimBlock comprises four modules: (1) global Internet topology construction using open third-party topology data, (2) global Internet routing simulation on the established topology, (3) route blocking simulation implementing various blocking techniques based on the designed routing algorithm, and (4) route blocking detection and identification through characteristic analysis. SimBlock is capable of simulating both autonomous system (AS)-level and router-level paths between arbitrary IP addresses. The system additionally supports the simulation of point-to-point packet transmission, ping probing, and traceroute probing, while enabling the granular simulation of dynamic network conditions, including congestion and failures. SimBlock demonstrates comprehensive simulation capabilities of at least five fundamental route blocking methods: DDoS attacks, IP blocking, physical blocking, route hijacking, and business relationship termination. Building upon this foundation, the system has successfully validated a route blocking detection and identification algorithm based on distributed prober triplets, delivering robust security measures to mitigate potential route blocking threats. Results: This paper conducts extensive experiments to validate the effectiveness of SimBlock. The experimental results demonstrate that: (1) even with 47.65% of the routers lacking valid IP addresses in the dataset, SimBlock can simulate valid AS/router-level paths with a 98.94% success rate, proving that the constructed global Internet topology maintains high coverage and excellent connectivity; (2) without prior knowledge of specific AS-routing policies, the AS-level paths simulated by SimBlock achieve an average 61.00% similarity with real-world traceroute paths (reaching over 80% similarity in 16.21% of cases), while the router-level paths maintain an average 42.44% similarity (exceeding 70% in 7.40% of cases) despite 47.65% missing router IPs, confirming that the simulation algorithm accurately captures overall routing trends; (3) for Internet topologies containing over 70, 000 AS nodes, SimBlock maintains millisecond-level latency in AS-level path simulation and handles router-level simulation for approximately 60 million nodes with second-level latency, demonstrating exceptional efficiency in large-scale Internet data processing; (4) across various victim-attacker country combinations, the detection algorithm of SimBlock reliably distinguishes route blocking from normal network failures, and its identification algorithm effectively differentiates between various blocking techniques, validating the effectiveness and universality of the system. Conclusions: In summary, SimBlock provides an effective solution for in-depth analysis of route blocking, while also offering an effective security measure to counter the potential threats posed by route blocking.

Key words： border gateway protocol (BGP); route blocking; routing threat detection; routing simulation

Cite this article

Yizhi LI , Jiang LI , Jiahao CAO , Yangyang WANG , Mingwei XU . SimBlock: Global internet route blocking simulation and detection system[J]. Journal of Tsinghua University(Science and Technology), 2025 , 65(11) : 2221 -2235 . DOI: 10.16511/j.cnki.qhdxxb.2025.27.051

互联网是由不同自治系统(autonomous system，AS) 通过边界网关协议(border gateway protocol，BGP)连接而成的分布式网络系统。不同AS之间通过BGP更新消息(包括BGP通告和BGP撤销)以促进路由和可达性信息的交换；每个AS依据自己的路由策略进行路由转发。
然而，BGP在设计之初缺乏对于安全性的考量，导致互联网上路由威胁事件层出不穷。常见的路由威胁包括源劫持、路径劫持和路由泄露等，每年约有1 000个不同的路由威胁事件被公开报道[1]。导致路由威胁事件的原因可能是恶意攻击，如巴基斯坦电信[2]和KLAYswap[3]遭遇的BGP劫持事件；也可能是管理者的一些错误配置[4]等。这些路由威胁事件所带来的经济损失通常是巨大的。
除了常见的路由威胁之外，在近年的俄乌冲突中还出现了“路由阻塞”这一类新型的路由威胁[5-9]。与一般的路由威胁不同，路由阻塞是地区间甚至国家间针对性的、大规模的网络层阻塞，其影响范围通常是地区级甚至国家级的。路由阻塞所带来的损害不仅是经济损失，更有可能引起政治或社会的动荡，因此亟需有效的安全措施。
然而，路由阻塞造成影响的范围很大，在真实互联网上进行大规模实验的执行难度大且成本高，并且会带来一系列的伦理道德问题。这阻碍了对大规模网络安全性的深入分析以及对相关防御措施有效性的验证。
因此，本文提出一个全球互联网路由阻塞模拟与检测系统SimBlock，通过模拟的方式来分析路由阻塞的典型特征，为安全措施的设计与验证提供更充分的依据。SimBlock是一个细粒度的路由阻塞模拟与检测系统，此系统分为4个模块：首先利用第三方公开的拓扑数据进行全球互联网拓扑搭建；然后在搭建得到的拓扑上进行全球互联网路由模拟，支持任意两IP地址之间的路由转发路径的模拟、具体路由转发行为的模拟，并且支持网络拥塞及网络故障等动态网络运行情况的模拟；再基于所设计的路由模拟算法，进行至少5种不同阻塞手段的路由阻塞模拟；最后通过分析路由阻塞的细粒度特征，设计并验证路由阻塞检测及手段识别方案，为应对路由阻塞的潜在威胁提供了有效的安全措施。

1 背景介绍

1.1 威胁模型

“路由阻塞”本质上是地区级或国家间有针对性的、大规模的网络层阻塞，主要影响的是网络层的连通性。给定受害方CV与攻击方CA，以下介绍5种基础的路由阻塞手段。
1) DDoS攻击。CA对CV的边界路由器或出口链路发起分布式拒绝服务攻击(distributed denial of service，DDoS)，造成CV到达互联网上其他区域出现较高的丢包率。
2) IP阻塞。CA对源IP和/或目的IP属于CV的数据包进行过滤，造成CV到达CA的大面积不可达。
3) 物理阻塞。CA物理破坏CV的边界路由器或物理破坏CV的出口链路，造成CV到达互联网上其他区域的大面积不可达。
4) 路由劫持。CA对CV的IP前缀发起路由劫持，使互联网上大量到达CV的流量被重定向至CA，造成CV到达互联网上其他区域的大面积不可达，具体影响范围由CV和CA在互联网上所处的具体位置所决定。本文仅对互联网的连通性进行考量，因此这里假定CA对劫持到的流量全部进行丢弃处理，而不考虑流量监听、流量拦截等其他复杂情况。
5) 商业关系终止。CA终止与CV的所有互联网商业关系，造成CV到达互联网上其他区域的大面积不可达，具体影响范围由CV和CA在互联网上所处的具体位置所决定。

1.2 相关工作

在路由阻塞的测量与分析方面，Jain等[5]和Luconi等[6]在俄乌冲突发生之后，对乌克兰网络所遭受的影响进行了测量与分析；Ye等[7]分析了不同国际海底电缆的损坏(一种物理阻塞)对互联网带来的影响，并给出了相应的安全措施；Kalra等[8]分析记录了印度政府发起强制网络中断(与路由阻塞等效)的地理分布、时间和理由；Bischof等[9]对政府下令的互联网关闭和自发中断进行了全面的纵向分析，并描述了可用的工具、数据源和分析方法。
在路由威胁的攻击与检测方面，除了路由阻塞之外，常见的路由威胁可以分为3种：源劫持、路径劫持和路由泄露。Birge-Lee等[10]提出通过操控BGP的Community属性来实现流量拦截攻击；RPKI(RFC 6480[11])是应对路由威胁的常用手段之一，Hlavacek等[12]通过破坏RPKI的验证机制，使得攻击者能够绕过RPKI的检查，从而发起路由攻击。路由威胁检测是应对路由威胁的常用且有效的安全措施，Ispy系统通过观察受害者与互联网的连通性缺失来检测路由威胁[13]，Argus系统应用性能监控工具首先对控制平面数据进行分析，检测出可疑的路由威胁，然后再利用数据平面探测的方式进行进一步验证[14]，ARTEMIS系统利用本地配置信息和正常AS链路的双向特性来检测路由威胁[15]；近年来，机器学习模型强大的特征提取能力使其能够作为路由威胁检测的强大工具，基于随机森林等机器学习模型，Themis系统通过分析多起源AS(multiple origin AS，MOAS)冲突的合法性来区分源劫持与正常的MOAS事件[16]；DFOH系统通过分析AS链路的合法性来检测路径劫持[17]；RoLL系统通过AS三元组的主体信息来检测AS路径(AS path)中出现的路由泄露[18]；此外，BEAM系统通过在AS商业关系数据集中进行无监督学习，得到每个AS在互联网上的隐空间表达，来进行零样本的路由威胁检测[19]。
在路由模拟方面，为了定量地分析路由威胁的特征以及其所带来的危害，通常需要对互联网路由进行模拟。Goldberg等[20]提出路由树算法，能够在AS之间的商业关系图中得到任意2个AS之间数据包传输的自治系统粒度路径；此外，Furuness等[21]提出的BGPy工具作为一个开源的、可扩展高效BGP安全模拟器，支持模拟各种BGP攻击和防御，但并不支持路由阻塞的模拟。

2 SimBlock系统概述

SimBlock系统原理图如图 1所示，分为4个模块，首先利用第三方公开的拓扑数据进行全球互联网拓扑搭建；然后在搭建得到的拓扑上进行全球互联网路由模拟；再基于所设计的路由模拟算法，进行多种不同阻塞手段的路由阻塞模拟；最后通过分析路由阻塞的特点，设计并验证路由阻塞检测及手段识别的准确性。
图 1 SimBlock系统原理
1) 全球互联网拓扑搭建。路由阻塞是对于互联网连通性的阻塞，因此对于路由阻塞的模拟需要以互联网拓扑结构为前提。SimBlock分别基于CAIDA AS relationships数据集[22]和CAIDA ITDK数据集[23]各自搭建了全球互联网自治系统粒度的拓扑图和全球互联网路由器粒度的拓扑图。由于互联网上存在部分路由器不响应ICMP(internet control message protocol)报文等原因，CAIDA ITDK数据集存在一定程度的数据缺失，导致搭建的路由器粒度的拓扑图并不是一个连通图，而是存在198个连通分量。针对这一问题，SimBlock首先在每个AS内部分别新增一个对应的“虚拟路由器”，并新增了一系列“虚拟链路”用以连通该AS内部所有其他的路由器，这使得路由器粒度的拓扑图从原始的非连通图转变成了一个连通图，原始的198个连通分量连接在了一起；其次，考虑到自治系统粒度拓扑和路由器粒度拓扑的内在一致性(即都是对全球互联网在拓扑上的描述)，SimBlock对每个在CAIDA AS relationships数据集中存在商业关系，但无法相互直达(即需要通过其他AS间接到达)的AS对，在路由器粒度拓扑上各新增了一条“虚拟链路”，这使得对于任意一条自治系统粒度的路径，都至少能找到一条路由器粒度的路径与其保持一致。这里对于保持一致的要求为：将路由器粒度路径中每个路由器通过其IP地址对应到所属AS，并将重复的AS去除后，与给出的自治系统粒度路径完全相同。至此，SimBlock得到了分别从自治系统粒度和路由器粒度反映全球互联网拓扑结构的2张拓扑图，分别记作GAS和GR。
2) 全球互联网路由模拟。路由阻塞主要影响的是网络层的路由转发行为，因此路由阻塞模拟的核心在于对互联网的路由转发行为进行模拟。为了模拟任意两个AS之间自治系统粒度的路径，SimBlock基于路由树算法[20]在GAS上进行模拟，得到的路径依次满足Local Preference、Shortest Path以及Tie Break等互联网路由的基本原则。为了模拟任意2个路由器之间路由器粒度的路径，SimBlock基于Dijkstra算法[24]在GR上沿着自治系统粒度路径的整体方向对路由器进行最短路径搜索，得到的路径在整体上与自治系统粒度路径保持一致，并且在每个AS内部优先选择最短路径。至此，SimBlock能够对任意2个给定的路由器模拟得到自治系统粒度路径和路由器粒度路径，分别记作PAS和PR，并且在98.94%的情况下二者都是非空的完整路径，仅在1.06%的情况下，基于路由树算法无法模拟得到满足互联网路由基本原则的自治系统粒度路径，导致模拟得到的PAS为空路径，进一步导致PR也为空路径。基于PR，SimBlock进一步在GR上进行单次发包模拟、ping探测模拟以及traceroute探测模拟。
3) 路由阻塞模拟。在全球互联网路由转发模拟的基础上，给定攻击方和受害方，SimBlock分别对DDoS攻击、IP阻塞、物理阻塞、路由劫持和商业关系终止等基础的路由阻塞手段进行细粒度的模拟。这5种路由阻塞手段从不同角度模拟了路由阻塞对互联网带来的影响，其中DDoS攻击、IP阻塞和物理阻塞仅改变网络数据包转发的过程，不改变路由器之间的路径；而在路由劫持或商业关系终止的情况下，到达受害方的路由器粒度路径会发生较大的变化。
4) 路由阻塞检测及手段识别。为了应对路由阻塞带来的潜在威胁，SimBlock通过在全球不同国家或地区分布式地部署多组探针三元组，提取三元组内两两探针之间周期性ping和traceroute探测的结果，来对路由阻塞进行检测及手段识别。这里的探针在实际的互联网上指的是终端可访问互联网的机器，在路由阻塞模拟中指的是GR上的路由器节点。由于路由阻塞是针对性的网络攻击，SimBlock基于各探针三元组内，两两探针之间ping探测的结果，对各探针三元组定义了一个“部分不可达状态”，用以描述该探针三元组覆盖的局部网络是否受到了路由阻塞的影响；由于不同路由阻塞手段对互联网造成影响的方式有明显区别，SimBlock基于各探针三元组内，两两探针之间traceroute探测结果与历史结果的相似度，对各种不同的路由阻塞手段分别定义了一个指示指标和一个相应的阈值，用以衡量各种阻塞手段对该组探针三元组所覆盖的局部网络造成的影响；由于路由阻塞造成的是地区间甚至国家间大面积的网络不可达，SimBlock通过统计处于“部分不可达状态”三元组的数目是否超过预设的阈值，来判断是否发生了路由阻塞；如果判断发生了路由阻塞，SimBlock通过统计各组三元组对于不同阻塞手段的指示指标是否超过对应的阈值，来识别具体的阻塞手段。模拟结果表明，对于多个不同受害方与攻击方的组合，SimBlock所定义的“部分不可达状态”都能够准确地将路由阻塞与互联网上普通的网络故障进行区分，并且三元组内的各指示指标都能够准确地对不同阻塞手段进行区分。

3 全球互联网拓扑搭建

路由阻塞是对于互联网连通性的阻塞，因此对于路由阻塞的模拟需要以互联网拓扑结构为前提。互联网是由单个不同的AS通过BGP连接而成，每个AS内部又有多个不同的路由器相互连通。为了进行路由阻塞的模拟，需要同时搭建自治系统粒度的拓扑和路由器粒度的拓扑。

3.1 自治系统粒度的拓扑

在互联网中，AS是指由一个或多个网络运营商管理的独立网络单元，拥有统一的路由策略。每个AS都有一个唯一的标识号，称为自治系统编号(AS number，ASN)，用于在互联网中识别和路由数据包。通过商业关系推断和额外数据源验证等方式，CAIDA AS relationships数据集[22]以月为周期收集了涉及超过7万个不同AS的共计超过50万条商业关系记录。每条记录给出2个ASN及其对应的商业关系类型。这里具体的商业关系分为peer-to-peer(P2P)或provider-to-customer(P2C)2类。根据这一数据集，SimBlock搭建一个自治系统粒度的层次化互联网拓扑图，记作GAS。在不考虑层次结构的情况下，GAS是一个连通图，所覆盖的AS范围也是相对全面的，因此SimBlock并不对这一数据集进行补充。

3.2 路由器粒度的拓扑

在互联网中，路由器由其所属的AS通过特定的路由策略进行管理和调控。通过主动测量(如traceroute)和被动数据收集等方式，CAIDA ITDK数据集[23]以年为周期收集了约六千万个路由器节点和约六千万条路由器之间的链路信息。其中超过半数的路由器给出至少一个有效的IP地址。基于这一数据集，SimBlock搭建一张路由器粒度的互联网拓扑图。此外，通过RIPE RIS[25]和RouteViews[26]等第三方数据来源给出的路由表，SimBlock得到IP地址与AS/国家的对应关系表FIP，并进一步将给出有效IP地址的路由器映射到其所属的AS/国家。
然而，由于互联网上存在部分路由器不响应ICMP报文等原因，CAIDA ITDK数据集存在一定程度的数据缺失，其中路由器节点部分，存在约45%的路由器节点缺失对应的IP地址；在路由器链路部分，由于数据缺失，搭建的拓扑图并不是一张连通图，而是存在198个连通分量。由于路由阻塞是对互联网连通性的阻塞，非连通的互联网拓扑会影响模拟算法的准确性。针对这一问题，SimBlock给出一个拓扑补全方案。首先，考虑到每个AS内部的路由器应当是连通的，SimBlock在每个AS内部分别新增一个对应的“虚拟路由器”，并新增了一系列“虚拟链路”用以连通该AS内部所有其他的路由器，这使得路由器粒度的拓扑图从原始的非连通图转变成了一个连通图，原始的198个连通分量连接在了一起；其次，考虑到AS拓扑和路由器拓扑的内在一致性(即都是对全球互联网在拓扑上的描述)，SimBlock对每个在CAIDA AS relationships数据集中存在商业关系，但无法在路由器粒度拓扑上相互直达(即需要通过其他AS间接到达)的AS对，各新增了一条“虚拟链路”，这使得对于任意一条自治系统粒度的路径，都至少能找到一条路由器粒度的路径与其保持一致。这里对于保持一致的要求为：将路由器粒度的路径中每个路由器通过其IP地址对应到所属AS，并将重复的AS合并后，与给出的自治系统粒度路径完全相同。至此，SimBlock得到了一张相对完整的路由器粒度的拓扑图，记作GR。

4 全球互联网路由模拟

路由阻塞主要影响的是网络层的路由转发行为，因此路由阻塞模拟的核心在于对互联网的路由转发行为进行模拟。给出起始路由器和目的路由器，模拟算法首先需要得到反映路由转发整体方向的自治系统粒度路径；然后，根据自治系统粒度路径的要求，模拟算法需要得到与自治系统粒度路径保持一致的路由器粒度路径；最后，根据模拟得到的路由器粒度路径，进行动态的路由转发模拟。

4.1 自治系统粒度的路径模拟

自治系统粒度的路径是由AS之间的商业关系所决定的，需要依次满足以下互联网路由的基本原则：
1) Local Preference原则：当到达目的地有多条路径时，AS优先选择客户(customer)方向的路径，其次是对等体(peer)方向，最后选择供应商(provider)方向的路径；
2) Shortest Path原则：当到达目的地有多条Local Preference相同但长度不同的路径时，AS优先选择长度最短的路径；
3) Tie Break原则：当到达目的地有多条Local Preference和路径长度都相同的路径时，AS优先选择下一跳ASN最小的路径。
依据这些原则要求，SimBlock基于路由树算法[20]进行自治系统粒度的路径模拟，算法大致流程如下：给定起始自治系统ASu和目的自治系统ASv，首先在拓扑图GAS上，以ASv为根构造一棵路由树；然后从ASu出发，沿着路由树遍历到ASv，所得到的路径即为所求的自治系统粒度的路径。构造路由树的过程分为3步：首先从ASv出发，沿着所有P2C关系向provider方向进行宽度优先搜索(breadth first search，BFS)，将所有未遍历过的AS加入路由树；然后分别从第一步已遍历到的AS出发，沿着P2P关系进行单次搜索，将未遍历过的AS加入路由树，这里的单次搜索指的是不再从新加入路由树的AS出发进行搜索；最后再分别从前两步已遍历到的AS出发，沿着所有P2C关系向customer方向进行宽度优先搜索，将所有未遍历过的AS加入路由树。
应当指出的是，以上描述的路由树算法是基于BFS进行遍历，并没有引入路径长度的考量，这会导致在第二步和第三步的遍历中，沿着peer/customer方向的不同起点的初始长度存在差异，进而导致算法并不能保证优先选择最短路径，这违背了上述Shortest Path原则。如图 2所示，其中圆圈表示具体的AS，数字表示ASN，AS之间向上为provider，向下为customer，左右互为peer。在此拓扑图上，基于宽度优先搜索的路由树算法从5到1所得到的自治系统粒度路径为 [5, 9, 8, 7, 6, 1]，而路径 [5, 4, 3, 2, 1]在同样满足Local Preference原则的情况下，路径长度更短。为了解决这一问题，需要在构造路由树的过程中记录搜索到的每一个AS到达ASv的路径长度，并将BFS替换成最短路径搜索(或其他考虑到AS层级的优先级搜索)。本文基于Dijkstra算法[24]进行路由树的构造，基于这一算法，能够得到同时满足上述三条路由原则的自治系统粒度路径，记作PAS(ASu, ASv)。
图 2 基于宽度优先搜索的路由树算法举例

注：该例呈现的是所得自治域粒度路径不满足Shortest Path原则。

4.2 路由器粒度的路径模拟

路由器粒度的路径反映了数据包在互联网上更细粒度的传播方向。这一路径不仅需要在AS层面与自治系统粒度的路径保持一致，还需要在每个AS内部满足最优路径的原则。本文对于“最优路径”的模拟不考虑流量和带宽等复杂因素，仅考虑路径长度。具体而言，本文使用“带AS约束的最短路径搜索算法”进行路由器粒度的路径模拟。这一算法的基本流程如下：给定起始路由器Ru、目的路由器Rv以及上一步得到的PAS (ASu, ASv)，基于Dijkstra算法[24]在GR上进行最短路径搜索；每一步的搜索过程中，记当前遍历到的路由器为Rx，每次遍历到可能的下一跳路由器Ry时，判断约束条件ϕ(Rx, Ry) 是否满足，如果满足则将Ry纳入搜索范围；直到首次遍历到Rv时算法结束。沿着Rv逆向回溯到Ru，再将得到的路径逆向处理即可得到所求的路由器粒度路径。应当指出的是，在全球互联网拓扑搭建的过程中，为了补充CAIDA ITDK数据集的缺失而引入了部分的“虚拟路由器”以及对应的“虚拟链路”，而“虚拟链路”选择的优先级应当比“真实链路”更低，因此在最短路径搜索的过程中，SimBlock对每一条“真实链路”赋一个单位1的路径长度，而对每条“虚拟链路”所赋的路径长度为Lmax (Lmax>1)，表示路由器粒度路径的最大长度。这样保证了模拟算法在满足自治系统粒度路径一致性的前提下，优先选择不经过“虚拟链路”的路径。
具体的算法流程如下：记Rx和Ry所对应的AS分别为ASx和ASy，则约束条件ϕ(Rx, Ry) 可表示为
$\phi\left(R_x, R_y\right):\left(\mathrm{AS}_y=\mathrm{AS}_x\right) \vee\left(\mathrm{AS}_y=\operatorname{ne}\left(\mathrm{AS}_x\right)\right) .$
其中：ne(ASx) 表示在PAS (ASu, ASv) 上ASx的下一跳，∨表示逻辑“或”。考虑到CAIDA ITDK数据集中存在约45%的路由器缺失对应的IP地址，因此无法判断其属于哪一个AS。对此，SimBlock将其视为“通配路由器”，当判断约束条件ϕ(Rx, Ry) 时，默认该路由器满足该约束条件。此外，考虑到全球互联网上的路由器数目总量十分庞大(在不同年份的ITDK数据集中约6×107~ 8×107个)，在GR上进行路由器粒度路径模拟的开销可能非常大；而“通配路由器”的引入则更加提高了算法的时间复杂度(即在每一跳AS的搜索过程中都需要对所有“通配路由器”进行搜索)，这严重降低了SimBlock系统的效率。基于这2点考虑，SimBlock将式(1) 的约束条件替换为如下形式：
$\begin{gathered}\phi\left(R_x, R_y\right): \\\left(R_y=R^*\right) \vee\left(\mathrm{AS}_y \in P_{\mathrm{AS}}\left(\mathrm{AS}_u, \mathrm{AS}_v\right)\right) .\end{gathered}$
其中R*表示“通配路由器”，ASy∈PAS (ASu, ASv) 表示ASy出现在PAS (ASu, ASv) 中。这样既保证了当GAS上存在自治系统粒度路径时，任意2个路由器之间都能模拟得到满足自治系统粒度路径一致性要求的路由器粒度路径；又减少了路由器粒度路径模拟的时间开销，从而大大提升了模拟算法的实用性。此处得到的路由器粒度路径记为PR (Ru, Rv)。

4.3 路由转发行为的模拟

给定GR上的起始路由器Ru和目的路由器Rv，PR (Ru, Rv) 为数据包从Ru发往Rv所经过的路由器粒度路径。如果要在GR上进行真实路由转发行为的模拟，还需要考虑到网络拥塞等动态的网络情况。在网络正常的情况下，SimBlock假定从Ru到Rv和从Rv到Ru的路径是对称的，即有PR (Ru, Rv)=rv(PR (Rv, Ru))，其中rv(P) 表示将路径P进行逆向。基于此，SimBlock设计了以下3种具体路由转发行为的模拟方式：
1) 单次发包的模拟send(Ru, Rv)。SimBlock沿着PR (Ru, Rv) 逐跳地进行数据包传输的模拟。每经过一个路由器或一条链路，SimBlock进行一次概率为rR或rL的判定，如果判定成功，则认为在该路由器或链路处出现了丢包，则send(Ru, Rv) 返回“失败”。其中rR、rL分别为网络拥塞等导致的，数据包在路由器、链路上丢失的概率。如果每次判定都失败，则认为此次发包成功，send(Ru, Rv) 返回“成功”。
2) Ping探测的模拟ping(Ru, Rv, Np)。SimBlock连续执行Np次单次发包的模拟函数sendi (Ru, Rv), 1≤i≤Np，并记录每次发包的结果；然后对每次发包成功的情况，执行一次对应的反向发包模拟sendi (Rv, Ru)。ping(Ru, Rv, Np) 返回正反向发包同时成功的次数，即：
$\begin{gathered}\operatorname{ping}\left(R_u, R_v, N_{\mathrm{p}}\right)= \\\sum\limits_N^i \operatorname{send}_i\left(R_u, R_v\right) \wedge \operatorname{send}_i\left(R_v, R_u\right) .\end{gathered}$
其中：Np表示此次ping探测的发包数目，∧表示逻辑“与”。
3) Traceroute探测的模拟tr(Ru, Rv, Nt)。SimBlock沿着PR (Ru, Rv) 逐跳地进行traceroute探测的模拟。具体而言，对PR(Ru, Rv) 路径上出现的每一个路由器Rw，进行一次ping(Ru, Rv, Nt) 探测。如果其返回值不为0，则在该位置记录探测结果为Rw；否则记录一个空路由器。tr(Ru, Rv, Nt) 将路径上每一跳的探测结果作为traceroute路径进行返回，其中Nt为此次traceroute探测每一跳的发包数目。

5 路由阻塞模拟

路由阻塞主要影响的是互联网的路由转发行为，基于第4章中所设计的路由转发模拟算法，SimBlock分别对DDoS攻击、IP阻塞、物理阻塞、路由劫持和商业关系终止等5种基础的路由阻塞手段进行细粒度的模拟。其中DDoS攻击、IP阻塞和物理阻塞仅改变网络数据包转发的过程，不改变路由器之间的路径；而在路由劫持或商业关系终止的情况下，到达受害方的路由器路径会发生较大的变化。路由阻塞是极端的网络攻击行为，其带来的影响是大面积的网络不可达，与之相比，普通网络故障仅影响局部网络的连通性。SimBlock同时对普通网络故障进行模拟。
1) 普通网络故障的模拟。除了网络拥塞等动态网络情况外，硬件故障、软件配置错误等因素也可导致互联网局部网络不可达的情况。这些网络故障通常是不可避免的，并且能在一定时间内自我恢复。分别给定路由器和链路的故障概率r′R和r′L，SimBlock分别以r′R和r′L的概率对GR上的路由器和链路进行故障状态标记，然后对send(Ru, Rv) 函数进行修改，如果PR(Ru, Rv) 上出现了故障状态的路由器或链路，则返回“失败”。其他部分的模拟过程不做修改。
2) DDoS攻击的模拟。在DDoS攻击的情况下，受害方的边界路由器或出口链路表现出较高的丢包率。给定CV，SimBlock对CV的边界路由器或出口链路设置概率为rD的丢包率。并对send(Ru, Rv) 函数进行修改，如果PR(Ru, Rv) 经过CV的边界路由器或出口链路，则需要进行概率为rD的判定，如果判定发生了丢包，则send(Ru, Rv) 返回“失败”。其他部分的模拟过程不做修改。
3) IP阻塞的模拟。在IP阻塞的情况下，攻击方丢弃所有起始IP地址或目的IP地址属于受害方的数据包。给定CA和CV，SimBlock对send(Ru, Rv) 函数进行修改，如果Ru或Rv为属于CV的路由器，且PR(Ru, Rv) 经过CA的路由器，则send(Ru, Rv) 函数返回“失败”。其他部分的模拟过程不做修改。
4) 物理阻塞的模拟。在物理阻塞的情况下，受害方的出口路由器或出口链路被物理破坏。给定CV，SimBlock对send(Ru, Rv) 函数进行修改，如果PR(Ru, Rv) 经过CV的边界路由器或出口链路，则send(Ru, Rv) 函数返回“失败”。其他部分的模拟过程不做修改。
5) 路由劫持的模拟。在路由劫持的情况下，部分AS之间的路由发生改变，需要重新计算对应的自治系统粒度路径PAS (ASu, ASv) 和路由器路径PR(Ru, Rv)。对此，给定CA和CV，SimBlock随机挑选Nw个CA的路由器作为劫持者，对攻击的IP前缀进行全面劫持，并对send(Ru, Rv) 函数进行修改。如果Rv为CV的路由器，则需要判定从Ru发往Rv的路径是否受到路由劫持的影响。假定SimBlock挑选的劫持者为Rw，所属的AS为ASw，且从ASu到ASw的自治系统粒度路径PAS(ASu, ASw) 的优先级比原路径PAS(ASu, ASv) 更高(见第4.1节中互联网路由的基本原则)，则认为从Ru发往Rv的路径受到了路由劫持的影响，此时send(Ru, Rv) 返回“失败”。其他部分的模拟过程不做修改。
6) 商业关系终止的模拟。在商业关系终止的情况下，攻击方终止与受害方的全部互联网商业关系。给定CA和CV，SimBlock将GAS中所有满足ASx属于CA且ASy属于CV的无向边(ASx, ASy) 或(ASy, ASx) 全部断开，然后重新计算PAS(ASu, ASv) 和PR(Ru, Rv)。其他部分的模拟过程不做修改。应当指出的是，商业关系终止可能导致GAS不再是一个连通图，模拟得到的PAS(ASu, ASv) 可能变成空路径。

6 路由阻塞检测及手段识别

如图 3所示，基于分布式探针三元组的路由阻塞检测及手段识别方案(route blocking detection and identification based on distributed prober triplets，RBDI-DPT)在整体上分为3个模块。首先，SimBlock在全球不同国家或地区挑选N组独立的数据平面探针三元组，每组探针两两之间以一个较短的周期进行ping探测以检查局部互联网的连通性情况，同时以一个相对较长的周期进行traceroute探测并保存探测结果以检查局部互联网在拓扑上的具体变化；然后，综合每组探针的ping探测结果，路由阻塞检测算法可以实时地判断是否发生了路由阻塞；最后，如果发生了路由阻塞，综合每组探针的ping和traceroute探测结果，路由阻塞手段识别算法可以准确地识别出路由阻塞所使用的具体手段。以下基于SimBlock所搭建的互联网拓扑分别详述这3个模块。
图 3 路由阻塞检测及手段识别原理

6.1 基于三元组探针的信息探测

为了收集检测路由阻塞所需要的路由信息，SimBlock在全球不同国家或地区挑选N组独立的数据平面探针三元组(pVi, pAi, pOi), 1≤i≤N，其中pVi、pAi和pOi分别表示IP地址属于CV、CA和其他方(CO)的路由器(在实际部署中，路由器可替换为其他可以访问互联网的机器)。这里引入pOi是为了达到对比验证的目的。每组探针内两两探针之间以T1为周期做ping探测以实时地检查局部互联网的连通性情况，以T2为周期做traceroute探测并保存探测到的路径以检查局部互联网在拓扑上的具体变化。考虑到ping探测时延较短，能够迅速地反映局部互联网的连通情况，因此T1的设置应该是一个相对较小的值(例如10 s)；而traceroute探测时延较长，且考虑到互联网拓扑的相对稳定性，因此T2的设置应该是一个相对较大的值(例如5分钟)。这样，每组探针负责探测对应的局部互联网的实时信息，局部信息汇总后用以检测路由阻塞以及区分具体的阻塞手段。
应当指出的是，探针三元组的部署应当尽可能地保证各三元组所维护的traceroute路径之间互不重合，从而避免因信息冗余而带来不必要的计算开销。对此，本章首先定义以下公式来计算2条路径之间的相似度：
$S\left(P_1, P_2\right)=1-\frac{\operatorname{ed}\left(P_1, P_2\right)}{\max \left(L_1, L_2\right)} .$
其中：ed(P1, P2) 表示路径P1与路径P2之间的编辑距离，L1和L2分别为路径P1与路径P2的长度。
基于式(4)，在部署第t (t≥2) 组探针三元组时，以从pVt到pAt的traceroute路径为例，探针三元组内两两探针之间的路径应当满足以下条件：
$\bar{S}=\frac{\sum\limits_{i=1}^{t-1} S\left(\operatorname{tr}\left(p_{\mathrm{V}}^i, p_{\mathrm{A}}^i\right), \operatorname{tr}\left(p_{\mathrm{V}}^t, p_{\mathrm{A}}^t\right)\right)}{t-1} \leqslant \mu_0 .$
其中：tr(x, y) 表示从探针x到探针y的traceroute路径，μ0为预设的接近于0的相似度阈值。

6.2 基于三元组特征的路由阻塞检测

路由阻塞达到的效果应当是受害方与攻击方之间，或者是受害方与其他所有国家或地区之间大面积的网络不可达，而互联网的剩余部分是正常且稳定的。基于这一点，本文定义一个探针三元组的“部分不可达状态”，在该状态下，pVi与pAi之间ping探测不可达，而pOi与pAi之间是可达的。基于式(3)，本小节对“可达性”做如下的定义：
$\frac{\operatorname{ping}\left(x, y, N_{\mathrm{p}}\right)}{N_{\mathrm{p}}} \geqslant \theta_0 .$
其中：x和y为具体的探针或者路由器，θ0为可达性对应的阈值，反映了在网络正常的情况下，ping探测收到回复包概率的最小值。在网络正常的情况下，可达性的取值应当是接近1的。则“部分不可达状态”满足：
$\begin{aligned}& \frac{\operatorname{ping}\left(p_{\mathrm{V}}^i, p_{\mathrm{A}}^i, N_{\mathrm{p}}\right)}{N_{\mathrm{p}}}＜\theta_0 \wedge \\& \frac{\operatorname{ping}\left(p_{\mathrm{O}}^i, p_{\mathrm{A}}^i, N_{\mathrm{p}}\right)}{N_{\mathrm{p}}} \geqslant \theta_0 .\end{aligned}$
记si表示第i个探针三元组所处的状态，取1和0时分别表示处于“部分不可达状态”和“正常状态”。当N个探针三元组中有M0组均处于“部分不可达状态”，即有
$\sum\limits_{i=1}^N s_i \geqslant M_0.$
则可推测发生了路由阻塞。互联网上的随机突发性网络故障也有可能会导致探针三元组的“部分不可达状态”，但是普通的网络故障仅发生在互联网的局部，不会是大面积的网络不可达，因此M0的具体取值应当大于普通网络故障所能达到的最大值。

6.3 基于三元组探测结果的路由阻塞手段识别

当检测到路由阻塞的发生，即处于“部分不可达状态”的探针三元组数目到达阈值M0时，路由阻塞手段识别算法将综合N个探针三元组探测得到的信息对路由阻塞的具体手段进行识别。具体而言，5种常见的路由阻塞手段各有其独特的“指纹”：
1) DDoS攻击。在受到DDoS攻击的情况下，三元组内从pVi到pAi的路径丢包率非常高，但并不会完全断开，即有
$0＜\frac{\operatorname{ping}\left(p_{\mathrm{V}}^i, p_{\mathrm{A}}^i, N_{\mathrm{p}}\right)}{N_{\mathrm{p}}} \leqslant \theta_1 .$
其中：θ1为一个接近0的正值，反映了在受到DDoS攻击的情况下，ping探测收到回复包概率的最大值。当有M1个三元组都满足此条件时，系统识别路由阻塞手段为DDoS攻击。
2) IP阻塞。在受到IP阻塞的情况下，三元组内从pVi到pAi的traceroute路径在CA的边界路由器处发生截断。具体而言，当前路径tr(pVi, pAi) 中不包含属于CA的路由器，并且历史路径tr′(pVi, pAi) 在移除掉所有属于CA的路由器之后，与当前路径保持一个较高的相似度。即有：
$S\left(\operatorname{tr}\left(p_{\mathrm{V}}^i, p_{\mathrm{A}}^i\right), \operatorname{rm}\left(\operatorname{tr}^{\prime}\left(p_{\mathrm{V}}^i, p_{\mathrm{A}}^i\right), C_{\mathrm{A}}\right)\right) \geqslant \mu_1 .$
其中：rm(P, C) 表示移除掉路径P中所有属于C的路由器后得到的剩余路径，μ1为预设的接近于1的相似度阈值。当N组探针三元组中有M2组都满足此条件时，系统识别阻塞手段为IP阻塞。
3) 物理阻塞。在受到物理阻塞的情况下，三元组内从pOi到pVi的traceroute路径在CV的边界路由器处发生截断。具体而言，当前路径tr(pOi, pVi) 中不包含属于CV的路由器，并且历史路径tr′(pOi, pVi) 在移除掉所有属于CV的路由器之后，与当前路径保持一个较高的相似度。即有：
$S\left(\operatorname{tr}\left(p_{\mathrm{O}}^i, p_{\mathrm{V}}^i\right), \operatorname{rm}\left(t r^{\prime}\left(p_{\mathrm{O}}^i, p_{\mathrm{V}}^i\right), C_{\mathrm{V}}\right)\right) \geqslant \mu_1 .$
当N组探针三元组中有M3组都满足此条件时，系统识别阻塞手段为物理阻塞。
4) 路由劫持。在受到路由劫持的情况下，三元组内从pOi到pVi的traceroute路径与历史路径相比表现出明显的分歧。具体而言，当前路径tr(pOi, pVi) 与历史路径tr′(pOi, pVi) 之间的相似度较低，即有：
$S\left(\operatorname{tr}\left(p_{\mathrm{O}}^i, p_{\mathrm{V}}^i\right), \operatorname{tr}^{\prime}\left(p_{\mathrm{O}}^i, p_{\mathrm{V}}^i\right)\right) \leqslant \mu_2 .$
其中：μ2是一个预定义的相似度阈值。当N组探针三元组中有M4组都满足此条件时，系统识别阻塞手段为路由劫持。
5) 商业关系终止。在商业关系终止的情况下，三元组内从pVi到pAi的traceroute路径与历史路径相比表现出明显的分歧。具体而言，当前路径tr(pVi, pAi) 与历史路径tr′(pVi, pAi)之间的相似度较低，即有：
$S\left(\operatorname{tr}\left(p_{\mathrm{V}}^i, p_{\mathrm{A}}^i\right), \operatorname{tr}^{\prime}\left(p_{\mathrm{V}}^i, p_{\mathrm{A}}^i\right)\right) \leqslant \mu_2 .$
当N组探针三元组中有M5组都满足此条件时，系统识别阻塞手段为商业关系终止。
基于以上分析，SimBlock通过以下公式定义一个路由阻塞手段识别的“指示向量” τ：
$\boldsymbol{\tau}=\left[M_1, M_2, M_3, M_4, M_5\right] .$
其中M1~M5是上述的5个识别指标，其两两之间相互独立。基于 τ可以进一步定义具体的路由阻塞手段识别规则，例如基于以下公式取最大参数：
$k=\arg \max\limits _i M_i .$
所得的k最终对应到具体的路由阻塞手段。

7 实验验证

7.1 数据集介绍

为保证SimBlock的可复现性，本章的实验验证均采用第三方公开数据集，为了避免因互联网拓扑变化而带来的实验误差，本章对所有数据集均选取相同时间点的版本。具体而言，本章需要使用的数据集如下：

7.1.1 拓扑数据

本章分别基于CAIDA AS relationships数据集[22]和CAIDA ITDK数据集[23]搭建全球互联网自治系统粒度的拓扑GAS和路由器粒度的拓扑GR。其中AS relationships数据集以月为周期记录了全球AS之间的商业关系；ITDK数据集以年为周期记录了全球的路由器节点和路由器之间的链路信息等。应当指出的是，这2个数据集均是通过对BGP路由数据进行人为推断所得到的，其本身就与真实互联网拓扑存在一定程度的误差。

7.1.2 路由数据

本章基于RIPE RIS[25]和RouteViews[26]上公开的路由数据得到IP地址与AS的映射表FIP。对于可能出现的MOAS情况(MOAS指多个AS同时宣告同一个IP地址的情况，这种情况可能是合法的，也可能是路由源劫持导致的，MOAS的合法性判断并不属于本文的研究范围)，本章并不进行合法性判断，默认选择编号最小的AS，因此FIP是一个一对一的映射关系表。

7.1.3 数据平面探测数据

CAIDA IPv4 Prefix-Probing Traceroute数据集[27]以月为周期记录了从多个不同节点出发，到达全球不同IP前缀的traceroute探测结果。本章使用此数据集作为真实样本以验证全球互联网路由转发模拟算法的准确性。

7.2 全球互联网拓扑搭建算法评估

互联网上各节点之间应当是相互连通的，因此AS/路由器粒度的路径模拟算法在绝大部分情况下都应该得到有效的路径。基于此，本小节随机挑选拓扑上的节点进行自治系统/路由器粒度的路径模拟实验，并通过统计模拟得到的有效路径的比例来评估对应拓扑的完整性。

7.2.1 自治系统粒度的拓扑

基于2023年3月1日的CAIDA AS relationships数据集搭建自治系统粒度的拓扑GAS。该数据集记录了涉及75 240个AS的共计502 545条商业关系记录。基于此数据集搭建得到的GAS本身是一个连通图，但由于GAS是一个层次化的图结构，并不是任意2个AS之间都能找到满足4.1节中提到的Local Preference、Shortest Path和Tie Break等互联网路由基本原则的自治系统粒度路径。对此，本小节对GAS上两两AS之间的连通率进行了测试，结果表明，98.94%的AS对能够通过4.1节中基于最短路径搜索的路由树算法模拟得到满足上述互联网路由基本原则的自治系统粒度的路径，验证了GAS的相对完整性。

7.2.2 路由器粒度的拓扑

基于2023年3月1日的CAIDA ITDK数据集搭建路由器粒度的拓扑GR。该数据集收集了共61 742 502个路由器节点和62 471 438条路由器链路信息记录，其中每条路由器链路信息包含多条路由器之间的链路关系，对应到GR上共计71 098 724条无向边。使用此数据集搭建得到的原始拓扑本身并不是一个连通图，而是具有198个连通分量，对此，本小节使用3.2节提出的方法进行拓扑补全。为了测试补全效果，本小节随机选取了5 000个路由器节点对，并在原始拓扑和补全后的拓扑上进行路由器粒度的路径模拟(见4.2节)。补全后拓扑的连通率从60.54%上升到了99.94%，提升了39.40%。其中连通率的计算方式为，在5 000个路由器节点对中，模拟得到有效路径的数目占总数目的百分比。

7.3 全球互联网路由模拟算法评估

全球互联网路由模拟算法是路由阻塞模拟的前提，其准确性直接影响了路由阻塞模拟的准确性，其模拟时延直接影响了SimBlock系统的实用性。因此，本小节对第4章所设计的路由模拟算法进行准确性和时延的评估。

7.3.1 准确性评估

本小节通过将模拟得到的自治系统/路由器粒度路径与真实互联网上的traceroute结果进行相似度比较，评估路由转发模拟算法的准确性。具体而言，本小节统一选取2023年3月1日的数据进行自治系统粒度拓扑GAS、路由器粒度拓扑GR以及IP地址到AS映射表FIP的搭建，并使用CAIDA IPv4 Prefix-Probing Traceroute数据集[27]上对应月份的traceroute数据作为真实样本与模拟结果进行对比。本小节随机挑选了5 000组样本进行实验评估，其中每组样本包括GR上的一个起始路由器Ru和一个目的路由器Rv。考虑到真实的traceroute数据集中，并不一定存在与Ru/Rv完全相同的起始/目的IP地址，本小节仅保证二者属于相同的/24 IP前缀。
图 4展示了模拟得到的自治系统粒度路径与真实traceroute路径的差异度分布，其中差异度的具体计算流程为：先将traceroute路径中的每个IP地址通过FIP映射到对应的AS，再将映射后的路径去重得到真实的自治系统粒度路径，然后基于式(4)对模拟的自治系统粒度路径和真实的自治系统粒度路径进行相似度S的计算，最终得到差异度为1-S。结果表明，基于最短路径搜索的路由树算法(见4.1节)能够在超过半数的情况下达到与真实情况的约60%的相似度，其在5 000组实验样本上相似度的平均值为61.00%，并且在16.21%的情况下能够达到80%以上的相似度。可能影响到相似度的因素除了路由树算法本身的误差之外，还有CAIDA AS relationships数据集本身的缺失、IP地址到AS映射表存在的误差，以及每个AS路由策略的动态变化等。此外，4.1节中基于最短路径搜索的路由树算法相较于基于宽度优先搜索的路由树算法而言，相似度的平均值提高了6.29%，说明其与真实情况更加符合。
图 4 自治系统粒度路径准确性评估结果
考虑到式(1)的开销过大(单条路由器粒度路径模拟的平均时延约77.48 s)，对于路由器粒度路径的准确性评估本小节默认使用式(2)。考虑到路由器粒度路径的模拟只需要尽可能地保证路径的整体方向与真实情况接近，并不需要保证每一跳的IP地址完全相同，因此此处对于相似度的计算引入一个掩码长度Lmask的考量，具体计算流程为：首先将路由器粒度路径上的每个路由器对应到具体的IP地址(在CAIDA ITDK数据集中给出)，再分别将每个路由器的IP地址和traceroute路径中的每个IP地址进行长度为Lmask的掩码，并分别将掩码后的路径去重，得到模拟的IP前缀路径和真实的IP前缀路径，然后基于式(4)计算二者的相似度。图 5展示了掩码长度为8、16和24的情况下，模拟路径与真实路径在5 000个随机样本下相似度分布的箱状图。结果表明，模拟得到的路由器粒度路径在此3个掩码长度下，与真实情况分别达到46.41%、42.44%和32.83%的平均相似度，并且当掩码长度为16时，在7.40%的情况下能够与真实情况达到70%以上的相似度。可能影响到相似度的因素除了自治系统粒度和路由器粒度的模拟算法本身的误差之外，还有CAIDA ITDK数据集本身的缺失(其中47.65%的路由器缺失IP地址)、互联网拓扑的动态变化以及traceroute数据集本身的测量误差等。
图 5 路由器粒度路径准确性评估结果

7.3.2 时延评估

由于4.3节对于路由转发行为的模拟不涉及全球互联网拓扑上的搜索行为，其时延可忽略不计，本小节仅对基于宽度优先搜索和基于最短路径搜索的自治系统粒度路径模拟算法，以及基于式(1)和式(2)的路由器粒度路径模拟算法进行时延评估。表 1展示了4种算法在500个随机样本上的时延情况，其中基于最短路径搜索的自治系统粒度路径模拟算法相较于基于宽度优先搜索的算法，平均时延从0.07 s上升至0.18 s，仍远低于路由器粒度路径模拟算法的平均时延，因此所增加的开销是可接受的，并且仍能够满足大规模数据的模拟要求；而基于式(1)的路由器粒度路径模拟算法平均时延达到77.48 s，这严重降低了路由阻塞模拟的效率，式(2)对其进行近似优化后，平均时延降低至16.36 s，这在很大程度上增加了路由模拟算法的实用性。
表 1 自治系统粒度和路由器粒度路径模拟算法时延评估结果
最大值/s 最小值/s 平均值/s
自治系统粒度(BFS) 0.10 0.06 0.07
自治系统粒度(SP) 0.24 0.15 0.18
路由器粒度(优化前) 190.15 10.00 77.48
路由器粒度(优化后) 33.53 3.24 16.36

注：BFS和SP分别表示基于宽度优先搜索和最短路径搜索的路由树算法。

7.4 路由阻塞检测及手段识别算法评估

本小节通过具体的模拟实验来评估第6章所设计的路由阻塞检测及手段识别算法的有效性。这里的有效性指的是，能够在模拟的实验环境中，有效地将被检测/识别的状态同其他状态进行区分，从而在一定程度上保证了算法的实用性。为了避免偶然性带来的实验误差，本小节的实验结果均是在使用5个不同的随机数种子进行5次独立实验后所取的平均值。

7.4.1 实验参数设置

本小节对于路由阻塞模拟、检测及手段识别的相关参数设置如下：4.3小节中，正常网络状态下路由器和链路上的丢包率rR=rL=10-3，ping和traceroute探测模拟的发包数目相同(Np=Nt)，具体取值在正常情况下和受到路由阻塞的情况下(增加发包数目以准确识别阻塞手段)分别为5和100；第5章中，普通网络故障下，路由器和链路的故障率r′R=r′L=10-3，DDoS攻击下，受影响的路由器/链路丢包率rD=0.7；第6章中，相似度阈值μ0=0.2，μ1=0.8，μ2=0.5，可达性阈值θ0= 0.6，θ1=0.3，探针三元组总数目N=100。

7.4.2 受害方—攻击方组合的选取

第6章所设计的路由阻塞检测与手段识别方案是一般性的检测方案，并不局限于某2个特定的对象，因此本小节挑选了多组不同的受害方与攻击方的组合进行实验验证。如表 2所示，按照各方在所搭建的路由器粒度拓扑GR上所拥有的路由器总数目进行从高到低的排序，并用Ci (i≥1) 进行排序。
表 2 路由阻塞检测及手段识别算法评估排序
排序 在GR上拥有的路由器总数目(占比)
C1 8 593 836 (13.92%)
C2 4 694 878 (7.60%)
C3 2 882 255 (4.67%)
C6 919 908 (1.49%)
C8 752 815 (1.22%)
C29 148 070 (0.24%)

7.4.3 路由阻塞检测算法有效性评估

路由阻塞检测算法应当有效地将路由阻塞与普通的网络故障进行区分，图 6展示了当C2和C1分别作为受害方和攻击方时，SimBlock在不同网络状态下基于式(7)的处于“部分不可达状态”的探针三元组数目占总数目的比例。结果表明，式(8)能够通过一个预定义的阈值M0来有效地区分路由阻塞与普通的网络故障，验证了路由阻塞检测算法的有效性，其具体取值应当根据网络运行的实际情况来确定。
图 6 路由阻塞检测算法准确性评估结果

7.4.4 路由阻塞手段识别算法有效性评估

路由阻塞手段识别算法应当在检测出路由阻塞的情况下，准确地识别出具体的阻塞手段。本小节分别对五种基础的路由阻塞手段进行了模拟实验，并记录了在不同阻塞手段下，指示向量 τ (见6.3节)的具体取值。表 3展示了分别以C2和C1作为图 1中的受害方和攻击方时，指示向量 τ能够捕捉到不同路由阻塞手段的独有特征，从而能够有效地区分出不同的路由阻塞手段。
表 3 不同阻塞手段下τ的具体取值
τ
DDoS攻击 [100.0, 0.0, 0.0, 0.0, 0.0]
IP阻塞 [0.0, 100.0, 48.0, 6.0, 0.0]
物理阻塞 [0.0, 75.0, 100.0, 28.0, 0.0]
路由劫持 [0.0, 33.6, 0.0, 50.0, 1.4]
商业关系终止 [0.0, 0.0, 0.0, 42.0, 62.0]

注：探针三元组的总数目N的取值均为100。

路由阻塞是两个国家或地区之间针对性的网络阻塞，不同对象之间发起路由阻塞所带来的影响会有所区别，而路由阻塞手段识别算法是一般性的识别算法，不应局限于特定的受害方与攻击方的组合。为了验证这一特性，本小节分别以(C2, C1)、(C6, C3) 和(C29, C8) 作为受害方与攻击方的组合进行路由阻塞模拟实验，并记录对应的指示向量 τ的取值。图 7上的每个点表示对于一个特定的受害方与攻击方组合，在一个特定的路由阻塞手段模拟下，将SimBlock所得到的指示向量 τ进行T-SNE降维后的二维可视化结果(横纵坐标值均经过归一化处理)。如图 7所示，指示向量 τ除了在DDoS攻击下不因组合的不同而改变之外，在其他四种路由阻塞手段下都因不同组合的改变而有所区别，但都能有效地区分出对应的阻塞手段，验证了路由阻塞手段识别算法对不同受害方与攻击方组合的普遍有效性。
图 7 路由阻塞手段识别算法有效性评估结果

8 总结与展望

本文提出一个全球互联网路由阻塞模拟与检测系统SimBlock。SimBlock系统首先基于互联网公开拓扑数据搭建全球互联网自治系统粒度和路由器粒度的拓扑图；然后在所搭建的拓扑图上模拟实际的路由转发过程；基于路由转发模拟，SimBlock系统支持至少5种路由阻塞手段的模拟；最后，基于模拟阶段所得到的路由信息，SimBlock系统验证了一种有效的路由阻塞检测与手段识别方案。经过充分的实验评估，SimBlock系统所搭建的互联网拓扑具有较高的完整性，所设计的路由转发模拟算法与真实情况较为接近，所提出的路由阻塞检测与手段识别方案具有较好的实用性，为应对路由威胁提供了一个有效的解决方案。
值得注意的是，SimBlock系统目前仅针对网络的连通性进行模拟，而实际的互联网运行还需要考虑到网络带宽等复杂情况。在未来的工作中，可以考虑对系统所搭建的路由器粒度拓扑图引入带宽等概念，从而进一步提高路由模拟的真实性。

References

Publishing order | Descend order by publishing year | Descend order by cited within
1
RIPE NCC Academy. Learn online with the RIPE NCC![EB/OL]. [2025-03-01]. https://academy.ripe.net.

2
RIPE NCC. YouTube Hijacking: A RIPE NCC RIS case study[EB/OL]. (2008-03-17)[2025-03-01]. https://www.ripe.net/about-us/news/youtube-hijacking-a-ripe-ncc-ris-case-study/.

3
KLAYswap. KLAYswap Incident Report[EB/OL]. (2022-02-03)[2025-03-01]. https://medium.com/klayswap/klayswap-incident-report-feb-03-2022-70ff124aed6b.

4
Major BGP leak disrupts thousands of networks globally[EB/OL]. (2021-04-17)[2025-03-01]. https://www.bleepingcomputer.com/news/security/major-bgp-leak-disrupts-thousands-of-networks-globally/.

5
JAIN A, PATRA D, XU P J, et al. The Ukrainian internet under attack: An NDT perspective[C]// Proceedings of the 22nd ACM Internet Measurement Conference. Nice, France: Association for Computing Machinery, 2022: 166-178.

6
LUCONI V, VECCHIO A. Impact of the first months of war on routing and latency in Ukraine[J]. Computer Networks, 2023, 224, 109596.

DOI

7
YE H L, WANG S, LI D. Impact of international submarine cable on internet routing[C]// IEEE INFOCOM 2023-IEEE Conference on Computer Communications. New York, USA: IEEE, 2023: 1-10.

8
KALRA A, LEVY R, MATTSSON M. Targeted disruptions: internet shutdowns in India[EB/OL]. Social Science Research Network, (2025-02-14)[2025-03-01]. https://papers.ssrn.com/sol3/papers.cfm?abstract_id=5129468.

9
BISCHOF Z S, PITCHER K, CARISIMO E, et al. Destination unreachable: Characterizing internet outages and shutdowns[C]// Proceedings of the ACM SIGCOMM 2023 Conference. New York, USA: Association for Computing Machinery, 2023: 608-621.

10
BIRGE-LEE H, WANG L, REXFORD J, et al. SICO: Surgical interception attacks by manipulating BGP communities[C]// Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. London, United Kingdom: Association for Computing Machinery, 2019: 431-448.

11
LEPINSKI M, KENT S. An infrastructure to support secure internet routing[R]. San Francisco: IETF, 2012.

12
HLAVACEK T, JEITNER P, MIRDITA D, et al. Stalloris: RPKI downgrade attack[C]// Proceedings of the 31st USENIX Security Symposium. Boston, USA: USENIX Association, 2022: 4455-4471.

13
ZHANG Z, ZHANG Y, HU Y C, et al. Ispy: Detecting ip prefix hijacking on my own[C]// Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication. Seattle, USA: Association for Computing Machinery, 2008: 327-338.

14
SHI X G, XIANG Y, WANG Z L, et al. Detecting prefix hijackings in the internet with argus[C]// Proceedings of the 2012 Internet Measurement Conference. Boston, USA: Association for Computing Machinery, 2012: 15-28.

15
SERMPEZIS P, KOTRONIS V, GIGIS P, et al. ARTEMIS: neutralizing BGP hijacking within a minute[J]. IEEE/ACM Transactions on Networking, 2018, 26(6): 2471- 2486.

DOI

16
QIN L C, LI D, LI R F, et al. Themis: Accelerating the detection of route origin hijacking by distinguishing legitimate and illegitimate MOAS[C]// Proceedings of the 31st USENIX Security Symposium. Boston, USA: USENIX Association, 2022: 4509-4524.

17
HOLTERBACH T, ALFROY T, PHOKEER A, et al. A system to detect forged-origin BGP hijacks[C]// Proceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation. Santa Clara, USA: USENIX Association, 2024: 1751-1770.

18
LI J, CAO J H, MENG Z L, et al. RoLL: real-time and accurate route leak location with AS triplet features[C]// IEEE International Conference on Communications. Rome, Italy: IEEE, 2023: 5240-5246.

19
CHEN Y H, YIN Q L, LI Q, et al. Learning with semantics: Towards a semantics-aware routing anomaly detection system[C]// Proceedings of the 33rd USENIX Conference on Security Symposium. Philadelphia, USA: USENIX Association, 2024: 5143-5160.

20
GOLDBERG S, SCHAPIRA M, HUMMON P, et al. How secure are secure interdomain routing protocols[C]// Proceedings of the ACM SIGCOMM 2010 Conference. New Delhi, India: Association for Computing Machinery, 2010: 87-98.

21
FURUNESS J, MORRIS C, MORILLO R, et al. BGPy: the BGP python security simulator[C]// Proceedings of the 16th Cyber Security Experimentation and Test Workshop. Marina del Rey, USA: Association for Computing Machinery, 2023: 41-56.

22
AS relationships (serial-2)[EB/OL]. (2015-12-01)[2025-03-01]. https://catalog.caida.org/dataset/as_relationships_serial_2.

23
ITDK: Internet topology data kit[EB/OL]. (2010-01)[2025-03-01]. https://catalog.caida.org/dataset/ark_itdk.

24
DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269- 271.

DOI

25
RIPE NCC. Routing information service (RIS)[EB/OL]. [2025-03-01]. https://www.ripe.net/analyse/internet-measurements/routing-information-service-ris/.

26
RouteViews. University of Oregon RouteViews project[EB/OL]. [2025-03-01]. https://www.routeviews.org/routeviews/.

27
Ark IPv4 prefix-probing[EB/OL]. (2015-12-08)[2025-03-01]. https://catalog.caida.org/dataset/ark_ipv4_prefix_probing.

Options
Outlines

/

〈 〉

Postal Code: 100084
Tel: 010-62788108/62771385/62792976/62792994　
E-mail：xuebaost@tsinghua.edu.cn
Powered by Beijing Magtech Co. Ltd.
Visited
    Total visitors:
    Visitors of today:
    Now online:
　
Copyright © Journal of Tsinghua University(Science and Technology)