Pedro Casas
email: pcasas@laas.fr

Johan Mazel
email: jmazel@laas.fr

Philippe Owezarski

Unsupervised Network Intrusion Detection Systems: Detecting the Unknown without Knowledge

Keywords: NIDS, Unsupervised Machine Learning, Sub-Space Clustering, Evidence Accumulation, Outliers Detection, Network Attacks, DDoS, Buffer Overflows Network Traffic Capturing Multi Resolution Flow Aggregation Computation

Traditional Network Intrusion Detection Systems (NIDSs) rely on either specialized signatures of previously seen attacks, or on expensive and difficult to produce labeled traffic datasets for user-profiling to hunt out network attacks. Despite being opposite in nature, both approaches share a common downside: they require the knowledge provided by an external agent, either in terms of signatures or as normal-operation profiles. In this paper we present UNIDS, an Unsupervised Network Intrusion Detection System capable of detecting unknown network attacks without using any kind of signatures, labeled traffic, or training. UNIDS uses a novel unsupervised outliers detection approach based on Sub-Space Clustering and Multiple Evidence Accumulation techniques to pin-point different kinds of network intrusions and attacks such as DoS/DDoS, probing attacks, propagation of worms, buffer overflows, illegal access to network resources, etc. We evaluate UNIDS in three different traffic datasets, including the well-known KDD99 dataset as well as real traffic traces from two operational networks. We particularly show the ability of UNIDS to detect unknown attacks, comparing its performance against traditional misuse-detection-based NIDSs. In addition, we also evidence the supremacy of our outliers detection approach with respect to different previously used unsupervised detection techniques.

Introduction

The detection of network attacks is a paramount task for network operators in today's Internet. Botnets, Malwares, Distributed Denial of Service attacks (DDoS), buffer overflow attacks, network-scanning activities, and spreading worms or viruses are examples of the different threats that daily compromise the integrity and normal operation of the network. The principal challenge in automatically detecting network attacks is that these are a moving and ever-growing target [START_REF] Hansman | A Taxonomy of Network and Computer Attacks[END_REF][START_REF]Symantec Internet Security Threat Report, Trends for 2010[END_REF]. Network Intrusion Detection Systems (NIDSs) are the war-horses of network security. Misuse detection is the de-facto approach used in most IDSs. When an attack is discovered, generally after its occurrence during a diagnosis phase, the associated malicious pattern is coded as a signature by human experts, which is then used to detect a new occurrence of the same attack.

To avoid costly and time-consuming human intervention, signatures can also be constructed by supervised machinelearning techniques, using instances of the discovered attack to build a detection model for it. Misuse detection systems are highly effective to detect those attacks which they are programmed to alert on. However, they cannot defend the network against new attacks, simply because they cannot recognize those attacks which do not match their lists of signatures. Indeed, networks protected by misused detection systems suffer from long periods of vulnerability between the diagnosis of a new attack and the construction of the new signature.

On the other hand, anomaly detection uses instances of normal-operation traffic to build normal-operation profiles, detecting anomalies as activities that deviate from this baseline. Such methods can detect new kinds of network attacks not seen before. Nevertheless, they require training to construct profiles, which is time-consuming and depends on the availability of anomaly-free traffic instances. In addition, it is not easy to maintain an accurate and up-to-date normal-operation profile, which induces high false-alarm rates.

Despite being opposite in nature, both misuse detection and anomaly detection share a common downside: they require the knowledge provided by an external agent to achieve their goal, either in terms of attack-signatures or as normal-operation profiles. As such, current network security looks more like a reactive countermeasure than a proactive prevention mechanism. Over the past years we have, however, witnessed an increased interest within the network security community in shifting away from reactive defense towards more proactive security systems [START_REF] Wyler | Aggressive Network Self-Defense[END_REF]. Our thesis behind this work is that reactive, knowledge-based approaches are not sufficient to tackle the network security problem, and that a holistic solution should also include proactive, knowledge-independent analysis techniques.

Armed with these ideas in mind, we present an Unsupervised Network Intrusion Detection System (UNIDS) capable of detecting network attacks without relying on signatures, training, or labeled traffic instances of any kind. Based on the observation that network attacks, and particularly the most difficult ones to detect, are contained in a small fraction of traffic instances with respect to normaloperation traffic [START_REF] Androulidakis | Network Anomaly Detection and Classification via Opportunistic Sampling[END_REF] (we show that this hypothesis can always be verified by using traffic aggregation), their unsupervised detection consists in identifying outliers, i.e. instances that are remarkably different from the majority. UNIDS relies on robust clustering techniques based on Sub-Space Clustering (SSC) [START_REF] Parsons | Subspace Clustering for High Dimensional Data: a Review[END_REF], Density-based Clustering [START_REF] Ester | A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[END_REF], and Evidence Accumulation (EA) [START_REF] Fred | Combining Multiple Clusterings Using Evidence Accumulation[END_REF] to blindly extract the traffic instances that compose an attack.

UNIDS runs in three consecutive steps, analyzing packets captured in contiguous time slots of fixed length. Figure 1 depicts a modular, high-level description of this system. The first step consists in detecting an anomalous time slot in which the clustering analysis will be performed. For doing so, captured packets are first aggregated into multiresolution traffic flows. Different time-series are then built on top of these flows, and any generic change-detection algorithm based on time-series analysis is finally used to flag an anomalous change. The second step takes as input all the flows in the time slot flagged as anomalous. At this step, outlying flows are identified using a robust multiclustering algorithm, based on a combination of Sub-Space Clustering (SSC) [START_REF] Parsons | Subspace Clustering for High Dimensional Data: a Review[END_REF], Density-based Clustering [START_REF] Ester | A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[END_REF], and Evidence Accumulation Clustering (EAC) [START_REF] Fred | Combining Multiple Clusterings Using Evidence Accumulation[END_REF] techniques.

The knowledge provided by this clustering algorithm is used to rank the degree of abnormality of all the identified outlying flows, building an outliers ranking. In the third and final step, the top-ranked outlying flows are flagged as anomalies, using a simple thresholding detection approach. As we will show through out the paper, the main contribution provided by UNIDS relies on its ability to detect unknown attacks in a completely unsupervised fashion.

The remainder of the paper is organized as follows. Section 2 presents a brief state of the art in the supervised and unsupervised attacks detection field, describing our main contributions. Section 3 describes the multiresolution traffic aggregation and change-detection procedures used in the first step of the UNIDS system. Section 3 describes the core of UNIDS, presenting an in depth description of the different clustering techniques used to construct the outliers ranking. Section 6 presents the validation of our U-NIDS in real traffic traces obtained from two different networking datasets: the public MAWI traffic repository of the WIDE project [START_REF] Cho | Traffic Data Repository at the WIDE Project[END_REF], and the METROSEC project dataset [START_REF]METROlogy for SECurity and QoS[END_REF]. In this section we also compare the performance of UNIDS against previous proposals for unsupervised detection of attacks available in the literature. Section 7 evaluates the ability of this system to detect unknown attacks in the well-known KDD99 network attacks dataset, comparing its performance with that obtained by an extensively investigated misuse NIDS based on decision trees. Finally, section 10 concludes the paper.

Related Work & Contributions

The problem of network attacks and intrusions detection has been extensively studied in the last decade. Most NIDS are based on misuse-detection techniques, being Bro [START_REF]Bro Intrusion Detection System[END_REF] and SNORT [START_REF]SNORT: an Open Source Network Intrusion Prevention and Detection System[END_REF] the two most celebrated open-source systems in the literature. Most of the different techniques used in the NIDS field are summarized in [START_REF] Kemmerer | Intrusion Detection: A Brief History and Overview[END_REF][START_REF] Sperotto | An Overview of IP Flow-Based Intrusion Detection[END_REF]. A particularly studied approach in recent years for misuse-detection that we shall use in the paper consists in the use of decision trees [START_REF] Kruegel | Using Decision Trees to Improve Signature-Based Intrusion Detection[END_REF][START_REF] Lee | Effective Value of Decision Tree with KDD99 Intrusion Detection Datasets for IDS[END_REF]. Decision trees are one of the most powerful and simple data mining methods for decision-making; a decision tree uses a tree-like graph consisting of branch nodes that represent a choice among different alternatives, and leaves representing a class for the evaluated data (i.e. attack or normal traffic).

The problem of network anomaly detection has been extensively studied during the last decade. Most approaches analyze statistical variations of traffic volume descriptors (e.g., no. of packets, bytes, or new flows) and/or particular traffic features (e.g., distribution of IP addresses and ports), using either single link measurements or network wide data. A non-exhaustive list of standard methods includes the use of signal processing techniques (e.g., ARIMA modeling, wavelets-based filtering) on single-link traffic measurements [START_REF] Barford | A Signal Analysis of Network Traffic Anomalies[END_REF], Kalman filters [START_REF] Soule | Combining Filtering and Statistical Methods for Anomaly Detection[END_REF] for networkwide anomaly detection, and Sketches applied to IP-flows [START_REF] Krishnamurthy | Sketchbased Change Detection: Methods, Evaluation, and Applications[END_REF][START_REF] Dewaele | Extracting Hidden Anomalies using Sketch and non Gaussian Multiresolution Statistical Detection Procedures[END_REF].

Our approach falls within the unsupervised anomaly detection domain. The vast majority of the unsupervised detection schemes proposed in the literature are based on clustering and outliers detection, being [START_REF] Portnoy | Intrusion Detection with Unlabeled Data Using Clustering[END_REF][START_REF] Eskin | A Geometric Framework for Unsupervised Anomaly Detection: Detecting Intrusions in Unlabeled Data[END_REF][START_REF] Leung | Unsupervised Anomaly Detection in Network Intrusion Detection Using Clustering[END_REF] some relevant examples. In [START_REF] Portnoy | Intrusion Detection with Unlabeled Data Using Clustering[END_REF], authors use a single-linkage hierarchical clustering method to cluster data from the KDD99 data-set, based on the standard Euclidean distance for inter-patterns similarity. Reference [START_REF] Eskin | A Geometric Framework for Unsupervised Anomaly Detection: Detecting Intrusions in Unlabeled Data[END_REF] reports improved results in the same data-set, using three different clustering algorithms: Fixed-Width clustering, an optimized version of k-NN, and one class SVM. Reference [START_REF] Leung | Unsupervised Anomaly Detection in Network Intrusion Detection Using Clustering[END_REF] presents a combined density-grid-based clustering algorithm to improve computational complexity, obtaining similar detection results. PCA and the sub-space approach is another well-known unsupervised anomaly detection technique, used in [START_REF] Lakhina | Diagnosing Network-Wide Traffic Anomalies[END_REF][START_REF] Lakhina | Mining Anomalies Using Traffic Feature Distributions[END_REF] to detect network-wide traffic anomalies in highly aggregated traffic flows, and more recently in [START_REF] Brauckhoff | Applying PCA for Traffic Anomaly Detection: Problems and Solutions[END_REF] for anomaly detection in single-router traffic metrics.

UNADA presents several advantages with respect to current state of the art. First and most important, it works in a completely unsupervised fashion, which means that it can be directly plugged-in to any monitoring system and start to work from scratch, without any kind of calibration and/or training step. Secondly, it uses a robust density-based clustering technique to avoid general clustering problems such as sensitivity to initialization, specification of number of clusters, detection of particular cluster shapes, or structure-masking by irrelevant features. Thirdly, it performs clustering in very low dimensional spaces, avoiding sparsity problems when working with high-dimensional data [START_REF] Jain | Data Clustering: 50 Years Beyond K-Means[END_REF]. Finally, we show that UNADA clearly outperforms previously proposed methods for unsupervised anomaly detection in real network traffic.

Multi-resolution Flow Aggregation & Change-Detection

UNADA performs unsupervised anomaly detection on single-link packet-level traffic, captured in consecutive time slots of fixed length ∆T and aggregated in IP flows (standard 5-tuples). IP flows are additionally aggregated at different flow-resolution levels, using 9 different aggregation keys l i . These include (from coarser to finer-grained resolution): traffic per Time Slot (l 1 :tpTS), source Network Prefixes (l 2,3,4 : IPsrc/8, /16, /24), destination Network Prefixes (l 5,6,7 : IPdst/8, /16, /24), source IPs (l 8 : IPsrc), and destination IPs (l 9 : IPdst). The 7 coarsestgrained resolutions are used for change-detection, while the remaining 2 are exclusively used in the clustering step.

To detect an anomalous time slot, time-series Z li t are constructed for simple traffic metrics such as number of bytes, packets, and IP flows per time slot, using aggregation keys i = 1, . . . , 7. Any generic change-detection algorithm F (.) based on time-series analysis is then applied to Z li t . At each new time slot, F (.) analyses the different time-series associated with each aggregation key, going from coarser (l 1 ) to finer resolution (l 7 ). Time slot t 0 is flagged as anomalous if F (Z li t0 ) triggers an alarm for any of the traffic metrics at any of the 7 aggregation levels. Tracking anomalies at multiple aggregation levels provides additional reliability to the change-detection algorithm, and permits to detect both single source-destination and distributed anomalies of very different intensities.

Figure 2 shows how a low intensity DDoS attack might be dwarfed by highly-aggregated traffic. The time-series associated with the number of packets, namely Z t = #pkts t , does not present a perceptible change ∆(#pkts t ) at tpTS aggregation (left); however, the attack can be easily detected using a finer-grained resolution, e.g., at the victim's network (IPdst/24 aggregation, on the right).

Unsupervised Anomaly Detection through Clustering

The unsupervised anomaly detection step takes as input all the IP flows in the flagged time slot. At this step UNADA ranks the degree of abnormality of each flow, using clustering and outliers analysis techniques. For doing so, IP flows are analyzed at two different resolutions, using either IPsrc or IPdst aggregation key. Traffic anomalies can be roughly grouped in two different classes, depending on their spatial structure and number of impacted IP flows: 1-to-N anomalies and N-to-1 anomalies. 1-to-N anomalies involve many IP flows from the same source towards different destinations; examples include network scans and spreading worms/virus. On the other hand, Nto-1 anomalies involve IP flows from different sources towards a single destination; examples include DDoS attacks and flash-crowds. 1-to-1 anomalies are a particular case of these classes, while N-to-N anomalies can be treated as multiple N-to-1 or 1-to-N instances. Using IPsrc key permits to highlight 1-to-N anomalies, while N-to-1 anomalies are more easily detected with IPdst key. The choice of both keys for clustering analysis ensures that even highly distributed anomalies, which may possibly involve a large number of IP flows, can be represented as outliers. Without loss of generality, let Y = {y 1 , . . . , y n } be the set of n aggregated-flows (at IPsrc or IPdst) in the flagged slot. Each flow y i ∈ Y is described by a set of m traffic attributes or features, like num. of sources, destination ports, or packet rate. Let x i ∈ R m be the vector of traffic features describing flow y i , and X = {x 1 , . . . , x n } ∈ R n×m the complete matrix of features, referred to as the feature space.

UNADA is based on clustering techniques applied to X. The objective of clustering is to partition a set of unlabeled samples into homogeneous groups of similar characteristics or clusters, based on some measure of similarity. Samples that do not belong to any of these clusters are classified as outliers. Our particular goal is to identify those outliers that are remarkably different from the rest of the samples, additionally ranking how much different these are. The most appropriate approach to find outliers is, ironically, to properly identify clusters. After all, an outlier is a sample that does not belong to any cluster. Unfortunately, even if hundreds of clustering algorithms exist [START_REF] Jain | Data Clustering: 50 Years Beyond K-Means[END_REF], it is very difficult to find a single one that can handle all types of cluster shapes and sizes. Different clustering algorithms produce different partitions of data, and even the same clustering algorithm provides different results when using different initializations and/or different algorithm parameters. This is in fact one of the major drawbacks in current cluster analysis techniques: the lack of robustness.

To avoid such a limitation, we have developed a divide & conquer clustering approach, using the notions of clustering ensemble and multiple clusterings combination. The idea is novel and appealing: why not taking advantage of the information provided by multiple partitions of X to improve clustering robustness and identification of outliers? A clustering ensemble P consists of a set of multiple partitions P i produced for the same data. Each partition provides an independent evidence of data structure, which can be combined to construct a new measure of similarity that better reflects natural groupings and outliers. There are different ways to produce a clustering ensemble. We use Sub-Space Clustering (SSC) [START_REF] Parsons | Subspace Clustering for High Dimensional Data: a Review[END_REF] to produce multiple data partitions, doing Density-based clustering in N different sub-spaces X i of the original space (see figure ??).

Clustering Ensemble and Sub-Space Clustering

Each of the N sub-spaces X i ⊂ X is obtained by selecting k features from the complete set of m attributes. To deeply explore the complete feature space, the number of sub-spaces N that are analyzed corresponds to the number of k-combinations-obtained-from-m. Each partition P i is obtained by applying DBSCAN [START_REF] Ester | A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[END_REF] to sub-space X i .

DBSCAN is a powerful clustering algorithm that discovers clusters of arbitrary shapes and sizes [START_REF] Jain | Data Clustering: 50 Years Beyond K-Means[END_REF], relying on a density-based notion of clusters: clusters are high-density regions of the space, separated by low-density areas. This algorithm perfectly fits our unsupervised traffic analysis, because it is not necessary to specify a-priori difficult to set parameters such as the number of clusters to identify. Results provided by applying DBSCAN to sub-space X i are twofold: a set of p(i)

clusters {C i 1 , C i 2 , .., C i p(i) } and a set of q(i) outliers {o i 1 , o i 2 , .., o i q(i) }.
To set the number of dimensions k of each sub-space, we take a very useful property of monotonicity in clustering sets, known as the downward closure property: if a collection of elements is a cluster in a k-dimensional space, then it is also part of a cluster in any (k -1) projections of this space. This directly implies that, if there exists any interesting evidence of density in X, it will certainly be present in its lowestdimensional sub-spaces. Using small values for k provides several advantages: firstly, doing clustering in lowdimensional spaces is more efficient and faster than clustering in bigger dimensions. Secondly, density-based clustering algorithms such as DBSCAN provide better results in low-dimensional spaces [START_REF] Jain | Data Clustering: 50 Years Beyond K-Means[END_REF], because high-dimensional spaces are usually sparse, making it difficult to distinguish between high and low density regions. Finally, clustering multiple low-dimensional sub-spaces provides a finergrained analysis, which improves the ability of UNADA to detect anomalies of very different characteristics. We shall therefore use k = 2 for SSC, which gives N = m(m -1)/2 partitions.

Ranking Outliers using Evidence Accumulation

Having produced the N partitions, the question now is how to use the information provided by the multiple clusters and outliers identified by density-based clustering to detect traffic anomalies. A possible answer is provided in [START_REF] Fred | Combining Multiple Clusterings Using Evidence Accumulation[END_REF], where authors introduced the idea of Evidence Accumulation Clustering (EAC). EAC uses the clustering results of multiple partitions P i to produce a new intersamples similarity measure that better reflects their natural groupings.

UNADA implements a particular algorithm for Evidence Accumulation, called Evidence Accumulation for Ranking Outliers (EA4RO): instead of producing a similarity measure between the n different aggregated flows described in X, EA4RO constructs a dissimilarity vector D ∈ R n in which it accumulates the distance between the different outliers o i j found in each sub-space i = 1, .., N and the centroid of the corresponding sub-space-biggestcluster C i Set density neighborhood δ i for DBSCAN 6:

P i = DBSCAN (X i , δ i , n min ) 7:
Update D(j), ∀ outlier o i j ∈ P i :

8: the minimum number of flows that can be classified as a cluster, while δ i indicates the maximum neighborhood distance of a sample to identify dense regions. n min is set at the initialization of the algorithm, simply as a fraction α of the total number of flows n to analyze (we take α = 5% of n). δ i is set as a fraction of the average distance between flows in sub-space X i (we take a fraction 1/10), which is estimated from 10% of the flows, randomly selected. This permits to fast-up computations. The weighting factor w i is used as an outlier-boosting parameter, as it gives more relevance to those outliers that are "less probable": w i takes bigger values when the size n max i of cluster C i max is closer to the total number of flows n. Finally, instead of using a simple Euclidean distance as a measure of dissimilarity, we compute the Mahalanobis distance d M between outliers and the centroid of the biggest cluster. The Mahalanobis distance takes into account the correlation between samples, dividing the standard Euclidean distance by the variance of the samples. This permits to boost the degree of abnormality of an outlier when the variance of the samples is smaller.

w i ← n (n -n max i ) + 9: D(j) ← D(j) + d M (o i j , C i max )
In the last part of EA4RO, flows are ranked according to the dissimilarity obtained in D, and the anomaly detection threshold T h is set. The computation of T h is simply achieved by finding the value for which the slope of the sorted dissimilarity values in D rank presents a major change. In the evaluation section we explain how to perform this computation with an example of real traffic analysis. Anomaly detection is finally done as a binary thresholding operation on D: if D(i) > T h , UNADA flags an anomaly in flow y i .

Experimental Evaluation of UNADA

We evaluate the ability of UNADA to detect different attacks in real traffic traces from the public MAWI repository of the WIDE project [START_REF] Cho | Traffic Data Repository at the WIDE Project[END_REF]. The WIDE operational network provides interconnection between different research institutions in Japan, as well as connection to different commercial ISPs and universities in the U.S.. The traffic repository consists of 15 minutes-long raw packet traces daily collected for the last ten years. The traces we shall work with consist of traffic from one of the transpacific links between Japan and the U.S.. MAWI traces are not labeled, but some previous work on anomaly detection has been done on them [START_REF] Dewaele | Extracting Hidden Anomalies using Sketch and non Gaussian Multiresolution Statistical Detection Procedures[END_REF][START_REF] Fernandes | Automated Classification of Network Traffic Anomalies[END_REF]. In particular, [START_REF] Fernandes | Automated Classification of Network Traffic Anomalies[END_REF] detects network attacks using a signature-based approach, while [START_REF] Dewaele | Extracting Hidden Anomalies using Sketch and non Gaussian Multiresolution Statistical Detection Procedures[END_REF] detects both attacks and anomalous flows using non-Gaussian modeling. We shall therefore refer to the combination of results obtained in both works as our ground truth for MAWI traffic. We shall also test the true positive and false positive rates obtained with UNADA in the detection of flooding attacks in traffic traces from the METROSEC project [START_REF]METROlogy for SECurity and QoS[END_REF]. These traces consist of real traffic collected on the French RENATER network, containing simulated attacks performed with well-known DDoS attack tools. Traces were collected between 2004 and 2006, and contain DDoS attacks that range from very low intensity (i.e., less than 4% of the overall traffic volume) to massive attacks (i.e., more than 80% of the overall traffic volume). In addition, we compare the performance of UNADA against some previous methods for unsupervised anomaly detection presented in section 2.

Features Selection for Detection of Attacks

The selection of the m features used in X to describe the aggregated flows in Y is a key issue to any anomaly detection algorithm, but it becomes critical and challenging in the case of unsupervised detection, because there is no additional information to select the most relevant set. In general terms, using different traffic features permits to detect different types of anomalies. In this paper we shall limit our study to detect well-known attacks, using a set of standard traffic features widely used in the literature. However, the reader should note that UNADA can be extended to detect other types of anomalies, considering different sets of traffic features. In fact, more features can be added to any standard list to improve detection results. For example, we could use the set of traffic features generally used in the traffic classification domain [START_REF] Williams | A Preliminary Performance Comparison of Five Machine Learning Algorithms for Practical IP Traffic Flow Classification[END_REF] for our problem of anomaly detection, as this set is generally broader; if these features are good enough to classify different traffic applications, they should be useful to perform anomaly detection. The main advantage of UNADA is that we have devised an algorithm to highlight outliers respect to any set of features, and this is why we claim that our algorithm is highly applicable.

In this paper we shall use the following list of m = 9 traffic features: number of source/destination IP addresses and ports (nSrcs, nDsts, nSrcPorts, nDstPorts), ratio of number of sources to number of destinations, packet rate (nPkts/sec), fraction of ICMP packets (nICMP/nPkts) and SYN packets (nSYN/nPkts), and average packet size (avgPktsSize). According to previous work on signaturebased anomaly characterization [START_REF] Fernandes | Automated Classification of Network Traffic Anomalies[END_REF], such simple traffic descriptors permit to describe standard network attacks such as DoS, DDoS, scans, and spreading worms/virus.

Table 1 describes the impacts of different types of attacks on the selected traffic features. All the thresholds used in the description are introduced to better explain the evidence of an attack in some of these features. DoS/DDoS attacks are characterized by many small packets sent from one or more source IPs towards a single destination IP. These attacks generally use particular packets such as TCP SYN or ICMP echo-reply. echo-request, or host unreachable packets. Port and network scans involve small packets from one source IP to several ports in one or more destination IPs, and are usually performed with SYN packets. Spreading worms differ from network scans in that they are directed towards a small specific group of ports for which there is a known vulnerability to exploit (e.g. Blaster on TCP port 135, Slammer on UDP port 1434, Sasser on TCP port 455), and they generally use slightly bigger packets. Some of these attacks can use other types of traffic, such as FIN, PUSH, URG TCP packets or small UDP datagrams.

Detecting Attacks in MAWI traffic

We begin by analyzing the performance of UNADA to detect network attacks and other types of anomalies in one of the traces previously analyzed in [START_REF] Dewaele | Extracting Hidden Anomalies using Sketch and non Gaussian Multiresolution Statistical Detection Procedures[END_REF]. IP flows are aggregated with IPsrc key. Figure 4.(a) shows the ordered dissimilarity values in D obtained by the EA4RO method, along with their corresponding manual classification. The first two most dissimilar flows correspond to a highly distributed SYN network scan (more than 500 destination hosts) and an ICMP spoofed flooding attack directed to a small number of victims (ICMP redirect traffic towards port 0). The following two flows correspond to unusual large rates of DNS traffic and HTTP requests; from there on, flows correspond to normal-operation traffic. The ICMP flooding attack and the two unusual flows are also detected in [START_REF] Dewaele | Extracting Hidden Anomalies using Sketch and non Gaussian Multiresolution Statistical Detection Procedures[END_REF]; the SYN scan was missed by their method, but it was correctly detected with accurate signatures [START_REF] Fernandes | Automated Classification of Network Traffic Anomalies[END_REF]. Setting the detection threshold according to the previously discussed approach results in T h1 . Indeed, if we focus on the shape of the ranked dissimilarity in figure 4.(a), we can clearly appreciate a major change in the slope after the 5th ranked flow. Note however that both attacks can be easily detected and isolated from the anomalous but yet legitimate traffic without false alarms, using for example the threshold T h2 on D. (b,c) depict the corresponding four anomalies in two of the N partitions produced by the EA4RO method. Besides showing typical characteristics of the attacks, such as a large value of nPkts/sec or a value 1 for attributes nICMP/nPkts and nSYN/nPkts respectively, both figures permit to appreciate that the detected attacks do not necessarily represent the largest elephant flows in the time slot. This emphasizes the ability of UNADA to detect attacks of low intensity, even of lower intensity than normal traffic. Port scan 1-to-1 IPsrc nSrcs = nDsts = 1, nDstPorts > β1, avgPktsSize < β2, nSYN/nPkts > β3.

Detecting Attacks with Ground Truth

Network scan 1-to-N IPsrc nSrcs = 1, nDsts > δ1, nDstPorts > δ2, avgPktsSize < δ3, nSYN/nPkts > δ4.

Spreading worms 1-to-N IPsrc nSrcs = 1, nDsts > η1, nDstPorts < η2, avgPktsSize < η3, nSYN/nPkts > η4.

Table 1: Features used by UNADA in the detection of DoS, DDoS, network/port scans, and spreading worms. For each type of attack, we describe its impact on the selected traffic features.

also corresponds to anomalies in MAWI traffic, but using IPdst as key. In this case, there are 9 anomalies, including different kinds of flooding DoS/DDoS attacks. Finally, figure 5.3.(c) corresponds to the detection of 9 DDoS attacks in the METROSEC data-set. From these, 5 correspond to massive attacks (more than 70% of traffic), 1 to a high intensity attack (about 40%), 2 are low intensity attacks (about 10%), and 1 is a very-low intensity attack (about 4%). The detection is performed using traffic aggregated with IPdst key. In the three evaluation scenarios, the ROC plot is obtained by comparing the sorted dissimilarities in D rank to a variable detection threshold. We compare the performance of UNADA against three previous approaches for unsupervised anomaly detection: DBSCAN-based, k-means-based, and PCA-based outliers detection. The first two consist in applying either DB-SCAN or k-means to the complete feature space X, identify the largest cluster C max , and compute the Mahalanobis distance of all the flows lying outside C max to its centroid. The ROC is finally obtained by comparing the sorted distances to a variable detection threshold. These approaches are similar to those used in previous work [START_REF] Portnoy | Intrusion Detection with Unlabeled Data Using Clustering[END_REF][START_REF] Eskin | A Geometric Framework for Unsupervised Anomaly Detection: Detecting Intrusions in Unlabeled Data[END_REF][START_REF] Leung | Unsupervised Anomaly Detection in Network Intrusion Detection Using Clustering[END_REF]. In the PCA-based approach, PCA and the sub-space methods [START_REF] Lakhina | Diagnosing Network-Wide Traffic Anomalies[END_REF][START_REF] Lakhina | Mining Anomalies Using Traffic Feature Distributions[END_REF] are applied to the complete matrix X, and the attacks are detected by comparing the residuals to a variable threshold. Both the k-means and the PCA-based approaches require fine tuning: in k-means, we repeat the clustering for different values of clusters k, and take the average results. In the case of PCA we present the best performance obtained for each evaluation scenario.

Obtained results permit to evidence the great advantage of using the SSC-Density-based algorithm in the clustering step with respect to previous approaches. In particular, all the approaches used in the comparison generally fail to detect all the attacks with a reasonable false alarm rate. Both the DBSCAN-based and the k-means-based algorithms get confused by masking features when analyzing the complete feature space X. The PCA approach shows to be not sensitive enough to discriminate different kinds of attacks of very different intensities, using the same representation for normal-operation traffic.

Experimental Evaluation in KDD99

In this section we evaluate the performance of the U-NIDS to detect network attacks in the well-known and widely used KDD99 network attacks dataset [? ]. In addition, we compare its performance with that obtained by an extensively investigated misuse NIDS based on decision trees, as well as against some other methods for unsupervised detection available in the literature.

The KDD99 dataset contains a wide variety of intrusions simulated in a military network environment. Traffic consists of packets aggregated into connections, being a connection a flow of TCP packets between a source and a destination IP address. Simulated attacks include DoS attacks, unauthorized access from a remote machine -R2L attacks (e.g. password guessing), unauthorized access to super-user privileges -U2R attacks (e.g. buffer overflows), and probing attacks (e.g. port scanning). Each connection or flow is described by a set of m = 41 features (e.g. number of bytes, TCP flags, failed remote-login attemps, etc.) and a label indicating either the name of the attack or if the flow corresponds to normal-operation traffic.

The KDD99 dataset has become widely discredited. This letter is intended to briefly outline the problems that have been cited with the KDD Cup'99 dataset, and discourage its further use. Pero como lo nico que hacemos es comprar uno contra el otro, de ltima no pasa nada. Adems es mas evidencia de que funciona.

In order to compare the performance of the unsupervised system against a decision-tree-based NIDS we take two different data sub-sets, the first used for training issues and the second one for testing. The testing dataset corresponds to instances of different attacks that are not present in the training dataset, which will permit us to evidence the paramount advantage of doing unsupervised detection when new attacks arise. DoS and probing attacks in KDD99 are represented by a large number of flows, in some cases even more flows than those corresponding to normal-operation traffic. While this issue limits the use of the outliers detection technique (i.e. the attack is not an outlier in those cases), we shall see in the following section that real network traffic can be aggregated either at source or destination IP address to dramatically reduce the number of flows that compose a highly distributed and/or large volume attack. In order to avoid this limitation in the already processed flows of KDD99 (which can not be aggregated because we do not have the corresponding IP addresses), we shall select only a small fraction of flows for both DoS and probing attacks in our training and testing datasets. The training dataset has 950 normal flows and 255 attacks, while the testing dataset consists of 950 normal flows and 162 attacks.

Let us first evaluate the detection properties of the EA4RO-based detection algorithm used by the U-NIDS when changing the detection threshold T h . Figure 6 depicts the True Positives Rate as a function of the False Positives Rates (i.e., the ROC curve) for both training and testing datasets. Figure 6.(a) shows the results obtained by applying the U-NIDS to the training dataset, while figure 6.(b) shows the results obtained when analyzing the testing dataset. In both cases we can appreciate that the EA4RO detection algorithm is able to detect a large fraction of attacks (more than 90%) with very low false positive rates (less than 1% and 3.5% respectively).

Figure 6 additionaly compares the detection performance obtained with EA4RO against three previous approaches for unsupervised anomaly detection proposed in the literature: DBSCAN-based, k-means-based, and PCAbased outliers detection. The first two consist in applying either DBSCAN or the celebrated k-means clustering algorithm [START_REF] Jain | Data Clustering: 50 Years Beyond K-Means[END_REF] to the complete feature space X, identify the largest cluster C max , and compute the Mahalanobis distance of all the flows lying outside C max to its centroid. The ROC is finally obtained by comparing the sorted distances to a variable detection threshold. These approaches are similar to those used in previous work [START_REF] Portnoy | Intrusion Detection with Unlabeled Data Using Clustering[END_REF][START_REF] Eskin | A Geometric Framework for Unsupervised Anomaly Detection: Detecting Intrusions in Unlabeled Data[END_REF][START_REF] Leung | Unsupervised Anomaly Detection in Network Intrusion Detection Using Clustering[END_REF]. In the PCA-based approach, PCA and the sub-space methods [START_REF] Lakhina | Diagnosing Network-Wide Traffic Anomalies[END_REF][START_REF] Lakhina | Mining Anomalies Using Traffic Feature Distributions[END_REF] are applied to the complete matrix X, and the attacks are detected by comparing the residuals to a variable threshold. Both the k-means and the PCA-based approaches require fine tuning: in k-means, we repeat the clustering for different values of clusters k, and take the av- erage results. In the case of PCA we present the best performance obtained for each evaluation scenario. In both cases we can appreciate the outperforming ability of the EA4OR detection algorithm w.r.t. these traditional approaches, which fail to detect as many attacks as EA4OR with a reasonable false alarms rate. Now that we have shown the detection properties of the algorithms used in the U-NIDS, we shall compare its performance with a largely studied misuse-based NIDS built through decision trees. We shall build a different decision tree for each of the four different categories of attacks (DoS, probe, R2L, and U2R), using the training dataset and standard C4.5 decision trees [START_REF] Kruegel | Using Decision Trees to Improve Signature-Based Intrusion Detection[END_REF][START_REF] Lee | Effective Value of Decision Tree with KDD99 Intrusion Detection Datasets for IDS[END_REF]. To train each of the trees for each different category of attacks, we consider that the flows belonging to the rest of the categories of attacks as well as the normal operation flows correspond to the "negative" class (there is no attack of the corresponding category). For example, let us suppose that we want to build a decision tree to detect R2L attacks; in that case, all the flows in the trainig dataset which belong to the R2L category belong to the "positive" class (there is a R2L attack), while the normal-operation flows as well as the DoS, probe, and U2R flows compose the negative class.

We shall compare the ability of the U-NIDS to detect unknown attacks with respect to a traditional misuseddetection NIDS based on decision trees. Decision trees permit to construct comprehensive signatures for network attacks in the form of multiple filtering-rules, using a graph structure. Figure 7 presents the detection accuracy (number of correctly detected attacks) obtained either with the U-NIDS or with the misuse-based NIDS previously described in both the training and testing datasets. Results are individually presented for each of the four categories of attacks. As expected, results obtained by both systems are very similar in the training dataset: for the case of U-NIDS, we have already shown in figure 6 that more than 90% of the attacks can be correctly detected; in the case of the misuse-based NIDS, it is quite obvious that using the system to detect the attacks which has been programmed to alert on shall provide performant results. What it is interesting to appreciate is what happens with both systems when we try to detect unknown attacks. Figure 7.(b) evidences the limitations of misuse-based NIDS to detect unknown attacks, and more importantly, the paramount advantage of using our U-NIDS for detecting new previously unseen attacks. We refer the reader to figures 8, 9, 10, and 11 to appreciate the detection accuracy obtained with both systems for the different attacks on each of the four different categories.

Detecting Attacks in Real Traffic Traces

Let us now evaluate the ability of the U-NIDS to detect different attacks in real traffic traces from the public MAWI repository of the WIDE project [START_REF] Cho | Traffic Data Repository at the WIDE Project[END_REF]. The WIDE operational network provides interconnection between different research institutions in Japan, as well as connection to different commercial ISPs and universities in the U.S.. The traffic repository consists of raw packet traces daily collected for the last ten years. The traces we shall work with consist of traffic from one of the trans-pacific links between Japan and the U.S.. MAWI traces are not labeled, but some previous work on anomaly detection has been done on them [START_REF] Dewaele | Extracting Hidden Anomalies using Sketch and non Gaussian Multiresolution Statistical Detection Procedures[END_REF][START_REF] Fernandes | Automated Classification of Network Traffic Anomalies[END_REF]. In particular, [START_REF] Fernandes | Automated Classification of Network Traffic Anomalies[END_REF] detects network attacks using a signature-based approach, while [START_REF] Dewaele | Extracting Hidden Anomalies using Sketch and non Gaussian Multiresolution Statistical Detection Procedures[END_REF] detects both attacks and anomalous flows using non-Gaussian modeling. We shall therefore refer to the combination of results obtained in both works as our ground truth for MAWI traffic. We shall also test the true positive and false positive rates obtained in the detection of flooding attacks in traffic traces from the METROSEC project [START_REF]METROlogy for SECurity and QoS[END_REF]. These traces consist of real traffic collected on the French RE-NATER network, containing simulated attacks performed with well-known DDoS attack tools. Traces were collected between 2004 and 2006, and contain DDoS attacks that range from very low intensity (i.e., less than 4% of the overall traffic volume) to massive attacks (i.e., more than 80% of the overall traffic volume). In addition, we compare the performance of the U-NIDS against the same unsupervised detection approaches presented in previous section.

In the following evaluations, we aggregate traffic either at source or destination IP address to show that the hypothesis of having a reduced number of flows as attacking flows is valid even in the case of distributed attacks. For example, if we define a flow as all the packets that are directed towards a single destination IP address, then this flow will be an outlier in the case of a DDoS, in which many different attackers send traffic to the same victim. As traffic features, we shall use in these evaluations basic traffic descriptors such as number of sources and destinations, number of source and destination ports, packet rate, fraction of SYN and ICMP packets, etc.

Figure 12 depicts the ROC curves obtained in the detection of different attacks in MAWI and METROSEC. Figure 12.(a) corresponds to the detection of 36 anomalies in MAWI traffic, using packets aggregated at source IP address. These anomalies include network and port scans, worm scanning activities (Sasser and Dabber variants), and some anomalous flows consisting on very high volumes of NNTP traffic. Figure 12.(b) corresponds to the detection of 9 DDoS attacks in the METROSEC dataset, using packets aggregated at destination IP address. From these, 5 correspond to massive attacks (more than 70% of traffic), 1 to a high intensity attack (about 40%), 2 are low intensity attacks (about 10%), and 1 is a very-low intensity attack (about 4%).

As before, obtained results permit to evidence the great advantage of using the EA4RO algorithm in the clustering step with respect to previously proposed approaches.

In particular, all the approaches used in the comparison generally fail to detect all the attacks with a reasonable false alarm rate. Both the DBSCAN-based and the kmeans-based algorithms get confused by masking features when analyzing the complete feature space X. The PCA approach shows to be not sensitive enough to discriminate different kinds of attacks of very different intensities, using the same representation for normal-operation traffic.

Implementation Issues

The SSC-EA-based algorithm performs clustering in N = m(m -1)/2 low-dimensional sub-spaces X i ∈ R 2 . As we have shown, this provides a high discrimination power to detect and characterize different types of network attacks. However, the multiple clusterings computation increases the total Computational Time (CT) of the algorithm, imposing scalability issues for on-line detection of network attacks in very-high-speed networks. Scalability should be addressed regarding both the number of features used to describe traffic flows (m) and the number of flows to analyze (n). In the real traffic evaluations that we have presented, the number of flows captured in a time slot of ∆T = 20 seconds rounds n = 2500 flows. For the m = 9 features that we have used, the total number of clusterings to compute is N = 36, which takes about 14.4 seconds in a standard single-processor machine.

Two key features of the SSC-EA-based algorithm can be exploited to reduce scalability problems in m and n. Firstly, clustering is performed in low-dimensional subspaces (R 2 ), independently of the number of features that are used. Clustering in low-dimensional feature spaces is faster than in high-dimensional spaces [START_REF] Jain | Data Clustering: 50 Years Beyond K-Means[END_REF], which partially alleviates the overhead of multiple clusterings computation. Secondly, the clustering of each sub-space X i can be performed independently of the analysis on the other sub-spaces, which is perfectly adapted for parallel computing architectures. Parallel computing has become the dominant paradigm for accelerating specific tasks and represents a booming domain, driven by the availability of strong computational-power entities at low costs. Parallelization can be achieved in different ways: using a single multi-processor and multi-core machine, using GPU (Graphic Processor Unit) capabilities, using network processor cards, using a distributed group of machines, or combining these techniques. We shall use the term "slice" as a reference to a single computational entity.

Modern network processor cards are able to perform traffic monitoring even in 10 Gbps network connections. In a average-loaded 10 Gbps link (about 50%-60%) there are about 500.000 packets per second; if we consider traffic flows with an average rate of 500 kbps (about 50 pkts/sec) and a average duration of at least 20 seconds, then we have about n = 10.000 flows to analyze in each time slot of ∆T = 20 seconds. From our experimentations, we know that we can analyze this number of flows using as much as m = 20 traffic descriptors in less than 20 seconds, using a parallel architecture with about 100 slices. Current network processor cards vendors offer multi-core solutions for high-performance networking with as much as 64 general purpose cores [? ], which are perfectly adapted to deploy our unsupervised detection algorithm for very high speed knowledge-independent traffic monitoring.

Computational Time and Parallelization

The last issue that we analyze is the Computational Time (CT) of the algorithm. The SSC-EA-based algorithm performs multiple clusterings in N (m) low-dimensional sub-spaces X i ⊂ X. This multiple computation imposes scalability issues for on-line detection of attacks in veryhigh-speed networks. Two key features of the algorithm are exploited to reduce scalability problems in number of features m and the number of aggregated flows n to analyze. Firstly, clustering is performed in very-low-dimensional sub-spaces, X i ∈ R 2 , which is faster than clustering in high-dimensional spaces [START_REF] Jain | Data Clustering: 50 Years Beyond K-Means[END_REF]. Secondly, each sub-space can be clustered independently of the other sub-spaces, which is perfectly adapted for parallel computing architectures. Parallelization can be achieved in different ways: using a single multi-processor and multi-core machine, using network processor cards and/or GPU (Graphic Processor Unit) capabilities, using a distributed group of machines, or combining these techniques. We shall use the term "slice" as a reference to a single computational entity.

Figure 13 depicts the CT of the SSC-EA-based algorithm, both (a) as a function of the number of features m used to describe traffic flows and (b) as a function of the number of flows n to analyze. Figure 13.(a) compares the CT obtained when clustering the complete feature space X, referred to as CT(X), against the CT obtained with SSC, varying m from 2 to 29 features. We analyze a large number of aggregated flows, n = 10 4 , and use two different number of slices, M = 40 and M = 100. The analysis is done with traffic from the WIDE network, combining different traces to attain the desired number of flows. To estimate the CT of SSC for a given value of m and M , we proceed as follows: first, we separately cluster each of the N = m(m-1)/2 sub-spaces X i , and take the worst-case of the obtained clustering time as a representative measure of the CT in a single sub-space, i.e., CT(X SSCwc ) = max i CT(X i ). Then, if N M , we have enough slices to completely parallelize the SSC algorithm, and the total CT corresponds to the worst-case, CT(X SSCwc ). On the contrary, if N > M , some slices have to cluster various subspaces, one after the other, and the total CT becomes (N %M + 1) times the worst-case CT(X SSCwc ), where % represents integer division. The first interesting observation from figure 13.(a) regards the increase of CT(X) when m increases, going from about 8 seconds for m = 2 to more than 200 seconds for m = 29. As we said before, clustering in low-dimensional spaces is faster, which reduces the overhead of multiple clusterings computation. The second paramount observation is about parallelization: if the algorithm is implemented in a parallel computing architecture, it can be used to analyze large volumes of traffic using many traffic descriptors in an on-line basis; for example, if we use 20 traffic features and a parallel architecture with 100 slices, we can analyze 10000 aggregated flows in less than 20 seconds. Figure 13.(b) compares CT(X) against CT(X SSCwc ) for an increasing number of flows n to analyze, using m = 20 traffic features and M = N = 190 slices (i.e., a completely parallelized implementation of the SSC-EA-based algorithm). As before, we can appreciate the difference in CT when clustering the complete feature space vs. using low-dimensional sub-spaces: the difference is more than one order of magnitude, independently of the number of flows to analyze. Regarding the volume of traffic that can be analyzed with this 100% parallel configuration, the SSC-EA-based algorithm can analyze up to 50000 flows with a reasonable CT, about 4 minutes in this experience. In the presented evaluations, the number of aggregated flows in a time slot of ∆T = 20 seconds rounds the 2500 flows, which represents a value of CT(X SSCwc ) ≈ 0.4 seconds. For the m = 9 features that we have used (N = 36), and even without doing parallelization, the total CT is N × CT(X SSCwc ) ≈ 14.4 seconds.

Conclusions

The Unsupervised Network Anomaly Detection Algorithm that we have proposed presents many interesting advantages with respect to previous proposals in the field of unsupervised anomaly detection. It uses exclusively unlabeled data to detect traffic anomalies, without assuming any particular model or any canonical data distribution, and without using signatures of anomalies or training. Despite using ordinary clustering techniques to identify traffic anomalies, UNADA avoids the lack of robustness of general clustering approaches, by combining the notions of Sub-Space Clustering, Density-based Clustering, and multiple Evidence Accumulation. We have verified the effectiveness of UNADA to detect real single source-destination and distributed network attacks in real traffic traces from different networks, all in a completely blind fashion, without assuming any particular traffic model, clustering parameters, or even clusters structure beyond a basic definition of what an anomaly is. Additionally, we have shown detection results that outperform traditional approaches for outliers detection, providing a stronger evidence of the accuracy of UNADA to detect network anomalies.

  Two different approaches are by far dominant in the research literature and commercial IDS security devices: signatures-based or misuse detection (detect what I know ) and anomaly detection (detect what it is different from what I know ).

Figure 1 :

 1 Figure 1: High-level description of the Unsupervised Network Intrusion Detection System (UNIDS).

Figure 2 :

 2 Figure 2: Low-intensity anomalies might be hidden inside highly aggregated traffic, but are visible at finer-grained aggregations. The DDoS attack is evident at the victim's network.

2 : 3 :

 23 max . The idea is to clearly highlight those flows that are far from the normal-operation traffic at each of the different sub-spaces, statistically represented by C i max . Algorithm 1 presents a pseudo-code for EA4RO. The different parameters used by EA4RO are automatically set by the algorithm itself. The first two parameters are used by the density-based clustering algorithm: n min specifies Algorithm 1 Evidence Accumulation for Ranking Outliers (EA4RO) 1: Initialization: Set dissimilarity vector D to a null n × 1 vector Set smallest cluster-size n min = α . n 4: for i = 1 : N do 5:

  w i 10: end for 11: Rank flows: D rank = sort(D) 12: Set anomaly detection threshold: T h = find-slopebreak(D rank )

Figure 3 :

 3 Figure 3: Evidence Accumulation for Ranking Outliers.

2 threshold T h 1 (

 21 rate of HTTP requests Very-high rate of DNS traffic threshold T h a) Unsupervised detection of network attacks and elephant flows.

Figure 4 :

 4 Figure 4: Detection and analysis of network attacks in WIDE.

Figures 4 .

 4

Figure 5 .

 5 3 depicts the True Positives Rate (TPR) as a function of the False Positives Rates (FTR) in the detection of different attacks in MAWI and METROSEC. Figure 5.3.(a) corresponds to the detection of 36 anomalies in MAWI traffic, using IPsrc as key. These anomalies include network and port scans, worm scanning activities (Sasser and Dabber variants), and some anomalous flows consisting on very high volumes of NNTP traffic.

  Figure 5.3.(b)

Figure 5 :

 5 Figure 5: True Positives Rate vs False Alarms in MAWI and METROSEC.

Figure 6 :

 6 Figure 6: True Positives Rate vs False Alarms in KDD99.

Figure 7 :Figure 8 :

 78 Figure 7: U-NIDS vs Misuse-based NIDS in KDD99.

Figure 9 :Figure 10 :

 910 Figure 9: U-NIDS vs Misuse-based NIDS -DoS attacks.

Figure 11 :

 11 Figure 11: U-NIDS vs Misuse-based NIDS -U2R attacks.

  MAWI, IP source flows. (b) METROSEC, IP dest. flows.

Figure 12 :

 12 Figure 12: True Positives Rate vs False Alarms in MAWI and MET-ROSEC.

  complete Feature Space Distributed Sub-Space Clustering, 190 slices (a) Time vs. n features. (b) Time vs. n patterns.

Figure 13 :

 13 Figure 13: Computational Time as a function of n of features and n of flows to analyze. The number of aggregated flows in (a) is n = 10000. The number of features and slices in (b) is m = 20 and M = 190 respectively.

Acknowledgments

This work has been done in the framework of the European project ECODE, funded by the European Commission under grant FP7-ICT-2007-2/223936.