Closed Bug 679986 Opened 9 years ago Closed 8 years ago

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

Categories

(Core :: JavaScript Engine, defect, critical)

x86
Linux
defect
Not set
critical

Tracking

()

VERIFIED FIXED
mozilla9
Tracking Status
firefox5 - unaffected
firefox6 - unaffected
firefox7 - wontfix
firefox8 + affected
firefox9 + fixed
firefox10 --- fixed
status1.9.2 --- unaffected

People

(Reporter: decoder, Assigned: dmandelin)

References

Details

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

Crash Data

Attachments

(2 files, 1 obsolete file)

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
Blocks: 346230
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
Blocks: 625600
Keywords: regression
Assignee: general → cdleary
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...
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.
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|.
(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.
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).
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
Attached patch Patch (obsolete) — Splinter Review
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)
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 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+
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)
Duplicate of this bug: 685477
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+
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
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/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
Closed: 8 years ago
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
(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
Status: RESOLVED → VERIFIED
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.