US6182228B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for very fast IP packet filtering
Assignee: International Business Machines Corp
•
Filing: 1998-08-17
•
Granted: 2001-01-30
•
Expires: 2018-08-17
Abstract
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 kernal; and interpreting the resolved filtering rules for each IP packet received at the physical interface.
Inventors
- 👤 Edward B. Boden
- 👤 Wesley A. Brzozowski
- 👤 Paul A. Gebler, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:34
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/74; H04L45/742; H04L63/00; H04L63/02; H04L63/0227; H04L63/0263; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99939
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
220 words
A method for generating, from user-entered rules, filtering rules for execution in an operating system kernel to filter an IP packet received at a physical interface to said operating system kernel comprising the steps of: compiling said user-entered filtering rules into sets of binary symbolic and image files, with one said set for each said physical interface for which there exist said user-entered rules; upon starting said physical interface to said operating system kernel, resolving filtering rules in said symbolic file to form resolved 6-tuple filtering rules in image format, and loading to said operating system kernel said resolved 6-tuple filtering rules and 6-tuple filtering rules from said image file; said 6-tuple filtering rules in image format including an operator field and, selectively, a next rule field, an offset field and zero or more parameter value fields; said operator field comprising a function index that is resolved to a function pointer upon being loaded to memory in said operating system kernel; said next rule field selectively comprising a pointer to a first 6-tuple of a next rule; said offset field selectively representing an offset into an IP packet to be checked by said first 6-tuple; and a first said parameter value field comprising a value to be compared against a field in said IP packet accessed by said offset field.
Claim 2
Independent Claim
220 words
A method for generating, from user-entered rules, filtering rules for execution in an operating system kernel to filter an IP packet received at a physical interface to said operating system kernel comprising the steps of: compiling said user-entered filtering rules into sets of binary symbolic and image files, with one said set for each said physical interface for which there exist said user-entered rules; upon starting said physical interface to said operating system kernel, resolving filtering rules in said symbolic file to form resolved 6-tuple filtering rules in image format, and loading to said operating system kernel said resolved 6-tuple filtering rules and 6-tuple filtering rules from said image file; said 6-tuple filtering rules in image format including an operator field and, selectively, a next rule field, an offset field and zero or more parameter value fields; said operator field comprising a function index that is resolved to a function pointer upon being loaded to memory in said operating system kernel; said next rule field selectively comprising a pointer to a first 6-tuple of a next rule; said offset field selectively representing an offset into an IP packet to be checked by said first 6-tuple; and a first said parameter value field comprising a value to be compared against a field in said IP packet accessed by said offset field.
Claim 3
Dependent Claim
40 words
The method of claim 1 wherein function and next rule indexes are resolved upon a 6-tuple load to said operating system kernel, whereby resolution is done once and need not be done for each IP packet as it is processed.
Claim 4
Dependent Claim
90 words
Method for filtering IP packets received from a caller at a physical interface to an operating system kernel, comprising the steps of: processing FILTER rule statements entered by a user in a rules file to generate 6-tuple filtering rules, each of said 6-tuple filtering rule including an operator index; resolving relative and symbolic indexes in said 6-tuple filtering rules to form resolved filtering rules and loading said resolved filtering rules to said operating system kernel; and interpreting said resolved filtering rules for each IP packet received at said physical interface.
Claim 5
Dependent Claim
90 words
Method for filtering IP packets received from a caller at a physical interface to an operating system kernel, comprising the steps of: processing FILTER rule statements entered by a user in a rules file to generate 6-tuple filtering rules, each of said 6-tuple filtering rule including an operator index; resolving relative and symbolic indexes in said 6-tuple filtering rules to form resolved filtering rules and loading said resolved filtering rules to said operating system kernel; and interpreting said resolved filtering rules for each IP packet received at said physical interface.
Claim 6
Dependent Claim
148 words
The method of claim 3 , said processing step comprising the further steps of: creating a tuple buffer to hold constructed 6-tuple filtering rules; setting a next byte pointer to the beginning of said tuple buffer; while more filter rule statements exist in said rules file, if a next rule is a filter statement, for each next logical condition in said filter statement, constructing a 6-tuple for said next logical condition, copying said 6-tuple to said tuple buffer at the location set by said next byte pointer, and incrementing said next byte pointer; constructing a final action 6-tuple and copying said final action 6-tuple to said tuple buffer at the location set by said next byte pointer, and incrementing said next byte pointer; and for each 6-tuple generated for this filter rule, setting a next rule tuple element to point to the next 6-tuple in said tuple buffer.
Claim 7
Dependent Claim
63 words
The method of claim 4 , said resolving and loading steps further comprising the steps of: for each 6-tuple generated for this filter rule, replacing said operator index with a pointer to a corresponding function; computing a next rule pointer to the next rule based on said next rule tuple element; and replacing said next rule tuple element with said next rule pointer.
Claim 8
Dependent Claim
109 words
The method of claim 5 , said interpreting step comprising the further steps of: obtaining a tuple pointer to a first 6-tuple; while an operator function returns a value of true, calling the operator function of the tuple designated by said tuple pointer, and passing, as the parameters to said operator function, the 6-tuple pointed to by said tuple pointer; responsive to said operator function returning a value of false, setting said tuple pointer to point to the next rule and leaving this while loop; responsive to said operator function returning a value of true, setting said tuple pointer to the next 6 -tuple and continuing this while loop.
Claim 9
Dependent Claim
66 words
The method of claim 6 , wherein the while loop of said interpreting step comprising the further steps of: responsive to the 6-tuple pointed to by said tuple pointer including a journal entry parameter which evaluates as true, generating a journal entry for said IP packet; and returning a result value to said caller selectively for permitting or denying the action requested in said IP packet.
Claim 10
Independent Claim
104 words
A system for filtering IP packets received from a caller at a physical interface to an operating system kernel, comprising: a first compiler function for processing FILTER rule statements entered by a user in a rules file to generate 6-tuple filtering rules, each said 6-tuple filtering rule including an operator index; a second compiler function for resolving relative and symbolic indexes in said 6-tuples filtering rules to form resolved filtering rules and loading said resolved filtering rules to said operating system kernel; and said operating system kernel being operative for interpreting said resolved filtering rules for each IP packet received at said physical interface.
Claim 11
Independent Claim
104 words
A system for filtering IP packets received from a caller at a physical interface to an operating system kernel, comprising: a first compiler function for processing FILTER rule statements entered by a user in a rules file to generate 6-tuple filtering rules, each said 6-tuple filtering rule including an operator index; a second compiler function for resolving relative and symbolic indexes in said 6-tuples filtering rules to form resolved filtering rules and loading said resolved filtering rules to said operating system kernel; and said operating system kernel being operative for interpreting said resolved filtering rules for each IP packet received at said physical interface.
Claim 12
Dependent Claim
110 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for filtering IP packets received from a caller at a physical interface to an operating system kernel, said method steps comprising: processing FILTER rule statements entered by a user in a rules file to generate 6-tuple filtering rules, each said 6-tuple filtering rule including an operator index; resolving relative and symbolic indexes in said 6-tuples filtering rules to form resolved filtering rules and loading said resolved filtering rules to said operating system kernel; and interpreting said resolved filtering rules for each IP packet received at said physical interface.
Claim 13
Dependent Claim
110 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for filtering IP packets received from a caller at a physical interface to an operating system kernel, said method steps comprising: processing FILTER rule statements entered by a user in a rules file to generate 6-tuple filtering rules, each said 6-tuple filtering rule including an operator index; resolving relative and symbolic indexes in said 6-tuples filtering rules to form resolved filtering rules and loading said resolved filtering rules to said operating system kernel; and interpreting said resolved filtering rules for each IP packet received at said physical interface.
Claim 14
Dependent Claim
145 words
An article of manufacture comprising: a computer useable medium having computer readable program code means embodied therein for filtering IP packets received from a caller at a physical interface to an operating system kernel, the computer readable program means in said article of manufacture comprising: computer readable program code means for causing a computer to effect processing FILTER rule statements entered by a user in a rules file to generate 6-tuple filtering rules, each said 6-tuple filtering rule including an operator index; computer readable program code means for causing a computer to effect resolving relative and symbolic indexes in said 6-tuple filtering rules to form resolved filtering rules and loading said resolved filtering rules to said operating system kernel; and computer readable program code means for causing a computer to effect interpreting said resolved filtering rules for each IP packet received at said physical interface.
Claim 15
Dependent Claim
145 words
An article of manufacture comprising: a computer useable medium having computer readable program code means embodied therein for filtering IP packets received from a caller at a physical interface to an operating system kernel, the computer readable program means in said article of manufacture comprising: computer readable program code means for causing a computer to effect processing FILTER rule statements entered by a user in a rules file to generate 6-tuple filtering rules, each said 6-tuple filtering rule including an operator index; computer readable program code means for causing a computer to effect resolving relative and symbolic indexes in said 6-tuple filtering rules to form resolved filtering rules and loading said resolved filtering rules to said operating system kernel; and computer readable program code means for causing a computer to effect interpreting said resolved filtering rules for each IP packet received at said physical interface.
References Cited (Backward Citations)
US5517628A
Cited
US5557798A
Cited
US5634015A
Cited
US5517622A
Cited
US5606668A
Cited
US5701316A
Cited
EP0854621A1
Cited
US6092110A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-01-30 | 2004-07-31 | 2005-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-30 | 2008-07-31 | 2009-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-30 | 2012-07-31 | 2013-01-30 | $7700.00 | Window Closed / Lapsed |