TriBiCa: Trie bitmap content analyzer for high-speed network intrusion detection

N. Sertac Artan, H. Jonathan Chao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Deep packet inspection (DPI) is often used in network intrusion detection and prevention systems (NIDPS), where incoming packet payloads are compared against known attack signatures. Processing every single byte in the incoming packet payload has a very stringent time constraint, e.g., 200 ps for a 40-Gbps line. Traditional DPI systems either need a large memory space or use special memory such as ternary content addressable memory (TCAM), limiting parallelism, or yielding high cost/power consumption. In this paper, we present a high-speed, single-chip DPI scheme that is scalable and configurable through memory updates. The scheme is based on a novel data structure called TriBiCa (Trie Bitmap Content Analyzer), which provides minimal perfect hashing functionality. It uses a trie structure with a hash function performed at each layer. Branching is determined by the hashing results with an objective to evenly partition attack signatures into multiple groups at each layer. During a query, as an input traverses the trie, an address to a table in the memory that stores all attack signatures is formed and is used to access the signature for an exact match. Due to the small space required, multiple copies of TriBiCa can be implemented on a single chip to perform pipelining and parallelism simultaneously, thus achieving high throughput. We have designed the TriBiCa on a modest FPGA chip, Xilinx Virtex II Pro, achieving 10-Gbps throughput without using any external memory. A proof-of-concept design is implemented and tested with 1-Gbps packet streams. By using today's state-of-the-art FPGAs, a throughput of 40 Gbps is believed to be achievable.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM 2007
Subtitle of host publication26th IEEE International Conference on Computer Communications
Pages125-133
Number of pages9
DOIs
StatePublished - 2007
EventIEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications - Anchorage, AK, United States
Duration: May 6 2007May 12 2007

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherIEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications
CountryUnited States
CityAnchorage, AK
Period5/6/075/12/07

Keywords

  • Minimal perfect hashing
  • NIDPS
  • TriBiCa

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'TriBiCa: Trie bitmap content analyzer for high-speed network intrusion detection'. Together they form a unique fingerprint.

Cite this