Reduction and acceleration of a deterministic finite automaton

Patent metadata

Field	Value
Publication number	US-11968178-B2
Application number	US-202217741158-A
Country	US
Kind code	B2
Filing date	May 10, 2022
Priority date	Apr 28, 2016
Publication date	Apr 23, 2024
Grant date	Apr 23, 2024

Abstract

Techniques for reduction and acceleration of a deterministic finite automaton (DFA) are disclosed. In some embodiments, a system, process, and/or computer program product for reduction and acceleration of a DFA includes receiving an input value; performing a reduced deterministic finite automaton lookup using a lookup key, wherein the lookup key comprises a current state and the input value; and determining a next state based on the lookup key.

First claim

What is claimed is:

1. A system, comprising:
a processor configured to:
receive an input value;
receive an update that includes updated versions of a bitmap table, a default state table, and a rule table from a cloud security service, wherein the updated versions of the bitmap table, the default state table, and the rule table are stored;
determine a next state based on a lookup key by performing a lookup in the updated bitmap table using the lookup key to determine whether to obtain the next state from the updated default state table or the updated rule table, wherein the lookup key comprises a current state and the input value, and wherein the determining of the next state comprises to:
determine whether the updated bitmap table returns a default state or a valid state using the lookup key, the default state corresponding to a most commonly occurring next-state pointer, the default state being different from the valid state; and
in response to a determination that the updated bitmap table returns the default state, determine that the next state is to be obtained from the updated default state table; and

determine the next state based on the lookup key, comprising to:
in response to a determination that the next state is to be obtained from the updated default state table, obtain the next state from the updated default state table based on the lookup key; and

a memory coupled to the processor and configured to provide the processor with instructions.

2. The system recited in claim 1 , wherein a deterministic finite automaton is reduced using the updated bitmap table, the updated rule table, and the updated default state table.

3. The system recited in claim 1 , wherein a deterministic finite automaton is reduced using the updated bitmap table, the updated rule table, and the updated default state table that are stored using on-chip memory of the processor.

4. A method, comprising:
receiving, using a processor, an input value;
receiving an update that includes updated versions of the bitmap table, the default state table, and the rule table from a cloud security service, wherein the updated versions of the bitmap table, the default state table, and the rule table are stored;
determining, using the processor, a next state based on a lookup key by performing a lookup in the updated bitmap table using the lookup key to determine whether to obtain the next state from the updated default state table or the updated rule table, wherein the lookup key comprises a current state and the input value, and wherein the determining of the next state comprises:
determining whether the updated bitmap table returns a default state or a valid state using the lookup key, the default state corresponding to a most commonly occurring next-state pointer, the default state being different from the valid state; and
in response to a determination that the updated bitmap table returns the default state, determining that the next state is to be obtained from the updated default state table; and

determining the next state based on the lookup key, comprising to:
in response to a determination that the next state is to be obtained from the updated default state table, obtaining the next state from the updated default state table based on the lookup key.

5. The method of claim 4 , wherein a deterministic finite automaton is reduced using the updated bitmap table, the updated rule table, and the updated default state table.

6. The method of claim 4 , wherein a deterministic finite automaton is reduced using the updated bitmap table, the updated rule table, and the updated default state table that are stored using on-chip memory of the processor.

7. A tangible non-transitory computer readable storage medium and comprising computer instructions for:
receiving an input value;
receiving an update that includes updated versions of the bitmap table, the default state table, and the rule table from a cloud security service, wherein the updated versions of the bitmap table, the default state table, and the rule table are stored;
determining a next state based on a lookup key by performing a lookup in the updated bitmap table using the lookup key to determine whether to obtain the next state from the updated default state table or the updated rule table, wherein the lookup key comprises a current state and the input value, and wherein the determining of the next state comprises:
determining whether the updated bitmap table returns a default state or a valid state using the lookup key, the default state corresponding to a most commonly occurring next-state pointer, the default state being different from the valid state; and
in response to a determination that the updated bitmap table returns the default state, determining that the next state is to be obtained from the updated default state table; and

determining the next state based on the lookup key, comprising to:
in response to a determination that the next state is to be obtained from the updated default state table, obtaining the next state from the updated default state table based on the lookup key.

8. The tangible non-transitory computer readable storage medium recited in claim 7 , wherein a deterministic finite automaton is reduced using the updated bitmap table, the updated rule table, and the updated default state table.

Assignees

• Palo Alto Networks Inc

Inventors

• Ganesh Subramani
• Li Sidong
• Chang Lei

Classifications

• H04L63/0263 Primary

  Rule management · CPC title

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F16/2282

  Tablespace storage structures; Management thereof · CPC title

• G06F16/90344

  by using string matching techniques · CPC title

• H04L63/06

  for supporting key management in a packet data network (cryptographic mechanisms or cryptographic arrangements for key management H04L9/08) · CPC title