Intrusion Detection Based On Sequential Patterns

Intrusion detection technique is the new generation of security assurance technology after firewall, data encryption and other techniques. With the development of Internet and the rapid increase of network data, the traditional intrusion detection technique of building model in manual manner does not accommodate the new network environment. In order to solve the problem of extracting knowledge from massive data, intrusion detection technique based on data mining is presented. Along with the improvement of intrusion technique, many intrusion behaviors hide their signatures in the occurrence order of events. An individual packet or command looks normal, which has not evident detection signatures in it. However, a sequence of packets or commands in order compose an attack, and the attack sequence appears only once in an attack. In order to find out the rule of this kind of attack, sequential pattern mining algorithms are introduced into intrusion detection systems. multi-instances of the sequential attack are gathered as training data, attribute sequences of attack behavior which appear multi-instances but only once in each instance are mined, and a detection model with these attribute sequences is built. The sequential pattern mining algorithms overcome the disadvantage of not reflecting the occurrence order of events in association rule algorithms, and detect application layer R2L (remote to local) and U2L (user to root) attack which is a difficult problem in intrusion detection at present. Thus detection rate is improved.First, the thesis introduces the origin, development and research status quo of intrusion detection and database mining. Then the paper describes the concept of sequential patterns and analyzes the advantages and disadvantages of several traditional sequential pattern algorithms.Then, A new algorithm for mining sequential patterns named SPAM (Sequential PAttern Mining) is discussed, which was proposed in SIGKDD International Conference in 2002 by Jay Ayres and so on. The algorithm utilizes the bitmap representation of data for efficient counting to calculate the support of sequences quickly.In order to further improve time and space efficiency of SPAM algorithm in the support counting process, it has to be modified. When a database is scanned for the first time to construct a last position table of 1-length sequence-extented sequences. In each customer sequence, it directly judges whether an item can be appended to the prefix sequence or not by comparing this item's last position with the prefix border position. Increment the support value of the candidate item by 1 if the candidate item's last position is larger than the prefix border position. A bitmap strategy is used to avoid such comparison process. A pre-constructed table, named ITEM_IS_EXITS_TABLE is constructed while first scanning to record the last position information. In each iteration, this table need to be checked to get information that a candidate is behind current position or not. To accumulate the support of candidate sequences, ITEM_IS_EXITS_TABLE need to be checked and the corresponding item's vector value is added. Thus the comparison process and ANDing operation can be avoided. These modifications are merely performed in sequence-extented process. In this paper, the improved SPAM algorithm is called MY-SPAM.Further, intrusion detection model based on sequential pattern algorithm named MY-SPAM is established and described in detail.Finally, the experiments are implemented on the intrusion detection model based on sequential pattern algorithm MY-SPAM. It is performed on enviroment in KDD CUP 99 data set with different support threshold minsup. The experimental result demonstrates that MY-SPAM outperforms SPAM in efficiency and feasibility and accuracy of the application to intrusion detection model.