# LDFGB Algorithm for Anomaly Intrusion Detection

Shang-Nan Yin, Zhi-Guo Chen, Sung-Ryul Kim

► To cite this version:

Shang-Nan Yin, Zhi-Guo Chen, Sung-Ryul Kim. LDFGB Algorithm for Anomaly Intrusion Detection. 2nd Information and Communication Technology - EurAsia Conference (ICT-EurAsia), Apr 2014, Bali, Indonesia. pp.396-404, 10.1007/978-3-642-55032-4_39. hal-01397240

HAL Id: hal-01397240

https://inria.hal.science/hal-01397240

Submitted on 15 Nov 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# LDFGB Algorithm for Anomaly Intrusion Detection

Shang-nan Yin, Zhi-guo Chen, and Sung-Ryul Kim

Division of Internet and Multimedia Engineering
Konkuk University, Seoul, Rep. of Korea
yinshangnan@gmail.com, chenzhiguo520@gmail.com, kimsr@konkuk.ac.kr
http://www.konkuk.ac.kr

**Abstract.** With the development of internet technology, more and more risks are appearing on the internet and the internet security has become an important issue. Intrusion detection technology is an important part of internet security. In intrusion detection, it is important to have a fast and effective method to find out known and unknown attacks. In this paper, we present a graph-based intrusion detection algorithm by outlier detection method which is based on local deviation factor (LDFGB). This algorithm has better detection rates than a previous clustering algorithm. Moreover, it is able to detect any shape of cluster and still keep high detection rate for detecting unknown or known attacks. LDFGB algorithm uses graph-based cluster algorithm (GB) to get an initial partition of dataset which depends on a parameter of cluster precision, then we use the outlier detection algorithm to further processing the results of graph-based cluster algorithm. This measure is effective to improve the detection rates and false positive rates.

**Keywords:** Graph-based clustering, outlier detection, Intrusion Detection.

## 1 Introduction

In modern society, we use internet at anytime and anywhere, so internet security becomes one of the hottest issues and we need to find an effective way to protect this network infrastructure. Intrusion detection system [1] is a useful method for detecting attacks. In 1987, Denning [2] introduced the first anomaly intrusion detection model, which is able to detect known and unknown attacks. After that research, many methods have been proposed for anomaly intrusion detection, such as machine learning [3], immunological [4] and data mining. Among these techniques, data mining has been widely used and it successfully solves the deficiencies of intrusion detection. The clustering algorithm is an important technology of data mining which can offset these deficiencies.

Clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (same attributes) to each other than to those in other groups (clusters). K-means algorithm [5]
is a popular clustering algorithm which is used in anomaly intrusion detection. This algorithm classifies similar data set into same clusters, and classifies dissimilar data set into different clusters. However, the user must set the number of clusters k, meaning that the user has to have some knowledge about the data. Other methods also have some disadvantages, for example, combining simulated annealing and clustering algorithm [6] requires a lot of training data and thus consumes excessive resource. In recent year, many researchers have proposed to avoid excessive resource consumption. One of effective methods is graph-based clustering. For example, PBS algorithm [7] introduces a measurement method of data points similarity which is based on an approximate function. But, this algorithm cannot achieve an exciting detection rate. LDC algorithm [8] improves the detection rate, but it doesn't accurately and comprehensively analyze the distribution situation of data nodes.

In this paper, we present LDFGB algorithm for intrusion detection which is one of the graph clustering algorithms. It is based on the LDC algorithm, uses local deviation factor to differentiate the distribution situation of data nodes and to identify outliers. The experimental results show that the proposed method is efficiently for anomaly based intrusion detection.

The paper is organized as follows. In section 2, we introduce the graph-based clustering. In section 3, we describe the LDFGB algorithm in detail. In section 4, we describe our evaluation methods and experimental results. Finally, we conclude this paper.

## 2 Graph-Based Cluster Algorithm

Graph-based clustering algorithm is a method commonly used in automatic partitioning of a data set into several clusters. It proceeds by setting a parameter of clustering precision to control the result of clustering. Records in dataset are packaged as a node. These nodes are treated as vertex of a complete undirected graph, and the distance values between these nodes as weight of the edge. The distance is calculated by Euclidean distance function (Table 1).

$$d(i, j) = \sqrt{|x_i 1 - x_j 2|^2 + |x_i 2 - x_j 2|^2 + \dots + |x_i p - x_j p|^2} \quad (1)$$

<table><caption>**Table 1.** Euclidean distance</caption><thead><tr><th></th><th>Id1</th><th>Id2</th><th>Id3</th><th>......</th><th>Idn</th></tr></thead><tbody><tr><td>Id1</td><td>0</td><td>0.81</td><td>0.11</td><td>......</td><td>0.02</td></tr><tr><td>Id2</td><td>0.81</td><td>0</td><td>0.45</td><td>......</td><td>0.71</td></tr><tr><td>Id3</td><td>0.11</td><td>0.45</td><td>0</td><td>......</td><td>0.15</td></tr><tr><td>......</td><td>......</td><td>......</td><td>......</td><td>......</td><td>......</td></tr><tr><td>Idn</td><td>0.02</td><td>0.71</td><td>0.15</td><td>......</td><td>0</td></tr></tbody></table>
According these values of distance, we construct a distance matrix I. And the threshold $\delta$ is computed from a parameter of cluster precision $\alpha$.

$$ \delta = dismin + dismax - dismin * Clusterprecision \quad (2) $$

dismin and dismax represent the minimum and maximal value of matrix I respectively. So an edge is cut down from this graph if its value of weight greater than threshold $\delta$ as shown in Figure.1

<figure><img src="image_2.png" /><figcaption>Fig. 1. GB Cluster</figcaption></figure>

Finally, we transverse the whole graph, the nodes would be classified into the same cluster if there is an edge between them. Therefore, several sub-graphs are created. Each sub-graph represents a cluster. Finally, outliers are processed.

The Steps of GB Algorithm Are as Follows:

Input: Dataset (record set), Cluster Precision

Record I is packaged as a note

Put note I into Graph

Repeat {

Calculate threshold (delta) by function

Cut down all the edges whose value is greater than the threshold (delta)

Transverse Graph, label all the sub-graphs.

Outlier processing

} until the outlier is processed completely

GB algorithm has been used for clustering for decades. However, it mainly has two shortcomings when it is applied for intrusion detection: the first one is that it distinguishes the normal and abnormal cluster just by a value of threshold. So the clustering accuracy is far from enough. Second, it doesn't offer a reasonable method to address outliers, but it just throws them away. With this coarse granularity partition, it cannot achieve a satisfactory detection rate. On the other hand, the ability to detect any shape of cluster has made it very suitable for the dataset with complex shape from real network.
## 3 LDFGB Algorithm for Intrusion Detection

In order to achieve higher detection rate, we further propose an improved graph-based clustering algorithm by using outlier detection method based on local deviation factor in label process. This method mainly focuses on how to classify the data on the boundary to be classified more accurately and then augment the difference between normal and abnormal clusters. Firstly, we define some related definitions:

**Definition 1: (Outlier).** These can be objects that are outlying relative to their local neighborhoods, particularly with respect to the densities of the neighborhoods. These outliers are regarded as local outliers. (Figure 2)

<figure><img src="image_3.png" /><figcaption>Fig. 2. $O_1$ and $O_2$ are outliers</figcaption></figure>

**Definition 2: (k distance of an object p).** For any positive integer k, the k-distance of object p, denoted as k-distance (p), is defined to be the distance d (p, o) between p and an object o∈D such that:

For at least k objects o'∈D \ {p}, it holds that d(p,o')≤d(p,o)

For at most k-1 objects o'∈D \ {p}, it holds that d(p,o')<d(p,o)

**Definition 3: (k-distance neighborhood of an object).** Given the k-distance of p, the k-distance neighborhood of p contains every object whose distance from p is not greater than the k-distance.

$$N_{k-distance}(p) = \{q \in D \setminus \{p\} | d(p, q) \le k - distance(p)\}$$

These objects q are called the k-nearest neighbors of p.
**Definition 4: (local deviation rate of an object).** Given the k-distance of p, and p is a center of circle with radius k. All objects in this circle are k-distance neighborhood of p. p is the Centre of mass of this circle. So the local deviation rate is defined to be:

$$LDR_{k(p)} = \frac{dis(p, p')}{|N_{k-distance(p)}|} \qquad (3)$$

The dis (p, p') is the distance between object p and Centre of mass of p'.

**Definition 5: (local deviation influence rate of an object).** Given the k-distance neighborhood of p and LDR, the local deviation influence rate is defined to be:

$$LDIR_{k(p)} = \frac{\sum_{o \in N_{k-distance}}^{LDR_{k(o)}}}{|N_{k-distance(p)}|} \qquad (4)$$

**Definition 6: (local deviation factor of an object).** Given LDR and LDIR, local deviation factor is defined to be:

$$LDF_{k(p)} = \frac{LDR_{k(p)}}{LDIR_{k(p)}} \qquad (5)$$

The local deviation factor of object p reflects k-distance neighborhood of object p within the dispersion degree. High value of LDF means higher probability of one object being an outlier; a low LDF value indicates that the density of an objects neighborhood is high. So its hardly to be an outlier.

*The Steps of LDF Algorithm Are as Follows:*

Step1: implement GB algorithm to cluster dataset and gain n clusters C1, C2...Cn, they are sorted in descending order according to the records they embraced.

Step2: initialize CN = {}, CS = {}, CA = {},

Step3: For i = 1 to n
    IF (C1.num+C2.num...Ci.num> (lambda)2*M),
        THEN CN={C1, C2...Ci-1},
        IF (Cn+Cn-1...Cj+1 > (lambda)2*M)
            THEN CA = {Cj+1...Cn}.
    The remaining cluster is classified into CS {Ci...Cj}.
End for.

Step4: compute LDF of every object p by the function (3) (4) and (5), p CS, sorted these values in descending order.
The first k records are classified in CA, and the rest
are classified in CN.

Step5: the data in CN are labeled as normal, while in CA, they are labeled as abnormal. After all data are labeled, the labeling process is over.

In this process, CN, CS and CA stand for the set of normal clusters, sus-
picious clusters and abnormal clusters respectively. CS is the set that need to
be processed in next step. In step 3, M is the number of data set and λ1, λ2
(λ1+λ2=1) represent the percentage of normal and anomaly rate. They should
meet the premise that the number of normal action is far greater than the number
of intrusion action. So their values must satisfy λ1≫λ2. Otherwise, the isolated
points were classified in abnormal clusters rather than discard them away. In
detecting phase, a new record d, calculate its distance to each data, it will be-
long to the cluster the same to the data that has nearest distance with it. If the
cluster is normal, d is normal. Otherwise, d is an attack.

4 Experiments And Results

To evaluate the performance of LDFGB approach, a series of experiments was
conducted on a 2-dimensional artificial dataset. (Figure 3)

<figure><img src="image_4.png" /><figcaption>Fig. 3. 2-dimensional dataset and LDF values</figcaption></figure>

Figure 4 shows that the data nodes distributed in two kinds of situations. Similar results are obtained by the LDC algorithm, so the LDC algorithm cant differentiate these kinds of situations. If we use the proposed method (LDFGB Algorithm) by adjusting K values that we can differentiate two situations. So the performance of LDFGB is the better than LDC algorithm.

KDDCup99 dataset is a dedicated test dataset established for intrusion detec-
tion assessment by Massachusetts Institute of Technology. It contains 24 kinds
of attacks categorized into 4 types: Denial of Service, Remote to User, User
<figure><img src="image_5.png" /><figcaption>Fig. 4. Two kinds of distribution</figcaption></figure>

to Root and Probing. In the dataset, a record has 7 classified attributes and 34 numeric attributes, and this belongs to the implementation of clustering in high-dimensional space. The In order to improve the detection efficiency of the experiment, we remove the attributes that is useless for this experiment. After careful analysis, we screen 20 properties as the objects of study, such as the lifetime of the TCP, window size and the length of the packet.

We randomly select 10000 samples for training data set. Besides, we randomly select 2500 samples of intrusion which types are different from the training dataset. It is aimed to evaluate ability of this algorithm on detecting unknown attacks. First, we alter the cluster precision of α. The result is shown in Table 2:

<table><caption>Table 2. Clustering result of GB</caption><thead><tr><td>Cluster precision (α)</td><td>Cluster number(n)</td></tr></thead><tbody><tr><td>0.02</td><td>21</td></tr><tr><td>0.05</td><td>9</td></tr><tr><td>0.20</td><td>6</td></tr><tr><td>0.50</td><td>4</td></tr></tbody></table>

On Table 2, we observe clearly that the change of cluster number with altering parameter of cluster precision. A relatively large α will lead to small number of clusters. As a result, excessive data would be classified in one large class. And most of the abnormal behaviors cant be detected in this situation. On the other hand, with a small value of α, the partition will generate excessive clusters.

The next step, for the GB model, the best situation is that all data were divided into 9 subsets. So we fixed α= 0.05. To meet the one of premise of anomaly intrusion detection that normal action is far greater than the number of intrusion action, we try the parameter of λ1 and λ2 in (0.9 , 1.0) and (0.0 , 0.1) respectively. Finally, we change the values of parameter K and testing these constructed models by group 3. We find that, when k=9, λ1=0.95 and λ2=0.05, the performance of this algorithm is the best. The output of detection rate and false positive rate showed in Table 3:

The LDC algorithm output of detection rate and false positive rate showed in Table4:
<table><caption>**Table 3.** The performance of LDFGB</caption><thead><tr><td>K</td><td>Detection rate</td><td>False positive rate</td></tr></thead><tbody><tr><td>5</td><td>94.30%</td><td>2.26%</td></tr><tr><td>8</td><td>96.14%</td><td>2.09%</td></tr><tr><td>12</td><td>97.25%</td><td>2.03%</td></tr><tr><td>15</td><td>96.52%</td><td>2.13%</td></tr></tbody></table>

<table><caption>**Table 4.** The performance of LDC</caption><thead><tr><td>K</td><td>Detection rate</td><td>False positive rate</td></tr></thead><tbody><tr><td>5</td><td>93.30%</td><td>2.24%</td></tr><tr><td>8</td><td>95.31%</td><td>2.08%</td></tr><tr><td>12</td><td>92.67%</td><td>2.14%</td></tr><tr><td>15</td><td>92.00%</td><td>2.11%</td></tr></tbody></table>

<figure><img src="image_6.png" /><figcaption>**Fig. 5.** The preference of our method and LDC method</figcaption></figure>
We discover the LDFGB algorithm achieves better detection rate than the LDC algorithm. Table 3 and Table 4 show that when there are the same K values, the performance of LDFGB algorithm is superior to the LDC algorithm. The experimental result shows that the parameter K is an important factor for the performance of this algorithm. We should not set a value for K that is too large, because a large K value will cause many isolated points to be classified from normal classes. On the other hand, a relatively small value of K will lead to the most of records have a large LDF value. Therefore, we could not separate the abnormal records from suspicious cluster. Both of these situations would decrease cluster precision. Figure 5 shows that the proposed method always outperforms the LDC method.

## 5 Conclusions

Intrusion detection system based on data mining increases the safety and reliability of network. Obviously, by means of clustering method, intrusion detection may be carried out. The LDFGB algorithm presented in this paper may overcome some disadvantages of the traditional cluster algorithm for intrusion detection and can obtain comparative satisfactory performance of intrusion detection. However, there are still many deficiencies that need to be improved. Our further research will focus on how to reduce the complexity of this algorithm because the memory requirement for computation increases dramatically as the number of records grow. Another disadvantage which should be fixed is that the initial percentage of abnormal and normal records need manual control to find the suspicious clusters, it more or less influences performance of this algorithm.

**Acknowledgments.** This research was supported by Next-Generation Information Computing Development Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning (2011-0029924).

## References

1. http://www.sans.org/reading(_room/whitepapers/detection/understanding-intrusion-detection-systems_337

2. D.E.Denning,: An intrusion-detection model. In IEEE computer society Symposium on research security and privacy. pp.118-131 (1987)

3. Stefan Savage, David Wetherall, Anna Karlin, Tom Anderson,: Network Support for IP traceback. IEEE/ACM Transactions on Networking. pp.226-237 (2001)

4. Dasgupta, D., Gonzalez, F.: An Immunity-Based Technique to Characterize Intrusions in Computer Networks. IEEE Trans. Evol. Comput. 6(3), 10811088 (2002)

5. L.Kaufan, P.J.Rousseeuw,:Finding groups in data: an introduction to cluster analysis.[M], New York: John Wiley & Sons. (1990)

6. Lin Ni, Hong-Ying Zheng,: An unsupervised intrusion detection method combined clustering with chaos simulated annealing. Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong, 1922 August(2007)
7. W.Guohui, L.Guoyuan,: Intrusion detection method based on graph clustering algorithm. Journal of Computer Applications, pp.1888-1900 July(2011)

8. Z.Mingqiang, H.Hui, W.Qian,: A Graph-based Clustering Algorithm Intrusion Detection. The 7th International Conference on Computer Science & Education(ICCSE). pp.1311-1314 (2012)