Application Of Non-Standard Pattern Matching Algorithm In Deep Packet Inspection

At present, the computer network has become an inseparable part in our daily life.However, with the development of network technology, network threats also increase rapidly,such as computer viruses, hacker attacks, network intrusions, and so on. This causes greatinconvenience to people’s life. The network security has become one of the hot issues peoplehave to focus on. Deep packet inspection system is a core component of network intrusionprevention system. Deep packet inspection system is a highly computationally intensiveprocess, accounting for about75%of the total CPU processing time of modern NIDS. Deeppacket inspection system enters into the application layer of the network to analysis andprocess the packet payload. It is more complex than the traditional protocol analyzer.High-speed network technologies such as10Gbps Ethernet, Gigabit fiber-optic network isincreasing popularity. The network transmits large-scale data. This puts forward a greatchallenge to deep packet inspection system. The existing deep packet inspection system cannot deal with high-speed network flow effectively, often losses packet and fails to report. Thisis undoubtedly a huge hidden danger of computer security. How to improve the performanceof deep packet inspection system and reduce the space cost becomes the main goal of theresearch in the field of network security. Currently, improving the performance of deep packetinspection system mainly bases on two methods, one is improving the matching algorithm andproposing a new efficient algorithm, the other is using new hardware platform.The matching algorithms used in deep packet inspection system usually are BMalgorithms, WM algorithm, AC automaton, Thompson automaton and so on. Because of thelimit of the algorithm, the processing speed of the deep packet inspection system is far fromachieving G ratio premium. When dealing with high-speed network traffic, the matchingalgorithm can not meet the need of the application in speed and memory footprint. Paralleltechnology using the inherent parallelism of the machine word can complete the processing ofthe data in constant time. No doubt, using parallel technology to improve the previousalgorithm will improve the performance of the algorithms greatly. However, limited bymatching word, the enhancing effect is not obvious. In addition, the majority of intrusiondetection products use regular expression to describe the attack, and usually use thedeterministic finite state automata (DFA) and nondeterministic finite state automata (NFA) tomatch the regular expression. But, DFA often occur state explosion, consume large amountsof storage space when fusion states. NFA is smaller than DFA in the storage space, butbecause of its uncertainty, it is complex in addressing state, and greatly reduces the matching efficiency. Therefore, seeking a pattern matching algorithm with high rate and low storagespace is one of the key points to improve the deep packet inspection system.In recent years, computer hardware technology develops rapidly. And, using emerginghardware platforms to improve the performance of deep packet inspection system has becomeone of the most effective means. Most researchers using multicore processors,Field-Programmable Gate Array (FPGA), Network Process Unit (NPU), Graphic ProcessingUnit (GPU) and other hardware platform realize improving the performance of deep packetinspection system. More transistors are used for data calculation, rather than logic control inGPU. So, it’s more suitable for large-scale data processing. Programmable GPU hasdeveloped into a highly parallelized, multi-threaded, multi-core processor, and has anoutstanding computing power and high memory bandwidth. At present, the actual process of atypical GPU computing speed gets up to20GFLOPS and memory gets up to25.3GB/sec, farmore than general-purpose CPU processor. Since the GPU has such a huge potential forcomputing, more and more applications are trying to be ported to the GPU. With the advent ofCUDA programming technology, it is no longer difficult to parallel programming on GPU.Processors execute bitwise operations very fast which can often be completed within theconstant time. In this paper, I use the multi-thread parallel features of GPU to break throughthe limitations of the machine word, and apply the bit parallel technology to matching longpattern and multi patterns. I put forward a new algorithm structure. The algorithm is notlimited to machine word, and also can achieve matching long pattern and multi patterns. Inaddition, I select the Glushkov automata which is more flexible than AC automata and hasfewer states than Thompson automata to achieve matching regular expression successfully.Through the experimental comparison, using bit parallel technology to match patterns in GPUplatform, the speed-up ratio reaches20times and the performance has been greatly improved.