# Length-Bounded Hybrid CPU/GPU Pattern Matching Algorithm for Deep Packet Inspection
## 3 Length-Bounded Hybrid CPU/GPU Pattern Matching Algorithm
### Length-Bounded Separation Algorithm  
Algorithm 1 describes the LBSA. This algorithm categorizes the incoming packets in advance according to a pre-determined payload length bound in order to reduce the payload length diversity for parallel processing. Given the current processing of packet payload set \(P\) and the length bound \(L_{b}\), the LBSA can determine the payloads in \(P\) with \(L_{b}\).  
Initially, the prefilter buffer \(T_{PB}\) and the full matching buffer \(T_{FB}\) are empty. In addition, a payload set \(P_{filtered}\) is declared to temporarily store the prefiltering results, which is also empty (Lines 1-3). A variable \(idx_{PB}\), the index of prefilter buffer entries, is set to zero (Line 4). For each payload in \(P\), the LBSA measures the payload length of packet \(P_{i}\) (denoted as \(L_{i}\)) for comparing it with the length bound \(L_{b}\) (Lines 5 and 6). If the payload length \(L_{i}\) exceeds the bound (longer than \(L_{b}\)), the system stores this packet in the prefilter buffer \(T_{PB}\) and waits for the CPU prefiltering process (Lines 7 and 8). After the packet is stored in \(T_{PB}\), the index of prefilter buffer entries \(idx_{PB}\) increases for the next insert (Line 9). Otherwise, this packet will be stored in the full matching buffer \(T_{FB}\) to wait for the GPU full pattern matching (Lines 10 and 11).  
Once the prefilter buffer \(T_{PB}\) is full, all of the packets in this buffer are delivered to the prefilter for processing. Then, the resulting payload set \(P_{filtered}\) is obtained and stored in the full matching buffer \(T_{FB}\) (Lines 14-16), and the system clears the data stored in \(P_{filtered}\), \(T_{PB}\) and \(idx_{PB}\) and continues the process for the next batch of incoming packets (Lines 17-19). On the other hand, once the full matching buffer \(T_{FB}\) becomes full, all of the packets in this buffer are copied to the GPU device memory and the full pattern matching process is executed. Finally, the matching result is returned, and system clears the data stored in \(T_{FB}\) (Lines 22-24).  
```
Input:\(P\) (packet payload set) and \(L_{b}\) (length boundary). \(T_{PB}\gets empty\); // Prefilter buffer \(T_{FB}\gets empty\); // Full matching buffer \(P_{filtered}\gets empty\); // Prefiltered payloads \(idx_{PB}\gets 0\); // Index of prefilter buffer \(P_{i}\)do \(L_{i}\leftarrow\) payload length of \(P_{i}\); if\(L_{i}>L_{b}\)then \(T_{PB}\)\([idx_{PB}]\gets P_{i}\); // store \(P_{i}\) in prefilter buffer \(idx_{PB}\gets idx_{PB}+1\); else \(T_{FB}\gets T_{FB}\cup P_{i}\); // store \(P_{i}\) in full matching buffer  end if if\(T_{PB}\) is fullthen \(P_{filtered}\gets prefiltering(T_{PB})\); // execute prefiltering algorithm and \(T_{FB}\gets T_{FB}\cup P_{filtered}\); // store \(P_{filtered}\) in full matching buffer \(P_{filtered}\gets empty\); \(T_{PB}\gets empty\); \(idx_{PB}\gets 0\);  end if if\(T_{FB}\) is fullthen \(result\leftarrow\)fullmatching\((T_{FB})\); // execute full matching algorithm and \(T_{FB}\leftarrow empty\); // return the matching result  end if  end if
```  
**Algorithm 1**Length-Bounded Separation Algorithm (LBSA).  
In this design, shorter packet payloads will be processed by the GPU that benefits the overall efficiency. Since using short packets is a typical way to attack [30], a large number of packets can be generated and sent in a shorter time; shorter packets are more likely malicious. If such packets are sent to the GPU directly, the redundant operations of CPU prefiltering caused by these packets can be reduced. Moreover, shorter packets can be collected into a larger number of packets that is favorable for the GPU because of much higher parallel processing power. On the other hand, longer packets may possibly pass the prefilter without being delivered to the GPU for complete inspection. Longer packet payloads--namely, most of the packet bytes--can be reduced by the prefilter to offload the GPU processing and decrease the data transfer latency.