The Research On Regular Expression Matching Algorithms For Deep Packet Inspection

Along with the development of technology, network applications aredramatically emerging one after another; network information security is threatenedby various rampant attacks. Deep Packet Inspection (DPI) is the key factor toNIDS/NIPS (Network Intrusion Detection/Prevention System), and RegularExpressions (REs) are usually used to represent the signatures of the rules, checkingnot only the header of data packets but also the payload. Regular Expression Matching(REM) is the key component of DPI. Traditional REM algorithms adoptNondeterministic Finite Automaton (NFA) and Deterministic Finite Automaton (DFA)to realize. NFA requires low memory size but has high memory bandwidth problem.However DFA memory bandwidth requirement is low but has high memory size.Hence the construction of time and space efficient REM algorithms is one of the hottopics on DPI research.In order to compress the DFA memory size efficiently, this paper proposes asimple novel REM algorithm based on Run Accumulation Length Encoding (RALE)called RALE-DFA. RALE-DFA introduces appearance character set of RE set tocompress the alphabet, and RALE algorithm is proposed to further compress thealphabet compression transition table, and bitmap is used to speed up matchingprocess. Examination results show that RALE-DFA reduces the DFA memory sizeefficiently. Comparing with traditional DFA, CSDFA (Character Substitution DFA)and D2FA (Delayed Input DFA), RALE-DFA reduces95.81%~98.56%,48.17%~73.34%and38.09%~76.15%respectively on DFA memory size.In some cases, REs with counting constriants will result in DFA state spaceexplosion, and make DFA impractical. In order to deal with counting constraintsproblem, this paper proposes Jump-CFA (Jump Counting FA) algorithm based onCounting-FA algorithm. Jump-CFA algorithm seperates counting constraints from REs,and jump strategy and counting strategy are used to reduce DFA states and speed upmatching process. Examination results show that Jump-CFA algorithm works outcounting constraints problem efficiently; and when comapred with traditional DFAand Counting-DFA, Jump-CFA reduces about73%~96%and5%~18%FA statesrespectively; Jump-CFA speeds up REM process by a factor of2-10when comparedwith Counting-FA.