152646 - Too many parentheses in JavaScript expression causes crash

Status: VERIFIED DUPLICATE of bug 192414

(Core :: JavaScript Engine, defect)

Description

[Mitchell Stoltz (not reading bugmail)]

The JS engine crashes when evaluating an expression with too many parentheses.

var a = ((((((((((((... a few hundred more ... ((( ))) ... and a few hundred of
these ... ))))):

This causes the stack to overflow. Here's a stack trace of one cycle in the
recursion:

BitAndExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2258 + 17 bytes
BitXorExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2245 + 17 bytes
BitOrExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2232 + 17 bytes
AndExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2221 + 17 bytes
OrExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2210 + 17 bytes
CondExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2170 + 17 bytes
AssignExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2116 + 17 bytes
Expr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2090 + 17 bytes
PrimaryExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2898 + 17 bytes
MemberExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8, int 1) line 2580 + 17 bytes
UnaryExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2498 + 19 bytes
MulExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2360 + 17 bytes
AddExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2342 + 17 bytes
ShiftExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2327 + 17 bytes
RelExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2295 + 17 bytes
EqExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2270 + 17 bytes
BitAndExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2258 + 17 bytes
BitXorExpr(JSContext * 0x03846028, JSTokenStream * 0x03be6130, JSTreeContext *
0x0012efc8) line 2245 + 17 bytes
BitOrExpr(JSContext... and so on

This does not appear to be an exploitable buffer overrun, merely a stack
overflow from too much recursion. This appears related to bug 96526, so I'm
assigning it to Kenton.

Comment 1

[Mitchell Stoltz (not reading bugmail)]

Attachment: testcase - this will cause a crash

Comment 2

[Pete Boyd]

I see this [Mozilla 2002061712, Windows 2000]

Talkback ID: TB7475581E

Comment 3

[timeless]

I see this [Netscape4.79, Windows 2000]

Talkback ID: TB747032E

Comment 4

[Kenton Hanson (gone)]

This is not recursion.  This is expression complexity.  

Elimination of unnecessary parentheses at the parsing stage is a possible
solution.  

Comment 5

[Phil Schwartau]

I looked up both Talkback incidents above, TB7475581E and TB747032E.
Simple stack overflow in the former, and no stack for the latter.

Comment 6

[Phil Schwartau]

Testcase added to JS testsuite:

          mozilla/js/tests/js1_5/Regress/regress-152646.js

Comment 7

[jack.jia]

Attachment: the call statck of mozilla for the testcase

I check the callstack, I find that the recursive call of the next function
cause the stack overflow and crash.

    MulExpr() line 2360
    AddExpr() line 2342 + 17 bytes
    ShiftExpr() line 2327 + 17 bytes
    RelExpr() line 2295 + 17 bytes
    EqExpr() line 2270 + 17 bytes
    BitAndExpr() line 2258 + 17 bytes
    BitXorExpr() line 2245 + 17 bytes
    BitOrExpr() line 2232 + 17 bytes
    AndExpr() line 2221 + 17 bytes
    OrExpr() line 2210 + 17 bytes
    CondExpr() line 2170 + 17 bytes
    AssignExpr() line 2116 + 17 bytes
    Expr() line 2090 + 17 bytes
    PrimaryExpr() line 2898 + 17 bytes
    MemberExpr() line 2580 + 17 bytes
    UnaryExpr() line 2498 + 19 bytes

    when it parse too many "((((( ... (((" in the testcase.Mozilla use the
recursive call. I suggest mozilla should add a limit to avoid recursive call
too deep and avoid stack overflow.

Comment 8

[jack.jia]

Attachment: a suggest patch for review

I add a limit to avoid the recursive call too deep. This patch worked well
for the testcase and didn't affect others.

Comment 9

[Brendan Eich [:brendan]]

Comment on attachment 90757 [details] [diff] [review]
a suggest patch for review

Sorry, using a static is not thread-safe.  Also, returning NULL without
reporting an error is bad form: it silently kills compilation without telling
the user why.

I think this bug is better addressed by avoiding recursion on the C stack. 
khanson may have some thoughts.

/be

Comment 10

[Kenton Hanson (gone)]

I don’t understand why this is marked critical.  No real world example has been
presented.  Why would anyone surround an expression with hundreds of enclosing
parenthesis?  I will continue to look for a solution.
Attachment 90757 [details] [diff] prevents a crash, but, what is the correct limit for the number
of nested parenthesis?  It varies from machine to machine and is dependant on
its embedding within the javascrpt program.  Does anyone have any suggestions
for stack sniffing routines for dynamically determining when the stack space is
getting low?

Comment 11

[Brendan Eich [:brendan]]

I see no comment from [e-mail] justifying the severity change.  Severity
is for reporters to set, so I'm restoring mstoltz's initial severity.

I agree with khanson that this is not a high-priority bug to work on right now.
 JS stack overflow hazards ought to be addressed systematically, too.  E.g., all
recursive procedures should have tuned or self-tuning limits, or should be
converted to iterative procedures.

/be

Comment 12

[Adam Hauner]

Kenton, Brendan: I marked this as critical because it's causing crash. I'm
sorry, change was IMHO correct according to impact scale in 'A Bug's Life Cycle'
document.

Comment 13

[Brendan Eich [:brendan]]

aha: sorry, a crash that never happens in practice cannot be critical.

Asa, Gerv: does the bug life cycle doc need more nuance?

/be

Comment 14

[Gervase Markham [:gerv]]

Well, it requires the application of common-sense when reading it :-)

Unsurprisingly, our website is so disorganised that I can't find that document.
Can someone post the URL?

Gerv

Comment 15

[Adam Hauner]

Gerv: http://bugzilla.mozilla.org/bug_status.html#severity
Brendan, Gerv: I'm sorry, it was half-automatic action while reading new bugs.

Comment 16

[Kenton Hanson (gone)]

Low priority due to its rare occurrence in real JavasScript programs. 
Preprocessing scripts to eliminate unnecessary parenthesis seems a bit
burdensome for scripts without this unnatural defect.  The proposed patch, while
avoiding crashes, puts an arbitrary limit on parenthesis depth, a limit that
should vary dynamically with platforms and script complexity.  I am still
looking for a methodology for dynamically detecting low stack conditions.  Any
suggestions?

Comment 17

[Brant Gurganus]

By the definitions on <http://bugzilla.mozilla.org/bug_status.html#severity> and
<http://bugzilla.mozilla.org/enter_bug.cgi?format=guided>, crashing and dataloss
bugs are of critical or possibly higher severity.  Only changing open bugs to
minimize unnecessary spam.  Keywords to trigger this would be crash, topcrash,
topcrash+, zt4newcrash, dataloss.

Comment 18

[Joseph Myers]

Right: suppose someone is browsing, in the middle of ordering from
Amazon.com--then they open another web page with 1000 parentheses in JavaScript,
and it crashes everything. Therefore, by application, anything that makes a
crash should be considered critical.

Comment 19

[Daniel Veditz [:dveditz]]

We really should scrap the emotionally charged "Priority" label (avoiding fights
over whose priority it is) and replace it with a less subjective
"frequency/visibility" field. 

Do any developers really use the Priority field to manage their work?

Comment 20

[Phil Schwartau]

Brendan pointed out to me that this bug and bug 192414 are duplicates.
Since more comments and patches have occurred on the latter bug, I am
going to dupe this one forward.

Anyone interested in following progress on this issue should cc himself
on bug 192414, "Parser recursion does not check stack overflow" -

*** This bug has been marked as a duplicate of 192414 ***

Comment 21

[Phil Schwartau]

Verified Duplicate -

Comment 22

[timeless]

Test results, smdebug

Test List: All tests
Skip List: lc2, lc3
1112 test(s) selected, 1112 test(s) completed, 6 failures reported (0.53% failed)
Engine command line: .\..\src\WINNT5.0_DBG.OBJ\js.exe
OS type: WIN
Testcase execution time: 14 minutes, 10 seconds.
Tests completed on Fri Nov 7 13:44:01 2003.

CVS is from between 10/21 and 10/27 based on cvs status for jsapi.h.

    Testcase js1_5/Regress/regress-152646.js failed
    [ Previous Failure | Next Failure | Top of Page ]
    Expected exit code 0, got 253
    Testcase terminated with signal 0
    Complete testcase output was:
    Testcase produced no output!

Comment 23

[timeless]

perhaps a new bug needs to be filed based on bug 192414 comment 29, bug 192414
comment 31, bug 192414 comment 32 for smdebug?

phil: could you possibly change the test files so that they point to a live bug
instead of a dead bug? running through the regression test suite and getting
failures is really confusing for me when i'm tired / rushed / distracted.

sorry about the reopen.

Comment 24

[Phil Schwartau]

timeless: I'm also failing on js1_5/Regress/regress-192414.js, 
in both the debug and optimized JS shell on WinNT.

Are you failing on that one, too?

Each testcase is named after the bug it was written for, and
points to that bug for the most thorough historical context.

Comment 25

[timeless]

yeah i'm failing that one too

Comment 26

[Phil Schwartau]

Shouldn't we reopen bug 192414, then, which this one had been duped against?

I'm going to go ahead and do that if no one minds: re-resolve this bug as
a dupe, and re-open bug 192414, since most of the work occurred there -

*** This bug has been marked as a duplicate of 192414 ***

Comment 27

[Phil Schwartau]

Re-marking Verified Duplicate.

timeless: thanks for finding this; I have cc'ed you on bug 192414 -