Cynthia Wagner
email: cynthia.wagner@uni.lu

Jérôme François
email: jerome.francois@uni.lu

Radu State
email: radu.state@uni.lu

Thomas Engel
email: thomas.engel@uni.lu

Machine Learning Approach for IP-Flow Record Anomaly Detection

Keywords: Netflow Monitoring, Kernel Functions, Machine Learning Techniques, Intrusion Detection

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In today's business areas, it is nearly impossible to imagine network architectures without monitoring tools, and this for several reasons. Network monitoring has become one of the most important tools in the detection of malicious or unusual events of different genres, and gathering network traffic information is the main requirement for taking appropriate countermeasures. A realistic assumption is to say that nearly all commercially available routers can export monitored data, called Netflow records. These IP flow records, chronologically ordered ranges of packet sequences, are the most important source for the analysis of unidentifiable events, even if a lot of storage capacity and processing time is needed for an accurate analysis.

In this paper, we present a new method for processing Netflow records by referring to Machine Learning techniques. In a first step, we have developed a new kernel function that operates over Netflow records by analyzing its contextual and quantitative information. For the detection of IP flow record anomalies, kernel functions have proven their usefulness, but to achieve good classification results, we apply in a second step, our kernel function to Support Vector Machines.

The structure of the paper is as follows: In section 2, we present the architecture of the model. We briefly present fundamental background information and present the anomaly detection part of the tool where we describe its main components. The more we describe the kernel function that has been used for the evaluation of Netflow records. In section 3 we describe the data set and the different attacks, used for the experiments and in section 4 we present our evaluation methods and discusses experimental results. Section 5 discusses related work and conclusions are given in section 6.

The Architecture of the Anomaly Detector

In the following section, we present the architecture of our model. The Netflow records, which are exported by the routers from the network to the Netflow collector module are used as input for our Anomaly Detector tool, represented in Figure 1. A Netflow record is a series of packets sent between two entities (hosts) in a chronological order. A Netflow record is composed of a source and destination IP-address, source and destination port numbers, traffic volume, packets and protocol for a session between the previous two endpoints. An argument for using Netflow records is, that they include all relevant network traffic information in a compressed version. It is composed of different modules, which are responsible for the pre-processing, evaluation and interpretation of the results, which means to answer the question, is there an attack or not. Detecting anomalies is related to classifying data in two different classes: benign and anomalies. Regarding the current context, the range of anomalies is very huge including Spam, Denial of Service (DoS), Scanning, Botnets, etc. Therefore, the anomaly class should regroup many different kinds of data points and so usual classifiers are not well fitted. For this purpose, multi-class classifier are potential solutions, but their main drawback is the necessity to have labeled samples for each class of anomaly you expect to detect. It also means that a system based on such classifier is unable to detect new anomalies which is usually the kind in the current networks and Internet. Therefore, we have decided to use a very specific kind of algorithm which is called one-class classification. The aim is to build a classifier that is able to detect new anomalies, i.e. data points which do not follow a general traffic profile which is used for training the classifier.

More precisely, we consider Support Vector Machine (SVM) which provide good accuracy with a low complexity in many domains [START_REF]Support Vector Machines: Theory and Applications[END_REF]. Besides, there is a specific one-class method which was initially proposed in [START_REF] Schölkopf | Estimating the support of a high-dimensional distribution[END_REF]. This specific method has also proven its accuracy for intrusion detection in different contexts such as the system calls on a UNIX system. We propose to use OCSVM (Oneclass SVM) [START_REF] Wang | Anomaly intrusion detection using one class svm[END_REF] for analyzing Netflow records based on a new kernel function.

OCSVM

In OCSVM, the main requirement is to have a dataset of samples assumed to represent the single class of data points. This set is denoted X. The general way to define the problem is the following one: assuming that the points from an original space S follow an underlying probability P , the goal is to define a subset space of this original space S such that the probability that a point from P lies outside S is maximized by a given value between 0 and 1 [START_REF] Schölkopf | Estimating the support of a high-dimensional distribution[END_REF]. This means that during the learning phase, the goal is to determine a function which is positive when applied to a point from S and negative otherwise. Therefore, during the testing phase, the sign of this function indicates if the point is classified to the single class or not.

Assume, a labeled sample X = {x 1 , . . . , x n }, the objective is to capture a small region enclosing these points by projecting them into a higher dimensional space, such that a better separation between a defined proportion of X and the origin, is obtained. The goal is to find a hyperplane with maximum margin, i.e., by maximizing its distance from the origin. The projection is performed thanks to the function φ(x) and the proportion of points to separate is defined by 1ν with ν ∈ [0, 1]. This problem is usually defined as follows:

min w,ρ,ξi...n 1 2 ||w|| 2 + 1 νn n i=1 (ξ i -ρ) (1)
subject to:

< w.φ(x i )) >≥ ρ -ξ i , ξ i ≥ 0 (2)
The optimization problem has to be solved to identify two variables: w and ρ. ξ i variables represent slack variables for allowing some points of S to not be located on the right side of the hyperplane. This avoids to bias the problem with very particular and maybe erroneous points. Since defining a projection function is not obvious, support vector methods traditionally rely on kernel functions. From a general point of view, they can be considered as similarity measure which have to be finitely positive semi-definite functions. The kernel function K(x i , x j ) is equal to < φ(x i ), φ(x j ) >. Based on this function and by transforming the problem into its dual form, we obtain:

min αi...n 1 2 n i,j=1 α i α j K(x i , x j ) (3)
subject to:

0 ≤ α i ≤ 1 νn , n i=1 α i = 1 (4)
Once this optimization problem is resolved, the decision function is defined by:

f (x) = sgn( n i=1 α i K(x i , x) -ρ) (5)
Therefore, this function is applied to each data point to test and if the sign is positive, it means that the point belongs to the class otherwise it is an anomaly. Obviously, many details were omitted due to space limits: the interested readers should refer to [START_REF] Schölkopf | Estimating the support of a high-dimensional distribution[END_REF][START_REF]Support Vector Machines: Theory and Applications[END_REF]. In fact, the main parameter ν represents the maximal proportion of points of X lying on the wrong size of the hyperplane.

Unsupervised classification

OCSVM is usually used in a supervised manner as described in the previous section. However, the training can identify outliers thanks to the slack variables ξ i . Therefore, only by applying this step to an entire dataset, detecting outliers and anomalies is possible. In this case, the parameter ν defines the maximum number of potential anomalies. Thus, it can be regarded as a threshold in a standard method for detecting a deviation from a profile. The main difference is that OCSVM benefit from a better detection, based on a better separation of data points in the high dimensional space. Thus, we investigate both supervised and unsupervised method in this paper. The main advantage of the supervised one is that it should be more accurate due to the learning stage. Its main drawback is the need of sample data which are free of anomalies while the normal traffic is well represented regarding the different context that may happen. This completeness may be hard to obtain and the unsupervised technique can counter this requirement.

The Kernel Function for Netflow Processing

Kernel functions have proved their potential in the classification of high dimensional data. A kernel function calculus is homologous to a similarity measure for small data portions, where a mapping of an input space onto a higher dimensional space is performed as already explained in the previous sections. This makes it possible to separate dissimilar data and to calculate the distances, which are derived from a dot product, in this new space. We refer to Vapnik [START_REF] Vapnik | Statistical Learning Theory[END_REF], who defines

a kernel function K as a mapping of K : X × X ∈ [0, ∞[ from an original input space X to a similarity score K(x, y) = i φ i (x)φ i (y) = φ(x) • φ(y)
, where φ i (x) describes a feature function over a data snippet x. A general property of a kernel function is symmetry, such that [K(x, y) = K(y, x)] and positive-definitness.

For analyzing monitored windows of Netflow records, we have introduced a new kernel function K(W 1 , W 2 ), which enables to determine the similarity between two windows of IP flow records W 1 and W 2 of n seconds, in order to detect anomalies. An illustrating example of input Netflow windows are shown in Figure 2. As input space we use the Netflow records log files and define two metrics for our kernel function, provided by these flow log files. The first parameter in our kernel function are the IP-addresses from the source (src) and destination (dst) in CIDR 1 format, such that IP = (pref ix, suf f ixlength). While comparing IP-addresses, we consider the pref ix as the longest common sequence of two IP-addresses and the remaining bits as the suf f ixlength. As second parameter we have the quantitative factor of the captured Netflow records, which uses the traffic volume, called vol in Bytes. By this, we can model a Netflow record window for our kernel function as a set of IP flows W = {f 1 , . . . , f n } and a IP flow f defined as a f i =(pref ix(src) i , suf f ixlength(src) i , pref ix(dst) i , suf f ixlength(dst) i ,vol i ). Our kernel function for Netflow windows K(W 1 , W 2 ) returns as output a similarity score given by the sum over four functions over all flows in a window, considering source and destination information as well as traffic volume and is composed of, a similarity function s(a i , b j ) ∈ [0, ∞[ for the source and destination information and a matching function v(a i , b j ) ∈ [0, 1] for the traffic information. A higher similarity score means the more similar two windows are. Our kernel function K for two windows W 1 and W 2 is defined as

K(W 1 , W 2 ) = i∈N W 1 ,j∈N W 2 s src (a i , b j ) × v src (a i , b j ) × s dst (a i , b j ) × v dst (a i , b j ) (6)
where the windows of flows denoted by W 1 and W 2 are represented by N W1 and N W2 . We define the similarity measure parts for source and destination, s src (a i , b j ), s dst (a i , b j ) between flows a i and b j by

s src,dst (a i , b j ) =          2 suf f ixlength j 2 suf f ixlength i if pref ix i prefix of pref ix j 2 suf f ixlength i 2 suf f ixlength j if pref ix j prefix of pref ix i 0 otherwise (7)
and the matching function for source and destination v src,dst (a i , b j ) by

v src,dst (a i , b j ) = exp - | vol i -vol j | 2 σ 2 (8)
σ is the width scaling factor for the Gaussian kernel [START_REF] Burges | A tutorial on support vector machines for pattern recognition[END_REF] and can be estimated on different ways, as for example by a grid search, where a range of values are used to find the optimal values for the kernel. To identify anomalous events, we use the different successive windows K(W i , W i+1 ) which we compare to each other. To illustrate the effectiveness of our kernel function without referring to

!" #!!!" $!!!" %!!!" &!!!" '!!!" (!!!" )!!!" *!!!" +!!!" #!" $!" %!" &!" '!" (!" )!" *!" +!" #!!" ##!"

!"# $ %&# $'( )*(++& ,-./01&1$23014&

,-."/0112"34356" 78"9*&":"9*(" Fig. 3. Visualizing an attack by using the kernel function classification, we show on a real example in Figure 3 that the used kernel function detects in this case a UDP flooding attack. Anomaly detection is a quite challenging topic and evaluating new innovative solutions is a hard task due to the lack of labeled datasets. There were some works aiming at providing such datasets. A very well-known dataset is the Lincoln data set2 but it is quite out-dated now. A recent dataset is provided in [START_REF] Sperotto | A labeled data set for flow-based intrusion detection[END_REF] based on Netflow records. However, this dataset is only limited in attacks since they use a honeypot. Furthermore, this kind of architecture collects attack traces from end-user point of view and not from the network point of view. The dataset is generated by injecting synthetic attack traces into real traces using the tool Flame [START_REF] Brauckhoff | Flame: a flow-level anomaly modeling engine[END_REF]. This tool is based on Netflows and is well suited in our case. It takes as input (flow reader) Netflow record files containing traces without malicious activities and creates attacks by generating (flow generator) or deleting (flow deleter) flow records based on attack models. The main idea is that attacks will generate traffic but also affect normal traffic like DDoS. That is why there is a need to merge these activities using the flow merger. Figure 4 highlights this process. A key part of Flame are the attack models which have to be created for the simulation of attacks. We use as starting point a real dataset provided by a network operator from Luxembourg and assume that it is free of malicious Netflow records. This assumption is made based on a secondary semi-automated screening of the traffic, where an ISP specific solution was used. The general characteristics of this data set are provided in Table 1. Even if the duration of the data set is small, it is sufficient for evaluating our scheme, since we have limited all attacks to last only 30 seconds. The Flame website also provides some attack models which were derived from real observations. At first we used this described attack model and later on, we extended it to create more stealthy attacks. Our data set contains the following attacks:

-Nachi scan: the Nachi/Welchia worm was released in 2003. First, it tests the reachability of hosts using ICMP scan which is considered in the attack model. One host of our original dataset sends single ICMP packets of 92 bytes to destination IP addresses following several properties: a shift between 40 to 45 between two consecutive scans, a positive or negative shift of 400 every 200 scans and a shift between 45 to 110 every 800 flows. The inter-arrival time of flows is generally around 2 milliseconds but there is a break of around 61 milliseconds after 5 scans. -Netbios scan: it is a traditional scan for finding vulnerabilities. The corresponding UDP flows contain a single packet to port 137 where the interarrival time is generally between 60 and 70 milliseconds. The destination hosts are scanned sequentially while keeping one IP address sometimes. Besides, between 100 and 200 scans there is a shift in the destination IP address between 60 and 70. -DDoS UDP flood: one host of our dataset receives UDP packets on various ports and also sends from multiple IP addresses with various ports. The attack operates by a burst of 40 flows. Then, there is a break between 60 and 120 milliseconds. -DDoS TCP flood: this denial of service attack is against web servers running on TCP port 80 with 3 packets and 128 bytes. There are bursts of 10 packets before a break between 60 and 120 milliseconds. -stealthy DDoS UDP flood: different to a normal UDP flood, we apply here more randomness on flows characteristics (number of packets, size, duration). The inter-arrival time can reach 1 second which represents a very stealthy characteristic for a flooding attack. This attack is more generic in order to improve the completeness of our tests. -DDoS UDP flood + traffic deletion: this is equivalent to the DDoS UDP flood, but each additional flow originated by the victim has a probability of 0.2 to be deleted due to the victim overload. -Popup spam: this kind of spam is similar of sending undesired Windows Messenger popups by using UDP port 1026 and 1027. Only one packet of 925 bytes is needed. The victims IP addresses do not highlight a regular pattern because two consecutive IP addresses have a gap of 200 addresses. The interarrivaltime is generally lower than 1 millisecond except every 200 flows where it is around 64 milliseconds and every 550 where it is 250 milliseconds.

-SSH scan + TCP flood: the goal of TCP scan is to probe an SSH server by trying to log in. This is by far the most popular attack occuring in the wild.Each flow contains between 1 and 4 packets. The inter-arrival time oscillates between 1 to 50 milliseconds. The destination IP addresses are scanned in a sequential way until 400 scans are executed approximately. After, there is a shift between 200 to 400 IP addresses. In order to test our approach in a real scenario, 5% of the attacks are considered successful and the corresponding victims trigger a TCP flood attack.

Evaluation

In the following section we describe the experimental part of this work. We have generated the data sets following the data set generation procedure, as shown in Figure 4. Generated Netflow windows have a duration of 5 seconds each. Then, we have applied our kernel function for the contextual and quantitative evaluation of Netflow record windows. On the similarity values obtained by the kernel function, the OCSVM has been applied in order to see, if our method can detect the different attacks or not. For each data set, we have used for the training phase about 20% of our Netflow record windows and for the testing phase the remaining 80%. The outcomes for our different simulations can be seen in Table 2. The results by using the OCSVM are very promising, we can see that we have only a very low false positive rate and that we have an average accuracy over all attack classes of around 92% for the classification results. To compare our work with others, refer to the work of Yuan et al. [START_REF] Li | An svm-based machine learning method for accurate internet traffic classification[END_REF] which used SVM for classification of network traffic of different types having attacks like worms, scans, etc. Yuan et al. achieved a similar classification accuracy (92,8%) as we did, which validates our approach, but there are no indications about the complexity of their algorithms.

Related work

Network monitoring techniques as, for example the work by Bahl et al. [START_REF] Bahl | Towards highly reliable enterprise network services via inference of multi-level dependencies[END_REF], are based on Netflow records or related data. One of the main interests of Netflow records is not only their compactness, but they can be used without respecting a complete TCP state machine and are available in most commercial available routers. For example, Karpilovsky et al. [START_REF] Karpilovsky | Quantifying the extent of ipv6 deployment[END_REF] analyzed the IPv6 deployment by referring to a Netflow analysis. A major drawback of using Netflow records is storage capacity. Large amounts of Netflow records (30 000 flows/second) are normal for ISP networks or networks with high link loads. In [START_REF] Sommer | Netflow: Information loss or win?[END_REF], authors have described the effect of Netflow capture on the accuracy analysis. To reduce the aspect of storage or to perform near real time analysis, it is often referred to Netflow sampling as described for example by C. Estan [START_REF] Estan | Building better netflow[END_REF] or Paredes-Oliva [START_REF] Paredes-Oliva | Portscan detection with sampled netflow[END_REF], but the challenge remains to identify good sampling rates. In the domain of information security and intrusion detection, a lot of relevant work has already been performed for evaluating and processing Netflow related data [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF] [7], as for example statistics on packet information.

A new observed trend is to refer to Machine Learning Techniques for evaluating Netflows or IP flow related data, like Flow Mining [START_REF] Lee | Mining in a data-flow environment: experience in network intrusion detection[END_REF], where main issue relies on the selection of good parameters for achieving high quality. Another aspect of using Machine Learning are the kernel methods, strong mathematical tools, which have found their utility in the evaluation of large and complex data sets. Kernel methods have already been introduced as a mathematical tool in early 1900's by Hilbert and were first introduced as part of Machine Learning Techniques in the late 1990's by Vapnik [START_REF] Vapnik | Statistical Learning Theory[END_REF] and further developed in the early 2000's by Schölkopf et al. [START_REF] Schölkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF]. In recent past, kernel functions found their applicability in most different various domains, i.e. Genetics [START_REF] Nguyen | Optimizing weighted kernel function for support vector machine by genetic algorithm[END_REF], Bioinformatics [START_REF] Vert | A tree kernel to analyze phylogenetic profiles[END_REF], Natural Language Processing [START_REF] Collins | Convolution kernels for natural language[END_REF], and can be applied to most different input formats, as structured format, i.e. graphs, trees, or unstructured format, i.e. texts.

A work that is similar to our work is the evaluation of temporal and spatial IP-flow records by kernel methods presented by Wagner et al. in [20] and [START_REF] Wagner | Peekkernelflows: Peeking into ip flows[END_REF]. The main difference is that the authors in [20] [START_REF] Wagner | Peekkernelflows: Peeking into ip flows[END_REF] refer to spatial and temporal aggregated IP-flows, using the Aguri [START_REF] Kaizaki | Characteristics of denial of service attacks on internet using aguri[END_REF] tool and apply a kernel function to detect anomalies. By referring to the aggregation tool, it is only possible to get a view from the source or destination side, but no global view of both sides. Using Netflow record windows without aggregation, we can keep a global view of the whole traffic information. Then, we go further and apply Support Vector Machines in order to detect and classify benign traffic from attacks. Supervised learning has become a common tool for evaluating large data sets on common patterns, as for example by using Support Vector Machines (SVM) [START_REF] Schölkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF] [START_REF] Vapnik | Statistical Learning Theory[END_REF]. SVMs have proven their utility in most different domains as in natural language processing [START_REF] Collins | Convolution kernels for natural language[END_REF] or bioinformatics [START_REF] Vert | A tree kernel to analyze phylogenetic profiles[END_REF]. Since a few years, SVMs are also used in computer security, where they are used for intrusion detection [START_REF] Khan | A new intrusion detection system using support vector machines and hierarchical clustering[END_REF] [START_REF] Zhang | Using support vector machine to detect unknown computer viruses[END_REF].

Conclusion

In this paper, we have presented a new approach for the evaluation of Netflow records on most various attacks on a real data set obtained from a large ISP in Luxembourg. For validating our approach, we have generated different types of attacks by referring to the trace modification tool called Flame. Our contribution first consists in the evaluation of Netflow records in their quantitative and contextual context, where we have developed a new kernel function for calculating the similarities between Netflow windows. Second, we have applied a new SVM algorithm to our developed kernel function in order to detect different attacks in data sets. We have implemented our tool in a distributed way by using Hadoop 3 . The classification results are very promising, such that most attacks can be identified.

Fig. 1 .

 1 Fig. 1. Anomaly detector architecture

  !""#$%%$!&'%()(%)!(*+!#'',#+'-./''%++*%+,*%!0*(#)+#1#1'$2'#&*!(+*%,&*(!),&''%!(%''1*!'3'''''%' !""#$%%$!&'%()(%)!(*+!#',0!'45/'''%,0*%+1*+(*&+)0"'$2'#&*!(+*!&*,+),!1#'''%!00'''0%(!01'''''%' !""#$%%$!&'%()(%)!(*+,"''+1('45/''%,0*%+1*+&*%##)0"'$2'#&*!(+*((*+%)%!&!'''0+0+''''&*0'3'''''%' !""#$%%$!&'%()(%)!(*+#,'',#%!'45/''%!#*!+*!%(*!"+)++,'$2'#&*!(+*%(!*%,1)%,&''(,(+''''&*1'3''%' !""#$%%$!&'%()(%)!(*&(1''(#%'-./''!!0*!"+*&!*!"(),"&+'$2'#&*!(+*,#*!,+),"''(%&,''''%*+'3'''''%' !""#$%%$!&'%1)"!),(*#,"''%1+'-./'''#&*!(+*%!%*!!#)(,(%#'$2'+#*##*1+*!"%)(,''''%(%''''01''%' !""#$%%$!&'%1)"!),(*#,"''+(%'-./'''#&*!(+*%!%*!!#)!&!0&'$2''%(1*!,(*(*!"()(,''%!(+''''#&'''%' !""#$%%$!&'%1)"!),(*#,"''!%"'-./'''+,*!,0*%1&*!,%)(,'$2'#&*!(+*%!%*!!#),1+0'''%%!'''%+#'''%' !""#$%%$!&'%1)"!),(*#,"''+&%'-./'''#&*!(+*%,%*%,+)%"!('$2'%#,*%1,*%0&*%"1)!("!''%11''(0''%' !""#$%%$!&'%1)"!),(*#,"''%!,'-./'''+%*%0%*!,#*!(+)#%!+'$2'+,*%1(*#1*%)(,''''%%%'''&1''%' !"# $ %&# ' (&)&*& 6789:;'6 % )' 6789:;'6 ! )'

Fig. 2 .

 2 Fig. 2. Principle of kernel function and example of Netflow windows

Fig. 4 .

 4 Fig. 4. Dataset generation

Table 1 .

 1 Data set statistics

	Flow #	1,371,194
	IP addresses #	128,781 (source), 125,723 (destination)
	Duration	13min 31sec
	Bytes #	7.5GB
	Avg. bytes/flow	5492
	Packets #	11.5M
	Avg. packets/flow	8.36
	UDP Flows #	983,511
	TCP Flows #	375,132
	ICMP Flows #	11,347
	Other protocols Flows #	1204

Table 2 .

 2 Classification results by using one class Support Vector Machines

	Type of Attack		Results
		Accuracy False Positive rate True Negative rate
	Nachi scan	0.896	0.004	0.996
	Netbios scan	0.938	0.000	1.000
	Popup Spam	0.915	0.023	0.97
	SSh scan + TCP flood	0.917	0.011	0.989
	DDoS UDP flood	0.915	0.022	0.978
	DDoS TCP flood	0.907	0.033	0.967
	stealthy DDoS UDP flood	0.938	0.000	1.000
	DDoS UDP flood + traffic deletion 0.934	0.000	1.000

CIDR -Classless InterDomain Routing: A standard system for the IP-address allocation and IP packet routing, where IP addresses are described by a network address part and a host identifier part within that network

http://www.ll.mit.edu/mission/communications/ist/index.html

http://hadoop.apache.org/

Acknowledgments. This project has been supported by the SnT -Interdisciplinary Centre for Security, Reliability and Trust. Furthermore, we want to address our special thanks to RESTENA Luxembourg for their support.


Jérôme Franc ¸ois
email: jerome.francois@uni.lu

Giovane C M Moura

Aiko Pras
email: a.pras@utwente.nl

Cleaning Your House First: Shifting the Paradigm on How to Secure Networks

The standard paradigm when securing networks is to filter ingress traffic to the domain to be protected. Even though many tools and techniques have been developed and employed over the recent years for this purpose, we are still far from having secure networks. In this work, we propose a paradigm shift on the way we secure networks, by investigating whether it would not be efficient to filter egress traffic as well. The main benefit of this approach is the possibility to mitigate malicious activities before they reach the Internet. To evaluate our proposal, we have developed a prototype and conducted experiments using NetFlow data from the University of Twente.

Introduction

When it comes to protecting their networks, Internet Service Providers (ISPs) and businesses employ a large set of specialized tools aiming at mitigate attacks targeting their networks. Examples of such tools include network firewalls, Network Intrusion Detection Systems (NIDS), antivirus, web proxies, and mail filters. Stills, we are far from having secure networks. To better illustrate this, take as example one of the largest security threats on the Internet nowadays: botnets [1]. By definition, a botnet is a network of compromised hosts (also known as bots/zombies) controlled by a botmaster, via a Command and Control (C&C) channel. They are used for different purposes, such as phishing, malware propagation, distributed denial of service (DDoS), and spamming. It is estimated 85% of the more than 100 billion daily spam messages are sent by bots [START_REF] John | Studying spamming botnets using Botlab[END_REF].

Behind the current security problems, there might be a subtle defense approach decision: ISPs and businesses usually focus on protecting their own network from the outside world, filtering mostly ingress traffic. However, much less attention is usually given to egress traffic, meaning that malicious traffic find little or no barrier to leave the originating domain. One example is spam -most companies filter heavily incoming mail, but usually they do not much when their own users spam other domains [START_REF] De Vries | Fighting spam on the sender side: A lightweight approach[END_REF]. Due to that, by the time a security event is detected, it has already taken its own share from routers, network links and computers that it had to go through to reach its final target, imposing direct and indirect costs. This left us wondering if it would not be the case of changing the paradigm on how we secure our networks, filtering egress traffic as well. Thus, this leads us to the following research question: what can be achieved by filtering egress traffic from a particular domain? -that is, why not "clean your house before looking for dirty at other's houses?" Some research works suggest that is worth doing. Van Eeten et al., for example, have shown that 10 ISPs account for 30% of unique IP addresses sending spam worldwide [START_REF] Michel Van Eeten | The Role of Internet Service Providers in Botnet Mitigation: An Empirical Analysis Based on Spam Data[END_REF]. According to that, by filtering outgoing mail from only 10 ISPs, we could reduce almost one third of all spam. In another work, de Vries et al. [START_REF] De Vries | Fighting spam on the sender side: A lightweight approach[END_REF] have shown that egress mail traffic can be easily filtered with higher detection rates.

In order to filter egress traffic, many sources of data can be employed, such as mail server logs, network traces, DNS blacklists. In this work we propose the use of flow records [5]. The main advantage is scalability, since flow records provide summarized information about the network traffic, thus coping much better with cfurrent high speed multi-gigabit lines. Besides that, by using flows records, the communication patterns in a network can be evaluated instead of having to process the content of each packet [START_REF] Sperotto | An Overview of IP Flow-Based Intrusion Detection[END_REF]. Finally, flows records are application independent, so they can potentially be used to detect and block any type of malicious activity in the network.

To analyze flow records, in this work we employ cluster analysis, since it is a unsupervised learning technique that does not require a priori knowledge about malicious communication patterns (in contrast to signature-based NIDS). The assumption is that we can detect different types of malicious traffic using flow records and cluster analysis. To prove technical feasibility of our proposal, we have developed a prototype and conducted an evaluation on network flows obtained from the University of Twente.

The rest of this paper is organized as follows: Section 2 provides background information and introduces the architecture proposed for detecting intra-domain malicious hosts. Next, Section 3 details the clustering algorithms employed. After that, Section 4 covers the experiments and the results obtained. Next, Section 5 presents the related work. Finally, Section 6 concludes the paper and proposes future work.

Intra-domain Malicious Hosts Detection Architecture

Figure 1 shows the proposed architecture for detecting intra-domain malicious hosts. NetFlow-enabled routers export flow records to a collector. This information is stored on a database and fed into the Anomaly Detection Engines (step 1 -in between parentheses -in the same figure) which are responsible for analyzing the input data. A broad range of attacks can be analyzed such as DDoS or port scan but we focus on spamming since botnets are well used for spamming [START_REF] Xie | Spamming botnets: signatures and characteristics[END_REF].

Hence, we aim to find bots by looking at group of hosts having similar communication patterns with some of them involved in spamming activity. In this way, detecting spammers helps to figure out entirely botnet related traffic (C&C as well as other malicious activities). To do that, we first obtain a list email senders (step 2 in Figure 1) and exclude legitimate mail servers from our domain (step 3). Next, hosts sending many more emails than others are considered as potential spammers (step 4). After obtaining a list of spamming hosts, we compute the following aggregated metrics (obtained from Botminer [START_REF] Gu | Botminer: clustering analysis of network traffic for protocol-and structure-independent botnet detection[END_REF]) for all flows: the average number of individual flows per hour (fph), the average number of packets per flow (ppf ) and the average number of bytes per packet (bpp).

In the end, for each flow we have the following tuple: <source IP address, destination IP address, destination UDP/TCP port, fph, ppf, bpp>. These metrics (step 5) allow to easily compare flow records from different hosts in order to find shared communication patterns (step 6). For example, if messages sent by a bot master reach two different hosts in our network, it is expected that they have similar properties, such as similar number of packets and bytes. In the same way, bots from a peer-to-peer botnet should exhibit similar communications to route the messages and to maintain the coherency of routing tables when nodes join or leave the network.

Once these agglomerative metrics are computed, the next step is to compare such metrics for flows related to hosts exhibiting abnormal activities in order to cluster them (step 6). It is important to note that it is applied on flows and not on hosts. It means that it also helps to distinguish the malicious traffic pattern from the benign ones for a single host.

The major advantage is the reduction the number of flows to be analyzed. Then, we extend the clusters to other flows (step 7) by comparing them with flows related to suspect hosts, reducing the overall complexity of the algorithm. Finally, a score is computed (step 8) for each cluster based on the similarity of flows within it and the number of hosts it contains which are tagged as suspect. Hosts as source of Netflow included in highly scored clusters are declared as malicious (step 9).

Detection Algorithms

Anomaly Detection Engine -Top Email Senders

On step 2 in Figure 1, we have to find a list of spamming hosts. After listing all hosts that have connections to mail servers outside our domain (machines have outgoing TCP connections on port 25), we remove legitimate IP addresses of legitimate mail servers from UT (step 3). Finally, we compute two metrics for each remaining host:

n i : the number of mail flows records per the host i, b i : the total volume of email data sent per host i (in bytes).

The idea behind combining these metrics is that we can detect both hosts contacting many different mail servers and hosts sending too much mail data (specially related with spam campaigns that include attachments, such as PDF files). A more complex approach to detect spam using flow records was proposed by Sperotto et al. [START_REF] Sperotto | Detecting spam at the network level[END_REF]. However, in our case we employ a faster and simpler approach because the output is the list of potential spammers for which no decision have to be taken and so can include benign hosts which will be discarded afterwards.

Therefore, a host is considered as a spamming one if the number of emails and bytes sent is higher than the observed average plus a margin expressed as a multiple of the standard deviation. Considering all hosts, the average number of emails sent by an individual host is avg n and the corresponding standard deviation is std n . In the same way, avg b and std b refer to the number of bytes. i is a spamming host if:

(n i > avg n + σstd n ) or (b i > avg b + γstd b ) (1)
In this paper, γ and σ are set to 3 based on preliminary experiments. The corresponding hosts form the set S which is constructed in a linear time (iteration over all email senders).

Email Senders Clustering

Before starting the clustering algorithm, we obtain the following tuple for each single flow: <source IP address, destination IP address, destination UDP/TCP port, number of bytes, number of packets>. After that, we divide this set into two subsets: F s , a subset that contains all the flows related to the spamming hosts and F a , that contains all the remaining flows from the other machines. Then, we compute for each flow f ∈ {F s ∪F a } the metrics introduced in section 2 ( f ph f , pp f f , and bpp f ).

In order to reduce the computational complexity, the first clustering process focuses on the suspect IP addresses (potential spammers) and creates clusters containing aggregated flow information from F s . Hence, the goal is to find similar communication patterns involving multiple suspect hosts. Without any prior knowledge, unsupervised clustering is required. Besides, there is no assumption about the shape of clusters (following a certain distribution) and that is why nearest neighbor clustering [START_REF] Day | Efficient algorithms for agglomerative hierarchical clustering methods[END_REF] is fitted in our case. Medoids based methods are excluded because they entail computational overhead.

Nearest neighbor clustering assumes that two data points belong to the same cluster if the distance, dist(d 1 , d 2 ), between them is lower than the threshold θ. Regarding our context, each data point represents a tuple f as a vector [ f ph f , pp f f , bpp f ]. After normalizing the values, we applied the Euclidean distance on the vectors since this is commonly used in various contexts with multidimensional data.

The algorithm iterates over all f i of F s and compute dist( f i , f j ) for all f j ∈ F s and f j = f i . The pairs of points which the resulting distance is lower than θ are aggregated into one cluster. If the aggregated points were prior assigned to another clusters, all points belonging to them are also aggregated (merging). The result is a set of clusters C. Like many unsupervised algorithm, computing the distance between each pair of data points is needed which implies a quadratic complexity. Thus, this clustering process is only applied to a limited subset of points which were previously selected and form the set F s .

Extending Clusters

The assignation list represents for each flow, the cluster where it is affected. Assuming K clusters, C = {c 1 , . . . , c K }, the assignation list is A = {a 1 , . . . , a |F s | } such that a i = c j if the flow f i ∈ F s is assigned to the cluster c j . Each remaining non suspect point is assigned to the closest cluster except if this distance is too high that lead to consider the host as a benign one. They are represented by points outside of clusters in Figure 2a The distance between a new point to assign and a cluster is the minimal distance between this point and any point of the cluster. The assignation list denoted A ′ = {a ′ 1 , . . . , a ′ |F a | } is defined as follows:

a ′ i = a k i f f k = arg min f j ∈F s dist( f i , f j ) and dist( f i , f k ) < θ ′ unassigned else (2)
From a computational point of view, the distance between each non suspect data point and suspect data points have to be computed.

Scoring

Once clusters are created, the goal is to identify those containing hosts with higher probability of being malicious. Since our approach relies on the malicious activities and the similar communication patterns, a score is assigned to each cluster based on these criteria. In brief, the first component of score named score anomaly i represents the proportion of hosts related to malicious activities in the cluster c i :

score anomaly i = |{ f j ∈ F s , a j = c i |} |{ f j ∈ F s , a j = c i |} + |{ f k ∈ F s , a k = c i |} (3)
The other component of the global score considers also the similarity among the flow information containing in the cluster. The lower the distances between the points of a cluster, the higher the score is. This can be regarded as the width of the cluster (maximal distance between two internal points as shown in figure 2b). The computation of the width can be long since clusters should contain hundreds or thousands of points and computing all pair-wise distance is quadratic. Therefore, we propose a simple method inspired from grid clustering techniques [START_REF] Schikuta | Grid-clustering: a fast hierarchical clustering method for very large data sets[END_REF] where each cluster is represented as a squared cell like in the toy example in figure 2b. Only one iteration per point is needed to compute the coordinate of the cell since the goal is to find the maximal and minimal value for each dimension (two in the toy example and three in our context). Assuming the cluster c i , the similarity score is defined:

score sim i = dist(FMin i , FMax i ) (4)
where FMin i and FMax i are fictive points containing minimal and maximal values for f ph f , pp f f and bpp f subject to f assigned to c i . For example, the first feature of FMin is: min

{ f j ∈F s ,a j =c i }∪{ f j ∈F a ,a ′ j =c i } f ph f j
Since, the iterations have only to cover each point one time, the complexity is O(n)

where n is the number of points in a cluster. Traditional methods have to compute pairwise distances for extracting then the minimal, maximal or the average one. Unlike our method, the complexity is O(n 2 ).

Finally, the global score of the cluster c i is the usual mean of both scores:

S i = score anomaly i + score sim i 2 (5)
If the score is higher than the threshold ψ, all source IP addresses related to the cluster are considered as malicious. It includes spamming hosts as well as other ones thanks to the cluster extension process.

Experimental Evaluation

In this section we describe the evaluation conducted to prove technical feasibility of our proposal. As describe in Figure 1, the first step is to obtain NetFlow data from external data sources. For this experiment, we have obtained two NetFlow datasets from the University of Twente (a /16 network):

-Dataset A: 1 hour of flow records (April 10th, 2010, from 5:00 PM to 6:00 PM CEST) -a total of more than 12 million records; -Dataset B: 2 hours of flow records (April 10th, 2010, from 3:00 PM to 5:00 PM CEST) -more than 24 million records.

Dataset A was used in the anomaly detection engine in Figure 1, while the dataset B was used in the host clustering engine. Next we present the detection results and the validation.

Malicious Host Detection

After obtaining the aforementioned datasets, we analyze the first one (A) to find hosts that have contacted more mail servers outside of our domain (steps 2 and 3 in Figure 1). Then, we removed legitimated mail servers from this list, and two hosts have been automatically selected to be fed into the host clustering engine. The first host was tagged as suspect since it has contacted 45 distinct mail servers outside our domain (some of them more than one time) within one hour, in a total of 250 flow records. Thus, we can assume that at least 250 accounts were target. The other host tagged as suspect has contacted 12 distinct mail servers in a total of 12 flow records.

Next, we have computed the metrics defined in Section 2 for the dataset B (step 5). In the end, we had 5,424,333 entries in the metrics table with the following format: IP source/destination, destination port, fph, ppf, and bpp. It is important to emphasize that we have computed these metrics for not only mail flow records, but all flow records. By doing that, our algorithm is suitable detecting common communication patterns and not only spam. So even, it helps to distinguish potential C&C flows from other ones even if there are few hosts.

In step 6 and 7, two level clustering is applied on the metrics obtained in the previous step, regard the parameter θ. We assume that θ = θ ′ (the similarity within a cluster has to be same when comparing spamming hosts or any other hosts). Therefore, when θ increases, more points are grouped within each cluster and so the total number of clusters decreases. This is shown in Figures 3a and3b where each cluster is represented by two points (the score and the size equivalent to the number of distinct source IP addresses among all flows of the cluster). The x-axis represents only an arbitrary cluster index but also indicates the total number of clusters which is the maximal index. More complex method, based on cluster characteristics, might be used to fine-tune the parameters similar to [START_REF] Franc ¸ois | Automated Behavioral Fingerprinting[END_REF].

In Figure 3a, there are two main groups of clusters. Firstly, many clusters have a very low scores. They represents normal group of IP addresses which the underling applications exhibit different patterns. Secondly, there are many clusters with high score (> 0.5). In fact, the corresponding sizes are very low (one or two IP addresses). Therefore, the high score is only due to the bias introduced by the anomaly score (score anomaly) equal 1. Indeed, such clusters may easily contain 100% of flows related to potential spammers since they contain only one or two IP addresses. That is why these clusters are discarded for further analysis. However, there is a third group of outlier scores below 0.1 between these extrema. In order to figure out them easily, θ is increased in Figure 3b to merge clusters with few IP addresses. This case is an extreme one showing very few clusters and highlighting only one score greatly higher than others (the second index on x-axis). Therefore, this case was chosen in the end of the clustering process. The selected cluster contains 100 different flow tuples from 52 distinct IP addresses under University of Twente domain, which represent the list of malicious hosts obtained in the step 7.

Complexity

The core construction of initial clusters is quadratic (section 3.2) due to the calculation of all pairwise distances. To avoid this drawback, some samples (potential spammers) are selected in a linear time (33k iterations) regarding the number of SMTP flows (section 3.1). Then, the two selected hosts coverages 143k records. It leads to 143k 2 calculations for the initial clustering. Then, 143k × 24M operations are necessary for the cluster extension which represent around 0.6% if no prior selection and clustering were performed (24M 2 iterations to compute all pair-wise distance). Finally, the scoring process has to deal with about 3,000,000 points in the worst case (the biggest cluster). The complexity of our scoring method is linear whereas traditional approaches are quadratic (section 3.4). So, the number of iterations is also divided by 3M.

Even our approach has similarities with other ones [START_REF] Gu | Botminer: clustering analysis of network traffic for protocol-and structure-independent botnet detection[END_REF], we have really focus on reducing the running time by optimizing the algorithms. This is particularly important when monitoring large networks.

Validation and Egress Traffic filtering

When evaluating the performance of techniques for intrusion detection, researches usually rely on labeled datasets, which contains meta-information about the attacks observed. Usually such kind of datasets are available in pcap format, i.e., complete network traces. Since our technique is based on flow records instead, we could not benefit from these datasets. Even though Sperotto et al. [START_REF] Sperotto | A Labeled Data Set for Flow-Based Intrusion Detection[END_REF] have provided the first labeled dataset for flow-based intrusion detection, this could not be used in our research, since in this work we evaluate egress traffic instead. More than that, their dataset is based on a single host -which is not suitable for our clustering technique. Due to that, we have to check manually the flow records associated to the 52 malicious hosts obtained as a result of our detection technique to try to find whether malicious behavior was observed or not. Some interesting findings were obtained:

-One desktop PC was found having 7151 SMTP flows to 245 different mail servers located in many different countries for a 24 hours period. Since flows contain only a summary of a connection, we cannot tell how many messages are sent per flow. Assuming, in this case, that only one message was sent per flow, we have a total of almost 5 mail messages send per second, which is very unusual for a desktop. Figure 4 shows the number of SMTP flows to each mail server. Moreover, the same machine have contacted two different IRC servers, in a total of 1193 flows. Such behavior is typical for a machine belonging to a spamming IRC botnet. -One Windows desktop found running a non-authorized service on UDP and TCP port 56168. After checking with the Security Administrator at UT, it was found that this machine was the desktop of a professor that was unaware of it. He was promptly notified. In this two hour period, this machine has been contacted by 72579 different IP addresses on the aforementioned port, transmitting more than 66MB of data. Also, a hidden web server was found on this machine, which was contacted by 353 different hosts. We have extended the analysis for this machine and found out that 330,925 different IP addresses reached it on April 10th 2010a very suspect behavior for a desktop. We suspect this machine may be working as a botmaster (remotely controlled) or as a coordination point for botnets like those used by Storm [START_REF] Porras | A Multi-perspective Analysis of the Storm (Peacomm) Worm[END_REF]. -Another computer on the wireless network -which, by definition, should not run any services -was found running a suspect service on port 23352, for TCP and UDP (mostly UDP). In this 2 hours period, the machine was contacted by 96.609 different hosts from various countries. Since this machine is mobile, we could not reach it by the time of the analysis. For this period, 19GB of data was transfered to these different hosts. -One machine from the student network was also running a suspect service on UDP and TCP port 32861, which was contacted by 77,434 different hosts in two hours. 67 MB of data were transfered in this case. -Another host was found running a suspect service on TCP and UDP port 39563, contacted by 79824 distinct IP addresses from various locations. 66 MB of data were transfered in this two hours.

Even though the validation process was manually and not extensively executed, this results shows that our approach was able to detect the involved hosts based on very small list of potential suspect addresses -2 spamming hosts detected before applying clustering. By blocking such malicious hosts in our domain ("cleaning our houses first"), we can avoid their malicious activities to reach the Internet. Some estimates can be calculated from blocking malicious hosts: assuming that every flow of the spamming bot we found represents a single spam, by blocking only this host, we could avoid 7151 bots, by dismantling it (looking at the IRC traffic) we could potentially avoid 715 millions spam messages to reach the Internet in a single day. That represents 878.2 GB of data by extrapolating the monitored metrics. The same reasoning can be extended to other machines that our previous analysis has figured out and as well to other source of network attacks, such as DDoS. The more egress filtering is employed by ISPs and businesses, the more malicious traffic can be blocked from the Internet.

Related Work

Van Eeten et al. [START_REF] Michel Van Eeten | The Role of Internet Service Providers in Botnet Mitigation: An Empirical Analysis Based on Spam Data[END_REF] have evaluated a dataset of 63 billion spam messages obtained between 2005 and 2008. By analyzing the IP addresses of the sources, they observed that 10 ISPs account for 30% of unique IP addresses sending spam worldwide, 50 ISPs for half of all sources. Even though this study was performed on a not up-to-date data set, it suggests the benefits that can be achieved by filtering egress traffic of few ISPs.

In another work, de Vries et al. [START_REF] De Vries | Fighting spam on the sender side: A lightweight approach[END_REF] have shown that egress mail traffic can be easily filtered using lightweight techniques. However, in this work the authors rely on the message's content when filtering the traffic. A survey on flow-based intrusion detection, on the hand, was presented by Sperotto et. al [START_REF] Sperotto | An Overview of IP Flow-Based Intrusion Detection[END_REF]. Differently from this work, the authors focus on detecting malicious host on the Internet, while in this work we target intradomain malicious hosts.

Deploying a honeypot to be infected by a bot software is usually a direct and convenient way to study a botnet but it may not be efficient [START_REF] Wang | Honeypot detection in advanced botnet attacks[END_REF]. Tracking infected hosts can also be done by monitoring DNS requests of the machines [START_REF] Moheeb | A multifaceted approach to understanding the botnet phenomenon[END_REF] especially for an IRC botnet. A lot of techniques detect a botnet relying on the malicious activities such as scanning or denial of service attacks [START_REF] Karasaridis | Wide-scale botnet detection and characterization[END_REF]. In our approach, we leverage the same knowledge but then we improve the botnet detection by detecting common communication patterns of the C&C channel. P2P botnets are usually detected by active techniques such as in [START_REF] Holz | Measurements and mitigation of peer-to-peer-based botnets: a case study on storm worm[END_REF]. Graph algorithms may be also employed to infer interesting properties of bots relationships [START_REF] Franc ¸ois | BotTrack: Tracking Botnets using NetFlow and PageRank[END_REF].

In this work, we have conducted a study case on spamming hosts. We based our work on two works by Gu et. al [8] [20]. In our work, we correlate malicious activities with C&C detected communication patterns. The main difference between BotMiner [START_REF] Gu | Botminer: clustering analysis of network traffic for protocol-and structure-independent botnet detection[END_REF] and our approach is that we apply clustering only to a small subset of Netflows resulting in clusters which are extended afterwards to all Netflows. It leads to a huge improvement of the complexity and so the running time.

Conclusions and Future Work

In this paper we propose a new paradigm to be employed by ISPs and businesses for protecting their own networks. Instead of solely filter ingress traffic, in this work we investigate the benefits that can be achieved by filtering egress traffic as well (cleaning our own house first). The motivation is that if such policy is widely adopted, the overall amount of malicious traffic on the Internet could be significantly reduced. That would ultimately lead to saving considerable amounts of money and computer/network resources.

Therefore, in this paper we investigated the following research question: what can be achieved by filtering egress traffic from a particular domain? To answer this question, we have refined clustering techniques to analyze flow records from the University of Twente. As our results have shown, we were able to detect many suspect hosts. By detecting and blocking one of these hosts, for example, we could have been able to avoid that 7151 spam messages could reach the Internet in first place. The same reasoning applies to the other suspect hosts. More than that, our results have shown that such filtering could help to detect and dismantle botnet operations outside the monitored domain. The benefits of egress filtering would only increase as more ISPs and businesses adopt it as a common practice.

As future work, we intend to combine surpervised detection methods (since they are more efficient to detect known attacks) with clustering analysis. The idea is to combine both methods for improving the detection accuracy in various scenarios. Finally, we plan to obtain an economic model in order to estimate how much can be saved by filtering egress traffic.

Fig. 1 :

 1 Fig. 1: Intra-domain malicious hosts detection architecture

Fig. 2 :

 2 Fig. 2: Clustering algorithms on a toy example

Fig. 3 :

 3 Fig. 3: Cluster construction

Fig. 4 :

 4 Fig. 4: Number of flows from one suspect host to different mail servers

  It is equivalent to |F s | × |F a | iterations. Considering the quadratic complexity of the constructions of clusters in the previous step, the total number of iterations is |F s | × (|F s | + |F a |) whereas naive clustering of all flows would have led to (|F s | + |F a |) 2 iterations.

Acknowledgments The authors would like to thank Radu State, Anna Sperotto, Marc Berenschot, Ramin Sadre, and Olivier Festor for their valuable comments, suggestions, and contributions for this work.