1. 论文基本信息

1.1. 标题

学习语义：迈向一个语义感知的路由异常检测系统 (Learning with Semantics: Towards a Semantics-Aware Routing Anomaly Detection System)

1.2. 作者

Yihao Chen (陈一浩), Qilei Yin (殷琦磊), Qi Li (李琦), Zhuotao Liu (刘卓涛), Ke Xu (徐恪), Yi Xu (徐轶), Mingwei Xu (徐明伟), Ziqian Liu (刘子乾), Jianping Wu (吴建平)。

隶属机构:

• 清华大学计算机科学与技术系 (Department of Computer Science and Technology, Tsinghua University)
• 北京网络科学与技术研究院 (BNRist, Tsinghua University)
• 中关村实验室 (Zhongguancun Laboratory)
• 清华大学网络科学与网络空间研究院 (Institute for Network Sciences and Cyberspace, Tsinghua University)
• 中国电信 (China Telecom)

1.3. 发表期刊/会议

发表于第 33 届 USENIX 安全研讨会 (33rd USENIX Security Symposium)。 USENIX Security Symposium 是计算机安全领域顶级的学术会议之一，以发表高质量、严谨且具有实际影响力的研究成果而闻名。

1.4. 发表年份

2024 年

1.5. 摘要

边界网关协议 (BGP) 是确保互联网全球连通性的事实上的域间路由协议 (inter-domain routing protocol)。然而，各种原因，例如蓄意攻击或配置错误，都可能导致 BGP 路由异常 (BGP routing anomalies)。传统的 BGP 路由异常检测方法需要网络运营商对路由进行大量的人工调查。尽管机器学习 (machine learning) 已被应用于自动化此过程，但现有技术通常会带来巨大的训练开销（例如大规模数据标注和特征工程），并且只能产生不可解释的结果。为了解决这些局限性，本文提出了一种围绕新型网络表示学习模型 BEAM (BGP sEmAntics aware network eMbedding) 的路由异常检测系统。BEAM 的核心设计是通过整合 BGP 语义 (BGP semantics) 来准确学习互联网中每个自治系统 (AS) 的独特属性（定义为路由角色 (routing role)）。因此，在给定 BEAM 的情况下，路由异常检测 (routing anomaly detection) 简化为在观察到新的路由公告 (route announcements) 时，发现意外的路由角色变化 (routing role churns)。我们实现了路由异常检测系统 (routing anomaly detection system) 的原型，并广泛评估了其性能。基于包含超过 110 亿路由公告记录 (route announcement records) 的 18 个真实 RouteViews 数据集的实验结果表明，我们的系统可以检测所有先前确认的路由异常 (previously-confirmed routing anomalies)，同时每 1.8 亿路由公告 (route announcements) 只引入最多五个误报 (false alarms)。我们还将系统部署在一个大型互联网服务提供商 (ISP) 进行了一个月的真实世界检测。在部署期间，我们的系统在实际环境中检测到 497 个真实异常 (true anomalies)，平均每天只有 1.65 个误报 (false alarms)。

1.6. 原文链接

• 会议链接: https://www.usenix.org/conference/usenixsecurity24/presentation/chen-yihao
• PDF 链接: https://www.usenix.org/system/files/usenixsecurity24-chen-yihao.pdf
• 发布状态: 已正式发表于 USENIX Security Symposium 2024 会议。

2. 整体概括

2.1. 研究背景与动机

2.1.1. 论文试图解决的核心问题是什么？

论文旨在解决 BGP 路由异常 (BGP routing anomalies) 检测中的核心挑战：如何在复杂、动态且缺乏内置安全机制的互联网路由环境中，实现 自动化、实时、高效且可解释 的路由异常检测。

2.1.2. 为什么这个问题在当前领域是重要的？现有研究存在哪些具体的挑战或空白 (Gap)？

• 重要性: BGP 是互联网的基石，但其缺乏内置的认证机制，导致易受各种攻击（如 BGP 劫持 (BGP hijacking)、路由泄露 (route leak)）和配置错误 (misconfigurations) 的影响。这些异常行为可能导致流量劫持 (traffic hijacking)、服务中断 (service outages) 甚至大规模网络不稳定，对互联网的连通性 (connectivity) 和安全性 (security) 构成严重威胁。近年来，涉及数百万美元损失的 BGP 攻击事件层出不穷，凸显了有效检测机制的紧迫性。
• 现有研究的挑战与空白:
  • 传统方法的局限性: 现有基于启发式规则或复杂网络分析的传统检测方法，通常需要网络运营商进行大量的人工调查和专业知识，耗时耗力，难以应对互联网的规模和动态性。
  • 机器学习方法的瓶颈: 尽管机器学习 (machine learning) 已被引入以自动化检测过程，但它们普遍面临以下问题：
    1. 高训练开销: 需要大规模的人工标注数据 (large-scale data labeling) 来训练模型，这在 BGP 异常这种稀有且难以确认的事件中极难获取。
    2. 复杂特征工程: 需要精心设计和提取特征 (feature crafting)，这本身就是一项复杂且耗时的任务，需要深厚的领域知识。
    3. 结果不可解释性: 许多机器学习模型，特别是深度学习模型，通常生成不透明的、难以理解的潜在特征 (uninterpretable results)。这意味着它们可以指出“这里有异常”，但无法解释“为什么是异常”以及“哪个自治系统 (AS) 负责”，这给网络运营商进行故障排查和修复带来了巨大障碍，限制了其实际应用。
  • 安全扩展的部署问题: 针对 BGP 安全性问题，已经提出了 BGPsec、psBGP、S-BGP 等安全扩展和 RPKI 等验证机制。然而，由于兼容性问题、部署复杂性和不完整的部署率，它们的有效性受到限制，无法全面解决所有 BGP 异常问题。例如，RPKI 虽能验证前缀所有权，但无法缓解路由操纵 (route manipulation) 或路由泄露 (route leak) 攻击。

2.1.3. 这篇论文的切入点或创新思路是什么？

本文的创新思路在于提出了一种语义感知 (semantics-aware) 的网络表示学习 (network representation learning) 方法，将 BGP 语义 (BGP semantics) 深度融入到自治系统 (AS) 嵌入 (AS embedding) 过程中，从而学习到每个自治系统 (AS) 可解释的路由角色 (routing role)。通过将异常检测转化为对这些路由角色 (routing role) 意外变化的发现，解决了现有机器学习方法不可解释和高开销的问题。

其核心切入点是：

1. 语义感知嵌入: 不再学习抽象的潜在特征，而是基于 BGP 业务关系 (AS business relationships) 中蕴含的路由策略 (routing policy) 信息，学习能够表征自治系统 (AS) 近邻度 (proximity) 和层级 (hierarchy) 的路由角色 (routing role)。
2. 无监督检测: 避免了对大规模标注数据的依赖，通过检测新路由公告引发的路由角色 (routing role) 的异常变化来识别异常。
3. 可解释性: 路由角色 (routing role) 本身就具有明确的 BGP 语义，其变化可以直接指导网络运营商理解异常的性质和来源。

2.2. 核心贡献/主要发现

2.2.1. 论文最主要的贡献是什么？

1. 提出了 BEAM (BGP Semantics Aware Network Embedding) 模型: 这是首个专门为 BGP 语义设计的网络表示学习模型，能够准确捕捉自治系统 (AS) 的路由角色 (routing role)。它通过在嵌入向量中保留自治系统 (AS) 的一阶近邻度 (first-order proximity)、二阶近邻度 (second-order proximity) 和层级 (hierarchy) 特性，实现了对自治系统 (AS) 路由行为的有效表征。
2. 开发了无监督、可解释的路由异常检测系统: 基于 BEAM 模型，构建了一个无需标注数据和特征工程的路由异常检测系统。该系统通过检测新路由公告导致的路由路径上自治系统 (AS) 路由角色 (routing role) 的意外变化 (churn) 来识别异常，并能提供可解释的结果，便于网络运营商理解和响应。
3. 大规模真实世界数据验证: 在包含超过 110 亿路由公告记录 (route announcement records) 的 18 个 RouteViews 数据集上进行了广泛评估。系统成功检测了所有已确认的历史路由异常 (previously-confirmed routing anomalies)，同时保持了极低的误报率（每 1.8 亿路由公告 (route announcements) 最多 5 个误报）。
4. 真实世界部署验证: 将系统在一个大型互联网服务提供商 (ISP) 进行了为期一个月的真实部署。在处理超过 1.5 亿条实时路由公告 (live route announcements) 后，系统成功检测到 497 个真实异常 (true anomalies)，平均每天仅产生 1.65 个误报 (false alarms)，证明了其在实际操作环境中的有效性和实用性。

2.2.2. 论文得出了哪些关键的结论或发现？

• 将 BGP 语义 (BGP semantics) 深度融入网络表示学习 (network representation learning) 中，能够显著提升路由异常检测的性能和可解释性。
• 自治系统 (AS) 的路由角色 (routing role) 可以通过其近邻度 (proximity) 和层级 (hierarchy) 特性来准确表征，并且这些角色变化是检测 BGP 异常的有效信号。
• 提出的 BEAM 模型在检测所有已确认历史 BGP 异常方面表现出色，同时保持了比现有基线方法更低的误报率。
• 该系统具有实时处理能力，即使在互联网规模的路由数据流下也能保持低运行时开销。
• 系统对噪声自治系统 (AS) 关系数据具有良好的鲁棒性。
• 在大型互联网服务提供商 (ISP) 的真实部署证实了 BEAM 系统的实用性，它能够发现现有安全机制未曾察觉的真实异常，并提供有助于故障定位的解释性结果。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. BGP (Border Gateway Protocol)

边界网关协议 (Border Gateway Protocol - BGP) 是互联网中不同自治系统 (AS) 之间交换路由信息的事实上的域间路由协议 (inter-domain routing protocol)。它是一种 路径向量 (path-vector) 路由协议，不基于最短路径原则，而是基于路由策略 (routing policy) 选择最佳路径。BGP 路由器通过交换 路由公告 (route announcement) 来学习到达不同 IP 前缀 (IP prefixes) 的路径，这些路径以自治系统路径 (AS-path) 的形式记录了流量将经过的自治系统 (AS) 序列。

3.1.2. 自治系统 (AS - Autonomous System)

自治系统 (Autonomous System - AS) 是由单一实体（如互联网服务提供商 (ISP)、大学或大型企业）管理和控制的互联 IP 网络集合。每个自治系统 (AS) 都由一个唯一的 自治系统号 (AS Number - ASN) 标识。自治系统 (AS) 之间通过 BGP 交换路由信息，共同构成了互联网的全球路由拓扑。

3.1.3. 路由公告 (Route Announcement)

路由公告 (Route Announcement) 是 BGP 路由器向其对等体 (peers) 发送的、用于宣告其可达某个 IP 前缀 (IP prefix) 的信息。每个公告都包含一个 AS-path，即到达该前缀 (prefix) 所需经过的自治系统 (AS) 序列，以及其他 BGP 属性 (attributes)。

3.1.4. BGP 异常 (BGP Anomalies)

BGP 异常 (BGP Anomalies) 是指 BGP 路由信息中出现的非预期或错误的状态，通常由配置错误 (misconfigurations)、软件缺陷 (software bugs) 或恶意攻击 (malicious attacks) 引起。它们可能导致流量路由到错误的目的地、被窃听 (eavesdropped) 或被丢弃 (dropped)。常见的 BGP 异常包括：

• BGP 劫持 (BGP Hijacking): 恶意自治系统 (AS) 虚假地宣告它拥有或能够到达某个 IP 前缀 (IP prefix)，而实际上它没有合法权限。这可能导致本应流向合法所有者的流量被重定向到攻击者处。有两种主要形式：
  • 虚假宣告前缀所有权 (falsely claiming the ownership of a prefix): 攻击者宣布一个不属于自己的 IP 前缀。
  • 宣布伪造路径 (announcing fake paths): 攻击者宣布一条通往合法前缀的、更优的（例如，更短的 AS-path）但伪造的路径，以吸引流量。
  • 子前缀劫持 (Subprefix Hijacking): 劫持者宣布合法前缀的一个更具体的子网，由于 BGP 的最长前缀匹配原则，子前缀会被优先选择，从而劫持流量。
• 路由泄露 (Route Leak): 一个自治系统 (AS) 将其从一个对等体 (peer) 或提供商 (provider) 处学习到的路由，违反其既定路由策略 (intended policies) 传播给另一个对等体 (peer) 或提供商 (provider)。这可能导致流量被重定向到非预期的路径，增加延迟 (latency)，甚至造成拥塞 (congestion)。

3.1.5. AS 业务关系 (AS Business Relationships)

自治系统 (AS) 之间通常会建立正式或非正式的 业务关系 (Business Relationships)，这些关系指导了 BGP 路由策略 (routing policies) 的制定。主要有三种类型：

• 提供商-客户 (Provider-to-Customer - P2C): 客户 (customer) 自治系统 (AS) 为获得互联网连通性 (Internet connectivity) 而向提供商 (provider) 自治系统 (AS) 付费。提供商 (provider) 会向客户 (customer) 宣告所有它能到达的路由，并从客户 (customer) 处学习其路由，再将其宣告给其他提供商 (provider) 和对等体 (peer)。
• 客户-提供商 (Customer-to-Provider - C2P): 这是 P2C 的逆向关系。
• 对等体-对等体 (Peer-to-Peer - P2P): 两个自治系统 (AS) 免费相互交换它们客户 (customer) 的路由。它们通常不会将从一个对等体 (peer) 学到的路由宣告给另一个对等体 (peer) 或提供商 (provider)。
• Gao-Rexford 模型 (Gao-Rexford Model): 描述了 BGP 路由传播的限制，其中核心是 “无谷 (valley-free)” 原则：一个自治系统 (AS) 接收到的路由，如果来自客户 (customer)，可以宣告给提供商 (provider)、对等体 (peer) 或其他客户 (customer)；如果来自对等体 (peer)，可以宣告给客户 (customer)；如果来自提供商 (provider)，也只能宣告给客户 (customer)。违反这个原则（例如，将从提供商 (provider) 学到的路由宣告给另一个提供商 (provider) 或对等体 (peer)）通常被视为路由泄露 (route leak)。

3.1.6. 网络表示学习 (Network Representation Learning - NRL)

网络表示学习 (Network Representation Learning - NRL)，也称为网络嵌入 (Network Embedding)，是一种将网络中的节点 (nodes)、边 (edges) 或整个图 (graph) 映射到低维连续向量空间 (low-dimensional continuous vector space) 的技术。这些向量通常被称为 嵌入向量 (embedding vectors)。NRL 的目标是在嵌入空间中保留网络的结构、属性和语义信息，使得相似的节点在向量空间中也彼此接近。这些学习到的嵌入向量 (embedding vectors) 可以作为特征用于各种下游任务，如节点分类 (node classification)、链接预测 (link prediction) 和异常检测 (anomaly detection)。

3.2. 前人工作

3.2.1. 传统路由异常检测方法

传统方法通常依赖于预设的规则和对路由数据的深入分析：

• 控制面 (Control-plane based) 方法 [11, 17, 18]: 维护每个前缀的正常/权威路由信息，检查新接收的路由是否与此信息矛盾。例如，ARTEMIS [11] 通过部署分布式监控器，利用路由注册表 (IRR) 和 RPKI 数据，实时检测并缓解 BGP 劫持。
• 数据面 (Data-plane based) 方法 [9, 14, 16]: 通过分析从多个主机到目标前缀的可达性 (reachability) 来识别路由异常。例如，iSpy [16] 通过周期性地向目标前缀发送探测包 (probe packets)，观察路径的变化来检测劫持。
• 混合方法 (Hybrid methods) [10, 12, 13, 15]: 结合控制面和数据面信息以提高检测的准确性和鲁棒性。
• 局限性: 这些方法通常需要大量人工调查、维护权威路由信息或部署大规模网络探测设施，导致 操作开销巨大 (unacceptable operation overhead)。

3.2.2. 机器学习 (ML) 基于路由异常检测方法

近年来，机器学习 (machine learning) 被应用于自动化 BGP 异常检测：

• AV (Shapira et al. [28]): 使用无监督词嵌入 (unsupervised word embedding) 技术来建模 BGP 路由。它将路由路径中的自治系统 (AS) 序列视为“句子”，并学习自治系统 (AS) 的嵌入表示。通过比较新的路由公告与已知正常路由的相似性来检测异常。
  • 缺点: 依赖于路由信息库 (RIB) 快照 (RIB snapshots)，无法检测在两个快照之间发生的瞬态异常 (transient anomalies)。此外，需要频繁重训练 (retraining) 以适应路由变化，导致显著的重训练开销 (retraining overheads)。
• LS (Dong et al. [22]) 和 Hoarau et al. [27]: 将 BGP 数据视为时间序列 (time series)，并应用监督分类 (supervised classification) 模型来识别异常时间段。
  • 缺点: 需要大规模的标注数据集 (large-scale labeled datasets) 进行训练，这在 BGP 异常这种稀有事件中很难获取。LS 虽然使用了弱监督学习 (weakly supervised learning)，但仍需要大量的 BGP 异常事件数据。
• 其他 ML 方法: 许多方法关注于提取 BGP 属性 (attributes) 的特征，然后使用分类器 (classifiers) (如决策树 (decision trees), 支持向量机 (SVMs), 神经网络 (neural networks)) 进行异常检测 [19-21, 23-26, 29]。
  • 共同缺点:
    • 大规模数据标注和特征工程: 需要大量人工工作来标注数据和设计有效特征。
    • 结果不可解释性: 许多模型学习深层潜在特征 (deep latent features)，导致其检测结果对网络操作员来说是“黑箱 (black-box)”，难以提供具体的故障排查指导。

3.2.3. 网络表示学习 (NRL) 的应用

网络表示学习 (NRL) 已在多个领域展现出强大的能力：

• 社交网络分析 [58]: 用于社区检测、用户行为预测等。
• 推荐系统 [59]: 用于学习用户和物品的表示，提高推荐准确性。
• 异常检测 [60]: 在金融欺诈、恶意软件检测等领域，通过识别嵌入空间中的离群点来发现异常。
• 本文的贡献: BEAM 是第一个专门将 BGP 语义 (BGP semantics) 深度整合到网络表示学习 (NRL) 框架中，用于路由异常检测的模型，旨在解决现有方法的解释性 (interpretability) 和训练开销 (training overhead) 问题。

3.3. 技术演进

BGP 异常检测领域的技术演进经历了从早期的人工分析和基于规则的系统，到利用控制面和数据面信息进行综合判断，再到近年来兴起的机器学习 (machine learning) 和深度学习 (deep learning) 自动化方法。

• 早期阶段 (人工/规则): 主要依赖网络工程师的经验和对 BGP 路由表的持续监控，以及基于简单规则（如 AS-path 长度、起源自治系统 (origin AS) 合法性）的检测。这种方式效率低下且难以扩展。
• 中间阶段 (控制面/数据面): 随着路由监控工具的发展，研究者开始利用大规模 BGP 路由数据（如 RouteViews, RIPE RIS）和网络探测数据（如 traceroute）来构建更复杂的检测系统。这些系统能够识别更精细的异常模式，但通常仍需要预设阈值或人工干预，且在应对未知攻击时存在局限。
• 当前阶段 (ML/DL): 机器学习 (machine learning) 和深度学习 (deep learning) 的兴起为 BGP 异常检测带来了自动化和模式识别的能力。然而，如前所述，这些方法面临标注数据稀缺、特征工程复杂和结果不可解释性的挑战。
• 本文的位置: 本文的工作 BEAM 代表了该领域的一个重要进展，它试图弥合机器学习的自动化能力与网络运维对可解释性的需求之间的鸿沟。通过将 BGP 语义 (BGP semantics) 融入网络表示学习 (network representation learning)，BEAM 提供了一种在保持自动化和高效性的同时，能够生成有意义、可解释的检测结果的新范式，从而克服了纯数据驱动机器学习模型的“黑箱”问题。

3.4. 差异化分析

本文提出的 BEAM 模型和检测系统与现有方法的关键区别和创新点在于：

1. 语义感知嵌入 (Semantics-Aware Embedding):

   • 现有 ML 方法: 大多学习抽象的、不透明的潜在特征 (latent features)，其含义难以直接与 BGP 路由行为关联，导致结果不可解释。
   • BEAM: 明确地将 BGP 语义 (BGP semantics)（如自治系统 (AS) 业务关系 (business relationships) 决定的近邻度 (proximity) 和层级 (hierarchy)）融入到网络表示学习 (network representation learning) 的目标函数中，直接学习具有明确含义的路由角色 (routing role)。这使得检测结果具有内在的可解释性 (inherent interpretability)。

2. 无监督学习 (Unsupervised Learning):

   • 现有监督 ML 方法 (LS, Hoarau et al.): 需要大规模的、高质量的标注数据 (labeled datasets) 来训练模型。BGP 异常事件稀少且难以准确标注，这在实践中是巨大的障碍。
   • BEAM: 仅使用相对稳定且易于获取的自治系统 (AS) 业务关系数据 (AS relationship data) 进行模型训练，而无需任何标注的异常数据。检测过程是无监督的，极大地降低了数据准备和模型更新的开销。

3. 实时和瞬态异常检测 (Real-time and Transient Anomaly Detection):

   • AV: 依赖于路由信息库 (RIB) 快照 (RIB snapshots)，可能无法捕捉到在快照间隔之间发生的瞬态、短命的路由异常 (transient anomalies)。
   • BEAM: 直接处理实时路由公告 (real-time route announcements) 流，能够捕捉并检测到瞬态和长期的路由异常，提高了检测的及时性。

4. 低训练和更新开销 (Low Training and Update Overhead):

   • AV 和 LS: 需要频繁地对大型 BGP 数据集（如 RIB entries 或时间序列）进行重训练，开销大。
   • BEAM: 主要依赖相对稳定的自治系统 (AS) 业务关系数据 (AS business relationship data)，其更新频率远低于路由公告。模型训练仅需在自治系统 (AS) 关系发生显著变化时（例如每月一次）进行，且训练时间可接受（约 10 小时）。

5. 综合性能优势: 在检测所有历史确认异常方面，BEAM 显著优于所有对比基线，同时保持了极低的误报率，并在真实世界部署中展现出强大的实用价值。

4. 方法论

本文提出了一种基于 BGP 语义感知网络嵌入模型 BEAM 的路由异常检测系统。BEAM 的核心思想是学习自治系统 (AS) 的路由角色 (routing role) 嵌入向量 (embedding vector)，然后通过检测路由路径上自治系统 (AS) 路由角色 (routing role) 的意外变化 (churn) 来识别异常。整个方法论分为 BEAM 模型和异常检测系统两大部分。

4.1. 方法原理

所用方法的核心思想是：互联网中每个自治系统 (AS) 在路由拓扑中都扮演着独特的角色，这些角色由其与邻居自治系统 (AS) 的业务关系 (business relationships) 所决定。例如，一个提供商 (provider) 自治系统 (AS) 和一个客户 (customer) 自治系统 (AS) 的路由行为和在网络中的地位是截然不同的。传统的路由异常检测方法往往难以捕捉这些细微但关键的语义差异。

BEAM 通过将自治系统 (AS) 嵌入到一个低维向量空间 (low-dimensional vector space) 来量化这些路由角色 (routing role)。关键在于，这个嵌入过程并非简单地学习网络结构，而是深度整合了 BGP 语义 (BGP semantics)。具体来说，BEAM 模型的设计目标是确保学习到的嵌入向量能够同时保留自治系统 (AS) 的近邻度 (proximity)（即连接相似性和邻居相似性）和层级 (hierarchy)（即提供商-客户 (P2C) 关系所体现的上下游关系）。

其背后的直觉 (intuition) 是：

1. 近邻度反映局部路由行为: 路由角色 (routing role) 相似的自治系统 (AS)（例如，同属一个组织或互为备份）通常具有相似的连接模式和邻居集合。

2. 层级反映全局路由地位: 提供商 (provider) 自治系统 (AS) 通常在路由拓扑中处于更高的层级，具有更广的连通性，而客户 (customer) 或末梢 (stub) 自治系统 (AS) 则处于较低层级。

3. 异常表现为角色变化: 在 BGP 劫持 (BGP hijacking) 或路由泄露 (route leak) 等异常事件中，路由路径上的自治系统 (AS) 序列会发生显著变化，往往导致某个自治系统 (AS) 出现在与其正常路由角色 (routing role) 不符的位置，或者整个路径呈现出与合法路径截然不同的路由角色 (routing role) 组合。这种意外的路由角色变化 (unexpected routing role churns)，正是 BEAM 系统检测异常的核心信号。

   通过这种方式，BEAM 不仅能够检测异常，还能通过分析嵌入向量 (embedding vector) 的变化来解释异常的性质，提供比“黑箱”机器学习模型更有价值的洞察。

4.2. 核心方法详解 (BEAM 模型)

BEAM (BGP Semantics Aware Network Embedding) 模型是整个异常检测系统的核心。它首先通过构建自治系统图 (AS Graph) 来表示自治系统 (AS) 之间的业务关系 (business relationships)，然后利用定制的嵌入算法学习每个自治系统 (AS) 的路由角色 (routing role) 嵌入向量 (embedding vector)。

4.2.1. BEAM 概述 (BEAM Overview)

BEAM 模型旨在学习自治系统 (AS) 的路由角色 (routing role)，这些角色能够有意义地表征 BGP 路由公告 (BGP route announcements) 中的自治系统 (AS)，并用于检测互联网路由异常 (Internet routing anomalies)。

工作流程 (参见原文 Figure 2):

1. 输入: 自治系统 (AS) 业务关系 (business relationships) 数据（例如，CAIDA AS relationship dataset）。

2. 构建自治系统图 (AS Graph): 根据输入数据，构建一个有向图 $G=(V, E)$，其中节点 $V$ 是自治系统 (AS)，边 $E$ 表示 P2C (Provider-to-Customer) 关系。

3. 自治系统嵌入 (AS Embedding): 这是 BEAM 的核心。它通过设计两个关键的距离函数来衡量自治系统 (AS) 的路由特性：

   • 近邻度 (Proximity): 衡量自治系统 (AS) 之间连接的相似性以及共享邻居的相似性。如图 2(II.1) 所示，如果两个自治系统 (AS) 直接连接并与许多共同邻居具有相同的业务关系，则它们的近邻度较高（即 p_score 较低）。
   • 层级 (Hierarchy): 衡量自治系统 (AS) 之间的层级差异。如图 2(II.2) 所示，如果一个自治系统 (AS) 必须通过多个连续的 P2C 链接才能到达另一个自治系统 (AS)，则它们之间的层级差异应较大（即 h_score 较高）。
   • 联合优化目标 (Joint Objective): BEAM 设计了一个单一的联合优化目标，同时优化 p_score 和 h_score，并通过负采样 (negative sampling) 来训练模型。

4. 输出: 每个自治系统 (AS) 的嵌入向量 (embedding vector)，这些向量代表了其路由角色 (routing role)。

5. 路由角色差异量化 (Routing Role Difference Quantification): 利用学习到的嵌入向量，定义函数 $D_{l,r}$ 来衡量任意两个自治系统 (AS) 之间的路由角色 (routing role) 差异。较高的 $D_{l,r}$ 值意味着更大的差异。

   关键特性: BEAM 是首个将 BGP 语义 (BGP semantics) 完全整合到训练过程中的专用网络表示学习模型，实现了对自治系统 (AS) 路由角色 (routing role) 的有意义且准确的表示。

以下是原文 Figure 2 的可视化：

该图像是图4，展示了基于BEAM的路由异常检测系统的工作流程，包含在线路由监控、BEAM引擎计算路径差异得分、检测异常路由变化及定位责任AS，最终生成易于理解的报告。

4.2.2. 模型公式 (Model Formulation)

为了形式化地描述 BEAM 模型，论文首先定义了几个基础概念。

定义 1 (自治系统图 - AS Graph): 一个自治系统图 (AS Graph) 是一个有向图 $G = (V, E)$，其中：

• 每个顶点 (vertex) $\nu \in V$ 代表一个自治系统 (AS)。
• 每条有向边 (directed edge) $e = (u, \nu) \in E$ 代表从 $u$ 到 $\nu$ 的提供商-客户 (P2C) 关系。
• 符号解释:
  • $G$: 自治系统图 (AS Graph)。
  • $V$: 顶点集合 (Set of vertices)，表示自治系统 (AS)。
  • $E$: 边集合 (Set of edges)，表示自治系统 (AS) 之间的提供商-客户 (P2C) 关系。
  • $u, \nu$: 图中的两个自治系统 (AS) 顶点。

定义 2 (一阶近邻度 - First-Order AS Proximity): 两个自治系统 (AS) 之间的一阶近邻度 (first-order proximity) 是它们在自治系统图 (AS Graph) 中的配对连接。对于一对顶点 $(u, \nu)$：

• 如果它们通过边 $e = (u, \nu) \in E$ 连接，则一阶近邻度为 1。
• 否则为 0。

定义 3 (二阶近邻度 - Second-Order AS Proximity): 两个自治系统 (AS) 之间的二阶近邻度 (second-order proximity) 是其邻域网络结构 (neighborhood network structures) 的相似性。给定顶点 $u, \nu$：

• 令 $\pmb{p_u} = \langle \pmb{w}_{u,1}, \ldots, \pmb{w}_{u,|V|} \rangle$ 表示自治系统 (AS) $u$ 与其他自治系统 (AS) 的一阶近邻度 (first-order proximity) 向量。
• $u$ 和 $\nu$ 之间的二阶近邻度 (second-order proximity) 基于 $\pmb{p_u}$ 和 $\pmb{p_{\nu}}$ 之间的一致性进行量化。

定义 4 (自治系统层级 - AS Hierarchy): 一个自治系统 (AS) 的层级 (hierarchy) 是其与其他自治系统 (AS) 建立提供商-客户 (P2C) 关系的倾向。对于两个顶点 $u, \nu$：

• 如果存在有向边 $\boldsymbol{e} = (u, \nu)$（即 $u$ 是提供商，$\nu$ 是客户），则从 $u$ 到 $\nu$ 的层级 (hierarchy) 是正的。

定义 5 (自治系统嵌入 - AS Embedding): 给定自治系统图 $G = (V, E)$，自治系统嵌入 (AS embedding) 是将每个顶点 $\nu \in V$ 映射到一个低维向量空间 $\mathbb{R}^d$ 的过程。即，学习一个映射函数 $f_{G; \Theta} : V \to \mathbb{R}^d$，其中：

• $\Theta$ 包含可学习参数 (learnable parameters)。
• $d \ll |V|$ (嵌入维度远小于顶点数量)。
• 符号解释:
  • $\mathbb{R}^d$: $d$ 维实数向量空间。
  • $f_{G; \Theta}$: 映射函数，将自治系统 (AS) 映射到其嵌入向量。
  • $\Theta$: 模型的可学习参数集合。
  • $d$: 嵌入向量的维度。
  • $|V|$: 图中自治系统 (AS) 的总数量。

定义 6 (BGP 语义感知网络嵌入 - BGP Semantics Aware Network Embedding): 给定自治系统 (AS) 关系，BEAM 模型构建自治系统图 $G = (V, E)$ 并执行自治系统嵌入 (AS embedding)，使得学习到的嵌入向量 $\pmb{x} = \{ \pmb{x_{\nu}} | \nu \in V, \pmb{x_{\nu}} = f_{G; \pmb{\theta}}(\nu) \}$ 保留自治系统 (AS) 的一阶近邻度 (first-order proximity)、二阶近邻度 (second-order proximity) 和层级 (hierarchy)。

• 符号解释:
  • $\pmb{x}$: 所有自治系统 (AS) 嵌入向量的集合。
  • $\pmb{x_{\nu}}$: 自治系统 (AS) $\nu$ 的嵌入向量。

4.2.3. 自治系统图构建 (AS Graph Construction)

BEAM 训练的第一步是构建自治系统图 (AS Graph)。

• 数据来源: 论文使用真实的 CAIDA AS relationship dataset [36]。该数据集记录了自治系统 (AS) 之间的业务关系 (business relationships)。
• 关系类型及图表示:
  • 业务关系三元组: 数据集中的每个业务关系表示为一个三元组 $(u, \nu, t)$，其中 $u$ 和 $\nu$ 是两个自治系统号 (ASN)，$t \in \{ \mathrm{P2P, P2C, C2P} \}$ 表示关系类型。
  • 图的边添加规则:
    • 如果 $t = \mathrm{P2C}$ (提供商-客户)，则添加一条有向边 $\boldsymbol{e} = (u, \nu)$ 到边集 $E$。
    • 如果 $t = \mathrm{C2P}$ (客户-提供商)，则添加一条有向边 $\boldsymbol{e} = (\nu, u)$ 到边集 $E$。
    • 如果 $t = \mathrm{P2P}$ (对等体-对等体)，则添加两条有向边 $\boldsymbol{e} = (u, \nu)$ 和 $\boldsymbol{e}' = (\nu, u)$ 到边集 $E$。
• 构建理由: 自治系统 (AS) 的业务关系是决定其如何更新从邻居接收的路由路径以及如何传播新生成的路由公告 (route announcements) 的主要因素 [30]。因此，它直接影响自治系统 (AS) 的路由角色 (routing role)。此外，业务关系相对稳定且数据噪声较少。

4.2.4. 自治系统嵌入 (AS Embedding)

在构建好自治系统图 (AS Graph) 后，BEAM 将自治系统 (AS) 嵌入到一个向量空间，同时保留其近邻度 (proximity) 和层级 (hierarchy) 特性。为此，设计了两个距离函数。

近邻度距离 (Proximity Distance) - p_score: p_score 建模自治系统 (AS) 之间的一阶近邻度 (first-order proximity)。较小的距离意味着较高的近邻度。

• 公式: $$p\_score(u, \nu) = (\pmb{x_{\nu}} - \pmb{x_u})^{\top} \big( (\pmb{x_{\nu}} - \pmb{x_u}) \odot \pmb{l} \big)$$
• 符号解释:
  • $u, \nu$: 两个自治系统 (AS) 的顶点。
  • $\pmb{x_u}, \pmb{x_{\nu}} \in \mathbb{R}^d$: 分别是自治系统 (AS) $u$ 和 $\nu$ 的嵌入向量 (embedding vectors)。
  • $\pmb{l} \in \mathbb{R}^d$: 一个可学习的权重向量 (learnable weight vector)，用于 $d$ 个维度分量。它将嵌入向量投影到旨在保留近邻度 (proximity) 的子空间 (subspace) 中。
  • $\top$: 矩阵转置 (matrix transpose)。
  • $\odot$: 哈达玛积 (Hadamard product)，即两个向量对应元素的乘积。
• 目的: BEAM 通过优化学习 $\pmb{x}$ 和 $\pmb{l}$，以减小有边连接的两个顶点之间的 p_score，同时增大没有直接连接的两个顶点之间的 p_score。这种训练策略也会隐式地保留二阶近邻度 (second-order proximity)。

层级距离 (Hierarchy Distance) - h_score: h_score 量化自治系统 (AS) 之间的层级差异 (hierarchical difference)。

• 公式: $$h\_score(u, \nu) = (\pmb{x_{\nu}} - \pmb{x_u})^{\top} \pmb{r}$$
• 符号解释:
  • $u, \nu$: 两个自治系统 (AS) 的顶点。
  • $\pmb{x_u}, \pmb{x_{\nu}} \in \mathbb{R}^d$: 分别是自治系统 (AS) $u$ 和 $\nu$ 的嵌入向量 (embedding vectors)。
  • $\pmb{r} \in \mathbb{R}^d$: 一个可学习的单位向量 (learnable unit vector)，指示层级下降的方向。它将嵌入向量投影到旨在保留层级 (hierarchy) 的子空间 (subspace) 中。
• 目的: BEAM 通过优化学习 $\pmb{x}$ 和 $\pmb{r}$，以增大具有有向边（即 P2C 关系）的两个顶点之间的 h_score，同时减小没有直接连接的两个顶点之间的 h_score。对于 P2P 关系，由于存在方向相反的两条边，它们的 h_score 将趋近于零，这符合 BGP 语义中对等自治系统 (AS) 通常处于同一层级的理解。

训练目标 (Training Objective): 为了确保训练后的 BEAM 同时保留近邻度 (proximity) 和层级 (hierarchy)，论文将这两个距离函数整合为一个统一的评分函数。

• 评分函数 score(u, v): $$score(u, \nu) = - p\_score(u, \nu) + h\_score(u, \nu)$$ 由于小的 p_score 意味着高近邻度 (proximity)，大的 h_score 意味着高层级差异，因此减去 p_score 使得 score 函数随着自治系统 (AS) 在近邻度 (proximity) 和层级 (hierarchy) 方面差异的增大而单调增加。
• 优化问题: 根据定义 2 和 4，对于一个观测到的边 $(u, \nu) \in E$ 和一个不存在的边 $(u', \nu') \notin E$，模型应该分配 $score(u, \nu) > score(u', \nu')$。为此，优化问题被 формулируется 为最小化以下损失函数： $$\arg \min_{\pmb{x}, \pmb{l}, \pmb{r}} L = \sum_{\substack{(u, \nu) \in E \\ (u', \nu') \notin E}} - \log \sigma (score(u, \nu) - score(u', \nu'))$$
• 符号解释:
  • $L$: 要最小化的目标函数 (objective function)。
  • $E$: 自治系统图 (AS Graph) 的边集。
  • $\sigma(z) = \frac{1}{1 + \exp(-z)}$: sigmoid 函数，将输入映射到 (0, 1) 区间，用于表示概率。
  • $(u, \nu) \in E$: 观测到的真实边。
  • $(u', \nu') \notin E$: 负样本，即不存在的边。
  • 最小化此损失函数，旨在使真实边的 score 高于负样本边的 score。
• 实现细节:
  • 通过一个全连接神经网络 (fully connected neural network) 求解此问题。
  • 神经网络包含一个嵌入层 (embedding layer) 用于生成自治系统 (AS) 的嵌入向量 $\pmb{x}$。
  • 两个线性层 (linear layers) 分别用于学习权重向量 $\pmb{l}$（保留近邻度 (proximity)）和单位向量 $\pmb{r}$（保留层级 (hierarchy)）。
  • 负采样 (Negative Sampling): 对于每条真实边 $(u, \nu) \in E$，采样 10 个负样本（不存在的边）$(u', \nu') \notin E)$。
  • 优化器: 使用随机梯度下降 (SGD) [38] 优化网络。
  • 超参数: 嵌入维度 $d=128$，训练 1000 轮 (epochs)，批次大小 (batch size) 为 1024，初始学习率 (initial learning rate) 为 $10^{-5}$。

计算配对自治系统差异 (Computing Pairwise AS Difference) - $D_l,r$: 一旦 BEAM 模型训练完成，就可以使用其学习到的参数 $(\pmb{x}, \pmb{l}, \pmb{r})$ 来量化任意两个自治系统 (AS) 在路由角色 (routing role) 上的差异。

• 公式: $$\begin{array}{rcl} D_{l,r}(u, \nu) & = & |p\_score(u, \nu)| + |h\_score(u, \nu)| \\ & = & \underbrace{(\pmb{x_{\nu}} - \pmb{x_u})^{\intercal} ((\pmb{x_{\nu}} - \pmb{x_u}) \odot \pmb{l})}_{\text{the first-order proximity}} + \underbrace{|(\pmb{x_{\nu}} - \pmb{x_u})^{\intercal} \pmb{r}|}_{\text{the hierarchy}} \end{array}$$
• 解释: 这个差异函数直接反映了一阶近邻度 (first-order proximity) 和层级 (hierarchy)。论文在附录 A 中证明，该函数也能够保留自治系统 (AS) 之间的二阶近邻度 (second-order proximity)。因此，$D_{l,r}(u, \nu)$ 综合捕捉了两个自治系统 (AS) 在路由角色 (routing role) 上的所有关键差异。

4.2.5. 嵌入结果分析 (Embedding Results Analysis)

为了验证 BEAM 学习到的嵌入向量 (embedding vectors) 确实反映了自治系统 (AS) 的路由特性，论文对嵌入结果进行了可视化和定量分析。

• 可视化嵌入向量 (Visualizing Embedding Vectors):
  • 将嵌入向量 (embedding vectors) 投影到 3D 空间进行可视化 (参见原文 Figure 3(A))。
  • Z 轴 (层级): 利用可学习的单位向量 $\pmb{r}$（代表层级下降方向），将每个嵌入向量 (embedding vector) 在 $\pmb{r}$ 上的投影长度作为 Z 轴坐标，表示自治系统 (AS) 的层级水平。
  • XY 轴 (近邻度): 将嵌入向量 (embedding vector) 在与 $\pmb{r}$ 正交的平面上的投影（即拒绝，rejection），使用 t-SNE [39] (一种降维方法) 进一步降维到 2D 空间，作为 X 和 Y 轴坐标。
  • 观察 (Figure 3(A), (B)):
    • 少数自治系统 (AS) （顶级和最低层级）密集聚集，表示其路由角色 (routing role) 相似（高近邻度）。
    • 大多数中等层级的自治系统 (AS) 分布稀疏，表示路由角色 (routing role) 多样（低近邻度）。
    • 这与 BGP 现实相符：少数骨干 (backbone) 自治系统 (AS) 提供中转服务，形成“互联网骨干”，具有相似角色；而大量末梢 (stub) 自治系统 (AS) 位于最低层级，形成多个集群；其他自治系统 (AS) 则处于中间层级，角色多样。
• 路由角色分析 (Routing Role Analysis) (Figure 3(C), (D)):
  • 选择典型的自治系统 (AS) 类型进行分析：16 个一级自治系统 (Tier-1 ASes)（如 AT&T），9 个主要但非一级自治系统 (major yet not Tier-1 ASes)（如 Telstra），以及 50 个随机选择的末梢自治系统 (stub ASes)。
  • YZ 平面投影 (Figure 3(C)):
    • 一级自治系统 (Tier-1 ASes) 在最高层级形成密集集群。
    • 主要但非一级自治系统 (major yet not Tier-1 ASes) 形成几个位于相对较低层级的密集集群。
    • 末梢自治系统 (stub ASes) 分散在更低的层级。
    • 这证实了嵌入向量 (embedding vectors) 保留了自治系统 (AS) 的近邻度 (proximity) 和层级 (hierarchy)。
  • XY 平面投影 (Figure 3(D)): 提供另一维度的可视化，进一步揭示近邻度关系。
• 配对自治系统差异比较 (Pairwise AS Difference Comparison) (Figure 3(E), (F), (G)):
  • 通过对不同类型自治系统 (AS) 对（P2P, P2C, 无关系，不同邻居交集，不同 P2C 链接数量）进行采样，计算其路由角色 (routing role) 差异的累积分布函数 (CDF) 曲线。
  • 一阶近邻度 (First-Order Proximity) 验证 (Figure 3(E)):
    • S0 (P2P 关系，低邻居 Jaccard 指数) 具有最小的差异。
    • N0 (无关系，低邻居 Jaccard 指数) 具有最大的差异。
    • H0 (P2C 关系) 介于两者之间。
    • 结果表明 BEAM 成功保留了一阶近邻度 (first-order proximity)。
  • 二阶近邻度 (Second-Order Proximity) 验证 (Figure 3(F)):
    • N1 到 N5 代表邻居交集程度逐渐增加的无关系自治系统 (AS) 对。
    • 结果显示，公共邻居越多（即二阶近邻度 (second-order proximity) 越高），自治系统 (AS) 的路由角色 (routing role) 差异越小。
  • 层级 (Hierarchy) 验证 (Figure 3(G)):

    • S1 (直接 P2P 链接) 和 H1 到 H6 (2 到 6 个连续 P2C 链接)。

    • 路由角色 (routing role) 差异随着连续 P2C 链接数量的增加而增大，这与自治系统层级 (AS hierarchy) 的性质一致。

      以下是原文 Figure 3 的可视化：

      该图像是图表，展示了异常和合法路由变化的路径差异评分的累计分布函数（CDF）在多个案例中的统计比较，横轴为路径差异评分，纵轴为CDF，曲线分别用橙色和蓝色表示异常和合法变化。

4.3. 异常检测系统

本节详细介绍基于 BEAM 模型构建的路由异常检测系统。

4.3.1. 系统概述 (System Overview)

该系统旨在检测全球规模的互联网路由异常 (global-scale Internet routing anomalies)。

系统架构 (参见原文 Figure 4): 系统由三个主要组件构成：

1. 路由监控器 (Routing Monitor):
   • 建立与全球视点 (global vantage points) 的连接，例如 RouteViews 或内部 BGP 路由器。
   • 实时捕获路由变化 (route changes)，包括新的路由公告 (route announcements) 或现有路由的撤销 (withdrawals)。
2. BEAM 引擎 (BEAM Engine):
   • 接收路由监控器 (routing monitor) 捕获的路由变化 (route changes)。
   • 利用预训练的 BEAM 模型计算这些路由变化 (route changes) 对应的 路径差异得分 (path difference scores)。这个得分量化了新路由路径与原始路由路径之间路由角色 (routing role) 的差异。
3. 异常检测器 (Anomaly Detector):
   • 基于 BEAM 引擎 (BEAM Engine) 计算的路径差异得分 (path difference scores)。
   • 识别可疑路由变化 (suspicious route changes): 路径差异得分 (path difference scores) 超出预设阈值的变化。
   • 识别异常前缀事件 (anomalous prefix events): 将影响相同 IP 前缀 (IP prefix) 的可疑路由变化 (suspicious route changes) 进行分组。
   • 定位责任自治系统 (responsible ASes): 找出导致异常的自治系统 (AS)。
   • 关联事件 (Correlate Events): 将由相同责任自治系统 (responsible ASes) 引起的不同前缀事件 (prefix events) 进行关联，以形成全面的异常报告。
   • 输出可解释的警报 (interpretable alarms): 报告受影响的前缀 (affected prefixes) 和责任自治系统 (responsible ASes)。

关键特点:

• 无监督 (Unsupervised): 检测系统仅使用自治系统 (AS) 业务关系 (business relationships) 数据进行 BEAM 模型训练，不依赖于标注的路由异常数据 (labeled routing anomaly data)。

• 可解释性 (Interpretable): 通过路由角色 (routing role) 差异来识别异常，可以直接提供给网络运营商有意义的诊断信息。

  以下是原文 Figure 4 的可视化：

  该图像是图表，展示了论文中检测系统的运行时开销。上半部分显示了每15分钟路由数据处理时间，下半部分比较了异常检测器在冷启动和稳定状态下处理每千条路由变化所需时间，反映系统的性能表现。

4.3.2. BEAM 引擎 (BEAM Engine)

BEAM 引擎 (BEAM Engine) 的主要任务是计算路由变化 (route changes) 的路径差异得分 (path difference score)。并非所有路由变化 (route changes) 都表示异常，例如多源自治系统 (MOAS) [41] 引起的合法起源变更。因此，需要一个能够准确区分合法与异常变化的机制。

• 路径差异得分 (Path Difference Score) 计算方法:
  • 核心算法: 动态时间规整 (Dynamic Time Warping - DTW) 算法 [42]。DTW 是一种有效的衡量两个不等长有序序列 (ordered sequences) 整体差异的方法。
  • 应用场景: 对于一个路由变化，我们比较其 原始路由路径 (original routing path) $S$ 和 新路由路径 (new routing path) $S'$。
    • $S = \langle \nu_1, \ldots, \nu_m \rangle$：原始路径中的自治系统 (AS) 序列。
    • $S' = \langle \nu_1', \ldots, \nu_n' \rangle$：新路径中的自治系统 (AS) 序列。
  • DTW 算法步骤:
    1. 生成合格自治系统 (AS) 对序列: DTW 算法反复从 $S$ 和 $S'$ 中选择一对自治系统 (AS)，并生成合格的自治系统 (AS) 对序列，需满足以下条件：
       • (i) S (S') 中的每个自治系统 (AS) 必须与 S' (S) 中的一个或多个自治系统 (AS) 配对。
       • (ii) $S$ 中的第一个 (最后一个) 自治系统 (AS) 必须与 $S'$ 中的第一个 (最后一个) 自治系统 (AS) 配对。
       • (iii) 给定 $i < j$，如果 $S$ 中的 $\nu_i$ 和 $\nu_j$ 分别与 $S'$ 中的 $\nu_k'$ 和 $\nu_l'$ 配对，则必须保持 $k \leq l$（即保持序列的顺序性）。
       • (iv) $S$ 和 $S'$ 是对称的，即配对操作对两条路径是等价的。
       • 示例: 如果 $S = \langle \nu_1, \nu_2, \nu_3 \rangle$, $S' = \langle \nu_1', \nu_2', \nu_3' \rangle$，则序列 $(( \nu_1, \nu_1' ), ( \nu_2, \nu_2' ), ( \nu_3, \nu_3' ))$ 和 $(( \nu_1, \nu_1' ), ( \nu_1, \nu_2' ), ( \nu_2, \nu_2' ), ( \nu_3, \nu_3' ))$ 都是合格的。但序列 $(( \nu_1, \nu_1' ), ( \nu_1, \nu_2' ), ( \nu_2, \nu_1' ), ( \nu_3, \nu_3' ))$ 不合格，因为它违反了条件 (iii)（$\nu_1$ 和 $\nu_2$ 在 $S$ 中顺序递增，但它们配对的 $\nu_2'$ 和 $\nu_1'$ 在 $S'$ 中顺序递减）。
    2. 计算序列总差异: 对于每个合格的自治系统 (AS) 对序列，累加其所有自治系统 (AS) 对的 配对自治系统差异 (pairwise AS difference)（由 BEAM 模型的 $D_{l,r}$ 函数给出）。
    3. 确定路径差异得分 (Path Difference Score): 从所有累加值中选择最小值作为路径差异得分 (path difference score)。这个具有最小值的自治系统 (AS) 对序列被称为 最优序列 (optimal sequence)。
  • 动态规划优化: 为了高效计算最优序列，采用动态规划 (dynamic programming) 方法。
    • 令 S[1:i] ( S'[1:j] ) 表示 $S$ ( $S'$ ) 的前 $i$ ( $j$ ) 个自治系统 (AS)。
    • 最优序列的计算基于先前状态：
      • 通过 S[1:i] 和 S'[1:j-1] 的最优序列，添加新的自治系统 (AS) 对 (S[i], S'[j])。
      • 通过 S[1:i-1] 和 S'[1:j] 的最优序列，添加新的自治系统 (AS) 对 (S[i], S'[j])。
      • 通过 S[1:i-1] 和 S'[1:j-1] 的最优序列，添加新的自治系统 (AS) 对 (S[i], S'[j])。
    • 选择产生最小配对自治系统差异 (pairwise AS difference) 之和的操作，作为 S[1:i] 和 S'[1:j] 的最优自治系统 (AS) 对序列。
    • 基准情况 (base case)：S[1:1] 和 S'[1:1] 的最优序列易于计算。
  • 更详细的算法描述可参考论文的附加技术报告 [43]。

4.3.3. 异常检测器 (Anomaly Detector)

异常检测器 (Anomaly Detector) 接收 BEAM 引擎 (BEAM Engine) 生成的路径差异得分 (path difference scores)，并执行以下步骤来识别、定位和关联路由异常。

1. 检测可疑路由变化 (Detecting Suspicious Route Changes):

   • 标准: 对于每一个路由变化 (route change)，检测器会检查其路径差异得分 (path difference score) 是否大于一个动态确定的阈值 $th_d$。
   • 阈值设定: $th_d$ 是根据历史合法路由变化 (legitimate route changes) 的路径差异得分 (path difference scores) 分布动态计算的，具体方法是取其累积分布函数 (CDF) 曲线的拐点 (knee point)。
   • 结果: 如果路径差异得分 (path difference score) 超过 $th_d$，则该路由变化被标记为 可疑路由变化 (suspicious route change)。

2. 识别异常前缀 (Identifying Anomalous Prefixes):

   • 目的: 优先处理影响范围广的路由异常。
   • 分组: 将影响相同 IP 前缀 (IP prefix) 的所有可疑路由变化 (suspicious route changes) 归类到不同的 前缀事件 (prefix events) 中。每个事件关联一个特定前缀，并按发生时间排序其内部的可疑路由变化 (suspicious route changes)。
   • 滑动窗口 (Sliding Window): 对于每个前缀事件，检测器使用一个滑动窗口 (sliding window) 来统计在窗口内观察到可疑路由变化 (suspicious route changes) 的 独立视点 (individual vantage points) 的数量。
   • 阈值: 如果这个视点数量超过预设阈值 $th_{\nu}$，则认为该前缀事件与一个 广泛的路由异常 (widespread routing anomaly) 相关联，并将其标记为 异常前缀事件 (anomalous prefix event)。

3. 定位责任自治系统 (Locating Responsible ASes):

   • 目的: 识别造成路由异常的“罪魁祸首”自治系统 (AS)，因为一个误行为的自治系统 (AS) 可能同时影响多个前缀。
   • 识别自治系统 (ASes): 对于每个与异常前缀事件 (anomalous prefix event) 关联的可疑路由变化 (suspicious route change)，检测器会识别出现在新路径 (new path) 或原始路径 (original path) 中的自治系统 (ASes)。
   • 计算交集: 将所有这些路由变化 (route changes) 中识别出的自治系统 (ASes) 进行交集运算，得到一组 责任自治系统 (responsible ASes)，它们被认为是该异常前缀事件 (anomalous prefix event) 的原因。

4. 关联事件和生成警报 (Correlating Events and Generating Alarms):

   • 事件关联: 如果两个异常前缀事件 (anomalous prefix events) 的时间范围重叠 (time ranges have overlaps)，并且它们具有 共同的责任自治系统 (common responsible ASes)，则认为这两个事件是相互关联的。
   • 聚合: 通过这种关联机制，所有异常前缀事件 (anomalous prefix events) 被划分为多个集合，每个集合内的事件彼此关联，但不同集合之间不关联。
   • 输出警报: 最终，异常检测器将每个集合视为一个独立的 路由异常 (routing anomaly)，并生成一个警报 (alarm)，其中明确指定了 受影响的前缀 (affected prefixes) 和 责任自治系统 (responsible ASes)。
   • 实现细节: 论文的附加技术报告 [43] 中提供了具体的实现细节。

5. 实验设置

5.1. 数据集

5.1.1. 实验数据集

• 来源: RouteViews [46] 收集的真实世界 BGP 路由公告 (route announcement records)。RouteViews 项目提供从全球多个视点 (vantage points) 收集的 BGP 路由信息。
• 数量和时间跨度: 18 个真实世界数据集，时间跨度从 2008 年到 2021 年。
• 数据量: 总计超过 110 亿 (11 billion) 条路由公告记录 (route announcement records)。
• 内容: 每个数据集都包含一个已确认的历史路由异常 (previously-confirmed routing anomaly)，包括 15 起 BGP 劫持 (BGP hijacking)（2 起前缀劫持 (prefix hijacking)，13 起子前缀劫持 (subprefix hijacking)）和 3 起 BGP 路由泄露 (BGP route leak) 事件。
• 异常信息来源: 异常的确认信息（如发生时间、受影响前缀）来自 Oracle blogs [44] 和 BGPStream monitor [45]。
• 数据提取: 对于每个异常，提取其发生前后 12 小时的所有路由公告 (route announcements)。
• 路由变化类型: 这些数据集中的异常路由变化 (anomalous route changes) 涵盖了起源变更 (origin change)（两条路由路径具有不同的起源自治系统 (origin ASes)）和路径变更 (path change)（两条路由路径共享相同的起源自治系统 (origin AS)，但遍历不同的自治系统 (ASes)）。同时，也包含了合法路由变化 (legitimate route changes)，例如由多源自治系统 (MOAS) [41] 引起的起源变更。
• 数据集命名: 每个数据集根据其所包含的异常事件进行命名，例如 PO_brazil。

5.1.2. CAIDA AS Relationship Dataset

• 用途: 用于训练 BEAM 模型，构建自治系统图 (AS Graph)。
• 选择原因: 自治系统 (AS) 业务关系 (business relationships) 主要决定了自治系统 (AS) 如何更新和传播路由，因此直接影响路由角色 (routing role)。该数据集比历史路由公告数据包含更少的错误条目 [34]，且业务关系相对稳定。
• 具体数据: 在 2018 年 6 月 1 日收集的数据集，包含 61,549 个自治系统 (AS) 和 439,981 条业务关系记录 (business relationship records)。选择这个时间点是为了确保数据在已确认 BGP 事件之前，避免噪声。

5.1.3. 为什么要选择这些数据集进行实验？它们是否能有效地验证方法的性能？

• 广泛代表性: RouteViews 数据集是 BGP 研究的黄金标准，提供了来自全球视点 (global vantage points) 的真实 BGP 数据，具有高度的代表性。
• 涵盖多样异常类型: 包含 BGP 劫持 (hijacking) 和路由泄露 (route leak) 的多种子类型，以及合法路由变化，确保了对系统识别不同异常能力和区分正常行为能力的全面评估。
• 真实世界事件: 所有异常都经过了第三方（Oracle blogs, BGPStream）的独立确认，确保了实验的真实性和可信度。
• 时间跨度长: 覆盖十多年的数据，验证了系统在不同互联网演进阶段的有效性。
• 验证有效性: 这些数据集能够有效地验证方法的性能。
  • 大规模的路由公告数据流用于测试系统在真实世界规模下的处理能力和效率。
  • 已确认的异常事件用于评估系统的检测率 (detection rate)。
  • 大量的合法路由变化用于评估系统的误报率 (false alarm rate) 和区分能力。
  • 不同时间点的 CAIDA 数据集用于训练 BEAM 模型，可以验证其在不同网络拓扑快照下的学习能力。

5.2. 评估指标

5.2.1. 检测率 (Detection Rate) 或 召回率 (Recall)

1. 概念定义: 衡量系统正确识别出所有实际存在的真实异常事件的能力。在路由异常检测中，高检测率意味着系统能够有效地捕捉到互联网中发生的绝大多数 BGP 异常，减少漏报 (false negatives) 的风险，这对于维护网络安全至关重要。
2. 数学公式: $$\text{Detection Rate} = \frac{\text{True Positives}}{\text{True Positives} + \text{False Negatives}}$$
3. 符号解释:
   • $\text{True Positives}$：系统正确识别出的真实异常事件数量（即，实际是异常且被系统成功告警的事件）。
   • $\text{False Negatives}$：系统未能识别出的真实异常事件数量（即，实际是异常但被系统漏报的事件）。

5.2.2. 误报数量 (Number of False Alarms)

1. 概念定义: 衡量系统将正常事件错误地识别为异常事件的频率。在路由异常检测中，低误报数量（或低误报率）至关重要，因为它可以减少网络运维人员检查和处理无效告警的负担，提高系统的实用性。
2. 数学公式: $\text{False Alarms}$ （直接统计数量，通常也与总告警数量相除得到误报率）
3. 符号解释:
   • $\text{False Alarms}$：系统错误地标记为异常的正常事件数量。

5.2.3. 告警数量 (Number of Alarms)

1. 概念定义: 系统在特定时间段或数据集上发出的总告警 (alarm) 数量，包括真实告警和误报 (false alarms)。这是一个衡量系统输出信息量的指标。
2. 数学公式: 无需复杂公式，直接统计数量。
3. 符号解释: 直接表示为计数，即系统发出的所有警报总数。

5.2.4. 运行时开销 (Runtime Overhead)

1. 概念定义: 衡量系统处理 BGP 数据流和执行检测任务所需的时间。在实时路由异常检测系统中，低运行时开销意味着系统能够跟上每秒数千条甚至数万条 BGP 路由更新的速率，及时发现异常并发出警报。
2. 数学公式: 通常以时间单位（秒、毫秒）表示，例如：
   • 每 15 分钟数据处理时间 (Time per 15 minutes of data)。
   • 每 1000 路由变化 (route changes) 处理时间 (Time per 1000 route changes)。
3. 符号解释: 直接以时间数值表示。

5.2.5. 鲁棒性 (Robustness)

1. 概念定义: 衡量系统在输入数据（例如自治系统 (AS) 业务关系 (business relationships) 数据）存在噪声或不准确性时，维持其检测性能的能力。在真实网络环境中，数据源可能不完美，因此系统必须对这些不确定性具有抵抗力。
2. 数学公式: 通过在不同噪声水平下重复上述指标（如检测率和误报数量）的测量来评估。
3. 符号解释: 通常通过比较在不同噪声比率下的检测到的真异常数量和误报数量来体现。

5.2.6. 异常验证模式 (Anomaly Verification Patterns)

为了验证除已确认异常之外的其他告警的准确性，论文定义了四种基于领域知识和权威数据（如 RPKI 验证状态）的异常路由变化模式。如果一个告警符合至少一种模式，则被视为高置信度的真实告警 (true alarm with high confidence)。

• P1 (未经授权的路由变化 - Unauthorized Route Change):
  1. 概念定义: 指路由变化前后的起源自治系统 (origin ASes) 属于不同的组织，并且它们的 RPKI 验证状态表明其中一个处于 invalid_ASN 状态而另一个处于 valid 状态。这通常意味着一个非法的自治系统 (AS) 错误地宣布了某个前缀的所有权。
  2. 数学公式: 无。
  3. 符号解释: invalid_ASN 指 RPKI 验证结果显示公告的起源自治系统 (origin AS) 与 RPKI 记录不匹配；valid 指 RPKI 验证结果显示起源自治系统 (origin AS) 和前缀长度均符合 RPKI 记录。
• P2 (路由泄露 - Route Leak):
  1. 概念定义: 指路由路径 (routing path) 在路由变化之前或之后违反了 BGP 的 valley-free criterion [30]。valley-free criterion 指路由不应该从提供商 (provider) 传递到对等体 (peer) 或另一个提供商 (provider)，或从对等体 (peer) 传递到提供商 (provider)。违反此原则通常意味着路由信息被非策略性地传播。
  2. 数学公式: 无。
  3. 符号解释: valley-free criterion 是 Gao-Rexford 模型中的一个核心规则，用于描述自治系统 (AS) 之间路由的合法传播方向。
• P3 (路径操纵 - Path Manipulation):
  1. 概念定义: 指路由路径 (routing path) 在路由变化之前或之后包含保留自治系统号 (reserved ASNs) 或相邻自治系统 (adjacent ASes) 之间没有业务关系记录 (business relationship records)。这通常表明路径是伪造的或存在异常。
  2. 数学公式: 无。
  3. 符号解释: 保留自治系统号 (reserved ASNs) 是指定用于私有用途或特殊用途的 ASN，不应出现在公共路由路径中；没有业务关系记录的相邻自治系统 (adjacent ASes) 可能意味着它们之间没有合法的 BGP 邻接关系。
• P4 (ROA 配置错误 - ROA Misconfiguration):
  1. 概念定义: 指路由变化前后的起源自治系统 (origin ASes) 属于同一组织，但它们的 RPKI 验证状态表明其中一个处于 invalid_length 或 invalid_ASN 状态而另一个处于 valid 状态。这通常是由于前缀长度或起源自治系统 (origin AS) 在 ROA (Route Origin Authorization) 记录中配置不正确导致的。
  2. 数学公式: 无。
  3. 符号解释: invalid_length 指 RPKI 验证结果显示公告的前缀长度与 ROA 记录不匹配；invalid_ASN 指 RPKI 验证结果显示公告的起源自治系统 (origin AS) 与 ROA 记录不匹配。

5.3. 对比基线 (Baselines)

论文将 BEAM 系统与两种类型的基线进行了比较：六种使用不同特征或通用网络表示学习模型来计算路径差异的变体，以及两种最先进的基于机器学习的 BGP 异常检测方法。

5.3.1. 基于特征或通用网络表示学习模型的变体 (Variants)

这些变体与 BEAM 共享相同的检测系统架构（BEAM 引擎 (BEAM Engine) 被替换，但异常检测器 (Anomaly Detector) 相同），仅在路径差异得分 (path difference score) 的计算方式上有所不同。它们都经过充分训练并使用与 BEAM 系统相同的设置。

• ED (Edit Distance):
  • 方法: 使用编辑距离 (Edit Distance) [48]（也称为 Levenshtein 距离）来衡量两条路由路径之间的差异。编辑距离是量化将一个字符串转换为另一个字符串所需的最小单字符编辑（插入、删除、替换）操作数量。
  • 代表性: 这是一种简单而直观的路径相似性度量，常用于比较序列。
• JI (Jaccard Index):
  • 方法: 使用邻居自治系统 (AS) 集合的 Jaccard 指数来衡量两个自治系统 (AS) 的相似性。对于两条路径中的自治系统 (AS) 对，计算它们的邻居集合的 Jaccard 指数。
  • 代表性: Jaccard 指数是衡量集合相似性的常用指标，可以反映自治系统 (AS) 在网络局部结构上的相似性。
• Li (LINE [35]):
  • 方法: LINE (Large-scale Information Network Embedding) 是一种通用网络表示学习模型，旨在学习大规模信息网络中的节点嵌入。它通过保留一阶和二阶近邻度 (first-order and second-order proximity) 来学习嵌入向量。在比较路径时，使用其嵌入向量的欧氏距离 (Euclidean distance) 来衡量自治系统 (AS) 的相似性。
  • 代表性: 是一个广泛使用的、高效的图嵌入算法。
• Ma (Marine [49]):
  • 方法: Marine 是一种多关系网络嵌入 (Multi-relational Network Embedding) 模型，它考虑了关系近邻度 (relational proximity) 和节点属性 (node attributes)。同样，在比较路径时，使用其嵌入向量的欧氏距离 (Euclidean distance) 来衡量自治系统 (AS) 的相似性。
  • 代表性: 适用于具有多种关系类型的复杂网络。
• NV (node2vec [50]):
  • 方法: node2vec 是一种基于随机游走 (random walks) 的图嵌入算法，它通过灵活地平衡广度优先搜索 (BFS) 和深度优先搜索 (DFS) 的采样策略来学习节点嵌入。使用其嵌入向量的欧氏距离 (Euclidean distance) 来衡量自治系统 (AS) 的相似性。
  • 代表性: 能够捕捉网络的多种结构特性，是流行的图嵌入方法之一。
• SD (SDNE [51]):
  • 方法: SDNE (Structural Deep Network Embedding) 是一种结合深度学习的图嵌入方法，它使用深度自编码器 (deep autoencoder) 同时捕捉网络的一阶和二阶近邻度 (first-order and second-order proximity)，尤其是非线性结构。使用其嵌入向量的欧氏距离 (Euclidean distance) 来衡量自治系统 (AS) 的相似性。
  • 代表性: 能够学习网络的非线性复杂结构。

5.3.2. 最先进的基于 ML 的 BGP 异常检测方法 (State-of-the-art ML-based BGP Anomaly Detection)

• AV (Shapira et al. [28]):
  • 方法: AP2vec (An Unsupervised Approach for BGP Hijacking Detection) 使用无监督词嵌入 (unsupervised word embedding) 技术来建模 BGP 路由。它将路由路径中的自治系统 (AS) 序列视为“句子”，并学习自治系统 (AS) 的嵌入表示。通过比较新的路由公告与已知正常路由的相似性来检测异常。
  • 特点: 该方法主要关注检测异常路由变化 (anomalous route changes) 和异常发生的时间间隔。
  • 比较设置: 按照原文设置，使用最新 RIB 快照训练模型，并在接下来的两小时 RIB 快照上进行检测。为了公平比较，将 AV 的检测结果通过本文的异常检测器 (Anomaly Detector) 聚合成警报。
• LS (Dong et al. [22]):
  • 方法: ISP self-operated BGP anomaly detection based on weakly supervised learning 将 BGP 公告聚合为时间序列，并提取 86 个特征。这是一个监督学习方法，通过弱监督学习 (weakly supervised learning) 进行训练，以识别每个时间间隔的异常。
  • 特点: 主要关注每分钟的异常检测。
  • 比较设置: 针对每个数据集，使用其他 17 个数据集作为训练数据来训练 LS 模型，然后对目标数据集中的时间间隔进行分类（正常或异常）。同样，将 LS 的检测结果通过本文的异常检测器 (Anomaly Detector) 聚合成警报。

5.3.3. 未对比方法说明

论文未与基于主动探测 (active probing-based) 的系统（如 [10, 15]）进行比较，原因是这些系统严重依赖于数据面设施收集的实时探测结果，而这些实时数据对于历史数据集是不可用的。

5.4. 阈值设定

在异常检测器 (Anomaly Detector) 中，有两个关键的动态阈值用于识别异常：$th_d$ 和 $th_ν$。

• $th_d$ (路径差异得分阈值):

  • 功能: 用于识别单个 可疑路由变化 (suspicious route change)。如果一个路由变化的路径差异得分 (path difference score) 大于 $th_d$，则被认为是可疑的。
  • 计算方法: $th_d$ 是根据历史数据动态计算的。具体来说，它使用当前检测窗口前两小时内观察到的所有 合法路由变化 (legitimate route changes) 的路径差异得分 (path difference scores) 作为参考分布。然后，将 $th_d$ 设定为该分布的累积分布函数 (CDF) 曲线上的 拐点 (knee point)。
  • 工具: 拐点 (knee point) 的计算通过 kneed [47] 工具自动化实现。选择拐点 (knee point) 是为了平衡检测灵敏度和误报率，因为它通常代表着数据分布中“异常”开始显著出现的位置。

• $th_{\nu}$ (视点数量阈值):

  • 功能: 用于识别 广泛的路由异常 (widespread routing anomaly)。在一个滑动窗口内，如果观察到可疑路由变化 (suspicious route changes) 的独立视点 (individual vantage points) 的数量超过 $th_{\nu}$，则该前缀事件被视为异常。
  • 计算方法: $th_{\nu}$ 的确定方法与 $th_d$ 类似，也是基于历史数据动态计算。

5.5. 异常验证模式 (Anomaly Verification Patterns)

为了验证系统检测到的警报，特别是那些未被独立第三方确认的“未知”告警，论文定义了四种基于领域知识和权威数据源（如 RPKI 验证状态）的异常路由变化模式。如果一个警报符合以下至少一种模式，则被视为高置信度的真实告警 (true alarm with high confidence)。这些模式也得到了在大型互联网服务提供商 (ISP) 部署系统的领域专家 (domain experts) 的认可。

1. P1 (未经授权的路由变化 - Unauthorized Route Change):

   • 描述: 路由变化前后的起源自治系统 (origin ASes) 属于不同的组织，并且在 RPKI 验证中，一个起源自治系统 (origin AS) 处于 invalid_ASN 状态，而另一个处于 valid 状态。
   • 含义: 这强烈表明发生了 BGP 劫持 (BGP hijacking)，即一个未经授权的自治系统 (AS) 冒充合法所有者。

2. P2 (路由泄露 - Route Leak):

   • 描述: 路由变化之前或之后的路由路径 (routing path) 违反了 BGP 的 valley-free criterion [30]。
   • 含义: 这是路由泄露 (route leak) 的经典定义，即路由信息被非策略性地传播。

3. P3 (路径操纵 - Path Manipulation):

   • 描述: 路由变化之前或之后的路由路径 (routing path) 包含保留自治系统号 (reserved ASNs) 或相邻自治系统 (adjacent ASes) 之间没有业务关系记录 (business relationship records)。
   • 含义: 路径中出现保留自治系统号 (reserved ASNs) 或不合法的自治系统 (AS) 邻接关系，表明路径可能是伪造的或受到操纵。

4. P4 (ROA 配置错误 - ROA Misconfiguration):

   • 描述: 路由变化前后的起源自治系统 (origin ASes) 属于同一组织，但它们的 RPKI 验证状态中，一个处于 invalid_length 或 invalid_ASN 状态，而另一个处于 valid 状态。

   • 含义: 尽管起源自治系统 (origin ASes) 属于同一实体，但 RPKI 验证失败表明其路由起源授权 (ROA) 配置存在错误，例如前缀长度或自治系统号 (ASN) 不匹配。

     重要说明: 这些模式本身不应直接用于检测路由异常 (routing anomalies)，因为它们可能导致大量孤立的告警。它们主要是作为验证工具，帮助确认聚合后的告警 (aggregated alarms) 的真实性。

6. 实验结果与分析

本节将详细分析论文的实验结果，包括路径差异得分的有效性、系统在历史数据集上的检测性能、运行时开销、鲁棒性以及真实世界部署的表现，并通过可视化和表格数据进行呈现。

6.1. 核心结果分析

6.1.1. 路径差异得分 (Path Difference Score) 的有效性

原文 Figure 5 展示了异常路由变化 (anomalous route changes) 和合法路由变化 (legitimate route changes) 的路径差异得分 (path difference scores) 的统计比较。

以下是原文 Figure 5 的可视化：

该图像是图7，展示了在存在噪声AS关系情况下的检测结果。上图展示了不同噪声比例下检测到的异常数量变化，下图显示了相同条件下误报数量的变化，体现了各检测方法在噪声干扰下的鲁棒性。

• 观察: 从图中可以清晰看出，异常路由变化的路径差异得分 (path difference scores) 显著高于合法路由变化的得分。异常变化的 CDF 曲线（橙色）右移，表明其得分分布在更高的值域。
• 分析: 这验证了 BEAM 引擎 (BEAM Engine) 计算的路径差异得分 (path difference score) 能够有效地区分合法和异常的路由行为。
  • 例如，在 $SO_{pakistan}$ 数据集中的异常事件中，起源自治系统 (origin ASes) 从 AS 36561 (YouTube) 变为 AS 17557 (Pakistan Telecom)。这两个自治系统 (ASes) 在地理位置、邻居以及在互联网中的层级方面存在巨大差异，导致其路由角色 (routing role) 迥异，从而产生高路径差异得分 (path difference score)。
  • 相比之下，合法路由变化（例如，由同一组织运营的 AS 6198 变为 AS 6197）通常涉及路由角色 (routing role) 相似的自治系统 (ASes)，因此路径差异得分 (path difference score) 较低。

6.1.2. 历史异常检测结果

论文在 18 个包含已确认历史路由异常 (previously-confirmed routing anomalies) 的真实 RouteViews 数据集上评估了系统的性能，并与多种基线方法进行了比较。

以下是原文 Table 1 的结果：

• 表头解释:

  • Dataset: 包含特定路由异常的测试数据集。
  • Detected: 表示该方法是否成功检测到数据集中已确认的异常。✓ 表示检测到，$x$ 表示未检测到。
  • #Alarms(#FalseAlarms): 表示该方法在数据集中发出的总告警数量，括号内是其中的误报数量。

• 核心发现:

  1. 检测率 (Detection Rate):
     • 本文系统 (Ours): 成功检测到所有 18 个已确认的路由异常 (confirmed routing anomalies) (18/18)，表现出 100% 的召回率。
     • 其他方法: 相比之下，所有基线方法的检测率都较低。表现最好的 NV (node2vec) 仅检测到 14/18，Ma 检测到 13/18，Li 和 ED、JI 检测到 11-12/18。最先进的 ML 方法 LS 仅检测到 9/18，而 AV 甚至更差，只检测到 4/18。SD (SDNE) 未能检测到任何异常 (0/18)。
  2. 误报数量 (False Alarms):
     • 本文系统 (Ours): 在所有数据集中总共产生了 29 个误报。有 6 个数据集甚至没有产生误报，在最差的情况下（RLjl），也只产生了 5 个误报。
     • 通用网络表示模型 (Variants): 这些方法的误报数量远高于本文系统。例如 ED 产生了 53 个，Li 产生了 68 个。
     • ML 基线 (LS, AV): 误报数量非常高。LS 总共产生了 635 个误报，AV 产生了 161 个误报。
     • 结论: 本文系统在保持高检测率的同时，显著降低了误报数量，这对于实际部署至关重要。

• 综合分析:

  • 本文系统解决了传统 ML 方法的局限性，实现了有效的互联网路由异常检测。
  • 通用网络表示学习模型（如 Li, Ma, NV, SD）无法有效捕捉 BGP 语义 (BGP semantics)，因此在检测性能上远不如 BEAM。
  • AV 和 LS 等现有最先进的 ML 方法在检测率和误报率上均逊色于本文系统，这表明 BEAM 在 BGP 异常检测领域取得了显著进展。
  • 误报主要与路由工程实践（如 AS 路径前置 - AS prepending）或连接有限的末梢自治系统 (stub ASes) 相关。

6.1.3. 运行时开销 (Runtime Overhead)

原文 Figure 6 展示了系统的运行时开销。

以下是原文 Figure 6 的可视化：

该图像是论文中图8的柱状图，展示了2023年1月每日真实告警和误报数量。蓝色柱代表真实告警，数量明显高于橙色误报，显示整体误报率较低且告警波动情况。

• 测试环境: Linux 服务器，Intel Xeon E5-2650v4 (2.20GHz)。
• 数据集特点: X 轴按时间顺序显示数据集，后期的数据集包含更多正在运行的自治系统 (ASes)（从 27,588 个增长到 73,014 个）。
• 观察:
  • 每 15 分钟数据处理时间 (上图): 大多数情况下处理时间少于 100 秒，最大处理时间约为 140 秒（在 RLjtl 数据集上）。
  • 每 1000 路由变化处理时间 (下图): 稳定状态下，异常检测器 (anomaly detector) 处理 1000 次路由变化仅需约 0.05 秒；冷启动 (cold start) 状态下约 0.2 秒。
• 分析:
  • 系统处理 15 分钟的数据所需时间远小于 15 分钟本身，这表明系统能够有效地实时处理全球路由公告流。即使自治系统 (AS) 数量增加，对运行时开销的影响也微乎其微。
  • 通过缓存机制（例如路径差异得分 (path difference scores) 的缓存），系统在稳定运行时的效率极高。

6.1.4. 鲁棒性分析 (Robustness Analysis)

论文分析了系统在面对噪声自治系统 (AS) 关系数据时的鲁棒性。通过修改或删除 CAIDA 数据集中的原始自治系统 (AS) 关系来创建噪声数据集。

以下是原文 Figure 7 的可视化：

该图像是论文中展示三类BGP路由异常检测示例的图表，分别为YouTube劫持、BackConnect劫持和JTL路由泄漏，展示异常变化与正常变化的节点关系及热力图。异常变化区域用红框标注，正常变化区域用绿框标注。

• 噪声数据集类型:
  • R1 (翻转标签): 随机选择 $r\%$ 的自治系统 (AS) 关系，翻转其标签（P2P 变为 P2C，P2C 变为 P2P）。模拟不准确的自治系统 (AS) 关系推断。
  • R2 (删除关系): 随机删除 $r\%$ 的自治系统 (AS) 关系。模拟不完整的自治系统 (AS) 关系推断。
  • W1 (翻转标签，低可见度): 选择 BGP 路由使用最少的 $r\%$ 自治系统 (AS) 关系，翻转其标签。模拟低互联网可见度 (limited Internet visibility) 区域的误标签。
  • W2 (删除关系，低可见度): 选择 BGP 路由使用最少的 $r\%$ 自治系统 (AS) 关系，删除它们。模拟低互联网可见度 (limited Internet visibility) 区域的关系缺失。
• 实验方法: 使用每个噪声数据集独立训练系统，并按照 5.2 节的步骤评估其检测性能。每个实验重复 5 次以避免偏差。
• 观察 (Figure 7):
  • 即使当噪声比率达到 20% 时，系统仍能检测到至少 17 个真实异常（总共 18 个）。
  • 在所有数据集中，误报数量均少于 40 个。
• 分析:
  • 实验结果表明系统在自治系统 (AS) 关系数据存在噪声的情况下表现出强大的鲁棒性。
  • 考虑到在实际中如此高的噪声比率非常罕见，这进一步增强了系统的实用性。

6.1.5. 真实世界部署 (Real-World Deployment)

论文在一个大型互联网服务提供商 (ISP) 的主操作自治系统 (AS) 中部署了系统，进行了为期一个月的真实检测。

以下是原文 Table 2 和 Figure 8 的结果：

Table 2: The overall impact of the detected anomalies.

Figure 8: Daily alarm number in real-world deployment.

该图像是图10，展示了系统在实际部署中生成的异常报告，包括未经授权的路由变更。图中通过热力图和网络节点可视化，揭示了路由角色的变化及异常检测细节。

• 部署环境:
  • ISP 的主操作自治系统 (AS)，全球排名前 100。
  • 与约 500 个邻居自治系统 (neighbor ASes) 维护实时 BGP 会话，包括 14 个一级自治系统 (Tier-1 ASes)。
  • 系统部署在服务器上，通过 iBGP 协议接收来自所有 BGP 路由器的实时路由公告 (real-time incoming route announcements)。
• 训练和配置:
  • BEAM 引擎 (BEAM Engine) 使用部署时最新的 CAIDA AS relationship dataset 训练（74,923 个自治系统 (AS)，505,927 条业务关系 (AS business relationship records)）。
  • 滑动窗口长度为一小时。
  • 参数设置和误报识别方法与历史数据评估相同。
  • 为了减少重复告警，共享相同异常前缀 (anomalous prefix) 和责任自治系统 (responsible AS) 的告警被聚合。
• 部署结果 (2023 年 1 月 1 日至 2 月 1 日):
  • 处理数据量: 处理了 152,493,303 条实时路由公告 (live route announcements)。
  • 检测到的路由变化: 5,106,442 次路由变化 (route changes)。
  • 发出的告警数量: 548 个告警 (alarms)。平均每天 17.68 个告警。
  • 真实异常数量: 497 个告警被领域专家 (domain experts) 验证为真实异常 (true anomalies)。
    • 这些异常未被 ISP 现有的路由安全机制检测到。
    • 包括 84 个未经授权的路由变化 (P1)、123 个路由泄露 (P2)、270 个路径操纵 (P3) 和 20 个 ROA 配置错误 (P4)。
  • 误报数量: 平均每天只有 1.65 个误报 (false alarms)。
  • 影响范围 (Table 2): 检测到的异常总共影响了 1,202 条路由、961 个前缀和 477 个起源自治系统 (origin ASes)。
• 与现有机制的比较:
  • ISP 现有机制: ISP 现有机制基于客户的 IRR (Internet Routing Registry) 检测无效路由，但在部署期间未产生任何告警（因覆盖率不完整）。因此，本文系统未错过 ISP 自身检测到的任何告警。
  • RPKI 验证结果作为参考: 本文系统仅错过了约 2.25% 的 RPKI 无效公告 (invalid announcements)，且大多数是由于有限的互联网可见度 (limited Internet visibility) 导致的。
  • 结论: 真实世界部署结果进一步证明了系统的实用性、高检测率和极低误报率。

6.2. 数据呈现 (表格)

6.2.1. Table 1: Detection results on the 18 real-world datasets.

该表格已在 6.1.2. 历史异常检测结果 中完整转录并分析。

6.2.2. Table 2: The overall impact of the detected anomalies.

该表格已在 6.1.5. 真实世界部署 中完整转录并分析。

6.2.3. Table 3: Comparison with ML-based Methods.

以下是原文 Table 3 的结果：

• 表头解释:

  • Method: 检测方法。
  • Training Data: 训练模型所需的数据类型。
  • Training Data Vol.: 训练数据量。
  • Retraining Req.: 重训练频率要求。
  • ML Model Type: 机器学习模型类型（监督/无监督）。
  • Detection Data: 检测时使用的数据类型。
  • Anomaly Type: 能够检测的异常类型（瞬态/长期）。

• 分析:

  • 训练数据和开销:
    • 本文系统: 仅使用自治系统 (AS) 关系数据（约 50 万条记录），每月重训练一次，且是无监督学习。训练开销小，数据易获取。
    • AV: 需要 RIB entries（约 1000 万条记录），每两小时重训练一次。训练开销巨大。
    • LS: 需要公告时间序列（约 1 亿条记录），重训练频率未知。是监督学习，需要大量标注数据。
  • 检测数据和异常类型:
    • 本文系统: 处理实时路由公告 (Ann.)，可以检测瞬态和长期异常 (Short & Long-lived)。
    • AV: 处理 RIB entries，只能检测长期异常 (Long-lived)，无法捕捉瞬态异常。
    • LS: 处理公告时间序列 (Ann. time series)，可以检测瞬态和长期异常 (Short & Long-lived)。
  • 结论: 本文系统在训练开销和可检测异常类型方面优于 AV 和 LS。特别是其无监督特性和对自治系统 (AS) 关系数据的依赖，使其在实际部署中更具优势。

6.2.4. Appendix B: Sampled AS Pair Datasets.

以下是原文附录 B 的表格：

• 表头解释:

  • Feature: 所测试的自治系统 (AS) 特性（一阶近邻度 (1st-order proximity)、二阶近邻度 (2nd-order proximity)、层级 (hierarchy)）。
  • Name: 采样数据集的名称。
  • #AS pair: 采样到的自治系统 (AS) 对数量。
  • Sampling rule: 采样规则，描述了这些自治系统 (AS) 对如何被选择。No rel 指没有直接关系；Ngbr JI 指邻居自治系统 (AS) 集合的 Jaccard 指数。

• 分析: 这个表格详细列出了用于评估 BEAM 模型学习到的路由角色 (routing role) 差异的自治系统 (AS) 对数据集。这些数据集的设计目的是系统性地测试模型在不同近邻度 (proximity) 和层级 (hierarchy) 场景下的表现，从而验证模型公式 (Model Formulation) 中定义的特性能够被嵌入向量 (embedding vectors) 准确捕捉。

6.3. 可视化分析

6.3.1. Figure 3: 可视化嵌入向量和路由角色差异

该图已在 4.2.5. 嵌入结果分析 中完整转录并分析。其子图 (A) 和 (B) 展示了自治系统 (AS) 嵌入向量 (embedding vectors) 在 3D 空间中的整体分布，(C) 和 (D) 展示了特定自治系统 (AS) 类型的投影，(E)、(F)、(G) 则通过 CDF 曲线验证了 BEAM 对一阶近邻度 (first-order proximity)、二阶近邻度 (second-order proximity) 和层级 (hierarchy) 的保留能力。

6.3.2. Figure 9: 历史 BGP 异常案例研究

原文 Figure 9 通过三个历史 BGP 异常案例展示了 BEAM 系统的解释能力。每个案例都包含了一个异常路由变化 (anomalous route change) 和一个合法路由变化 (legitimate route change) 的对比，并使用热力图 (heat map) 和嵌入图 (embedding map) 进行可视化。

以下是原文 Figure 9 的可视化：

该图像是两个折线图组成的图表，展示了使恶意路径与合法路径的路由角色相似所需控制的自治系统数量和需建立的自治系统关系数量的经验估计。横轴为不同测试配置，纵轴分别表示所需数量及其误差范围。

• 可视化方法:

  • 热力图 (Heat Map): 展示了路由路径差异得分 (path difference scores) 在 DTW (Dynamic Time Warping) 算法配对过程中的变化。图中的对角线表示原始路径和新路径的自治系统 (AS) 完全匹配，偏离对角线则表示存在差异。颜色越深通常表示差异越大。最优序列 (optimal sequence) 被标记出来。
  • 嵌入图 (Embedding Map): 使用 t-SNE [39] 将自治系统 (AS) 嵌入向量 (embedding vectors) 降维到 2D 空间，可视化路由路径上自治系统 (AS) 的路由角色 (routing role) 及其相互关系。

• 案例 1: 起源变更 (Origin Change) - SO_pakistan (Figure 9(A))

  • 事件: AS 17557 (Pakistan Telecom) 劫持 (hijacked) 了 AS 36561 (YouTube) 的子前缀 (subprefix)。
  • 异常模式:
    • 热力图 (Figure 9(A)(I)): 异常模式显示新旧路径上的大部分自治系统 (ASes) 不同。路径差异得分 (path difference score) 随着自治系统 (AS) 配对操作的进行而急剧上升，因为两条路径的自治系统 (ASes) 很快就完全不同。
    • 嵌入图 (Figure 9(A)(I)): 两个起源自治系统 (origin ASes)，AS 17557 和 AS 36561，在嵌入图 (embedding map) 中相距遥远，很少有共同邻居，表明它们的路由角色 (routing role) 非常不同。
  • 合法模式 (Figure 9(A)(II)): 同一天发生的合法路由变化具有较低的路径差异得分 (path difference scores)。嵌入图 (embedding map) 中路径几乎重叠，因为合法的起源更新（AS 6198 变为 AS 6197）发生在属于同一组织（BellSouth Network）且路由角色 (routing role) 相似的自治系统 (ASes) 之间。

• 案例 2: 路径变更 (Path Change) - $SP_backcon_2$ (Figure 9(B))

  • 事件: AS 203959 (BackConnect) 劫持 (hijacked) 了 AS 25761 (Staminus Comm.) 的子前缀 (subprefix)，通过伪造一条不存在的路径指向真实起源自治系统 (real origin AS)。
  • 异常模式:
    • 热力图 (Figure 9(B)(I)): 路径差异得分 (path difference score) 急剧上升。最优序列 (optimal sequence) 显著偏离热力图 (heat map) 的对角线，这表明原始路径中没有自治系统 (AS) 与 AS 203959 相似。
    • 嵌入图 (Figure 9(B)(I)): 伪造路径 (fake path) 显著偏离真实路径 (real path)，因为 AS 203959 既不在真实路径上，其路由角色 (routing role) 也与真实路径上的任何自治系统 (AS) 不相似。
  • 合法模式 (Figure 9(B)(II)): 合法路由变化中的路径在路由角色 (routing role) 上相似，路径差异很小。

• 案例 3: 路由泄露 (Route Leak) - RL_JTL (Figure 9(C))

  • 事件: AS 36866 (JTL) 从其提供商 AS 8966 (Emirates Tel.) 接收到路由，并将其泄露给另一个提供商 AS 37662 (WIOCC)。
  • 异常模式:
    • 热力图 (Figure 9(C)(I)): 泄露路由导致路径显著变长，通过 AS 37662 显著绕行。路径差异得分 (path difference scores) 很高，最优序列 (optimal sequence) 形成一个远离对角线的驼峰状模式。这还违反了 valley-free criterion。
    • 嵌入图 (Figure 9(C)(I)): 泄露的路径在嵌入图 (embedding map) 中显示出与原始路径 (original path) 的显著偏离。
  • 合法模式 (Figure 9(C)(II)): 合法路由变化路径差异微小。

6.3.3. Figure 10: 真实世界部署中的告警报告

原文 Figure 10 展示了系统在真实世界部署中报告的第一个告警 (Alarm 0)。

以下是原文 Figure 10 的可视化：

该图像是论文中BEAM模型架构示意图，展示了输入AS关系后，经过AS图构建、AS嵌入生成，最终输出AS路由角色的嵌入向量。图中详细说明了BEAM的近邻度量$p\_score$,层级度量$h\_score$,联合优化目标以及路由角色差异函数$D\_{l,r}$。

• 事件概述 (顶部):
  • 告警 ID: Alarm 0。
  • 时间: 2023 年 1 月 1 日 01:04:40 开始，持续约 1 小时 24 分钟。
  • 影响: 影响三个前缀 (prefixes)，涉及六条路由 (routes)，由两个独立视点 (individual vantage points) 观察到。
• 代表性路由变化事件 (底部):
  • 视点: 从 AS 6453 观察到的事件。
  • 异常内容: AS 42440 (RDG-AS) 未经授权宣布了 185.88.179.0/24 前缀，而该前缀的合法所有者是 AS 201691 (WEIDE)。
  • RPKI 状态: AS 42440 的 RPKI 验证状态为 invalid_ASN。
  • 异常类型: 此外，AS 42440 也在路由变化前的路径上，这表明这是一个 RFC 7908 [55] 中描述的 Type-5 路由泄露 (route leak)。
  • 可视化结果:
    • 热力图 (Heat Map): 在 AS 42440 之前的最优序列 (optimal sequence) 沿着对角线（相似路径），但在 AS 42440 之后，路径差异得分 (path difference score) 急剧增加，表明路由角色 (routing role) 发生了显著变化。
    • 嵌入图 (Embedding Map): 清晰地展示了 AS 42440 与 AS 201691 之间路由角色 (routing role) 的明显差异。
• 分析: 这个案例研究生动地展示了 BEAM 系统不仅能够检测到真实世界中的复杂异常，而且通过热力图 (heat map) 和嵌入图 (embedding map) 提供了直观、可解释的证据，极大地便利了网络运营商对异常的理解和排查。

6.4. 消融实验/参数分析

论文中没有明确标注为“消融实验 (Ablation Study)”或“参数分析 (Parameter Analysis)”的独立章节。然而，其设计和实验结果隐含地提供了类似消融实验的证据，并讨论了部分参数设置。

1. 隐式消融实验——与通用网络表示学习模型 (General Network Representation Learning Models) 的对比:

   • 论文将 BEAM 与 LINE, Marine, node2vec, SDNE 等通用网络表示学习模型进行了比较 (参见 Table 1)。这些通用模型虽然也能生成自治系统 (AS) 嵌入，但它们没有专门集成 BGP 语义 (BGP semantics)。
   • 结果显示: BEAM 在检测率和误报率上均显著优于这些通用模型。这间接证明了 BEAM 核心设计中“BGP 语义感知 (BGP semantics aware)”的有效性。即，专门针对领域语义进行嵌入学习，比通用图嵌入方法能更好地捕捉 BGP 路由的特性。

2. 鲁棒性分析 (Robustness Analysis) 中的参数影响 (Figure 7):

   • 通过改变噪声比率 (noise ratio) 来评估系统在不同质量的自治系统 (AS) 关系数据下的性能。这可以看作是对输入数据质量这一“参数”的分析。
   • 结果表明: 即使噪声比率高达 20%，系统仍表现出良好的性能，证明了其对数据质量变化的鲁棒性。

3. 适应性攻击 (Adaptive Attacks) 的经验研究 (Appendix D):

   • 虽然不是传统的消融实验，但这项研究探讨了攻击者需要付出多大“成本”才能绕过系统。它量化了攻击者需要控制的自治系统 (AS) 数量和需要建立的新自治系统 (AS) 关系数量，以使恶意路径的路由角色 (routing role) 与合法路径相似。
   • 结果: 攻击者通常需要控制至少两个自治系统 (AS) 并建立数百条新关系。这间接说明了 BEAM 模型学习到的路由角色 (routing role) 具有一定的复杂性和难以伪造性，从而增强了系统的鲁棒性。

4. 模型参数设置 (Section 3.4):

   • 嵌入维度 $d=128$。

   • 训练 1000 轮 (epochs)。

   • 批次大小 (batch size) 1024。

   • 初始学习率 $10^{-5}$。

   • 每条边 10 个负样本 (negative samples)。

   • 这些是 BEAM 模型训练时的超参数选择，但论文未详细讨论其选择依据或不同参数值对性能的影响。

     总结: 尽管没有独立的消融实验章节，但论文通过与多种基线的对比和鲁棒性分析，有效地验证了 BEAM 核心设计中 BGP 语义感知嵌入的价值和系统的稳健性。

7. 总结与思考

7.1. 结论总结

本文提出了一个名为 BEAM (BGP Semantics Aware Network Embedding) 的新型网络表示学习模型，并围绕它构建了一个创新的路由异常检测系统。BEAM 的核心在于深度整合 BGP 语义 (BGP semantics)，以准确学习互联网中每个自治系统 (AS) 的独特路由角色 (routing role)。通过这种方式，路由异常检测问题被巧妙地转化并简化为发现新路由公告 (route announcements) 中自治系统 (AS) 路由角色 (routing role) 的意外变化 (churn)。

该系统具有以下显著优势：

• 语义感知与可解释性: 不同于传统机器学习模型的“黑箱”特性，BEAM 学习的路由角色 (routing role) 基于自治系统 (AS) 的近邻度 (proximity) 和层级 (hierarchy) 等 BGP 语义 (BGP semantics) 属性，使得检测结果具有内在的可解释性，能够为网络运营商提供有意义的诊断信息。

• 无监督学习: 系统无需大规模的标注数据或复杂的特征工程，仅依赖相对稳定且易于获取的自治系统 (AS) 业务关系数据进行训练，大大降低了部署和维护成本。

• 卓越的检测性能: 在包含超过 110 亿路由公告记录 (route announcement records) 的 18 个真实 RouteViews 数据集上的广泛评估表明，该系统能够检测所有已确认的历史路由异常 (previously-confirmed routing anomalies)，同时保持极低的误报率（每 1.8 亿路由公告 (route announcements) 最多 5 个误报）。

• 实时与高鲁棒性: 系统具有低运行时开销，能够实时处理全球路由公告流。此外，在面对高达 20% 噪声的自治系统 (AS) 关系数据时，系统依然展现出强大的鲁棒性。

• 真实世界实用性: 在一个大型互联网服务提供商 (ISP) 部署一个月的实践证明，系统成功检测到 497 个真实异常 (true anomalies)，平均每天仅产生 1.65 个误报 (false alarms)，且能够发现现有安全机制未察觉的异常，充分展示了其在实际网络运维环境中的有效性和实用价值。

  总而言之，本文的工作为解决 BGP 路由异常检测中的解释性 (interpretability) 和高开销问题提供了一个开创性的解决方案，为构建更安全、更可靠的互联网路由系统迈出了重要一步。

7.2. 局限性与未来工作

7.2.1. 论文作者指出的自身局限性

1. 单一前缀阈值 (Per-Prefix Threshold):
   • 局限性: 系统目前对所有 IP 前缀 (IP prefixes) 使用相同的检测阈值 $th_d$ 和 $th_{\nu}$。为每个前缀分配独立的阈值可能带来更好的检测结果，但考虑到互联网中庞大的前缀数量（例如，超过 94 万个 IPv4 和 20 万个 IPv6 前缀），这将导致巨大的计算开销和检测延迟，不适合在线检测。
2. 未知自治系统 (Unknown ASes):
   • 局限性: BEAM 模型无法学习与网络中其他自治系统 (ASes) 关系未知（即不存在于 CAIDA 数据集中）的自治系统 (ASes) 的路由角色 (routing roles)。
   • 缓解: 现有的研究 [34] 表明，大多数自治系统 (ASes) 的关系是已知的。在论文分析的最新事件中，未知自治系统 (ASes) 仅占总自治系统 (ASes) 的 0.05040%。此外，一些未知自治系统 (ASes) 使用的是为私有用途保留的自治系统号 (AS numbers)，包含这些自治系统 (ASes) 的路由路径应被视为异常。

7.2.2. 提出了哪些未来可能的研究方向？

1. 减少误报的启发式方法 (Heuristics to Reduce False Alarms):
   • 短命异常过滤: 大多数路由劫持 (route hijacks) 和路由泄露 (route leaks) 都是短命的 [10]。可以利用这一特性，将长期存活的路由标记为正常，从而进一步减少误报。
   • MOAS 区分: 合法多源自治系统 (MOAS) 事件中的不同起源自治系统 (origin ASes) 通常具有相似的路由特性（例如，属于同一组织），而恶意自治系统 (ASes) 则不然。可以利用这一差异来更好地区分合法 MOAS 和恶意事件。
2. 持续适应路由角色演变 (Evolving Routing Roles):
   • 互联网拓扑和自治系统 (AS) 路由策略 (routing policies) 是动态变化的。尽管 BEAM 系统对路由角色演变具有一定的弹性（训练与检测之间即使有 30 天的时间差仍表现良好），但仍需定期更新模型。
   • 解决方案: 鉴于 CAIDA 数据集通常每月更新，并且 BEAM 的训练开销可接受（使用 GeForce RTX 2080 Ti 约 10 小时），可以定期重新训练 BEAM 模型以跟上路由角色 (routing role) 的演变。

7.3. 个人启发与批判

7.3.1. 这篇论文对你有什么启发？其方法或结论是否可以迁移或应用到其他领域？

• 领域知识深度融合的价值: BEAM 最重要的启发是，在特定领域（如 BGP 路由）中，将领域知识（BGP 语义 (BGP semantics)）深度融入到机器学习模型（网络表示学习 (network representation learning)）的设计中，可以显著提升模型的性能、鲁棒性和最关键的可解释性 (interpretability)。这比纯粹依赖数据驱动的“黑箱”模型更具实践价值。
• 无监督学习的潜力: 在异常检测这类标注数据稀缺的场景中，无监督学习 (unsupervised learning) 方法（如 BEAM）通过利用结构化数据（如自治系统 (AS) 关系）的内在规律来识别异常，展现出巨大的应用潜力。
• 动态时间规整 (DTW) 的创新应用: 将 DTW 算法应用于比较路由路径的自治系统 (AS) 序列，并结合语义感知的自治系统 (AS) 差异度量，为序列数据（不仅限于路由路径）的比较和异常检测提供了新的思路。这种方法可以迁移到其他需要比较复杂序列模式的领域。
• 可解释性是落地的关键: 论文强调并实际展示了可解释性 (interpretability) 对于网络运维的重要性。提供“为什么是异常”的解释，而非仅仅“是异常”，是推动技术从实验室走向实际部署的关键。
• 方法迁移性:
  • 其他网络协议异常检测: 类似的思想可以应用于其他具有复杂结构和语义的网络协议（如 DNS 异常检测、SDN 中的策略违规检测），通过构建协议实体（如 DNS 域名、SDN 控制器）的语义感知嵌入来识别异常行为。
  • 复杂系统行为分析: 任何具有明确实体和实体间关系（可以构建图）且行为模式蕴含语义的复杂系统（如供应链网络、金融交易网络、生物分子网络），都可以借鉴 BEAM 的思想，通过学习实体“角色”的语义嵌入来检测异常或理解其行为模式。

7.3.2. 你认为其潜在的问题、未经验证的假设或可以改进的地方是什么？

• 适应性攻击 (Adaptive Attacks) 的真实成本: 论文在附录 D 中对适应性攻击 (adaptive attacks) 的成本进行了经验估计，但这个估计基于一个简化假设（仅需要 10% 的共同邻居即可使路由角色 (routing role) 相似）。实际的攻击者可能会寻找更隐蔽、更复杂的手段来规避检测，例如缓慢地、逐步地建立关系，或利用更高级的社会工程学手段。此外，攻击者可能不会完全模仿一个“正常”路由角色 (routing role)，而是试图创造一个“看起来正常但略有不同”的模式来规避检测。因此，实际的防御挑战可能比论文估计的更大。
• 阈值的动态性与鲁棒性: 尽管 $th_d$ 和 $th_{\nu}$ 是动态计算的，但它们依赖于过去两小时的“合法”路由变化 (legitimate route changes) 分布。如果在此期间存在隐蔽的或新型的异常，可能污染“合法”分布，从而影响阈值的准确性。此外，对于极罕见或零日攻击，这种基于历史合法行为的阈值可能不够灵敏。
• 未覆盖的异常类型: 论文主要关注 BGP 劫持 (hijacking) 和路由泄露 (route leak)。BGP 异常还包括路由震荡 (route flapping)、路由黑洞 (blackholing) 等。系统对这些其他类型异常的检测能力如何，以及是否需要额外的语义来捕捉它们，是未被探讨的。
• 解释性深度的进一步提升: 尽管路由角色 (routing role) 提供了可解释的结果，但对于非专业的网络操作员，直接理解“路由角色 (routing role) 发生了变化”的深层含义，以及如何据此进行故障排查，可能仍需要更用户友好的可视化工具或自然语言解释生成器。例如，系统能否进一步解释“这个 AS 的层级 (hierarchy) 为什么突然下降了，这通常意味着什么类型的错误”？
• 未知自治系统 (Unknown ASes) 的处理策略优化: 虽然论文提到未知自治系统 (Unknown ASes) 数量较少，且可能包含私有 ASN (AS numbers) 并被标记为异常，但这并非一个通用解决方案。对于确实是合法但未被 CAIDA 数据集收录的新自治系统 (new ASes)，系统可能会将其误报。这需要更精细的机制，例如结合其他数据源进行验证，或者对新出现的自治系统 (ASes) 采取更长的观察期。
• 多维度语义的融合: BEAM 专注于近邻度 (proximity) 和层级 (hierarchy)，但自治系统 (AS) 的路由角色 (routing role) 还可能受到其他复杂因素的影响，例如地理位置、业务类型、QoS 策略等。未来工作可以探索如何将更多维度的 BGP 语义 (BGP semantics) 融入嵌入模型，以学习更丰富、更精确的路由角色 (routing role)。
• 对 BGP 更新消息 (UPDATE messages) 的处理细化: BGP UPDATE 消息包含 WITHDRAW (撤销) 和 ANNOUNCE (公告) 两种。论文主要描述了处理新的路由公告 (route announcements)。对于路由撤销 (route withdrawals) 导致的路径变化，系统如何计算差异得分并识别异常，可以进一步明确。