Research Abstracts - 2006

Stateful Anycast for DDoS Mitigation

Richard Hansen & Karen Sollins

Introduction

Distributed denial of service (DDoS) by packet flooding (see figure 1) can easily cripple victim hosts or networks, yet effective defenses remain elusive. This is because the Internet provides no general way for a receiver to tell the network to not deliver a particular packet to it.

Figure 1: Traffic sourced by many distributed attackers adds up to saturate a victim's network links.

One possible defense is to use IP anycast [9] to diffuse traffic to multiple servers. Anycast is a network mechanism where packets addressed to a group are delivered to any one member of the group. Anycast gives service providers the ability to deploy multiple servers to handle a large expected load without enabling a distributed attacker to target any one server (see figure 2). IP anycast is used today by several of the root DNS servers [1] [6].

Figure 2: Traffic sent from distributed sources is naturally diffused among anycast group members. A source cannot control which member receives its traffic because all members share the same address.

Unfortunately, IP anycast has two important drawbacks. First, it does not scale in the number of anycast groups: each group requires an entry in routing tables. Second, it does not support stateful sessions because the recipient may change to a different group member over time.

The purpose of this research is to develop Stateful Anycast, a scalable network service that supports stateful sessions. Stateful Anycast will likely build upon an existing proposal to make IP anycast scale, such as PIAS [2]. The ultimate goal is to develop a service that can be used to mitigate DDoS attacks by allowing providers to diffuse attack traffic among replicated and distributed servers—without significantly impacting performance for legitimate users.

Approach

Stateful Anycast introduces a new network entity called an anycast proxy. These proxies provide a layer of indirection to provide scalability and support for stateful sessions. A packet's journey from sender to receiver is broken into two stages. The first stage is delivery using regular IP anycast to an anycast proxy. The second stage of delivery is to an anycast group member, which is done by encapsulating the packet and sending it via unicast. The two-stage approach provides scalability and allows the design of the second stage to determine support for stateful sessions and additional defenses against DDoS attacks.

Making Anycast Scale

As described in [2], anycast proxies can provide scalability by receiving packets on behalf of many anycast groups. Internet routers only need to know a route to an anycast proxy in order to provide reachability to all of the groups handled by the proxy. Internet routers determine a route to the closest anycast proxy by listening to BGP announcements sent by all of the proxies, just like in normal IP unicast routing.

The anycast proxies support many groups by listening to a large, contiguous block of IP addresses. Each anycast group is assigned one of these addresses. When a packet arrives at an anycast proxy, the proxy uses the destination IP address in the packet to determine the intended recipient group.

Adding Support for Stateful Sessions

To support stateful sessions, all anycast proxies must be able to direct packets belonging to a particular session to the particular group member that is holding the session. This way, if a client's packets start arriving at a different anycast proxy due to network changes (movement of a mobile host, routing changes due to a failed or new link, the addition or withdrawal of an anycast proxy, etc.), the proxy can route the packets appropriately.

The task of determining the proper group member can be divided into two sub-tasks. The first sub-task is to determine which session a packet belongs in. This is done by requiring a session ID in every packet. For example, in TCP's case the session ID could be the tuple {source IP, source port, destination IP, destination port}—data that is already in each packet. If a packet is part of a sessionless protocol, or the packet is meant to establish a new session, the packet is simply forwarded to any member.

The second sub-task is to determine which anycast group member is holding the session identified by the session ID in a packet. There are a few general methods to accomplish this task. One such method is to have a well-known static mapping between all possible session IDs and the anycast group members. Another method is to use a directory service to determine which group member is associated with a session ID. Figure 3 illustrates the initiation of a TCP session in Stateful Anycast when a directory service is used. A third method is to route the packet among the anycast proxies until it reaches a proxy that knows which group member is holding the session. Each of these methods will be evaluated for their ability to provide an efficient, DDoS-resistant service.

Figure 3: Simplified illustration of the initiation of a TCP session through an anycast proxy. The session ID is the tuple {source IP, source port, destination IP, destination port}. Packets sent between the proxy and server are encapsulated, allowing for the inclusion of cryptographic protections as well as proxy–server control signals.

Previous work

There are many previously proposed DDoS protection techniques. Capabilities [12] defines state that is awarded to the sender by the receiver and attached to all packets. This state is checked for validity at trust checkpoints inside the network to determine whether the packet is authorized to proceed to the receiver. The NewArch project [3] defined trust-modulated transparency as the idea of limiting communication except between mutually trusting hosts. Client puzzles [4] assigns computationally difficult tasks that the sending host must solve before being allowed to hold a communication session with the receiver. CAPTCHAs [11] and Kill-Bots [7] use reverse Turing tests to ensure that humans have priority over machines in accessing services. Firebreak [5] uses an anycast-like proxy system to move the filtering capabilities of firewalls away from the recipient and towards the senders so that traffic can be dropped early.

There has been some recent work to create a scalable global IP anycast. GIA [8] maps an anycast address to a default unicast address so that routes to rarely used anycast addresses need not consume router state. Internet Indirection Infrastructure (i3) [10] is a general service that decouples the act of sending from the act of receiving by using “triggers” that are resolved using distributed hash tables (DHTs). The use of DHTs allows anycast and other services to be built upon i3 in a scalable fashion. PIAS [2] uses an overlay network connecting anycast proxy servers to provide scalability without modifying the routing infrastructure or clients. The proposed stateful anycast will build upon one of these global anycast services.

References:

[1] Joe Abley. ISC Technical Note ISC-TN-2003-1: Hierarchical Anycast for Global Service Distribution. 2003. Available on-line at: http://www.isc.org/pubs/tn/isc-tn-2003-1.html (as of March 14, 2006).

[2] Hitesh Ballani and Paul Francis. Towards a Global IP Anycast Service. In SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, pp. 301–312, Philadelphia, Pennsylvania, USA, August 2005. doi:10.1145/1080091.1080127

[3] David Clark, Karen Sollins, John Wroclawski, Dina Katabi, Joanna Kulik, and Xiaowei Yang. New Arch: Future Generation Internet Architecture (Final Technical Report). USA, 2003. Available on-line at: http://www.isi.edu/newarch/ (as of March 14, 2006).

[4] Wu-chang Feng, Ed Kaiser, Wu-chi Feng, and Antoine Luu. The Design and Implementation of Network Puzzles. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, vol. 4, pp. 2372–2382, Miami, Florida, USA, March 2005. doi:10.1109/INFCOM.2005.1498523

[5] Paul Francis. Firebreak: An IP Perimeter Defense Architecture. To be published. Available on-line at: http://www.cs.cornell.edu/People/francis/firebreak/ (as of March 14, 2006).

[6] T. Hardie. RFC 3258: Distributing Authoritative Name Servers via Shared Unicast Addresses. April 2002. Available on-line at: http://www.rfc-editor.org/rfc/rfc3258.txt (as of March 14, 2006).

[7] Srikanth Kandula, Dina Katabi, Matthias Jacob, and Arthur Berger. Botz-4-Sale: Surviving Organized DDoS Attacks That Mimic Flash Crowds. In Proceedings USENIX NSDI '05, pp. 287–300, Boston, Massachusetts, USA, May 2005. Also available on-line at: http://www.usenix.org/events/nsdi05/tech/kandula.html (as of March 14, 2006).

[8] Dina Katabi and John Wroclawski. A Framework for Scalable Global IP-Anycast (GIA). In ACM SIGCOMM Computer Communication Review, vol. 31, issue 2 supplement, pp. 186–219, April 2001. doi:10.1145/844193.844206

[9] C. Partridge, T. Mendez, and W. Milliken. RFC 1546: Host Anycast Service. November 1993. Available on-line at: http://www.rfc-editor.org/rfc/rfc1546.txt (as of March 14, 2006).

[10] Ion Stoica, Daniel Adkins, Shelley Zhuang, Scott Shenker, and Sonesh Surana. Internet Indirection Infrastructure. In SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, pp. 73–86, Pittsburgh, Pennsylvania, USA, August 2002. doi:10.1145/633025.633033

[11] Luis von Ahn, Manuel Blum, Nicholas J. Hopper, John Langford. CAPTCHA: Using Hard AI Problems for Security. In EUROCRYPT 2003—Lecture Notes in Computer Science, Volume 2656, pp. 294–311, Warsaw, Poland, May 2003. Also available on-line at: http://www.springerlink.com/link.asp?id=p8t2q8q6bxey8tvx (as of March 14, 2006). Also see: http://www.captcha.net/ (as of March 14, 2006).

[12] Xiaowei Yang, David Wetherall, and Thomas Anderson. A DoS-limiting Network Architecture. In SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, pp. 241–252, Philadelphia, Pennsylvania, USA, August 2005. doi:10.1145/1080091.1080120