Ant-Colony Optimization Algorithm For Intrusion Detection (IADC-2006)
Venue: San Diego
Location: USA, United States
Event Date/Time: Jun 27, 2006 | End Date/Time: Jul 05, 2006 |
Abstract Submission Date: Jun 05, 2006 |
Description
Intrusion Detection
K. Praveen Kumar Rao Ms. P. Kamakshi
M. Tech (CSE) Lecturer, CSE Dept
KITS(W) KITS(W)
Abstract—This paper proposes a boosting Ant-colony optimization algorithm for intrusion detection in computer networks. The goal of the algorithm is to extract a set of classification rules from a network dataset. These rules are capable of detecting normal and abnormal behaviors. The presented algorithm is evaluated according to some measures like detection, false alarm, and classification rates. Results show that the proposed boosting algorithm is capable of producing a reliable intrusion detection system.
I. INTRODUCTION
Security of the information in the computer networks has been one of the most important point.. To preserves the secure condition it is essential to be aware of the behavior of the incoming data. Is it a normal or abnormal data? It is a too vulnerable and complicated question. Owing to the fact that intrusive data are in several and similar forms, distinguishing them from the normal ones is so astounding. Fundamentally, two models of intrusion detection have been introduced
1. Anomaly Detection: This model first constructs the normal profile that contains metrics extracted from the system operation. While monitoring the system, current observation is compared with the normal profile in order to detect changes in the patterns of utilization or behavior of the system.
2. Signature or Misuse Detection: This technique relies on the patterns of the known intrusions in order to match and identify intrusion. The intrusion detection can be viewed as a classification problem.
Ant-colony optimization algorithm is an evolutionary learning algorithm which could be applied to solve the combinatorial optimization problems [9]-[11]. ACO algorithm fundamental idea has been inspired by the behavior of the real ants. Ants deposit pheromone as a trace to direct the other ones in finding foods. They choose their path according to the congestion of the pheromone. The above behavior of the real ants has inspired an algorithm which a set of artificial ants, as a group of simple agents, cooperate with each other to solve a problem by exchanging information via pheromone deposited on the graphs of the edges. Pheromone acts like a distributed memory for communicating ants with each other. This algorithm creates an ant system applied to many combinatorial optimization problems such as traveling salesman problem (TSP) [12]-[15] and the quadratic assignment problem [16], [17]. ACO has been used in the context of data mining for clustering [18], and classification [19] problems.
Ant-Miner [19] is an ant colony based system which is used for the classification task of data mining. In this algorithm, the objective is to assign each case (record, or instance) to one class, from the set of predefined classes, based on the values of antecedent attributes (called predictor attributes) of the case. Discovered knowledge gained from the classification task is shown by a set of rules. Each rule consists of two parts.
IF < term1&term2&... > THEN < class > (1)
IF part includes of some terms (predicator attribute) which are connected by the logical operation "and (&)". The organization of each term is a triple like
< attribute , operator , value > (2)
Example: < Sex = male >. THEN part indicates the predicated class for the cases which their attributes satisfy all the terms in the antecedent rule part.
This paper is organized as follow: first reviewing of Ant- Miner algorithm and its superiority in comparison to the other ones. Next, introduces the variations which produce the boosting Ant-Miner. Finally, some conclusions are mentioned.
II. DATA MINING USING ACO
As mentioned before, ACO algorithm has recently been used in various kinds of data mining problems such as clustering, and classification. Ant-Miner algorithm is the result of applying ACO for discovering rules [19]. This learning algorithm utilizes of the artificial simple ants in order to explore the training search space and gradually make candidate rules. Each tour of the ants is directed by the combination of pheromone and an Entropy function. Then among the candidate rules, the best one is selected and augmented to the discovered rules. This process will be done iteratively and finally a set of rules would be discovered which they could be used as our detection patterns to apply in larger data sets. This algorithm is presented in Fig. 1. At first the rule list is empty (line 3). Then the algorithm insert into the main loop (line 4). Pheromone is initialized and then algorithm inserts into the inner loop (line 7). In this part each ant gradually makes a rule (line 8). As mentioned, each term in the antecedent part of the rule is organized in the following pattern:
< attribute = value > (3)
Then the selection of a value for each attribute is performed according to a hybrid function which is a combination of ant’s pheromone and Entropy heuristic function (line 9). After generating a new rule, pruning function will be called (finding simpler rule with the higher quality), and after updating the pheromone will be done (line 10 and 11). Once the number of the rules reaches to the No_ of_ ants threshold or recently rules converge to a specific rule, the constraint of the inner loop will be satisfied (line 17). Then the best quality rule should be selected and added to the discovered rule list (lines 18 and 19). In this step the Training-Set will be updated (line 20). This iteration will be repeated until the Training-Set is greater than the Max_ uncovered _cases.
1 A High-Level Description of Ant-Miner
2 Training-Set = {all training cases}
3 DiscoveredRuleList = [ ] /* rule list is empty at first */
4 WHILE ( TrainingSet > Max_ uncovered_ cases)
5 t = 1 /* ant index */
6 j = 1 /* convergence test index */
7 initialize all trails with the same amount of pheromone.
8 REPEAT
9 Antt starts with an empty rule and incrementally
constructs a classification rule Rt by adding one term at a
time to the current rule
*********************
Prune rule Rt
*********************
11 Update the pheromone of all trails by increasing pheromone in the trail followed by Ant (proportional to the quality of Rt ) and decreasing pheromone in the other
trails (simulating pheromone evaporation)
*********************
12 IF (Rt is equal to Rt-1) /* update convergence test */
13 THEN j = j + 1
14 ELSE j = 1
15 END IF
16 t = t + 1
17 UNTIL (t >= No_ of_ ants) OR (j >= No_ rules_ converge)
18 Choose the best rule Rbest among all rules Rt constructed by all the ants
19 Add rule Rbest to DiscoveredRuleList
20 Training-Set = Training-Set -{set of cases correctly covered by Rbest }
21 END WHILE
Fig 1: Ant-Miner Algorithm [11]
Entropy Function
For each Ai = Vij (Ai is the ith attribute and Vij is the jth possible value of this attribute) an Entropy function is
computed according to equation (4)
where W is the class attribute (i.e., the attribute whose domain consists of the classes to be predicted), and k is the number of classes. P is the probability of observing class w if Ai = Vij has been observed.
In summary the higher, H (W | Ai = Vij ), the more uniformly the class distributed.
Quality Computation
In Ant-Miner the quality of a rule is computed according to equation.
Q = TP / ( TP + FN ) * TN / ( TN + FP ) (5)
TP: true positives, the number of cases in our training set covered by the rule that have the class predicted by the rule.
FP: false positives, the number of cases covered by the rule that have a class different from the class predicted by the rule.
FN: false negatives, the number of cases that are not covered by the rule but that have the class predicted by the rule.
TN: true negatives, the number of cases that are not covered by the rule and that do not have the class predicted by the rule. As it is mentioned, the Quality is used for selecting the best rule between discovered ones. Besides, Ant-Miner uses the quality as a factor for pheromone updating.
Pheromone Updating
In each iteration t, the pheromone will be increased for all the terms including in the constructed rule.
where R is the set of all the terms included in the rule. Furthermore, the pheromone should be decreased for every Tij not in the antecedent part of the rule. By normalizing the pheromone this objective would be satisfied.
Classification of new Cases
In order to classify a new test case, discovered rules are inserted into a sorted list according to their production orders. The first rule that covers the new record would be the indicator. Then the class predicted by that rule is compared with the class of the case. It is possible that no rule of the list covers the new case. In this situation, the new case is classified by a default rule that simply predicts the majority class in the set of uncovered training cases.
Thresholds
Ant-Miner algorithm uses some thresholds in order to satisfy some constraints in both iterations of the algorithm. These thresholds are as follow:
Number of ants (No_ of_ ants): it indicates the maximum number of the ants involved in rule discovery process.
Minimum number of cases per rule (Min_ cases_ per_ rule): Each rule must cover at least Min_ cases_ per_ rule to ensure a minimum generality.
Maximum number of uncovered cases in the training set (Max_ uncovered_ cases): it is used as an ending constraint to terminate the main loop.
Number of rules used to test convergence of the ants (No_ rules_ converge): If the current ant has constructed a rule that is exactly the same as the rules constructed by the No_ rules_ converge -1 previous ants, then convergence has occurred. Therefore the current iteration of the main loop of the Algorithm is stopped and the next iteration is started.
III. NEW BOOSTING APPROACH
The new approach insists on improving the classification rate. In this variation of Ant-Miner, attempt is made to preserve the benefits of Ant-Miner as much as possible, in order to reach the Boosting Ant-Miner by applying the following updates:
Dataset Partitioning
One of the disadvantages of the original Ant-Miner is that it does not assign the same chance to each of the classes in the rule discovery process. To overcome this problem, we have partitioned the main Training-set according to the different classes. The algorithm is then applied to each of these sets separately.
Changing the view of Quality
The computation of the quality of each rule is changed by considering the whole Training-set during the algorithm operation. By this variation, selection of more general rules is observed. Besides, because each part contains only one class, it is essential in order to cope with the original formulation of the quality, selecting them in basis of the whole Training-set not the separated Training-sets.
Heuristic Function Conversion
After dataset partitioning, there are various candidates for the selection of a heuristic function. If the original Entropy function is used, it will be converted to the following formula:
This formula is not as efficient as its original version. For instance it should be considered the H function when P approaches to zero or one. In both conditions H approach to the zero result. But only in one of this condition this result is proper ( P →1). Notice that in the previous definition of H, the formula was a sigma not only a single expression. The Heuristic function is updated according to equation.
Change the Pruning Technique
In the last variation, we change the step of applying the pruning procedure. Instead of pruning each rule in the inner iteration, we only prune the best rule which is discovered and inserted into the discovered rules. In the other word, using the suggested pruning update for the algorithm will decrease the running time and increase the performance of the whole algorithm significantly. One of the reasons that the operation of the algorithm improves using the proposed pruning technique is that the pheromone updating process will be done more effectively. However it is necessary to investigate the effect of different pruning techniques to obtain more efficient classification system. After applying these new variations, the new Ant-Miner algorithm performs for each minor Training-set independently. In each of these datasets we gain a group of rules. Then the first rule will be selected (like the method of original Ant-Miner in classifying the new cases) and insert it into the discovered rules. After performing this operation on all of the separated Training-sets, the total size of the discovered rules is equal to the number of different classes. Then we apply these rules to the whole Training-set and eliminate the cases (records) which covered by these rules. Now the original Ant-Miner is applied on the remained Training-set records. As a result we gain another set of rules and add it to the end of the ordered rule list. So we now have a list of rules and could utilize it in other new datasets. The method of classifying new cases is the same as the original Ant-Miner.
IV. CONCLUSION
In this paper a boosting Ant Colony Optimization algorithm is presented. The suggested algorithm is used to generate classification rules for intrusion detection problem. The proposed algorithm is an improved version of Ant-Miner which is a rule discovery solution in classification problems. The main new features of the presented algorithm are as follows:
1) The algorithm partitions the original Training-Set to some sub-partitions. Each of these sub-partitions is related to a specific class of the classification problem.
2) The view of quality assignment for each rule is based on the original Training-Set. Note that in the original Ant- Miner, the Training-Set is updated each iteration.
3) New heuristic functions are applied to the boosting Ant- Miner. These heuristics enabled the algorithm to improve the detection rate and false alarm rate independently.
4) The step of applying the pruning procedure is changed from inner iteration to the outer one. This modification caused a significant improvement for the presented algorithm. The effect of this modification is left to our future work.
REFERENCES
[1] M. Dorigo, A. Colorni, and V. Maniezzo, “The ant system: Optimization by a colony of cooperating agents” IEEE Trans. Syst.Man Cybern. B, vol. 26, pp. 29–41, Feb. 1996.
[2] M. Dorigo and G. Di Caro, “The ant colony optimization metaheuristic” in New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, Eds. New York: McGraw-Hill, 1999, pp. 11–32.
[3] M. Dorigo, G. Di Caro, and L. M. Gambardella, “Ant algorithms for discrete optimization” Artif. Life, vol. 5, no. 2, pp. 137–172, 1999.
[4] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies” in Proc. ECAL91—Eur. Conf. Artificial Life. New York: Elsevier, 1991, pp. 134–142.
[5] M Dorigo, V Maniezzo, A Colorni “An investigation of some properties of an ant algorithm” in Proc. Parallel Problem Solving from Nature Conference (PPSN 92) New York: Elsevier, 1992, pp. 509– 520.
[6] M. Dorigo, “Optimization, learning and natural algorithms” Ph.D. dissertation, DEI, Politecnico di Milano, Italy, 1992 (in Italian).
[7] M. Dorigo, V. Maniezzo, and A. Colorni, “The ant system: Optimizationby a colony of cooperating agents” IEEE Trans. Syst, Man, Cybern. B, vol. 26, no. 2, pp. 29–41, 1996.
[8] V. Maniezzo, A. Colorni, and M. Dorigo, “The ant system applied to the quadratic assignment problem” Universit´e Libre de Bruxelles, Belgium, Tech. Rep. IRIDIA/94-28, 1994.
[9] L. M. Gambardella, E. Taillard, and M. Dorigo, “Ant colonies for QAP” IDSIA, Lugano, Switzerland, Tech. Rep. IDSIA 97-4, 1997.
[10] N. Monmarché, “On data clustering with artificial ants” in Data Mining with Evolutionary Algorithms, Research Directions – Papers from the AAAI Workshop, A. Freitas, Ed. Menlo Park, CA: AAAI Press, 1999, pp. 23–26.
[11] RS Parpinelli, HS Lopes, AA Freitas "Data Mining With an Ant Colony Optimization Algorithm"- IEEE Transactions on Evolutionary Computation, 2002
Venue
Restrictions
Members Only
Invitation Only