Introduction

Three criteria are important for computer systems security: confidentiality, integrity and availability. Computer security is defined as a protection against threads for these criteria. The major manners of computer security are techniques like user authentication, data encryption, avoiding programming errors and firewalls. They are known as first line of defense. The last line of defense is used Intrusion Detection System (IDS). An Intrusion Detection System is software application (device respectively) that monitors network and system activities for malicious attempts, threads or policy violations and produces reports and statistics. Several machine-learning paradigms including soft computing approach [2], neural networks and fuzzy inference system [11], genetic algorithms [14], Bayesian network, matrix factorization approach [16], multivariate adaptive regression splines etc. have been investigated for the design of IDS. In this paper we investigate and evaluate the performance of Farthest First Traversal, K-means, COBWEB/CLASSIT clustering algorithms and classification via Support Vector Machines. The motivation for using the clustering algorithms and SVM is to improve the accuracy of the Intrusion Detection System.

Clustering Algorithms and Their Classification

Cluster analysis is the process of grouping the objects (usually represented as a vector of measurements, or a point in a multidimensional space) so that the objects of one cluster are similar to each other whereas objects of different clusters are dissimilar.

Clustering is the unsupervised classification of objects (observations, data items, instances, cases, patterns, or feature vectors) into groups, clusters. In [4] author cite that from a machine learning perspective, clusters correspond to hidden patterns, the search for clusters is unsupervised learning, and the resulting system represents a data concept. Therefore, clustering is unsupervised learning of a hidden data concept.

The applications of clustering often deal with large datasets and data with many attributes. Clustering is related to many other fields. The classic introduction to clustering in pattern recognition is given in [7]. Machine learning clustering algorithms were applied to image segmentation and computer vision [12].

Classification of Clustering Algorithms

The various clustering algorithms can be classified according to how they create clusters of objects. Such division of clustering algorithms is shown in Fig. 1.

For our intention of using the clustering algorithms in an IDS, we need algorithms that can determine the jurisdiction of the object X to cluster, even if the object X was not included in the set of objects, from which we generate clusters. For this purpose we chose the algorithms K-means, Farthest First Traversal (they are partitional algorithms) and Cobweb/CLASSIT (this is a conceptual clustering algorithm).

Partitional Algorithms Partitional algorithms divide the objects into several disjoint sets and creates a one level of non-overlapping clusters. But the problem is to determine how many clusters has algorithm detect.

Algorithms of Conceptual Clustering

Algorithms of conceptual clustering create by incremental way, the structure of the data by division of observed objects into subclasses. The result of these algorithms is a classification tree. Each node of the tree contains the objects of its child nodes, so root of this tree contains a all objects. According to the above classification are a these algorithms hierarchical, incremental algorithms that combine both -aggregation and division approach.

Farthest First Traversal

Farthest first traversal (FFT) algorithm is partitional clustering algorithm. This algorithm first select K objects as the centers of clusters and then assign other objects into the cluster (according to measure of dissimilarity to centers of the clusters). The first center of cluster is chosen randomly, the second center of cluster as most dissimilar to first center of cluster and every other center of cluster is chosen as the one whose value of measure of dissimilarity [9] to the previously selected centers of the clusters is greatest.

K-means

Algorithm K-means, according to the classification above is partitional clustering algorithm. The main idea of the algorithm is to find K centers (one for each cluster) of clusters. The question is, how choose these centers of clusters, because this choice will significantly affect the resulting clusters. The best would be to pick center of cluster least similar to each other. The next step is assign each object from data set to the center of cluster, to which is most similar. Once this occurs, the next step in the classification is to determine the new center of each cluster (centers are derived from clusters of objects). Again, is performed the classification of objects into different clusters according to their dissimilarity [9] with new centers of clusters. These steps are repeated until we find out that centers of clusters no longer change or until is achieved maximum number of repetitions.

COBWEB/CLASSIT

This incremental clustering algorithm creates a hierarchical structure of clusters by using four operators (operator for creating a new cluster, inserting an object into an existing cluster, union of two clusters into one cluster and splitting cluster into two clusters) [8] and the categorization utility [15]. When processing object into the cluster is always used one of the operators, but always are tested all four operators and categorization utility evaluate distribution of clusters after applying one of the operator. Finally, as the resulting distribution is chosen distribution that was evaluated (by using a categorization utility) as the best.

3 Classification SVM of type 1 (C-SVM) and their parameters

1 2 w 2 + C i ε i (1)

with respect to: 1

− ε i − y i (w • x i + b) ≤ 0, −ε i ≤ 0, i = 1, 2 . . . , m

Regardless of having some elements misclassified (Fig. 2) it is possible to balance between the incorrectly classified instances and the width of the separating margin. In this context, the positive slack variables ε i and the penalty parameter C are introduced. Slacks represents the distances of misclassified points to the initial hyper-plane, while parameter C models the penalty for misclassified training points, that trades-off the margin size for the number of erroneous classifications (bigger the C smaller the number of misclassifications and smaller the margin). The goal is to find a hyper-plane that minimizes misclassification errors while maximizing the margin between classes. This optimization problem is usually solved in its dual form (dual space of Lagrange multipliers):

w * = m i=1 α i y i x i(2)

where C ≥ α i ≥ 0, i = 1, . . . , m, and where w * is a linear combination of training examples for an optimal hyper-plane. However, it can be shown that w * represents a linear combination of Support Vectors x i for which the corresponding α i Langrangian multipliers are non-zero values. Support Vectors for which C > α i > 0 condition holds, belong either to h 1 or h −1 . Let x a and x b be two such Support Vectors (C > α a , α b > 0) for which y a = 1 and y b = −1. Now b could be calculated from b * = 0.5w * (x a + x b ), so that classification (decision) function finally becomes:

f (x) = sgn m i=1 α i y i (x i • x) + b *(3)

To solve non-linear classification , one can propose the mapping of instances to a so-called feature space of very high dimension: ϕ : R n → R d , n d i.e. x → ϕ(x). The basic idea of this mapping into a high dimensional space is to transform the non-linear case into linear and then use the general algorithm already explained above Eqs. (1), (2), and (3). In such space, dot-product from Eq. (3) transforms into ϕ(x i ) • ϕ(x). A certain class of functions called kernels [6] for which k(x, y) = ϕ(x) • ϕ(y) holds, are called kernels. They represent dot-products in some high dimensional dot-product spaces (feature spaces), and yet could be easily recomputed into the original space. As example was chosen a Radial Basis Function Eq. ( 4), also known as Gaussian kernel [1], and was one of implemented kernels in the experimenting procedure.

k(x, y) = exp(−γ x − y 2 )(4)

Now Eq. ( 3) becomes:

f (x) = sgn m i=1 α i y i k(x i • x) + b *(5)

After removing all training data that are not Support Vectors and retraining the classifier, the same result would be obtained [6] by applying the function above. Thus, one depicted, Support Vectors could replace the entire training set, which is the central idea of SVM implementation.

Experiments

The data used for training and testing was prepared by the Agency DARPA intrusion detection evaluation program in 1998 at MIT Lincoln Labs [13]. Experiments were performed on a collection containing five pairs of data sets: the learning set (5092 vectors of 42 attributes) and testing set (6890 vectors of 42 attributes). Each pair represents a learning and testing data for one type of five classes of network attacks. Individual vectors describing the network traffic are described by 41 attributes (range 0 − 1, is therefore not necessary to normalization). The 42 nd attribute was used in learning process. The attribute determines type of network attack in the question. In the case of testing, the existence of the attribute was neglected. We measure only classification accuracy of the vector, that describes the network attack.

Classification Using SVM type 1 (C-SVM)

It is necessary to determine the appropriate combination of parameters C and γ for better efficiency. In our experiment, the parameter C is in the range of 2 −5 and 2 15 in increments of powers of 2 and a parameter γ is in the range of 2 −15 and 2 3 in increments of powers of 2. We used 110 combinations of parameters C γ in total. In the case of same results of prediction with different parameters C and γ, the combination of parameters with the lowest time-intensive calculation model was chosen. In Tables 1,2, 3, and 4 is possible to see the best result combination.

The four most utilized kernel functions (linear, polynomial, RBF and sigmoid) was used for process of learning. As technology, we used library LibSVM [5].

Classification with Algorithm Farthest First Traversal

During experiments with the algorithm Farthest First Traversal we tried to reveal the effect of number of generated clusters on success rate of the classification of network traffic, and on training time. The measure used by this algorithm was cosine measure. Tables 5 and 6 shows results of each experiments with algorithm FFT. Of these it is possible to deduce that the time of training increases with the number of generated clusters. We tried to optimize this algorithm by using data structure KD-tree. Training time of this algorithm with and without using of KD-tree is shown in Tables 5 and 6. As you can see in the Tables 5 and 6 training time of this algorithm with using KD-tree was reduced by almost half. Table 7 presents the results of the algorithm FFT with using a KD-tree for each class of attack.

Classification with Algorithm K-means

During experiments with algorithm K-means we tried to reveal the influence of the number of generated clusters on training time and success rate of the network traffic classification. The measure that was used by this algorithm was cosine measure. In Tables 8, 9 and 10 are shown results for each experiment. Of these it is possible to deduce that the time of training is increasing with the number of generated clusters. We tried to optimize this algorithm by using data structure KD-tree. Training time of this algorithm with and without using of KD-tree is shown in Tables 8 and 9. As you can see in the Tables 8 and 9, training time of this algorithm with using KD-tree not declined as significantly as at algorithm FFT. For certain number of generated clusters was training time even worse than at algorithm without using KD-tree. This is due overhead of creating KD-tree in each iteration of the algorithm and for a small number of generated clusters is more effective search cluster, where object fall, sequentially than by using KD-tree. Table 10 presents the results of algorithm K-means using a KD-tree for each class of attack.

Conclusion

In this paper we have described the method for the illustrated prediction accuracy by using clustering algorithms and SVM in the IDS. In Table 13 for each used algorithm is shown success rate for each class of attack. The best average success rate has SVM algorithm, more than 99% (best of all is algorithm SVM that is using the RBF kernel, it has a success rate 99.722%). The average success rate of other algorithms was between 91.228% and 98.998%. It will be useful to compare these two methods on other document collections. In our future work we will investigate other kernel functions to search for better attacks prediction in the IDS, SVM paralelization and optimalization clustering algorithms.