Closed Bug 539080 Opened 15 years ago Closed 3 years ago

RegExp engine hangs

Categories

(Core :: JavaScript Engine, defect)

Product:
Core
Component:
JavaScript Engine
Platform:
x86
Windows Vista
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: vagababov, Unassigned)

Details

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1.7) Gecko/20091221 Firefox/3.5.7 GTB6 (.NET CLR 3.5.30729)
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1.7) Gecko/20091221 Firefox/3.5.7 GTB6 (.NET CLR 3.5.30729)

when passing following (not correct, though) regular expression the FF hangs.
var re = new RegExp("^(\\w+[_-\\s]?)+$", "i");



Reproducible: Always

Steps to Reproduce:
Write the page containing the JS code to invoke the provided regular expression.
Actual Results:  
The FF Will hang.

Expected Results:  
Error message/skipping of the incorrect regexp.
Not verified, but hiding for now. There is some discussion whether we should classify bugs like this as security sensitive, but I hate it when my browser hangs, and this one has a test case, so I vote for hiding.
Group: core-security
I'm having trouble reproducing this hang; I've tried:
 - TraceMonkey tip js shell
 - FF 3.5.7 error console
 - FF 3.5.7 loading this page:

<html><head><script>var re = new RegExp("^(\\w+[_-\\s]?)+$", "i");</script></head></html>

All forms just give an error about an invalid character class.
Same here. I tried this in the url bar with javascript:
No hang on Vista either.
We do not hide hang bugs, period. Please stop doing it, it just makes it harder for people who could help resolve the bug to find it.

Victor: are you matching re against a string, or do you see a hang just from the one-line 'var re = new RegExp(...)' program? A testcase attached to the bug would be a big help.

Is the nested closure in the regexp an exponential backtracking case? If so try setting relimit:

http://kb.mozillazine.org/Javascript.options.relimit

/be
Group: core-security
Actually, when I returned to my desk half an hour later it was finished.
 So, it just took unreasonable time to process.
I'll try to create the simplest page in which I can reproduce the situation and post it later.
The relimit option was added in bug 330569, but bug 452451needs to be fixed so setting .relimit actually works. Rob, can this be assigned so it's fixed in 3.7 if not sooner?

For past exponential regexp bugs, see bug 265353, bug 349021, bug 351448, bug 414001, bug 508542. We seem not to be dup'ing to an ur-bug, rather invalidating. I'll let someone figure out how best to dispose of this bug.

/be
To clarify comment 7, this is either a "works as designed" bug, or a "quality of implementation" bug, where we try to chase Perl and PCRE-based engines and decide that we are not going to match and return the correct result early -- or we turn on the relimit option and throw an exception.

It's a shame JS stole from Perl which stole from whoever (Henry Spencer?) and thus bought the exponential-NFA-backtracking hazard in the bargain, but we are stuck with it. JS hackers need to avoid writing such expressions, whether any particular browser runs too long or not (until such time as all browsers shortcut or terminate such regexps when used).

A current survey of what various browsers do could help inform the Ecma standards body. Best to do this by testing and publishing results to es-discuss@mozilla.org if anyone has the time and wants to help. Thanks,

/be
(In reply to comment #8)
> To clarify comment 7, this is either a "works as designed" bug, or a "quality
> of implementation" bug

For me this the latter. The engine should be able to deal with such regexps in the same way it deals with infinite loops.
Couldn't reproduce this bug in FF4.0b10, probably because of overhaul in regular expressions. Now the output is: 

[14:16:10.259] invalid range in character class @ javascript:new%20RegExp("^(\\w+[_-\\s]?)+$",%20"i");:1

So browser doesn't crash or hang.
(In reply to comment #10)
> [14:16:10.259] invalid range in character class @
> javascript:new%20RegExp("^(\\w+[_-\\s]?)+$",%20"i");:1

If you turn: "[_-\\s]" into "[\\s-_]" it should work. This errors were made the same as in FF 3.6 -- see bug 576837.
Assignee: general → nobody
Between comment 10 and comment 11 it sounds like this bug is invalid.
Does anyone disagree?
Status: UNCONFIRMED → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.