Ares: Comprehensive Path Hijacking Detection via Routing Tree

Ares: Comprehensive Path Hijacking Detection via Routing Tree

Speakers: Yinxiang Tao

Conference: USENIX Security

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

Overview

In an era where the internet underpins global communication and commerce, the integrity of its foundational routing protocols is paramount. Border Gateway Protocol (BGP) hijacking represents a critical and persistent threat, capable of rerouting internet traffic maliciously, leading to significant economic and security repercussions such as traffic interception or denial-of-service attacks. While origin hijacking, where an attacker falsely claims ownership of an IP prefix, has seen improvements in detection and mitigation through methods like ROV (Route Origin Validation), a more insidious form known as path hijacking continues to pose a significant challenge.

Path hijacking occurs when an attacker forges the AS (Autonomous System) path in a BGP announcement, often prepending the correct origin AS, thereby bypassing origin-centric validation mechanisms like ROV. This talk introduces Ares, a novel and comprehensive detection method designed to tackle the complexities of path hijacking, including its elusive subtype, the Defcon attack (or Type U hijacking), which presents a seemingly legitimate path to the victim. Developed by Yinxiang Tao from Chinua University, Ares fundamentally shifts the detection paradigm by monitoring and comparing the routing trees formed by BGP announcements, rather than solely relying on origin validation.

Ares distinguishes itself through its ability to cover all types of path hijacking with high recall and a remarkably low false positive rate, while also being computationally efficient enough for real-time deployment. By recognizing that a hijacking event fundamentally alters the routing tree for a given prefix, Ares provides an effective and scalable solution to a long-standing security vulnerability in internet routing. This work is particularly vital for enhancing the resilience of critical internet infrastructure against sophisticated routing attacks.

Background

▶ Watch: Introduction to BGP pass hijacking and its challenges (0:00)

The internet's global connectivity relies heavily on the Border Gateway Protocol (BGP), which dictates how data packets traverse the vast network of interconnected Autonomous Systems (ASes). However, BGP's inherent trust model, designed for a cooperative internet, makes it vulnerable to various forms of hijacking. BGP hijacking events, such as those reported in 2022 causing substantial losses, underscore the urgency of robust detection and prevention mechanisms.

BGP hijacking broadly categorizes into two main types: origin hijacking and path hijacking. Origin hijacking is the more commonly understood form, where an attacker announces prefixes that do not legitimately belong to them, masquerading as the true origin AS. This type of attack is relatively well-studied, and defenses like Route Origin Validation (ROV), often implemented via RPKI (Resource Public Key Infrastructure), have been developed to mitigate it by checking the validity of the announced origin AS against a registry. While ROV has significantly improved the security posture against origin hijacking, it does not provide a complete solution.

Path hijacking presents a more complex and persistent challenge. In this scenario, attackers do not necessarily forge the origin AS; instead, they manipulate the AS path attribute within BGP announcements. By prepending the correct origin AS at the end of a forged path, attackers can craft seemingly legitimate routes that bypass origin-centric validation methods like ROV. This makes path hijacking particularly difficult to detect using existing techniques that primarily focus on the origin AS. A particularly sophisticated subtype, known as the Defcon attack or Type U hijacking, further complicates detection by presenting a path that appears to be a real, albeit manipulated, route to the victim. This subtlety allows attackers to redirect traffic without triggering alarms based on overtly incorrect origin ASes or clearly invalid paths. The limitations of current detection methods against these advanced forms of path hijacking necessitated the development of a more sophisticated approach like Ares.

Key Findings

▶ Watch: Challenges in applying Ares for comprehensive hijacking detection (4:00)

Ares demonstrates a significant advancement in the detection of BGP path hijacking, achieving comprehensive coverage, high accuracy, and impressive efficiency. The core findings highlight its effectiveness across various real-world and simulated scenarios:

• Comprehensive Coverage: Ares is designed to cover all types of path hijacking, including the challenging Defcon/Type U attacks, which existing methods often fail to detect effectively. This holistic approach ensures a broader protective scope against sophisticated attackers.
• High Recall on Historical Events: When tested against 12 historical path hijacking events, Ares successfully detected all of them, achieving a perfect 100% recall rate. This demonstrates its capability to identify known real-world attacks without fail.
• Low False Positive Rate on Historical Data: During the detection of historical events, Ares maintained an exceptionally low false positive rate, generating an average of only 2.31 alarms per hour. This indicates its precision in distinguishing genuine threats from normal routing fluctuations.
• Robust Performance in Simulated Scenarios: Ares was rigorously evaluated across 16 different simulated hijacking scenarios, varying the attacker and victim AS types (Tier-1, content, enterprise, transit access). In critical scenarios where Tier-1 or content ASes were victims, Ares achieved an average recall rate of 97.2% for exact prefix hijackings and 99.3% for sub-prefix hijackings. Even against enterprise and transit access victims, recall rates remained high at 98.5% for exact prefix hijackings and 97.0% for sub-prefix hijackings.
• Minimal False Positives in Real-World BGP Changes: When tested on sampled real-world BGP changes, Ares maintained a remarkably low false positive rate of 1.06%, further validating its practical applicability and reliability in dynamic internet environments.
• High Efficiency and Real-time Capability: Ares exhibits low runtime overhead, processing updates from a RIPE collector in October 2020 at an average of just 6.33 seconds every 5 minutes. It consistently used less than 8 seconds for most 5-minute data intervals during historical event detection. This efficiency demonstrates Ares's capability for real-time detection, making it suitable for active monitoring systems.

These findings collectively establish Ares as a highly effective, efficient, and reliable solution for comprehensive path hijacking detection, addressing a critical gap in internet routing security.

Technical Deep Dive

▶ Watch: Ares's architecture and weighted edited distance (WED) explained (4:50)

Ares's innovative approach to path hijacking detection is rooted in the fundamental observation that a hijacking event fundamentally alters the routing tree for a specific IP prefix. Instead of focusing solely on individual BGP announcements or origin ASes, Ares monitors the aggregate view of best paths to a prefix, as observed by a set of Route Views (RVs) peers. The system then compares newly emerged routing trees with existing ones to identify anomalies indicative of path hijacking.

The architecture of Ares is composed of three main components: a Route Monitor, a Clustering module, and an Anomaly Detector.

Weighted Edited Distance (WED)

A core challenge in comparing routing trees is quantifying their differences in a meaningful way that amplifies suspicious changes. Ares addresses this by designing a specific type of Weighted Edited Distance (WED). Unlike standard edit distances, Ares's WED is tailored to BGP routing trees to differentiate between normal routing changes and malicious hijacking events.

The WED calculates the cost of transforming one routing tree into another, considering operations like edge deletion and insertion. Crucially, Ares assigns high weights to specific types of links to amplify their impact on the distance calculation:

• Suspicious Links: Links that appear infrequently in the internet or span large geographic distances are considered more suspicious. These are rare in legitimate routing and are thus more likely to be forged links introduced by an attacker.
• Impactful Links: Links closer to the origin AS or observed by a larger number of VPs (presumably referring to Route Views peers or vantage points) are deemed more impactful. Changes to such links have a greater effect on internet routing and are therefore assigned higher weights.

For instance, if two trees differ by a "red link" (highly impactful/suspicious) versus a "blue link" (less impactful), the WED will register a significantly larger difference for the red link, making the anomaly more pronounced. This selective weighting allows Ares to effectively quantify and highlight the differences that are most indicative of a hijacking event.

Clustering Strategy for Efficiency

Directly comparing every newly observed routing tree with all existing trees for the same origin AS would incur an unmanageably high computational overhead. To overcome this, Ares employs a sophisticated clustering strategy to reduce the number of comparisons required.

The clustering process involves two main steps:

1. Topology Merging: Initially, routing trees with identical topologies are merged using a hash function. This step quickly consolidates exact duplicates, reducing the initial set of unique trees.
2. Similarity Clustering: Subsequently, similar trees are merged into clusters based on their WED and a predefined threshold. If the WED between two routing trees is below this threshold, they are considered sufficiently similar and are grouped into the same cluster.

After this clustering process, Ares only needs to compare newly observed trees with the representatives of these existing clusters. If a newly emerged tree cannot be merged into any existing cluster (i.e., its WED to all existing cluster representatives exceeds the threshold), it is flagged as a candidate alarm. This significantly reduces the computational burden, making the detection process feasible and efficient.

Heuristic Filters for False Positive Mitigation

Candidate alarms, while potentially indicative of hijacking, can also be triggered by normal, albeit unusual, BGP updates or incomplete convergence. To mitigate false positives, Ares incorporates four heuristic rules that act as filters for candidate alarms:

1. Partial Added Distance: This heuristic recognizes that the disappearance of edges in a routing tree can be a normal part of BGP convergence, rather than a sign of hijacking. When calculating the WED for a candidate alarm, Ares specifically ignores ages (edges) that have disappeared. This prevents false alarms triggered by normal route withdrawals or changes where a new, smaller tree is a subset of a previous one.
2. Size of New Cluster: Analysis of historical BGP hijacking events reveals that attackers typically target a limited number of prefixes. Therefore, if a candidate alarm involves a very large number of prefixes, it is less likely to be a hijacking event. This heuristic filters out candidate alarms that affect an unusually high volume of prefixes, based on the observed patterns of legitimate BGP updates versus targeted attacks.
3. Historical Information: Ares leverages historical routing context to validate candidate alarms. It compares the routing tree associated with a candidate alarm against former versions of routing trees from the same origin AS. If the WED between the candidate alarm's tree and any historical version is below the preset threshold, it suggests that the current state is not entirely novel but rather a reversion or a known variant, indicating a normal BGP update rather than a hijack.
4. Existing Relationships: The final heuristic examines the nature of high-weighted links within a candidate alarm. If a high-weighted link (i.e., a suspicious or impactful link as defined by WED) is not found in a business relationship dataset or if it violates the value-free principle (e.g., a peer-to-peer link that should not carry transit traffic), it significantly increases the suspicion level. Such links are highly indicative of forged paths. If a candidate alarm passes the first three filters and contains such a highly suspicious link, it is finally classified as a true alarm.

These technical components—WED, clustering, and heuristic filters—work in concert to enable Ares to effectively and efficiently identify path hijacking events with high accuracy and a low rate of false positives.

Evaluation and Effectiveness

▶ Watch: Heuristic rules to filter false alarms from BGP updates (8:00)

While the talk did not present a live demonstration in the traditional sense, the effectiveness of Ares was rigorously evaluated through extensive testing against both historical and simulated BGP hijacking events, alongside real-world BGP changes. This comprehensive evaluation serves as a robust proof of concept for Ares's capabilities.

Firstly, Ares was tested against 12 historical BGP hijacking events. These events, which occurred in the past and are well-documented, provided a crucial benchmark for the system's ability to identify real-world attacks. Ares successfully detected all 12 events, achieving a 100% recall rate. Critically, during this process, Ares maintained an average of only 2.31 alarms per hour, demonstrating its ability to accurately identify threats without overwhelming operators with false positives.

Secondly, to assess its performance across a wider range of potential attack scenarios, researchers generated simulated hijacking events. This involved 16 different scenarios, varying the types of attacker and victim ASes, including Tier-1 providers, content providers, enterprise networks, and transit access providers. The results were highly encouraging:

• For exact prefix hijacking and sub-prefix hijacking scenarios where non-Tier-1 attackers targeted Tier-1 or content victims, Ares achieved an average recall rate of 97.2% and 99.3%, respectively. These are particularly important scenarios given the critical role of Tier-1 and content ASes in internet infrastructure.
• Even when detecting hijacks against inter-enterprise and transit access victims, Ares maintained strong performance, with recall rates of 98.5% for exact prefix hijackings and 97.0% for sub-prefix hijackings.

Beyond recall rates, Ares's false positive rate was also evaluated on sampled real-world BGP changes. In this dynamic and often noisy environment, Ares maintained a very low false positive rate of 1.06%, underscoring its practical reliability for continuous monitoring.

Finally, the runtime overhead of Ares was a key aspect of the evaluation, demonstrating its suitability for real-time deployment. When processing historical hijacking events, Ares typically used less than 8 seconds for every five minutes of data. More specifically, it took an average of only 6.33 seconds to process updates from a RIPE collector every 5 minutes in October 2020. This high efficiency and low runtime overhead confirm Ares's capability to operate as a real-time detection system, crucial for mitigating fast-evolving threats in internet routing. The detailed results across various scenarios underscore Ares's robust and efficient performance in identifying complex path hijacking attacks.

Defensive Implications

▶ Watch: Evaluation results: 100% recall and low false positives (11:00)

The development and validation of Ares offer critical insights and actionable strategies for network defenders seeking to bolster their resilience against BGP path hijacking. The core implication is the necessity of moving beyond origin-centric validation and adopting methods that scrutinize the entire AS path and the resulting routing topology.

Here are key defensive implications:

• Prioritize Path Hijacking Detection: Organizations, especially those operating critical infrastructure (Tier-1, content providers), must recognize that ROV (Route Origin Validation) is insufficient for comprehensive BGP security. Dedicated solutions or methodologies capable of detecting path hijacking, like Ares, are essential.
• Monitor Routing Tree Changes: Defenders should implement systems that monitor and analyze changes in the routing tree for their prefixes. Understanding how the set of best paths evolves, rather than just individual announcements, provides a more holistic view of routing integrity.
• Scrutinize Suspicious Links: Emphasize the identification of suspicious links within AS paths. Links that are geographically distant, appear infrequently in typical internet routing, or violate established business relationships (e.g., transit links where only peering should exist) should trigger elevated alerts.
• Leverage Historical Context: Incorporate historical routing data into detection mechanisms. Understanding the normal evolution of routing paths for an AS allows for better differentiation between legitimate BGP updates and potential hijacking attempts. Solutions should be able to compare current routing states against historical norms.
• Implement Real-time Monitoring: Given the speed at which BGP changes propagate and attacks can unfold, detection systems must be efficient enough for real-time operation. The low runtime overhead demonstrated by Ares highlights the feasibility of such systems.
• Integrate with BGP Watch or Similar Platforms: The integration of Ares into the BGP watch project, a collaborative BGP routing analysis and diagnosis platform, suggests a model for broader adoption. Defenders should explore collaborative platforms or integrate similar advanced detection capabilities into their existing network monitoring tools.
• Understand BGP Convergence: Defenders need to distinguish between incomplete BGP convergence and malicious activity. Heuristics like "partial added distance" in Ares, which account for the disappearance of edges during normal convergence, are crucial for reducing false positives and focusing on genuine threats.
• Collaborate and Share Threat Intelligence: The BGP ecosystem relies on trust and collaboration. Sharing information about detected anomalies and confirmed hijackings can help improve the collective defense posture across the internet.

By adopting a proactive and comprehensive approach to monitoring routing trees and scrutinizing AS paths, network defenders can significantly enhance their ability to detect and respond to sophisticated BGP path hijacking attacks, thereby protecting their traffic and maintaining the stability of the internet.

Key Takeaways

• Path hijacking is a critical and complex threat that bypasses traditional origin-centric BGP security mechanisms like ROV.
• Ares introduces a novel approach by detecting path hijacking through the monitoring and comparison of routing trees for IP prefixes.
• Weighted Edited Distance (WED) is central to Ares, specifically designed to amplify differences introduced by suspicious and impactful links in routing trees.
• Efficiency is achieved through a clustering strategy that groups similar routing trees, significantly reducing computational overhead for real-time detection.
• Ares employs four heuristic filters (partial added distance, size of new cluster, historical information, existing relationships) to effectively mitigate false positives caused by normal BGP dynamics.
• Evaluations confirm Ares's high performance, demonstrating 100% recall on historical events, high recall (97-99%) in diverse simulated scenarios, and a consistently low false positive rate (1.06% on real-world data), all while maintaining real-time processing efficiency.

About the Speaker(s)

Yinxiang Tao is a researcher from Chinua University who presented the work on Ares. Their research focuses on enhancing internet routing security, specifically addressing the challenges posed by BGP path hijacking. Yinxiang Tao is also involved in the BGP watch project, a collaborative platform for BGP routing analysis and diagnosis, where Ares has been integrated to further its real-world application and impact.