Generating a tunable finite automaton for regular expression matching
US8943063B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 10, 2012 |
| Grant date | Jan 27, 2015 |
| Priority date | — |
| Expiry date | Mar 1, 2033 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L43/028
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Deterministic Finite Automatons (DFAs) and Nondeterministic Finite Automatons (NFAs) are two typical automatons used in the Network Intrusion Detection System (NIDS). Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. A new automaton representation of regular expressions, called Tunable Finite Automaton (TFA), is described. TFAs resolve the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. A TFA can achieve significan…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.