  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 \emph{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.
