CN117336240B - IP five-tuple matching method and system under high-capacity rule - Google Patents

Abstract

The present invention discloses an IP five-tuple matching method and system under large-capacity rules, and the method comprises: S1, dividing the large-capacity IP five-tuple rules into a sparse rule set or a dense rule set according to the mask length; S2, for the sparse rule set, adopting the pre-IP filtering method to construct its corresponding IP HASH table; S3, for the dense rule set, constructing its corresponding TRIE tree; S4, matching the IP five-tuple to be matched by querying the IP HASH table and the TRIE tree. The present invention optimizes various indicators during compilation under large-capacity rules by dividing and conquering the rules, such as the peak memory occupancy and compilation time during compilation, and takes into account the high-performance matching speed during runtime. Based on the method of the present invention, the ability to match millions or even tens of millions of IP five-tuple rules is achieved on a general-purpose processor.

Description

A method and system for matching IP quintuples under large-capacity rules

Technical Field

The invention belongs to the field of IP (Internal Protocol) communication technology, and in particular relates to an IP quintuple matching method and system under a large-capacity rule.

Background technique

IP quintuple is a communication term, the English name is five-tuple or 5-tuple, which usually refers to a session represented by five fields such as source IP, source port, destination IP, destination port, and the layer 4 protocol.

In the field of network security, with the increasing number of network threats, the rule capacity demand for IP five-tuple rules has rapidly increased to the order of millions. Five-tuple-based packet filtering technology is often used in the field of network data packet analysis and packet classification, such as access control lists (ACLs) in firewalls and routers. The current TRIE tree-based IP matching method has good performance in matching, but the explosive growth of memory in the compilation stage and the slow compilation speed make it only suitable for small-scale rule sets within 200,000; when there are millions of rules, it cannot be used due to memory or compilation speed.

Summary of the invention

In view of the above-mentioned deficiencies in the prior art, the IP five-tuple matching method and system under large-capacity rules provided by the present invention solve the problem that the existing IP five-tuple matching method cannot be used when the rule capacity is too large.

In order to achieve the above-mentioned invention object, the technical solution adopted by the present invention is: an IP quintuple matching method under a large-capacity rule, comprising the following steps:

S1. Divide the large-capacity IP five-tuple rules into sparse rule sets or dense rule sets according to the mask length;

S2. For sparse rule sets, use the pre-IP filtering method to build the corresponding IP HASH table;

S3. For a dense rule set, construct its corresponding TRIE tree;

S4. Match the IP quintuples to be matched by querying the IP HASH table and the TRIE tree.

Furthermore, in step S1, the IP quintuple rules whose mask length of any one of the source IP and the destination IP in the IP quintuple is greater than a preset mask length threshold are divided into a sparse rule set, otherwise they are divided into a dense rule set.

Furthermore, in step S2, the constructed IP HASH table includes a source IP HASH table and a destination IP HASH table; the method for constructing the IP HASH table is:

S21, using the IP address with a larger mask length in the source IP or destination IP in the IP five-tuple rule as a pre-filtering rule;

S22, perform IP expansion on the IP address used as the pre-filtering rule, and insert it into the IP HASH table as the pre-rule;

S23. Use the IP address of the pre-filtering rule as the key of the IP HASH table, and store the remaining rules as the Value in the IP HASH table.

Furthermore, in step S3, the method for constructing the TRIE tree is specifically as follows:

S31, expand each rule of the IP quintuple according to a preset step length, and insert it into the TRIE tree level by level to construct a TRIE tree of a single rule;

S32. Merge the TRIE trees of the individual rules and add them into the global TRIE tree as the TRIE tree of the dense rule set.

Furthermore, in step S31, when merging the TRIE trees of each single rule into the global TRIE tree, first search for the same node under the same path and determine its union, and then add the segmentation result of the union as a new node into the global TRIE tree.

Furthermore, in step S4:

When querying the TRIE tree, determine whether there is a matching IP quintuple in the TRIE tree;

If yes, the match is successful, and the 5-tuple rule ID of the successful match is added to the hit result set;

If not, the match fails;

When querying the IP HASH table, extract the source IP and destination IP, and determine whether the source IP and destination IP addresses exist in the corresponding IP HASH table;

If yes, use the Value structure of the corresponding IP HASH table to perform numerical comparison to determine whether the subsequent rules match; if yes, the match is successful, and the 5-tuple rule ID of the successful match is added to the hit result set; if no, the match fails;

If not, the match fails.

An IP quintuple matching system, comprising:

Rule set division unit: used to divide large-capacity IP quintuples into rule set types, including dense rule sets and sparse rule sets;

Query table construction unit: used to construct a corresponding query table according to the rule set type, including an IP HASH table and a TRIE tree;

Rule matching unit: used to perform rule matching on the IP quintuple to be matched in each query table to obtain the matching result.

Furthermore, in the rule set division unit, when the mask length of any one of the source IP and the destination IP in the IP quintuple is greater than a preset mask length threshold, the IP quintuple rule is divided into a sparse rule set, otherwise it is divided into a dense rule set.

Furthermore, in the query table construction unit, a corresponding IP HASH table is constructed for the sparse rule set, which includes a source IP HASH table and a destination IP HASH table; in the IP HASH table, the source IP or the destination IP is expanded as a pre-rule and a key of the IP HASH table, and the remaining rules are stored as Values in the IP HASH table;

For dense rule sets, each rule of the IP quintuple is expanded to construct a TRIE tree of a single rule, and then merged and added to the global TRIE tree.

Further, in the rule matching unit, for the IP quintuple to be matched, when all the rules of the IP quintuple to be matched exist in the TRIE tree, the match is successful, and the id of the IP quintuple to be matched is stored in the hit result set as the matching result;

For the quintuple to be matched, when the source IP or destination IP of the quintuple to be matched exists in the IP HASH table, and the remaining rules obtained by searching the corresponding IP HASH table are matched, the match is successful, and the id of the quintuple to be matched is stored in the hit result set as the matching result.

The beneficial effects of the present invention are:

(1) The present invention optimizes various indicators during compilation under large-capacity rules by dividing and conquering rules, such as peak memory usage and compilation time during compilation, while taking into account high-performance matching speed during runtime.

(2) Based on the method of the present invention, a general-purpose processor is capable of matching millions or even tens of millions of IP quintuple rules.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a flow chart of an IP quintuple matching method under a large-capacity rule provided by the present invention.

FIG. 2 is a schematic diagram of constructing an IP HASH table provided by the present invention.

FIG. 3 is a representation of the content of a rule with a rule ID of 100 provided by the present invention.

FIG4 is a schematic diagram of constructing a TRIE tree provided by the present invention.

FIG5 is a schematic diagram of rule merging provided by the present invention.

Detailed ways

The specific implementation modes of the present invention are described below so that those skilled in the art can understand the present invention. However, it should be clear that the present invention is not limited to the scope of the specific implementation modes. For those of ordinary skill in the art, as long as various changes are within the spirit and scope of the present invention as defined and determined by the attached claims, these changes are obvious, and all inventions and creations utilizing the concept of the present invention are protected.

Embodiment 1:

The embodiment of the present invention provides an IP quintuple matching method under a large-capacity rule, as shown in FIG1 , comprising the following steps:

S1. Divide the large-capacity IP five-tuple rules into sparse rule sets or dense rule sets according to the mask length;

S2. For sparse rule sets, use the pre-IP filtering method to build the corresponding IP HASH table;

S3. For a dense rule set, construct its corresponding TRIE tree;

S4. Match the IP quintuples to be matched by querying the IP HASH table and the TRIE tree.

In step S1 of the embodiment of the present invention, the mask length threshold is determined according to the hardware resources. Generally, the longer the mask length is, the more memory will be occupied during compilation, and the faster the matching speed will be during matching operation. Therefore, a mask length threshold is required according to the memory capacity of the physical machine. In this embodiment, taking the test environment with 256G memory as an example, the mask length threshold is selected as 24.

In step S1 of an embodiment of the present invention, in a large-capacity IP quintuple, the IP quintuple rules whose mask length of any one of the source IP and the destination IP in the IP quintuple is greater than a preset mask length threshold are divided into a sparse rule set, and vice versa, they are divided into a dense rule set; in this embodiment, the IP quintuple rules are divided so that in subsequent matching, the expansion of the dense rules will generate more nodes, and the number of sparse rule nodes after expansion is much smaller than the number of nodes when the dense rules are expanded.

In step S2 of the embodiment of the present invention, the constructed IP HASH table includes a source IP HASH table and a destination IP HASH table; in this embodiment, for the rule features of the sparse rule set, which include clear IP features, a pre-IP filtering method is adopted to expand the IPs whose masks are greater than the mask length threshold, insert them into the HASH table as pre-rules, and associate the pre-rules with the remaining rules. Specifically, in step S2 of this embodiment, the method for constructing the IP HASH table is:

S21, using the IP address with the larger mask length in the source IP and the destination IP in the IP five-tuple rule as a pre-filtering rule;

S22, perform IP expansion on the IP address used as the pre-filtering rule, and insert it into the IP HASH table as the pre-rule;

S23. Use the IP address of the pre-filtering rule as the key of the IP HASH table, and store the remaining rules as the Value in the IP HASH table.

In this embodiment, the following example is provided for the construction of the IP HASH table:

Select an IP address with a larger mask length as the pre-filtering rule. For example, if the rule id is 100 and the rule content is [protocol is 6][source IP address 192.168.255.255/16][source port 80][destination IP address 224.1.1.1/30][destination port 8888], select 224.1.1.1/30 as the filtering rule, and the expanded set is [224.1.1.0, 224.1.1.1, 224.1.1.2, 224.1.1. 3], in the calculation, 32-bit unsigned numbers are used as 0xe0010100, 0xe0010101, 0xe0010102, 0xe0010103, which are inserted into the HASH table, and the remaining items are encoded and stored as tuple_plane structure, resulting in the HASH table structure shown in Figure 2. In the subsequent rule matching, the hash table is used to associate the previous rule and tuple_plane. Only when the previous rule hits, the tuple_plane is used for the final verification of whether it matches.

In step S3 of the embodiment of the present invention, for the dense rule set, according to its rule characteristics, the mask is expanded for the IP quintuple with a step length of 1 to construct a TRIE tree with a depth of 13 levels; specifically, the method for constructing the TRIE tree is as follows:

S31, expand each rule of the IP quintuple according to a preset step length, and insert it into the TRIE tree level by level to construct a TRIE tree of a single rule;

In this embodiment, the preset step size is set to 1;

S32. Merge the TRIE trees of the individual rules and add them into the global TRIE tree as the TRIE tree of the dense rule set.

In this embodiment, the following example is provided for the construction of a TRIE tree:

Expand with a step length of 1 byte and insert into the TRIE tree level by level to build a single regular TRIE tree;

For example, for a rule id of 100, the rule content is [protocol is 6][source IP address 192.168.255.255/16][source port 80][destination IP address 224.1.1.1][destination port 8888], and the rule occupies 13 bytes in the memory, as shown in FIG3 ;

Take the content 6 of the first byte to establish a TRIE node, pointing to the node content 192 (0xc0 in hexadecimal) corresponding to the second byte, and repeat this process to complete the construction of the TRIE tree. The compiled TRIE model is shown in Figure 4, a TRIE tree with a depth of 13.

In step S31 of this embodiment, when merging the TRIE trees of each single rule into the global TRIE tree, first search for the same node under the same path and determine its union, and then add the segmentation result of the union as a new node to the global TRIE tree.

In this embodiment, the merging of IP quintuple rules 192.168.255.255/16 and 192.168.64.255/23 is taken as an example, and the merging process is shown in FIG5 , wherein dark colors represent deleted nodes and light colors represent new nodes after the merging; wherein, TRIE_A and TRIE_B have the same prefix path [192->168], and the third-level interval [0-255] is divided into three intervals [0-63], [64-65], and [66-255] by the third-level node [64-65] of TRIE_B.

In step S4 of the embodiment of the present invention:

When querying the TRIE tree, determine whether there is a matching IP quintuple in the TRIE tree;

If yes, the match is successful, and the 5-tuple rule ID of the successful match is added to the hit result set;

If not, the match fails;

When querying the IP HASH table, extract the source IP and destination IP, and determine whether the source IP and destination IP addresses exist in the corresponding IP HASH table;

If yes, use the Value structure of the corresponding IP HASH table to perform numerical comparison to determine whether the subsequent rules match; if yes, the match is successful, and the 5-tuple rule ID of the successful match is added to the hit result set; if no, the match fails;

If not, the match fails.

In this embodiment, according to the compiled data structures of the source IP HASH table, the destination IP HASH table and the TRIE tree, in the matching process, it is only necessary to complete the query of these three tables to complete the fast matching of the IP quintuple.

Embodiment 2:

This embodiment provides an IP quintuple matching system of the IP quintuple matching method corresponding to the IP quintuple matching method in Embodiment 1, including:

Rule set division unit: used to divide large-capacity IP quintuples into rule set types, including dense rule sets and sparse rule sets;

Query table construction unit: used to construct a corresponding query table according to the rule set type, including an IP HASH table and a TRIE tree;

Rule matching unit: used to perform rule matching on the IP quintuple to be matched in each query table to obtain the matching result.

In the rule set division unit in this embodiment, when the mask length of any one of the source IP and the destination IP in the IP quintuple is greater than a preset mask length threshold, the IP quintuple rule is divided into a sparse rule set, otherwise it is divided into a dense rule set.

In the query table construction unit in this embodiment, a corresponding IP HASH table is constructed for a sparse rule set, which includes a source IP HASH table and a destination IP HASH table; in the IP HASH table, the source IP or the destination IP is expanded as the preceding rule and key of the IP HASH table, and the remaining rules are stored as Values in the IP HASH table; for a dense rule set, each rule of the IP quintuple is expanded to construct a TRIE tree of a single rule, and the rules are merged and added to the global TRIE tree.

In the rule matching unit in this embodiment, for the IP quintuple to be matched, when all the rules of the IP quintuple to be matched exist in the TRIE tree, the match is successful, and the id of the IP quintuple to be matched is stored in the hit result set as the matching result;

For the quintuple to be matched, when the source IP or destination IP of the quintuple to be matched exists in the IP HASH table, and the remaining rules obtained by searching the corresponding IP HASH table are matched, the match is successful, and the id of the quintuple to be matched is stored in the hit result set as the matching result.

In this embodiment, according to the compiled data structures of the source IP HASH table, the destination IP HASH table and the TRIE tree, in the matching process, it is only necessary to complete the query of these three tables to complete the fast matching of the IP quintuple.

Embodiment 3:

The embodiment of the present invention provides a comparative test example of the matching method in embodiment 1;

In this embodiment, the hardware environment is as follows:

System: CentOS Linux release 7.9.2009

CPU: Intel(R) Xeon(R) Gold 6230R CPU@2.10GHz

Memory: 256G

The test input is 100 million IP quintuples;

The test results are shown in Table 1;

Table 1: Test results of this method

The comparison of DPDK-ACL test results is shown in Table 2;

Table 2: DPDK-ACL test results

When using DPDK-ACL to compile 1 million network segment rules, the compilation time is greater than 20 minutes and the compilation memory usage is greater than 40G, so the compilation is stopped.

By comparing the above table, we can see that:

Compared with dpdk-acl:

TestCase1 matches 1 million precise rules, and the matching speed is similar. TestCase2, in the case of 1 million network segment rules, cannot be processed by dpdk-acl; the solution of the present invention can handle it and can also quickly complete the matching.

In TestCase3, TestCase4, TestCase5, and TestCase6, the number of rules is further increased to increase the test pressure, and the solution of the present invention can also complete the compilation and fast matching of the rules.

Based on this, the solution of the present invention runs faster when there are a small number of rules. As the number of rules increases, the matching speed slows down in a smooth trend rather than suddenly decreasing when a certain number threshold is reached.

The present invention uses specific embodiments to illustrate the principles and implementation methods of the present invention. The description of the above embodiments is only used to help understand the method of the present invention and its core idea. At the same time, for those skilled in the art, according to the idea of the present invention, there will be changes in the specific implementation methods and application scope. In summary, the content of this specification should not be understood as a limitation on the present invention.

Those skilled in the art will appreciate that the embodiments described herein are intended to help readers understand the principles of the present invention, and should be understood that the protection scope of the present invention is not limited to such specific statements and embodiments. Those skilled in the art can make various other specific variations and combinations that do not deviate from the essence of the present invention based on the technical revelations disclosed by the present invention, and these variations and combinations are still within the protection scope of the present invention.

Claims (3)

1. The IP five-tuple matching method under the large-capacity rule is characterized by comprising the following steps of:

S1, dividing the high-capacity IP five-tuple rule into a sparse rule set or a dense rule set according to the mask length;

s2, for the sparse rule set, constructing a corresponding IP HASH table by adopting a preposed IP filtering method;

s3, constructing a TRIE tree corresponding to the dense rule set;

S4, searching an IP HASH table and a TRIE, and matching the IP five-tuple to be matched;

In the step S1, the rule of the IP five-tuple with any one mask length greater than the preset mask length threshold value is divided into a sparse rule set, and otherwise, the rule is divided into a dense rule set;

in the step S2, the constructed IP HASH table comprises a source IP HASH table and a destination IP HASH table;

the method for constructing the IP HASH table comprises the following steps:

S21, taking an IP address with a larger mask length in a source IP or a destination IP in the IP five-tuple rule as a pre-filtering rule;

s22, carrying out IP expansion on the IP address serving as a pre-filtering rule, and inserting the IP address serving as the pre-filtering rule into an IP HASH table;

s23, taking the IP address of the pre-filtering rule as a key of an IP HASH table, and storing the remaining rule as Value in the IP HASH table;

In the step S3, the method for constructing the TRIE specifically includes:

S31, expanding each rule of the IP five-tuple according to a preset step length, and gradually inserting the rule into the TRIE number to construct a TRIE of a single rule;

S32, merging and adding the TRIE of each single rule into a global TRIE to serve as a TRIE of a dense rule set;

in the step S31, when the TRIE of each single rule is added to the global TRIE in a merging manner, the same node under the same path is searched first and the union is determined, and the division result of the union is added to the global TRIE as a new node.

2. The method for matching IP five-tuple under high-capacity rule according to claim 1, wherein in step S4:

judging whether a matched IP five-tuple exists in the TRIE or not when inquiring the TRIE;

if yes, matching is successful, and the matched five-tuple rule id is added into a hit result set;

if not, the matching fails;

when the IP HASH table is inquired, extracting a source IP and a destination IP in the IP HASH table, and judging whether the source IP and the destination IP address exist in the corresponding IP HASH table or not;

If yes, using the Value structure of the corresponding IP HASH table to carry out numerical comparison and judging whether the follow-up rules are matched; if yes, matching is successful, and the matched five-tuple rule id is added into a hit result set; if not, the matching fails;

if not, the matching fails.

3. An IP five-tuple matching system based on the IP five-tuple matching method under the high-capacity rule of any one of claims 1 to 2, comprising:

Rule set dividing unit: the rule set type classification method is used for carrying out rule set type classification on the large-capacity IP five-tuple, and comprises a dense rule set and a sparse rule set;

The lookup table construction unit: the method comprises the steps of constructing a corresponding lookup table according to rule set types, wherein the lookup table comprises an IP HASH table and a TRIE;

rule matching unit: the method comprises the steps of performing rule matching on IP five-tuple to be matched in each lookup table to obtain a matching result;

in the rule set dividing unit, when any one mask length of a source IP and a destination IP in the IP quintuple is larger than a preset mask length threshold value, dividing the IP quintuple rule into a sparse rule set, and otherwise, dividing the IP quintuple rule into a dense rule set;

In the lookup table construction unit, constructing a corresponding IP HASH table for the sparse rule set, wherein the IP HASH table comprises a source IP HASH table and a target IP HASH table; in the IP HASH table, a source IP or a destination IP is unfolded to be used as a front rule and a key of the IP HASH table, and the rest rules are stored in the IP HASH table as values;

For the dense rule set, developing each rule of the IP five-tuple to construct a TRIE of a single rule, and merging and adding the TRIE into a global TRIE;

in the rule matching unit, for the to-be-matched IP quintuples, when all rules of the to-be-matched IP quintuples exist in the TRIE, the matching is successful, and the to-be-matched IP quintuple ids are stored in a hit result set to be used as a matching result;

And for the to-be-matched quintuples, when the source IP or the destination IP of the to-be-matched IP quintuples exists in the IP HASH table and the residual rules obtained by searching the corresponding IP HASH table are matched, the matching is successful, and the to-be-matched IP quintuple id is stored into a hit result set to be used as a matching result.