Closed Bug 813366 Opened 12 years ago Closed 10 years ago

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

Categories

(Core :: JavaScript Engine, defect)

x86_64
Linux
defect
Not set
critical

Tracking

()

RESOLVED FIXED
mozilla32
Tracking Status
firefox31 --- fixed
firefox32 --- fixed

People

(Reporter: decoder, Assigned: h4writer)

Details

(Keywords: assertion, testcase, Whiteboard: [jsbugmon:])

Attachments

(6 files, 1 obsolete file)

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)
}
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
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
Whiteboard: [jsbugmon:update,bisect]
Whiteboard: [jsbugmon:update,bisect] → [jsbugmon:update]
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.
Whiteboard: [jsbugmon:update] → [jsbugmon:]
JSBugMon: Cannot process bug: Unknown exception (check manually)
Whiteboard: [jsbugmon:] → [jsbugmon:update]
Whiteboard: [jsbugmon:update] → [jsbugmon:]
JSBugMon: Cannot process bug: Error: Failed to compile specified revision fc1684f4d3a9 (maybe try another?)
Attached 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)
Attached 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: general → hv1989
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)
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)
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)
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: 10 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
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 → ---
Going to take over the needinfo, since it is actually my patch.
Flags: needinfo?(till) → needinfo?(hv1989)
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)
(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: 10 years ago10 years ago
Resolution: --- → FIXED
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.