Method and apparatus for pattern matching for intrusion detection/prevention systems
View Patent ↗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.
1. 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.
2. The medium of claim 1 , wherein the method further comprises:
comparing the input string with another pattern defined by another backref-regex.
3. The medium of claim 1 , wherein the method further comprises:
constructing backref-NFA based on the backref-regex.
4. The medium 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.
5. The medium 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.
6. The medium 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; and
a match indicator for identifying whether is a particular bracket of the backref-NFA is being matched.
7. An apparatus, comprising:
a memory; and
a processor operably coupled to the memory and configured by instructions stored thereon to:
compare 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.
8. The apparatus of claim 7 , wherein the processor is further configured to compare the input string with another pattern defined by another backref-regex.
9. The apparatus of claim 7 , wherein a determination is made that the input string matches the pattern on the condition that the final configurations-set contains the configuration associated with the final state.
10. The apparatus of claim 7 , wherein the processor is further configured to determine that the input string does not match the pattern on the condition that the final configurations-set lacks the configuration associated with the final state.
11. The apparatus of claim 7 , wherein the updating of 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.
12. The apparatus of claim 7 , 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.
13. The apparatus of claim 7 , 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; and
a match indicator for identifying a particular bracket of the backref-NFA to be matched.
14. 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.
15. The method of claim 14 , further comprising comparing the input string with another pattern defined by another backref-regex.
16. The method of claim 14 , further comprising determining that the input string does not match the pattern on the condition that the final configurations-set is empty.
17. The method of claim 14 , further comprising determining that the input string matches the pattern on the condition that the final configurations-set contains the configuration associated with the final state.
18. The method of claim 14 , further comprising determining that the input string does not match the pattern on the condition that the final configurations-set lacks the configuration associated with the final state.
19. The method of claim 14 , further comprising constructing backref-NFA based on the backref-regex.
20. The method of claim 14 , 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.
21. The method of claim 20 , wherein the new configuration is a configuration reachable by consuming the selected character from at least one of the one or more configurations in the configurations-set
22. The method of claim 14 , wherein the updating of the configurations-set for the selected character comprises:
on the condition that 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.
23. The method of claim 22 , 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.
24. The method of claim 14 , 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; and
a match indicator for identifying a particular bracket of the backref-NFA to be matched.
25. The method of claim 14 , further comprising removing from the configurations-sets those back-reference entries that are not alive.