STATE MACHINE COMPRESSION

• US 20080270764A1
• Filed: 04/30/2008
• Published: 10/30/2008
• Est. Priority Date: 04/30/2007
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Ruehle, Michael D., McMillen, Robert James
• Granted Patent: US 7,788,206 B2
• Time in Patent Office: Days
• US Class Current: 712/220
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

Compressing state transition instructions may achieve a reduction in the binary instruction footprint of a state machine. In certain embodiments, the compressed state transition instructions are used by state machine engines that use one or more caches in order to increase the speed at which the state machine engine can execute a state machine. In addition to reducing the instruction footprint, the use of compressed state transition instructions as discussed herein may also increase the cache hit rate of a cache-based state machine engine, resulting in an increase in performance.

Claims

1. A method of evaluating a state machine with respect to a data string, wherein the state machine comprises a plurality of state transition instruction that are associated with transitions from respective states, the method comprising:

storing at least some of the state transition instructions in a first memory;

determining if a state transition instruction associated with a currently active state of the state machine comprises a multi-character state transition instruction;

in response to determining that the state transition instruction associated with the currently active state comprises a multi-character state transition instruction,

determining a quantity P of transition conditions indicated in the multi-character state transition instruction, where P is greater than or equal to 2;

determining the transition conditions indicated in the multi-character state transition instruction; and

determining if the next P characters of the data string match the P transition conditions indicated in the multi-character state transition instruction.

2. The method of claim 1, further comprising:

in response to determining that the state transition instruction associated with the currently active state does not comprise a multi-character state transition instruction, determining if the next one character of the data string matches a single transition condition indicated in the state transition instruction.

3. The method of claim 1, wherein the transition conditions each comprise an indication of a character or a character class.

4. The method of claim 1, wherein the data string comprises data transmitted across at least the Internet and received at a network node.

5. The method of claim 1, wherein the state machine is configured to match one or more anti-virus signatures.

6. An apparatus for evaluating a state machine with reference to a data string comprising a plurality of characters, the apparatus comprising:

a memory configured to store at least some of a plurality of state transition instructions associated with respective states of the state machine;

an interface for receiving characters of the data string; and

a processor for selectively accessing memory locations of the memory in response to respective characters of the data string, wherein the processor is further configured to determine if a particular state transition instruction stored in the memory comprises transition conditions associated with transitions between 2 or more sequential states of a linear path of the state machine.

7. The apparatus of claim 6, wherein the processor is further configured to determine transition characters associated with the 2 or more sequential states and to compare the transition characters with next characters of the data string in order to determine if a next state transition instruction associated with the state transition instruction should be next accessed by the processor.

8. The apparatus of claim 6, wherein the transition conditions each comprise an indication of a character or a character class.

9. The apparatus of claim 6, wherein the apparatus comprises one or more of a network interface card, an application specific integrated circuit, a field programmable gate array, a multi-chip module, and a reconfigurable logic circuit.

10. The apparatus of claim 6, wherein the apparatus is configured to interface with a network server.

11. A method of generating a compressed state machine representative of a plurality of regular expressions that are associated with data strings, the method comprising:

determining state transition instructions associated with respective states of the state machine, wherein at least some of the state transition instructions indicate at least one respective transition character and at least one next state transition instruction,

wherein at least one of the state transition instructions indicates two or more sequential characters of an input data stream that must be received by the state machine engine in order to initiate transition to an indicated next state transition instruction.

12. The method of claim 11, wherein the two or more sequential characters comprise characters of at least one of the data strings.

13. The method of claim 11, wherein a first of the state transition instructions indicates a first quantity of characters of the data string that must be received by the state machine engine in order to transition to a second of the state transition instructions and the second state transition instruction indicates a second quantity of characters of the data string that must be received by the state machine engine in order to transition to a third of the state transition instructions.

14. The method of claim 13, wherein the first quantity is equal to a maximum quantity of characters associated with respective state transition instructions and the second quantity is less than or equal to the maximum quantity.

15. The method of claim 14, wherein the maximum quantity is selected from the group comprising 2, 3, 4, 5, 6, 7, 8, 10, 16, 24, 32, 64, and 128.

16. The method of claim 13, wherein the first state transition instruction is configured to indicate a quantity of state transition instructions for pre-fetching in the cache memory in response to activation of the first state transition instruction by the state machine engine.

17. The method of claim 13, wherein the first state transition instruction indicates a quantity of state transition instructions associated with states following the first state transition instruction that each indicate two or more sequential characters of the input data stream that must be received by the state machine engine in order to initiate transition to respectively indicated next states.

18. The method of claim 17, further comprising prefetching from a first memory at least some of the quantity of state transition instructions

19. The method of claim 11, further comprising:

determining one or more instructions of the state machine for caching in a cache memory of a state machine engine, wherein the state machine engine comprises the cache memory and at least one main memory, wherein access times of the cache memory are lower than access times of the at least one main memory.

20. The method of claim 11, wherein each of the two or more sequential characters comprise an indication of a character or a character class.