The Research On The DFA Compression Algorithm And Parsing Snort Rules

With the development of network technology, the attacks aiming at importantnetwork information become more secretive and complex. the attacks are included inthe packet’s headers or payloads, such as malicious code, invasion of instructions etcmay be hidden in the packet’s payloads. Deep Packet Inspection(DPI) detects not onlythe packet header but also the payloads. DPI compares one set of specified rules withthe captured data packs to discover the characteristic carried by the data pack’scontents.In earlier security rules, people use precise strings to describe the signature ofintrusion. These strings constitute a rule set of filter. However, the various attacks(malicious codes and intrusion) deliberately hide their characteristics in order to avoiddetection, which lead to the exact strings cannot adequately describe these features.Therefore, regular expressions become a new generation tool using to describe attacksignatures with its flexible skills. Traditional Regular Expression MatchingAlgorithms(REMA) adopts Deterministic Finite Automata(DFA) to realize. DFA hasefficient matching rate, but occupies a large storage space. If implemented in software,it will take more time; If implemented in hardware, the storage space may be small.Generally, the size of the hardware available storage space is only hundreds of KB to2MB, therefore, the construction of time and space efficient REMA is one of the mostpopular topics in the field of DPI research.This paper focuses on the problem of DFA storage compression, and the regularexpression derives from some key options of Snort2.8rule set. This article will brieflyintroduce the parsing approach about these key options in our experiment. The mainfour work aspects are as follows:(1) There are more DFAs used to identify the same regular language. However,any regular language has a unique DFA(regardless of the homogeneous) with states ofa minimum number. The DFA minimization algorithm can convert any DFA to theequivalent and states of a minimum number. This paper analyzes the algorithmtheoretical basis for minimizing states in DFA, and provides a classical DFAminimization algorithm.(2) The DFA complied by regular expression usually produces problems such asdata blowup and redundancy. As analysis of DFA’s transition function table, DFAconsumes large memory resources, which is related to its character set and the number of state. Therefore, this paper respectively present character set compression algorithmand states compression algorithm based on the hierarchical clustering method.(3) This paper introduces the constitution of Snort2.8rule, and explains theparsing process from the text rule to the data structure into memory, and provides themethod of extracting key option in Snort rules.(4) This paper use Snort2.8rules for evaluating compression efficiency with twocompression algorithms. Compared with traditional DFA and D2FA, this algorithmreduces98.7%and63.2%respectively on DFA memory size.