Patent ID: 8683590

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