US 2018/0006906 A1 · LEADER STATE TRANSITION COMPRESSION MECHANISM TO EFFICIENTLY COMPRESS DFA BASED REGULAR EXPRESSION SIGNATURES

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 a single occurrence of a most repeated leader state transition within each group, the unique leader state transitions comprising the leader state transitions that are different from the most repeated leader state transition within the respective group; and leader transition bitmasks associated respectively with the leader states within each group.

Claims25

Dependent claims

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,
a single occurrence of a most repeated leader state transition from the plurality of leader state transitions and the leader state transitions that are unique, within each group of the compressed DFA, wherein the unique leader state transitions comprises the leader state transitions that are different from the most repeated leader state transition within the respective group;
and
leader transition bitmasks associated respectively with the leader states within each group, wherein each of the leader transition bitmasks comprises a plurality of leader bitmasks that identify the unique leader state transitions from the plurality of leader state transitions with each group.

1 more element

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 a 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 a leader transition bitmask to the leader state within each group, wherein the leader transition bitmask comprises a plurality of leader bitmasks that identify the unique leader state transitions wherein the unique leader state transitions comprises the leader state transitions that are different from a most repeated leader state transition within the respective group.

A method for fetching a next state transition from a compressed deterministic finite automata (DFA) using a processing circuit in a hardware accelerator circuit of signature matching hardware accelerator system, wherein the DFA comprises 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 and wherein each of the leader state is associated with a leader transition bitmask comprising a plurality of leader bitmasks that identify unique leader state transitions comprising the leader state transitions that are different from a most repeated leader state transition within the leader state and wherein each of the member state is associated with a member transition bitmask comprising a plurality of member bitmasks that identify unique member state transitions comprising the member state transitions within the respective member state that are different from the leader state transitions for the respective character, comprising:

receiving information on a current state and a current input character that defines an incoming data;
fetching the next state transition for the current state selectively from an address mapping table comprising the most repeated state transition of the leader state, or a transition table comprising the unique leader state transitions and the unique member state transitions, within a memory circuit of the hardware accelerator circuit, based on the leader transition bitmask, when the current state is a leader state;
and
fetching the next state transition for the current state selectively from the address mapping table or the transition table, based on the respective member transition bitmask, and when the member transition bitmask indicates a member state transition that is not unique, the leader transition bitmask, when the current state is a member state.

1 more element

Dependencies are inferred from the claim text.

Leader state transition compression mechanism to efficiently compress dfa based regular expression signatures

Life of this patent

Leader state transition compression mechanism to efficiently compress dfa based regular expression signatures

Life of this patent

Abstract

Claims25