Learning with Semantics: Towards a Semantics-Aware Routing Anomaly Detection System

Yihao Chen, Qilei Yin, Qi Li, Zhuotao Liu, Ke Xu, Yi Xu, Mingwei Xu, Ziqian Liu, Jianping Wu

Introduction

The Border Gateway Protocol (BGP) serves as the fundamental routing protocol of the Internet, enabling thousands of Autonomous Systems (ASes)—including Internet Service Providers (ISPs), content delivery networks, and large enterprises—to exchange reachability information. Despite its critical role, BGP was originally designed based on a model of implicit trust. This vulnerability allows for significant routing anomalies, primarily BGP hijacking and route leaks.

Visualizing BGP Hijacking and Route Leaks

BGP hijacking occurs when a malicious or misconfigured AS announces a prefix it does not own, effectively "stealing" traffic. Route leaks involve the propagation of routing advertisements beyond their intended scope, often violating business agreements and leading to suboptimal or congested paths. Traditional detection methods often struggle with high false-positive rates or require extensive manual rule-tuning.

The BEAM Framework

To address these challenges, researchers introduced BEAM (BGP sEmAntics aware network eMbedding), an unsupervised machine learning system designed to detect anomalies by understanding the "business roles" of networks. Unlike previous "black box" models, BEAM is highly interpretable and identifies when a route path suddenly stops making "semantic sense."

The BEAM Architecture and Semantic Embedding Components

The BEAM architecture operates in several distinct stages:

  1. AS Graph Construction: Instead of relying solely on traffic patterns, BEAM utilizes known business relationships (e.g., Provider-to-Customer, Peer-to-Peer) to build a structured graph of the Internet.
  2. Semantic Embedding: The system learns low-dimensional vector representations (embeddings) for each AS. This process is governed by two primary objectives:
  3. Proximity: Ensuring networks with similar connectivity patterns (common neighbors) are positioned closely in the vector space.
  4. Hierarchy: Explicitly modeling the tiered structure of the Internet (e.g., Tier-1 vs. Tier-3 providers) to capture the "up-and-down" nature of traffic flow.
  5. Anomaly Detection: By comparing the "semantic sequence" of a new route path against historical norms using Dynamic Time Warping (DTW), BEAM identifies "role churn"—instances where a path suddenly deviates from expected business logic.

Evaluation and Real-World Performance

The efficacy of BEAM was validated using extensive historical and live datasets. The researchers analyzed over 11 billion route announcement records from RouteViews (2008–2021), covering 15 major hijacks and 3 significant route leaks.

Key results include:

  • Perfect Historical Recall: BEAM successfully identified all 18 confirmed historical anomalies.
  • Operational Efficiency: During a one-month deployment at a top-100 global ISP, the system processed 150 million live announcements, detecting 497 true anomalies with an average of only 1.65 false alarms per day—a manageable volume for human operators.
  • Speed: The model is lightweight, processing 1,000 route changes in approximately 0.05 seconds on standard hardware.

Discussion and Future Directions

The core insight behind BEAM is that BGP anomalies are essentially violations of business logic. While technical paths may change frequently, the underlying business roles of ASes remain relatively stable. By modeling these roles, BEAM achieves high interpretability; operators can visualize why a path is flagged by observing its detour into suspicious semantic neighborhoods via t-SNE maps.

Current limitations include the handling of brand-new ASes (approximately 0.5% of cases) and complex Multi-Origin AS (MOAS) events. Future work aims to integrate real-time data feeds to further refine the system's accuracy and reduce the remaining margin of false alarms caused by legitimate but complex routing changes.

Summary updated

BibTeX
@inproceedings{chen2024learning,
  author = {Yihao Chen and Qilei Yin and Qi Li and Zhuotao Liu and Ke Xu and Yi Xu and Mingwei Xu and Ziqian Liu and Jianping Wu},
  title = {{Learning with Semantics: Towards a Semantics-Aware Routing Anomaly Detection System}},
  booktitle = {USENIX Security},
  year = {2024},
  url = {https://openreview.net/forum?id=rrIRMD1W2m},
}
Figure