Target Link Flooding Attack
あらまし 近年，新種のDDoS攻撃であるTarget Link Flooding Attackの検知が急務である．この攻撃は，特定の
Traceroute based Target Link Flooding Attack Detection Scheme by
Analyzing Hop Count to the Destination
, 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
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 ﬁnding 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
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 ﬂooding attack which is
a new type of DDoS attack has been proposed [1, 2]. This attack cuts oﬀ speciﬁc links over the Internet and
discon-nects a speciﬁc region from other regions. More speciﬁcally,
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 diﬀerent destinations through the links. As a result, the corresponding links are
ﬂooded and the area is isolated. Target link ﬂooding 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
eﬀectively against the target link ﬂooding attack.
In order to deal with target link ﬂooding attack,
sev-eral schemes have been proposed [6–9]. Those schemes are
roughly classiﬁed 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 . That scheme is an AS (Autonomous System)
level target link ﬂooding 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 Deﬁned Networking) . Since SDN can change
network ﬂexibly, 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 , 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 ﬁrst 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 ﬂooding 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. . Thus, we pay attention to that scheme. Hirayama et al.  propose fast target link ﬂooding 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
ﬂood-ing attack detection scheme by analyzﬂood-ing hop count to the
The contribution of this paper is as follows:
（1） By computer simulation with real dataset, we dis-covered a novel feature of target link ﬂooding 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
Detection Servers Detection Alert
Global Detection Server
Fig. 1 System model.
Decoy Server Bot Target Link
Fig. 2 The overview of the target link ﬂooding attack.
symptom. That is, it can more easily capture the sophisti-cated attack which attacker’s traceroute sending rate is low.
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 speciﬁc region called
target area from other regions. Fig.2 shows the overview of
the target link ﬂooding 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 . By using PPI
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 ﬂooded 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 ﬁnds target links which frequently appear in the results.
（4） Selects bot-decoy pairs which can ﬂood the target links.
（5） Commands bots to send attacking ﬂow.
2. 3 ChangeFinder
Our proposed scheme and the conventional scheme use ChangeFinder . 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.
Hirayama et al. propose fast target link ﬂooding 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.
In order to alleviate the shortcomings mentioned above,
we propose traceroute-based target link ﬂooding attack
de-tection scheme by analyzing hop count to the destination. Since the attacker needs to ﬁnd 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 classiﬁed 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 speciﬁc 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
ﬁrst 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 speciﬁcation of traceroute.
First, sender sends a packet to the destination with TTL = 1. Then, the ﬁrst 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
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
Fig. 3 Number of hop count vs Ratio.
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 . 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  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
classiﬁes them according to hop count. By using matrix, this
is described as
⎜ ⎜ ⎜ ⎜ ⎝
m11 m12 . . . m1h
m21 m22 . . . m2h
. ... . .. ...
mt1 mt2 . . . mth
⎟ ⎟ ⎟ ⎟ ⎠
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 ﬁrst 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 deﬁned as
2σ , (3)
where σdenotes a variance of a noise term ǫin thek-order AR model andw is denoted asw=k
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(i−t+1)j,· · ·, aij)) and the smoothing
processing is calculated as
The ﬁnal score is described as
⎜ ⎜ ⎜ ⎜ ⎝
s11 s12 . . . s1h
s21 s22 . . . s2h
. ... . .. ...
st1 st2 . . . sth
⎟ ⎟ ⎟ ⎟ ⎠
wheresijis calculated as
sij=−logp(i−1)j(x=aij|a1j,· · ·, a(i−1)j). (6)
Finally, let dth be the predeﬁned threshold value. For
i = [2, t], detection servers judge the change as an attack if the conditionsij−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 ).
We evaluate our scheme by computer simulation. To show
Table 1 Simulation Parameters
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
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
classiﬁcation algorithm. If an algorithm perfectly classiﬁes
attacks and non-attacks, the AUC indicates 1.0. On the
con-trary, if an algorithm randomly classiﬁes 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 conﬁrm 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 eﬀectiveness
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 . Table 1 shows simulation parameters.
We assume that each AS has only one router to simplify
simulations. In accordance with , 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λ.
5. 2 Simulation Methodology
In order to ﬁnd the abnormal point, ChangeFinder needs
to learn the normal state. Thus, we generate two time series
data as follows:
A time series data which includes only the number of tracer-oute packets sent by legitimate users.
A time series data which includes the number of traceroute
packets sent by bots and legitimate users.
At ﬁrst, 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
speciﬁc hop count signiﬁcantly increases due to the attacker’s
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
5 200 400 600 800 1000 sending_interval[ms]
0.0 0.2 0.4 0.6 0.8 1.0
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
(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
(b) AUC vs BC of the Proposed Scheme.
Fig. 6 AUC vs Betweenness Centrality.
scheme keeps higher AUC than the conventional scheme in
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
In this paper, we have proposed traceroute based tar-get link ﬂooding 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 eﬀectiveness 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.
This work is partly supported by the Grant in Aid for
Scientiﬁc Research (No.17K06440) from Japan Society for
Promotion of Science (JSPS).
 A. Studer and A. Perrig, “The Coremelt Attack,” Computer Security ESORICS 2009, vol.5789, pp.37–52, Aug. 2009.  M.S. Kang, S.B. Lee, and V.D. Gligor, “The crossﬁre
at-tack,” Proc. IEEE Symp. on Security and Privacy, pp.127– 141, May 2013.
 H. Beitollahi and G. Deconinck, “Analyzing well-known countermeasures against distributed denial of service at-tacks,” Computer Communications, vol.35, pp.1312–1332, 2012.
 S.T. Zargar, J. Joshi, and D. Tipper, “A survey of defense mechanisms against distributed denial of service (DDoS) ﬂooding attacks,” IEEE Communications Surveys & Tuto-rials, vol.15, pp.2046–2069, 2013.
 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.
 S.B. Lee, M.S. Kang, and V.D. Gligor, “CoDef: collabora-tive defense against large-scale link-ﬂooding attacks,” Proc. ACM CoNEXT, pp.417–428, 2013.
 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.
 L. Xue, X. Luo, E.W.W. Chan, and X. Zhan, “Towards de-tecting target link ﬂooding attack,” in Proc. USENIX LISA, pp.81–96, 2014.
 T. Hirayama, K. Toyoda, and I. Sasase, “Fast target link ﬂooding attack detection scheme by analyzing traceroute packets ﬂow,” 2015 IEEE International Workshop on Infor-mation Forensics and Security, WIFS 2015 - Proceedings, pp.1–6, 2015.
 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.
 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.
 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.