In this paper , we investigate an unsupervised machine learning method based on one-class Support Vector Machines for anomaly detection in network traffic. In the absence of any prior expert knowledge on anomalous data, we propose the use of a similarity measure for Multivariate Time Series to evaluate the output results and select the best model. A set of Key Performance Indicators, oriented for network and traffic monitoring, has been used to demonstrate the promising performance of the unsupervised learning approach.
Anomaly detection aims at identifying unusual
patterns in data that do not conform to expected
behavior [1]. These non-conforming patterns are generally
referred in different application fields to as anomalies,
aberrations, discordant observations, exceptions,
novelty, outliers, peculiarities or contaminants, surprises,
strangeness. There has been applications in several
application fields from intrusion detection, e.g.
identifying strange patterns in network traffic that could
signal a hack [2], to system health monitoring, e.g.
spotting a malignant tumor in an MRI image scan [3],
and from fraud detection in credit card transactions
[
Support Vector Machines (SVMs) have been one of the most successful machine learning techniques that can be used in a variety of classification applications.
SVMs perform at least as good as other methods in terms of the generalization error [6].
Many factors contributed to the high popularity of SVMs today. First of all, their theoretical foundations have been deeply investigated and they come with a convex optimization procedure ensuring that the global optimum will be reached. Moreover, the solution is sparse making it really efficient in comparison to other kernel-based approaches [7]. In addition, they may use a non linear transformation in the form of a kernel that even allow SVMs to be considered as a dimensionality reduction technique [8]. One-Class SVMs [9] have been devised for cases in which one class only is known and the problem is to detect anything outside this class. This is known as novelty detection and it refers to automatic identification of unforeseen or abnormal phenomena [1; 10; 11], i.e. outliers, embedded in a large amount of normal data.
In contrast to traditional SVMs, One-Class SVMs
(OC-SVM) learn a decision boundary that achieves
maximum separation between the samples of the
known class and the origin [
Anomaly detection is particularly important for network traffic. The observed growth rate of informational and economic damage caused by intentionally or unintentionally attacks, faults, and anomalies has been a driving force behind efforts to ensure that network monitoring systems are able to detect abnormal activity and characterize it. The limitations of computing and storage resources require competence and ingenuity to effectively characterize everchanging network traffic trends.
Non-availability of labelled data, high costs for constituting labeled training data, and need to identify anomalous and novel observations in data without having necessarily seen an example of that behaviour in the past are the main challenges tackled in this work. A central issue is model selection, i.e. choice of the optimal hyper-parameters that define the OCSVM learning configuration. This requires a method to evaluate the results.
This paper contributes to this problem by evaluating the results of the trained model by comparing samples predicted normal with samples in the training set. Because samples are composed of a set of signals over a temporal window, we propose to use a similarity index for Multivariate Time Series (MTS) called EROS (Extended Frobenius Norm). The results of the model are evaluated iterativelly for different hyper-parameters of OC-SVM and the model that evaluates best is selected. We show that OC-SVM in combination with the Eros index [read more in Section 4.1] can create automatically tuned reliable classifiers with reasonable computation cost.
The remainder of this paper is organized as follows. Section 2 presents our case study. Section 3 is devoted to an overview of SVMs and One-Class SVMs methods. In Section 4, we present the EROS similarity measure used to search for the best training model for anomaly detection. Experimental results and related discussions are provided in Section 5 to demonstrate the approach performance. Finally, Section 6 concludes the paper. 2
Processing network traffic involves dealing with an immense amount of data that is quickly and constantly varying. Considering the enormous amount of data involved it is very easy for malicious activities to go undetected, especially without any knowledge a priori about the nature of the traffic, like it is often the case in the network domain.
In this study, data was collected from a real-time monitoring platform dedicated to ensure key application performance. 51 sites using applications of the same kind and having roughly the same uses at the same time, were chosen. For each application, we selected carefully four relevant Key Performance Indicators (KPIs) describing: 1. Total Incoming Traffic. 2. Total Outgoing Traffic. 3. Server Delay, i.e. the connection time to the server, which sets the expiration time for sending a request. 4. Network Delay that specifies how long it takes for a bit of data to travel across the network from one node to another.
A history of two months (3408 samples) of data generated at a 5 minutes rate was collected for each of the four KPIs above and for each site. Data was segmented into time-windows wi, each of 48 points. Figure 1 shows the data contained in the training set. Each time-window wi 2 fw0; :::; wlg, l = 70, is identified between lines and there are 70 samples.
Let us notice that the data samples that are provided
to the OC-SVM classification algorithm are
multivariate, each composed of four KPI segments over the
same time-window. The idea is to detect insidious
problems that require an analysis of the signal
underlying interactions. We therefore want to detect
“abnormal windows”. Each segment is characterized by
seven statistical attributes: minimum (MIN),
maximum (MAX), mean (MEAN), median (MED),
standard deviation (STD), number of average crossings
(nbpMean), squared mean error (SME) computed
between the raw data and the linear fitting. These
attributes are used by OC-SVM after normalization.
Figure 2 shows the attributes built for the 70 segments
of the four KPIs mentioned above. The seven
attributes MEAN, MED, MAX, MIN, STD, nbpMean,
and SME are illustrated in sub-figures from left to
right. We can already notice some overruns that will
make considerable contribution to the classifier
profile defined by the decision function.
Support Vector Machines (SVMs) have always been
of interest in anomaly detection because of their
ability to provide non-linear classification through a
kernel function. Via this short overview, we show that
SVMs are theoretically well founded. We briefly
introduce the basic concepts of SVMs then focus on
OC-SVM that we adopted in this study. A more
detailed presentation can be found in [
Let us consider the traditional two-class support vector machines in which we are given a set of n training instances S = f(x1; y1); (x2; y2); :::; (xn; yn)g. xi 2 Rd, where yi is the class label of the xi instance and yi 2 [ 1; +1]. The linear SVMs classifier recovers an optimal separating hyperplane maximizing the "margin" of the classifier with the equation: wT x + b = 0, with w 2 F and b 2 R two parameters witch determine the position of the decision hyperplane in feature space F (its orientation is tuned by w and its displacement by b). The decision function can thus be generally written as: f (x; w; b) = sign(wT x + b) 2 f 1; +1g (1) where: sign(wT x + b) = + 1; if (wT x + b)
0
The concept of SVMs is to find (w; b) such that the hyperplane is positioned at maximum distance of the nearest training samples of the two classes in order to reduce the generalization error. This distance defines the "margin". SVMs have first been proposed for linearly separable classification tasks. However they were extended to non-linearly separable classification problems. Some samples are allowed to violate the margin (soft-margin SVMs) and a non-linear decision boundary can be obtained by projecting the data into a higher dimension space thanks to a non-linear function (x). Data points may not be linearly separable in their original space but they are “lifted” into a feature space F where a hyperplane can separate them. When that hyperplane is projected back into the input space, it has a non-linear shape. To prevent the SVM classifier from over-fitting noisy data, slack variables are introduced to allow some data points to lie within the margin, and the parameter C > 0 (Eq.2) tunes the trade-off between the classification error on the training data and margin maximization. The objective function of SVM classifiers has the following minimization formulation: n min kwk2 + C X w;b; i 2 i=1 i (2)
yi(wT (xi) + b) 1
i i
0; i = 1; :::; n
The minimization problem is solved using Lagrange Multipliers i; i = 1; : : : ; n. The new decision function rule for a data point x is:
n f (x) = sign(X i=1 iyiK(x; xi) + b) (3) Every i > 0 is weighted in the decision function and thus supports the machine. Since SVMs are considered to be sparse, there are relatively few Lagrange multipliers with a non-zero value.
The function K(x; xi) = (x)T (xi) is known as the kernel function. Since the outcome of the decision function only relies on the dot-product of the vectors in the feature space F (i.e. all the pairwise distances for the vectors), it is not necessary to perform an explicit projection. As long as a function K provides the same results, it can be used instead. This is known as the kernel trick.
Popular choices for the kernel function are linear, polynomial, and sigmoïdal. In this study, we used the Gaussian Radial Base Function:
K(x; xi) = exp( kx where 2 R is a kernel parameter and kx xik is the dissimilarity measure. With this set of formulas and concepts we are able to classify a set of data point into two classes with a non-linear decision function.
The power of the method comes from using kernel functions, which enable it to operate in a highdimensional, implicit feature space without ever computing the coordinates of the data in that space, but rather by simply computing the inner products between the images of all pairs of data in the feature space. This operation is often computationally cheaper than the explicit computation of the coordinates. Figure 3 illustrates a non linearly separable data set clustered by SVM with two different kernel functions: linear and radial based. The observations are plotted blue or magenta depending on the class and the background is darker as the distance from the hyperplane is higher. Scores are given on the right bottom corners and show a significant increase for the non linear kernel. 3.2
One-Class SVMs (OC-SVMs) are used to separate
the data of one specific class, the target class, from
other data. They are trained with positive examples
only, i.e. data points from the target class. There are
two different approaches: the approach according to
Schölkopf [
In the feature space F , OC-SVM method basically separates all the data points from the origin by a hyperplane and it maximizes the distance of this hyperplane to the origin. This results in a binary function which captures the region of the input space where the training data lives. Thus the function returns +1 in a “small” region (capturing the training data points) and 1 elsewhere. The quadratic programming minimization function is slightly different from the original stated by (Eq.2) and (Eq.3): Subject to: min kwk2 + w; i; 2 w: (xi) 1 Xn
i=1 n 0 i i (5) i = 1; :::; n
Schölkopf et al. [
Again by using Lagrange techniques and using a kernel function for the dot-product calculations, the decision function becomes: f (x) = sign((w (xi)) )
n (6) = sign(X iK(x; xi) )
i=1
OC-SVMs thus create a hyperplane characterized by w and which has maximal distance from the origin in the feature space F , hence separating all the data points from the origin. 4
In this section, we address the problem of fitting the hyper-parameters of OC-SVM automatically, that is the problem of automatic model selection. In the case of OC-SVM, this amounts to choose the kernel parameter and the regularization parameter . A pair ( i; j ) is defined as a learning configuration.
For this purpose, we propose to run OC-SVM for several learning configurations and select the best configuration by evaluating the similarity of the KPI signals for the windows tagged normal by OC-SVM and the KPI windows of the training data that are assumed to be normal examples. Since a sample window is composed of several KPI signals, we need a multidimensional similarity index for Multivariate Time Series (MTS). 4.1
Multidimensional similarity measures aim to indicate simultaneously the level of similarity between several datasets (databases, data clusters, etc.). Unlike other methods [15; 16; 17] that seek the level of similarity between two variables by omitting the existing correlation between the set of variables, a multidimensional method takes into account the contribution of each variable in defining a global similarity measure.
One of the methods processing MTS is the method
Eros (Extended Frobenius Norm) [
We briefly describe the similarity index Eros based
on the Frobenius Norm below. The definitions and
notations used in this paper are taken from [
Definition 1. Eros (Extended Frobenius Norm). Let A and B be two MTS items of size mA n and mB n respectively. Let VA and VB two right eigenvector matrices by applying Singular Value Decomposition (SVD) to the covariance matrices, MA and MB, respectively. Let VA = [a1; : : : ; an] and VB = [b1; : : : ; bn], where ai and bi are columnorthonormal of size n. The Eros similarity of A and B is then defined as: n Eros(A; B; w) = X
wi j< ai; bi >j i=1 n = X jcos( i)j i=1 (7) where hai; bii is the inner product of ai and bi, w is a weight vector which is based on the eigenvalues of the MTS dataset, Pn
i=1 wi = 1 and cos( i) is the angle between ai and bi. The range of Eros is between 0 and 1, with 1 being the most similar.
Definition 2. Singular Value Decomposition. Let A be a general real m n matrix. The singular value decomposition (SVD) of A is the factorization: A = U V (8) where U is a column-orthonormal N r matrix, r is the rank of the matrix A, is a diagonal r r matrix of the eigenvalues i of A where 1 r 0 and V is a column-orthonormal M r matrix. The eigenvalues and the corresponding eigenvectors are sorted in non-increasing order. V is called the right eigenvector matrix, and U the left eigenvector matrix.
Yang et al. (2005) [
4. Compute the weight w of individuals by
normalizing the eigenvalues [
4.2
The first task is to define the learning configurations that will be tested with OC-SVM. We follow the steps below: 1. Define the hyper-parameter space and a procedure to explore this space. In our case, we set a min-max and a variation step to constitute a grid ( ) value pairs, i.e. values for each hyperparameter. 2. Explore the hyper-parameter space and set OCSVM accordingly: for each pair of values, one OC-SVM classifier is obtained after the learning step. The best configuration is retained by using the Eros similarity index on the validation data (25% of all data) and the training data (50% of all data). The corresponding OC-SVM classifier is taken as the best model. 3. Once found the best model, anomaly detection is performed on new data to evaluate how well the model behaves.
The similarity of windows tagged normal by OCSVM, denoted by MTSknormal, k = 0; :::; p, and the data windows of the training data (considered as normal), denoted by MTSllearn, l = 1; :::; q, is obtained as follows. For every learning configuration [Figure 4] given by ( i; j ): l = 1; :::; q.
(MTSnkormal; MTSllearn), k = window pair 0; :::; p, and 2. Compute the average similarity "Erosmean" over all the window pairs.
The best learning configuration is taken as the one
leading to the maximal "Erosmean" value over all
considered learning configurations ( i; j ).
Our detection approach was applied to the case study
presented in Section 2. A history of two months of
data generated every 5 minutes for four KPIs was
collected over 151 sites. The window segmentation [
As mentioned in section 2, the time-window length was chosen of 4 hours, i.e. 48 samples. Clearly, when access to web applications is established in a few hours, a window of four hours is considered a significant period for traffic analysis. As noted above, each time-window is characterized by seven statistical attributes: minimum (MIN), maximum (MAX), mean (MEAN), median (MED), standard deviation (STD), number of average crossings (nbpMean), squared mean error (SME) computed between the raw data and their linear fit. The attributes are computed for each time-window in order to obtain a multidimensional scatter plot, where each point represents a timewindow. One of the major interests of segmentation and feature computation is to synthesize the information contained in a time-window. This allows the detection not only of singular points, but also of an atypical set of points even if each point taken.
Acquired raw data provide KPIs with different ranges, then features (attributes) themselves don’t have homogeneous ranges. In order to guarantee good performances of the anomaly detection approach, we chose to normalize these attributes with respect to their maximal and minimal values with a tolerance using a threshold s 2 [0; 1]. This standard preprocessing ensures that all the attributes contribute equally to the decision process independently of the parameters responsible of KPI dynamics.
To automatically select the best model, the hyperparameter space was discretized with a 10 10 grid, i.e. = 10. 100 learning configurations were therefore evaluated to select the best model. This off-line task was performed for each application site and appeared computationally feasible.
Figure 5 shows some of the test results (25% of all data). From 24 time-windows (wi 2 fw0; : : : ; wmg, m = 23), 4 anomalies have been detected represented by the 4 time-windows (yellow colored): w3, w4, w10 and w12. The results were confirmed with Parallel Coordinates plots given in Figure 6.
In a Parallel Coordinates Plot, each attribute is given its own axis and all the axes are placed parallel to each other. Values are plotted as a series of lines that connect across all the axes. This means that each line corresponds to one data window for which we have 7 4 attributes (7 features for every KPI).
The order in which the axes are arranged can impact the way how the reader understands the data. One reason for this is that the relationships between adjacent variables are easier to perceive than those between non-adjacent variables. So re-ordering the axes can help in discovering patterns or correlations across variables. We clearly see that the four time-windows defined by the pink lines represent a strange behavior compared to the normal windows defined by the green lines.
Presenting this type of detection can ensure that the
network administrators adopts another reasoning to
characterize the nature of the traffic (normal,
abnormal, critical, ...) circulating on the network. It may
help him to identify the different forms of anomaly
in his network. Data analysis must give meaning
to the data with the goal of discovering useful
information, suggesting conclusions, and supporting
decision-making. The value of the data lies in the
story it tells.
In this work, we applied the OC-SVM method to
detect anomalies in real network traffic, contributing
with an automatic method based on the similarity
index Eros [
The advantages of novelty detection for complex processes like network traffic are multiple. In particular there is no need of faulty data. A wide variety of cases of anomaly exist and it would be impossible to characterize them all or to gather the corresponding data. Challenges for future work is related to the fact that data comes in a stream and dealing with the data in real-time is quite tedious. The amount of data leads to cases where resources are limited. Novelty detection in a distributed framework is also to be investigated.
Acknowledgement The authors thank Bertrand Le Marec and David Maisonneuve, leading team of LivingObjects, for their support and valuable comments about the application.