System, method and computer program for filtering multi-action rule set

• US 6,473,763 B1
• Filed: 03/31/2000
• Issued: 10/29/2002
• Est. Priority Date: 03/31/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Corl, Everett Arthur Jr., Jeffries, Clark Debs, Verrilli, Colin Beaton
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): MOFIZ, APU M
• Application Number:
  US09/540,921
• Time in Patent Office: 942 Days
• Field of Search: 707/1, 707/2, 707/3, 707/5, 707/100, 707/102, 707/101, 376/401, 709/203, 709/218, 709/225, 709/238, 709/239, 712/235, 714/26, 714/758
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/1433 Vulnerability analysis
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and system for testing a plurality of filter rules in a computer system is disclosed. The plurality of filter rules is used with a key. Each of the plurality of filter rules is capable of being described using a plurality of bits corresponding to a portion of the key. The plurality of bits can include at least one binary value, at least one wildcard, and at least one boundary symbol. The at least one binary value can be a zero or a one. The method and system include selecting a portion of the plurality of filter rules that the key can match by testing part of the key against a portion of the plurality of bits and explicitly testing the key against the portion of the plurality of filter rules. A first bit of the portion of the plurality of bits has a first maximum number of the at least one binary symbol for the plurality of filter rules. Each subsequent bit of the portion plurality of bits has a second maximum number of the at least one binary symbol for a plurality of remaining bits and is selected based on testing of a prior bit. Preferably, the portion of the plurality of bits is tested using a decision tree which includes nodes corresponding to a second portion of the plurality of bits.

Claims

1. A method for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the method comprising the steps of:

(a) selecting a portion of the plurality of filter rules that the key can match by testing the key against a portion of the plurality of bits, a first bit of the portion of the plurality of bits having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent bit of the portion plurality of bits having a second maximum number of the at least one binary symbol for a plurality of remaining bits and being selected based on testing of a prior bit of the portion of the plurality of bits; and

(b) testing the portion of the plurality of rules against the key.

2. The method of claim 1 wherein the selecting step (a) further includes the step of:

(a1) selecting the portion of the plurality of filter rules that the key can match using a decision tree and the portion of the plurality of bits, the decision tree including a plurality of nodes and a plurality of leaves, the portion of the plurality of filter rules being on at least one leaf of the plurality of leaves, a first node of the plurality of nodes corresponding to the first bit of the plurality of bits for each of the plurality of filter rules, the first bit having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent node of the plurality of nodes corresponding to a bit of a second plurality of remaining bits for each of the plurality of filter rules, the bit having a second maximum number of the at least one binary symbol for the plurality of remaining bits.

3. The method of claim 2 wherein the method further includes the step of:

(c) providing the decision tree, the decision tree providing step including the steps of;

(c1) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules;

(c2) providing a first node of the plurality of nodes using the first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has the first maximum number of the at least one binary symbols for the plurality of filter rules;

(c3) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one;

(c4) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero;

(c5) repeating steps (c2) through (c4) for each of the second matrix and the third matrix until the plurality of nodes is provided.

4. The method of claim 3 wherein the first matrix providing step further includes the step of:

(c1i) ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.

5. The method of claim 3 wherein the first matrix providing step further includes the step of:

(c1i) ranking the plurality of filter rules based on a type of each of the plurality of filter rules.

6. The method of claim 3 wherein the first matrix providing step further includes the step of:

(c1i) ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.

7. The method of claim 3 wherein the first, second and third matrix are capable of having a pair of duplicate rows having a same type, a first row of the pair of duplicate rows having a higher priority, a second row of the pair of duplicate rows having a lower priority, neither row of the pair of duplicate rows having a boundary symbol, the first matrix, second matrix and third matrix further being provided by removing the second row.

8. The method of claim 1 wherein the key further includes a plurality of fields and wherein the plurality of bits for each of the plurality of filter rules corresponds to a field of the plurality of fields.

9. The method of claim 8 wherein the plurality of filter rules are further described by a second plurality of bits corresponding to remaining fields of the plurality of fields, and wherein the method further includes the steps of:

(c) repeating steps (a) and (b) for the remaining fields of the plurality of fields using a portion of the second plurality of bits.

10. The method of claim 3 wherein the decision tree includes at least one pointer from at least one particular node of the plurality of nodes to at least a starting node of at least one subtree, thereby allowing the at least one subtree to be utilized for more than a single node.

11. The method of claim 1 wherein the plurality of filter rules can be of a plurality of types.

12. A method for providing a decision tree for testing a plurality of filter rules in a computer system, the decision tree including a plurality of nodes and a plurality of leaves, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the method comprising the steps of:

(a) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules;

(b) providing a first node of the plurality of nodes using a first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has a first maximum number of the at least one binary symbols for the plurality of filter rules;

(c) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one;

(d) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero;

(e) repeating steps (b) through (d) for each of the second matrix and the third matrix until the plurality of nodes is provided.

13. The method of claim 12 wherein the first matrix providing step further includes the step of:

(a1) ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.

14. The method of claim 12 wherein the first matrix providing step further includes the step of:

(a2) ranking the plurality of filter rules based on a type of each of the plurality of filter rules.

15. The method of claim 12 wherein the first matrix providing step further includes the step of:

(a3) ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.

16. The method of claim 12 wherein the first, second and third matrix are capable of having a pair of duplicate rows having a same type, a first row of the pair of duplicate rows having a higher priority, a second row of the pair of duplicate rows having a lower priority, neither row of the pair of duplicate rows having a boundary symbol, the first matrix, second matrix and third matrix further being provided by removing the second row.

17. The method of claim 13 wherein the key further includes a plurality of fields and wherein the plurality of bits for each of the plurality of filter rules corresponds to a field of the plurality of fields.

18. The method of claim 17 wherein the plurality of filter rules are further described by a second plurality of bits corresponding to remaining fields of the plurality of fields, and wherein the method further includes the steps of:

(f) repeating steps (a) through (e) for the remaining fields of the plurality of fields using a portion of the second plurality of bits, thereby providing a plurality of decision trees for the plurality of fields.

19. The method of claim 12 further comprising the step of:

(f) replacing at least one particular subtree with at least one pointer from at least one particular node of the at least one particular subtree to at least a starting node of at least one other subtree, thereby allowing the at least one other subtree to be utilized in place of the at least one particular subtree.

20. A computer-readable medium including a program for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the program including instructions for:

(a) selecting a portion of the plurality of filter rules that the key can match by testing the key against a portion of the plurality of bits, a first bit of the portion of the plurality of bits having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent bit of the portion plurality of bits having a second maximum number of the at least one binary symbol for a plurality of remaining bits and being selected based on testing of a prior bit of the portion of the plurality of bits; and

(b) testing the portion of the plurality of rules against the key.

21. The computer-readable medium of claim 20 wherein the selecting instructions (a) further includes instructions for:

(a1) selecting the portion of the plurality of filter rules that the key can match using a decision tree and the portion of the plurality of bits, the decision tree including a plurality of nodes and a plurality of leaves, the portion of the plurality of filter rules being on at least one leaf of the plurality of leaves, a first node of the plurality of nodes corresponding to the first bit of the plurality of bits for each of the plurality of filter rules, the first bit having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent node of the plurality of nodes corresponding to a bit of a second plurality of remaining bits for each of the plurality of filter rules, the bit having a second maximum number of the at least one binary symbol for the plurality of remaining bits.

22. The computer-readable medium of claim 21 wherein the program further includes instructions for:

(c) providing the decision tree, the decision tree providing instruction including instructions for;

(c1) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules;

(c2) providing a first node of the plurality of nodes using the first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has the first maximum number of the at least one binary symbols for the plurality of filter rules;

(c3) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one;

(c4) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero;

(c5) repeating instructions (c2) through (c4) for each of the second matrix and the third matrix until the plurality of nodes are provided.

23. The computer-readable medium of claim 22 wherein the first matrix providing step further includes instructions for:

(c1i) ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.

24. The computer-readable medium of claim 22 wherein the first matrix providing step further includes instructions for:

(c1i) ranking the plurality of filter rules based on a type of each of the plurality of filter rules.

25. The computer-readable medium of claim 22 wherein the first matrix providing step further includes instructions for:

(c1i) ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.

26. The computer-readable medium of claim 22 wherein the decision tree includes at least one pointer from at least one particular node of the plurality of nodes to at least a starting node of at least one subtree, thereby allowing the at least one subtree to be utilized for more than a single node.

27. A computer-readable medium containing a program for providing a decision tree for testing a plurality of filter rules in a computer system, the decision tree including a plurality of nodes and a plurality of leaves, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the program including instructions for:

(a) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules;

(b) providing a first node of the plurality of nodes using a first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has a first maximum number of the at least one binary symbols for the plurality of filter rules;

(c) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one;

(d) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero;

(e) repeating steps (b) through (d) for each of the second matrix and the third matrix until the plurality of nodes is provided.

28. A system for testing a plurality of filter rules in a computer system, A method for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the system comprising:

a plurality of hosts for transmitting and receiving data;

a switch for selecting a portion of the plurality of filter rules that the key can match by testing the key against a portion of the plurality of bits, a first bit of the portion of the plurality of bits having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent bit of the portion plurality of bits having a second maximum number of the at least one binary symbol for a plurality of remaining bits and being selected based on testing of a prior bit of the portion of the plurality of bits and for testing the portion of the plurality of rules against the key.

29. The system of claim 28 wherein the switch includes:

a decision tree, the decision tree including a plurality of nodes and a plurality of leaves, the portion of the plurality of filter rules being on at least one leaf of the plurality of leaves, a first node of the plurality of nodes corresponding to the first bit of the plurality of bits for each of the plurality of filter rules, the first bit having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent node of the plurality of nodes corresponding to a bit of a second plurality of remaining bits for each of the plurality of filter rules, the bit having a second maximum number of the at least one binary symbol for the plurality of remaining bits.

30. The system of claim 29 further comprising:

a control point for providing the decision tree, the decision tree being provided by providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules, providing a first node of the plurality of nodes using the first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has the first maximum number of the at least one binary symbols for the plurality of filter rules, providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one, providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one zero and excluding a row of the first matrix if the entry in the column for the row is a zero and repeating the steps of selecting the columns, providing a node, providing the second matrix and providing the third matrix for the second and third matrices until the portion of the plurality of rules can be isolated on the decision tree.

31. The system of claim 30 wherein the first matrix is provided by ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.

32. The system of claim 30 wherein the first matrix is provided by ranking the plurality of filter rules based on a type of each of the plurality of filter rules.

33. The system of claim 30 wherein the first matrix is provided by ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.

34. The system of claim 30 wherein the first, second and third matrix are capable of having a pair of duplicate rows having a same type, a first row of the pair of duplicate rows having a higher priority, a second row of the pair of duplicate rows having a lower priority, neither row of the pair of duplicate rows having a boundary symbol, the first matrix, second matrix and third matrix further being provided by removing the second row.

35. The system of claim 28 wherein the key further includes a plurality of fields and wherein the plurality of bits for each of the plurality of filter rules corresponds to a field of the plurality of fields.

36. The system of claim 35 wherein the plurality of filter rules are further described by a second plurality of bits corresponding to remaining fields of the plurality of fields, and wherein the switch repeats the selection of the portion of the plurality of filter rules and the testing of the portion of the plurality of filter rules for the remaining fields of the plurality of fields using a portion of the second plurality of bits.

37. The system of claim 30 wherein the decision tree includes at least one pointer from at least one particular node of the plurality of nodes to at least a starting node of at least one subtree, thereby allowing the at least one subtree to be utilized for more than a single node.

38. The system of claim 29 wherein the plurality of filter rules can be of a plurality of types.

39. A system for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the system comprising:

a plurality of hosts for transmitting and receiving data;

a control point for providing a decision tree; and

logic coupled with the plurality of hosts and the control point for testing the plurality of filter rules, the logic including the decision tree having a plurality of nodes and a plurality of leaves, the decision tree being provided by providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules, providing a first node of the plurality of nodes using a first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has a first maximum number of the at least one binary symbols for the plurality of filter rules, providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one, providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one zero and excluding a row of the first matrix if the entry in the column for the row is a zero and repeating the column selecting, second matrix providing and third matrix providing steps for the second and third matrix to provide a plurality of remaining nodes for the decision tree.

40. The system of claim 39 wherein the first matrix is provided by ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.

41. The system of claim 39 wherein the first matrix is provided by ranking the plurality of filter rules based on a type of each of the plurality of filter rules.

42. The system of claim 39 wherein the first matrix is provided by ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.

43. The system of claim 39 wherein the key further includes a plurality of fields and wherein the plurality of bits for each of the plurality of filter rules corresponds to a field of the plurality of fields.

44. The system of claim 39 wherein the first, second and third matrix are capable of having a pair of duplicate rows having a same type, a first row of the pair of duplicate rows having a higher priority, a second row of the pair of duplicate rows having a lower priority, neither row of the pair of duplicate rows having a boundary symbol, the first matrix, second matrix and third matrix further being provided by removing the second row.

45. The system of claim 39 wherein the decision tree is further formed by replacing at least one particular subtree with at least one pointer from at least one particular node of the at least one particular subtree to at least a starting node of at least one other subtree, thereby allowing the at least one other subtree to be utilized in place of the at least one particular subtree.