Characterizing Large-scale Routing Anomalies A Case Study of the China Telecom Incident

This blog posting summarizes an article that will appear in the Passive and Active Measurement conference in March 2013. Please refer to the project page for the full write up and data sets.

In April 2010, China Telecom’s network announced incorrect paths to 50,000 IP prefixes, referred to as a “hijack”. While incidents like this are not uncommon [3, 7, 11], there were several properties that made the China Telecom incident unique. The scale of China Telecom’s network meant that (1) they had the capacity to handle the volume of traffic that flowed to their network as a result of the hijack and (2) there was potential for inconsistent state between routers in their network. As a result, traffic was able to flow into China Telecom’s network and back out to the correct destination, referred to as “interception”. Interception is difficult to detect without continuous monitoring because service continues uninterrupted aside from potentially higher network latencies (typically not noticed by Internet users).

The politically sensitive nature of some of the IP prefixes that were hijacked, including those registered to the US Department of Defense, Department of Transport and US Patent and Trademark Office, brought this incident to the attention of the US government in a report issued by the US-China Economic and Security Review Commission [2].

The unusual nature of the China Telecom incident led to widespread speculation on the potential cause of the incident [1, 4, 8, 10]. The incident raises many important questions about how we characterize and reason about large-scale routing incidents when they occur. Our goal was to characterize this incident using only publicly available data and shed light on what may have potentially happened. However, it is important to note that while we can provide evidence to support certain hypothesis there is currently no way to definitively distinguish accidental incidents from those with malicious intent using purely empirical data.

Which countries were impacted?

We first characterize the geographic distribution of the countries where the hijacked prefixes were registered. Our goal was to understand whether the prefixes appear to be a random subset of the routing table maintained at the Chinese router. This would support the conclusion that it was an accidental leak of routing table entries to the global Internet.

Figure 1 plots the geographic distribution of prefixes hijacked by China Telecom compared with the distribution of all routable prefixes on the Internet. Here we can see a disproportionate number of Chinese prefixes (especially belonging to China Telecom’s AS 4134) being hijacked. Additionally, when comparing hijacked prefixes to the global distribution of prefixes there appears to be little evidence for attack. Indeed, the US shows fewer prefixes being hijacked than would be expected based on the global distribution, while countries in the Asia-Pacifiic region (e.g., China, Korea, Australia) have more hijacked prefixes.

Were any of the announcements subprefix hijacks?

Routing on the Internet is done based on the concept of “longest prefix match”, matching based on the first bits in the IP address (e.g., 128.100.0.0/16 represents the set of 65K IP addresses with the first 16 bits in common). If a hijack involves announcing a longer prefix, “subprefix hijacking”, then potentially all traffic for the hijacked prefix will be directed towards the hijacking network. Indeed, this is what happened in the case of Pakistan Telecom when they hijacked YouTube [3].

Subprefix hijacking was extremely rare. When considering the length of the prefixes announced by China Telecom, we observe that subprefix hijacking was extremely rare. Indeed, when we exclude Chinese networks, we observe less than 1% of the hijacked prefixes being longer than prefixes that exist in the routing table.

How was interception possible?

The fact that China Telecom’s network was able to intercept traffic was highly unusual and indeed makes this incident appear even more suspicious. We wanted to understand how interception was possible and whether it could be caused by inconsistencies within China Telecom’s network.

There are two routing decisions that must occur for traffic to be intercepted:
Decision 1. A neighbor of China Telecom must choose to route to China Telecom for the hijacked prefix
Decision 2. A different neighbor of China Telecom must not choose to route to China Telecom for the same prefix.

Figure 2. Example topology that allows for traffic interception. (China Telecom networks shown in purple, business relationships between networks denoted by arrows.)

Figure 2 shows a topology observed in Routeviews data [12] where these two events will occur. First, AT&T will choose the path announced by China Telecom because it is shorter than the path announced by Level 3 (3 hops vs. 4 hops). Second, Level 3 will not choose the path announced by China Telecom. This is because Verizon is a customer of Level 3, whereas China Telecom is a peer. Level 3 will prefer to route to its customer Verizon (because it will pay for the traffic) rather than route to its peer. As a result, traffic is able to flow from AT&T, into China Telecom’s network and back out to the intended destination.

Table 1. Neighboring networks that routed towards China Telecom

Which networks routed to China Telecom?

We first consider how many networks made Decision 1 and chose to route traffic to China Telecom. In total, we observe 44 networks routing traffic towards China Telecom. Table 1 summarizes the networks that chose to route to China Telecom for the largest number of prefixes. Table 1 highlights the role of geography in the hijack, with networks operating in Europe and Asia-Pacific regions being most impacted. Academic networks (AARNet and National LambdaRail) are also heavily impacted.

China Telecom’s path was shorter than the existing path. When we consider the paths these networks had to the destination prefixes, we find that 98 percent of the time the path offered by China Telecom was shorter than their existing path.

Why did networks not route to China Telecom?

We use traceroute measurements from the iPlane project [9] to understand why neighboring ASes chose not to route to China Telecom (Decision 2). In Figure 2, Level 3 chooses not to route to China Telecom because it has a path via its customer Verizon. However, this is only one reason a network would choose not to route to China Telecom. We consider the cases of interception observed in the traceroute measurements and determine why the neighboring network did not route to China Telecom.

Table 2. Why networks chose not to route to China Telecom

Table 2 summarizes the reasons neighbors of China Telecom did not route to China Telecom. Here we consider the 357 traceroutes where interception was observed and a response was received from the target. The majority of neighbors handling intercepted traffic did not choose the China Telecom route because it was longer than their existing route for the prefix in question. However, in many cases (39 percent) networks maintained their existing path to a customer network and continued to export this path to China Telecom, which allowed China Telecom to maintain connectivity to the victim prefix.

Discussion

Our study sheds light on properties of the China Telecom incident using only publicly available data sets.

On diagnosing routing incidents. Our work highlights the challenge of understanding large-scale routing incidents from a purely technical perspective. While empirical analysis can provide evidence to support or refute hypotheses about root cause, it cannot prove the intent behind the incident. However, empirical analysis can provide a starting point for discussions about the incident.

On the available data. When the results of analysis can lead to real-world reaction it is important that the data used for analysis is as complete as possible and robustness/limitation of results are clearly stated. These two properties can be achieved by increasing the number of BGP monitors [6] and performing careful analysis of robustness and limitations [5].

References

[1] BGPMon. China telecom hijack, 2010. http://bgpmon.net/blog/?p=282

[2] D. Blumenthal, P. Brookes, R. Cleveland, J. Fiedler, P. Mulloy, W. Reinsch,
D. Shea, P. Videnieks, M. Wessel, and L. Wortzel. Report to Congress of the
US-China Economic and Security Review Commission, 2010. http://www.uscc.
gov/annual_report/2010/annual_report_full_10.pdf.

[3] M. Brown. Renesys Blog. Pakistan hijacks YouTube. http://www.renesys.com/blog/2008/
02/pakistan_hijacks_youtube_1.shtml.

[4] J. Cowie. Renesys blog: China’s 18-minute mystery. http://www.renesys.com/
blog/2010/11/chinas-18-minute-mystery.shtml

[5] P. Gill, M. Schapira, and S. Goldberg. Modeling on quicksand: Dealing with the
scarcity of ground truth in interdomain routing data. ACM SIGCOMM Computer
Communication Review, 2012.

[6] E. Gregori, A. Improta, L. Lenzini, L. Rossi, and L. Sani. On the incompleteness
of the AS-level graph: A novel methodology for BGP route collector placement. In
ACM Internet Measurement Conference, 2012.

[7] V. Khare, Q. Ju, and B. Zhang. Concurrent prefix hijacks: Occurrence and impacts.
In ACM Internet Measurement Conference, 2012.

[8] C. Labovitz. China hijacks 15% of Internet traffic?, 2010. http://ddos.
arbornetworks.com/2010/11/china-hijacks-15-of-internet-traffic/.

[9] H. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy,
and A. Venkataramani. iPlane: An information plane for distributed services. In
In Proc. of OSDI, 2006

[10] R. McMillan. A Chinese ISP momentarily hijacks the Internet,
2010. http://www.nytimes.com/external/idg/2010/04/08/
08idg-a-chinese-isp-momentarily-hijacks-the-internet-33717.html

[11] S. Misel. “Wow, AS7007!”. Merit NANOG Archive, 1997. http://www.merit.
edu/mail.archives/nanog/1997-04/msg00340.html.

[12] Route views project. http://www.routeviews.org/.