Rethinking Security For Internet Routing

On June 12, 2015, an incident in the Asia-Pacific region caused network performance problems for hundreds of thousands of Internet destinations, including Facebook and Amazon.^24,37 It was not the result of a natural disaster, a failed transatlantic cable, or a malicious attack. Instead, it resulted from a misconfiguration at a Malaysian ISP that inadvertently exploited the Internet’s Border Gateway Protocol (BGP) to disrupt connectivity at networks in Malaysia and beyond. BGP establishes Internet connectivity by setting up routes between independently operated networks. Over the past two decades, several high-profile routing incidents (often resulting from misconfigurations^4,8,28,30,37) have regularly demonstrated that BGP is highly vulnerable to malicious attacks. BGP attacks cause a victim network Internet traffic to be rerouted to the attacker’s own network. The rerouted traffic might then be dropped before it reaches its legitimate destination^4,28,30,37 or, more deviously, be subject to eavesdropping,^2,32 traffic analysis,³⁶ or tampering.^15,21,34

Back to Top

Barriers to securing BGP. To deal with these vulnerabilities, the Internet community has spent almost two decades considering a variety of protocols for securing BGP.⁵ Today, however, Internet routing remains largely unprotected by BGP security protocols. The sluggish deployment of BGP security is the result of economic, operational, and policy challenges. The root cause for this situation is that the Internet lacks a single authority that can mandate deployment of BGP security upgrades. Deployment decisions are instead made by independently operated networks according to their own local policy and business objectives. BGP security is adopted by a network only if its security benefits are thought to justify its deployment and operational costs. Moreover, the diversity of BGP security protocols has led to some controversy as to which protocol should actually be deployed. This issue is exacerbated by the fact that each protocol offers different security benefits and comes with different costs.

Our goal. Which BGP security protocol should be deployed throughout the Internet? To answer, we have developed a framework for quantifying the security benefits provided to the Internet as a whole by different BGP security protocols. We begin with a full deployment scenario, where a BGP security protocol is deployed by every network in the Internet. In practice, however, full deployment remains elusive. Indeed, a standardized BGP security protocol, the Resource Public Key Infrastructure (RPKI),²⁰ has been in the process of deployment since the start of this decade but currently contains security information about only ≈ 5% of the Internet’s routes.²⁹ We thus also study partial deployment scenarios, where some networks deploy a BGP security protocol, but others do not.

Our results. We obtained our results via simulations of BGP routing on empirically measured graphs of the Internet’s topology. This article focuses on the security benefits provided by a given protocol, on average, to the welfare of the Internet as a whole. First, we find that valuable security benefits can be provided by simple whitelisting technologies—prefix filtering⁹—and they are comparable even to those provided by the strongest cryptographic protocols, notably BGPSEC.¹⁹ Next, we find that partial deployment has been a blind spot for the network routing community; operational issues that can arise during partial deployment cause the strongest cryptographic protocols to provide fewer security benefits than might initially have been expected. Taken together, our results call for rethinking the efforts to promote only the strongest cryptographic routing protocols (such as BGPSEC). Our results point instead toward using a combination of simple whitelisting technology (prefix filtering) available in most BGP-speaking routers today with weaker cryptographic protocols (such as the RPKI).

Back to Top

BGP Threats and Defenses

How does routing with BGP work? Why is BGP vulnerable to attacks? And what BGP security protocols are available to patch these vulnerabilities? We explore the answers using Figure 1.

Routing with BGP. The Internet can be regarded as a network of autonomous systems (ASes). ASes are large networks operated by different organizations, each with a different AS number. In Figure 1, AS 27781 is operated by an ISP in St. Maarten and AS 23520 by an ISP serving the Caribbean, AS 701 is Verizon’s backbone network, and AS 6939 is Hurricane Electric’s backbone network. Viewed at this resolution, the Internet can be described as a graph where nodes are ASes and edges are the links between them. Interconnections between ASes change on a very slow timescale (months to years), so we treat the edges in the AS graph as static.

Neighboring ASes remunerate each other for Internet service according to their business relationship. We show two key business relationships in Figure 1: customer-to-provider, where the customer AS purchases Internet connectivity from its provider AS (a directed edge from customer to provider) or settlement-free peering, where two ASes transit each other’s customer traffic for free (an undirected edge). Such free peering agreements are often established between ASes of equal size or between large content providers (such as Google and Microsoft) and other ASes. Figure 1 is a subgraph of the IPv4 AS topology inferred by Chi et al.⁶ using data from September 24, 2012, and contains 39,056 ASes, 73,442 customer-provider links, and 62,129 settlement-free peering links. All results in this article are based on this IP version 4 (IPv4) AS-level graph; we consider an IPv6 AS-level graph in the online appendix.

IP prefixes. Instead of maintaining routes to all possible Internet Protocol (IP) addresses, ASes use BGP to discover routes to a much smaller number of IP prefixes. An IPv4 is a 32-bit address (such as 72.252.8.8) where every number is a byte in decimal, and the dots are separators. An IP prefix is a set of IP addresses with a common prefix (such as 72.252.0.0/16) is the set of IP addresses {72.252.0.0, 72.252.0.1,..., 72.252.255.255}, where the notation /16 (“slash sixteen”) implies the first 16 bits (the “prefix”) are common to all addresses in the set (namely, those beginning with 72.252). IP prefixes have variable lengths, and the addresses in one IP prefix may contain the addresses in another; for example, IP prefix 72.252.0.0/16 contains IP prefix 72.252.8.0/21). Each AS is allocated a set of IP prefixes; for example, 72.252.0.0/16 is allocated to AS 23520, while 72.252.8.0/21 is allocated to AS 27781 in Figure 1.

Longest-prefix-match routing. The IP address 72.252.8.8 is contained in both IP prefix 72.252.0.0/16 and IP prefix 72.252.8.0/21. So how should routers forward IP packets with destination IP address 72.252.8.8? To avoid ambiguity, every Internet router identifies the longest IP prefix that covers the destination IP address in the packet and forwards the packet along the route to that IP prefix. In Figure 1, a packet with destination IP address 72.252.8.8 would be forwarded on a route to the longer 21-bit IP prefix 72.252.8.0/21 allocated to AS 27781, rather than the shorter 16-bit IP prefix 72.252.0.0/16 allocated to AS 23520.

Learning paths with BGP. How do ASes use BGP to learn the path to 72.252.8.0/21 in Figure 1? The process starts when AS 27781 originates the BGP announcement

72.252.8.0/21 : 27781

to each of its neighbors, including AS 23520. AS 23520 selects this route and sends the BGP announcement

72.252.8:0/21 : 27781, 23520

to its neighbor AS 2828. This process continues until AS m learns following two routes

72.252.8.0/21 :27781, 23520; 2828; 6939 72:252.8.0/21 :27781, 701, 16795

in BGP announcements from its neighbors AS 6939 and AS 16795, respectively. We say these routes are available to AS m, since every AS on each route has actually announced the route to its neighbor on the route. We next discuss why AS m does not have an available route through AS 5580.

Each AS uses its local BGP routing policy to select a single best route from the set of routes it learns from its neighbors. In Figure 1, AS m selects the route through its peer AS 6939; m prefers the “peer route” through its peer AS 6939 (because this route comes at no monetary cost) over the “provider route” through its provider AS 16795 (which comes at monetary cost). Once an AS selects a route, it announces that route to a subset of its neighbors according to its local export policy. In Figure 1, AS 5580 chooses not to announce, to its neighbor AS m, its one-hop peer route to AS 27781. This is because AS 5580 will transit traffic from only one neighbor (AS m) to another (AS 27781) if at least one neighbor is a customer that pays for Internet service.

Why is BGP insecure? BGP is “insecure” because any AS can announce any path it wants to any subset of its neighbors. An attacker can exploit this to reroute traffic to the attacker’s own network.

Threat model. We consider a single attacking AS m that wants to attract, to m‘s own network, the traffic destined to an IP prefix that is legitimately allocated to a victim AS d and actually announced in BGP by d. Outside our scope are attacks (such as by spammers^33,39) on “unused” IP prefixes, or prefixes that are either not allocated or not announced in BGP.^a Attacker m can announce any path it wants to any neighbor it wants, even if that path is bogus, or if announcing that path violates m‘s normal export policies. However, because m cannot lie to its neighbor about their business relationship or about m‘s own AS number (because this information is programmed into its neighbor’s routers), any path announced by m must include m‘s own AS number as the first hop. Finally, the threat of multiple colluding ASes is out of scope, since the strongest proposals for securing BGP cannot withstand this threat,^b and most attacks in the wild involve only a single attacking AS.

We now illustrate the existence of threats to BGP by choosing examples from Figure 1 and simulating them on Chi et al.’s Internet topology,⁶ using a framework described later; the impact of these threats is also described later. (Experts might thus wish to read the section on quantifying security benefits first.) The following threats are commonly seen in the wild.

Threat. Subprefix hijack. One devastating attack on BGP is the subprefix hijack.^{4,21,28,31,34} If AS m wishes to launch a subprefix hijack on the victim’s IP prefix 72.252.8.0/21 in Figure 1, it announces to each of its neighbors a route, such as

72.252.8.0/24 : m

Importantly, AS m is not actually allocated this subprefix. Nevertheless, longest-prefix match routing still ensures that any AS that learns the bogus route to the subprefix 72.252.8.0/24 through m will forward all IP packets destined for addresses in this subprefix to m. Notice, because of longest-prefix-match routing, the actual ASes on the attacker’s route are irrelevant.

Threat. Prefix hijack. In a prefix hijack,^8,37 the hijacker originates the exact same IP prefix that belongs to a victim. The attacker m in Figure 1 can launch this attack on a victim IP prefix 72.252.8.0/21 by announcing

72.252.8.0/21 : m

to its neighbors. Rather than attracting 100% of traffic, as in a subprefix hijack, in a prefix hijack, traffic will split, with ASes “closer” to the hijacker selecting the hijacked route, and ASes “closer” to the legitimate origin AS selecting the legitimate route. We simulated this attack by m on prefix 72.252.8.0/21 on Chi et al.’s Internet topology⁶ and found that 56% of ASes route through m and 44% route through AS 27781.

---

BGP is “insecure” because any AS can announce any path it wants to any subset of its neighbors.

---

Threat. Route leak. In a route leak, an attacker violates its normal export policies by announcing a legitimate route to too many of its neighbors.²⁷ In Figure 1, AS 5580 could violate its normal export policies by leaking the route

72.252.8.0/21 : 27781, 5580

to all its neighbors, including its peers AS 23520 and AS m. This violates AS 5580’s normal export policy, which requires AS 5580 to announce peer routes, or routes through a neighboring peer, to neighboring customers only. While route leaks might seem innocuous, several incidents observed in the wild have proved to be quite damaging.^30,37 Simulations, as discussed later, show that the route leak allows AS 5580 to attract traffic from 45% of ASes in the graph instead of the 3.7% it would attract under normal conditions.

How can we secure BGP? The past two decades have seen several proposals for securing BGP.⁵ To simplify the landscape, we describe the most prominent proposals in terms of their security guarantees, as well the threats they can and cannot prevent.

Defense. Origin validation. Prefix and subprefix hijacks arise because BGP does not offer a way to validate the allocation of IP prefixes. To remedy this deficiency, origin validation^5,20,26 provides a trusted database binding ASes to the IP prefixes allocated to them, and any BGP message that does not adhere to this binding is ignored. With origin validation, in Figure 1, m cannot hijack prefix 72.252.8.0/21, because the trusted database does not contain a binding from that prefix to m. The only proposal for origin validation that has seen some deployment²⁹ is a cryptographic certificate infrastructure called the Resource Public Key Infrastructure (RPKI).20 The RPKI is relatively lightweight and requires neither online cryptographic computations nor changes to the BGP message structure. Instead, ASes download and cryptographically validate RPKI certificates to a local cache at infrequent intervals (daily), then check the BGP messages they receive against the already-cryptographically validated information in their local cache.

Threat. The one-hop hijack. While origin validation eliminates prefix and subprefix hijacks, it cannot prevent an attacker from announcing any path that ends at the AS that is legitimately allocated the victim’s IP prefix. Origin validation does not stop AS m in Figure 1 from launching a one-hop hijack, where m announces the route

72.252.8.0/21 : 27781, m

to each of its neighbors. Because the 72.252.8.0/21 is legitimately allocated to AS 27781, this route will not be discarded by origin validation. However, this route is bogus because no edge exists between m and 27781. Simulations, as discussed later, show that this causes 31% of ASes to select bogus routes through m, instead of the legitimate AS 27781.

Defense. Topology validation. The one-hop hijack succeeded because origin validation fails to validate that the first edge (between m and AS 27781) in the BGP announcement actually exists in the AS graph. Topology validation validates that every edge in a BGP announcement exists in the AS graph. Secure Origin BGP (soBGP)40 is a well-known proposal that provides topology validation. Like the RPKI, soBGP uses a cryptographic certificate infrastructure that ASes infrequently download to their local caches to provide origin validation and certify the presence of links between pairs of ASes.^c Like the RPKI, it requires neither changes to the BGP message structure nor to online cryptographic computations.

Threat. Announce an unavailable path. Topology validation does not prevent an attacker from announcing a path that exists in the AS graph, but is not available, or has not been announced by each AS on the route. In Figure 1, the attacker m can attract traffic from 17% of ASes, as discussed later, by announcing the short path

72.252.8.0/21 : 27781, 5580, m

to each of its neighbors, instead of its legitimate longer path through AS 6939 shown in Figure 1. While this short path exists in the topology, it is still bogus because it is not actually available to m; this follows because AS 5580 has an export policy that forbids it from announcing the peer path through AS 27781 to its peer m.

Defense. Path validation. To prevent this attack, path validation forces the attacker to announce only available paths. Path validation is a “gold standard” for BGP security, and several proposals provide this security guarantee;^5,18,19 of them, BGPSEC has the most traction and is being standardized. BGPSEC is relatively heavyweight, requiring deployment of the RPKI, each AS on a route to append its cryptographic digital signature to every BGP message, and each AS on a route to cryptographically validate, in real time, every signature on every BGP message it receives. The computational overhead involved in signing and validating routes for all 500,000 of the Internet’s IP prefixes, in real time and even under router failure-recovery scenarios, could require routers to be upgraded with crypto hardware accelerators.

Threat. Announce an available path. Path validation does not prevent an attacker from announcing a short available path to each of its neighbors, even if doing so violates the attacking AS’s normal export policies, or if the attacker is not actually forwarding traffic along the announced path.^d In Figure 1, m attracts traffic from < 0.01% of ASes when m honestly announces its preferred five-hop peer path through AS 6939. Meanwhile, even with path validation, m can instead announce its shorter (but less-preferred) four-hop provider path

72.252.8:0/21 : 27781, 701; 16795, m

to all its neighbors, allowing m to attract traffic from 4.5% of ASes. Notice this is also a route leak.

Under the assumption there is only a single attacker occupying a single AS, it follows that path validation is a strictly stronger defense than topology validation, and topology validation is strictly stronger than origin validation. Any attack that succeeds against the stronger defense also succeeds against the weaker one. Moreover, each defense provides a mechanism for validating the correctness of BGP announcements, but neither restricts the export policies an AS can use. All three defenses are thus still vulnerable to route leaks. Fortunately, there is an orthogonal defense that can sometimes prevent route leaks.

Defense. Prefix filtering. In this article, we assume that prefix filtering whitelists the BGP announcements made by stub ASes; a stub is an AS with no customers. As stubs are consumers (rather than providers) of Internet service, stubs should carry only incoming traffic destined for their own allocated IP prefixes. If each provider AS has a “prefix list” of the IP prefixes allocated to its customers that are stub ASes, when a stub announces any path to any IP prefix that is not allocated to the stub, the stub’s provider could thus ignore that announcement. If all providers of a particular stub AS implement prefix filtering, prefix filtering completely eliminates every possible attack by that stub, including route leaks. Prefix filtering requires no changes to the BGP message structure, uses access control lists rather than cryptography, is available in most BGP speaking routers, and can be combined with any of the defenses we described earlier. However, it does require an ISP to maintain prefix lists for each customer, by collecting its own data or by using information in public databases (such as Internet Routing Registries³⁵). Because it can be challenging for ISPs to keep this information up to date,³⁵ we use a conservative definition of prefix filtering; indeed, in practice, many ISPs filter not only their stubs but also their customer cone, or their customers, their customer’s customers, and their customer’s customer’s customers.⁹ In the next section we show that even this conservative definition provides tangible security benefits, even though it cannot prevent attacks by non-stub ASes.

Back to Top

Full Deployment

What defense should be deployed in the Internet? Should ISPs require the “gold standard” defense of path validation, which comes at the cost of online cryptographic computations and a modifications to the BGP message structure? Or does the lighter offline cryptography used for origin validation suffice? Should ISPs forgo cryptography altogether and use prefix filtering instead? We aim to answer these questions quantitatively by comparing the efficacy of each defense discussed earlier at limiting the impact of routing attacks. Because we cannot just go out and launch BGP attacks on the Internet, we instead simulate attacks on the empirically measured AS-level topology⁶ described earlier. In this section, we assume a particular defense is fully deployed by every AS. We consider partial deployment scenarios later. We next present our quantitative framework, then describe our results.

Quantifying security benefits. We earlier illustrated the existence of threats to BGP using examples from Figure 1. But how representative are these examples, and what sort of damage can each attack cause? To answer, we simulate routing when attacker AS m performs an attack on victim AS d, and determine what source ASes in the AS graph are safe, or do not select a route that passes through m‘s network, and which are deceived, or are not safe. Then, to get a measure of the global damage m caused to d by the attack, we count the number of deceived ASes when m attacks d. Finally, we measure the overall damage caused by the attack by averaging the number of deceived ASes over randomly selected pairs of attacker AS m and victim AS d. This measurement also allows us to avoid predicting what ASes will launch an attack or what ASes an attack might target. (Other approaches for measuring damage are discussed in the online appendix.)

Modeling routing policies and export policies. We need a concrete model of how ASes select routes during attacks. In practice, ASes’ routing policies can differ between ASes and are often kept private, so we use the classic routing model of Gao and Rexford¹¹ and Huston,¹⁷ which was shown to capture the policies of many ASes.¹ The model assumes each AS executes the following steps (in order) when choosing a single route from the set of routes to a given IP prefix:

Local pref (LP). Prefer “customer routes” (through a neighboring customer) that generate revenue over “peer routes” (through a neighboring peer) that are revenue neutral over “provider routes” (through a neighboring provider) that come at a cost;^e

AS paths (SP). Prefer shorter routes over longer routes; and

Tiebreak (TB). Use other criteria (such as geographic location) to break ties among remaining routes; we lack empirical information about how ASes implement their TB step, so, unless stated otherwise, we model this step as if it were done randomly.

After selecting a single route, an AS announces that route to a subset of its neighbors:

Export policy (Ex). A customer route is exported to all neighbors. Peer routes and provider routes are exported to customers only. This export policy captures ASes’ willingness to transit traffic from one neighbor to another only if at least one neighbor is a paying customer.

LP implies that AS m in Figure 1 prefers the peer route through AS 6939 over the provider route through AS 16795. Moreover, Ex implies that AS 5580 in Figure 1 does not announce to its peer AS 23520 the direct peer route to the destination AS 27781.

Applying our threat model. How can we quantify the “security” provided by each of the four secure routing protocols described earlier? Ideally, we would measure the overall damage caused by the most damaging attack on each protocol. Intuition suggests the most damaging attack is as follows:

Naive attack. Announce to every neighbor the shortest possible path that is valid according to the secure routing protocol. When attacking BGP (respectively, origin validation, topology validation, path validation), the attacker thus announces to each of its neighbors a subprefix hijack (respectively, one-hop hijack, the shortest path that exists in the topology, the shortest path available to the attacker).

The naive attack is not, however, the most damaging. Indeed, in Goldberg et al.,¹⁴ we proved it is NP-hard to find an attacker’s optimal traffic-attraction attack strategy. In fact, it is sometimes more effective to announce a longer path instead of a shorter path. We thus use the naive attack to lower bound the damage that might be done by an attacker; this lower bound suffices to allow us to compare secure routing protocols.

Comparing defenses. We simulate naive attacks for each secure routing protocol on the empirical AS-level topology⁶ for 292,000 randomly chosen (attacker AS, victim AS) pairs. This number of simulations was sufficient for our results to stabilize.

Figure 2. We present the average fraction of safe ASes for BGP, origin, topology, and path validation. The right (yellow) and left (blue) bars represent results when prefix filtering is and is not used in combination with each defense, respectively. The horizontal line represents the percentage of attacks completely eliminated by prefix filtering. Since 85% of ASes in the AS graph are stubs, prefix filtering guarantees that only 15% of non-stub attackers can successfully launch a naive attack on any given victim.

Figure 3. Since Figure 2 presented only averages, we present the full picture in Figure 3. For each defense, we plot the empirical cumulative distribution function for the percentage of safe ASes. The BGP curve is essentially a step function at x = 0, since the attacker that launches a subprefix hijack attracts traffic from 100% of ASes in almost every simulation. Meanwhile, the prefix filtering curve is a step function at x = 0 with y = 15%; for = 15% of simulations where the attacker is not a stub, the attacker launches a subprefix hijack and attracts traffic from 100% of ASes, while for the remaining simulations the attacker is a stub and is thus forced to behave honestly. Likewise, the combination of prefix filtering with origin validation causes the origin validation curve to shift into the bottom 15% of the plot; again, this happens because only the 15% of attackers that are non-stubs can launch a naive attack.

Despite the fact that we used suboptimal attack strategies for the attacker, we can still make several observations:

• With fully deployed prefix filtering, at most 15% of ASes can be deceived when we average over all (attacker, destination) pairs; this follows because 85% of ASes are stubs, and fully deployed prefix filtering eliminates all attacks by stubs;
• Even though the attacker runs a suboptimal attack strategy, and even when we assume path validation (without prefix filtering) is fully deployed, we still find that on average 100 – 93 = 7% of ASes are deceived when path validation is fully deployed; path validation makes just 15 – 7 = 8% more ASes safe, on average, over prefix filtering alone;
• The benefits provided by topology validation and path validation are almost identical, even though path validation is a stronger defense. In Goldberg et al.,¹⁴ we argued this is because path lengths in the Internet are fairly short. The paths the attacker announces with topology validation are only slightly shorter (on average) than those it can announce with path validation; and
• The combination of origin validation with prefix filtering provides benefits comparable to those provided by topology/path validation alone.

Takeaways. Our results suggest that origin/topology/path validation protocols are dealing with only one half of the problem; while they do restrict (a) the path the attacker can choose to announce, they fail to restrict (b) its export policies. Meanwhile, prefix filtering restricts both (a) and (b) but only for stub ASes. We conclude that ISPs should strive to secure the routing system through a combination of prefix filtering and origin/topology/path validation.

Back to Top

Partial Deployment

Thus far we have completely overlooked one crucial fact—that, in practice, it may take decades before a given routing security solution is fully deployed by every AS in the Internet. We expect instead most routing protocols to exist for years in a state of partial deployment, where some ASes deploy the secure protocol but others do not. Indeed, prefix filtering has been partially deployed for several decades,^9,35 and the origin validation with the RPKI has been partially deployed since the start of this decade. We now quantify the “security” of various defenses in partial deployment.

Prefix filtering in partial deployment. Why is prefix filtering not yet fully deployed? Prefix filtering is implemented solely at the discretion of each individual ISP, and there is no way for one AS to validate that another AS has properly implemented prefix filtering. This is in stark contrast to cryptographic protocols^18–20,40 (for path/topology/ origin validation) that allow any AS that deploys the protocol to validate routes announced by other ASes that have deployed the protocol. Moreover, an ISP deploying prefix filtering derives little local benefit for itself. Instead, it altruistically protects the rest of the Internet from attacks. This leads to lopsided incentives for deployment. We therefore analyze prefix filtering in partial deployment, where some providers filter BGP announcements from their stub customers, but others do not.

Attacks by a given stub are thwarted only if all its providers implement prefix filtering. What happens when only the k largest providers filter announcements from their stub customers? It follows that an attack by a stub will fail if and only if that stub’s smallest provider implements prefix filtering. Figure 4 is a pie chart that breaks up stubs by the size of their smallest provider. Figure 4 shows only 85% of the pie, since the other 15% of ASes are non-stubs. We see that if all providers with more than 500 customers were to implement prefix filtering, then attacks by 13.8% of ASes would be eliminated (the lightest gray slice of the pie). This translates to just 14 providers implementing prefix filtering. If all providers with more than 25 customers filter (corresponding to approximately 422 of the 6,092 providers in our topology), then the fraction of ASes that can attack drops by almost half (48.4% = 13.8% + 15.0 % + 19.6%).

Takeaways. We focused on filtering stubs. Our results could hence underestimate the efficacy of prefix filtering, because, in practice,⁹ some providers use even more rigorous prefix filters that filter their entire customer cone. We conclude that prefix filtering, even by just few large ISPs, effectively prevents attacks on BGP.

Topology/path validation in partial deployment. We found little difference between the efficacy of topology validation and path validation. So, from now on, we treat the two as interchangeable. We also found that the combination of prefix filtering with origin/topology/path validation provides the best protection against routing attacks, and that prefix filtering is useful even when partially deployed. This suggests that prefix filtering should be deployed in combination with any cryptographic BGP security protocol. However, deployment of origin validation (with, say, the RPKI²⁰) is already a significant challenge for ISPs,⁷ and any topology or path validation protocol necessarily incorporates one for origin validation as well. Is it really worthwhile for ISPs to deploy topology/path validation on top of origin validation with prefix filtering? To answer, we assume a future scenario where both prefix filtering and origin validation are fully deployed, and the remaining challenge is adoption of topology/path validation. We say an AS is an “adopter” if it deploys topology or path validation (on top of origin validation with prefix filtering); a “non-adopter” AS uses only origin validation with prefix filtering.

Our partial-deployment threat model. Our goal is to quantify the security benefits obtained from a set S of adopters of path/topology validation. As discussed earlier, we use simulations to measure the average percentage of ASes in the topology that are safe (do not select a route through attacker m) when m attacks a victim AS d. We then average over all pairs (m, d) of victim AS d and non-stub attacker m. (The attacker must be a non-stub, since we assume prefix filtering is fully deployed.) But what does it mean for an attacker to launch an attack in our partial-deployment scenario? Since origin validation and prefix filtering are already fully deployed, we need consider only the naive attack that slips past the combination of these protocols—one-hop hijacks by non-stub attackers, as discussed earlier.

Attacking adopters? Naturally, non-adopter ASes (that have not deployed topology/path validation) can fall victim to one-hop hijacks launched by non-stub attackers. But what about adopters? To answer, we must first define the notion of a “secure route.” A secure route is a route for which every AS on the route is an adopter, whereas an insecure route contains at least one non-adopter AS. We use this definition because BGPSEC (respectively, soBGP) fails to achieve path (respectively, topology) validation for a path if at least one AS on the path is a non-adopter. Moreover, even an adopter must sometimes select an insecure route; if an adopter never selected an insecure route, it would lose connectivity to ASes that cannot be reached via secure routes. But can an adopter that does have a secure route to a destination still be affected by a one-hop hijack? Unfortunately, it can be so affected in the following way:

Figure 5. Figure 5 shows how AS 21740 could select a bogus route during a one-hop hijack by AS m of IP prefix 4.0.0.0/8. Under normal conditions, AS 21740 has a secure provider route directly to 4.0.0.0/8. Note that AS 21740 does not have a peer route via AS 174; AS 174’s export policy Ex prevents it from announcing, to AS 21740, its peer route to AS 3356. During the attack, m announces it is directly connected to AS 3356, so AS 21740 sees a bogus insecure four-hop peer route via its peer AS 174. Importantly, AS 21740 has no idea this route is bogus, as it looks like any other route that might be announced with legacy BGP. What should AS 21740 do? It could select the expensive secure provider route, deciding the added security is more important than the added cost of the provider route. On the other hand, it could decide security is not worth the added cost, and thus fall victim to the attack by choosing the cheaper but insecure peer route.

Secure routing policy model. Why would an adopter prefer an insecure route over a secure route? This can happen because economics and performance often outweigh security concerns. During partial deployment, network operators are expected to cautiously incorporate security into routing policies, placing it after the LP and SP steps (see the routing policy model discussed earlier) to avoid disruptions due to changes in the traffic through their networks and revenue lost when expensive secure routes are chosen instead of revenue-generating customer routes. Security may be only the top priority once these disruptions are absent (such as in full deployment) or to protect highly sensitive IP prefixes. Our model thus assumes every adopter will add the following step to its routing policy between the SP and TB steps:

SecP. Prefer a secure path over an insecure path. Placing the SecP step after the LP and SP steps means both economics and performance supercede security. A survey of 100 network operators¹² found that the majority (over 57%) of those that opted to answer this question would rank security this way.

Which ASes should adopt? To quantify the security benefits of topology/path validation in each of these three routing policy models, we must first decide which set of ASes to consider as adopters. In Lychev et al.²³ we showed we can gain valuable insights even by completely sidestepping the question. Our framework is based on a key observation: For each attacker-destination pair (m, d), it is possible to partition ASes into three distinct categories based on their position in the AS graph:

Doomed. Some ASes are doomed to route through the attacker regardless of which ASes are adopters. AS 174 in Figure 5 is doomed, as it always prefers the bogus customer route to the attacker m over a (possibly secure) peer path to 4.0.0.0/8 for every possible choice of set of adopters;

Immune. Other ASes are immune to the attack regardless of which ASes are adopters. AS 23520 in Figure 1 is immune to attacks, as its one-hop customer route to 72.252.8.0/21 is always more attractive than the one-hop hijack path offered by attacker m, regardless of which ASes are adopters; and

Protectable. Only the remaining ASes are protectable, or whether or not they route through the attacker depends on which specific ASes are adopters.

---

Prefix filtering should therefore be deployed in combination with any cryptographic BGP security protocol.

---

We leverage this observation as follows. Recall that we quantify security benefits by computing the average fraction of safe ASes over pairs of attacker m and victim d. We thus get a lower bound on the average fraction of safe ASes for all possible sets of adopters by averaging the fraction of immune ASes over (m, d) pairs. This follows because immune ASes are always safe, regardless of which ASes are adopters. Likewise, we get an upper bound by computing the average fraction of ASes that are not doomed.

The marginal benefits of path/topology validation. We now quantify the marginal benefits of topology/path validation over just origin validation with prefix filtering. We compute the average fraction of immune, protectable, and doomed source ASes, averaged over all possible pairs of destinations and non-stub attackers in the AS graph. We find that 53% of ASes are immune, 30% of ASes are doomed, and only 17% of ASes are protectable. This means the average fraction of safe ASes is already 53%, even if there are no adopters of topology/path validation. Furthermore, on average, only 17% of ASes can additionally be made safe if topology/path validation is deployed in addition to origin validation and prefix filtering. Thus 17% represents the maximum gain of topology/path validation; in realistic partial deployment scenarios, where some ASes are adopters, but others are not, we find this gain is even smaller. The online appendix has more discussion of these results, including an analysis of other routing-policy models.

Takeaways. Given the routing policies that operators favor most during partial deployment, in practice, it will be difficult to realize the security benefits of topology/path validation over those already provided by origin validation and prefix filtering.

Back to Top

Conclusion

The aggregate trends revealed through our quantitative analysis can be used to inform the debate about which BGP security protocols should be deployed in the Internet.^f

First, we find that prefix filtering,⁹ a simple whitelisting technology available in most BGP-speaking routers today, provides a defense comparable to that provided by the cryptographic technologies that have been developed by standards bodies for the past two decades. Prefix filtering should therefore be deployed in combination with any cryptographic BGP security protocol. Prefix filtering is also useful even when it is partially deployed by only a few tens or hundreds of large ASes. Second, we find that partial deployment has been a blind spot in our discussions of routing security. In full deployment, robust cryptographic security guarantees like path validation (such as BGPSEC¹⁹) or topology validation (such as soBGP⁴⁰) unquestionably provide more protection against attacks than weaker guarantees like origin validation (such as the RPKI²⁰). These more robust security guarantees come at the cost of higher overheads. However, when path or topology validation technologies are partially deployed, our results indicate they provide limited security benefits over what is already provided by origin validation and prefix filtering. The routing community should therefore aggressively deploy prefix filtering and origin validation and focus its energy on the non-trivial operational35 and policy issues, especially those related to trust and liability for information in RPKI certificates^7,10 that must be addressed before these technologies can be fully deployed.

Back to Top

Acknowledgments

This article is a new synthesis of earlier research we published in Goldberg et al.14 and Lychev et al.²³ Our related research was supported, in part, by the National Science Foundation grants (1017907, 1350733), Microsoft Research, and Cisco. We thank Alison Kendler, Jeff Lupien, and Paul Oka for outstanding research assistance, as well as our other research collaborators on work that has shaped the discussion here: Kyle Brogle, Danny Cooper, Yossi Gilad, Phillipa Gill, Shai Halevi, Ethan Heilman, Pete Hummon, Aanchal Mal-hotra, Leonid Reyzin, Jennifer Rexford, and Tony Tauber.

Back to Top

Back to Top

Back to Top

Back to Top

Back to top