Closed Bug 616491 Opened 14 years ago Closed 10 years ago

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

Categories

(Core :: JavaScript Engine, defect, P2)

x86
Linux
defect

Tracking

()

RESOLVED WONTFIX
mozilla31
Tracking Status
firefox25 --- wontfix
firefox26 --- wontfix
firefox27 --- wontfix
firefox28 --- wontfix
firefox29 --- fixed
firefox30 --- fixed
firefox31 --- fixed
firefox-esr24 --- wontfix
b2g18 --- wontfix
b2g-v1.1hd --- wontfix
b2g-v1.2 --- wontfix
b2g-v1.3 --- wontfix
b2g-v1.3T --- wontfix
b2g-v1.4 --- fixed
b2g-v2.0 --- fixed

People

(Reporter: decoder, Assigned: sstangl)

References

Details

(4 keywords, Whiteboard: softblocker, stack-exhaustion, [jsbugmon:testComment=7,origRev=885cde564ff3])

Attachments

(6 files)

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
blocking2.0: --- → ?
Nice report. Thanks.
Status: UNCONFIRMED → NEW
Ever confirmed: true
Priority: -- → P2
Chris, can you look into this? And please suggest a security rating here.
Assignee: general → cdleary
Looks like a too-much-recursion crash, which should be safe. Did you see something that looked like actual memory corruption?
(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.
Keywords: crash, testcase
Summary: Large number of groups in regex causes stack overflow (segfault) → Large number of groups in regex causes too-much-recursion crash
Group: core-security
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.
blocking2.0: ? → final+
Whiteboard: softblocker
** 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
blocking2.0: final+ → .x+
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");
}
Simplest thing that could possibly work -- I think Christian said that this would be helpful for his fuzz testing.
Attachment #583318 - Flags: review?(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?
Attachment #583318 - Flags: review?(dmandelin)
Assignee: cdleary → dmandelin
Summary: Large number of groups in regex causes too-much-recursion crash → Large number of groups in regex causes too-much-recursion crash (YARR)
Keywords: csec-dos, csec-other
Whiteboard: softblocker → softblocker, stack-exhaustion
Whiteboard: softblocker, stack-exhaustion → softblocker, stack-exhaustion, [jsbugmon:update,testComment=7,origRev=885cde564ff3]
Whiteboard: softblocker, stack-exhaustion, [jsbugmon:update,testComment=7,origRev=885cde564ff3] → softblocker, stack-exhaustion, [jsbugmon:testComment=7,origRev=885cde564ff3]
JSBugMon: Cannot process bug: Error: Unsupported branch "unspecified" required by bug
Whiteboard: softblocker, stack-exhaustion, [jsbugmon:testComment=7,origRev=885cde564ff3] → softblocker, stack-exhaustion, [jsbugmon:update,testComment=7,origRev=885cde564ff3]
Version: unspecified → Trunk
Blocks: 835696
Whiteboard: softblocker, stack-exhaustion, [jsbugmon:update,testComment=7,origRev=885cde564ff3] → softblocker, stack-exhaustion, [jsbugmon:testComment=7,origRev=885cde564ff3]
JSBugMon: Cannot process bug: Error: Failed to compile specified revision 885cde564ff3 (maybe try another?)
Attached file stack
I can still reproduce this on m-c rev 9afe2a1145bd, tested with a 64-bit debug threadsafe shell on Mac.
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?
Flags: needinfo?(sstangl)
(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.
Attached patch patchSplinter Review
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.
Attachment #8397411 - Flags: review?(mrosenberg)
Flags: needinfo?(sstangl)
Comment on attachment 8397411 [details] [diff] [review]
patch

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

*grumble pointer arithmetic*  *grumble C spec*
looks good.
Attachment #8397411 - Flags: review?(mrosenberg) → review+
Assignee: dmandelin → 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.
https://hg.mozilla.org/mozilla-central/rev/fe0c6926b8b4
Status: NEW → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla31
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.
Attachment #8397411 - Flags: approval-mozilla-esr24?
Attachment #8397411 - Flags: approval-mozilla-beta?
Attachment #8397411 - Flags: approval-mozilla-b2g28?
Attachment #8397411 - Flags: approval-mozilla-aurora?
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.
Attachment #8397411 - Flags: approval-mozilla-esr24?
Attachment #8397411 - Flags: approval-mozilla-esr24-
Attachment #8397411 - Flags: approval-mozilla-beta?
Attachment #8397411 - Flags: approval-mozilla-beta+
Attachment #8397411 - Flags: approval-mozilla-aurora?
Attachment #8397411 - Flags: approval-mozilla-aurora+
(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.
Attachment #8397411 - Flags: approval-mozilla-b2g28? → approval-mozilla-b2g28-
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?
Flags: needinfo?
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
*/
Flags: needinfo? → needinfo?(paul.silaghi)
(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
Flags: needinfo?(paul.silaghi)
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.
Status: RESOLVED → REOPENED
Flags: needinfo?(sstangl)
Resolution: FIXED → ---
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.
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?
Flags: needinfo?(gary)
(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! :)
Flags: needinfo?(gary)
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.
Attachment #8403546 - Flags: review?(mrosenberg)
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.
Attachment #8403546 - Flags: review?(mrosenberg) → review+
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.
Flags: needinfo?(sstangl)
Is this fixed as per the status flags?
Sean: is this bug fixed? Your patch was backed out in comment 39. Also, we replaced YARR with irregexp in Firefox 32 (bug 976446).
Flags: needinfo?(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.
Status: REOPENED → RESOLVED
Closed: 10 years ago10 years ago
Flags: needinfo?(sstangl)
Resolution: --- → WONTFIX
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?
(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.
You need to log in before you can comment on or make changes to this bug.