616491 - Large number of groups in regex causes too-much-recursion crash (YARR)

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect, P2)

Description

[Christian Holler (:decoder)]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.12) Gecko/20101027 Ubuntu/10.10 (maverick) Firefox/3.6.12
Build Identifier: 

The following code produces a segmentation fault on the 2.0 branch:

testThis(100000, false, 'hello', 'goodbye');

function testThis(numParens, doBackRefs, strOriginal, strReplace)
{
  var openParen = doBackRefs? '(' : '(?:';
  var closeParen = ')';
  var pattern = '';
  for (var i=0; i<numParens; i++) {pattern += openParen;}
  for (i=0; i<numParens; i++) {pattern += closeParen;}
  var re = new RegExp(pattern);
}

The reason is a stack overflow due to recursion in JSC::Yarr::RegexPatternConstructor::setupAlternativeOffsets.

I guess some limit on the number of parentheses is missing here :)

Flagged as security related (memory corruption) although I think exploitation shouldn't be possible in this case.

Stable branch 1.9.2 isn't affected.

Reproducible: Always

Steps to Reproduce:
Create large amount of regex groups
Actual Results:  
Crash

Expected Results:  
Error message/limitation on number of groups

Comment 1

[Andreas Gal :gal]

Nice report. Thanks.

Comment 2

[Johnny Stenback (:jst)]

Chris, can you look into this? And please suggest a security rating here.

Comment 3

[Jesse Ruderman]

Looks like a too-much-recursion crash, which should be safe. Did you see something that looked like actual memory corruption?

Comment 4

[Christian Holler (:decoder)]

(In reply to comment #3)
> Looks like a too-much-recursion crash, which should be safe.

That doesn't hold in general, I've seen recursion crashes that were indeed exploitable (there was an infinite recursion problem in postscript that could be exploited). However, in this case I haven't seen anything that looked exploitable.

Comment 5

[Alex Miller]

On stable 1.9.2 I got a hang, which is expected for this. I have not seen any evidence of memory corruption, or anything else exploitable.

Comment 6

[Mike Beltzner [:beltzner, not reading bugmail]]

** PRODUCT DRIVERS PLEASE NOTE **

This bug is one of 7 automatically changed from blocking2.0:final+ to blocking2.0:.x during the endgame of Firefox 4 for the following reasons:

 - it was marked as a soft blocking issue without a requirement for beta coverage

Comment 7

[Christian Holler (:decoder)]

Since bug 673188 (lazy regexp compilation) landed, the test in comment 0 will no longer reproduce. The bug can still be triggered by modifying that test to explicitly use the created regular expression:


testThis(100000, false, 'hello', 'goodbye');
function testThis(numParens, doBackRefs, strOriginal, strReplace) {
  var openParen = doBackRefs? '(' : '(?:';
  var closeParen = ')';
  var pattern = '';
  for (var i=0; i<numParens; i++) {pattern += openParen;}
  for (i=0; i<numParens; i++) {pattern += closeParen;}
  var re = new RegExp(pattern);
  re.exec("foo");
}

Comment 8

[Chris Leary [:cdleary] (not checking bugmail)]

Attachment: Prevent over recursion.

Simplest thing that could possibly work -- I think Christian said that this would be helpful for his fuzz testing.

Comment 9

[David Mandelin [:dmandelin]]

Comment on attachment 583318 [details] [diff] [review]
Prevent over recursion.

Review of attachment 583318 [details] [diff] [review]:
-----------------------------------------------------------------

A couple of questions:

1. Should we upstream this to JSC?

2. What about initializing the base the first time the reentrant function is called, so that a set function is not required?

Comment 11

[Christian Holler (:decoder)]

JSBugMon: Cannot process bug: Error: Unsupported branch "unspecified" required by bug

Comment 12

[Christian Holler (:decoder)]

Attachment: [crash-signature] Machine-readable crash signature

Comment 13

[Christian Holler (:decoder)]

JSBugMon: Cannot process bug: Error: Failed to compile specified revision 885cde564ff3 (maybe try another?)

Comment 14

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: stack

I can still reproduce this on m-c rev 9afe2a1145bd, tested with a 64-bit debug threadsafe shell on Mac.

Comment 15

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Sean, cleary had some sort-of a patch in comment 8, review comments in comment 9, perhaps you'd know of the best way to move this forward?

Comment 16

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(In reply to Gary Kwong [:gkw] [:nth10sd] from comment #14)
> I can still reproduce this on m-c rev 9afe2a1145bd, tested with a 64-bit
> debug threadsafe shell on Mac.

FWIW, I tested the testcase in comment 7.

Comment 17

[Sean Stangl [:sstangl]]

Attachment: patch

This bug is pretty embarrassing. A perfectly good patch to fix this was sitting here since 2011. This version just updates the patch to be in our modern style, but attempting to detect over-recursion is just a good idea.

Comment 18

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 8397411 [details] [diff] [review]
patch

Review of attachment 8397411 [details] [diff] [review]:
-----------------------------------------------------------------

*grumble pointer arithmetic*  *grumble C spec*
looks good.

Comment 19

[Sean Stangl [:sstangl]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/fe0c6926b8b4

Comment 20

[Sean Stangl [:sstangl]]

Note that this bug is also filed with WebKit as https://bugs.webkit.org/show_bug.cgi?id=103813, which appears to be security-sensitive.

Comment 21

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/fe0c6926b8b4

Comment 23

[Sean Stangl [:sstangl]]

Comment on attachment 8397411 [details] [diff] [review]
patch

Nominating per Bug 835696 Comment 38.

[Approval Request Comment]
Bug caused by (feature/regressing bug #): YARR since initial import
User impact if declined: Maliciously crafted regular expressions with excessive backreferences crash the JS engine.
Testing completed (on m-c, etc.): m-c
Risk to taking this patch (and alternatives if risky): It is possible, but extremely unlikely, that some script may depend on proper execution of a regular expression with tens of thousands of backreferences, which this patch would detect as OOM.
String or IDL/UUID changes made by this patch: None.

Comment 24

[Sylvestre Ledru [:Sylvestre]]

Comment on attachment 8397411 [details] [diff] [review]
patch

Unless that is an important security issue (which is unlikely since this bug is public), we won't approve that to ESR. We only uplift important security issues.

Comment 25

[bhavana bajaj [:bajaj]]

(In reply to Sylvestre Ledru [:sylvestre] from comment #24)
> Comment on attachment 8397411 [details] [diff] [review]
> patch
> 
> Unless that is an important security issue (which is unlikely since this bug
> is public), we won't approve that to ESR. We only uplift important security
> issues.

same applies for b2g28. We are taking critical blockers at this time, wontixing this for 1.3/1.3T now. Given mozilla-aurora (gecko 30) is the gecko base FxOs 1.4 this should be resolved once uplifted to aurora on 1.4.

Comment 26

[Paul Silaghi, QA [:pauly]]

Run the code in comment 7 in the web console -> crash 31.0a1 (2014-03-30), Win 7 x64
https://crash-stats.mozilla.com/report/index/d740309d-5dda-4ed1-8605-ee3f72140331

Thoughts?

Comment 27

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Paul, do you mind rechecking please? I think the testcase in comment 7 got fixed by Sean's patch, at least in the shell.

Moreover, in the latest nightly browser (but on Mac), after running it in Scratchpad, I only got:

/*
Exception: regular expression too complex
testThis@Scratchpad/1:18:3
@Scratchpad/1:10:1
*/

Comment 28

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/e0cac690e8ae
https://hg.mozilla.org/releases/mozilla-beta/rev/9ed2ec49735e

Comment 29

[Paul Silaghi, QA [:pauly]]

(In reply to Gary Kwong [:gkw] [:nth10sd] from comment #27)
> Paul, do you mind rechecking please?
Rechecked - https://crash-stats.mozilla.com/report/index/e6e46b88-dc94-41c4-b9bd-3c2ec2140401

> Moreover, in the latest nightly browser (but on Mac), after running it in
> Scratchpad, I only got:
> Exception: regular expression too complex
Indeed, it's not repro on Mac or Linux, only on Win

Comment 30

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

I reconfirm this crash on Windows. Thanks, Paul.

There's now a crash at mozilla::VectorBase with infinite recursion over JSC::Yarr::YarrPatternConstructor::setupAlternativeOffsets and/or JSC::Yarr::YarrPatternConstructor::setupDisjunctionOffsets.

Sean, I guess this isn't fixed on Windows. I'll attach a stack.

Comment 31

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: Windows stack for debug js shells

Tested on m-c rev 4941a2ac0786, with the following configure parameters (32-bit debug Windows shell):

MAKE=mozmake AR=ar sh ../configure --enable-optimize --enable-debug --enable-profiling --enable-gczeal --enable-debug-symbols --disable-tests --disable-threadsafe

This also crashes opt builds (and thus the browser) with too-much-recursion at JSC::Yarr::YarrPatternConstructor::setupAlternativeOffsets and/or JSC::Yarr::YarrPatternConstructor::setupDisjunctionOffsets.

Comment 32

[Sean Stangl [:sstangl]]

Bear in mind that this bug is the stack running out of memory, which can be affected by the total amount of system memory available, and the behavior of the host kernel. This patch doesn't solve the issue, which isn't really solvable, but instead tries to predict when OOM is about to happen by setting a reasonable bound. The bound may be wrong for Windows.

Gary, would you mind changing the constant at js/src/yarr/YarrPattern.cpp:582 from "1024*1024" to "1 << 19", and seeing whether that fixes the crash on Windows? If it doesn't, would you mind finding the highest value X such that "1 << X" does not reproduce the crash on your system?

Comment 33

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

(In reply to Sean Stangl [:sstangl] from comment #32)
> Gary, would you mind changing the constant at
> js/src/yarr/YarrPattern.cpp:582 from "1024*1024" to "1 << 19", and seeing
> whether that fixes the crash on Windows?

I made this change as suggested:

-        if (m_stackBase - &stackDummy_ > 1024*1024)
+        if (m_stackBase - &stackDummy_ > (1 << 19))

and yes, the crash does go away! :)

Comment 34

[Sean Stangl [:sstangl]]

Attachment: Lower limit to 256KB to fix Windows

Follow-up based on Gary's tests: 256KB should be sufficiently large to handle most parses. The patch isn't minimal because I also took the opportunity to move the logic out to a helper function and put it in another place that could easily over-recurse with the right regexp.

Comment 35

[Marty Rosenberg [:mjrosenb]]

Comment on attachment 8403546 [details] [diff] [review]
Lower limit to 256KB to fix Windows

Review of attachment 8403546 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/yarr/YarrPattern.cpp
@@ +311,5 @@
> +    bool isOverRecursed() {
> +        /*
> +         * Bug 616491: attempt detection of over-recursion.
> +         * "256KB should be enough stack for anyone."
> +         */

I want to say that 16 kb should be enough for anyone, but this is less likely to give strange behavior.

Comment 36

[Sean Stangl [:sstangl]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/9e43ff213b64

Comment 37

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

Backed out in http://hg.mozilla.org/integration/mozilla-inbound/rev/190102c75df0 for breaking the build like this: https://tbpl.mozilla.org/php/getParsedLog.php?id=38202295&tree=Mozilla-Inbound

So far, Linux, OSX, and Android have failed. Windows and B2G are still running.

Comment 38

[Sean Stangl [:sstangl]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/0c0a5a6b57d9

Comment 39

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

(In reply to Sean Stangl [:sstangl] from comment #38)
> https://hg.mozilla.org/integration/mozilla-inbound/rev/0c0a5a6b57d9

Backed this out in http://hg.mozilla.org/integration/mozilla-inbound/rev/1a2d8d974ca7 for jsreftest bustage: https://tbpl.mozilla.org/php/getParsedLog.php?id=38208299&tree=Mozilla-Inbound

Comment 40

[u279076]

Is this fixed as per the status flags?

Comment 41

[Chris Peterson [:cpeterson]]

Sean: is this bug fixed? Your patch was backed out in comment 39. Also, we replaced YARR with irregexp in Firefox 32 (bug 976446).

Comment 42

[Sean Stangl [:sstangl]]

No, I didn't notice that it was backed out again. Given that this patch only applies to Beta/ESR31, and that other Yarr patches have been rejected from Beta, this bug is WONTFIX.

Comment 43

[peter.koff.ca]

Guys, I hate to say this but the bug is back in v32.
My regexes work perfectly well in v31, upgrading to v32 brakes them.

Any comment?

Comment 44

[Chris Peterson [:cpeterson]]

(In reply to peter.koff.ca from comment #43)
> Guys, I hate to say this but the bug is back in v32.
> My regexes work perfectly well in v31, upgrading to v32 brakes them.

Peter, can you please file a new bug about Firefox 32 with an example regex? This bug report is about a specific problem in the old YARR regex engine. The new problem is probably a regression in the new  irregexp engine added in bug 976446.