Argus

Introduction

Prefix hijacking is often generated by accidental misconfigurations, and may cause serious routing problems and economic losses. To improve the security of BGP, several methods have been proposed, which broadly fall into three categories: cryptographic based prevention, anomaly mitigation, and anomaly detection. Cryptographic approaches usually use the Public Key Infrastructure (PKI) to ensure the authentication of routing announcements and prevent hijacking. They often consume significant router resources due to their computation and storage complexity, and are unlikely to be widely deployed very soon. Anomaly mitigation approaches propose to ignore or demote suspicious routes once they are detected. These approaches are hard to deploy, and their misjudgments may disturb the routing system. At last, anomaly detection approaches aim to discover anomalous information or behavior in BGP announcements and raise alarm. As a viable secure scheme in the current stage, they offer valuable information for the understanding and diagnosis of the routing system, and help to push ISPs to deploy cryptographic solutions.

This paper focuses on the third category, anomaly detection. Although workable detection systems have been developed, more or less, they have weaknesses such as long detection delay, high false alarm rate and great deployment difficulty. Our solution, Argus, exploits a key observation about IP prefix hijacking: polluted routers (i.e., routers whose traffic is hijacked) usually can not communicate with the hosts in the victim prefix, while normal routers can. This observation makes hijacking distinguishable from other anomalous route events, and let Argus achieve four superior capabilities over existing solutions: (1) Low false positive rate: Argus closely correlates the control-plane anomaly and the data-plane reachability information of a large number of vantage points, so that prefix hijacking can be accurately distinguished from other BGP events. (2) Low false negative rate: Argus monitors a much wider range of routing anomalies, including origin AS and AS-path anomalies, and considers the sub-prefix problem, so the chance of missing a hijacking event is much lower. (3) Realtime detection: Argus usually detects a hijacking within a few seconds, while existing methods often need orders of magnitudes longer. (4) Agile: Argus is very easy to deploy, and does not need to upgrade any existing network infrastructure or device.

Key Observation

Generally speaking, when the prefix hijacker acts as a black-hole, it is likely that a data-plane probe sent from an unpolluted AS to the victim prefix can successfully arrive at the destination and get a reply, while a probe from a polluted AS will most probably get no reply. This simple observation is the key basis of Argus, our prefix hijacking detection system. Next, we analyze this data-plane reachability problem in more detail.

As shown in Fig. 3, after an anomalous AS-path affects a portion of ASes in the Internet, the reachability to the affected prefix reflects different scenarios:

1. When multi-origin (e.g., due to AS multi-homing, BGP anycast or static route) or traffic engineering is deployed, a new origin AS or new AS-path segments are introduced, and traffic may reach the destination prefix via different paths. In this case, both the normal ASes and the affected ASes can reach the destination prefix. (Fig. 3(a))
2. When node or link failure happens, there may not exist a valid route to the destination prefix, then no AS can reach it. Firewalls or inactive hosts may also lead to this result. (Fig. 3(b))
3. When route migrates (e.g., due to network merge or prefix acquisition, the ownership of a prefix changes, or new AS-path segments are used, either temporarily or permanently), ASes that have learned the new route are able to reach the destination prefix, while ASes have not learned the new route are not. (Fig. 3(c))
4. Under a hijacking as explained above, normal ASes can reach the destination prefix while polluted ASes can not. (Fig. 3(d))

The relation between the routes (control-plane) and the reachabilities (data-plane) in different ASes can be regarded as a fingerprint of a route event, and by this fingerprint, we can figure out whether a route change is actually caused by a hijacking. In Argus, we use show ip bgp to get the BGP routes, and use ping to test the reachability. These two commands are very simple, and are commonly enabled in a vast number of public route-servers and looking-glasses. These diagnosis nodes lie in different ASes nearly all over the Internet, and using them can greatly enhance our detection capabilities. Argus correlates the control-plane and data-plane information of a large number of diagnosis nodes in a statistical manner.

Prefix Detection System - Argus

Overview

Argus is composed of three main modules: the Anomaly Monitoring Module (AMM), the Live-IP Retrieving Module (LRM), and the Hijacking Identification Module (HIM). The whole system is depicted in Figure 5.

The Anomaly Monitoring Module receives live BGP UPDATEs from BGPmon [2], a real-time BGP feed in the Route Views project [33] that collects UPDATEs from routers all over the world. When the AMM receives an UPDATE, it will check whether the embedded AS-path has an anomalous origin AS or an anomalous AS-path segment according to its local routing information database.

The Live-IP Retrieving Module maintains a pool of live IPs by periodically collecting from various sources. For an anomalous prefix f, it will carefully select an live IP as the probing target of the identification module.

The Hijacking Identification Module is responsible for collecting information from a number of vantage points, computing the fingerprint for the anomalous route event, and making final decisions about whether the suspicious prefix is really hijacked. It is the core of Argus.

Monitor Anomalies

In Argus, we consider three types of route anomalies: origin anomalies (OA), adjacency anomalies (AA), and policy anomalies (PA), as illustrated in Fig. 6.

An origin anomaly (OA) happens when the origin AS in the AS-path of a prefix changes to a different AS. For example, in Figure 6(a), AS3 is not the origin AS of the prefix f, thus any AS-path for f ending with ⟨3⟩ is anomalous. Argus maintains a database which keeps track of the normal origin AS of each prefix to help detect origin anomalies.

In an AS-path of a prefix, if any pair of neighboring ASes has not appeared before, Argus will report an adjancency anomaly (AA), since such a pair indicates that the adjancency between two ASes changes. Figure 6(b) illustrates such an example, where AS3 does not directly connect to AS1, but erroneously announces an AS pair ⟨3,1⟩ in the AS-path.

On the other hand, since BGP is a policy based routing, it often cares about whether routes learned from one neighbor should be propagated to another neighbor. For example, in Figure 6(c), although AS3 directly connects to AS2 and AS4, it should not announce routes learned from its provider AS2 to another provider AS4. In case that a new triple of neighboring ASes appears, e.g., an AS-path containing the triple ⟨4, 3, 2⟩ is received in this example, Argus will report a policy anomaly (PA).

By considering the above three kinds of anomalies, Argus can detect a much wider range of hijackings. Once the AMM detects an anomaly, it will notify the HIM to identify whether a hijacking truly happens. If not, it will add the new origin AS or the AS pair/triple into the local database since they are normal. The database will also be refreshed periodically by removing those origin ASs or AS pairs/triples inactive for a long period (i.e., more than two months).

Retrive Live IPs

When anomaly is detected for a prefix f, the Live-IP Retrieving Module (LRM) tries to find a live IP address $i$ in $f$. The reachability to this address is a key factor for determining whether $f$ is hijacked. The LRM accomplishes this task by maintaining a local database of candidate live IP addresses in all announced prefixes in the Internet. These IPs are collected from CAIDA’s Ark and iPlane daily traceroute results, and from many DNS records.

Identify Hijackings

The Hijacking Identification Module (HIM) employs a number of public route-servers and looking-glasses, called as the eyes of Argus, to finally determine whether an anomaly detected by the AMM is actually a prefix hijacking or not. At each eye, Argus activates two processes, one for gathering the control-plane route status of the victim prefix $f$, and the other for obtaining the data-plane reachability to the selected live IP $i$.

Specifically, Argus uses show ip bgp to extract the best BGP route $p_{t,j}(f)$ that its $j$-th eye chooses for the anomalous prefix f, in the $t$-th second. Then it checks whether $p_{t,j}(f)$ is affected by the anomalous origin AS (or AS pair/triple) reported by the AMM. Meanwhile, Argus uses ping to test whether the live IP $i$ is reachable from each eye. Both of the two commands are very fast, so realtime results can be collected once every second.

After an anomaly is reported, we continuously do that for W seconds on N eyes. At the $t$-th second(1≤$t$≤W), we compose the control-plane results of all eyes into a binary vector $C_t = \lbrace C_{t,j}|1 \le j \le N \rbrace$, where

$C_{t,j}= \begin{cases} 0, & \text{if} \, p_{t,j}(f) \, \text{is} \, \text{affected} \, \text{by} \, \text{the} \, \text{anomaly} \\1, & \text{if} \, p_{t,j}(f) \, \text{is} \, \text{not} \, \text{affected} \, \text{by} \, \text{the} \, \text{anomaly} \end{cases}$

and compose the data-plane reachability results into a binary vector $D_t = \lbrace D_{t,j}|1 \le j \le N \rbrace$, where

$D_{t,j} = \begin{cases} 0, &\text {if} \, \text{the} \, j\text{-th} \, \text{eye} \, \text{gets} \, \text{no} \, \text{reply} \, \text{from} \, \text{the} \, \text{IP} \, i \\1, &\text{if} \, \text{the} \, j\text{-th} \, \text{eye} \, \text{gets} \, \text{a} \, \text{reply} \, \text{from} \, \text{the} \, \text{IP} \, i \end{cases}$

Due to the possible inconsistency between the control and data plane at a node, we do not directly compare $C_{t,j}$ and $D_{t,j}$ of the same $j$-th eye one by one. Instead, we utilize the correlation coefficient of the two vectors $C_t$ and $D_t$ to measure this relationship, mathmatically defined as

$F_t=\frac{\sum_{j=1}^n [(C_{t,j} - \overline{C_t})(D_{t,j}-\overline{D_t})]}{\sqrt{\sum_{j=1}^n(C_{t,j} - \overline{C_t})^2 \times \sum_{j=1}^n(D_{t,j}-\overline{D_t})^2}}$

where $\overline{C_t}$ and $\overline{D_t}$ are the average of $C_{t,j}$’s and $D_{t,j}$’s (1 ≤$j$≤ N) on all eyes, respectively. We also call $F_t$ and $D_t$ the fingerprint and reachability of the route event at time t, respectively. Fig. 8 schematically illustrates the fingerprint and reachability distribution of different route events. When $F_t$ is close to 1, $D_t$ and $C_t$ have a strong positive correlation (i.e., most polluted eyes cannot get reply from the victim prefix, while most normal eyes can), then very probably a prefix hijacking is going on. Since routing may be inconsistent and instable, we raise a hijacking alarm only when $F_t$ is greater than a threshold $\mu$ for at least a period of T seconds. The choice of $\mu$ and T will affect the detection accuracy. We compute $F_t$ in each second for a total of 120 seconds.

Publications

Detecting Prefix Hijackings in the Internet with Argus

Xingang Shi, Yang Xiang, Xia Yin, Zhiliang Wang, Jianping Wu from Tsinghua University

Argus is a prefix hijacking detection system, which leverages not only the control plane information but also the data plane reachability and correlates them togethem to detect potential prefix hijack in the internet. For more details, you can see our paper published in IMC 2012. Argus has won the best community contribution award.

[PDF]

Presentation

Detecting Prefix Hijackings in the Internet with Argus

You can download the slides here.

Hijacking Events

You can find the latest released hijacking alarm here.

Authors

Xingang Shi, Tsinghua University, shixg@cernet.edu.cn

Yang Xiang, Tsinghua University, sharangxy@gmail.com

Zhiliang Wang, Tsinghua University, wzl@cernet.edu.cn

Xia Yin, Tsinghua University, yxia@tsinghua.edu.cn

Jianping Wu, Tsinghua University, jianping@cernet.edu.cn