Multicore-GPU Based Algorithm and Architecture Design for Parallel Regular Expression Pattern Matching(I)

[[abstract]]Regular Expression has been widely used in Network Intrusion Detection Systems (NIDS) to represent network attack signatures. Because Regular Expression Pattern Matching is the most computation-intensive process in an NIDS, increasing the throughput of Regular Expression Pattern Matching has become a critical issue. Despite the tremendous amount of research seeking speed improvements, it is still very difficult for the system to meet the throughput requirement because of an ever increasing number of viruses. In this proposal, we intend to use multicore Graphic Processing Units (multicore-GPUs) to design and implement a very high-throughput Regular Expression Pattern Matching process. It is known that in areas such as the number of cores, memory bandwidth, and memory clock, the development of multicore-GPUs has progressed faster than that of multicore Central Processing Units (multicore-CPUs). Using parallel programming techniques, the performance of multicore-GPUs may be dozens of times, even hundreds of times faster than that of multicore-CPUs. Therefore, in addition to graphic processing, multicore-GPUs have been successfully applied to scientific computations, such as computational fluid dynamics, electronic design automation, numeric calculation, etc. However, as far as we know, there are no studies that focus on using the GPU to deal with the problem of network intrusion detection systems. Current compliers cannot effectively optimize programs for multicore-GPUs. In other words, directly compiling the regular expression matching software to multicore-GPUs will not achieve high throughput requirement. The optimization needs specific parallel algorithm and programming techniques based on the characteristics of multicore-GPU hardware architectures. Therefore, in this three year project, we intend to explore the parallelism techniques for Regular Expression Pattern Matching on multicore-GPUs. We will focus on the following three main issues. 1. Multicore-GPU based Architecture for Parallel Regular Expression Pattern Matching: Increasing bandwidth of pattern matching can increase parallelism and therefore improve throughput and performance, but suffers from the problems of boundary alignment and false positive. Therefore, we will propose a modified algorithm and implement on multicore-GPUs to evaluate the performance and throughput. 2. Multicore-GPU based Hierarchical State Machine Architecture: Compiling multiple regular expression patterns into a single composite Deterministic Finite Automaton (DFA) is an efficient way to increase the parallelism of Regular Expression Pattern Matching. However, there are specific Regular Expression patterns which cause the composite DFA to grow exponentially. Therefore, we will propose a Hierarchical State Machine Architecture to mitigate the memory explosion caused by such complex Regular Expression patterns, and then implement on multicore-GPUs to evaluate the performance and throughput. 3. Performance-Driven Multicore-GPU based Architecture for Parallel Regular Expression Pattern Matching: The performance of multicore-GPU based architecture for Parallel Regular Expression Pattern Matching is not only related to the parallelism of pattern matching algorithm, complexity of automaton, and memory requirements and allocation, but also closely linked to hardware architectures of GPUs, computation methodologies, and parallel programming. Therefore, we will propose optimization strategies for Parallel Regular Expression Pattern Matching on multicore-GPUs. In summary, we will study in detail the parallelism of Regular Expression Pattern Matching, and then implement and evaluate our Parallel Regular Expression Pattern Matching algorithm and architecture on the multicore-GPUs developed by the NVIDIA Corporation. Additionally, we intend to use Snort, Bro, and L7-filter as benchmarks to verify our results. We expect our proposed multicore-GPU based Architecture for Parallel Regular Expression Pattern Matching could be utilized for the development of NIDS.