330352 - Very non-greedy regexp causes crash in jsregexp.c

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Kohei Yoshino [:kohei]]

User-Agent:       Mozilla/5.0 (Macintosh; U; PPC Mac OS X Mach-O; en-US; rv:1.8.0.1) Gecko/20060111 Firefox/1.5.0.1
Build Identifier: Mozilla/5.0 (Macintosh; U; PPC Mac OS X Mach-O; en-US; rv:1.9a1) Gecko/20060313 Firefox/1.6a1

Note: This bug was originally reported to IPA (Information-technology Promotion Agency, Japan) and forwarded to us at Mozilla Japan. I'm NOT original reporter. Don't ask me about details. For more information about IPA, visit http://www.ipa.go.jp/about/english/ 

IPA#36438227


Reproducible: Always

Steps to Reproduce:
Loading the following script causes Firefox to crash:
javascript:if("AB".match(/(.*?)*?B/)){alert(RegExp.lastMatch);}

No problem with:
javascript:if("AB".match(/(.*)*?B/)){alert(RegExp.lastMatch);}
or
javascript:if("AB".match(/(.*?)*B/)){alert(RegExp.lastMatch);}

Actual Results:  
Firefox consumes large amounts of memory and CPU time of machine, causes application error, and crashes.


Expected Results:  
Don't crash


Comment from IPA:
This bug allows websites to crash user machines or perform a DoS attack. We [IPA] have examined the problem and found that application error occurred at jsregexp.c. Attackers might run arbitrary code, but we have not found real way of code injection.

IPA asked us to treat this bug confidential, but if there are no risks, uncheck the security mark.

Comment 1

[Daniel Veditz [:dveditz]]

In a 1.8.0.2-ish debug build I crash dereferencing a null "result->sz" in PushBackTrackState. Didn't notice a particularly large amount of memory use though, so maybe I'm hitting something different given some of the other js fixes  that went into 1.8.0.2

Comment 2

[Blake Kaplan (:mrbkap) (inactive)]

This looks like a non-exploitable null pointer dereference caused (in part) by a failure to propagate OOM. I want to look and see why we're spinning out of control here with the non-greedy regexps only, though.

Comment 3

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: Fix the crash

This fixes the crash due to the OOM that we're hitting. We shouldn't be hitting an OOM condition at all, though. I'll file a new bug on fixing the non-greedy quantifiers to not be wrong.

Comment 4

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 215298 [details] [diff] [review]
Fix the crash

Actually, I have a more complete patch that fixes both problems.

Comment 5

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: More complete fix

As far as I can tell, this does the right thing.

Comment 6

[Brendan Eich [:brendan]]

Comment on attachment 215337 [details] [diff] [review]
More complete fix

Good as far as it goes, but not the complete fix.

/be

Comment 7

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/Regress/regress-330352.js

Comment 8

[Daniel Veditz [:dveditz]]

Based on comment 2, can we remove the security flag?

Comment 9

[Blake Kaplan (:mrbkap) (inactive)]

(In reply to comment #8)
> Based on comment 2, can we remove the security flag?

Yes, we can. Clearing the security-sensitive flag.

Comment 10

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 215337 [details] [diff] [review]
More complete fix

This actually causes worse crashes.

Comment 11

[Bob Clary [:bc] (inactive)]

Checking in regress-330352.js;
/cvsroot/mozilla/js/tests/js1_5/Regress/regress-330352.js,v  <--  regress-330352.js
initial revision: 1.1

Comment 12

[Jesse Ruderman]

mrbkap, are you going to be able to continue working on this patch?

Comment 13

[Jesse Ruderman]

options("relimit") doesn't help, fwiw.

options("relimit"); /(a*?)+?/.exec("");
still causes js to consume all available memory.

Comment 14

[Brian Crowder]

Taking this one from mrbkap so I won't forget to work on it.

Comment 15

[Brian Crowder]

Attachment: empty result allowed at RPAREN

This is a similar bug to bug 367888: we have a match-case which doesn't properly consume an empty match, causing the "repeat" code to continue repeating forever.  The usual pieces (ie., the parts that didn't fail before) of the test-suite pass with this patch applied.

Comment 16

[Brian Crowder]

Here's the perl behavior on the same match, for reference:

$ perl -e '"AB" =~ /(.*?)*?B/; print "$&, $1\n"'
AB, A

Comment 17

[Brian Crowder]

jsregexp.c: 3.138

Comment 18

[Bob Clary [:bc] (inactive)]

verified fixed linux, windows, mac* shell 20070406