Abstract:
A method of speeding up packet filtering that utilizes a search filter in compliance with the rules of the firewall, includes the following steps of presenting a mask characteristic value set in a first hash space with regard to all specific masks in need of being filtered in the firewall rules; presenting a packet characteristic value set in a second hash space with regard to each packet received by the firewall; performing a specific Boolean operation in use of the first and second hash spaces with the same size; and as long as the result of the specific Boolean operation determine that the packet characteristic value set is out of the mask characteristic value set, rapidly allowing the packet to pass through the firewall so as to reduce calculation time of all of the firewall rules, decrease system loading and prevent network congestion.

Description:
BACKGROUND OF INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The present invention relates to a method of speeding up packet filtering, and more particularly, to a method of speeding up packet filtering with a search filter used in a network security apparatus.  
         [0003]     2. Description of the Prior Art  
         [0004]     The last development of networking technology facilitates rapid transmission of large amounts of data among different places in the world. How to improve network security becomes an important issue. In an ordinary computer networking system, several networking apparatuses connected to a backbone network, such as a virtual private network (VPN), a gateway, and a router mostly have firewalls disposed therein or the outside thereof. Such firewall that provides a mechanism of packet filtering implements protection in the IP Layers. The packet filtering principle of the mechanism is to check each out-coming packet passing through the firewall with using a firewall rule predefined by users. However, each firewall rule indicates a cost in searching, which includes time consumption, Isystem loading, and labor power. Excess firewall rules or excess details defined within the rules can result in higher accuracy in searching but higher searching costs. If it spends too much time to process packets, the performance of the whole networking will decrease or the network congestion will occur. This situation is not desirable. On the other hand, only considering the searching cost but neglecting the protection score of a firewall would result in the degradation of the performance of the firewall. Therefore, one thing to consider when designing a firewall is to filter packets accurately with the lowest possible cost.  
         [0005]     A conventional method of packet filtering is to determine if each out-coming packet is in a score defined by the firewall rules. A commonly used one of the methods, called “linear search”, is to respectively check the received packets with each firewall rule. In addition, some improved methods apply known searching algorithms on filtering packets that are harmful or suspected. However, most packets that the firewall receives are not included in the score defined by the firewall and thus are unharmful. In other words, most packets can pass the filtering of a firewall. It means that most searching algorithms spend too much searching cost, i.e. time, in filtering packets that need not be filtered.  
         [0006]     To overcome the disadvantages of the prior art, the present invention utilizes a search method of low cost before searching packets to find most well-behaved packets and let them pass the firewall, and leave a small amount of packets having problems checked by the conventional ways so as to lower searching cost without modifying any firewall rule.  
         [0007]     The present invention utilizes a search filter to solve the problems described above. “Search filter” is the method of searching words or documents proposed by Severance and Lohman in 1976. The principle of the method is that: selecting a Hash function, such as MD5 first; taking a value to be searched, such as “m”, as the “key” of the Hash function, such as f(m) to perform Hush operation and obtain a proper data structure arrangement; and using the data structure to select the values to be checked. When a key is selected, it is not sure that the key can be fined in a search set according to the property of search filter, because the Hash space that the search filter uses is limited. On the other hand, when a key selected does not belong to a search set, the search filter determines that the key does not belong to the search set.  
       SUMMARY OF INVENTION  
       [0008]     According to the claim  1 , the present invention discloses a method of speeding up packet filtering used in a network security apparatus comprising: generating a first hash space according to at least one rule used to filter the packets received by the network security apparatus, and the first hash space presenting a mask characteristic value set; generating a second hash space according to at least one of the packets received by the network security apparatus, and the second hash space with the same size as the first hash space, presenting a packet characteristic value set; performing a specific Boolean operation with the first hash space and the second hash space; and determining whether the packet characteristic value set is out of the mask characteristic value set, according to the results of said Boolean operation, then it is decided whether the packet is allowed to pass through the network security apparatus.  
         [0009]     These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings. 
     
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0010]      FIG. 1  illustrates a network and firewall according to a preferred embodiment of the present invention.  
         [0011]      FIG. 2  illustrates a flowchart of speeding up packet filtering in the present invention.  
         [0012]      FIG. 3  illustrates a flowchart of generating a packet characteristic value set.  
         [0013]      FIG. 4  illustrates a flowchart of a checking operation. 
     
    
     DETAILED DESCRIPTION  
       [0014]     Please refer to  FIG. 1 .  FIG. 1  illustrates a network and firewall according to a preferred embodiment of the present invention. The invention is applied to a network security device, such as the firewall  20 , and performs packet filtering with a plurality of pre-installed firewall rules  22  in the firewall  20 . The firewall  20  can be connected between the Internet  10  (or other wide-area network) and a local area network (LAN)  30  as shown in  FIG. 1  to filter all packets from the Internet  10 . The packets which are determined to be acceptable after filtering can enter the LAN  30 .  
         [0015]     According to the principles of a search filter described before, method of speeding up packet filtering in the present invention includes:  
         [0016]     1. A method of generating a mask characteristic value set:  
         [0017]     (1) Predetermined Conditions:  
         [0018]     (a) Suppose the firewall  20  in the  FIG. 1  has N firewall rules {1≦i≦N|r i }, wherein each rule consists of five itmes: {source network r i net s , destination network r i net d , source port r i port s , destination port r i port d , protocol r i p}. Each network in the above rules includes the IP addresses that users want to remove.  
         [0019]     (b) Predetermine K independent hash functions hi {1≦i≦K}, (for example, two independent hash functions h1 and h2 do not make ensure that if m≠m′, h1(m)‡h2(m′)) for generating a hash function space H.  
         [0020]     (c) Notice that the method of the present invention is limited to the size of the predetermined hash space and the characteristics of the selected hash function. In addition, functions of the search filter mentioned above can be achieved by hardware or software.  
         [0021]     (2) Method Flow:  
         [0022]     As the procedure S 400  illustrates in  FIG. 2 , first define the volume of each hash space as the volume of output address space of each hash function h i =C*K*L, wherein C is a self-defined constant, and L is the number of bits in the IP addresses (take IPV4 for example, L=32).  
         [0023]     As the procedure S 405  shows, the method extracts a source network r i net s  from each firewall rule. In the procedure S 410 , the method converts the source network r i net s  into the binary code (including bit values and addresses). In the procedure S 415 , the method searches for a set of M relative addresses b m  (0≦b m ≦L−1, 0≦m≦M−1) which have bit values “1” from the codes of the source network r i net s . In the procedure S 420 , the method sets each address having a bit value “1”, source port r i port s  and protocol r i p, to be the keys of the hash function and substitutes the keys into K specific hash functions h i  (such as h i  (b m , r i port s , r i p)) for hash calculation in order to get K*M values k j  between 0 to (C*K*L)−1. These k j  are the relative addresses pointing to a hash space H s  in the source network. As the described in the procedure S 425 , the set of the relative addresses pointing to a hash space H s  can express the characteristic values of the source network r i net s  in the hash space H s . However, the keys of the hash function mentioned before are chosen by the user, but they should be at least one of the address having a bit value “1”, source port r i port s  and protocol r i p. For example, the key of the hash function is the address having a bit value “1” in the network.  
         [0024]     Like the filtering procedure of the source network r i net s  described before, the filtering procedures of the destination network r i net d  for the same firewall rule r i  are to repeat the procedures S 400  to S 250 : by first converting the destination network r i net d  into the binary code (including bit values and address), then setting W addresses b w  (0≦b w ≦L−1, 0≦w≦w−1) having bit value “1”, destination port r i port d  and protocol r i p as the keys of the hash function, and substituting the keys into K specific hash functions h i  (such as h i  (b w , r i port d , r i p)) for hash calculation in order to get K*M values k between 0 to (C*K*L)−1. These k j  include the relative addresses pointing to a hash space H d  in the destination network r i net d . The set of the relative addresses pointing to a hash space H d  can express the characteristic value of the source network r i net s  in the hash space H d . Notice that each hash space uses the same C, K and L, so the size of the hash space H d  mentioned above equals the size of the hash space H s , and also equals sizes of other hash spaces.  
         [0025]     In the procedure S 435  and the procedure S 440 , the method repeats the same calculations for networks of N firewall rules (include source network and destination network) and obtain a plurality of hash spaces H d  and H s . In d the procedure S 430 , the method collects the sets of the relative addresses of all masks pointing to the hash space H in the N firewall rules. For example, the method totals each bit value of the same addresses of all hash spaces H d  and H s  in N firewall rules so that the characteristic value sum of the masks in N firewall rules is presented in the same hash space H (H=H d +H s ).  
         [0026]     In the procedure S 445 , the method sets the bit values which are out of the value “0” in the hash space H of the characteristic value sum to be “1”. Otherwise, the method keeps the bit values “0” as “0”. Finally in the procedure S 450 , the method obtains a mask characteristic value set of N firewall rules in the same hash space H.  
         [0027]     2. A method of generating a packet characteristic value set:  
         [0028]     (1) Predetermined Conditions:  
         [0029]     Suppose that each packet p to be checked includes: {source IP pip s , destination IP Pip d , source port pport s , destination port pport d , protocol pp}, and the method of processing packets is similar to the method of processing networks mentioned before. The present invention defines the volume of another hash space H′=the volume of previous hash space H=the volume C*K*L, and resets each bit to “0”, and uses the same K hash functions h i  {1≦i≦K}.  
         [0030]     (2) Method Flow:  
         [0031]     Firstly in the procedure S 550 , the method receives a packet p to be checked. In the procedure S 505 , the method extracts a source IP pip s  from the packet. In the procedure S 510 , the method converts the source IP pip s  of the packet into binary code. In the procedure S 505 , the method searches for a set of M′ relative addresses b m  (0≦b m ′≦L−1,01≦m≦M−1) which have bit values “1” from the code of the source IP pip s . In the procedure S 520 , the method sets each address having a bit value “1”, source port pport s  and protocol pp, as the keys of the hash function, and substitutes the keys into K hash functions h i  (such as h i  (b″ m , pport s , pp)) for hash calculation in order to obtain K*M values k between 0 to (C*K*L)−1. These k j  include the relative addresses pointing to a hash space H&#39;s in the source IP pip s . As the described in the procedure S 525 , the setting of the relative addresses pointing to a hash space H&#39;s can present the characteristics of the source IP pip s  in the hash space H′ s .  
         [0032]     According to the same principles, if setting the destination IP pip d , the destination port pport d , and the protocol pp as the keys of the hash function to perform calculations of K hash functions, one converts destination IP pip d  of the packet into a set of relative addresses pointing to a hash space H′ s . Thus, the mask characteristic values of the destination IP pip d  of the packet are presented in the hash space H′ d .  
         [0033]     In the procedure S 535 , the method repeats the same calculations for other IP addresses in one packet. In the procedure S 530 , the method collects the sets of the relative addresses of all IP addresses pointing to the hash space H′ s  of the packet. For example, the method totals the bit values belonging to the same address of all hash spaces H′ d  and H′ s  and shows the packet characteristic value sum in a hash space H′ (H′=H′ d +H′ s ). In the procedure S 540 , the method sets the bit values which are out of the value “0” in the hash space H′ to be “1”, 0≦j≦(K*M′)−1. Finally, in the procedure S 545 , the method obtains a packet characteristic value set in the hash space H′.  
         [0034]     Then, in the procedure S 550 , the method performs a Boolean operation checking. For the same hash space, the method checks the packet characteristic value set by the mask characteristic value set described above to determine if the packet characteristic value set is covered in the mask characteristic value set.  
         [0035]     3. Method of Operation Checking:  
         [0036]     First in the procedures S 600  and S 605 , the method obtains a hash space H having a mask characteristic value set and a hash space H having a packet characteristic value set. In the procedure S 610  and S 615 , the method performs the following Boolean operation:  
         [0037]     (H OR H′) XOR H  
         [0038]     In the procedure S 620 , the method determines the result of the above Boolean operation. If all the bits are “0”, the method performs the procedure S 640 ; the IP address of the packet p could be included in the mask characteristic value set of the N firewall rules. Then, as shown in the procedure S 645 , the method confirms the firewall rule or filters the packet in coordination with a further searching mechanism (with higher cost). Otherwise, if the results of the procedure S 620  have at least one bit that is out of the value “0”, it means, as shown in the procedure S 625 , the IP address of the packet p must not be included in the mask characteristic value set of the N firewall rules. Then, the method performs the procedure S 630 , allowing the packet to pass the firewall.  
         [0039]     Notice that if there is any other additional/reduced firewall rule, the mask characteristic value H c  in the hash space of the rule should be found, and then the hash function having the mask characteristic value sum is H=H−H c  or H=H+H c , the method calculating the new mask characteristic value set. If the firewall rules need modifying, repeat the method described above and remove the old rules and add the new rules to obtain a new mask characteristic value set.  
       4. EXAMPLES  
       [0040]     Suppose that a firewall has two firewall rules (N=2), as follows:  
                                                           Source   Source   Destination   Destination               Sequence   Network   Port   Network   Port   Protocol   Action                   1   12.0.0.0/24   0   202.1.237.21/32   80   1   Accept       2   12.0.0.0/24   0   172.17.23.152/29   23   1   Accept                  
 
 (wherein “0” in the communication port represents any port) 
 
         [0041]     Additionally, suppose another constant C=2, the size of each IP address L=32, and two independent hash functions are {1≦i≦2|h i } (K=2), so the size of each hash function H=the size of each output addressing space=C*K*L=2*2*32=128 bits. The method resets each bit to “0” and the hash function H becomes  
                                                                                        
 
         [0042]     The method extracts a source network r 1 net s  (12.0.0.0/24) from the first firewall rule and converts the source network into binary code, as follows:  
                                                                                        
 
         [0043]     The method searches for a set of M relative addresses having bit value “1” from the binary code of the above. Therefore, we know: M=10, and the set of the relative addresses={b0, b1, b2, b3, b4, b5, b6, b7, b8, b9}={0,1,2,3,4,5,6,7,26,27} 
         [0044]     The method sets the relative addresses mentioned above in which the binary bit values are “1”, source port r 1 port s (0) and protocol r 1 p(1), as the keys of the hash function, and substitutes the keys into two hash functions h i  to obtain the following 20 M×K address sets pointing to a hash function H 1s : 
    h1(0,0,1)=41, h1(1,1,1)=111, h1(2,0,1)=41, h1(3,0,1)=39,     h1(4,0,1)=100, h1(5,0,1)=42, h1(6,0,1)=1, h1(7,0,1)=21,     h1(26,0,1)=92, h1(27,0,1)=4     h2(0,0,1)=21, h2(1,0,1)=41, h2(2,0,1)=40, h2(3,0,1)=1,     h2(4,0,1)=98, h2(5,0,1)=120, h2(6,0,1)=12, h2(7,0,1)=88,     h2(26,0,1)=76, h2(27,0,1)=110    
 
         [0051]     According to the address sets pointing to a hash function H 1s , the following shows the source mask characteristic value which presents the first firewall rule in the hash space H 1s :  
                                                                                        
 
         [0052]     The method extracts a destination network r 1 net d  (202.1.237.21/32) from the first firewall rule, and converts the destination network r 1 net d  to binary code:  
                                                                                        
 
         [0053]     The method searches for sets of W relative addresses having bit value “1” from the binary code of the destination network r 1 net d  described above. Therefore, W=14, the sets of W relative addresses={b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13}={0,2,4,8,10,11,13,14,15,16,25,27,30,31} 
         [0054]     The method sets the relative addresses in which each bit value of the binary codes is “1” described above {0,2,4,8,10,11,13,14,15,16,25,27,30,31}, destination port r 1 port d (80) and protocol r 1 p(1), as the keys of the hash function, and substitutes the keys into two hash functions h i  to obtain the following 28 (K×W) subsets of addresses that point to a hash space H 1d : 
    h1(0,80,1)=50, h1(2,80,1)=76, h1(4,80,1)=43,     h1(8,80,1)=66,     h1(10,80,1)=9, h1(11,80,1)=12, h1(13,80,1)=21, h1(14,80,1)=36,     h1(15,80,1)=61, h1(16,80,1)=58, h1(25,80,1)=81, h1(27,80,1)=108,     h1(30,80,1)=52, h1(31,80,1)=12     h2(0,80,1)=20, h2(2,80,1)=67, h2(4,80,1)=7, h2(8,80,1)=96,     h2(10,80,1)=12, h2(11,80,1)=84, h2(13,80,1)=61, h2(14,80,1)=29,     h2(15,80,1)=17, h2(16,80,1)=77, h2(25,80,1)=20, h2(27,80,1)=99,     h2(30,80,1)=121, h2(31,80,1)=41    
 
         [0064]     According to 28 sets of addresses that point to a hash space H 1d , the destination mask characteristic value of the first firewall rule is presented in the hash space H 1d , and the method collects all sets of addresses in which all networks pointing to a hash space H of the first firewall rule. In other words, the method totals the bits belonging to the same address in two hash spaces H 1d  and H 1s  in order to present the mask characteristic value sum of the first firewall rule in the hash space H (H=H 1s +H 1d ):  
                                                                                        
 
         [0065]     The method extracts a source network r 2 net s  (12.0.0.0/24) from the second firewall rule. However, the source network r 2 net s  is the same as source network r 1 net s , so the operation procedure of the hash function is omitted. The hash function H 2S  is added directly in the above hash space H to total the bits. Thus, the hash function H=H+H 2S  presents the mask characteristic value sum, as follows:  
                                                                                        
 
         [0066]     Next the method extracts a destination network r 2 net d  (172.17.23.152/29) from the second firewall rule and converts the destination network r  2 net d  into the binary code, as follows:  
                                                                                        
 
         [0067]     The method searches for sets of W relative addresses having bit value “1” from the binary code of the destination network r 2 net d  described above. Therefore, W=16, the sets of W relative addresses={b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b14, b14, b15}={0, 1,2,3,4,7,8,9,10,12,16,20,26,27,29,31} 
         [0068]     The method sets the relative addresses in which each bit value of the binary code is “1” described above {0,2,4,8,10,11,13,14,15,16,25,27,30,31}, destination port r 2 port d (80) and protocol r 2 p(1), as the keys of the hash function, and substitutes the keys into two hash functions h i  to obtain the following 32 (K×W) sets of addresses that points to a hash space H 2d : 
    h1(0,23,1)=3, h1(1,23,1)=69, h1(2,23,1)=30, h1(3,23,1)=0,     h1(4,23,1)=56, h1(7,23,1)=59, h1(8,23,1)=83, h1(9,23,1)=46,     h1(10,23,1)=31, h1(12,23,1)=47, h1(16,23,1)=61, h1(20,23,1)=79,     h1(26,23,1)=13, h1(27,23,1)=17, h1(29,23,1)=28, h1(31,23,1)=82     h2(0,23,1)=13, h2(1,23,1)=9, h2(2,23,1)=82, h2(3,23,1)=10,     h2(4,23,1)=109, h2(7,23,1)=34, h2(8,23,1)=79, h2(9,23,1)=22,     h2(10,23,1)=59, h2(12,23,1)=111, h2(16,23,1)=12, h2(20,23,1)=7,     h2(26,23,1)=109, h2(27,23,1)=107, h2(29,23,1)=3, h2(31,23,1)=55    
 
         [0077]     According to the 32 sets of addresses that point to a hash space H 2d , the method presents the destination mask characteristic value of the second firewall rule in the hash space H 2d , and adds the hash space H 2d  into the previous hash space H. Thus, the method totals the bit values belonging to the same address and presents the mask characteristic value sum of the whole firewall rules in the hash space H (H=H+H 2d ).  
                                                                                        
 
         [0078]     The method set the bit values which are out of the value “0” in the above mask characteristic value sum to “1” so as to present mask characteristic value sets of all firewall rules in the hash space H.  
                                                                                        
 
         [0079]     As long as the firewall receives a packet p that tries to pass the firewall (pip s , pport s , pip d , pport d , pp)=(12.0.0.4, 1067, 172.17.23.153, 80, 1), the method of processing the packet is similar to the method of processing the firewall rules, which utilizes two equivalent (K=2) hash functions h i  {1≦i≦2} to define a hash space H′=C*K*L=128 bit of the same size, and each bit value is reset to “0” as follows:  
         [0080]     Hash Space H′ 
                                                                                        
 
         [0081]     The method extracts a source IP pip s  (12.0.0.4) from the packet and convert the source IP into the binary code, as follows:  
                                                                                        
 
         [0082]     The method searches for sets of M′ relative addresses having bit values of “1” from the binary code of the source IP pip s  described above. Therefore, M′=3, the sets of M′ relative addresses {b0, b1, b2}={2,26,27}.  
         [0083]     Subsequently, the method sets the relative addresses in which each bit value of the binary code is “1” described above {2,26,27}, source port pport s  (1067) and protocol pp (1), as the keys of the hash function, and substitutes the keys into two hash functions h i  to obtain the following 6 (K×M) sets of addresses that points to a hash space H′: 
    h1(2,1067,1)=61, h1(26,1067,1)=10, h1(27,1067,1)=111     h2(2,1067,1)=39, h2(26,1067,1)=46, h2(27,1067,1)=12    
 
         [0086]     According to 6 sets of addresses that point to a hash space H′, the following presents the source packet characteristic value:  
                                                                                        
 
         [0087]     The method extracts a destination IP pip d  (172.17.23.153) from the same packet and converts the destination IP pip d  into binary code, as follows:  
                                                                                        
 
         [0088]     The method searches for sets of M′ relative addresses having bit values of “1” from the binary code of the destination IP pip d  described above. Therefore, W=14, the sets of the relative addresses={b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13}={0,3,4,7,8,9,10,12,16,20,26,27,29,31}.  
         [0089]     The method sets the relative addresses in which each bit value of the binary codes is “1” described above {0,3,4,7,8,9,10,12,16,20,26,27,29,31}, destination port pport d  (80) and protocol pp (1), as the keys of the hash function, and substitutes the keys into two hash functions h i  to obtain the following 28 (K×W′) sets of addresses that point to a hash space H′ d : 
    h1(0,80,1)=60, h1(3,80,1)=1, h1(4,80,1)=107, h1(7,80,1)=8, h1(8,80,1)=39,     h1(9,80,1)=61, h1(10,80,1)=40, h1(12,80,1)=55, h1(16,80,1)=83,     h1(20,80,1)=97, h1(26,80,1)=24, h1(27,80,1)=66, h1(29,80,1)=70,     h1(31,80,1)=24     h2(0,80,1)=25, h2(3,80,1)=33, h2(4,80,1)=1, h2(7,80,1)=66, h2(8,80,1)=51,     h2(9,80,1)=43, h2(10,80,1)=37, h2(12,80,1)=13, h2(16,80,1)=90,     h2(20,80,1)=69, h2(26,80,1)=22, h2(27,80,1)=91, h2(29,80,1)=111,     h2(31,80,1)=121    
 
         [0098]     According to the 28 sets of addresses that point to the hash space H′ d , the method presents the destination packet characteristic value in the hash space H′ d . Then, the method collects all sets of the addresses that point to the hash space H′ and adds the hash space H′ d  into the previous hash space H′ s . For example, the method totals the bit values belonging to the same address to generate a hash space H′=H′ s +H′ d . The following presents the packet characteristic value sum.  
                                                                                        
 
         [0099]     The method sets the bit values which are out of the value “0” in the above mask characteristic value sum to “1” so as to present the packet characteristic value sets in the hash space H′.  
                                                                                        
 
         [0100]     The method performs operation checking: (H OR H) XOR H. Then, we find that at least one bit value is out of the value “0”, so the packet characteristic value set is not included in the mask characteristic value set. That means the packet p does not satisfy any firewall rule previously described, and so is allowed to pass the firewall.  
         [0101]     The method of speeding up packet filtering in the present invention utilizes a search filter to determine if one packet is covered by the range of the firewall rules in a fixed period of time and lets a large amount of packets be out of the range, considered as acceptable packets, rapidly pass the firewall so as to prevent excessive traffic in the network. On the other hand, a small amount of packets inside the range possibly having problems can be further filtered with other packet filters of higher searching cost. Therefore, the present invention can reduce the searching time and improve searching efficiency, which cannot be achieved by the prior art.  
         [0102]     Those skilled in the art will readily observe that numerous modifications and alterations of the device may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.