A Study on Multi-Pattern Matching Algorithms with Gpgpu

Project: National Science and Technology CouncilNational Science and Technology Council Academic Grants

Project Details


With the fast growing popularity of the Internet, there is an increasing demand for network security. Traditional firewalls only provide basic network protection by examining the information contained in the header of an incoming packet, which is not enough to satisfy the increasing security requirements. Network Intrusion Detection Systems (NIDS) have been proposed to complement firewalls. They monitor packets in the network and scan packet payloads to detect malicious intrusions according to the predefined rules called patterns or signatures. Studies revealed that pattern matching is the bottleneck in NIDS. For example, it consumes about 70% of the total execution time in Snort, a popular open-source NIDS. Thus, it is important to design a fast multi-pattern matching algorithm to cope with the increasing network speed. The recent trend shows that General-Purpose Graphics Processing Unit (GPGPU) computing density improves fasters than CPU. Moreover, GPGPUs are cheap and readily available, which is suitable for computing intensive applications. In this project, we aim to design an efficient multi-pattern matching algorithm with GPGPU acceleration. Different from the existing approaches, this project focuses on balancing the loading between the CPU and the GPGPU. The key idea behind the proposed approach is to pre-filter packets with a fast algorithm executed by the CPU. Then GPGPU performs an exact matching algorithm for the packets passing through the CPU. To understand the design guideline of the pre-filtering algorithm, we analyze the relationship between the filtering rate and the processing speed. The proposed pre-filtering algorithm is also analyzed to show that it can fulfill its objectives. We will implement the proposed multi-pattern matching algorithm in Linux to evaluate its performance.

Project IDs

Project ID:PB10207-1791
External Project ID:NSC102-2221-E182-034
Effective start/end date01/08/1331/07/14


  • multi-pattern matching
  • general-purpose graphics processing unit


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.