CN118337480A - Multi-mode character string matching method for disordered data packet based on P4 - Google Patents

Abstract

The invention provides a multi-mode character string matching method of disordered data packets based on P4, wherein a system comprises a issuing module, P4 network equipment, disordered data packet processing modules, a rule extraction module, a data processing module and a database module, wherein the P4 network equipment judges whether an analysis data packet is a fragmented or segmented data packet, the disordered data packet processing modules order the disordered fragmented or segmented data packets and then send the ordered fragmented or segmented data packets to the data processing module to execute an algorithm, and then the ordered data packets are input into the rule extraction module, and the database stores logs output by the rule extraction module; by the multi-mode matching method for the disordered data packets, the detection efficiency and accuracy of the disordered data packets are improved, the disordered data packets are simply and rapidly ordered, and the data reading accuracy is improved.

Description

A multi-pattern string matching method for out-of-order data packets based on P4

Technical Field

The invention belongs to the field of disordered data packet processing, and in particular relates to a multi-mode character string matching method for disordered data packets based on P4.

Background technique

Multi-pattern string matching is a core technology in the field of network security. It is widely used in intrusion detection systems (IDS), content-aware firewalls, and network monitoring systems. In these applications, data packets passing through the network must be quickly and accurately checked to identify malware, virus signatures, spam, or other predefined string patterns. With the increase in network bandwidth and the rapid expansion of data traffic, traditional multi-pattern string matching methods are gradually reaching bottlenecks.

In recent years, the emergence of programmable data planes, especially programmable switches based on P4 (Programming Protocol-Independent Packet Processors), has provided new opportunities for solving string matching problems in high-speed network environments. P4 allows researchers and engineers to write code to directly control how packets are processed in network devices, so that customized packet processing logic can be designed to meet specific network function requirements. Many studies have attempted to deploy multi-mode string matching methods on P4, effectively utilizing the fast and flexible hardware processing characteristics of P4. For example, some studies have unloaded string matching algorithms such as AC from the CPU to dedicated ASIC chips to improve performance. Typical methods include PPS and BOLT. These studies have achieved performance of more than Tbps, which provides a new type of solution for intrusion detection systems while meeting the needs of high-bandwidth networks.

However, although this method meets the performance requirements, it has huge defects in deployment. In actual networks, fragmented and segmented data packets may be out of order during transmission due to load balancing and other reasons, and the most advanced P4-based multi-pattern string matching algorithms PPS and BOLT cannot solve this problem. When PPS and BOLT encounter out-of-order fragmented and segmented data packets, they will simply treat them as a single data packet because there is no corresponding mechanism. For many attack rules, there are multiple pattern strings (for example, most Snort3 rules contain more than two pattern strings). When the pattern strings are distributed in different fragments or segmented data packets that belong to the same complete data packet, PPS and BOLT will fail to detect and cause loss of detection accuracy.

In addition, due to the limitations of memory and computing resources, the traditional caching and reorganization methods cannot be used to deploy multi-pattern string matching algorithms on P4 switches, which brings many challenges to our implementation.

In order to avoid the loss of detection accuracy and correctly match the matching of out-of-order fragments and segmented packets, it is particularly important to develop a multi-mode string matching method for out-of-order packets based on P4. This method needs to be able to accurately distinguish whether the packet is out of order and make correct execution while maintaining high throughput and low latency.

Summary of the invention

In view of the above-mentioned defects of the prior art, an object of the present invention is to provide a multi-mode string matching method for out-of-order data packets based on P4.

The above technical objectives of the present invention are achieved through the following solutions:

A multi-mode string matching method for out-of-order data packets based on P4, comprising the following steps:

S1: Initialize and determine the NFA root state and state transition flow table entries;

S2: Get the data packet to be parsed and parse it into a parsed data packet, determine the data packet characteristics and generate an index according to the data packet header information and protocol, and determine whether the parsed data packet and the data packet to be parsed are segmented data packets or fragmented data packets. If so, execute S4, otherwise execute S3;

S3: Execute NFA state transfer on the payload of the parsed data packet, read the NFA state corresponding to the parsed data packet, extract it if it exists, and assign it to the root state if it does not exist, and end after sending the result to the rule extraction module;

S4: Determine whether the index value of the fragmented data packet or the segmented data packet has a corresponding index value that is continuous with the cached data packet, and if so, execute S5;

If not, cache it temporarily;

S5: Execute the preset rule string offset according to the state transition flow table, assign the corresponding NFA state in the state transition flow table to the data packet, and determine whether the fragment or segment is the last one.

If not, execute the aforementioned NFA state update operation and execute the multi-pattern matching algorithm to release the current cache.

If yes, execute the multi-pattern matching algorithm, update the NFA state, and submit the processed data packet to the rule extraction module;

S6: Receive the information output by the rule extraction module, check whether there is rule information in the data packet header, and if so, generate a log and send it to the database for storage.

Furthermore, in S2, the parsed data packet is parsed to obtain data packet header data and a valid load.

Furthermore, the data packet to be parsed in S2 is a mirrored data packet generated when the P4 network device receives the data packet from the receiving port and sends the data packet body to the forwarding port.

Furthermore, the index in S2 is the source address, destination address, protocol field, identification field, or source IP, destination IP, source port, destination port, and transport layer protocol type of the IP header of the data packet.

Further, the status of the data packet is judged, and the judgment content includes:

Determine whether it is a fragmented data packet or a segmented data packet according to the header information of the data packet. If so, perform a disorder judgment. If not, execute S3;

The out-of-order judgment content includes: judging whether it is an out-of-order fragmented data packet or an out-of-order segmented data packet according to the header information of the data packet, if so, executing S4, if not, executing S3.

Furthermore, the information cached locally in S4 is sent back to the P4 register after a preset time, and the process jumps to execute S4.

Furthermore, a system for processing out-of-order data packets comprises:

A sending module, used for sending NFA root state, entries of state transition flow table and entries of pattern string mapping rule flow table to P4 network device;

The P4 network device obtains an initial data packet from a receiving port, mirrors the initial data packet into a mirrored data packet and forwards it to a forwarding port, and at the same time, performs a pattern matching algorithm on the mirrored data packet; and is also used to perform data processing on the method described in any one of claims 1 to 6;

An out-of-order data packet processing module receives out-of-order data packets after passing through a multi-pattern matching algorithm;

A rule extraction module receives non-fragmented data packets, non-segmented data packets, rule data packets and processed out-of-order data packets after the data packets pass the multi-mode matching algorithm;

A data processing module that performs a multi-pattern matching algorithm on data packets;

The database module stores the logs output by the rule extraction module.

Compared with the prior art, the present invention has the following advantages:

(1) This method designs a multi-pattern matching method for out-of-order packets based on programmable switches to address the complex situation of out-of-order fragmented packets in complex network scenarios. This method improves the detection efficiency and accuracy of out-of-order packets, makes it easy and quick to sort out out-of-order packets, and improves data reading accuracy. Compared with traditional multi-pattern matching algorithms, this method offloads the multi-pattern string matching method to the programmable switch, thereby reducing computing resource overhead.

(2) This method integrates multiple modules, including the sending module, P4 network equipment, rule extraction module and out-of-order packet processing module. This composite module design separates the data plane, control plane and computing plane. Each module performs its own function, which improves the efficiency and maintainability of the system.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a system structure diagram of a preferred embodiment of the present invention;

FIG2 is a schematic diagram of a P4 network device register according to a preferred embodiment of the present invention;

3 is a flow chart of a P4 network device processing a data packet according to a preferred embodiment of the present invention;

FIG4 is a flow chart of an out-of-order data packet processing module according to a preferred embodiment of the present invention;

FIG5 is a schematic diagram of a flow table entry sent down according to a preferred embodiment of the present invention.

Detailed ways

The embodiments of the present invention are described in detail below. The following embodiments are implemented on the premise of the technical solution of the present invention, and detailed implementation methods and specific operation processes are given, but the protection scope of the present invention is not limited to the following embodiments.

A multi-mode string matching method for out-of-order data packets based on P4, as shown in the process of Figures 3 and 4,

S1: Initialize and determine the NFA root state, state transition flow table entries, and pattern string mapping rule flow table entries;

S2: Get the data packet to be parsed and parse it into a parsed data packet, determine the data packet characteristics and generate an index according to the data packet header information and protocol, and determine whether the parsed data packet and the data packet to be parsed are segmented data packets or fragmented data packets. If so, execute S4, otherwise execute S3;

S3: Execute NFA state transfer on the payload of the parsed data packet, read the NFA state corresponding to the parsed data packet, extract it if it exists, and assign it to the root state if it does not exist, and end after sending the result to the rule extraction module;

S4: Determine whether the index value of the fragmented data packet or the segmented data packet has a corresponding index value that is continuous with the cached data packet, and if so, execute S5;

If not, cache it temporarily;

S5: Execute the preset rule string offset according to the state transition flow table, assign the corresponding NFA state in the state transition flow table to the data packet, and determine whether the fragment or segment is the last one.

If not, execute the aforementioned NFA state update operation and execute the multi-pattern matching algorithm to release the current cache.

If yes, execute the multi-pattern matching algorithm, update the NFA state, and submit the processed data packet to the rule extraction module;

S6: Receive the information output by the rule extraction module, check whether there is rule information in the data packet header, and if so, generate a log and send it to the database for storage.

In step S1 of this embodiment, the issuing module is initialized to be responsible for issuing the NFA root state, entries of the state transition flow table and entries of the pattern string mapping rule flow table to the P4 network device. The P4 network device performs a multi-pattern string matching algorithm based on the configuration of the issuing module, as shown in FIG1 .

In the step S2 of this embodiment, the data packet to be parsed is obtained by the P4 network device parsing the parsed data packet to obtain the data packet header data and the effective load. The data packet to be parsed is a mirror data packet generated when the P4 network device receives the data packet from the receiving port and sends the data packet body to the forwarding port. The subsequent multi-mode matching algorithm is executed for the mirror data packet, and the mirror data packet will be destroyed after the multi-mode matching algorithm is executed and will not be cached.

In the step S2 of this embodiment, the index is the source address, destination address, protocol field, identification field, or source IP, destination IP, source port, destination port, and transport layer protocol type of the IP header of the data packet. That is, for the case of IP fragmentation, a five-tuple is designed, which is composed of the source address, destination address, protocol field, and identification field of the IP header of the fragmented data packet as the unique feature to distinguish the fragmented packet; for the case of TCP segmentation, another five-tuple is designed, which is composed of the source IP, destination IP, source port, destination port, and transport layer protocol type as the feature to distinguish the unique fragmented packet.

The step S2 in this embodiment reads the register information based on the hash result of the five-tuple to determine whether the data packet is a fragmented or segmented data packet.

The specific NFA state transfer method in step S3 of this embodiment is: for the NFA state information of the register, the NFA state transfer algorithm is executed on the payload of the data packet according to the NFA state transfer entry, as shown in Figure 5, the initial state is s0, when the next character in the payload of the data packet matches ro, the state is transferred to s2, and the payload is shifted back two characters. After completing the final state transfer, the detection rule result is sent to the rule extraction module, as shown in Figure 5, when the string pattern information 1010 is matched, it means that rule 1 is matched.

In this embodiment, the status of the data packet is judged, and the judgment content includes:

Determine whether it is a fragmented data packet or a segmented data packet according to the header information of the data packet. If so, perform a disorder judgment. If not, execute S3;

The out-of-order judgment content includes: judging whether it is an out-of-order fragmented data packet or an out-of-order segmented data packet according to the header information of the data packet, if so, executing S4, if not, executing S3.

That is, to determine whether the data packet is an out-of-order IP fragment data packet, the IP fragment field of the current data packet is compared with the IP fragment information of the previous fragment data packet recorded in the register.

If the absolute value of the difference is consistent with the MTU (maximum transmission unit) size of the current data packet, it means that the data packet is not an out-of-order IP fragment data packet;

Otherwise, the data packet is an out-of-order IP fragment data packet, and the data packet is sent to the out-of-order data packet processing module together with the information of the corresponding data packet recorded in the current register.

Determine whether the data packet is an out-of-order TCP segmented data packet based on a comparison between the TCP segmentation field of the current data packet and the TCP segmentation field of the previous segmented data packet recorded in the register.

In step S4 of this embodiment, when the out-of-order data packet processing module receives an out-of-order fragment or segment data packet carrying register information, the out-of-order data packet processing module caches the current out-of-order data packet and the register information it carries, and waits for the subsequent out-of-order data packet to arrive. When a new out-of-order data packet arrives without register information, the out-of-order data packet processing module reads the cached register information based on the five-tuple hash index value, determines whether the index value of the out-of-order fragment data packet or the out-of-order segment data packet has a corresponding index value that is continuous with each other,

If yes, execute S5;

If not, it is temporarily cached, and the locally cached information is sent back to the P4 register after a preset time, and the jump is re-executed in S4.

The NFA state transfer in step S5 in this embodiment is to perform a preset rule string offset based on the matched NFA state in the register information recorded by the P4 network device, and finally determine whether the fragment or segment is the last one according to the MF field of the data network layer message header or the FIN field of the transport layer message header;

If MF=1 or FIN=0, it is not, indicating that there are fragmented or segmented data packets to arrive later. At this time, the aforementioned NFA state update operation is executed, and the multi-pattern matching algorithm is executed to release the currently cached data packets;

If MF=0 or FIN=1, the multi-pattern matching algorithm is executed, the NFA state is updated, and the processed data packet is submitted to the rule extraction module.

The present embodiment also includes a system structure, as shown in FIG1 , including a sending module, a P4 network device, a disordered data packet processing module, a rule extraction module, a data processing module and a database module.

A sending module, used for sending NFA root state, entries of state transition flow table and entries of pattern string mapping rule flow table to P4 network device;

The P4 network device is used to forward the data packets entering through the input port to the output port normally, and mirror a copy of the data packet. It is also used to process the data packet, parse the data packet content, complete string matching, and update the rule information of data packet mapping; it is also used to process the data of any method in this embodiment; the P4 network device register is shown in Figure 2.

An out-of-order data packet processing module receives out-of-order data packets after passing through a multi-pattern matching algorithm;

A rule extraction module receives non-fragmented data packets, non-segmented data packets, rule data packets and processed out-of-order data packets after the data packets pass the multi-mode matching algorithm;

A data processing module that performs a multi-pattern matching algorithm on data packets;

The database module stores the logs output by the rule extraction module and stores the data extracted by the rule extraction module in the form of tables to facilitate later query and retrieval.

In summary, based on the multi-pattern string matching technology of out-of-order data packets, this method designs a multi-pattern matching method for out-of-order data packets based on programmable switches for the complex situation of out-of-order fragmented data packets in complex network scenarios. This method improves the calculation speed of the system and improves the accuracy. Compared with the traditional multi-pattern matching algorithm, this method offloads the multi-pattern string matching method to the programmable switch, thereby reducing the computing resource overhead.

The preferred specific embodiments of the present invention are described in detail above. It should be understood that ordinary technicians in the field can make many modifications and changes based on the concept of the present invention without creative work. Therefore, all technical solutions that can be obtained by technicians in the technical field based on the concept of the present invention through logical analysis, reasoning or limited experiments on the basis of the prior art should be within the scope of protection determined by the claims.

Claims (7)

1. A multi-mode character string matching method of an out-of-order data packet based on P4 is characterized by comprising the following steps:

s1: initializing and determining NFA root states and state transfer flow table entries;

S2: acquiring a data packet to be analyzed and analyzing the data packet to be analyzed into an analysis data packet, determining data packet characteristics according to data packet head information and a protocol to generate an index, judging whether the analysis data packet and the data packet to be analyzed are segmented data packets or fragmented data packets, if so, executing S4, and if not, executing S3;

S3: performing NFA state transition on the effective load of the analysis data packet, reading the NFA state corresponding to the analysis data packet, extracting if yes, giving a root state if no, and ending after sending the result to a rule extraction module;

S4: judging whether the index value of the fragmented data packet or the segmented data packet and the cached data packet have corresponding index values which are continuous with each other, and if so, executing S5;

if not, temporary caching is performed;

s5: executing preset rule character string offset according to the state transfer flow table, giving data packets corresponding to NFA states in the state transfer flow table, judging whether the fragments or segments are the last,

If not, the NFA status update operation is performed, and a multi-pattern matching algorithm is performed, releasing the current cache,

If yes, executing a multi-mode matching algorithm, updating the NFA state, and submitting the processed data packet to a rule extraction module;

S6: and receiving information output by the rule extraction module, checking whether rule information exists in the data packet head, and if so, generating a log and transmitting a database for storage.

2. The method for multimodal string matching for P4-based out-of-order packets as recited in claim 1, wherein said parsing said parsed packet in S2 obtains header data and a payload.

3. The method for matching multi-mode strings of P4-based out-of-order data packets according to claim 1, wherein the data packet to be parsed in S2 is a mirror data packet generated when a P4 network device receives the data packet from a receiving port and sends a data packet body to a forwarding port.

4. The method for matching multi-mode strings of P4-based out-of-order packets according to claim 1, wherein said index in S2 is a source address, a destination address, a protocol field, an identification field, or a source IP, a destination IP, a source port, a destination port, a transport layer protocol type of an IP header of said packet.

5. The method for matching multi-pattern character strings of P4-based out-of-order data packets according to claim 1, wherein the judging the state of the data packets comprises:

Judging whether the data packet is a fragmented data packet or a segmented data packet according to the head information of the data packet, if so, carrying out disorder judgment, and if not, executing S3;

the disorder judgment content comprises: and judging whether the packet head information is an out-of-order fragmented packet or an out-of-order segmented packet, if so, executing S4, and if not, executing S3.

6. The method for matching multi-pattern strings of out-of-order data packets based on P4 according to claim 1, wherein the information buffered in S4 is sent back to the P4 register after a preset time passes, and the step S4 is performed in a skip mode.

7. An out-of-order packet processing system, the system comprising:

the issuing module is used for issuing the NFA root state, the entry of the state transfer flow table and the entry of the mode character string mapping rule flow table to the P4 network equipment;

P4 network equipment acquires an initial data packet from a receiving port, mirrors the initial data packet into a mirror image data packet, forwards the mirror image data packet to a forwarding port, and simultaneously executes a pattern matching algorithm on the mirror image data packet; also for data processing of the method of any of claims 1-6;

The out-of-order data packet processing module is used for receiving out-of-order data packets of the data packets after passing through the multi-mode matching algorithm;

The rule extraction module is used for receiving the non-fragmented data packet, the non-segmented data packet, the rule data packet and the processed out-of-order data packet of the data packet after the multi-mode matching algorithm;

the data processing module is used for executing a multi-mode matching algorithm on the data packet;

and the database module is used for storing the log output by the rule extraction module.