409037 - Multiple non-critical hangs in javascript regular expression handling

Status: RESOLVED DUPLICATE of bug 330569

(Core :: JavaScript Engine, defect)

Description

[Will Drewry]

User-Agent:       Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.4; en-US; rv:1.9b1) Gecko/2007110903 Firefox/3.0b1
Build Identifier: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.4; en-US; rv:1.9b1) Gecko/2007110903 Firefox/3.0b1

My colleague, Tavis Ormandy ([e-mail]), and I have been researching regular expression engine security and will be presenting our findings in late January.  Of course, spidermonkey fell into this work and we've run across a few infinite loops.  The page above contains each of the examples.

Entries FF 6 and trunk 1-6 appear to apply to the 3.0 beta code.  In my experience, FF 1 and 3 applied to FF 2.0.0.10 on Linux (but should be cross-applicable). In all cases, these infinite loops are caught by the Firefox timeout, but other embedded instances of spidermonkey will not necessarily have that safety.  I have not manually investigated all of these cases, but they appear to be a combination of exponential evaluation time during backtracking, and in one case in particular, the bytecode is optimized in such a way that it enters an infinite loop in and out of backtracking. (JMP, return, JMP,...).

Reproducible: Always

Steps to Reproduce:
1. Open page above
2. Select attack code
3. Click "Attack!"
Actual Results:  
The firefox process hangs until the time-out catches it. 

Expected Results:  
It depends on the case - where the bytecode is mis-optimized, it should not enter an infinite loop.  (A quick walk through the standalone spidermonkey shell with gdb should show the affected code.)

In the cases of a large number of states/operations, a upper bound would protect against out-of-control execution.  This is default behavior in software like lex, and I've just added a simplistic version (max NFA states) to TCL: http://tcl.cvs.sourceforge.net/tcl/tcl/generic/regc_nfa.c?r1=1.10&r2=1.11

I'd been sitting on these a while hoping to do some more investigation, but it seemed like it'd be better to share now than wait!  In addition, we have a fuzz testing harness for javascript regular expressions that works well with the standalone spidermonkey which we're happy to share. (We'll be releasing it later with our presentation.)

If you also consider these security issues and choose to issue an advisory/whatever, we'd greatly appreciate credit to "Will Drewry <[e-mail]> and Tavis Ormandy <[e-mail]> of the Google Security Team" - absoutely at your discretion of course.

Please let me know if there's anything we can do to help out!

Comment 1

[Jeff Walden [:Waldo]]

(In reply to comment #0)
> In the cases of a large number of states/operations, a upper bound would
> protect against out-of-control execution.

We added an upper-bound to trunk SpiderMonkey near the beginning of the year, so I'm a little surprised (although I haven't taken the time to read our regexp code yet) we wouldn't be hitting that:

http://bonsai.mozilla.org/cvsblame.cgi?file=/mozilla/js/src/jsregexp.c&rev=3.173&mark=338-339#320

CCing the author of the patch that added that, since he'll have rather more insight than I will.

Comment 2

[Will Drewry]

The backtrack limit appears to be enabled only via the 'relimit' js option (JSOPTION_RELIMIT).   I'm not sure how I missed that before, but it's there.  However, I don't see that in use anywhere but the standalone shell.  Is Firefox, etc supposed to be making use of it?

Comment 3

[Will Drewry]

Okay, so with that in mind, it is default-off in the config:
javascript.options.relimit.

Flipped to true, all is well.  So my whole bug boils down to a request to enable that by default both in FF and in spidermonkey itself to default-protect users.  (The timeout works well in FF as well, but having that flipped is a much nicer user experience.)  However, since it's in there, this bug is a lot less of a big deal!  Sorry for causing so much noise!

Comment 4

[Brian Crowder]

I don't that this sort of DOS attack really qualifies as security sensitive.  There are lots of ways to hang the browser until the slow-script dialog appears.  I implemented the relimit feature mainly to allow authors and the impatient to avoid that long wait for obviously complex expressions (worse than O(n-cubed)) by causing an exception to be thrown.  The problem is that I am still not entirely sure how much of the web would be broken by making this behavior the default.  As I understand it, Safari's forked PCRE allows some arbitrarily large number of backtrack states before failing silently (I think no exception is thrown, correct me if I am wrong).  What we do, instead, is allow
    MAX(400000, pow(strlen(input_string), 3)
backtrack states, before throwing an exception.  This usually means that you get a result very rapidly, long before the slow-script timer will gripe, certainly.  But we do not impose an artificial maximum as Safari does, which means we can still be DOSed by a very long input string.  It might be that we should fix this, but I'm not convinced it's a huge issue.  I don't think the browser-DOS business is a very attractive one, not even for mischief-makers.

That said, I'd be thrilled to have a look at your fuzzer and its results, as would Jesse, no doubt.

I'm duping this bug back to the bug in which I patched in relimit.

Comment 5

[Brian Crowder]

> in one case in particular, the bytecode is optimized in such a way that it
> enters an infinite loop in and out of backtracking. (JMP, return, JMP,...).

If you can open a separate bug for this, with a reduced testcase including the bad regexp, that would be great.  Thanks.

Comment 6

[Will Drewry]

> I don't that this sort of DOS attack really qualifies as security sensitive. 

Yep, I just wanted to give you the opportunity to decide.  There are so many ways to do it that adding one more to the pile doesn't seem notable.   I wasn't sure if this would have any effect on other spidermonkey consumers.  Hopefully, however, they will use the relimit option.

(Also, we're interested in discussing bugs that have occurred in engines we've surveyed, and I'd hate to do that without any sort of notification even if there's no real impact!)

> That said, I'd be thrilled to have a look at your fuzzer and its results, as
> would Jesse, no doubt.

I'll mail you (Brian) and Jesse the unpolished version along with any relevant details.

> If you can open a separate bug for this, with a reduced testcase including the
> bad regexp, that would be great.  Thanks.

I'm dusting off some old notes and will post a separate bug with the details soonish.

thanks!
will