Granted Patent B2

US 9,083,731 · App. 14/165,620 · Granted Jul 14, 2015

Abstract

Claims (50)

1. A non-transitory computer readable medium storing software instructions which, when executed by a processor, cause the processor to perform a method for estimating a 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), wherein the backref-NFA comprises 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.

2. The medium of claim 1 , wherein the method further comprises:

determining a value of the worst-case time complexity of the backref-regex based on the determined maximum number; and

providing the determined worst-case time complexity value.

3. The medium of claim 2 , 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 bracket and an ending bracket, the edges extending from a sub-backref-NFA corresponding to a sub-backref-regex embedded inside the each pair of brackets.

4. The medium of claim 3 , wherein the edges of the backref-NFA corresponding to the brackets of the backref-regex represent epsilon transitions.

5. The medium of claim 2 , wherein constructing the backref-NFA comprises:

for each sub-backref-regex embedded in a pair of matching brackets, constructing a corresponding sub-backref-NFA, and 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 each pair of matching brackets; and

for each back-reference, constructing an additional edge labeled to indicate the back-reference.

6. The medium of claim 1 , wherein the method further comprises:

comparing a value of the worst-case time complexity indicated by the determined maximum number to a pre-defined threshold; and

if the indicated worst-case time complexity value is above the pre-defined threshold, flagging a potentially bad pattern.

7. The medium of claim 1 , wherein the method further comprises removing from said backref-NFA NFA-state entries referring to back-references that are not alive.

8. The medium of claim 2 , wherein the method further comprises:

comparing the determined worst-case time complexity to a pre-defined threshold; and

if the determined worst-case time complexity value is above the pre-defined threshold, flagging a potentially bad pattern.

9. The medium of claim 1 , wherein the method further comprises selecting a pattern for use in identifying malicious packets if the indicated worst-case time complexity associated with the pattern being below a pre-defined threshold.

10. The medium of claim 9 , wherein said method is used to process each of a plurality of pattern-defining regular expressions to provide a set of patterns selected for use in identifying malicious packets.

11. The medium of claim 9 , wherein a received packet is identified as a malicious packet when an input string representing the received packet compares favorably with the pattern selected for use in identifying malicious packets.

12. The medium of claim 9 , wherein said method further comprises comparing an input string comprising a plurality of characters representing received packet to the pattern selected for use in identifying malicious packets 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.

13. The medium of claim 10 , wherein said method further comprises forwarding patterns selected for use in identifying malicious packets toward a packet-matching engine adapted to determine whether incoming packets to be rejected.

14. The medium of claim 9 , wherein said method further comprises 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 if the input string contains an unselected character;

updating the configurations-set, after all characters of the input string have been selected, to generate a final configurations-set; and

determining whether the final configurations-set contains a configuration associated with a final NFA-state.

15. The medium of claim 9 , wherein said method is implemented within an intrusion detection system and intrusion prevention system (IDS/IPS) operative to analyze packets transiting between an unsecured network and a secured network.

16. An apparatus, comprising:

a memory for storing program logic; and

a processor operably coupled to the memory and configured by the program logic stored thereon to estimate a worst-case time complexity of a regular expression comprising one or more back-references (backref-regex), the regular expression defining a pattern adapted for identifying malicious packets, the program logic comprising:

logic for constructing a non-deterministic finite automaton (NFA) corresponding to the backref-regex (backref-NFA), wherein the backref-NFA comprises a plurality of NFA-states and a respectively labeled edge for each of the one or more back-references of the backref-regex;

logic for 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;

logic for 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; and

if the indicated worst-case time complexity is below a pre-defined threshold, logic for selecting the pattern for use in identifying malicious packets.

17. The apparatus of claim 16 , wherein said apparatus is implemented within an intrusion detection system and intrusion prevention system (IDS/IPS) operative to analyze packets transiting between an unsecured network and a secured network.

18. A tangible and non-transitory computer program product wherein computer instructions, when executed by a processor in a telecom network element, adapt operation of the telecom network element to provide a method for evaluating a pattern to determine if the pattern should be included within a set of patterns used by a malicious packet detector, the malicious packet detector comparing an input string representing a packet received at a network element to one or more patterns within the set of patterns to identify malicious packets, the method comprising:

estimating worst-case time complexity of a regular expression comprising one or more back-references (backref-regex), the regular expression defining a pattern adapted for identifying malicious packets; and

if the estimated worst-case time complexity is below a pre-defined threshold, selecting the pattern for inclusion within the set of patterns;

wherein said estimating comprises:

constructing a non-deterministic finite automaton (NFA) corresponding to the backref-regex (backref-NFA), wherein the backref-NFA comprises 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.

19. The computer program product of claim 18 , wherein said method further comprises forwarding patterns selected for use in identifying malicious packets toward a packet-matching engine adapted to determine whether incoming packets to be rejected.

20. The computer program product of claim 18 , wherein said method further comprises comparing an input string comprising a plurality of characters representing received packet to a pattern selected for use in identifying malicious packets 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.

Assignments (12)