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

Status: VERIFIED FIXED

(Core :: CSS Parsing and Computation, defect, P2)

Description

[Paul Nickerson]

Attachment: 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.

Comment 1

[Martijn Wargers (dead)]

Attachment: 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..

Comment 2

[Martijn Wargers (dead)]

Moving over to style system.

Comment 4

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

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.

Comment 5

[Daniel Veditz [:dveditz]]

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.

Comment 6

[Daniel Veditz [:dveditz]]

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.

Comment 7

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

Comment 8

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

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.

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(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".)

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(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

[(dormant account)]

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.

Comment 12

[Daniel Veditz [:dveditz]]

Attachment: testcase from Alexios Fakos (n.runs AG)

Comment 13

[David Mandelin [:dmandelin]]

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

[Benjamin Smedberg]

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.

Comment 15

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Fixed on mozilla-central: http://hg.mozilla.org/mozilla-central/rev/cdb8066f1da2

Comment 16

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

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.

Comment 17

[Martijn Wargers (dead)]

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)

Comment 18

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

Comment on attachment 351475 [details] [diff] [review]
patch

a191=beltzner; should this not also be marked blocking?

Comment 19

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Fixed on 1.9.1: http://hg.mozilla.org/releases/mozilla-1.9.1/rev/593aa76b76f5

Comment 20

[Daniel Veditz [:dveditz]]

Comment on attachment 351475 [details] [diff] [review]
patch

Approved for 1.9.0.6, a=dveditz for release-drivers.

Comment 21

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Checked in to CVS trunk, 2008-12-22 07:44 -0800.

Comment 22

[Al Billings [:abillings - ex-MoCo]]

(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?

Comment 23

[Martijn Wargers (dead)]

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