Lightweight and Scalable Intrusion Trace Classification Using Interelement Dependency Models Suitable for Wireless Sensor Network Environment

Abstract

We present a lightweight and scalable method for classifying network and program traces to detect system intrusion attempts. By employing interelement dependency models to overcome the independence violation problem inherent in the Naive Bayes learners, our method yields intrusion detectors with better accuracy. For efficient and lightweight counting of n-gram features without losing accuracy, we use a k-truncated generalized suffix tree (k-TGST) for storing n-gram features. The k-TGST storage mechanism enables us to scale up the classifiers, which cannot be easily achieved by Support-Vector-Machine- (SVM-) based methods that require implausible computing power and resources for accuracy. Experimental results on a set of practical benchmark datasets show that our method is scalable up to 20-gram with consistent accuracy comparable to SVMs.

1. Introduction

Data mining algorithms have been widely used for classifying program traces (i.e., sequences of system calls or sequences of network packets) in intrusion detection tasks. For example, in a host-based intrusion detection task, a program trace is defined as a sequence of system calls that the program invokes during its execution, whereas in a network-based intrusion detection task, a program trace can be defined as a sequence of network packets that the program transmits during its execution. As a preprocessing step for data mining algorithms on intrusion detection tasks, the n-gram (n consecutive system calls in a trace) approach [1] has been widely used for featurization of system call sequences [2–5].

However, those n-gram approaches suffer from three critical problems when applied to intrusion detection tasks.

• (1)

Dimensionality Issues. Since the number of distinct system calls is usually as many as about 200, the number of distinct n-gram features increases drastically as n increases. For example, the number of distinct SunOS system calls is 183, and if a 20-gram approach is used, then the number of 20-gram features will be $183^{20}$ , which is impractical for real world applications. The data mining algorithms that have nonlinear space complexity (such as Support Vector Machines (SVMs) [6, 7]) severely suffer from this problem.

(2)

Overlap of Features. When n-gram features are generated from an original trace using a fixed-length sliding window, one system call in the trace can be considered as many as n times in the worse case, in the resulting n-gram features [8, 9].

(3)

Violation of Independence Assumption. If the resulting intrusion detectors rely on the statistical independence assumption among features (e.g., Naive Bayes), the above-mentioned way of generating overlapped features systematically breaks the assumption.

Against these backgrounds, we applied interelement dependency models [8, 10] of n-gram features to intrusion detection tasks and compared their performance with those of widely used data mining algorithms such as Naive Bayes with n-gram features and those of SVM with n-gram features. To overcome the curse of dimensionality problem, we adapted the k-truncated generalized suffix tree storage mechanism [11, 12] to index system call traces and to generate counts for each n-gram in an efficient way. Since the features with more order information (i.e., longer n-gram features) from an appropriate amount of input data sets usually contribute more to classification, it is important for an intrusion detection algorithm to be scalable with the length of n-grams.

Experimental results on host-based and network-based intrusion detection benchmark data sets show that the proposed method outperforms the Naive Bayes learner with n-gram features as input, which breaks the independence assumption, on intrusion detection tasks and shows comparable accuracies and false positive rates to those of SVMs with n-gram features. With the suffix tree storage mechanism, we tested the performance of the classifiers up to 20-gram in the experiments, which indicates the advantage of scalability of the proposed combination of the interdependency model of n-gram features and suffix tree storage mechanism over the other methods. We were able to perform the experiments with n-grams much longer than 20-grams, but because of lack of data sets and overfitting, the results were not so significant.

The rest of the paper is organized as follows: Section 2 describes our method, Section 3 presents the experimental results, and Section 4 summarizes and concludes this paper.

2. Method

First of all, we introduce Naive Bayes with n-gram features (NB n-gram), interdependency models of n-Grams (IM(n)), and SVM with n-gram features (SVM n-gram). After that, we explain suffix tree mechanism which is used to store n-gram features.

Before we describe each method, we formally define the intrusion detection problem as follows: Let $\Sigma =\{s_1,s_2,s_3,\dots ,s_m\}$ be a set of system calls, where $m=|\Sigma |$ is the number of system calls. Data set D can be defined as a set of labeled sequences (i.e., program traces) $\{〈Z_i,c_i〉\mid Z_i\in {\Sigma }^{*},c_i\in \{\mathrm{0,1}\}\}$ , where $Z_i=z_1,z_2,z_3,\dots ,z_l$ is an input sequence and $c_i$ is a corresponding class label denoting 0 for “normal” label and 1 for “intrusion” label. Given the data set D, the goal of a learning algorithm is to find an intrusion detector $h:{\Sigma }^{*}\to \{\mathrm{0,1}\}$ that maximizes given criteria such as accuracy, F-1 measure, detection rate, and false positive rate.

If a probabilistic model is applied for the intrusion detector h (e.g., Naive Bayes), then the probabilistic model $P_h$ specifies for a sequence Z the probability $P_h(Z=z_1,z_2,z_3,\dots ,z_l)$ as follows.

• (1)

For each class $c_i$ , estimate the probabilities $P_h(c_i)$ using all the sequences Z coupled with $c_i$ .

(2)

For a new sequence Z, assign the class c such that

$$\begin{array}{cc}& c_h=\underset{c\in \left\{\mathrm{0,1}\right\}}{\text{argmax}}\hspace{0.17em}{P}_h\left(Z=z_1,z_2,z_3,\dots ,z_l\mid c\right)·P_h\left(c\right)\text{.}\end{array}$$

(1)

2.1. Naive Bayes Classifier

One of the important assumptions in the Naive Bayes classifier as a host-based intrusion detector is that each system call of the sequence is independent of the other system calls given the class label. Therefore, as for Naive Bayes, the classification (shown in (1)) of a new sequence will be formulated as follows:

$$\begin{array}{cc}& c_{\text{NB}}=\underset{c\in \left\{\mathrm{0,1}\right\}}{\text{argmax}}\hspace{0.17em}{P}_h\left(c\right)·\prod _i‍P_h\left(z_i\mid c\right)\text{.}\hspace{0.17em}\end{array}$$

(2)

When the Naive Bayes classifier is applied to text or protein sequence classification, it treats each document or protein sequence as a bag or set of words or letters that denotes amino acid [9, 13]. There are a few researches [15–17] that explore intrusion detection tasks with a bag or set of system calls, but most intrusion detection researches focus on the n-gram approach [4, 14, 18, 19].

2.2. Naive Bayes with n-Gram Features (NB n-Gram)

Since it is difficult to deal with variable length sequences directly, each sequence $Z\in {\Sigma }^{*}$ is mapped into a finite n-dimensional feature vector (i.e., n-gram features). In host-based intrusion detection tasks, if we want to monitor a program's behavior, we consider the program's trace as a sequence. Thus, to generate n-gram features from an input trace, a sliding window of size n is applied to the trace, moving from the beginning of the trace to the end of the trace by one system call at each step, to generate a bag of n-gram features from the trace. Then, the probabilistic model for this n-gram representation is straightforward from (2):

$$\begin{array}{cc}& c_{\text{NB}\hspace{0.17em}n\text{-gram}}=\underset{c\in \left\{\mathrm{0,1}\right\}}{\text{argmax}}\hspace{0.17em}{P}_h\left(c\right)·\prod _{i=1}^{l-n+1}‍P_h\left(z_i,\dots ,z_{i+n-1}\mid c\right)\text{,}\end{array}$$

(3)

where l is the length of the sequence.

There is one serious problem in the NB n-gram approach. When n-gram features are generated from an original trace using a sliding window, one system call in the trace can be considered and included as many as n times in the resulting n-gram features. This systematically violates the independence assumption of the Naive Bayes learning algorithm.

2.3. Interdependency Models of n-Grams (IM(n))

To overcome the previously mentioned problem, we applied interdependency models of n-grams [8, 10] for scalable n-gram-based intrusion detection. The applied method tried to explicitly model the dependencies among the elements inside an n-gram feature generated from a sequence.

Figure 1 shows the model that describes dependencies among six consecutive elements in a sequence.

Figure 1

Graphical models that incorporate the dependencies among the six consecutive elements in a sequence.

Following the Junction Tree Theorem [20], the probabilistic model for IM(n) is as follows:

$$\begin{array}{cc}& c_{\text{IM}\left(n\right)}=\underset{c\in \left\{\mathrm{0,1}\right\}}{\text{argmax}}\hspace{0.17em}\frac{{\prod }_1^{l-n+1}{P}_h\left(z_i,\dots ,z_{i+n-1}\mid c\right)}{{\prod }_2^{l-n+1}{P}_h\left(z_i,\dots ,z_{i+n-2}\mid c\right)}{P}_h\left(c\right)\text{.}\end{array}$$

(4)

From Figure 1 and (4), it can be seen that the probabilistic graphical model of IM(n) is a Markov Network where the probabilistic distribution is obtained by dividing the product of the marginals of the maximal cliques (maximally connected subgraphs) in the graph by the product of the marginals of the separators (overlaps among cliques).

Algorithm 1 shows the pseudocode of the intrusion detection algorithm using the interdependency model.

Algorithm 1: Intrusion detection algorithm with interdependency model.

IntrusionDetector( S ):

begin

 (1) Input: sequence data set $S=s_1,\dots ,s_n$ and interdependency model α as a

    probabilistic model

 (2) Learning: For each class $c_j$ , estimate probabilities $P_{\alpha }(S=s_1,\dots ,s_n)$ of $\alpha (c_j)$

    based on D that comprises the intrusion detector h

 (3) Testing: For a novel sequence $\widehat{S}=s_1,\dots ,s_n$ , predict the classification $c(\widehat{S})$ as

    follows:

        $c(\widehat{S})=\underset{c_j\in C}{\text{argmax}}\left\{P_{\alpha }(\widehat{S}=s_1,\dots ,s_n\mid c_j)P(c_j)\right\}$

end.

2.4. Support Vector Machines with n-Gram Features (SVM n-Gram)

For the comparison of IM(n)'s performance with the other data mining algorithm, we consider Support Vector Machines with n-grams as input.

It is of interest to compare IM(n) and NB n-gram with SVM n-gram, because, in contrast to Naive Bayes with n-gram features (NB n-gram), SVMs do not rely on the independence assumption between features.

However, the SVM algorithm suffers from the explosion of the number of features as n increases, because it takes at least $O(n^2)$ time and space to prepare a kernel matrix for SVM. In other words, since the SVM learning algorithm has nonlinear asymptotic complexity and due to the nature of n-gram attributes, as n increases, the number of attributes and the size of the working memory increase drastically (i.e., curse of dimensionality). In the actual experiment, because of these computational and memory requirements, we were only able to conduct the experiment of SVM n-gram for $n=1,2,$ and $3$ .

2.5. k-Truncated Suffix Tree

A suffix tree is a data structure to index a string [11]. Figure 2 shows an example suffix tree for a string “banana$”, where “$” denotes the end of the string. The number in each node represents the number of pattern occurrences. For example, in the string “banana$”, “a” occurs three times and “na” occurs twice.

Figure 2

A suffix tree of a string “banana$”. The number in each node represents the number of pattern occurrences.

When the length of a string is l, then it takes $O(l)$ time [21] to build a suffix tree for the string. Once a suffix tree is generated, then it takes $O(m)$ time to find a pattern string with length m. Also, with edge-label compression, it only needs $O(l)$ space for a suffix tree.

In practice, to store multiple strings, a generalized suffix tree is used. A generalized suffix tree is a storage that contains all suffixes of a set of strings [11]. An example of a generalized suffix tree for the strings “bagle ${\text{\$}}_1$ ” and “beagle ${\text{\$}}_2$ ” is shown in Figure 4.

Even with the suffix tree storage, it still takes a lot of memory to save the entire traces of system calls. However, in our application, it is not necessary to store a whole trace into a suffix tree. Instead, we store n-gram features into the generalized suffix tree, as shown in Figure 3, which are of interest for generating intrusion detectors.

Figure 3

A 4-truncated suffix tree of “ktruncatedsuffixtree$”.

Figure 4

A generalized suffix tree of “bagle ${\text{\$}}_1$ ” and “beagle ${\text{\$}}_2$ ”.

3. Experimental Setup and Results

To evaluate the performance of interdependency models of n-grams (IM(n)), we compared its performance with Naive Bayes (NB), Naive Bayes with n-gram features (NB n-gram), and Support Vector Machines with n-gram features (SVM n-gram). For the experiment, we chose publicly available data sets from the University of New Mexico (UNM) [14] and MIT Lincoln Lab 1998 DARPA Intrusion Detection Evaluation Data Sets (MIT LL 1998) [22].

3.1. Data Sets

3.1.1. UNM Data Sets

The University of New Mexico (UNM) provides a number of system call data sets. Each data set corresponds to a specific attack or exploit. The data sets we tested are “live lpr”, “live lpr MIT”, and “denial of service” (DoS).

In UNM system call traces, each trace is an output of one program. Sometimes, one trace has multiple processes. In such cases, we have made as many sequences as the number of processes in the original trace. Thus, multiple sequences of system calls are made from one trace if the input trace has multiple processes in it. However, most traces have only one process and usually one sequence is created for each trace. Table 1 shows the number of original traces and the number of sequences for each data set.

Table 1

The number of instances for each type of attack.

Attack	Positive	Negative	Total
Live lpr (l_lpr)	1001	1231	2232
Live lpr MIT (l_lpr.MIT)	1001	2703	3704
Denial of service (stide)	105	13726	13831

There are two different mapping files in the UNM call traces we used for the experiment. One is Sun (live lpr and live lpr.MIT), and the other is Linux (denial of service). There are old and new Sun mapping files but only one system call is added to the new mapping file, so both can be easily converted. The Sun mapping file has a few duplicate system calls (e.g., “fstat”, “stat”, etc.), but we changed them such that each system call is unique.

3.1.2. MIT LL 1998 Data Sets

In the MIT Lincoln Lab 1998 data sets [14], we used both seven weeks of training data and two weeks of testing data. The data comprises a detailed set of data files representing the state of a particular system over eight-hour daytime periods over the course of the nine weeks (seven for training and two for testing). Of interest to the experiments are the omnibus data files containing all system calls made during the collection period and the network traffic analysis files (distilled from raw network data) that identify inbound network connection attempts.

We explained the issues with cross-indexing the data files. The MIT Lincoln Lab data sets include omnibus files containing all system call traces. For each omnibus file, there is a separate, network traffic analysis data file that indicates inbound network connections to the system. Attack attempts are logged with the network data, which implies that labeling the training data requires cross-indexing this file with the system call trace file. The system call trace file identifies the source of each call using the process ID. Therefore, cross-indexing requires tracking the argument to the “exec” system call identifying the binary to be executed. Additionally, the timestamps from the network traffic analyzer do not exactly correspond to the execution timestamps from the operating system kernel. A tolerance of one second is arbitrarily chosen and permits the matching of a large majority of connection attempts with their corresponding server processes on the target system.

All processes detected that do not correspond to some network connection attempt identified in the trace are removed from consideration (since they cannot be classified), as are all calls attributed to a process ID for which an “exec” system call is not found.

As for the experimental setting, we both followed training and testing experiments as explained in the data set description and performed 10-fold cross-validation over the whole nine-week data sets.

3.2. Results

We applied the following performance measures:

$$\begin{array}{cc}& \text{Accuracy}=\frac{\text{TP}+\text{TN}}{\text{TP}+\text{TN}+\text{FP}+\text{FN}},\\ \text{False}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Positive}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{Rate}=\frac{\text{FP}}{\text{FP}+\text{TN}},\end{array}$$

(5)

where TP is the number of true positives, FP is the number of false positives, TN is the number of true negatives, and FN is the number of false negatives.

Table 2 shows accuracies and false positive rates of the three algorithms (IM(n), NB n-gram, and SVM n-gram) on the “UNM live lpr” data. IM(n) shows the best performance when n is from 6 to 8. Its performance is comparable to that of Support Vector Machines (SVMs). Overall, IM(n) shows better performance than NB n-gram.

Table 2

Comparison of accuracy (A) and false positive rate (FP) of intrusion detectors generated by IM(n), NB n-gram, and SVM n-gram on the UNM live lpr data. The accuracies and false positive rates were estimated using 10-fold cross-validation. We calculated a 99% confidence interval on the accuracies and false positive rates. Note that when $n\ge 3$ , SVM n-gram is infeasible because of computational and memory requirements.

N	IM(n)		NB n-gram		SVM n-gram
	A	FP	A	FP	A	FP
1	$\mathrm{84.09}\pm \mathrm{0.02}$	$\mathrm{28.84}\pm \mathrm{0.02}$	$\mathrm{84.09}\pm \mathrm{0.02}$	$\mathrm{28.84}\pm \mathrm{0.02}$	100.00 ± 0.00	0.00 ± 0.00
2	$\mathrm{99.78}\pm \mathrm{0.00}$	$\mathrm{0.41}\pm \mathrm{0.00}$	$\mathrm{98.30}\pm \mathrm{0.01}$	$\mathrm{3.09}\pm \mathrm{0.01}$	$\mathrm{99.96}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$
3	$\mathrm{99.96}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.01}\pm \mathrm{0.01}$	$\mathrm{1.79}\pm \mathrm{0.01}$	N/A	N/A
4	$\mathrm{99.96}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.60}\pm \mathrm{0.00}$	$\mathrm{0.73}\pm \mathrm{0.00}$	N/A	N/A
5	$\mathrm{99.96}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.82}\pm \mathrm{0.00}$	$\mathrm{0.32}\pm \mathrm{0.00}$	N/A	N/A
6–8	100.00 ± 0.00	0.00 ± 0.00	99.87 ± 0.00	0.24 ± 0.00	N/A	N/A
9-10	$\mathrm{99.96}\pm \mathrm{0.00}$	$\mathrm{0.08}\pm \mathrm{0.00}$	$\mathrm{99.82}\pm \mathrm{0.00}$	$\mathrm{0.32}\pm \mathrm{0.00}$	N/A	N/A
11–20	$\mathrm{99.96}\pm \mathrm{0.00}$	$\mathrm{0.08}\pm \mathrm{0.00}$	$\mathrm{99.78}\pm \mathrm{0.00}$	$\mathrm{0.41}\pm \mathrm{0.00}$	N/A	N/A

As for the “UNM live lpr” data, IM(n) and NB n-gram show the best performance when n is from 6 to 8. The best accuracy and false positive rate of IM(n) are 100.00 and 0.00, and the best accuracy and false positive rate of NB n-gram are 99.87 and 0.24. These results correspond to the widely known claim that “six is the magic number” [23]. However, for the other data sets (“UNM live lpr MIT” and “UNM denial of service”) we have tested, the claim does not always hold.

Table 3 shows the results of the three algorithms for UNM live lpr MIT data. When n is from 17 to 20, IM(n) shows the best performance (accuracy is 99.97 and false positive rate is 0.00) over SVM (accuracy is 99.95 and false positive rate is 0.00) and NB n-gram (accuracy is 93.49 and false positive rate is 8.92).

Table 3

Comparison of accuracy (A) and false positive rate (FP) of intrusion detectors generated by IM(n), NB n-gram, and SVM n-gram on UNM live lpr MIT data. The accuracies and false positive rates were estimated using 10-fold cross-validation. We calculated a 99% confidence interval on the accuracies and false positive rates. Note that when $n\ge 3$ , SVM n-gram is infeasible because of computational and memory requirements.

N	IM(n)		NB n-gram		SVM n-gram
	A	FP	A	FP	A	FP
1	$\mathrm{54.56}\pm \mathrm{0.02}$	$\mathrm{62.26}\pm \mathrm{0.02}$	$\mathrm{54.56}\pm \mathrm{0.02}$	$\mathrm{62.26}\pm \mathrm{0.02}$	$\mathrm{99.83}\pm \mathrm{0.00}$	$\mathrm{0.14}\pm \mathrm{0.00}$
2	$\mathrm{96.76}\pm \mathrm{0.01}$	$\mathrm{4.44}\pm \mathrm{0.01}$	$\mathrm{78.75}\pm \mathrm{0.02}$	$\mathrm{29.12}\pm \mathrm{0.02}$	99.95 ± 0.00	0.00 ± 0.00
3	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{86.23}\pm \mathrm{0.01}$	$\mathrm{18.87}\pm \mathrm{0.02}$	N/A	N/A
4	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{89.28}\pm \mathrm{0.01}$	$\mathrm{14.69}\pm \mathrm{0.02}$	N/A	N/A
5	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{91.17}\pm \mathrm{0.01}$	$\mathrm{12.10}\pm \mathrm{0.01}$	N/A	N/A
6	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{91.77}\pm \mathrm{0.01}$	$\mathrm{11.28}\pm \mathrm{0.01}$	N/A	N/A
7	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{91.85}\pm \mathrm{0.01}$	$\mathrm{11.17}\pm \mathrm{0.01}$	N/A	N/A
8	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{91.98}\pm \mathrm{0.01}$	$\mathrm{10.99}\pm \mathrm{0.01}$	N/A	N/A
9	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{92.09}\pm \mathrm{0.01}$	$\mathrm{10.84}\pm \mathrm{0.01}$	N/A	N/A
10	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{92.04}\pm \mathrm{0.01}$	$\mathrm{10.91}\pm \mathrm{0.01}$	N/A	N/A
11	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{92.33}\pm \mathrm{0.01}$	$\mathrm{10.51}\pm \mathrm{0.01}$	N/A	N/A
12	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{92.68}\pm \mathrm{0.01}$	$\mathrm{10.03}\pm \mathrm{0.01}$	N/A	N/A
13	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{92.85}\pm \mathrm{0.01}$	$\mathrm{9.80}\pm \mathrm{0.01}$	N/A	N/A
14	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{92.95}\pm \mathrm{0.01}$	$\mathrm{9.66}\pm \mathrm{0.01}$	N/A	N/A
15	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{93.17}\pm \mathrm{0.01}$	$\mathrm{9.36}\pm \mathrm{0.01}$	N/A	N/A
16	$\mathrm{99.95}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{93.28}\pm \mathrm{0.01}$	$\mathrm{9.21}\pm \mathrm{0.01}$	N/A	N/A
17	99.97 ± 0.00	0.00 ± 0.00	$\mathrm{93.30}\pm \mathrm{0.01}$	$\mathrm{9.17}\pm \mathrm{0.01}$	N/A	N/A
18	99.97 ± 0.00	0.00 ± 0.00	$\mathrm{93.36}\pm \mathrm{0.01}$	$\mathrm{9.10}\pm \mathrm{0.01}$	N/A	N/A
19-20	99.97 ± 0.00	0.00 ± 0.00	93.49 ± 0.01	8.92 ± 0.01	N/A	N/A

In Table 4, which is for the UNM denial of service data, we can see that SVM with 2-grams shows the best performance (accuracy is 99.99 and false positive rate is 0.00), but the difference from the results of IM(n) is very marginal (accuracy is 99.93 and false positive rate is 0.00). Moreover, during the training stage, SVM learns its discriminative model by the Sequential Minimal Optimization algorithm [24], which takes more than several hours. In contrast, IM(n) takes only about one or two minutes and its performance is comparable to that of SVM.

Table 4

Comparison of accuracy (A) and false positive rate (FP) of intrusion detectors generated by IM(n), NB n-gram, and SVM n-gram on the UNM denial of service data. The accuracies and false positive rates were estimated using 10-fold cross-validation. We calculated a 99% confidence interval on the accuracies and false positive rates. Note that when $n\ge 3$ , SVM n-gram is infeasible because of computational and memory requirements.

N	IM(n)		NB n-gram		SVM n-gram
	A	FP	A	FP	A	FP
1	$\mathrm{98.69}\pm \mathrm{0.00}$	$\mathrm{0.92}\pm \mathrm{0.00}$	$\mathrm{98.69}\pm \mathrm{0.00}$	$\mathrm{0.92}\pm \mathrm{0.00}$	$\mathrm{99.98}\pm \mathrm{0.00}$	$\mathrm{0.01}\pm \mathrm{0.00}$
2	$\mathrm{99.27}\pm \mathrm{0.00}$	$\mathrm{0.01}\pm \mathrm{0.00}$	$\mathrm{99.24}\pm \mathrm{0.00}$	$\mathrm{0.04}\pm \mathrm{0.00}$	99.99 ± 0.00	0.00 ± 0.00
3	$\mathrm{99.24}\pm \mathrm{0.00}$	$\mathrm{0.01}\pm \mathrm{0.00}$	$\mathrm{99.06}\pm \mathrm{0.00}$	$\mathrm{0.69}\pm \mathrm{0.00}$	N/A	N/A
4	$\mathrm{99.23}\pm \mathrm{0.00}$	$\mathrm{0.01}\pm \mathrm{0.00}$	$\mathrm{99.18}\pm \mathrm{0.00}$	$\mathrm{0.68}\pm \mathrm{0.00}$	N/A	N/A
5	$\mathrm{99.23}\pm \mathrm{0.00}$	$\mathrm{0.01}\pm \mathrm{0.00}$	$\mathrm{99.24}\pm \mathrm{0.00}$	$\mathrm{0.65}\pm \mathrm{0.00}$	N/A	N/A
6	$\mathrm{99.23}\pm \mathrm{0.00}$	$\mathrm{0.01}\pm \mathrm{0.00}$	$\mathrm{99.32}\pm \mathrm{0.00}$	$\mathrm{0.63}\pm \mathrm{0.00}$	N/A	N/A
7	$\mathrm{99.24}\pm \mathrm{0.00}$	$\mathrm{0.01}\pm \mathrm{0.00}$	$\mathrm{99.40}\pm \mathrm{0.00}$	$\mathrm{0.59}\pm \mathrm{0.00}$	N/A	N/A
8	$\mathrm{99.25}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.52}\pm \mathrm{0.00}$	$\mathrm{0.47}\pm \mathrm{0.00}$	N/A	N/A
9	$\mathrm{99.36}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.66}\pm \mathrm{0.00}$	$\mathrm{0.33}\pm \mathrm{0.00}$	N/A	N/A
10	$\mathrm{99.65}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.66}\pm \mathrm{0.00}$	$\mathrm{0.33}\pm \mathrm{0.00}$	N/A	N/A
11	$\mathrm{99.80}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.66}\pm \mathrm{0.00}$	$\mathrm{0.33}\pm \mathrm{0.00}$	N/A	N/A
12	$\mathrm{99.84}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.66}\pm \mathrm{0.00}$	$\mathrm{0.33}\pm \mathrm{0.00}$	N/A	N/A
13	$\mathrm{99.87}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.66}\pm \mathrm{0.00}$	$\mathrm{0.33}\pm \mathrm{0.00}$	N/A	N/A
14	$\mathrm{99.88}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.67}\pm \mathrm{0.00}$	$\mathrm{0.31}\pm \mathrm{0.00}$	N/A	N/A
15	$\mathrm{99.89}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.67}\pm \mathrm{0.00}$	$\mathrm{0.31}\pm \mathrm{0.00}$	N/A	N/A
16	$\mathrm{99.89}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.68}\pm \mathrm{0.00}$	$\mathrm{0.31}\pm \mathrm{0.00}$	N/A	N/A
17	$\mathrm{99.91}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.69}\pm \mathrm{0.00}$	$\mathrm{0.30}\pm \mathrm{0.00}$	N/A	N/A
18	$\mathrm{99.92}\pm \mathrm{0.00}$	$\mathrm{0.00}\pm \mathrm{0.00}$	$\mathrm{99.69}\pm \mathrm{0.00}$	$\mathrm{0.30}\pm \mathrm{0.00}$	N/A	N/A
19-20	99.93 ± 0.00	0.00 ± 0.00	99.69 ± 0.00	0.30 ± 0.00	N/A	N/A

In Table 5, we show the results of training and testing experiments on the MIT LL 1998 data sets. In these training and testing experiments, we use predefined training data sets of the MIT LL 1998 data sets for learning intrusion detectors and use predefined testing data sets for evaluating the intrusion detectors. Notice that we do not calculate confidence intervals because it is infeasible to obtain distributions from the train/test setting.

Table 5

Comparison of accuracy (A) and false positive rate (FP) of intrusion detectors generated by IM(n), NB n-gram, and SVM n-gram on MIT LL 1998 data. We followed the train/test setting specified in the data set description. Note that when $n\ge 4$ , SVM n-gram is infeasible because of computational and memory requirements.

N	IM(n)		NB n-gram		SVM n-gram
	A	FP	A	FP	A	FP
1	36.57	62.49	36.57	62.49	81.55	7.45
2	80.33	0.06	80.36	0.03	80.53	8.28
3	80.35	0.03	80.35	0.05	80.28	9.35
4	80.37	0.00	80.34	0.03	N/A	N/A
5	80.33	0.05	80.35	0.03	N/A	N/A
6	80.33	0.05	80.30	0.08	N/A	N/A
7	80.37	0.04	78.50	2.89	N/A	N/A
8	79.51	1.11	78.45	2.95	N/A	N/A
9	79.44	1.20	75.22	6.93	N/A	N/A
10	75.99	5.50	75.12	7.07	N/A	N/A
11	75.93	5.57	74.99	7.27	N/A	N/A
12	75.93	5.57	75.05	7.29	N/A	N/A
13	75.93	5.58	74.85	7.56	N/A	N/A
14	75.91	5.59	71.11	12.84	N/A	N/A
15	75.79	5.76	65.10	25.30	N/A	N/A
16	76.97	6.26	52.47	42.21	N/A	N/A
17	72.23	12.46	50.39	44.82	N/A	N/A
18	71.98	12.67	50.42	44.77	N/A	N/A
19	71.99	12.66	50.36	44.88	N/A	N/A
20	74.95	9.06	49.88	44.93	N/A	N/A

It can be seen that SVM with 1-gram shows the best performance on the accuracy with 81.55, but the false positive rate is 7.45. The difference from the results of IM(4) is marginal (accuracy is 80.37 and false positive rate is 0.00). Moreover, the false positive rate of IM(4) is far better than that of SVM with 1-gram. As discussed, the total learning and testing time of SVM is more than several hours, while, in contrast, it takes about one or two minutes for all the IM(n) models and their performances in general are comparable to those of SVMs.

In Figure 5, we show the Receiver Operating Characteristic (ROC) curves of train/test experiments on the MIT LL 1998 data sets. Area under the curve (AUC) of IM(4) is 0.7290, AUC of NB 2-gram is 0.6654, and AUC of SVM 1-gram is 0.7043. Thus, in terms of ROC, IM(4) outperforms SVM 1-gram.

Figure 5

Receiver Operating Characteristic (ROC) curves of interelement dependency model of 4-gram (IM(4), $\text{AUC}=0.7290$ ), Naive Bayes of 2-gram (NB 2-gram, $\text{AUC}=0.6654$ ), and Support Vector Machines of 1-gram (SVM 1-gram, $\text{AUC}=0.7043$ ) on the MIT LL 1998 data estimated with the train/test setting.

In Table 6, we show the results of 10-fold cross-validation on the MIT LL 1998 data sets.

Table 6

Comparison of accuracy (A) and false positive rate (FP) of intrusion detectors generated by IM(n), NB n-gram, and SVM n-gram on MIT LL 1998 data. The accuracies and false positive rates were estimated using 10-fold cross-validation. We calculated a 99% confidence interval on the accuracies and false positive rates. Note that when $n\ge 3$ , SVM n-gram is infeasible because of computational and memory requirements.

$N\mathrm{\hspace{0.17em}\hspace{0.17em}}$	IM(n)		NB n-gram		SVM n-gram
	A	FP	A	FP	A	FP
1	$\mathrm{32.55}\pm \mathrm{0.37}$	$\mathrm{88.55}\pm \mathrm{0.25}$	$\mathrm{32.55}\pm \mathrm{0.37}$	$\mathrm{88.55}\pm \mathrm{0.25}$	$\mathrm{91.83}\pm \mathrm{0.21}$	$\mathrm{0.03}\pm \mathrm{0.01}$
2	$\mathrm{74.54}\pm \mathrm{0.34}$	$\mathrm{26.17}\pm \mathrm{0.34}$	$\mathrm{60.61}\pm \mathrm{0.38}$	$\mathrm{41.91}\pm \mathrm{0.38}$	$\mathrm{92.45}\pm \mathrm{0.21}$	$\mathrm{4.46}\pm \mathrm{0.16}$
3	$\mathrm{48.33}\pm \mathrm{0.39}$	$\mathrm{56.18}\pm \mathrm{0.39}$	$\mathrm{46.97}\pm \mathrm{0.39}$	$\mathrm{57.44}\pm \mathrm{0.39}$	93.34 ± 0.19	4.40 ± 0.16
4	$\mathrm{85.39}\pm \mathrm{0.28}$	$\mathrm{13.84}\pm \mathrm{0.27}$	$\mathrm{50.73}\pm \mathrm{0.39}$	$\mathrm{53.29}\pm \mathrm{0.39}$	N/A	N/A
5	$\mathrm{92.17}\pm \mathrm{0.21}$	$\mathrm{6.02}\pm \mathrm{0.19}$	$\mathrm{56.28}\pm \mathrm{0.39}$	$\mathrm{47.08}\pm \mathrm{0.39}$	N/A	N/A
6	$\mathrm{93.12}\pm \mathrm{0.20}$	$\mathrm{4.97}\pm \mathrm{0.17}$	$\mathrm{60.77}\pm \mathrm{0.38}$	$\mathrm{42.02}\pm \mathrm{0.38}$	N/A	N/A
7	$\mathrm{93.17}\pm \mathrm{0.20}$	$\mathrm{3.97}\pm \mathrm{0.15}$	$\mathrm{76.68}\pm \mathrm{0.33}$	$\mathrm{24.54}\pm \mathrm{0.33}$	N/A	N/A
8	$\mathrm{93.23}\pm \mathrm{0.20}$	$\mathrm{3.96}\pm \mathrm{0.15}$	$\mathrm{77.58}\pm \mathrm{0.33}$	$\mathrm{22.43}\pm \mathrm{0.33}$	N/A	N/A
9	$\mathrm{93.22}\pm \mathrm{0.20}$	$\mathrm{3.94}\pm \mathrm{0.15}$	$\mathrm{78.74}\pm \mathrm{0.32}$	$\mathrm{21.18}\pm \mathrm{0.32}$	N/A	N/A
10	93.24 ± 0.20	3.93 ± 0.15	$\mathrm{79.33}\pm \mathrm{0.32}$	$\mathrm{20.532}\pm \mathrm{0.32}$	N/A	N/A
11	$\mathrm{93.24}\pm \mathrm{0.20}$	$\mathrm{3.94}\pm \mathrm{0.15}$	$\mathrm{78.71}\pm \mathrm{0.32}$	$\mathrm{21.92}\pm \mathrm{0.32}$	N/A	N/A
12	$\mathrm{93.37}\pm \mathrm{0.19}$	$\mathrm{4.00}\pm \mathrm{0.15}$	$\mathrm{78.64}\pm \mathrm{0.32}$	$\mathrm{21.54}\pm \mathrm{0.32}$	N/A	N/A
13	$\mathrm{91.65}\pm \mathrm{0.22}$	$\mathrm{1.44}\pm \mathrm{0.09}$	$\mathrm{82.43}\pm \mathrm{0.30}$	$\mathrm{12.55}\pm \mathrm{0.26}$	N/A	N/A
14	$\mathrm{91.39}\pm \mathrm{0.22}$	$\mathrm{1.73}\pm \mathrm{0.10}$	86.21 ± 0.27	8.12 ± 0.21	N/A	N/A
15	$\mathrm{91.35}\pm \mathrm{0.22}$	$\mathrm{1.77}\pm \mathrm{0.10}$	$\mathrm{85.09}\pm \mathrm{0.28}$	$\mathrm{14.54}\pm \mathrm{0.27}$	N/A	N/A
16	$\mathrm{91.27}\pm \mathrm{0.22}$	$\mathrm{2.36}\pm \mathrm{0.12}$	$\mathrm{85.10}\pm \mathrm{0.28}$	$\mathrm{13.92}\pm \mathrm{0.27}$	N/A	N/A
17	$\mathrm{91.50}\pm \mathrm{0.22}$	$\mathrm{5.39}\pm \mathrm{0.18}$	$\mathrm{85.24}\pm \mathrm{0.28}$	$\mathrm{13.20}\pm \mathrm{0.26}$	N/A	N/A
18	$\mathrm{91.42}\pm \mathrm{0.22}$	$\mathrm{4.98}\pm \mathrm{0.17}$	$\mathrm{85.37}\pm \mathrm{0.28}$	$\mathrm{13.03}\pm \mathrm{0.26}$	N/A	N/A
19	$\mathrm{91.47}\pm \mathrm{0.22}$	$\mathrm{5.41}\pm \mathrm{0.18}$	$\mathrm{85.54}\pm \mathrm{0.27}$	$\mathrm{12.83}\pm \mathrm{0.26}$	N/A	N/A
20	$\mathrm{91.46}\pm \mathrm{0.22}$	$\mathrm{5.43}\pm \mathrm{0.18}$	$\mathrm{85.68}\pm \mathrm{0.27}$	$\mathrm{13.87}\pm \mathrm{0.27}$	N/A	N/A

It can be seen that SVM with 3-grams shows the best performance with the accuracy 93.34 and the false positive rate 4.40. Again, the difference from the results of IM(n) is marginal (accuracy is 93.24 and false positive rate is 3.93). Moreover, the running time of SVM 3-grams is more than a week for learning and testing, whereas the running time of IM(n) is less than two minutes and the performance of IM(n) is comparable to that of SVM.

In Figure 6, we show the Receiver Operating Characteristic (ROC) curves of train/test experiments on the MIT LL 1998 data sets. Area Under the Curve (AUC) of IM(10) is 0.7742, AUC of NB 2-gram is 0.5271, and AUC of SVM 1-gram is 0.8729. Thus, in terms of ROC, SVM 1-gram shows the best performance among the three.

Figure 6

Receiver Operating Characteristic (ROC) curves of interelement dependency model of 10-gram (IM(10), $\text{AUC}=0.7742$ ), Naive Bayes of 14-gram (NB 14-gram, $\text{AUC}=0.5271$ ), and Support Vector Machines of 3-gram (SVM 3-gram, $\text{AUC}=0.8729$ ) on MIT LL 1998 data estimated using 10-fold cross-validation.

To show the big picture of comparing IM(n) and NB n-gram, in Figure 7, we show ROC curves of the train/test experiments on the MIT LL 1998 data sets, when $2\le n\le 17$ .

Figure 7

ROC curves of the train/test experiments on the MIT LL 1998 data sets, when $2\le n\le 17$ .

4. Conclusion

4.1. Related Work

Peng and Schuurmans [8] introduced n-gram augmented Naive Bayes and applied their algorithms to text classification. Silvescu et al. [10] proposed interelement dependency models which are similar to n-gram-augmented Naive Bayes. However, to the best of our knowledge, there has been no research on application of interelement dependency models for intrusion detection tasks.

Rieck and Laskov [4] used language models to detect unknown network attacks. They used a trie data structure [25, 26] to compute the similarity between two traces. The generalized suffix tree we used is more advantageous for storing n-gram features in that it does not take constant time to find a substring in a trie data structure. We performed our experiments with n ranging from 1 to 20, whereas Rieck and Laskov did the experiments when n is only 1, 3, and 5.

Most intrusion detection research focuses on the n-gram approach [4, 14, 18, 19]. However, there have been a few research efforts [15–17] that explore intrusion detection tasks with a bag or set of system calls. Liao and Vemuri [15] applied the K-Nearest Neighbor text classification method to intrusion detection tasks. Kang et al. [16] proposed a bag of system calls representation for intrusion detection. They performed various experiments for misuse detection and anomaly detection and showed that a bag of system calls representation is effective for misuse detection. Liu et al. [17] compared different system call feature representations and concluded that system call alone is not sufficient for detecting insider threats. Our work extends the representation to n-gram and shows that the resulting intrusion detectors are more accurate than n-gram features in terms of accuracy and false positive rate.

Forrest et al. [18] devised a Sequence Time-Delay Embedding (STIDE) intrusion detector which takes the n-gram approach with a few thresholds. Tan and Maxion [23] tried to define the operational limit of STIDE and concluded that 6-gram is enough for anomaly detection. Our work shows that the interelement dependency model (IM(n)) is more accurate than the n-gram approach and, for some attack types (UNM live lpr MIT and UNM denial of service), six is not always the magic number.

4.2. Summary and Future Work

We discussed an application of interelement dependency models to n-grams stored in a k-truncated generalized suffix tree (k-TGST) directly to classify intrusive sequences. We evaluated the performance of our method with those of Naive Bayes and Support Vector Machines (SVMs) with n-gram features by the experiments on intrusion detection benchmark data sets.

Experimental results on the University of New Mexico (UNM) benchmark data sets and MIT Lincoln Lab 1998 DARPA intrusion detection evaluation data sets show that our method, which solves the problem of independence violation that happens when n-gram-features are directly applied to Naive Bayes (i.e., Naive Bayes with n-gram features), yields intrusion detectors with higher accuracy than those from Naive Bayes with n-gram features and shows comparable accuracy to those from SVM with n-gram features.

For scalable and lightweight counting of n-gram features, we use the k-truncated generalized suffix tree mechanism for storing n-gram features. With this mechanism, we tested the performance of the classifiers up to 20-gram in our experiment, which illustrates the scalability and accuracy of n-gram augmented Naive Bayes with the k-truncated generalized suffix tree storage mechanism.

As for future work, we plan to apply n-gram representation to system call arguments [27], because system call arguments are important for accurate intrusion detection. Since there has been a lot of research on n-gram approaches, it is of interest to devise an n-gram representation where each element is the audit record data structure (i.e., system call and its arguments). However, there have been no researches we are aware of for the application of n-gram representation for the audit record data structure.