Firewall Packet Filtering

A computer program product comprising a non-transitory computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a firewall device, causes the firewall device to:

• receive a data packet;
• perform a hash operation on a header field value of a header of the data packet to generate a hash value;
• perform a lookup operation in a hash table associated with a type of the header field value based on the hash value to identify a hash table entry;
• retrieve a bit string associated with the hash table entry, wherein each bit in the bit string corresponds to a class of rules of a rule set of a firewall;
• perform a matching operation of the header field value to rules in one or more classes of rules corresponding to bits set in the bit string;
• and
• perform an operation based on zero or more rules in the one or more classes of rules being matched by the header field value of the data packet.

A firewall device, comprising:

• a processor, and
• a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to:
• receive a data packet;
• perform a hash operation on a header field value of a header of the data packet to generate a hash value;
• perform a lookup operation in a hash table associated with a type of the header field value based on the hash value to identify a hash table entry;
• retrieve a bit string associated with the hash table entry, wherein each bit in the bit string corresponds to a class of rules of a rule set of a firewall;
• perform a matching operation of the header field value to rules in one or more classes of rules corresponding to bits set in the bit string;
• and
• perform an operation based on zero or more rules in the one or more classes of rules being matched by the header field value of the data packet.

A method, in a firewall device for processing a data packet, comprising:

• creating at least two hash table data structures in a memory of the firewall device, wherein each hash table data structure is indexed by a different data packet header field type and each cell in each hash table comprises a list of search trees whose rules reference the data packet header field type that is an index for the hash table data structure;
• performing, by the firewall device, a hash operation on at least two different data packet header fields of a data packet to generate a plurality of hash values;
• performing, by the firewall device, a lookup operation in the at least two hash table data structures based on the plurality of hash values to identify a list of search trees corresponding to matching entries in the at least two hash table data structures;
• and
• processing, by the firewall device, the data packet based on rules associated with the search trees in the list of search trees to perform an operation on the data packet corresponding to one or more matching rules.