TL;DR
This paper introduces AS-CRED, a novel system that builds trust in the Internet's routing infrastructure by assigning reputation scores to Autonomous Systems (ASes). AS-CRED analyzes historical BGP update data to detect anomalous routing behavior, such as prefix hijacking and excessive route flapping, and uses these insights to generate tiered alerts, significantly improving upon existing methods.
What Problem Does This Paper Address?
The Border Gateway Protocol (BGP) is the backbone of the internet, enabling communication between different network domains (Autonomous Systems or ASes). However, BGP operates on a principle of implicit trust: ASes generally accept routing information from their peers without rigorous verification. This blind trust is a critical vulnerability, as evidenced by the increasing number of anomalous BGP updates. These anomalies, often caused by misconfigurations or malicious intent, can lead to widespread network disruptions, effectively making parts of the internet inaccessible. The paper highlights three core challenges: the lack of a definitive "ground truth" for validating routing information, the dynamic and often mixed behavior of ASes (announcing both valid and invalid routes), and the sheer scale of the internet, making comprehensive security solutions difficult to deploy.
Methods
AS-CRED tackles these challenges with a multi-pronged approach centered around reputation and anomaly detection.
- Historical Anomaly Detection: The system analyzes past BGP updates to identify two types of anomalous behaviors:
- Hijacked Updates: An AS announces a prefix that it does not legitimately own.
-
Vacillating Updates: An AS repeatedly announces and withdraws a prefix in quick succession, rendering the routing information unstable and ineffective. This detection is based on analyzing the stability of AS-prefix bindings, using metrics like prevalence (the percentage of time a prefix is claimed) and persistence (the average duration of a binding).
-
AS Reputation Function: Based on the detected anomalies, AS-CRED computes a reputation score for each AS. This score is a quantitative measure of an AS's tendency to exhibit poor behavior. The reputation function uses a time-decay mechanism, giving more weight to recent anomalous activities and allowing reputations to naturally improve over time if no further bad behavior is observed.
- Tiered Alert System: The system employs a multi-level alert mechanism. A "white-list" (Valid Binding List or VBL) of stable, legitimate AS-prefix bindings is maintained. Updates corresponding to entries in the VBL are considered valid and generate no alerts. For non-VBL entries, the AS's reputation score is used to predict the likelihood of anomalous behavior. A Support Vector Machine (SVM) classifier is trained to predict "Vacillating" or "Hijacked" alerts. A special "Potentially Invalid" alert is also introduced to flag reputable ASes that start exhibiting unusual behavior, mitigating the risk of trusting them implicitly.
Datasets
The primary dataset used in this research is BGP trace data from the RouteViews project. This data was collected over a six-month period and served as the basis for both training the anomaly detection and reputation models and evaluating the system's performance. The paper also mentions using Internet Routing Registries (IRR) as a source of ground truth for validating AS-prefix bindings and assessing the accuracy of the anomaly detection.
Key Insights and Ideas
- Past behavior predicts future behavior: A core insight is that ASes exhibiting anomalous behavior in the past are highly likely to repeat it. This forms the foundation of the reputation system.
- Reputation as a nuanced metric: Instead of a simple binary "good/bad" classification, AS-CRED provides a quantitative reputation score that reflects the tendency towards anomalous behavior, offering a more sophisticated view.
- Tiered alerts are crucial: A single type of alert is insufficient for the complexity of BGP. AS-CRED's tiered system (VBL filtering, SVM-based prediction, and "Potentially Invalid" alerts) effectively balances security with the need to avoid false positives.
- The "white-list" is a powerful tool: Maintaining a list of known good AS-prefix bindings significantly reduces the workload for anomaly detection and alert generation, acting as a crucial filter.
- Time-decay is essential for dynamic environments: The internet routing landscape is constantly evolving. The time-decay in the reputation function ensures that the system adapts to changes in AS behavior.
Key Results
- High Accuracy in Anomaly Detection: The AS-CRED system demonstrated high accuracy in classifying AS-prefix bindings, with a significant majority of bindings classified as "Good" or "Vacillating" being validated against IRR data.
- Improved Alert Accuracy over Existing Systems: When compared to the Internet Alert Registry (IAR), AS-CRED showed a significantly lower error rate (12.8% vs. 66.3%) in identifying hijacked prefixes.
- Effective Detection of Vacillating Bindings: The system accurately identified vacillating bindings with approximately 95% correctness.
- Repetitive Nature of Anomalies: The analysis confirmed that a small percentage of ASes are responsible for a disproportionately large number of anomalous updates, and these ASes tend to repeat their problematic behavior.
- Quantitative Reputation Reflects Behavior: The reputation scores generated by AS-CRED were shown to be representative of an AS's historical anomalous activities, providing a predictive metric.
Limitations and Future Work
- Reliance on RouteViews: The system's performance is dependent on the trustworthiness and comprehensiveness of the RouteViews data. While RouteViews is considered a good source, potential biases or gaps could affect results.
- Ground Truth Imperfection: The use of IRR as a ground truth is acknowledged as imperfect, meaning that some misclassifications might still occur.
- Data Source Diversity: The authors suggest that incorporating data from multiple BGP collectors (e.g., RIPE RIS) could further improve the accuracy and coverage of AS-CRED.
- More Descriptive AS Behaviors: Future work aims to define and track a wider range of AS behaviors beyond just hijacked and vacillating updates.
- Predicting Invalid Behavior Volume: The goal is to use the AS reputation information to predict the likely volume of invalid BGP behaviors at any given time.
- Enhancing Slander Mitigation: The paper mentions plans to integrate data-plane probing techniques to build better fingerprints of ASes and improve defenses against slander attacks.
Summary updated