Alex Liu, Fast Regular Expression Matching using Small TCAMs for Network Intrusion Detection and Prevention Systems
Regular expression (RegEx) matching is a core component of deep packet inspection in modern networking and security devices. Prior RegEx matching algorithms are either software-based or FPGA-based. Software-based solutions have to be implemented in customized ASIC chips to achieve high-speed, the limitations of which include high deployment cost and being hard-wired to a specific solution and thus limited ability to adapt to new RegEx matching solutions. Although FPGA-based solutions can be modified, resynthesizing and updating FPGA circuitry in a deployed system to handle RegEx updates is slow and difficult. In this talk, we present the first hardware-based RegEx matching solution that uses Ternary Content Addressable Memories (TCAMs), which are off-the-shelf chips and have been widely deployed in modern networking devices for packet classification. There are three main reasons why TCAM-based RegEx matching works well. First, a small TCAM is capable of encoding a large Deterministic Finite Automata (DFA) with carefully designed algorithms leveraging the ternary nature and first-match semantics of TCAMs. Second, TCAMs facilitate high-speed RegEx matching because TCAMs are essentially high-performance parallel lookup systems: any lookup takes constant time (i.e, a few CPU cycles) regardless of the number of occupied entries. Third, because TCAMs are off-the-shelf chips that are widely deployed in modern networking devices, it is easy to design networking devices that include our TCAM based RegEx matching solution. About the speaker: Alex X. Liu is currently an assistant professor in the Department of Computer Science and Engineering at Michigan State University. He received his Ph.D. degree in Computer Science from The University of Texas at Austin in 2006. He received the IEEE & IFIP William C. Carter Award in 2004 and the National Science Foundation CAREER Award in 2009. His special research interests are in networking, security, and privacy. His general research interests include computer systems, distributed computing, and dependable systems.
Create your
podcast in
minutes
It is Free