System and method for very fast IP packet filtering
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
12 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. - View Dependent Claims (2)
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. - View Dependent Claims (8)
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.
-
Specification