Mitigating Bandwidth-Exhaustion Attacks usingCongestion Puzzles(Extended Abstract)XiaoFeng Wang∗Michael K. Reiter†ABSTRACTWe present congestion puzzles (CP), a new countermeasureto bandwidth-exhaustion attacks. Like other defenses basedon client puzzles, CP attempts to force attackers to in-vest vast resources in order to effectively perform denial-of-service attacks. Unlike previous puzzle-based approaches,however, ours is the first designed for the bandwidth-exhaustionattacks that are common at the network (IP) layer. At thecore of CP is an elegant distributed puzzle mechanism thatpermits routers to cooperatively impose and check puzzles.We demonstrate through analysis and simulation that CPcan effectively defend networks from flooding attacks with-out relying on the formulation of attack signatures to filtertraffic. Moreover, as many such attacks are conducted by“zombie” computers that have been silently commandeeredwithout the knowledge of their owners, the overheads thatCP imposes on heavily engaged zombies can increase thelikelihood that the computer’s owner detects the compro-mise and takes action to remedy it.Categories and Subject DescriptorsC.2.0 [Computer-Communication Networks]: General—security and protection; C.2.6 [Computer-CommunicationNetworks]: Internetworking—routersGeneral TermsSecurityKeywordsclient puzzle, denial of service1. INTRODUCTIONCurrent Internet sites continue to suffer from a rangeof distributed denial-of-service (DDoS) attacks, especiallybandwidth-exhaustion attacks. In a bandwidth-exhaustion∗School of Informatics and Computer Science Department,Indiana University at Bloomington, Bloomington, IN, USA;[email protected]†Department of Electrical and Computer Engineering, De-partment of Computer Science, and CyLab, Carnegie MellonUniversity, Pittsburgh, PA, USA; [email protected] to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.CCS’04, October 25-29, 2004, Washington, DC, USA.Copyright 2004 ACM 1-58113-961-6/04/0010 ...$5.00.attack, adversaries employ DDoS tools to capture a fleet of“zombie” computers, from which they collectively generatea huge volume of traffic to overwhelm the bandwidth of thetarget network. As in many other types of denial-of-serviceattacks, bandwidth exhaustion attacks can be mounted withlittle cost to each zombie and its adjacent network, while inaggregate imposing significant burden on the target.In this paper, we present congestion puzzles (CP), a newcountermeasure to bandwidth-exhaustion attacks. A typicalpuzzle is composed of a moderately-hard function; solvingthe puzzle requires a brute-force search in the solution space.Once a link adjacent to a router implementing the CP mech-anism (a puzzle router) is congested, the router requires thetraffic flow to be accompanied by a corresponding computa-tion flow, i.e., a continuous flow of puzzle solutions, therebyimposing a computational burden on clients who transmitvia this router. The rate of the computation flow (averagenumber of searching steps per second) is tied to the band-width consumed (bytes per second) by a puzzle-based ratelimiter (PRL) implemented in the router. As a result, thiscoarsely requires from clients a computation flow commen-surate with their bandwidth usage on the congested link,thereby impairing their ability to sustain a flooding attack.The consumption of CPU cycles in zombie computers mayadditionally alert the unwitting owners of those computersto their contribution to the attack, and motivate them torepair their computers.While the CP mechanism can be somewhat effective whenimplemented by each router in isolation, our approach ad-ditionally extends to a distributed puzzle mechanism (DPM)through which a router can ask its upstream1routers to helpcontrol the attack flows before converging to the congestedlink. DPM enables multiple routers to efficiently coordinatewith each other to generate and distribute puzzles and tocheck puzzle solutions. On the other hand, DPM also hasrouters work independently, and so is robust to attacks fromcorrupted routers.CP offers many other advantages among approaches fordefending against flooding attacks. First, unlike many pro-posals for deploying defenses in the network (e.g., [25, 21,39]), CP does not require the formulation of accurate at-tack signatures by which routers detect or filter attack traf-fic. Second, congestion puzzles support incremental deploy-ment; our simulation results suggest that the bandwidth-exhaustion attacks can be greatly mitigated with only asmall fraction of routers implementing CP. Third, we demon-strate that CP permits lightweight implementation within1Throughout the paper, we call the direction of attack flows(from zombies to the victim) the “downstream” directionand the reverse direction the “upstream” direction.257routers. Fourth, since we apply puzzles at the network(IP) layer, CP might assist in defending against higher-leveldenial-of-service attacks, as well.2. RELATED WORK2.1 Countermeasurestobandwidth-exhaustionattacksMechanisms to counter bandwidth-exhaustion attacks in-clude aggregate-based congestion control [25, 21, 40], trace-back [11, 8, 31, 34, 13, 4, 33] and filtering [17, 24, 36, 32,22, 39].Aggregate-based congestion control (ACC) has been pro-posed by Mahajan et al. [25] and implemented by Ioannidisand Bellovin [21]. This mechanism extends traditional flow-based congestion controls [15, 35, 18, 26] so as to managepacket flows at a finer granularity. An aggregate is definedas a collection of packets that share some property (signa-ture). ACC provides mechanisms for detecting and control-ling aggregates at a router using an attack signature, anda pushback mechanism to propagate aggregate control re-quests (and the attack signature) to upstream routers. ACCcritically depends on the mechanism by which attacks aredetected and an attack signature is formulated, and this canbe a source of difficulty against an intelligent adversary thatvaries its traffic characteristics over time. A goal of CP isto avoid the need to formulate attack signatures.A related congestion control