Low-Rate TCP-Targeted Denial of Service Attacks(The Shrew vs. the Mice and Elephants) yAleksandar Kuzmanovic and Edward W. KnightlyECE/CS DepartmentsRice UniversityHouston, TX 77005, USAfakuzma,[email protected] of Service attacks are presenting an increasing threat to theglobal inter-networking infrastructure. While TCP’s congestioncontrol algorithm is highly robust to diverse network conditions,its implicit assumption of end-system cooperation results in a well-known vulnerability to attack by high-rate non-responsive flows. Inthis paper, we investigate a class of low-rate denial of service at-tacks which, unlike high-rate attacks, are difficult for routers andcounter-DoS mechanisms to detect. Using a combination of ana-lytical modeling, simulations, and Internet experiments, we showthat maliciously chosen low-rate DoS traffic patterns that exploitTCP’s retransmission time-out mechanism can throttle TCP flowsto a small fraction of their ideal rate while eluding detection. More-over, as such attacks exploit protocol homogeneity, we study fun-damental limits of the ability of a class of randomized time-outmechanisms to thwart such low-rate DoS attacks.Categories and Subject DescriptorsC.2.0 [Security and Protection]: Denial of Service;C.2.2 [Computer-Communication Networks]: Network Proto-colsGeneral TermsAlgorithms, Performance, SecurityKeywordsDenial of Service, TCP, retransmission timeout This research is supported by NSF ITR Grant ANI-0085842, NSFSpecial Projects Grant ANI-0099148, a Sloan Fellowship, and byHP Laboratories.yA shrew is a small but aggressive mammal that ferociously attacksand kills much larger animals with a venomous bite.Permission 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.SIGCOMM’03,August25–29, 2003, Karlsruhe, Germany.Copyright 2003 ACM 1-58113-735-4/03/0008 ...$5.00.1. INTRODUCTIONDenial of Service (DoS) attacks consume resources in networks,server clusters, or end hosts, with the malicious objective of pre-venting or severely degrading service to legitimate users. Resourcesthat are typically consumed in such attacks include network band-width, server or router CPU cycles, server interrupt processing ca-pacity, and specific protocol data structures. Example DoS attacksinclude TCP SYN attacks that consume protocol data structures onthe server operating system; ICMP directed broadcasts that directa broadcast address to send a flood of ICMP replies to a target hostthereby overwhelming it; and DNS flood attacks that use specificweaknesses in DNS protocols to generate high volumes of trafficdirected at a targeted victim.Common to the above attacks is a large number of compromisedmachines or agents involved in the attack and a “sledge-hammer”approach of high-rate transmission of packets towards the attackednode. While potentially quite harmful, the high-rate nature of suchattacks presents a statistical anomaly to network monitors such thatthe attack can potentially be detected, the attacker identified, andthe effects of the attack mitigated (see for example, [6, 22, 30]).In this paper, we study low-rate DoS attacks, which we term“shrew attacks,” that attempt to deny bandwidth to TCP flows whilesending at sufficiently low average rate to elude detection by counter-DoS mechanisms.TCP congestion control operates on two timescales. On smallertimescales of round trip times (RTT), typically 10’s to 100’s ofmsec, TCP performs additive-increase multiplicative-decrease (AIMD)control with the objective of having each flow transmit at the fairrate of its bottleneck link. At times of severe congestion in whichmultiple losses occur, TCP operates on longer timescales of Re-transmission Time Out (RTO).1In an attempt to avoid congestioncollapse, flows reduce their congestion window to one packet andwait for a period of RTO after which the packet is resent. Upon fur-ther loss, RTO doubles with each subsequent timeout. If a packetis successfully received, TCP re-enters AIMD via slow start.To explore low-rate DoS, we take a frequency-domain perspec-tive and consider periodic on-off “square-wave” shrew attacks thatconsist of short, maliciously-chosen-duration bursts that repeat witha fixed, maliciously chosen, slow-timescale frequency. Consider-ing first a single TCP flow, if the total traffic (DoS and TCP traffic)during an RTT-timescale burst is sufficient to induce enough packetlosses, the TCP flow will enter a timeout and attempt to send a newpacket RTO seconds later. If the period of the DoS flow approxi-mates the RTO of the TCP flow, the TCP flow will continually incurloss as it tries to exit the timeout state, fail to exit timeout, and ob-tain near zero throughput. Moreover, if the DoS period is near but1recommended minimum value 1 sec [1]75outside the RTO range, significant, but not complete throughputdegradation will occur. Hence the foundation of the shrew attack isa null frequency at the relatively slow timescale of approximatelyRTO enabling a low average rate attack that is difficult to detect.In a simplified model with heterogeneous-RTT aggregated flowssharing a bottleneck link, we derive an expression for the through-put of the attacked flows as a function of the timescale of the DoSflow, and hence of the DoS flow’s average rate. Furthermore, wederive the “optimal” DoS traffic pattern (a two-level periodic squarewave) that minimizes its average rate for a given level of TCPthroughput for the victim, including zero throughput.Next, we use ns-2 simulations to explore the impact of aggrega-tion and heterogeneity on the effectiveness of the shrew attack. Weshow that even under aggregate flows with heterogeneous RTT’s,heterogeneous file sizes, different TCP variants (New Reno, SACK,etc.), and different buffer management schemes (drop tail, RED,etc.), similar behavior occurs albeit with different severity for dif-ferent flows and scenarios. The reason for this is that once the firstbrief outage occurs, all flows will simultaneously timeout. If theirRTOs are nearly identical, they synchronize to the attacker’s pe-riod and will enter a cycle identical to the single-flow case,