Hardware acceleration architecture for signature matching applications for deep packet inspection

Patent metadata

Field	Value
Publication number	US-10091074-B2
Application number	US-201615199210-A
Country	US
Kind code	B2
Filing date	Jun 30, 2016
Priority date	Jun 30, 2016
Publication date	Oct 2, 2018
Grant date	Oct 2, 2018

Abstract

A signature matching hardware accelerator system comprising one or more hardware accelerator circuits, wherein each of the hardware accelerator circuit utilizes a compressed deterministic finite automata (DFA) comprising a state table representing a database of digital signatures defined by a plurality of states and a plurality of characters, wherein the plurality of states are divided into groups, each group comprising a leader state having a plurality of leader state transitions and one or more member states, each having a plurality of member state transitions is disclosed. The hardware accelerator circuit comprises a memory circuit configured to store the leader state transitions within each group of the compressed DFA, only the member state transitions that are different from the leader state transitions for a respective character within each group of the compressed DFA and a plurality of member transition bitmasks associated respectively with the plurality of member state transitions.

First claim

The invention claimed is:

1. A hardware accelerator system for signature matching in a distributed network system comprising one or more hardware accelerator circuits, wherein each of the hardware accelerator circuit utilizes a compressed deterministic finite automata (DFA) comprising a state table representing a database of digital signatures defined by a plurality of states and a plurality of characters, wherein the plurality of states are divided into groups, each group comprising a leader state having a plurality of leader state transitions and one or more member states, each having a plurality of member state transitions, the one or more hardware accelerators comprising:
a memory circuit configured to store,
the leader state transitions within each group of the compressed DFA;
only the member state transitions that are different from the leader state transitions for a respective character within each group of the compressed DFA; and
member transition bitmasks associated respectively with the one or more member states, wherein each of the member transition bitmasks comprises a plurality of bitmasks that identify the member state transitions within the respective member state that are different from the leader state transitions for a respective character within each group of the compressed DFA.

2. The system of claim 1 , wherein the one or more hardware accelerator circuits further comprises a processing circuit configured to fetch a next state transition from the leader state transitions or the member state transitions in the memory circuit, based on the information of a current state, a current input character and, when the current state is a member state, the member transition bitmask.

3. The system of claim 2 , wherein the processing circuit is further configured to receive the current state and the current input character prior to fetching the next state transition.

4. system of claim 2 , wherein the current state is defined by a group ID that identifies the group in the compressed DFA to which the current state belongs and a member ID that identifies if the current state is a leader state or a member state.

5. The system of claim 2 , wherein the memory circuit comprises a leader transition table configured to store the leader transitions within each group of the compressed DFA and a member transition table configured to store the member state transitions that are different from the leader state transitions for a respective character within each group of the compressed DFA.

6. The system of claim 5 , wherein the memory circuit further comprises a member bitmask table configured to store the plurality of member transition bitmasks associated with the one or more member states within each group and a previous transition count that indicates a count of the member state transitions that are different from the corresponding leader state transitions, before the respective member state in each group.

7. The system of claim 6 , wherein the memory circuit further comprises an address mapping table configured to store,
a leader transition base address of each group within the leader transition table;
a member transition base address of each group within the member transition table;
member transition bitmask and previous transition count base address of each group within the member bitmask table; and
an overall bitmap of each group.

8. The system of claim 7 , wherein the processing circuit is configured to fetch the next state transition from the leader transition table,
when the current state is a leader state, or
when the current state is a member state and the member transition bitmask from the member bitmask table for the respective member state indicates that a member state transition of the respective member state and a leader state transition for the current input character are the same.

9. The system of claim 8 , wherein the processing circuit is further configured to determine a leader transition address that indicates the address of the next state transition in the leader state table based on the leader transition base address and the overall bitmap from the address mapping table, prior to fetching the next state transition from the leader transition table.

10. The system of claim 7 , wherein the processing circuit is configured to fetch the next state transition from the member transition table, when the current state is a member state and the member transition bitmask from the member bitmask table for the respective member state indicates that a member state transition of the respective member state and a leader state transition for the current input character are different.

11. The system of claim 10 , wherein the processing circuit is further configured to determine a member transition address that indicates the address of the next state transition in the member state table based on the member transition base address and the previous transition count from the address mapping table, and a count of the bitmasks of member state transitions that are different from the corresponding leader state transitions for the current state before the current input character, prior to fetching the next state transition from the member transition table.

12. The system of claim 1 , wherein the DFA associated with the one or more hardware accelerator circuits are the same.

13. The system of claim 1 , wherein the DFA associated with the one or more hardware accelerator circuits is different.

14. The system of claim 13 , wherein a plurality of signatures associated with an application is split between the DFA associated with the one or more hardware accelerator circuits.

15. The system of claim 1 , wherein the one or more hardware accelerators are selectively activated based on the system requirements.

16. A method for compression of a deterministic finite automata (DFA) comprising a state table representing a database of digital signatures defined by a plurality of states and a plurality of characters, each of the plurality of states having a plurality of next state transitions associated therewith, in a processing circuit, comprising:
grouping the plurality of states into one or more groups based on an overall bitmap of the respective states, each group comprising a leader state having a plurality of leader state transitions and one or more member states, each having a plurality of member state transitions; and
assigning member transition bitmasks respectively to the one or more member states within each group, wherein the member transition bitmasks comprises a plurality of bitmasks that identify the member state transitions within the respective member state that are different from the leader state transitions for a respective character.

17. The method of claim 16 , further comprising storing the leader state transitions, the member state transitions that are different from the leader state transitions for the respective character and the plurality of member transition bitmasks in a memory circuit.

18. The method of claim 17 , further comprising assigning a plurality of bitmaps respectively to the plurality of state transitions within each of the plurality of states of the DFA, forming the overall bitmap for each of the plurality of states, prior to grouping the plurality of states.

19. The method of claim 18 , wherein grouping the plurality of states comprises dividing the plurality of states into one or more groups, wherein each of the plurality of states within each group have the same overall bitmap.

20. The method of c

Assignees

• Intel Corp

Inventors

• Lin Pinxing
• Subramanian Shiva Shankar

Classifications

• G06F17/30867

  Physics · mapped topic

• H04L63/1408

  by monitoring network traffic (monitoring network traffic per se H04L43/00) · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title

• H04L43/028 Primary

  by filtering · CPC title

• H04L63/1416 Primary

  Event detection, e.g. attack signature detection · CPC title