230216 - No overflow check for regexp back reference and quantifier bounds

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Igor Bukanov]

Currently SpiderMonkey does not check against numerical overflow in regexps in
back reference and bounds for {} quantifier. For example, the following code:
/(a)\21474836481/.test("aa")
instead of expected error about too big number gives true in js shell since
21474836481 overflows as 1.

Similarly 
/a{21474836481}/.test("a")
also produces true.

More dangerous case is /a\21474836480/.test("") where 21474836480 is treated as
0 which leads to call to backrefMatcher in jsregexp.c with length set to
4294967295 or (uint)-1 and thus accessing REMatchState->parens[-1]. In principle
this can lead to a crash although I was not able to trigger it.

Comment 1

[Igor Bukanov]

CC Brendan to look at it

Comment 2

[Igor Bukanov]

Attachment: Fix: GetDecimalValue in jsregexp.c takes max allowed value argument

The patch also makes sure that parenIndex declared in various structs always
uses uin16 type instead of the current mixture of uin16/intN/jsint

Comment 3

[Igor Bukanov]

Attachment: Patch fix: proper JC_ASSERT and more typeupdate for parentCount

Comment 4

[Brendan Eich [:brendan]]

Attachment: proposed fix based on igor's patch

Fixed GetDecimalValue to check for overflow on first character, simplified
strict check for invalid/bad backref, added invalid backref strict
check/warning for \0.

/be

Comment 5

[Brendan Eich [:brendan]]

Comment on attachment 148389 [details] [diff] [review]
proposed fix based on igor's patch

Trying to get this in for RC2's build tomorrow.

/be

Comment 6

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Comment on attachment 148389 [details] [diff] [review]
proposed fix based on igor's patch

sr=shaver

Comment 7

[Asa Dotzler [:asa]]

Comment on attachment 148389 [details] [diff] [review]
proposed fix based on igor's patch

a=asa (on behalf of drivers) for checkin to 1.7

Comment 8

[Brendan Eich [:brendan]]

Attachment: better fix, handles forward "backrefs"

Given

pattern = /((\3|b)\2(a)x)+/;
string = 'aaxabxbaxbbx';

pattern(string) should return ["ax", "ax", "", "a"], per ECMA-262 Edition 3
15.10.2.9, first production.

Not perl-ish, but that's the way it was standardized.  This patch fixes the
testsuite case that the last patch regressed, but avoids the longstanding hack
of JS_MAX(9, state->parenCount) used to dodge the bullet (with one parsing
pass, state->parenCount will be 2 when \3 is parsed).  To minimize code
footprint for this hard case, I added a lazy reparse of the whole regexp to get
a total count of parentheticals.

/be

Comment 9

[Brendan Eich [:brendan]]

Comment on attachment 148442 [details] [diff] [review]
better fix, handles forward "backrefs"

Sorry to re-request so soon, but I should have run the testsuite.  I wasn't
prepared to turn over this rock and find all the creepy-crawlies, but the patch
isn't too bad, although JSREG_TEMP_STATE is a hack.

I suppose if there's an error later in the regexp, the nested, lazy reparse
will report it, but the error will be ignored and we'll re-report it.  I'd like
to fix that later, on the 1.8 trunk.  I'll leave this bug open.

/be

Comment 10

[Asa Dotzler [:asa]]

Comment on attachment 148442 [details] [diff] [review]
better fix, handles forward "backrefs"

a=asa (on behalf of drivers) for checkin to 1.7

Comment 11

[Brendan Eich [:brendan]]

Attachment: What I checked in on the trunk

I added the error propagation with the least additional code possible.

/be

Comment 12

[Brendan Eich [:brendan]]

Fixed on trunk and branch.

/be

Comment 13

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/Regress/regress-230216-1.js

Igor's test 1

Comment 14

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/Regress/regress-230216-2.js

Igor's test 2. Igor, with your permission these two tests will be included in
the javascript test library.

Comment 15

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/Regress/regress-230216-3.js

thanks to be.

Comment 16

[Bob Clary [:bc] (inactive)]

js1_5/Regress/regress-230216-1.js, js1_5/Regress/regress-230216-2.js,
js1_5/Regress/regress-230216-3.js checked in.

Comment 17

[Bob Clary [:bc] (inactive)]

verified fixed.