互联网是一个由近8万个自治系统（AS）组成的网络，它们使用BGP协议相互交换路由可达性信息。然而，BGP协议缺乏路由真实性验证，这使得攻击者可以将虚假路由注入路由系统，达到劫持流量的目的，这就是所谓的BGP路由劫持。路由劫持可以分为源劫持和路径劫持。在源劫持中，攻击者把自己宣告为他人IP前缀的源AS，源劫持通常会引发MOAS（Multi-Origin AS）冲突[1]，即一条前缀对应于多个源AS，现有许多劫持检测系统[2][3][4]均基于MOAS。为了规避MOAS，一些攻击者在宣告IP前缀的同时篡改AS-PATH，这被称为路径劫持。如图1所示，攻击者AS5向AS4宣告受害者AS1的前缀10.0.0.0/16，同时将AS1添加到了AS-PATH末尾，使得其规避了MOAS，但是却引入了未曾见过的虚假链路AS5-AS1。早期的路由劫持主要是由错误配置引起的源劫持，如2008年的巴基斯坦电信劫持YouTube事件[5]和2010年的中国电信劫持事件[6]。然而，在过去的几年里，路径劫持已经成为攻击者青睐的方法，因为它是一种更隐蔽的攻击形式。
目前抵御路由劫持有两种方式。一种是主动预防，通过RPKI[7]、BGPsec[8]和ASPA[9]等技术防止路由劫持。另一种是被动检测, 利用劫持的特征对其进行检测，然后再做出响应。由于前者的部署缓慢，所以后者仍然是目前防御路由劫持的主要方式。源劫持已经得到了广泛的研究，但关于路径劫持的工作较少，而它更隐蔽且更难检测。目前路径劫持检测算法均基于未见链路[2][10]，即直接将BGP更新中过去一段时间内未见过的AS链路作为可疑事件，然后再通过数据平面的ping或者traceroute等探测技术进行验证。它们的问题在于，并非所有未见链路都是攻击者伪造的虚假链路，而且事实上只有极少部分未见链路是由路径劫持导致。因此，这些系统会产生大量不必要的验证开销，使得系统的效率、实时性受到损害。
图1 路径劫持和未见链路
为了解决该问题，本文提出使用链路预测技术评估未见链路的真实性并用于过滤正常的未见链路，基于此，提出并实现了一个实时虚假AS-PATH检测框架Metis。Metis通过构造可靠AS链路库并训练得到链路预测器的方式对未见链路的真实性进行评估，然后再结合虚假AS-PATH的特征进行辅助判断。
链路预测是通过现有可观测的部分网络去推断两个结点是否有可能存在链路的技术。链路预测是一个成熟的研究领域，但是并没有广泛地应用于 AS 拓扑当中。本文从图特征的角度对 AS 拓扑结构的链路可预测性进行一些解释。度数和核数是可以用来衡量一个结点在图中的重要性和中心性[16]的主要特征，图2为使用 2022 年 1 月的 CAIDA AS 连接关系数据集得到的一些图特征统计结果。图2（a）表明，AS 的度数分布仍然遵循 1999 年首次发现的幂律分布 ，图2（b）则表明 AS 拓扑中的度-度负相关性，即具有较大度数的 AS倾向于与具有较小度数的 AS 连接。图2（c）显示了 AS 核数的互补累积分布函数（Complementary Cumulative Distribution Function，CCDF），可以看出核数的 CCDF图近似于幂律分布，这反映了 AS 拓扑的层次性。最后，图2（d）显示，AS 链路倾向于连接具有类似属性的 AS，例如，42.0% 的链路连接来自同一个国家的 AS，69.4%的链路连接来自同一个 RIR 的 AS，83.3% 的 AS 对至少有一个公共邻居。上述结果表明，AS 拓扑结构并不是一个随机网络，其链路存在一定的可预测性。
图2 AS拓扑的图特征
图3 Metis框架
图3显示了Metis的总体架构，Metis有四个关键组件：可靠AS链路库，链路预测器，Type-1规则集和Type-2规则集。
Metis在检测前需要构造可靠AS链路库并训练链路预测器，可靠AS链路指的是不需要验证的可靠真实链路，链路预测器的训练需要借助可靠AS链路。
Metis的检测流程如下。首先，Metis从实时BGP路由数据源（如RIPE live）获取实时BGP UPDATE消息，并从AS-PATH中提取AS链路。接下来，Metis检查链路是否为可靠链路、Type-1链路和Type-2链路。Type-1 链路指的是包含历史未出现的 AS的新增链路，而 Type-2 链路是已知 AS 构成的新增链路。可靠链路无需检验，Type-1链路需要使用Type-1规则集对该链路及对应的AS-PATH进行检测。而对于Type-2链路，首先使用已经训练好的链路预测器输出一个预测值，然后用该预测值和预设的阈值进行比较，如果预测值大于阈值，则该Type-2链路为有效，否则该链路为可疑，然后再用Type-2规则集来获取其可疑程度。如果一个AS-PATH的所有AS链路都是有效的，那么该AS-PATH被标记为有效。如果不是，AS-PATH被标记为可疑的，并输出一个带有可疑链路和匹配规则的事件。
本文使用 CAIDA AS 连接关系数据集的过去 6 个月的并集作为可靠 AS 链路库，使用基于图神经网络的预测器 SEAL[17]作为链路预测算法，我们的实验证明SEAL在对未见链路分类上能达到0.95的准确率和0.98的AUC（受试者工作特征曲线ROC下方的面积大小，Area Under the Curve）。
Type-1 链路包含不在可靠 AS 链路库中的 ASN。这些新出现的 AS 可能由于正常的 BGP 操作或错误的配置和 BGP 劫持而出现。我们使用以下规则来检查无效的 Type-1 链路。
1.该链路包含至少一个在五个RIR的AS注册记录中找不到的AS。通常情况下，一个ASN应该在RIR中注册后才能在互联网上使用。Eugenio等人的测量结果表明，未注册的ASN通常是由错误配置和恶意劫持造成的。
2.链路中包含了IANA规定的不应该出现在互联网上的ASN。管理员可能忘记过滤私有ASN（64512-65534，4200000000- 4294967294），导致它们泄露到互联网。
3.链路中的新AS不是AS-PATH中的最后1跳。我们的测量结果表明，97%的新注册AS以边缘AS的形式出现在互联网上，其余的情况是私有ASN、错误配置、IXP ASN和为兄弟AS传输流量的ASN。
预测值小于预设阈值的链路被输出为可疑 Type-2 链路，Type-2规则用于进一步区分原因和确定可疑程度。对于每个包含可疑链路的AS-PATH，我们首先设定初始可疑分数为0。如果以下规则中的任何1条被成功匹配，则分数增加1：
1.AS-PATH中长度（去除重复AS的AS-PATH）大于预先设定的阈值。在路径劫持中，攻击者需要在AS-PATH中插入ASN，这可能导致AS-PATH发生膨胀。本文建议将阈值设置为全球BGP路由表中1.5~2个平均AS-PATH长度（2021年11月约为4.5跳）。
2.在AS-PATH的末尾有单数字ASN的可疑链路。例如，在AS-PATH “300 200 100 2”中，如果链路 “100-2”是可疑链路，那么该AS-PATH就符合这一规则。这条规则考虑到运营商在进行ASPP操作时，可能会意外地在AS-PATH的末尾引入单数字ASN。（AS 路径预设（AS-PATH Prepending， ASPP）是一种常见的流量工程技术，它将一个 ASN重复多次添加到 AS-PATH中，使得 AS-PATH 长度发生膨胀而降低其优先级。）
3.可疑链路的两个ASN的编辑距离不超过1。与前者相同，错误的配置可能导致这种AS链路。
4.AS-PATH有AS环路，可疑链路处于环路中。AS环路通常是由BGP投毒引起的，环路中的链路通常是虚假的。
5.AS-PATH违反了无谷规则。一些恶意的BGP劫持行为可能会将低Tier的ASN插入AS-PATH中，使其违反无谷规则。
6.AS-PATH导致流量迂回，即流量从一个国家出去，然后又回到这个国家。流量迂回很少见，2021年全球BGP路由表中仅有6%的AS-PATH存在迂回。路径劫持会往AS-PATH中插入AS，通常导致流量迂回。
可疑链路位于AS-PATH的末端，并且该链路是国内链路（两个AS属于同一个国家）。这种情况经常发生在一个边缘AS与一个国内ISP连接的时候，极有可能是误报。
虚假 AS-PATH 和路径劫持在真实的互联网上是罕见的，而且验证虚假 AS-PATH 和路径劫持也是极其困难的工作，所以目前并不存在大规模路径劫持验证数据集。为了评估 Metis，本文人工构建了一个验证数据集。该数据集由正样本（有效 AS-PATH）和负样本（虚假 AS-PATH）构成。我们从 2021 年 11 月 1 日零点的RRC00 的 RIB 中随机选择 7000 条 AS-PATH 作为正样本。对于负样本，本研究考虑产生虚假 AS-PATH 的三种最常见情况：错误配置、路径劫持和 BGP 投毒。
错误配置。为了获得该类型的AS-PATH，首先从 RIB 中抽取 1000 个 AS-PATH，然后在 AS-PATH 的尾部随机添加单数字ASN 和相似 ASN（与源 ASN 编辑距离相差 1 的 ASN）。本文为上述两种类型的错误配置各创建 1000 个负样本，并分别命名为Type-1 错误配置和 Type-2 错误配置。
路径劫持。一般来说，路径劫持产生的无效AS-PATH 可以分为两段：真实段和虚假段。本文沿用 ARTEMIS[15]中提出的术语“Type-N 劫持”来描述不同类型的路径劫持，其中 N 是指虚假段的长度。本文构造 Type-N 劫持 AS-PATH 的方法如下：首先从RIB 中选取一些AS-PATH 作为真实段，然后从另一些 AS-PATH 中提取末尾 N 个 ASN 作为虚假段，最后将真实段和虚假段连接起来作为 Type-N AS-PATH。本文对每个 AS-PATH 只构造一条虚假 AS 链路。本文分别为 Type-1、Type-2 和 Type-3 劫持各创建1000 个样本。
BGP投毒。为了得到该类型 AS-PATH，本文首先在 RIB 中随机选取一些AS-PATH，然后再随机选择 ASN 插入到投毒的 AS-PATH 环路中。本文使用Type-N BGP 投毒区分不同类型的投毒，其中 N 是被插入的 ASN 数目。本文为 Type-1 和 Type-2 BGP 投毒分别创建 1000 个样本。
图4 检测结果
如图4 (a)所示，负样本链路的预测值明显低于正样本链路，对于错误配置和BGP投毒，超过75%的预测值低于0.4，而且Type-2场景的链路要比Type-1低很多。但是对于路径劫持，随着N的增长，链路预测值迅速升高。对于来自正样本中的Type-2链路，50%的预测值接近于1，超过75%的预测值大于0.8。实验暂时将正样本中的所有链路视为真实链路，然后计算不同预测值阈值t下Metis对Type-2链路分类任务的精确率和召回率。因为在正样本中只得到187条Type-2链路，而在负样本中得到了数千条链路，为了使正负样本平衡，实验时从负样本的所有类型的Type-2链路中均匀地选择了总共189条（27*7）链路进行实验，最终结果如图4（b）所示。可以发现，精确率-召回率的曲线在t=0.8附近相交，且当t=0.8时，Metis可以得到约80%的精确率和80%的召回率。所以，实验中我们把阈值t设为0.8时，最终，各类样本的检测结果如表1所示。
表1 检测结果
Metis在检测正样本、错误配置、Type-1劫持和BGP投毒的结果都比较好。但是对Type-2劫持和Type-3劫持的结果不佳。“Type-N劫持”中N是指虚假AS路径段的长度。事实上，攻击者会避免使用大N路径劫持，因为随着N的增长，劫持会因为山谷路径和迂回路径而减少其隐匿性。图4（c）显示，有hegemony valley和国家迂回的AS-PATH的比例随着N的增加而迅速增加。此外，大N的路径劫持将减少传播范围，因为膨胀的AS-PATH降低了其路由的优先级（图4（d）显示平均AS-PATH长度与N正比）,而且由于AS-PATH插入了高Tier的AS，会使得这些高Tier的AS丢弃虚假路由（AS-PATH环路自检机制）。
Metis进行了在线实验，检测了RRC00在2021年整个11月的BGP更新。实验时，为了消除冷启动的影响，我们先让Metis运行1天，然后从11月2日开始计算并检测未见链路。最终，Metis平均每天可以收到161808.2个可靠链路、30个新AS，244.0个Type-1链路（7.3个可疑Type-1链路），以及1321.0个Type-2链路。图5显示了所有Type-2链路预测值的CDF曲线。如果预测阈值t被设置为0.8，那么可疑Type-2链路比例为0.229。最终，Metis过滤了236.7个Type-1链路和1018.5个Type-2链路。
图5 链路预测值分布
由于现有系统直接将所有的未见链路当作可疑事件，导致其需要在数据平面花费大量计算资源用于验证正常的链路。为了解决这一问题，本文提出了一种基于链路预测的链路真实度评估方法，本文从实验上证明了AS链路的可预测性，并基于链路预测实现了一个实时虚假AS-PATH检测系统Metis。Metis能有效地检测错误配置、路径劫持和BGP投毒产生的虚假AS-PATH。不过Metis存在一定的局限性，因为它不能检测到伪造带有真实AS链路的虚假AS-PATH或真实度高的链路。为了解决这个问题，未来计划改变Metis的检测机制，将链路预测值和AS-PATH特征输入给机器模型进行自动分类，未来的工作还包括探索更多可靠AS库构建方法、链路预测算法和Type-1规则。
参考文献
[1] X. Zhao, D. Pei, and L. Zhang, “An analysis of bgp multiple origin as (moas) conflicts,” in Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, ser. IMW ’01. New York, NY, USA: Association for Computing Machinery, 2001, p. 31–35.
[2] X. Shi, Y. Xiang, Z. Wang, X. Yin, and J. Wu, “Detecting prefix hijackings in the internet with argus,” in Proceedings of the 2012 Internet Measurement Conference, 2012, pp. 15–28.
[3] “Bgpmon,” 2021. [Online]. Available: https://bgpstream.com/
[4] “Bgpwatch,” 2021. [Online]. Available: https://bgpwatch.cgtf.net/
[5] “Youtube hijacking: A ripe ncc ris case study,” 2008. [Online]. Available: https://www.ripe.net/publications/news/industry-developments/youtubehijacking-a-ripe-ncc-ris-case-study
[6] “Chinese isp hijacks the internet,” 2010. [Online]. Available: https: //www.bgpmon.net/chinese-isp-hijacked-10-of-the-internet/
[7] Lepinski M, Kent S. An infrastructure to support secure internet routing, RFC6480. 2012.
[8] Lepinski M, Sriram K. BGPSEC protocol specification[J]. RFC8205, 2017.
[9] Azimov A, Bogomazov E, Bush R, et al. BGP AS_PATH Verification Based on Resource Public Key Infrastructure (RPKI) Autonomous System Provider Authorization (ASPA) Objects: draft-ietf-sidrops-aspa-verification-11[R/OL]. Internet Engineering Task Force, 2023. https: //datatracker.ietf.org/doc/draft-ietf-sidrops-aspa-verification/11/
[10] H. Ballani, P. Francis, and X. Zhang, “A study of prefix hijacking and interception in the internet,” ACM SIGCOMM Computer Communication Review, vol. 37, no. 4, pp. 265–276, 2007.
[11] M. Lad, D. Massey, D. Pei, Y. Wu, B. Zhang, and L. Zhang, “Phas: A prefix hijack alert system.” in USENIX Security symposium, vol. 1, no. 2, 2006, p. 3.
[12] Dong Y, Li Q, Sinnott R O, et al. ISP self-operated BGP anomaly detection based on weakly supervised learning[C]//2021 IEEE 29th International Conference on Network Protocols (ICNP). IEEE, 2021: 1-11.
[13] X. Hu and Z. M. Mao, “Accurate real-time identification of IP prefix hijacking,” in 2007 IEEE Symposium on Security and Privacy (SP’07). IEEE, 2007, pp. 3–17.
[14] L. Qin, D. Li, R. Li, and K. Wang, “Themis: Accelerating the detection of route origin hijacking by distinguishing legitimate and illegitimate MOAS,” in 31st USENIX Security Symposium (USENIX Security 22), 2022, pp. 4509–4524.
[15] P. Sermpezis, V. Kotronis, P. Gigis, X. Dimitropoulos, D. Cicalese, A. King, and A. Dainotti, “Artemis: Neutralizing BGP hijacking within a minute,” IEEE/ACM Trans. Netw., vol. 26, no. 6, p. 2471–2486, DEC 2018.
[16] Kong Y X, Shi G Y, Wu R J, et al. k-core: Theories and applications[J]. Physics Reports, 2019,832: 1-32.
[17] M. Zhang and Y. Chen, “Link prediction based on graph neural networks,” Advances in neural information processing systems, vol. 31, 2018.
原文始发于微信公众号（风眼实验室）：基于链路预测的BGP路由路径劫持检测框架
