Research On Pattern Matching Algorithm Based On OBDD

At present,the development of computer and network is more and more rapid,and the related problems of network security are becoming more and more serious.Modern network security applications,such as network-based intrusion detection systems and firewalls,routinely employ deep packet inspection to identify malicious traffic.Firewall is a passive defense protection technology,and it can not meet the large number of complex changes in the data.Intrusion detection system,as a supplement to the firewall,plays an increasingly important role in network security.The key to using signatures to identify attacks and malicious traffic is the efficient use of string matching algorithms to match network packets.Pattern matching in network security applications should satisfy two requirements: time efficiency and space efficiency.Since network applications are often deployed over high speed network links,time efficiency requires the time spent on processing each byte of data to be small to keep up with the Gbps of packet processing speed and space efficiency requires that the representation of larger number of patterns be small to fit into the main memory of a system.Most of pattern matching only considered regular expressions containing no capturing groups,i.e.,they do not support submatch extraction.Existing solutions for submatch extraction are based on non-deterministic finite automata(NFA)or recursive backtracking.While NFA are space-efficient and can extract submatches with a compact memory footprint,they are not time-efficient.Ordered binary decision diagram can compress the information to deal with large-scale problems efficiently.This paper combines the data structure features of OBDD and pattern matching algorithm to deal with signature matching.This paper focuses on the problem of pattern matching algorithm,it mainly includes:The Boolean function of a tagged NFA (Q,?,?,q0,Fin)uses four vectors (?),(?) and (?).The Boolean functions are represented and manipulated using OBDD to improve the NFA-based pattern matching to improve the time efficiency of NFA-based signature matching.The paper uses tags to distinguish the capturing groups within a regular expression,and extends Thompson's NFA construction approach to convert a regular expression with capturing groups to a tagged-NFA.This paper represents tagged-NFA with symbolic Boolean functions,and manipulates the Boolean functions using ordered binary decision diagrams(OBDD)to improve the time efficiency of the submatch extraction.NIDS are often deployed over high-speed network links,so it is efficient enough to provide high throughput intrusion detection on large volume of network traffic.The experiments results show that proposed NFA-OBDD is correct and efficient.NFA-OBDD outperforms a traditional NFA implementation by three orders of magnitude,avoid memory blowups and resist known algorithmic complexity attacks.While Submatch-OBDD improve the extraction efficiency of the submatch.The paper measured Submatch-OBDD's time efficiency and space efficiency by matching the patterns with network traces,synthetic traces,and enterprise event logs.Submatch-OBDD achieves its ideal performance when patterns are combined.In the best case,Submatch-OBDD is faster than RE2 and PCRE by one to two orders of magnitude.