# Presentation: 091677

## Defending against Large-ScaleDistributed Denial-of-Service Attacks

- Department of Electrical and Computer Engineering
- Advanced Research in Information Assurance and Security (ARIAS) Lab
- Virginia Tech
- Jung-Min Park

## Overview of DoS Attacks

- What is a DoS attack?
- An attack that disrupts network services to legitimate clients
- Large-scale Distributed DoS (DDoS) attack of Feb. 2000
- A DDoS attack took down Yahoo, EBay, and Amazon.com
- Outage caused millions of dollars in lost revenue
- Hundreds of attacks are observed each day
- Global corporations lost over $1.39 trillion in revenue due to security breaches in 2000, and
- Over 60% are due to viruses and DoS attacks (http://www.captusnetworks.com/BeenDoSd.pdf)
- FBI reports indicate DoS attacks are on the rise

**Notes:**
What are DoS attacks?
Attacks that disrupt network services to legitimate clients
DDoS attacks
Also called flooding-based DDoS attacks or flooding attacks
Unlike other forms of DoS attacks, DDoS attacks do not rely on particular system weaknesses or network protocols. 
Instead, they exploit the very architecture that forms the foundation of Internet design—reliance on intelligent end hosts connected by a relatively simple network (i.e., the end-to-end principle). In this architecture, an adversary can freely send useless packets toward a victim, while the victim has no way of stopping those packets from reaching the destination. 
In a typical DDoS attack, an adversary compromises a large number of third party hosts (known as “zombies”) and use them as “traffic amplifiers” to direct an enormous amount of traffic toward a particular victim (or its network).  

## Taxonomy of DoS Attacks

- Attacks that exploit system design weaknesses
- Teardrop attack
- Ping-of-death attack
- Land attack
- SYN flood attack
- Attacks that exploit the weakness of particular protocols
- Attacks against authentication protocols
- Attacks against key agreement protocols
- Attacks that exploit the asymmetry between “line rate” and throughput of hosts and routers
- Flooding-based DDoS attacks

**Notes:**
Teardrop attack: Some implementation of the TCP/IP IP fragmentation re-assembly code do not properly handle overlapping IP fragments. Teardrop is an attack tool that exploits this vulnerability. 
IP layer attack
Solution: apply software patch
Ping-of-death attack: According to RFC-791, an IP packet’s maximum size (including header) is 65,535 (216-1) bytes. An adversary can attack a machine by sending it packets that are larger than this size. 
Typically, the easiest way to create such packets is to use the “ping” program. The ping program would send ICMP ECHO request packets that exceed the max. size limit to the victim.
IP layer attack
Solution: apply software patch 
Land attack: Spoof IP source address and port # so that they are identical to the address and port # of the destination. 
TCP layer attack
Solution: apply software patch
SYN flood: An attacker sends a large number of SYN packets from spoofed IP addresses to the victim, thus creating a large number of half-open connections that are stored on the server. The server has limited memory in terms of the number of half-open connections it can store.  An attacker can effectively exhaust the server’s resources by filling the buffer of half-open connections which denies service to future clients.
TCP layer attack
Sol: SYN cookies, SYN caches, TCP client puzzles
Attacks against authentication and key agreement protocols exploit application level protocols.

## Flooding-based DDoS Attacks

- Exploits the asymmetry between “line rate” and throughput of hosts and routers
- Large volume of packets is sent toward a victim
- Consumes bandwidth and processing power of the victim
- DDoS attacks utilize attack handlers and zombies to hide the identity of the real attacker

**Notes:**
DDoS attacks flood the target server or network with an enormous amount of packets, thus overwhelming the packet processing capabilities of the server and routers in its vicinity. Such attacks are possible because a typical peak network “line rate” exceeds the throughput of typical servers and routers, often by more than an order of magnitude.
Ex) analysis of Internet flooding-based DDoS attacks shows that peak line rates can exceed 600K packets per second, yet specialized firewalls designed to protect servers can be disabled by line rates as low as 14K packets per second. Simulation results show that even a highly replicated service with 64 application servers designed to withstand flooding attacks may be overwhelmed by a well-coordinated large-scale attack. 
IP layer attack

## Lines of Defense Against DDoS Attacks

-  Apply software patch
-  SYN cookies, client puzzles
-  Design DoS attack resistant systems
-  Overlay networks

-  Signature (misuse) detection
-  Anomaly detection

-  _**Client puzzles**_
-  Aggregate filtering, pushback
-  Overlay networks

-  _**IP traceback: packet marking**_
-  IP traceback: packet logging
-  “Attack traceback”

**Notes:**
Overlay networks: Mayday is one example.
Mayday uses a distributed set of overlay nodes that are trusted to distinguish legitimate traffic from attack-traffic. To protect a server from DDoS traffic, Mayday prevents general Internet hosts from communicating directly w/ the server by imposing a router-based, network-layer filter ring around the server. Instead, clients communicate w/ the overlay nodes, who verify that the client is permitted to use the service. These overlay nodes then use an easily implemented lightweight authenticator (such as sending the traffic to the correct TCP port on the server) to get through the filter ring.
Detection
Signature detection: Detects intrusions or attacks by comparing network data with a database of known attack signatures. 
Drawback: Cannot detect novel attacks.
Anomaly detection: Decides that an intrusion has occurred if the observed parameter deviates from the normal threshold (that was set beforehand).
Drawback: High rate of false alarms.
Aggregate filtering
In most cases, congestion is caused by a well-defined subset of the traffic – a high bandwidth aggregate. This scheme detects and controls high bandwidth aggregates at the downstream router.
Note: Identifying aggregates is a nontrivial problem. In one paper, destination address was used to identify aggregates. One can use other parameters such as the source address (although a source address cannot be trusted).
Pushback
When implementing aggregate filtering at a downstream router is not enough, this router asks upstream routers to cooperatively filter aggregates (thus, called pushback).
IP traceback
Packet marking: mark traceback info. on the IP header of packets	
Packet logging: let routers store traceback info.
Attack traceback: tracing the actual attacker, and not zombies.

## TRACK:A New Approach to IP Traceback

## The IP Traceback Problem 

- IP traceback strategies:
- Probabilistic Packet Marking (PPM)
- Packet Logging

**Notes:**
In all IP traceback schemes, we assume that the attack detection unit can distinguish between attack packets and benign packets.

## Limitations of Current IP Traceback Schemes 

- Do not support last-hop traceback
- Packet logging schemes
- Significant computation overhead on routers
- Significant storage overhead on routers
- Packet marking
- Not scalable: Complexity of path reconstruction process increases rapidly as number of attackers increase
- Large number of packets need to be collected

**Notes:**
Packet logging
Even with the latest optimized packet logging technique, a router on a duplex OC-192 link would need to compute eight million hash functions per second and store 5 GB of data per hour. 
Packet marking
Complexity of path reconstruction is O(N8), where N is the # of attackers.
Multiple fragments (marked packet) from the same router on an attack path are needed to trace back that attack path.  large # of packets need to be collected. 

## rouTer poRt mArking and paCKet filtering (TRACK)

- Objective:
**Reduce computation complexity of path reconstruction**
**Reduce number of packets that need to be collected**
- Support last-hop traceback
- Support gradual deployment
- Filter attack traffic using traceback information

**Notes:**
The framework is primarily for the last bullet. The box of “Route Port marking for traceback to zombies” meet the requirement of the first two bullets.

## Basic Principles of TRACK

- 	A string composed of locally-unique router interface port numbers is a globally unique identifier of a path.

**Notes:**
The router port marking scheme marks packets by probabilistically writing a router interface’s port number, a locally unique 6-digit identifier, to the packets it transmits. We use the term “port” to denote a router’s hardware interface. A router allocates a number to every port and can forward packets to a specified port number. The port number is assigned in advance and locally unique. 
A string composed of locally-unique router input port numbers is a globally unique identifier of a path. Use C3 or C4 for example.
Mention that in a shared media LAN there is a MAC address to 6-digit port number mapping. Mention that this is the key for last-hop traceback.
Some clients are connected to a border router via a broadcast link-layer channel (such as a LAN), instead of distinct ports. In that case, C1, C2 and C3 may be connected to the same port of M. One method of solving this problem is to map MAC addresses to 6-bit identifiers, and then use these six bits as the PN field value for packet marking. If a router port only hears frames coming from a single MAC address, the appropriate port number is marked on the incoming packets. If multiple MAC addresses are heard, the port maps each address to a unique 6-bit identifier and marks the packets with the respective 6-bit identifiers 
Mention that 6-digit is enough because router degree is smaller than 64 for 98.5% routers in the Internet. Moreover, we can overcome the problem by marking the packets twice.

## Marking Traceback Information in the IP Header

**Notes:**
IP header coding. The easiest way is to forbid IP fragmentation. However, TRACK supports compatibility with IP fragmentation. Mention that this problem has been well studied and using Identification field is widely accepted.
Studies have shown that fragmented packets account for less than 0.25% of Internet traffic. Moreover, fragments that cannot be reassembled can be recovered by high-level protocol retransmissions.

## Router Port Marking Procedure

- Active Port Marking Mode (APMM) at probability of *p *:

- Passive Port Marking Mode (PPMM) at probability of 1 – *p *:

**Notes:**
How to transmit port number information to the victim?

## Path Reconstruction Process of TRACK

- Objective
- Recover the port number sequence of an attack path and convert them into a sequence of router IP addresses
- Approach
- Distribute the path reconstruction process among the victim’s upstream routers (victim  attacker’s border router)(similar to Pushback)
- Employ a *trace table* and *trace packets*
- Use same info. to filter attack traffic at the border router of the attacker
- Computational Complexity: *O*(*N*2)

## Path Reconstruction Process of TRACK

- MKF = 1, XOR = PN = 18,Distance = TTL5 (254) = 30

- MKF = 1, PN = 18,Distance = 30, TTL5 = 27, XOR = 2 (=18  47  34  21);
- d = 30 – 27 = 3

- Assume C3 is sending packets to V
- M is in APMM; F, B, and A are in PPMM

## Path Reconstruction Process of TRACK

| Router closest to V in APMM * | Hop Count: d | Port Number: PN(d) | XOR: XOR(d) |
| --- | --- | --- | --- |
| A | 0 | 21 [010101]** | 21 |
| B | 1 | 34 [100010] | 55 ( 34 = 21) |
| F | 2 | 47 [100111] | 16 ( 47 = 55) |
| M | 3 | 18 [010010] | 02 ( 18 = 16) |

- d = Distance – TTL5

- XOR(d+1)  PN(d+1) = XOR(d)
- C3’s path: 21-34-47-18

## Number of Packets Needed for Path Reconstruction

*p* = 0.04

*p* = 0.01

**Notes:**
TRACK is better because only one fragment is required.

## False Positive Rate

- Skitter Internet map

- Complete tree topology model

**Notes:**
We adopt two different network topologies for our simulations. The first topology was chosen from the  Skitter Internet map [Skit04]. Based on the provided undirected link data, we first chose a router with a degree of six as the victim’s border router, and then randomly chose several distinct routes originating from it. The second network topology is an n-degree complete tree model. In the n-degree complete tree model, we model the victim’s upstream routers as a subset of a complete tree rooted by its border router, with every router having n adjacent routers or hosts (i.e., one parent router and (n1) children routers or hosts. Recall that in the Skitter project, the average router degree in the Internet was found to be 6.34. In our simulations, we use n = 6 and n = 8. 
In [Jin03], experiments have shown that a typical hop count distribution from clients to a server can be regarded as a Gaussian distribution, with a mean of 16.5 and a standard deviation of 4. In our simulation experiments for both network topologies, we used this distribution for generating the routes’ hop counts. The   upper bound and lower bound of the hop counts were set to 32 and 1, respectively.

Restricted to the victim’s upstream tree.

## Gradual Deployment

- Complete tree topology model

- Skitter Internet map

## Chained Puzzles:A Novel Approach to IP-Layer Puzzles

## Client Puzzle Protocols

- A technique used to mitigate DoS attacks that does not rely on distinguishing between attack traffic and legitimate client traffic
- Puzzles are typically based on difficult problems from cryptosystems
- Partial reversal of a hash function
- Exhaustive key search in a private key cryptosystem

**Notes:**
To date all client puzzle algorithms are based on hash functions.

## Basic Principles of Chained Puzzles

- Puzzle algorithm: Exhaustive key search of XTEA6
- XTEA6: Truncated version of the XTEA encryption algorithm

- Puzzle Routers
- Puzzle distribution and verification is performed by the “first-hop” border router called a Puzzle Router
- Puzzles are enabled by downstream Puzzle Routers

## Message Exchange Between Puzzle Routers

- Downstream Puzzle Routers enable puzzles at the upstream Puzzle Routers

## Optimal Location for Detection and Mitigation

**Detection:  **DDoS attacks are detected easily near the server or the main victim of the attack (packet loss, heavy congestion, etc.)
**Mitigation:  **Preventing or mitigating an attack is best performed as close to the source of the attack as possible

## Puzzle Distribution

- How do we distribute puzzles?
- Easy in TCP  3-way handshake
- IP is connectionless and a client puzzle protocol is connection oriented
- Client asks for a puzzle
- Server sends the puzzle to the client
- Client solves the puzzle, sends the solution back to the server

- Solution
- Puzzle solution chaining

## Puzzle Solution Chaining

- When Puzzles are enabled, “bootstrapping” procedure is needed to create the first puzzle
- Subsequent puzzles are created by the client independently
- Current solution becomes plaintext for the next puzzle

## Puzzle Solution Chaining – cont’d

- Client creates a chain of puzzles

- The Puzzle Router reissues the puzzle challenge periodically

## Probabilistic Verification

- Probabilistic verification
- Puzzle Routers verify incoming puzzles according to  a given probability
- Increase performance and throughput of the Puzzle Routers

## Simulation Results: NPSR	

- Normal Packet Survival Ratio (NPSR)
- Percentage of legitimate packets that can make their way to the victim in the midst of a DDoS attack

**Notes:**
Q is the prob. that an attacker solves a puzzle and embeds it in a packet.

## Future Work	

- IP Traceback
- Improve scalability
- Better support of gradual deployment
- Minimize the number of false positives
- Support IP fragments
- Support router degrees greater than 64
- Client puzzle protocol
- Specification of a Puzzle Router’s functions
- Resolve protocol architecture issues
- Counter puzzle protocol circumvention
- Ensure fairness

## Questions?

## Conclusion

- Last-hop traceback capability: a step closer to attack traceback
- Support of gradual deployment: more realistic solution
- Using router port instead of router as the atomic unit for traceback: fewer packets and less computational complexity for path reconstruction, finer granularity, and less false positive
- Attack detection at the victim and packet filtering at the zombies’ border routers: the optimal location for both modules

**Notes:**
Tracing back to a border router may have a huge list of network activities that result in a great number of flows being recorded by such tools as Netflow. With the capability of last-hop traceback, we can filter out the records that are specific to a certain host. By collecting such records for multiple zombies, the commonality among them could indicate the source of the real attacker.
FIT (which occurred in INFOCOM 2005) is the only seen scheme that support gradual deployment

## Backup

## Path Reconstruction Process of TRACK

| Router closest to V in APMM | Hop Count: d  | Port Number: PN(d) | XOR: XOR(d)  |
| --- | --- | --- | --- |
| A | 0 | 21 [010101] | 21 [010101] |
| A | 0 | 42 [101010] | 42 [101010] |
| B | 1 | 34 [100010] | 55 [110111] ( 34 = 21) |
| C | 1 | 62 [111110] | 20 [010100] ( 62 = 42) |
| F | 2 | 47 [100111] | 16 [010000] ( 47 = 55) |
| H | 2 | 08 [001000] | 28 [011100] ( 08 = 20) |
| M | 3 | 18 [010010] | 02 [000010] ( 18 = 16) |
| P | 3 | 32 [100000] | 60 [111100] ( 32 = 28) |

- Objective
- Recover the port number sequence of an attack path and convert them into a sequence of router IP addresses
- Approach
- Distribute the path reconstruction process among the victim’s upstream routers (victim  attacker’s border router)(similar to Pushback)
- Employ a *trace table* and *trace packets*
- Use same info. to filter attack traffic at the border router of the attacker
- Computational Complexity: *O*(*N*2)

**Notes:**
How to reconstruct the path after collecting enough packets? 
Packet filtering can be executed in the same process.

## Limitation of Current Attack Mitigation Schemes

- Problem
- Conventional countermeasures attempt to detect and filter at the same location
- Fact
- Attack detection is easier closer to the victim, packet filtering is more effective closer to the attack source
- Solution
- Separate the two functions in separate modules

**Notes:**
the flow of packets caused by a DDoS attack resembles water passing through a “funnel”: attack packets are generated at the wide end of the funnel, and the victim is located at the narrow end, receiving all the attack packets coming from the wide end. 
DDoS attacks can be most readily detected at the victim network since all attack packets can be observed. In contrast, it is more difficult for an individual source network, where attack sources are located, to detect an attack unless a large number of attack sources are located in that network. 
For mitigation, the opposite is true. It is most effective to filter or rate limit attack packets as close to the attack source as possible. The effectiveness of a mitigation scheme declines rapidly as attack packets are dropped closer to the victim.  

## Attack Mitigation (Packet Filtering)

- Location of attack detectionand packet filtering:
- At the victim
- In the network
- At the attack source

## Probabilistic Packet Marking (Basics)

- Routers mark packets with fragments of its IP addresses probabilistically
*Identification* field in IP header is used (The probability of IP fragmentation is 0.25%)
- The victim can collect IP fragments from many packets to reconstruct attacking path

**Notes:**
Because TRACK is basically a type of PPM scheme, we first briefly introduce the basic mechanism of a PPM scheme.

## Overhead of Packet Logging

**For a OC-192 link:**
- TRACK: 50k destination IP address insertion or update per second; 900MB/hours storage, upper-bounded by 20GB
- The scheme in [Snoe01]: 60 million hash operations per second; 44GB storage per hour, bounded by the maximum allowed traceback time
- The scheme in [Li04]: 8 million hash operations per second; 5.2GB storage per hour, bounded by the maximum allowed traceback time

**Notes:**
In case there is question on the false positive. We need mention that false positive is restricted within the victim’s upstream tree. The method is to log the packet’s destination IP addresses, so that a router knows whether it need to pushback a trace table or not.

## False Positive Analysis

**False Positive Analysis**

**Notes:**
Rx becomes a false positive when in the trace table there is a record with three fields (hop count, PN, XOR) happening to be the same as the record actively marked by Rx. If a zombie is far enough, the probability of colliding with the record becomes the probability of the coincidence of the same 12-bit  PN and XOR. This probability is independent for each hop traceback since the port numbers are allocated randomly.

## Gradual Deployment

- Neighbor-Discovery Handshake Protocol
- Jump back to source during path reconstruction

**Notes:**
The shaded routers are TRACK-enabled (updated). The border router of the victim must be updated. Since Distance field is not changed in PPMM (this is not true for most of other traceback schemes), hop count can still be computed. A can jump to F with the information of the neighborhood. F can filter packets on port 47, which may increase false positive.