CN111901311B - A method, system, terminal and storage medium for searching firewall policy based on spatial sorting - Google Patents

Abstract

The invention discloses a firewall policy searching method based on spatial sorting, compared with the prior art, the algorithm time complexity of the searching method is only O (N/2 + log) ₂ N), the algorithm time complexity O (N) of the existing searching method is greatly reduced, and the calculation performance is obviously improved; the invention also discloses a searching system, which is used for realizing the searching method.

Description

A method, system, terminal and storage for firewall policy search based on spatial sorting medium

technical field

The present invention relates to the technical field of firewalls, in particular to a method, system, terminal and storage medium for searching firewall policies based on space sorting.

Background technique

The existing firewall policy search method is: set the existing policy list on the firewall as P[0..N-1], and N is the number of policies; set the policy to be searched as x; assuming that the target relationship of the search is an inclusion relationship:

Step 1: Traverse the list P, take the current policy P[i], compare the source address, destination address, destination port and protocol of policy x and policy P[i], and determine the inclusion relationship between P[i] and x, if P[i] i] contains x, then save P[i] in the result list R;

Step 2: Return to list R.

The time complexity of the algorithm of this search method is O(N), which takes a long time.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to provide a firewall policy search method based on spatial sorting to significantly reduce the time complexity of the algorithm, thereby significantly improving the computing performance.

The present invention is implemented in this way. The technical solution adopted by a method for searching firewall policies based on spatial sorting provided by the present invention is: the target relationship of the search is an inclusion relationship, and the search method includes the following steps:

S1: Traverse the existing policy list on the firewall, obtain the current policy of the policy list, convert the source address, destination address and destination port of the current policy of the policy list, and the converted source address, the The destination address and the destination port form a cuboid in a three-dimensional space;

S2: Calculate the weight of the cuboid;

S3: End the traversal of the policy list, obtain a new policy list, and sort the new policy list in descending order;

S4: Calculate the weight of the strategy to be searched according to the steps S1 and S2; the strategy to be searched is a search strategy input from the outside;

S5: Perform a binary search on the new strategy list, and find a minimum value that is greater than or equal to the weight of the strategy to be searched;

S6: Read the sub-policy list from the new policy list, traverse the sub-policy list, obtain the current policy of the sub-policy list, and convert the protocol value, source address, destination address, and port range of the policy to be searched Compare with the protocol value, source address, destination address and port range of the current policy of the sub-policy list, if the protocol value, source address, destination address and port range of the to-be-searched policy are the same as the current If the comparison result of the protocol value, source address, destination address and port range of the policy is equal or inclusive, then the policy corresponding to the current policy of the sub-policy list in the policy list is saved in the result list;

S7: End the traversal, and return the result list.

将P[i]的目的地址转换为(Dst_s,Dst_t),记为

将P[i]的目的端口转换为(Port_s,Port_t)，记为

所述源地址、所述目的地址以及所述目的端口构成三维空间的长方体表示为<(Src_s,Dst_s,Port_s),(Src_t,Dst_t,Port_t)>，记为C_i。Further, the strategy list is P[0..N-1], and N is the number of strategies; the current strategy of the strategy list is P[i], and the source address of P[i] is converted into (Src _s , Src _t ), denoted as

Convert the destination address of P[i] to (Dst _s , Dst _t ), denoted as

Convert the destination port of P[i] to (Port _s , Port _t ), denoted as

The source address, the destination address and the destination port form a cuboid in a three-dimensional space, which is represented as <(Src _s , Dst _s , Port _s ), (Src _t , Dst _t , Port _t )>, denoted as C _i .

Further, the calculation method of the step S2 is:

其中有一个向量的长度为0，则W_i为另外两个向量所构成的长方形的面积，如果其中两个向量的长度都为0，则W_i为剩下的向量的长度，如果三个向量的长度都为0，则W_i记为0，否则，W_i为C_i的体积。The weight of the _cuboid is Wi, if

One of the vectors has a length of 0, then Wi is the area of the _rectangle formed by the other two vectors. If the length of two of the vectors is 0, then _Wi is the length of the remaining vectors. If the three vectors The lengths of are all 0, then _Wi is recorded as 0, otherwise, Wi is the _volume of _Ci .

Further, the new strategy list is W[0..N-1], and N is the number of strategies.

Further, the strategy to be searched is x, and the weight of the strategy to be searched is W _x .

Further, the minimum value of the weight of the strategy to be searched is W _y .

Further, the sub-policy list is W _0-y , the current strategy of the sub-policy list is W _j , and the result list is R.

The present invention also includes a search system, which is used to implement the above-mentioned method for searching firewall policies based on spatial sorting, and the search system includes a storage unit, an acquisition unit, a calculation unit, a comparison unit, and an output unit ;

The storage unit is used to store the above-mentioned policy list and new policy list;

The obtaining unit is used to obtain the strategy to be searched for the above-mentioned external input;

The computing unit is used to implement the above steps S1-S5;

The comparison unit is used to realize the above-mentioned step S6;

The output unit is used for outputting the above result list.

The present invention also includes a terminal, comprising a memory, a processor, and a computer program stored in the memory and running on the processor, characterized in that the processor implements the above when executing the computer program The steps of a method for searching firewall policies based on spatial ordering described above.

The present invention also includes a computer-readable storage medium storing a computer program, characterized in that, when the computer program is executed by the processor, the above-mentioned space-sort-based firewall policy is implemented Search method steps.

Compared with the prior art, the beneficial effect of the present invention is that the algorithm time complexity of the search method is only O(N/2+log ₂ N), so that the algorithm time complexity O(N) of the existing search method is greatly reduced. reduced, resulting in a significant increase in computing performance.

Description of drawings

In order to illustrate the technical solutions in the embodiments of the present invention more clearly, the following briefly introduces the drawings required in the embodiments. Obviously, the drawings in the following description are only some embodiments of the present invention. For those of ordinary skill in the art, other drawings can also be obtained from these drawings without any creative effort.

FIG. 1 is a schematic flowchart of a method for searching firewall policies based on spatial sorting according to an embodiment of the present invention.

FIG. 2 is a schematic diagram of the composition of a search system according to an embodiment of the present invention.

The symbols in the above drawings are: 1. Search system; 101, Storage unit; 102, Acquisition unit; 103, Calculation unit; 104, Comparison unit; 105, Output unit.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention.

In the drawings of this embodiment, the same or similar reference numerals correspond to the same or similar components; in the description of the present invention, it should be noted that when an element is referred to as being "fixed" to another element, it can be directly connected to another element. There may also be centered elements on the elements. When an element is referred to as being "connected" to another element, it can be directly connected to the other element or there may be intervening elements The orientation or positional relationship indicated by ” and the like is based on the orientation or positional relationship shown in the accompanying drawings, which is only for the convenience of describing the present invention and simplifying the description, rather than indicating or implying that the referred device or element must have a specific orientation, a specific orientation, and a specific orientation. Therefore, the terms describing the positional relationship in the accompanying drawings are only used for exemplary illustration, and should not be construed as a limitation on this patent. For those of ordinary skill in the art, they can understand the specific meanings of the above terms according to specific situations. .

The technical solutions of the present invention will be described in detail below with reference to the accompanying drawings and specific embodiments.

The present invention proposes a method for searching firewall policies based on spatial sorting. A preferred embodiment is shown in FIG. 1 . The target relationship of the search is an inclusion relationship. The search method includes the following steps:

S1: Traverse the existing policy list on the firewall, obtain the current policy of the policy list, convert the source address, destination address and destination port of the current policy in the policy list, and the converted source address, destination address and destination port form a three-dimensional space the cuboid;

S2: Calculate the weight of the cuboid;

S3: End the traversal of the strategy list, obtain a new strategy list, and sort the new strategy list in descending order;

S4: Calculate the weight of the strategy to be searched according to steps S1 and S2; the strategy to be searched is a search strategy input from the outside world;

S5: Perform a binary search on the new strategy list, and find the minimum value that is greater than or equal to the weight of the strategy to be searched;

S6: Read the sub-policy list from the new policy list, traverse the sub-policy list, obtain the current policy of the sub-policy list, and compare the protocol value, source address, destination address and port range of the policy to be searched with the protocol of the current policy of the sub-policy list Value, source address, destination address and port range are compared, if the protocol value, source address, destination address and port range of the policy to be searched are compared with the protocol value, source address, destination address and port range of the current policy in the sub-policy list If the result is an equality or inclusion relationship, save the corresponding strategy of the current strategy of the sub-policy list in the strategy list to the result list;

S7: End the traversal and return the result list;

Among them, the target relationship of the search is an inclusion relationship.

Compared with the prior art, the algorithm time complexity of the present search method is only O(N/2+log ₂ N), which makes the algorithm time of the existing search method The complexity O(N) is greatly reduced, thereby significantly improving the computing performance.

将P[i]的目的地址转换为(Dst_s,Dst_t),记为

将P[i]的目的端口转换为(Port_s,Port_t)，记为

源地址、目的地址以及目的端口构成三维空间的长方体表示为<(Src_s,Dst_s,Port_s),(Src_t,Dst_t,Port_t)>，记为C_i。As an embodiment of the present invention, the policy list is P[0..N-1], and N is the number of policies; the current policy of the policy list is P[i], and the source address of P[i] is converted to (Src _s , Src _t ), denoted as

Convert the destination address of P[i] to (Dst _s , Dst _t ), denoted as

Convert the destination port of P[i] to (Port _s , Port _t ), denoted as

The source address, destination address and destination port form a cuboid in a three-dimensional space, which is represented as <(Src _s , Dst _s , Port _s ), (Src _t , Dst _t , Port _t )>, denoted as C _i .

As an embodiment of the present invention, the calculation method of step S2 is:

其中有一个向量的长度为0，则W_i为另外两个向量所构成的长方形的面积，如果其中两个向量的长度都为0，则W_i为剩下的向量的长度，如果三个向量的长度都为0，则W_i记为0，否则，W_i为C_i的体积。The weight of the _cuboid is Wi, if

One of the vectors has a length of 0, then Wi is the area of the _rectangle formed by the other two vectors. If the length of two of the vectors is 0, then _Wi is the length of the remaining vectors. If the three vectors The lengths of are all 0, then _Wi is recorded as 0, otherwise, Wi is the _volume of _Ci .

As an embodiment of the present invention, the new strategy list is W[0..N-1], where N is the number of strategies.

As an embodiment of the present invention, the strategy to be searched is x, and the weight of the strategy to be searched is W _x .

As an embodiment of the present invention, the minimum value of the weight of the strategy to be searched is W _y .

As an embodiment of the present invention, the sub-policy list is W _0-y , the current policy of the sub-policy list is W _j , and the result list is R .

Specifically, the implementation of this search method is as follows:

Let the existing policy list on the firewall be P[0..N-1], and N is the number of policies; let the policy to be searched be x; assuming that the target relationship to be searched is an inclusive relationship, the search steps are as follows:

将P[i]的目的地址转换为(Dst_s,Dst_t),记为

将P[i]的目的端口转换为(Port_s,Port_t)，记为

构成三维空间的长方体<(Src_s,Dst_s,Port_s),(Src_s,Dst_s,Port_s)>，记为C_i；S1: Traverse the list P, take the current policy P[i], convert the source address of P[i] to (Src _s , Src _t ), denoted as

Convert the destination address of P[i] to (Dst _s , Dst _t ), denoted as

Convert the destination port of P[i] to (Port _s , Port _t ), denoted as

The cuboid <(Src _s ,Dst _s ,Port _s ),(Src _s ,Dst _s ,Port _s )> that constitutes the three-dimensional space, denoted as C _i ;

其中有一个向量的长度为0，则W_i为另外两个向量所构成的长方形的面积，如果其中两个向量的长度都为0，则W_i为剩下的向量的长度，如果三个向量的长度都为0，则W_i记为0，否则，W_i为C_i的体积；S2: Calculate the weight of C _i , denoted as Wi _, the calculation method is: if

One of the vectors has a length of 0, then Wi is the area of the _rectangle formed by the other two vectors. If the length of two of the vectors is 0, then _Wi is the length of the remaining vectors. If the three vectors The lengths of all are 0, then _Wi is recorded as 0, otherwise, Wi is the _volume of _Ci ;

S3: End the traversal of the list P, get the list W[0..N-1], and sort W in descending order;

S4: Calculate the weight W _x of the policy x according to the methods of steps S1 and S2;

S5: Perform a binary search on the list W, and find the minimum value W _y that is greater than or equal to W _x ;

S6: Take the sublist W _0-y from the W list, traverse W _0-y , take the current policy W _j , compare the protocol value, source address, destination address and port range of policy x and policy W _j , if they are equal or include Then save the strategy corresponding to W _j in the list P to the result list R;

S7: End the traversal, and return the result list R.

The present invention also provides a search system 1, which is used to implement the above search method. As shown in FIG. 2, the search system 1 includes a storage unit 101, an acquisition unit 102, a calculation unit 103, a comparison unit 104 and an output unit 105;

A storage unit 101, used for storing a policy list and a new policy list;

an obtaining unit 102, configured to obtain a strategy to be searched for external input;

a computing unit 103, configured to implement the above steps S1-S5;

a comparison unit 104, configured to implement the above step S6;

The output unit 105 is used for outputting the result list.

The present invention also provides a terminal including a memory, a processor and a computer program stored in the memory and running on the processor, characterized in that the processor implements the steps of the search method when executing the computer program.

The present invention also provides a computer-readable storage medium, where a computer program is stored in the computer-readable storage medium, wherein the computer program implements the steps of the above search method when the computer program is executed by a processor.

Preferably, all computer programs involved in the present invention are written and implemented using existing, public, and open source program codes; software programmers in the field can easily implement the technical solutions described in the embodiments of the present invention.

The above descriptions are only preferred embodiments of the present invention and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention shall be included in the protection of the present invention. within the range.

Claims (4)

1. a firewall policy search method based on space sorting, is characterized in that, the target relation of search is containment relation, and described search method may further comprise the steps: S1: Traverse the existing policy list on the firewall, obtain the current policy of the policy list, convert the source address, destination address and destination port of the current policy of the policy list, and the converted source address, the The destination address and the destination port form a cuboid in a three-dimensional space; S2: Calculate the weight of the cuboid; The policy list is P[0..N-1], and N is the number of policies; the current policy of the policy list is P[i], and the source address of P[i] is converted into (Src _s , Src _t ) , denoted as

Convert the destination address of P[i] to (Dst _s , Dst _t ), denoted as

Convert the destination port of P[i] to (Port _s , Port _t ), denoted as

The source address, the destination address and the destination port form a cuboid in a three-dimensional space, which is represented as <(Src _s , Dst _s , Port _s ), (Src _t , Dst _t , Port _t )>, denoted as C _i ; The weight of the _cuboid is Wi, if

One of the vectors has a length of 0, then Wi is the area of the _rectangle formed by the other two vectors. If the length of two of the vectors is 0, then _Wi is the length of the remaining vectors. If the three vectors The lengths of all are 0, then _Wi is recorded as 0, otherwise, Wi is the _volume of _Ci ; S3: End the traversal of the strategy list, obtain a new strategy list, and sort the new strategy list in descending order; the new strategy list is W[0..N-1], and N is the strategy number; S4: Calculate the weight of the strategy to be searched according to the steps S1 and S2; the strategy to be searched is a search strategy input from the outside world; the strategy to be searched is x, and the weight of the strategy to be searched is W _x ; S5: perform a binary search on the new strategy list, and find a minimum value that is greater than or equal to the weight of the strategy to be searched; the minimum value of the weight of the strategy to be searched is W _y ; S6: Read the sub-policy list from the new policy list, traverse the sub-policy list, obtain the current policy of the sub-policy list, and convert the protocol value, source address, destination address, and port range of the policy to be searched Compare with the protocol value, source address, destination address and port range of the current policy of the sub-policy list, if the protocol value, source address, destination address and port range of the to-be-searched policy are the same as the current If the comparison result of the policy's protocol value, source address, destination address, and port range is equal or inclusive, the policy corresponding to the current policy of the sub-policy list in the policy list is saved in the result list; the sub-policy list is stored in the result list; The strategy list is W _0-y , the current strategy of the sub-policy list is W _j , and the result list is R; S7: End the traversal, and return the result list. 2. A search system, characterized in that, the search system is used to implement a spatial sorting-based firewall policy search method as claimed in claim 1, and the search system comprises a storage unit, an acquisition unit, a calculation unit, a Comparison unit and output unit; The storage unit is used for a policy list and a new policy list; The obtaining unit is used to obtain the strategy to be searched for input from the outside world; The computing unit is used to implement the above steps S1-S5; The comparison unit is used to realize the above step S6; The output unit is used for outputting the result list. 3. A terminal comprising a memory, a processor and a computer program stored in the memory and running on the processor, wherein the processor implements the computer program as claimed in claim 1 when the processor executes the computer program The steps of a method for searching firewall policies based on space sorting. 4. A computer-readable storage medium, wherein the computer-readable storage medium stores a computer program, wherein when the computer program is executed by the processor, a space-sort-based firewall as claimed in claim 1 is implemented The steps of the policy search method.

Images