LaFA: Lookahead Finite Automata for Scalable Regular Expression Detection

Although Regular Expressions (RegExes) have been widely used in network security applications, their inherent com-plexity often limits the total number of RegExes that can be detected using a single chip for a reasonable through-put. This limit on the number of RegExes impairs the scal-ability of today’s RegEx detection systems. The scalability of existing schemes is generally limited by the traditional per character state processing and state transition detection paradigm. The main focus of existing schemes is in opti-mizing the number of states and the required transitions, but not the suboptimal character-based detection method. Furthermore, the potential benefits of reduced number of op-erations and states using out-of-sequence detection methods have not been explored. In this paper, we propose Looka-head Finite Automata (LaFA) to perform scalable RegEx detection using very small amount of memory. LaFA’s mem-ory requirement is very small due to the following three ar-eas of effort described in this paper: (1) Different parts of a RegEx, namely RegEx components, are detected using dif-ferent detectors, each of which is specialized and optimized for the detection of a certain RegEx component. (2) We systematically reorder the RegEx component detection se-quence, which provides us with new possibilities for mem-ory optimization. (3) Many redundant states in classical finite automata are identified and eliminated in LaFA. Our simulations show that LaFA requires an order of magnitude less memory compared to today’s state-of-the-art RegEx de-tection systems. A single commodity Field Programmable Gate Array (FPGA) chip can accommodate up to twenty-five thousand (25k) RegExes. Based on the throughput of our LaFA prototype on FPGA, we estimated that a 34-Gbps throughput can be achieved