PathProb: Probabilistic Inference and Path Scoring for Enhanced and Flexible BGP Route Leak Detection

PathProb: Probabilistic Inference and Path Scoring for Enhanced and Flexible BGP Route Leak Detection

Speakers: Yingqian Hao

Conference: NDSS Symposium 2026

YouTube: https://www.youtube.com/watch?v=Zdh9tla1KNE

Overview

BGP (Border Gateway Protocol) remains the de facto inter-domain routing protocol for the global internet, yet it was designed without security mechanisms, leaving it vulnerable to route leaks and prefix hijacks. Route leaks -- where an Autonomous System (AS) shares routes with the wrong type of neighbors -- occurred even more frequently than hijacks in Q3 2025, causing event dropping, network overloads, and black holes. This talk introduces PathProb, a probabilistic route leak detection system that assigns probability distributions to each AS link's relationship type and calculates legitimacy scores for each AS path. Unlike rule-based approaches that produce binary (leak/not-leak) decisions with high false positive rates, and machine learning approaches that lack interpretability, PathProb offers operators adjustable detection thresholds to balance security sensitivity against false alarms. The system achieves the highest precision and lowest false positive rate while maintaining 98-100% recall, and is compatible with emerging ASPA (Autonomous System Provider Authorization) deployment.

Background

▶ Watch: BGP route leaks more frequent than hijacks in Q3 2025 (0:30)

BGP connects autonomous networks (ASes), and each AS link has a specific relationship type: primarily provider-to-customer (P2C), peer-to-peer (P2P), or less commonly other relationship types. These relationships define export policies -- rules governing how learned routes can be shared with neighbors. A route leak occurs when an AS shares routes with the wrong type of neighbor, violating the valley-free constraint: a valid path should begin with zero or more C2P links, contain at most one P2P link, and end with zero or more P2C links.

Existing detection approaches fall into two categories. Rule-based methods first infer AS link relationships and then detect leaks using valley-free rules. They struggle with inference accuracy, producing either poor detection capability or high false positive rates. Machine learning methods learn normal routing patterns from BGP data and identify deviations, but lack interpretability and remain sensitive to data quality, still requiring BGP experts to interpret results.

ASPA is an emerging standard that provides cryptographically verifiable AS relationship information. ASPA deployment began in late 2024, with several thousand ASPA objects now available, providing ground truth relationship data for the first time.

Key Findings

▶ Watch: PathProb: probability distributions for AS link relationships (3:30)

Probabilistic inference outperforms binary classification: By assigning probability distributions to AS link relationships rather than making binary decisions, PathProb achieves 5-23 percentage points higher accuracy on long-term datasets and 6-20 percentage points on short-term datasets compared to existing methods, with non-overlapping 95% confidence intervals.

Triple minimum method solves long-path false positives: Route leaks are localized, typically occurring in just three consecutive ASes. The full-path legitimacy scoring method tends to misclassify long legitimate paths. The triple minimum method calculates legitimacy scores for each AS triple along the path and uses the minimum score, correctly localizing leak detection.

Adjustable thresholds balance precision and recall: An optimal threshold of 0.35 best balances precision, recall, and false positive rate. Leak paths concentrate their scores in the 0-0.1 range, while legitimate paths receive scores around 0.5 or higher, providing clear separation.

ASPA compatibility enhances accuracy: PathProb can incorporate ASPA data as ground truth for AS relationships, further improving detection accuracy. Simulation shows that even in early ASPA deployment stages, PathProb substantially reduces infected ASes.

Technical Deep Dive

▶ Watch: Core vs edge link inference with Markov Random Fields (5:30)

PathProb classifies AS links into core links (densely interconnected backbone links) and edge links (sparse boundary links) and applies different inference algorithms to each.

Core link inference uses Markov Random Fields (MRF), which naturally capture local dependency between interconnected core links. Gibbs sampling efficiently calculates marginal probabilities for each core link's relationship type. To accelerate convergence, the sampling is initialized using results from a loose model (an Integer Linear Programming formulation that allows a limited number of valley-free violations, avoiding unresolvable cases from legitimate paths with long-term deviations).

Edge link inference propagates from adjacent core links: if a core link is highly likely to be P2C or P2P, the connected edge link is inferred as P2C. For isolated edge links without contextual information, a uniform prior distribution assigns equal probability (1/3) to each relationship type.

Path legitimacy scoring enumerates all possible valley-free realizations of a path and sums their probabilities. The full path method calculates this for the entire path, while the triple minimum method calculates scores for each consecutive triple of ASes and selects the minimum as the path score. The triple minimum method is preferred because route leaks are localized phenomena.

The system formulates valley-free constraints as an Integer Linear Programming (ILP) problem with two models: the strict model (full compliance) and the loose model (limited violations allowed).

Demo / Proof of Concept

▶ Watch: Accuracy results: 5-23% improvement over existing methods (9:30)

The evaluation uses CAIDA and ASBAR AS relationship data as validation datasets. For route leak detection, BGP updates around leak events reported by Cloudflare Radar are extracted and labeled. PathProb achieves the highest precision and lowest false positive rate while maintaining 98-100% recall. A fine-grained assessment across three dimensions confirms robustness. Internet topology simulation using a BGP simulator with 10,000 randomly selected attacker-victim AS pairs evaluates mitigation effectiveness under multiple deployment scenarios with varying ASPA issuance and deployment rates. PathProb demonstrates compatibility with ASPA and complementary mechanisms like OTC (Only-to-Customer) filtering.

Defensive Implications

▶ Watch: ASPA compatibility and deployment simulation results (11:00)

For network operators, PathProb provides a more practical route leak detection tool than existing approaches. The adjustable threshold allows operators to tune detection sensitivity based on their risk tolerance -- critical networks can set lower thresholds (higher sensitivity, more false positives), while general-purpose networks can use the optimal 0.35 threshold.

For RPKI/ASPA deployment strategists, PathProb's compatibility with ASPA data means it can leverage emerging ground truth as ASPA adoption grows, providing increasingly accurate detection over time. In the early deployment stage, PathProb's probabilistic inference fills the gap where ASPA coverage is still incomplete.

For internet routing security researchers, the Cloudflare Radar evaluation data is acknowledged as far from ground truth (it heavily relies on CAIDA relationships built 20 years ago). The emergence of ASPA as actual ground truth data represents a significant opportunity for future evaluation.

Key Takeaways

• Route leaks occurred more frequently than prefix hijacks in Q3 2025, causing significant internet disruptions
• Probabilistic AS relationship inference achieves 5-23 percentage points higher accuracy than existing methods
• The triple minimum method correctly localizes route leak detection to three consecutive ASes
• Adjustable detection thresholds allow operators to balance precision and false alarm rates
• PathProb is compatible with emerging ASPA deployment, improving accuracy as ground truth data grows
• Highest precision and lowest false positive rate with 98-100% recall in evaluation
• Internet topology simulation confirms mitigation effectiveness under realistic deployment scenarios

About the Speaker(s)

Yingqian Hao is a researcher working on BGP security and inter-domain routing. The research addresses a critical internet infrastructure security challenge, combining probabilistic graphical models (Markov Random Fields) with BGP domain expertise to improve route leak detection accuracy and operability.