ABSTRACT
Being the backbone routing system of the Internet, the operational aspect of the inter-domain routing is highly complex. Building a trustworthy ecosystem for inter-domain 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 the 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 inter-domain routing operation. In this paper, we present ASCRED, 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.
BACKGROUND
Hijacked Updates: these updates establish AS-prefix bindings with prefixes not belonging to the AS making the announcement. Table I shows a list of wellknown hijacked prefix announcements in the past. Hijacking is a persistent threat within the inter-domain world and has been triggered as a result of misconfiguration or for malicious purposes such as spamming.
For instance, AS37035 was seen announcing and withdrawing the prefix 41.222.179.0/24, which it owns, 4824 times between Dec. 3, 2009 and Dec. 7, 2009 (more examples are shown in Table II). This amounts to announcing and withdrawing the prefix repeatedly, once every 1.5 minutes on average.
AS-CRED: REPUTATION AND ALERT SERVICE FOR INTER-DOMAIN ROUTING
Fig. 1. AS-CRED Architecture.
The AS-CRED service is designed to be a portal for disseminating information about ASes and their anomalous updates announcements. AS-CRED has five main components (see Figure 1)
- BGP Activity Manager
- Historical Anomaly Detector
- Reputation Manager
- Reputation Portal
- Alert Manager
Fig. 2. Data Source Time Windows.
Our experiments began with the BGP data from Nov. 1, 2009 – Dec. 30, 2009 (see Figure 2). This 60 day period is the initial observation window. AS behavior during this period is used to compute the reputation of the ASes on Jan. 1, 2010, leaving a 24-hour grace-period on Dec. 31, 2009. These reputations are then used to generate alerts for the updates received on Jan. 1, 2010.
HISTORICAL ANOMALY DETECTION
Computing reputation for ASes requires feedback on their historical prefix announcements. In this section, we present the stability property used by the Historical Anomaly Detector component to generate feedback for reputation computation.
In the inter-domain routing world, it has been shown that valid AS-prefix bindings last for long durations and are very stable in nature. On the other hand, shorter binding duration implies greater chances of the binding being invalid. Inspired by this results, we first present two heuristics to compute the level of stability of AS-prefix bindings and can therefore can be used to deduce their validity.
REPUTATION-BASED ALERTS
Fig. 3. AS-CRED Alert Generation Process.
Figure 3 illustrates the alert generation process. In ASCRED, the alerts are generated based on a combination of the VBL filtering and reputation-based labeling. The alert service is tiered in the types of alerts generated. This is specifically designed to tackle the complex dynamics of BGP operation. We believe that existing alert systems that produce binary alerts of goodness or badness of updates are inherently incapable of capturing this complexit.
AS-CRED PARAMETER SELECTION
Fig. 4. Setting TPs and TPr Threshold Values.
Figure 4 shows our analysis using IRR for different TPr and TPs for updates received between Nov. 1, 2009 to Dec. 30, 2009. Notice that we do not have to consider false negatives (FNs) in identifying the threshold values as it falls entirely under the FP surface. We find that the lowest FP value is obtained at TPr = 1% and TPs = 4 hours. However, for this work, we chose the values TPr = 1% and TPs = 10 hours as the thresholds.
SECURITY ANALYSIS OF AS-CRED
AS-CRED provides reputation values that can be used by ASes to be cognizant of the behavior of others. Consequently, it exposes itself to attacks that try to: (1) promote ASes, or (2) defame ASes. In this section, we analyze AS-CRED’s resilience to such attacks AS-CRED provides reputation values that can be used by ASes to be cognizant of the behavior of others. Consequently, it exposes itself to attacks that try to: (1) promote ASes, or (2) defame ASes. In this section, we analyze AS-CRED’s resilience to such attacks.
As a result, the reputation function is designed to only consider poor behavior. The only way reputation can be improved is to wait and let the time-decay function heal the reputation. Furthermore, a “healed” reputation value will not give an AS any substantial benefit since: (1) reputable ASes are given only limited trust; and (2) AS-CRED provides not just current AS reputation values but also the past reputation trends.
PERFORMANCE RESULTS
Fig. 5. (a) Validity of AS-prefix bindings in GBU sets, (b) Number of Announcements and Withdrawals of vacillating AS-prefix bindings in B set compared to AS-prefix bindings in G set.
Figure 5(a) shows the percentage of AS-prefix bindings in the G set, vacillating bindings in the B set and hijacked ones in the U set that have a match in IRR. It can be seen that AS-prefix bindings in the G and the B sets can overwhelmingly be found in IRR, compared to those in the U set. Figure 5(b) charts the average number of instances of binding establishment and withdrawal seen for entries in the G set and the vacillating entries in the B set on a selected set of dates.
Fig. 6. (a) Historical Anomaly Detection Statistics, (b) Extent of Poor Behaviors displayed.
In this subsection, we summarize the results of the historical anomaly detection and show that ASes repeat their behaviors. Figure 6(a) shows the summary of the historical anomaly detection over the six months of AS-CRED’s operation. Figure 6(b) shows, with the benefit of hindsight, how many of the AS-prefix bindings seen every day from Jan. 1, 2010 to Jun. 30, 2010 eventually turned out to be hijacked or vacillating.
Fig. 8. Alert Generation Statistics.
Figure 8 shows the percentage of updates triggering alerts during the six months of alert generation. As seen during historical anomaly detection, we find that the number of alerts generated for updates with vacillating bindings in VT set are an order of magnitude greater than those in the HJ set or updates having illegal AS numbers. In the rest of the section, we analyze the correctness and errors of the alerts generated.
RELATED WORK
Recent years have seen considerable number of works in anomaly detection and prevention for the inter-domain routing system. In this section we describe the prominent research in this area.
Anomaly Prevention Mechanisms. S-BGP is one of the earliest and the most concrete security mechanism to address BGP vulnerabilities. It constructs PKIs rooted at RIRs for authenticating IP prefix ownership. AS PATH information is also protected using nested digital signatures as the BGP updates propagate through the network. However, the deployment difficulties and computational overhead of these schemes have made their adoption cumbersome in the inter-domain world.
CONCLUSIONS
In this paper we presented AS-CRED, an AS reputation and alert service that not only detects anomalous BGP updates but also provides a quantitative view of AS behavior. AS-CRED works by computing AS reputation based on feedback provided by analyzing the historical BGP data for the presence of anomalies (i.e., hijacked or vacillating). Based on this analysis, AS-CRED also creates a “white-list” of valid AS-prefix bindings. The reputation and “white-list” are combined to design a novel tiered alert system for tracking subsequent anomalous updates.
We publish the AS reputation information on a publicly available portal website (http://rtg.cis.upenn.edu/qtm/ascred/). The analysis of AS-CRED over a six month period indicates its effectiveness and improvement of over similar alert systems, a fact also demonstrated by its ability to successfully detect large scale hijack events. In the future, we would like to construct more descriptive AS behaviors, and use the resulting AS reputation information to predict the likely amount of invalid BGP behaviors that are going to be exhibited at any given time in the future.
Source: University of Pennsylvania
Authors: Jian Chang | Krishna Venkatasubramanian | Andrew G. West | Sampath Kannan | Insup Lee | Boon Thau Loo | Oleg Sokolsky