YARR Assertion Failure with Crash [@ WTF::CrashOnOverflow::overflowed]

RESOLVED FIXED in Firefox 31

Status

()

defect
--
critical
RESOLVED FIXED
7 years ago
5 years ago

People

(Reporter: decoder, Assigned: h4writer)

Tracking

(Blocks 1 bug, {assertion, testcase})

Trunk
mozilla32
x86_64
Linux
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(firefox31 fixed, firefox32 fixed)

Details

(Whiteboard: [jsbugmon:])

Attachments

(6 attachments, 1 obsolete attachment)

Reporter

Description

7 years ago
The following testcase asserts on mozilla-central revision fc1684f4d3a9 (no options required):


var a = [ (/(?:(?=g)).{2147483648,}/), ];
for (var j = 0; j < 200; ++j) {
  var js = "" + j;
  for (var i = 0; i < a.length; i++)
     "".match(a[i] + js)
}
Reporter

Comment 1

7 years ago
Not sure if this is actually a security problem, but from the crash trace and the function/file names it looks like arithmetic is overflowing although it should not (but the condition is recognized and the program aborted):


Program received signal SIGSEGV, Segmentation fault.
0x0000000000970795 in WTF::CrashOnOverflow::overflowed (this=0x7fffffffa930) at /srv/repos/mozilla-central/js/src/yarr/CheckedArithmetic.h:79
79              CRASH();
(gdb) bt
#0  0x0000000000970795 in WTF::CrashOnOverflow::overflowed (this=0x7fffffffa930) at /srv/repos/mozilla-central/js/src/yarr/CheckedArithmetic.h:79
#1  0x00000000009a2fb6 in WTF::Checked<int, WTF::CrashOnOverflow>::Checked<long> (this=0x7fffffffa930, rhs=...) at /srv/repos/mozilla-central/js/src/yarr/CheckedArithmetic.h:455
#2  0x00000000009a0c8c in JSC::Yarr::YarrGenerator<(JSC::Yarr::YarrJITCompileMode)1>::generateCharacterClassFixed (this=0x7fffffffb3e0, opIndex=11) at /srv/repos/mozilla-central/js/src/yarr/YarrJIT.cpp:1019
#3  0x0000000000999e0c in JSC::Yarr::YarrGenerator<(JSC::Yarr::YarrJITCompileMode)1>::generateTerm (this=0x7fffffffb3e0, opIndex=11) at /srv/repos/mozilla-central/js/src/yarr/YarrJIT.cpp:1233
#4  0x0000000000995b72 in JSC::Yarr::YarrGenerator<(JSC::Yarr::YarrJITCompileMode)1>::generate (this=0x7fffffffb3e0) at /srv/repos/mozilla-central/js/src/yarr/YarrJIT.cpp:1350
#5  0x000000000099140c in JSC::Yarr::YarrGenerator<(JSC::Yarr::YarrJITCompileMode)1>::compile (this=0x7fffffffb3e0, globalData=0x7fffffffba70, jitObject=...) at /srv/repos/mozilla-central/js/src/yarr/YarrJIT.cpp:2648
#6  0x00000000009905f0 in JSC::Yarr::jitCompile (pattern=..., charSize=JSC::Yarr::Char16, globalData=0x7fffffffba70, jitObject=..., mode=JSC::Yarr::IncludeSubpatterns)
    at /srv/repos/mozilla-central/js/src/yarr/YarrJIT.cpp:2711
#7  0x0000000000784d6f in js::detail::RegExpCode::compile (this=0xee75b0, cx=0xedf440, pattern=..., parenCount=0xee75f0, flags=js::NoFlags) at /srv/repos/mozilla-central/js/src/vm/RegExpObject.cpp:201
Reporter

Comment 2

7 years ago
Easier test:


"".match(/(?:(?=g)).{2147483648,}/ + "");
Looks like CRASH is defined to MOZ_CRASH, and WTF::Checked<...> is set up to always perform these checks, so the regex jitter will never access any bad memory due to this.
That being said, the problem is almost certainly attempting to look (unsigned int)INT_MIN characters ahead.
Group: core-security
Reporter

Updated

6 years ago
Whiteboard: [jsbugmon:update,bisect]
Reporter

Updated

6 years ago
Whiteboard: [jsbugmon:update,bisect] → [jsbugmon:update]
Reporter

Comment 4

6 years ago
JSBugMon: Bisection requested, result:
autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   112142:8bf2f8cb5e73
user:        David Anderson
date:        Thu Nov 01 21:35:25 2012 -0700
summary:     Update Yarr to WebKit rev 130234 (bug 740015, r=dmandelin).

This iteration took 97.015 seconds to run.
Reporter

Updated

6 years ago
Whiteboard: [jsbugmon:update] → [jsbugmon:]
Reporter

Comment 5

6 years ago
JSBugMon: Cannot process bug: Unknown exception (check manually)
Whiteboard: [jsbugmon:] → [jsbugmon:update]
Reporter

Updated

5 years ago
Whiteboard: [jsbugmon:update] → [jsbugmon:]
Reporter

Comment 7

5 years ago
JSBugMon: Cannot process bug: Error: Failed to compile specified revision fc1684f4d3a9 (maybe try another?)
Posted file stack
Testing the testcase in comment 2, it seems to be fixed by bug 872971.

autoBisect shows this is probably related to the following changeset:

The first good revision is:
changeset:   http://hg.mozilla.org/mozilla-central/rev/ff67c72677a6
user:        Till Schneidereit
date:        Wed Dec 18 16:45:26 2013 +0100
summary:     Bug 872971 - Clamp regexp quantifiers to INT_MAX. r=jandem

However, the testcase in comment 0 still seems to reproduce (see attached stack), on a 64-bit debug threadsafe shell on Mac m-c rev 9afe2a1145bd.
Hannes, how should we move this forward?
Flags: needinfo?(hv1989)
Assignee

Comment 10

5 years ago
Posted patch Making jit creation fallible (obsolete) — Splinter Review
(In reply to Gary Kwong [:gkw] [:nth10sd] from comment #9)
> Hannes, how should we move this forward?

By fixing off course ;)

Putting an unsigned into a signed without checking is never a good idea. So I made jit generation fallible and fallback to the yarr interpreter for these edge cases. I think that's the best way, since I'm pretty sure this is not the only place we will see this pop up. So this will make it easier to fix other problems.
Flags: needinfo?(hv1989)
Assignee

Updated

5 years ago
Assignee: general → hv1989
Assignee

Comment 11

5 years ago
Posting in 3 patches to make difference more obvious. I will land as 1 patch.
Part 1 removes the workaround in bug 872971. Since it will not be needed anymore after this fix.
Attachment #8398775 - Attachment is obsolete: true
Attachment #8399921 - Flags: review?(till)
Assignee

Comment 12

5 years ago
No observable changes. This just makes all "generate*" functions "return true" upon success. Upon "return false" the regexp get annotated to use the interpreter.
Attachment #8399922 - Flags: review?(till)
Assignee

Comment 13

5 years ago
m_checked is a signed int32, while m_minimumSize is a unsigned int32. So we need to check if m_minimumSize fits into the signed int32. If not, we fail the generate function.
Attachment #8399925 - Flags: review?(till)
Assignee

Comment 14

5 years ago
Comment on attachment 8399922 [details] [diff] [review]
Part 2: Make generate function fallible

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

::: js/src/tests/js1_8_5/regress/regress-yarr-regexp.js
@@ +16,5 @@
>  reportCompare(/x{2147483648,}x/.test('1'), false);
>  reportCompare(/x{2147483647,2147483648}x/.test('1'), false);
> +// Some for these. See bug 813366
> +reportCompare("".match(/.{2147483647}11/), null);
> +reportCompare("".match(/(?:(?=g)).{2147483648,}/ + ""), null);

Nit: I should have only added this as part 3 actually. Sorry for this bad split.

::: js/src/yarr/YarrJIT.cpp
@@ +754,1 @@
>          

Nit: remove whitespace while I'm here.

@@ +819,5 @@
>  
>              allCharacters |= (currentCharacter << shiftAmount);
>  
>              if ((m_pattern.m_ignoreCase) && (isASCIIAlpha(currentCharacter)))
>                  ignoreCaseMask |= 32 << shiftAmount;                    

Nit: remove whitespace while I'm here.

@@ +1225,5 @@
>      void backtrackDotStarEnclosure(size_t opIndex)
>      {
>          backtrackTermDefault(opIndex);
>      }
>      

Nit: Remove whitespace while I'm here.
Comment on attachment 8399921 [details] [diff] [review]
Part 1: revert bug 872971

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

Nice to see this removed (but please really do fold it into one patch with the rest, for bisecting-sanity)
Attachment #8399921 - Flags: review?(till) → review+
Comment on attachment 8399922 [details] [diff] [review]
Part 2: Make generate function fallible

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

r=me

Discussions on IRC have resulted in the conclusion that, technically, it'd be cleaner to also make `fallback` fallible. It isn't, however, required for correctness, and with Yarr being on the way out, it doesn't make sense to introduce churn.

::: js/src/tests/js1_8_5/regress/regress-yarr-regexp.js
@@ +14,5 @@
>  // These just mustn't crash. See bug 872971
>  reportCompare(/x{2147483648}x/.test('1'), false);
>  reportCompare(/x{2147483648,}x/.test('1'), false);
>  reportCompare(/x{2147483647,2147483648}x/.test('1'), false);
> +// Some for these. See bug 813366

s/Some/Same/
Attachment #8399922 - Flags: review?(till) → review+
Comment on attachment 8399925 [details] [diff] [review]
Part 3: Check for overflow when setting m_checked

yup
Attachment #8399925 - Flags: review?(till) → review+
https://hg.mozilla.org/mozilla-central/rev/20f9666aff6c
Status: NEW → RESOLVED
Closed: 5 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla31
The following changeset is now in Firefox Nightly:

> 20f9666aff6c Bug 813366 - Fix handling of failing to create jit code in yarr, r=till

Nightly Build Information:

        ID: 20140402030201
 Changeset: 4941a2ac0786109b08856738019b016a6c5a66a6
   Version: 31.0a1
      TBPL: https://tbpl.mozilla.org/?rev=4941a2ac0786
       URL: https://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/2014/04/2014-04-02-03-02-01-mozilla-central

Download Links:

>         Linux x86: https://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/2014/04/2014-04-02-03-02-01-mozilla-central/firefox-31.0a1.en-US.linux-i686.tar.bz2
>      Linux x86_64: https://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/2014/04/2014-04-02-03-02-01-mozilla-central/firefox-31.0a1.en-US.linux-x86_64.tar.bz2
> Linux x86_64 ASAN: https://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/2014/04/2014-04-02-03-02-01-mozilla-central/firefox-31.0a1.en-US.linux-x86_64-asan.tar.bz2
>               Mac: https://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/2014/04/2014-04-02-03-02-01-mozilla-central/firefox-31.0a1.en-US.mac.dmg
>             Win32: https://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/2014/04/2014-04-02-03-02-01-mozilla-central/firefox-31.0a1.en-US.win32.installer.exe
>             Win64: https://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/2014/04/2014-04-02-03-02-01-mozilla-central/firefox-31.0a1.en-US.win64-x86_64.installer.exe

Previous Nightly Build Information:

        ID: 20140401030203
 Changeset: 1417d180a1d8665b1a91b897d1cc4cc31e7980d4
   Version: 31.0a1
      TBPL: https://tbpl.mozilla.org/?rev=1417d180a1d8
       URL: https://ftp.mozilla.org/pub/mozilla.org/firefox/nightly/2014/04/2014-04-01-03-02-03-mozilla-central
Reporter

Comment 21

5 years ago
This test still crashes for me on mozilla-central revision ac376a4e8174:


var re = new RegExp("(?:/.{2147483647}11/)*");
'8:5-8'.match(re);


Looks exactly the same as the tests above and has the same signature. Till, can you check if your fix is complete? Thanks.
Status: RESOLVED → REOPENED
Flags: needinfo?(till)
Resolution: FIXED → ---
Assignee

Comment 22

5 years ago
Going to take over the needinfo, since it is actually my patch.
Flags: needinfo?(till) → needinfo?(hv1989)
Assignee

Comment 23

5 years ago
1) Use "RecordOverflow" instead of "CrashOnOverflow" when checking.
Note: this still crashes. The difference is that CrashOnOverflow crashes immediately, giving no time to check and report overflows. RecordOverflow only crashes when using unsafeGet(). Which actually mean the same visual behaviour, only the possibility to check it now.
2) Change all uses of unsafeGet into "safeGet" or add check "hasOverflown" in YarrParser and YarrJIT
3) Added some extra overflow checks when doing "term.inputPosition = currentInputPosition". (@Webkit devs: Unsigned to int transformation is not safe)

Note: I didn't do the YarrInterpreter.cpp unsafeGet transforms. I eyeballed the code and the few checks that are in there shouldn't trigger. The information is created in the Parser. So should already have been checked. (So those will still crash).
Attachment #8411778 - Flags: review?(till)
Flags: needinfo?(hv1989)
Assignee

Comment 24

5 years ago
(In reply to Christian Holler (:decoder) from comment #21)
> var re = new RegExp("(?:/.{2147483647}11/)*");
> '8:5-8'.match(re);

So the currently happens in YarrJIT, but actually something wrong already happened in the parser (unsigned to int). It now gives the following error:
/tmp/test37.js:2:0 InternalError: an error occurred while executing regular expression
Comment on attachment 8411778 [details] [diff] [review]
Aggressively check all "Checked" uses

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

Returning `true` on failure: *such* a weird decision. After adapting to that, I liked how much clearer some of the code became, actually.
Attachment #8411778 - Flags: review?(till) → review+
https://hg.mozilla.org/mozilla-central/rev/133eecf5f0f0
Status: REOPENED → RESOLVED
Closed: 5 years ago5 years ago
Resolution: --- → FIXED
Assignee

Comment 27

5 years ago
Comment on attachment 8411778 [details] [diff] [review]
Aggressively check all "Checked" uses

[Approval Request Comment]
Bug caused by (feature/regressing bug #): 
bug 740015, Yarr import

User impact if declined: 
Deliberate (safe) crashes on certain regexps

Testing completed (on m-c, etc.): 
few days m-i/m-c

Risk to taking this patch (and alternatives if risky): 
Risk should be low. It adjust our path of crashing into using the normal way to report an error. The patch is very mechanical of scope (as in changing everything into if(!...) return false). Nothing strange or unknown. We could decide not to uplift, since it is not a new regression. But finally lets get all these possible crashes away! Also the other patches landed in FF31+. Only this patch is FF32+. I didn't create a new bug report by accident.

String or IDL/UUID changes made by this patch:
/
Attachment #8411778 - Flags: approval-mozilla-aurora?
Attachment #8411778 - Flags: approval-mozilla-aurora? → approval-mozilla-aurora+
Target Milestone: mozilla31 → mozilla32
You need to log in before you can comment on or make changes to this bug.