Very non-greedy regexp causes crash in jsregexp.c

VERIFIED FIXED in mozilla1.9alpha1

Status

()

Core
JavaScript Engine
P1
critical
VERIFIED FIXED
12 years ago
11 years ago

People

(Reporter: kohei, Assigned: Brian Crowder)

Tracking

({crash})

Trunk
mozilla1.9alpha1
crash
Points:
---
Dependency tree / graph
Bug Flags:
blocking1.9 ?
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [sg:nse] null deref)

Attachments

(3 attachments, 1 obsolete attachment)

(Reporter)

Description

12 years ago
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.
(Reporter)

Updated

12 years ago
Keywords: crash

Updated

12 years ago
Status: UNCONFIRMED → NEW
Ever confirmed: true
Summary: Crash in jsregexp.c → Very non-greedy regexp causes crash in jsregexp.c
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
Assignee: general → mrbkap
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.
Priority: -- → P1
Target Milestone: --- → mozilla1.9alpha

Updated

12 years ago
Status: NEW → ASSIGNED
Whiteboard: [patch]
Created attachment 215298 [details] [diff] [review]
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.
Attachment #215298 - Flags: review?(brendan)
Comment on attachment 215298 [details] [diff] [review]
Fix the crash

Actually, I have a more complete patch that fixes both problems.
Attachment #215298 - Attachment is obsolete: true
Attachment #215298 - Flags: review?(brendan)
Created attachment 215337 [details] [diff] [review]
More complete fix

As far as I can tell, this does the right thing.
Attachment #215337 - Flags: review?(brendan)
Comment on attachment 215337 [details] [diff] [review]
More complete fix

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

/be
Attachment #215337 - Flags: review?(brendan) → review+

Comment 7

12 years ago
Created attachment 215688 [details]
js1_5/Regress/regress-330352.js

Updated

12 years ago
Flags: in-testsuite+

Updated

12 years ago
Whiteboard: [patch]
Based on comment 2, can we remove the security flag?
Whiteboard: [sg:nse] null deref
(In reply to comment #8)
> Based on comment 2, can we remove the security flag?

Yes, we can. Clearing the security-sensitive flag.
Group: security
Comment on attachment 215337 [details] [diff] [review]
More complete fix

This actually causes worse crashes.
Attachment #215337 - Flags: review+ → review-

Comment 11

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

Updated

11 years ago
Depends on: 330793

Comment 12

11 years ago
mrbkap, are you going to be able to continue working on this patch?
Flags: blocking1.9?

Comment 13

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

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

Comment 14

11 years ago
Taking this one from mrbkap so I won't forget to work on it.
Assignee: mrbkap → crowder
Status: ASSIGNED → NEW
(Assignee)

Comment 15

11 years ago
Created attachment 259385 [details] [diff] [review]
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.
Attachment #259385 - Flags: review?(mrbkap)
(Assignee)

Comment 16

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

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

Updated

11 years ago
Attachment #259385 - Flags: review?(mrbkap) → review+
(Assignee)

Comment 17

11 years ago
jsregexp.c: 3.138
Status: NEW → RESOLVED
Last Resolved: 11 years ago
Resolution: --- → FIXED

Comment 18

11 years ago
verified fixed linux, windows, mac* shell 20070406
Status: RESOLVED → VERIFIED

Updated

11 years ago
Blocks: 379056
You need to log in before you can comment on or make changes to this bug.