Reduction of Quality Attacks on Adaptation Mechanisms - Mina Guirguis

BOSTON UNIVERSITY GRADUATE SCHOOL OF ARTS AND SCIENCE Dissertation REDUCTION-OF-QUALITY ATTACKS ON ADAPTATION MECHANISMS MINA GUIRGUIS B., Boston University, 2005 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2007 UMI Number: 3240623 Copyright 2006 by Guirguis, Mina All rights reserved. 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 3240623 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 MINA GUIRGUIS 2006 Approved by First Reader Azer Ẹ| 6 Bestavros, Ph. Professor of Computer Science Boston University Second Reader AMAL Tbrahim Matta, Ph. Associate Professor of Computer Science Boston University Third Reader "; Katabi, Pal pdistant Professdf of Computer Science assachusetts Institute of Technology Acknowledgments Looking back over the past few years, I am most certain that this work would not have been of any significance, if it was not for the support and help that I have received from many individuals during my graduate career at Boston University.

I am most grateful and truly indebted to my advisors, Azer Bestavros and Ibrahim Matta, for they have taught me how to be a computer scientist. They have supported me tremendously throughout my Ph. program and have been much more than advisors; they have been teachers, mentors and friends. They have always maintained an open door, offering their time and help, no matter how their schedules seemed busy.

The time I have spent interacting with them has benefited me extremely, not just on the academic level but also on the personal level. I would like to thank John Byers and Mark Crovella for their valuable feedback on different pieces of my research work, for supporting me with their recommendation letters and for serving on my thesis committee. I would also like to thank Dina Katabi, for her feedback on earlier versions of this thesis and for serving on my thesis committee. I would also like to thank Abdelsalam Heddaya and Sonia Fahmy for their efforts throughout my job application process.

They have supported me with recommendation letters and have always made sure to let me know of any opportunities that would be of an interest to me. I would like to specially thank Yuting Zhang for her help with some of the experimental work done in this thesis. Additional support for my research work has been provided by the National Science Foundation and by Fortress Technologies. I would like to thank Owais Hassan and Magued Barsoum for their support during my internships at Fortress and beyond.

I am very grateful to Fady Barsoum for his constant support as early as I could re- member. He has invested great efforts in following up with my applications when I was applying for graduate schools and he has always been there for me when I needed advice. iv There is no way to thank my family enough, for their love, support and prayers that brought me to this stage of my career and brought my thesis to completion. I would also like to thank George Atia, Hany Morcos, Karim Mattar, Maria Mitsi, Dan Buzan, and Xiaoyu Jiang for their support during my Ph.

Special thanks to Raymond Sweha for his help in submitting my thesis and paperwork for graduation. Finally, I would like to thank all members of the WING, NRG and BOSS for the wonderful times that I spent at Boston University. REDUCTION-OF-QUALITY ATTACKS ON ADAPTATION MECHANISMS (Order No. ) MINA GUIRGUIS Boston University, Graduate School of Arts and Science, 2007 Major Professor: Azer Bestavros, Professor of Computer Science Department ABSTRACT One important consideration in realizing dependable computing systems and networks is to uncover vulnerabilities in their designs to adversarial attacks.

Currently, the designs of these systems employ different forms of adaptation mechanisms in order to optimize their performance by ensuring that desirable properties, such as stability, efficiency and fairness, are not compromised. This thesis discovers and studies a new type of adversarial attacks that target such adaptation mechanisms by exploiting their dynamics of operation — ?., the characteristics of their transient behavior. We coin this new breed of adversarial attacks, Reduction of Quality (RoQ) attacks. The premise of RoQ attacks is to keep an adaptive mechanism constantly in a transient state, effectively depriving the system from much of its capacity and significantly reducing its service quality.

In this thesis we develop a general control-theoretic framework that provides a uni- fied approach to modeling and vulnerability assessment of the dynamics underlying RoQ exploits. Within this framework, we introduce and formalize the notion of an attack ” Po- tency” that capitalizes on the attacker’s best incentive: maximizing the marginal utility of its attack traffic. Unlike traditional brute-force Denial of Service attacks that aim to take down a system at any cost, RoQ attacks aim to maximize the damage inflicted on a system through consuming an innocuous, small fraction of that system’s hijacked capacity. vi We instantiate our framework using detailed analytical models and associated metrics on a series of adaptation mechanisms that are commonly used in networking protocols, end- system admission controllers and load balancers.

We assess the impact of RoQ attacks using analysis, simulations, and Internet experiments. We identify key factors that expose the tradeoffs between resilience and susceptibility to RoQ attacks. These factors could be used to harden adaptation mechanisms against RoQ exploits, in addition to developing new forms of countermeasures and defense mechanisms. vii Contents 1 Introduction eCoNŒRFO 1.

1 co Ca 6 8 L6 an 1. 00800 eae “ca 6 1 U18 8 2 RoQ Attack Definition and Premise 11 2.1 Attack Goal and Definition .2 Adaptation as an Optimization Process. ee ee 17 3 RoQ Attacks on Network Transport Protocols 20 3.3 Numerical and Simulation Results .4 Internet Experiments and Implementation Results cS g 31 3.c R1 1 8 SA 35 Distributed RoQ Attacks for Stealing Bandwidth 41 Attack Definition. cv và số Ce HC R6 8 C8 411 RoQ Attack Construction .2 Selecting the Targeted links .3 A Lower Bound on Zombies .3 Internet Experiments and Implementation Results 4.

EU NÓ L8 viii 5 Bounds on the Impact of Low-Rate Attacks 50 5. ee oe SA 1 K6 8 8 8 8 51 5. uc ee ee, 55 5.2 Low-Rate Attacks 2. es Se SS L9 56 5.

e ue v1 YÊU ÔN 56 5.2 Reduction of Quality Attacks .2 An Outline for a Possible Defense Mechanism .3 RTO Randomization vs. Randomized Attacker 66 6 RoQ Attacks on End-System Admission Controllers 68 6.4 Internet Experiments and Implementation Results. ¬ 82 7 RoQ Attacks on End-System Load Balancers 7. cuc ch cu ko {R6 C8 8 R8 7.

eee ee oe. An Upper Bound on Attack Potency .2 Potency for Dynamic Load Balancing .3 A Lower Bound on Attack Potency. ee ee Ce .5 Internet Experiments and Implementation Results — 8 Conclusions, Derivative Work and Future Work 119 8.2 Derivative Work and Impact.1 Exposing Additional Vulnerabilities in Adaptation Mechanisms .2 Other (Less Harmful and More Plausible) RoQ-like Exploits.3 Control-Plane Intrusion Detection System ¬ 123 Appendix A 124 Appendix B 126 References 130 Curriculum Vitae 138 List of Tables 3.1 Potency values for Bandwidth (withQ=1) .2 Potency values for Delay Jitter (withQ=1).1 Gain Ratio for different round-trip time TCP connections .1 Model parameters for a PI admission controller. 71 71 Model parameters for load balancing policles.

0 e 90 x1 List of Figures 11 Thesis organization. cv kg vn kg kg gà kg và 9 21 A general block diagram for the adaptation mechanisms considered. 14 2:2 An example of a pricing function and the effect of a RoQ attack. 15 2:3 Attack potency versus attack peak rate for different 9 values.

19 3-1 Block diagram showing the feedback control system for TCP and RED. 22 3:2 Vulnerability assessment of TCP+RED and TCP+DropTail to RoQ attacks. 26 3:3 Tuning RoQ attack parameters to maximize potency for link bandwidth. 30 3-4 Tuning RoQ attack parameters to maximize potency for delay jitter.

31 đỗ Setup for Internet Experiments. 0 0 HQ nh Q va va 32 j.6 RoQ attack potency as the attack period T is changed. 33 3:7 RoQ attack potency as the attack duration 7 is changed.1 Adversarial scheme considered for distributed RoQ attacks. 39 4-2 A more detailed view of the adversarial scheme considered.

41 4:3 A lower bound on zombies for different probabilities and degrees.4 The two-link topology used in ns-2 simulation experiments. 45 4:5 Improvement in allocated bandwidth as the level of DoS attack increases. 45 4:6 Improvement in allocated bandwidth as r changes for a fixed Tanddé. 46 4:7 The five-link topology used in ns-2 simulation experiments.

46 4:8 Throughput allocated to each flow from the BC flows.9 Setup for Internet experimenf§. 48 4:10 Throughput allocated to the connection between C4 and S90. 49 xi 5-1 Buffer process and window evolution via the AIMD mechanism. 5:2 Under-utilization due to a Shrew attack at saturation.

5:3 Under-utilization due to a Shrew attack at full buffer. 5:4 Normalized potency versus buffer size for different attack variants. 5:5 Under-utilization due to a RoQ attack at saturation. 5-6 Under-utilization due to a Shrew attack at full buffer.

5-7 Assessment of RTO randomization for different RTT connections. 5:8 Impact of different ranges of randomization under periodic attack. 5-9 Impact of different ranges of randomization under randomized attack. 6-1 Block diagram for the components of the admission control feedback loop.

70 6:2 Linearized instances for the web-server model functions. 70 6:3 Numerical assessment of admission controllers to RoQ attacks. 78 6-4 Setup for Internet experiments. 0 ee và 80 6:5 Experimental assessment of admission controllers to RoQ attacks.

81 71 A general setup for load balancing. ee 89 7:2 Vulnerability assessment for proportional load-balancing to RoQ attacks. 99 7:3 Vulnerability assessment for weighted load-balancing to RoQ attacks. 99 7-4 Vulnerability assessment for least-loaded load-balancing to RoQ attacks.

100 7:5 Attack potency under different balancing policies. 101 76 Simulation result for the optimal balancing policy. 103 77 Vulnerability assessment for proportional load balancers. 104 7:8 Impact of feedback delay on the attack potency .004 105 7-9 Service degradation model as a linear function of the queue size.

107 7:10 Impact of overhead/thrashing on attack potency. 108 7-11 Changes in the queue size observed by a monitor. 109 7-12 Impact of Ø on the admission ratio under proportional balancing policy. 111 7-13 Experimental assessment for the proportional load-balancer (@ = 0.

113 xi1 7-14 Experimental assessment for the weighted load-balancer (y=0. 115 7-15 Experimental assessment for the least-loaded load-balancer. 116 7-16 Experimental assessment for load balancing policies to RoQ attacks. 117 7-17 Effect of feedback update periods.

0004 ee 117 XIV List of Abbreviations AIMD. Additive Increase Multiplicative Decrease AQM. Active Queue Management DDoS _. Distributed Denial of Service DoS.

Denial of Service DTW. Dynamic Time Warping ESM _. End System Multicast FRED. Flow Random Early Drop TT.

Internet Protocol PL. Proportional Integral RED. Random Early Detection REM. Random Exponential Marking RoQ —.

Reduction of Quality RIT. Round-Trip Time TCP _. Transmission Control Protocol 10) D). User Data-gram Protocol VoIP _.

Voice over Internet Protocol xv Chapter 1 Introduction The Internet continues to play a vital role in our daily lives with a profound impact on our economy and on our society.