Fast Regular Expression Matching using Small TCAMs for Network Intrusion Detection and Prevention Systems

Oct 13, 2010

Download: MP4 Video Size: 443.1MB  
Watch on YouTube

Abstract

Regular [removed]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.