# Presentation: 426116

## Distributed Denial of Service Games

- by
- Chinar Dingankar, Student
-  Dr. R. R. Brooks, Associate Professor
- Holcombe Department of Electrical and Computer Engineering
- Clemson University
- Clemson, SC 29634-0915
- Tel.   864-656-0920
- Fax.   864-656-1347
- email: rrb@acm.org

## Introduction

- Combinatorial game theory to analyze the dynamics of DDoS attacks on an enterprise
- A game is played on a capacitated graph (computer network)
- Nodes have limited CPU capacities
- Links/Edges have bandwidth constraints
- A distributed application runs on the computer network
- Our approach gives two important results –
- It quantifies the resources an attacker needs to disable a distributed application
- If the attacker does not have enough zombies required  provide near optimal strategies for reconfiguration of the distributed application in response to attempted DDoS attacks

## Physical Environment

- A simple two player game to be played on a computer network
- The “physical” graph (computer network) is represented by a directed graph structure (EG) with *N* nodes
- EG = [EV,EE]
- EV→ vertices with known CPU bandwidth
- EE→ is a set of directed edges or links with known communication bandwidth
- Local bandwidth on each node - Infinite

## Players

- Two players in the game –
**Blue** – A set of distributed programs running on physically connected computers
- BG = [BV,BE]
- BV→ is a set of nodes representing distributed programs with known CPU load
- BE→ is a set of edges or links representing the communications bandwidth needed between two programs
- Local bandwidth on each node - Infinite
- Represented by the color **BLUE**
**Red***** ****– ***Red*** *is an attacker that places zombie processes on physical graph nodes.
- Zombies send network traffic over the physical edges
- Number of zombies and where to place them
- Represented by the color **RED**

## Set of feasible Blue configurations set of mappings of BV onto EV that satisfy two classes of constraints: 
Nodal Capacity Constraint:

Edge Capacity Constraint: 

Two Blue nodes on same Physical node – Infinite Arc capacity
Maxflow for each pair of source and sink on the network 
Set of feasible configurations  BC = {BC1, BC2... BCL}	 	 

- Nodal Capacity Constraint:
- Edge Capacity Constraint:
- Two **Blue** nodes on same Physical node – Infinite *Arc capacity*
**Maxflow** for each pair of ***source*** and ***sink*** on the network
- Set of feasible configurations  **BC = {BC****1****, BC****2****...**** ****BC****L****}****	**** ****	**** **

- Feasible Blue Configurations

**Infinite B/W**

## RED disrupts Blue

**Red** disrupts a **Blue** configuration by placing zombies so as to -
- Attack node capacities - **Red** places zombies nodes hosting one or more **Blue **processes.
- The node capacity attack is rather trivial and not very interesting
- Difficult for Red to compromise the servers used by **Blue**
- Flood arcs – **Red** places zombies on nodes that do not host **Blue** processes.
- Zombies produce network traffic that consumes communications bandwidth on edges in *EE*
- A **Blue **configuration is disabled  required arc capacity of any Blue edge (s-t) becomes greater than the available maxflow from s-t on the physical graph
- Our analysis focuses on flooding attacks

## To determine the set of zombies needed by Red, we: 
Calculate the mincut for each element of BE 
Blue slack capacity at the mincut (BS) 
Expected number of blue packets dropped 
Volume of red traffic  so that  no. of blue packets dropped > BS 
Red traffic (RT) ,                               

Zombie Placement: If the Maxflow to a node in the mincut of an element of BE is > RT then that node is a candidate for zombie placement.
We need minimum number of zombies  so look for zombie nodes that can disable more than one element of BC. 
We get a smallest set of zombies needed to disable all elements of BC 

- Calculate the **mincut** for each element of *BE*
- Blue slack capacity at the **mincut **(BS)
- Expected number of blue packets dropped
- Volume of red traffic  so that  no. of blue packets dropped > BS
- Red traffic (RT) ,
**Zombie Placement:** If the ***Maxflow*** to a node in the m**incut** of an element of *BE* is** **>** *****RT*** then that node is a candidate for zombie placement.
- We need minimum number of zombies  so look for zombie nodes that can disable more than one element of *BC*.
- We get a smallest set of zombies needed to disable all elements of *BC *

- Zombie Traffic and Zombie Placement

-  λ packets is the Blue traffic

*C* is the capacity of the
-  physical arc

## Game

- If the attacker does not have enough zombies to disable all blue configurations  **Blue** has a chance to recover from the DDoS attack by reconfiguring.
- A simple board game.
- Rules for the game:
**Blue** starts the game.
- Each player is allowed one move at a time.
**Blue** can take one possible configuration out of the available BC’s for one move.
**Blue **cannot have redundancy i.e. multiple **Blue** copies.
- Once **Red** places a zombie on a node it cannot move that zombie until its next turn
**Blue** reconfigures by migrating a single process from a physical node* *to another.
**Blue** and **Red **have perfect knowledge of each other’s configurations.
- Aim of each player
**Red** tries to force **Blue** into a position where it cannot recover by transitioning to another element of *BC*.
**Blue** tries to find a “loopy” game where it can always return to a previous configuration.

## An Example Game

| Blue Configuration | Reconfigure |
| --- | --- |
| 1 | 2, 3, 4 |
| 2 | 1, 5, 6 |
| 3 | 1, 7 |
| 4 | 1,10 |
| 5 | 2, 8, 9 |
| 6 | 2, 9 |
| 7 | 3, 10 |
| 8 | 5 |
| 9 | 5, 6 |
| 10 | 4, 7 |

| Zombie Move | Zombies | Disrupt Blue Configurations |
| --- | --- | --- |
| A | 3, 5  | 1, 2, 7  |
| B | 1, 6  | 3, 4, 5  |
| C | 3, 4  | 2, 6, 9  |
| D | 1, 5  | 8, 9, 10  |

## An Example Game

- 5

- 2

- 1

- 6

- 2

- 9

- NA – Zombie at A

- 6 is chosen

- NA – Zombie at C

- NA – Zombie at A

- A

- C

- [1, 2, 7]

- [2, 6, 9]

- RED WINS THE GAME !!!!

## An Example Game

- A

- [1, 2, 7]

- 5

- 1

- 6

- NA – Zombie at A

- 5 is chosen

- B

- [3, 4, 5]

- 2

- 8

- 9

- Loop – (2-5-2) Blue Wins

- 9 is chosen

- C

- [2, 6, 9]

- 5

- 6

- NA – Zombie at C

- Loop – (5-9-5) Blue Wins

- BLUE WINS
- THE GAME !!!!

## Thermographs

- Any given enterprise relies on multiple distributed processes
- Each distributed process represents a single game
- An attacker can not expect to destroy all of the processes at any point in time  tries to maximize the number of disabled processes
- This situation describes a “sum of games” problem
- Blue and Red have alternate moves
- At each turn, a player chooses a game (process) and a move to make in that game
- This problem has been shown to be  P-Space complete
- Thermographs can be used to find the near optimal solution
- Use of thermographs to choose a game from all the games and then make a move in that game

## Applications

**Local Area Networks (LANs):** Zombies in the larger Internet may target processes on the LAN
- To identify system bottlenecks
- To determine if volume of the external traffic can compromise distributed processes on the LAN.
**Corporate Networks:*** *Zombies can attack the VPN traffic traveling through global Internet
- Graph structure of the VPN connections can be used to create an adaptive VPN infrastructure that can tolerate DDoS attacks.
**Global routing problems:*** *Routing between AS uses the BGP, which is subject to instability in the presence of flooding DDoS attacks.
- AS graph structure can be used to determine if the volume of traffic reaching sensitive BGP nodes is enough to disrupt the routing between critical agencies.