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

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

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

Comment 1

[Christian Holler (:decoder)]

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

Comment 2

[Christian Holler (:decoder)]

Easier test:


"".match(/(?:(?=g)).{2147483648,}/ + "");

Comment 3

[Marty Rosenberg [:mjrosenb]]

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.

Comment 4

[Christian Holler (:decoder)]

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.

Comment 5

[Christian Holler (:decoder)]

JSBugMon: Cannot process bug: Unknown exception (check manually)

Comment 6

[Christian Holler (:decoder)]

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

Comment 7

[Christian Holler (:decoder)]

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

Comment 8

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

Attachment: 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.

Comment 9

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

Hannes, how should we move this forward?

Comment 10

[Hannes Verschore [:h4writer]]

Attachment: Making jit creation fallible

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

Comment 11

[Hannes Verschore [:h4writer]]

Attachment: Part 1: revert bug 872971

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.

Comment 12

[Hannes Verschore [:h4writer]]

Attachment: Part 2: Make generate function fallible

No observable changes. This just makes all "generate*" functions "return true" upon success. Upon "return false" the regexp get annotated to use the interpreter.

Comment 13

[Hannes Verschore [:h4writer]]

Attachment: Part 3: Check for overflow when setting m_checked

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.

Comment 14

[Hannes Verschore [:h4writer]]

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 15

[Till Schneidereit [:till]]

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)

Comment 16

[Till Schneidereit [:till]]

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/

Comment 17

[Till Schneidereit [:till]]

Comment on attachment 8399925 [details] [diff] [review]
Part 3: Check for overflow when setting m_checked

yup

Comment 18

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/20f9666aff6c

Comment 19

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/20f9666aff6c

Comment 20

[Firefox Commit Bot]

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

Comment 21

[Christian Holler (:decoder)]

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.

Comment 22

[Hannes Verschore [:h4writer]]

Going to take over the needinfo, since it is actually my patch.

Comment 23

[Hannes Verschore [:h4writer]]

Attachment: Aggressively check all "Checked" uses

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

Comment 24

[Hannes Verschore [:h4writer]]

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

[Till Schneidereit [:till]]

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.

Comment 26

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/133eecf5f0f0

Comment 27

[Hannes Verschore [:h4writer]]

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:
/

Comment 28

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/b7c28ae27595