Regular expression matching using tcams for network intrusion detection
AssigneeBoard of Trustees of Michigan State University
InventorsXiang-Yang A. Liu, Chad R. Meiners, Eric Torng
Life of this patent
Estimating the term…
Abstract
A method is provided for implementing regular expression matching using ternary content-addressable memory devices. The method includes: receiving a set of regular expressions (REs) that specify data elements to be extracted from data packets; constructing a deterministic finite automaton (DFA) from the set of regular expressions; building a state transition table for each node of the deterministic finite automaton; combining the state transition tables into a single lookup table; and instantiating the lookup table in a ternary content-addressable memory device. Additional techniques are provided to reduce the TCAM space and improve RE matching speed.
Claims17
A computer-implemented method for implementing regular expression matching using ternary content-addressable memory devices, comprising:
- receiving a set of regular expressions that specify characters to be extracted from data packets;
- constructing a deterministic finite automaton from the set of regular expressions;
- building a state transition table for each node of the deterministic finite automaton, the table having an input field having a fixed number of bits for encoding characters to be extracted from data packets;
- combining the state transition tables into a single lookup table;
- instantiating the lookup table in a ternary content-addressable memory device.
A method for encoding identifiers for source states in a state transition table, comprising:
- constructing a space reduction graph from the deterministic finite automaton, where vertices of the graph represent a distinct state of the automaton and weight assigned to each edge of the graph is a number of common transitions between two connected states;
- trimming away edges in the graph having a weight below a predefined threshold;
- computing a deferment forest by finding a maximum weight spanning forest for the space reduction graph;
- assigning identifiers for source states and destination states for states of the deferment forest.
Dependencies are inferred from the claim text.