Security rule database searching in a network security environment

• US 6,347,376 B1
• Filed: 08/12/1999
• Issued: 02/12/2002
• Est. Priority Date: 08/12/1999
• Status: Expired due to Term

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Attwood, Kira Sterling, Overby, Linwood Hugh Jr., Wierbowski, David John, Godwin, James Russell, Perry, Brian Sean
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): RAYYAN, SUSAN F
• Application Number:
  US09/373,104
• Time in Patent Office: 915 Days
• Field of Search: 713/200, 713/168, 709/221, 709/223, 709/225, 707/3, 707/9, 707/104
• US Class Current: 726/1
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/0272 Virtual private networks
• CPC Class Codes: H04L 63/102 Entity profiles
• CPC Class Codes: H04L 63/164 at the network layer
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Ipsec rules are searched in order from rules containing the most specificity of attributes to those containing the least specificity of attributes. The static rules include placeholders for sets of dynamic rules. The placeholders in the static table immediately precede and point to an associated set of dynamic rules. Dynamic rules are searched only if a placeholder is found to be the first matching rule in the static table. Sets of dynamic rules are partitioned into separate groups. Within each group there is no rule order dependence. Each such group is searched with an enhanced search mechanism, such as a search tree. Searching is further improved by searching at layers higher than the IP layer.

Claims

1. A method of searching a database of security rules for a match between the values of specified attributes of a packet and the values of corresponding attributes associated with each rule, wherein the database is searched in the order of the rules containing the most specific values of attributes to the least specific values of attributes, comprising

arranging the database into a set of relatively stable static rules and one or more sets of dynamic security rules, wherein a static rule can be a placeholder for a set of dynamic rules,

searching the static rules of the database for the first static rule having attributes that match the corresponding attributes of the packet,

determining if the matching static rule is a placeholder for a set of dynamic rules,

if the matching static rule is a placeholder for a set of dynamic rules, searching the set of dynamic rules associated with the matching static rule for a match between the packet attributes and attributes contained in the dynamic rules, and

applying security processing to the packet as specified by the matching static or dynamic rule.

2. The method of claim 1 further comprising

partitioning a set of dynamic rules into groups according to attributes such that within each group there is no order dependency of the rules, and

searching the dynamic rules within a group using a non-sequential search mechanism.

3. The method of claim 2 wherein the groups are defined on attributes of the internet protocol (IP) and ordered as follows:

a first group specifying attributes of source IP address, destination IP address, source port, destination port, and protocol;

a second group specifying attributes of source IP address, destination IP address, either a source port or an address port, and protocol;

a third group specifying attributes of source IP address, destination IP address, the other of the source port or the destination port that is not specified by the second group, and protocol;

a fourth group specifying source IP address, destination IP address, and protocol; and

a fifth group specifying source IP address and destination IP address.

4. The method of claim 3 further comprising

defining a sixth group of dynamic rules that contain a range of IP addresses specified in either or both of the source and destination addresses, and

sequentially the rules of the sixth group if no match is found between the attributes specified in the dynamic rules of the first through the fifth groups and the corresponding attributes of the packet.

5. Apparatus for searching a database of security rules for a match between the values of specified attributes of a packet and the values of corresponding attributes associated with each rule, wherein the database is searched in the order of the rules containing the most specific values of attributes to the least specific values of attributes, comprising

a set of relatively stable static rules in the database and one or more sets of dynamic security rules in the database, wherein a static rule can be a placeholder for a set of dynamic rules,

structure for searching the static rules of the database for the first static rule having attributes that match the corresponding attributes of the packet,

structure for determining if the matching static rule is a placeholder for a set of dynamic rules,

structure responsive to the determining structure for searching a set of dynamic rules associated with a matching placeholder for a match between the packet attributes and attributes contained in the dynamic rules, and

security processing structure for processing the packet as specified by the matching static or dynamic rule.

6. The apparatus of claim 5 further comprising

structure for partitioning a set of dynamic rules into groups according to attributes such that within each group there is no order dependency of the rules, and

structure for searching the dynamic rules within a group using a non-sequential search mechanism.

7. The apparatus of claim 6 wherein the groups are defined on the attributes of the internet protocol (IP) and ordered as follows:

a first group specifying attributes of source IP address, destination IP address, source port, destination port, and protocol;

a second group specifying attributes of source IP address, destination IP address, either a source port or an address port, and protocol;

a third group specifying attributes of source IP address, destination IP address, the other of the source port or the destination port that is not specified by the second group, and protocol;

a fourth group specifying source IP address, destination IP address, and protocol; and

a fifth group specifying source IP address and destination IP address.

8. The apparatus of claim 7 further comprising

a sixth group of dynamic rules containing a range of IP addresses specified in either or both of the source and destination addresses, and

structure activated after the first through the fifth groups of dynamic rules of a set have been unsuccessfully searched for sequentially searching the rules of the sixth group.

9. A storage medium containing stored executable computer instructions for controlling a computer to search a database of security rules for a match between the values of specified attributes of a packet and the values of corresponding attributes associated with each rule, wherein the database is searched in the order of the rules containing the most specific values of attributes to the least specific values of attributes, comprising

a first code segment for arranging the database into a set of relatively stable static rules and one or more sets of dynamic security rules, wherein a static rule can be a placeholder for a set of dynamic rules,

a second code segment for searching the static rules of the database for the first static rule having attributes that match the corresponding attributes of the packet,

a third code segment for determining if the matching static rule is a placeholder for a set of dynamic rules,

a fourth code segment responsive to the third segment for searching the set of dynamic rules associated with the matching placeholder for a match between the packet attributes and attributes contained in the dynamic rules, and

a fifth code segment for applying security processing to the packet as specified by the matching static or dynamic rule.

10. The storage medium of claim 9 further comprising

a sixth code segment for partitioning a set of dynamic rules into groups according to attributes such that within each group there is no order dependency of the rules, and

an seventh code segment for searching the dynamic rules within a group using a non-sequential search mechanism.

11. The storage medium of claim 10 wherein the first code segment defines the groups on the internet protocol (IP) and orders then as follows:

a first group specifying attributes of source IP address, destination IP address, source port, destination port, and protocol;

a second group specifying attributes of source IP address, destination IP address, either a source port or an address port, and protocol;

a third group specifying attributes of source IP address, destination IP address, the other of the source port or the destination port that is not specified by the second group, and protocol;

a fourth group specifying source IP address, destination IP address, and protocol; and

a fifth group specifying source IP address and destination IP address.

12. The storage medium of claim 11 further comprising

an eighth code segment for defining a sixth group of dynamic rules that contain a range of IP addresses specified in either or both of the source and destination addresses, and

a ninth code segment for sequentially searching the rules of the sixth group if no match is found between the attributes specified in the dynamic rules of the first through the fifth groups and the corresponding attributes of the packet.

13. A carrier wave embodying a computer data signal and containing stored executable computer instructions for controlling a computer to search a database of security rules for a match between the values of specified attributes of a packet and the values of corresponding attributes associated with each rule, wherein the database is searched in the order of the rules containing the most specific values of attributes to the least specific values of attributes, comprising

a first code segment for arranging the database into a set of relatively stable static rules and one or more sets of dynamic security rules, wherein a static rule can be a placeholder for a set of dynamic rules,

a second code segment for searching the static rules of the database for the first static rule having attributes that match the corresponding attributes of the packet,

a third code segment for determining if the matching static rule is a placeholder for a set of dynamic rules,

a fourth code segment responsive to the third code segment for searching the set of dynamic rules associated with the matching placeholder for a match between the packet attributes and attributes contained in the dynamic rules, and

a fifth code segment for applying security processing to the packet as specified by the matching static or dynamic rule.

14. The carrier wave of claim 13 further comprising

a sixth code segment for partitioning a set of dynamic rules into groups according to attributes such that within each group there is no order dependency of the rules, and

an seventh code segment for searching the dynamic rules within a group using a non-sequential search mechanism.

15. The carrier wave of claim 14 wherein the first code segment defines the groups on the internet protocol (IP) and orders then as follows:

a first group specifying attributes of source IP address, destination IP address, source port, destination port, and protocol;

a second group specifying attributes of source IP address, destination IP address, either a source port or an address port, and protocol;

a third group specifying attributes of source IP address, destination IP address, the other of the source port or the destination port that is not specified by the second group, and protocol;

a fourth group specifying source IP address, destination IP address, and protocol; and

a fifth group specifying source IP address and destination IP address.

16. The data signal of claim 15 further comprising

a eighth code segment for defining a sixth group of dynamic rules that contain a range of IP addresses specified in either or both of the source and destination addresses, and

a ninth code segment for sequentially searching the rules of the sixth group if no match is found between the attributes specified in the dynamic rules of the first through the fifth groups and the corresponding attributes of the packet.