High-speed regular expression matching hybrid system and method based on FPGA+NPU

Abstract

The invention provides a high speed regular expression matching hybrid system and method based on FPGA and NPU (field programmable gate array and network processing unit); the system is mainly composed of an FPGA chip and a multicore NPU; a plurality of parallel hardware matching engines are implemented on the FPGA chip, a plurality of software matching engines are instantiated on the NPU, and the hardware engines and the software engines operate in running water manner. In addition, a high speed RAM (random-access memory) on the FGPA chip and an off-chip DDR3 SDARM (double-date-rate three synchronous dynamic random-access memory) are used to construct two-level storage architecture; secondly, a regular expression rule set is compiled to generate a hybrid automaton; thirdly, state table items of the hybrid automaton are configured; fourthly, network messages are processed. The high speed regular expression matching hybrid system and method based on FPGA and NPU have the advantages that matching performance under complex rule sets is improved greatly, and the problem that the complex rule sets have poor performance is solved.

Description

technical field [0001] The invention mainly supports the deep message detection technology in the high-speed network, and is mainly applied in the intrusion detection system and the protocol identification system. Background technique [0002] Glossary [0003] FPGA: (English: Field Programmable Gate Array, abbreviated as FPGA), Field Programmable Gate Array. [0004] NPU: (English: Network Processing Unit, abbreviated as NPU), is a processor specially applied to network application data packets. [0005] FSM: (English: finite state automata, abbreviated as FSM), finite state automata. [0006] DFA: (English: deterministic finite automata, abbreviated as DFA), deterministic finite automata [0007] NFA: (English: nondeterministic finite automata, abbreviated as NFA), non-deterministic finite automata. [0008] Hybrid-FA: ​​(English: hybrid finite automata, abbreviated as Hybrid-FA), hybrid automata. [0009] GPU: (English: graphics processing unit, abbreviated as GPU), ...

AI Technical Summary

Problems solved by technology

The first challenge comes from automata. With the expansion of network applications, more and more rules need to be detected, and the rules become more and more complex, which leads to the increasing scale of DFA.

The storage overhead of DFA may be higher than the storage resources in current network equipment, and even a complete DFA cannot be generated in many applications

The second challenge comes from performance. The current Internet link rate is growing at a rate of 40% to 50% per year, and many deep packet detection applications such as intrusion detection systems require real-time processing of packets, so regular expression matching wire speed requirement

[0022] 1. Ignoring the core factor of memory access in practice, memory access delay is the most important decisive factor for regular expression matching

[0023] 2. Too much reliance on a single platform and architecture in the implementation, and each platform has its own defects that make it impossible to provide a satisfactory solution

[0024] 3. The design of the automata has not been fully integrated with the design of the architecture, resulting in a disconnect between the two research directions

The matching operations are all read operations, so each RAM block corresponds to two engines, doubling the performance

Images