Method and apparatus for pattern matching for intrusion detection/prevention systems
AssigneeAlcatel Lucent
InventorsKedar S. Namjoshi, Girija J. Narlikar
Life of this patent
Estimating the term…
Loading patent…
AssigneeAlcatel Lucent
InventorsKedar S. Namjoshi, Girija J. Narlikar
Estimating the term…
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.
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:
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:
Dependencies are inferred from the claim text.