US6301669B2 — System and method for very fast IP packet filteri…

Claim 1

Independent Claim 91 words

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.

Claim 2

Independent Claim 91 words

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.

Claim 3

Dependent Claim 123 words

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.

Claim 4

Independent Claim 125 words

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.

Claim 5

Independent Claim 125 words

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.

Claim 6

Independent Claim 143 words

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.

Claim 7

Independent Claim 143 words

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.

Claim 8

Independent Claim 154 words

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.

Claim 9

Independent Claim 154 words

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.

Claim 10

Independent Claim 93 words

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.

Claim 11

Independent Claim 93 words

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.

Claim 12

Dependent Claim 114 words

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.

Claim 13

Dependent Claim 114 words

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.

Claim 14

Dependent Claim 125 words

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.

Claim 15

Dependent Claim 143 words

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.

Claim 16

Dependent Claim 143 words

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.

Claim 17

Dependent Claim 162 words

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.

Claim 18

Dependent Claim 162 words

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.

Claim 19

Dependent Claim 174 words

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.

Claim 20

Dependent Claim 174 words

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.

Claim 21

Dependent Claim 113 words

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.

Claim 22

Dependent Claim 113 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2004-10-08	2005-04-09	2005-10-09	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2008-10-08	2009-04-09	2009-10-09	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2012-10-08	2013-04-09	2013-10-09	$7700.00	Window Closed / Lapsed

System and method for very fast IP packet filtering

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag