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

RESOLVED WONTFIX

Status

()

P2
critical
RESOLVED WONTFIX
8 years ago
4 years ago

People

(Reporter: decoder, Assigned: sstangl)

Tracking

(Blocks: 1 bug, 4 keywords)

Trunk
mozilla31
x86
Linux
crash, csectype-dos, csectype-other, testcase
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(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)

Details

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

Attachments

(6 attachments)

(Reporter)

Description

8 years ago
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

Updated

8 years ago
blocking2.0: --- → ?

Comment 1

8 years ago
Nice report. Thanks.
Status: UNCONFIRMED → NEW
Ever confirmed: true

Updated

8 years ago
Priority: -- → P2
Chris, can you look into this? And please suggest a security rating here.
Assignee: general → cdleary

Comment 3

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

Comment 4

8 years ago
(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.

Updated

8 years ago
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

Updated

8 years ago
Group: core-security

Comment 5

8 years ago
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.

Updated

8 years ago
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+
(Reporter)

Updated

7 years ago
Blocks: 676763
(Reporter)

Comment 7

7 years ago
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");
}
Created attachment 583318 [details] [diff] [review]
Prevent over recursion.

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
Duplicate of this bug: 817285
(Reporter)

Updated

6 years ago
Whiteboard: softblocker, stack-exhaustion → softblocker, stack-exhaustion, [jsbugmon:update,testComment=7,origRev=885cde564ff3]
(Reporter)

Updated

6 years ago
Whiteboard: softblocker, stack-exhaustion, [jsbugmon:update,testComment=7,origRev=885cde564ff3] → softblocker, stack-exhaustion, [jsbugmon:testComment=7,origRev=885cde564ff3]
(Reporter)

Comment 11

6 years ago
JSBugMon: Cannot process bug: Error: Unsupported branch "unspecified" required by bug
(Reporter)

Updated

6 years ago
Whiteboard: softblocker, stack-exhaustion, [jsbugmon:testComment=7,origRev=885cde564ff3] → softblocker, stack-exhaustion, [jsbugmon:update,testComment=7,origRev=885cde564ff3]
Version: unspecified → Trunk
Blocks: 835696
(Reporter)

Comment 12

5 years ago
Created attachment 758491 [details]
[crash-signature] Machine-readable crash signature
(Reporter)

Updated

5 years ago
status-firefox25: --- → affected
status-firefox26: --- → affected
status-firefox27: --- → affected
status-firefox28: --- → affected
(Reporter)

Updated

5 years ago
Whiteboard: softblocker, stack-exhaustion, [jsbugmon:update,testComment=7,origRev=885cde564ff3] → softblocker, stack-exhaustion, [jsbugmon:testComment=7,origRev=885cde564ff3]
(Reporter)

Comment 13

5 years ago
JSBugMon: Cannot process bug: Error: Failed to compile specified revision 885cde564ff3 (maybe try another?)
Created attachment 8397265 [details]
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.
(Assignee)

Comment 17

5 years ago
Created attachment 8397411 [details] [diff] [review]
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.
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)

Updated

5 years ago
Assignee: dmandelin → sstangl
(Assignee)

Comment 20

5 years ago
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
Last Resolved: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla31
Duplicate of this bug: 835696
status-b2g18: --- → affected
status-b2g-v1.1hd: --- → affected
status-b2g-v1.2: --- → affected
status-b2g-v1.3: --- → affected
status-b2g-v1.3T: --- → affected
status-b2g-v1.4: --- → affected
status-b2g-v2.0: --- → affected
status-firefox29: --- → affected
status-firefox30: --- → affected
status-firefox31: --- → fixed
status-firefox-esr24: --- → affected
tracking-b2g18: --- → ?
tracking-b2g-v1.2: --- → ?
tracking-b2g-v1.3: --- → ?
tracking-firefox29: --- → ?
tracking-firefox30: --- → ?
tracking-firefox31: --- → ?
tracking-firefox-esr24: --- → ?
blocking2.0: .x+ → ---
status-b2g18: affected → wontfix
status-b2g-v1.1hd: affected → wontfix
status-b2g-v1.2: affected → wontfix
status-b2g-v2.0: affected → fixed
status-firefox25: affected → wontfix
status-firefox26: affected → wontfix
status-firefox27: affected → wontfix
status-firefox28: affected → wontfix
tracking-b2g18: ? → ---
tracking-b2g-v1.2: ? → ---
tracking-b2g-v1.3: ? → ---
tracking-firefox29: ? → ---
tracking-firefox30: ? → ---
tracking-firefox31: ? → ---
tracking-firefox-esr24: ? → ---
(Assignee)

Comment 23

5 years ago
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.

Updated

5 years ago
status-b2g-v1.3: affected → wontfix
status-b2g-v1.3T: affected → wontfix

Updated

5 years ago
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)
https://hg.mozilla.org/releases/mozilla-aurora/rev/e0cac690e8ae
https://hg.mozilla.org/releases/mozilla-beta/rev/9ed2ec49735e
status-b2g-v1.4: affected → fixed
status-firefox29: affected → fixed
status-firefox30: affected → fixed
(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 → ---
Created attachment 8400282 [details]
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.
(Assignee)

Comment 32

5 years ago
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)
(Assignee)

Comment 34

5 years ago
Created attachment 8403546 [details] [diff] [review]
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.
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)
status-firefox-esr24: affected → wontfix
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)
(Assignee)

Comment 42

4 years ago
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
Last Resolved: 5 years ago4 years ago
Flags: needinfo?(sstangl)
Resolution: --- → WONTFIX

Comment 43

4 years ago
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.