High-Speed Network Intrusion Detection and Prevention

Network Intrusion Detection and Prevention Systems (NIDPSs) are vital in the fight against network intrusions. NIDPSs search for certain malicious content in network traffic (i.e., signatures) by  a method called Deep Packet Inspection (DPI), 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.
The main goal of this project is to develop low-cost, high-speed and scalable DPI methods. To achieve this goal, we developed 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.

As part of the low-cost, high-speed and scalable DPI goal, our research also involves optimizing current state-of-the-art building blocks for DPI. One such popular building block is the Bloom Filter (BF). To increase throughput by reducing off-chip access, BFs are used as on-chip filters. We show that BFs have shortcomings when implemented on hardware. Hence, we propose Aggregated Bloom Filters (ABF) to increase the throughput and scalability of hardware BFs. ABF leverages the query mechanism for hardware BFs by removing redundant hash calculations and redundant on-chip memory accesses for higher throughput. ABF also improves scalability by aggregating small distributed BFs to a single BF for better on-chip memory utilization. ABF shows seven-fold improvement in the average query throughput and four times less memory usage compared to previous hardware BFs for NIDPS.
Precision is also crucial for NIDPS, which can easily be evaded by fragmentation of attack packets. The straightforward defragmentation method is not applicable at high-speeds due to high memory requirement. In our earlier work, this multi-packet signature detection problem is addressed using a defragmentation-free, space-efficient solution. A new data structure, the Prefix Bloom Filter (PBF), is proposed to significantly reduce the storage requirement of the problem.
Another important factor that affects the precision of NIDPS is the quality of attack signatures. Recently, regular expression based signatures gain more attention compared to exact signatures due to their flexibility of defining attacks. Regular expressions allow signature writers to be more specific when preparing signatures which increases the precision of NIDPS. Currently, our research also targets NIDPS using regular expression based signatures while keeping our original goal of low-cost, high-speed and scalability.

Participating members: H. Jonathan Chao (chao@poly.edu), Sertac Artan (sartan@poly.edu), Masanori Bando (mbando01@students.poly.edu)

[1] N. Sertac Artan and H. Jonathan Chao, "Design and Analysis of a Multi-packet Signature Detection System, " Int. J. Security and Networks, Vol. 2, No. 1/2, 2007.
[2] N. Sertac Artan, and H. Jonathan Chao, "Multi-packet Signature Detection using Prefix Bloom Filters, " IEEE Global Telecommunications Conference, GLOBECOM 2005, St Louis, MO, Nov-Dec 2005.
[3] N. Sertac Artan, and H. Jonathan Chao, "TriBiCa: Trie Bitmap Content Analyzer for High-Speed Network Intrusion Detection, " in Proceedings of 26th Annual IEEE Conference on Computer Communications INFOCOM 2007, pp. 125-133, Anchorage, AK, May 2007.
[4] N. Sertac Artan, Rajdip Ghosh, Yanchuan Guo, and H. Jonathan Chao, "A 10-Gbps High-Speed Single-Chip Network Intrusion Detection and Prevention System, " IEEE Global Communications Conference, GLOBECOM 2007, Washington, DC, Nov 26-30, 2007.
[5] N. Sertac Artan, Kaustubh Sinkar, Jalpa Patel, and H. Jonathan Chao, "Aggregated Bloom Filters For Intrusion Detection And Prevention Hardware, " IEEE Global Communications Conference, GLOBECOM 2007, Washington, DC, Nov 26-30, 2007.