Network Anomaly Detection: A Survey and Comparative Analysis of Stochastic and Deterministic Methods

We present five methods to the problem of network anomaly detection. These methods cover most of the common techniques in the anomaly detection field, including Statistical Hypothesis Tests (SHT), Support Vector Machines (SVM) and clustering analysis. We evaluate all methods in a simulated network that consists of nominal data, three flow-level anomalies and one packet-level attack. Through analyzing the results, we point out the advantages and disadvantages of each method and conclude that combining the results of the individual methods can yield improved anomaly detection results.


I. INTRODUCTION
A network anomaly is any potentially malicious traffic that has implications for the security of the network. It is of particular importance to the prevention of zero-day attacks, i.e., attacks not previously seen, and malicious data exfiltration. These are key areas of concern for both government and corporate entities.
From the perspective of methodology, network anomaly detection methods can be classified as stochastic and deterministic. Stochastic methods fit reference data to a probabilistic model and evaluate the fitness of the new traffic with respect to this model [7], [11], [12], [22], [29]. The evaluation can be done using Statistical Hypothesis Testing (SHT) [5], [13], [16], [19]. Deterministic methods, on the other hand, try to partition the feature space into "normal" and "abnormal" regions through a deterministic decision boundary. The boundary can be determined using methods like Support Vector Machine (SVM), particularly 1-class SVM [9], [21], [25], and clustering analysis [1], [6].
From the perspective of data, network anomaly methods can be either packet-based [7], [17], flow-based [2], [18] or window-based [12]. Packet-based methods evaluate the raw packets directly while both flow-based and window-based methods aggregate the packets first. Flow-based methods evalulate each flow individually, which is defined as a collection of packets with similar properties. Flows are considered as a good tradeoff between cost of collection and level of detail [26]. Window-based methods group consecutive packets or flows based on a sliding window. suspicious windows of time can be identified as anomalous.
Model-free and model-based methods are stochastic and the rest methods are deterministic.
A challenging problem in the evaluation of anomaly detection methods is the lack of test data with ground truth, due to the limited availability of such data. The most widely used labeled dataset, DAPRA intrusion detection dataset [14], was collected 14 years ago. Since then, the network condition has changed significantly. In order to address this problem, we developed software to generate labeled data, including a flow-level anomaly data generator (SADIT [28]) and a packet-level botnet attack data generator (IMALSE [27]). We evaluate all of our methodologies on a simulated network and compare their performance under three flow-level anomalies and one Distributed Denial of Service (DDoS) attack.
The rest of the paper is organized as follows. Section II describes the representation of network traffic data. Section III provides a mathematical description of the methods used to identify anomalies. Section IV provides an in-depth explanation of the simulated network and the anomalies. Section V presents the results of the five methods on the simulated network data. Finally, Section VI provides concluding remarks.

II. NETWORK TRAFFIC REPRESENTATION
Let S = {s 1 , . . . , s |S| } denote the collection of all packets on the server which is monitored, where each element of S is one packet. We focus on host-based anomaly detection, in which case we only care about the user IP address, namely the destination IP addresses for the outgoing packets and the source IP addresses for the incoming packets. Denote the user IP address in a packet s i as x i , whose format will be discussed later. The size of s i is b i ∈ [0, ∞) in bytes and the start time of transmission is t i ∈ [0, ∞) in seconds. Using this convention, the packet s i can be represented as Due to the vast number of packets, we consolidate this representation of network traffic by grouping series of packets into flows. We compile a sequence of packets s 1 = ( . . , n and some prescribed δ F ∈ (0, ∞). Here, the size b is simply the sum of the sizes of the packets that comprise the flow. The value d t = t n − t 1 denotes the flow duration. The value t = t 1 denotes the start time of the first packet of the flow. In this way, we can translate the large collection of traffic packets S into a relatively small collection of flows F = {f 1 , . . . , f |F | }.
In some applications in which large numbers of users frequently access the server under surveillance, it may be infeasible to characterize network behavior for each user. Different methods deal with this dilemma differently.
For both statistical and SVM methods, we first distill the "user space" into something more manageable while enabling us to characterize network behavior of user groups instead of just individual users. For simplicity of notation, we only consider IPv4 addresses. If . . , 255} 4 are two IPv4 addresses, the distance between them is defined as: d(x i , x j ) = k=1,...,4 256 4−k |x i k − x j k |. This metric can be easily extended to IPv6 addresses if needed. Suppose X is the set of unique IP addresses in F. We apply typical K-means clustering on X [8], [15]. For each x ∈ X , we thus obtain a cluster label k(x). Suppose the cluster center for cluster k isx k , then the distance of x to the corresponding cluster center is d a (x) = d(x,x k(x) ). Using user clusters, we can produce our final representation of a flow as: For the ART clustering method, distilling the user space beforehand is not required. However, instead of using the IP address directly, we use a compact representation. Let n f (x) be the number of flows transmitted between the user with IP address x and the server. Define d b (x) = d(x, x * ), ∀x ∈ X , where x * is the IP address of the server we are monitoring; then the alternative flow representation we use is: (2)

A. Statistical Methods
Let h be the interval between the start points of two consecutive time windows and w s be an appropriate window size; then the total number of windows is be the flow attributes in f i without the start time t i and G j = {g 1 , g 2 , . . . , g |Gj | } be the flows in window j. Let G ref be the set of all flows used as reference. The window-based methods will compare G j with G ref for all j = 1, . . . n w . Both statistical methods we will present in this section fall into this category and can work in supervised as well as unsupervised modes. In supervised mode, G j is generated by removing suspicious flows from a small fragment of data through human inspection. In unsupervised mode, we assume that the anomales are shortlived thus G j can be chosen as a large set of nework traffic.
Since the approach introduced in what follows applies to all windows as well as to nominal flows, we use . We can then define a discrete alphabet Σ da = d min a where |Σ da | is called quantization level. Σ b and Σ dt can be defined similarly for b i and d i t . We then quantize d a (x i ), b i and d i t in g i to the closest symbol in the discrete alphabet set Σ da and Σ b and Σ dt , respectively. Suppose the total number of user clusters is K. Then we can denote the quantized flow sequence discrete alphabet for quantization where each symbol in Σ corresponds to a flow state.
1) Model-free Method: In cases in which all flows emanating from the server under surveillance are i.i.d., we construct the empirical measure of flow sequence G = {g 1 , . . . , g |G| } as the frequency distribution vector where 1{·} denotes the indicator function and σ(g i ) denotes the flow state in Σ that g i gets mapped to. We will denote the probability vector derived from the empirical measure of the form in (3) as Let µ denote the probability vector calculated from the reference flows G ref . That is, µ(σ) is the reference marginal probability of flow state σ. Using Sanov's theorem [16], [4], we construct a metric to compare empirical measures of the form in (3) to µ, thus a metric of the "normality" of a sequence of flows. For every probability vector ν with support Σ, let H(ν|µ) = σ∈Σ ν(σ) log (ν(σ)/µ(σ)) be the relative entropy of ν with respect to µ. Allowing η = − 1 n log , where is a tolerable false alarm rate, then the model-free anomaly detector is: where It was shown in [19] that (4) is asymptotically Neyman-Pearson optimal.
2) Model-based Method: As an alternative to the i.i.d. assumption on the sequence of flows under the model-free method, we now turn to the case in which the sequence of flows adheres to a first-order Markov chain. The notion of empirical measure on the sequence G = {g 1 , . . . , g |G| } must now be adapted to consider subsequent pairs of flow states. We assume no knowledge of an initial flow state σ(g 1 ) and define the empirical measure on G, under the Markovian assumption, as the frequency distribution on the possible flow state transitions, where 1{·} denotes the indicator function and σ(g l ) denotes the flow state in Σ which g l gets mapped to. We will denote probability matrices formed by the empirical measure in (5) ..,|Σ| . In the following, we will refer to matrices of the form Q = {q(σ i , σ j )} i,j=1,...,|Σ| as probability matrices with support Σ × Σ. By design, the empirical measures of the form (5) are probability matrices with support Σ × Σ. Each probability matrix, under the Markovian assumption, is associated with a transition probability matrix of the form Here q(σ i ) = |Σ| j=1 q(σ i , σ j ) denotes the marginal probability of flow state σ i in Q.
Let Π = {π(σ i , σ j )} i,j=1,...,|Σ| denote, under the Markovian assumption, the true probability matrix of sequences of flows. As in the i.i.d. case, we compute Π via (5) from G ref . Following a similar procedure as in the i.i.d. case, we use an analog of the Sanov's Theorem for the Markovian case, which appears in [4], as the basis for our modelbased stochastic anomaly detector. For every shift invariant probability matrix Q with support Σ × Σ, let be the relative entropy of Q with respect to Π. Then in the model-based method, the indicator of anomaly for G is: where and η = 1 n log with be an allowable false alarm rate. Again, the model-based detector has been proved in [19] to be asymptotically Neyman-Pearson optimal.

B. 1-class SVM
We turn now to deterministic methods based on the construction of a decision boundary. We focus on one popular technique named 1-class SVM [16], [24]. The premise behind 1-class SVM is to find a hyperplane that separates the majority of the data Z = {z 1 , . . . , z |Z| } from the outliers by solving a Quadratic Programming (QP) Problem [19], [24]. The hyperplane can be generalized to a nonlinear boundary by mapping the inputs into high-dimensional spaces with a kernel function K(·, ·) [9]. There is a tunable parameter ν effectively tuning the number of outliers.
1) Flow 1-class SVM: We consider a set of flows G = {g 1 , . . . , g |G| } that need to be evaluated. According to (1), each flow has the format of g = (k(x), d a (x), b, d t ), which has already provided a rather compact representation of network traffic. The only additional process required is to remove the label of the cluster each user belongs to. The new data are: The reasoning for this is that, since we are measuring departures from nominal users, the actual cluster a user belongs to is less important than the distance between the user the cluster center. Besides, as a categorical attribute, cluster labels make 1-class SVM method more unstable in practice. Besides, we choose the radial basis as the kernel function [16].
2) Window 1-class SVM: We combine the techniques described in Section III-A and the 1-class SVM into a window-based 1-class SVM method. For each window j with flows G j , we can get the model-free empirical measure E Gj and the model-based empirical measure E Gj B . Let the feature vector for window j be Y j = E Gj , E Gj B , |G j | . Let Y = {Y 1 , . . . , Y |Y| } be a time series consisting of the features for all windows, then an 1-class SVM can be used to evaluate Y, resulting in a window-based anomaly detector. Note that since the dimension of feature Y j is usually very large, it often helps to apply Principal Component Analysis (PCA) [20] to reduce the dimensionality first.

C. ART Clustering
In this section, we present a clustering algorithm based on ART theory [3] and apply it to network anomaly detection. The algorithm first organizes inputs into clusters based on a customized distance metric. Then, a dynamic learning approach is used to update clusters or to create new clusters.
Assume a set of flows F = {f 1 , . . . , f |F | } with form in (2). Similar to the statistical methods, we define to be the attributes in f i without the start time t i and G is the counterpart of F. Suppose g ij is the jth attribute of flow g i for all i = 1, . . . , |G| and j = 1, 2, 3, 4. Defining f min (j, G) and f max (j, G) to be the minimum and maximum of the set {g ij : ∀i = 1, . . . , |G|}, we can normalize G according toĝ ij = g ij −fmin(j,G)) fmax(j,G)−fmin(j,G) for all i = 1, . . . , |G|, and j = 1, 2, 3, 4. In this section we assume that the data in G has already been normalized.
Define the distance metric for two m-dimensional vectors p = (p 1 , . . . , p m ) and q = ( represent the center of cluster k and c j k be its j component. Let C be the set of all cluster centers. For every c ∈ C and a prescribed r, defines an ellipsoid in R m . A higher vigilance in one dimension means the ellipsoid is more shallow in this direction. The ART clustering algorithm is shown in Algorithm 1. Initially C is empty. For each flow g i ∈ G, we calculate the set D which consists of all clusters whose ellipsoid defined by (8) contains g i . Suppose E(g, c) is the Euclidean distance between g and c. If D is not empty, g i is assigned to the cluster whose center has the smallest Euclidean distance with g i and the corresponding cluster center is updated; otherwise a new cluster is created. Suppose that flow g i will be assigned to cluster k, let c j k and c j k be the jth component of the center of cluster k before and after the assignment, then where p is the number of flows in cluster k before the assignment. Because of the adaptive update (9), some assignments may become unreasonable after update as some flows may become closer to other cluster centers. As a result, the algorithm processes flows in G again until an equilibrium is reached. Once a stable equilibrium is reached, small outlying clusters are identified as anomalous based on the rule where I A (T k ) is an indicator of anomaly for T k , τ ∈ [0, 1] is a prescribed detection threshold, |C| and |G| are the total Algorithm 1 ART clustering Algorithm Recalculate cluster center of T k using (9) end if end for end while central node number of clusters and flows, respectively. τ determines how small a cluster must be to be considered as anomalous, thus it influences the number of alarms. We will discuss the relationship of τ and the false alarm rate further in Section V.

IV. NETWORK SIMULATION
The lack of annotated data is a common problem in the network anomaly detection community. As a result, we developed two open source software packages to provide flow-level and packet-level validation datasets, respectively. SADIT [28] is a software package containing all the algorithms we described above. It also provides an annotated flow record generator powered by the fs [26] simulator. IMALSE [27] uses the NS3 simulator [10] for the network simulation and generates packet-level annotated data. Simulation at the packet-level takes more computation resources but can mimic certain attacks, like botnet-based attacks, in a more realistic way. We validate our algorithms with the help of these two software packages. The packets generated by IMALSE, which is of pcap format [27], are transformed into flow records first. Then the flows generated by SADIT and IMASLE are tested independently with each algorithm.
The simulated network is partitioned into an internal network with a hub and spoke topology that connects to the Internet via a gateway (Fig. 2). The internal network consists of 8 normal users (CT1-CT8) and 1 server (SRV) with some sensitive information. We monitor the traffic on the server.

A. Flow-level Anomalies
First, we generate a dataset with flow-level anomalies. The size and the transmission of the nominal flows for user i is assumed to follow a Gaussian distribution N (m i , σ 2 i ) and Poisson process with arrival rate λ i , respectively. We investigate three most common types of flow-level anomalies.
The first one mimics the scenario according to which a network intruder or unauthorized user downloads restricted data. A previously unseen user who has a large IP distance to the rest of the users starts transmission for a short period. The second one is a user i with suspicious flow size distribution characterized by a mean m a i higher than a typical value m i . Usually flows with substantially large flow size are associated with the situation when some users try to download large files from the server, which can happen when the attacker tries to download the sensitive information packed into a large file. The last one is a user increasing its flow transmission rate to an unusual value λ a i , which could be indicative of the user finding an important directory on the server and downloading, repeatedly, sensitive files within that directory.

B. Packet-level Anomalies
A second anomalous dataset is created using the tool IMALSE [27]. The nominal traffic is generated using the on-off application in NS3 [10], [27] in which the user sends packets for t on seconds and the interval between two consecutive transmission is t of f . The traffic is a Poisson process, which means the on time and off times are exponentially distributed with parameter λ on and λ of f , respectively.
We assume there is a botnet in the network. There is a botmaster controlling the bot network and a Command and Control (C&C) server issuing control commands to the bots. In our simulation, both the botmaster and C&C server are the machine INT2 in the Internet, and CT1-CT5 in the internal network have been infected as bots. We investigate a DDoS Ping flood attack in which each bot sends a lot of ping packets to the server SRV upon the request of the C&C server, aiming to exhaust the bandwidth of SRV. The attack is simulated at the packet-level and the data are then transformed into flow records using techniques described in Section II. With appropriate δ F , the t on becomes the flow duration of nominal flows and the t of f determines the flow transmission rate of nominal flows. The initiating stage of the attack is similar to the first case in the previous section. During the attack, both the flow transmission rate and the flow size of the bots may be affected. First, the flow transmission rate is increased as the bots ping SRV more frequently. Second, the ping packets have different sizes from normal network traffic. Also, consecutive ping packets may be combined together if they are sent over a short time interval. The resulting flows may be very large in size if these combinations are common or very small otherwise, depending on the attack pattern.

V. RESULTS
A. Flow-level Anomalies 1) Atypical User: Figure 3 shows the response of all methods described above when there is an atypical user trying to access the server between 1000s and 1300s. For window-based methods, the interval between the starting point of two consecutive time windows is h = 30s and the window size is chosen as w s = 200s, so there is overlap between two consecutive time windows. We also distill the user space by using K-Means clustering with 3 clusters. The quantization levels for flow size, distance to cluster and flow duration are 3, 2, 1, respectively, thus |Σ| = 18. The x-axis in all graphs corresponds to time (s) and the total simulation time is 5000s. The first two graphs depict the entropy metric in (4) and (6) of the model-free and model-based methods, respectively. For both graphs, the green dashed line is the threshold when the false alarm rate is = 0.01. The interval during which the entropy curve is above the threshold line (the red part) is the interval the method reports as abnormal. The x coordinates of the red points with a '+' marker correspond to the start point of the flow or the window the method reports as abnormal. The parameter ν for the flow 1-class SVM and window 1-class SVM is 0.002 and 0.1, respectively. The threshold τ for ART clustering is 0.05.
We can observe from Figure 3 that stochastic methods, including our model-free and model-based methods, tend to produce more stable results in the sense that they generate fewer false alarms. At the same time, the flow 1-class SVM and ART clustering methods, both of which are flow-based, can provide higher identification resolution in the sense that they can identify the suspicious flows, which is beyond the capabilities of the stochastic methods. In the window 1-class SVM method, we can tune the window size to adjust the tradeoff of resolution and stability. However, the window size in the model-free and model-based methods has to be reasonably large since the optimality of the decision rule (4) and (6) relies on the assumption of a large flow number in each window.
This observation indicates that these methods are complementary to each other. One way to combine them is to use stochastic methods and window-based deterministic methods to get a rough interval of an anomaly. Then, only the flows that are both identified as suspicious by flow-based deterministic methods and belong to the interval need to be further evaluated. The first subfigure in Figure 4 shows the Receiver Operating Characteristic (ROC) curve of the ART clustering method, which is a flow-based method, and the combination of the ART clustering and the model-free method. The ROC curve has been substantially improved after combining the two methods. The second subfigure in Figure 4 shows the relationship between the threshold τ defined in (10) and the false alarm rate. The x-axis is the false alarm rate and y-axis corresponds to the threshold. As we can see, the false alarm rate increases when the threshold increases and they are almost linearly related to each other.  2) Large File Download: Figure 5 is the output of all methods in the case where a user doubles its mean flow size between 1000s and 1300s. Again, the first two graphs show the entropy curve and threshold line of the model-free and model-based methods. The total simulation time is 5000s. The common window parameters h and w s are the same as in the previous case. The false alarm rate is = 0.01 for both model-free and model-based methods. The parameter ν for flow 1-class SVM and window 1-class SVM is 0.0015 and 0.1, respectively. τ = 0.01 for ART clustering.
3) Large Access Rate: Figure 6 shows the response of model-free, model-based, window 1-class SVM and ART clustering methods when a user suspiciously increases its access rate to 6 times of its normal value during 1000s and 1300s. The total simulation time is 2000s. The parameters for the algorithms are the same in the atypical user case.
Note that flow 1-class SVM cannot work for this type of anomaly since it is purely temporal-based. The flow itself does not change but its frequency does. There is no way to identify the frequency change by just observing the individual flows with representation in (1). ART clustering works fairly well for this case because the attacker will have larger n f (x) as it transmits more flows. Interestingly, the model-based and model-free methods can work very well since the portion of traffic originating from the attacker changes, influencing the empirical measure defined in (3) and (5). The two methods will not be effective in the very rare case when all users increase their rate by the same ratio synchronously.  Figure 7 shows the response of model-free, model-based, window 1-class SVM and flow 1-class SVM methods when there is a DDoS attack targeting SRV between 500s and 600s. The total simulation time is 900s. For window-based methods, the interval between consecutive time windows is h = 10s and the window size is w s = 100s. The false alarm rate for the model-free and model-based method is = 0.01 and ν = 0.05 for window SVM.

B. DDoS Attack
Since the nominal traffic in IMALSE is generated based on an i.i.d assumption, it is hard for the model-based method to capture a Markov model. Yet, the model-based method still detects the start and the end of the attack, during which the transitional behavior changes the most. Model-free and window 1-class SVM are more stable while the flow 1-class SVM method provides higher resolution.
The ART clustering method is also not suited to detect these type of attacks because the unsupervised learning model is based on the assumption that malicious network traffic represents a small percentage of total network traffic. A DDoS attack generates a large number of packets and without some prior knowledge of good or bad network traffic, the ART clustering algorithm cannot distinguish between the nominal and abnormal flows. It is also the reason for the relatively unsatisfactory performance of the flow 1-class SVM method. However, window 1-class SVM is not affected by this because despite the large number of abnormal flows, the number of abnormal windows is still very small.

VI. CONCLUSION
We presented five complementary approaches, based on SHT, SVM and clustering, that cover the common techniques for host-based network anomaly detection. We developed two open source software packages to provide flow-level and packet-level validation datasets, respectively. With the help of these software packages, we evaluated all methods on a simulated network mimicking typical networks in organizations. We consider three flow-level anomalies and one packet-level DDoS attack.
Through analyzing the results, we summarize the advantages and disadvantages of each method. In general, deterministic and flow-based methods, such as flow 1-class SVM and ART clustering, are more likely to have unstable results with higher false alarm rates but they can identify abnormal flows, namely they have better resolution. Stochastic and window-based methods, such as our model-free and modelbased methods, could yield more stable results and detect temporal anomalies better, but they have relatively poor resolution as they are not able to explicitly detect the anomalous network flows. In addition, deterministic and window-based methods, like window 1-class SVM offer parameters to adjust the tradeoff of resolution and stability. This observation suggests that combining the results of all, instead of just using one method, can yield better overall performance.