A DoS Limiting Network Architecture


Denial-of-Service (DoS) flooding attacks have become an increasing threat to the reliability of the Internet. These attacks are capable of knocking any user, site, and server right off the Internet. The goal of this project is to design a network architecture that is resistant to DoS flooding attacks. Currently we are exploring two directions: one is capabilities combined with hierarchical fair queuing, and the other is packet filtering based on authentic source address.

Traffic Validation Architecture (TVA)

TVA is built on capabilities, which are short-term authorizations that senders obtain from receivers and stamp on their packets. If a receiver does not want traffic from a sender, it can simply refuse to grant capabilities to the sender, and the traffic will have lower priority. This allows the receiver to control the traffic it receives and prevent attackers from congesting links by flooding.

With TVA, a typical session between a sender X and a receiver Y is:

  1. X sends a request to Y, asking for capabilities.
  2. If Y does not want traffic from X, it will ignore the request. Now assuming Y would like to receive traffic from X, it sends capabilities back to X.
  3. X sends traffic to Y, with capabilities embedded in each packet.

All TVA-related messages are piggy-backed into normal traffic between senders and receivers. For instance, in the session described above, if X and Y use TCP to communicate, the request message would be embedded into the packet carrying TCP SYN from X to Y, and the capabilities-granting message would be embedded into the packet carrying TCP SYN/ACK from Y to X.

There are several challenges in designing TVA:

We made a prototype of TVA on Linux and benchmarked it. With a commodity PC we can achieve the forward speed of about 660k packet-per-second for small packets with capabilities (no caching on routers). We also made a prototype of TVA in ns2 simulator and compared with several other DoS prevention schemes. We out-performed others in all the simulations.

Source Authentication with Packet Passport

Packet filtering is another tool for mitigating DoS flooding attacks: when a receiver does not want to receive traffic from a sender, it can request to install filters to block the traffic. However, existing packet filtering systems are rendered ineffective by source address spoofing: in the current Internet, it is easy for attackers to spoof source IP addresses to evade attack detection and packet filtering. Source address spoofing also enables attackers to launch reflector attacks, in which the attackers can hide behind innocent sources and the attack traffic can be significantly magnified.

Our solution to authenticating source addresses is "Packet Passport". A Packet Passport is a piece of authentication information embedded into an IP packet that authenticates the source IP address. Packet Passports cannot be spoofed, and they can be verified by routers on the path at packet forwarding time. A naive way to implement Packet Passports is to use digital signatures: the sender signs each packet with its private key, and routers and the receiver verify the digital signature with the source's public key. This approach is infeasible with current hardware technology, because digital signature generation and verification are still too slow to support line-speed packet forwarding. To make Packet Passport generation and verification efficient, we use Message Authentication Codes (MACs) instead of digital signatures. MAC computation is light-weighted, and there are already hardware implementations for some MAC schemes.
Figure 1: Packet Passport Overview

Figure 1 provides an overview of our Packet Passport System. Some fields of the Packet Passport are omitted here for simplicity. Before normal data packets are sent, every two domains have established a key shared between them using Diffie-Hellman key exchange protocol. For instance, AS1 and AS2 share a key K(AS1, AS2). These pair-wise keys are used to generate and verify Packet Passports. The key exchange messages are piggy-backed in BGP prefix announcements.

Now suppose host A in AS1 sends a packet to host B in AS4. The border router R2 inserts into the packet a Passport with three MACs, each computed using the key K(AS1,ASj), j = 2, 3, 4. When the packet arrives at AS2, the border router R3 uses K(AS1,AS2) to verify the first MAC to make sure that the packet comes from AS1. Similarly, R5 and R7 each uses the corresponding key shared with AS1 to verify the corresponding MAC.

One key feature of our design is that it requires minimum trust between domains. No transitive trust is required: if a domain is malicious or has its routers compromised, it cannot spoof Packet Passports of other domains, because it does not know the keys shared between other pairs of domains. This significantly limits the damage compromised routers or malicious domains can cause. It also gives domains the incentives to maintain good behavior and avoid having routers compromised. Due to this requirement for minimum trust, our design provides immediate benefits for early adopters, and therefore is much more adoptable than other source spoofing prevention systems such as ingress filtering, which requires every domain drop packets with spoofed source IP addresses. With ingress filtering, each domain has to trust that all other domains have eliminated source IP address spoofing. If a single domain does not do ingress filtering, either because it has not deployed or because it has compromised routers, attackers in it can spoof anyone's source IP address, and other domains cannot treat source IP addresses of the packets they receive as reliable source identifiers.

We have implemented a prototype of the Packet Passport System on Linux. The benchmark result shows that on a commodity PC we can stamp Packet Passports and forward the packets at the speed of up to 600k packets per second. We also have run emulations on Deterlab to demonstrate that a Packet Passport System can mitigate reflector attacks even without separate DoS defense systems. Moreover, we have also modeled the adoptability of source spoofing prevention systems to show that Packet Passport System provides stronger security and deployment incentives than alternatives such as ingress filtering.

Packet Filtering with StopIt

Even with source IP addresses authenticated by Packet Passport, it is not a trivial task to design a secure and effective packet filtering system. There are a number of challenges:

Our packet filtering system, StopIt, fully addresses these challenges. StopIt employs a novel closed-control and open-service architecture to combat various strategic attacks at the defense system itself, and at the same time enable any receiver to block the undesired traffic it receives. It never aggregates the source address of a filter, avoiding collateral damage to innocent sources. It uses per-source-AS fair queuing to limit the damage of attack traffic that is not stopped by filters. This source-based fair queuing also provides strong incentives for deployment, because if a source domain does not deploy StopIt to stop the attack traffic originating from itself, such attack traffic would only harm the domain's legitimate traffic on bottleneck links.
Figure 2: StopIt Overview

Figure 2 provides an overview of the StopIt system. Each AS has a StopIt server that handles filter requests from its access routers and other ASes. In order to authenticate and prioritize inter-domain filter requests, each AS has to know the source address of every StopIt server, and each pair of ASes have to share a secret key. To achieve these two goals, the StopIt server addresses are published in BGP, and the AS pairwise keys are established using Diffie-Hellman key exchange protocol embedded in BGP (if Packet Passport System is used to authenticate source addresses, its AS pairwise keys can be reused by StopIt). The steps to install a filter are as follows:

  1. A destination host Hd that wishes to block an attack flow sends a host-router StopIt request to its access router Rd. This request includes the attack flow's source and destination IP addresses: (Hs, Hd) and a block period Tb.
  2. The access router Rd verifies this request to confirm that the source Hs is attacking the destination Hd and sends a router-server request to the AS's StopIt server Sd. The verification involves sending end-to-end StopIt requests to Hs.
  3. The StopIt server Sd in the destination Hd's AS forwards an inter-domain StopIt request to the StopIt server Ss in the source Hs's AS to block the flow (Hs, Hd) for Tb seconds.
  4. The source StopIt server Ss locates the access router Rs of the attacking source Hs, and sends a server-router request to the access router. A StopIt server ignores inter-domain StopIt requests that block itself to prevent deadlocks.
  5. In the last step, the access router Rs verifies the StopIt request, installs a filter, and sends a router-host StopIt request to the attacking source Hs. After receiving this request, a compliant host Hs installs a local filter to stop sending to Hd. If Hs does not stop, it will be punished by Rs.

Rd has to install temporary filters to confirm the attack in Step 2, but it only has limited filter slots. Therefore, Rd communicates with Hd using a secure filter swapping protocol to handle filter exhaustion. Similarly, Rs may also run out of filter slots to block attack sources in Step 5. It uses random filter replacement combined with filter request quota to mitigate filter exhaustion attacks.

We have implemented a prototype of StopIt on both Linux and ns2 simulator. Our evaluation on Deterlab demonstrates that StopIt can block the attack traffic from a few millions of attackers in tens of minutes with bounded router memory. Our simulations in ns2 simulator show that StopIt outperforms existing packet filtering systems.

Comparison between Filters and Capabilities

Figure 3: Summary of Comparison between Filters and Capabilities

Both filters and capabilities are promising building blocks for DoS flooding defense systems. They both enable a receiver to control the traffic it receives, but differ dramatically in methodology. The advocates of filters argue that "capabilities are neither sufficient nor necessary to combat DoS", while the proponents of capabilities "strongly disagree". However, there lacks a comprehensive comparison study between these two.

With TVA and StopIt on hand, we are finally able to compare filters and capabilities under similar assumptions and practical constraints. We conduct a comparison of six different DoS flooding mitigation systems, including TVA and StopIt, that are based on either filters or capabilities. Our comparison uses large scale ns2 simulations on realistic topologies, and covers various attack strategies.

The result of the comparison is summarized in Figure 3. When the attackers' power is low, both filters and capabilities work, although filters work slightly better. As the attackers' power increases, filters become ineffective when they cannot be properly installed, and then capabilities become ineffective when attackers can get capabilities from colluders. When the attackers' power is extremely high, both filters and capabilities become ineffective, and other fail-safe mechanisms such as fair queuing are needed.

While there is no clear winner between filters and capabilities in terms of effectiveness, a capability-based system tends to be simpler than a filter-based system. Therefore, we suspect that capabilities combined with per-source-AS fairness might be the most cost-effective DoS flooding mitigation architecture. It is our future work to validate this hypothesis.





This work is supported by the National Science Foundation under Award 0627787.


We welcome any comment, question or feedback. Please send email to Xin Liu or Xiaowei Yang.

Last Updated: October 22, 2008