Rule parser

• US 9,092,471 B2
• Filed: 02/14/2014
• Issued: 07/28/2015
• Est. Priority Date: 12/10/2003
• Status: Expired due to Fees

• Current Assignee: McAfee, LLC
• Original Assignee: McAfee, Inc. (McAfee, LLC)
• Inventors: de la Iglesia, Erik, Deninger, William J.
• Primary Examiner(s): Patel, Chirag R
• Application Number:
  US14/181,521
• Publication Number:
  US 20140164442A1
• Time in Patent Office: 529 Days
• Field of Search: 726 11- 14, 726 22- 26, 709231-233
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/028 by filtering
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212

Abstract

In one embodiment of the present invention, a rule compiler can compress a plurality of rules to be parsed over a block of data into one state table tree structure. In one embodiment of the present invention, rue parsing over the block of data includes selecting a unit of the block of data, indexing into a state table of the state table tree using the selected unit. The state table indexed into can be used for determining whether a decision regarding the block of data can be reached based on the indexed entry, and for selecting a next state table indicated by the indexed entry if the decision regarding the block of data cannot be reached.

Claims

1. A non-transitory machine-readable medium having stored thereon data representing instructions that, when executed by at least one processor, cause the at least one processor to perform operations comprising:

constructing a state table chain for each capture rule of a plurality of capture rules used to determine whether intercepted objects are to be stored;

generating a state table tree using the plurality of state table chains;

intercepting packets being transmitted on a network, the packets associated with a flow that includes a particular intercepted object; and

parsing the plurality of capture rules by traversing the state table tree using a tag that comprises a data structure containing meta-data associated with the particular intercepted object, wherein the particular intercepted object is stored in response to traversing the state table tree using the tag and matching the tag to a capture rule of the plurality of capture rules in the state table tree.

2. The non-transitory machine-readable medium of claim 1, wherein the instructions, when executed by the at least one processor, cause the at least one processor to perform operations comprising:

receiving at least one capture rule of the plurality of capture rules from a user via a user interface.

3. The non-transitory machine-readable medium of claim 1, wherein the generating the state table tree comprises combining the plurality of state table chains to a configured tradeoff level, the tradeoff level indicating a tradeoff between memory usage and editing speed for the state table tree.

4. The non-transitory machine-readable medium of claim 1, wherein the instructions, when executed by the at least one processor, cause the at least one processor to perform operations comprising:

editing the state table tree by re-generating the state table tree in response to receiving an edited version of one of the plurality of capture rules.

5. The non-transitory machine-readable medium of claim 1, wherein the parsing comprises:

selecting a unit of the tag;

indexing into a state table using the selected unit;

determining whether a decision regarding the tag can be reached based on the indexed entry; and

selecting a next state table indicated by the indexed entry if the decision regarding the tag cannot be reached.

6. The non-transitory machine-readable medium of claim 1, wherein the plurality of capture rules are applied to the tag during a single traversal of the state table tree.

7. The non-transitory machine-readable medium of claim 1, wherein the state table tree is a data structure in the form of a tree with nodes, wherein the nodes include state tables indicating a state of the parsing.

8. The non-transitory machine-readable medium of claim 1, wherein the capture rule is associated with storing objects.

9. The non-transitory machine-readable medium of claim 8, wherein the capture rule has precedence over other capture rules of the plurality of capture rules that are matched to the tag when the state table tree is traversed.

10. A capture device, comprising:

a rule compiler configured to generate a state table tree from a plurality of capture rules used to determine whether intercepted objects are to be stored;

a capture module for capturing packets being transmitted on a network, wherein the packets are associated with a flow that includes a particular intercepted object; and

a rule parser configured to parse the plurality of capture rules by traversing the state table tree using a tag that comprises a data structure containing meta-data associated with the particular intercepted object, wherein the particular intercepted object is stored in response to traversing the state table tree using the tag and matching the tag to a capture rule of the plurality of capture rules in the state table tree.

11. The capture device of claim 10, further comprising a capture filter configured to:

receive a decision regarding the tag after the plurality of capture rules are parsed; and

determine whether to store the particular intercepted object based on the decision.

12. The capture device of claim 10, further comprising an object store module to store the particular intercepted object and the tag.

13. The capture device of claim 12, wherein the object store module comprises a canonical content store to store the particular intercepted object and a tag database to store the tag.

14. The capture device of claim 10, further comprising:

a user interface configured to allow a user to edit one or more of the plurality of capture rules, delete one or more of the plurality of capture rules, and insert one or more new capture rules, wherein the rule compiler is configured to edit the state table tree in response to the user editing, deleting, or inserting any capture rule.

15. The capture device of claim 10, wherein the rule compiler is configured to generate the state table tree by constructing a state table chain corresponding to each capture rule and by combining at least a part of each state table chain.

16. A method comprising:

constructing a state table chain for each capture rule of a plurality of capture rules used to determine whether intercepted objects are to be stored;

generating a state table tree using the plurality of state table chains;

intercepting packets being transmitted on a network, the packets associated with a flow that includes a particular intercepted object; and

parsing the plurality of capture rules by traversing the state table tree using a tag that comprises a data structure containing meta-data associated with the particular intercepted object, wherein the particular intercepted object is stored in response to traversing the state table tree using the tag and matching the tag to a capture rule of the plurality of capture rules in the state table tree.

17. The method of claim 16, further comprising:

receiving at least one capture rule of the plurality of capture rules from a user via a user interface.

18. The method of claim 16, wherein the plurality of capture rules are applied to the tag during a single traversal of the state table tree.

19. The method of claim 16, further comprising:

receiving an edited version of one of the plurality of capture rules; and

editing the state table tree without decompiling or recompiling the state table tree if the edited version affects only a leaf node of the state table tree.

20. The method of claim 19, further comprising editing the state table tree by re-generating the state table tree in response to receiving an edited version of one of the plurality of capture rules.

21. An apparatus, comprising:

a rule compiler configured to generate a state table tree from a plurality of capture rules used to determine whether objects are to be stored; and

a rule parser configured to parse the plurality of capture rules to determine whether to store a particular object included in a flow that includes the objects, wherein the flow is associated with packets being transmitted on a network, wherein the rule parser is configured to parse the plurality of capture rules by traversing the state table tree using a tag containing meta-data associated with the particular object, and wherein the particular object is stored in response to traversing the state table tree using the tag and matching the tag to a capture rule of the plurality of capture rules in the state table tree.

22. The apparatus of claim 21, further comprising:

a user interface configured to allow a user to author at least one capture rule of the plurality of capture rules.

23. The apparatus of claim 22, wherein the user interface is configured to allow a user to edit one or more of the plurality of capture rules, delete one or more of the plurality of capture rules, and insert one or more new capture rules, wherein the rule compiler is configured to edit the state table tree in response to the user editing, deleting, or inserting any capture rule.

24. The apparatus of claim 21, wherein the rule compiler is configured to:

translate each capture rule of the plurality of capture rules into a state table chain; and

compress the plurality of state table chains to generate the state table tree.

25. The apparatus of claim 21, wherein the packets are captured by a capture device, and wherein the apparatus and the capture device are separate devices.