Research On Regular Expression Matching Of Successive Packets In High-speed Networks

The regular expression is a kind of patterns with wild cards, which is widely used inNetwork Intrusion Detection Systems (NIDS) with the characteristics of rich in meaning, strongexpression ability, powerful to describe various features and so on. With the rapid increasing ofInternet transmission speed and the diversification of application, regular expression matchingcannot meet the demand of high-speed networks. There are three notoriously important problemspreventing from prevail abroad:(1) The growing of rule-sets which are used to describe theattack results in the rapid expansion of the memory space in the finite automaton and theexpansion rate far exceeds that of the memory space.(2) Matching engines cannot handle morethan one character per cycle and the speed of match is too low to meet the demand of high-speednetworks.(3) Current regular expression matching cannot detect sensitive words which aredivided into successive packets, and it brings link-up pretermission. To solve the problem, thepaper brings NetFlow to achieve successive packet inspection, but the rate of the traditionNetFlow methods is low and the existing of a large number of inactive timeout flows will lead tothe extravasation of the session table.To solve these problems, this dissertation studies successive regular expression matching inhigh-speed networks. First, we propose multi-step logic finite automaton (m-LFA) to reducememory space and increase matching speed. Then we propose the method of singly parallelmulti-linked lists to improve performance of NetFlow. In the end, we design the system ofsuccessive regular expression matching based on the combination of multi-step finite automatonand NetFlow. The researches in the dissertation are as follows:1. Multi-step logic finite automaton is proposed to reduce memory space and increasematching speed. Firstly, the algorithm divides rules into small patterns by Kleen. Secondly, smallpatterns are cut into the corresponding subpatterns which make the definitive automaton withflags. Thirdly, handle the flags with logic cells. Fourthly, reduce memory space with the idea ofnear-start-state decomposition and the result of this step is logic finite automaton. Finally, theautomaton is processed with multi-step to increase matching speed. Theory analysis andexperimental results show logic finite automaton can reduce by near97%, when other algorithmsare near95%. The rate of3-step logic finite automaton reaches4.6Gbps with the space expenseof50%.2. The method of singly parallel multi-linked lists is proposed to improve the handlingability and timely remove inactive timeout flows. All operations of NetFlow are the model of"read-process-write", so the bottleneck of NetFlow is the memory access. The efficiency of thedata bus is36%. The method proposed can read and write continuously to handle the arriving packets, whose efficiency reaches90%. The method of singly parallel multi-linked lists isproposed based on the method of continuous reading and writing to remove inactive timeoutflows. Theory analysis and experimental results show that the method can be applied inOC-768(40Gbps) to manage tens of millions of entries better than that of others inOC-192(10Gbps) to manage millions.3. The subsystem of successive regular expression matching is designed for NIDS. Thesubsystem is composed of regular expression matching based on m-LFA and NetFlow based onsingly parallel multi-linked lists. It separates the management of rules on software and thematching with hardware. It designs the pretreatment module, regular expression matchingmodule and NetFlow module seriously and improves the ability of real-time inspection withextendeding algorithm and pipelining design.