Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Protection at a particular protocol layer
Reexamination Certificate
1999-08-12
2002-02-12
Breene, John (Department: 2177)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Protection at a particular protocol layer
C707S793000
Reexamination Certificate
active
06347376
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to the field of networking and network security, and specifically to improvements in the implementation of security arrangements that conform to the requirements of RFC 2401—“Security Architecture for the Internet Protocol”.
Specifically, the invention uses a data structure and arrangement that avoids the searching of dynamic security rules except when a static rule placeholder pointing to a set of dynamic rules is found to govern the security processing of a packet.
BACKGROUND OF THE INVENTION
RFC 2401 sets forth an architecture for the implementation of security in networks that use the IP protocol. This security architecture is commonly referred as IPsec. IPsec is the architecture endorsed by the Internet Engineering Task Force (IETF) for applying encryption and authentication security services to datagrams, or packets, at the IP layer of the protocol stack. The IPsec specification requires a Security Policy Database (SPD) that is used to determine how each incoming and outgoing packet is to be handled from a security perspective. The basic choices are deny packet, permit packet, and permit packet with Ipsec processing. If Ipsec processing is to be applied to a packet, the database specifies the precise processing that is to be applied. Because IPsec is applied at the IP layer, it is used for all upper layer protocols (TCP, UDP, ICMP, etc.) and it is applied as a connectionless protocol. That is, each IP packet is processed independently of any other packet.
In the known art, the SPD contains static rules and placeholders for dynamic rules. The rules and placeholders contain attributes to be matched against the corresponding attributes of incoming and outgoing packets to determine which rule should be applied to a packet. The attributes contained in the rules and placeholders might be different combinations of IP source address, source port, IP destination address, destination port and the protocol to be used. The attributes contained within a specific rule or placeholder can be as granular as specific hosts, ports and protocol for a match to occur, or as coarse as wild carded host pairs.
A static rule is essentially a policy rule. It is predefined for a network and generally not changed very often. For example, static rules might specify that all traffic between hosts A and B will be permitted without Ipsec processing and that all traffic between hosts A and C will be encrypted by IPsec. A dynamic rule is negotiated as needed and linked into the SPD database. The how, when and why of a dynamic rule negotiation is not part of the present invention and is not discussed in any detail. It suffices to say that when a dynamic rule is negotiated, the placeholder that contains the most specific attributes that includes the negotiated attributes is used to link the negotiated rule into the SPD database at the appropriate point. In the known art, the static rules, dynamic rules and placeholders are searched for every incoming and outgoing packet at a node to determine how to process the packet.
The IPsec architecture also requires that the rules be defined and processed in a specific order. This is absolutely necessary, because it is important for different hosts to apply the same type of security processing to the same packet. If a packet is encrypted with a specific algorithm, it is important that the receiving node locate the correct rule to decrypt the packet with the corresponding decryption algorithm. RFC 2401 requires that the SPD be ordered and that the SPD always be searched in the same order to insure consistent results at different nodes. The traditional technique of ordering the rules and placeholders in the SPD is from the most specific to least specific in terms of the specification of the attributes in the rules that are used for matching; the database (including static, dynamic rules and placeholders) is searched linearly in this order for every incoming and outgoing packet until a first match is found between the attributes of a packet and the attributes stored in a rule. At that point, the matching rule specifies whether the packet is denied, permitted without Ipsec processing or permitted with Ipsec processing. If the packet is permitted with Ipsec processing, the database specifies the details of that processing. This could be authentication or encryption or both.
In systems that become aggregation points (firewalls and servers) the number of filter rules in the database can be hundreds to thousands, depending on the network. In the known art, the SPD database is searched sequentially until a matching rule is found for all incoming and outgoing packets. This sequential search includes static rules and dynamic rules as they are encountered in the database. The performance cost on systems as a result of this searching is significant. In a system that has a mixture of IPsec and non-IPsec traffic, even the non-IPsec traffic is penalized because the filter rules must be searched to determine if a particular packet is subject to Ipsec processing or not.
SUMMARY OF THE INVENTION
The invention improves the performance of system IPsec rule searching in a number of ways. It is important that the Ipsec rules be searched in a predictable manner so that Ipsec processing applied at a sending end can be reversed at a receiving end. To achieve this predictability, Ipsec rules are searched in order from rules containing the most specificity of attributes to those containing the least specificity of attributes. In accordance with one aspect of the invention, the table of security rules is arranged in a way that significantly reduces the search time in most cases. The static rules include placeholders for sets of dynamic rules that are negotiated and entered into the dynamic sets as needed. The placeholders in the static table immediately precede and point to an associated set of dynamic rules. A set of dynamic rules is searched only if a match is found on the corresponding static placeholder during a search of the static rules. This dramatically improves performance, since most of the dynamic rules are not searched on a per packet basis, in contrast to the known prior art.
According to a second aspect of the invention, sets of dynamic rules are partitioned into separate groups such that within a group there is no rule order dependence. That is, within a group, the order of appearance of the rules is irrelevant. Because the rules for a group are order independent, each group can be represented by an enhanced search mechanism, rather than just a sequentially linked list of rules. Such mechanisms might be binary search trees, promoted lists and hash tables. A binary search tree, specifically a patricia tree, is used to represent each group in the preferred embodiment. There are five such groups in the preferred embodiment. The groups are searched in the order of groups containing the most specific attributes to those containing the least specific attributes. The attributes are source IP address (SA), destination IP address (DA), source port (SP), destination port (DP) and a protocol P. Each dynamic rule contained in the first group of dynamic rules specifies values for all five attributes (SA, DA, SP, DP, P). The second and third groups specify the IP addresses SA and DA and the protocol P. In addition, the second group specifies the source port SP; the third group specifies the destination port DP. The second and third groups are special in that which appears first in sequence is not important.
The rules of the fourth group specify source address SA, destination address DA and the protocol attribute P. The rules of the fifth group specify only source address SA and destination address DA.
There is a sixth group which is order dependent and cannot be optimized for enhanced searching. The rules of the sixth group contain a range of addresses in either or both of the source and destination address fields. This fact makes the order of appearance of rules within the group important. The sixth group is searched by sequentially searching the
Attwood Kira Sterling
Godwin James Russell
Overby, Jr. Linwood Hugh
Perry Brian Sean
Wierbowski David John
Breene John
Herndon Jerry W.
International Business Machines Corp.
Rayyan Susan
LandOfFree
Security rule database searching in a network security... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Security rule database searching in a network security..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Security rule database searching in a network security... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2942560