Method for high speed discrimination of policy in packet filtering type firewall system

1. A method for high speed discrimination of a policy in a packet filtering type firewall system, the method comprising the steps of:

(A) setting policy set tables for minimizing a required time to discriminate the policy among a plurality of policies for an incoming packet, wherein the step of setting policy set tables comprising the sub-steps of:

(a1) generating a plurality of first-order policy set tables containing policy information to be compared with packet information sectioned by a predetermined bits in the packet;

(a2) pairing off the plurality of first-order policy set tables arbitrarily, and generating a plurality of second-order policy set tables constituted policy members which belong to both paired first-order policy set tables; and

(a3) generating sequentially at least one post-second order policy set tables including k-th (where, 3≦k, k is a natural number) order policy set tables by pairing off (k- 1 )-th order policy set tables arbitrarily, and generating k-th order policy set tables constituted the policy members which belong to paired (k- 1 )-th order policy set tables in common; and

(B) discriminating the policy firstly conformed to each condition of the fields of the incoming packet information from the plurality of policies as a final policy corresponding to the packet, wherein the step of discriminating a policy comprising the steps of:

(b1) sectioning the packet to obtain the packet sections, and extracting the packet variables which is an object to be compared with the policy information contained in the first-order policy set tables; and

(b2) querying to the first through K-th order policy set tables sequentially by using the index values corresponding to the packet variables extracted from the packet sections obtained by sectioning the packet with the predetermined bits, and discriminating the final policy by using the queried index values.

2. The method of claim 1 , wherein the step of setting policy set tables comprising the steps of:

generating a predetermined number of tables so that the first-order policy set tables constituted with the predetermined number by the user is correspondence to the number of the sectioned packet with the predetermined bits;

pairing off the first-order policy set tables arbitrarily, and generating second-order policy set tables constituted all available intersections of the paired first-order policy set tables;

pairing off the second-order policy set tables arbitrarily, and generating third-order policy set tables constituted all available intersections of the paired second-order policy set tables; and

generating fourth-order policy set table constituted all available intersections of the third-order policy set tables, and selecting and leaving only a highest priority policy member in each intersections.

3. The method of claim 2 , wherein one first-order policy set table unpaired is used as a second-order policy set table.

4. The method of claim 1 , wherein each of the first-order policy set tables includes the index values corresponding to the variables having each information to be compared to the packet information in the incoming packet, and the policy sets corresponding to each index values.

5. The method of claim 2 , wherein each of the first-order policy set tables includes the index values corresponding to the variables having each information to be compared to the packet information in the incoming packet, and the policy sets corresponding to each index values.

6. The method of claim 2 , wherein each numbers of said first-order, second-order, third-order and k-th order policy set tables are 7, 4, 2 and 1, respectively.

7. The method of claim 2 , wherein each of said second through fourth-order policy set tables comprises all the intersections of all the paired policy sets derived between the corresponding paired policy set tables of previous-order.

8. The method of claim 1 , wherein the step of setting policy set tables, in case of replacing new policy set tables for old policy set tables, further comprises the steps of:

generating a policy map by diagramming ranges of one or more polices for a section of packet information through their respective conditional extents from start points to end points on a reference line having points from 0 to 65535; and

generating a new first-order policy set tables by referring to all possible point numbers from 0 to 65535 on the reference line together with the policy members spanning their own ranges on the reference line in the policy map.

9. The method of claim 8 , wherein said step of generating a new first-order policy set tables comprises the steps of:

detecting whether any policy members in the policy map are duplicated one another; and

labeling each of the policy members with a unique policy label.

10. The method of claim 1 , wherein the step of setting policy set tables, in case of replacing new policy set tables for old policy set tables, further comprises the steps of:

generating new policy set tables in another memory separated from the existing memory containing said old policy set tables; and

replacing said new policy set tables for said old policy set tables in the existing memory instantaneously upon completing the generation of said new policy set tables.

11. The method of claim 1 , wherein the step of discriminating a policy comprising the steps of:

sectioning the received packet by the predetermined bit to obtain the packet sections, and extracting the packet information corresponding to the information including the policy, and querying the variable values corresponding to each packet information and the index values corresponding to the variables;

pairing off the each index values queried in the first-order policy set tables, calculating variables from the paired index values for querying the second-order policy set tables, and querying the index values corresponding to each variable in the second-order policy set tables;

pairing off the index values queried in the second-order policy set tables, calculating variables from the paired indexes for querying the third-order policy set tables, and querying the index values corresponding to each variable in the third-order policy set tables; and

pairing off the index values queried in the third-order policy set tables, and calculating a variable from the paired index values for querying the fourth-order policy set table, and discriminating a final policy by querying the fourth-order policy set table with the variable.

12. The method of claim 11 , wherein said packet information comprises two 16-bit source IP addresses extracted from the upper half portion and lower half portion of an original 32-bit source IP address, two 16-bit destination IP addresses extracted from the upper half portion and lower half portion of a original 32-bit destination IP address, a 16-bit source port, a 16-bit destination port, and another 16-bit information consisted of a 3-bit interface, a 8-bit protocol and a 5-bit TCP flag.

13. The method of claim 11 , wherein said steps of calculating variables use the following equation

( a )= nx 1 +y 1

where, a is the variable,

n is the total number of indexes of a second table of the paired policy set tables,

x 1 is an index value of a first table of the paired policy set tables, and

y 1 is an index value of the second table of the paired policy set tables.