Alex Liu - Michigan State University

Alex Liu

Oct 13, 2010

Size: 443.1MB

Download: Video Icon MP4 Video  
Watch in your Browser   Watch on Youtube Watch on YouTube

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

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.

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.

Unless otherwise noted, the security seminar is held on Wednesdays at 4:30P.M. STEW G52 (Suite 050B), West Lafayette Campus. More information...

Coming Up!

Our annual security symposium will take place on April 7 & 8, 2020.
Purdue University, West Lafayette, IN

More Information