Data packet filtering

• US 20030120622A1
• Filed: 09/21/2001
• Published: 06/26/2003
• Est. Priority Date: 09/21/2001
• Status: Active Grant

• Current Assignee: Forcepoint LLC
• Original Assignee: Stonesoft Corporation
• Inventors: Rautila, Mika, Nurmela, Kari
• Granted Patent: US 7,386,525 B2
• Time in Patent Office: Days
• US Class Current: 706/47
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/0263 Rule management

Abstract

The invention relates to data packet filtering and finding a rule matching a data packet in a rule base. A data packet comprises parameter fields for identifying the data packet, the rule base comprises a plurality of rules, each rule comprises one or more parameter fields, and the matching rule is a rule, whose parameter field values correspond to the parameter field values of said data packet. The matching rule is found by determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match, and by finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet. Additionally, the invention relates to finding an element with the smallest label that is present in a plurality of finite subsets containing finite number of elements, said subsets being subsets of a set containing finite number of sequentially labelled elements.

Claims

1. A method for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and the method comprising the steps of:

determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match, and

finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet.

2. A method according to claim 1, wherein, in a rule set, the rules following said rule matching the data packet form a remainder of said rule set, and said method further comprises the step of

finding the rule with the smallest label that is present in said remainders of all rule sets of the data packet, said further smallest element indicating a further rule matching the data packet.

3. A method for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and the method comprising the steps of:

computing, for each parameter field in the rule base, a data structure indicating different values or value ranges of the parameter field and, for each different value or value range, a rule set of the rules, to which said value or value range can match,

storing said data structures,

finding, in said data structures, rule sets for the data packet, said rule sets being the rule sets corresponding to the parameter field values of the data packet, and

finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet.

4. A method according to claim 3, wherein the step of computing comprises

computing, for a parameter field, a rule set for each value or value range defined in the rules of the rule base, and

computing a further rule set for the values of said parameter field, which are not included in the values or value ranges defined in the rules of the rule base.

5. A method according to claim 3, wherein, if two or more values or value ranges of the parameter fields in a rule base result in the same rule set, the rule set is stored in a data structure in connection with a first occurrence of said rule set, and in connection with a second occurrence of the rule set, a reference to said stored rule set is stored.

6. A method according to claim 3, wherein the rules following said rule matching the data packet in a rule set form a remainder of said rule set, and said method further comprises the step of

finding the rule with the smallest label that is present in said remainders of all rule sets of the data packet, said further smallest element indicating a further rule matching the data packet.

7. A method for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and the method comprising the steps of:

determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,

computing a table for the combination of the rule sets of the data packet, the rows of the table corresponding to the labels of the rules in the rule base, and the columns of the table corresponding to the different rule sets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of a rule of the respective rule set and equal to or larger than the label of the respective row,

observing a first element in a first row of a first column and comparing the first element to the respective row label,

if the element is equal to the row label, jumping to another column in the same row and observing a second element found therein, or otherwise jumping to the row indicated by the first element and observing a second element found in a column therein, and

proceeding on the basis of the second element and the respective row label in the same way as with the first element, and

repeating the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row or said equal element indicating the rule matching the data packet.

8. A method for finding an element with the smallest label that is present in a plurality of finite subsets containing finite number of elements, said subsets being subsets of a set containing finite number of sequentially labelled elements, said method comprising the steps of:

computing a table for the plurality of finite subsets, the rows of the table corresponding to the labels of the elements of the set, and the columns of the table corresponding to the different subsets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of an element of the respective subset and equal to or larger than the label of the respective row,

observing a first element in a first row of a first column and comparing the first element to the respective row label,

if the element is equal to the row label, jumping to another column in the same row and observing a second element found therein, or otherwise jumping to the row indicated by the first element and observing a second element found in a column therein, and

proceeding on the basis of the second element and the respective row label in the same way as with the first element, and

repeating the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row indicating the element with the smallest label that is present in the plurality of subsets.

9. A method for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and the method comprising the steps of:

determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,

computing low level bit sequences for the data packet, each low level bit sequence corresponding to one rule set in the combination of the rule sets of the data packet, each bit of a low level bit sequence corresponding to one rule in the rule base, and a bit in a low level bit sequence being set to 0, if the corresponding rule is not present in the corresponding rule set, and a bit in a low level bit sequence being set to 1, if the corresponding rule is present in the corresponding rule set,

computing bitwise AND for said low level bit sequences of the data packet for obtaining low level result sequence, and

finding, in said low level result sequence, the first 1 starting from the beginning of the low level result sequence, the position of said first 1 in the low level result sequence indicating the rule matching the data packet.

10. A method according to claim 9 further comprising the steps of

computing high level bit sequences for each low level bit sequence of the data packet, each bit of a high level bit sequence corresponding to N consecutive bits of a low level bit sequence, a bit in a high level bit sequence being set to 0, if the corresponding N bits in the low level bit sequence are 0, and a bit in a high level bit sequence being set to 1, if at least one of the corresponding N bits in the low level bit sequence is 1,

computing bitwise AND for said high level bit sequences for obtaining a high level result sequence,

finding, in the high level result sequence, the first 1 starting from the beginning of the high level result sequence, and

computing said low level result sequence using N bits of the low level bit sequences, said N bits being indicated by said first 1 in the high level result sequence.

11. A network element comprising functionality for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the network element comprising memory for the rule base, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and said network element comprising:

a first mechanism for determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match, and

a second mechanism for finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet.

12. A network element comprising functionality for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the network element comprising memory for the rule base, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and said network element comprising:

a third mechanism for computing, for each parameter field in the rule base, a data structure indicating different values or value ranges of the parameter field and, for each different value or value range, a rule set of the rules, to which said value or value range can match,

memory for storing said data structures,

a first mechanism for finding in said data structures rule sets for the data packet, said rule sets being the rule sets corresponding to the parameter field values of the data packet, and

a second mechanism for finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet.

13. A network element comprising functionality for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the network element comprising memory for the rule base, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and said network element comprising:

a first mechanism for determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,

a fourth mechanism for computing a table for the combination of the rule sets of the data packet, the rows of the table corresponding to the labels of the rules in the rule base, and the columns of the table corresponding to the different rule sets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of a rule of the respective rule set and equal to or larger than the label of the respective row, and

a second mechanism for observing a first element in a first row of a first column and comparing the first element to the respective row label, which second mechanism is adapted

if the element is equal to the row label, to jump to another column in the same row and to observe a second element found therein, or otherwise to jump to the row indicated by the first element and to observe a second element found in a column therein, and

to proceed on the basis of the second element and the respective row label in the same way as with the first element, and wherein

the second mechanism is further adapted to repeat the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row or said equal element indicating the rule matching the data packet.

14. A network element comprising functionality for finding an element with the smallest label that is present in a plurality of finite subsets containing finite number of elements, said subsets being subsets of a set containing finite number of sequentially labelled elements, said network element comprising:

a fourth mechanism for computing a table for the plurality of finite subsets, the rows of the table corresponding to the labels of the elements of the set, and the columns of the table corresponding to the different subsets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of an element of the respective subset and equal to or larger than the label of the respective row, and

a second mechanism for observing a first element in a first row of a first column and comparing the first element to the respective row label, which second mechanism is adapted

if the element is equal to the row label, to jump to another column in the same row and to observe a second element found therein, or otherwise to jump to the row indicated by the first element and to observe a second element found in a column therein, and

to proceed on the basis of the second element and the respective row label in the same way as with the first element, and wherein

the second mechanism is further adapted to repeat the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row indicating the element with the smallest label that is present in the plurality of subsets.

15. A network element comprising functionality for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the network element comprising memory for the rule base, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and said network element comprising:

a first mechanism for determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,

a fourth mechanism for computing low level bit sequences for the data packet, each low level bit sequence corresponding to one rule set in the combination of the rule sets of the data packet, each bit of a low level bit sequence corresponding to one rule in the rule base, and a bit in a low level bit sequence being set to 0, if the corresponding rule is not present in the corresponding rule set, and a bit in a low level bit sequence being set to 1, if the corresponding rule is present in the corresponding rule set, and

a second mechanism for computing bitwise AND for said low level bit sequences of the data packet for obtaining low level result sequence, and for finding, in said low level result sequence, the first 1 starting from the beginning of the low level result sequence, the position of said first 1 indicating the rule matching the data packet.

16. A computer program product, containing computer program code for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and wherein executing said computer program code in a computer causes the computer to execute the steps of:

determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match, and

finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet.

17. A computer program product, containing computer program code for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and wherein executing said computer program code in a computer causes the computer to execute the steps of:

computing, for each parameter field in the rule base, a data structure indicating different values or value ranges of the parameter field and, for each different value or value range, a rule set of the rules, to which said value or value range can match,

storing said data structures,

finding in said data structures rule sets for the data packet, said rule sets being the rule sets corresponding to the parameter field values of the data packet, and

finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet.

18. A computer program product, containing computer program code for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and wherein executing said computer program code in a computer causes the computer to execute the steps of:

determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,

computing a table for the combination of the rule sets of the data packet, the rows of the table corresponding to the labels of the rules in the rule base, and the columns of the table corresponding to the different rule sets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of a rule of the respective rule set and equal to or larger than the label of the respective row,

observing a first element in a first row of a first column and comparing the first element to the respective row label,

if the element is equal to the row label, jumping to another column in the same row and observing a second element found therein, or otherwise jumping to the row indicated by the first element and observing a second element found in a column therein, and

proceeding on the basis of the second element and the respective row label in the same way as with the first element, and

repeating the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row or said equal element indicating the rule matching the data packet.

19. A computer program product, containing computer program code for finding an element with the smallest label that is present in a plurality of finite subsets containing finite number of elements, said subsets being subsets of a set containing finite number of sequentially labelled elements, and wherein executing said computer program code in a computer causes the computer to execute the steps of:

computing a table for the plurality of finite subsets, the rows of the table corresponding to the labels of the elements of the set, and the columns of the table corresponding to the different subsets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of an element of the respective subset and equal to or larger than the label of the respective row,

observing a first element in a first row of a first column and comparing the first element to the respective row label,

if the element is equal to the row label, jumping to another column in the same row and observing a second element found therein, or otherwise jumping to the row indicated by the first element and observing a second element found in a column therein, and

proceeding on the basis of the second element and the respective row label in the same way as with the first element, and

repeating the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row indicating the element with the smallest label that is present in the plurality of subsets.

20. A computer program product, containing computer program code for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and wherein executing said computer program code in a computer causes the computer to execute the steps of:

determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,

computing low level bit sequences for the data packet, each low level bit sequence corresponding to one rule set in the combination of the rule sets of the data packet, each bit of a low level bit sequence corresponding to one rule in the rule base, and a bit in a low level bit sequence being set to 0, if the corresponding rule is not present in the corresponding rule set, and a bit in a low level bit sequence being set to 1, if the corresponding rule is present in the corresponding rule set,

computing bitwise AND for said low level bit sequences of the data packet for obtaining low level result sequence, and

finding, in said low level result sequence, the first 1 starting from the beginning of the low level result sequence, the position of said first 1 indicating the rule matching the data packet.