[go: up one dir, main page]

CN119363477B - Prefix-based IP blacklist storage and retrieval method and system - Google Patents

Prefix-based IP blacklist storage and retrieval method and system Download PDF

Info

Publication number
CN119363477B
CN119363477B CN202411875228.5A CN202411875228A CN119363477B CN 119363477 B CN119363477 B CN 119363477B CN 202411875228 A CN202411875228 A CN 202411875228A CN 119363477 B CN119363477 B CN 119363477B
Authority
CN
China
Prior art keywords
blacklist
address
cidr
search tree
prefix
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202411875228.5A
Other languages
Chinese (zh)
Other versions
CN119363477A (en
Inventor
包华宇
殷庆荣
颜科
高庆官
谢峥
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nanjing Cyber Peace Technology Co Ltd
Original Assignee
Nanjing Cyber Peace Technology Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nanjing Cyber Peace Technology Co Ltd filed Critical Nanjing Cyber Peace Technology Co Ltd
Priority to CN202411875228.5A priority Critical patent/CN119363477B/en
Publication of CN119363477A publication Critical patent/CN119363477A/en
Application granted granted Critical
Publication of CN119363477B publication Critical patent/CN119363477B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/02—Network architectures or network communication protocols for network security for separating internal from external traffic, e.g. firewalls
    • H04L63/0227—Filtering policies
    • H04L63/0236—Filtering by address, protocol, port number or service, e.g. IP-address or URL
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L61/00—Network arrangements, protocols or services for addressing or naming
    • H04L61/09—Mapping addresses
    • H04L61/25—Mapping addresses of the same type
    • H04L61/2503—Translation of Internet protocol [IP] addresses
    • H04L61/251—Translation of Internet protocol [IP] addresses between different IP versions
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L61/00—Network arrangements, protocols or services for addressing or naming
    • H04L61/09—Mapping addresses
    • H04L61/25—Mapping addresses of the same type
    • H04L61/2503—Translation of Internet protocol [IP] addresses
    • H04L61/2557—Translation policies or rules
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/10—Network architectures or network communication protocols for network security for controlling access to devices or network resources
    • H04L63/101—Access control lists [ACL]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/40—Network security protocols
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2101/00—Indexing scheme associated with group H04L61/00
    • H04L2101/30—Types of network names
    • H04L2101/35—Types of network names containing special prefixes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2101/00—Indexing scheme associated with group H04L61/00
    • H04L2101/60—Types of network addresses
    • H04L2101/604—Address structures or formats

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Hardware Design (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

The invention discloses a prefix-based IP blacklist storage and retrieval method and system. In the storage method of the invention, all black lists are classified according to CIDR addresses and single IP addresses, adjacent single IP addresses are combined into CIDR address forms, the CIDR addresses are converted into a format of prefix plus free address range, the free address ranges of the same prefix are combined, wherein the prefix is expressed as hexadecimal form, a base tree structure is used for constructing a black list search tree, the path of the search tree is the public prefix of the CIDR addresses, the free address range is stored in a leaf node, and the free address range of the single IP address is contracted to 0. In the searching method, the single IP address is converted into hexadecimal form, iterative searching is carried out on the blacklist searching tree, and whether the CIDR address or the single IP address in the blacklist is hit or not is judged through logic. The invention can reduce the storage space requirement of the blacklist and improve the retrieval efficiency.

Description

Prefix-based IP blacklist storage and retrieval method and system
Technical Field
The invention relates to an IP blacklist storage and retrieval method and system based on prefix, belonging to the technical field of network security.
Background
In a security protection system such as a Web application firewall (Web Application Firewall, WAF), a user may define a blacklist based on a single IP address or a generic-Domain-free Routing (CIDR) address, typically in the following format:
{ "ip_blacklist": [
"1.1.1.1",
"10.2.0.0/24"
] }
Where 1.1.1.1 is a particular blacklist IP,10.2.0.0/24 indicates that all IPs with IP addresses 10.2.0.0 to 10.2.0.255 are blacklist. The WAF system parses the IP parameters in the key parts (e.g., headers) in the request and decides whether to release the request based on whether it matches the blacklist.
In the actual system operation process, users can dynamically adjust blacklist configuration according to network threats or self-safety construction requirements. After the blacklist is frequently adjusted, the problem that 1, a method for uniformly searching the IP blacklist segment based on CIDR and a single value form is lacking is brought. Converting CIDR into single blacklist IP for storing respectively, wasting storage space and reducing blacklist searching speed. 2. The user can change the blacklist frequently according to the requirement, and the storage space can not be dynamically adjusted according to the change of the blacklist, so that the storage and retrieval efficiency is low.
Disclosure of Invention
Aiming at the problems in the prior art, the invention aims to provide an IP blacklist storage method and a search method based on prefixes, and a corresponding computer system and program product, so as to reduce the storage space requirement of the blacklist and improve the search efficiency.
The technical scheme is that in order to achieve the aim of the invention, the invention adopts the following technical scheme:
in a first aspect, the present invention provides a prefix-based IP blacklist storage method, including the steps of:
Step 11, acquiring all blacklists configured by a user, and classifying according to CIDR addresses and single IP addresses to obtain a CIDR classification set and a single IP classification set;
Step 12, merging adjacent single IP addresses in the single IP classification set into a CIDR address form, and moving the single IP addresses into the CIDR classification set;
step 13, formatting each CIDR address in the CIDR classification set, and converting the CIDR address into a format of adding a prefix into a free address range, wherein the prefix is expressed in hexadecimal form;
step 14, traversing the formatted CIDR classification set, and merging the free address ranges of the same prefix;
step 15, repeating the step 14 until the combined CIDR classification set is not changed;
Step 16, constructing a blacklist search tree based on the combined CIDR classification set, and using a base tree as a basic storage structure, wherein the path of the blacklist search tree is a common prefix of CIDR addresses, and free address ranges are stored in leaf nodes;
Step 17, traversing the single IP classification set, representing each single IP address as hexadecimal form, and executing steps 18 to 19 on each single IP address;
Step 18, judging whether the single IP address hits the blacklist search tree, if yes, returning to step 17, and continuing the next single IP address, otherwise, entering step 19;
And step 19, adding the single IP address in hexadecimal form into a blacklist search tree, and setting the free address range of the leaf node to be in the form of contracted 0.
Further, the prefix of the CIDR address is determined by taking bits of X- (X mod 8) as the prefix address, mod represents the remainder operation, X is the network bit number of the CIDR address, and the free address range of the CIDR address is determined by calculating a range [0, 2 Y -1] according to the value of Y=8- (X mod 8), the initial address A of the free address range is the result of the value of the first 8 bits of the CIDR address after the prefix is removed and B, the free address range is [ A, A+2 Y -1], B is an 8-bit value, the first 8-Y bits are 1, and the last Y bits are 0.
Further, in step 18, the step of determining whether the single IP address hits in the blacklist search tree includes performing iterative search on the single IP address M in hexadecimal form, where the first iteration is denoted as k=1, and the kth iteration calculating step includes:
Step 181, taking the character substring of [0, k multiplied by 2-1] bit in M, and judging whether the character substring exists in the blacklist search tree;
step 182, if the substring does not exist in the blacklist search tree, returning to the missed blacklist and ending, otherwise, entering step 183;
Step 183, judging whether the node in the current sub-string is a leaf node, if so, adding 1 to k, and returning to step 181, otherwise, entering step 184;
Step 184, if the value of k is length (M)/2, and length (M) is the character length of M, judging whether the free address range in the current leaf node is in the form of 0, if yes, returning a hit blacklist, otherwise, returning a miss blacklist, if the value of k is less than length (M)/2, proceeding to step 185;
And 185, taking data of [ kX 2, length (M) ] bit of M, converting the data into a decimal expression form, judging whether the data is in a free address range of a leaf node, if yes, returning a hit blacklist, and otherwise, returning a miss blacklist.
And if the new blacklist is added, judging whether the single IP address to be added hits the blacklist search tree, if yes, ending, otherwise, combining adjacent single IP addresses into a CIDR form in a set formed by the original single IP address and the single IP address to be added to obtain a new CIDR set, combining the obtained new CIDR set with the original CIDR classified set, constructing a new blacklist search tree based on the combined CIDR classified set and the single IP address classified set, and replacing the original blacklist search tree after construction is finished.
Further, when the blacklist is newly added, if the newly added address is the CIDR address, combining the CIDR address to be newly added with the original CIDR classified set, keeping the original single IP classified set unchanged, constructing a new blacklist search tree based on the combined CIDR classified set and the original single IP classified set, and replacing the original blacklist search tree after the construction is completed.
And if the free address range of the leaf node in the hit result is in the contracted form of 0, deleting the single IP address to be deleted from the original single IP classification set, constructing a new blacklist search tree based on the original CIDR classification set and the new single IP classification set, and replacing the original blacklist search tree with the new blacklist search tree after the new blacklist search tree is constructed.
And if the CIDR address to be deleted is deleted, converting the CIDR address to be deleted into a format of adding a prefix with a free address range, searching the prefix of the CIDR address to be deleted in a black list search tree, and ending if the search result is empty, otherwise, deleting the CIDR address to be deleted from the original CIDR classification set, constructing a new black list search tree based on the new CIDR classification set and the original single IP classification set, and replacing the original black list search tree with the new black list search tree after the new black list search tree is constructed.
In a second aspect, the present invention provides a prefix-based IP blacklist searching method, including the steps of:
Step 21, each single IP address is expressed in hexadecimal form;
step 22, performing iterative search on a single IP address M in hexadecimal form in a blacklist search tree, wherein the blacklist search tree uses a radix tree as a basic storage structure, the path of the search tree is a common prefix of a CIDR address, a free address range is stored in a leaf node, the free address range of the leaf node is set to be in a contracted 0 form for a single IP address, the first iteration is recorded as k=1, and the kth round of iterative calculation step comprises the following steps:
step 221, taking the character substring of [0, k multiplied by 2-1] bit in M, and judging whether the character substring exists in the blacklist search tree;
Step 222, if the substring does not exist in the blacklist search tree, returning to the missed blacklist and ending, otherwise, entering step 223;
Step 223, judging whether the node in the current sub-string is a leaf node, if so, adding 1 to k, and returning to step 221, otherwise, entering step 224;
Step 224, if the value of k is length (M)/2, length (M) is the character length of M, judging whether the free address range in the current leaf node is in the form of appointed 0, if yes, returning a hit blacklist, otherwise, returning a miss blacklist, if the value of k is not length (M)/2, entering step 225;
and 225, converting the character substring of the [ k multiplied by 2, length (M) ] bit of M into a decimal expression form, judging whether the character substring is in the free address range of the leaf node, if so, returning to hit the blacklist, otherwise, returning to miss the blacklist.
In a third aspect, the present invention provides a computer system comprising a memory, a processor and a computer program/instruction stored on the memory and executable on the processor, the computer program/instruction implementing the steps of the prefix-based IP blacklist storage method or the prefix-based IP blacklist retrieval method described above when executed by the processor.
In a fourth aspect, the present invention provides a computer program product comprising computer programs/instructions which when executed by a processor implement the above-described prefix-based IP blacklist storage method, or the steps of the prefix-based IP blacklist retrieval method.
Compared with the prior art, the invention has the following advantages:
1. The invention uniformly stores the single IP address and the CIDR address in a form of combining a prefix expression and a free address range (the free address range of the single IP address is contracted to 0). Regardless of whether the user uses a single IP address or a CIDR address to define the blacklist, the occupied memory space is small.
2. The invention improves the efficiency of blacklist IP searching by encoding and compressing the height of the blacklist searching tree. For the address corresponding to IPv4, the compressed tree height is 8 at maximum, that is, a maximum of 4 searches are performed in a multi-way tree to reach a conclusion.
3. The invention can automatically combine and split the blacklist expression according to the adjustment of the user configuration, ensures the lowest memory occupancy rate, reduces unnecessary blacklist searching paths and improves the searching efficiency.
Drawings
FIG. 1 is a diagram illustrating an exemplary process for formatting CIDR addresses in accordance with embodiments of the present invention.
Fig. 2 is a flowchart of a prefix-based IP blacklist storage method according to an embodiment of the present invention.
Fig. 3 is an exemplary diagram of a prefix-based blacklist search tree in an embodiment of the present invention.
Fig. 4 is a flowchart of a prefix-based IP blacklist searching method according to an embodiment of the present invention.
Fig. 5 is a flowchart of a process for adding a new single IP address to a blacklist in an embodiment of the present invention.
FIG. 6 is a flowchart of a process for adding a CIDR address to a blacklist according to an embodiment of the present invention.
Fig. 7 is a flowchart of a blacklist deletion list IP address processing according to an embodiment of the present invention.
FIG. 8 is a flowchart of a process for blacklist deletion CIDR address according to an embodiment of the present invention.
Detailed Description
The technical scheme of the invention will be clearly and completely described below with reference to the accompanying drawings and specific embodiments.
First, the formatting and encoding of the CIDR network address according to the present invention will be described.
The CIDR network address is formatted by adding a free address range to the prefix, and the calculation method is as follows:
For CIDR addresses in a form such as 192.169.1.4/X, the bits of X- (X mod 8) are taken as prefix addresses, mod representing the remainder operation. Assuming x=30, then the first 30- (30 mod 8) =24 bits are taken as the prefix address, i.e. prefix= 192.169.1.
The range of variation of the suffix address is calculated from the value of y=8- (X mod 8). Assuming x=30, then y=8- (30 mod 8) =2, the free range of variation of the suffix address is [0, 2^Y-1] = [0, 3], and the starting address a of the suffix is the result of the values of the first 8 bits (4 in 192.169.1.4/X) and B of the CIDR address after the prefix has been removed. Where B is an 8-bit value, the first 8-Y bits are 1 and the last Y bits are 0. The free address range is [ A, A+2 Y -1], and for 192.169.1.4/30 the starting address is 4, then the free address range of the CIDR is [0+4, 3+4] = [4, 7].
The calculation methods of IPv6 and IPv4 are consistent. For an IPv6 address of the form ef0 b:/10, the prefix is ef, the free address corresponds to y=8- (10 mod 8) =6, and the free range of variation of the suffix address is [0, 2^Y-1] = [0, 63]. The starting address of the free range is the result of the subsequent 8 bits and B of the CIDR address after the prefix is removed. Where B is an 8-bit value, the first 8-Y bits are 1 and the last Y bits are 0.
Converting each eight bits of the obtained prefix address into hexadecimal system, and carrying out unified formatting. For 192.169.1, 192 has a hexadecimal number of C0, 169 has a hexadecimal number of A9, 1 has a hexadecimal number of 01, and the formatted prefix is C0A901. The final 192.169.1.4/30 formatting result is prefix = C0a901, free address range [4,7]. The prefix P, the free address range Q, cidr=p+q, and fig. 1 illustrates the formatted representation of the CIDR address.
As shown in fig. 2, the method for storing the IP blacklist based on the prefix disclosed in the embodiment of the present invention specifically includes the following steps:
And 11, acquiring all blacklists configured by a user, and classifying according to the CIDR address and the single IP address to obtain a CIDR classification set and a single IP classification set. Wherein the CIDR classification set is denoted as s= { S1, S2,..sn }, the single IP classification set is denoted as r= { R1, R2,..rm }, n and m are respectively the CIDR address and the number of single IP addresses, si is the i-th CIDR address, i=1, 2,...
Step 12, traversing the single IP classification set R, merging the adjacent single IP addresses into CIDR address form, adding the single IP addresses into the CIDR classification set S, and simultaneously removing the IP addresses from the R. Such as 192.168.0.4 and 192.168.0.5 may be combined to a CIDR of 192.168.0.5/31, and 192.168.0.4, 192.168.0.5, 192.168.0.6, 192.168.0.7 may be combined to a CIDR of 192.168.0.5/30.
Step 13, format each CIDR address in the set S, and convert the CIDR address into a format with prefix added with a free address range, i.e. S '= { { P1, Q1}, { P2, Q2}, { Pn', qn '}, where n' is the number of combined CIDR addresses, pi, qi is the prefix and the free address range of the i-th CIDR address, i=1, 2,...
Step 14, traversing the set S', and merging the free address ranges of the same prefix. The merging method is as follows:
If two free address ranges are contiguous in the integer domain, they are merged into one larger free address range. For two Q1 and Q2 that can be combined, the range is denoted as [ Q1min, Q1max ], [ Q2min, Q2max ], and the combined free address range is [ min (Q1 min, Q2 min), max (Q1 max, Q2 max) ].
For the free address range with the same prefix and discontinuous integer domain, no processing is performed.
For example 192.169.201.0/30,192.169.201.4/30,192.169.201.12/30 three CIDR, the formatted representations were ：192.169.201.0/30={C0A9C9, [0, 3]};192.169.201.4/30={C0A9C9, [4, 7]};192.169.201.12/30={C0A9C9, [12, 15]}; combined to { C0A9C9, [0, 7] }, { C0A9C9, [12, 15] }, respectively.
Step 15, repeat step 14 until the set S' is no longer changed.
And 16, constructing a blacklist search tree based on the set S', and using the base tree as a basic storage structure of the search tree, wherein the path of the search tree is a common prefix of CIDR, and the free address range is stored in the leaf node. A specific memory structure is shown in fig. 3.
And step 17, traversing the single IP classification set R, carrying out formatting coding on each IP address in a mode of converting each eight bits into hexadecimal, marking the obtained result as M, and executing the operations from step 18 to step 19 until all elements in R are traversed.
Step 18, based on the blacklist search tree constructed in step 16, referring to step 22 of a prefix-based IP blacklist search method described below, it is determined whether the current IP address hits the blacklist search tree, if yes, step 17 is skipped, and if not step 19 is skipped.
And step 19, adding M into the search tree, wherein the free address range of the leaf node is [0,0].
As shown in fig. 4, the IP blacklist searching method based on the prefix disclosed in the embodiment of the present invention specifically includes the following steps:
and step 21, formatting and encoding the single IP address in a mode of converting each eight bits into hexadecimal, and marking the obtained result as M. For 192.169.0.1, the encoded formatting result is m=c0a90001.
And step 22, iteratively searching in the blacklist search tree in the following way, and judging whether the IP hits the blacklist search tree. The first iteration is noted as k=1, the maximum number of iterations is 4 for IPv4 and 16 for IPv 6. The k-th round of iterative computation is as follows:
In step 221, the string with bits [0, kx2-1 ] in M is taken, and whether it exists in the blacklist search tree is determined, and for k=1, "C0" is taken as the string, and for k=3, "C0a900" is taken as the string.
Step 222, if the substring does not exist in the blacklist search tree, returning to the missed blacklist, ending the search flow, otherwise, jumping to step 223;
Step 223, judging whether the node in the current sub-string is a leaf node. If the node is a non-leaf node, k=k+1, step 221 is skipped, otherwise step 224 is skipped;
Step 224, if it has iterated to the last of M (i.e. k=length (M)/2, length (M) is the character length of M, k=4 for IPv 4), determine whether the data in the current leaf node is [0, 0], if so, return to hit blacklist, otherwise return to miss blacklist. If not iterating to M to the end, jumping to step 225;
And 225, converting the character substring of the [ kX 2, length (M) ] bit of M into a decimal expression form, marking the obtained result as N, and judging whether the N is in the free address range of the leaf node. If in the free address range, returning to hit the blacklist, otherwise, the range does not hit the blacklist.
For the query example shown in FIG. 3, 192.169.0.1 is detected in query path C0- > A9- >0001, hit by the detection rule of step 224, and 192.168.201.3 is detected in query path C0- > A9- > C9, hit by the detection rule of step 225.
Fig. 5 and 6 illustrate a process flow of adding a blacklist.
As shown in fig. 5, when a single IP address is newly added, the specific steps are as follows:
And step 31, executing a searching process of the single IP in the blacklist searching tree according to the IP blacklist searching method based on the prefix, and judging whether the IP address to be newly added hits the blacklist searching tree. If hit, the flow ends, otherwise jump to step 32.
Step 32, taking all existing single IP addresses and the single IP address to be newly added to form a set, traversingAll elements in the list are combined into CIDR form, and the obtained CIDR set is recorded asAt the same time fromThese merged single IP addresses are removed.
Step 33, willMerging with the original CIDR classification set S to obtain a set. Pair aggregationAndAnd executing the construction flow of the blacklist search tree according to the prefix-based IP blacklist storage method.
And step 34, after the blacklist search tree in step 33 is constructed, replacing the original blacklist search tree by the blacklist search tree.
As shown in fig. 6, when a CIDR address is newly added, the CIDR address to be newly added is combined with the original CIDR classification set S, the original single IP classification set R is kept unchanged, and a construction flow of a blacklist search tree is executed on the combined CIDR classification set and the original single IP classification set according to an IP blacklist storage method based on prefixes. After the new blacklist search tree is constructed, the original blacklist search tree is replaced by the new blacklist search tree.
Fig. 7 and 8 illustrate a process flow of deleting a blacklist.
As shown in fig. 7, when deleting a single IP address, the specific steps are as follows:
step 41, judging whether the to-be-deleted single IP address hits the blacklist search tree, if not, ending the flow, otherwise, jumping to step 42.
Step 42, if the free address range of the leaf node in the hit result is [0,0], the single IP address is directly deleted from the blacklist search tree, the process is ended, otherwise, the step 43 is skipped.
Step 43, deleting the single IP address from the original single IP classification set R, and constructing a new blacklist search tree with reference to steps 12 to 19.
And 45, after the new blacklist search tree is constructed, replacing the original blacklist search tree by the new blacklist search tree.
As shown in fig. 8, when the CIDR address is deleted, the specific steps are as follows:
And step 51, formatting the CIDR address to be deleted, and converting the CIDR address to a format of adding a prefix and a free address range.
And 52, searching the prefix of the CIDR address to be deleted in the blacklist search tree, if the search result is null, ending the flow, otherwise, jumping to the step 53.
Step 53, after deleting the CIDR address to be deleted from the original CIDR classification set S, a new blacklist search tree is constructed with reference to steps 12 to 19.
And 54, after the new blacklist search tree is constructed, replacing the original blacklist search tree by the new blacklist search tree.
The embodiment of the invention also discloses a computer system which comprises a memory, a processor and a computer program/instruction stored on the memory and capable of running on the processor, wherein the computer program/instruction realizes the steps of the method when being executed by the processor.
The embodiment of the invention also discloses a computer program product which comprises a computer program/instructions, wherein the computer program/instructions realize the steps of the method when being executed by a processor. The program/instruction code for implementing the methods of the present invention may be written in any combination of one or more programming languages. These program/instruction codes may be provided to a processor or controller of a general purpose computer, special purpose computer or other programmable data processing apparatus, such that the program/instruction codes, when executed by the processor or controller, cause the steps of the inventive method to be implemented. The program/instruction code may execute entirely on the machine, partly on the machine, as a stand-alone software package, partly on the machine and partly on a remote machine or entirely on the remote machine or server. The present invention is not described in detail in the present application, and is well known to those skilled in the art.

Claims (10)

1.一种基于前缀的IP黑名单存储方法，其特征在于，包括如下步骤：1. A prefix-based IP blacklist storage method, characterized in that it includes the following steps: 步骤11、获取用户配置的所有的黑名单，按CIDR地址和单IP地址进行分类，得到CIDR分类集合和单IP分类集合；Step 11: Obtain all blacklists configured by the user, classify them by CIDR address and single IP address, and obtain CIDR classification set and single IP classification set; 步骤12、将单IP分类集合中相临的单IP地址合并为CIDR地址形式，并移入到CIDR分类集合中；Step 12: merge adjacent single IP addresses in the single IP classification set into a CIDR address format and move them into the CIDR classification set; 步骤13、将CIDR分类集合中的每个CIDR地址进行格式化，转换为前缀加自由地址范围的格式，其中前缀表示为十六进制形式；Step 13, format each CIDR address in the CIDR classification set and convert it into a format of prefix plus free address range, where the prefix is expressed in hexadecimal form; 步骤14、遍历格式化后的CIDR分类集合，对相同前缀的自由地址范围进行合并；Step 14: traverse the formatted CIDR classification set and merge the free address ranges with the same prefix; 步骤15、重复步骤14直到合并后的CIDR分类集合不再变化；Step 15: Repeat step 14 until the merged CIDR classification set does not change; 步骤16、基于合并后的CIDR分类集合，构建黑名单搜索树，使用基数树作为基础存储结构，其中黑名单搜索树的路径为CIDR地址的公共前缀，叶子结点中存储自由地址范围；Step 16: Based on the merged CIDR classification set, a blacklist search tree is constructed, using a radix tree as a basic storage structure, wherein the path of the blacklist search tree is a common prefix of the CIDR address, and the leaf node stores the free address range; 步骤17、遍历单IP分类集合，将每个单IP地址表示为十六进制形式，对每个单IP地址执行步骤18到步骤19；Step 17, traverse the single IP classification set, express each single IP address in hexadecimal form, and execute steps 18 to 19 for each single IP address; 步骤18、判断单IP地址是否命中黑名单搜索树，如果命中则回到步骤17，继续下一个单IP地址；否则进入步骤19；Step 18: Determine whether the single IP address hits the blacklist search tree. If it hits, go back to step 17 and continue to the next single IP address; otherwise, go to step 19; 步骤19、将十六进制形式的单IP地址加入到黑名单搜索树中，叶子结点的自由地址范围设置为约定的0的形式。Step 19: Add the single IP address in hexadecimal format to the blacklist search tree, and set the free address range of the leaf node to the agreed 0 format. 2.根据权利要求1所述的一种基于前缀的IP黑名单存储方法，其特征在于，CIDR地址的前缀确定方式为：取X-(X mod 8)的比特位作为前缀地址，mod代表取余操作，X是CIDR地址的网络位数；CIDR地址的自由地址范围确定方式为：根据Y=8-(X mod 8)的值计算一个范围[0, 2Y-1]，自由地址范围的起始地址A为去除前缀后的CIDR地址的前8比特的数值与B的结果，自由地址范围为[A, A+2Y-1]，其中B为一个8比特的数值，前8-Y个比特为1，后Y个比特为0。2. A prefix-based IP blacklist storage method according to claim 1, characterized in that the prefix of the CIDR address is determined in the following manner: taking the bits of X-(X mod 8) as the prefix address, mod represents the remainder operation, and X is the number of network bits of the CIDR address; the free address range of the CIDR address is determined in the following manner: calculating a range [0, 2 Y -1] according to the value of Y=8-(X mod 8), the starting address A of the free address range is the result of the value of the first 8 bits of the CIDR address after removing the prefix and B, and the free address range is [A, A+2 Y -1], wherein B is an 8-bit value, the first 8-Y bits are 1, and the last Y bits are 0. 3.根据权利要求1所述的一种基于前缀的IP黑名单存储方法，其特征在于，步骤18中，判断单IP地址是否命中黑名单搜索树的步骤包括：对十六进制形式的单IP地址M进行迭代检索，第一轮迭代记为k=1，第k轮迭代计算步骤包括：3. According to the prefix-based IP blacklist storage method of claim 1, it is characterized in that in step 18, the step of determining whether a single IP address hits the blacklist search tree comprises: iteratively searching the single IP address M in hexadecimal form, the first round of iteration is denoted as k=1, and the kth round of iterative calculation steps comprises: 步骤181、取M中[0, k×2-1]位的字符子串，判断其在黑名单搜索树中是否存在；Step 181, take the character substring of [0, k×2-1] bits in M, and determine whether it exists in the blacklist search tree; 步骤182、如果子串在黑名单搜索树中不存在，返回未命中黑名单，结束；否则进入步骤183；Step 182: If the substring does not exist in the blacklist search tree, return to the missed blacklist and end; otherwise, go to step 183; 步骤183、判断当前子串命中的节点是否是叶子结点，如果是非叶子结点，将k加1后，返回步骤181；否则进入步骤184；Step 183, determine whether the node hit by the current substring is a leaf node. If it is a non-leaf node, add 1 to k and return to step 181; otherwise, go to step 184; 步骤184，如果k取值为lenth(M)/2，lenth(M)为M的字符长度，判断当前叶子结点中的自由地址范围是否为约定的0的形式，是则返回命中黑名单；否则返回未命中黑名单；如果k取值未到lenth(M)/2，进入步骤185；Step 184, if the value of k is lenth(M)/2, where lenth(M) is the character length of M, determine whether the free address range in the current leaf node is in the agreed form of 0, if so, return to the hit blacklist; otherwise, return to the miss blacklist; if the value of k is less than lenth(M)/2, proceed to step 185; 步骤185，取M的第[k×2，lenth(M)]位的数据，并转化为十进制的表达形式，判断是否在叶子结点的自由地址范围中，如果在则返回命中黑名单，否则返回未命中黑名单。Step 185, take the data of the [k×2, lenth(M)]th bit of M and convert it into a decimal expression, and determine whether it is in the free address range of the leaf node. If so, return the hit blacklist, otherwise return the miss blacklist. 4.根据权利要求1所述的一种基于前缀的IP黑名单存储方法，其特征在于，新增黑名单时，若新增的是单IP地址，判断待新增单IP地址是否命中黑名单搜索树，如果命中则结束；否则：在原有所有单IP地址和待新增单IP地址组成的集合中，将相邻的单IP地址合并为CIDR形式，得到新的CIDR集合，并将得到新的CIDR集合与原CIDR分类集合进行合并，基于合并后的CIDR分类集合和单IP地址分类集合构建新的黑名单搜索树，构建完成后替换原黑名单搜索树。4. According to the prefix-based IP blacklist storage method described in claim 1, it is characterized in that when adding a new blacklist, if a single IP address is added, it is determined whether the single IP address to be added hits the blacklist search tree, and if it hits, the process ends; otherwise: in the set consisting of all the original single IP addresses and the single IP address to be added, the adjacent single IP addresses are merged into CIDR format to obtain a new CIDR set, and the new CIDR set is merged with the original CIDR classification set, and a new blacklist search tree is constructed based on the merged CIDR classification set and the single IP address classification set, and the original blacklist search tree is replaced after the construction is completed. 5.根据权利要求1所述的一种基于前缀的IP黑名单存储方法，其特征在于，新增黑名单时，若新增的是CIDR地址，将待新增CIDR地址与原CIDR分类集合合并，保持原单IP分类集合不变，基于合并后的CIDR分类集合和原单IP分类集合构建新的黑名单搜索树，构建完成后替换原黑名单搜索树。5. According to the prefix-based IP blacklist storage method described in claim 1, it is characterized in that when a new blacklist is added, if the new address is a CIDR address, the CIDR address to be added is merged with the original CIDR classification set, the original single IP classification set is kept unchanged, and a new blacklist search tree is constructed based on the merged CIDR classification set and the original single IP classification set. After the construction is completed, the original blacklist search tree is replaced. 6.根据权利要求1所述的一种基于前缀的IP黑名单存储方法，其特征在于，删除黑名单时，若删除的是单IP地址，判断待删除单IP地址是否命中黑名单搜索树，如果未命中则结束；否则：若命中结果中叶子结点的自由地址范围为约定的0的形式，从黑名单搜索树中直接删除该待删除单IP地址，否则，从原单IP分类集合中删除该待删除单IP地址，基于原CIDR分类集合和新的单IP分类集合，构建新的黑名单搜索树，新的黑名单搜索树构建完成后，用其替换原黑名单搜索树。6. A prefix-based IP blacklist storage method according to claim 1, characterized in that, when deleting a blacklist, if a single IP address is deleted, it is determined whether the single IP address to be deleted hits the blacklist search tree, and if not, the process ends; otherwise: if the free address range of the leaf node in the hit result is in the agreed form of 0, the single IP address to be deleted is directly deleted from the blacklist search tree, otherwise, the single IP address to be deleted is deleted from the original single IP classification set, and a new blacklist search tree is constructed based on the original CIDR classification set and the new single IP classification set. After the new blacklist search tree is constructed, it is used to replace the original blacklist search tree. 7.根据权利要求1所述的一种基于前缀的IP黑名单存储方法，其特征在于，删除黑名单时，若删除的是CIDR地址，将待删除CIDR地址转换为前缀加自由地址范围的格式，在黑名单搜索树中搜索待删除CIDR地址的前缀，如果搜索结果为空，则结束；否则：从原CIDR分类集合中删除该待删除CIDR地址，基于新的CIDR分类集合和原单IP分类集合，构建新的黑名单搜索树，新的黑名单搜索树构建完成后，用其替换原黑名单搜索树。7. According to a prefix-based IP blacklist storage method described in claim 1, it is characterized in that, when deleting the blacklist, if the CIDR address is deleted, the CIDR address to be deleted is converted into a format of prefix plus free address range, and the prefix of the CIDR address to be deleted is searched in the blacklist search tree. If the search result is empty, the process ends; otherwise: the CIDR address to be deleted is deleted from the original CIDR classification set, and a new blacklist search tree is constructed based on the new CIDR classification set and the original single IP classification set. After the new blacklist search tree is constructed, it is used to replace the original blacklist search tree. 8.一种基于前缀的IP黑名单检索方法，其特征在于，包括如下步骤：8. A prefix-based IP blacklist retrieval method, characterized in that it comprises the following steps: 步骤21、将每个单IP地址表示为十六进制形式；Step 21, express each single IP address in hexadecimal form; 步骤22、在黑名单搜索树中，对十六进制形式的单IP地址M进行迭代检索，所述黑名单搜索树，使用基数树作为基础存储结构，搜索树的路径为CIDR地址的公共前缀，叶子结点中存储自由地址范围；对于单个IP地址，叶子结点的自由地址范围设置为约定的0的形式；第一次迭代记为k=1，第k轮迭代计算步骤包括：Step 22: In the blacklist search tree, iteratively search for a single IP address M in hexadecimal form. The blacklist search tree uses a radix tree as a basic storage structure. The path of the search tree is a common prefix of a CIDR address. The free address range is stored in a leaf node. For a single IP address, the free address range of the leaf node is set to the agreed form of 0. The first iteration is recorded as k=1, and the kth round of iterative calculation steps include: 步骤221、取M中[0, k×2-1]位的字符子串，判断其在黑名单搜索树中是否存在；Step 221, take the character substring of [0, k×2-1] bits in M, and determine whether it exists in the blacklist search tree; 步骤222、如果子串在黑名单搜索树中不存在，返回未命中黑名单，结束；否则进入步骤223；Step 222: If the substring does not exist in the blacklist search tree, return to the missed blacklist and end; otherwise, proceed to step 223; 步骤223、判断当前子串命中的节点是否是叶子结点，如果是非叶子结点，将k加1后，返回步骤221；否则进入步骤224；Step 223, determine whether the node hit by the current substring is a leaf node. If it is a non-leaf node, add 1 to k and return to step 221; otherwise, go to step 224; 步骤224、如果k取值为lenth(M)/2，lenth(M)为M的字符长度，判断当前叶子结点中的自由地址范围是否为约定的0的形式，是则返回命中黑名单；否则返回未命中黑名单；如果k取值未到lenth(M)/2，进入步骤225；Step 224, if the value of k is lenth(M)/2, where lenth(M) is the character length of M, determine whether the free address range in the current leaf node is in the agreed form of 0, if so, return to the hit blacklist; otherwise, return to the miss blacklist; if the value of k is less than lenth(M)/2, proceed to step 225; 步骤225、取M的第[k×2，lenth(M)]位的字符子串，并转化为十进制的表达形式，判断是否在叶子结点的自由地址范围中，如果在则返回命中黑名单，否则返回未命中黑名单。Step 225, take the character substring of the [k×2, lenth(M)]th position of M, and convert it into a decimal expression, and determine whether it is in the free address range of the leaf node. If so, return the hit blacklist, otherwise return the miss blacklist. 9.一种计算机系统，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述计算机程序被处理器执行时实现根据权利要求1-8任一项所述方法的步骤。9. A computer system comprising a memory, a processor and a computer program stored in the memory and executable on the processor, wherein the computer program implements the steps of the method according to any one of claims 1 to 8 when executed by the processor. 10.一种计算机程序产品，包括计算机程序，其特征在于，所述计算机程序被处理器执行时实现根据权利要求1-8任一项所述方法的步骤。10. A computer program product, comprising a computer program, characterized in that when the computer program is executed by a processor, the steps of the method according to any one of claims 1 to 8 are implemented.
CN202411875228.5A 2024-12-19 2024-12-19 Prefix-based IP blacklist storage and retrieval method and system Active CN119363477B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202411875228.5A CN119363477B (en) 2024-12-19 2024-12-19 Prefix-based IP blacklist storage and retrieval method and system

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202411875228.5A CN119363477B (en) 2024-12-19 2024-12-19 Prefix-based IP blacklist storage and retrieval method and system

Publications (2)

Publication Number Publication Date
CN119363477A CN119363477A (en) 2025-01-24
CN119363477B true CN119363477B (en) 2025-03-11

Family

ID=94313691

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202411875228.5A Active CN119363477B (en) 2024-12-19 2024-12-19 Prefix-based IP blacklist storage and retrieval method and system

Country Status (1)

Country Link
CN (1) CN119363477B (en)

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110071871A (en) * 2019-03-13 2019-07-30 国家计算机网络与信息安全管理中心 A kind of large model pool ip address matching process
CN115174243A (en) * 2022-07-15 2022-10-11 优刻得科技股份有限公司 Malicious IP address blocking processing method, device, equipment and storage medium

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050154762A1 (en) * 2004-01-14 2005-07-14 Bing Wang Fast rule lookup with arbitrary IP range configurations
US8161155B2 (en) * 2008-09-29 2012-04-17 At&T Intellectual Property I, L.P. Filtering unwanted data traffic via a per-customer blacklist
CN116319044A (en) * 2023-04-03 2023-06-23 京东科技信息技术有限公司 IP address interception method, device, electronic equipment and readable medium

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110071871A (en) * 2019-03-13 2019-07-30 国家计算机网络与信息安全管理中心 A kind of large model pool ip address matching process
CN115174243A (en) * 2022-07-15 2022-10-11 优刻得科技股份有限公司 Malicious IP address blocking processing method, device, equipment and storage medium

Also Published As

Publication number Publication date
CN119363477A (en) 2025-01-24

Similar Documents

Publication Publication Date Title
CN103561133B (en) A kind of IP address attribution information index method and method for quickly querying
US9521082B2 (en) Methods and devices for creating, compressing and searching binary tree
KR100962653B1 (en) Method and apparatus for searching IP address using bloom filter and multiple hashing structure
US8732110B2 (en) Method and device for classifying a packet
CN101605129A (en) A URL Search Method for URL Filtering System
CN107967219A (en) A kind of extensive character string high-speed searching method based on TCAM
CN102597973B (en) Method and apparatus for improving scalability of longest prefix matching
CN101345707A (en) A method and device for realizing IPv6 message classification
CN108628966B (en) String-based fast matching identification method and device
CN113824814B (en) Address matching method, device, network equipment and medium of forwarding table
CN110071871A (en) A kind of large model pool ip address matching process
CN108021569A (en) The structure of AC automatic machines and Chinese multi-model matching method and relevant apparatus
CN108197313A (en) The dictionary index method of space optimization is realized by 16 Trie trees
JP2014504042A (en) Packet classifier, packet classification method, and packet classification program
CN100496019C (en) A Method for Rapid Search and Update of IPv6 Routing Table
CN102045412A (en) Method and equipment for carrying out compressed storage on internet protocol version (IPv)6 address prefix
KR101587756B1 (en) Apparatus and method for searching string data using bloom filter pre-searching
CN119363477B (en) Prefix-based IP blacklist storage and retrieval method and system
CN108566335B (en) Network topology generation method based on NetFlow
CN114780536A (en) SQL Server database index creation method and device, electronic equipment and storage medium
CN104468344B (en) Wire-speed soft-tuple packet classification method
CN110995876B (en) Method and device for storing and searching IP
CN105227468A (en) One searches device, lookup method and collocation method
US20160301658A1 (en) Method, apparatus, and computer-readable medium for efficient subnet identification
CN112115312B (en) Data name searching method, system and storage medium

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant