TOLERATING DENIAL-OF-SERVICE ATTACKS
UNIVERSITY OF CALIFORNIA, SAN DIEGO
Tolerating Denial-of-Service Attacks
– A System Approach
A dissertation submitted in partial satisfaction of the requirements for the degree Doctor of Philosophy
in
Computer Science
by
JU WANG
Committee in charge:
Andrew A. Chien, Chair
Kimberly C. Claffy
Rene L. Cruz
Keith Marzullo
Stefan Savage
Giovanni Vigna
2005
The dissertation of Ju Wang is approved, and it is
acceptable in quality and form for publication on
microfilm:
_____________________________________
_____________________________________
_____________________________________
_____________________________________
_____________________________________
_____________________________________
Chair
University of California, San Diego
2005
Table of Contents
Signature Page iii
Table of Contents iv
List of Figures viii
List of Tables xi
Acknowledgements xii
Vita xiv
Publications xiv
Abstract of The Dissertation xv
Chapter 1 Introduction 1
1.1 Denial-of-Service Attacks on Internet Service Applications 1
1.2 Proxy Network-based DoS Defense 6
1.3 Challenges 8
1.4 Thesis and Approach 10
1.5 Contributions 14
1.6 Organization 17
Chapter 2 Background 18
2.1 DoS Problem for Internet Service Applications 18
2.1.1 Internet Service Applications 19
2.1.2 Denial-of-Service Attacks 20
2.1.3 Defense of Denial-of-Service Attacks 24
2.1.4 Summary 26
2.2 Proxy Network-Based DoS Defense 26
2.2.1 Basics of Overlay Networks 27
2.2.2 Definition of Proxy Network-based DoS Defense 29
2.2.3 Attacks on Proxy Network-based DoS Defense 31
2.2.4 Mechanisms Used to Protect Proxy Network-based DoS Defense 33
2.2.5 Understanding of Proxy Network-based DoS Defense 35
2.3 Summary 38
Chapter 3 Thesis Statement 40
3.1 Context 40
3.2 Problem Definition 41
3.3 Thesis Statement 44
Chapter 4 Approach 48
4.1 Overview 48
4.2 A Generic Framework for Proxy Network-based DoS Defense 52
4.2.1 Definition of the Generic Framework 53
4.2.2 Generality of the Generic Framework 61
4.3 Resisting Penetration Attacks 65
4.4 Resisting Proxy Depletion Attacks 67
4.5 Resilience to DoS Attacks on Proxy Network 68
4.6 Summary 72
Chapter 5 Resisting Penetration Attacks 74
5.1 Introduction 74
5.2 Stochastic Model for System Component Dynamics 76
5.3 System Dynamics Under Penetration Attacks 81
5.4 Analytical Results: Uncorrelated Vulnerabilities 83
5.4.1 Theorems for Penetration Resistance 83
5.4.2 Can Proxy Networks Resist Penetration Attacks? 87
5.4.3 What System Parameters Enable Effective Resistance? 88
5.5 Simulation Results: Correlated Vulnerabilities 92
5.5.1 How Does Adding Correlated Host Vulnerabilities Affect Previous Results? 93
5.5.2 How to Mitigate the Impact of Correlated Host Vulnerabilities? 94
5.5.3 Can Proxy Networks Resist Penetration Attacks with Correlated Vulnerabilities? 97
5.6 Summary 101
Chapter 6 Resisting Proxy Depletion Attacks 103
6.1 Introduction 103
6.2 Stochastic Model 104
6.3 Graph-Theoretic analysis 106
6.3.1 Analysis and Results 107
6.3.2 Design Principles 116
6.4 Case Study 117
6.4.1 Topologies 118
6.4.2 Comparison using Theory 121
6.5 Summary 124
Chapter 7 Resisting Denial-of-Service Attacks 126
7.1 Introduction 126
7.2 Methodology 127
7.2.1 High-level Design of Experiments 128
7.2.2 System Components 129
7.2.3 Simulation Framework 134
7.2.4 Veracity of the Experiments 136
7.3 Experiments and Results 139
7.3.1 Impact of DoS Attacks on Application Performance 140
7.3.2 Resisting Large-Scale DoS Attacks 141
7.3.3 Scalability of Proxy Networks’ Resilience to DoS attacks 148
7.4 Summary 149
Chapter 8 Conclusion 151
8.1 Dissertation Summary 151
8.2 Implications and Impacts 155
8.3 Deployment Issues 157
8.4 Future Work 160
8.4.1 Further Studies 160
8.4.2 Covering a Wider Range of Attacks 161
8.4.3 Exploring Multiple Dimensions of the Design Space 162
8.4.4 Supporting a Wider Range of Applications 162
8.4.5 Resisting Application-level DoS Attacks 163
Appendix: Basic facts on the spectra of graphs 164
References 166
List of Figures
FIGURE 1-1 NUMBER OF ATTACK INCIDENTS ON THE INTERNET (REPORTED TO CERT) 2
Figure 1-2 Denial-of-Service Attack 3
Figure 1-3 Proxy Network-based DoS Defense 6
Figure 2-1 Internet Service Application (Left: Deployment, Right: Model) 19
Figure 2-2 A Typical DDoS Zombie Network 23
Figure 2-3 Illustration of an Overlay Network 28
Figure 2-4 Proxy Network-based DoS Defense 30
Figure 2-5 Secure Overlay Services (SOS) 36
Figure 2-6 Internet Indirection Infrastructure (i3) 37
Figure 3-1 Direct Access vs. Mediation 40
Figure 3-2 Proxy Network as Mediator 41
Figure 4-1 Three Classes of Attacks on Proxy Networks 49
Figure 4-2 Generic Framework for Proxy Networks 53
Figure 4-3 Penetration Attacks 58
Figure 4-4 Proxy Depletion Attacks 58
Figure 4-5 System Component State Transitions 59
Figure 4-6 Secure Overlay Services (SOS) 62
Figure 4-7 Internet Indirection Infrastructure (i3) 63
Figure 4-8 Penetration Attacks 66
Figure 4-9 Proxy Depletion Attacks 67
Figure 4-10 Denial of Service attacks 69
Figure 5-1 Host State Transitions 77
Figure 5-2 Domain-Based Correlated Host Vulnerability Model 78
Figure 5-3 Proxy State Transition 79
Figure 5-4 System Dynamics under Penetration Attacks 82
Figure 5-5 Markov State Transition (without reconfiguration) 84
Figure 5-6 Markov State Transition (with proxy migration) 85
Figure 5-7 Impact of Proxy Network Depth 89
Figure 5-8 Impact of Proxy Migration 91
Figure 5-9 Impact of Proxy Network Depth with Correlated Host Vulnerabilities 93
Figure 5-10 Penetration Probability under Varied Proactive Reset Rates 94
Figure 5-11 Penetration Probability under Varied Host Diversity 96
Figure 5-12 Host Diversity in a Proxy Chain 96
Figure 5-13 Interleaved Design for A Proxy Chain 98
Figure 5-14 Effectiveness of Interleaved Design 99
Figure 5-15 Effectiveness of Interleaved Design (data points observed from 107 and 108 time steps) 100
Figure 6-1 Proxy State Transition 105
Figure 6-2 System Dynamics under Proxy Depletion Attacks 106
Figure 6-3 Illustration of Theorem 3 108
Figure 6-4 Illustration of Theorem 4 112
Figure 6-5 Chord Network Topology (N=8) 119
Figure 6-6 Two-dimensional CAN Network (N=9) 119
Figure 6-7 Undirected Binary de Bruijn Graph (N=8) 120
Figure 6-8 3-dimensional Hypercube (N=8) 121
Figure 6-9 Eigenvalues of the Topologies Studied 122
Figure 6-10 [pic] Values of the Topologies Studied ((( is Laplacian Spectrum) 123
Figure 7-1 Experiment Configuration 128
Figure 7-2 Proxy Network Implementation 131
Figure 7-3 Direct Access vs. Proxy Network Mediation 137
Figure 7-4 Application Performance (Direct Application Access vs. Proxy Network Mediation) 139
Figure 7-5 Impact of DoS attacks on Application Performance 140
Figure 7-6 Spread DoS Attacks 141
Figure 7-7 Concentrated DoS Attacks 142
Figure 7-8 Application Performance under Spread DoS Attack 143
Figure 7-9 Correlation among Proxies and Users 144
Figure 7-10 Application Performance under Concentrated DoS Attacks (Static Edge Proxy Selection) 145
Figure 7-11 Application Performance under Concentrated DoS Attacks (Dynamic Edge Proxy Selection) 146
Figure 7-12 Analysis of Dynamic Edge Proxy Selection 147
Figure 7-13 Resilience and Proxy Network Size 149
List of Tables
TABLE 5-1 PARAMETERS OF THE STOCHASTIC MODEL 76
Table 5-2 Windows Vulnerability Statistics 80
Table 6-1 Topological Properties of Selected Graphs 118
Acknowledgements
I WOULD LIKE TO THANK EVERYONE WHO SUPPORTED ME INTELLECTUALLY, SOCIALLY, EMOTIONALLY, AND ACADEMICALLY DURING MY MANY YEARS OF GRADUATE SCHOOL AT UNIVERSITY OF CALIFORNIA, SAN DIEGO. I AM GREATLY INDEBTED TO ALL OF THEM.
First of all, I would like to thank my advisor Professor Andrew A. Chien. Without his invaluable advices, guidance, and support on my research, I could not have achieved what I have done. It has been a great honor to have the opportunity to learn from him and work with him. I am also deeply indebted to Professor Bradley Calder for his help and guidance in Entropia, UCSD, and during my job hunting process. It is my real pleasure to have a chance to work with him. Furthermore, I would like to thank Professor Keith Marzullo, Professor Stefan Savage, Professor Professor Rene I. Cruz, Professor Giovanni Vigna, and Dr. Kimberly Claffy for serving on my committee, and helping me with my dissertation.
I would also like to acknowledge my fellow graduate students and colleagues. I thank all the CSAG members, who worked with me and gave me tremendous help in many aspects of my life. In particular, I would like to thank Xinran Wu, Xin Liu, Huaxia Xia, Eric Weigle, Justin Burke, Nut Taesombut, Luis Rivera, Richard Huang, Alex Olugbile, Kenjiro Taura, Adam Brust, Troy Chuang, Kay Connelly, and Scott Pakin. Many of the key research findings in my thesis work came from the discussion and collaboration with them. They also gave me invaluable help on my thesis writing. I cannot thank them enough for their support. Furthermore, I would like to thank Linyuan Lu, Hongyu Chen, Alvin AuYoung, Congchun He, Lexing Ying, Professor Vijay Karamcheti, Eric Freudnthal, and Bao Liu for their enlightening discussions and valuable advices on my research. Also, I want to express my thankfulness to Patricia Bladh and Jenine Combs for helping me with my thesis and defense preparation.
Finally, I would like to thank my family and great friends for their unconditional support. They helped me get through many difficult times, and shared joy and bitterness with me during my seven years here in San Diego. Without them, I could not have completed this dissertation.
Vita
|1998 |B.S. TSINGHUA UNIVERSITY |
|1998 – 2005 |Research Assistant, University of California, San Diego |
|2000 |M.S, University of California, San Diego |
|2000 – 2001 |Software Engineer, Entropia Inc., San Diego |
|2005 |Ph.D., University of California, San Diego |
Publications
1. “UNDERSTANDING WHEN LOCATION-HIDING USING OVERLAY NETWORKS IS FEASIBLE”, JU WANG AND ANDREW A. CHIEN, IN SPECIAL ISSUE OF COMPUTER NETWORKS (ELSEVIER) ON OVERLAY DISTRIBUTION STRUCTURES AND THEIR APPLICATIONS, 2005.
2. “Empirical Study of Tolerating Denial-of-Service Attacks with a Proxy Network”, Ju Wang, Xin Liu and Andrew A. Chien, in proceeding of the 14th ACM/USENIX Security Symposium, August 2005.
3. “The Entropia Virtual Machine for Desktop Grids”, Brad Calder, Andrew A. Chien, Ju Wang, and Don Yang, in proceedings of ACM/USENIX Virtual Execution Environments 2005 (VEE'05), June 2005.
4. “Tolerating Denial-of-Service Attacks Using Overlay Networks – Impact of Overlay Network Topology”, Ju Wang, Linyuan Lu, Andrew A. Chien, in 2003 ACM Workshop on Survivable and Self-Regenerative Systems, October 2003.
5. "A New Fast Message Passing Communication System for Multiprocessor Workstation Clusters", Jun Shen, Weimin Zheng, and Ju Wang, Parallel and Distributed Computing Practices, Volume 1, No. 4, December 1998.
Abstract of The Dissertation
TOLERATING DENIAL-OF-SERVICE ATTACKS – A SYSTEM APPROACH
by
Ju Wang
Doctor of Philosophy in Computer Science
University of California, San Diego, 2005
Professor Andrew A. Chien, Chair
Proxy network-based defense has recently emerged to address an open research challenge – protecting Internet service applications from Denial-of-Service (DoS) attacks. Such schemes use a proxy network as a mediator for a hidden application to prevent direct attacks on the application’s physical infrastructure, while maintaining communication between users and the application. The proxy network provides a distributed front-end to disperse DoS attack traffic, thereby shielding the application. However, the basic feasibility and fundamental properties of such schemes remain unclear, posing critical challenges for their use.
This dissertation addresses these challenges by exploring proxy networks’ ability to resist important attacks: penetration, proxy depletion, and DoS attacks. We develop a generic analytic framework for proxy network-based systems, and use it to analyze proxy networks’ resilience to penetration and proxy depletion attacks, characterizing how attacks, defenses, proxy network structure, and correlation in host vulnerabilities affect feasibility. Furthermore, using online simulation, we quantify the resistance to DoS attacks at an unprecedented scale and realism, by running real application, proxy network, and attack programs in a simulated network with a size comparable to tier-1 ISP networks.
We show that proxy network-based DoS defense can effectively resist these attacks, and protect applications successfully. Specific results are the following. First, proactive defenses, such as proxy migration, are required for penetration resistance – proxy networks can be effectively impenetrable with proxy migration, but will be penetrated easily without proactive defenses. Second, correlation in host vulnerabilities makes proxy networks vulnerable to penetration. By exploiting host diversity and intelligent proxy network construction, effective resistance can be achieved. Third, topology is crucial for resisting proxy depletion attacks: when a topology’s eigenvalue is smaller than the speed ratio between defense and attack, all compromised proxies will always be recovered; when a topology’s Laplacian spectrum is larger than this ratio, compromised proxies will linger, making the proxy network unrecoverable. Last, proxy networks provide effective and scalable DoS defense. They can resist large-scale DoS attacks, while preserving performance for the majority (>90%) of users. Furthermore, increasing the proxy network size linearly improves the level of resistance to DoS attacks.
Introduction
1 Denial-of-Service Attacks on Internet Service Applications
The past two decades have seen a tremendous growth of the Internet. During this time, a wide variety of Internet service applications, such as search engines (e.g. Yahoo! and Google), online banking (e.g. Bank of America Online Banking and PayPal), online trading (e.g. E*Trade and ScotTrade), online travel agencies (e.g. Expedia and ), and e-Commerce (e.g. Amazon and ) applications, have emerged to become critical parts of today’s society and economy. Studies [1-5] show that the majority of Internet users use Internet service applications in their daily life; for example, 84% of Internet users use search engines, nearly 50% use online banking, and 74% shop online; these numbers are growing quickly. Furthermore, Internet service applications are an important factor in today’s economy and their importance is increasing quickly. Studies [3, 4, 6] show that, in 2004, e-Commerce retail sales and online travel sales in the U.S. combined over $120 billion in revenue; by the year 2007, their revenue is projected to grow to more than $287 billion.
The importance of these Internet service applications makes their resilience to attacks and failures critical. However, studies show that the security and availability of Internet service applications are increasingly threatened by a variety of attacks. According to CERT (Computer Emergency Response Team), the number of attack incidents has grown from only 6 in 1988, to 137,529 in 2003 [7] (see Figure 1-1). Among these incidents, Denial-of-Service (DoS) attacks pose one of the most serious threats to Internet service applications.
[pic]
Figure 1-1 Number of Attack Incidents on the Internet (Reported to CERT)
DoS attacks are malicious attempts aiming to limit or deny service availability to legitimate users. A DoS attack on an Internet service application can be achieved by consuming critical resources (such as network bandwidth, server memory, disk space, or CPU time) on which the application or access to the application depends. Depletion of these resources can prevent the application from functioning, or disconnect the application from the Internet, and thus make the application unavailable to its users. A DoS attack occurs either at the infrastructure-level by attacking the resources directly (e.g. by flooding the application’s sub-network with IP packets), or at the application-level by attacking through the application interface (e.g. by overloading the application with abusive workload). In a typical DoS attack, an attacker first compromises a number of hosts (chosen from the hundreds of millions of vulnerable hosts) in the Internet, and then instructs these compromised hosts to attack an application by sending either infrastructure-level or application-level attack traffic to it (Figure 1-2). The recent emergence of sophisticated attacks tools, such as Trinoo [8], mstream [9], and TFN2K [10], and of Internet worms, such as CodeRed [11, 12], slammer [13], and MyDoom [14] – which automate the process of compromising hosts – makes it possible for attackers to control a large number (tens of thousands or even millions) of Internet hosts. These hosts can then be used to generate attack traffic, and to construct massive distributed DoS attacks, which can generate sufficient traffic to saturate even the largest Internet service applications. Therefore, such DoS attacks are a great threat to the availability of all Internet service applications.
[pic]
Figure 1-2 Denial-of-Service Attack
The real-world impact of these DoS attacks is severe. For example, in 1999, a series of large-scale DoS attacks targeted popular Internet service applications, such as Yahoo!, Amazon, eBay, and [15, 16]. These attacks kept the target sites offline for several hours, causing millions of dollars in lost revenue. In 2001, the “Code Red” and “Code Red II” worms spread widely in the Internet as part of a distributed DoS attack on the White House web site, forcing it to relocate [11]. In 2003, a series of large-scale DoS attacks using Internet worms caused outages at Microsoft’s website [13] and SCO Group’s website [14]. According to a survey [17] of 251 organizations conducted by Computer Security Institute and the FBI, DoS attacks were the second-most costly computer crime, with a damage exceeding 65 million dollars in 2003. These incidents and statistics show that DoS attacks have a serious economic and social impact.
Furthermore, DoS attacks are widespread in the Internet. In an attempt to characterize the frequency of DoS activities on the Internet, researchers at UCSD and CAIDA (the Cooperative Association for Internet Data Analysis) used backscatter detection techniques to infer DoS activities [18]. Their results reported more than 12,000 DoS attacks on more than 5000 targets during a span of three weeks, in February 2001. The victims of these attacks span the entire spectrum of commercial business sites, such as Yahoo!, CNN, as well as many small businesses. These numbers indicate that DoS attacks are common in the Internet, and that any Internet service application can become a victim of such attacks.
Since DoS attacks pose a critical threat to Internet service applications, researchers are exploring a wide range of defenses. As system researchers, our focus is infrastructure-level attacks, since these attacks target service infrastructures, and should be addressed at the system level. Application-level attacks are specific to the detailed structure of application interfaces, properties, and configurations, and thus can only be addressed by application designers. Existing system-level defense mechanisms [19-21] aim at blunting infrastructure-level DoS attacks[1] by filtering the attack traffic. These schemes use routers to filter all the incoming network packets, and discard packets suspected to be part of an attack.
However, accurately distinguishing attack and normal packets is difficult, and increasingly so, as attack sophistication increases. As a result, these filter-based defenses are typically based on specific attack details, and do not apply generally to DoS attacks. For example, common methods use details of network packets, such as protocols (e.g. UDP or ICMP packets), the destination port, and source IP addresses [19-24], to identify attack packets. This lack of generality poses a fundamental limitation on their effectiveness.
Furthermore, in order for filter-based defenses to be effective, they must be deployed globally and in the basic Internet infrastructure of routers, since the attack traffic can come from millions of hosts dispersed across the Internet. Partial deployment leaves vast resources that can be used by attackers to generate devastating attack traffic which will saturate Internet service applications.
In summary, protecting Internet service applications from DoS attacks is a critical issue for Internet service applications. The current defense mechanisms are primarily based on filtering. They cannot protect applications from DoS attacks in general because they rely on specific attack details. Furthermore, they require global deployment with the basic Internet infrastructure. Due to these limitations, the filter-based defense mechanisms do not provide a general solution to the problem of protecting Internet service applications from DoS attacks. In the following section, we consider an alternative approach.
2 Proxy Network-based DoS Defense
Recently, researchers have proposed the use of proxy networks as a system-level defense that protects Internet service applications from infrastructure-level DoS attacks [25-29] [30-35]. This new scheme does not suffer from the limitations of existing DoS defense mechanisms, and has shown promise in protecting applications’ availability from DoS attacks. It is an attractive approach for DoS defense.
[pic]
Figure 1-3 Proxy Network-based DoS Defense
A proxy network (Figure 1-3) is an overlay network composed of interconnected proxies which run on hosts dispersed across the Internet. In a proxy network-based DoS defense, a proxy network is used as an application mediator, delivering application messages between the application and its users. As shown in Figure 1-3, on one side of the proxy network, a set of proxies (known as application proxies) are connected to the application; on the other side of the proxy network, a select set of nodes (known as edge proxies) publish their IP addresses, providing application access to users.
Proxy network-based DoS defense is based on two key ideas. First, a proxy network mediates application messages between users and the application, providing the only public interface for application access. Since the proxy network delivers only application messages, this prevents direct infrastructure-level DoS attacks on the application. Second, the proxy network presents a broad public access by using a large number of edge proxies. This broad front disperses the attack traffic, and dilutes the impact of even distributed DoS attacks.
Proxy network-based DoS defense has shown promise in accomplishing these key ideas, for the following reasons. First, an application is protected by a series of proxy indirections, all of which must be compromised by attackers to expose the application to direct attacks. Because the number of indirections can be adjusted by reconfiguring the proxy network, it provides a flexible structure for resisting an attacker’s penetration and protecting the application from direct attacks. Second, the edge proxies can be widely dispersed, making it difficult for attackers to saturate all of them, and thereby, interrupt application service. This allows proxy networks to tolerate DoS attacks by dispersing attack traffic. By mediating application access to prevent direct attacks, and by providing a DoS-resilient front-end for the application to dilute the impact of attacks, a proxy network has the potential to protect the application from DoS attacks.
Furthermore, besides its potential to protect an application’s availability, a proxy network-based DoS defense has shown promise for large-scale deployment. Since proxy networks are application-level overlay networks built on top of the Internet, they do not require any modification to the existing Internet infrastructure. This greatly facilitates large-scale deployment of proxy networks. Success of large-scale proxy networks, such as Content Delivery Networks (e.g. Akamai [36] proxy network which has over 15,000 proxies deployed in over 1,200 networks across 65 countries), demonstrates the practical feasibility of large-scale deployment of proxy networks.
In short, proxy network-based DoS defense is an attractive scheme for protecting Internet service applications from DoS attacks. It does not have the limitations of the existing DoS defense mechanisms. By mediating application access to avoid direct DoS attacks, and by providing a distributed front-end to shield the application from DoS attacks, a proxy network-based DoS defense shows promise in protecting an application’s availability from DoS attacks. Furthermore, it is feasible to deploy a proxy network-based DoS defense scheme at the Internet-scale, providing a global DoS defense for Internet service applications in practice. Thus, this scheme has the potential to provide a feasible solution to protect Internet service applications from DoS attacks.
3 Challenges
Although a proxy network-based DoS defense shows promise as an effective solution to DoS attacks, little is understood about the basic properties of this scheme, and how it should be designed. Fundamental questions remain: can a proxy network-based DoS defense resist possible attacks, and protect an application’s availability? In particular, can a proxy network prevent attackers’ penetration, thereby preventing direct DoS attacks on the application? Can a proxy network protect an application’s performance from DoS attacks, thereby shielding the application from DoS attacks? The answers to these questions address the basic feasibility of proxy network-based DoS defense. A thorough study of these problems will also provide insight on how to design such defense systems.
To answer these questions, we need to understand a proxy network’s resistance to possible attacks. Specifically, we exclude non-technical attacks (e.g. social engineering) and broad attacks on the resource pool (e.g. Internet worms crippling the whole Internet infrastructure), since such attacks operate in a space separate from proxy networks. We can classify the technical attacks on proxy networks into three types: penetration attacks, proxy depletion attacks, and DoS attacks.
First, penetration attacks compromise proxies along a path in a proxy network towards the application, in order to penetrate the proxy network and to expose the application to direct attacks. Therefore, a basic feasibility question for the proxy network-based DoS defense is whether a proxy network is capable of resisting penetration attacks. Specifically, how much time is required to penetrate a proxy network? What defensive mechanisms are required to enable effective defense?
Second, proxy depletion attacks compromise proxies along the proxy network topology, in order to control all the proxies, thereby disabling the proxy network. To be a stable defense system, a proxy network must be recoverable under proxy depletion attacks; that is, the proxy network must be able to recover all the compromised proxies, regardless of how many proxies are compromised initially. In short, a recoverable proxy network can remove the effect of any attack progress. Therefore, a basic question is under what circumstances a proxy network can be recoverable under proxy depletion attacks.
Third, DoS attacks flood the infrastructure around edge proxies with network traffic in order to saturate them, thereby denying user access to the proxy network. A proxy network must be able to support continued user access under such attacks. Specifically, we ask critical questions about the effectiveness and scalability of a proxy network’s resilience to DoS attacks. How well can a proxy network protect an application’s performance from DoS attacks? Can a proxy network’s resistance to DoS attacks be increased by increasing its size? Can this resistance be used to resist stronger DoS attacks?
So far, the research community’s understanding of these problems has been limited. Existing studies [25-32] on proxy network-based DoS defense are limited to specific instances of proxy networks. There has been no systematic exploration of the fundamental properties of a general class of proxy network-based DoS defense schemes. Furthermore, existing studies do not address important attack scenarios, including penetration attacks and proxy depletion attacks; their analysis of DoS attacks is based on simple models, which do not capture network dynamics critical to application performance, and therefore provide only limited insight. As a result, whether or not a proxy network can resist attacks and protect an application’s availability remains an open research problem.
4 Thesis and Approach
Our research studies the feasibility of the proxy network-based DoS defense by exploring a proxy network’s ability to resist attacks. The thesis of our study is best stated as follows:
By hiding applications from penetration attacks and providing a stable and DoS-resilient front-end, proxy networks can effectively protect an application from a range of infrastructure-level DoS attacks. Specifically, a proxy network can be used as an application mediator, forming a barrier against penetration attacks and thereby protecting the application from direct attacks. Moreover, a proxy network can effectively resist proxy depletion attacks by removing the impact of attack, thereby providing a stable defense. Furthermore, a proxy network can effectively resist infrastructure-level DoS attacks by dispersing the attack traffic among a distributed front-end and diffusing the impact of DoS attacks, thereby enabling continued application service.
The thesis addresses the fundamental properties of the proxy network-based DoS defense by characterizing a proxy network’s resistance to three important classes of attacks: penetration attacks, proxy depletion attacks, and infrastructure-level DoS attacks. Resisting these attacks allows a proxy network to protect applications from DoS attacks effectively. We use the following approaches to study a proxy network’s resistance to these attacks, and thus prove the thesis.
In order to study a general class of proxy networks, we develop a generic framework which encompasses a wide range of proxy network-based DoS defense. The framework defines key components of a proxy network system, and describes how attacks and defenses change the system state. It enables rigorous study of a large class of proxy networks, with results that bear on the entire class. Based on the generic framework for proxy network schemes, we develop a stochastic model to characterize how attacks and defenses change the state of system components quantitatively, thereby allowing for a rigorous study of system dynamics as a function of attacks and defenses. This generic framework and stochastic model provides a basis for our study of both penetration attacks and proxy depletion attacks.
1 Resistance to Penetration Attacks
Based on the generic framework and stochastic model, we combine analysis with Monte Carlo simulation techniques to study how long it takes a penetration attack to penetrate a proxy network. We study when a proxy network can resist penetration attacks for a long period of time, making such attacks practically impossible. We also study the impact of key system parameters on a proxy network’s resistance to penetration attacks, and identify the key system requirements for achieving effective defense.
2 Resistance to Proxy Depletion Attacks
We use the generic framework and stochastic model described earlier to characterize the impact of proxy depletion attacks on a proxy network system. Based on the framework and model, we study system dynamics as a function of attacks and defenses. We analyze when a proxy network can remove all the compromised proxies, regardless of how many proxies are compromised initially. This way, we characterize the circumstances when a proxy network can resist proxy depletion attacks effectively, and when it cannot. From these results, we develop guidelines for proxy network design.
3 Resilience to DoS attacks
We study the properties of proxy networks under DoS attacks empirically, using online packet-level network simulation with full applications, a real software implementation of proxy network, and real attacks. In particular, our experiments are performed using a large-scale online simulator – MicroGrid [37] which enables packet-level accurate simulation of large-scale network environments with 10,000 routers and 40 Autonomous Systems (ASes). These network sizes are comparable to a large ISP network. Furthermore, Microgrid supports direct execution of unmodified application binaries, and thus allows us to use real applications and a real proxy network implementation in the simulation. In our study, we build a DDoS zombie network (comparable to one which contains 10,000 zombies with DSL or cable modem connections) with a real DoS attack toolkit [8], and use the zombies to generate attack traffic. Total attack traffic intensities up to 6.4Gbps, and a wide range of DoS attack scenarios are explored.
This experimental configuration is large and real enough to capture key properties of the Internet environment and application dynamics, such as router queues, packet drops, real temporal and feedback behavior of network and application protocols, which are critical to the application behavior and performance under DoS attacks. Therefore, this approach enables accurate modeling of the full complexity of network and application behavior needed to reproduce DoS dynamics, and to characterize application and proxy network performance in varied attack scenarios. With this leverage, we study application performance delivered by a proxy network for a range of proxy network structures and attack scenarios.
5 Contributions
The primary contribution of our work is to be the first systematic evaluation of the use of proxy networks for protecting Internet service applications from DoS attacks. This study includes a thorough evaluation of proxy networks’ resistance to three important technical attacks: penetration attacks, proxy depletion attacks, and DoS attacks, providing a basic understanding of the fundamental capabilities and viability of proxy network-based DoS defense. The specific contributions of the dissertation are summarized below:
1) To define a novel, generic analytic framework for proxy network-based DoS defense, which provides a basis for systematic exploration of a proxy network’s resistance to penetration and proxy depletion attacks. This framework defines a canonical set of elements and their interactions in proxy network-based DoS defense, as well as a set of stochastic models to characterize system dynamics.
2) To identify the key system requirements for effective resistance to penetration attacks. We prove that proactive defenses, such as proxy migration, are required for resisting penetration attacks. Without such mechanisms, a proxy network will be penetrated in time which grows linearly with its depth[2]. With proxy migration, the time to penetrate a proxy network grows exponentially with its depth, thus making proxy networks of modest depths effectively impenetrable. For example, with realistic assumptions, it might take thousands of years to penetrate a proxy network of depth six.
3) To quantitatively characterize a proxy network’s ability to resist penetration attacks in systems with correlated host vulnerabilities. First, we show that if host vulnerabilities are correlated, attackers can easily penetrate a proxy network. Second, we show that, by exploiting the host (OS/software) diversity and intelligent proxy network construction, the resistance can be improved dramatically, enabling proxy networks to resist penetration attacks effectively.
4) To prove two theorems that characterize the circumstances when proxy networks can stably defend against proxy depletion attacks. The first theorem shows that, when the eigenvalue of a proxy network’s topology is smaller than the ratio between the defense speed and the attack speed, the proxy network can always recover all the compromised proxies. The second theorem shows that, when a function of the Laplacian spectrum of a proxy network’s topology is larger than the ratio between the defense speed and the attack speed, compromised proxies will linger, and the proxy network will be unable to recover from proxy depletion attacks.
5) To derive a set of design guidelines for when proxy networks can effectively resist proxy depletion attacks. Specifically, proxy network topologies with low vertex degrees and balanced distribution of connectivity (no tightly connected sub-graphs) are favorable for supporting effective defense against proxy depletion attacks; topologies with high vertex degrees or large clusters of tightly connected nodes are unfavorable.
6) To present a case study on popular proxy network topologies, which shows that Chord [38], a widely-used proxy network topology [25, 26, 28, 29], is unfavorable for resisting proxy depletion attacks; in contrast, 2D-CAN [39] and binary de Bruijn graphs [40] are better topologies for resistance to proxy depletion attacks.
7) To quantitatively characterize proxy networks’ resistance to DoS attacks using online simulation at an unprecedented scale and realism. Our experiments use real applications and real attack programs in a simulated large-scale network of 10,000 routers and 40 Autonomous Systems. This network is comparable in scale to a Tier-1 ISP network [37, 41, 42]. The simulation includes a large DoS attack network, comparable to one having 10,000 hosts with DSL connections, producing attack traffic intensities up to 6.4 Gbps.
8) To demonstrate via simulation that proxy networks can provide both effective and scalable defense for applications against DoS attacks. Our studies show that a 192-node proxy network with 64 edge proxies (each connected by a 100Mbps uplink) can successfully resist a range of large-scale distributed DoS attacks with up to 6.0Gbps aggregated traffic and several different attack distributions. The majority (>90%) of users do not experience significant performance degradation under these attacks. We also demonstrate that by increasing the proxy network size, we linearly increase the level of resistance to DoS attacks, while preserving application performance.
6 Organization
The remainder of the dissertation is structured as follows. Chapter 2 presents the requisite background information needed to understand this dissertation work and to put it in context. Chapter 3 formulates the precise problem we are addressing, and gives our thesis statement. Chapter 4 describes the high-level approach. Chapter 5, 6, and 7 present our study of proxy networks’ resistance to penetration attacks, proxy depletion attacks, and DoS attacks respectively. Finally, Chapter 8 summarizes our research and discusses avenues for future work.
Background
This chapter provides background on the use of proxy networks for protecting Internet service applications from Denial-of-Service (DoS) attacks by describing DoS attacks on Internet service applications, and the proxy network-based DoS defense. Section 2.1 describes DoS attacks on Internet service applications and surveys existing defense mechanisms, showing that protecting Internet service applications from DoS attacks remains an important, open research challenge. Section 2.2 describes the proxy network-based DoS defense scheme, which has recently emerged, and shows promise in solving the DoS problem. We summarize the current limited understanding and outstanding questions.
1 DoS Problem for Internet Service Applications
We focus on how to protect Internet service applications from DoS attacks because such attacks continue to be a major security threat to Internet service applications, a critical part of today’s economy and society. This section describes DoS attacks on Internet service applications and state of art defense mechanisms against DoS attacks. In the following, we first describe Internet service applications, and then define DoS attacks and discuss their impact; finally, we survey the existing defense mechanisms and point out their key limitations.
1 Internet Service Applications
[pic][pic]
Figure 2-1 Internet Service Application (Left: Deployment, Right: Model)
During the past two decades, along with the tremendous growth of the Internet, various Internet service applications, such as search engines, e-Commerce sites, and online banking, have emerged as indispensable parts of today’s society and economy. Security and availability of these applications are critical components of a stable Internet. Our research focuses on protecting these applications from DoS attacks (described in Section 2.1.2). In this section, we define the application model, describe the key properties of these applications, and discuss the unique challenges and opportunities in protecting these applications.
An Internet service application is the server program of a client-server application operating over the Internet. It provides certain services (e.g. web search) to users running application client programs (e.g. a web browser). The client programs access the server based on a well-defined application-level protocol. Two important properties of Internet service applications are relevant to our research:
1. Localized deployment: As shown in Figure 2-1, Internet service applications typically run on server clusters localized in collocation facilities, or data centers. This simplifies the design and maintenance of Internet service applications. However, the localized deployment limits the scale and number of (network, CPU, storage) resources available to the applications, making it possible for attackers to consume all of the server resources and deny application service. How to protect applications from such attacks without changing their localized deployment is a key challenge.
2. Well-defined application level protocol: in the Internet service application model (shown in Figure 2-1), the Internet acts as a communication layer used to convey a well-defined application-level protocol between an application and it users. So it is possible to differentiate application messages from other traffic using a mediator, preventing attack traffic from reaching the application. This provides a basis for the proxy network-based DoS defense (see Section 2.2) studied in this dissertation.
2 Denial-of-Service Attacks
A DoS attack is characterized by an explicit attempt to prevent legitimate users of a service from using that service. A DoS attack on an Internet service application can be achieved by consumption of scarce, limited, or non-renewable resources on which the application (or access to the application) depends. These resources may include network bandwidth, server memory, disk space, CPU time, and access to other computers and networks. Depletion of these resources can prevent the application from functioning or disconnect the application from the Internet, thereby causing service disruption and, thus, making the application unavailable to its users.
The impact of DoS attacks is severe. For example, DoS attacks have shut down high-profile sites, such as Yahoo!, Amazon, EBay and [15, 16], causing millions of dollars in lost revenue. A range of DoS attacks in recent years [11-14] disrupted the websites of the government and high-profile companies (such as Microsoft and ), causing a significant social impact. According to a survey [17] collected from 251 organizations, DoS attacks were the second-most expensive computer crime, with a cost of more than 65 million dollars, in the year 2003.
Furthermore, DoS attacks are a widespread phenomenon in the Internet. For example, studies [18] reported more than 12,000 DoS attacks on more than 5000 targets during the short span of three weeks in February 2001. The victims of these attacks span the entire spectrum of commercial business sites, such as Yahoo!, CNN and many small businesses.
In conclusion, DoS attacks are a major threat to Internet service applications. They are widespread in the Internet, threaten the availability of various Internet service applications, and cause significant economic and social impact. Therefore, protecting Internet service applications from DoS attacks is an important problem.
In the following, we first classify DoS attacks according to their high-level approaches because each approach presents a unique set of problems; then, we describe how DoS attacks are constructed.
1 Classification of Denial-of-Service Attacks
DoS attacks on an Internet service application can be achieved either by directly attacking the resources on which the application (or access to the application) depends, or by attacking through the application interface. We classify DoS attacks as infrastructure-level and application-level attacks, according to these high-level approaches. Infrastructure-level attacks target the service infrastructure resources directly, such as the networks and hosts of the application; for example, by sending floods of network traffic to saturate the victim network, attackers can disconnect the application from its users. In contrast, application-level attacks exploit an application’s weaknesses via the application interface; for example, by overloading the application with an abusive workload, attackers can make the application unavailable to legitimate users.
Infrastructure-level and application-level DoS attacks are fundamentally different. Infrastructure-level attacks focus on the service infrastructure resources (e.g. hosts and network), regardless of the application running on that infrastructure; the details of the application are irrelevant to such attacks. In contrast, application-level attacks focus on the weaknesses of the application, regardless of the service infrastructure the application uses; the details of the application are critical to these attacks.
This distinction makes defense against infrastructure-level and application-level DoS attacks fundamentally different problems. The key challenge in defending against infrastructure-level attacks is building a system to protect the service infrastructure. In contrast, the key challenge in defending against application-level attacks is making an application robust. Since each application is unique, this is an application-specific problem, and there are no system-level solutions. As system researchers, we focus on infrastructure-level DoS attacks and explore system-level solutions that protect Internet service applications from infrastructure-level DoS attacks. We leave application-level DoS attacks for application designers to solve.
2 Construction of Denial-of-Service Attacks
In this subsection, we explain how Denial-of-Service attacks are constructed. Attackers can use a varied number of hosts, ranging from a single host to millions of hosts dispersed in the Internet, to construct a DoS attack. We focus on attacks that can use many hosts, because solutions to such attacks typically apply to attacks using fewer hosts. In particular, we describe distributed DoS (DDoS) attacks, a common DoS attack scheme that can use a large number of hosts.
[pic]
Figure 2-2 A Typical DDoS Zombie Network
Construction of a DDoS attack has two stages. First, attackers build a zombie network by compromising many Internet hosts and installing zombie programs on each; the zombie programs are controlled by attackers. Second, attackers activate this large zombie network, directing them to attack a victim. Figure 2-2 shows a typical zombie network used in DDoS attacks. There are two types of zombies: daemons which generate attack traffic, and masters which activate and control the daemons. An attacker can control many masters, each of which in turn controls a large number of daemons. This hierarchical structure allows an attacker to control a DDoS network with a large number of zombies.
Automated DDoS toolkits such as Trinoo, TFN2k and mstream [8-10] and worms such as CodeRed and slammer [11-13] automates the process of compromising vulnerable Internet hosts, enabling attackers to control a large number (e.g. tens of thousands, or even more) of hosts. This capability increases the scale of DoS attacks dramatically, bringing significant challenges to the defense. First, it allows an attacker to generate enough traffic to saturate large network links (e.g. ten thousand hosts with DSL links can generate multi-Gigabits per second attack traffic). Therefore, attackers can disconnect the whole sub-network of the application from the Internet, making all localized defense schemes ineffective. Second, the attack traffic can come from a large number of hosts dispersed all over the Internet. Therefore it is difficult to prevent the attack traffic by blocking all the sources.
3 Defense of Denial-of-Service Attacks
How to protect Internet service applications from DoS attacks is an open research question. Existing defense mechanisms try to prevent DoS attacks by filtering the attack traffic at the router level [19-24, 43-45]. They use filters implemented inside routers to examine all the incoming network packets, and discard the suspected attack packets.
However, accurately distinguishing attack and normal packets is difficult, and increasingly so, as attack sophistication increases. As a result, these filter-based defenses are typically based on specific attack details, and do not apply generally to DoS attacks. Common methods use details of network packets or the source IP addresses to identify attack packets. We briefly describe these approaches and discuss their limitations.
Schemes using details of network packets to identify attack traffic include type-based filtering schemes [20, 21, 45-51] and ingress/egress filtering schemes [19, 52]. Type-based filtering schemes treat a specific type of packets as attack traffic. For example, based on known patterns of attack traffic, these schemes filter all packets of a specific protocol (e.g. UDP and ICMP), packets with a particular destination port, or packets that follow a particular statistic pattern. Ingress and egress filtering schemes treat all packets with forged source addresses as attack traffic, since some attacks use such packets. When these schemes are globally deployed on all the routers in the Internet, they can prevent attacks that match the specific filtering criteria. However, these schemes are attack-specific; they cannot apply to DoS attacks in general.
Some schemes [22-24, 43, 44, 53-57] use a packet’s source IP address to identify attack traffic. These schemes select the sources that send traffic to the victim at a high rate, and block all the packets from those sources. Such schemes are effective against small-scale DoS attacks which use only a handful of hosts because the traffic rate from each attack source is prominently high. However, in a large-scale DoS attack using many hosts, it is difficult to identify the sources of the attack traffic because the traffic rate from each source can be low enough to avoid suspicion, but the aggregated attack traffic rate can still be devastating. Therefore, these schemes have serious limitations against large-scale distributed DoS attacks.
In addition, these schemes require global deployment and modification in the basic Internet infrastructure, since they aim at filtering attack traffic from its sources at the router level, and the attack traffic can come from millions of hosts dispersed all over the Internet. A partial deployment of these defense mechanisms still leaves enough resources for attackers to generate a large amount of attack traffic, thereby providing little defense. In practice, this poses a challenge for their use.
4 Summary
To summarize, Denial-of-Service attacks are an important threat to Internet service applications. Current defense mechanisms have critical limitations: they are attack-specific and do not protect applications from DoS attacks in general; in practice, they are also difficult to deploy. Therefore current defense mechanisms do not provide an effective solution to the DoS problem. This problem remains an open research challenge. In Section 2.2, we introduce a newly emerged scheme to address this problem – the proxy network-based DoS defense.
2 Proxy Network-Based DoS Defense
Recently, researchers proposed the use of proxy networks as a system-level defense that protects Internet service applications from DoS attacks [25-29] [30-34]. This new scheme uses a proxy network to mediate the communication between an application and its users, thereby shielding the application from DoS attacks. This scheme is attractive because it has the potential to protect applications from general DoS attacks, and it requires no changes to the basic Internet infrastructure, thereby facilitating its large-scale use in practice.
However, the research community’s understanding of these problems has been limited and incomplete. Existing studies [25-29] on proxy network-based DoS defense are confined to specific implementations of proxy networks. There has been no systematic exploration of the fundamental properties of a general class of proxy network-based DoS defense schemes. Furthermore, existing studies do not address important attack scenarios, and their analysis is based on simple models, which do not capture system dynamics critical to application performance. As a result, these studies provide only limited insight. The fundamental problem of whether a proxy network can resist attacks and protect an application’s availability remains an open research challenge. Solving this problem can fundamentally improve our defensive capability against DoS attacks.
This section describes the proxy network-based DoS defense, discusses the known properties of this scheme, and points out the key unsolved issues. Section 2.2.1 introduces the basics of overlay networks, as the proxy network-based DoS defense is a specific use of overlay networks. Section 2.2.2 defines the proxy network-based DoS defense; section 2.2.3 discusses possible attacks on a proxy network-based DoS defense; and Section 2.2.4 surveys defensive mechanisms that a proxy network can use to resist these attacks. Finally, Section 2.2.5 describes implementations of the proxy network-based DoS defense and discusses what is known and what remains unclear.
1 Basics of Overlay Networks
An overlay network is a network of interconnected nodes built on top of an existing network. The connections between overlay nodes are logical connections, not physical links. Typically, an overlay network is built on top of the Internet with nodes running on a set of Internet hosts, acting as a higher-level communication layer with new capabilities. Figure 2-3 illustrates a typical overlay network. Each overlay node is a software program that runs on an Internet host. These nodes connect to each other (e.g. via TCP connections) to form an overlay network, which can be used as an application-level communication layer to provide applications with new capabilities. For example, overlay networks have been used to support efficient multicast [58-66], mobility [67-69], data sharing [70-76], increase reliability [59, 73, 77-83], and enhance security [25-29, 68, 84, 85]. Among these uses, our research focuses on the use of overlay networks for protecting Internet service applications from DoS attacks.
[pic]
Figure 2-3 Illustration of an Overlay Network
An overlay network has three key properties: topology, routing, and deployment. Topology is the most important property of an overlay network relevant to our research. It defines how overlay nodes are connected to one another. Specifically, an overlay topology can be represented by a graph, where vertices represent overlay nodes, and edges represent the connections among the nodes. Topology has critical impacts on many important characteristics of an overlay network. For instance, studies [86, 87] have shown that topology has critical impacts on performance and fault tolerance of an overlay network. More importantly, as we will see in this dissertation, when an overlay network is used for DoS defense, its topology has a critical impact on its resistance to important attacks (see Chapter 6 for details).
Overlay network routing protocol determines how a message is routed from one overlay node to another along a path in the overlay network topology. Specifically, a routing protocol is a set of rules the overlay nodes use to determine the appropriate path onto which a message should be forwarded. An overlay network can use different routing protocols to support communication between overlay nodes.
Overlay network deployment defines the mapping between overlay nodes and the underlying Internet hosts. Specifically, it defines which overlay node runs on which Internet host. The deployment of an overlay network determines the latency and bandwidth between connected overlay nodes, thereby affecting the overall performance (e.g. latency, bandwidth) between any pair of overlay nodes.
2 Definition of Proxy Network-based DoS Defense
A proxy network is an overlay network that serves as an application mediator to support communication between an application and its users. In our research, we study proxy networks that are used to protect Internet service applications from infrastructure-level DoS attacks. As shown in Figure 2-4, the application is hidden behind the proxy network which mediates the application messages between the application and its users. On one side of the proxy network, a set of proxies (known as application proxies) are connected to the application; on the other side of the proxy network, a select set of nodes (known as edge proxies) publish their IP addresses providing access to users of the application. In this way, users access the edge proxies to communicate with the application via the proxy network. To ensure that the proxy network is the only public interface for the application, the application either has a secret IP address or resides behind a distributed set of filters which blocks all packets except for those coming from the application proxies.
[pic]
Figure 2-4 Proxy Network-based DoS Defense
The proxy network operates in a large resource pool of tens of thousands or even millions of Internet hosts. Existing infrastructure of large-scale distributed systems, such as content delivery networks and peer-to-peer systems, demonstrate the feasibility of such a large resource pool. For example, the Akamai network has over 15,000 servers deployed in over 1,200 ISP networks in 65 countries [36]; peer-to-peer overlay systems, such as Skype [88] and BitTorrent [89], operate continuously with millions of hosts online, and hundreds of millions of participant nodes in total. Such large resource pools amassed by Skype for VoIP relay and BitTorrent for file serving provide an massive server infrastructure to support large overlay systems. Furthermore, the number of Internet hosts is increasing rapidly, thus the size of the resource pools that can be built will increase accordingly in the near future. Therefore, the proxy network-based DoS defense system which depends on having a resource pool of millions of hosts appears reasonable.
Proxy network-based DoS defense has two key ideas. First, a proxy network provides the only public interface for application access, so that DoS attackers cannot attack the application directly. Second, the proxy network shields the application from DoS attacks by providing a large number of front-ends (edge proxies) for the application to disperse attack traffic and dilute the impact of attacks. In this way, the proxy network-based DoS defense has the potential to protect application availability from DoS attacks.
Furthermore, proxy networks are also promising for large-scale deployment. Since proxy networks are application-level overlay networks, they do not require any modification to the existing Internet infrastructure. This greatly facilitates large-scale deployment of proxy networks; for example, a variety of overlay networks, such as Skype [88] and BitTorrent [89], have been successfully deployed on millions of hosts in the Internet. Since the proxy network-based DoS defense is promising for protecting application availability and feasible for large-scale deployment, it has the potential to have a qualitative advance over existing DoS defense mechanisms, and provide a feasible solution to protect Internet service applications from DoS attacks.
3 Attacks on Proxy Network-based DoS Defense
There are three high-level strategies to attack the proxy network-based DoS defense. First, attackers can compromise the application proxies. Since application proxies connect to the application directly, compromising them enables attackers to bypass the proxy network and expose the application to direct attacks. Second, attackers can make the proxy network dysfunctional, preventing it from mediating communication between users and the application. Third, attackers can make the proxy network inaccessible to users, thereby denying users application access.
Corresponding to these high-level strategies, there are three important classes of technical attacks against the proxy network-based DoS defense: penetration attacks, proxy depletion attacks, and DoS attacks. Penetration attacks attempt to compromise proxies along a path in a proxy network towards the application, thereby penetrating the proxy network, and eventually compromising an application proxy, exposing the application to direct attacks. Proxy depletion attacks compromise proxies along a proxy network’s topology, thereby increasing the number of compromised proxies, and eventually disabling the proxy network. DoS attacks attempt to flood the infrastructure around edge proxies with network traffic, in order to saturate them, thereby preventing communication between users and the application. In addition to these three attacks, attackers can also make the proxy network dysfunctional by exploiting weaknesses specific to a particular implementation of proxy network-based DoS defense. We do not focus on such attacks because they do not apply to the proxy network-based DoS defense in general.
Penetration attacks, proxy depletion attacks, and DoS attacks on proxy networks are further studied in this dissertation. Here we describe the low-level mechanisms used to implement these attacks. The low-level mechanisms used in DoS attacks on proxy networks are the same as those described in Section 2.1.2. The low-level mechanisms used in penetration attacks and proxy depletion attacks are “host compromise attacks”, which can compromise proxy nodes.
A host compromise attack is characterized by an explicit attempt by attackers to gain unauthorized control over a computer system. A host compromise attack can be achieved by using password attacks [90], Trojan horse programs [90], or buffer overflow mechanisms [90, 91]. A successful host compromise attack allows attackers to gain unauthorized access to files, monitor network communication, and run or kill arbitrary programs on the victim system. Therefore, attackers can use these attacks to compromise proxy nodes, preventing them from functioning. Furthermore, compromising a proxy node also allows attackers to discover the IP addresses of all other proxies communicating with it. Due to these impacts, host compromise attacks can be used to construct penetration attacks and proxy depletion attacks.
4 Mechanisms Used to Protect Proxy Network-based DoS Defense
The high-level defense scheme used by proxy networks to resist penetration attacks and proxy depletion attacks is proxy network reconfiguration. Proxy network reconfiguration schemes dynamically change a proxy network’s structure or proxies’ location, in order to invalidate the information acquired by attackers. By doing this, proxy networks can disrupt both penetration attacks and proxy depletion attacks. Proxy network reconfiguration schemes include dynamic change of a proxy network’s topology and proxy migration. In the former case, a proxy network’s topology is changed dynamically, so that a compromised proxy is disconnected from the rest of the network, thereby preventing the progress of attacks which propagate along the proxy network topology. In the latter case, proxies migrate among Internet hosts; a proxy can thus escape to a new location unknown to attackers, after its IP address is discovered by attackers, thereby retracting the attackers’ progress. Both schemes can disrupt the propagation of penetration attacks and proxy depletion attacks by invalidating the structure and location information acquired by attackers.
The low-level defense mechanism used by proxy networks to address host compromise attacks is resource recovery. Resource recovery mechanisms eliminate attackers’ control on compromised hosts and proxies; they also prevent future attacks that exploit the same vulnerabilities of the host. There are three levels of resource recovery mechanisms against host compromise attacks: preemptive defense, detection, and recovery. Preemptive defense schemes prevent hosts from being compromised; examples of preemptive defense schemes include patch management [90, 92, 93], safe runtime systems [94-97], and firewalls [90]. Detection schemes detect on-going host compromises; they can be used to trigger other defensive mechanisms in order to mitigate, contain, and remove the impact of attacks; examples of intrusion detection systems include [98-108]. Recovery schemes remove the impact of host compromises, and return a compromised host to a clean state; examples of recovery mechanisms include termination of compromised processes, removal and replacement of infected software components, clean reload of system images, revocation of suspected user accounts, and so on. Recovery mechanisms are typically combined with installation of up-to-date software patches to set the system into a state without known vulnerabilities. They can be triggered by intrusion detection systems, or be applied periodically. Preemptive defense, detection, and recovery schemes are used together to counter host compromise attacks.
5 Understanding of Proxy Network-based DoS Defense
So far, there are two implementations of proxy network-based DoS defense: Secure Overlay Services (SOS) and Internet Indirection Infrastructure (i3). Studies have explored some properties of these implementations and evaluated their potential for DoS defense. In this subsection, we describe these proxy network implementations, and summarize our current understanding of proxy network-based DoS defense.
1 Implementations of Proxy Network-based DoS Defense
Secure Overlay Services (SOS) [26] is an implementation of proxy network-based DoS defense. As shown in Figure 2-5, SOS uses the Chord [38] overlay network to mediate all traffic between users and applications and to protect applications from DoS attacks. On one side of the Chord network, a set of overlay nodes known as “access points” publish their IP addresses and provide users access to the application. On the other side of the Chord network, a set of overlay nodes known as “servlets” connect to the application. Application-level traffic between users and applications is mediated through the Chord network via the access points and the servlets. Furthermore, filters are used around the application to ensure that only traffic from the servlets can reach the application, thereby preventing direct infrastructure-level DoS attacks against the application.
[pic]
Figure 2-5 Secure Overlay Services (SOS)
Internet Indirection Infrastructure (i3) [28] is another implementation of proxy network-based DoS defense. As shown in Figure 2-6, i3 uses the Chord overlay to protect applications from infrastructure-level DoS attacks by means of rendezvous-based indirect communication. On one side of the Chord network, the IP addresses of a set of overlay nodes are published; users can access these nodes to communicate with any node in the Chord network. On the other side of the Chord network, an overlay node called “trigger” directly connects to the application and serves as a rendezvous point for the application. As such, users can access the application by sending messages through the Chord network to the “trigger” which forwards the messages to the application. This structure allows communication between users and the application without disclosing the application’s IP address, thereby preventing direct infrastructure-level DoS attacks on the application.
[pic]
Figure 2-6 Internet Indirection Infrastructure (i3)
2 Known Results on Proxy Network-based DoS Defense
Studies [25-34] have explored some properties of the SOS and i3 implementations of the proxy network-based DoS defense. Using a simplistic analytical model, studies [25, 26, 30-33] have explored an attack specific to the SOS protocol. They have shown that the SOS implementation (which depends on the Chord routing protocol) can provide continued user access to the application when attackers disable random SOS nodes. Other studies [28, 29, 34] have explored some i3-specific attacks targeted at the protocol used by i3 for trigger installation. They have shown that the i3 implementation can resist such attacks and provide continued user access to the application.
However, these existing explorations of the proxy network-based DoS defense have three fundamental limitations:
First, each of these efforts focuses on a specific implementation of the proxy network-based DoS defense. The evaluation of one applies only to that particular implementation. There has been no systematic exploration of the fundamental capabilities and limitations of the general class of proxy network-based DoS defense.
Second, these efforts have not studied penetration attacks and proxy depletion attacks which are critical threats to the proxy network-based DoS defense. In order to understand the fundamental feasibility of the proxy network-based defense and learn how to design such schemes, we need to study whether and when a proxy network can resist these important attacks.
Third, these efforts have not studied how well a proxy network can protect an application’s performance under DoS attacks. In order to understand the effectiveness of a proxy network-based DoS defense, we need to study detailed application performance under DoS attacks, in large-scale network environments.
In summary, our understanding of proxy network-based DoS defense schemes has been limited and incomplete. The fundamental capabilities and limitations of this scheme remain unclear. Specifically, little is known about a proxy network’s resistance to the three important classes of technical attacks: penetration attacks, proxy depletion attacks, and DoS attacks. A clear understanding of these issues is essential to the proxy network-based DoS defense, and will provide a major advance in the area of DoS defense.
3 Summary
This chapter has provided relevant background for our research by describing the Denial-of-Service problem for Internet service applications, current defenses against DoS attacks, and the newly emerged proxy network-based DoS defense.
We have shown that DoS attacks are an important threat to Internet service applications. Current defense mechanisms have critical limitations and do not provide effective defense. Therefore, protecting Internet service applications from DoS attacks remains an important open research challenge.
A newly emerged proxy network-based DoS defense shows promise in solving the DoS problem. By mediating application accesses to prevent direct infrastructure-level DoS attacks, and providing a distributed front-end for the application to disperse attack traffic, this new scheme shows promise in protecting the application’s availability from DoS attacks. Furthermore, it is feasible in practice to deploy this scheme at the Internet-scale, providing a global DoS defense for Internet service applications.
However, fundamental properties of this new scheme are poorly understood. For example, it is unclear whether a proxy network can resist large-scale DoS attacks and protect applications. It is also unclear whether attackers can penetrate a proxy network and expose the application to direct DoS attacks. Furthermore, it is unclear how the system behaves under different attack scenarios and how a proxy network should be designed for better resistance to various attacks. A clear understanding of these issues is essential to the proxy network-based DoS defense, and would provide a major advance in the area of DoS defense.
Thesis Statement
Denial-of-Service (DoS) attacks are an important security threat to Internet applications. Our research focus is the study of a generic system-level approach which protects Internet applications against infrastructure-level DoS attacks, and the characterization of the capabilities and limitations of such approach. Through the study, we develop design guidelines for its effective deployment. In this chapter we outline the research context, define the research problem, and present the thesis statement.
1 Context
In recent years, varied Internet services, such as search engines and e-Commerce applications, have emerged as critical parts of today’s society and economy. Typically, these applications are made available by publishing an IP address which enables direct user connection (see Figure 3-1). However, this public IP address means that the application is exposed to DoS attacks. How to protect Internet services from DoS attacks is an important research problem.
[pic]
Figure 3-1 Direct Access vs. Mediation
One approach to the problem is to mediate user access to an application. As shown in Figure 3-1, mediation adds a level of indirection; application servers do not publish their IP addresses; instead users access the application through the mediator. Thus, instead of the application servers being exposed to direct DoS attacks, the burden is shifted to the mediators. For a mediator to protect an application from infrastructure-level DoS attacks, it must support communication between users and the application, hide the applications’ IP addresses, and resist DoS attacks.
If the application is only accessible via the mediator, direct infrastructure-level DoS attacks on the application are prevented, and the mediator can shield the application. Furthermore, if the mediator can resist DoS attacks and continue to support user access to the application, then attackers cannot deny application service by attacking the mediator. Therefore if these requirements are met, a mediator can protect applications from infrastructure-level DoS attacks. The idea of using mediation to address the DoS problem is straightforward, but the key research challenge is how to design mediators to meet the requirements.
2 Problem Definition
[pic]
Figure 3-2 Proxy Network as Mediator
Proxy networks are an attractive approach to building mediators for DoS resistance (see Figure 3-2). In the proxy network scheme, a proxy network runs on a large resource pool of Internet hosts. Applications are hidden behind the proxy network and all traffic to and from the application goes through the proxy network. A select set of nodes known as edge proxies publish their IP addresses, providing public access to users of the applications. To ensure that the proxy network is the only public interface for the application, the application either has a secret IP address or resides behind a distributed set of filters which blocks all packets except for those coming from the application proxies.
Proxy networks are an attractive approach to building mediators for DoS defense [25-29, 35], for the following reasons. First, the application is protected by a series of proxy indirections, all of which must be compromised by attackers to expose the application to direct attacks. Since the number of indirections can be adjusted by reconfiguring the proxy network, proxy networks provide a flexible structure for resisting an attackers’ penetration and, therefore, protecting the application from direct attacks. Second, the edge proxies can be widely dispersed, making it difficult for attackers to saturate them and, thereby, interrupt application service. This allows proxy networks to tolerate DoS attacks by dispersing attack traffic. By mediating application access to prevent direct attacks and by providing a DoS-resilient front-end for the application to dilute the impact of DoS attacks, a proxy network can protect the application from infrastructure-level DoS attacks.
However, to understand whether or not proxy networks can be a viable DoS defense, we need to understand their resistance to possible attacks. We assume that attackers cannot attack a proxy unless they know its IP address, and that attackers cannot concurrently attack all of the resource pool. In this case, the three important classes of technical attacks on proxy networks are penetration attacks, proxy depletion attacks, and infrastructure-level DoS attacks. Penetration attacks attempt to compromise proxies along a path in a proxy network towards the application, in order to penetrate the proxy network and expose the application to direct attacks. Proxy depletion attacks compromise proxies along the proxy network topology in order to control all the proxies, and thus disable the proxy network. Infrastructure-level DoS attacks flood the infrastructure around edge proxies with network traffic to saturate them, and thereby prevent the proxy network from mediating the communication between users and the application. Studying proxy networks’ resistance to these attacks provides a deeper understanding of the viability of the proxy network-based DoS resistance scheme. In this dissertation, we explore the following research questions.
• Can a proxy network resist penetration attacks?
Penetration attacks are a key threat to the proxy network scheme because, if successful, they can expose the application to direct DoS attacks. Therefore, a basic question for proxy network-based DoS defense is whether proxy networks are capable of resisting penetration attacks. Specifically, we ask the basic feasibility questions: How much time is required to penetrate a proxy network? Can the proxy indirections alone resist penetration attacks, or are some other defensive mechanisms required, and if so what are they?
• Can a proxy network resist proxy depletion attacks?
Proxy depletion attacks are another threat to the proxy network scheme because, if successful, all proxies in the proxy network are under the attackers’ control, and thus make the proxy network dysfunctional. A proxy network must be able to resist such attacks, in order to provide a stable defense for the applications. Specifically, we ask the following question: can a proxy network recover all the compromised proxies regardless of how many proxies are compromised at the beginning?
• Can proxy networks resist infrastructure-level DoS attacks and shield applications?
To protect applications from infrastructure-level DoS attacks, proxy networks themselves must be capable of resisting such attacks, so that attackers cannot deny application service by attacking the proxy network. Specifically, we ask critical questions about the effectiveness and scalability of proxy networks’ resilience to DoS attacks. How well can proxy networks tolerate infrastructure-level DoS attacks and keep applications accessible to their users? Can a proxy network’s resistance to DoS attacks be increased by increasing the size of the proxy network? Can this resistance be used to resist stronger DoS attacks?
3 Thesis Statement
My thesis is stated as follows:
By hiding applications from penetration attacks and providing a stable and DoS-resilient front-end, proxy networks can effectively protect an application from a range of infrastructure-level DoS attacks. Specifically, a proxy network can be used as an application mediator that forms a barrier against penetration attacks, and thereby protects an application from direct attacks. Moreover, a proxy network can effectively resist proxy depletion attacks by removing the impact of attack, thereby providing a stable defense. Furthermore, a proxy network can effectively resist infrastructure-level DoS attacks by dispersing the attack traffic among a distributed front-end and diffusing the impact of DoS attacks, thereby enabling continued application service.
The thesis addresses the fundamental properties of the proxy network scheme in protecting Internet service applications from DoS attacks. The thesis addresses three important classes of attacks: penetration attacks, proxy depletion attacks, and infrastructure-level DoS attacks. Resisting these attacks allows a proxy network to effectively protect applications from DoS attacks.
1 Resistance to Penetration Attacks
To prove that proxy networks can resist penetration attacks, we build a generic framework and a stochastic model to describe the proxy network system and characterize system dynamics, modeling the progress of attacks and defenses as stochastic processes. Based on our stochastic model, we use analysis and Monte Carlo simulations to show that proactive mechanisms, such as proxy migration, enable a proxy network to defend penetration attacks effectively. With such a defense, an attacker’s penetration requires a significant amount of time, which grows exponentially with the proxy network depth. For example, in realistic settings, penetrating a proxy network of depth five can take hundreds of years on average, and a proxy network of depth six would take thousands of years on average. Practically, this means that a proxy network of a modest size can be made effectively impenetrable.
2 Resistance to Proxy Depletion Attacks
To prove that proxy networks can resist proxy depletion attacks, we use a generic framework and a stochastic model to describe the proxy network system and characterize system dynamics, modeling the progress of proxy depletion attacks and defenses as stochastic processes. Based on this model, we characterize analytically the circumstances under which a proxy network can resist proxy depletion attacks effectively. Specifically, the analysis shows that an appropriate topology can enable a proxy network to remove compromised proxies completely regardless of how many proxies are compromised initially. We then apply these results to a range of popular proxy network topologies to identify favorable ones which enable effective defense against proxy depletion attacks.
3 Resilience to Infrastructure-level DoS attacks on Proxy Networks
We take two steps to study the DoS-resilience of proxy networks. First, by simulation, we demonstrate that in a large resource pool (hosts and network), a proxy network can continue to deliver application service during DoS attacks. These results are then confirmed over a range of attack magnitudes and distributions. Second, to show that proxy networks cannot simply be overwhelmed, we show that the magnitude of DoS attacks that a proxy network can resist may be increased by using a larger proxy network. In fact, the magnitude of DoS attacks that can be resisted grows linearly to the proxy network size. These two results together show that proxy networks can be both effective and scalable DoS-resilient mediators.
Our experiments are performed using a large-scale online simulator – MicroGrid [37, 41] which enables packet-level accurate simulation of large-scale network environments with up to 10,000 routers and 40 ASes. These network sizes are comparable to a large ISP network. Furthermore, Microgrid supports direct execution of unmodified application binaries, allowing us to use real applications and a real proxy network implementation in the simulation. In our study, we use a DDoS zombie network of 100 nodes with a real DoS attack toolkit, and use the zombies to generate attack traffic. The total attack traffic intensities up to 6.4Gbps and a wide range of DoS attack scenarios are explored. This experimental configuration is large enough to capture key properties of the Internet environment, such as router queues, as well as networking and routing protocol dynamics, which are critical to the application behavior and performance under various DoS attack scenarios. These tools enable a realistic study of the proxy network-based scheme.
In summary, to prove the thesis, our study explores proxy network resistance against three important attacks: penetration, proxy depletion, and infrastructure-level DoS attacks. We first prove that proxy networks can resist penetration attacks effectively, and then show how proxy network can be designed to resist proxy depletion attacks effectively. Next, to show that proxy networks can provide both effective and scalable resilience against DoS attacks, we use simulation to demonstrate that, in a large resource pool, a proxy network can continue to deliver application service during DoS attacks. These simulations also show that the magnitude of DoS attacks that a proxy network can resist may be increased linearly by increasing proxy network size. These results together prove that proxy networks can resist penetration attacks, proxy depletion attacks, and DoS attacks effectively, thereby providing a viable DoS defense for Internet service applications. Furthermore, study of these problems also develops a deeper understanding of the fundamental capabilities of proxy networks, and provides guidelines for proxy network design in support of DoS resistance.
Approach
1 Overview
This chapter describes our high-level approach used to study proxy network-based DoS defense. In order to understand proxy networks’ ability to protect Internet service applications from infrastructure-level DoS attacks, we consider possible attacks against proxy networks, and study their properties under such attacks.
From an attacker’s perspective, there are three strategies to defeat the proxy network scheme. First, attackers can penetrate the proxy network and compromise the application proxies. Since the application proxies connect to the application directly, this enables attackers to bypass the proxy network and attack the application directly. Second, attackers can make the proxy network dysfunctional by compromising all the proxies. Third, attackers can make the proxy network inaccessible to users, preventing users from accessing the application service.
Corresponding to these high-level strategies, there are three important classes of attacks against the proxy network scheme (see Figure 4-1): penetration attacks, proxy depletion attacks, and DoS attacks on proxy network. Using the host compromise mechanisms described in Section 2.2.3, penetration attacks attempt to compromise proxies along a path in a proxy network towards the application, penetrating the proxy network, and thereby eventually exposing the application to direct attacks. Using the host compromise mechanisms described in Section 2.2.3, proxy depletion attacks compromise proxies along a proxy network’s topology, thereby increasing the number of compromised proxies and eventually disabling the proxy network. Infrastructure-level DoS attacks attempt to flood the infrastructure around edge proxies with network traffic in order to saturate them, thereby preventing communication between users and the application. By studying proxy networks’ resistance to these attacks, we can develop a deeper understanding of the viability of proxy network-based DoS resistance. In our research, we study proxy networks’ resistance to these attacks. The approaches used to study each attack are outlined as follows.
[pic]
Figure 4-1 Three Classes of Attacks on Proxy Networks
1 Study of Penetration Attacks using Generic Framework and Stochastic Modeling
Our approach to studying penetration attacks has two elements: a generic framework for proxy network-based DoS defense and the use of a stochastic model to characterize the impact of attacks on a proxy network system.
In order to study a general class of proxy networks, we develop a generic framework which encompasses a wide range of proxy network-based DoS defense. The framework defines key components of a proxy network system and describes how attacks and defenses change the system state. It enables rigorous study of a large class of proxy networks with results that bear on the entire class.
Based on the generic framework for proxy network schemes, we develop a stochastic model to characterize how attacks and defenses change the state of system components quantitatively, thereby allowing rigorous study of system dynamics as a function of attacks and defenses. Based on our stochastic model, we combine analysis with Monte Carlo simulation techniques to study how long it takes a penetration attack to penetrate a proxy network. As such, we answer a range of fundamental feasibility questions, and study when a proxy network can resist penetration attacks effectively.
2 Study of Proxy Depletion Attacks using Generic Framework and Stochastic Modeling
Our approach to studying proxy depletion attacks has two elements: a generic framework for proxy network-based DoS defense and the use of a stochastic model to characterize the impact of attacks on a proxy network system. Since proxy depletion attacks use the same attack mechanism (host compromise attacks) as penetration attacks, we use the same framework and stochastic model as describe above.
Using the framework and model, we study system dynamics as a function of attacks and defenses. We analyze when a proxy network can remove all the compromised proxies regardless how many proxies are compromised initially and when it cannot. As such, we characterize when a proxy network can resist proxy depletion attacks effectively and when it cannot.
3 Study of DoS Attacks on Proxy Network using Online Simulation
We study the properties of proxy networks under DoS attacks empirically, using online packet-level network simulation with full applications, a real software implementation of proxy network, and real attacks. This approach enables study of detailed network and application dynamics such as packet drops, router queues, real temporal and feedback behavior of network and application protocols, which are critical to application and proxy network performance under DoS attacks. Therefore, this approach enables accurate modeling of the full complexity of network and application behavior needed to reproduce DoS dynamics, and to characterize application and proxy network performance in varied attack scenarios. With this leverage, we study application performance delivered by a proxy network for a range of proxy network structures and attack scenarios. As such, we study proxy networks’ resilience to DoS attacks.
The rest of the chapter is structured as follows. Section 4.2 describes our generic framework which encompasses a wide range of proxy network-based DoS defense. We use this framework to study penetration attacks and proxy depletion attacks. Section 4.3, Section 4.4, and Section 4.5 describe the high-level approach used to study penetration attacks, proxy depletion attacks, and DoS attacks on proxy networks respectively. Section 4.6 gives a brief summary of our approach.
2 A Generic Framework for Proxy Network-based DoS Defense
Researchers explore the use of proxy networks as mediators to protect Internet applications from DoS attacks [25-29, 35]. Two key elements are the common core of all of these approaches (e.g. SOS [25, 26] and i3 [28, 29, 35]). First, all these approaches use an overlay network – proxy network – to mediate communication between users and applications. As long as the application is only accessible via the proxy network, the application servers cannot be attacked directly. Second, all these approaches use a large set of public proxies to provide access to the application and allow the number of public proxies to be increased flexibly. In order to deny application service, attackers must saturate this large number of proxies. The flexibility enables scalable resilience against DoS attacks. The commonality of these approaches allows them to be studied within a single framework.
In this section, we propose a generic framework which captures the key elements of all proxy network approaches and defines a system state model which describes the impact of attacks and defenses. The framework serves two purposes: 1) it provides a formal basis for discussion of proxy networks and attacks, and 2) it enables study of properties of a large class of proxy networks. We use this framework to study both penetration attacks and proxy depletion attacks. In the following, we introduce our generic framework, and then discuss how previously proposed proxy network schemes are captured in the framework.
1 Definition of the Generic Framework
The framework for proxy network schemes has two parts, a description of system components, including applications, users, hosts, and a generic proxy network, and a description of how attack and defense processes affect system dynamics.
1 System Components
[pic]
Figure 4-2 Generic Framework for Proxy Networks
As shown in Figure 4-2, our generic framework describes a system where a proxy network mediates all traffic between an application and its users, and protects the application from infrastructure-level DoS attacks. In the following section, we define the four key system components: applications, users, hosts, and a proxy network.
1 Application
An application is a deployed software system that implements an Internet service which responds to user requests and runs on a host in the Internet. In the proxy network scheme (see Figure 4-2), the IP address of the application is hidden and the application has connections with the proxy network, through which the application communicates with its users.
2 Users
A user is the principal that uses the application client software to interactively access the application, in order to use the application service. For example, a user can be a person using a web browser to access the Internet service application. In the proxy network scheme (see Figure 4-2), users are outside the proxy network and access the application via edge proxies (defined below) and through the proxy network.
3 Hosts
A host is a computer system connected with the Internet which provides the software and hardware infrastructure to support the operation of proxy nodes (defined below). A large number of such hosts dispersed widely in the Internet form a resource pool for the proxy network (see Figure 4-2).
Hosts may have vulnerabilities, such as exploitable bugs in the operating system software, which allow attackers to compromise the hosts. Furthermore, the vulnerabilities of the hosts in the resource pool may be correlated (e.g. same operating system software with the same bugs). If host vulnerabilities are correlated, once a host is compromised, others may be easily compromised using similar techniques.
4 Proxy Network
As shown in Figure 4-2, a proxy network is an overlay network which runs on the resource pool of Internet hosts and mediates all traffic to and from the application. A proxy network is a set of interconnected proxies, each of which is a software program that runs on an Internet host and forwards application traffic. There are two types of proxies, edge proxies and internal proxies. Edge proxies have published IP addresses. Internal proxies are those which are not edge proxies; their IP addresses are hidden.
As shown in Figure 4-2, on one side of the proxy network a selected set of proxies are connected to the application, and on the other side of the proxy network, a set of edge proxies publish their IP addresses providing access to users of the application. As such, the proxy network mediates all traffic between users and the application.
There are three important properties of a proxy network: topology, depth, and width.
The topology of a proxy network characterizes the internal connectivity amongst proxies. The topology of a proxy network can be represented by a graph, where vertices represent proxies and edges represent the connections among proxies. Technically two proxies are connected if they can route packets to each other. In the context of network security, the important distinction is that connected proxies know each other’s IP address.
The depth of a proxy network is the minimum number of proxy indirections between an application and its users. The depth of a proxy network for an application is defined as the minimum path length in the proxy network topology graph from any edge proxy to the application. For example, the depth of the proxy network shown in Figure 4-2 is four.
The width of a proxy network is the number of public access points the proxy network presents to the users of an application. The width of a proxy network is defined as the number of edge proxies. For example, the width of the proxy network shown in Figure 4-2 is six.
2 System Dynamics
System dynamics describes the changes in system state which result from attacks and defenses. By studying the system dynamics of a proxy network under various attack and defense scenarios, we can understand when the proxy network can provide stable defense against penetration attacks and proxy depletion attacks. We first introduce terminology to describe the system state, and then discuss how attacks and defenses affect the overall system dynamics.
1 System State
We define the state of system components as follows. A host has two states: compromised and intact. A host is compromised when attackers have control over it and any information stored there may be revealed to attackers. A host is intact if and only if it is not compromised.
A proxy has three states: exposed, compromised and intact. A proxy is exposed if attackers know its location, i.e. the IP address of the host where the proxy runs; in this case the proxy is subject to future attacks. A proxy is compromised if it runs on a compromised host. A proxy is intact if it is neither exposed nor compromised.
The system state is the combined state of all the proxies in the proxy network and all the hosts in the resource pool. However, it is convenient to also consider the system state as the progress of the attacks having the following attributes:
• The number of intact hosts in the resource pool. The health of the resource pool and the amount of intact resource available to the proxy network.
• The number and distribution of compromised proxies in the proxy network. How many and which proxies are compromised and under attackers’ control. It reflects the amount of control attackers have on the proxy network.
• The minimum distance between the exposed proxies and the application in the proxy network topology graph. The minimum number of proxy indirections that separates the application from attackers. It reflects the progress and structural information of the proxy network attackers have obtained.
In a healthy proxy network system, all the hosts in the resource pool are intact, none of the proxies are compromised, and only edge proxies are exposed because their IP addresses are published to provide user access. By compromising and exposing proxies, attacks may increase the population of compromised proxies and reduce the minimum distance to application. Defenses may recover hosts and proxies, decreasing the number of compromised hosts and proxies, and increasing attackers’ distance to application. In the next two sections, we discuss how attacks and defenses change the system state.
2 Attacks
Our generic framework captures a range of attacks, among which we study penetration attacks and proxy depletion attacks.
The goal of penetration attacks is to discover the IP address of the application protected by a proxy network. The strategy is to explore the structure of the proxy network and compromise proxies along a path in the proxy network towards the application. As shown in Figure 4-3, these attacks allow attackers to penetrate into the proxy network, reducing the distance between the application and the exposed proxies, and perhaps, eventually discovering the IP address of the application.
[pic]
Figure 4-3 Penetration Attacks
The goal of proxy depletion attacks is to compromise all the proxies in a proxy network, thereby making the proxy network dysfunctional. The strategy is to compromise proxies and propagate along the proxy network topology. As shown in Figure 4-4, these attacks allow attackers to propagate in the proxy network, increase the number of compromised proxies, and perhaps, eventually compromise all the proxies.
[pic]
Figure 4-4 Proxy Depletion Attacks
Both penetration attacks and proxy depletion attacks use the same mechanisms, host compromise attacks, such as those explained in Chapter 2. As shown in Figure 4-5, host compromise attacks change the state of hosts and proxies. A successful host compromise attack changes an intact host to a compromised host. By compromising the host on which a proxy runs, an attacker can compromise the proxy. The neighbors of the compromised proxy then become exposed because attackers may learn their IP addresses from the compromised proxy.
Using host compromise attacks, we can construct both penetration attacks and proxy depletion attacks. In a penetration attack, attackers start from an edge proxy and use host compromise mechanisms to compromise the edge proxy. Once the proxy is compromised, all of its neighbor proxies become exposed. By compromising a sequence of exposed proxies along a path from the edge proxy to the application, attackers can penetrate the proxy network and eventually expose the application. On the other hand, in a proxy depletion attack, after compromising a proxy, attackers attack all the exposed neighbors, thereby propagating along the proxy network topology, increasing the number of compromised proxies.
[pic]
Figure 4-5 System Component State Transitions
3 Defensive Mechanisms
The goal of defense is to reverse the negative impact of attacks on the system. Defenses can recover compromised hosts, making them intact, thereby increasing the population of intact hosts for proxy networks to use. Defenses can also turn compromised and exposed proxies into intact proxies, thereby reducing the population of compromised proxies and increasing the distance between exposed proxies and the application. We discuss two types of defense in the following section: resource recovery and proxy network reconfiguration.
Resource recovery mechanisms are defenses which address host compromise attacks. Examples of resource recovery include removal of infected software components, clean reload of system images with up-to-date security patches, revocation of suspected user accounts, and so on. Such resource recovery can eliminate attackers’ control on compromised hosts and proxies, and also prevent future attacks using the same vulnerabilities of the hosts. We consider their use on all the hosts in the resource pool and trigger them using two policies: reactive recoveries and proactive resets. Reactive recoveries depend on intrusion or compromise detection, and are triggered when compromises are detected. In contrast, proactive resets happen periodically, regardless of the current state of the host.
The detailed mechanics of our resource recovery mechanisms are explained in Chapter 2. They change the state of system components. At the host level (see Figure 4-5), resource recovery takes compromised hosts and returns them to the intact state. At the proxy level, resource recovery turns a compromised proxy into the exposed state by recovering the underlying host.
Proxy network reconfiguration is another type of defense. Reconfiguration can invalidate the location information acquired by attackers, and disrupt both penetration attacks and proxy depletion attacks. Examples include changing proxy network topology and proxy migration. We focus on “random proxy migration”, where proxies can migrate from one host to another inside the resource pool, but the proxy network topology is unchanged. The migration mechanism is deployed on all the proxies in the proxy network, and every proxy (except edge proxies) periodically migrates randomly amongst hosts in the resource pool.
Proxy migration can change the state of proxies. As shown in Figure 4-5, proxy migration can turn an exposed or compromised proxy into an intact one, by moving the proxy to an intact host unknown to attackers. Furthermore, this mechanism allows proxies to escape from exposed locations before they are compromised by attackers, thereby preventing the propagation of attacks and disrupting both penetration attacks and proxy depletion attacks.
2 Generality of the Generic Framework
Having defined a generic framework for proxy network-based DoS defense, we show how it captures several previously proposed proxy network schemes, including Secure Overlay Services (SOS) [25, 26] and Internet Indirection Infrastructure (i3) [28, 29, 35]. Then, moving beyond specific examples, we discuss the space of proxy network-based DoS defense schemes captured by our framework.
1 Secure Overlay Services (SOS)
[pic]
Figure 4-6 Secure Overlay Services (SOS)
As shown in Figure 4-6, Secure Overlay Services (SOS) is a proxy network scheme that uses the Chord overlay network [38] to mediate all traffic between users and applications and protect applications from DoS attacks. On one side of the Chord network, a set of overlay nodes (“access points”) publish their IP addresses and provide users access to the application. On the other side, a set of overlay nodes (“servlets”) connect to the application. Application traffic between users and applications is mediated through the Chord network via the access points and the servlets. Furthermore, filters are used around the application to enforce that only traffic from the servlets can reach the application, thereby preventing direct infrastructure-level DoS attacks on the application. Our generic framework captures the key properties of the SOS scheme as follows.
First, the key components of SOS system match those of our generic framework. The Chord network used by SOS can be represented using our generic proxy network with a Chord topology, the access points of SOS correspond to the edge proxies in our framework, and the “servlets” correspond to the proxies that directly connect to the application in our framework.
Second, the attack and defense processes described in our generic framework can apply to the SOS system. Regarding attacks, both penetration attacks and proxy depletion attacks described in our framework are key threats to the SOS system. Using penetration attacks, attackers can penetrate the Chord network and discover the IP addresses of the servlets. Once the servlets are exposed, attackers can easily defeat the SOS defense, because DoS attacks using packets spoofed with servlets’ IP addresses can go through the filters, and reach the application. On the other hand, using proxy depletion attacks, attackers may compromise all the SOS nodes, thereby disabling the SOS system. Regarding defenses, both reactive and proactive resource recoveries described in our framework can directly apply to the SOS system. The SOS proposal does not include any proxy network reconfiguration mechanism.
2 Internet Indirection Infrastructure (i3)
[pic]
Figure 4-7 Internet Indirection Infrastructure (i3)
Internet Indirection Infrastructure (i3) is another proxy network scheme that protects Internet services from DoS attacks. As shown in Figure 4-7, the i3 system uses a Chord overlay network to mediate all traffic between users and applications, protecting applications from DoS attacks. In the i3 system, the IP address of the application is hidden from users. On one side of the Chord network, a set of overlay nodes publish their IP addresses, providing users access to the Chord network. On the other side, an overlay node called “trigger” directly connects to the application and serves as a rendezvous point for the application. As such, i3 mediates application traffic through the Chord network and prevents direct infrastructure-level DoS attacks on the application. Our generic framework captures the key properties of the i3 scheme as follows.
First, the key components of the i3 system match those of our generic framework. The Chord network used by i3 can be represented using our generic proxy network with a Chord topology, the i3 nodes with published IP addresses correspond to the edge proxies in our framework, and the triggers correspond to the proxies that directly connect to the application in our framework.
Second, the attack and defense processes described in our generic framework can also apply to the i3 system. Regarding attacks, both penetration attacks and proxy depletion attacks described in our framework are key threats to the i3 system. Using penetration attacks, attackers can penetrate the Chord network and discover the IP addresses of the application, thereby exposing the application to direct DoS attacks. On the other hand, using proxy depletion attacks, attackers may compromise all the i3 nodes, thereby disabling the i3 system. Regarding defenses, both reactive and proactive resource recoveries described in our framework can apply to the i3 system directly. The i3 proposal does not include any proxy network reconfiguration mechanism.
3 Space of Proxy Networks
Besides the existing proxy network proposals, our generic framework admits DoS resistance schemes using a wide range of proxy networks, varying in topologies, depth and width, deployment schemes, and defensive mechanisms. For example, a proxy network may use a tree or a hypercube [40] as its topology instead of Chord. A proxy network may also employ defensive mechanisms such as proxy migration or dynamic change of proxy network topology.
Our generic framework provides a basis for a general exploration of the space of proxy networks. First, this framework allows study of fundamental capabilities and limitations of a large class of proxy network-based DoS defense schemes with results that bear on the entire class. Second, this framework also allows exploration of the design space of proxy networks, providing design guidelines for proxy network-based DoS defense.
3 Resisting Penetration Attacks
Penetration attacks are an important class of attacks on proxy networks. As shown in Figure 4-8, penetration attacks attempt to compromise proxies along a path in a proxy network towards the application, thereby penetrating the proxy network, and eventually exposing the application to direct attacks.
[pic]
Figure 4-8 Penetration Attacks
We use the amount of time attackers take to penetrate a proxy network as a metric to evaluate the proxy network’s resistance to penetration attacks. If the time to penetrate a proxy network is sufficiently long (e.g. over a hundred years), then penetration attacks are no longer a practical threat to the proxy network. In this case, the proxy network can resist penetration attacks effectively. We study when a proxy network can resist penetration attacks effectively and what defensive mechanisms are required to achieve effective resistance.
In order to study these problems, we develop a stochastic model from the generic framework (defined in Section 4.2) to characterize how attacks and defenses change the state of system components. In particular, we model the attacks and defenses as stochastic processes which describe how attacks compromise hosts and proxies and how defenses recover them. Using this stochastic model, we combine analysis and Monte Carlo simulation to quantify how long it takes for attackers to penetrate a proxy network as a function of attacks and defenses. In such way, we characterize the circumstances under which a proxy network can resist penetration attacks effectively, and what defense parameters are critical for effective defense.
Using a stochastic approach has two advantages. First, it provides a simple model to characterize attacks and defenses, making study tractable and results easy to understand. Second, stochastic analysis enables study of a full spectrum of proxy networks and attack scenarios at once, and a thorough exploration of the design space. However, the stochastic approach also has limitations. It is subject to the correctness and precision of the stochastic model which does not capture all the details of the system components.
4 Resisting Proxy Depletion Attacks
[pic]
Figure 4-9 Proxy Depletion Attacks
Proxy depletion attacks are an important class of attacks on proxy networks. As shown in Figure 4-9, proxy depletion attacks attempt to compromise all the proxies in a proxy network, by compromising proxies and propagating along the proxy network topology, thereby making the proxy network dysfunctional.
To study a proxy network’s resistance to proxy depletion attacks, we study when a proxy network is recoverable under such attacks. We define a proxy network to be recoverable under proxy depletion attacks if all the compromised proxies can be recovered regardless how many proxies are compromised initially. A recoverable proxy network can provide stable defense against proxy depletion attacks.
In order to study the system dynamics under proxy depletion attacks, we develop a stochastic model from the generic framework (defined in Section 4.2) to characterize how attacks and defenses change the state of system components. In particular, we model the attacks and defenses as stochastic processes which describe how attacks compromise hosts and proxies and how defenses recover them. Using this stochastic model, we use graph-theoretical analysis to quantify how the population of compromised proxies changes under proxy depletion attacks as a function of attacks, defenses, and proxy network topologies. We use these results to study when a proxy network is recoverable under proxy depletion attacks, providing stable defense, and when it is not. By doing so, we develop guidelines of proxy network design for effective resistance to proxy depletion attacks.
The stochastic approach used for the study of proxy depletion attacks is similar to the one discussed in Section 4.3; thereby, it shares similar advantages and limitations. It provides a simple model, and thus makes study tractable and results easy to understand. Furthermore, the analysis allows for the examination of a full spectrum of proxy networks and attack scenarios at once, as well as a thorough exploration of the design space. However, the key limitation is that it is subject to the correctness and precision of the stochastic model, which does not capture all the details of the system components.
5 Resilience to DoS Attacks on Proxy Network
DoS attacks are another important class of attacks on proxy networks. As shown in Figure 4-10, attackers can use infrastructure-level DoS attacks to saturate the edge proxies by flooding the infrastructure around edge proxies with network traffic, thereby causing Denial-of-Service for users.
[pic]
Figure 4-10 Denial of Service attacks
In order to study the use of proxy networks for DoS defense, we need to understand how well a proxy network can keep applications accessible and maintain good performance for users under DoS attacks. In particular, we use the user experienced application performance delivered by a proxy network under DoS attacks as a metric to evaluate a proxy network’s resilience to DoS attacks. A proxy network can resist a DoS attack effectively, if the majority of the users (e.g. >90%) do not experience significant performance degradation during the attack. Using this metric, we study whether a proxy network can resist DoS attacks effectively for a variety of attack scenarios and proxy network configurations.
There are two major challenges to perform this study. First, for realistic studies we need to capture detailed network dynamics and behavior of applications and attacks, since they greatly affect application and proxy network performance under DoS attacks. Second, we need to study the problem in a large-scale network environment, because it is a key aspect of the DoS problem for Internet applications.
Theoretical analysis and small-scale simulation cannot meet these challenges because they cannot capture detailed network behavior in large networks, such as router queues, packet drops, and dynamic behavior of network and application protocols. All these factors are critical to application performance and DoS behavior. On the other hand, experiments on large testbeds such as PlanetLab [109] cannot meet the challenges either because such testbeds are shared infrastructure; DoS experiments may disrupt other testbed users by flooding the infrastructure. Thus, the scale, intensity, and range of attack scenarios that can be studied using an open testbed are very limited.
To address these challenges, we take an experimental approach based on online simulation. The element is the use of a large-scale packet-level online network simulation tool, MicroGrid [37, 41], that supports direct execution of real applications and can model detailed network dynamics, real temporal and feedback behavior of network protocols correctly. Furthermore, MicroGrid also supports simulation of large networks (size comparable to tier-1 ISP networks [37]). These capabilities of MicroGrid meet the challenges stated above. In our empirical study, we use the following components to construct our experiments.
• a large-scale, high-fidelity packet-level online network simulator – MicroGrid – to simulate a large-scale realistic network environment, which has up to 10,000 routers and 40 ASes, comparable to the size of a Tier-1 ISP network,
• a real proxy network implementation and real applications deployed in the simulation environment, and
• a zombie network and a real distributed DDoS toolkit to create attack scenarios. Attack traffic intensities up to 6.4 Gbps and a wide range of different attack scenarios are explored.
Using these experiments, we take two steps to study how well proxy networks can resist DoS attacks. First, we demonstrate that in a large resource pool (hosts and network), a proxy network maintain good performance for most users during DoS attacks. These results are then confirmed over a range of varied attack magnitude and distribution. Second, to show that proxy networks cannot be overwhelmed by simply increasing the volume of DoS attack, we show that the magnitude of DoS attacks that a proxy network can resist may be increased by using a larger proxy network. These results together show that proxy networks can be both effective and scalable DoS-resilient mediators.
Our simulation-based approach has several advantages. First, the direct execution of real applications enables use of a real implementation of the proxy network, real applications, and real attacks in our study to correctly capture all their complex dynamics and performance behavior. Second, correct modeling of the detailed network and protocol dynamics enables correct characterization of application and proxy network performance under DoS attacks. Third, simulation of large-scale networks enables study of the DoS problem in a large-scale network environment. Fourth, the use of a simulator enables study of a wide range of attack scenarios of various scales and intensities. These advantages are the key to enable large-scale realistic study.
6 Summary
In summary, to study the use of proxy networks for DoS defense, we explore the capability of proxy networks against three important attacks: penetration attacks, proxy depletion attacks, and DoS attacks. To study penetration attacks and proxy depletion attacks, we develop a generic framework to capture a wide range of proxy network-based DoS defense and build stochastic models for attack and defense processes to characterize system dynamics. Using the stochastic models, we combine analysis with Monte Carlo simulation to study when stable defense against penetration attacks is feasible. We then use graph-theoretical analysis based on the stochastic models to study when a proxy network can resist proxy depletion attacks effectively. On the other hand, we study DoS attacks empirically based on online simulation. In particular, we use a large-scale online packet-level network simulator to simulate a large network environment and deploy a real software implementation for the proxy network, applications, and DoS attackers. By using full applications and network protocol stacks in a realistic detailed packet-level simulation environment, we can model the full complexity of the network behavior needed to reproduce DoS dynamics accurately. With this leverage, we study the resilience to DoS attacks for a range of proxy network structures and attack scenarios.
The analysis and experiments are presented in the next three chapters. Chapter 5 studies whether proxy networks can resist penetration attacks effectively, and characterizes the key requirements for effective defense against penetration attacks. Chapter 6 studies proxy networks’ ability to resist proxy depletion attacks and shows how to design proxy networks for effective resistance to proxy depletion attacks. Chapter 7 studies proxy networks’ resilience to DoS attacks by empirical exploration of application performance under DoS attacks for a range of attack parameters and proxy network configurations.
Resisting Penetration Attacks
Penetration attacks are a key threat for the proxy network-based DoS defense. By compromising a chain of proxies towards the application, such attacks penetrate a proxy network and defeat the proxy network-based scheme by exposing the application to direct DoS attacks. In this chapter, we study proxy networks’ ability to resist penetration attacks and characterize the requirements for successful resistance.
1 Introduction
We study proxy networks’ ability to resist penetration attacks. In particular, we study the following questions. How long can a proxy network resist a penetration attack and hide an application’s location? How do the defense properties affect a proxy network’s resistance to penetration attacks, and what factors make resistance feasible?
To study these problems, we develop a stochastic model for the generic framework (defined in Chapter 4) to characterize the dynamics of system components. In particular, our stochastic model describes quantitatively how attacks, defenses, and correlated host vulnerabilities affect changes in the state of system components. With the stochastic model, we combine analysis and Monte-Carlo simulation to analyze behavior of proxy network systems under penetration attacks, characterizing when their resistance to penetration attacks is feasible.
We consider correlated vulnerabilities among hosts, which can greatly affect the behavior of penetration attacks. This is because the low-level mechanisms for penetration attacks – host compromises – depend on the exploitation of host vulnerabilities, and correlated vulnerabilities among hosts affect the speed of host compromises, thereby affecting the progress of penetration attacks. Since correlated host vulnerabilities complicate the analysis, our approach has two steps.
First, we study a system with uncorrelated host vulnerabilities and analytically characterize the system behavior. In particular, we characterize quantitatively the expected time for attackers to expose an application’s location as a function of system parameters. We prove two theorems which characterize dynamic system behavior, and show that, with appropriate defense, proxy networks can resist penetration attacks effectively. We use these theorems to study the questions described above.
Second, we use a Monte Carlo simulation to study a system with correlated host vulnerabilities. In particular, we study how correlation in host vulnerabilities affects a proxy network’s ability to resist penetration attacks. We show that correlated vulnerabilities can jeopardize a proxy network’s ability to resist attacks. We also demonstrate that, by exploiting limited host diversity and intelligent proxy network construction, we can compensate for the negative impact of correlated host vulnerabilities and build a proxy network which can resist penetration attacks successfully.
Combining both the correlated and uncorrelated host vulnerability cases, we prove that, in general, proxy networks can be designed to resist penetration attacks effectively. The remainder of the chapter is structured as follows. Section 5.2 describes our stochastic model. Section 5.4 and Section 5.5 present the results of our analysis and Monte Carlo Simulation respectively. We conclude in Section 5.6 with a brief summary.
2 Stochastic Model for System Component Dynamics
We model system state as a discrete-time stochastic process in which the state transitions of system components – hosts and proxies – are stochastic events. As such, we can quantify how attacks, defenses, correlated host vulnerabilities, and proxy network topology affect the system. Our stochastic model has two parts: host state transitions and proxy state transitions; Table 5-1 shows the parameters of the model. We first describe the model and then interpret the model in practical settings.
Table 5-1 Parameters of the Stochastic Model
|Notation |Meaning |
|(0 |Rate of host compromises based on new vulnerabilities |
|(v |Rate of host compromises based on known vulnerabilities |
|(s |Rate of proactive resets |
|(d |Speed of reactive recovery |
|(r |Rate of proxy migration |
2 Host State Transitions
Attacks, resource recovery (both proactive and reactive), and correlated host vulnerabilities are the three main factors that affect the transitions of host states. We first describe how our model captures attacks and resource recovery when the host vulnerabilities are uncorrelated; we then describe how our model captures correlated host vulnerabilities.
[pic]
Figure 5-1 Host State Transitions
The shaded area in Figure 5-1 shows the host state transitions when the host vulnerabilities are uncorrelated. Our model uses three parameters (0, (d, and (s to describe the speed of attacks, reactive resource recovery, and proactive resets, respectively. Within a discrete time step, attackers have a probability (0 to compromise an intact host by exploiting a vulnerability of the host. Meanwhile, reactive resource recovery has a probability (d to recover a compromised host by detecting and removing the infection, while proactive resets have a probability (s to recover a compromised host by proactively reloading the host with a clean system image.
Our model also captures correlated host vulnerabilities. We use “domains” to describe the correlated vulnerabilities among hosts (see Figure 5-2). Hosts are grouped into domains. Within a domain, hosts use similar software with similar configurations, thereby sharing similar vulnerabilities. Across domains, hosts differ in software, configurations, and other attributes, thereby providing a model for uncorrelated vulnerabilities. A system with uncorrelated host vulnerabilities (see Figure 5-2.A) is an extreme case where each host is in its own domain. Another extreme case is one where all hosts are in the same domain (see Figure 5-2.B). In general, hosts in a system are grouped into multiple domains (see Figure 5-2.C), and the number of domains is a measure of host diversity in the system.
[pic]
Figure 5-2 Domain-Based Correlated Host Vulnerability Model
To model the impact of correlated host vulnerabilities, we introduce an intermediate host state “intactv” (an intact host with a known vulnerability) and one more parameter (v (see Figure 5-1). Here is the revised model. Within a discrete time step, with probability (0 attackers can compromise an intact host by exploiting a new vulnerability, changing the other intact hosts in the same domain to the “intactv” state. With probability (v attackers can compromise an “intactv” host by exploiting a known vulnerability. Meanwhile, with probability (s proactive resets can return a host from the “íntactv” state to the intact state, by removing the known vulnerabilities. With probability (d and (s, reactive recovery and proactive resets can return a compromised host to the intact state respectively.
3 Proxy State Transition
[pic]
Figure 5-3 Proxy State Transition
A proxy’s state depends on three factors: the state of the host where the proxy runs, the state of the neighboring proxies, and whether or not the proxy is an edge proxy. Based on the host state transition model described above, we can use the following rules to determine the state of a proxy under host compromise attacks.
• A proxy is compromised if and only if its host is.
• The neighbors of a compromised proxy are exposed, or compromised.
• All edge proxies are exposed or compromised.
Furthermore, proxy migration moves a proxy to a different host and changes the proxy’s state accordingly. We use a migration rate (r to describe the proxy migration process, where proxies choose migration targets randomly and the migration overhead is small compared to the interval between migrations. More precisely, a proxy has probability (r to move to a different host within a discrete time step. After migration, the proxy’s state is determined by the rules above.
4 Discussion of the Model and Real World Data
Our model, while simple, captures all the key factors of the system, including speed of attack, speed of defense, proxy network structure, and correlated host vulnerabilities. These factors together determine how the system state changes over time, and allow us to study the system dynamics under penetration attacks. To interpret our model (see Table 5-1) in practical settings, we present numbers from real systems.
Table 5-2 Windows Vulnerability Statistics
|Year |2001 |2002 |2003 |2004 |
|WinXp Pro |5 |20 |19 |18 |
|Win2K Server |28 |24 |19 |18 |
Parameter (0 is the rate of discovery and exploit of new host vulnerabilities, an example of which is the exploitable vulnerabilities of the operating system software. The Microsoft security bulletin [110] catalogues critical and remotely exploitable vulnerabilities of Windows XP Professional and Windows 2K Server. Table 5-2 shows the number of new vulnerabilities discovered for each period. On average, there are about 20 new vulnerabilities discovered each year, one new vulnerability every two to three weeks. These numbers provide a realistic approximation of (0 in practice.
Parameter (v is the rate of host compromises using known vulnerabilities. Studies on computer vulnerabilities and attack incidents [111, 112] show that discovery and exploitation of new vulnerabilities is time-consuming and requires a significant amount of expertise in the victim system. In contrast, compromising a host using a known bug is fairly easy, because techniques and tools used in previous attacks can be leveraged. Therefore, (v is typically significantly larger than (0 ((0(, we have [pic]; and when (r2(0, T0 is between [pic] and [pic]; when (r2(0), the time to penetrate a proxy network grows exponentially with the proxy network’s depth. In this case, small increases in proxy network depth can improve penetration resistance significantly. Consequently, proxy networks of moderate depth can resist penetration attacks effectively. For example, using the numbers in Table 5-2 (attackers take two weeks to compromise a host), if the proxy migration rate is sufficiently fast (e.g. (r=10(0), then penetrating a proxy network of depth four takes about fifty years on average, a proxy network of depth six would take about five thousand years on average, thus eliminating penetration attacks as a practical concern. In contrast, Theorem 2 states that when the proxy migration rate is insufficient ((r ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- list of service businesses
- examples of service based companies
- examples of service marketing
- seven ps of service marketing
- 7 ps of service marketing
- job description of service manager
- examples of service businesses
- terms of service template
- importance of service marketing mix
- examples of service philosophy
- sign of heart attacks in men
- list of service connected disabilities