PCA-ICA Ensembled Intrusion Detection System by Pareto-Optimal Optimization

INTRODUCTION

Intrusion Detection Systems (IDS) is to recognize and notify the users` various security events, e.g., incidents and anomalies, which can be observed from users` behaviors. The challenge for an IDS is how to discover a users or programs behavior from large audit data. Machine learning approaches were successfully applied to intrusion detection due to their learning abilities. These approaches including but not limited to Artificial Neural Network (ANN) (Verwoerd and Hunt 2002; Joo et al., 2003; Zhang et al., 2003), Artificial Immune (Aickelin et al., 2004; Harmer et al., 2002), Markov Model (Ye et al., 2001; Du et al., 2004), Support Vector Machines (Mukkamala and Sung, 2003; Chen et al., 2005), are being used to build IDS.

In recent years, Support Vector Machine (SVM) is gaining much popularity as one of those effective methods for machine learning (Scholkopf et al., 1997). It has been found that SVMs perform better than neural networks for intrusion classifications (Sung and Mukkamala, 2004). Moreover, SVM is more suitable for intrusion detection, for it is faster while training (Mukkamala and Sung, 2003), independent of data dimension and can learn incrementally (Ralaivola and D`Alche-Buc, 2001).

Whereas, in the former studies (Gu et al., 2005), we found that false negative error is very high in intrusion detection by standard SVM algorithm. False negative error is incurred when the IDS does not function properly or mistakenly ignores an attack (Joo et al., 2003; Iheagwara et al., 2004). The cost of false negative error is higher than that of false positive error, which means IDS misinterprets normal packets or activities as attacks, because it reflects the possibility that the system is threatened (Joo et al., 2003; Iheagwara et al., 2004).

An intrusion detection ensemble system is presented in this study, which investigated two feature extract techniques, Principal Component Analysis (PCA) and Independent Component Analysis (ICA) and SVM for classification. We discovered that PCA feature extraction had a low false positive error and a high false negative error and ICA feature extraction was opposite. Whereas, to combine these two costs into a single scalar objective function, we need incorporating a priori information into the aggregation method, which is a difficult task. Therefore, the multi-object optimization technology is adopted to obtain Pareto-front solutions. The final solution set is presented to user for estimation.

PCA-ICA ENSEMBLED IDS

For an intrusion system, when false negative error occurs, this means that the attack will succeed and the target resource will be damaged. In present experiment, standard SVM has a high false negative error, which is a big threat to the security of the system. The reason might be the complicated relativity among the features. Feature extraction is an unsupervised approach that aims to search the proper features in data. So the features extracted are likely to better reflect the essential characteristics of intrusion.

In this study, we have investigated the intrusion detection algorithm based on PCA and ICA for feature extraction, respectively.

Fig. 1:	Structure model of intrusion detection ensemble system

PCA is a multivariate statistics method and its basic idea is to seek a projection that best represents the data in a least-squares sense. Independent Component Analysis is also a linear transform technology. While Principal Component Analysis seeks directions in feature space that represent the data in a sum-squared error sense, Independent Component Analysis instead seeks directions that are most independent from each other.

The framework of the system is shown in Fig. 1 . This system is composed of four parts: (1) Event producer; (2) Event analyzer; (3) Event response unit; (4) Event library.

The mechanism of this ensemble classification system is as follow: each detecting Agent of event producer collects and unifies audit data and then submits the data to event analyzer. Principal component analysis and independent component analysis extract the data separately. SVM is used to classify the data extracted, viz. (Here, it means constructing an optimal hyperplane in two different spaces.) The optimal hyperplane thus can be constructed in the corresponding principle component space and independent component space, by using SVM. Then, event analyzer combined the outputs from two individual classifiers (PCA SVM and ICA SVM) to judge whether the event is an intrusion. If event analyzer verdicts that the event is suspect, the event response will adopt corresponding step or simply record it in log file. Event library is used to preserve support vector sets of PCA SVM and ICA SVM, the weight of the ensemble system and the rules learned from intrusion events, etc.

The learning method of combined classifiers in the system is called Ensemble. It was shown in many domains that an ensemble is often more accurate than any of the single classifiers in the ensemble (Brown et al., 2005).

ENSEMBLE WEIGHT OPTIMIZATION

In an Intrusion Detection System, the cost of false negative error is higher than of false positive error. However, with high false positive error, large amount of normal networks being regarded as intrusion by IDS will bring much trouble to the administrators. That is to say, the key point of IDS is how to make both false negative error and false positive error as low as possible. After investigating FP, FN of PCA SVM and ICA SVM, we can see: When PCA SVM classifier works, the system has low false positive error; while ICA SVM classifier works and the system has low false negative error. It showed that the errors of PCA SVM and ICA SVM distributed in the different position of error space. If we combine them, the ensemble might be an effective way to detect intrusion.

The optimization problem is:

(1)

In present intrusion detection ensemble system, the output of event analyzer is obtained by weighted average of the output of PCA SVM and ICA SVM in order to optimize the upper formula.

(2)

ω^(k) (k = 1, 2) are, respectively the weights of the two individual classifiers:

(3)

c^(k) (k = 1, 2) are, respectively the output of PCA SVM classifier and ICA SVM classifier:

where, K( ) is kernel function.

Traditional methods to solve (1) attempt to combine these two costs (false negative error and false positive

error) into a single scalar objective function (Pietraszek, 2004; Joo et al., 2003) and then find the optimal solution. A drawback to this approach is that we need incorporating a prior information into the aggregation method (Abbass, 2003). To choose a optimal tradeoff is difficult, for instance, in Pietraszek (2004), the authors selected an individual classifier that gives a good tradeoff between false positives and false negatives for cost ratio ICR = 50, while the ratio 5 is considered to be proper (Joo et al., 2003).

In this study, the two objective functions (false negative error and false positive error) are optimized simultaneously. Usually, the minimization of a certain objective (e.g., FP_error) implies degradation in another objective (FN_error). Since our aim is at minimizing two criteria during the search, it will produce a set of classifiers which is the tradeoff between the criteria. Therefore, we need to find the Pareto-optimal set in our problem. A solution z∈Ω dominates a solution z` and we write z z` if and only if ∃k ∈{1,..., K}: f_k (z)<f_k (z`) and k ∈{1,..., K}: f<sub>k</sub> (z)>f<sub>k</sub> (z`). The elements of the set {z| z` ∈Ω: z`<z} are called Pareto-optimal.

In our experiments, the niched Pareto multiobjective genetic algorithm (NP-GA) (Kupinski and Anastasio, 1999) is used to maintain stable subpopulations of good solution. With NP-GA`s, a niche method is used to maintain stable subpopulations of good solution. An objective vector is optimized instead of a scalar fitness function in GA. Before the selection is performed, the population is ranked based on the concept of dominance, incorporates the multiobjective nature of the problem into the selection mechanism. When two or more solutions in a tournament have the same rank, the winner of a tied tournament is the solution that has the smallest niche count. The niche count estimates the density of solutions in a localized region (niche) around an individual.

The complete algorithm of the evolution of the intrusion detection ensemble system can be described below:

Algorithm:
Input: The training set (x_i, y_i), i = 1, ..., l collected and packed by detecting Agent:

•	Step 1: Project the training data to the corresponding feature space by PCA and ICA and the process is
•	Step 1.1: Principle component analysis Calculate the ith principal component adopting the following formula

where, function G is usually

is a standard Gauss random variable.

It turns to be a quadratic optimization problem as follows.

NP-GA divides each generation into several classes and selects some individuals with high fitness from each class to represent this class. Then generates a new group by crossover and mutation and selection by using sharing function.

The niche count m_i for the ith solution is given by

where, d_ij is the distance between solutions i and j. s(d_ij) is the so-called sharing function given by

Here, σ_share is called the niche radius, which represents the maximum distance between solutions that will result in an increase in their niche counts.