US 8,015,208 B2Granted

Systems and methods for processing regular expressions

AssigneeLSI Corporation

InventorRobert J. McMillen

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for reducing the size of a DFA associated with a regular expression separates the functions of locating subexpressions within the DFA and determining if the located subexpressions satisfy a regular expression. For example, the functions of (1) locating subexpressions in a range asserting expression and, (2) determining whether the subexpressions satisfy the range of the range asserting expression are partitioned. In one embodiment, a first component may locate the subexpressions in a data stream using one or more DFAs, while a second component determines if the located subexpressions satisfy the range. In this embodiment, because the DFAs are not configured to determine a relationship between subexpressions, such as a range between subexpressions, the size of the resultant DFA may be significantly reduced.

Claims20

Dependent claims

A system for analyzing a data stream in order to match at least a portion of the data stream with a regular expression comprising at least a first subexpression and a second subexpression, the system comprising:

a storage device storing a state machine comprising a first terminal state indicative of locating a first subexpression and a second terminal state indicative of locating a second subexpression, wherein a regular expression comprises each of the first and second subexpressions and defines a required relationship between the first and second subexpressions, wherein the storage device further stores a template comprising relationship information indicating the required relationship between the first and second subexpressions, as indicated in the regular expression;
a processing engine configured to receive a data stream and apply the state machine to the data stream, wherein upon reaching the first or second terminal state the processing engine initiates recordation of tokens comprising information regarding the respective first or second subexpressions;
and
a post processing module configured to access the recorded tokens and the stored template, wherein the post processing module determines if the information of the recorded tokens matches the relationship information indicated in the template, wherein matching of the recorded tokens to the relationship information indicates location of the regular expression including both of the first and second subexpressions in the data stream.

1 more element

A computerized method for analyzing a data stream in order to match at least a portion of the data stream with a regular expression comprising at least a first subexpression and a second subexpression, the computerized method configured for execution by a computing device having one or more processors and one or more storage devices, the system comprising:

storing on a storage device a state machine comprising a first terminal state indicative of locating a first subexpression and a second terminal state indicative of locating the second subexpression;
storing on a storage device a template comprising relationship information regarding the first and second subexpressions as indicated in a regular expression;
receiving a data stream;
applying the state machine to the data stream;
in response to reaching the first terminal state of, initiating recordation of a first token indicative of at least a first location of data in the data stream matching the first subexpression;
in response to reaching the second terminal state of, initiating recordation of a second token indicative of at least a second location of data in the data stream matching the second subexpression;
in response to determining that the information of the recorded tokens matches the relationship information indicated in the template, providing an indication a match of the regular expression, including both the first and second subexpressions, in the data stream.

4 more elements

A computer readable medium having software code stored thereon, the software code configured for execution by a computing device having one or more processors, wherein, if executed, the software code causes the computing device to perform a method of analyzing a data stream in order to match at least a portion of the data stream with a regular expression comprising at least a first subexpression and a second subexpression, the method comprising:

accessing a state machine comprising a first terminal state associated with locating a first subexpression and a second terminal state associated with locating a second subexpression;
applying the state machine to a data stream;
in response to reaching the first terminal state, initiating recordation of a first token indicative of at least a first location of data in the data stream matching the first subexpression;
in response to reaching the second terminal state, initiating recordation of a second token indicative of at least a second location of data in the data stream matching the second subexpression;
comparing information of the first and second tokens to relationship information regarding the first and second subexpressions, wherein the relationship information indicates a required relationship between data matching the first and second subexpressions in the data stream, in order to determine whether a regular expression including the first and second subexpressions is matched in the data stream.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 12/402,447Filed 11 Mar 2009 · division
Priority: 5 Jun 2006
Published: US 2009/0172001 A12 Jul 2009
Granted: 6 Sep 2011
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

H04L 63/145
Countermeasures against malicious traffic: the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
Y10S 707/99942
Database schema or data structure: manipulating data structure, e.g. compression, compaction, compilation
Y10S 707/99943
Database schema or data structure: generating database or data structure, e.g. via user interface
Y10S 707/99944
Database schema or data structure: object-oriented database structure

Family

Application11/422,312Parent of this division · filed 5 Jun 2006
US 2009/0172001 A1Pre-grant publication · published 2 Jul 2009
US 7,512,634 B2Parent of this division
US 2007/0282833 A1Published application
US 8,015,208 B2This patent

From the US filing history. Foreign family members aren’t listed.