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

Yihao Chen
Tsinghua University  Qilei Yin
Zhongguancun Lab  Qi Li
Tsinghua University  Zhuotao Liu
Tsinghua University  Ke Xu
Tsinghua University  Yi Xu
Tsinghua University  Mingwei Xu
Tsinghua University  Ziqian Liu
China Telecom  Jianping Wu
Tsinghua University

###### Abstract

BGP is the de facto inter-domain routing protocol to ensure global
connectivity of the Internet. However, various reasons, such as deliberate
attacks or misconfigurations, could cause BGP routing anomalies. Traditional
methods for BGP routing anomaly detection require significant manual
investigation of routes by network operators. Although machine learning has
been applied to automate the process, prior arts typically impose significant
training overhead (such as large-scale data labeling and feature crafting),
and only produce uninterpretable results. To address these limitations, this
paper presents a routing anomaly detection system centering around a novel
network representation learning model named BEAM. The core design of BEAM is
to accurately learn the unique properties (defined as _routing role_) of each
Autonomous System (AS) in the Internet by incorporating BGP semantics. As a
result, routing anomaly detection, given BEAM, is reduced to a matter of
discovering unexpected routing role churns upon observing new route
announcements. We implement a prototype of our routing anomaly detection
system and extensively evaluate its performance. The experimental results,
based on 18 real-world RouteViews datasets containing over 11 billion route
announcement records, demonstrate that our system can detect all previously-
confirmed routing anomalies, while only introducing at most five false alarms
every 180 million route announcements. We also deploy our system at a large
ISP to perform real-world detection for one month. During the course of
deployment, our system detects 497 true anomalies in the wild with an average
of only 1.65 false alarms per day.

##  1 Introduction

The Border Gateway Protocol (BGP) is the de facto inter-domain routing
protocol to achieve global connectivity in the Internet. BGP establishes
Internet-wide routing paths by exchanging route announcements among the
networks operated by different organizations, referred to as Autonomous
Systems (ASes). Each route announcement carries AS-level path information for
reaching certain prefixes (_i.e.,_ a block of IP addresses). At its steady
state, every AS learns an AS-path to reach every globally routable Internet
prefix. Despite its global adoption, BGP itself has no built-in authentication
mechanism. As a result, a misbehaved AS can announce arbitrary routes in the
Internet, either due to deliberate attacks or misconfigurations. These bogus
routes form serious threats to routing security, namely BGP hijacking (_i.e.,_
forcing certain traffic to go through a malicious AS) and BGP route leaks
(_i.e.,_ redirecting traffic over unintended links). Over the past decade, the
Internet has witnessed several severe BGP incidents. For example, a Swiss
company leaked over 70,000 routes in 2019 [1] and a British company hijacked
more than 31,000 prefixes in 2021 [2]. A cryptocurrency platform recently
confirmed the loss of $1.9 million after a BGP hijacking attack [3]. Although
several security extensions have been proposed to counter these threats,
_e.g.,_ BGPsec [4], psBGP [5] and S-BGP [6], they are not widely deployed,
possibly due to incompatibility with the current Internet architecture.
Besides, while RPKI [7] has gained traction in providing authoritative
information about IP prefix ownership, its effectiveness is largely limited by
the incomplete deployment of ROV [8]. More importantly, RPKI is not designed
to mitigate route manipulation attacks or route leaks.

Detecting routing anomalies in the global Internet is the first step towards
secure Internet routing. The community has proposed significant research in
this regard [9, 10, 11, 12, 13, 14, 15, 16, 17, 18]. However, they typically
rely on extensive analysis of routing data from multiple sources. More
crucially, these methods require non-trivial human supervision to produce
reasonable results. The advance in Machine Learning (ML) motivates the
community to apply ML techniques to automate and simplify anomaly detection by
recognizing different patterns of route announcements [19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31]. However, existing methods require large datasets
with manual labels and/or handcrafted features, imposing significant overheads
on data collection and model update. Moreover, many of these methods learn
deep latent features for classification, producing largely uninterpretable
results. As a consequence, these methods provide limited practical guidance
for network operators to fix routing anomalies.

To address these challenges, we present a routing anomaly detection system
centering around a novel network representation learning model, BEAM (BGP
sEmAntics aware network eMbedding). Instead of learning any latent or opaque
features, BEAM enables interpretable and accurate routing anomaly detection
based on the intrinsic routing characteristics of ASes that are derived from
the _domain specific knowledge of BGP semantics_. Specifically, we propose the
concept of _AS routing role_ to meaningfully characterize ASes in BGP route
announcements. The design of routing role is derived from the AS business
relationship graph (rather than any handcrafted features), because an AS’s
business relationship with its neighboring ASes determines how the AS chooses
to update the route announcements received from neighbors, and how the newly
generated route announcements are further propagated [32]. Given accurate
modeling of ASes’ routing roles, anomaly detection is reduced to a matter of
detecting unexpected AS routing role churns from the original route to the new
route announcement.

The key design challenges in obtaining routing roles are two-fold. First, the
available dataset of route announcements could contain non-trivial noises due
to the unrevealed routing anomalies in the Internet [33]. For instance, AS
4134 leaked over 70,000 routes in 2019 [1] and AS 55410 hijacked more than
31,000 prefixes in 2021 [2]. As a result, computing routing roles directly
from the noisy route announcement dataset (using either raw announcements or
statistical features) could lead to high false positive rates [20, 24, 25,
26]. Second, due to the dynamism and scale of Internet routing, AS routing
roles are evolving over time.

To address the above challenges, BEAM employs a novel embedding mechanism to
learn an embedding vector for each AS based on the AS graph constructed from
AS relationships. The key of BEAM’s embedding is to preserve an AS’s proximity
and hierarchy properties that are essential to its routing role. The exact
definitions of proximity and hierarchy are given in §3.2. The embedding
vectors are further employed to uniquely represent and interpret the routing
roles of ASes, based on which our routing anomaly detection system reports
routing anomalies upon observing abnormal routing role churns. Further, we
design our learning mechanism to ensure that the embedding vectors can
properly capture routing roles despite the ever-changing Internet routing and
topology.

We validate our system on 18 real-world route announcement datasets collected
from global vantage points111A vantage point is a BGP participant (_e.g.,_ a
router) that provides public access to its routing table and/or its received
route announcements.. The entire datasets include over 11 billion route
announcement records spanning from 2008 to 2021. The experimental results show
that BEAM produces interpretable results regarding AS routing role changes,
based on which our system correctly identifies all previously-confirmed
routing anomalies, while only incurring at most five false alarms every 180
million route announcements (about 1.61 false alarms per day). We also deploy
our system at a large ISP to detect routing anomalies over a one-month period.
We further visualize AS routing roles to achieve interpretable routing
behavior analysis. Our work can serve as a complement to existing BGP security
extensions, such as RPKI, to protect against both BGP hijacking and BGP route
leaks.

To summarize, our contributions are four-fold:

  * •

We design the first BGP semantics aware network representation learning model,
BEAM, that accurately captures the routing roles of ASes.

  * •

We develop an unsupervised routing anomaly detection system based on BEAM,
which achieves real-time detection in an interpretable manner without
requiring labeled routing data or feature engineering.

  * •

We validate our system by conducting experiments on 18 RouteViews datasets
with more than 11 billion route announcement records. Our system can detect
all confirmed anomalies with minor false alarms.

  * •

We deploy our system at a large ISP to collect real-world detection results
for a month. The system detects 497 true anomalies in the wild from over 150
million live route announcements, with only 1.65 daily false alarms on
average.

##  2 Background

Figure 1: Illustrations of BGP anomalies. In BGP hijacking, the adversary can
either (I) falsely claim the ownership of a prefix, or (II) announce a fake
yet more preferable route. In BGP route leak, routes are propagated to
unintended ASes.

Inter-domain Routing Protocol. The Internet contains over 73,000 advertised
Autonomous Systems (ASes) as of Jun 2023. Each AS consists of several networks
under the management of the same organization and is identified by a uniquely
allocated non-negative integer called AS Number (ASN). BGP is the de facto
inter-AS routing protocol to achieve global connectivity of the Internet. BGP
is a path-vector routing protocol that maintains AS-level path information,
which gets updated as BGP announcements propagate in the network. Upon
receiving a BGP announcement, an AS, following its _routing policy_ , may stop
further propagating the announcement, or append its ASN to the AS-path and
send the updated announcement to a _selective_ set of neighbors.

Business relationship largely determines one AS’s routing policy [32, 34]. Two
neighboring ASes typically have three types of business relationships222We
ignore complex AS relationships [35]. They are much more unusual and play a
minor role in defining the overall routing behavior of an AS.: provider-to-
customer (P2C), peer-to-peer (P2P) and customer-to-provider (C2P), where a
customer AS pays its provider for connectivity while two peering ASes forward
traffic to each other free of charge. Thus, the inter-domain routing system of
the Internet can be reconstructed as an AS graph based on AS relationships.
This AS-level topology exhibits hierarchy [32], with several well recognized
Tier-1 (large-scale) ASes. However, the topology is not strictly hierarchical
and is flattening over time [36].

BGP Anomalies. Although widely deployed, BGP lacks built-in authentication,
_i.e.,_ one AS can broadcast virtually arbitrary BGP announcements to disrupt
the security and reliability of Internet routing. BGP anomalies can be
classified into two categories: hijacking and route leak, as illustrated in
Fig. 1. BGP hijacking itself has two subcategories: (i) falsely claiming the
ownership of a prefix or (ii) announcing fake paths (usually more preferable
than real paths) to prefixes. The first type of hijacking is solvable by Route
Origin Validation (ROV) [7], which is experiencing gradual deployment. Yet,
the second type of hijacking usually needs per-hop path validation protocols
such as BGPsec [4] that has very limited deployment. Also, BGP hijacking can
be classified as _prefix hijacking_ (targeting a prefix of others) or
_subprefix hijacking_ (targeting a subset of others’ prefix, _i.e.,_
subprefix).

The other category of BGP anomalies is route leak: a misbehaved AS propagates
BGP announcements to another AS in violation of the intended policies,
resulting in traffic forwarded through unintended links. The Gao-Rexford model
[32] describes the restrictions on BGP route propagation and can be used to
identify BGP route leak (_i.e.,_ the valley-free criterion). For example, in
2019, AS 21217 (_Safe Host_) broke the valley-free criterion by propagating
announcements received from its providers (_e.g.,_ AS 13237 (_euNetworks
GmbH_)) to another provider AS 4134 (_China Telecom_), redirecting large
amounts of Internet traffic destined for European mobile networks through
_China Telecom_ [1].

##  3 Semantics Aware Analysis

Figure 2: Learning AS routing roles via BEAM. BEAM takes AS relationships as
the input and outputs the embedding vectors that represent AS routing roles.
(II.1) BEAM characterizes the proximity between ASes by $p\\_score$. If two
ASes are directly connected and have the same business relationships with many
common neighbors, their proximity tends to be high, _i.e.,_ a lower
$p\\_score$. (II.2) BEAM characterizes the hierarchy among ASes by
$h\\_score$. If an AS must traverse multiple consecutive P2C links to reach
another AS, their hierarchy difference should be large, _i.e.,_ a higher
$h\\_score$. (II.3) BEAM utilizes one joint objective to optimize both
$p\\_score$ and $h\\_score$; negative sampling is also applied. (II.4) The
function $D_{\bm{l},\bm{r}}$ measures the routing-role difference between two
ASes. A higher $D_{\bm{l},\bm{r}}$ value means higher difference.

###  3.1 BEAM Overview

We propose a novel network representation learning model, BEAM, to learn the
routing roles of ASes. The routing roles meaningfully characterize the ASes in
BGP route announcements and are utilized to detect Internet routing anomalies.
As shown in Fig. 2, BEAM takes the AS business relationships as the input and
generates the embedding vector for each AS by (i) constructing an AS graph,
and (ii) performing AS embedding. To compute AS embedding vectors, BEAM
designs distance functions to measure two routing characteristics of the ASes:
the proximity (see Fig. 2(II.1)) and the hierarchy (see Fig. 2(II.2)). The
exact definitions of the two characteristics are given in §3.2. We design a
dedicated optimization objective such that BEAM preserves both the proximity
and the hierarchy through the embedding (see Fig. 2(II.3)). After obtaining
the optimized embedding vectors, we can further measure the pairwise AS
difference in terms of their routing roles (see Fig. 2(II.4)).

To our best knowledge, BEAM is the first dedicated network representation
learning model that fully integrates BGP semantics into the training process
and enables meaningful and accurate representation of ASes’ routing roles.
Applying network representation learning, rather than using “raw” AS business
relationships, is essential to characterize ASes’ routing roles. In
particular, our network representation learning model can capture the global
routing characteristics of each AS and translate them into embedding vectors,
while the original AS business relationships can only indicate the local
routing policy between two directly connected ASes. Further, with the
embedding vectors, we can quantify the difference in routing roles between
_any_ pair of ASes, regardless of whether they are connected or not. This
enables us to detect the unexpected AS routing role churns in the global
Internet that capture routing anomalies.

###  3.2 Model Formulation

###### Definition 1 (AS Graph).

An AS graph is a directed graph $G=(V,E)$ where each vertex $v\in V$
represents an AS and each directed edge $e=(u,v)\in E$ represents a P2C
relationship from $u$ to $v$.

We regard each unique AS (identified by its ASN) as a vertex, and the P2C
relationship between two vertices as a directed edge from provider to
customer. Accordingly, a C2P relationship is viewed as a reversed P2C one, and
a P2P relationship is represented via two edges in opposite directions.

We define two types of AS proximity to represent the similarity between two
ASes according to their local connections/relationships with their neighbors.

###### Definition 2 (First-Order AS Proximity).

The first-order proximity between two ASes is their pairwise connection in the
AS graph. For a pair of vertices $(u,v)$, the first-order proximity between
them is 1 if they are connected by an edge $e=(u,v)\in E$; otherwise it is 0.

###### Definition 3 (Second-Order AS Proximity).

The second-order proximity between two ASes is the similarity between their
neighborhood network structures. Given vertices $u,v$, let
$\bm{p_{u}}=\langle\bm{w_{u,1}},\dots,\bm{w_{u,|V|}}\rangle$ denote the first-
order proximity of AS $u$ with other ASes, the second-order proximity between
$u$ and $v$ is quantified based on the consistency between $\bm{p_{u}}$ and
$\bm{p_{v}}$.

While the concept of proximity has been proposed before [37], BEAM is the
first to extend its interpretation to BGP semantics. As illustrated in Fig.
2(II.1), ASes C and D have high first-order proximity due to the P2P
relationship (_i.e.,_ two edges in the AS graph), and also high second-order
proximity since they provide Internet transit services for a similar set of
customers. We also confirm our interpretation via a real-world example: AS
8903 and AS 12541, owned by cloud service provider _Evolutio_ , serve as each
other’s backup and hence have very similar routing roles. In terms of
proximity, they have 25 common customers and their neighbor AS sets are highly
similar (with a Jaccard index of 86.2%); thus, the proximity is consistent
with routing role similarity.

As discussed in §2, the Internet topology exhibits hierarchy. Typically, a
provider AS is considered on a higher level than its customers. Thus, we
define AS hierarchy as follows:

###### Definition 4 (AS Hierarchy).

The hierarchy of an AS is its tendency to establish P2C relationship with
other ASes. For two vertices $u,v$, if there exists a directed edge $e=(u,v)$,
the hierarchy from $u$ to $v$ is positive.

In real world, AS 7018 (_AT &T_) lies on the top of the Internet since it
establishes either P2C or P2P relationship with other ASes, while AS 140061
(_China Telecom_) is a stub AS without any customers. Thus, AS 7018 and AS
140061 have very different routing roles in BGP, which is aligned with the
positive hierarchy between them.

To quantify the AS proximity and hierarchy, we embed ASes into low-dimensional
representations.

###### Definition 5 (AS Embedding).

Given $G=(V,E)$, AS embedding is to map each vertex $v\in V$ into a low-
dimensional vector space $\mathbb{R}^{d}$, _i.e.,_ learn a mapping function
$f_{G;\theta}:V\rightarrow\mathbb{R}^{d}$, where $\theta$ contains learnable
parameters and $d\ll|V|$.

Finally, we define our BEAM model as follows:

###### Definition 6 (BGP Semantics Aware Network Embedding).

Given AS relationships, the BEAM model constructs the AS graph $G=(V,E)$ and
performs AS embedding, such that the embedding vectors
$\bm{x}=\\{\bm{x_{v}}|v\in V,\bm{x_{v}}=f_{G;\theta}(v)\\}$ preserve the
first- and second-order proximity and the hierarchy of ASes.

###  3.3 AS Graph Construction

The first step of training BEAM is to construct the AS graph. We use the real-
world CAIDA AS relationship dataset [38]333CAIDA is not the only source of AS
business relationships. Other sources like TopoScope [39] are also available
for training our system. to construct the AS graph $G$. A business
relationship between two ASes can be denoted as a tuple $(u,v,t)$, where $u$
and $v$ are two ASNs and $t\in\\{\textsc{P2P},\textsc{P2C},\textsc{C2P}\\}$
refers to the relationship type. For each tuple $(u,v,t)$ in the CAIDA
dataset, if $t=\textsc{P2C}$, we add a directed edge $e=(u,v)$ into $E$. If
$t=\textsc{C2P}$, we add a directed edge $e=(v,u)$ into $E$. And if
$t=\textsc{P2P}$, we add two directed edges $e=(u,v)$ and $e^{\prime}=(v,u)$
into $E$.

The rationale for using AS business relationship to construct the AS graph is
that it primarily determines how an AS chooses to update the routing paths
received from neighbors, and how the new generated route announcements are
propagated [32]. Hence, it has direct impacts on ASes’ routing roles.
Moreover, the AS business relationship is a relatively stable property
determined by real-world commercial agreements between connected ASes. Thus,
it is challenging to impersonate a specific AS without simultaneously changing
or faking multiple AS relationships. Besides, unlike historical route
announcement data, the AS business relationship dataset contains fewer
incorrect entries [36].

###  3.4 AS Embedding

With a constructed AS graph, we embed ASes into a vector space while
preserving proximity and hierarchy. To this end, we design two distance
functions to measure the difference between ASes regarding proximity and
hierarchy, respectively.

Proximity Distance. The proximity distance, indicated by $p\\_score$, models
the first-order proximity between ASes: a small distance between two ASes
means that their proximity is large. Per Def. 2, given a pair of directly
linked vertices $(u,v)$ and another pair of vertices $(u^{\prime},v^{\prime})$
without a direct edge, $p\\_score$ should reflect the difference between their
first-order proximity, _i.e.,_
$p\\_score(u,v)<p\\_score(u^{\prime},v^{\prime})$. Therefore, we define
$p\\_score$ as follows:

$p\\_score(u,v)=(\bm{x_{v}}-\bm{x_{u}})^{\intercal}\big{(}(\bm{x_{v}}-\bm{x_{u}})\odot\bm{l}\big{)},$
(1)

where $\bm{x_{u}},\bm{x_{v}}\in\mathbb{R}^{d}$ denote the embedding vectors of
$u,v$, respectively. $\bm{l}\in\mathbb{R}^{d}$ is a learnable weight vector
for the $d$ components. $\intercal$ and $\odot$ denote matrix transpose and
Hadamard product, respectively. Intuitively, $\bm{l}$ projects the embedding
vectors into a subspace intended for preserving the proximity. To explicitly
preserve the first-order proximity, BEAM learns $\bm{x},\bm{l}$ by decreasing
the $p\\_score$ of two vertices with an edge, while increasing the $p\\_score$
of two vertices that are not directly connected. Since this training strategy
also preserves the second-order proximity implicitly (elaborated later in this
section), we do not define a dedicated distance function for the second-order
proximity.

Hierarchy Distance. The hierarchy distance, indicated by $h\\_score$,
quantifies the hierarchical difference between ASes. Per Def. 4, given a pair
of vertices $(u,v)$ where $(u,v)\in E,(v,u)\notin E$, and another pair of
vertices $(u^{\prime},v^{\prime})$ without a directed edge, _i.e.,_
$(u^{\prime},v^{\prime})\notin E$, the $h\\_score$ should reflect the
difference between their hierarchy, _i.e.,_
$h\\_score(u,v)>h\\_score(u^{\prime},v^{\prime})$. To this end, we design
$h\\_score$ as follows:

$h\\_score(u,v)=(\bm{x_{v}}-\bm{x_{u}})^{\intercal}\bm{r},$ (2)

where $\bm{x_{u}},\bm{x_{v}}\in\mathbb{R}^{d}$ denote the embedding vectors of
$u,v$, respectively. $\bm{r}\in\mathbb{R}^{d}$ is a learnable unit vector
indicating the descending direction of hierarchy. Intuitively, $\bm{r}$
projects the embedding vectors into a subspace intended for preserving the
hierarchy, and thus the $h\\_score$ calculates the projected length of
$\bm{x_{v}}-\bm{x_{u}}$ on the specific direction vector $\bm{r}$ such that it
has two important properties, _i.e.,_ $h\\_score(u,v)=-h\\_score(v,u)$ and
$h\\_score(u,v)=h\\_score(u,w)+h\\_score(w,v)$. To explicitly preserve the
hierarchy of ASes, BEAM learns $\bm{x},\bm{r}$ by increasing the $h\\_score$
of two vertices with a directed edge (_i.e.,_ a P2C relationship), while
decreasing $h\\_score$ of two vertices not directly connected. Since ASes with
P2P relationship is connected by two edges in opposite directions, their
$h\\_score$ would approach zero under this training strategy, which is
consistent with the BGP semantics that two peering ASes are typically on the
same hierarchy of the Internet.

Training Objective. With the two distance functions, we design the training
objective of BEAM to ensure that a trained BEAM preserves both proximity and
hierarchy. We consolidate the two distance functions as follows:

$score(u,v)=-p\\_score(u,v)+h\\_score(u,v).$ (3)

Since a small $p\\_score$ means large proximity and a large $h\\_score$ means
large hierarchy, we subtract $p\\_score$ in Eq.(3) so that $score$ increases
monotonically with the difference between ASes in terms of proximity and
hierarchy. This design allows BEAM to preserve the two routing characteristics
better. Although $score$ may become zero in some cases, it will not affect
BEAM ’s training since the training objective is to enlarge the difference of
$score$ between observed edges and nonexistent edges. Per Def. 2 and 4, given
an observed edge $(u,v)$ and a nonexistent edge $(u^{\prime},v^{\prime})$, our
model should assign $score(u,v)>score(u^{\prime},v^{\prime})$ with the optimal
$\bm{x}$, $\bm{l}$ and $\bm{r}$. To this end, we formulate the optimization
problem as follows:

$\arg\min_{\bm{x},\bm{l},\bm{r}}L=\sum_{\begin{subarray}{c}(u,v)\in E\\\
(u^{\prime},v^{\prime})\notin
E\end{subarray}}-\log\sigma(score(u,v)-score(u^{\prime},v^{\prime})),$ (4)

where $E$ is the edge set of the AS graph, $\sigma(z)=\frac{1}{1+exp(-z)}$ is
the sigmoid function, and $L$ is the objective function to be minimized. We
solve this problem via a fully connected neural network, which has an
embedding layer and two linear layers. The embedding layer generates the
embedding vectors ($\bm{x}$) that represent ASes’ routing roles and the two
linear layers project the embedding vectors into two subspaces that preserve
proximity ($\bm{l}$) and hierarchy ($\bm{r}$), respectively. For each edge
$(u,v)\in E$, we sample 10 negative (nonexistent) edges
$(u^{\prime},v^{\prime})\notin E$ and each $((u,v),(u^{\prime},v^{\prime}))$
forms one training instance. The neural network generates the embedding
vectors of $u$ and $v$, computes the loss via Eq.(4), and uses SGD [40] to
optimize itself. When the training is complete, the neural network learns the
ASes’ routing roles. We empirically set $d=128$ and train the network for
1,000 epochs. The batch size is 1024 and the initial learning rate is
$10^{-5}$.

Computing Pairwise AS Difference. The pairwise AS difference represents their
difference in the routing roles, which we define between the embedding vectors
of two ASes using the BEAM model (including its parameters $\bm{x}$, $\bm{l}$,
and $\bm{r}$):

$\begin{split}D_{\bm{l},\bm{r}}(u,v)&=|p\\_score(u,v)|+|h\\_score(u,v)|\\\
=&\underbrace{(\bm{x_{v}}-\bm{x_{u}})^{\intercal}((\bm{x_{v}}-\bm{x_{u}})\odot\bm{l})}_{\text{\emph{the
first-order
proximity}}}+\underbrace{|(\bm{x_{v}}-\bm{x_{u}})^{\intercal}\bm{r}|}_{\text{\emph{the
hierarchy}}}.\end{split}$ (5)

Note that this pairwise AS difference directly reflects the first-order
proximity and the hierarchy between ASes. Moreover, per the definition of the
second-order proximity (Def. 3), the pairwise AS difference between two
vertices should be small if their neighbors and the business relationships
with their neighbors are similar. In Appendix A, we prove a theorem that this
pairwise AS difference does preserve the second-order proximity between ASes.
Thus, our BEAM model can preserve the first-order proximity, the second-order
proximity and the hierarchy between ASes.

###  3.5 Embedding Results Analysis

We train BEAM with the CAIDA AS relationship dataset collected on 06/01/2018
to study the routing roles of ASes. The dataset contains 61,549 ASes and
439,981 business relationships, and is randomly selected from the CAIDA
datasets collected before historical BGP incidents (see §5).

Figure 3: Embedding results. (A) All embedding vectors visualized in a 3-D
space. The Z-axis represents the hierarchy level and the XY-plane reflects the
proximity. (B) The terrain plot of the embedding vectors. The estimated
spatial distribution shows the overall characteristics of AS routing roles.
(C) The YZ-plane projection of the embedding vectors. The X-axis and the
Y-axis of the projection plane indicate the proximity and the hierarchy,
respectively. The areas with different colors illustrate the distribution of
typical ASes (_i.e.,_ vertices with different colors), and the dashed lines
show their average hierarchy levels. (D) The XY-plane projection of the
embedding vectors. (E) The routing role difference regarding the sampled
subset $S_{0}$, $H_{0}$ and $N_{0}$. (F) The routing role difference regarding
the sampled subset $N_{1}$ to $N_{5}$. (G) The routing role difference
regarding $S_{1}$ and $H_{1}$ to $H_{6}$.

Visualizing Embedding Vectors. We visualize the embedding vectors computed by
BEAM in a 3-D space to illustrate the overall characteristics of AS routing
roles. Since BEAM learns the unit direction vector $\bm{r}$ that represents
the descending direction of hierarchy, we decompose each embedding vector into
two parts: the projection on $\bm{r}$, and the projection on the plane
orthogonal to $\bm{r}$ (_i.e.,_ the rejection). We use the length of the
projection as the coordinate value of the Z-axis to represent the hierarchy
level of each AS. We further transform the rejection into a 2-D space by the
widely used dimension reduction method t-SNE [41], and hence obtain the
coordinate values of the X-axis and the Y-axis.

We visualize all embedding vectors in Fig. 3(A), where each vertex represents
a unique AS and the color indicates the AS hierarchy level. We observe that a
few vertices are densely located (_i.e.,_ high proximity) on the highest and
the lowest levels of the Internet, while more medium-level vertices are
sparsely distributed (_i.e.,_ low proximity). For a better illustration, we
show the terrain plot of the same 3-D space in Fig. 3(B) via IDW [42], an
interpolation metric widely used for spatial distribution estimation. The
observations are consistent with the BGP fact that a small number of ASes on
the highest hierarchy level have similar routing roles, since they all provide
transit services for other ASes and establish P2P relationships with the ASes
on the same level to form “Internet backbone”. On the contrary, it takes
multiple C2P links for another small set of ASes to reach the backbone ASes.
Thus, they lie on the lowest hierarchy level, forming several clusters with
lower Z-axis coordinate values. The rest ASes are located on the medium
hierarchy. They have different providers and customers, and serve diverse
routing roles.

Routing Role Analysis. We further study the routing roles of specific ASes to
check if the computed embedding vectors reflect their actual routing
properties in the Internet. In particular, we choose 16 Tier-1 ASes (_e.g.,_
_AT &T_), 9 major yet not Tier-1 ASes (_e.g.,_ _Telstra_), and 50 other random
stub ASes (_i.e.,_ the ASes connected to only one other AS). We present the
projections of their routing roles on both YZ-plane (Fig. 3(C)) and XY-plane
(Fig. 3(D)). The results show that the Tier-1 ASes form dense clusters on the
highest hierarchy level, the major yet not Tier-1 ASes form several dense
clusters on the levels relatively lower than those of Tier-1 ASes, and the
stub ASes are dispersed on the much lower levels. This confirms that the
computed embedding vectors preserve both the proximity and hierarchy of ASes.
Figure 3(C), however, does not exhibit distinct hierarchies, which is expected
since the Internet topology is not strictly hierarchical [36]; for example, AS
4134 (_China Telecom_) has P2P relationship with the Tier-1 AS 1299
(_Arelion_), yet it also keeps a route with 2 consecutive C2P links to reach
AS 1299.

Pairwise AS Difference Comparison. We measure the difference of routing roles
between two ASes. We choose AS pairs in three categories: (i) We randomly
sample a subset $S_{0}$ from all pairs of ASes with the P2P relationship while
enforcing the following constraint. In particular, given an AS pair, we obtain
the neighbor AS set of each AS in the pair. The AS pair is eligible only if
the Jaccard index (_i.e.,_ the similarity) of the two neighbor AS sets is
between 0% and 10%. We also sample another subset $S_{1}$ without enforcing
this constraint. (ii) We randomly sample six subsets (denoted as $N_{0}$ to
$N_{5}$) from all pairs of ASes that are not connected directly, where the
Jaccard indices of the two neighbor AS sets are between 0% and 10%, 0% and
20%, 20% and 40%, 40% and 60%, 60% and 80%, and 80% and 100%, respectively.
(iii) We randomly sample seven subsets (denoted as $H_{0}$ to $H_{6}$), where
the shortest path between two ASes in one pair is a direct P2P link, and 2, 3,
4, 5, and 6 consecutive P2C links, respectively. For instance, if two AS pairs
(_e.g.,_ AS1 and AS2, AS2 and AS3) are both in the P2C relationship, then AS1
and AS3 form two consecutive P2C links. See details in Appendix B.

For each sampled subset, we compute the difference of routing roles between
two ASes and obtain Cumulative Distribution Function (CDF) curves. We make
three types of comparisons among the CDF curves of different subsets. The
comparisons of the P2P AS pairs ($S_{0}$), P2C AS pairs ($H_{0}$) and no-
relationship AS pairs ($N_{0}$) show that $S_{0}$ has the smallest difference
and $N_{0}$ exhibits the largest difference (see Fig. 3(E)). It reveals that
BEAM preserves the first-order proximity. The comparisons among the subsets
with different degrees of neighbor intersection ($N_{1}$ to $N_{5}$) show that
if two ASes have more common neighbors (_i.e.,_ high second-order proximity),
they tend to have similar routing roles (see Fig. 3(F)). In Fig. 3(G), the
difference of routing roles increases with the number of consecutive P2C links
between two ASes, which is consistent with the nature of AS hierarchy.

##  4 The Anomaly Detection System

In this section, we develop a semantics aware routing anomaly detection system
built upon BEAM 444Our system is open source at this GitHub repository..

Figure 4: The workflow of our routing anomaly detection system built upon
BEAM.

###  4.1 System Overview

Our routing anomaly detection system is designed to detect global-scale
Internet routing anomalies. As shown in Fig. 4, our detection system consists
of three components: the routing monitor, the BEAM engine, and the anomaly
detector. The routing monitor establishes connections with global vantage
points to capture route changes in real time. The BEAM engine utilizes our
BEAM model to compute the _path difference scores_ of the route changes, which
quantifies the routing role difference between the new and the original
routing paths. Based on the path difference scores, the anomaly detector
identifies suspicious route changes, and groups the suspicious route changes
sharing the same prefix into anomalous prefix events. This is necessary to
identify the prefixes impacted by widespread routing anomalies. It further
locates the ASes responsible for each anomalous prefix event and correlates
the events caused by the same set of responsible ASes. Since the BEAM model
used in our detection system is pretrained with AS relationship data (instead
of labeled routing anomaly data), our detection is unsupervised.

###  4.2 BEAM Engine

Not all route changes are caused by routing anomalies. For instance, different
ASes of the same organization may claim the ownership of a specific prefix
simultaneously, thus generating two routing paths with different origin ASes.
This is called multiple origin AS (MOAS) [43] and should not be considered as
anomalous. Thus, the BEAM engine relies on _path difference score_ to identify
suspicious route changes.

To compute the path difference score for a route change, we design a method
based on the dynamic time warping (DTW) algorithm [44], an effective way of
measuring the overall difference between two ordered sequences of unequal
length. Specifically, given two routing paths $S=\langle
v_{1},\dots,v_{m}\rangle$ and $S^{\prime}=\langle
v^{\prime}_{1},\dots,v^{\prime}_{n}\rangle$, the DTW algorithm repeatedly
selects a pair of ASes from $S$ and $S^{\prime}$, and generates eligible
sequences of AS pairs by satisfying the following conditions: (i) Each AS in
$S$ ($S^{\prime}$) should be paired with one or more ASes from $S^{\prime}$
($S$). (ii) The first (last) AS in $S$ should be paired with the first (last)
AS in $S^{\prime}$. (iii) Given $i<j$, if $v_{i}$ and $v_{j}$ from $S$ are
paired with $v^{\prime}_{k}$ and $v^{\prime}_{l}$ in $S^{\prime}$, then there
keeps $k\leq l$; S and S’ are symmetric. For example, if $S=\langle
v_{1},v_{2},v_{3}\rangle$, $S^{\prime}=\langle
v^{\prime}_{1},v^{\prime}_{2},v^{\prime}_{3}\rangle$, then
$((v_{1},v^{\prime}_{1}),(v_{2},v^{\prime}_{2}),(v_{3},v^{\prime}_{3}))$ and
$((v_{1},v^{\prime}_{1}),(v_{1},v^{\prime}_{2}),(v_{2},v^{\prime}_{2}),(v_{3},v^{\prime}_{3}))$
are both eligible, but
$((v_{1},v^{\prime}_{1}),(v_{1},v^{\prime}_{2}),(v_{2},v^{\prime}_{1}),(v_{3},v^{\prime}_{3}))$
is ineligible because the two pairs $(v_{1},v^{\prime}_{2})$ and
$(v_{2},v^{\prime}_{1})$ violate the condition (iii). For each eligible
sequence, we sum the pairwise AS difference (given by BEAM) of its AS pairs.
Then, we choose the minimum value from all summed values as the path
difference score. The sequence of AS pairs with the minimum value is referred
to as _the optimal sequence_. Let $S[1:i]$ ($S^{\prime}[1:j]$) denote the
first $i$ ($j$) ASes in $S$ ($S^{\prime}$). We apply dynamic programming to
obtain the optimal sequence of AS pairs for $S[1:i]$ and $S^{\prime}[1:j]$
based on prior states as follows:

  * •

Given the optimal sequence for $S[1:i]$ and $S^{\prime}[1:j-1]$, add a new AS
pair $(S[i],S^{\prime}[j])$ to the sequence.

  * •

Given the optimal sequence for $S[1:i-1]$ and $S^{\prime}[1:j]$, add a new AS
pair $(S[i],S^{\prime}[j])$ to the sequence.

  * •

Given the optimal sequence for $S[1:i-1]$ and $S^{\prime}[1:j-1]$, add a new
AS pair $(S[i],S^{\prime}[j])$ to the sequence.

We choose the operation yielding the minimal sum of pairwise AS difference as
the optimal AS pair sequence for $S[1:i]$ and $S^{\prime}[1:j]$. The induction
base, _i.e.,_ the optimal AS pair sequence for $S[1:1]$ and $S^{\prime}[1:1]$,
is trivial to compute. The pseudo-code of this algorithm is presented in
Appendix E.

###  4.3 Anomaly Detector

Detecting Suspicious Route Changes. The anomaly detector first identifies
suspicious route changes caused by routing anomalies. Specifically, for a
route change, the anomaly detector checks whether its path difference score is
greater than a threshold $th_{d}$, which is dynamically computed using
historical legitimate route changes (detailed in §5.2). If so, the route
change is regarded as _suspicious_.

Identifying Anomalous Prefixes. It is necessary to prioritize the widespread
routing anomalies captured by multiple vantage points. Towards this end, the
anomaly detector groups the suspicious route changes that impact the same
prefix into different _prefix events_ , where each event is associated with a
specific prefix and sorts the suspicious route changes by their occurrence
time. For each event, the anomaly detector applies a sliding window to count
the number of individual vantage points that observe suspicious route changes
within the window. If this number is above a threshold $th_{v}$ (detailed in
§5.2), we consider the prefix event is associated with a widespread routing
anomaly and regard the event as anomalous.

Locating Responsible ASes. The misbehaved ASes that are responsible for
routing anomalies may impact multiple prefixes simultaneously. To obtain
comprehensive information about the affected prefixes in each routing anomaly,
the anomaly detector correlates all anomalous prefix events based on their
responsible ASes. In particular, for each suspicious route change associated
with an anomalous prefix event, our detector identifies the ASes that either
appear in the new path or in the original path. Then, we compute the
intersection of these ASes from all route changes as the responsible ASes for
the anomalous prefix event. Given two prefix events, if their time ranges have
overlaps and they have common responsible ASes, we consider they are
correlated. Thereby, we can divide all anomalous prefix events into multiple
sets, where each event only correlates with the other events in the same set
(_i.e.,_ no cross-set correlation). Finally, our anomaly detector treats each
set as an individual routing anomaly and outputs an alarm that specifies both
the affected prefixes and the responsible ASes. The additional details of our
detection system is supplemented in Appendix E.

##  5 Experimental Results

In this section, we evaluate the path difference scores and perform
experiments with real-world BGP data. We also deploy our system at a large ISP
to verify its effectiveness in practice.

###  5.1 Measuring Path Difference Score

Figure 5: Statistical comparisons of path difference scores between anomalous
and legitimate route changes.

We use real-world route announcements to analyze both legitimate and anomalous
route changes in terms of path difference scores. We collect 18 reports on
historical routing anomalies spanning from 2008 to 2021, including 15 BGP
hijacking (2 prefix and 13 subprefix hijacking) and 3 BGP route leak
incidents. For each anomaly, we obtain manually confirmed information (_e.g.,_
the time of anomalies and the affected prefixes) from two authoritative
sources, the Oracle blogs [45] and the BGPStream monitor [46]. Based on the
information, we fetch all route announcements 12 hours before and after the
anomalies from RouteViews [47] and obtain 18 datasets. The total number of
collected route announcements is 11,861,377,951. In each dataset, we identify
the anomalous route changes with the confirmed information of the anomaly. The
anomalous route changes in our datasets cover both _origin change_ (_i.e.,_
two routing paths have different origin ASes) and _path change_ (_i.e.,_ two
routing paths share the same origin yet traverse different ASes). We also
locate legitimate route changes such as origin changes incurred by the
multiple origin AS issue [43]. The details are in Appendix C and D.

Figure 5 shows the path difference scores measured by the BEAM engine on the
18 datasets. The path difference scores of anomalous route changes are much
higher than those of legitimate ones, indicating that routing anomalies would
significantly change the routing roles of ASes on the routing paths. For
instance, the anomalous route changes in $SO_{pakistan}$ changed the origin AS
from AS 36561 (_YouTube_) to AS 17557 (_Pakistan Telecom_). These two origin
ASes are significantly different in their neighbors, geographic locations and
hierarchical levels in the Internet. In contrast, the different origin ASes in
a legitimate route change often belong to the same organization and their
neighbors are more similar (_e.g.,_ the same upstream AS), resulting in much
smaller routing role churn between the original and new routes.

###  5.2 Routing Anomaly Detection Results

Table 1: Detection results on the 18 real-world datasets. The ✓/✗ indicates whether the confirmed anomaly of a dataset is _detected_. If _detected_ , the number of all raised alarms (#Alarms) and that of false alarms (#FalseAlarms) are presented in bold. Dataset | Detected | #Alarms(#FalseAlarms)
---|---|---
ED |  JI | Li |  Ma | NV |  SD | LS |  AV | Ours |  ED | JI |  Li | Ma |  NV | SD |  LS | AV |  Ours
${SP}_{backcon\\_5}$ | ✓ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✗ |  ✗ | ✓ |  18(5) | 12(3) |  21(4) | 15(3) |  17(2) | 9(1) |  62(31) | 5(1) |  34(2)
${SP}_{backcon\\_4}$ | ✓ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✓ |  ✓ | ✓ |  14(1) | 8(1) |  15(2) | 13(1) |  12(1) | 7(1) |  42(17) | 22(6) |  21(0)
${SP}_{backcon\\_2}$ | ✓ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✓ |  ✗ | ✓ |  29(7) | 21(7) |  24(5) | 25(7) |  21(4) | 8(3) |  38(13) | 23(18) |  37(1)
${SP}_{bitcanal\\_1}$ | ✗ |  ✗ | ✗ |  ✓ | ✓ |  ✗ | ✗ |  ✗ | ✓ |  16(0) | 16(0) |  14(0) | 18(0) |  17(0) | 7(0) |  67(36) | 30(10) |  16(0)
${SP}_{petersburg}$ | ✓ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✓ |  ✓ | ✓ |  22(3) | 14(0) |  21(3) | 20(1) |  16(0) | 12(2) |  66(28) | 37(16) |  24(0)
${SP}_{defcon}$ | ✓ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✓ |  ✓ | ✓ |  7(2) | 7(2) |  9(3) | 9(3) |  9(3) | 2(2) |  28(10) | 17(9) |  7(1)
${SO}_{iran}$ | ✓ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✗ |  ✗ | ✓ |  15(1) | 8(1) |  24(5) | 12(2) |  16(3) | 0(0) |  21(11) | 19(10) |  31(2)
${SO}_{bitcanal\\_3}$ | ✗ |  ✗ | ✗ |  ✗ | ✓ |  ✗ | ✗ |  ✗ | ✓ |  26(4) | 24(3) |  29(6) | 25(3) |  26(5) | 7(0) |  44(19) | 17(8) |  40(1)
${SO}_{backcon\\_3}$ | ✓ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✗ |  ✗ | ✓ |  32(8) | 23(4) |  27(6) | 34(8) |  34(9) | 6(1) |  49(27) | 19(9) |  35(5)
${SO}_{backcon\\_1}$ | ✓ |  ✗ | ✓ |  ✓ | ✓ |  ✗ | ✗ |  ✗ | ✓ |  19(6) | 16(4) |  35(14) | 18(4) |  17(7) | 0(0) |  63(35) | 25(11) |  18(3)
${SO}_{bitcanal\\_2}$ | ✗ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✗ |  ✗ | ✓ |  16(1) | 15(1) |  17(2) | 15(1) |  16(1) | 12(2) |  39(14) | 29(8) |  24(0)
${SO}_{h3s}$ | ✓ |  ✗ | ✓ |  ✓ | ✓ |  ✗ | ✓ |  ✗ | ✓ |  11(1) | 3(0) |  15(3) | 12(2) |  9(0) | 5(1) |  38(22) | 27(8) |  14(0)
${SO}_{pakistan}$ | ✓ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✗ |  ✗ | ✓ |  12(4) | 8(2) |  9(2) | 10(4) |  8(1) | 1(0) |  26(14) | 2(0) |  10(1)
${PO}_{brazil}$ | ✓ |  ✓ | ✓ |  ✓ | ✓ |  ✗ | ✗ |  ✓ | ✓ |  30(5) | 32(4) |  30(5) | 37(5) |  25(3) | 11(2) |  52(25) | 28(11) |  51(1)
${PO}_{sprint}$ | ✗ |  ✗ | ✗ |  ✗ | ✗ |  ✗ | ✓ |  ✗ | ✓ |  20(0) | 18(0) |  16(0) | 22(2) |  19(2) | 10(2) |  84(24) | 33(8) |  29(0)
${RL}_{jtl}$ | ✗ |  ✗ | ✗ |  ✗ | ✗ |  ✗ | ✓ |  ✗ | ✓ |  17(1) | 16(1) |  21(2) | 16(2) |  17(1) | 6(3) |  60(40) | 21(11) |  46(5)
${RL}_{stelkom}$ | ✗ |  ✓ | ✗ |  ✗ | ✗ |  ✗ | ✓ |  ✗ | ✓ |  25(4) | 21(2) |  34(6) | 26(3) |  23(3) | 4(0) |  284(225) | 17(8) |  43(3)
${RL}_{itregion}$ | ✗ |  ✗ | ✗ |  ✗ | ✗ |  ✗ | ✓ |  ✗ | ✓ |  25(0) | 21(1) |  23(0) | 20(0) |  21(3) | 6(2) |  74(44) | 23(9) |  44(4)
Overall | 11/18 |  11/18 | 12/18 |  13/18 | 14/18 |  0/18 | 9/18 |  4/18 | 18/18 |  354(53) | 283(36) |  384(68) | 347(51) |  323(48) | 113(22) |  1137(635) | 394(161) |  524(29)

We now validate the performance of our detection system. Since RouteViews
archives the RIB data (_i.e.,_ the snapshot of routing table) of global
vantage points bi-hourly, for each dataset, we fetch the most recent RIB data
before the confirmed anomaly to initialize the routing tables that our
detection system monitors. Then we use the route announcements observed within
two hours as input, which include all routes associated with the confirmed
anomaly and enough legitimate route changes. We set the sliding window length
to two hours for the same reason. The thresholds $th_{d}$ and $th_{v}$ are
decided by historical data. Specifically, we use the observed path difference
scores for all legitimate route changes two hours before the current window as
a reference distribution, and set $th_{d}$ as the knee point of its CDF curve.
$th_{v}$ is determined similarly. The calculation of the knee point is
automated via kneed [48].

To systematically evaluate our system, we substitute the BEAM engine with
other commonly used features or representation learning models to create
variants of our detection system. In particular, we create 6 variants: ED uses
the edit distance [49] to measure path difference; JI uses the Jaccard index
of neighbor AS sets to measure the similarity of two ASes; Li, Ma, NV and SD
uses the general network representation model Line [37], Marine [50], node2vec
[51] and SDNE [52] to train embedding vectors, respectively, and utilize
Euclidean distance of embedding vectors to measure the similarity of two ASes.
All these variants are well-trained and use the same settings as our detection
system. Moreover, we compare our system with two state-of-the-art ML-based BGP
anomaly detection approaches: AV [30] and LS [22]. AV and LS identify
anomalous route changes and the time intervals where anomalies occur,
respectively. For fair comparisons, we apply our anomaly detector to aggregate
their detection results into different alarms (see Appendix G). We do not
compare our work with the active probing-based systems like [10, 15] because
they heavily rely on the real-time probing results collected by many data-
plane facilities. These real-time probing results are not available for our
historical datasets.

Each detection system may raise multiple alarms for a dataset. Each alarm
reports a potential routing anomaly. If any alarm matches the confirmed
information, _i.e.,_ the target prefix is reported as one of the anomalous
prefixes and the misbehaved ASes are also identified as responsible, we
consider the confirmed anomaly in this dataset as _detected_. Besides the
confirmed anomaly, there could be other alarms that indicate unrevealed
routing anomalies or are simply false alarms. It is difficult to contact the
operators to further confirm these potential anomalies since most anomalies
occurred long ago. To verify these unknown alarms, we define four anomalous
route change patterns that represent typical routing anomalies based on domain
knowledge and authorized data such as RPKI validation states. If an alarm
matches at least one pattern, we consider it a true alarm with high
confidence, otherwise it is a _false alarm_. These patterns are as follows:

  * •

P1 (Unauthorized Route Change): The origin ASes before and after the route
change belong to different organizations and have different RPKI validation
states, _i.e.,_ one in the _invalid_ASN_ state and the other in the _valid_
state [7].

  * •

P2 (Route Leak): The routing path before or after the route change violates
the valley-free criterion [32].

  * •

P3 (Path Manipulation): The routing path before or after the route change
contains reserved ASNs or adjacent ASes that have no business relationship
records between them [11].

  * •

P4 (ROA Misconfiguration): The origin ASes before and after the change are
from the same organization but have different RPKI validation states, _i.e.,_
one in the _invalid_length_ or _invalid_ASN_ state and the other in the
_valid_ state [53].

These patterns are endorsed by the domain experts from a large ISP where we
deployed our system. They also apply these patterns to verify our real-world
detection results (see §5.5). Note that these patterns alone _should not_ be
used to detect routing anomalies directly because they cannot correlate
massive route changes with the same root cause, which would result in too many
false alarms. We discuss the rationale behind these patterns in Appendix F.

Table 1 shows that all previously-confirmed 18 routing anomalies are correctly
detected by our system within tens of alarms. Further, our system reports no
false alarms for 6 datasets that cover the confirmed anomalies, and only 5
false alarms in the worst case. These false alarms are mainly related to route
engineering practices such as AS prepending [54], while some involve stub ASes
with limited connections. In contrast, the baselines cannot detect all these
anomalies and raise more false alarms than ours (except for SD that cannot
detect any anomalies). Besides, the baselines require many extra data to train
the models, _e.g.,_ AV needs RIB entries in every two hours and LS requires a
large amount of training data to eliminate the negative impacts of label
noises. Moreover, AV cannot detect transient anomalies and LS incurs high FP
due to per-minute anomaly detection. Please see the details in Appendix G.
Overall, our detection system outperforms these baselines by significant
margins. In summary, (i) our system addresses the key challenges of ML-based
detection methods and realize effective Internet routing anomaly detection.
(ii) compared with our BEAM model, general network representation learning
models are not able to effectively capture BGP semantics for routing anomaly
detection.

###  5.3 Runtime Overhead

Our system runs on a Linux server with Intel Xeon E5-2650v4 (2.20GHz). We
present its runtime overhead in Fig. 6. The X-axis displays the datasets in
their chronological order, with the later datasets containing more ASes in
operation. The number of ASes in our datasets increases from 27,588 to 73,014
over the entire period. The top figure shows the average time it takes to
process every 15 minutes of data from each dataset. The error bar reflects the
95% confidence interval. The variance in processing time is mostly caused by
the variance in the sizes of 15-minute data. The processing time is less than
100 seconds in most cases, indicating that the increase of ASes only slightly
impacts our system’s runtime overhead. The largest processing time ($\sim$140s
in $RL_{jtl}$) is still much smaller than 15 minutes, meaning that our system
can effectively process the stream of global route announcements in real time.
The bottom figure plots the average time it takes to process every 1,000 route
changes. Due to the caching employed by our system (_e.g.,_ the caching of
path difference scores), the anomaly detector spends much less time at the
steady state ($\sim$0.05s per 1,000 route changes), compared with the cold
start ($\sim$0.2s).

Figure 6: The runtime overhead of our detection system.

###  5.4 Robustness Analysis

We analyze the robustness of our system given noisy AS relationship data,
which is created by modifying or deleting the original AS relationships in the
CAIDA dataset. We consider four types of noisy datasets. In particular, given
a noise ratio $r$, we first randomly select $r\%$ AS relationships, and then
flip their labels (_i.e.,_ changing P2P to P2C and P2C to P2P) to produce the
R1 dataset, or delete them to create the R2 dataset. R1 and R2 represent the
noisy dataset caused by inaccurate and incomplete AS relationship inference,
respectively. To create another two types of noisy datasets, we first select
top-$r\%$ AS relationships with the fewest BGP routes that use their
underlying AS-to-AS links and create the W1 dataset by flipping their labels
and W2 by deleting them. These two types of noisy data are common in the
Internet because the AS relationships serving fewer routes are more likely to
be mislabeled due to their limited Internet visibility.

We train our system with each noisy dataset independently and evaluate its
detection performance following the same steps in §5.2. We repeat each
experiment for 5 times to avoid bias and plot the results in Fig. 7. The error
bar shows the 95% confidence interval. Even when the noise ratio reaches 20%,
our system still detects at least 17 true anomalies (18 in total) and only
generates less than 40 false alarms across all datasets. Note that such a high
noise ratio is rare in practice. These results demonstrate the robustness of
our system under noisy AS relationship data.

Figure 7: Detection results given noisy AS relationships.

###  5.5 Real-World Deployment

We deploy our detection system in the main operational AS of a large ISP to
evaluate its performance in practice. Based on the customer cone size, the AS
rank is in the global top 100 [55]. At the time of our deployment, the AS
maintains live BGP sessions with about 500 neighbors, including 14 Tier-1
ASes. Thereby, the AS has a fairly comprehensive view on the Internet-wide
routing paths. We set up our detection system in a server that receives real-
time incoming route announcements from all BGP routers within the AS via the
iBGP protocol. We train the BEAM engine of our system using the latest CAIDA
AS relationship dataset collected at the time of our deployment, which
includes 74,923 ASes and 505,927 AS business relationship records. The sliding
window length of our system is one hour. We use the same parameter settings
and the method of identifying false alarms as described in §5.2. To reduce the
repetitive alarms raised in different time windows, we aggregate the alarms
sharing the same anomalous prefix and responsible AS.

The system is online since Jaunary 1, 2023. We analyze the generated results
from January 1 to February 1, 2023. In total, the system processes 152,493,303
live route announcements during this month, detects 5,106,442 route changes
and raises 548 alarms. We show the alarms’ impact and daily statistics in
Table 2 and Fig. 8, respectively. On average, our system identifies 17.68
alarms per day. The domain experts of the ISP carefully verify the correctness
of each alarm based on the patterns described in §5.2. They find that most
alarms (497 out of 548) indicate real routing anomalies, _i.e.,_ true alarms.
These true alarms, not detected by the ISP’s existing routing security
mechanisms, include 84 unauthorized route changes (P1), 123 route leaks (P2),
270 path manipulations (P3) and 20 ROA misconfiguration (P4). The
interpretability of these alarms greatly facilitates the identification of
anomaly sources (see §6 for detailed case study). More importantly, our system
only raises an average of 1.65 false alarms per day. These false alarms can be
further eliminated with minimal intervention (see discussions in §7). Overall,
our detection system demonstrates promising results in real-world deployment.

We further investigate _how many anomalies are caught by an existing security
mechanism but not our system_. First, we check whether our system misses the
anomalies detected by the ISP’s existing security mechanism. The ISP detects
invalid routes based on its customers’ IRRs. However, due to the incomplete
coverage of prefixes, the ISP’s security mechanism does not generate any alarm
during our system’s deployment. Thus, our system does not miss any alarm
raised by the ISP itself. Next, we check whether there are real routing
anomalies missed by both our system and the ISP itself. This requires a
reliable source for BGP incidents. Although BGPstream is a promising
candidate, we cannot use it in our paper because its vantage points are quite
different from those of the ISP, which would introduce non-negligible
experimental bias. Therefore, we use the RPKI validation results as a
reference. Specifically, among all the RPKI-invalid announcements that are
generated during our system’s deployment, our system only misses about 2.25%
of them and most of the missed ones are due to the limited Internet
visibility, _i.e.,_ only a few vantage points observe these invalid
announcements. Overall, this result indicates our system has very low false
negatives.

Ethics. We operate our detection system in compliance with the ISP’s
policy/agreement and under the close supervision of ISP’s administrators. Our
evaluation does not involve any sensitive or privacy data. We only collect
results for analysis and do not interfere with Internet routing operations.

Table 2: The overall impact of the detected anomalies. #Affected Routes | #Affected Prefixes |  #Affected Origins
---|---|---
1,202 | 961 |  477
Figure 8: Daily alarm number in real-world deployment.

##  6 Case Study

Figure 9:  Typical anomalous/legitimate route changes.  In each plot, the heat
map (left) displays the path difference score at each AS pairing step of DTW
in a top-to-bottom and left-to-right order. The white arrows show the optimal
sequence of AS pairs. The embedding map (right) represents embedding vectors
in a 2-D plane. The purple dots denote the common neighbors of the two routing
paths, while the orange and cyan dots correspond to the exclusive neighbors
for the new and old paths, respectively.

In this section, we illustrate the interpretability of our detection results
by analyzing four detected anomalies: three from historical events (Cases 1-3)
and one from our real-world deployment (Case 4). Cases 1-3 each cover a
different category of routing anomalies, _i.e.,_ origin change, path change,
and route leak. In each case, we compare a representative anomalous route
change with a legitimate one that occurred on the same day. To interpret the
difference between routing paths, we apply two visualization techniques: the
heat map of the path difference scores and the embedding map of the routing
roles. In particular, the heat map shows the path difference scores for the
eligible sequences of AS pairs and marks the optimal sequence identified by
DTW. The embedding map, generated by t-SNE [41], visualizes the routing roles
of the ASes to illustrate the deviations between two paths.

Case 1. Figure 9(A) shows the origin change in $SO_{pakistan}$, where AS 17557
(_Pakistan Telecom_) hijacked a subprefix of AS 36561 (_YouTube_) by
announcing 208.65.153.0/24. Figure 9(A)(I) sees the anomalous pattern that
most ASes on the new path are different from those on the old path. The two
origin ASes, AS 17557 and AS 36561, are far apart in the embedding map with
few common neighbors, indicating very different routing roles. Thus, their
route announcements would traverse quite different paths before they
eventually converge on AS 5503. This pattern also appears in the heat map,
where the path difference score rises sharply as the AS pairing operation
proceeds, because the ASes from two paths are completely different after a few
steps. In contrast, Fig. 9(A)(II) shows a legitimate route change on the same
day with low path difference scores and almost overlapping paths in the
embedding map, because the legitimate route update changes the origin from AS
6198 to AS 6197, both operated by _BellSouth Network_ and with similar routing
roles.

Case 2. Figure 9(B) shows the path change in $SP_{backcon\\_2}$, where AS
203959 (_BackConnect_) hijacked a subprefix of AS 25761 (_Staminus Comm._) by
faking a nonexistent routing path to the real origin AS. The embedding map
reveals that the fake path detours significantly from the real one, as AS
203959 is neither on the real path nor similar to any ASes on it in terms of
routing roles. The heat map also indicates an upsurge in the path difference
score in the AS pairing. The optimal sequence of AS pairs greatly deviates
from the diagonal of the heat map because no AS is similar to AS 203959 in the
counterpart. In contrast, the paths in the legitimate route change are similar
in routing roles; we leave the analysis to the reader.

Case 3. Figure 9(C) shows the route leak in $RL_{JTL}$, where AS 36866 (_JTL_)
received the route to 156.0.233.0/24 from its provider AS 8966 (_Emirates
Tel._) and leaked it to its another provider AS 37662 (_WIOCC_). The leaked
route results in a much longer path through AS 37662 that detours
significantly from the original one. It also violates the valley-free
criterion. Accordingly, the heat map shows high path difference scores and the
optimal sequence forms a hump-like pattern away from the diagonal. In
contrast, the legitimate route change has minor path difference; we leave the
analysis to the reader.

Case 4. We represent the first alarm reported by our system during its real-
world deployment in Fig. 10. This alarm, labeled Alarm 0, starts at 01:04:40,
January 1, 2023, and lasts about 1 hour and 24 minutes, affecting three
prefixes and six routes observed by two individual vantage points. The top
part of Fig. 10 provides an overview of this alarm. The bottom part of Fig. 10
further plots a representative route change event captured by this alarm
observed from AS 6453. In this event, AS 42440 (_RDG-AS_) announces
185.88.179.0/24, which is owned by AS 201691 (_WEIDE_), without authorization
(its RPKI validation state is _invalid_ASN_). Moreover, AS 42440 is also on
the path before the route change, indicating a Type-5 route leak as described
in RFC 7908 [56]. This pattern also appears in the heat map. The optimal
sequence before AS 42440 follows the diagonal and the path difference score
increases sharply after AS 42440, indicating a significant change of routing
roles. The embedding map also demonstrates the clear difference between AS
42440 and AS 201691.

Figure 10: An anomaly report in real-world deployment.

##  7 Discussion

Per-Prefix Threshold. Our system uses the same detection threshold values
(_i.e.,_ $th_{d}$ and $th_{v}$) for all prefixes. Assigning an individual
threshold for each prefix may gain better results. But it will incur
significant computational overheads and large detection delays due to the
large number of prefixes in the Internet (_i.e.,_ over 940k IPv4 and 200k IPv6
prefixes in November 2023), which is inappropriate for online detection.

Reducing False Alarms. We can apply two heuristics to further reduce our
system’s false alarms. (i) Since most route hijacks and route leaks are short-
lived [10], we can label the long-lived routes as normal. (ii) The different
origin ASes in a legitimate MOAS event usually have similar routing
characteristics [43] (_e.g.,_ from the same organization) while the malicious
ASes do not. We leave the application of both heuristics in our system to
future work.

Adaptive Attacks. An adaptive attacker may attempt to bypass our system by
mimicking the normal ASes’ routing roles, yet it is very difficult in
practice. Specifically, to imitate a normal AS’s routing role, a malicious AS
has to establish business relationships with the normal AS’s neighbors, which
is time-consuming and would reduce the malicious AS’s stealthiness due to the
possible scrutiny required for establishing neighboring relationships.
Further, to make the routing roles of a forged path similar to those of a real
path, the attacker has to control multiple ASes on the forged path. Our
empirical study (presented in detail in Appendix H) reveals that it requires
the attacker to control at least two ASes and establish hundreds of new AS
relationships to make the routing roles of a forged path similar to those of a
real path. This is considerably intractable in practical scenarios.

Evolving Routing Roles. AS routing roles evolve as ASes update routing
policies. Our system is resilient against routing role evolution. Per §5, even
if the time gap between training and detection is over 30 days (_i.e.,_ the
dataset update cycle), our system still performs well. Moreover, we can
retrain BEAM with latest AS relationships to keep up with the routing role
evolution. It takes $\sim$10 hours to train the model on our platform with
GeForce RTX 2080 Ti, which is acceptable since CAIDA releases a new dataset
roughly every month.

Detection with Unknown ASes. BEAM cannot learn routing roles of ASes whose
relationships with other ASes are unknown (_i.e.,_ unknown ASes). Fortunately,
the existing study [36] has revealed AS relationships for most ASes absent in
the dataset. For instance, there are only 368 unknown ASes in the most recent
events that we analyze, which is only 0.5040% of the total ASes. Further, our
measurement study discovered that some unknown ASes use the AS numbers that
are reserved for private use [57]. The routing paths containing such unknown
ASes should be regarded as anomalous.

##  8 Related Work

Traditional Routing Anomaly Detection. The existing studies consist of the
control-plane based [11, 18, 17], the data-plane based [16, 14, 9] and the
hybrid methods [12, 15, 10, 13]. The control-plane based methods maintain the
normal/authoritative route information for each prefix and check if the newly
received route contradicts it. The data-plane based methods identify routing
anomalies by analyzing the reachability from multiple hosts to the target
prefix. However, these traditional approaches require non-trivial manual
investigation from network operators, _e.g.,_ collecting the normal route
information of each prefix, and deploying vast network probes to monitor the
prefixes in the world, which incurs unacceptable operation overhead for
deployment.

ML Based Routing Anomaly Detection. Machine learning is utilized to detect
routing anomalies [19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31].
Shapira _et al._ [30] (AV) use unsupervised word embedding to model routes.
But AV fails to detect transient anomalies due to its reliance on RIB
snapshots and suffers from non-trivial retraining overheads. Dong _et al._
[22] and Hoarau _et al._ [29] perform supervised classification on BGP time
series. Both require large-scale labeled datasets, which is hard to achieve in
practice. Moreover, all these methods cannot provide interpretable results,
incurring great manual efforts for validation.

Application of Network Representation Learning. Network representation
learning (NRL) [58] aims to learn latent, low-dimensional representations of
network vertices, while preserving network characteristics, _e.g.,_ the
structure information and vertex content, where the learnt representations can
be used for downstream tasks. NRL has been applied in various domains, _e.g.,_
social network analysis [59, 60, 61], recommendation system [62, 63, 64], and
anomaly detection [65, 66, 67]. In this paper, we develop a BGP semantics
aware NRL model to measure ASes’ routing roles for routing anomaly detection.

##  9 Conclusion

In this paper, we present a routing anomaly detection system centering around
a novel network representation learning model named BEAM. The core design of
BEAM is to accurately learn the routing roles of Internet ASes by
incorporating the BGP semantics. As a result, routing anomaly detection, given
BEAM, is reduced to discovering unexpected routing role churns upon observing
new route announcements. We implement a prototype of our routing anomaly
detection system and extensively evaluate its performance using 18 real-world
RouteViews datasets containing over 11 billion route announcement records. The
results demonstrate that our system can detect all previously-confirmed
routing anomalies within an acceptable number of alarms. We also perform one
month of real-world detection at a large ISP and detect 497 true anomalies in
the wild with only 1.65 daily false alarms on average, demonstrating the
practical feasibility of our system.

## References

  * [1] M. Doug, “Large european routing leak sends traffic through china telecom,” Oracle blog, 2019. [Online]. Available: https://blogs.oracle.com/internetintelligence/
  * [2] S. Aftab, “A major bgp hijack by as55410-vodafone idea ltd,” MANRS blog, 2021\. [Online]. Available: https://www.manrs.org/2021/04/a-major-bgp-hijack-by-as55410-vodafone-idea-ltd/
  * [3] C. Catalin, “Klayswap crypto users lose funds after bgp hijack,” The Record blog, 2022. [Online]. Available: https://therecord.media/klayswap-crypto-users-lose-funds-after-bgp-hijack/
  * [4] M. Lepinski and K. Sriram, “Bgpsec protocol specification,” _RFC 8205, IETF_ , 2017.
  * [5] P. v. Oorschot, T. Wan, and E. Kranakis, “On interdomain routing security and pretty secure bgp (psbgp),” _TISSEC_ , vol. 10, no. 3, pp. 11–es, 2007.
  * [6] S. Kent, C. Lynn, and K. Seo, “Secure border gateway protocol (s-bgp),” _J-SAC_ , vol. 18, no. 4, pp. 582–592, 2000.
  * [7] P. Mohapatra, J. Scudder, D. Ward, R. Bush, and R. Austein, “Bgp prefix origin validation,” in _IETF RFC 6811_ , 2013.
  * [8] W. Chen, Z. Wang, D. Han, C. Duan, X. Yin, J. Yang, and X. Shi, “Rov-mi: Large-scale, accurate and efficient measurement of rov deployment,” in _NDSS_ , 2022.
  * [9] C. Zheng, L. Ji, D. Pei, J. Wang, and P. Francis, “A light-weight distributed scheme for detecting ip prefix hijacks in real-time,” _SIGCOMM CCR_ , vol. 37, no. 4, pp. 277–288, 2007.
  * [10] P.-A. Vervier, O. Thonnard, and M. Dacier, “Mind your blocks: On the stealthiness of malicious bgp hijacks.” in _NDSS_ , 2015.
  * [11] P. Sermpezis, V. Kotronis, P. Gigis, X. Dimitropoulos, D. Cicalese, A. King, and A. Dainotti, “Artemis: Neutralizing bgp hijacking within a minute,” _TON_ , vol. 26, no. 6, pp. 2471–2486, 2018.
  * [12] J. Schlamp, R. Holz, Q. Jacquemart, G. Carle, and E. W. Biersack, “Heap: reliable assessment of bgp hijacking attacks,” _J-SAC_ , vol. 34, no. 6, pp. 1849–1861, 2016.
  * [13] X. Hu and Z. M. Mao, “Accurate real-time identification of ip prefix hijacking,” in _S &P_. IEEE, 2007, pp. 3–17.
  * [14] J. Li, T. Ehrenkranz, and P. Elliott, “Buddyguard: A buddy system for fast and reliable detection of ip prefix anomalies,” in _ICNP_. IEEE, 2012, pp. 1–10.
  * [15] X. Shi, Y. Xiang, Z. Wang, X. Yin, and J. Wu, “Detecting prefix hijackings in the internet with argus,” in _IMC_ , 2012, pp. 15–28.
  * [16] Z. Zhang, Y. Zhang, Y. C. Hu, Z. M. Mao, and R. Bush, “ispy: Detecting ip prefix hijacking on my own,” in _SIGCOMM_ , 2008, pp. 327–338.
  * [17] J. Li, D. Dou, Z. Wu, S. Kim, and V. Agarwal, “An internet routing forensics framework for discovering rules of abnormal bgp events,” _SIGCOMM CCR_ , vol. 35, no. 5, pp. 55–66, 2005.
  * [18] H. Yan, R. Oliveira, K. Burnett, D. Matthews, L. Zhang, and D. Massey, “Bgpmon: A real-time, scalable, extensible monitoring system,” in _CATCH_. IEEE, 2009, pp. 212–223.
  * [19] M. Cheng, Q. Xu, L. Jianming, W. Liu, Q. Li, and J. Wang, “Ms-lstm: A multi-scale lstm model for bgp anomaly detection,” in _ICNP_. IEEE, 2016, pp. 1–6.
  * [20] C. Testart, P. Richter, A. King, A. Dainotti, and D. Clark, “Profiling bgp serial hijackers: capturing persistent misbehavior in the global routing table,” in _IMC_ , 2019, pp. 420–434.
  * [21] M. Cheng, Q. Li, J. Lv, W. Liu, and J. Wang, “Multi-scale lstm model for bgp anomaly classification,” _TSC_ , 2018.
  * [22] Y. Dong, Q. Li, R. O. Sinnott, Y. Jiang, and S. Xia, “Isp self-operated bgp anomaly detection based on weakly supervised learning,” in _ICNP_. IEEE, 2021, pp. 1–11.
  * [23] B. Al-Musawi, P. Branch, and G. Armitage, “Detecting bgp instability using recurrence quantification analysis (rqa),” in _IPCCC_. IEEE, 2015, pp. 1–8.
  * [24] N. M. Al-Rousan and L. Trajković, “Machine learning models for classification of bgp anomalies,” in _HPSR_. IEEE, 2012, pp. 103–108.
  * [25] A. Lutu, M. Bagnulo, J. Cid-Sueiro, and O. Maennel, “Separating wheat from chaff: Winnowing unintended prefixes using machine learning,” in _INFOCOM_. IEEE, 2014, pp. 943–951.
  * [26] S. Deshpande, M. Thottan, T. K. Ho, and B. Sikdar, “An online mechanism for bgp instability detection and analysis,” _TOC_ , vol. 58, no. 11, pp. 1470–1484, 2009.
  * [27] G. Theodoridis, O. Tsigkas, and D. Tzovaras, “A novel unsupervised method for securing bgp against routing hijacks,” in _ISCIS_. Springer, 2013, pp. 21–29.
  * [28] T. Shapira and Y. Shavitt, “A deep learning approach for ip hijack detection based on asn embedding,” in _NetAI_ , 2020, pp. 35–41.
  * [29] K. Hoarau, P. U. Tournoux, and T. Razafindralambo, “Suitability of graph representation for bgp anomaly detection,” in _LCN_. IEEE, 2021, pp. 305–310.
  * [30] T. Shapira and Y. Shavitt, “Ap2vec: an unsupervised approach for bgp hijacking detection,” _TNSM_ , vol. 19, no. 3, pp. 2255–2268, 2022.
  * [31] O. R. Sanchez, S. Ferlin, C. Pelsser, and R. Bush, “Comparing machine learning algorithms for bgp anomaly detection using graph features,” in _Big-DAMA_ , 2019, pp. 35–41.
  * [32] L. Gao, “On inferring autonomous system relationships in the internet,” _TON_ , vol. 9, no. 6, pp. 733–745, 2001.
  * [33] H. Ballani, P. Francis, and X. Zhang, “A study of prefix hijacking and interception in the internet,” _SIGCOMM CCR_ , vol. 37, no. 4, pp. 265–276, 2007.
  * [34] L. Prehn and A. Feldmann, “How biased is our validation (data) for as relationships?” in _IMC_ , 2021, pp. 612–620.
  * [35] V. Giotsas, M. Luckie, B. Huffaker, and K. Claffy, “Inferring complex as relationships,” in _IMC_ , 2014, pp. 23–30.
  * [36] M. Luckie, B. Huffaker, A. Dhamdhere, V. Giotsas, and K. Claffy, “As relationships, customer cones, and validation,” in _IMC_ , 2013, pp. 243–256.
  * [37] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in _WWW_ , 2015, pp. 1067–1077.
  * [38] CAIDA. AS Relationships Dataset. Accessed Dec. 10, 2021. [Online]. Available: https://www.caida.org/catalog/datasets/as-relationships/
  * [39] Z. Jin, X. Shi, Y. Yang, X. Yin, Z. Wang, and J. Wu, “Toposcope: Recover as relationships from fragmentary observations,” in _IMC_ , 2020, pp. 266–280.
  * [40] H. Robbins and S. Monro, “A stochastic approximation method,” _Ann. Math. Stat._ , pp. 400–407, 1951.
  * [41] L. Van der Maaten and G. Hinton, “Visualizing data using t-sne.” _J. Mach. Learn. Res._ , vol. 9, no. 11, 2008.
  * [42] G. Y. Lu and D. W. Wong, “An adaptive inverse-distance weighting spatial interpolation technique,” _Comput Geosci_ , vol. 34, no. 9, pp. 1044–1055, 2008.
  * [43] X. Zhao, D. Pei, L. Wang, D. Massey, A. Mankin, S. F. Wu, and L. Zhang, “An analysis of bgp multiple origin as (moas) conflicts,” in _SIGCOMM WS_ , 2001, pp. 31–35.
  * [44] D. J. Berndt and J. Clifford, “Using dynamic time warping to find patterns in time series.” in _KDD workshop_ , vol. 10, no. 16. Seattle, WA, USA:, 1994, pp. 359–370.
  * [45] “Oracle blogs,” Accessed Dec. 10, 2021. [Online]. Available: https://blogs.oracle.com/internetintelligence/
  * [46] BGPStream. All Events for BGP Stream. Accessed Dec. 10, 2021. [Online]. Available: https://bgpstream.com/
  * [47] University of Oregon Route Views Project. MRT format RIBs and UPDATEs. Accessed Dec. 10, 2021. [Online]. Available: http://routeviews.org/
  * [48] K. Arvai, “kneed.” [Online]. Available: https://github.com/arvkevi/kneed
  * [49] E. S. Ristad and P. N. Yianilos, “Learning string-edit distance,” _PAMI_ , vol. 20, no. 5, pp. 522–532, 1998.
  * [50] M.-H. Feng, C.-C. Hsu, C.-T. Li, M.-Y. Yeh, and S.-D. Lin, “Marine: Multi-relational network embeddings with relational proximity and node attributes,” in _ACM WWW_ , 2019, pp. 470–479.
  * [51] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _SIGKDD_ , 2016, pp. 855–864.
  * [52] D. Wang, P. Cui, and W. Zhu, “Structural deep network embedding,” in _SIGKDD_ , 2016, pp. 1225–1234.
  * [53] Y. Gilad, A. Cohen, A. Herzberg, M. Schapira, and H. Shulman, “Are we there yet? on rpki’s deployment and security,” _Cryptology ePrint Archive_ , 2016\.
  * [54] R. K. Chang and M. Lo, “Inbound traffic engineering for multihomed ass using as path prepending,” _IEEE Netw._ , vol. 19, no. 2, pp. 18–25, 2005.
  * [55] CAIDA. AS Rank. Accessed May. 25, 2023. [Online]. Available: https://asrank.caida.org/
  * [56] K. Sriram, D. Montgomery, D. McPherson, E. Osterweil, and B. Dickson, “Problem definition and classification of bgp route leaks,” _RFC 7908, IETF_ , 2016\.
  * [57] J. Mitchell, “Autonomous system (as) reservation for private use,” _RFC 6996, IETF_ , 2013.
  * [58] D. Zhang, J. Yin, X. Zhu, and C. Zhang, “Network representation learning: A survey,” _TBD_ , vol. 6, no. 1, pp. 3–28, 2018.
  * [59] Z. Qiu, W. Hu, J. Wu, Z. Tang, and X. Jia, “Noise-resilient similarity preserving network embedding for social networks.” in _IJCAI_ , 2019, pp. 3282–3288.
  * [60] L. Liu, X. Li, W. K. Cheung, and L. Liao, “Structural representation learning for user alignment across social networks,” _TKDE_ , vol. 32, no. 9, pp. 1824–1837, 2019.
  * [61] W. Wang, H. Yin, X. Du, W. Hua, Y. Li, and Q. V. H. Nguyen, “Online user representation learning across heterogeneous social networks,” in _SIGIR_ , 2019, pp. 545–554.
  * [62] Q. Tan, N. Liu, X. Zhao, H. Yang, J. Zhou, and X. Hu, “Learning to hash with graph neural networks for recommender systems,” in _WWW_ , 2020, pp. 1988–1998.
  * [63] S. Ge, C. Wu, F. Wu, T. Qi, and Y. Huang, “Graph enhanced representation learning for news recommendation,” in _WWW_ , 2020, pp. 2863–2869.
  * [64] H. Liu, J. Han, Y. Fu, J. Zhou, X. Lu, and H. Xiong, “Multi-modal transportation recommendation with unified route representation learning,” _VLDB_ , vol. 14, no. 3, pp. 342–350, 2020.
  * [65] Y. Ye, S. Hou, L. Chen, J. Lei, W. Wan, J. Wang, Q. Xiong, and F. Shao, “Out-of-sample node representation learning for heterogeneous graph in real-time android malware detection,” in _IJCAI_ , 2019.
  * [66] S. Zhang, H. Yin, T. Chen, Q. V. N. Hung, Z. Huang, and L. Cui, “Gcn-based user representation learning for unifying robust recommendation and fraudster detection,” in _SIGIR_ , 2020, pp. 689–698.
  * [67] Y. Fan, M. Ju, S. Hou, Y. Ye, W. Wan, K. Wang, Y. Mei, and Q. Xiong, “Heterogeneous temporal graph transformer: An intelligent system for evolving android malware detection,” in _SIGKDD_ , 2021, pp. 2831–2839.
  * [68] CAIDA. AS Organizations Dataset. Accessed Dec. 10, 2021. [Online]. Available: https://www.caida.org/catalog/datasets/as-organizations/
  * [69] ——. AS-to-Organization Mapping Dataset. Accessed May. 25, 2023. [Online]. Available: https://www.caida.org/catalog/datasets/as-organizations/

##  Appendix A Preservation of the Second-Order Proximity

In practice, we derive the weight vector $\bm{l}$ (see Def. 2) from the
softmax transformation of a learnable variable
$\bm{l^{\prime}}\in\mathbb{R}^{d}$, and ensures that the minimum value of its
components is above $\alpha$ $(\alpha>0)$ to avoid trivial solutions:

$\bm{l}=[l_{0},\dots,l_{d-1}]^{\intercal}=\big{(}softmax(\bm{l^{\prime}})\big{)}_{\alpha+}.$
(6)

Accordingly, $\bm{l}$ is differentiable with respect to $\bm{l^{\prime}}$ and
satisfies the following criteria:

$\|\bm{l}\|_{1}=\sum_{i=0}^{d-1}|l_{i}|=1,\quad
l_{min}=\min\\{l_{0},\dots,l_{d-1}\\}\geq\alpha.$ (7)

In practice, we set $\alpha=\frac{1}{d}\times 10^{-6}$, a rather small
positive number. Now, we prove the theorem that the pairwise AS difference
does preserve the characteristics of the second-order proximity between
ASes555Note that this is a theoretical proof under ideal conditions. In the
actual training process, the convergence of the embedding vectors would also
be affected by initial values and sampling techniques..

######  Theorem 1.

The distance function (5) preserves the second-order proximity.

###### Proof.

Given two vertices $u,v$ $(u\neq v)$ having similar neighbors and the
corresponding business relationships, there must exist at least one vertex $w$
$(w\neq u,w\neq v)$ such that $(u,w)\in E,(v,w)\in E$. Then after sufficient
optimization of the objective function, there must exist two thresholds
$\epsilon_{1},\epsilon_{2}>0$ such that

$0\leq p\\_score(u,w),p\\_score(v,w)\leq\epsilon_{1},$

and

$h\\_score(u,w),h\\_score(v,w)\geq\epsilon_{2}.$

According to Equation (7), we have

$\displaystyle p\\_score(u,w)$ $\displaystyle\leq\epsilon_{1}$ (8)
$\displaystyle\Longrightarrow(\bm{x_{w}}-\bm{x_{u}})^{\intercal}((\bm{x_{w}}-\bm{x_{u}})\odot\bm{l})\leq\epsilon_{1}.$
(9)
$\displaystyle\Longrightarrow\|\bm{x_{w}}-\bm{x_{u}}\|_{2}\leq\sqrt{\frac{\epsilon_{1}}{l_{min}}}\leq\sqrt{\frac{\epsilon_{1}}{\alpha}}.$
(10) $\displaystyle p\\_score(v,w)$ $\displaystyle\leq\epsilon_{1}$ (11)
$\displaystyle\Longrightarrow(\bm{x_{w}}-\bm{x_{v}})^{\intercal}((\bm{x_{w}}-\bm{x_{v}})\odot\bm{l})\leq\epsilon_{1}.$
(12)
$\displaystyle\Longrightarrow\|\bm{x_{w}}-\bm{x_{v}}\|_{2}\leq\sqrt{\frac{\epsilon_{1}}{l_{min}}}\leq\sqrt{\frac{\epsilon_{1}}{\alpha}}.$
(13)

When it comes to $p\\_score(u,v)$, the upper bound is determined according to
Equation (1):

$p\\_score(u,v)\leq p\\_score(u,w)+p\\_score(v,w)\leq 2\epsilon_{1}$

When it comes to $h\\_score(u,v)$, the upper bound is determined according to
Equation (2), (10) and (13):

$\displaystyle|h\\_score(u,v)|$
$\displaystyle=|h\\_score(u,w)-h\\_score(v,w)|$
$\displaystyle\leq|h\\_score(u,w)|+|h\\_score(v,w)|$
$\displaystyle=|(\bm{x_{w}}-\bm{x_{u}})^{\intercal}\bm{r}|+|(\bm{x_{w}}-\bm{x_{v}})^{\intercal}\bm{r}|$
$\displaystyle\leq\|\bm{x_{w}}-\bm{x_{u}}\|_{2}\cdot\|\bm{r}\|_{2}+\|\bm{x_{w}}-\bm{x_{v}}\|_{2}\cdot\|\bm{r}\|_{2}$
$\displaystyle\leq 2\sqrt{\frac{\epsilon_{1}}{\alpha}}.$

Thus, we have $D_{\bm{l},\bm{r}}(u,v)=|p\\_score(u,v)|+|h\\_score(u,v)|\leq
2\epsilon_{1}+2\sqrt{\frac{\epsilon_{1}}{\alpha}}$. That is, there exists an
upper bound for the distance between $u,v$ in terms of the distance function
(5). Moreover, when the objective function is sufficiently optimized,
$\epsilon_{1}$ is a rather small positive number approaching zero and $\alpha$
is a constant, and then the distance $D_{\bm{l},\bm{r}}(u,v)$ should approach
zero, which means the two vertices $u,v$ are at a close distance to each other
in the low-dimensional vector space. Hence the proof completes. ∎

##  Appendix B Sampled AS Pair Datasets

According to §3.5, we sample AS pairs in three categories and obtain 15
datasets, as presented in Table 3.

Table 3: Sampled AS pair datasets. _No rel_ is no relationship. _Ngbr JI_ refers to the Jaccard index of two neighbor AS sets. Feature | Name |  #AS pair | Sampling rule
---|---|---|---
1st-order proximity | $S_{0}$ |  10,000 |  P2P, $\textrm{Ngbr JI}\in[0\%,10\%)$
$H_{0}$ |  10,000 |  P2C, $\textrm{Ngbr JI}\in[0\%,10\%)$
$N_{0}$ |  10,000 |  no rel, $\textrm{Ngbr JI}\in[0\%,10\%)$
2nd-order proximity | $N_{1}$ |  2,000 |  no rel, $\textrm{Ngbr JI}\in[0\%,20\%)$
$N_{2}$ |  2,000 |  no rel, $\textrm{Ngbr JI}\in[20\%,40\%)$
$N_{3}$ |  2,000 |  no rel, $\textrm{Ngbr JI}\in[40\%,60\%)$
$N_{4}$ |  2,000 |  no rel, $\textrm{Ngbr JI}\in[60\%,80\%)$
$N_{5}$ |  2,000 |  no rel, $\textrm{Ngbr JI}\geq 80\%$
hierarchy | $S_{1}$ |  10,000 | with a direct P2P
$H_{1}$ |  10,000 | with a direct P2C
$H_{2}$ |  10,000 | with 2 consecutive P2C
$H_{3}$ |  10,000 | with 3 consecutive P2C
$H_{4}$ |  10,000 | with 4 consecutive P2C
$H_{5}$ |  10,000 | with 5 consecutive P2C
$H_{6}$ |  10,000 | with 6 consecutive P2C

##  Appendix C Real-World Route Announcement Datasets

We collect 18 real-world route announcement datasets from RouteViews Project
[47]. Each dataset contains all route announements from all RouteViews
collectors 12 hours before and after a previously-confirmed routing anomaly.
We name each dataset (_e.g.,_ $PO_{brazil}$) by the category and the
abbreviation of the confirmed routing anomaly related with the dataset. Table
4 shows the details of each dataset.

Table 4: Real-world datasets with previously-confirmed routing anomalies. $PO$, $SO$, $SP$ and $RL$ indicate the categories of anomalies, _i.e.,_ the prefix origin change, the subprefix origin change, the subprefix path change, and the route leak, respectively. _#Total Ann_ denotes the number of announcements in each dataset. _GT Duration_ , _#GT Ann_ , and _#GT VP_ denote the duration of the ground-truth anomaly, the number of anomalous announcements in the ground-truth anomaly, and the number of vantage points observing the ground-truth anomaly, respectively.  Category | Name |  Time Span ($\bm{\pm 12h}$) | #Total Ann |  GT Duration | #GT Ann |  #GT VP
---|---|---|---|---|---|---
prefix hijacking (origin change) | $PO_{brazil}$ |  2014-09-10 00:30:00 | 93,942,111 |  1h28m39s | 127 |  24
$PO_{sprint}$ |  2014-09-09 13:45:00 | 91,338,780 |  7s | 198 |  74
subprefix hijacking (origin change) | $SO_{iran}$ |  2018-07-30 06:15:00 | 201,516,610 |  3h25m42s | 587 |  102
$SO_{bitcanal\\_3}$ |  2018-06-29 13:00:00 | 141,856,933 |  47m34s | 672 |  107
$SO_{backcon\\_3}$ |  2016-02-21 10:00:00 | 279,389,745 |  4s | 1,156 |  100
$SO_{backcon\\_1}$ |  2015-12-03 22:00:00 | 186,952,580 |  16m5s | 695 |  96
$SO_{bitcanal\\_2}$ |  2015-01-23 12:00:00 | 60,327,936 |  5m11s | 284 |  34
$SO_{h3s}$ |  2014-11-14 23:00:00 | 94,519,947 |  2s | 581 |  86
$SO_{pakistan}$ |  2008-02-24 18:00:00 | 8,155,604 |  4h57m6s | 156 |  20
subprefix hijacking (path change) | $SP_{backcon\\_5}$ |  2016-05-20 21:30:00 | 147,824,105 |  1h33m47s | 296 |  61
$SP_{backcon\\_4}$ |  2016-04-16 07:00:00 | 100,632,725 |  11m28s | 1,032 |  98
$SP_{backcon\\_2}$ |  2016-02-20 08:30:00 | 314,047,522 |  3m10s | 825 |  73
$SP_{bitcanal\\_1}$ |  2015-01-07 12:00:00 | 57,902,559 |  12m55s | 286 |  38
$SP_{petersburg}$ |  2015-01-07 09:00:00 | 60,016,016 |  28s | 1,000 |  83
$SP_{defcon}$ |  2008-08-10 19:30:00 | 5,701,271 |  26s | 72 |  21
route leak | $RL_{jtl}$ |  2021-11-21 06:30:00 | 3,035,292,256 |  1h14m47s | 2,419 |  146
$RL_{stelkom}$ |  2021-11-17 23:30:00 | 3,572,332,877 |  3m18s | 1,888 |  140
$RL_{itregion}$ |  2021-11-16 11:30:00 | 3,409,628,374 |  31m32s | 2,409 |  144

##  Appendix D Identifying Legitimate Route Changes

We identify legitimate route changes via a heuristic rule derived from the
multi-homing settings [43], which is a common route engineering practice. We
label an origin change as legitimate if it satisfies two conditions: (i) Two
different origin ASes (_i.e.,_ on the changed and the original routing paths,
respectively) belong to the same organization; (ii) There is no duplicate AS
numbers in its routing paths. The first condition ensures the legitimacy of
this route change since the actual ownership of the corresponding prefix is
not changed, and the second one filters out the potential noises caused by
routing paths manipulations, _e.g.,_ AS prepending. Note that we use the CAIDA
AS organization dataset [68] to obtain the organization name of each AS. These
rules can not identify all legitimate route changes in the Internet. We only
utilize them to find out changes with high confidence.

##  Appendix E Detection System built upon BEAM

Algorithm 1 Measuring Path Difference Scores

1:function PathDiffScore($S$: Array $[1\dots m]$, $S^{\prime}$: Array $[1\dots
n]$)

2: external function $D_{\mathbf{l},\mathbf{r}}$

3: DIFF $\coloneqq$ Array $[0\dots m,0\dots n]$

4: for $i\coloneqq 0$ to $m$ do

5: for $j\coloneqq 0$ to $n$ do

6: DIFF$[i,j]\coloneqq+\infty$

7: DIFF$[0,0]\coloneqq 0$

8: for $i\coloneqq 1$ to $m$ do

9: for $j\coloneqq 1$ to $n$ do

10: diff $\coloneqq D_{\mathbf{l},\mathbf{r}}(S[i],S^{\prime}[j])$

11: $\begin{aligned}
\text{DIFF}[i,j]\coloneqq\text{diff}+\text{minimum}(\text{DIFF}[i-1,j],\\\
\text{DIFF}[i,j-1],\text{DIFF}[i-1,j-1])\end{aligned}$

12: return $\text{DIFF}[m,n]$

Our detection system built upon BEAM consists of three components, _i.e.,_ the
routing monitor, the BEAM engine, and the anomaly detector. At a high level,
the routing monitor detects route changes from the BGP route update
announcements. The BEAM engine utilizes a pre-trained BEAM model to compute
the path difference scores of the route changes. The detailed path difference
score computation process is presented in §4.2 and we supplement its pseudo-
code in Algorithm 1. Besides, the anomaly detector is responsible for
identifying routing anomalies from the route changes and generating
corresponding alarms. Here, we will introduce the details of the routing
monitor and anomaly detector.

The Routing Monitor. This component collects the BGP route update
announcements from global vantage points, to detect route changes. In
particular, it maintains a routing table for each vantage point. To reduce the
storage space and facilitate detection, the routing table is in a trie
structure, where each node represents a unique prefix and its routing path.
Also, the prefix of each parent node is the super prefix of its child nodes.
When the routing monitor receives a new route update message that announces
routing path $l$ to prefix $p$ from a vantage point, it searches $p$ in the
corresponding trie structure routing table. If a routing path to prefix $p$
(denoted by $l^{\prime}$) already exists in the routing table, we compare it
with $l$ and find a route change when $l\neq l^{\prime}$. If $p$ is not in the
routing table, we compare $l$ with the routing path to the most specific super
prefix of $p$, which can be obtained from the parent node of $p$. After
detecting route changes, the routing monitor updates the routing table with
the newly received update message.

The Anomaly Detector. This component aims to detect routing anomalies from the
route changes and generate corresponding alarms. Its detection procedure
includes three steps: detecting suspicious route changes, identifying
anomalous prefixes, and locating responsible ASes.

Formally, we represent each detected route change by
$(t,r,p,p^{\prime},l,l^{\prime})$, where $t$ is the occurrence time of the
route change, $r$ is the AS number of the vantage point that captures the
route change, $p$ is the prefix announced in the update announcement that
triggers the route change, $p^{\prime}$ is the prefix in the routing table
that conflicts with $p$ (_i.e.,_ the same as $p$ or the most specific super
prefix of $p$), and $l$ and $l^{\prime}$ are the routing path to $p$ and
$p^{\prime}$, respectively. The computed path difference score between $l$ and
$l^{\prime}$ is denoted as $d_{l,l^{\prime}}$. If $d_{l,l^{\prime}}$ is above
a threshold $th_{d}$ computed based on historical legitimate route changes
(detailed in §5.2), the anomaly detector flags the route change as
_suspicious_.

It is necessary to prioritize the widespread routing anomalies captured by
multiple vantage points, otherwise the transient route changes in the Internet
will generate numerous insignificant alarms. Towards this end, the anomaly
detector further groups suspicious route changes that share the same
$(p,p^{\prime})$ and denotes each group as a _prefix event_ , where each event
is associated with a specific $(p,p^{\prime})$ and sorts the suspicious route
changes by their occurrence time. To each event, the anomaly detector utilizes
a sliding window (with time interval $w$) to count the number of individual
vantage points that observe the suspicious route changes within the window. If
the counted number (denoted by $N_{r}$) is above another threshold $th_{v}$,
the anomaly detector considers the prefix event is caused by a widespread
routing anomaly and regards it as anomalous. The formal definition of
anomalous prefix event is:

###### Definition 7 (Anomalous Prefix Event).

Given parameters $th_{d},w,th_{v}$, a prefix event of
$(\hat{p},\hat{p}^{\prime})\equiv P=\\{(t,r,p,p^{\prime},l,l^{\prime})\mid
p=\hat{p},p^{\prime}=\hat{p}^{\prime},d_{l,l^{\prime}}>th_{d}\\}$ is anomalous
if and only if $\exists A\subseteq
P,\forall(t_{1},r_{1},p_{1},p^{\prime}_{1},l_{1},l^{\prime}_{1}),(t_{2},r_{2},p_{2},p^{\prime}_{2},l_{2},l^{\prime}_{2})\in
A,|t_{1}-t_{2}|<w,N_{r}=|\\{r\mid(t,r,p,p^{\prime},l,l^{\prime})\in
A\\}|>th_{v}$.

In realistic circumstances, a misbehaved ASes may impact multiple prefixes
simultaneously, _e.g.,_ AS 55410 hijacked more than 30,000 prefixes in April
2021, resulting in several different anomalous prefix events. To provide
network administrators with comprehensive information about the impacted
prefixes of each routing anomaly, the anomaly detector correlates all
anomalous prefix events based on their responsible ASes. Intuitively, the ASes
responsible for a suspicious route change (where
$l=\\{AS_{1},AS_{2},\dots,AS_{n}\\},l^{\prime}=\\{AS^{\prime}_{1},AS^{\prime}_{2},\dots,AS^{\prime}_{m}\\}$)
are either within the ASes present in $l$ but absent in $l^{\prime}$ (_i.e.,_
$l-l^{\prime}$ in terms of set subtraction and we denote it as the _drop-out
AS set_), or within the ASes absent in $l$ but present in $l^{\prime}$
(_i.e.,_ $l^{\prime}-l$ in terms of set subtraction and we denote it as the
_pop-up AS set_). For each anomalous prefix event, we compare its all
suspicious route changes to find the intersection of their drop-out AS sets
and the intersection of their pop-up AS sets, respectively. If any set is not
empty, we denote the ASes in two intersection sets as the responsible ASes for
the anomalous prefix event. Thus, the responsible ASes for an anomalous prefix
event is defined as follows:

###### Definition 8 (Responsible AS).

Given an anomalous prefix event $A$, let
$L=\\{(l,l^{\prime})\mid(t,r,p,p^{\prime},l,l^{\prime})\in A\\}$. If
$I_{\text{drop-out}}=\bigcap_{(l,l^{\prime})\in L}(l-l^{\prime})\neq\emptyset$
or $I_{\text{pop-up}}=\bigcap_{(l,l^{\prime})\in
L}(l^{\prime}-l)\neq\emptyset$, the responsible ASes for $A$ are the ASes
belonging to $I_{\text{drop-out}}\cup I_{\text{pop-up}}$. Otherwise, there are
no responsible ASes for $A$.

Then, the anomaly detector correlates the anomalous prefix events based on
their responsible ASes. Given two different anomalous prefix events, if their
time ranges are overlapped and they have common responsible ASes, we consider
they are correlated. The formal definition of a correlated anomalous prefix
event is:

###### Definition 9 (Correlated Anomalous Prefix Event).

Given two different anomalous prefix events $A$ and $A^{\prime}$, let
$T=\\{t\mid(t,r,p,p^{\prime},l,l^{\prime})\in
A\\},T^{\prime}=\\{t\mid(t,r,p,p^{\prime},l,l^{\prime})\in A^{\prime}\\}$,
denote the set of responsible ASes for $A$ as $R_{A}$ and that for
$A^{\prime}$ as $R_{A^{\prime}}$. $A$ and $A^{\prime}$ are correlated if and
only if $R_{A}\cap R_{A^{\prime}}\neq\emptyset,\exists t_{1},t_{2}\in
T,t_{1}<t_{2},t^{\prime}_{1},t^{\prime}_{2}\in
T^{\prime},t^{\prime}_{1}<t^{\prime}_{2},[t_{1},t_{2}]\cap[t^{\prime}_{1},t^{\prime}_{2}]\neq\emptyset$.

Finally, we divide all anomalous prefix events into different sets, where the
event in one set only correlates the other events in the same set. The anomaly
detector treats each set as an individual routing anomaly and outputs a
corresponding alarm that includes both the affected prefixes and the
responsible ASes.

##  Appendix F Alarms Validation via Pattern Matching

We discuss the rationale of P1-P4 in §5.2, which are confirmed by domain
experts. Each pattern represents one typical kind of Internet routing
anomalies. Specifically, P1 tracks the change of RPKI validity states, which
indicates the legitimacy of AS-Prefix bindings [7], during a route change to
detect the unauthorized prefix announcements caused by misconfiguration or
hijacking attacks. P2 tracks the violation of the valley-free criterion during
a route change. This criterion describes an inherent attribute of normal
routing paths in terms of business relationships [32]. According to RFC 7908
[56], the violation of this criterion indicates a route leak. P3 tracks the
appearance of suspicious path segments during a route change, including
private ASNs and adjacent ASes that do not have business relationship records
in the CAIDA dataset. In particular, the private ASNs [57] only appear in the
global routing paths when adversaries tamper with the routing path or
misconfigurations happen. Besides, considering CAIDA maintains a relatively
comprehensive knowledge base of the business relationships among global ASes,
the adjacent ASes that have no relationship records in the CAIDA dataset
typically represent nonexistent routing connections and are very likely to be
forged by sophisticated attacks, _e.g.,_ the Type-N hijacking [11]. Lastly, P4
tracks the conflicts between route announcements and Route Origin
Authorization (ROA) objects where the conflicting ASes belong to the same
organization. Since the ASes in the same organization usually share the same
interests, these conflicts indicate the ROA object misconfigurations.

We explain how to use these patterns to analyze the alarms. For each reported
routing anomaly event, we calculate the fraction of suspicious route changes
in the event that match each pattern (_i.e.,_ P1-P4) as the explanatory power
(EP) of each pattern. Then, if the EP of any pattern is higher than 50%
(_i.e.,_ an absolute majority), we consider the event an anomaly with high
confidence (H.C.), otherwise with low confidence (L.C.). Specifically, we use
the RIPEstat web API666https://stat.ripe.net/ui2013/ to query RPKI validation
states and the CAIDA AS-to-organization mapping dataset [69] to identify the
organizations of ASes. We show the number of H.C. and L.C. events detected by
our system in each dataset and the average EP of the H.C. events in Table 5.
We report the L.C. events as false alarms in §5.2.

Table 5: Anomalous patterns of the routing anomaly events reported by our detection system. Name | H.C. |  L.C. | Avg.EP
---|---|---|---
P1 |  P2 | P3 |  P4 | Any
$SP_{backcon\\_5}$ | 0 |  25 | 30 |  2 | 32 |  2 | 0.6478
$SP_{backcon\\_4}$ | 2 |  20 | 19 |  1 | 21 |  0 | 0.8163
$SP_{backcon\\_2}$ | 1 |  29 | 31 |  3 | 36 |  1 | 0.7628
$SP_{bitcanal\\_1}$ | 1 |  10 | 16 |  0 | 16 |  0 | 0.7473
$SP_{petersburg}$ | 2 |  18 | 24 |  3 | 24 |  0 | 0.8912
$SP_{defcon}$ | 3 |  3 | 3 |  1 | 6 |  1 | 0.9624
$SO_{iran}$ | 5 |  21 | 27 |  2 | 29 |  2 | 0.8190
$SO_{bitcanal\\_3}$ | 8 |  36 | 38 |  2 | 39 |  1 | 0.8966
$SO_{backcon\\_3}$ | 3 |  24 | 25 |  2 | 30 |  5 | 0.7520
$SO_{backcon\\_1}$ | 0 |  15 | 12 |  1 | 15 |  3 | 0.8691
$SO_{bitcanal\\_2}$ | 4 |  19 | 24 |  2 | 24 |  0 | 0.8798
$SO_{h3s}$ | 1 |  13 | 12 |  1 | 14 |  0 | 0.8444
$SO_{pakistan}$ | 2 |  8 | 5 |  0 | 9 |  1 | 0.7058
$PO_{brazil}$ | 4 |  34 | 50 |  2 | 50 |  1 | 0.5878
$PO_{sprint}$ | 1 |  26 | 28 |  3 | 29 |  0 | 0.9262
$RL_{jtl}$ | 1 |  30 | 34 |  0 | 41 |  5 | 0.7072
$RL_{stelkom}$ | 3 |  32 | 37 |  0 | 40 |  3 | 0.7644
$RL_{itregion}$ | 5 |  33 | 38 |  1 | 40 |  4 | 0.8187

Given that some route change events occurred long ago, before their
corresponding prefixes had registered ROA objects, we use the most recent RPKI
validation results to identify the RPKI-related patterns P1 and P4. Further,
to reduce the negative impact of the inconsistency between historical and
current ROA objects, we double-check each event matching P1 and P4 based on
the RIPEstat database and only regard those with unchanged authorized AS-
prefix bindings as H.C.

##  Appendix G Comparison with ML-based Methods

We implement two baselines, _i.e.,_ AV and LS, according to their papers [30,
22]. Here, we describe their experimental setup and compare them to our system
in detail.

AV Setup. In accordance with the original setup in the paper [30], for each
dataset, we train an AV detection model based on the most recent RIB snapshots
collected from all vantage points before the confirmed anomaly occurs, and
perform detection on the next RIB snapshots in the next two hours. To reduce
the training time, the model is trained offline on all two-hour RIB snapshots
in parallel. Note that this strategy is not realizable for an AV model
deployed for real-world online detection task, because the model has to be
trained on the RIB snapshot collected 2 hours earlier and perform detection on
the latest RIB snapshot. We set the hyperparameters the same to the original
paper. The outputs of the AV detection model are anomalous route changes. For
fair comparisons, we further apply our anomaly detector (see §4.3) to
aggregate these route changes into alarms, _i.e.,_ identifying anomalous
prefixes and locating responsible ASes.

LS Setup. The LS method aggregates all BGP announcements in each two minutes
into a time interval and extracts 86 features. Note that LS is a supervised
detection method. Thus, for each dataset, we use the other 17 datasets as the
training data to train an LS model, and then classify the time intervals
(_i.e.,_ normal or anomalous) in this dataset. The labeling method of the
training data and the parameters of the LS detection model are the same to the
original paper. All route changes in the detected anomalous time intervals are
considered anomalous. Finally, we also utilize our anomaly detector to
aggregate these anomalous route changes into alarms.

The Comparison. We compare our system with AV and LS in Table 6. Specifically,
since AV performs detection in the RIB snapshots of every two hours, it cannot
detect transient routing anomalies that occur within the period between two
RIB snapshots. Besides, AV requires frequent model updates because tens of
millions of RIB entries are updated bihourly, which incurs significant
retraining overheads. To the best of our knowledge, there is no technique that
can be directly applied to accelerate the training of AV. By contrast, our
system directly checks every route change collected from each real-time BGP
announcement such that it can detect both transient and long-lived routing
anomalies. Further, our system only requires the AS relationship data for
training, which is much smaller than the RIB snapshots and more stable,
ensuring a small retraining overhead.

LS characterizes announcements as time series and applies a supervised neural
network to detect if each data point in the time series is associated with
routing anomalies. However, each data point in the time series, _e.g.,_ the
data in a two-minute time interval, may include a large number of legitimate
announcements, leading to much more false alarms than our system. Besides,
since LS utilizes a supervised model, it requires a large amount of BGP
anomaly data for training, _e.g.,_ more than 2,000 BGP anomaly events [22],
which is difficult to achieve in practice. By contrast, our system performs
detection in an unsupervised manner and gets rid of the reliance on anomalous
training data.

Table 6: Comparison with ML-based methods. _Vol._ , _Req._ and _Ann._ are short for Volume, Requirement and BGP Announcement, respectively. Method |  | Training |  | Detection
---|---|---|---|---
|  Training Data | Training Data Vol. |  Retraining Req. | ML Model Type |  | Detection Data |  Anomaly Type
Ours |  |  AS relationships |  $\sim$500K |  Monthly | Unsupervised |  | Ann |  Short & Long-lived
AV [30] |  |  RIB entries |  $\sim$10M |  Bihourly | Unsupervised |  | RIB entries |  Long-lived
LS [22] |  |  Ann. time series |  $\sim$100M |  Unknown | Supervised |  | Ann. time series |  Short & Long-lived

##  Appendix H An Empirical Study on Adaptive Attacks

We empirically study how many ASes an adaptive attacker needs to control and
how many AS relationships need to be established to make the routing roles of
a malicious path777A malicious path refers to a routing path that contains the
known malicious AS in the BGP anomaly event. similar to those of a legitimate
path. Specifically, for each legitimate routing path from the 18 real-world
datasets (described in §5.1), we start from the vantage point of the
legitimate path and search for the malicious path that has the most
overlapping segments with the legitimate path. Then, we choose the ASes that
appear on the malicious path but not on the legitimate path. These ASes have
to be controlled by the attacker to mimic the legitimate path ASes’ routing
roles. Next, we compare the neighbors of the malicious and the legitimate path
and calculate the minimum number of relationships that need to be established
to make 10% neighbors the same. In this study, we assume that having 10%
common neighbors is sufficient to make the routing roles of a malicious path
similar to those of the legitimate path. This reduces the difficulty for the
attacker, such that the result is a lower-bound estimate.

We show the result in Fig. 11, where the top and bottom figures display the
average number of ASes that must be controlled and the average number of AS
relationships that need to be established, respectively. The error bar shows
the 95% confidence interval. We can see that, in most cases, an adaptive
attacker has to control at least two ASes and establish hundreds of new AS
relationships to make the routing roles of a malicious path and a legitimate
path similar. Note that, the cost for an adaptive attacker to bypass our
system in practice would be much higher than the above result. This is because
our system monitors multiple vantage points simultaneously, _i.e.,_ the
attacker has to make the routing roles of multiple malicious routing paths
similar to those of normal paths. Thus, it is very difficult for adaptive
attackers to bypass our system’s detection.

Figure 11: The empirical estimate of the cost for an adaptive attacker to make
the routing roles of a malicious path and a legitimate path similar.