PAMELA: Pattern Matching Engine with Limited-Time Update for NIDS/NIPS

Tran Ngoc THINH  Surin KITTITORNKUN  Shigenori TOMIYAMA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.5   pp.1049-1061
Publication Date: 2009/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.1049
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: VLSI Systems
Keyword: 
Cuckoo Hashing,  dynamic update,  pattern matching,  FPGA,  NIDS/NIPS,  

Full Text: PDF>>
Buy this Article




Summary: 
Several hardware-based pattern matching engines for network intrusion/prevention detection systems (NIDS/NIPSs) can achieve high throughput with less hardware resources. However, their flexibility to update new patterns is limited and still challenging. This paper describes a PAttern Matching Engine with Limited-time updAte (PAMELA) engine using a recently proposed hashing algorithm called Cuckoo Hashing. PAMELA features on-the-fly pattern updates without reconfiguration, more efficient hardware utilization, and higher performance compared with other works. First, we implement the improved parallel exact pattern matching with arbitrary length based on Cuckoo Hashing and linked-list technique. Second, while PAMELA is being updated with new attack patterns, both stack and FIFO are utilized to bound insertion time due to the drawback of Cuckoo Hashing and to avoid interruption of input data stream. Third, we extend the system for multi-character processing to achieve higher throughput. Our engine can accommodate the latest Snort rule-set, an open source NIDS/NIPS, and achieve the throughput up to 8.8 Gigabit per second while consuming the lowest amount of hardware. Compared to other approaches, ours is far more efficient than any other implemented on Xilinx FPGA architectures.