Transcript Group_11_slide

Expert Systems With Applications, 2008 - Elsevier
Haining Wang, Member, IEEE,
Cheng Jin, and Kang G. Shin, Fellow, IEEE
Speaker:
羅聖傑 R96725015
鄭京恆 R96725026
劉俊良 R96725027
2000年2月
Yahoo遭受DDoS攻擊以致於無法提供服務
2
2008年4月
台灣電玩大站巴哈姆特、遊戲基地，相繼
遭到大陸駭客以DDoS攻擊以致於癱瘓
難道，我們對於DDoS，一點辦法都沒有!?
3
當然是 大錯特錯 ！！！
我們網路學術界高手如雲，
豈會敗在區區一個DDoS之下，
這篇文章，正是教導你如何對抗DDoS！
4

IP spoofing (IP欺騙)
同一台電腦用同一個IP，卻可以用某些方法，將自己發出
之封包的source IP改掉，以隱藏自己的IP位址，常用於
DDoS的攻擊。

Distributed Denial of Service
(DDos， 分散式阻斷服務)
利用許多傀儡電腦，一起發送大量的垃圾封包給server，
運用這些封包攻擊server，使server一直忙於處理垃圾封包，
而無法服務正常使用者。
5

Introduction

Basic Principles in HCF

Does Hop-Count Filtering Really Work?

Construction of IP2HC Mapping Table

Running States of HCF

Conclusion and Feature Work
6

What is the Problem ?
 Spoofed IP
▪ A compromised Internet host can spoof IP packed with
arbitrary source IP address into packet header.
▪ Distributed Denial of Service (DDoS)
▪ Router-based
▪ Host-based
▪ Distributed Reflection Denial of Service (DRDoS)
7

Defense Mechanisms
 Distributed Denial of Service (DDoS)
▪ Router-based approach
▪ Installs defense mechanisms inside IP routers
▪ Coordination among different routers and network, wide –spread
deployment
▪ Host-based approach
▪ Sophisticated resource-management
▪ Reducing the resource consumption of each request
▪ Most work at transport-layer
8

Defense Mechanisms (Drawbacks)
 Distributed Denial of Service (DDoS)
▪ Router-based approach
▪ Not only router support, but also wide-deployment
▪ Host-based approach
▪ Most work at transport-layer, can not prevent from consumming
CPU resource
9

Without detecting and discarding spoofed IP
traffic at the very beginning , Spoofed packets
will share the same resource principals and
code path as legitimate request.

The ability to detect and filter spoofed packets
at the IP layer without router support is
essential to protect against DDoS.
10
Hop-Count Filtering

Goal
 Light-weight scheme
 Without using any cryptographic methodology or router
support
 Screen out most bogus traffic
11
Hop-Count Filtering

Fundamental Idea
 Utilize inherent network information
1. Each packet carries
2. Attacker cannot easily forge
▪ Number of hops ! ( indirect from the Time-to-Live ,TTL
field)
12
Hop-Count Filtering

Fundamental Idea
 Hop-Count (number of hops):
most randomly spoofed IP packet , when arriving
at victims, do not carry hop-count values that are
consistent with the spoofed IP address.
Hop-Count Filtering
with IP-to-Hop-Count (IP2HC) table.
13
Hop-Count Filtering (HCF)
 Two running state!
▪ 1. Learning
▪ Learn and train IP2HC table
▪ Under normal conditions, HCF stay in here.
▪ Do not discard any packet, no collateral damage
▪ 2. Filtering
▪ Switch in here while detecting an attack.
▪ Discard any packet with mismatching hop-count
14

Introduction

Basic Principles in HCF

Does Hop-Count Filtering Really Work?

Construction of IP2HC Mapping Table

Running States of HCF

Conclusion and Feature Work
15

A. Hop-Count Computation
 Hop-Count is derived from 8-bit IP header field :TTL field
Hop-Count = Initial TTL – final TTL value.
 The destination only sees the final TTL value
 Most initial (OS default) TTL value are far apart.
▪ 30, 32, 60, 64, 128, 255
 Few internet hosts are apart by more than 30 hops
 How to decide the initial TTL value ?
▪ The Closest One.
 Drawback…?
▪ “odd” initial TTL value may be incorrectly identified as spoofed.
16

B. Capturing Legitimate Hop-Count Value
 In order to maintain an accurate IP2HC table
▪ Capture only valid hop-count mappings
▪ Capture only legitimate change
▪ Foil any attempt to slowly pollute the IP2HC
▪ The IP2HC should be updated only by packet belonging
to TCP connections in the established state.
▪ User-configurable parameter k to adjust the frequency
of update.
17

C. Inspection and Validation Algorithm
For each packet:
extract the final TTL Tf and the source IP address S;
infer the initial TTL Ti;
compute the hop-count Hc = Ti – Tf;
index S to get the stored hop-count Hs;
if( Hc != Hs)
the packet is spoofed;
else
the packet is legitimate;
18

Introduction

Basic Principles in HCF

Does Hop-Count Filtering Really Work?

Construction of IP2HC Mapping Table

Running States of HCF

Conclusion and Feature Work
19
Feasibility of HCF hinges on four factors
1. diversity of hop-count values
2. effectiveness in detecting spoofed packet
3. robustness against evasions
4. stability of hop-counts
20

1. Diversity of Hop-Count Distribution
 A good hop-count distribution should have two
properties
▪ 1. Symmetric around the mean value
▪ Advantage of the full range of hop-count
▪ 2. reasonably diverse over the entire range
▪ Help maximize the effectiveness of HCF
21

1. Diversity of Hop-Count Distribution
 Use the raw traceroute data from 47 different traceroute gateways
22

1. Diversity of Hop-Count Distribution
 Gaussian distribution ( bell-shaped curve) founded
23

1. Diversity of Hop-Count Distribution
 Gaussian distribution ( bell-shaped curve) founded
CDF of means of hop-count dis.
CDF of standard deviations of hop-count dis.
The larger the σ, the more diverse the HC dis. , and the more effective HCF will be!
24

2. Effectiveness of HCF Against Simple Attacks
What fraction of spoofed IP packets can be detected
by proposed HCF ??
 Assumption:
▪ Potential victim servers know the complete mapping
between client IP address and hop-counts
▪ Attacker evenly divides the flooding traffic among the
flooding sources
▪ Most of the available DDoS attacks do not alter the intial
TTL value of packets
25

B. Effectiveness of HCF Against Simple Attacks
Two scenarios!
 Single Flooding Source
 Multiple Flooding Sources
26
2. Effectiveness of HCF Against Simple Attacks
1.Single Flooding Source -> same hop-count

Fraction of spoofed IP
address that cannot be
detected is
αh
, and identified and
discarded by HCF is (1-αh)
90% of success detection;
HCF is highly effective
against a single attacking
source!!
27

2. Effectiveness of HCF Against Simple Attacks
 n sources of flood, total F packets
 Adding more flooding sources does not diminish the
ability of HCF to identify spoofed IP packets!!
28

3. Robustness Against HCF-Aware Attackers
 1. Randomization of Initial TTL
▪ Randomizing the initial TTL value create an illusion of
attacking packets having many different hop-count
value
▪ Randomize from range Ir = [Id + hz - 30, Id + hz -1]
▪ Id : default initial TTL, hz : hop-count from source to victim
▪ The final TTL value Tv follow the same R random distribution.
29

3. Robustness Against HCF-Aware Attackers
 1. Randomization of Initial TTL
▪ Uniform distribution
▪ Based on hop-count distribution
30

3. Robustness Against HCF-Aware Attackers
 2. Learning of Hop-Count Values (set a n appropriate
initial TTL value for each spoofed packet)
hz : hop-count from zombie
hs : hop-count from spoofed IP
▪ Learning hz from “a” zombie to hop-count is easy (by using
traceroute)`, but… from “n” zombies ?
▪ Learning hs ? Attacker has to build priori an IP2HC that
cover the “entire” spoofed IP address space
31

4. Hop-Count Stability
 The stability in hop-count between server and clients is
“crucial” for HCF’s accuracy and effectiveness.
 Frequent changes lead to excessive mapping update,
enlarge damage from out-of-date mapping
 So… Is current Internet stable ..?
32

4. Hop-Count Stability
 According to studies on end-to-end routing stability
▪ Internet paths were found to be dominated by a few prevalent routes
▪ About 2/3 of internet paths were observed to have routes persisting for
either days or weeks.
 According to observation
▪ Daily traceroute measurement, ten-minute intervals, among 113 sites,
from Jan 1st to Apri 30, 2003
-> 95% of the paths had fewer than 5
observable daily change
 According to recent Internet experiments
▪ A large fraction of destination prefixes have remarkably stable BGP.
▪ Popular prefixes tend to have stable BGP routes for days or weeks
▪ A vast majority of BGP instability stems from a small number of unpopular
destinations
It’s reasonable to expect hop-count to be stable in the Internet.
33
Also, the proposed filter contains a dynamic update procedure to get hop-count changes

Introduction

Basic Principles in HCF

Does Hop-Count Filtering Really Work?

Construction of IP2HC Mapping Table

Running States of HCF

Conclusion and Feature Work
34

We know that HCF can remove nearly 90% of
spoofed traffic with an accurate mapping
between IP addresses and hop counts. Thus,
building an accurate IP2HC mapping table is
critical. Our objectives in building a table are:
1) accurate IP2HC mapping
2) up-to-date IP2HC mapping
3) moderate storage requirement.
35

IP Address Aggregation
 Aggregation Techniques
 Evaluation of Filtering Accuracy

Table Initialization and Update
 Initialization and Addition of New Entries
 Updating Hop-Count

Hop-Count Ambiguity Caused by NATs.
36

Ideally, the IP2HC mapping table has one
entry for each valid IP address.

But this will consume a very large amount of
memory.

So, we use IP address aggregation.
37



Aggregating hosts according to address
prefix, especially the 24-bit address prefix.
We use an array with one-byte hop-count
entry per network prefix, the storage
requirement is 224 bytes or 16 MB.
But IP addresses within each 24-bit address
prefix may be allocated to different physical
networks, and they do not have identical
hop-counts.
38

To obtain a more accurate IP2HC mapping,
one can further divide IP addresses within
each 24-bit prefix into smaller clusters based
on hop-count.

Using a binary tree, we can easily cluster IP
addresses.

In our test, we are able to aggregate 11 /17 IP
addresses into four network prefixes.
39
40

We assume that the attacker generates
packets by randomly selecting source IP
addresses among legitimate clients.

We further assume that the attacker knows
the general hop-count distribution for each
web server and uses it to randomly generate
a hop-count for each spoofed packet.
41

We use two symbols:
 False Positives
▪ Those legitimate client IP addresses that are incorrectly
identified as spoofed.
 False Negatives
▪ Spoofed IP addresses that go undetected by HCF.

A good aggregation method should minimize
both.
42
43
47 routers
test results
44

Clustering-Based Filtering has nearly identical
performance as 32-bit Strict Filtering.

Clustering-based Filtering increases the
number of entries by no more than 20%.

The 32-bit Strict Filtering increases the
number of entries by at least 67%.
45

Initialization and Addition of New Entries.
 The initial collection period should be long
enough to ensure good filtering accuracy.

Updating Hop-Counts.
 IP2HC table only update when there is an TCP
connection.
 Reclustering is complex, but should have a
relatively small impact on system performance.
46




What is NAT (Network Address Translation)?
How does it lower the IP2HC mapping
accuracy?
But NAT automatically prevents the zombies
behind NAT boxes from IP spoofing.
To have NAT boxes reset the TTL value of
each outgoing IP packet to a default initial
TTL.
47

Introduction

Basic Principles in HCF

Does Hop-Count Filtering Really Work?

Construction of IP2HC Mapping Table

Running States of HCF

Conclusion and Feature Work
48

Tasks in two states :
 Learning state
▪ sample incoming packets for hop-count inspection
▪ calculate the spoofed packet counter
▪ update the IP2HC mapping table
 Filtering state
▪ must examine every packet (instead of sampling only a
subset of packets)
▪ discards spoofed packets
49
50

Server :

HCF should not alternate between the
learning and filtering states when t fluctuates
T1 around .
51



To protect server resources such as CPU and
memory, HCF can be installed at a server
itself or at any network device near the
servers.
This scheme will not be effective against
DDoS attacks that target the bandwidth of a
network.
The solution must involve the stub network’s
ISP.
52

Solution :
 To maintain an updated HCF table since only end-
hosts can see established TCP connections.
 If under an attack, install a packet filter based on
the HCF table on the ISP’s edge router.
 Once the HCF table is enabled at the ISP’s edge
router, most spoofed packets will be intercepted
53

Distributed Reflections Denial of Service
(DRDos).
 An attacker forges IP packets that contain
legitimate requests by setting the source IP
addresses of these spoofed packets to the actual
victim’s IP address.
 The attacker then sends these spoofed packets to
a large number of reflectors

But it’s no use for HCF.
54

Introduction

Basic Principles in HCF

Does Hop-Count Filtering Really Work?

Construction of IP2HC Mapping Table

Running States of HCF

Conclusion and Feature Work
55

We presented HCF, IP2HC mapping table.

It can remove 90% of spoofed traffic.

HCF is a simple and effective solution in
protecting Internet servers against spoofed IP
packets and readily deployable in end-system.
HCF is not a complete solution to the generic
DDoS, but it deprives an attacker of his power
weapon.

56

We need a systematic procedure for setting
the parameters of HCF, such as the frequency
of dynamic updates.

We would like to build and deploy HCF in
various high-profile server sites to see how
effective it is against real spoofed DDoS traffic.
57
Thank You
58