307456 - Freeze when certain Javascript regular expressions are executed; should warn about long-running script

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Lupin.wp]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.10) Gecko/20050822 Firefox/1.0.6 (Debian package 1.0.6-3)
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.10) Gecko/20050822 Firefox/1.0.6 (Debian package 1.0.6-3)

If you load the attached file and OK the first alert box, then firefox freezes,
consuming 100% of CPU. This is bad.

Reproducible: Always

Steps to Reproduce:
1. Load the attached file.

Actual Results:  
Firefox consumes 100% of cpu and cannot be interrupted except by killing it.

Expected Results:  
At the very least, the dialog about resource-hogging scripts should appear and
give the option to cancel the script.

Comment 1

[Lupin.wp]

Attachment: File demonstrating a regex causing a freeze

Comment 2

[Josh Birnbaum]

Confirmed with SeaMonkey 2005090705 on WinXP.  bug 265353 looks similar.

Comment 3

[Brendan Eich [:brendan]]

Blake, can you take a look?

If bug 265353 is the same, it should be reproducible on trunk builds.  Is it?

/be

Comment 4

[Blake Kaplan (:mrbkap) (inactive)]

I'll take this. I can't reproduce bug 265353, but I certainly can reproduce this
bug.

Comment 5

[Asa Dotzler [:asa]]

please request approval if you come up with a good safe fix. 

Comment 6

[Bob Clary [:bc] (inactive)]

reproducible hang on winxp/1.8/trunk

Checking in regress-307456.js;
/cvsroot/mozilla/js/tests/ecma_3/RegExp/regress-307456.js,v  <--  regress-307456.js
initial revision: 1.1
done

Comment 7

[Lupin.wp]

Bug #320483 has similar symptoms and a much simpler one-line testcase. I don't know if it has the same underlying cause as this bug.

Comment 8

[Reed Loden [:reed]]

This bug completely froze my Firefox [Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8) Gecko/20051111 Firefox/1.5] and never unhung. :/

Requesting blocking1.8.0.1 and blocking1.8.1.

Comment 9

[Bob Clary [:bc] (inactive)]

*** Bug 320483 has been marked as a duplicate of this bug. ***

Comment 10

[Brendan Eich [:brendan]]

Superlinearity can be detected as Friedl's book shows, mrbkap was gonna work on that.  Longer term, we should merge the REOP_ bytecodes into the main JSOP_ ones so we can police backtracking as we do backward branches, with the API-configured branch callback.

/be

Comment 11

[Daniel Veditz [:dveditz]]

Missed 1.5, still no patch, doesn't seem like 1.5.0.1 material (maybe 1.5.0.2 if a patch appears).

Comment 12

[Diego]

Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9a1) Gecko/20060317 Firefox/1.6a1 from cvs

Still hangs,

following stack traces

#0  0xb7deff1b in ExecuteREBytecode (gData=0xbf8fe4d0, x=0x9089c08) at jsregexp.c:2977
#1  0xb7df041c in MatchRegExp (gData=0xbf8fe4d0, x=0x9089c08) at jsregexp.c:3178
[..]

#0  0xb7dedfa5 in PushBackTrackState (gData=0xbf8fe4d0, op=3213878480, target=0xbf8fe4d0 "Hp\uffff\b\uffffz\017\t\001", x=0x9089c08, cp=0xbf8fe4d0, parenIndex=0,
    parenCount=0) at jsregexp.c:2084
#1  0xb7def888 in ExecuteREBytecode (gData=0xbf8fe4d0, x=0x9089c08) at jsregexp.c:2781
#2  0xb7df041c in MatchRegExp (gData=0xbf8fe4d0, x=0x9089c08) at jsregexp.c:3178
[..]

#0  0xb7def0c6 in SimpleMatch (gData=0xbf8fe4d0, x=0x9089c08, op=35, startpc=0xbf8fe438, updatecp=1) at jsregexp.c:2573
#1  0xb7df03a7 in ExecuteREBytecode (gData=0xbf8fe4d0, x=0x9089c08) at jsregexp.c:2713
#2  0xb7df041c in MatchRegExp (gData=0xbf8fe4d0, x=0x9089c08) at jsregexp.c:3178
#3  0xb7df06c2 in js_ExecuteRegExp (cx=0x8d97048, re=0x90f7ad8, str=0x8593d48, indexp=0xbf8fe588, test=1, rval=0xbf8fe6c0) at jsregexp.c:3277
#4  0xb7dfd13d in match_or_replace (cx=0x8d97048, obj=0x86d21e0, argc=2, argv=0x90f7ad8, glob=0xb7dfde7c <replace_glob>, data=0xbf8fe5d0, rval=0xbf8fe6c0)
    at jsstr.c:1197
#5  0xb7dfe194 in str_replace (cx=0x8d97048, obj=0x86d21e0, argc=2, argv=0x9083518, rval=0xbf8fe6c0) at jsstr.c:1678
#6  0xb7db9df4 in js_Invoke (cx=0x8d97048, argc=2, flags=0) at jsinterp.c:1246
#7  0xb7dc46d9 in js_Interpret (cx=0x8d97048, pc=0x9132887 ":", result=0xbf8feb70) at jsinterp.c:3884
#8  0xb7dba781 in js_Execute (cx=0x8d97048, chain=0x89e52d0, script=0x9132828, down=0x0, flags=35, result=0x23) at jsinterp.c:1496
#9  0xb7d91498 in JS_EvaluateUCScriptForPrincipals (cx=0x8d97048, obj=0x89e52d0, principals=0x90a827c, chars=0x9003228, length=661,
    filename=0x90ea748 "https://bugzilla.mozilla.org/attachment.cgi?id=195224", lineno=1, rval=0xbf8fec4c) at jsapi.c:4134
#10 0xb6b5887b in nsJSContext::EvaluateString (this=0x8ae6e48, aScript=@0xbf8fee20, aScopeObject=0x89e52d0, aPrincipal=0x90a8278,
    aURL=0x90ea748 "https://bugzilla.mozilla.org/attachment.cgi?id=195224", aLineNo=1, aVersion=0x0, aRetValue=0x0, aIsUndefined=0xbf8fed3c)
    at nsJSEnvironment.cpp:1069
#11 0xb69d391b in nsScriptLoader::EvaluateScript (this=0x8e92d44, aRequest=0x91327f0, aScript=@0xbf8fee20) at nsScriptLoader.cpp:756
#12 0xb69d34a9 in nsScriptLoader::ProcessRequest (this=0x8e92d28, aRequest=0x91327f0) at nsScriptLoader.cpp:659
#13 0xb69d2d43 in nsScriptLoader::DoProcessScriptElement (this=0x8e92d28, aElement=0xbf8ff180, aObserver=0x9132490, aFireErrorNotification=0xbf8ff3c8)
    at nsScriptLoader.cpp:592
#14 0xb69d2288 in nsScriptLoader::ProcessScriptElement (this=0x8e92d28, aElement=0x9132494, aObserver=0x9132490) at nsScriptLoader.cpp:341
#15 0xb6a595cb in nsHTMLScriptElement::MaybeProcessScript (this=0x9132470) at nsHTMLScriptElement.cpp:707
#16 0xb6a590d0 in nsHTMLScriptElement::DoneAddingChildren (this=0x23, aHaveNotified=0) at nsHTMLScriptElement.cpp:562
#17 0xb6a7ec84 in HTMLContentSink::ProcessSCRIPTEndTag (this=0x90dafa0, content=0x9132470, aHaveNotified=0, aMalformed=0) at nsHTMLContentSink.cpp:3919
#18 0xb6a79144 in SinkContext::CloseContainer (this=0x90db118, aTag=eHTMLTag_script, aMalformed=0) at nsHTMLContentSink.cpp:1404 #19 0xb6a7cd47 in HTMLContentSink::CloseContainer (this=0x3, aTag=3213878480) at nsHTMLContentSink.cpp:2972
#20 0xb597dea0 in CNavDTD::CloseContainer (this=0x909cde8, aTag=eHTMLTag_script, aMalformed=0) at CNavDTD.cpp:2679
#21 0xb597c3fc in CNavDTD::HandleEndToken (this=0x909cde8, aToken=0x8ea2338) at CNavDTD.cpp:1545
[..]

Comment 13

[Brendan Eich [:brendan]]

Yes, nothing has been patched yet, so no need to add "still hangs" or other me-too comments.

/be

Comment 14

[Darin Fisher]

Would be nice to get this fixed for 1.8.1

Comment 15

[Myk Melez [:myk] [@mykmelez]]

For microsummaries, it would be useful to be able to flag a regexp as untrusted and have it be interruptable in a programmatically-detectable way (as opposed to a user-detectable way, as the resource-hogging dialog does) to prevent microsummary generators with problematic regexps from hanging the app.

Comment 16

[Myk Melez [:myk] [@mykmelez]]

Robert Sayre pointed me to this description of how Perl handles such regexes:

http://perlmonks.org/index.pl?node_id=502408

Comment 17

[Feng Qian (Google)]

The test case can be simplified to just /(Z|Z)*X/, Given a string 'XZZZZZZZZ...' with N trailing 'Z's, it tooks O(2^N) time. I talked to Blake Kaplan that I will give it a shoot. 

Comment 18

[Feng Qian (Google)]

BTW, IE6 is O(2^N) too, but it is twice faster than Firefox. 

Comment 19

[Feng Qian (Google)]

Attachment: add callback in regexp engine, allows a user to stop the script

Per our discussion, this is a simple fix to let regular expression obey dom.max_script_run_time limit.

Comment 20

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 226584 [details] [diff] [review]
add callback in regexp engine, allows a user to stop the script

My only concern is that this might hurt RegExp performance. If it does, then we might want to consider calling the branch callback every 100 REOP_REPEATs or something.

Comment 21

[Brendan Eich [:brendan]]

We should try to gather some benchmarks and see the performance effect of this patch before landing it.  I'm also interested in head-to-head perf vs. IE and Safari.  The twice-rewritten jsregexp.c implementation is far from the last word on optimization of NFAs.

/be

Comment 22

[Feng Qian (Google)]

I tested this benchmark on IE6 and Safari, IE6 is about twice fast than Firefox, but also exponential.
Safari 2.0.3 on MacOSX is about twice faster than Firefox1.5.0.4, and also exponential.
Latest Safari built on kjs has an incompatible regex engine, which cannot handle this benchmark. It doesn't handle /([^Y]|Z)*X/ properly.

(In reply to comment #21)
> We should try to gather some benchmarks and see the performance effect of this
> patch before landing it.  I'm also interested in head-to-head perf vs. IE and
> Safari.  The twice-rewritten jsregexp.c implementation is far from the last
> word on optimization of NFAs.
> 
> /be
> 

Comment 23

[Feng Qian (Google)]

Attachment: revised patch

If we don't call onbranch at every REOP_REPEAT, it does hurt performance. It is about 10% slowdown. If calling onbranch for every 100 REOP_REPEAT, no measureable slowdown on this benchmark, and also allows the browser to stop the script in approximately dom.max_script_run_time. Using a slightly modified regexp match 'ZZZZZZZZZZZZZZZZ'.match(/(Z|Z)*X/), which executes REOP_REPEAT intensively, no slowdown either. I think 100 is good number.

Comment 24

[Feng Qian (Google)]

(In reply to comment #23)
> Created an attachment (id=226860) [edit]
> revised patch
> 
> If we don't call onbranch at every REOP_REPEAT, it does hurt performance. It is

typo here, should be "If we call onbranch at every REOP_REPEAT, ..."

> about 10% slowdown. If calling onbranch for every 100 REOP_REPEAT, no
> measureable slowdown on this benchmark, and also allows the browser to stop the
> script in approximately dom.max_script_run_time. Using a slightly modified
> regexp match 'ZZZZZZZZZZZZZZZZ'.match(/(Z|Z)*X/), which executes REOP_REPEAT
> intensively, no slowdown either. I think 100 is good number.  
> 

Comment 25

[Brendan Eich [:brendan]]

Comment on attachment 226860 [details] [diff] [review]
revised patch

Nit-picking for smallest code:

>+    int onbranchCalls = 0;
>+#define ONBRANCH_CALLS_INTERVAL        100
>+#define CHECK_BRANCH()                                                         \
>+    JS_BEGIN_MACRO                                                             \
>+        if (onbranch && (onbranchCalls++ >= ONBRANCH_CALLS_INTERVAL)) {        \
>+            onbranchCalls = 0;                                                 \
>+            if (!(*onbranch)(gData->cx, NULL)) { 

Using ++onbranchCalls > ... would avoid a temporary.

Also, using (++onbranchCalls & ONBRANCH_CALLS_MASK) where ONBRANCH_CALLS_MASK is 127 would avoid the need to reset onbranchCalls.

/be

Comment 26

[Feng Qian (Google)]

Attachment: revised patch (2)

Incorporate Brendan's comments.

Comment 27

[Brendan Eich [:brendan]]

Comment on attachment 227083 [details] [diff] [review]
revised patch (2)

>+    JSBranchCallback onbranch = gData->cx->branchCallback;
>+    int onbranchCalls = 0;

Use unsigned instead of int (uintN is JS shorthand, meant to suggest N for Native or Natural register width integer type), since you're using & as a strength-reduced % operator and % on a signed numerator requires extra work (style only, since & doesn't mind).

>+#define ONBRANCH_CALLS_MASK             127
>+#define CHECK_BRANCH()                                                         \
>+    JS_BEGIN_MACRO                                                             \
>+        if (onbranch && (++onbranchCalls & ONBRANCH_CALLS_MASK)) {             \
>+            if (!(*onbranch)(gData->cx, NULL)) {                              

Collapse into single if using && at end of lines, splitting across three lines total?

/be

Comment 28

[Brendan Eich [:brendan]]

Comment on attachment 227083 [details] [diff] [review]
revised patch (2)

>+        if (onbranch && (++onbranchCalls & ONBRANCH_CALLS_MASK)) {             

Oops, you want !(++onbranchCalls & ONBRANCH_CALLS_MASK) here. Retracting sr+.

/be

Comment 29

[Brendan Eich [:brendan]]

Comment on attachment 227083 [details] [diff] [review]
revised patch (2)

Or to be less hax0rish, test (++onbranchCalls & ONBRANCH_CALLS_MASK) == 0 instead of abusing !.

/be

Comment 30

[Feng Qian (Google)]

Attachment: revised patch (3)

Silly mistake!, your suggestion is taken.

Comment 31

[Brendan Eich [:brendan]]

Comment on attachment 227148 [details] [diff] [review]
revised patch (3)

>+            ((++onbranchCalls & ONBRANCH_CALLS_MASK) == 0) &&                  

This is totally a nit-pick, and it telegraphs my not being a Lisp hacker, and my early-age counter-reaction to Pascal in favor of C: prevailing style would not parenthesize the == expression against &&, since that is unnecessary.

Other than that, sr=me!

/be

Comment 32

[Feng Qian (Google)]

Attachment: revised patch (4)

Take Brendan's comment about no parenthesis around == expression. That's the only difference from previous patch, which has been approved.

Comment 33

[Brendan Eich [:brendan]]

Comment on attachment 227166 [details] [diff] [review]
revised patch (4)

feng, please request individual bugzilla ids so we get email.  Marking r+sr, since mrbkap r+'d last time. Thanks,

/be

Comment 34

[Darin Fisher]

Comment on attachment 227166 [details] [diff] [review]
revised patch (4)

a=darin on behalf of drivers (please land this on the MOZILLA_1_8_BRANCH promptly and add the fixed1.8.1 keyword)

Comment 35

[Mike Beltzner [:beltzner, not reading bugmail]]

Will this be checked in as part of the JS 1.7 landing? It's got a=drivers for the 1.8.1 branch, but hasn't been marked fixed yet ...

Comment 36

[Blake Kaplan (:mrbkap) (inactive)]

Fix checked into trunk.

Comment 37

[Darin Fisher]

fixed1.8.1

Comment 38

[Bob Clary [:bc] (inactive)]

I still hang like a surfer in a hurricane on ecma_3/RegExp/regress-307456.js in both 1.8.1 and 1.9 on winxp with cvs and nightly builds from 20060707. 

Comment 39

[Bob Clary [:bc] (inactive)]

sorry for reopening this bug. I had an extremely long dom.max_script_run_time in the profile I used to test this with.

verified fixed 1.8.1 and 1.9.

Comment 40

[Bob Clary [:bc] (inactive)]

Thanks to ispiked for catching my mistake and pointing it out to me.

Comment 41

[Feng Qian (Google)]

*** Bug 330684 has been marked as a duplicate of this bug. ***