644526 - xml parser can generate deep DOM trees which crashes recursive layout algorithms

Status: RESOLVED DUPLICATE of bug 485941

(Core :: XML, defect)

Description

[max deliso [:delimax]]

User-Agent:       Mozilla/5.0 (Windows NT 5.1; rv:2.0) Gecko/20100101 Firefox/4.0
Build Identifier: Mozilla/5.0 (Windows NT 5.1; rv:2.0) Gecko/20100101 Firefox/4.0

When served with an xml file with node nesting of sufficient depth, the xul.dll module fails to return the 'depth exceeded' error and instead crashes and burns. It is possible that this bug could be used maliciously.

Reproducible: Always

Steps to Reproduce:
1. be running windows
2. start up firefox
3. load the example url
Actual Results:  
firefox crashes

Expected Results:  
firefox should return the xml error: Excessive node nesting.

xul.dll is the module at fault

Comment 1

[Brandon Sterne (:bsterne)]

Attachment: crash stack

Hmm, this isn't the stack I expected to get with this type of bug.  Here are the top 25 frames from my crash stack.

I wonder if we're calling nsTArrayInfallibleAllocator::Free on an invalid object.

Comment 2

[Jesse Ruderman]

Comment 0 sounds like bug 323394, but comment 1 doesn't.

Brandon, does your debugger tell you what address Firefox was trying to access that gave it a segfault?  In particular, is it in the end-of-stack guard page?

Comment 3

[Daniel Veditz [:dveditz]]

David: is this an expected resource-exhaustion crash with infallible malloc, or something worse? Wasn't really expecting a failure in free().

Comment 4

[max deliso [:delimax]]

My crash stack differs somewhat from the one posted by bsterne. In mine, the segfault occurs in the IsAncestorOf() function as the result of a NULL pointer dereference in the file ../mozilla/src/content/events/src/nsEventStateManager.cpp on line 4212. The generic cause is the same though, the mutually recursive functions AddFrameConstructionItemsInternal(..) and BuildInlineChildItems(..) call each other until some kind of unhandled resource exhaustion scenario plays out. Might I suggest adding code in one of the above mentioned functions to explicitly prevent recursions of a predetermined depth? I will write the patch and submit it for review if this is considered to be a good idea. Also, i've attached my crash stack and some other gdb information.

Comment 5

[max deliso [:delimax]]

Attachment: it's a crash stack

Comment 6

[max deliso [:delimax]]

Attachment: valgrind report

sorry for incorrectly setting the mime type of the previous attachment, this is a valgrind report confirming that the crash happens as the result of a stack overflow

Comment 7

[max deliso [:delimax]]

Attachment: this patch prevents firefox from crashing due to excessive xml node nesting

I found that this fixes the problem of xml documents with excessive node nesting crashing firefox, however I realize that there are a few problems with my approach. Firstly, I used a magic number to impose a hard limit upon the content stack for the xml content sink, where a symbolic constant is more appropriate. The reason for this is that I wasn't sure where to define the constant. Secondly, the number that I chose was somewhat arbitrary, and I believe it actually must be a lot larger. I'm not sure if theres some standards document that can be consulted in determining it's correct value or if the choice is going to have to be somewhat arbitrary. There are probably also other problems that I am unaware of, on account of my newbiness.

Comment 8

[Peter Van der Beken [:peterv]]

I think we haven't done these spot fixes in the past, since there are a number of other ways we can hit this (eg through DOM API calls) and we felt it didn't make sense to just fix one. Jonas, Boris, what do you think?

Comment 9

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Adjusting the summary as this doesn't appear to be due to buffer overflow, nor due to any problem in the parser itself. Feel free to adjust more (or back to what it was) if you disagree.

Yes, just fixing things in the parser isn't going to prevent any attacker, since you can do exactly the same thing using the DOM.

The reason we have a similar limit in the HTML parser is that it's very easy to *accidentally* create HTML markup which generate very deeply nested trees. So the limit there isn't to prevent attackers, but rather to prevent the causal webdev from crashing users.


I also don't think that there is anything exploitable here. Exhausting the stack should simply cause the OS to kill the process.


That said, I'm fine with taking a limit in the XML parser, as long as we can make the limit sufficiently deep. I don't want to harm people that load XML documents using XMLHttpRequest or similar unless it brings tangible benefits. And as far as I know we don't see a lot of people crashing due to overly deep DOM trees, nor do we know of any exploits that are made possible by it.

Comment 10

[Jesse Ruderman]

The adjusted summary makes this a dup of bug 323394.  But did we ever figure out what was going on in comment 1?

Comment 11

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

> Hmm, this isn't the stack I expected to get with this type of bug.  Here are
> the top 25 frames from my crash stack.

Whenever you crash due to stack exhaustion the top of the stack will almost always be some random piece of code which is called by the recursive algorithm.

Most recursive algorithms will call into other pieces of code which all use stack space. In other words such calls will "dip deeper" into the stack. Whichever such dip happens to reach the stack limit first will be the one to appear at the top of the stack.

The interesting part for stack exhausting is the reoccurring pattern a bit higher up on the stack.

> I wonder if we're calling nsTArrayInfallibleAllocator::Free on an invalid
> object.

Your stack is currently in the process of freeing memory, so I doubt it.

Comment 12

[Jesse Ruderman]

Ok.

I guess this isn't quite a dup of bug 323394, because this bug proposes a workaround in the XML parser rather than a solution to the more general problem.

Comment 13

[Boris Zbarsky [:bzbarsky]]

> Jonas, Boris, what do you think?

I think comment 9 sort of summarizes my views, with an emphasis on the last paragraph.

Comment 14

[max deliso [:delimax]]

So we're sort of in agreement that we should impose a hard limit on the XML parser's recursion depth? In that case, there must be a way to do this that is more elegant than what I proposed in comment 7.

Comment 15

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

Well, there seems to be agreement that we want to impose limits on the *DOM*. I.e. not changing anything about the parser, but rather modifying the DOM code such that you can't construct DOMs which are "too deep" through any means.

But there also doesn't seem to be any urgency with this since as far as we know so far there are no exploitable problems here, nor do we think a lot of users are running into this problem.

However in particular the last statement (not a lot of users are running into this) is something that we don't have very good data on at this time.