regex grouping fails with more than one group

Question

I have this regex, for C#. The alert portion works fine, but when I add the msg group, it just hangs with cursor blinking on command line.

What have I missed, they both work by themselves, but not in full group map.

string pattern = @"(?<action>alert\s+(?:tcp|udp|icmp)\s+(.*?)*[(])\s+" +
                                     @"(?<msg>msg[:](.*?)\[;\s*])";
                    Regex rgx = new Regex(pattern);
                    Match res = rgx.Match(rule);

I'm trying to match a string like #alert tcp $EXTERNAL_NET any -> $HOME_NET 12345:12346 (msg:"MALWARE-BACKDOOR netbus getinfo"; flow:to_server,established;

Answer 1

The problem is with (.*?)* in your first group. Try (.*?) instead.

When matching without the second group, that just matches till the end of the line. However, when adding the second group, it needs to back off to allow the second group to match. Since you've got two quantifiers interacting, there are a bazillion ways to match until it has backed off sufficiently to allow the second group to match.

An example. Let's say you're matching the string abc with (.*?)*. The ways for that to match are:

(a)(b)(c)
(a)(bc)
(ab)(c)
(abc)

And that's not counting the possible empty strings that regex might match in between (because .* will match an empty string as well). Trying to match one character more, say abcd, yields as possible matches:

(a)(b)(c)(d)
(a)(b)(cd)
(a)(bc)(d)
(a)(bcd)
(ab)(c)(d)
(ab)(cd)
(abc)(d)
(abcd)

So the number of possible matches doubles for every character added.