Bug in mSearchREG() that can make Snort go into an infinite loop.

[Andreas Östling <andreaso () it su se>]

Hello,

As described by a few others (for example
http://sourceforge.net/tracker/index.php?func=detail&aid=494612&group_id=3357&atid=103357)
my Snort sometimes also stopped logging, and went up to near 100% CPU
usage.

I recently managed to reproduce this without just starting Snort and wait
a few days for it to happen again. In particular, SID 1250, which is a
regex rule, seems to cause the behaviour when certain packets are seen.
A simplified version of this rule is:

alert tcp any any -> any 80 (msg:"test"; content:"/level/*/exec/"; regex;)

When starting Snort with this (and only this) rule, sending the string
"123456/ABCDEFGHIJKLMNO/exec/" to a host having port 80 listening will
make Snort immediately jump up to near 100% CPU usage, and just stay
there forever. Ktrace confirms that Snort is probably stuck in an endless
internal loop (no output at all). Tests below are done with 1.8.4-beta1
(Build 91). Everything is probably not correct, but will hopefully at
least be enough to point to the right direction.

Snort is started with:
snort -c snort.conf -l /tmp -d -i lo0

The only line in snort.conf is the rule above.
Then sending the evil string:
echo '123456/ABCDEFGHIJKLMNO/exec/' | nc localhost 80

After a few seconds, 'top' output shows:

  PID USERNAME PRI NICE  SIZE   RES STATE WAIT     TIME    CPU COMMAND
23845 root      64    0  644K  856K run   -        0:59 94.97% snort

And trust me, my loopback interface is not THAT busy :)

The problem seems to be in the mSearchREG function, found in mstring.c.
I'll try to show what I think is going on in the code, step by step.
Feel free to point out all the misassumptions/errors I've made.
There are probably also a few typos since it was made in kind of a hurry.
("*" is where the character comparision will start)

1)
             *
/level/*/exec/
123456/ABCDEFGHIJKLMNO/exec/

"G" does not equal "/", and since "G" is not even in the pattern,
b_idx is "skip-shifted" to 28. So we get:

2)
                           *
              /level/*/exec/
123456/ABCDEFGHIJKLMNO/exec/

The while(buf[--b_idx] == ptrn[--p_idx] ... || (ptrn[p_idx] == '*' &&
!literal) will end when p_idx is 7, since we have a "*" there.
The character left to it is a "/". Next, while(buf[--b_idx] !=
ptrn[p_idx]) will check buf from right to left until it finds a matching
"/" (the 'wildcard final char'), which exists in buf[6].

3)
     *
/level/*/exec/
123456/ABCDEFGHIJKLMNO/exec/

Here "6" will not match "l", and b_idx will be skip-shifted to 27 (22
steps) since there is no "6" in the pattern.

4)
We get:
                          *
             /level/*/exec/
123456/ABCDEFGHIJKLMNO/exec/

"c" does not equal "/", and the pattern will be skip-shifted to 28.

5)
We now get:
                           *
              /level/*/exec/
123456/ABCDEFGHIJKLMNO/exec/

However, this is exactly where we were at step 2), so we're now in
an infinite loop.

The solution?
Here is a quick and wild guess... I would say that the problem is in 3).
Since the "*" wildcard matched "ABCDEFGHIJKLMNO", we're not interested in
that part anymore. Therefore, b_idx should be skip-shifted to 22 + the
length of the pattern just matched by the wildcard.

For example with this patch:

--- mstring.c.org       Mon Feb 11 23:32:58 2002
+++ mstring.c   Mon Feb 11 23:37:32 2002
@@ -581,6 +581,7 @@
     int b_idx = plen;
     int literal = 0;
     int cmpcnt = 0;
+    int regexcomp = 0;

   DebugMessage(DEBUG_PATTERN_MATCH, "buf: %p  blen: %d  ptrn: %p "
             " plen: %d b_idx: %d\n", buf, blen, ptrn, plen, b_idx);
@@ -624,6 +625,7 @@
                   DebugMessage(DEBUG_PATTERN_MATCH, "comparing: b[%d]:%c -> p[%d]:%c\n",
                             b_idx, buf[b_idx], p_idx, ptrn[p_idx]);

+                   regexcomp++;
                     if(b_idx == 0)
                     {
                       DebugMessage(DEBUG_PATTERN_MATCH, "b_idx went to 0, returning 0\n");
@@ -651,6 +653,9 @@

         b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;
       DebugMessage(DEBUG_PATTERN_MATCH, "b_idx skip-shifted to %d\n", b_idx);
+        b_idx += regexcomp;
+      DebugMessage(DEBUG_PATTERN_MATCH, "b_idx regex compensated %d steps, to %d\n", regexcomp, b_idx);
+        regexcomp = 0;
     }

   DebugMessage(DEBUG_PATTERN_MATCH, "no match: compares = %d, b_idx = %d, "



But again, be warned that this is mostly a wild guess and may break many
other things. Paranoid people may instead want to disable the regex rules
(should not be a big deal) until a confirmed working fix is out.

It would be nice to know if disabling the regex rules actually solves the
similar problems other people are having, or if this is a totally
different bug.

Regards,
Andreas Östling


_______________________________________________
Snort-users mailing list
Snort-users () lists sourceforge net
Go to this URL to change user options or unsubscribe:
https://lists.sourceforge.net/lists/listinfo/snort-users
Snort-users list archive:
http://www.geocrawler.com/redir-sf.php3?list=snort-users