AS-CRED: Reputation and Alert Service for Interdomain Routing

Jian Chang, Krishna K. Venkatasubramanian, Andrew G. West, Sampath Kannan, Insup Lee, Boon Thau Loo, Oleg Sokolsky

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

Abstract

As the backbone routing system of the Internet, the operational aspect of the interdomain routing is highly complex. Building a trustworthy ecosystem for interdomain routing requires the proper maintenance of trust relationships among tens of thousands of peer IP domains called autonomous systems (ASes). ASes today implicitly trust any routing information received from other ASes as part of border gateway protocol (BGP) updates. Such blind trust is problematic given the dramatic rise in the number of anomalous updates being disseminated, which pose grave security consequences for the interdomain routing operation. In this paper, we present AS-CRED, an AS reputation and alert service that not only detects anomalous BGP updates, but also provides a quantitative view of AS' tendencies to perpetrate anomalous behavior. AS-CRED focuses on detecting two types of anomalous updates: 1) hijacked updates where ASes announcing a prefix that they do not own, and 2) vacillating updates that are part of a quick succession of announcements and withdrawals involving a specific prefix, rendering the information practically ineffective for routing. AS-CRED works by analyzing the past updates announced by ASes for the presence of these anomalies. Based on this analysis, it generates AS reputation values that provide an aggregate and quantitative view of the AS' anomalous behavior history. The reputation values are then used in a tiered alert system for tracking any subsequent anomalous updates observed. Analyzing AS-CRED's operation with real-world BGP traffic over six months, we demonstrate the effectiveness and improvement of the proposed approach over similar alert systems.
BibTeX
@inproceedings{chang2013as,
  author = {Jian Chang and Krishna K. Venkatasubramanian and Andrew G. West and Sampath Kannan and Insup Lee and Boon Thau Loo and Oleg Sokolsky},
  title = {{AS-CRED: Reputation and Alert Service for Interdomain Routing}},
  booktitle = {IEEE Syst. J},
  year = {2013},
  url = {https://openreview.net/forum?id=BJrm3XNe0vo},
}
Figure