R377 2017 11 sakuma CS

Loading....

Loading....

Loading....

Loading....

Loading....

全文

(1)

宛先までのホップ数解析による

Traceroute

を用いた

Target Link Flooding Attack

検知手法

佐久間 慧

朝比奈 啓

春田秀一郎

笹瀬

慶應義塾大学

神奈川県横浜市港北区日吉

3-14-1

E-mail:

{sakuma,asahina,haruta}@sasase.ics.keio.ac.jp,

††

sasase@ics.keio.ac.jp

あらまし 近年,新種のDDoS攻撃であるTarget Link Flooding Attackの検知が急務である.この攻撃は,特定の

リンクを輻輳させることで標的のネットワークをインターネットから孤立させることが可能である.また,標的が直

接攻撃されているわけではないため,従来のDDoS攻撃への対策を講じにくいという特徴がある.この攻撃への対策

はいくつか存在するが,攻撃の予兆を検知することができるTracerouteを用いた手法が着目されている.この方式

ではTracerouteの急激な増加を観測した場合に攻撃を検知する.しかし,攻撃者がTracerouteの送信レートを下げ

た場合は検知不可能である.本論文では,宛先までのホップ数解析によるTracerouteを用いた検知手法を提案する.

正規のTracerouteが分散するのに対し,攻撃者のTracerouteは特定のホップ数内に集中するということに着目し,

Tracerouteをホップ数毎に分けて観測することにより,変化が強調され,従来では捉えることができなかった攻撃を検

知することが可能になる.コンピュータシミュレーションにより,提案手法が従来手法よりも優れていることを示す.

キーワード ネットワークセキュリティ,DDoS攻撃,検知

Traceroute based Target Link Flooding Attack Detection Scheme by

Analyzing Hop Count to the Destination

Kei SAKUMA

, Hiromu ASAHINA

, Shuichiro HARUTA

, and Iwao SASASE

Dept. of Information and Computer Science, Keio University

3-14-1 Hiyoshi, Kohoku, Yokohama, Kanagawa 223-8322, Japan

E-mail:

{sakuma,asahina,haruta}@sasase.ics.keio.ac.jp,

††

sasase@ics.keio.ac.jp

Abstract Recently, the detection of target link flooding attack which is a new type of DDoS (Distributed Denial

of Service) is required. Among several schemes for target link flooding attack, the scheme focusing on traceroute is gathering attention. That scheme detects the attack by finding rapid increase of traceroute. However, it cannot work when attacker’s traceroute ratio is low. In this paper, we propose traceroute-based target link flooding attack detection scheme by analyzing hop count to the destination. By analyzing the number of traceroutes per hop counts, the change can be emphasized. By computer simulations, we show that our scheme has more robustness compared with the conventional scheme.

Key words Network security, Target link flooding attack, Detection

1.

Introduction

DDoS (Distributed Denial of Service) attack is one of the

main threads of the current Internet services. In DDoS

at-tack, attackers exhaust legitimate service’s bandwidth and

resources (e.g. sockets, CPU memory) by a lot of network entities sending many packets to the targeted server.

Re-cently, in this context, target link flooding attack which is

a new type of DDoS attack has been proposed [1, 2]. This attack cuts off specific links over the Internet and

discon-nects a specific region from other regions. More specifically,

an attacker targets an area and chooses links which connect

the area to the Internet. Then, a lot of bots commanded by

the attacker send low rate packets to different destinations through the links. As a result, the corresponding links are

flooded and the area is isolated. Target link flooding attack

― 9 ―

This article is a technical report without peer review, and its polished and/or extended version may be published elsewhere. 一般社団法人 電子情報通信学会 信学技報

THE I NSTI TUTE OF ELECTRONI CS,         I EI CE Tec hni c al Repor t

I NFORMATI ON AND COMMUNI CATI ON ENGI NEERS CS2017- 56 ( 2017- 11)  

(2)

has two remarkable features: 1) the target area is not directly

attacked and 2) the attacker uses valid IP addresses or

trans-mits low rate traffic. For these reasons, although there are a

lot of researches to detect and mitigate DDoS attacks [3–5], those detection schemes against DDoS attacks do not work

effectively against the target link flooding attack.

In order to deal with target link flooding attack,

sev-eral schemes have been proposed [6–9]. Those schemes are

roughly classified into two categories: Avoidance schemes and Detection schemes. In the avoidance schemes, they aim to

mitigate the damage of the attack [6, 7]. Lee et al. propose

CoDef which uses collaborative rerouting and rate control

strategies [6]. That scheme is an AS (Autonomous System)

level target link flooding attack avoidance scheme. When the attack occurs, a congested router sends a rerouting request

and rate-control request to source ASes to mitigate link

con-gestion. Wang et al. propose the scheme based on SDN

(Software Defined Networking) [7]. Since SDN can change

network flexibly, it deals with the link congestion promptly. However, the avoidance schemes cannot work without

detect-ing attack symptom. Thus, we argue that detection schemes

are more important than avoidance schemes. As the

detec-tion scheme, Xue et al. propose LinkScope [8], which is a

net-work measurement system. In that scheme, it captures ab-normal performance degradation such as packet loss rate or

RTT (Round Trip Time) and detects the attack. LinkScope

is the first system that can conduct both end-to-end and

hop-by-hop non-cooperative measurement. By using LinkScope,

it is possible to detect target link flooding attack with high accuracy. However, LinkScope works after link congestion

occurs. This shortcoming is regarded as the same situation

of all avoidance schemes. To our knowledge, the only work

dealing with this shortcoming is the scheme proposed by

Hi-rayama et al. [9]. Thus, we pay attention to that scheme. Hirayama et al. [9] propose fast target link flooding attack

detection by analyzing "traceroute" which is used for

sur-veying network topology. That scheme focuses on the fact

that the attacker needs to send a large amount of traceroute

in order to grasp network topology around the target area before the attack starts. However, that scheme can only

de-tect a rapid increase of traceroute. In order to alleviate this

shortcoming, we propose traceroute-based target link

flood-ing attack detection scheme by analyzflood-ing hop count to the

destination.

The contribution of this paper is as follows:

(1) By computer simulation with real dataset, we dis-covered a novel feature of target link flooding attack that the

destination of attacker’s traceroute is concentrated within several hops from the target link.

(2) Our scheme is robust in terms of detecting attack

ASes

Detection Servers Detection Alert

Global Detection Server

Traceroute Log

Fig. 1 System model.

Target Area

Decoy Server Bot Target Link

Attack Flow

Fig. 2 The overview of the target link flooding attack.

symptom. That is, it can more easily capture the sophisti-cated attack which attacker’s traceroute sending rate is low.

2.

Preliminaries

2. 1 System Model

Here, we describe the system model of the conventional and proposed scheme. Fig.1 shows the system model of the

both schemes. The system consists of AS (Autonomous

Sys-tem), "Detection Server", and "Global detection server". AS

is a network managed by a single administrative domain (e.g.

Internet service provider) and consists of routers and links. Each AS collects traceroutes which pass through itself and

its log is sent to detection server. Each detection server

an-alyzes these traceroute logs. When detection servers detect

the attack, they report it to global detection server. Global

detection server informs ASes of the occurrence of the attack and instructs some countermeasure such as rerouting.

2. 2 Attacker Model

The attacker’s goal is to disconnect a specific region called

target area from other regions. Fig.2 shows the overview of

the target link flooding attack. In order to realize this at-tack, the attacker needs to prepare large amount of bots. We

assume he/she can buy them through some market such as

PPI (Pay Per Install) botnet markets [10]. By using PPI

(3)

control all bots from a remote place. Since the attacker has

no information of the network topology around the target

area, he/she needs to investigate it by using traceroute for

each bot. Traceroute’s results denote the information of path to the destination. The links, which are often appeared in

the results, are likely to the flooded link. The attacker takes

the following procedures:

(1) Selects the target area and decoy servers which are public ones located near the target area.

(2) Creates a map of network topology around target servers by having bots send traceroute.

(3) Aggregates all traceroute results and finds target links which frequently appear in the results.

(4) Selects bot-decoy pairs which can flood the target links.

(5) Commands bots to send attacking flow.

2. 3 ChangeFinder

Our proposed scheme and the conventional scheme use ChangeFinder [11]. ChangeFinder is a unifying framework

for detecting outliers and changing points from time series

data. In this research, detection server uses it and detects

points of traceroute’s increase. ChangeFinder calculates the

score of abnormality by using SDAR (Sequentially Discount-ing Auto Regressive model learnDiscount-ing) algorithm. It detects

the change when high score is observed.

3.

Conventional Scheme

Hirayama et al. propose fast target link flooding attack de-tection scheme by analyzing traceroute. That scheme focuses

on the fact that the attacker needs to send a large amount

of traceroute in order to grasp network topology around the

target area before the attack starts. This is because he/she

has no information about a location of bots and target area over the Internet. Since the number of bots controlled by

the attacker is very large, the traceroute packets observed

by detection server are increased. By using ChangeFinder

mentioned in Section 2. 3, each AS can observe the increase

of traceroute and detects the attack before link congestion occurs.

3. 1 Shortcomings of the Conventional Scheme

The detection accuracy decreases when legitimate user’s

traceroute ratio is high. This is because the conventional

scheme cannot distinguish attacker’s traceroute and legiti-mate user’s one. For example, the conventional scheme

can-not handle following situation.

3. 1. 1 Less frequently traceroute

The conventional scheme can only detect a rapid increase

of traceroute. According to [2, 12], the average lifetime of bots is about 47 days and 72% of layer-3 links measured by

traceroute are persistent. Thus, the attacker can grasp

net-work topology without sending traceroute rapidly.

3. 1. 2 In low-betweenness centrality router

The conventional scheme is difficult to detect the attack

in low betweenness centrality router. Betweenness centrality is a measure which denotes the number of times a node acts

as a bridge along the shortest path between other nodes.

Since the number of traceroute of malicious bots observed

in low-betweenness centrality router is small, capturing the

change can be difficult. In actual network, betweenness cen-trality of the routers is the power low distribution. In other

words, low-betweenness centrality router exists much more

than high-betweenness centrality router. Hence, it needs to

detect an attack in low betweenness routers.

4.

Proposed Scheme

In order to alleviate the shortcomings mentioned above,

we propose traceroute-based target link flooding attack

de-tection scheme by analyzing hop count to the destination. Since the attacker needs to find route to the decoy server

that contains the target link, we argue that the destination

of traceroute is concentrated within several hops from the

target link. Motivated by this assumption, when the

num-ber of traceroute is classified according to hop count to its destination, the number of legitimate one is distributed

uni-formly regardless of the hop counts. On the other hand,

the number of attacker’s one is concentrated on specific hop

counts. Thus, by analyzing the number of traceroutes per

hop counts, the change can be emphasized and the attack symptom might be more easily captured. In this section, we

first explain why we can know the hop count to the

destina-tion from traceroute. Then, by using computer simuladestina-tion,

we prove that attacker’s traceroutes are concentrated within

several hops from the target link. Finally, we show our algo-rithm with equations.

4. 1 Analyzing Traceroute Destination

Here, we describe how to know the hop count to the

desti-nation by analyzing traceroute. Traceroute is an ICMP

(In-ternet Control Message Protocol) packet and its Time Ex-ceeded packet is used to know the hop count. Sender can

know the route to the destination by sending packets while

changing TTL (Time To Live) value. The procedure below

is present specification of traceroute.

First, sender sends a packet to the destination with TTL = 1. Then, the first node in the middle of path sends back the

Time Exceeded packet since the TTL becomes 0. After

re-ceiving the Time Exceeded packet, sender sends a packets

with TTL = 2. This procedure is repeated until the sender

receives Echo reply from the destination. Thus, the router located between source and destination can know the hop

(4)

2 4 6 8 10 The number of hop

0.00 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40

Ratio

Fig. 3 Number of hop count vs Ratio.

Exceeded packet.

4. 2 Proof of the Assumption

We run a simple simulation in order to prove the

assump-tion that the destinaassump-tion of attacker’s traceroute is concen-trated within several hops from target link. In this

sim-ulation, we investigate the distribution of packets passed

through the target link per hop count. First, we randomly

select a node from top 5% of high-betweenness centrality

nodes. Second, we choose the node with highest between-ness centrality from neighbors of the node selected above.

The edge between these nodes is assumed to be target link

because links between high betweenness centrality nodes are

likely to be selected as the target link [2]. Then, all nodes

send packets to all other nodes by using shortest path. We select the all packets which pass through the target link and

check the hop count from the target link. The above

proce-dures are repeated 1000 times and average value is used for

the result. We use the dataset [13] and construct network

topology which has 3000 nodes for this simulation.

Fig.3 shows the result of this simulation. As shown in

Fig.3, most of packets which passed through the target link

are concentrated within three hops. This result proves that

our assumption is correct.

4. 3 Algorithm

Here, we describe the algorithm of our scheme. Our scheme

takes following procedures.

4. 3. 1 Collect and classify traceroute

As mentioned in 2. 1, detection servers monitor each AS

and collect traceroute log. Traceroutes sent by legitimate users act as a ‘noise’ from the perspective of the attack

de-tection. We suppose noise are randomly sent by legitimate

users. After collecting traceroute logs, each detection server

classifies them according to hop count. By using matrix, this

is described as

M =

⎜ ⎜ ⎜ ⎜ ⎝

m11 m12 . . . m1h

m21 m22 . . . m2h

..

. ... . .. ...

mt1 mt2 . . . mth

⎟ ⎟ ⎟ ⎟ ⎠

, (1)

wheremij,t, andhdenote the number of traceroutes whose

destination is j hops far from observing AS at time i, the latest time index, and the maximum hop count, respectively.

4. 3. 2 Detection by ChangeFinder

We adapt each column ofM to ChangeFinder and detect changing points. Here, we focus onjth column. That is, we consider m = (m1j, m2j, . . . , mij, . . . , mtj). ChangeFinder first detects outliers in m by calculating abnormality aij from each point mij. Abnormality aij is logarithmic loss

score and calculated as

aij=−logp(i−1)j(x=mij|m1j,· · ·, m(i−1)j), (2)

where p(i−1)j(x) is the conditional probability density

func-tion calculated from (m1j,· · ·, m(i−1)j). This is defined as

p(i−1)j(x) =

1

2πσexp

−(xw) 2

2σ , (3)

where σdenotes a variance of a noise term ǫin thek-order AR model andw is denoted asw=k

nαn(minǫ)−ǫ.

Then, in order to avoid the situation where single outlier causes false attack detection, we apply smoothing processing

to aij fori= [1, t]. LetT denote the number of used latest

anomaly values (i.e. (a(it+1)j,· · ·, aij)) and the smoothing

processing is calculated as

aij=

1

T

i

n=iT+1

anj. (4)

The final score is described as

S=

⎜ ⎜ ⎜ ⎜ ⎝

s11 s12 . . . s1h

s21 s22 . . . s2h

..

. ... . .. ...

st1 st2 . . . sth

⎟ ⎟ ⎟ ⎟ ⎠

, (5)

wheresijis calculated as

sij=−logp(i−1)j(x=aij|a1j,· · ·, a(i−1)j). (6)

Finally, let dth be the predefined threshold value. For

i = [2, t], detection servers judge the change as an attack if the conditionsijs(i−1)j> dthholds.

4. 3. 3 After Detection

As mentioned in 2. 1, we use global detection server. When a detection server raises an alert, that is reported to the

global detection server. After attack symptom detection,

global detection server instructs ASes to take some

counter-measure such as rerouting (e.g.CoDef [6]).

5.

Evaluation

We evaluate our scheme by computer simulation. To show

(5)

Table 1 Simulation Parameters

Parameter Value

Number of ASes 1,000

Number of bots 2,000

Number of decoy servers 2,000

Process time for a traceroute 13ms/hop

Number of times the attacker sends traceroute

3

Interval of sending traceroute 5 - 1000(ms)

Model of legitimate user’s generating traceroute packets

Poisson distribution withλ

Values ofλ 10, 100, 1,000, 10,000

Curve) of ROC (Receiver Operating Characteristic) curve. The ROC curve is a graph which plots TP (True Positive)

against FP (False Positive) at various threshold settings. In

this evaluation, TP and FP denote the ratio that attack is

accurately detected as attack and non-attack is inaccurately

detected as attack, respectively. AUC is the area under plot-ted ROC curve, and thus it indicates an accuracy of the

classification algorithm. If an algorithm perfectly classifies

attacks and non-attacks, the AUC indicates 1.0. On the

con-trary, if an algorithm randomly classifies a given data, the

AUC indicates 0.5.

5. 1 Simulation Setup

5. 1. 1 Performance Metrics

We evaluate the detection accuracy from three perspectives

in order to compare the stability of the proposed scheme with

the conventional scheme. First, we evaluate the number of noise versus the number of ASes which achieve high AUC in

order to confirm whether the proposed scheme has a

resis-tance to noise. Second, we evaluate the AUC while

chang-ing the sendchang-ing interval of attacker’s traceroutes. Finally, we

evaluate the AUC versus BC (Betweenness Centrality). This is because the conventional scheme cannot handle those

situ-ations as mentioned in 3. 1. We can indicate the effectiveness

of our scheme if it is able to deal with those situation.

5. 1. 2 Simulation Environment

We construct network topology using Caida AS Relation-ships Dataset [13]. Table 1 shows simulation parameters.

We assume that each AS has only one router to simplify

simulations. In accordance with [2], the number of bots and

decoy servers is set to twice as many as the number of ASes.

The behavior of bots and legitimate users is as follows: A bot sends traceroutes to all decoy servers three times at any given

point in time. On the other hand, a legitimate user sends

traceroute to a randomly chosen destination. The number

of the traceroutes per an AS follows the Poisson distribution

10 100 1000 10000

λ

0 100 200 300 400 500 600 700

Number of ASes (AUC > 0.9) ProposedConventional

Fig. 4 Number of ASes vs noiseλ.

withλ.

5. 2 Simulation Methodology

In order to find the abnormal point, ChangeFinder needs

to learn the normal state. Thus, we generate two time series

data as follows:

Training data:

A time series data which includes only the number of tracer-oute packets sent by legitimate users.

Test data:

A time series data which includes the number of traceroute

packets sent by bots and legitimate users.

At first, each detection server loads training data. After the training phase, each detection server judges a given test time

series data with thresholddth by using test data. Each

de-tection server tries each thresholddth= (0.0,0.1,· · ·,20.0).

Then, each detection server calculates AUC for eachdth. 5. 3 Simulation Results

5. 3. 1 Detection Accuracy versus Noise

Fig.4 shows the number of ASes that achieve AUC>0.9 versus noise. As shown in Fig.4, the number of ASes that

have high AUC in the conventional scheme decreases as the noise increases. This is because it becomes harder to

dis-tinguish between attacker’s traceroutes and noise due to the

increase of the noise. Especially, the conventional scheme

cannot detect the attack whenλis larger than 1000. On the contrary, the proposed scheme can detect the attack even if noise increases. This is because the proposed scheme can

grasp the phenomenon that the number of traceroute at a

specific hop count significantly increases due to the attacker’s

traceroute.

5. 3. 2 Detection Accuracy versus Sending Interval

Fig.5 shows AUC versus traceroute sending interval. As can be seen from Fig.5, AUC of the conventional scheme

de-creases as the sending interval inde-creases. This is because the

number of attacker’s traceroute observed in a short time is

reduced. Thus, the attacker’s traceroute is mixed with

legit-imate user’s traceroute and it is difficult to detect a change point. The AUC is below 0.5 at 1000ms and it becomes

(6)

5 200 400 600 800 1000 sending_interval[ms]

0.0 0.2 0.4 0.6 0.8 1.0

AUC

Proposed Conventional

Fig. 5 AUC vs sending interval.

0.0 0.1 0.2 0.3 0.4 0.5

betweenness centrality 0.0

0.2 0.4 0.6 0.8 1.0

AU

C

(a) AUC vs BC of the Conventional Scheme.

0.0 0.1 0.2 0.3 0.4 0.5

betweenness centrality 0.0

0.2 0.4 0.6 0.8 1.0

AU

C

(b) AUC vs BC of the Proposed Scheme.

Fig. 6 AUC vs Betweenness Centrality.

scheme keeps higher AUC than the conventional scheme in

all cases.

5. 3. 3 Detection Accuracy versus BC

Fig.6 shows AUC vs BC of the conventional and proposed

scheme. Error bars show the standard deviation. As can

be seen in Fig.6(a), AUC of the conventional scheme

be-comes low as the betweenness centrality decreases. This is because the traceroute sent from attacker is likely to be

routed through the ASes that have high betweenness

cen-trality. Since the conventional scheme is fragile to noise, it

cannot detect the attack in low betweenness centrality ASes.

On the contrary, as can be seen in Fig.6(b), the proposed scheme can detect the attack even in low betweenness

cen-trality ASes.

6.

Conclusion

In this paper, we have proposed traceroute based tar-get link flooding attack detection scheme by analyzing hop

count to the destination. We focus on the fact that normal

traceroute packets are distributed uniformly while attacker’s

ones are concentrated. By analyzing traceroute’s hop counts

to the destination, it becomes easier to capture the attack symptom. We show the effectiveness of our scheme by

com-puter simulations. Our scheme can detect the attack when

noise and traceroute sending rate increase. Moreover, our

scheme can detect the attack in low betweenness ASes.

7.

ACKNOWLEDGMENT

This work is partly supported by the Grant in Aid for

Scientific Research (No.17K06440) from Japan Society for

Promotion of Science (JSPS).

References

[1] A. Studer and A. Perrig, “The Coremelt Attack,” Computer Security ESORICS 2009, vol.5789, pp.37–52, Aug. 2009. [2] M.S. Kang, S.B. Lee, and V.D. Gligor, “The crossfire

at-tack,” Proc. IEEE Symp. on Security and Privacy, pp.127– 141, May 2013.

[3] H. Beitollahi and G. Deconinck, “Analyzing well-known countermeasures against distributed denial of service at-tacks,” Computer Communications, vol.35, pp.1312–1332, 2012.

[4] S.T. Zargar, J. Joshi, and D. Tipper, “A survey of defense mechanisms against distributed denial of service (DDoS) flooding attacks,” IEEE Communications Surveys & Tuto-rials, vol.15, pp.2046–2069, 2013.

[5] T. Peng, C. Leckie, and K. Ramamohanarao, “Survey of network-based defense mechanisms countering the DoS and DDoS problems,” ACM Computing Surveys, vol.39, no.1, pp.1–35, 2007.

[6] S.B. Lee, M.S. Kang, and V.D. Gligor, “CoDef: collabora-tive defense against large-scale link-flooding attacks,” Proc. ACM CoNEXT, pp.417–428, 2013.

[7] L. Wang, Q. Li, Y. Jiang, and J. Wu, “Towards mitigating Link Flooding Attack via incremental SDN deployment,” Proceedings - IEEE Symposium on Computers and Com-munications, vol.2016-Augus, pp.397–402, 2016.

[8] L. Xue, X. Luo, E.W.W. Chan, and X. Zhan, “Towards de-tecting target link flooding attack,” in Proc. USENIX LISA, pp.81–96, 2014.

[9] T. Hirayama, K. Toyoda, and I. Sasase, “Fast target link flooding attack detection scheme by analyzing traceroute packets flow,” 2015 IEEE International Workshop on Infor-mation Forensics and Security, WIFS 2015 - Proceedings, pp.1–6, 2015.

[10] J. Caballero, C. Grier, C. Kreibich, V. Paxson, and U.C. Berkeley, “Measuring Pay-per-Install : The Commoditiza-tion of Malware DistribuCommoditiza-tion,” USENIX Security Sympo-sium, pp.13–13, 2011.

[11] J. Takeuchi and K. Yamanishi, “A unifying framework for detecting outliers and change points from time series,” IEEE Trans. Knowledge and Data Eng., vol.18, no.4, pp.482–492, 2006.

[12] M. Abu Rajab, J. Zarfoss, F. Monrose, and A. Terzis, “A multifaceted approach to understanding the botnet phe-nomenon,” Proceedings of the 6th ACM SIGCOMM on In-ternet measurement - IMC ’06, pp.41–52, 2006.

Updating...

参照

Updating...

関連した話題 :