Intrusion detection

Summary

The task of developed intrusion detection system is to analyse the authentication records and separate genuine and fraudulent authentication attempts for each user account in the system. To achieve this we combine two machine learning algorithms – Expectation Maximisation (EM) algorithm followed by Bayesian Classification. The Expectation Maximisation algorithm uses a maximum likelihood type parameter estimation approach and is ideally suited for cases in which the available data set is incomplete or "hidden". It is an iterative procedure which under certain conditions converges to values at a local or global maximum of the likelihood function. EM algorithm has been first proposed more than 30 years ago and since then it has been used in fields as varied as statistics, computer vision, signal processing, machine learning, pattern recognition and many others. The problem we are trying to address using EM algorithm can be simplified and described as a problem of "learning a mixture of two Gaussians" described with Figure 1. Data presented to algorithm is generated by picking one of two Gaussians at random and then sampling from the selected distribution. If each Gaussian describes on of two users – genuine and fraudulent, trying to authenticate, knowing from which Gaussian each sample of our data originated would completely solve our ID problem. Gaussian type distributions are assumed here for both genuine and fraudulent user, although it is possible to modify the equations implementing the EM in order to tackle any other density function, as long as it can be parameterised. So what are the hidden variables in this problem? Well, if we knew which sample in our set is generated by which distribution we could easily solve the problem. It would then be easy to calculate sample mean and variance for each distribution. All that would be left in this situation would be to somehow classify the new samples (i.e. new authentication attempts) as members of one or the other Gaussian.


Figure 1. Recognising original pdfs for intrusion detection

Since this is not the case we need to think of each data sample as a triple of the form {xi, zi1, zi2}, where zij is 1 if xi is generated by jth Gaussian and 0 otherwise. zij variables are not known to us, i.e. those variables are hidden. The EM algorithm solves this problem by starting from an arbitrary hypothesis h={µ1, µ2} and working iteratively by estimating the expected values of hidden variables based on the current hypothesis for {µ1, µ2} and then adjusting this hypothesis. It can be proved that each iteration of the algorithm increases the likelihood of the data given and that EM algorithm therefore converges to one of local maxima depending on the initial hypothesis, i.e. its starting point. This approach can also be generalised to an arbitrary number of Gaussians but it has been found that the algorithm sensitivity to the choice of starting point increases in such situations. Various approaches to algorithm initialisation have been suggested in those situations. More generally, the setting of the EM algorithm involves a set of m independently drawn samples and two sets of variables X={x1, x2, …, xm} and Z={z1, z2, …, zm} that correspond to the observed data and hidden variables, respectively. If the set of all hypothesis can be parametrised by θ, the goal of the EM algorithm is to find θ that maximises E[ln P[Y|h]|X] where h denotes the current hypothesis. The EM algorithm consists of two previously mentioned steps. Speaking in mathematical terms:

1. Expectation step: Calculate Q(h'|h) = E[ln P[Y|h']|h,X] (i.e. obtain score for each possible hypothesis h' based on h,X)
2. Maximisation step: Set h' = argmax Q(h'|h)

For the case of two components equations for E and M steps of the algorithm can be derived from the general expressions given above. Iterative EM procedure and corresponding update equations for the case of two-Gaussian mixture are shown below.


Figure 2. Expectation Maximisation algorithm for two-Gaussian mixture

EM procedure performs well for well separated Gaussians but struggles to provide good results when distributions are close to each other. This problem is area of intensive research in data mining and pattern recognition fields. EM algorithm can also be extended to consider multidimensional data, i.e. each sample from our set can be described with more than one attribute. One example of such data is shown at the end of this section. Following the successful estimation of parameter set θ, we apply Bayes classification rule to assign the particular sample x to a class ωj with the highest posterior probability – probability that data sample x belongs to a particular class ωj where j = 1, 2, … J for J possible classes.


Figure 3. Bayes classification rule

The Bayes approach to pattern classification is a fundamental technique and is used in many pattern recognition applications. Since Bayes classifier poses the classification problem in terms of probabilities, all of the probabilities must be known or estimated from the data. In our system this has been done using the previously discussed EM algorithm. Figure 4 demonstrates the performance of EM algorithm for 3D (3 attribute) authentication data. More general results can be seen in the results section.




Figure 4. EM and Bayes algorithms applied to authentication data

Matlab source code

Convergence achieved in 14 iterations!

Estimated mean:

mu =
1.8412 6.9039
12.1577 16.9794
10.0447 4.2297



* Attribute values in GENUINE session identified as FRAUDULENT: *
ans =

ans =
11.7963
19.7565
12.6032

ans =

* Attribute values in FRAUDULENT session identified as GENUINE: *
ans =
Empty matrix: 0-by-1

ans =
Empty matrix: 0-by-1

ans =
Empty matrix: 0-by-1




generatedata.m

multivarpdf.m

plotdata.m

plotEMsearch.m

plotGauss1D.m

contourGauss2D.m

elipsoidGauss3D.m

kmeansinitialisation.m

Back to top of page.

Results

Collection of real data for ID algorithm testing and development is a difficult task, taking into consideration both technical and ethical aspects of this process. During the course of the work on this project we have developed a new idea for the collection of real data in "simulated" ID environment. This technique relies on concepts developed at Carnegie Mellon University. The researchers at Carnegie Mellon used the Internet to engage the public in playing casual games (2-3 minutes in duration) which indirectly contributed towards automated identification of images. We have implemented a variation which uses the Internet to engage the public in playing a casual game (trivia about animals) which indirectly generates usage data with similar statistical characteristics as user authentication activities. More details about this should soon be available (link). We hope to be able to collect data using this approach and test our ID algorithm on this data in the near future.

Meanwhile, in the first phase of work on ID algorithm testing and development we have used a data simulation approach where parameters of two uni- or multi-variate Gaussian distributions have initially been selected and data randomly drawn from those two distributions - one representing genuine, and another fraudulent user attributes. Number of samples drawn from one or the other distribution could also be selected.

We show here some results obtained using two sets of simulated data drawn from 1 and 3 dimensional Gaussians. The attributes used to describe 3-D data samples are: (i) number of incorrectly answered ques¬tions during the authentication session, (ii) time duration of the authentication session and (iii) time spent on the system following the successful authentication. A single attribute – duration of the authentication session was used to describe 1-D data samples. Part of data set presented to our ID algorithm for 3-D Gaussian case is shown on Figure 1. Obviously, to investigate performance of algorithm on 1-D type data, only one attribute (in this case attribute 2) from the Figure 5 was used.


Figure 5. Simulated authentication data (a) ID data presented to EM algorithm, (b) "Labelled" ID data.

Table 1. Parameters for each attribute used in the example discussed further in this section.


To test the sensitivity of the algorithm to the size of training data set, algorithm was initially trained using data sets of size ntraining=50, 100, 150, 200 and 400 and then tested on the set of another ntesting=500 data samples. Total percentage of misclassified samples, i.e. false positives (FP) and false negatives (FN), is calculated for both training and testing phases and results averaged over 100 independent runs of the algorithm. Tests have been performed for 1-D and 3-D Gaussian mixtures. Percentages of FPs and FNs for both cases (1-D and 3-D) are shown below.

a)

b)
Figure 6. Results obtained for different sizes of training data set (a) 1-D Gaussian mixture, (b) 3-D Gaussian mixture.

The importance of data dimensionality - number of attributes used to describe each authentication attempt can be clearly seen from this set of results. Percentage of misclassified authentication attempts is significantly reduced when three attributes (3-D) are used compared to single attribute case (1-D). Another important factor is the size of training data set. Larger number of samples used in training data set results in reduced misclassification error, although increasing the size of data set above 100 does not improve the performance of the algorithm significantly, especially for 3-D Gaussian mixtures.

Figure 7 shows the performance of EM based IDS for different ratios of genuine and fraudulent data sessions in the training and test sets. This parameter does not have a significant influence on the system performance, although some improvement is evident when the percentage of fraudulent authentication attempts in mixtures is reduced.

a)

b)
Figure 7. Results obtained for different genuine-fraudulent attempts ratios in both sets (a) 1-D Gaussian mixture, (b) 3-D Gaussian mixture.

Presented results suggest that there is a potential value in applying the proposed ID algorithm in knowledge based type of authentication systems. It should also be kept in mind that, so far we have tested our algorithm using data drawn from two Gaussian data distributions. Next parameter to be investigated in this phase of work is the performance of the algorithm with respect to a degree of overlap between those Gaussian distributions. With more than one fraudulent user trying to gain the access to the system we might also have to deal with the unknown number of Gaussians generating our authentication data. A modification of the EM algorithm able to automatically detect this number should therefore be considered.

Final challenge of this project, as we have already mentioned at the beginning of this section, is to prove the Gaussian nature of ID data by collecting real data in an unbiased manner. Alternatively, our algorithm might have to be modified further to account for differently shaped user distributions.

PowerPoint presentation format

This information is also available to view as a PowerPoint presentation.


Back to top of page.