Author(s): Jignesh Patel, Alex Liu and Eric Torng

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.