Assertion failure: limit >= start, at jsregexpinlines.h:274 or Crash [@ QuoteString]

VERIFIED FIXED in Firefox 9

Status

()

Core
JavaScript Engine
--
critical
VERIFIED FIXED
6 years ago
5 years ago

People

(Reporter: decoder, Assigned: dmandelin)

Tracking

(Blocks: 1 bug, 4 keywords)

Trunk
mozilla9
x86
Linux
assertion, crash, regression, testcase
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(firefox5- unaffected, firefox6- unaffected, firefox7- wontfix, firefox8+ affected, firefox9+ fixed, firefox10 fixed, status1.9.2 unaffected)

Details

(Whiteboard: [sg:high][qa-] js-triage-done wanted-standalone-js, crash signature)

Attachments

(2 attachments, 1 obsolete attachment)

(Reporter)

Description

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

Updated

6 years ago
Blocks: 346230
(Reporter)

Comment 1

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

Updated

6 years ago
status-firefox5: --- → unaffected
status-firefox6: --- → unaffected
status-firefox7: --- → affected
status-firefox8: --- → affected
status-firefox9: --- → affected
tracking-firefox5: --- → -
tracking-firefox6: --- → -
tracking-firefox7: --- → +
tracking-firefox8: --- → +
tracking-firefox9: --- → +

Updated

6 years ago
Blocks: 625600
Keywords: regression
Assignee: general → cdleary
(Reporter)

Comment 2

6 years ago
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.
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...
status-firefox7: affected → wontfix
tracking-firefox7: + → -
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.
(Assignee)

Comment 5

6 years ago
Filed https://bugs.webkit.org/show_bug.cgi?id=67752
(Assignee)

Comment 6

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

Comment 7

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

Updated

6 years ago
Whiteboard: [sg:critical?] js-triage-needed → [sg:critical?] js-triage-needed wanted-standalone-js
(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).
(Assignee)

Comment 9

6 years ago
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.
Assignee: cdleary → dmandelin
(Assignee)

Comment 10

6 years ago
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.
Attachment #568835 - Flags: review?(cdleary)
(Assignee)

Comment 11

6 years ago
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.
status1.9.2: --- → unaffected
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?
Attachment #568835 - Flags: review?(cdleary) → review+
(Assignee)

Comment 13

6 years ago
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.
Attachment #568835 - Attachment is obsolete: true
Attachment #569733 - Flags: review?(cdleary)
(Assignee)

Updated

6 years ago
Duplicate of this bug: 685477
(Assignee)

Updated

6 years ago
Duplicate of this bug: 687302
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.
Attachment #569733 - Flags: review?(cdleary) → review+
(Assignee)

Comment 17

6 years ago
Created attachment 570878 [details] [diff] [review]
Deoptimization patch, fixed tabs
(Reporter)

Comment 18

6 years ago
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.
Whiteboard: [sg:critical?] js-triage-needed wanted-standalone-js → [sg:high] js-triage-needed wanted-standalone-js
(Assignee)

Comment 19

6 years ago
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.
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.)
https://hg.mozilla.org/integration/mozilla-inbound/rev/ad6b14835247
http://hg.mozilla.org/releases/mozilla-aurora/rev/a78bbe2376be

Holding off on FF8...
Target Milestone: --- → mozilla9
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)
Status: NEW → RESOLVED
Last Resolved: 6 years ago
status-firefox10: --- → fixed
status-firefox9: affected → fixed
Resolution: --- → FIXED
Is there something QA can do to verify this fix?
Whiteboard: [sg:high] js-triage-needed wanted-standalone-js → [sg:high][qa?] js-triage-needed wanted-standalone-js
(Assignee)

Comment 24

6 years ago
(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.
Whiteboard: [sg:high][qa?] js-triage-needed wanted-standalone-js → [sg:high][qa-] js-triage-needed wanted-standalone-js
Whiteboard: [sg:high][qa-] js-triage-needed wanted-standalone-js → [sg:high][qa-] js-triage-done wanted-standalone-js
Group: core-security
(Reporter)

Updated

6 years ago
Status: RESOLVED → VERIFIED
(Reporter)

Comment 25

5 years ago
A testcase for this bug was automatically identified at js/src/jit-test/tests/basic/bug679986-2.js.
Flags: in-testsuite+
You need to log in before you can comment on or make changes to this bug.