Table of Contents

List of figures

Acronyms and Definitions

1. Purpose of the Document Deliverable D4.1 describes the preliminary work performed on the design of the online traffic characterization system. It first draws the state of the art of the existing work related with online traffic characterization and anomaly detection, especially focusing on the full range of approaches going from supervised to unsupervised ones. The deliverable also defines the basics of the generic online characterization system and the specificities of the two main topics addressed in WP 4 namely traffic pattern evolution analysis and anomaly detection. It particularly indicates how this architecture takes advantage of the big data infrastructure as developed in WP2. Deliverable 4.1 also indicates the principles of the algorithms for both traffic pattern evolution analysis and anomaly detection. Moreover, it creates the link with use case 1 (Network Anomaly detection) of WP5, indicating how the algorithm evaluation could be performed.

Scope

This document provides the description of the current status of work lead in WP4 on the online traffic classification system. The progress in ONTIC on the online traffic classification system, traffic pattern evolution analysis, and anomaly detection during the second year will be held in Deliverable 4.2, as a continuation of the current deliverable. The third and last year will generate deliverable 4.3 aiming at presenting the results of the intensive evaluation of the algorithms designed for the online classification system and related applications, i.e. pattern evolution subsystem, and anomaly detection.

Intended Audience

The intended audience includes every partner within ONTIC project, especially those involved in WP2, WP3, WP4 and WP5.

Suggested Previous Readings

There are some overview papers that might be interesting to get started in machine learning: § Tom M. Mitchell, "The Discipline of Machine Learning". This is a white paper defining the discipline of Machine Learning. This was a piece of the argument Mitchell used to convince the President of CMU to create a standalone Machine Learning department for a subject that will still be around in 100 years. The paper can be found at the following URL: http://www.cs.cmu.edu/~tom/pubs/MachineLearning.pdf § Pedro Domingos, "A Few Useful Things to Know about Machine Learning". This is a great paper because it pulls back from specific algorithms and motivates a number of important issues such as feature selection generalizability and model simplicity. This is all good stuff to get right and think clearly about from the beginning. The paper can be found at the following URL: http://homes.cs.

Executive Summary

ONTIC aims at proposing a framework composed of techniques that can mostly be qualified as unsupervised (or semi supervised in some cases) for traffic characterization with direct applications that are: a) Able to catch traffic patterns evolution b) Able to detect network anomalies and especially attacks.

This system has to run online with a reactive level close to real-time. It then has to cope with the huge amount of data and their high dimensionality level. In addition, this system consists of several functions (detection and analysis of traffic patterns evolution, anomalies and intrusions detection, automatic defense devices configuration with autonomously generated filtering rules, continuous updating of the system knowledge database, visualization, etc.) that have to run continuously and in parallel: parallelizing and synchronizing the execution of these functions is therefore an essential feature of the system. As the subsystems have to mainly rely on unsupervised techniques (such as clustering), we have investigated a scalable and elastic architecture for online data stream clustering for which more/less processes can be seamlessly added or removed on the fly during computation. A specific architecture for all these functionalities is being designed in order to reach the near real-time reaction objective. It is based on sub-space clustering that allows parallelization of the computing in all subspaces, as they are completely independent. It is then possible with powerful enough parallel machines to theoretically benefit from a maximum speedup. Subspace clustering also limits the dramatic impact on the clustering results of the noise inherent to large and high dimensionality spaces. The noise is being the source of inaccuracy and inefficiency in many existing clustering techniques that limit their capabilities for analyzing large sets of data as traffic flowing in highspeed networks. This point is then at the heart of researches in the domain of clustering algorithms for some time, with more or less valuable results that often depend on kind of data to me mined. The subspace clustering technique is being designed with the objective of overpassing other ones in terms of accuracy, efficiency and speed in all situations as it is natively designed to cope with the huge amount of data flowing in high-speed networks and their related high dimensionality level.

On the other side, when traffic patterns evolution is detected, a supervised subsystem can be of interest working in conjunction with the unsupervised one. After classes of traffic, including possible new ones have been extracted from the traffic, the supervised system can be re-trained for updating the system knowledge database. It could also help the intrusion detection subsystem for improving its efficiency by reducing the analysis domain in each case.

Last, the anomaly detection subsystem aims at autonomously detecting anomalies (including the ones due to attacks), and to autonomously trigger countermeasures. For this purpose we are investigating data mining techniques for autonomously generating anomalies characteristics. In the following months of the ONTIC project we will investigate information theory techniques for giving a score to anomalies abnormality, and depending on the score, generate automatically filtering rules to be deployed on network security devices. The target is to have very fast reaction giving the feeling to administrators and users of a proactive defense system.

6. Related work The simultaneous detection and characterization of traffic anomalies has also received quite a lot of attention in the past, but results are few and present important limitations, either because they rely on some kind of training data and/or anomaly signatures, or because they do not provide meaningful and tractable information to a human network operator, who has to take the final decision about the nature of the detected problem.

Authors in [START_REF] Lakhina | Characterization of network-wide anomalies in traffic flows[END_REF] characterize network-wide anomalies in highly aggregated traffic (Origin-Destination flows or OD flows for short), using PCA and the sub-space approach [START_REF] Lakhina | Diagnosing network-wide traffic anomalies[END_REF]. An important limitation of this approach is that the information obtained from OD flow data is too coarse-grained to provide meaningful information to the network operator. Papers like Lakhina et al. [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF] and Biang et al. [START_REF] Li | Detection and identification of network anomalies using sketch subspaces[END_REF] detect and characterize anomalies using finergrained traffic information, basically applying the same PCA approach to the sample entropy of the empirical distribution of specific traffic features. One clear limitation of these approaches is that the information they provide is not immediately usable and easyto-understand by the network operator, who may not even be familiar with concepts distant from his tasks such as sample entropy. Besides, the PCA approach is highly sensitive to noise when used for anomaly detection [START_REF] Casas | Optimal volume anomaly detection and isolation in large-scale ip networks using coarse-grained measurements[END_REF][9], requiring in practice a fine-tuning and data-dependent calibration step to work.

UNADA (Unsupervised Network Anomaly detection Algorithm) [START_REF] Casas | Unada: Unsupervised network anomaly detection using sub-space outliers ranking[END_REF] falls within the unsupervised anomaly detection domain, a novel research area that has drawn quite a lot of interest in the research community, but that still represents a rather immature field. Most work on unsupervised network anomaly detection has been devoted to the IDS field, generally targeting the detection of network intrusions in the very well-known KDD'99 dataset. The great majority of the detection schemes proposed in the literature are based on clustering techniques and outliers detection, being [START_REF] Eskin | A geometric framework for unsupervised anomaly detection: Detecting intrusions in unlabeled data[END_REF][12] [START_REF] Portnoy | Intrusion detection with unlabeled data using clustering[END_REF] some examples. The objective of clustering is to partition a set of unlabeled patterns into homogeneous groups of "similar'" characteristics, based on some similarity measure. Outliers detection consists in identifying those patterns that do not belong to any of these clusters. In [START_REF] Portnoy | Intrusion detection with unlabeled data using clustering[END_REF], authors use a simple single-linkage hierarchical clustering method to cluster data from the KDD'99 dataset, based on the standard Euclidean distance for inter-pattern similarity. Eskin et al. [START_REF] Eskin | A geometric framework for unsupervised anomaly detection: Detecting intrusions in unlabeled data[END_REF] reports improved results in the same dataset, using three different clustering algorithms: the Fixed-Width clustering algorithm, an optimized version of the K-NN algorithm, and the one-class SVM algorithm. Leung and Leckie [START_REF] Leung | Unsupervised anomaly detection in network intrusion detection using clustering[END_REF] present a combined density-based and grid-based clustering algorithm to improve computational complexity, obtaining similar detection results.

Previous work of some ONTIC partners permits to automatically characterize network traffic anomalies [START_REF] Fernandes | Automated classification of network traffic anomalies[END_REF], but using a-priori well-defined anomaly signatures. Closer to our current work, authors in [START_REF] Silveira | RCA: Pulling anomalies by their root causes[END_REF] present URCA (Unsupervised Root Cause Analysis), a two-steps algorithm to characterize network anomalies in an unsupervised fashion. URCA uses as input the traffic in the anomalous time slots detected by any generic time-slot-based detection algorithm [START_REF] Cormode | What's new: Finding significant differences in network data streams[END_REF]. In the first step, it identifies the anomaly by iteratively removing from the anomalous time slots those flows that seem normal. In the second step, the algorithm uses a hierarchical clustering method to characterize the particular flows identified as anomalous. We identify some serious drawbacks and omissions in URCA: authors claim that the approach is unsupervised, which is not true, as it actually uses previously labeled anomalous events for the characterization. As in previous works, the algorithm uses difficult-to-interpret traffic descriptors for the clustering step (e.g. sample entropy of the distribution of IP addresses, aggregated at different levels), obscuring the comprehension of the network operator. Finally, the algorithm removes those flows that seem normal before the characterization step, which drags possible errors to the clustering step.

The Unsupervised Anomaly Detection and Characterization algorithm [START_REF] Mazel | Sub-space clustering, interclustering results association & anomaly correlation for unsupervised network anomaly detection[END_REF] from some ONTIC partners 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 into any monitoring system and start to work from scratch. Secondly, anomaly detection is performed based not only on outliers detection, but also by identifying small-clusters. This is achieved by using different levels of traffic aggregation, both at the source and destination of the traffic; this additionally permits to discover lowintensity and distributed anomalies. Thirdly, the lack of robustness of general clustering approaches is avoided by combining the notions of Sub-Space Clustering [START_REF] Parsons | Subspace clustering for high dimensional data: a review[END_REF] and multiple Evidence Accumulation [START_REF] Fred | Combining multiple clusterings using evidence accumulation[END_REF]. In particular, this algorithm is immune to general clustering problems like sensitivity to initialization, specification of number of clusters, or structuremasking by irrelevant features. Fourthly, the algorithm performs clustering in lowdimensional feature spaces, using simple traffic descriptors like number of source IP addresses or fraction of SYN packets. This simplifies the characterization of the anomaly, and avoids well-known clustering problems when working with high-dimensional data [START_REF] Jain | Data clustering: 50 years beyond k-means[END_REF]. This algorithm ranks the multiple evidence of an anomaly detected in different sub-spaces, combining the most relevant traffic descriptors into a compact and easy-to-interpret signature that characterizes the problem. This permits to reduce the time spent by the network operator to understand the nature of the anomaly. Finally, this algorithm is designed to work in an on-line fashion, analyzing traffic from consecutive time slots in near real time. This is possible even when working with large number of traffic descriptors, because the sub-space clustering and the evidence accumulation algorithms are perfectly adapted for parallelization (see [START_REF] Mazel | Sub-space clustering, interclustering results association & anomaly correlation for unsupervised network anomaly detection[END_REF]).

Traffic pattern evolution

As stated in the previous section, unsupervised traffic analysis has received a lot of attention during the past decade. In this section, some of the main approaches and recent proposals for the application of these techniques to the problem of pattern evolution detection, analysis and prediction are discussed.

Online Clustering 6.2.1

Clustering is one of the most popular approaches for unsupervised learning. Most classic clustering schemes generally rely on multiple passes over the data to reach convergence. Moreover, they group the data in hyperspheres, and the number of clusters requires to be set a priori by the user. These characteristics have very important drawbacks: (1) Performing multiple passes over big data sets is impractical, and often infeasible, (2) the constantly streaming, pseudo-infinite nature of many data sources nowadays completely rules out the possibility of multiple passes, (3) Gaussianity is necessary for hyperspheric clusters to be accurate and ( 4) prior knowledge about the expected number of clusters is necessary for the algorithm to perform well. In addition, clustering algorithms in an online setting must address the problems of concept drift, concept shift and ageing. There have been numerous attempts to overcome these issues for the applicability of clustering methods to online data streams, which undoubtedly constitutes an active research topic today. Some of the most relevant proposals in this field are presented below.

Micro Clustering

In [START_REF] Aggarwal | A framework for clustering evolving data streams[END_REF], the concept of Micro-Clustering is described, along with the CluStream algorithm. This algorithm builds upon notions previously proposed by Single-Pass k-Means [START_REF] Farnstrom | Scalability for clustering algorithms revisited[END_REF] and BIRCH [START_REF] Zhang | Birch: an efficient data clustering method for very large databases[END_REF].

The system is divided into two components, one online and one offline. The online phase constructs Clustering Features (CF), which represent a small set of data points, taking temporal information into account (CFT). Incoming points are absorbed by a CF if they fall within its maximum boundary. Otherwise, a new CFT is created. A maximum level of clusters is kept, removing old ones in favor of newer ones. CFTs can be stored periodically and aggregated in pyramidal form for offline clustering with different levels of granularity. The notion of Micro-Clustering (i.e. summaries to describe the data more compactly) has been used and developed extensively in posterior streaming clustering techniques.

Partitioning Clustering

Several researchers have proposed variations on the classic k-Means formula to enable the clustering of data streams. Two of the first notable proposals in this area are Scalable k-Means [START_REF] Bradley | Scaling clustering algorithms to large databases[END_REF] and Single-pass k-Means [START_REF] Farnstrom | Scalability for clustering algorithms revisited[END_REF]. In [START_REF] O'callaghan | Streaming-data algorithms for high-quality clustering[END_REF], O'Callaghan et al. propose STREAM, that analyzes arriving chunks (i.e. subsets of the stream that can fit into memory) in search of distinct points, which are then clustered using an algorithm called LOCALSEARCH. More recent works include StreamKM++ [START_REF] Ackermann | Streamkm++: A clustering algorithm for data streams[END_REF]. In this paper, the authors present a streaming version of the k-Means++ algorithm and introduce the concept of coreset tree. Coresets are small sets that yield similar clustering results to those of much larger sets, i.e. they are compact representations that retain features relevant for clustering. According to the experimental results presented, the algorithm is slower than BIRCH [START_REF] Zhang | Birch: an efficient data clustering method for very large databases[END_REF] and Stream [START_REF] Guha | Clustering data streams: Theory and practice[END_REF] but yields better results in terms of squared errors. In [START_REF] Zhou | Tracking clusters in evolving data streams over sliding windows[END_REF] an algorithm for tracking cluster changes over sliding windows, SWCluster, is described. They propose a new data structure, the Exponential Histogram of Cluster Features (EHCF), to keep track of in-cluster evolution. This structure allows for efficient constant updates of the cluster structure, diminishing the influence of outdated records. The method is shown to outperform CluStream when applied to sliding windows and has bounded memory requirements.

The EHCF is a flexible tool that can be used along other solutions.

Grid Clustering

In grid clustering, the d-dimensional input space is divided into cells by a set of (d-1)dimensional hyperplanes. There exist multiple works that apply this type of algorithms to online settings. In [START_REF] Hinneburg | Optimal grid-clustering: Towards breaking the curse of dimensionality in high-dimensional clustering[END_REF], the authors describe methods for finding optimal hyperplanes according to certain criteria: hyperplanes should lie on low-density areas to avoid splitting clusters and they should discriminate clusters as much as possible. Another interesting approach using this notion is Fractal Clustering, that clusters points based on their impact on the fractal dimension of the group. In [START_REF] Chen | Density-based clustering for real-time stream data[END_REF], D-Stream is presented. This algorithm makes a different partition for each dimension of the input space, which yields as many density grids as the product of the number of partitions for each dimension. Incoming points are mapped onto one of these grids and clusters are created offline based on the density of each grid. D-Stream was later extended with D-Stream II [START_REF] Tu | Stream data clustering based on grid density and attraction[END_REF], which alleviates the problem of wrongly created clusters by considering the position of data points to decide whether to merge neighboring dense partitions or not. In [START_REF] Wan | Density-based clustering of data streams at multiple resolutions[END_REF] the authors describe MR-Stream, which according to the authors performs the online computations in constant time, allows for the discovery of clusters at multiple resolutions using a tree-like structure, determines the right time to generate clusters, generates highly pure clusters and determines the right threshold for density-based clustering. The tree built by the algorithm is pruned online. Other proposals include ExCC [START_REF] Bhatnagar | Clustering data streams using grid-based synopsis[END_REF], DUCStream [START_REF] Gao | An incremental data stream clustering algorithm based on dense units detection[END_REF], DD-Stream [START_REF] Jia | A grid and density-based clustering algorithm for processing data stream[END_REF], PKS-Stream [START_REF] Ren | Clustering over data streams based on grid density and index tree[END_REF] and DENGRIS-Stream [START_REF] Amini | Dengris-stream: A density-grid based clustering algorithm for evolving data streams over sliding window[END_REF].

Density-Based Clustering

Several density-based algorithms for streaming data have been proposed in recent literature. Among the most notable ones is DenStream [START_REF] Cao | Density-based clustering over an evolving data stream with noise[END_REF]. This algorithm combines DBSCAN and the concept of micro-clustering on a fading window over a data stream, and bounds storage using a pruning procedure. It succeeds at recognizing arbitrarily shaped clusters. In [START_REF] Ruiz | C-denstream: Using domain knowledge on a data stream[END_REF], C-DenStream is described. This algorithm extends DenStream relying on certain external constraints to guide the clustering process. In particular, they utilize the notions of Must-link and Cannot-link to enforce or prevent particular groupings among the data based on prior knowledge. In [START_REF] Ntoutsi | Density-based projected clustering over high dimensional data streams[END_REF], the authors propose HDDStream, with which they try to solve the problem of high-dimensional stream clustering, which can be challenging due to the presence of irrelevant features and the locality of relevance. It improves older partition-based HPStream [START_REF] Aggarwal | A framework for projected clustering of high dimensional data streams[END_REF], which assumes that the number of clusters does not change. It functions by summarizing sets of objects in their relevant dimensions. Finally, Flockstream [START_REF] Forestiero | A single pass algorithm for clustering evolving data streams based on swarm intelligence[END_REF] is a multi-agent flocking model. Its greatest advantage is that it does not need the offline component that other density-based methods utilize for the final clustering. Other proposals include StreamOptics [START_REF] Tasoulis | Visualising the cluster structure of data streams[END_REF], rDenStream [START_REF] Li-Xiong | A three-step clustering algorithm over an evolving data stream[END_REF], SDStream [START_REF] Ren | Density-based data streams clustering over sliding windows[END_REF], HDenStream [START_REF] Lin | A density-based clustering over evolving heterogeneous data stream[END_REF], SOStream [START_REF] Isaksson | Sostream: Self organizing density-based clustering over data stream[END_REF] and PreDeConStream [START_REF] Hassani | Density-based projected clustering of data streams[END_REF].

Network Traffic Prediction 6.2.2

In order to harness the complexity of network traffic evolution over time to make predictions it is essential to identify its dynamics, regularities and temporal interdependence. In the recent literature, there exist several proposals that employ machine learning techniques to enhance existing time series analysis and prediction methods or build new ones. Some of the works that have developed these methods in the field of network traffic and similar areas are described below.

Support Vector Regression

Some authors propose to use Support Vector Regression (SVR) as a method for the prediction of various network traffic variables. Support Vector Machines (SVM) are a very successful classification method that pose the problem of finding an optimal hyperplane to separate two sets of data points. It can be used for regression by imposing a maximum distance constraint on the objective function. Although SVMs are a supervised approach, SVR does not need expert intervention, since the 'labels' in this case are the values of the input function. In [START_REF] Mirza | A machine learning approach to tcp throughput prediction[END_REF], the authors use this technique to try to predict TCP throughput using different network metrics such as Available Bandwidth, Queue loss and Packet loss, and find the last two to be the most relevant. They claim to obtain measures within 10% of the actual value 87% of the time, although the data set used was artificially generated on their local network. In [START_REF] Bermolen | Support vector regression for link load prediction[END_REF], another SVR based proposal is described. The authors of this work attempt to predict the link load based on previous records. The data set used is a one-day long capture from a major Italian ISP. They conclude that, even though SVR does not seem to yield significant improvements over ARMA models in terms of accuracy for short-term link load prediction, it presents extremely advantageous qualities such as robustness to parameter variation, low computational complexity and the possibility to extend the forecasting horizon by using cascading SVR models.

Dimensionality Reduction

The application of forecasting techniques can be especially challenging when dealing with highdimensional input data spaces. This problem can be addressed using dimensionality reduction techniques such as Singular Value Decomposition (SVD) and PCA. In [START_REF] Gursun | Describing and forecasting video access patterns[END_REF], SVD is used on YouTube video access data in order to extract patterns and make predictions more efficiently using an ARMA model. To perform predictions, they consider a data matrix comprised of 366 columns, each of which being a year-long time series of daily views for each video considered.

An ARMA model is built for the first principal components of this data matrix (matrix U of decomposition USV). The predicted vectors are then projected back onto the original space by multiplying them by matrices S and V for interpretation. Their results are encouraging, and the approach is sufficiently generic to be directly applied to network traces using certain features of interest, e.g. number of flows in the network, failed flow ratio, etc. In order to cope with rarely accessed videos, the authors use hierarchical clustering to group similar series. Predictions for a video are made mapping that video to a cluster and rescaling its mean time series.

Signal Processing & Neural Networks

Neural Networks have seen a significant resurgence since the potential of deep architectures started to be acknowledged and fast methods for training them were developed after 2006 [34][35]. These models have been applied to the problem of network traffic prediction combined with signal processing techniques. In [START_REF] Alarcon-Aquino | Multiresolution fir neural-network-based learning algorithm applied to network traffic prediction[END_REF], the authors build a multiresolution finite impulse response (FIR) neural network that uses a discrete wavelet transform (DWT) to adequately represent the time series data. The model is tested on the Bellcore Morristown Research and Engineering Center Ethernet traffic traces, and is shown to outperform an RLS predictor and a single resolution FIRNN. The slow convergence of the backpropagation algorithm, however, could hamper its applicability to online environments. In [START_REF] Park | Structure optimization of bilinear recurrent neural networks and its application to ethernet network traffic prediction[END_REF] the authors propose an optimized training procedure for a Bilinear Recurrent Neural Network (BLRNN) [START_REF] Park | Bilinear recurrent neural network[END_REF] and use it to predict the behavior of network traffic. The optimization consists of two parts: first, the multiplications for bilinear components are reduced; then, the network is pruned using a genetic algorithm. The method is also tested on the Bellcore data set. It shows improvements over traditional neural networks, but fails to predict peaks and in terms of accuracy it performs worse than the multiresolution model described in [START_REF] Alarcon-Aquino | Multiresolution fir neural-network-based learning algorithm applied to network traffic prediction[END_REF]. However, its reduced computational cost is very relevant to online implementation.

Online traffic characterization architecture basics 7.1 Generic architecture design principle

This section aims at defining the principles for the generic architecture of the online classification system. We recall that WP4 aims at defining a scalable online network traffic characterization system.

Note also that WP4 architecture design principles take into account that WP5 Use Cases will have to integrate specific mechanisms developed in WP4.

One of the key functions to be designed and developed is related to scalable online flow classification. Based on this function, the two objectives are (1) to design a traffic pattern evolution sub-system, and (2) to design a network anomalies and intrusion detection sub-system (use case #1).

Given the online and scalable nature of the system and sub-systems, the key issues to be addressed are related to:

1. The traffic capture system and the way the capture traffic stream is afterwards sent to the flow classification system. This capture system has to be fast and needs to process data to transform it in the appropriate time series whose format has to be completed in the following months; 2. The computing of this large amount of data of high dimensions by the data-mining and Machine-Learning algorithms. These algorithms have to be able to handle large amounts of data in real time and in a scalable way.

Traffic capture 7.1.1

Figure 1 illustrates what has to be done to transform raw packet traces into aggregated traffic traces to be presented at the different data-mining and machine-learning algorithms that will be designed / used for flow classification, traffic pattern evolution, and anomaly detection. This architecture is aimed at being generic enough for coping with all possible algorithms that could run on top of it. It is especially possible this traffic aggregation task to be run on the capturing machines as they could perform it much faster than the machines running the machine learning and data mining algorithms. It that later case, it could lead to performance and scalability issues. The performance evaluation to be run in the second year of the project should provide the required figures for making the decision. Nevertheless, it will not change the principle of the proposed functional architecture. Given the real-time and scalability objectives for the classification, traffic pattern study, and anomaly detection functions, the related algorithms need to be fast and efficient, in addition of being robust and accurate. The two next sections will detail the specific functional architecture for (1) traffic pattern evolution, and (2) anomaly detection.

Specific architecture details for traffic pattern evolution

In this section, an overview of the architectural foundations for a Traffic Pattern Evolution Subsystem is described. Some of the specific requirements and desirable properties of online algorithms for data streams are described in section 8.1 . All families of machine learning algorithms (classification, clustering, regression/prediction) can be applied to the problem of temporal traffic pattern evolution detection and analysis. However, some common ground for the different techniques that can be employed for this purpose can be established, and an abstract layout of the elements to participate in the traffic pattern evolution subsystem can be extracted.

Traffic Pattern Evolution Subsystem Architecture Description 7.2.1

As every other element of the ONTIC architecture, the Traffic Pattern Evolution Subsystem will process network data. These data must undergo a feature engineering process via a Feature Engineering Subsystem (FES) so that the algorithms involved can receive the data in an adequate representation.

Online streaming algorithms can consume data in various forms. Samples can be processed and immediately discarded one at a time. Alternatively, a sliding window can be maintained. In this case, the algorithm will need to keep the most recent sample (x t ) and the n previous ones (x t-n, …, x t-1 ) in memory in order to be able to utilize a n+1 long window of data.

The Scalable Stream Processing System (Scalable-SPS) consists of the Streaming Algorithm (SA) or set of streaming algorithms to be used (please refer to section 6.2 for details), which will be deployed on top of an Online Distributed Computing Framework such as STORM or SAMZA. The adaptation of existing state-of-the-art techniques to these platform is one of the core goals of this project. Therefore, the Scalable-SPS will be one of the major contributions by ONTIC.

As described in section 6.2 , it is common for streaming machine learning algorithms to be comprised of an online and an offline component. The offline component can provide support for less time-critical tasks that can improve the online performance. For instance, a Support Vector Regression-based prediction system could immensely benefit from separate equipment for periodical retraining. The samples can be temporarily stored in a separate Temporary Storage device. When a temporal or storage threshold is surpassed, a Batch Learner can retrain the algorithm, dismiss the stored samples and transmit the new parameters to the predictor. The Traffic Pattern Evolution Subsystem permanently generates output according to the problem at hand. A classifier determines the traffic class (e.g. application class) a packet, a set of packets, a flow or a set of flows belongs to. A clustering algorithm yields the description of the resulting clusters, which can contain the centroid location, the cluster density, the average cluster age and more. A forecasting system outputs a series of discrete forecasts, whose length depends on the established horizon. These problems pose challenges that fall within the scope of the ONTIC project. These challenges are discussed in section 8.1 .

Specific architecture details for anomaly detection

Most of the solution quoted in the state of the art (section 6.1 ) on anomaly detection (except unsupervised ones) share a common downside: they require the knowledge provided by an external agent to achieve their goal, either in terms of anomaly or attack signatures or as normal-operation profiles. As such, current network security and management look more like a reactive countermeasure than a proactive prevention mechanism. Over the past years we have, however, witnessed an increased interest within the network community in shifting away from reactive management and defense towards more proactive 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 management and 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 (UNADS) capable of detecting network anomalies without relying on signatures, training, or labeled traffic instances of any kind. Based on the observation that network anomalies, and particularly the ones that are the most difficult to detect, are contained in a small fraction of traffic instances with respect to normal-operation 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. UNADS relies on robust clustering techniques to blindly extract the traffic instances that compose an anomaly. This unsupervised system runs in three consecutive steps, analyzing packets captured in contiguous time slots of fixed length. Figure 3: High-level description of the Unsupervised network Anomaly Detection System depicts a modular, high-level description of this system.

The first step consists in preparing the flow/features matrix that will represent the research space for the clustering algorithms. For doing so, captured packets are first aggregated into multiresolution traffic flows. The idea deals with considering the larger possible space including all features for the most possible accurate result. The scalability issue in terms of computing time will be addressed in next steps. Different time-series are then built on top of these flows.

The second step takes as input the full flow matrix. At this step, outlying flows are identified using a robust multi-clustering 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. Based on the knowledge provided by this clustering algorithm, and an analytic formulae applied on network and traffic features (still to be improved), the system ranks the degree of abnormality of all the identified outlying flows, building an outlying flows ranking (see section 8.2 for more information).

In the third step, the top-ranked outlying flows are flagged as anomalies, using a simple threshold detection approach. Based on our first analysis in real case with previously labeled traffic as ground truth, threshold appears to be constant for discriminating between legitimate, erroneous and illegitimate traffic. Further studies will nevertheless been run in the coming months to confirm this first result.

The main contribution of UNADS relies on its ability to detect unknown attacks in a completely unsupervised fashion, avoiding the need of signatures, training, or labeled traffic flows. In addition, previous work [START_REF] Mazel | Sub-space clustering, inter-clustering results association & anomaly correlation for unsupervised network anomaly detection[END_REF] shows that evaluations on the computational time of UNADS permits to envisage an on-line operation of the system, using a parallel computing architecture for the core algorithms. This paper represents a continuation of our previous work on unsupervised anomaly detection [START_REF] Mazel | Sub-space clustering, inter-clustering results association & anomaly correlation for unsupervised network anomaly detection[END_REF].

21 / 31 ! ! Conventional machine learning algorithms require the complete data set to be available for training. This is known as batch processing. On the contrary, online streaming machine learning algorithms operate assuming that data streams are infinite, and can thus only function using a relatively small fraction of the data. Some of the ideal requirements for online algorithms are described below. § Requirement 1: Process one sample at a time, at most once: Data streams are often continuous, which requires a stream mining algorithm to outpace their frequency.

Due to the infinite nature of the stream, data samples must be processed and eventually discarded. § Requirement 2: Use a limited amount of memory: a streaming algorithm must function in a manner such that the amount of memory needed is independently bounded. § Requirement 3: Work in a limited amount of time: ideally, the running time complexity of a streaming algorithm will depend linearly on the number of treated samples. As mentioned before, stream mining algorithms must outpace the arrival rate of the data. § Requirement 4: Readiness: These algorithms should ideally be ready to make predictions or decisions at any moment.

Of course, these requirements describe the ideal stream mining algorithm, but depending on the setting, some or all of them can be relaxed while maintaining a sufficiently satisfactory performance. The first requirement, for instance, can be overlooked if the algorithm can function using only a subset of the arriving samples. If some of the data are correctly discarded, the computational demands of the system can be significantly decreased. Requirement 2 can be relaxed as well. An exception can be made if external storage is used, although this can inflict unacceptable penalties on speed requirements. In general, these requisites can be observed with different levels of rigor if the environment allows it. The main restriction to be kept in mind by the algorithm designer is that the system must deal with a theoretically infinite amount of information.

Sometimes, the greatest benefits can be obtained from hybrid models, i.e. algorithms that combine batch processing with stream mining. Most machine learning-based prediction systems available in the literature are a good example of this. In the case of neural network-based predictors, for instance, the algorithms are capable of making predictions based on a window of time series values, but they must be trained offline. In general, these systems can be periodically retrained with the most recently collected data, and the newly found parameters can be transmitted to the predictor.

In addition to the requirements described above, online algorithms must deal with the fact that incoming data is often non-stationary. This is reflected in the notions of concept-drift (data evolve over time) and concept-shift (data change abruptly). These algorithms must also be robust to long-term deployment. A fading coefficient must dampen the influence of outdated samples on the performance of the system if necessary.

Classification and forecasting algorithms present specific challenges. Existing techniques can make decisions very fast. The decision function often runs in constant time, and techniques such as Support Vector Machines, which are regarded as some of the slowest solutions, depend linearly on the number of support vectors (usually a very small subset of the training data).

Therefore, the challenge lies in the training process. In an online scenario, data are continuously generated (they are theoretically unlimited) and their nature can change over time (concept drift and concept shift). A trained model might become rapidly outdated, rendering the output of the algorithm unreliable. In order to address this, incoming data could be relayed to a training module to periodically update the model. However, training is usually very slow, and in big data scenarios this module would be almost immediately outpaced by the arriving data. Hence, a set of specific questions arises regarding this issue: § Can we find fast enough alternatives or approximations for training algorithms to keep some state-of-the-art classification technique up to date in an online big data scenario? § How can we determine how often we need to retrain the system? § Can we summarize the data so that we can retrain the system without sacrificing samples? § How much data do we need to use for training in order to have a sufficiently general model?

All these questions fall well within the scope of ONTIC. In the case of classification, however, the problem of labeling the data makes online solutions unfeasible. This reality makes it especially pertinent to lean toward unsupervised solutions.

Anomaly detection

In this deliverable we present a completely unsupervised method to detect and characterize network anomalies and attacks, without relying on signatures, training, or labeled traffic of any kind. Our approach relies on robust clustering algorithms to detect both well-known as well as completely unknown attacks, and to automatically produce easy-to-interpret signatures to characterize them, both in an on-line basis.

Traffic flow aggregation 8.2.1

The analysis is performed on 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 9 different flow levels l i . These include (from finer to coarser-grained resolution): source IPs (l 1 : IPsrc}), destination IPs (l 2 : IPdst), source Network Prefixes (l 3,4,5 : IPsrc/24, /16, /8), destination Network Prefixes (l 6,7,8 : IPdst/24, /16, /8}), and traffic per Time Slot (l 9 : tpTS}).

Unsupervised detection of anomalies 8.2.2

The unsupervised detection stage takes as input all the IP flows in the considered time slot, aggregated according to one of the different aggregation levels used in the first stage. Let Y = {y 1 ,.., y n } be the set of n flows in the considered time slot. Each flow y i ∈ Y is described by a set of m traffic attributes or features on which the analysis is performed. The selection of these features is a key issue to any anomaly detection algorithm, and it becomes critical in the case of unsupervised detection, because there is no additional information to select the most relevant set. In this deliverable we shall limit our study to detect and characterize well-known anomalies and attacks, using a set of standard traffic features widely used in the literature. However, the reader should note that the approach can be easily extended to detect other types of anomalies or attacks, considering different sets of traffic features. In fact, more features can be added to any standard list to improve detection and characterization results.

The set that we shall use here includes the following m = 9 traffic features: number of source/destination IP addresses and ports, ratio of number of sources to number of destinations, packet rate, ratio of packets to number of destinations, and fraction of ICMP and SYN packets. According to previous work on signature-based 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. Let x i = (x i (1),.., x i (m)) ∈ R m be the corresponding vector of traffic features describing flow y i , and X = {x 1 ,.., x n } the complete matrix of features, referred to as the feature space.

The algorithm is based on clustering techniques applied to X. The objective of clustering is to partition a set of unlabeled elements into homogeneous groups of similar characteristics, based on some measure of similarity. Our goal is to identify in Y the different aggregated flows that may compose the attack. For doing so, the reader should note that an attack may consist of either outliers (i.e., single isolated flows) or compact small-size clusters, depending on the aggregation level of flows in Y. For example, a DDoS attack is represented as an outlier flow if the aggregation is done for IPdst, consisting of all the attacking IP flows sent towards the same victim. On the contrary, the attack is represented as a cluster if we use IPsrc flow-resolution. To avoid the lack of robustness of general clustering techniques, we have developed a parallelmulti-clustering approach, combining the notions of Density-based Clustering [START_REF] Ester | A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[END_REF], Sub-Space Clustering [START_REF] Parsons | Subspace clustering for high dimensional data: a review[END_REF], and Evidence Accumulation [START_REF] Fred | Combining multiple clusterings using evidence accumulation[END_REF]. In what follows, we shall present the general idea behind the approach.

Instead of directly partitioning the complete feature space X using a traditional inter-flow similarity measure (i.e., the Euclidean distance), we do parallel clustering in N different subspaces X i ⊂ X of smaller dimensions, obtaining N different partitions P i of the flows in Y. Each sub-space X i is constructed using only r < m traffic features; this permits to analyze the structure of X from N(m,r) different perspectives, using a finer-grained resolution. In particular, we do clustering in very-low dimensional sub-spaces, using r=2. To deeply explore the complete feature space, we analyze all the r-combinations-obtained-from-m sub-spaces; hence, N(m) = m(m-1)/2. The information provided by the multiple partitions P i is then combined to produce a new similarity measure between the flows in Y, which has the paramount advantage of clearly highlighting both those outliers and small-size clusters that were simultaneously identified in different sub-spaces. This new similarity measure is finally used to easily extract the anomalous flows from the rest of the traffic.

Automatic characterization of anomalies 8.2.3

The following task after the detection of a group of anomalous flows is to automatically produce a set of K filtering rules f k (Y), k=1,..,K to characterize them. In the one hand, such filtering rules provide useful insights on the nature of the anomaly, easing the analysis task of the network operator. On the other hand, different rules can be combined to construct a signature of the anomaly, which can be used to easily detect its occurrence in the future. To produce filtering rules f k (Y), the algorithm selects those sub-spaces X i where the separation between the anomalous flows and the rest of the traffic is the biggest. We define two different classes of filtering rule: absolute rules f A (Y) and relative rules f R (Y). Absolute rules are only used in the characterization of small-size clusters, and correspond to the presence of dominant features in the flows of the anomalous cluster. An absolute rule for feature j has the form f A (Y) = {y i ∈ Y: x i (j) == λ}. For example, in the case of an ICMP flooding attack, the vast majority of the associated flows use only ICMP packets, hence the absolute filtering rule {nICMP/nPkts == 1} makes sense, (nICMP/nPkts corresponds to the fraction of ICMP packets).

On the other hand, relative filtering rules depend on the relative separation between anomalous and normal-operation flows. Basically, if the anomalous flows are well separated from the rest of the traffic in a certain partition P i , then the features of the corresponding sub-space X i are good candidates to define a relative filtering rule. A relative rule defined for feature j has the form f R (Y) = {y i ∈ Y: x i (j) < λ or x i (j) > λ}. We shall also define a covering relation between filtering rules: we say that rule f 1 covers rule f 2 ⇔ f 2 (Y) ⊂ f 1 (Y). If two or more rules overlap (i.e., they are associated to the same feature), the algorithm keeps the one that covers the rest.

In order to construct a compact signature of the anomaly, we have to devise a procedure to select the most discriminant filtering rules. Absolute rules are important, because they define inherent characteristics of the anomaly. Regarding relatives rules, their relevance is directly tied to the degree of separation between flows. In the case of outliers, we select the K features for which the normalized distance to the normal-operation traffic (statistically represented by the biggest cluster in each sub-space) is among the top-K biggest distances. In the case of smallsize clusters, we rank the degree of separation to the rest of the clusters using the well-known Fisher Score (FS) [START_REF] Jaakkola | Exploiting Generative Models in Discriminative Classifiers[END_REF], and select the top-K ranked rules. The FS basically measures the separation between clusters, relative to the total variance within each cluster. To finally construct the signature, the absolute rules and the top-K relative rules are combined into a single inclusive predicate, using the covering relation in case of overlapping rules.

Experimental evaluation 8.2.4

This section is aimed at showing how the unsupervised approach can detect and characterize different network attacks without using signatures, labels, or learning. We shall begin by detecting and characterizing a distributed SYN network scan directed to many victim hosts under the same /16 destination network. Packets in Y are aggregated using IPdst/24 flow resolution, thus the attack is detected as a small-size cluster. The length of each time slot is ΔT = 20 seconds. As we explained in section 8.2.2 , the SSC-EA-based clustering algorithm constructs a new similarity measure between flows in Y, using the multiple clustering results obtained from the different sub-spaces. Let us express this new similarity measure as a n × n matrix S, in which element S(i,j) represents the degree of similarity between flows i and j. Figure 4 depicts a histogram on the distribution of inter-flows similarity, according to S. The structure of flows in Y provided by S evidences the presence of a small isolated cluster in multiple sub-spaces. Selecting this cluster results in 53 anomalous IPdst/24 flows; a further analysis of the packets in these flows reveals multiple IP flows of SYN packets with the same IPsrc address and sequential IPdst addresses, scanning primary the same TCP port. Such a behavior is characteristic of a worm in the spreading phase.

Regarding filtering rules, Figure 5 depicts some of the partitions P i where both absolute and top-K relative rules were produced. These involve the number of sources and destinations, and the fraction of SYN packets. Combining them produces a signature that can be expressed as (nSrcs == 1) ∧ (nDsts > λ 1 }) ∧ (nSYN/nPkts > λ 2 ), where both λ 1 and λ 2 are obtained by separating clusters at half distance. Surprisingly enough, the extracted signature matches quite closely the standard signature used to detect such an attack in current signature-based systems [START_REF] Fernandes | Automated classification of network traffic anomalies[END_REF]. The beauty and main advantage of the unsupervised approach relies on the fact that this new signature has been produced without any previous information about the attack or baseline traffic, and now it can be directly exported towards any security device to rapidly detect the same attack in the future. respect to S selects a compact cluster with the most similar flows, corresponding to the set of attacking hosts. The obtained signature can be expressed as (nDsts == 1) ∧ (nSYN/nPkts > λ 3 ) ∧ (nPkts/sec > λ 4 ),} which combined with the large number of identified sources (nSrcs > λ 5 ) confirms the nature of a SYN DDoS attack. This signature is able to correctly isolate the most aggressive hosts of the DDoS attack, i.e., those with highest packet rate. Thus the attack is now detected as an outlier rather than as a small-size cluster. Absolute rules are not applicable in the case of outliers detection. Relative rules correspond to the separation of the outlier from the biggest cluster in each sub-space, which statistically represents normal-operation traffic. Besides showing typical characteristics of this attack, such as a high packet rate of exclusively ICMP packets from the same source host, both partitions show that the detected attack does not involve the largest elephant flows in the time slot. This emphasizes the ability of the algorithm to detect attacks that are not necessarily different from normal-operation traffic in terms of volume, but that they differ in other, less evident characteristics. The obtained signature can be expressed as (nICMP/nPkts > λ 6 ) ∧ (nPkts/sec > λ 7 ). The completely unsupervised algorithm for detection of network attacks that we have presented has many interesting advantages with respect to previous proposals. It uses exclusively unlabeled data to detect and characterize network attacks, without assuming any kind of signature, particular model, or canonical data distribution. This allows detection of new previously unseen network attacks, even without using statistical-learning. By combining the notions of Sub-Space Clustering and multiple Evidence Accumulation, the algorithm avoids the lack of robustness of general clustering approaches, improving the power of discrimination between normal-operation and anomalous traffic. We have shown how to use the algorithm to automatically construct signatures of network attacks without relying on any kind of previous information.

In the following month, we will continue improving the algorithm, perform intensive evaluation for estimating its accuracy and scalability, and start developing a prototype to be further included in the general ONTIC system.

Figure 1 :

 1 Figure 1: Traffic pre-processing for scalable online characterization ................................ 17Figure 2: Traffic Pattern Evolution Subsystem Architecture ........................................... 19 Figure 3: High-level description of the Unsupervised network Anomaly Detection System ....... 21 Figure 4: Detecting a distributed SYN network scan using S ........................................... 26 Figure 5: SYN network scan .................................................................................. 26 Figure 6: SYN DDoS ............................................................................................ 27 Figure 7: ICMP flooding DoS ................................................................................. 27

Figure 2 : 21 Figure 4 :

 2214 Figure 1: Traffic pre-processing for scalable online characterization ................................ 17Figure 2: Traffic Pattern Evolution Subsystem Architecture ........................................... 19 Figure 3: High-level description of the Unsupervised network Anomaly Detection System ....... 21 Figure 4: Detecting a distributed SYN network scan using S ........................................... 26 Figure 5: SYN network scan .................................................................................. 26 Figure 6: SYN DDoS ............................................................................................ 27 Figure 7: ICMP flooding DoS ................................................................................. 27

6. 1

 1 From supervised to unsupervised traffic classification and anomaly detection The problem of network anomaly detection has been extensively studied during the last decade. Most of the approaches analyze statistical variations of traffic volume (e.g. number of packets, bytes or new flows) and/or traffic features (e.g. 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 -Autoregressive Integrated Moving Average -modeling, wavelets-based filtering) on singlelink traffic measurements [1][2], PCA (Principal Component Analysis) for network-wide anomaly detection [4][5][6], and Sketches applied to IP-flows [3][7].

  There exist different types of clustering algorithms: § Partitioning algorithms, which divide a set of objects into different clusters with the goal of minimizing an objective function. An example is the classic k-means. § Micro-clustering: they consist of two phases, a preliminary online micro-clustering of the data and a grouping into global clusters. Examples are BIRCH and CluStream. § Density-based algorithms based on connectivity and density functions. Examples are DBSCAN and OPTICS. § Grid-based algorithms, based on a multiple-level granularity structure, such as Fractal Clustering and STING, CLIQUE and MAFIA. § Model-based algorithms, which aim to fit a model as well as possible, such as COBWEB and Kohonen's Self-Organized Maps.

Figure 1 :

 1 Figure 1: Traffic pre-processing for scalable online characterization

Figure 2 :

 2 Figure 2: Traffic Pattern Evolution Subsystem Architecture

Figure 3 : 1 22 / 31 ! ! 8 .

 31318 Figure 3: High-level description of the Unsupervised network Anomaly Detection System

Figure 6

 6 Figure 6 depicts different rules obtained in the detection of a SYN DDoS attack. IP flows are now aggregated according to IPsrc resolution. The distribution analysis of inter-flows similarity with

Figure 7

 7 Figure 7 depicts the detection of an ICMP flooding DoS attack. Traffic is aggregated in IPdst flows.Thus the attack is now detected as an outlier rather than as a small-size cluster. Absolute rules are not applicable in the case of outliers detection. Relative rules correspond to the separation of the outlier from the biggest cluster in each sub-space, which statistically represents normal-operation traffic. Besides showing typical characteristics of this attack, such as a high packet rate of exclusively ICMP packets from the same source host, both partitions show that the detected attack does not involve the largest elephant flows in the time slot. This emphasizes the ability of the algorithm to detect attacks that are not necessarily different from normal-operation traffic in terms of volume, but that they differ in other, less evident characteristics. The obtained signature can be expressed as (nICMP/nPkts > λ 6 ) ∧ (nPkts/sec > λ 7 ).

Figure 4 :Figure 5

 45 Figure 4: Detecting a distributed SYN network scan using S

Figure 6

 6 Figure 6: SYN DDoS

ONTIC. Deliverable 4.1

/ 31