A couple of months ago, we discussed how a small Czech provider ended up causing global Internet mayhem by tickling a Cisco bug via a rather ridiculous routing announcement. While it's easy to fault the instigator of this meltdown, ultimate responsibility belongs with the vendors of poorly tested code. If we've learned anything in decades of software engineering, it is that you can't assume anything about user input. If you don't check that input for validity, you are not just being careless, you are creating a time bomb that will eventually go off. Another such bomb went off on Sunday, 3 May 2009, taking out a large swath of the Internet. We recount the sorry tale here.
Sundays are usually pretty quiet from an engineering perspective on the Internet, so we were surprised by a sudden and prolonged influx of routing updates at our collection sites. Thankfully, we have some very nifty event correlation software, written by Renesys über-hacker Alin Popescu, to which I turned to see what was going on. Alin's code sorts through all the routing activity on the Internet in real time and correlates activity via the attributes they have in common. We can then say things like "this spike in outages came from networks in Kyrgyzstan as transited via Golden Telecom in Russia", potentially providing some insight into the root cause of the problem. It's really very slick. However, the only problem with pinpointing Sunday's event was that it occurred all over the place. We saw sharp spikes in outages and instabilities in Indonesia, Bulgaria, Germany, Romania, Brazil, Russia, the United States and many other places. Upwards of a couple thousand prefixes (networks) were impacted during a period of about 6 hours. Given the wide reach of the event, we immediately thought of the Czech situation and wondered if this was another live Internet QA test. Turns out we were right.
To understand the problem, let's first provide some background. As readers of this blog will know, every organization responsible for Internet routing has two things under their control: block(s) of IP addresses (prefixes) and an identifying number, or ASN. Like IP addresses themselves, ASNs are also running out, at least the old style ones. The original Internet designers allocated only 2 bytes for storing ASNs, which means at most 65,536 of them. Since then, ASNs have been largely allocated consecutively starting at 1, with Phosworks Drift & Services getting the most recent allocation of ASN 49232. Reserved (private) ASNs are at the high end of the range, starting at 64512. So this means that at present we only have about 15 thousand 2-byte ASNs remaining unassigned.
If there weren't an alternative, the 2-byte limitation for ASNs would mean that before too much longer, there would be no new members of the Internet routing club: no new ISPs and no companies with multiple providers and direct control of their routing. Fortunately, there is an alternative available today, and that is 4-byte ASNs. RIPE has been assigning them by default since the start of 2009. But unlike IPv6, the proposed alternative to dwindling IPv4 addresses, 4-byte ASNs can seamlessly and safely co-exist with 2-byte ASNs. No complete overhaul of the Internet is required.
Returning to our story, if 4-byte ASNs are available and interoperate with 2-byte ASNs, there shouldn't be any problems with announcing them anyway we want today. Yeah right. The African Network Operators' Group (AfNOG) will soon be meeting in Cairo, Egypt, and plans to be multi-homed. They acquired the 4-byte ASN 327686, which equals 5*(216) + 6 and hence is also written as 5.6, and planned to use it as stated here:
One of the aims of this setup is to demonstrate that 32-bit ASNs do work and people should not steer away from them, especially since the pool of 16-bit ASNs is shrinking fast. A showcase network goes a long way in this regard.
Now, AfNOG does have an IPv4 prefix, 196.200.208.0/20, and a traditional 2-byte ASN, namely 37095, at their disposal. On 30 April at 17:21:49 UTC, we started seeing the 2-byte ASN announcing this prefix, but with ridiculously long AS paths like
- 24863 37095 37095 37095 37095 37095 37095 37095 37095 37095 37095 37095
- 24863 327686 327686 327686 327686 327686 327686 327686 327686 327686 327686 37095
So what happened? Well, not everyone can afford a Cisco or Juniper router. Some folks make do with cheap Linux boxes running the free routing software called Quagga. And you guessed it! Older versions of Quagga have a buffer overflow problem, dropping the associated BGP sessions like a brick when they saw this announcement. The latest Quagga release, 0.99.11, came out on 2 October 2008. The prior version had the following gem of a comment.
/* ASN takes 5 chars at least, plus seperator, see below. * If there is one differing segment type, we need an additional * 2 chars for segment delimiters, and the final '\0'. * Hopefully this is large enough to avoid hitting the realloc * code below for most common sequences. * * With 32bit ASNs, this range will increase, but only worth changing * once there are significant numbers of ASN >= 100000 */Or until someone prepends a 4-byte ASN a few times. Talk about lame. So this latest experiment in real-time Internet QA identified everyone running old versions of Quagga, thanks to the time bomb left behind by one very lazy programmer. The latest version of Quagga appears to handle this condition a little more carefully, but I can't help but wonder about any software version that starts with a zero.
Looking for the positive, it was nice to see some diversity on the Internet with respect to routing. Imagine if this had been a Cisco bug? Still we found it surprising to see the number and variety of organizations running Quagga in a production environment. The following graph gives the per-country distribution of prefixes for every country with at least 10 outages due to this bug.
The lessons are obvious. If you don't check user input and don't allocate sufficient memory, bad things will ultimately happen. Every possible permutation that you can think of, and perhaps some that you can't, will eventually be tried by someone, either accidentally or on purpose. So far, we're mainly seeing the former, which is good news. Ultimately though, bugs need to be found in lab, not in the production Internet.
Great article. It's always amazing to see how easy it is to introduce instability.
Just a clarification question:
What is the exact difference between outage & Unstable in the graph?
Editor's Note: An outaged prefix has been withdrawn from a routing table; an unstable prefix is showing frequent announcements and withdrawals.
A factual corrections:
It was not a buffer overflow. It was a failure to re-allocate sufficient memory for a string form of the AS_PATH. This error condition was carefully checked for and handled (by exiting).
The code in question was integrated into Quagga prior to 4-byte support. My "time bomb" comment on the quagga-list referred to having integrated code that was not robust to future *changes in the code* (i.e. the addition of AS4 support, anticipated even when this code was integrated). The code itself is robust, even with 4-byte paths (once a '5' is changed to a '10' to match the added AS4 support).
I'll admit to the lazy part generally, but in this specific case it was more a failure of foresight than laziness.
I think you may be misinterpreting the comment in the Quagga code - it's talking about pre-allocating a buffer that should be big enough for the common cases, in order to avoid the inefficiency of having to reallocate and grow the buffer later. It's just a performance optimisation and shouldn't affect correctness, so the programmer is not at fault for being lazy and ignoring the very rare large-ASN situations.
The real problem is the similar comment later in that function, where it similarly assumes ASNs are no more than 5 digits, and uses that number when deciding whether to reallocate and grow the buffer. When that assumption is violated it runs out of buffer space and fails. That seems less a case of intentional laziness, and more a case of writing buggy code and not realising the consequences and not testing adequately.
Fantastic article, thanks. Based on your chart, it appears the Internet returned to "normal" levels outages and unstables in about 9-10 hours. Is this a correct interpretation? If so, was it due to operators upgrading to newest version of Quagga in that same timeframe? If so, this seems like an amazing level of uncoordinated response to correct a problem (on a Sunday, no less!). Or am I misunderstanding something?
Editor's Note: Excellent observation and we wondered about the same thing. We are assuming that these folks upgraded Quagga, blocked the announcements taking out their old version of Quagga, or announced their outaged prefixes in some other way, during the restoration time period.
We were hit by this, we debugged, patched and deployed our updated version of quagga in well under an hour. In the shorter term dropping the affected upstream brought us back up.
C-savvy coders able to hack their Quaggas may have been able to get back up and running fast, but operators of router appliances based upon Quagga without source or build tools may not have been so flexible. I wonder how many resorted to having their 2-byte-only upstream simply filter AS23456 on advertisements?