平行多字元字串比對演算法研發

Multi-string matching has been widely used in NIDS to detect network attacks and malicious network packets by matching packet contents with thousands of attack patterns. Due to the rapid increase of growing network attacks and network speeds, multistring matching faces the challenges for limited performance and insufficient throughput. In order to improve the performance and throughput of multi-string matching, this thesis presents a novel hierarchical parallelism that can accelerate multi-string matching on multiple GPUs. The hierarchical parallelism consists of three layers of parallelism. From top to bottom, the first layer is the data parallelism on multiple GPUs; The second layer is the task parallelism on a single GPU; The last layer is the data parallelism of the Aho-Corasick algorithm. Experimental results show that the hierarchical parallelism on a machine featured with four Nvidia Titan X GPUs can achieve 70 Gbps of throughput which is 40 times faster than the Aho-Corasick algorithm used in Snort. As the number of GPUs increase, the throughput of the hierarchical parallelism will also increase. In addition, the proposed approach adopts the perfect hashing to construct state machines that can achieve memory reduction on Snort up to 99.2%. Finally, the proposed hierarchical parallelism is implemented in the open source network intrusion detection system using Snort.