Daniel R. Simon, Sharad Agarwal, David A. Maltz
Microsoft ResearchAbstract— Defenses against botnet-based distributed denial-of-service (DDoS) attacks must demonstrate that in addition to being technically feasible, they are also economically viable, particularly when compared with the two most widely deployed defenses—simple massive overprovisioning of resources to absorb and handle DDoS trafﬁc, and “scrubbing” of incoming trafﬁc by the victim’s ISP. We argue that the key to cost-effective handling of DDoS attacks on a network such as the Internet is accountability, meaning that the sources of all trafﬁc can be accurately and reliably identiﬁed, and receivers can effectively block trafﬁc to them from any source.
We propose a simple approach to directly providing accountability within a group of ASes. It combines strict ingress ﬁltering on all edge trafﬁc with an AS-based infrastructure that allows hosts to request that trafﬁc to them from speciﬁc other hosts be blocked at the source. We also propose using the previously proposed “evil bit” in IP headers to allow a group of ASes that implement accountability to collectively reduce the impact of DDoS attacks originating outside their portion of the Internet. Finally, we present evidence for the economic competitiveness of our approach, compared with the current default approaches of massive overprovisioning and ISP scrubbing.
With the advent of the underground botnet market, denial-of-service (DoS) attacks have graduated from amateur recreation to for-proﬁt crime. Major content providers and server operators currently spend millions of US dollars each on resources to cope with attacks that cost less than $1000 each to launch . So long as this disparity remains, there will be an incentive to use DoS attacks to extort “protection money” or harm business competitors.
DoS attacks work by diverting the target’s resources away from dealing with legitimate trafﬁc. In particular, a network-layer DoS attack attempts to exhaust the target’s network capacity, ﬂooding it with so many attack packets that legitimate trafﬁc might never even reach the target. To be effective, then, a defense against network-layer DoS must involve the network itself.
The simplest defense against this attack, which is also the current default solution for actual or potential DoS targets, is extreme overprovisioning of bandwidth, enabling the target to absorb DoS trafﬁc while still serving legitimate clients. A related solution is to have the target’s ISP “scrub” the trafﬁc before it reaches the customer, ﬁltering out enough to avoid overwhelming the customer’s bandwidth. These approaches can both be quite costly, given that large botnets can generate stunningly huge volumes of trafﬁc. But they also have a number of attractive features:
•Incremental deployability: individual customers are able to implement them and see beneﬁts, without every user or AS on the Internet having to participate.
•Independence of infrastructure hardware: they require no changes to deployed router hardware throughout the Internet.
•Backward compatibility: traffic among non-deployers does not get the benefit of deployers' resiliency against DoS attacks, but unaffected.
•Economic viability: they can be provided at a cost that DoS targets are willing to pay.
This last property is crucial. A more sophisticated network-based defense against DoS attacks must involve ﬁnding a way to distinguish legitimate trafﬁc and concentrate resources on it. Incorporating such a defense into the network will inevitably impose a cost. If that cost is greater than the cost of the aforementioned current practices, then it is highly unlikely to displace them. Conversely, if it is considerably cheaper than these practices, and can also match their other desirable properties, then it should be able to supplant the current solutions-of-choice in the marketplace.
In this paper, we describe a set of techniques that together satisfy these criteria. Our approach is to create an architecture for accountability, inside which hosts receiving unwanted packets can cause these packets to be ﬁltered at the source. The elements of this architecture include:
Deployment of general and on-demand ingress ﬁltering. We present a practical approach to ingress ﬁltering deployment, thus ensuring that DoS targets can distinguish network-level DoS trafﬁc from legitimate trafﬁc based on its (accurate) source address. We then provide a mechanism for allowing DoS targets to request that trafﬁc sent to them from a particular source be ﬁltered at the source.
Distinguishing trafﬁc by the accountability of the source AS. Crocker  proposed using a bit in the packet header to indicate whether or not the packet originates from “wellmaintained machines.” We extend this idea by using a bit in the packet header to distinguish the trafﬁc of ASes that deploy our accountability architecture from the trafﬁc of those ASes that do not. Thus our system helps create a working ecosystem out of pairwise trust among providers, within which untrusworthy trafﬁc from outside the ecosystem can be recognized and ﬁltered as necessary. (In deference to an “April’s fools” joke RFC by Bellovin , we refer to the bit in the packet header as the “evil-bit.”1)
In addition to presenting our proposal, we will offer a detailed analysis of its economic viability, arguing that its deployment would be signiﬁcantly less costly than long-term continued reliance on the current default alternatives. We believe this is the ﬁrst such analysis of a proposed solution to the DoS problem.
Section II discusses related work and contrasts it with our own. Section III explains and justiﬁes our deﬁnition of the DoS problem and Internet accountability. Section IV describes how accountability can be achieved among a club (not necessarily a clique) of ASes with pairwise trust. Sections V to VI explain how accountability can be used to block DoS trafﬁc, and how to deal with ASes who misbehave within the club of accountable ones. Finally, Section VII examines the economics of accountability, compared with the current state of affairs.
To date, DoS defense has followed one of two approaches. The ﬁrst approach involves applying enough resources to absorb the attack – for example, placing “scrubber boxes” between the attackers’ trafﬁc and the targeted servers and provisioning these scrubbers with sufﬁcient resources and algorithms to separate the attack trafﬁc from the desired trafﬁc. This approach and its costs are explored in more detail in Section VII.
The second approach is to change the Internet’s architecture so that DoS trafﬁc is easily identiﬁed and dealt with. Since our approach is also architectural, we brieﬂy review the three major types of proposed anti-DoS architecture.
Source Identiﬁcation: Source identiﬁcation mechanisms, such as ingress ﬁltering , PKI-based IPSec  and IP Traceback , provide a method by which DoS targets can distinguish attack trafﬁc from other trafﬁc based on its source. However, source identiﬁcation mechanisms, by themselves, provide little beneﬁt until they are deployed universally — since attackers can simply avoid their range of effectiveness — and hence do not justify the cost of partial deployments. Moreover, IP addresses alone are in some cases too transient to be useful source identiﬁers. Finally, the ability to identify DoS trafﬁc once it arrives at its target doesn’t by itself protect the target entirely — for example, its last-hop bandwidth may be overwhelmed regardless.
Pushback: “IP Pushback”  involves in-band signaling among adjacent routers near an attacked end host that speciﬁc links are being overwhelmed, presumably by DoS trafﬁc. Because it does not attempt to identify DoS trafﬁc except in the aggregate, Pushback can only achieve partial ﬁltering of unwanted trafﬁc and risks dropping much wanted trafﬁc as collateral damage. Moreover, Pushback requests require an authentication infrastructure, lest they themselves become a tool for DoS attacks, and they may also require router hardware changes. Finally, reﬂection attacks  (see Section IV-E), in which the attacker rapidly shifts the apparent source of the DoS trafﬁc by bouncing it off any of the innocent hosts in the Internet, can render Pushback ineffective.
Packet-carried Capabilities: In capability-based systems , , , routers generate per-path labels, which are then combined to form a “capability” for that path. Recipients relay the capability to each welcome sender on request, and routers give preferential treatment to packets carrying a valid capability. There are three drawbacks to this architecture. First, the capability request process is itself not protected by the capability mechanism, and is therefore vulnerable to ﬂooding attacks. (In , the statistical identiﬁcation methods of  are used to reduce but not eliminate this problem.) Second, routers throughout the network must have their hardware modiﬁed to maintain expensive per-capability state to prevent capabilities from being overused. Finally, the architecture inherently limits identiﬁcation to network location alone, rather than a more persistent attribute. Hence in some cases (e.g., mobile hosts like laptops), the identiﬁcation will be transient and easy to circumvent.
A ﬁltering architecture not entirely dissimilar to ours has recently been proposed . However, it posits ﬁlters at arbitrary points in the network, and replaces ingress ﬁltering with a randomized path-marking technique (which leaves open the possibility of reﬂection attacks). Filter requests in that architecture are validated using a TCP-style handshake, whose initiation can itself be used as a DoS-attack mechanism. Another, similar, proposed general ﬁltering architecture  piggybacks on the routing infrastructure, and addresses neither authenticity of ﬁltering requests, nor source-address spooﬁng of attack trafﬁc, nor reﬂection attacks.
Crocker  proposed that ISPs decide whether or not their customers run well-managed networks, marking packets from well-managed networks with a DiffServ code point entitling them to preferential treatment over poorly-run networks during times of overload. We use a variant of Crocker’s idea to distinguish packets by originating AS. We then add the ability for trafﬁc within accountable ASes to be blocked on a per-customer basis. Together these enable the AS’ decision regarding whether a particular customer is “well-managed” to be effectively automated, as described in Section V.III. ACCOUNTABILITY AND (D)DOS
The goal of a DoS attack is to impair the target’s functioning by forcing it to spend resources (bandwidth, processing time, or storage space) handling the attacker’s trafﬁc. If the resources needed to handle the attacker’s trafﬁc are a large enough fraction of the target’s total available resources that the remainder is insufﬁcient to handle legitimate trafﬁc, then the attack succeeds.
Once a DoS attack is in progress, the target’s only defense is to attempt to distinguish between DoS trafﬁc and legitimate trafﬁc — typically, based on its source — and reduce the cost of dealing with DoS trafﬁc. The attacker’s resources are measured in the number of hosts the attacker has at its disposal, since that number gives a rough approximation of the resources that the attacker can muster, assuming that the attacker controls a large botnet consisting of compromised end hosts. 2
At the application layer, numerous end host-based strategies may be available to the target for distinguishing DoS sources from others. For example, the target may use a handshake (such as the TCP handshake) to identify hosts by network location, and detect and blacklist hosts that use up abnormally large amounts of the target’s resources. Or the target may attempt to distinguish hosts controlled interactively by humans from those generating trafﬁc automatically , under the assumption that all legitimate trafﬁc to the application will be in the former category. The attacker may in turn attempt to counter each of these defenses, of course—say, by taking advantage of DHCP to change network addresses frequently, or by attempting to simulate interactive human controllers in software.
However, vulnerability to application-layer DoS is ultimately completely application-dependent. For example, if the application is so vulnerable to DoS attacks that a single client can launch a successful DoS attack against it by issuing a legitimate sequence of application-layer requests, then the only feasible defense is to ﬁx the application. Conversely, a sufﬁciently well-designed application may be completely invulnerable to application-layer DoS, in the sense of being capable of handling all application trafﬁc that can possibly ﬁt through its network connection.
On the other hand, even before trafﬁc reaches the application layer, it must ﬁrst pass through the network layer, where its processing consumes resources — especially bandwidth — irrespective of the destination application. If the attacker can cause enough resource consumption at the network layer, then application-level anti-DoS measures will be useless. And in practice, it is common for botnets to ﬂood a target with many times more trafﬁc than even peak loads of legitimate trafﬁc ever reach.
For example, a large website or host may plan for a peak (“ﬂash crowd”) load of 100,000 “hits” per second of presumably legitimate trafﬁc, with each hit requiring roughly 5KB of transmission. This level of trafﬁc can be handled by a 4Gbps connection. However, a botnet of 4,000 nodes, each using a 1Mbps broadband connection, can completely saturate a 4Gbps line. Such botnets are by no means uncommon, and are reputedly available for rental at a rate of 10 cents per bot, or $400 .
Hence, unless the target can distinguish and block DoS trafﬁc in the network layer, DoS defense will require, at the very least, a large outlay for surplus network capacity and per-packet processing or upstream “scrubbing”. (We discuss these costs in detail in Section VII.) Minimizing these network-layer costs is thus a key to effective-yet-economical DoS defense.
In light of the need, noted above, to distinguish and block DoS trafﬁc in the network layer, we deﬁne accountability in a network as having two components:
1) Identiﬁcation: the originators of trafﬁc can be identiﬁed by some persistent attribute—that is, one that is relatively difﬁcult to create, re-create or change. The originator’s IP address itself might be difﬁcult to create or change, for example—or it might be easy to create or change, but reliably associated, at any given moment, with another more permanent attribute (e.g., legal name or credit card number).
2) Defensibility: destinations are able to prevent trafﬁc from a source with a particular address or persistent attribute from affecting their use of the network. Note that defensibility requires, but does not necessarily follow from, identiﬁcation: a network that doesn’t provide identiﬁcation cannot provide defensibility— since the latter requires that trafﬁc be distinguishable by originator—but a network that provides identiﬁcation can still fail to provide defensibility (and hence, full accountability).
The reason why identiﬁcation must be by a persistent attribute should be clear from the deﬁnition of defensibility: the latter is useless if the originators of unwanted trafﬁc are able to escape identiﬁcation merely by changing the attribute that identiﬁes them. For example, if a trafﬁc originator’s IP address is easily and quickly changed—as it can be, in some circumstances—then identifying him or her by IP address alone does little to help stop the unwanted trafﬁc. The originator can, after all, resume sending the trafﬁc using a different IP address.
Conversely, if senders of trafﬁc can be identiﬁed by a persistent attribute, then a fairly simple policy can be formulated regarding acceptable consumption of network-layer resources by a sender. Senders who violate this policy would be deemed to be DoS attackers, and their trafﬁc would be blocked. A DoS attack is thus reduced to the equivalent of a transient “ﬂash crowd”: each attacker can only consume roughly as much of the target’s resources as a “normal” sender would.IV. MAKING THE INTERNET ACCOUNTABLE This section outlines the ﬁve steps involved in creating accountability among a group of ASes, where peering ASes have a contractual basis for trust, shared keys, and agreement on operating procedures, but non-peered ASes in the group need not have any trust or shared keys with each other. This assumption is no stronger than the kind upon which the Internet already relies, where peered ASes must agree on the meaning and use of BGP community strings for interdomain routing to function properly .
A. Step 1: Identifying the customerAccountability is based on the network having the ability to associate the source IP address of a packet with a particular customer. We deﬁne the customer of an AS as an entity to which the AS has issued one or more subnets of IP addresses, agreeing to deliver trafﬁc to those IP addresses to that entity. (We call an AS with customers an ISP.) Some customers, such as DSL customers, may have only a single IP address in their subnet. Others (e.g., small companies) might have many addresses.
To track the association between source IP address and customer, we require ISPs to upgrade their customer relationship management (CRM) systems so that each customer record stores not only the billing information of the customer, but also the IP addresses assigned for use by that customer. The most common methods for connecting to an ISP already create such an association, and the few methods that do not meet it are easily changed to ones that do. For example, companies connecting over a leased-line (e.g., a T1) can be associated when the leased-line is physically connected. DSL customers connect to their ISP through a Broadband Remote Access Server (BRAS) that identiﬁes and authenticates the customer by either the Permanent Virtual Circuit (PVC) or the user name and password of the PPPoE connection over which they connect. Cable companies authenticate their users at the Cable Modem Termination System (CMTS) by the cable loop and modem MAC address over which they connect.
For ISPs that dynamically assign customers IP addresses, either through DHCP or by employing NAT and assigning customers different port numbers behind a single IP address, the ISP will need to retain DHCP and NAT logs for some limited period of time. With these logs, the combination of 4 an IP address, port number(s) and time precisely identiﬁes an individual customer.3
For defensibility to be possible, a host receiving a packet must be able to extract enough information from the packet to uniquely identify the customer that sent the packet. To ensure that the source IP address of a packet can be traced back to the customer that sent it, participating ISPs deploy strict ingress ﬁltering  over all their customers. This means that as a customer connects, the router conﬁguration management system will conﬁgure a packet ﬁlter on the interface/port to which the customer has connected that drops any packet with a source IP address outside the subnet(s) assigned to the customer.
We implement defensibility by creating a system of Filter Request Servers (FRSes) that take a target host’s request that trafﬁc to it from an IP Address be stopped, and relay the request to the FRS in the ISP where the customer using that IP address is connected. Since the customer’s immediate ISP is the only entity that can easily map an IP address to a customer, it is uniquely capable of implementing ﬁltering based on persistent attributes, regardless of any tricks the customer might use to evade it. For example, should the customer change its IP address (say, if it is connecting via a “hotspot” network), the FRS can ensure that ﬁlters requested against the customer are updated with its new address, and move with it.
The technical difﬁculty in implementing near-the-source ﬁltering is in veriﬁably conveying ﬁltering requests from target hosts to source hosts’ ISPs. If it were possible to spoof, forge or replay ﬁlter requests, then the ﬁltering mechanism itself could be used for DoS attacks. Section V describes our design for such a veriﬁable system.
Performing ﬁltering in the ISP actually connected to the source has several additional advantages: downstream ASes are spared the unwanted trafﬁc; multiple paths, requiring multiple ﬁlters, are less likely to exist at the ﬁltering point; and habitual offenders — presumably botnet participants — can be recognized and dealt with.
Cases where the “customer” consists of a large number of hosts may be handled in one of two ways. If the customer — say, a university or enterprise — has a relatively well-managed network, and wants to avoid all-or-nothing ﬁltering, then it can deploy its own FRS, and become the equivalent of an ISP serving its end hosts as if they were individual customers. Thus accountability will be preserved, and a single rogue end host can be ﬁltered without interrupting service to the customer’s other hosts.
Alternatively, the customer — say, a public wireless “hotspot” — may be unwilling to take the trouble to police its hosts. In that case, its best course of action is simply to have its ISP treat it as if it were a separate ISP that has not deployed our Internet accountability system. We explain next how our system deals with trafﬁc from such ISPs.
Not all ISPs will implement Internet accountability, and yet communication between hosts in participating and nonparticipating ISPs must continue as least as well as it does today. Packets carried by a non-participating ISP may have spoofed source addresses and will almost certainly not be impeded by ﬁlter requests, so there must be some mechanism beyond the FRS to deal with them. Our solution is to leverage the existing relationships among ASes. Participating, hence accountable, ASes will conﬁgure their border routers to set the “evil bit” on any packet entering from a non-participating, unaccountable, AS. Packets entering from other participating ASes will have their evil bit left unchanged. With this simple change, customers of an accountable ISP receiving a packet with the evil bit clear will know that the source address of the packet can be tied to a customer, and therefore that trafﬁc from that customer will stop in response to a ﬁlter request. Packets with the evil bit set, on the other hand, are not necessarily malicious, but they may be, and moreover their source addresses may have been forged.
To prevent unaccountable trafﬁc from overwhelming a host, router, or link, accountable ISPs and servers preferentially drop packets with the evil bit set when an overload condition exists. The evil bit and this priority scheme can be implemented using the DiffServ  hardware and conﬁguration commands that already exist in essentially all ISP routers. The evil bit could either be assigned from the six bits in the DiffServ Code Point (DSCP)  or represented by a well-known value of the DSCP.
Otherwise-innocent customers of unaccountable ISPs would be unaffected by this scheme, except when trying to communicate with a host under DDoS attack. In that case, the customer would be completely cut off — its packets having been dropped — whereas a customer with a fully accountable path to the host would likely still be able to get through. While minor, this advantage could serve as an incentive to ISPs to embrace accountability for the sake of their customers.
In a “reﬂection attack” , the attacker, instead of sending packets directly to the target, sends packets to arbitrary hosts that cause those hosts to send packets in turn to the target. In the simplest example, the attacker sends TCP SYN packets to an arbitrary host, with the target’s IP address as the source address. The host then sends its SYNACK packets to the target. The result is that the attacker is subjected to the same volume of trafﬁc, but from a far larger number of sources.
In a universally accountable Internet, ingress ﬁltering would make source address spooﬁng, and hence reﬂection attacks, impossible. On partially accountable networks, however—such as the Internet after partial deployment of accountability—reﬂection attacks provide a means by which attackers in unaccountable parts of the network can “launder” their attack trafﬁc of the evil bit that would normally be attached to it by reﬂecting it off hosts in accountable networks. Targets of a reﬂection attack in an accountable network could request ﬁlters against the reﬂectors, but the attack trafﬁc can easily dodge this ﬁltering by choosing different reﬂectors.
A simple solution to this problem is for hosts to ensure that every response to an incoming packet preserves the “evil bit state” of the packet to which it is responding. For example, every TCP SYN-ACK should bear an evil bit with the same value as its corresponding TCP SYN. Thus, reﬂection attack trafﬁc is rendered effectively no different from direct attack trafﬁc, and can be ﬁltered or rate-limited along with all other unaccountable trafﬁc during an attack. For protocols where the kernel cannot associate outgoing packets with the incoming packets that caused them (e.g., DNS, which uses UDP transport), it will fall to the application to carry over the evil bit state of the incoming request to the outgoing response. This can be achieved by extensions to the socket API so that evil bit state can be queried when a packet is received and set when a packet is sent.
Of course, this solution requires that hosts be upgraded to recognize and preserve evil bit state. Like accountability itself, this upgrade will at best be deployed slowly across Internet hosts, presumably bundled together with other updates and bug ﬁxes to minimize distribution costs. Hence ISPs that deploy accountability will have to deal with hosts that haven’t yet been upgraded. As an interim measure, ISPs can set the evil bit on all trafﬁc (including, obviously, reﬂected trafﬁc) originating at hosts that haven’t yet been upgraded. Fortunately, testing whether a host has upgraded is easy: for each protocol vulnerable to reﬂection attacks (TCP, ICMP, and so on), and each port number, the ISP sends an initial packet to the host being tested, with its evil bit set. The host “passes” the test if and only if the response to these probes always has the evil bit set. Hosts running unpatched kernels or applications that are used as reﬂectors may also end up with many ﬁlters being requested against them, which will also result in the host having its trafﬁc marked with the evil bit by the ISP. This is fair, as unpatched hosts used as reﬂectors are a source of DoS trafﬁc, even though an indirect one.
While the idea of updating end-host network stacks may seem onerous, our observation is that reﬂection attacks represent a fundamental problem. By their nature, reﬂectors allow an attacker to cause an innocent host to send trafﬁc to a target of the attacker’s choosing. This means that any approach to controlling DoS will involve either (1) not responding to any trafﬁc with an untrustworthy source address, or (2) implementing inheritance of some property of the incoming packet in the response packet. But the ﬁrst option would prevent hosts using one accountability scheme from communicating at all with hosts under a different accountability scheme, and hence destroys backward compatibility, leaving option 2 as the only acceptable one.
The next section describes the FRS in more detail, examines attacks on the system, and explains how untrustworthy ASes are discovered and evicted.V. FILTER PROPAGATION Our solution requires a complete system for relaying ﬁlter requests among accountable ASes, to effect defensibility. In this section, we give a detailed design of such a system.
The system must have the following properties:
Note that the ﬁrst goal is quite limited, since it says nothing about trafﬁc passing through non-participating ASes.
B. The System
1) Filter Request Servers: Every accountable AS and ISP must run a Filter Request Server (FRS). Customers request a ﬁlter by sending their own ISP’s FRS a ﬁlter request consisting of the IP address whose trafﬁc should be blocked, the time the offending trafﬁc was received, the source/destination port numbers (if any), and for how long the trafﬁc should be blocked. The time and port numbers may be needed by the FRS at the trafﬁc’s source to match the trafﬁc to a customer if DHCP or NAT are being used. Since the ISP running the FRS is accountable, it will already be enforcing ingress ﬁltering on its customers, and the FRS can easily identify the customer making the request.
2) Filter Request Processing: First, the FRS determines if that customer is entitled to issue a ﬁlter request. By default, customers should have very limited ability to do so, since they should have little need. The ISP may forbid most of its customers to issue ﬁlter requests at all, or it may allow them to issue requests at a very low rate, in response to harassment from individual users.
However, on request, and presumably upon paying a mild premium, a customer—typically, a server operator— would be allowed to issue ﬁlter requests on a large (that is, essentially unlimited) scale. Customers of this type would also be allowed, if they desire, to issue ﬁlter requests from a single IP address on behalf of a block of IP addresses belonging to the same customer—perhaps only from the particular designated IP address of a relatively secure host (to minimize the threat of a single host compromise resulting in a ﬂood of requests).
3) Filter Request Forwarding: When two peered ASes agree to implement accountability with each other, they tell each other the IP addresses of their FRSes.
Upon authorizing an incoming request, the FRS then determines, based on the IP address speciﬁed as the trafﬁc source, a “next hop” AS to which to forward the request. By running an iBGP session with any local router, the FRS can obtain this “next hop AS” information. The FRS then forwards the request to the next-hop AS’s FRS, appending the correct source address from which the sending FRS received the request. With the source address veriﬁcation provided by ingress ﬁltering, the next-hop FRS can verify that the request has indeed been forwarded from a neighboring AS’s FRS. (For extra security, the FRSs can also share an IPSec SA. The overhead will be small, given the small number of neighboring ASes for a given AS, but ought not to be strictly necessary.)
The request builds up a chain of addresses as it travels, starting with the originator of the request, and continuing with a sequence of AS’ FRS IP addresses. When the request reaches the FRS of the ISP that owns the IP address in question, the ISP acknowledges the request, by passing the acknowledgment back along the same chain of FRSs as the one the request took. This backtracking mechanism prevents asymmetric routes from causing acknowledgments to pass through non-participating ASes.
The FRS in the ISP of the offending trafﬁc source uses the IP address, time and port number listed in the request to determine which customer’s trafﬁc needs to be ﬁltered, and then translates that customer identity into a ﬁlter location and source/destination IP addresses to ﬁlter. The FRS then contacts the AS’s router conﬁguration system, requesting the application of the appropriate ﬁlter at the appropriate location. As with ﬁlter requests themselves, the instructions from the local FRS can be authenticated based on their originating IP address—assumed reliable, given full source address veriﬁcation—or based on an IPSec SA, for extra security.
Filter requests may include an expiration time—say, a day, or a week, or a month—to allow for the possibility of the target “reforming” (for example, repairing a compromised end host that had been incorporated into a botnet). The requested duration of a ﬁlter would likely be chosen by the requesting customer based on the frequency and volume of unwanted trafﬁc emanating from the source being ﬁltered.
ISPs may also take additional measures beyond application of the ﬁlter. For example, if a particular customer repeatedly triggers numerous ﬁlters against itself, thus imposing extra costs on the ISP, then the ISP may respond by imposing extra limitations on the customer. These might include rate-limiting of trafﬁc; imposing extra charges; or, more positively, offering to sell root-kit scrubbing or computer maintenance services to the customer. The effort required from an ISP to respond to ﬁlters against a customer is bounded, because if a customer has more ﬁlters requested against than the ISP has resources to handle (e.g., due to router limitations), then ISP can set the “evil” bit on all packets emanating from the customer.
Consider the example shown in Figure 1. ASes 1, 2, 3 and 4 are all accountable and are interconnected as shown. AS1 is a large DSL provider. Its customers connect to the network through a DSLAM (DSL Access Multiplier). The DSLAM connects to the rest of the network via router R1. R2 and R3 provide connectivity to other ASes. Since this AS is accountable, it runs an FRS, which communicates with the local CRM (Customer Relationship Management) system to access customer information, and has the credentials to implement ﬁlters at routers and DSLAMs. AS2 and AS3 are large transit providers and do not have any end-hosts. For accountability, they need to only house FRSs. AS4 is a large web-hosting provider and has a server W1 which is under attack. W1 sends a ﬁlter request to FRS-4. FRS-4 has an iBGP peering session with R6 and learns about BGP routes to the offending IP address, which resides in AS1. It decides to forward the ﬁlter request to AS2. It looks up AS2 in its list of FRS’s that it knows about and sends the request to FRS-2. FRS-2 similarly then forwards the request to FRS-1. FRS-1 looks up the IP address in the local network routing protocol, such as OSPF or IS-IS, and ﬁnds out that the DSLAM is assigned that address. It looks up the relevant records in the CRM and ﬁnds that the offending address is currently used by a customer with a DSL subscription, which happens to be the home with E1 and E2. Since the CRM only knows about a single account and single IP address on that DSLAM port, it cannot distinguish between E1 and E2, the FRS implements a ﬁlter at the DSLAM for that port. The ﬁlter blocks any trafﬁc from E1 or E2 to W2. If the home with E1 and E2 had an FRS that it had registered with FRS-1, then FRS-1 would have forwarded the request to this home FRS, which would then have to determine which of E1 and E2 sent the offending trafﬁc, perhaps by looking at the source port number and timestamp in the ﬁlter request.
Figure 1: Example of filter request propagation.
Note that while FRS-4 had forwarded the request to FRS-2, it could have instead picked FRS-3. The choice of path does not matter as long as a chain of trusted FRSs is traversed to FRS-1. If AS1 was not an accountable network, trafﬁc from it would most likely be marked as evil, and then in that case W1 would not generate a ﬁlter request to FRS-4 instead it would consider requesting rate limiting of evil bit trafﬁc. If AS1 did not have an FRS and AS2 and AS3 nonetheless allowed trafﬁc from AS1 to not be marked as evil, it would be their responsibility to implement the ﬁlter at R4 and R5.
1) Spooﬁng Attacks: As long as participating ISPs perform source address veriﬁcation, customers of participating ISPs cannot launch spooﬁng attacks. Non-participating ISPs can, of course, be the source of arbitrarily large amounts of spoofed trafﬁc. But trafﬁc from non-participating ISPs will be marked with the evil bit, and, as mentioned above, we assume that such trafﬁc will necessarily require massive, relatively indiscriminate ﬁltering in the event of a DoS attack. (e.g., a lower queuing priority or collective rate-limiting). The end result is that trafﬁc from nonparticipating ISPs to servers in participating ISPs will see performance roughly equivalent to today, where DoS trafﬁc can swamp out desired trafﬁc. Trafﬁc between hosts in participating ISPs should see DoS-free performance, as servers can protect themselves from DoS.
2) DoS Attacks: The ﬁlter request system must itself be robust to DoS attacks of any kind, otherwise it will suffer from the very problem it is trying to solve. The following are the three major classes of DoS Attack and how the FRS deals with them.
Overloading the FRS with requests, to prevent it from accepting requests from customers under DoS attack. The FRS itself is capable of causing routers to block trafﬁc, and can therefore block attack trafﬁc at the source on detection. This applies both to attackers from within the same ISP, who can be ﬁltered directly, and those whose requests come via other ISPs’ FRSs.
Requesting so many ﬁlters for fellow DoS attackers that the ISP refuses to apply more ﬁlters to them, allowing them to launch DoS attacks with impunity. All routers have limits to the number of individual packet ﬁlters they can apply to trafﬁc ﬂowing through them, so at some point more ﬁlters may be requested against a customer’s addresses than the router can implement. Rather than allowing such a user to send trafﬁc with impunity, the ISP would remove all the ﬁlters on the customer and instead set the evil bit on all the customer’s trafﬁc. This allows the ISP to control its resource outlays and upholds the principle of accountability at the same time.
Requesting numerous ﬁlters for innocent customers, with the goal of causing them to be identiﬁed as habitual DoS attackers themselves. The application of the ﬁlters themselves is harmless, since the target was presumably uninterested in sending trafﬁc to the attacker anyway. The goal of such a “framing attack” would be to cause unwarranted ISP action against the targeted customer. However, an ISP can easily check to see if a customer is being framed by examining the packets sent by the customer before taking action -if there are no packets from the customer to the ﬁlter requester, there is a framing attack underway.
A compromised server cutting off trafﬁc to itself. If a server itself is compromised and requests long-lived ﬁlters for sources whose trafﬁc is actually desired, there is a possibility of blocking wanted trafﬁc even after the compromise has been repaired. However, the server’s local FRS will have copies of every ﬁlter request it sent while compromised, and these ﬁlters can be recalled. Part of the process of recovery from the compromise would be revocation of those ﬁlters. Issuing and processing revocations of ﬁlters would be roughly identical to the issuing and processing of the ﬁlters themselves.
Detecting an ISP that fails to apply on-demand ﬁltering is easy, as other ISPs’ customers will immediately notice that their ﬁlter requests are being ignored, and can raise the alarm that that ISP is not honoring its agreements. The more difﬁcult case is that of an ISP who fails to honor its commitment to apply proper ingress ﬁltering to its customers. In that case, its customers may launch DDoS attacks that do not implicate the ISP—indeed, they may implicate other ISPs.
Cases of ISP malfeasance at ingress-ﬁltering are likely to be rare (as malicious BGP misconﬁguration is rare), but require out-of-band methods to resolve. For example, if an ISP receives complaints that another ISP is failing to ﬁlter attack trafﬁc (claiming to be) from its customers, it can sample the trafﬁc arriving from peer ASes, ﬁnd the ASes from which the attack trafﬁc is arriving, and demand that those ASes deal with the problem—either by properly ﬁltering customers, or by enforcing contractual terms to ensure that upstream ASes do likewise. Those ASes in turn can follow the same procedure, and eventually an AS that fulﬁlls its obligations will confront one that doesn’t. The former, having not been satisﬁed with the latter’s effort to stop the ﬂow of DoS trafﬁc, will then simply evict the AS from the accountability club by setting the evil bit on all trafﬁc from the evicted ISP.
This approach is very different from statistical approaches to DDoS defense, such as IP traceback. In IP traceback, every DoS attacker has to be identiﬁed individually, by IP address, for each target in turn, so that its trafﬁc can be ignored. In our approach, ASes only need identify sources at the granularity of the offending AS, and only need to identify one consistently unﬁltered attack trafﬁc source, once, to implicate an AS. Finally, beyond simply blocking trafﬁc from a particular attacker, the community of network operators has recourse — an exposed AS can be designated as unaccountable and its trafﬁc treated accordingly. Moreover, such identiﬁcation may include penalties speciﬁed in the ISP’s peering agreements. If these penalties are severe enough, then we can expect that their deterrent effect will make the need for this kind of sampling-and-tracking procedure quite rare.
In this section, we assess the economic viability of our proposal, by comparing the cost of its deployment with the costs currently incurred by DoS victims.
A conventional tactic that some enterprise networks use for DoS defense is the combination of “scrubbing” devices with heavy over-provisioning of WAN connectivity. A scrubber is a network device that is typically placed at the edge of the enterprise network, facing the WAN connection. The scrubber inspects all inbound trafﬁc and ﬁlters out “malicious” packets and connections. However, this can only protect connectivity within the enterprise network – since the WAN connection can still be ﬂooded, the enterprise network. Thus typically the WAN connection it is heavily over-provisioned to match the expected attack volume, and enough scrubbers are deployed to handle the size of the connection. An example of a scrubber device is the Cisco Guard XT 5650, which can scrub trafﬁc at a line rate of 1Gbps and retails for roughly $68,000 .
Instead of keeping the scrubber device continually in the path between the local network and the WAN, and thus paying a latency penalty, it can be coupled with a Cisco XT 5600 Trafﬁc Anomaly Detector, which will detect a potential DoS situation and then shunt trafﬁc to the 5650. A Cisco XT 5600 retails for about $45,000 . The administrators of an enterprise network would estimate the volume of the largest attack that they wish to defend against in multiples of OC-12s, and then lease that much connectivity from multiple ISPs. They would then couple each OC-12 (622 Mbps) with one Cisco XT 5650 and possibly an XT 5600. An OC-12 from a “tier-1” ISP will cost about $30,000 per month , . The initial setup cost for a leased line is about $6,000 . Thus for an organization wishing to defend itself against an attack stream of X Mbps for Y years, the total cost will be about $ ((30000 * 12) Y + (45000 + 68000 + 6000)) X / 622 which is about $(580 X Y + 190 X).
An alternative strategy available to enterprise networks today is to take advantage of scrubbing services provided by large ISPs such as MCI  and Saavis . The MCI service costs between $2,000 per month for a T-3 line (45Mbps) and $69,000 per month for an OC-48 line (2.448Gbps). This is in addition to the cost of raw IP connectivity, which we previously quoted as $30,000 for an OC-12 (622Mbps). Setup fees range from $200 to $2,500. Thus for an organization wishing to defend itself against an attack stream of X Mbps for Y years, the cost will be about $12 X Y * 69000 / 2448 which is about $(338 X Y), plus the setup fee.
Estimating the cost in dollars that an ISP would have to pay to upgrade its network to support our system is not easy. The bulk of the expense will not be the new equipment and software that must be purchased — an FRS is, after all, no more complicated than a load-balanced cluster of machines running a database application. Rather, the majority of the cost will come from integrating the FRS into the ISP’s existing systems. New ﬁelds will need to be added to the databases in the Customer Relationship Management (CRM) systems. New software interfaces to the router conﬁguration management systems will need to be coded. Customer service personnel will have to be trained on new procedures and customer documentation updated. Activities like these are carried out continuously at major ISPs, using internal staff and external contract consultants, but ISPs rarely disclose the resulting costs.
However, we can bound the costs of implementing accountability by analogy to two network upgrades for which there is data in the public record. In 2002, cellular carriers in the US were required by the Federal Communications Commission (FCC) to upgrade their networks to support Number Block Pooling and Local Number Portability (a.k.a. wireless number portability). Number Block Pooling increases the granularity of phone number allocations, roughly analogous to Classless Interdomain Routing (CIDR). Local Number Portability allows customers to keep their phone numbers, even if they change carriers. Each of these upgrades required changes far more extensive than would be necessary to implement accountability.
Sprint Wireless operates a network supporting 13M subscribers, and estimated the cost of its Number Block Pooling upgrade at $59M. Implementing Local Number Portability required changes to over 70 systems inside the carrier, from their routing architecture to their external websites, and was estimated to cost $36M . Leap Wireless, which provides service in dozens of cities across the US, estimated the costs of number pooling at $6M, and local number portability at an additional $2M . They have a subscriber base of 1.62M as of September 2005 . The cost estimates by both Sprint and Leap include all aspects of the network upgrades, including cost to update CRM software, cost for upgrading network elements, costs for new documentation and training for both network and customer support personnel, etc..4
According to the US Congressional Budget Ofﬁce, the 30 OECD nations have 55.8M broadband subscriptions , and about 17M websites. Thus, if we use the cost of Number Block Pooling as representative of the cost of implementing accountability for all the broadband connections in the OECD nations, we arrive at about $188M to $231M. If we instead rely on Local Number Portability, we arrive at $63M to $141M.
An additional cost occurs in upgrading end host stacks to respond to evil bit trafﬁc with the evil bit set in their replies. Since our accountability system allows incremental deployment, this update to end host OSes and reﬂection-susceptible applications can also occur incrementally. This update can be included with any more critical updates and does not require special user attention or intervention, thus minimizing the cost for the user.
Recall that we’ve estimated the rough cost of conventional protection for an organization against an X Mbps DDoS attack for Y years to be somewhere between $(338 XY) and $(580 XY + 191 X). We assume that organizations acquiring this protection will expect to be protected against a DDoS attack consisting of up to 50,000 broadband hosts, each with a minimum of 128Kbps upstream bandwidth— that is, an attack stream of up to 6.4Gbps. If we consider DoS defense over 3 years, the cost of conventional protection for 1 organization is roughly $6.5M to $12M. We estimate the cost for implementing accountability to be in the range $63M to $231M. Hence if there are at least 36 networked organizations that are afraid of being attacked by a large botnet army, it will be cheaper for the entire Internet to implement accountability.
While the ISPs willing to spend money to defend themselves against DoS are different from the ISPs that tend to serve compromised end hosts, we believe that competitive pressure among ISPs that serve large organizational customers will eventually drive them towards the less expensive option of subsidizing the widespread implementation of accountability, in order to allow them to undercut competitors offering the more expensive alternatives.
This paper proposes a simple approach to blocking DoS attacks, based on the concept of accountability. It allows hosts to stop receiving undesired trafﬁc, and ISPs to identify habitual offenders within their network. Our system employs an “evil bit” label on packets, to allow a subset of the Internet to implement accountability and still obtain some relief from DoS. It thereby solves the problem of incremental deployment that ingress ﬁltering and other DoS prevention techniques have faced in the past.
Our system does require some changes to ISP operations, and thus introduces costs, but since the current Internet is prone to DoS attacks, any solution will require change, and will therefore have a cost component to it. We have made rough estimates of the cost of deploying accountability, and compared it to the amount that organizations are willing to spend today to defend themselves against attacks. Our analysis shows that if there exist today at least a few organizations (say, 36 large corporations) that wish to defend themselves against large botnet attacks for a few years, then implementing our system for the entire Internet will cost less than the currently available alternatives. We believe that far more than 36 such corporations exist on the Internet today.
 T. Anderson, T. Roscoe, and D. Wetherall. Preventing Internet denial-of-service with capabilities. In Proc. ACM HotNets-II, November 2003.
 K. Argyraki and D. Cheriton. Active internet trafﬁc ﬁltering: Real-time response to denial-of-service attacks. In USENIX, 2005.
 H. Ballani, Y. Chawathe, S. Ratnasamy, T. Roscoe, and S. Shenker. Off by default! In Proc. ACM HotNets-IV, November 2005.
 S. Bellovin. The security ﬂag in the IPv4 header. RFC 3514, 2003.
 J. Binkley and S. Singh. An algorithm for anomaly-based botnet detection. In Proc. Usenix Workshop on Steps to Reducing Unwanted Trafﬁc on the Internet, 2006.
 S. Blake, D. Black, M. Carlson, E. Davies, and Z. W. W. Weiss. An architecture for differentiated services. RFC 2475, 1998.
 CNET Shopper prices for Cisco Guard XT 5650. https://shopper.cnet.com/Cisco_Guard_XT_5650_security_appliance/4014-3243 9-31208569.html.
 CNET Shopper prices for Cisco Trafﬁc Anomaly Detector XT 5600. https://shopper.cnet.com/Cisco_Traffic_Anomaly_Detector_XT_5600_security_appliance/4014-3243_9-31208808.html
 E. Cooke, F. Jahanian, and D. McPherson. The zombie roundup: Understanding, detecting, and disrupting botnets. In Proc. Usenix Workshop on Steps to Reducing Unwanted Trafﬁc on the Internet, 2005.
 S. D. Crocker. Protecting the Internet from distributed denial-of-service attacks: A proposal. Proceedings of the IEEE, 92(9):1375– 1381, September 2004.
 Reply comments of Leap Wireless. WT Docket No. 01-184, October 2001.
 Reply Comments of Sprint PCS. WT Docket No. 01184, October 2001. https://gullfoss2.fcc.gov/prod/ecfs/retrieve.cgi?native_or_pdf=pdf&id_document=6512767909
 P. Ferguson and D. Senie. Network ingress ﬁltering: Defeating denial of service attacks that employ IP source address spooﬁng. Internet RFC 2827, 2000.
 F. Freiling, T. Holz, and G. Wicherski. Botnet tracking: Exploring a root-cause methodology to prevent distributed denial-of-service attacks. In Computer Security -ESORICS 2005: 10th European Symposium on Research in Computer Security, 2005.
 C. Garretson. Savvis launches security service. Network World, December 2005. https://www.networkworld.com/news/2005/121905-savvis.html.
 A. Helland. The economics of large-scale data transfer: the beneﬁts of ﬁbre channel and SONET for high-performance, cost-effective data transport through WAN -storage networking. Computer Technology Review, December 2002.
 J. Ioannidis and S. M. Bellovin. Implementing pushback: Router-based defense against DDoS attacks. In Proc. ISOC Symp. on Network and Distributed Systems Security, 2002.
 S. Kandula, D. Katabi, M. Jacob, and A. Burger. Botz-4-sale: Surviving DDoS attacks that mimic ﬂash crowds. In NSDI, 2005.
 S. Kent and R. Atkinson. Security architecture for the internet protocol. Internet RFC 2401, 1998.
 J. Layden. Phatbot arrest throws open trade in zombie PCs. The Register, May 2004. https://www.theregister.co.uk/2004/05/12/phatbot_zombie_trade/
 Leap investor relations website. https://phx.corporate-ir.net/phoenix.zhtml?c=95536&p=irol-irhome.
 R. A. Mortimer. Investment and cooperation among internet backbone ﬁrms. UC Berkeley Economics, 2001. PhD Dissertation.
 K. Nichols, S. Blake, F. Baker, and D. Black. Deﬁnition of the differentiated services ﬁeld (DS ﬁeld) in the IPv4 and IPv6 headers. RFC 2474, 1998.
 U. C. B. Ofﬁce. Economic and Budget Issue Brief, February 2004. https://www.cbo.gov/showdoc.cfm?index=5082&sequence=0.
 D. Pappalardo. MCI offers network protection service. Network World, June 2005. https://www.networkworld.com/news/2005/060605-mci-security.html.
 V. Paxson. An analysis of using reﬂectors for distributed denial-of-service attacks. ACM CCR, 31(3), July 2001.
 A. Ramachandran, N. Feamster, and D. Dagon. Revealing botnet membership using dnsbl counter-intelligence. In Proc. Usenix Workshop on Steps to Reducing Unwanted Trafﬁc on the Internet, 2006.
 S. Savage, D. Wetherall, A. Karlin, and T. Anderson. Practical network support for IP traceback. In ACM SIGCOMM, August 2000.
 J. Stewart. BGP4: Inter-Domain Routing in the Internet. Addison-Wesley, 1998.
 T1-shopper.com prices for Verio connectivity. https://www.t1shopper.com/carriers/verio/.
 R. Vogt, J. Aycock, and M. Jacobson. Army of botnets. In Proc. ISOC Symp. on Network and Distributed Systems Security, 2007.
 A. Yaar, A. Perrig, and D. Song. Pi: A path identiﬁcation mechanism to defend against DDoS attacks. In Proc. IEEE Symposium on Security and Privacy, May 2003.
 A. Yaar, A. Perrig, and D. Song. SIFF: a stateless internet ﬂow ﬁlter to mitigate DDoS ﬂooding attacks. In Proc. IEEE Symposium on Security and Privacy, May 2004.
 X. Yang, D. Wetherall, and T. Anderson. A DoS-limiting network architecture. In ACM SIGCOMM, August 2005.
1Steve Bellovin proposed the addition of an “evil bit” to the IP packet header: all applications and hosts with malicious intent would be required to set this bit to 1, and all routers would preferentially drop evil trafﬁc.
2It is a common misconception that unwanted trafﬁc on the Internet is purely a product of end host insecurity. However, that is not the case. Suppose, for instance, that a solution to the insecure end host problem were suddenly installed on every host connected to the Internet. One property of that solution, of course, would be that the legitimate users of that host could then run any software they pleased — say, the latest version of SETI@home  — completely safely, without any risk of compromising their own data or other software on the host. Likewise, a simple “DDoS@home” application could (and no doubt soon would) be distributed, which, in return for performing some pleasing service to the user — showing attractive images of some sort, for instance — would borrow some of the end host’s spare CPU cycles and bandwidth, for use in the distributor’s “virtual botnet”. The user would be completely unharmed—protected by bulletproof end host security — and may or may not even know, or care, how his or her (cost-free) spare cycles and bandwidth are being used. The distributor’s botnet would be as large and effective as before, and ready to continue its DDoS attacks. Clearly, then, DDoS attacks do not depend solely on the ubiquitous availability of insecure end hosts.
3We do assume that customers cannot obtain a new address via DHCP, or reuse a NAT port number, in periods shorter than the maximum round trip time plus network time synchronization. However, this assumption is typically valid, as network time sync under 100 ms is easy to obtain and round trip times more than a few seconds are rare. In any case the period of reuse is under the ISP’s control and not the customer’s, so a participating ISP can choose appropriate values.
4Also noteworthy is that Sprint’s ﬁlings argued against requiring carriers to implement these network upgrades, while Leap’s ﬁlings argued in favor. This suggests that these estimates do bracket the true costs.