HTML: Cap nesting depth

[DemiMarie]

Almost all HTML parsers are vulnerable to stack overflows and denial-of-service attacks, because HTML parsing can easily be made to exhibit quadratic behavior by deep nesting of documents, and because naive tree-traversal algorithms are recursive.

I propose that the nesting depth of an HTML document be capped at 500. Any attempt to insert a node at a depth past that is erroneous — DOM APIs throw exceptions, while an implicit end tag is inserted if this is encountered during parsing.

[domenic]

I don't believe that preventing pages from crashing themselves is in our threat model, but maybe @whatwg/security can confirm.

[DemiMarie]

The problem is that while every modern browser uses a multiprocess architecture, there are entities that parse HTML other than browsers, and these are subject to the same attacks. They should not need to parse HTML to different parse trees for security.

On Sun, Jun 3, 2018, 9:33 PM Domenic Denicola notifications@github.com wrote:

I don't believe that preventing pages from crashing themselves is in our threat model, but maybe @whatwg/security https://github.com/orgs/whatwg/teams/security can confirm.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/whatwg/html/issues/3732#issuecomment-394211720, or mute the thread https://github.com/notifications/unsubscribe-auth/AGGWB5aBSAvhujFJK2SuXNjUmwVE56HXks5t5I51gaJpZM4UYO5A .

[domenic]

Those parsers aren't covered by this specification; if that is your concern, you should file issues on those parsers instead of on the specification for web browsers.

[DemiMarie]

Correct, they are not. But they are generally trying to follow it.

I know of no way that a server side application can safely parse HTML according to the specs and not be vulnerable to denial of service attacks.

Furthermore, Safari already has a nesting limit in its parser. Firefox and Chrome don’t. I think that there should be a single nesting limit that applies everywhere.

On Sun, Jun 3, 2018, 9:36 PM Domenic Denicola notifications@github.com wrote:

Those parsers aren't covered by this specification; if that is your concern, you should file issues on those parsers instead of on the specification for web browsers.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/whatwg/html/issues/3732#issuecomment-394212088, or mute the thread https://github.com/notifications/unsubscribe-auth/AGGWB_AbnHiQ4UueEEYsIOzGsodR006Zks5t5I86gaJpZM4UYO5A .

[domenic]

Thanks for the clarification. I'll close this, and you can file bugs on those other parsers if you want them to not follow the spec (which makes sense for non web browsers with different threat models), and on Safari if you want it to follow the spec.

[domenic]

Reopening as I forgot I wanted to wait a while to confirm the threat model with @whatwg/security. Please forgive the sloppy 4am bug-triaging :)

[bzbarsky]

@domenic Firefox and Blink (as of Sept 2017 at least) also violate the current HTML parsing spec at large nesting depths, fwiw. They just violate it in a different way than Safari (and different versions of Firefox do it slightly differently).

Please see discussion and testcases in https://bugzilla.mozilla.org/show_bug.cgi?id=256180 and https://bugzilla.mozilla.org/show_bug.cgi?id=1188731 and https://groups.google.com/d/msg/mozilla.dev.platform/SUknMzK1ZAc/sMNBAjKCAgAJ (this last complete with @hsivonen saying "I'm rather unhappy about the prospect of having to examine another browser's HTML parser beyond reading the spec in order to achieve interop".... of course then he had to do just that with Blink, to achieve interop).

[bzbarsky]

And to be clear, a hard limit of 500 with failures when it's reached is probably not web-compatible enough, but it's hard to say without more data.

[DemiMarie]

I was thinking to fail if is added by JS, but otherwise to close the tag before adding a new one.

On Sun, Jun 3, 2018, 11:38 PM Boris Zbarsky notifications@github.com wrote:

And to be clear, a hard limit of 500 with failures when it's reached is probably not web-compatible enough, but it's hard to say without more data.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/whatwg/html/issues/3732#issuecomment-394226008, or mute the thread https://github.com/notifications/unsubscribe-auth/AGGWB6BSWzCoiEpxH_9y-Jz2Q6zhBhEWks5t5KuXgaJpZM4UYO5A .

[bzbarsky]

Does any browser have the "fail if added by JS" behavior?

For the other, please check with @hsivonen what his investigations mentioned above showed.

[zcorpan]

The HTML parser already has some limits, I don't see a problem in principle to specify this one as well.

[hsivonen]

The Gecko-side status is:

1. I want Gecko's parser limit to match Blink's parser limit exactly. Blink's magic number is 512, but if you put it in the spec, be sure to check that you count the same way as Blink and use the same comparison operator. (My Gecko patch has 511 as the magic number in order to get the same black-box behavior with different counting.) Please don't invent a new arbitrary number (i.e. please don't make it 500 exactly for no good reason).
2. It's very important that the parser not throw away nodes but instead reparent them. See the nodeFromStackWithBlinkCompat() method in my patch
3. The Gecko parser patch needs a corresponding layout patch to allow deeper frame construction.
4. The patches haven't landed, because I failed to figure out how to increase the runtime stack on Android so as to not crash on Robohornet with the higher layout limits. Robohornet says "RoboHornet is a benchmark designed around performance pain points real web developers care about." Yet, it creates an unrealistically deep DOM tree. Still, the abandoned benchmark is out there and it would look bad if Firefox for Android crashed on it. So in the mean time, some webmail users don't see parts of emails from MUAs that generate bad HTML. But hey, at least we don't crash on an unrealistic benchmark.

I'm not convinced that we need to make DOM APIs throw at a certain depth limit. Has interop on that point been a problem in practice. (It is on the parser side.)

[DemiMarie]

It is if we want to ensure that browsers do not stack overflow. Stack overflow can be exploited in practice — for instance, they can be used for a denial-of-service attack on in-process webviews (as found on iOS), and I believe they can be exploited for arbitrary code execution in certain cases.

On Mon, Jun 4, 2018, 7:55 AM Henri Sivonen notifications@github.com wrote:

The Gecko-side status is:

1. I want Gecko's parser limit to match Blink's parser limit exactly. Blink's magic number is 512, but if you put it in the spec, be sure to check that you count the same way as Blink and use the same comparison operator. (My Gecko patch has 511 as the magic number in order to get the same black-box behavior with different counting.) Please don't invent a new arbitrary number (i.e. please don't make it 500 exactly for no good reason).
2. It's very important that the parser not throw away nodes but instead reparent them. See the nodeFromStackWithBlinkCompat() method in my patch https://reviewboard.mozilla.org/r/178790/diff/21#index_header
3. The Gecko parser patch needs a corresponding layout patch to allow deeper frame construction.
4. The patches haven't landed, because I failed to figure out how to increase the runtime stack on Android so as to not crash on Robohornet with the higher layout limits. Robohornet says "RoboHornet is a benchmark designed around performance pain points real web developers care about." Yet, it creates an unrealistically deep DOM tree. Still, the abandoned benchmark is out there and it would look bad if Firefox for Android crashed on it. So in the mean time, some webmail users don't see parts of emails from MUAs that generate bad HTML. But hey, at least we don't crash on an unrealistic benchmark.

I'm not convinced that we need to make DOM APIs throw at a certain depth limit. Has interop on that point been a problem in practice. (It is on the parser side.)

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/whatwg/html/issues/3732#issuecomment-394329075, or mute the thread https://github.com/notifications/unsubscribe-auth/AGGWBwBz3G3Of19G09NPwShW7g_9UxSrks5t5SA5gaJpZM4UYO5A .

[bzbarsky]

Stack overflow in the sense of "try to allocate stack and fail" is not the same as stack overflow in the sense of "try to write to the stack and write outside its bounds". The former is not exploitable to achieve code execution, to my knowledge, though I would love to see a reference if it is.

[DemiMarie]

It can be in kernel contexts. It also can be in userspace, if a single very large stack allocation occurs and skips the guard page.

That said, I still think that the risk of denial of service attacks alone warrants a limit. A web page should not be able to crash the host application, even if it runs in-process. Consider a browser that gets its security from being written almost entirely in a memory safe language, but which cannot support sandboxing because its host environment does not.

On Thu, Jun 7, 2018, 11:16 PM Boris Zbarsky notifications@github.com wrote:

Stack overflow in the sense of "try to allocate stack and fail" is not the same as stack overflow in the sense of "try to write to the stack and write outside its bounds". The former is not exploitable to achieve code execution, to my knowledge, though I would love to see a reference if it is.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/whatwg/html/issues/3732#issuecomment-395633674, or mute the thread https://github.com/notifications/unsubscribe-auth/AGGWB7mHJImZfsRr0tKkB4d2Vk-P1qAwks5t6eyigaJpZM4UYO5A .

[hsivonen]

That said, I still think that the risk of denial of service attacks alone warrants a limit.

I disagree. There are so many ways to crash a browser engine in a safe way by resource exhaustion that it only makes sense to put limits for cases that get easily triggered by accident. Countering deliberate resource exhaustion attacks by means other than letting a content process crash is futile.

The Gecko-side status is

The fix to align the HTML parser in Gecko with the HTML parser in Blink has landed. The Java diff is the easiest one to map back to spec text. There are reftests.

Now that Gecko and Blink agree, I think the behavior seen in the above Java diff should be put in the spec.

[hsivonen]

Specifically, in places where the code calls nodeFromStackWithBlinkCompat(), instead of taking the most-recently-pushed element from the tree builder stack, element at index 511 is taken if there are more elements on the stack. Assumes zero-based indexing where the "html" element is at index 0.

[domenic]

Although I still don't really understand the motivation for why browsers are doing this, we should indeed align the spec with implementations. @hsivonen, would you be willing to submit a pull request?

[bzbarsky]

Although I still don't really understand the motivation for why browsers are doing this,

Basically, to not crash any time you load e-mail stuff via the web. Unfortunately, (1) mail archive software tends to do a poor job of escaping the <foo@bar.org> bits in mail headers and just dumps it on the web as-is and (2) HTML mail creation tends to create hugely nested tag hierarchies because their many HTML editors are terrible.

And while preventing pages from crashing themselves deliberately is not in browsers' threat model, browsers do have incentive to not crash the gmail process when users click on something in their gmail inbox.

[DemiMarie]

And while preventing pages from crashing themselves deliberately is not in browsers' threat model, browsers do have incentive to not crash the gmail process when users click on something in their gmail inbox.

Furthermore, browsers are not the only programs that need to parse HTML. Server-side HTML sanitizers do as well, and there denial of service is a legitimate attack vector.

[rniwa]

The Gecko-side status is:

1. I want Gecko's parser limit to match Blink's parser limit exactly. Blink's magic number is 512, but if you put it in the spec, be sure to check that you count the same way as Blink and use the same comparison operator. (My Gecko patch has 511 as the magic number in order to get the same black-box behavior with different counting.) Please don't invent a new arbitrary number (i.e. please don't make it 500 exactly for no good reason).

FWIW, the limit comes from a 9 year old code change in WebKit before Blink fork so WebKit shares the same limit. We might as well as integrate the limit into the spec given all three major browsers agree on the parser limit at this point.

[othermaciej]

(Our current limit seems to be 512, notwithstanding that commit starting at 4096).

[hsivonen]

would you be willing to submit a pull request?

Unfortunately, I expect not to have time for this in the near future. However, if someone want to volunteer, I still recommend looking at the Java patch.