119909 - small number of back references in regular expression (regexp) cause crash

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Stephen Ostermiller]

A regular expression with as few as twenty back references will cause mozilla 
to crash.  I have observed this behaviour using both the split() and replace()
functions.

Comment 1

[Stephen Ostermiller]

Attachment: Testcase that allows the number of parenthesis in a regexp to be specified.

Twenty backreferences will cause a crash.  If backreferences are not selected,
I 
can use over 10,000 parenthesis.

Comment 2

[Stephen Ostermiller]

This is similar to bug 112626 but (I believe) distinct.  That bug only crashes
on Windows and with a single set of parenthesis.

Comment 3

[Olav Vitters]

Attachment: Stacktrace Linux todays CVS (30 back references)

Comment 4

[timeless]

using xpcshell from a fbsd cvs build from about friday
function alert(a){print(a)}
function test (numparens,checked){
    if ('' + numparens != 'NaN' || numparens < 0){
        var toFind = 'hello';
        var toReplace = 'goodbye';
        var regExpStr = '';
        var i;
        var startParen = checked?'(':'(?:';
        for (i=0; i<numparens; i++){
            regExpStr += startParen;
        }
        regExpStr += toFind;
        for (i=0; i<numparens; i++){
            regExpStr += ')';
        }
        alert(toFind + '.replace(\nnew RegExp(\n' + regExpStr + '\n),\n' +
toReplace + '\n);');
        var testRegExp = new RegExp(regExpStr);
        alert(toFind.replace(testRegExp, toReplace));
    } else {
        alert('Positive integer expected');
    }
}
test(2395)
this was the smallest x that i could use to generate a core dump. it's useless
and i'd be shot for providing it.

Note that 2395 didn't always crash (it crashed in all but one attempt

fwiw
Mem: 126M Active, 143M Inact, 79M Wired, 8548K Cache, 61M Buf, 144M Free
Swap: 1024M Total, 261M Used, 763M Free, 25% Inuse

fwiw i had 46209 timeless  48   0 50488K 49196K STOP    13:15  0.00%  0.00%
xpcshell sitting around holding memory (it was building test(1000000) or
something larger..)

#0  0x280ee5c9 in ParseAtom (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:775
#1  0x280ee17b in ParseQuantAtom (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:657
#2  0x280ee148 in ParseItem (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:634
#3  0x280edebb in ParseAltern (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:543
#4  0x280edd27 in ParseRegExp (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:496
#5  0x280ee714 in ParseAtom (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:861
#6  0x280ee17b in ParseQuantAtom (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:657
#7  0x280ee148 in ParseItem (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:634
#8  0x280edebb in ParseAltern (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:543
#9  0x280edd27 in ParseRegExp (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:496
#10 0x280ee714 in ParseAtom (state=0xbfbfcce8) at
/home/timeless/mozilla/js/src/jsregexp.c:861

most of the stack is like 6-10 and it's well over 120 deep.  totally useless
edge case.  something's special about navigator.

Comment 5

[Phil Schwartau]

Testcase added to JS testsuite:

          mozilla/js/tests/ecma_3/RegExp/regress-119909.js

Comment 6

[Phil Schwartau]

Confirming crash on WinNT as well as Linux. OS: Linux ---> All.
Occurs in JS shell and is purely JS Engine; removing jst as a cc.

Comment 7

[Phil Schwartau]

Attachment: Stacktrace WinNT on reduced JS testcase in JS shell

Comment 8

[Phil Schwartau]

Note: in the standalone debug JS shell on WinNT, I had to increase
the number of nested parentheses to 150 or so in order to crash!
And I was only able to crash if the regexp stored the backreferences,
i.e. used '(' as the open-parens, and not '(?:' 

Comment 9

[Brendan Eich [:brendan]]

Can this bug be targeted at 0.9.9?

/be

Comment 10

[rogerl (gone)]

Targetting 0.9.9

Comment 11

[rogerl (gone)]

Attachment: Fix range test.

Off by one on checking index against allocated chunk.

Comment 12

[Phil Schwartau]

Just need r=, sr= to get this patch in.

Comment 13

[Brendan Eich [:brendan]]

Comment on attachment 66012 [details] [diff] [review]
Fix range test.

sr=[e-mail]

Comment 14

[Phil Schwartau]

Now just need r= to get this fix in. Anyone?

Comment 15

[rogerl (gone)]

Comment on attachment 66012 [details] [diff] [review]
Fix range test.

r=thesteve

Comment 16

[rogerl (gone)]

Fix checked in.

Comment 17

[Phil Schwartau]

Verified FIXED on WinNT, Linux, Mac9.1 The standalone JS testcase above
now passes in the debug and optimized JS shell. Furthermore, Stephen's
testcase passes in current Mozilla trunk builds on all three platforms.

I tried the latter with up to 200 parentheses, in both the capturing
and non-capturing cases -