Research Of Compression Algorithm For Deep Packet Based On Regular Expressions

Traditional deep packet inspection exploited a simple string matching technology to match packets with a fixed string.But with the detection of the contents of the packets complexly, traditional detection methods can no longer meet the requirements. Regular expressions can provide greater expressive power and better flexibility, so depth packet inspection based on regular expression has become the focus of research.A typical pattern set contains hundreds of regular expressions,and complex regular expressions are represented by DFA(Deterministic Finite Automation), requiring a large of memory, leading to a larger time and space complexity,greatly lowering detection algorithm efficiency. At present,how to improve the efficiency of deep packet inspection based on regular expression which is still in the exploratory at home and abroad.Research in this paper is carried out on this background.This paper first analyzes the shortcomings of current IDS(Instrusion Detection System),introduces CLAY system(a common procedural framework associated with correlation engine),and introduces relational research about current deep-packet technology; And then specify date packet filtering technology and intrusion detection technology,based on which this paper describes working principle of deep packet inspection technology.Through the analysis of advantages and disadvantages of common pattern matching algorithms,this paper introduces regular expression compression and proposes DFA split algorithm.Regular expression compression is that regular expression are rewritten by rewriting rules before regular expressions which meet rewriting rules transform into DFA, making the number of DFA states from the original square or exponential growth to line growth. DFA split algorithm splits the DFA state transition table into an indirect index table,a transition output table and a direct transition table,greatly reducing the space of the DFA occupying,achieving high efficiency compression storage of DFA.Finally,the paper proposes a view that regular expression compression and DFA split algorithm are applied to CLAY system to detect the deep packets of the network,which has a certain practical value.