Partition First, Detect Faster: A Multi-Partition Subgraph Framework for BGP Anomaly Detection

<p><strong>The Border Gateway Protocol (BGP) serves as the foundation of inter-domain communication between Autonomous Systems (AS), enabling global Internet connectivity. However, due to the lack of built-in security mechanisms, BGP remains vulnerable to anomalies such as route hijacks and route leaks, which can severely compromise routing stability and availability. Existing anomaly detection approaches often fail to capture the structural complexity of AS-level topologies and overlook computational efficiency, limiting their scalability and real-world applicability.</strong></p><p>To address these limitations, this thesis introduces a subgraph-based framework designed to achieve high detection accuracy while ensuring computational efficiency in BGP anomaly detection. By partitioning the AS-level topology into structurally cohesive subgraphs using Louvain, Leiden, and $N$-hop strategies, the framework supports localized analysis of routing behaviour while significantly reducing the cost of structural feature extraction. Anomalies are identified by capturing deviations in centrality-based features through an unsupervised learning model, allowing effective detection of inter-domain routing disruptions.</p><p>We evaluate the proposed framework on real-world BGP anomaly events across diverse scenarios and vantage points. Compared to whole-network baselines, subgraph partitioning significantly reduces the computation time of betweenness and closeness centrality, in some cases by nearly 99\%, while maintaining comparable detection accuracy. For instance, during the CenturyLink incident, closeness computation time at the WIDE collector was reduced by 95.8\%, and betweenness by 98.86\%, without performance degradation. These findings validate the proposed “partition first, detect faster” strategy and demonstrate its potential for scalable, real-time anomaly detection in large-scale inter-domain networks.</p>