System and method for very fast IP packet filtering

• US 6,301,669 B2
• Filed: 11/29/2000
• Issued: 10/09/2001
• Est. Priority Date: 08/17/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gebler, Paul A. Jr., Boden, Edward B., Brzozowski, Wesley A.
• Primary Examiner(s): Beausoleil, Robert
• Assistant Examiner(s): BADERMAN, SCOTT T
• Application Number:
  US09/726,203
• Publication Number:
  US 20010000193A1
• Time in Patent Office: 314 Days
• Field of Search: 713/201, 713/153, 713/151, 713/154-160, 713/164, 709/227, 709/228, 709/229, 709/237, 707/9, 707/101, 707/102
• US Class Current: 726/1
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

Small, optimized sequences of binary 6-tuples representing filter rules achieve very fast IP packet filtering. Filtering IP packets received from a caller at the physical interface to an operating system kernel is accomplished by processing FILTER rule statements entered by a user in a rules file to generate 6-tuple filtering rules, each of the 6-tuple filtering rules including an operator index; resolving relative and symbolic indexes in these 6-tuples filtering rules to form resolved filtering rules and loading the resolved filtering rules to the operating system kernel; and interpreting the resolved filtering rules for each IP packet received at the physical interface.

Claims

1. A method of compiling filtering rules into sets of binary symbolic and image files comprising the steps of:

expanding a primary file and N secondary included files to produce an expanded in-memory rule table including one or more source filter rules;

reading source filter rules from said in-memory rule table;

recognizing a plurality of physical interfaces that are targets for said source filter rules;

for said physical interfaces that are non-dynamic, generating binary image rule output files; and

for said physical interfaces that are dynamic, generating binary symbolic rule output files.

2. The method of claim 1, further comprising the steps of:

forming and loading 6-tuple filtering rules into an operating system kernel, said filtering rules including an operating field, a next rule field, an offset field, and at least one parameter value field;

combining a plurality of said 6-tuple filtering rules into a loadable binary image having load control indicia for defining tuple type and for allocating said 6-tuple filtering rules to interfaces;

executing a privileged process to load a copy of said loadable binary image across an operating system kernel boundary into said kernel; and

responsive to said control indicia in said loadable binary image, splitting said loadable binary image into copies specifically associated with each of said plurality of physical interfaces.

3. A method of processing filter rule statements to generate 6-tuple filtering rules, comprising the steps of:

providing a plurality of 6-tuple filtering rules having an operator index;

for each filter statement, finding within said filter statement a selector field;

for each said selector field, finding a selector name, selector value, and selector operator; and

generating a tuple by changing said selector name into a tuple offset value, changing said selector operator into a tuple operator index value, and copying said selector value into a tuple value field; and

for each said tuple, generating a a nextrule tuple-element by computing the offset between said tuple and a last tuple generated for said filter statement, and inserting said offset into the nextrule tuple element of said tuple.

4. A method of loading and resolving relative and symbolic indices in an operating system comprising the steps of:

providing symbolic indices in a set of 6-tuple filtering rules;

providing relative indices in said set of 6-tuple filtering rules;

resolving symbolic indices to IP address data outside of a kernel;

moving a copy of said symbolic and relative indices to operating system kernel space;

allocating system memory for said symbolic and relative indices and copying said 6-tuple filtering rules to said system memory organized according to a physical interface;

for each current 6-tuple filtering rule, resolving said relative indices to absolute addresses by combining a relative index and absolute address of said current 6-tuple filtering rule; and

resolving other symbolic indices in a tuple operator index field by table lookup to convert a 6-tuple operating index into an absolute physical address of a program.

5. A method of interpreting 6-tuples for each IP datagram in an operating system, comprising the steps of:

responsive to a request from a caller whose address is in said 6-tuple, passing said 6-tuple as an argument to an interpreter program for interpreting said 6-tuple;

executing said program to operate on said 6-tuple and return one of five code values, said code values including true, false, permit, deny and other codes;

in the case of said false code, jumping to a next rule and continuing interpreting a next 6-tuple;

in case of said true code, interpreting a physically next tuple in memory;

in case of said permit code, stopping interpreting and returning said permit code to said caller;

in case of said deny code, exiting said interpreter program and returning said deny code to said caller; and

in case of said other codes, exiting said interpreter program and returning other code action to said caller.

6. A method of operating a filter rule interpreter to activate operator functions in an operating system, comprising the steps of:

providing an ordered set of interpreter 6-tuples in a 6-tuple stream, said 6-tuples including addresses of callable functions and data for operating said callable functions;

providing an interpreter which, responsive to an external invocation, operates on said 6-tuple stream to interpret successive said 6-tuples until told to exit by said 6-tuple stream; and

interpreting each 6-tuple by calling that 6-tuple'"'"'s callable function and passing said 6-tuple as an argument to said callable function.

7. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for a method of compiling filtering rules into sets of binary symbolic and image files, said method steps comprising:

expanding a primary file and N secondary included files to produce an expanded in-memory rule table including one or more source filter rules;

reading source filter rules from said in-memory rule table;

recognizing a plurality of physical interfaces that are targets for said source filter rules;

for said physical interfaces that are non-dynamic, generating binary image rule output files; and

for said physical interfaces that are dynamic, generating binary symbolic rule output files.

8. The program storage device of claim 7, said method steps further including:

forming and loading 6-tuple filtering rules into an operating system kernel, said filtering rules including an operating field, a next rule field, an offset field, and at least one parameter value field;

combining a plurality of said 6-tuple filtering rules into a loadable binary image having load control indicia for defining tuple type and for allocating said 6-tuple filtering rules to interfaces;

executing a privileged process to load a copy of said loadable binary image across an operating system kernel boundary into said kernel; and

responsive to said control indicia in said loadable binary image, splitting said loadable binary image into copies specifically associated with each of said plurality of physical interfaces.

9. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for processing filter rule statements to generate 6-tuple filtering rules, said method steps comprising:

providing a plurality of 6-tuple filtering rules having an operator index;

for each filter statement, finding within said filter statement a selector field;

for each said selector field, finding a selector name, selector value, and selector operator; and

generating a tuple by changing said selector name into a tuple offset value, changing said selector operator into a tuple operator index value, and copying said selector value into a tuple value field; and

for each said tuple, generating a nextrule tuple-element by computing the offset between said tuple and a last tuple generated for said filter statement, and inserting said offset into the nextrule tuple-element of said tuple.

10. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for loading and resolving relative and symbolic indices in an operating system, said method ste comprising:

providing symbolic indices in a set of 6-tuple filtering rules;

providing relative indices in said set of 6-tuple filtering rules;

resolving symbolic indices to IP address data outside of a kernel;

moving a copy of said symbolic and relative indices to operating system kernel space;

allocating system memory for said symbolic and relative indices and copying said 6-tuple filtering rules to said system memory organized according to physical interface;

for each current 6-tuple filtering rule, resolving said relative indices to absolute addresses by combining a relative index and absolute address of said current 6-tuple filtering rule; and

resolving other symbolic indices in a tuple operator index field by table lookup to convert a 6-tuple operating index into an absolute physical address of a program.

11. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for interpreting 6-tuples for each IP datagram in an operating system, comprising the steps of:

responsive to a request from a caller whose address is in said 6-tuple, passing said 6-tuple as an argument to an interpreter program for interpreting said 6-tuple;

executing said program to operate on said 6-tuple and return one of five code values, said code values including true, false, permit, deny and other codes;

in the case of said false code, jumping to a next rule and continuing interpreting a next 6-tuple;

in case of said true code, interpreting a physically next tuple in memory;

in case of said permit code, stopping interpreting and returning said permit code to said caller;

in case of said deny code, exiting said interpreter program and returning said deny code to said caller; and

in case of said other codes, exiting said interpreter program and returning other code action to said caller.

12. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for operating a filter rule interpreter to activate operator functions in an operating system, said method steps comprising:

providing an ordered set of interpreter 6-tuples in an 6-tuple stream, said 6-tuples including addresses of callable functions and data for operating said callable functions;

providing an interpreter which, responsive to an external invocation, operates on said 6-tuple stream to interpret successive said 6-tuples until told to exit by said 6-tuple stream; and

interpreting each 6-tuple by calling that 6-tuple'"'"'s callable function and passing said 6-tuple as an argument to said callable function.