If you think a bug might affect users in the 57 release, please set the correct tracking and status flags for Release Management.

CSS parser stack overflow parsing lots of '{' - CSSParserImpl::SkipUntil recursion

VERIFIED FIXED in mozilla1.9.1b3

Status

()

Core
CSS Parsing and Computation
P2
critical
VERIFIED FIXED
10 years ago
8 years ago

People

(Reporter: Paul Nickerson, Assigned: dbaron)

Tracking

(Blocks: 1 bug, 4 keywords)

Trunk
mozilla1.9.1b3
crash, testcase, verified1.9.0.6, verified1.9.1
Points:
---
Bug Flags:
blocking1.9.1 +
blocking1.9.0.6 +
wanted1.9.0.x +
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(4 attachments)

(Reporter)

Description

10 years ago
Created attachment 319707 [details]
testcase

Non-exploitable stack overflow hit when decompressing gzip-encoded http responses.

Attached is the text file that must be plugged into the tool in bug 431609.
Created attachment 334463 [details]
testcase2

Basically, I see the same stacktrace as with this one.
The first testcase generates:
http://crash-stats.mozilla.com/report/index/3a60dc28-6deb-11dd-b229-001321b13766?p=1
0  	xul.dll  	StringUnicharInputStream::Read  	 xpcom/io/nsUnicharInputStream.cpp:76
1 	xul.dll 	nsCSSScanner::Next 	layout/style/nsCSSScanner.cpp:644
2 	xul.dll 	CSSParserImpl::GetToken 	layout/style/nsCSSParser.cpp:1244
3 	xul.dll 	CSSParserImpl::SkipUntil 	layout/style/nsCSSParser.cpp:2113
4 	xul.dll 	CSSParserImpl::SkipUntil 	layout/style/nsCSSParser.cpp:2125
5 	xul.dll 	CSSParserImpl::SkipUntil 	layout/style/nsCSSParser.cpp:2125
etc...

With this testcase, I get:
http://crash-stats.mozilla.com/report/index/854904d4-6ded-11dd-82b0-001a4bd43e5c?p=1
0  	xul.dll  	nsCSSScanner::Next  	 layout/style/nsCSSScanner.cpp:723
1 	xul.dll 	CSSParserImpl::GetToken 	layout/style/nsCSSParser.cpp:1244
2 	xul.dll 	CSSParserImpl::SkipUntil 	layout/style/nsCSSParser.cpp:2113
3 	xul.dll 	CSSParserImpl::SkipUntil 	layout/style/nsCSSParser.cpp:2125
4 	xul.dll 	CSSParserImpl::SkipUntil 	layout/style/nsCSSParser.cpp:2125
5 	xul.dll 	CSSParserImpl::SkipUntil 	layout/style/nsCSSParser.cpp:2125
etc..
Moving over to style system.
Component: General → Style System (CSS)
Keywords: crash, testcase
QA Contact: general → style-system
Summary: Stack overflow at xpcom_core.dll!nsAString_internal::Capacity() → CSS parser stack overflow parsing lots of '{' - CSSParserImpl::SkipUntil recursion
Duplicate of this bug: 467970
This probably would be relatively easy to fix by making SkipUntil maintain its own stack in an nsAutoTArray<PRUnichar, 4>.

We should also see if there are any other similar things in the parser.  Having a recursive descent parser has some dangers when arbitrary recursion is allowed, although in CSS that's mostly (although not entirely) not the case.
The testcase in bug 467970 uses '(' rather than '{', and we were just independently sent a testcase using '['. The same fix will no doubt take care of all three but we should cover them all in the eventual testcase that gets checked in with the fix.
Since this has triggered crashes in three independent fuzz testing systems I suspect we'll be seeing more dupes of this. Prioritizing it ahead of other similar non-exploitable crashes may save us some time and grief later.
Flags: blocking1.9.2?
Flags: blocking1.9.1?
Assignee: nobody → dbaron
Status: NEW → ASSIGNED
Created attachment 351475 [details] [diff] [review]
patch
Attachment #351475 - Flags: superreview?(bzbarsky)
Attachment #351475 - Flags: review?(bzbarsky)
I wonder if Taras has any tools that can tell us if there are any other places in nsCSSParser or nsCSSScanner where we can end up with infinite recursion.

In particular, if there are no other bugs like this, we ought to just be able to make a table of all the functions in those two files and what other functions they call, and be unable to construct out of that table no call tree deeper than about 15 or 20.

But with a recursive descent parser, there's always a danger of writing code that can recurse to death.
(And building all the possible trees shouldn't be that expensive unless there are infinite ones... we could just start from the toplevel parsing entry points -- the things in CSSParserImpl that implement methods on nsICSSParser whose names start with "Parse".)
(And to be clear, the part of that that's hard for me to do is the "make a table of all the functions in those two files and what other functions they call".  I'd probably do it manually, which would take quite a while and be somewhat error-prone.)

Comment 11

9 years ago
Figuring out if something can die from recursion sounds too much like the halting problem, I don't plan on solving that anytime soon :)

However if you phrase the question more trivially, such as your table of functions comment, that's usually easy to automate.

The "what other functions they call" part sounds hard, but I think that's doable given the various callgraph attempts we've had in the past.
Attachment #351475 - Flags: superreview?(bzbarsky)
Attachment #351475 - Flags: superreview+
Attachment #351475 - Flags: review?(bzbarsky)
Attachment #351475 - Flags: review+
Flags: wanted1.9.0.x+
Flags: blocking1.9.0.6?
Created attachment 351573 [details]
testcase from Alexios Fakos (n.runs AG)
Flags: blocking1.9.0.6? → blocking1.9.0.6+
I think the static analysis described in comment 8 and comment 11 would work. Maybe the output could just be a list of any cycles that occur in the call graph and/or a list of acyclic paths greater than a threshold length. Hopefully that would not be too hard to audit manually. (Side note: we should really get the call graph stuff moved into the official Dehydra distro and documented.)

Comment 14

9 years ago
Yeah, I've got scripts which can do that in bug 458807, though they need some love and bugfixes before they are useful. Of course function pointers invalidate all bets, and virtual functions are hard if you end up calling nsISupports::Release or any function that can basically re-enter the entire tree.
Fixed on mozilla-central: http://hg.mozilla.org/mozilla-central/rev/cdb8066f1da2
Status: ASSIGNED → RESOLVED
Last Resolved: 9 years ago
OS: Windows XP → All
Hardware: PC → All
Resolution: --- → FIXED
Target Milestone: --- → mozilla1.9.2a1
Comment on attachment 351475 [details] [diff] [review]
patch

Requesting approval for a simple fix for a crash that tends to be caught by fuzzing tools.
Attachment #351475 - Flags: approval1.9.1?
Verified fixed, using:
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2a1pre) Gecko/20081209 Minefield/3.2a1pre
(although I haven't verified the first testcase)
Status: RESOLVED → VERIFIED
Attachment #351475 - Flags: approval1.9.1? → approval1.9.1+
Comment on attachment 351475 [details] [diff] [review]
patch

a191=beltzner; should this not also be marked blocking?
Fixed on 1.9.1: http://hg.mozilla.org/releases/mozilla-1.9.1/rev/593aa76b76f5
Keywords: fixed1.9.1
Target Milestone: mozilla1.9.2a1 → mozilla1.9.1b3
Attachment #351475 - Flags: approval1.9.0.6?
Flags: in-testsuite+
Flags: blocking1.9.1? → blocking1.9.1+
Priority: -- → P2
Comment on attachment 351475 [details] [diff] [review]
patch

Approved for 1.9.0.6, a=dveditz for release-drivers.
Attachment #351475 - Flags: approval1.9.0.6? → approval1.9.0.6+
Checked in to CVS trunk, 2008-12-22 07:44 -0800.
Keywords: fixed1.9.0.6
(In reply to comment #17)
> Verified fixed, using:
> Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2a1pre) Gecko/20081209
> Minefield/3.2a1pre
> (although I haven't verified the first testcase)

Martijn, can you verify this with a current 1.9.0 build since you are familiar with it?
Verified for 1.9.0.6, using:
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.6pre) Gecko/2009010606 GranParadiso/3.0.6pre

And verified for 1.9.1, using:
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.1b3pre) Gecko/20081229 Shiretoko/3.1b3pre
Keywords: fixed1.9.0.6, fixed1.9.1 → verified1.9.0.6, verified1.9.1
Flags: blocking1.9.2?
You need to log in before you can comment on or make changes to this bug.