Title: How to avoid infinite loops in the .NET RegEx class?
Tags: .net;regex;infinite-loop
Question: Got a simple task to get a XPath expression and return a prefix that matches the parent of the node that (might be) selected.

Example:

```/aaa/bbb       =&gt;   /aaa
/aaa/bbb/ccc   =&gt;   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] =&gt; /aaa/bbb
```

Because the patterns inside the square brackets might contain brackets within quotes, I decided to try to achieve this with the use of regular expressions. Here's a code snippet:

```string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match
```

Because the patterns are rather regular, I looked for '/' followed by indentifier followed by an optional group that matches at the end of the string (....)?$

The code seemd to work but playing with different values for the input string, I found that by simply inserting a space (in the location shown in the comment), the .NET IsMatch function gets into an infinite loop, taking all the CPU it gets.

Now regardless of whether this regular expression pattern is the best one (I had more complex but simplified it to show the problem), this seems to show that using RegEx with anything not trivial may be very risky.

Am I missing something? Is there a way to guard against infinite loops in regular expression matches?

Comment: in general, isn't that equivalent to the halting problem?

Here is the accepted answer: Ok, let's break this down then:

```Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$
```

(I assume you meant \" in your C#-escaped string, not ""... translation from VB.NET?)

First, /[a-zA-Z0-9]+ will gobble up through the first square bracket, leaving:

```Input: [@x='1' and @y="/aaa[name='z'] "]
```

The outer group of (\[([^]]*(]"")?)+])?$" should match if there is 0 or 1 instance before the EOL. So let's break inside and see if it matches anything.

The "[" gets gobbled right away, leaving us with:

```Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]
```

Breaking down the pattern: match 0 or more non-] characters and then match "] 0 or 1 times, and keep doing this until you can't. Then try to find and gobble a ] afterward.

The pattern matches based on [^]]* until it reaches the ].

Since there's a space between ] and ", it can't gobble either of those characters, but the ? after (]") allows it to return true anyway.

Now we've successfully matched ([^]]*(]")?) once, but the + says we should attempt to keep matching it any number of times we can.

This leaves us with:

```Input: ] "]
```

The problem here is that this input can match ([^]]*(]")?) an infinite of times without ever being gobbled up, and "+" will force it to just keep trying.

You're essentially matching "1 or more" situations where you can match "0 or 1" of something followed by "0 or 1" of something else. Since neither of the two subpatterns exists in the remaining input, it keeps matching 0 of [^]]\* and 0 of (]")? in an endless loop.

The input never gets gobbled, and the rest of the pattern after the "+" never gets evaluated.

(Hopefully I got the SO-escape-of-regex-escape right above.)

Comment for this answer: The problem here is that this input can match ([^]]*(]")?) an infinite of times without ever being gobbled up, and "+" will force it to just keep trying.     WHY ????
Comment for this answer: Encountered this myself with a complex pattern.  Sure makes me want to never use Regex again.  You have something that can have a landmine in it, and not because of a bug.  With a sufficiently complex pattern, you're never quite sure if that landmine will strike.
Comment for this answer: I think the differences you saw were due to the different dialects of regex, not fancy infinite-loop-detection in other engines.

The core problem is wrapping something that can match *empty text* an infinite number of times. Anything that's a variation of (x?)+ or (x?)* could be dangerous given the right input. Refactoring your pattern should allow you to get what you need without creating a potential for an infinite loop.

Regardless of the language, the lesson is to always program defensively against arbitrary user input.
Comment for this answer: Well that was productive (to me) - thanks Richard.

I conclude that:
1. Getting a regex pattern from an external source is dangerous and can easily hose an application
2. That the regex in .NET does not detect infinite loops and is also not providing a way to limit processing
3. That different regex engine can give different results so even if the syntax is the same, some semantics may be different (portability  note)

Thanks.

Here is another answer: To answer the original question (i.e. how to avoid infinite loop with regex), this has become easy with .Net 4.5 as you can simply pass a time out to the Regex methods. There is an internal timer that will stop the regex loop when the timeout expires and raise a RegexMatchTimeoutException

For example, you would do the following

```string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$";
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));
```

You can check out MSDN for more details

Comment for this answer: Thanks! - that's certainly useful and relevant info but still the original intent was to understand how to avoid this case to begin with) - it's nice to know that after 5 seconds it will throw an exception but it is much better to write it correctly to begin with...

Here is another answer: It shows that using code with anything not trivial can be risky. You created code that can result in an infinite loop, and the RegEx compiler obliged. Nothing new that hasn't been done since the first 20 IF X=0 THEN GOTO 10.

If you're worried about this in a particular edge case, you could spawn a thread for RegEx and then kill it after some reasonable execution time.

Comment for this answer: I find this answer contra productive. Other RegEx engines I tried didn't get into an infinite loop (try, for example, the online JavaScript RegEx tester at http://www.regular-expressions.info/javascriptexample.html and you'll see it works just fine).

This regular expression is simple enough and I do not find it trivial that its _expected_ failure mode (when no match is found) is an infinite loop.

The thread idea is not useful either. Should I use this idea anywhere an external RegEx is provided? I don't think so. I think this is probably a bug in the RegEx (or else a big gaping hole).

Here is another answer: ```
  The problem here is that this input can match ([^]]*(]")?) an infinite of times without ever being gobbled up, and "+" will force it to just keep trying.
```

That's one hell of a bug in .NET's RegEx implementation. Regular expressions just don't work like that. When you turn them into automata, you automatically get the fact that an infinite repetition of an empty string is still an empty string.

In other words, any non-buggy regex engine will execute this infinite loop instantly and continue with the rest of the regex.

If you prefer, regular expressions are such a limited language that it's possible (and easy) to detect and avoid such infinite loops.


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 4, 'CommentCount': 1, 'ContentLicense': 'CC BY-SA 2.5', 'CreationDate': '2009:00:07/29/09', 'FavoriteCount': 1.0, 'PostTypeId': 1, 'Tags': '<.net><regex><infinite-loop>', 'Title': 'How to avoid infinite loops in the .NET RegEx class?', 'ViewCount': 4393, 'id': 1200655, 'user_AboutMe': '', 'user_AccountId': 34903.0, 'user_DisplayName': 'Dror Harari', 'user_Reputation': 2867.0, 'user_Views': 224.0, 'user_id': 98694.0}}