# US 2010/0146623 A1 · Method and apparatus for pattern matching for intrusion detection/prevention systems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0146623 A1
- Document ID: US20100146623A1
- Status: Published application
- Kind: A1
- Application number: 12/610,825
- Filed: 2009-11-02
- Published: 2010-06-10
- Earliest claimed: 2008-10-31
- Assignees: Alcatel Lucent
- Inventors: Kedar S. Namjoshi; Girija J. Narlikar
- Web page: https://patentgrep.com/patent/US20100146623A1

## CPC

- H04L 63/1408: {by monitoring network traffic (monitoring network traffic per se H04L43/00)}
- G06F 21/552: {involving long-term monitoring or reporting}
- H04L 63/0263: {Rule management}
- H04L 63/1416: {Event detection, e.g. attack signature detection}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A packet is compared to a pattern defined by a regular expression with back-references (backref-regex) in a single pass of a non-deterministic finite automaton corresponding to the backref-regex (backref-NFA) that includes representations for all backref-regex's back-references. The packet's characters are sequentially selected and analyzed against the backref-NFA until a match or no-match between the packet and pattern is determined. Upon selecting a character, a corresponding configurations-set is updated, where the set includes configurations associated with respective NFA-states of the backref-NFA and indicating whether the selected character is being matched against a back-reference. With the configurations-set being updated the comparison process proceeds along backref-NFA's NFA-states. The updated configurations-set includes configurations associated with NFA-states reachable from the configurations in the pre-updated set. When the configurations-set includes a final state, a match is determined. When the configurations-set becomes empty, or upon selection of all characters lacks the final state, a no-match is determined.

## Claims

### Claim 1

A computer readable medium storing software instructions which, when executed by a processor, cause the processor to perform a method for analyzing packets, the method comprising:
comparing an input string representing a received packet with a pattern defined by a regular expression containing one or more back-references (backref-regex) via a single pass of a non-deterministic finite automation (NFA) corresponding to the backref-regex (backref-NFA) to determine whether the input string matches the pattern, the input string comprising a plurality of characters, wherein the comparing comprising:
selecting sequentially characters of the input string until a determination as to whether the input string matches the pattern is made, wherein:
for each selected character, the comparing further comprises updating a configurations-set associated with the character, the configuration-set comprising one or more configurations, wherein:
the updating is based on the one or more configurations, the character, and the backref-NFA,
each configuration is associated with a particular NFA-state of the backref-NFA and adapted to indicate as to whether a particular back-reference of the backref-NFA is being matched; and
the updated configurations-set is associated with a next selected character when the input string contains an unselected character.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
generating an indicator as to whether the packet matches the pattern.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
comparing the input string with another pattern defined by another backref-regex.

### Claim 4 (depends on 1)

The method of claim 1, wherein when the updated configurations-set is empty a determination that the input string does not match the pattern is made.

### Claim 5 (depends on 1)

The method of claim 1, wherein the comparing further comprises:
after all characters of the input string have been selected, updating the configurations-set to generate a final configuration-set; and
determining whether the final configurations-set contains a configuration associated with a final NFA-state.

### Claim 6 (depends on 5)

The method of claim 5, wherein when the final configurations-set contains the configuration associated with the final state, a determination that the input string matches the pattern is made.

### Claim 7 (depends on 5)

The method of claim 5, wherein when the final configurations-set lacks the configuration associated with the final state a determination that the input string does not match the pattern is made.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
prior to the selecting, initializing the configurations-set.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
constructing backref-NFA based on the backref-regex.

### Claim 10 (depends on 1)

The method of claim 1, wherein updating the configurations-set for the selected character comprises building a new configurations-set by adding new configurations based on the current configurations-set and the selected character.

### Claim 11 (depends on 10)

The method of claim 10, wherein the new configuration is one of:
a configuration reachable by consuming the selected character from at least one of the one or more configurations in the configurations-set; and
a configuration reachable without consuming the selected character from at least one of the one or more configurations in the configurations-set.

### Claim 12 (depends on 1)

The method of claim 1, wherein the updating of the configurations-set for the selected character comprises:
if at least one configuration is reachable without consuming the selected character, based on the backref-NFA, from the one or more configurations of the configurations-set, adding to the configurations-set all configurations reachable without consuming the selected character, based on the backref-NFA, from each configuration in the configurations-set.

### Claim 13 (depends on 12)

The method of claim 12, wherein the updating further comprises:
determining all configurations reachable by consuming the selected character based on the backref-NFA from each configuration in the configurations-set to generate the updated configurations-set.

### Claim 14 (depends on 1)

The method of claim 1, wherein each configuration comprises:
the NFA-state with which the configuration is associated;
one or more bracket indicators for identifying a sub-string of the input string that has been compared to a particular bracket;
a match indicator for identifying whether is a particular bracket of the backref-NFA is being matched.

### Claim 15 (depends on 1)

The method of claim 1, further comprising reducing configuration-set size by removing from the from configurations-sets those back-reference entries that are not alive.

### Claim 16

A computer readable medium storing software instructions which, when executed by a processor, cause the processor to perform a method for estimating worst-case time complexity of a regular expression comprising one or more back-references (backref-regex), the method comprising:
constructing a non-deterministic finite automaton (NFA) corresponding to the backref-regex (backref-NFA), the backref-NFA comprising:
a plurality of NFA-states; and
a respectively labeled edge for each of the one or more back-references of the backref-regex;
performing liveness analysis on the backref-NFA to determine for each NFA-state of the backref-NFA a set of back-references alive at the NFA-state; and
determining a maximum number of alive back-references over the plurality of NFA-states, wherein the determined maximum number is indicative of the worst-case time complexity of the backref-regex.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
determining a value of the worst-case time complexity of the backref-regex based on the maximum number; and
providing the determined time-complexity value.

### Claim 18 (depends on 17)

The method of claim 17, wherein the backref-NFA further comprises:
for each pair of brackets in the backref-regex, a corresponding pair of edges labeled to identify respectively a beginning and an ending bracket, the edges extending from a sub-backref-NFA corresponding to a sub-backref regex embedded inside the pair of brackets.

### Claim 19 (depends on 18)

The method of claim 18, where the edges of the backref-NFA corresponding to the brackets of the backref-regex represent epsilon transitions.

### Claim 20 (depends on 17)

The method of claim 17, wherein the constructing of the backref-NFA comprises:
for each sub-backref-regex embedded in a pair of matching brackets, constructing:
a corresponding sub-backref-NFA;
additional edges on both sides of the sub-backref-NFA, the additional edges respectively labeled to identify an opening bracket and a closing bracket of the pair of matching brackets; and
for each back-reference, constructing an additional edge labeled to indicate the back-reference.

### Claim 21 (depends on 16)

The method of claim 16, further comprising:
comparing a value of the worst-case time complexity determined based on the maximum number to a pre-defined threshold; and
upon determining that the value is above the pre-defined threshold, flagging the pattern as potentially bad pattern.

### Claim 22 (depends on 16)

The method of claim 16, further comprising removing from said backref-NFA those NFA-state entries that refer to back-references that are not alive.
