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

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

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

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

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

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

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]]

Filed https://bugs.webkit.org/show_bug.cgi?id=67752

Comment 6

[David Mandelin [:dmandelin]]

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]]

(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)]

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

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]]

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

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

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]]

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

[Chris Leary [:cdleary] (not checking bugmail)]

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]]

Attachment: Deoptimization patch, fixed tabs

Comment 18

[Christian Holler (:decoder)]

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]]

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

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

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

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

[u279076]

Is there something QA can do to verify this fix?

Comment 24

[David Mandelin [:dmandelin]]

(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)]

A testcase for this bug was automatically identified at js/src/jit-test/tests/basic/bug679986-2.js.