Last Comment Bug 679986 - Assertion failure: limit >= start, at jsregexpinlines.h:274 or Crash [@ QuoteString]
: Assertion failure: limit >= start, at jsregexpinlines.h:274 or Crash [@ Quote...
Status: VERIFIED FIXED
[sg:high][qa-] js-triage-done wanted-...
: assertion, crash, regression, testcase
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: x86 Linux
: -- critical (vote)
: mozilla9
Assigned To: David Mandelin [:dmandelin]
:
Mentors:
: 685477 687302 (view as bug list)
Depends on:
Blocks: 346230 625600
  Show dependency treegraph
 
Reported: 2011-08-17 21:41 PDT by Christian Holler (:decoder)
Modified: 2013-01-14 07:48 PST (History)
10 users (show)
choller: in‑testsuite+
See Also:
Crash Signature:
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---
-
unaffected
-
unaffected
-
wontfix
+
affected
+
fixed
fixed
unaffected


Attachments
Patch (1.80 KB, patch)
2011-10-21 18:16 PDT, David Mandelin [:dmandelin]
cdleary: review+
Details | Diff | Splinter Review
Deoptimization patch (1.80 KB, patch)
2011-10-26 11:11 PDT, David Mandelin [:dmandelin]
cdleary: review+
Details | Diff | Splinter Review
Deoptimization patch, fixed tabs (1.98 KB, patch)
2011-10-31 16:09 PDT, David Mandelin [:dmandelin]
no flags Details | Diff | Splinter Review

Description Christian Holler (:decoder) 2011-08-17 21:41:25 PDT
The following test asserts on mozilla-central (tested revision 7054f0e3e70e) when run with options "-j -m". Stepping through violates several more asserts and then crashes, the optimized build also crashes. I also verified this crash with Firefox 7.0a2 (see bp-7c8779d1-ac27-4f72-ae94-71a762110817). Test was produced by Jesse's RegExp fuzzer:


function testRegexp(res, mode, strings) {
  try { 
    re = new RegExp(res, mode);
    for (var i = 0; i < strings.length; ++i) {
      var str = strings[i];
      var execResult = re.exec(str);
      uneval(execResult);
    }
  } catch(e) { 
  }
}
testRegexp("(?:\\3{0}|\\2\\1)+", "i", ["", "", "\x7F\x7F", "", "", "", "", "mmmm_mmmm_", "", ""]);


The nature of the crash and the assert make me believe that this is exploitable with high probability. Backtrace:


==29756== Invalid read of size 2
==29756==    at 0x4B8270: QuoteString(js::Sprinter*, JSString*, unsigned int) (jsopcode.cpp:780)
==29756==    by 0x4B85BB: js_QuoteString (jsopcode.cpp:844)
==29756==    by 0x520D46: js_ValueToSource(JSContext*, js::Value const&) (jsstr.cpp:3489)
==29756==    by 0x42B187: array_toSource(JSContext*, unsigned int, js::Value*) (jsarray.cpp:1196)
==29756==    by 0x486659: js::Invoke(JSContext*, js::CallArgs const&, js::MaybeConstruct) (jscntxtinlines.h:281)
==29756==    by 0x486C78: js::ExternalInvoke(JSContext*, js::Value const&, js::Value const&, unsigned int, js::Value*, js::Value*) (jsinterp.h:169)
==29756==    by 0x520DE4: js_ValueToSource(JSContext*, js::Value const&) (jsstr.cpp:3507)
==29756==    by 0x520E2B: str_uneval(JSContext*, unsigned int, js::Value*) (jsstr.cpp:308)
==29756==    by 0x486659: js::Invoke(JSContext*, js::CallArgs const&, js::MaybeConstruct) (jscntxtinlines.h:281)
==29756==    by 0x682099: js::Interpret(JSContext*, js::StackFrame*, js::InterpMode) (jsinterp.cpp:4016)
==29756==    by 0x487103: js::ExternalExecute(JSContext*, JSScript*, JSObject&, js::Value*) (jsinterp.cpp:912)
==29756==    by 0x4152B7: JS_ExecuteScript (jsapi.cpp:4926)
==29756==  Address 0x4200000 is not stack'd, malloc'd or (recently) free'd
Comment 1 Christian Holler (:decoder) 2011-08-18 09:45:54 PDT
autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   70607:cc36a234d0d6
user:        David Mandelin
date:        Thu May 12 18:39:47 2011 -0700
summary:     Bug 625600: Update Yarr import to WebKit rev 86639, r=cdleary,dvander
Comment 2 Christian Holler (:decoder) 2011-08-25 18:15:28 PDT
The following test was found by LangFuzz with the regular expression extension:

re = new RegExp("(((..).)|(.))+?a[b-m]|\(\1\)*\(x\)" , "i");
re.exec("aaaaaaceax");

It looks different but the assertion is the same and the bisect points to the same changeset (though that changeset probably includes lots of changes). It does not crash though. If this is a different bug, please let me know and I'll file it separately.
Comment 3 Johnny Stenback (:jst, jst@mozilla.com) 2011-09-01 13:30:58 PDT
Chris, any updates here? Seems it's too late to take this for 7, unless this is a trivial fix we can do in the next couple of days or so...
Comment 4 Brandon Sterne (:bsterne) 2011-09-06 09:19:09 PDT
Our opinion is that this bug should be easily discoverable by anyone with a RegExp fuzzer, so we need to prioritize fixing this bug ASAP.
Comment 5 David Mandelin [:dmandelin] 2011-09-07 18:51:58 PDT
Filed https://bugs.webkit.org/show_bug.cgi?id=67752
Comment 6 David Mandelin [:dmandelin] 2011-09-07 18:52:42 PDT
This asserts because Yarr::execute returns 0 (indicating a match) but the |output| buffer has invalid data. The first pair is (0, -2), which is supposed to be (start, end), so clearly that's not right.

I noticed that the test regexp has backreferences, but no capturing parens, so that might be the source of the problem. The spec seems to say that's "an error", but both Chrome and IE run this without throwing. It looks like V8 converts any backreference to a capturing group that hasn't been seen yet into an empty pattern. Yarr seems to convert those to a ForwardReference, which then has empty cases later, presumably to get the same effect.

When I debug through YarrJIT, I see that it's compiling "TypePatternCharacter" terms where I would expect to see the ForwardReferences. Very strange. Just before the return, the generated code has "sub edx, 2", presumably to bump the pointer back after it was bumped forward to try to match the putative length-2 subpattern. That's where the -2 comes from in |output|.
Comment 7 David Mandelin [:dmandelin] 2011-09-07 18:53:02 PDT
(In reply to Christian Holler (:decoder) from comment #2)
> The following test was found by LangFuzz with the regular expression
> extension:
> 
> re = new RegExp("(((..).)|(.))+?a[b-m]|\(\1\)*\(x\)" , "i");
> re.exec("aaaaaaceax");
> 
> It looks different but the assertion is the same and the bisect points to
> the same changeset (though that changeset probably includes lots of
> changes). It does not crash though. If this is a different bug, please let
> me know and I'll file it separately.

Please file separately, I think it's a different bug.
Comment 8 Chris Leary [:cdleary] (not checking bugmail) 2011-09-26 16:25:55 PDT
(In reply to David Mandelin from comment #6)

I'm pretty sure that we have a non-standard extension to change \5 into the literal character 5 whenever 5 (or any other single digit character) > the number of capturing groups. We really should start documenting these things (I should have done it when I was encountering all this junk in the YARR port).
Comment 9 David Mandelin [:dmandelin] 2011-10-21 16:42:14 PDT
Here is a reduced test case:

  "".match(/(?:|a)+/);

Note that it doesn't have any backrefs. Chris is right: invalid backrefs get converted to octal escapes in Yarr as well: this was intentional behavior to match Firefox. It appears the key is to have an empty first alternative inside a quantified group, which I think Christian pointed out somewhere. Some of the other Yarr bugs are probably also of this type. Continuing to investigate.
Comment 10 David Mandelin [:dmandelin] 2011-10-21 18:16:10 PDT
Created attachment 568835 [details] [diff] [review]
Patch

I'm going to ask about this patch in the WebKit bug. It fixes the assert and passes all of our tests.
Comment 11 David Mandelin [:dmandelin] 2011-10-21 18:54:50 PDT
See https://bugs.webkit.org/show_bug.cgi?id=67752#c5 and also comment 6 for a detailed explanation of the problem and the patch I just posted.
Comment 12 Chris Leary [:cdleary] (not checking bugmail) 2011-10-22 09:53:57 PDT
Comment on attachment 568835 [details] [diff] [review]
Patch

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

Can we add the /(?:a|aa)*/ test that I believe we said suffers from the same problem?
Comment 13 David Mandelin [:dmandelin] 2011-10-26 11:11:20 PDT
Created attachment 569733 [details] [diff] [review]
Deoptimization patch

The previous patch is incorrect--it doesn't handle these test cases correctly. I decided that it's going to be easiest to fix this in the short term by turning off the optimization in the cases in which it's unsafe. Chris and I talked about what's going on already, and a summary is given in the comment in the patch.
Comment 14 David Mandelin [:dmandelin] 2011-10-26 11:13:31 PDT
*** Bug 685477 has been marked as a duplicate of this bug. ***
Comment 15 David Mandelin [:dmandelin] 2011-10-26 11:15:26 PDT
*** Bug 687302 has been marked as a duplicate of this bug. ***
Comment 16 Chris Leary [:cdleary] (not checking bugmail) 2011-10-31 11:17:16 PDT
Comment on attachment 569733 [details] [diff] [review]
Deoptimization patch

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

Looks like some hard tabs accidentally snuck in there.
Comment 17 David Mandelin [:dmandelin] 2011-10-31 16:09:26 PDT
Created attachment 570878 [details] [diff] [review]
Deoptimization patch, fixed tabs
Comment 18 Christian Holler (:decoder) 2011-11-01 10:59:28 PDT
After closer inspection, this seems to be sg:high (it looks like an invalid read due to an integer overflow, but the read is not influencing control flow but rather the memory areas read are processed as data and might be leaked at some point). If this is wrong, feel free to correct my rating.
Comment 19 David Mandelin [:dmandelin] 2011-11-03 14:41:38 PDT
I told WebKit we would land this Monday, Nov 7 unless they tell us otherwise. I'll be traveling, so cdleary will coordinate the landing.
Comment 20 Chris Leary [:cdleary] (not checking bugmail) 2011-11-07 12:22:25 PST
So I landed this on inbound and aurora. From the bug, I'm not clear about our intent to land this in mozilla-beta. My guess would be yes from the bug history, but after the downgrade to sg:high I'm not totally clear. jst, any guidance there? (Sorry, should have clarified this with dmandelin before he took off.)
Comment 21 Chris Leary [:cdleary] (not checking bugmail) 2011-11-07 16:07:29 PST
https://hg.mozilla.org/integration/mozilla-inbound/rev/ad6b14835247
http://hg.mozilla.org/releases/mozilla-aurora/rev/a78bbe2376be

Holding off on FF8...
Comment 22 Justin Wood (:Callek) 2011-11-08 01:24:46 PST
https://hg.mozilla.org/mozilla-central/rev/ad6b14835247 for gecko 10

(In reply to Chris Leary [:cdleary] from comment #21)
> Holding off on FF8...

Which is shipping tomorrow, so unless there is a chemspill won't be in there

Also chris, it doesn't *look* like this bug had an aurora approval either (sec bugs, afaik still need approvals)
Comment 23 Anthony Hughes (:ashughes) [GFX][QA][Mentor] 2011-11-21 16:44:55 PST
Is there something QA can do to verify this fix?
Comment 24 David Mandelin [:dmandelin] 2011-11-21 16:56:17 PST
(In reply to Anthony Hughes, Mozilla QA (irc: ashughes) from comment #23)
> Is there something QA can do to verify this fix?

No, the test cases we added should be enough.
Comment 25 Christian Holler (:decoder) 2013-01-14 07:48:50 PST
A testcase for this bug was automatically identified at js/src/jit-test/tests/basic/bug679986-2.js.

Note You need to log in before you can comment on or make changes to this bug.