Rule parser

• US 20050132034A1
• Filed: 06/08/2004
• Published: 06/16/2005
• Est. Priority Date: 12/10/2003
• Status: Active Grant

• Current Assignee: McAfee, LLC
• Original Assignee: McAfee, Inc. (McAfee, LLC)
• Inventors: Deninger, William, Iglesia, Erik de la
• Granted Patent: US 8,656,039 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• 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; and

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.

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 the tag comprises a data structure containing meta-data associated with an intercepted object.

4. The method of claim 3, further comprising capturing the intercepted object by traversing the state table tree to parse the tag.

5. 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.

6. 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.

7. 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; and

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

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

9. The method of claim 8, 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.

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

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

12. A method for filtering a tag by parsing a plurality of filter rules over the tag, the method comprising:

i) selecting initial state table of a state table tree;

ii) selecting a first byte of the tag;

iii) indexing an entry of the selected state table using the selected byte;

iv) determining whether the indexed entry indicated a decision;

v) if the indexed entry does not indicate a decision, then selecting a next state table of the state table tree and a next byte of the tag using the indexed entry, and continuing from processing block iii) until the decision is indicated.

13. 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 reach a capture by traversing the state table tree using the tag.

14. The capture device of claim 13, 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.

15. The capture device of claim 14, further comprising an object store module to store the intercepted object and the tag.

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

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

18. The capture device of claim 13, 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.

19. The capture device of claim 13, 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.

20. A 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; and

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.

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

22. The machine-readable medium of claim 20, wherein the tag comprises a data structure containing meta-data associated with an intercepted object.

23. The machine-readable medium of claim 22, wherein the instruction further cause the processor to capture the intercepted object by traversing the state table tree to parse the tag.

24. The machine-readable medium of claim 20, 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.

25. The machine-readable medium of claim 20, 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.

26. A 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; and

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

27. The machine-readable medium of claim 26, 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.

28. The machine-readable medium of claim 27, 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.

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

30. The machine-readable medium of claim 26, wherein the block of data comprises a tag and each unit of the tag comprises a byte.