Paper 04
Paper 04
Paper 04
Michael Singhof
Heinrich-Heine-Universität
Institut für Informatik
Universitätsstraße 1
40225 Düsseldorf, Deutschland
[email protected]
1. INTRODUCTION
2. INTRODUCTION TO DDOS ATTACKS
Denial of service (DoS) attacks are attacks that have the
goal of making a network service unusable for its legitimate Denial of service and distributed denial of service attacks
users. This can be achieved in different ways, either by are not a new threat in the internet. In [15] the first notable
denial of service attack is dated to 1996 when the internet
provider Panix was taken down for a week by a TCP SYN
flood attack. The same article dates the first noteworthy
distributed denial of service attack to the year 1997 when
internet service providers in several countries as well as an
IRC network were attacked by a teenager. Since then, many
of the more elaborate attacks that worked well in the past,
have been successfully defused.
25th GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 28.05.2013 - 31.05.2013, Ilmenau, Germany. Let us, as an example, examine the TCP SYN flood at-
Copyright is held by the author/owner(s). tack. A TCP connection is established by a three way hand-
shake. On getting a SYN request packet, in order to open a
TCP connection, the addressed computer has to store some
information on the incoming packet and then answers with
a SYN ACK packet which is, on regularly opening a TCP
connection, again replied by an ACK packet.
The idea of the SYN flood attack is to cause a memory
overrun on the victim by sending many TCP SYN packets.
As for every such packet the victim has to store information
while the attacker just generates new packets and ignores the
victim’s answers. By this the whole available memory of the
victim can be used up, thus disabling the victim to open le-
gitimate connection to regular clients. As a countermeasure, Figure 1: Detection locations for DDoS attacks.
in [7] SYN cookies were introduced. Here, instead of storing
the information associated with the only half opened TCP
connection in the local memory, that information is coded
testing that allows users, among other functions, to volun-
into the TCP sequence number. Since that number is re-
tary join a botnet in order to carry out an attack. Since
turned by regular clients on sending the last packet of the
the tool is mainly for testing purposes, the queries are not
already described three way handshake and initial sequence
masqueraded so that it is easy to identify the participat-
numbers can be arbitrarily chosen by each connection part-
ing persons. Again, however, the initiator of the attack does
ner, no changes on the TCP implementation of the client
not necessarily have to have direct contact to the victim and
side have to be made. Essentially, this reduces the SYN
thus remains unknown.
cookie attack to a mere bandwidth based attack.
A great diversity of approaches to solve the problem of
The same applies to many other attack methods that have
detecting DDoS attacks exists. Note again, that this work
been successfully used in the past, such as the smurf attack
focuses on anomaly detection methods only. This describes
[1] or the fraggle attack. Both of these attacks are so called
methods, that essentially make use of outlier detection meth-
reflector attacks that consist of sending an echo packet –
ods to distinguish normal traffic and attack traffic. In a field
ICMP echo in case of the smurf attack and UDP echo in
with as many publications as intrusion detection and even,
case of the fraggle attack – to a network’s broadcast address.
more specialised, DDoS detection, it is not surprising, that
The sender’s address in this packet has to be forged so that
many different approaches are used, most of which are com-
the packet occurs to be sent by the victim of the attack, so
mon in other knowledge discovery research fields as well.
that all replies caused by the echo packet are routed to the
As can be seen in Figure 1 this research part, again, can
victim.
be divided in three major categories, namely distributed de-
Thus, it seems like nowadays most denial of service attacks
tection or in network detection, source end detection and
are distributed denial of service attack trying to exhaust the
end point or victim end detection.
victims bandwidth. Examples for this are the attacks on
By distributed detection approaches we denote all ap-
Estonian government and business computers in 2007 [12].
proaches that use more than one node in order to monitor
As already mentioned, distributed denial of service attacks
the network traffic. This kind of solution is mostly aimed
are denial of service attacks with several participating at-
to be used by internet providers and sometimes cooperation
tackers. The number of participating computers can differ
between more than one or even all ISPs is expected. The
largely, ranging from just a few machines to several thou-
main idea of almost all of these systems is to monitor the
sands. Also, in most cases, the owners of these computers
network traffic inside the backbone network. Monitors are
are not aware that they are part of an attack. This lies in the
mostly expected to be backbone routers, that communicate
nature of most DDoS attacks which consist of three steps:
the results of their monitoring either to a central instance or
1. Building or reusing a malware that is able to receive among each other. These systems allow an early detection of
commands from the main attacker (“master”) and to suspicious network traffic so that an attack can be detected
carry out the attack. A popular DDoS framework is and disabled – by dropping the suspicious network packets
Stacheldraht [9]. – before it reaches the server the attack is aimed at. How-
ever, despite these methods being very mighty in theory,
2. Distribute the software created in step one to create they suffer the main disadvantage of not being able to be
a botnet. This step can essentially be carried out in employed without the help of one or more ISPs. Currently,
every known method of distributing malware, for ex- this makes these approaches impractical for end users since,
ample by forged mail attachments or by adding it to to the knowledge of the author, at this moment no ISP uses
software like pirate copies. such an approach.
Source end detection describes approaches that monitor
3. Launch the attack by giving the infected computers outgoing attack streams. Of course, such methods can only
the command. be successful if the owner of an attacking computer is not
aware of his computer participating in that attack. A widely
This procedure – from the point of view of the main at- used deployment of such solutions is necessary for them to
tacker – has the advantage of not having to maintain a direct have an effect. If this happens, however, these methods have
connection to the victim. This makes it very hard to track the chance to not only detect distributed denial of service
that person. It is notable though, that during attacks origi- attacks but also to prevent them by stopping the attacking
nating to Anonymous in the years 2010 and 2012 Low Orbit traffic flows. However, in our opinion, the necessity of wide
Ion Cannon [6] was used. This is originally a tool for stress deployment makes a successful usage of this methods – at
Packet type No of packets Percentage 1e+08
Number of packets over arrival times
IP 65612516 100
1e+07
TCP 65295894 99.5174
UDP 77 0.0001 1e+06
ICMP 316545 0.4824
100000
Number of packets
Protocol Incoming Traffic Outgoing Traffic
10000
IP 24363685 41248831
TCP 24204679 41091215 1000
UDP 77 0
ICMP 158929 157616 100
10
Table 1: Distribution of web traffic on protocol types
and incoming and outgoing traffic at the university’s 1
web server. 0 0.2 0.4 0.6 0.8 1
Arrival time [seconds]
least in the near future – difficult. Figure 2: Arrival times for the university’s web-
In contrast to the approaches described above, end point server trace.
detection describes those methods that rely on one host only.
In general, this host can be either the same server other ap-
UDP packets seem to be unwanted packets as none of these
plications are running on or a dedicated firewall in the case
packets is replied. The low overall number of these packets is
of small networks. Clearly, these approaches suffer one dis-
an indicator for this fact, too. With ICMP traffic, incoming
advantage: Attacks cannot be detected before the attack
and outgoing packet numbers are nearly the same which lies
packets arrive at their destination, as only those packets
in the nature of this message protocol.
can be inspected. On the other hand end point based meth-
In order to overcome the problems with old traces, based
ods allow individual deployment and can therefore be used
on the characteristics of the web trace, as a next step we
nowadays. Due to this fact, our work focuses on end point
implement a simulator for distributed denial of service at-
approaches.
tacks. As the results in [20] show, the network simulators
OMNeT++ [19], ns-3 [10] and JiST [5] are, in terms of speed
3. TEST TRACES OF DISTRIBUTED DE- and memory usage, more or less equal. To not let the simula-
tion become either too slow or too inaccurate, it is intended
NIAL OF SERVICE ATTACKS to simulate a nearer neighbourhood of the victim server very
Today, the testing of DDoS detection methods unfortu- accurately. With greater distance to the victim, it is planned
nately is not easy, as not many recordings of real or simu- to simulate in less detail. In this context, the distance be-
lated DDoS attacks exist or, at least, are not publicly avail- tween two network nodes is given by the number of hops
able. The best known test trace is the KDD Cup 99 data between the nodes.
set [3]. A detailed description of this data set is given in Simulation results then will be compared with the afore-
[18]. Other known datasets are the 1998 DARPA intrusion mentioned network trace to ensure its realistic behaviour.
detection evaluation data set that has been described in [14] After the simulation of normal network traffic resembles the
as well as the 1999 DARPA intrusion detection evaluation real traffic at the victim server close enough, we will proceed
data set examined in [13]. by implementing distributed denial of service attacks in the
In terms of the internet, with an age of 14 to 15 years, simulator environment. With this simulator it will then,
these data sets are rather old and therefore cannot reflect hopefully, be possible to test existing and new distributed
today’s traffic volume and behaviour in a realistic fashion. denial of service detection approaches in greater detail as
Since testing with real distributed denial of service attacks has been possible in the past.
is rather difficult both on technical as well as legal level, we
suggest the usage of a DDoS simulator. In order to get a feel-
ing for today’s web traffic, we recorded a trace at the main 4. EXISTING APPROACHES
web server of Heinrich-Heine-Universität. Tracing started on Many approaches to the detection of distributed denial of
17th September 2012 at eight o’clock local time and lasted service attacks already exist. As has been previously pointed
until eight o’clock the next day. out in section 1, in contrast to many other outlier and nov-
This trace consists of 65612516 packets of IP traffic with elty detection applications in the KDD field, the detection
31841 unique communication partners contacting the web of DDoS attacks is extremely time critical, hence near real
server. As can be seen in Table 1 almost all of these packets time detection is necessary.
are TCP traffic. This is not surprising as the HTTP protocol Intuitively, the less parameters are observed by an ap-
uses the TCP protocol and web page requests are HTTP proach, the faster it should work. Therefore, first, we take a
messages. look at a recently issued method that relies on one parameter
About one third of the TCP traffic is incoming traffic. only.
This, too, is no surprise as most clients send small request
messages and, in return, get web pages that often include 4.1 Arrival Time Based DDoS Detection
images or other larger data and thus consist of more than In [17] the authors propose an approach that bases on ir-
one package. It can also be seen, clearly, that all of the regularities in the inter packet arrival times. By this term
1
Now, since we are solely interested in the estimation of x̄,
0.9 only 1 M is needed, which is computed to be [x̄, x̄] since
0.8 1 β β 1 1
g(1) = − 1 + = (1 − β + β) =
0.7
2 2 2 2 2
0.6 and
1
0.5
zg(1) = Φ−1 (1 − g(1)) = Φ−1 ( ) = 0.
α
2
0.4
During traffic monitoring, for a given time interval, the
0.3
current traffic arrival times tc are computed by estimating
0.2
1 1 1 1
[tc ]α = ln , ln
0.1 1 − p rα 1 − p lα
0
0.00122 0.00124 0.00126 0.00128 0.0013 0.00132 0.00134 0.00136 0.00138 0.0014 0.00142 where p is some given but again not specified probability and
Arrival times [s] [lα , rα ] are the α-cuts for E(T ) = t̄. As described above, the
only value that is of further use is tc , the only value in the
Figure 3: The fuzzy mean estimator constructed ac- interval of [tc ]1 . Since [E(T )]1 = [t̄]1 = [t̄, t̄] it follows that
cording to [17].
1 1 1 1
[tc ]1 = ln , ln
1 − p t̄ 1 − p t̄
the authors describe the time that elapses between two sub- and thus
sequent packets.
The main idea of this work is based on [8] where non- 1 1 1
tc = ln = (ln(1) − ln(1 − p)) .
asymptotic fuzzy estimators are used to estimate variable 1−p t̄ t̄
costs. Here, this idea is used to estimate the mean arrival As ln(1) = 0 this can be further simplified to
time x̄ of normal traffic packets. Then, the mean arrival
time of the current traffic – denoted by tc – is estimated, ln(1 − p)
tc = − ∈ [0, ∞)
too, and compared to the overall value. If tc > x̄, the traffic t̄
is considered as normal traffic and if tc < x̄ a DDoS attack with p ∈ [0, 1).
is assumed to be happening. We suppose here, that for a By this we are able to determine a value for p by choosing
value of tc = x̄ no attack is happening, although this case is the smallest p where tc ≥ x̄ for all intervals in our trace. An
not considered in the original paper. interval length of four seconds was chosen to ensure compa-
To get a general feeling for the arrival times, we computed rability with the results presented in [17].
them for our trace. The result is shown in Figure 2. Note, During the interval with the highest traffic volume 53568
that the y-axis is scaled logarithmic as values for arrival packets arrived resulting in an average arrival time of t̄ ≈
times larger than 0.1 seconds could not been distinguished 7.4671 · 10−5 seconds. Note here, that we did not maximise
from zero on a linear y-axis. It can be seen here, that most the number of packets for the interval but instead let the first
arrival times are very close to zero. It is also noteworthy interval begin at the first timestamp in our trace rounded
that, due to the limited precision of libpcap [2], the most down to full seconds and split the trace sequentially from
common arrival interval is zero. there on.
Computing the fuzzy mean estimator for packet arrival Now, in order to compute p one has to set
times yields the graph presented in Figure 3 and x̄ ≈ 0.00132.
Note, that since the choice of parameter β ∈ [0, 1) is not p = 1 − e−x̄t̄
specified in [17], we here chose β = 12 . We will see, however,
leading to p ≈ 9.8359 · 10−8 . As soon as this value of p is
that, as far as our understanding of the proposed method
learned, the approach is essentially a static comparison.
goes, this parameter has no further influence.
There are, however, other weaknesses to this approach
To compute the α-cuts of a fuzzy number, one has to
as well: Since the only monitored value is the arrival time,
compute
a statement on values such as bandwidth usage cannot be
α σ σ made. Consider an attack where multiple corrupted com-
M = x̄ − zg(α) √ , x̄ + zg(α) √ puters try to download a large file from a server via a TCP
n n
connection. This behaviour will result in relatively large
where x̄ is the mean value – i.e. exactly the value that is packets being sent from the server to the clients, resulting
going to be estimated – and σ is presumably the arrival in larger arrival times as well. Still, the server’s connec-
times’ deviation. Also tion can be jammed by this traffic thus causing a denial of
service.
1 β β
g(α) = − α+ By this, we draw the conclusion that a method relying on
2 2 2
only one parameter – in this example arrival times – can-
and not detect all kinds of DDoS attacks. Thus, despite its low
zg(α) = Φ−1 (1 − g(α)). processing requirements, such an approach in our opinion is
not suited for general DDoS detection even if it seems that
Note, that α M is the (1 − α)(1 − β) confidence interval it can detect packet flooding attacks with high precision as
for µ, the real mean value of packet arrival times. stated in the paper.
Algorithm 1 LCFS algorithm based on [11].
Require: the initial set of all features I,
the class-outputs y,
the desired number of features n
Ensure: the dimension reduced subset F ⊂ I
1: for all fi ∈ I do
2: compute corr(fi , y)
3: end for
4: f := max{correlation(fi , y)|fi ∈ I}
5: F := {f }
6: I := I \ {f }
7: while |F | <(n do )
1
P
8: f := max corr(fi , y) − |F | corr(fi , fj ) fi ∈ I
Figure 4: Protocol specific DDoS detection architec- fj ∈F
ture as proposed in [11]. 9: F := F ∪ {f }
10: I := I \ {f }
11: end while
4.2 Protocol Type Specific DDoS Detection 12: return F
In [11] another approach is presented: Instead of using the
same methods on all types of packets, different procedures
are used for different protocol types. This is due to the fact, the university’s campus. The presented results show that
that different protocols show different behaviour. Especially on all data sets the DDoS detection accuracy varies in the
TCP traffic behaviour differs from UDP and ICMP traffic range of 99.683% to 99,986% if all of the traffic’s attributes
because of its flow control features. By this the authors try are used. When reduced to three or five attributes, accuracy
to minimise the feature set characterising distributed denial stays high with DDoS detection of 99.481% to 99.972%. At
of service attacks for every protocol type, separately, such the same time, the computation time shrinks by a factor of
that computation time is minimised, too. two leading to a per instance computation time of 0.0116ms
The proposed detection scheme is described as a four step (three attributes) on the KDD Cup data set and 0.0108ms
approach, as shown in Figure 4. Here, the first step is the (three attributes) and 0.0163ms (five attributes) on the self-
preprocessing where all features of the raw network traffic recorded data sets of the authors.
are extracted. Then packets are forwarded to the correspon- Taking into account the 53568 packets in a four second
dent modules based on the packet’s protocol type. interval we recorded, the computation time during this in-
The next step is the protocol specific feature selection. terval would be about (53568 · 0.0163ms ≈) 0.87 seconds.
Here, per protocol type, the most significant features are However, there is no information about the machine that
selected. This is done by using the linear correlation based carried out the computations given in the paper such that
feature selection (LCFS) algorithm that has been introduced this number appears to be rather meaningless. If we suppose
in [4], which essentially ranks the given features by their a fast machine with no additional tasks, this computation
correlation coefficients given by time would be relatively high.
Pn
(xi − x̄)(yi − x̄) Nevertheless, the results presented in the paper at hand
corr(X, Y ) := pPn i=1 Pn are promising enough to consider a future re-evaluation on a
i=1 (xi − x̄)
2
i=1 (yi − ȳ)
2
known machine with our recorded trace and simulated DDoS
for two random variables X, Y with values xi , yi , 1 ≤ i ≤ n, attacks.
respectively. A pseudo code version of LCFS is given in
Algorithm 1. As can be seen there, the number of features
in the reduced set must be given by the user. This number 5. CONCLUSION
characterises the trade-off between precision of the detection We have seen that distributed denial of service attacks are,
and detection speed. in comparison to the age of the internet itself, a relatively
The third step is the classification of the instances in ei- old threat. Against many of the more sophisticated attacks
ther normal traffic or DDoS traffic. The classification is specialised counter measures exist, such as TCP SYN cook-
trained on the reduced feature set generated in the previous ies in order to prevent the dangers of SYN flooding. Thus,
step. The authors tested different well known classification most DDoS attacks nowadays are pure bandwidth or brute
techniques and established C4.5 [16] as the method working force attacks and attack detection should focus on this types
best in this case. of attacks, making outlier detection techniques the method
Finally, the outputs of the classifiers are given to the of choice. Still, since many DDoS toolkits such as Stachel-
merger to be able to report warnings over one alarm gen- draht allow for attacks like SYN flooding properties of this
eration interface instead of three. The authors mention that attacks can still indicate an ongoing attack.
there is a check for false positives in the merger, too. How- Also, albeit much research on the field of DDoS detection
ever, there is no further information given on how this check has been done during the last two decades that lead to a
works apart from the fact that it is relatively slow. nearly equally large number of possible solutions, in section
The presented experiments have been carried out on the 3 we have seen that one of the biggest problems is the un-
aforementioned KDD Cup data set as well as on two self- availability of recent test traces or a simulator being able
made data sets for which the authors attacked a server within to produce such traces. With the best known test series
having an age of fourteen years, today, the results presented Off-line Intrusion Detection Evaluation. In DARPA
in many of the research papers on this topic are difficult to Information Survivability Conference and Exposition,
compare and confirm. 2000. DISCEX’00. Proceedings, volume 2, pages
Even if one can rate the suitability of certain approaches in 12–26. IEEE, 2000.
respect to detect certain approaches, such as seen in section [15] G. Loukas and G. Öke. Protection Against Denial of
4, a definite judgement of given methods is not easy. We Service Attacks: A Survey. The Computer Journal,
therefore, before starting to implement an own approach to 53(7):1020–1037, 2010.
distributed denial of service detection, want to overcome this [16] J. R. Quinlan. C4.5: Programs for Machine Learning,
problem by implementing a DDoS simulator. volume 1. Morgan Kaufmann, 1993.
With the help of this tool, we will be subsequently able to [17] S. N. Shiaeles, V. Katos, A. S. Karakos, and B. K.
compare existing approaches among each other and to our Papadopoulos. Real Time DDoS Detection Using
ideas in a fashion reproducible for others. Fuzzy Estimators. Computers & Security,
31(6):782–790, 2012.
6. REFERENCES [18] M. Tavallaee, E. Bagheri, W. Lu, and A.-A. Ghorbani.
[1] CERT CC. Smurf Attack. A Detailed Analysis of the KDD CUP 99 Data Set. In
http://www.cert.org/advisories/CA-1998-01.html. Proceedings of the Second IEEE Symposium on
[2] The Homepage of Tcpdump and Libpcap. Computational Intelligence for Security and Defence
http://www.tcpdump.org/. Applications 2009, 2009.
[3] KDD Cup Dataset. [19] A. Varga and R. Hornig. An Overview of the
http://kdd.ics.uci.edu/databases/kddcup99/ OMNeT++ Simulation Environment. In Proceedings
kddcup99.html, 1999. of the 1st International Conference on Simulation
[4] F. Amiri, M. Rezaei Yousefi, C. Lucas, A. Shakery, Tools and Techniques for Communications, Networks
and N. Yazdani. Mutual Information-based Feature and Systems & Workshops, Simutools ’08, pages
Selection for Intrusion Detection Systems. Journal of 60:1–60:10, ICST, Brussels, Belgium, Belgium, 2008.
Network and Computer Applications, 34(4):1184–1199, ICST (Institute for Computer Sciences,
2011. Social-Informatics and Telecommunications
[5] R. Barr, Z. J. Haas, and R. van Renesse. JiST: An Engineering).
Efficient Approach to Simulation Using Virtual [20] E. Weingartner, H. vom Lehn, and K. Wehrle. A
Machines. Software: Practice and Experience, Performance Comparison of Recent Network
35(6):539–576, 2005. Simulators. In Communications, 2009. ICC ’09. IEEE
[6] A. M. Batishchev. Low Orbit Ion Cannon. International Conference on, pages 1–5, 2009.
http://sourceforge.net/projects/loic/.
[7] D. Bernstein and E. Schenk. TCP SYN Cookies.
on-line journal, http://cr.yp.to/syncookies.html, 1996.
[8] K. A. Chrysafis and B. K. Papadopoulos.
Cost–volume–profit Analysis Under Uncertainty: A
Model with Fuzzy Estimators Based on Confidence
Intervals. International Journal of Production
Research, 47(21):5977–5999, 2009.
[9] D. Dittrich. The ‘Stacheldraht’ Distributed Denial of
Service Attack Tool.
http://staff.washington.edu/dittrich/misc/
stacheldraht.analysis, 1999.
[10] T. Henderson. ns-3 Overview.
http://www.nsnam.org/docs/ns-3-overview.pdf, May
2011.
[11] H. J. Kashyap and D. Bhattacharyya. A DDoS Attack
Detection Mechanism Based on Protocol Specific
Traffic Features. In Proceedings of the Second
International Conference on Computational Science,
Engineering and Information Technology, pages
194–200. ACM, 2012.
[12] M. Lesk. The New Front Line: Estonia under
Cyberassault. Security & Privacy, IEEE, 5(4):76–79,
2007.
[13] R. Lippmann, J. W. Haines, D. J. Fried, J. Korba, and
K. Das. The 1999 DARPA Off-line Intrusion Detection
Evaluation. Computer networks, 34(4):579–595, 2000.
[14] R. P. Lippmann, D. J. Fried, I. Graf, J. W. Haines,
K. R. Kendall, D. McClung, D. Weber, S. E. Webster,
D. Wyschogrod, R. K. Cunningham, et al. Evaluating
Intrusion Detection Systems: The 1998 DARPA