Bypassing Space Explosion in Regular Expression Matching for Network Intrusion Detection and Prevention Systems
Download: Paper (PDF)
Date: 8 Feb 2012
Document Type: Briefing Papers
Additional Documents: Slides
Associated Event: NDSS Symposium 2012
NDSes/NPSes use regular expressions, represented as automata, to detect security threats. Prior automata construction algorithms use a “Union then Minimize” framework, which leads to extensive memory usage. In this paper, we propose a “Minimize then Union” framework for constructing compact alternative automata focusing on the DDFA. In our experiments, our algorithm runs up to 302 times faster and uses 1390 times less memory than previous algorithms.