宛先までのホップ数解析による 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)
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 analyzing 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 services, the attacker has ability to run any program and
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 learning) 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 simulation, 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 count to the destination by analyzing TTL and ICMP Time
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 destination 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)
where mij, t, and h denote 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 of M to ChangeFinder and detect changing points. Here, we focus on j th 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= − log p(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
−(x − w)
2
2σ
, (3)
where σ denotes a variance of a noise term ǫ in the k-order AR model and w is denoted as w = knαn(mi−n− ǫ) − ǫ. Then, in order to avoid the situation where single outlier causes false attack detection, we apply smoothing processing to aij for i = [1, t]. Let T denote the number of used latest anomaly values (i.e. (a(i−t+1)j,· · · , aij)) and the smoothing processing is calculated as
aij= 1 T
i
n=i−T +1
anj. (4)
The final score is described as
S=
⎛
⎜
⎜
⎜
⎜
⎝
s11 s12 . . . s1h
s21 s22 . . . s2h
... ... . .. ... st1 st2 . . . sth
⎞
⎟
⎟
⎟
⎟
⎠
, (5)
where sijis calculated as
sij= − log p(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 condition sij− s(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 effectiveness of our scheme, we introduce AUC (Area Under
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 sending 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 threshold dth by using test data. Each de- tection server tries each threshold dth= (0.0, 0.1, · · · , 20.0). Then, each detection server calculates AUC for each dth.
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 increases. 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 un- able to detect the attack. On the contrary, the proposed
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
AUC
(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
AUC
(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 Distribution,” 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.
[13] “AS Relationships”. http://www.caida.org/data/as-relationships
