Design Of XFA Compression Algorithms Based On Subgraph Isomorphism

Network Intrusion Detection and Prevention(NIDP)is an important technical means in the field of information security.The basic principle of NIDP is to make certain pre-established security policy and check detected content with security policy.If something which is not allowed by security policy is detected,it will be blocked or dealt with other way.The Deep Packet Inspection(DPI)is an important technology to achieve NIDP.Since regular expression is flexible and efficient,it is commonly used in network security DPI.Traditional regular expression matching algorithm implementation is either based on non-deterministic finite automata(NFA,Nondeterministic Finite Automaton)or deterministic finite automata(DFA,Deterministic Finite Automaton).NFA and DFA can take advantage of matching efficiency and storage optimization at same time.NFA required storage space is small but very slow match;DFA since the match quickly became a realization method makes DFA regular expression matching the popular choice,but the DFA's match speed is high can be expanded exponentially at the expense of the state space.In recent years,researchers have proposed the concept of Finite Automata Extended(XFA),XFA's main idea is to add some additional instructions in some of the state to implement compression of DFA.Additional instructions have set register is reset,the counter is reset accumulate operations.Some contain wildcards for the data."*" Optimiz ation has great effect.Based on the analysis of traditional regular expression matching algorithm NFA and DFA cannot meet the performance requirements of causes,trying to further optimize the XFA.According to our research on the actual data set regular expression studies,we found that these generated XFA contains a lot of similar structure.We tried to use the principle subgraph isomorphic XFA into blocks proposed treatment,its reasonable coding,thereby further storage compression and storage space,improve throughput.The open source regular expression tool called regex was used to convert the data,and they are used to simulate the Ternary Content Addressable Memory(TCAM).Experimental results show that this method can compress the storage space up to 26.8%,and the throughput of the same storage capacity can be increased to 2.6 times.