# Length-Bounded Hybrid CPU/GPU Pattern Matching Algorithm for Deep Packet Inspection
## 1 Introduction  
Deep packet inspection (DPI) is a technique that examines the packet content to ensure the network security. While packet headers can be examined for blocking malicious packets, DPI is responsible for checking packet contents for application awareness [1; 2; 3] demanded by modern networks. The network intrusion detection system (NIDS) is one of the DPI applications for network security. The anomaly-based and signature-based NIDSs are two forms of NIDSs to monitor the network traffic. Anomaly-based NIDSs determine whether the behaviors in the network are normal or anomalous [4; 5; 6]. In contrast, signature-based NIDSs inspect whether the packet payloads contain any malicious content. Specific data strings considered as malicious contents and appearing in the packet payloads are called \"signatures\" or \"patterns\". A collection of those malicious strings is called a \"pattern set\". Once any pattern is recognized in a packet payload, the NIDS will alert or drop this packet in order to protect the resources in the network. In the system, the pattern matching algorithm is needed to recognize the patterns, which is the core mechanism for searching patterns in the payloads. Designing an efficient pattern matching algorithm has become a priority because pattern matching is very time-consuming and can occupy around 70% of system execution time [7; 8]. Several pattern matching algorithms for signature-based NIDSs designed on software platforms have been proposed. In order to satisfy the required processing speed in high speed networks, some research focused onimplementing the pattern matching algorithms on the graphic processing units (GPUs) [9]. Since the capability of central processing units (CPUs) cannot meet the performance requirement for such networks nowadays, GPUs with more parallel processing power than CPUs may be deployed. However, although GPU processing power is superior, the overall performance of GPUs is limited due to the GPU overhead. The GPU overhead consists of kernel launch latency and data transfer latency; this limitation must be taken into account during the development. As a consequence, designing an efficient cooperative pattern matching algorithm between CPUs and GPUs becomes an essential issue. Here, we focus on designing the software-based and collaborative pattern matching algorithms. Initially, a hybrid CPU/GPU pattern matching algorithm (HPMA) [10] has been proposed. We designed HPMA based on the considerations that CPU features performance degradation with the computation and memory-intensive operations such as pattern matching algorithms, and GPU efficiency is limited with the data transfer overhead via the peripheral component interconnect express (PCIe) channel. Hence, an HPMA procedure was divided into \"pre-filtering\" and \"full pattern matching\", which is executed, respectively, by CPUs and GPUs. CPUs provide a rapid and high-filtration-ratio pre-filtering to classify the \"normal\" and \"suspicious\" packets first, and then the suspicious packets are delivered to GPU for full pattern matching. The normal packets can pass through directly. This mechanism can not only lessen the computation and memory-intensive operations for CPU, but also reduce CPU-GPU data transfer overhead to achieve the task allocation balancing. The experiment showed that the HPMA brought higher efficiency than the CPU-only and GPU-only full pattern matching algorithms, indicating that such collaboration is effective. However, the HPMA performance may be restricted under a few conditions. For example, the input traffic with varying length packets can cause a large variation of thread execution time in parallel processing, resulting in throughput degradation. In this paper, a length-bounded hybrid CPU/GPU pattern matching algorithm (LHPMA) is proposed to deal with this problem. Once an incoming packet is loaded, the LHPMA categorizes the packet in advance according to a pre-determined payload length bound.