Date of Award

8-2007

Document Type

Thesis

Degree Name

Master of Science (MS)

Legacy Department

Electrical Engineering

Advisor

Brooks, Dr. Richard R

Committee Member

Sander , Dr. Samuel T

Committee Member

Walker , Dr. Ian D

Abstract

Computer networks are the nerve systems of modern enterprises. Unfortunately, these networks are subject to numerous attacks. Safeguarding these systems is challenging. In this thesis we describe current threats to enterprise security, before concentrating on the Distributed denial of Service (DDoS) problem.
DDoS attacks on popular websites like Amazon, Yahoo, CNN, eBay, Buy, and the recent acts of war using DDoS attacks against NATO ally Estonia [1] graphically illustrate the seriousness of these attacks. Denial of Service (DoS) attacks are explicit attempts to block legitimate users' system access by reducing system availability [2]. A DDoS attack deploys multiple attacking entities to attain this goal [3]. Unfortunately, DDoS attacks are difficult to prevent and the solutions proposed to date are insufficient. This thesis uses combinatorial game theory to analyze the dynamics of DDoS attacks on an enterprise and find traffic adaptations that counter the attack.
This work builds on the DDoS analysis in [4]. The approach we present designs networks with a structure that either resists DDoS attacks, or adapts around them. The attacker (Red) launches a DDoS on the distributed application (Blue). Both Red and Blue play an abstract board game defined on a capacitated graph, where nodes have limited CPU capacities and edges have bandwidth constraints. Our technique provides two important results that aid in designing DDoS resistant systems:
1.It quantifies the resources an attacker needs to disable a distributed application. The design alternative that maximizes this value will be the least vulnerable to DDoS attacks.
2.When the attacker does not have enough resources to satisfy the limit in 1, we provide near optimal strategies for reconfiguring the distributed application in response to attempted DDoS attacks.
Our analysis starts by finding the feasible network configurations for Blue that satisfy its computation and communications requirements. The min-cut sets [5] of these configurations are the locations most vulnerable to packet flooding DDoS attacks.
Red places 'zombie' processes on the graph that consume network bandwidth. Red attempts to break Blue communications links. Blue reconfigures its network to re-establish communications. We analyze this board game using the theory of surreal numbers [6]. If Blue can make the game 'loopy' (i.e. move to one of its previous configurations), it wins [7]. If Red creates a situation where Blue can not successfully reconfigure the network, it wins.
In practice, each enterprise relies on multiple distributed processes. Similarly, an attacker can not expect to destroy all of the processes used by the enterprise at any point in time. The attacker will try to maximize the number of processes it can disable at any point in time. This situation describes a 'sum of games' problem [6], where Blue and Red alternate moves. We adapt Berlekamp's strategies for Go endgames, to tractably find near optimal reconfiguration regimes for this P-Space complete problem [6], [7].

Share

COinS