Rule parser

• US 8,656,039 B2
• Filed: 06/08/2004
• Issued: 02/18/2014
• Est. Priority Date: 12/10/2003
• Status: Active Grant

• Current Assignee: McAfee, LLC
• Original Assignee: McAfee, Inc. (McAfee, LLC)
• Inventors: de la Iglesia, Erik, Deninger, William
• Primary Examiner(s): Patel, Chirag R
• Application Number:
  US10/864,153
• Publication Number:
  US 20050132034A1
• Time in Patent Office: 3,542 Days
• Field of Search: 709231-233, 726 11- 14, 726 22- 26
• US Class Current: 709/231
• 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 method comprising:

receiving a plurality of capture rules used to determine whether intercepted objects are to be stored;

for each received rule, constructing a state table chain configured to parse a tag for the rule;

generating a state table tree using the plurality of state table chains, the state table tree being configured to parse the tag for the plurality of capture rules; and

intercepting packets being transmitted on a network, the packets associated with a document that includes the intercepted objects, wherein the document is captured based on a particular capture rule associated with the intercepted objects, and wherein the tag comprises a data structure containing meta-data associated with a particular intercepted object, and wherein the document is stored in response to traversing the state table tree to parse the tag and match the tag to the particular capture rule.

2. The method of claim 1, wherein receiving the plurality of capture rules comprises a user inputting at least one of the plurality of capture rules via a user interface.

3. The method of claim 1, wherein 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 method of claim 1, further comprising receiving an edited version of one of the plurality of capture rules, and re-generating the state table tree in response to the received edited version.

5. A method of rule parsing over a block of data comprising:

selecting a unit of the block of data;

indexing into a state table using the selected unit;

determining whether a decision regarding the block of data can be reached based on the indexed entry;

selecting a next state table indicated by the indexed entry if the decision regarding the block of data cannot be reached, wherein the block of data comprises a tag and each unit of the tag comprises a byte; and

intercepting packets being transmitted on a network, the packets associated with a document that includes intercepted objects, wherein the document is captured based on a particular capture rule associated with the intercepted objects, and wherein the tag comprises a data structure containing meta-data associated with a particular intercepted object, and wherein the document is stored in response to traversing the state table to parse the tag and match the tag to the particular capture rule.

6. The method of claim 5, further comprising selecting a next unit of the block of data if the decision regarding the block of data cannot be reached.

7. The method of claim 6, further comprising iteratively repeating indexing into the next state table using the next unit, determining whether the decision regarding the block of data can be reached based on the indexed entry, and selecting another next state table indicated by the indexed entry if the decision regarding the block of data cannot be reached, until the decision regarding the block of data is reached.

8. The method of claim 6, wherein selecting the next unit the block of data is based on a forward/reverse operator indicated by the indexed entry.

9. The method of claim 5, wherein the block of data comprises a tag and each unit of the tag comprises a byte.

10. A capture device comprising:

a user interface to enable a user to author a plurality of capture rules;

a rule compiler to generate a state table tree, wherein a single traversal of the state table tree applies all of the plurality of capture rules to a tag containing meta-data over an intercepted object; and

a rule parser to parse the capture rules by traversing the state table tree using the tag, the capture device being configured to intercept packets being transmitted on a network, the packets associated with a document that includes the intercepted objects, wherein the document is captured based on a particular capture rule associated with the intercepted objects, and wherein the tag comprises a data structure containing meta-data associated with a particular intercepted object, and wherein the document is stored in response to traversing the state table tree to parse the tag and match the tag to the particular capture rule.

11. The capture device of claim 10, further comprising a capture filter to determine whether to store the intercepted object based on the decision, wherein the decision comprises a determination of one of the plurality of capture rules being hit by the tag.

12. The capture device of claim 11, further comprising an object store module to store the 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 intercepted object and a tag database to store the tag.

14. The capture device of claim 10, further comprising an object capture and classification module to populate the tag by reconstructing and classifying the captured object.

15. The capture device of claim 10, wherein the user interface is configured to allow a user to edit the plurality of capture rules, delete one of the plurality of capture rules, and insert a new capture rule, and the rule compiler is configured to re-generate the state table tree in response to the user editing, deleting, or inserting a capture rule.

16. 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 generating the state table tree by combining at least a part of each state table chain.

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

receiving a plurality of capture rules used to determine whether intercepted objects are to be stored;

for each received rule, constructing a state table chain configured to parse a tag for the rule;

generating a state table tree using the plurality of state table chains, the state table tree being configured to parse the tag for the plurality of capture rules; and

intercepting packets being transmitted on a network, the packets associated with a document that includes the intercepted objects, wherein the document is captured based on a particular capture rule associated with the intercepted objects, and wherein the tag comprises a data structure containing meta-data associated with a particular intercepted object, and wherein the document is stored in response to traversing the state table tree to parse the tag and match the tag to the particular capture rule.

18. The non-transitory machine-readable medium of claim 17, wherein receiving the plurality of capture rules comprises a user inputting at least one of the plurality of capture rules via a user interface.

19. The non-transitory machine-readable medium of claim 17, wherein 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.

20. The non-transitory machine-readable medium of claim 17, further comprising receiving an edited version of one of the plurality of capture rules, and re-generating the state table tree in response to the received edited version.

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

selecting a unit of a block of data;

indexing into a state table using the selected unit;

determining whether a decision regarding the block of data can be reached based on the indexed entry;

selecting a next state table indicated by the indexed entry if the decision regarding the block of data cannot be reached, wherein the block of data comprises a tag and each unit of the tag comprises a byte; and

intercepting packets being transmitted on a network, the packets associated with a document that includes intercepted objects, wherein the document is captured based on a particular capture rule associated with the intercepted objects, and wherein the tag comprises a data structure containing meta-data associated with a particular intercepted object, and wherein the document is stored in response to traversing the state table to parse the tag and match the tag to the particular capture rule.

22. The non-transitory machine-readable medium of claim 21, wherein the instructions further cause the processor to select a next unit of the block of data if the decision regarding the block of data cannot be reached.

23. The non-transitory machine-readable medium of claim 22, wherein the instructions further cause the processor to iteratively repeat indexing into the next state table using the next unit, determining whether the decision regarding the block of data can be reached based

on the indexed entry, and selecting another next state table indicated by the indexed entry if the decision regarding the block of data cannot be reached, until the decision regarding the block of data is reached.

24. The non-transitory machine-readable medium of claim 22, wherein selecting the next unit the block of data is based on a forward/reverse operator indicated by the indexed entry.