SCALABLE DEFENSE AGAINST INTERNET BANDWIDTH FLOODING ATTACKS A DISSERTATION SUBMITTED TO THE DEPARTMENT OF ELECTRICAL ENGINEERING AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Aikaterini Argyraki December 2006 UMI Number: 3242516 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion.
® UMI UMI Microform 3242516 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.
Box 1346 Ann Arbor, MI 48106-1346 @ Copyright by Aikaterini Argyraki 2007 All Rights Reserved ii I certify that Ihave read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation foz-Re degree of Doctor of Philosophy. Cheriton) Principal Adviser I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of r of Philosophy. X LÍ JÀ AN + NC (Nick McKeown) I certify that Ihave read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. Ea (Nick Bambos) Approved for the University Committee on Graduate Studies.
ili Abstract During a distributed bandwidth-flooding attack, a large number of attack sources coordinate to send a high volume of undesired traffic to the intended victim; the goal is to exhaust the victim’s band- width, so that the victim fails to respond to its legitimate traffic. These attacks have proved difficult (sometimes impossible) to combat, as they require that action be taken before the victim’s tail cir- cuit. Current practice is typically restricted to the administrator of the victim calling their ISP and asking them to manually install filters to block the attack, an approach increasingly insufficient as attacks become more sophisticated. The intuitive response is to automate this process, i., enable the victim to automatically compute undesired-traffic signatures and send appropriate filtering re- quests to its ISP.
Yet, this approach faces significant challenges: Given the magnitude of currently witnessed attacks, it is unlikely that an ISP alone has enough resources to protect multiple attacked clients. Moreover, asking for help from other ISPs is complicated, in that it requires special inter-ISP relationships that do not exist today and raises security issues. This dissertation presents Active Internet Traffic Filtering (AITF), an IP-layer defense mech- anism against distributed bandwidth-flooding attacks that addresses these challenges. Three key points guide the design of the presented solution: First, an “attack source” is defined as an entity that has been asked to stop sending certain traffic and has been caught disobeying; this definition simplifies the task of the network (no need to detect complex attack patterns) and prevents false positives (innocent hosts prove their innocence by obeying).
Second, attack traffic is blocked at routers located close to the attack sources; this is key for the mechanism’s scalability, as each net- work that hosts attack sources becomes responsible for blocking its own misbehaving clients. Third, a network that hosts attack sources either cooperates and helps block attack traffic, or risks losing its access to the victim; this is a strong incentive to cooperate, especially if the victim is a popular public-access site — as is often the case with flooding-attack victims. We show that Active Internet Traffic Filtering preserves a significant percentage of a victim’s bandwidth in the face of bandwidth flooding, while the per-client cost for each participating ISP is already affordable by today’s ISPs and not expected to increase as the Internet grows. We also show that AITF can be incrementally deployed in the Internet without any special inter-ISP relationships.
We conclude that the IP-layer of the Internet can provide an effective, scalable and deployable solution against distributed bandwidth-flooding attacks. Acknowledgments First, I want to thank my adviser, David R. Painfully honest and politically incorrect, DRC is not your typical PhD adviser. He is tough and uncompromising, in an ongoing mission to reveal the one and only truth, or “the way God intended us” to build the Internet.
I am grateful to have shared his mission for the last six years. Working with him was a bumpy, never boring, always rewarding ride: he taught me to (i) search for the e = me? answer to every problem, (ii) use Occam’s razor, and (iii) respect (but not yield to) the power of the hack —~ because, as all DSGers know, great things in life come in groups of three. I also want to thank the two other members of my thesis committee, Professors Nick Bambos and Nick McKeown, for having the patience to read this dissertation and provide constructive feedback. I am grateful to all those who honored me with their cooperation and/or friendship during my graduate studies: Professor Scott Shenker became my mentor during my internship at the Interna- tional Computer Science Institute and has generously offered his ideas and advice ever since.
Petros Maniatis patiently taught me how to work with others and became my link to the research commu- nity as well as a great friend. Athina Markopoulou and George Candea were the closest witnesses to my PhD journey; Athina took me under her wing when I first started; George taught me that research can be at the same time serious and fun; they both provided inspiration, comfort when things got rough, and a round-the-clock emergency service. Daniel Braga de Faria, my office mate for five years, bravely responded to untimely calls for research/philosophical discussions; together with Evan Greenberg, Dapeng Zhu, Mark Gritter (thank you for patiently answering questions like “why is it again that we don’t like virtual circuits?”), Vince Laviano (DSG meetings, not to mention post-meeting therapy, were never the same without you), Sam Liang and Tassos Argyros, they all helped make the ride smoother and more rewarding. Ken Duda, chief superintendent of all things that matter at Arastra, showed great understanding when I took time off to finish this dissertation.
vi Finally, I am grateful to my dearest friends Tania Yendiki and Dimitris Makris, who lent me a bit of their strength and determination whenever I lost faith in myself. And to my parents, Sophocles and Soteria, and my brother George, who stood faithfully in my corner, waiting to console me, put me back on my feet, and send me out to fight the next round; this dissertation is for them. vil Contents Abstract iv Acknowledgments vi 1 Introduction 1.1 Denial of Service and Bandwidth Flooding.2 Identifying Undesired Traffic 1. LH HQ kẻ n®+aD l3 Filtering Undesired Traffic 2.
QC Q Q Q Q Q Q Q n n nu và ky sa 1.ee 2 Related Work \o 2. uc ch ng kg ky g 2. ng gà hà gi gi ga kia 2.4 Hardware-friendly LSRR Implementations .2 Undesired-traffic IdentiicaHon. cuc ch ra vi yt 2.3 Undesired-traffic Filtering.
ch Quà kia kia va 2.1 Overlay-based Proactive Filtering. kg ky kia gia 2. Black-listing and PointsofControl.4 White-listing and Network Capabilities. Vili 3 Basic Protocol and Properties 21 3.
cu kg kg va 22 3.2 Undesired-traffic Identification. Path-based Wire-speed Filtering ©.5 Provider-client Message Authentication .16 Non-compromised Path. ng kg k kh kg ki v v k va 26 Z2. Q0kg ki ko 26 c6“1 xa.
ae ẽẽ Ma .5 Resource-consumption ContfoÏ. c c c ch HQ HH sa 29 3.3 Properties SH HA.1 Maximum Number ofBlockedFlows. ng Q kg kg kg vâng 34 3. Legitimate and Deaf SOUTC€S.
Q Q Q Q Q Q Q Q n n Q n k k kg gà kg kg kg va 39 3.5 Non-coordinated On-off Sources.6 Coordinated On-off Sources 2. Q Q Q Q Q Q Q cu va 42 343/7 AITFILImIS.4 Summary äẵẳỗĂIÏT.Ha 45 4 Resource Requirements and Scalability 46 4.1 Satisfying Outbound Filtering Requests 2.1 Wire-speed Filters per Client.2 Reduced Filtering Capacity.2 Satisfying Inbound Filtering Requests 2.1 Wire-speed Filters per Cooperating Clhent.2 DRAM per Cooperating Client.3 Resources per Non-cooperating Client. uc cu ng gà k k k k cv k ki ki ki Kia 51 ix 4.4 Evolution of Resource Requirements and Cost. 5 Operation in Untrusted Environments 56 5.1 Malicious Filtering Requests.1 Verifying Filtering-request Orlgin .2 Verifying Non-cooperation Claims.2 Non-cooperating Source Gateways cuc uc Q cu ee KT k kia 61 5.1 Classifying a Source Gateway as Non-cooperating .2 Long-term Aggregate Filtering and Escalaion.
Impact of Non-cooperating Gateways on the Receiver’s Tail Circuit .4 Maximum Number of Flows Blocked with Long-term Filters.3 Spoofed Addresses and Paths.1 Source-address Spoolng. ch ha va 66 5. cv k k kg kg xa va 67 5. ———— ee 71 6 Evaluation through Simulation 74 6.
cu ng gà ga kg và 74 6.2 Identification and Request Overhead. cu nu ca 76 6.3 Tail-circuit Capacity Loss: Non-coordinated Sources.4 Tail-circuit Capacity Loss: Coordinated Sources. 88 7 Conclusions 89 7A Summary =ốẮẽ 89 7.2 Future Work 0ee 91 7. gà kg kg ki kg kg k k k Na 92 A_ AITF Message Format 94 Bibliography 95 List of Tables 3.1 The parameters of the AITF protocol.
The example values are justified later in this chapter (when we discuss AITF properties) and in Chapter 4 (when we discuss AITF cost).2 Qualitative description of the receiver J's states. F’ is the undesired flow.3 State machine for the receiver R. The first column lists all states; the second column de- scribes the events that trigger a set of actions in each state; the third column describes in pseudo-code the actions that take place as a result of each event, including state transitions; the fourth column repeats the state to which we transition after these actions. F is the undesired flow and ?¿„ is the receiver’s gateway, Wy is the filtering window, defined in Table 3.4 Qualitative description of the receiver’s gateway (su) states.
F is the undesired flow; REQout is a parameter definedinTable3.5 State machine for the receiver’s gateway R,. The first column lists all states, the second column describes the events that trigger a set of actions in each state; the third column describes in pseudo-code the actions that take place as a result of each event, including state transitions; the fourth column repeats the state to which we transition after these actions. R is the undesired-traffic receiver, F is the undesired flow, and S,,, is the source gateway; REQoue and Tg, are AITF parameters defined in Table3.6 Qualitative description of the source gateway (S,,,) states. #' is the undesired flow, REQin, W; and Tg, are AITF parameters defined in Table3.
6 eee ee es 32 3.7 State machine for the source gateway Ss„. The first column lists all non-terminal states, the second column describes the events that trigger a set of actions in each state; the third column describes in pseudo-code the actions that take place as a result of each event, includ- ing state transitions; the fourth column repeats the state to which we transition after these actions, F is the undesired flow and S is the undesired-flow source. W;, REQ:, and Tas are parameters defined In Table3. Q2 nu nu kg va 33 Xi 3.8 Characteristics of the receiver and the undesired traffic that we use to quantify the effective- nessOfAITF 2.1 Qualitative description of the receiver (f)’s states with respect to a flow F.
Ty, is an AITF parameter defined in Table3.2 State machine for the receiver R.