Bug 15123 – Self-replicating code makes Safari hang and eventually crash

• Component: DOM
• Status: RESOLVED FIXED

The attached test case makes Safari hang and eventually crash.

Created attachment 16168 [details]
Test case (will crash)

Causes Firefox to hang, too.

[David Kilzer (:ddkilzer)]

<rdar://problem/5453375>

[David Kilzer (:ddkilzer)]

Not a regression as Safari 2.0.4 (419.3) with original WebKit on Mac OS X 10.4.10 (8R218) also exhibits this behavior.

Console message (repeated ad nauseum until crash):

[6861] http://bugs.webkit.org/attachment.cgi?id=16168&action=view:Error - Recursion too deep

[chris reiss]

I've started working on this ...

[chris reiss]

This creates infinite recursion in WebCore::Document::write( ).

A simple fix seems to be to simply limit the depth of this recursion.

Would this break anything?  It's hard for me to envision a real world example 
more than a level or two deep (and those are pretty strange.)

Feedback welcome ...

[chris reiss]

I tested this on Firefox (3.6.3, ubuntu release) and it handled this gracefully, bailing at 150 levels deep.

I see mention of this bug here https://bugzilla.mozilla.org/show_bug.cgi?id=82042.   Their solution refers vaguely to 'recursion checks', i'm looking for the exact gecko code that implements this.

[chris reiss]

So gecko fixed this bug here, 
   https://bugzilla.mozilla.org/show_bug.cgi?id=197052.   

The patch imposes a recursion limit on document.write( ) of 20 (not 150, sorry.)

Since this has survived since mid 2008, this appears to be a safe fix.

Patch coming soon ...

[chris reiss]

bug 18689 appears to be a duplicate of this one.

[Alexey Proskuryakov]

> (not 150, sorry.)

Why not 150?

[chris reiss]

150 was a miscalculation on my part before i went into the Gecko source.

The Gecko limit is given here :

content/html/document/src/nsHTMLDocument.cpp:151

    #define NS_MAX_DOCUMENT_WRITE_DEPTH 20

[chris reiss]

Created attachment 79006 [details]
defense against infinite recursion in document.write( )

[WebKit Review Bot]

Attachment 79006 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/dom/html/level2/html/selfRepli..." exit_code: 1

Source/WebCore/dom/Document.cpp:2251:  Missing spaces around ==  [whitespace/operators] [3]
Source/WebCore/dom/Document.cpp:2251:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
Source/WebCore/dom/Document.cpp:2252:  Missing spaces around =  [whitespace/operators] [4]
Source/WebCore/dom/Document.h:1397:  Extra space between int and m_writeRecursionDepth  [whitespace/declaration] [3]
Total errors found: 4 in 4 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Adam Barth]

Comment on attachment 79006 [details]
defense against infinite recursion in document.write( )

View in context: https://bugs.webkit.org/attachment.cgi?id=79006&action=review

> WebCore/dom/Document.cpp:214
> +#define MAX_WRITE_RECURSION_DEPTH 20

We usually use constants instead of pre-processor macros.

> WebCore/dom/Document.cpp:425
> +    , m_tooDeepWriteRecursion(false)
> +    , m_writeRecursionDepth(0)

Why do we have both of these variables?  One would seem to be sufficient.

> WebCore/dom/Document.cpp:2222
> +    // Prevent DOS attack from self-replicating javascript which causes infinite recursion here

This comment isn't necessary.

> WebCore/dom/Document.cpp:2233
> +    if (m_tooDeepWriteRecursion) {
> +       m_writeRecursionDepth--;
> +       return;
> +    } else {
> +       m_writeRecursionDepth++;
> +    }

This logic doesn't make much sense to me.  Typically for these recursion-depth counts, we use a small class that increments the counter on construction and decrements the counter on destruction.  That way we know that we never leak a count.  There are examples of how to do this in the HTML parser related to the script nesting level.

[chris reiss]

Thanks for the quick feedback, i'll rework this to use const and a counter class.

As for the second variable,  m_tooDeepWriteRecursion,  and the odd logic here - 

> +    if (m_tooDeepWriteRecursion) {
> +       m_writeRecursionDepth--;
> +       return;
> +    } else {
> +       m_writeRecursionDepth++;
> +    }




these were counterintuitive to me too.  My first cut at fixing this just returned one level up when
 m_writeRecursionDepth > MAX_WRITE_RECURSION_DEPTH.   This didn't fix the crash.

I noticed that Gecko's fix included extra logic to 'panic' all the way up the stack the moment the recursion depth is exceeded.  
(see https://bug197052.bugzilla.mozilla.org/attachment.cgi?id=293907.)   

After a bit of research I found the javascript self-replication actually makes a tree of recursive calls like so - 

The first time through Script A appends an extra copy of itself : 

Script-A  -->  Script-A  + Script-A 

          -->  4 * Script-A

and so on.    So just bouncing up one level still allows a million or so copies to replicate.

Since the recursion is depth-first, Gecko takes the approach if the recursion depth has been 
exceeded, keep returning all the way up the stack.

[Adam Barth]

I mean, there's no way to stop this crash in general.  Is this a problem in the real world or only in pathological cases?

[chris reiss]

Not a real-world web page; but the bug makes for an easy DOS attack (with one line of javascript code, a page can be created which hangs and crashes any webkit based browser.)

Updated the patch just now, i'm pretty sure this will handle any simple case of recursive document.write( ) 's.

However, if a person is aware of the max-recursion-depth, it may be possible to come up with a somewhat more complicated variant ...

[Adam Barth]

(In reply to comment #16)
> Not a real-world web page; but the bug makes for an easy DOS attack (with one line of javascript code, a page can be created which hangs and crashes any webkit based browser.)

There are plenty of other one-liners that do the same thing.  There's no way for us to remove them all.

[chris reiss]

Created attachment 79213 [details]
updated fix to infinite recursion in document.write( )

[WebKit Review Bot]

Attachment 79213 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/dom/html/level2/html/selfRepli..." exit_code: 1

Source/WebCore/dom/Document.cpp:2248:  Tab found; better to use spaces  [whitespace/tab] [1]
Source/WebCore/dom/Document.cpp:2250:  Tab found; better to use spaces  [whitespace/tab] [1]
Total errors found: 2 in 4 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[chris reiss]

Created attachment 79215 [details]
updated fix w/ tabs(!) removed

[WebKit Review Bot]

Attachment 79213 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7548176

[Andreas Kling]

Comment on attachment 79215 [details]
updated fix w/ tabs(!) removed

View in context: https://bugs.webkit.org/attachment.cgi?id=79215&action=review

This patch needs a ChangeLog, please see http://trac.webkit.org/wiki/QtWebKitContrib for more information on how to make patches.

Also, there are a number of coding style violations and unnecessary whitespace changes, please fix those for the next iteration.

> WebCore/dom/Document.h:22
> - * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
> + * the Free Software Foundation, Inc.,killed myspace 51 Franklin Street, Fifth Floor,

Not sure what's going on here ;)

[Alexey Proskuryakov]

Comment on attachment 79215 [details]
updated fix w/ tabs(!) removed

View in context: https://bugs.webkit.org/attachment.cgi?id=79215&action=review

It seems fine to fix this specific case that Firefox gets right, but I'll let it for others (Adam) to decide.

The below are just some style nits.

Please do add ChangeLogs: http://webkit.org/coding/contributing.html

> WebCore/dom/Document.h:22
> + * the Free Software Foundation, Inc.,killed myspace 51 Franklin Street, Fifth Floor,

I didn't know that!

> WebCore/dom/Document.h:1383
> +    bool m_tooDeepWriteRecursion;

For better readability, "m_writeRecursionIsTooDeep".

> WebCore/dom/Document.h:1384
> +    unsigned int m_writeRecursionDepth;

We just use "unsigned", not "unsigned int".

> WebCore/dom/Document.cpp:100
> +#include "NestingLevelIncrementer.h"
>  #include "MediaQueryList.h"

Includes should be in alphabetical order.

> WebCore/dom/Document.cpp:215
> +static const  int cMaxWriteRecursionDepth= 20;

There shouldn't be two spaces between const and int, and there should be a space before "=".

> WebCore/dom/Document.cpp:2226
> +    m_tooDeepWriteRecursion = (m_writeRecursionDepth>1) && m_tooDeepWriteRecursion;
> +    m_tooDeepWriteRecursion = (m_writeRecursionDepth>cMaxWriteRecursionDepth) || m_tooDeepWriteRecursion;

There should be spaces around ">".

> WebCore/dom/Document.cpp:2242
>      if (!hasInsertionPoint && m_ignoreDestructiveWriteCount)
>          return;
>  
> +
>      if (!hasInsertionPoint)
>          open(ownerDocument);

Why did you add this empty line?

> WebCore/dom/Document.cpp:2250
> -#endif    
> +#endif   

You removed one space, which is fine, but why not the other three?

> LayoutTests/dom/html/level2/html/selfReplicatingJS.html:6
> +<script type='text/javascript' src='selfhtml.js'></script><script type='text/javascript'>function loadComplete() { startTest(); }</script></HEAD>

Please don't add new tests to LayoutTests/dom, and use an appropriate subdirectory of LayoutTests/fast/dom instead. These are imported W3C tests.

[WebKit Review Bot]

Attachment 79215 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7595185

[chris reiss]

Created attachment 79455 [details]
multiple style fixes, layout tests removed, changelogs updated

[chris reiss]

Created attachment 79975 [details]
fix for document write recursion

Changed max recursion depth by 1 so output exactly matches that of Firefox.

[chris reiss]

To summarize, this patch is the same logic as in FireFox patch https://bug197052.bugzilla.mozilla.org/attachment.cgi?id=293907 in bug 
https://bugzilla.mozilla.org/show_bug.cgi?id=197052 .

This latest tweak corrects an off-by-one count so that webkit's output matches that of firefox.

IE also handles this special case, but with a lower max recursion depth.

[chris reiss]

Created attachment 80078 [details]
same as above, updated to merge cleanly

[Adam Barth]

Comment on attachment 80078 [details]
same as above, updated to merge cleanly

View in context: https://bugs.webkit.org/attachment.cgi?id=80078&action=review

> Source/WebCore/dom/Document.cpp:105
> +#include "NestingLevelIncrementer.h"

Technically we shouldn't be including headers from the parser directory in other parts of the project.  Ideally we'd move this class to WebCore/platform or to WTF, but I'm not going to make you do that in this patch.  It would be nice to do as a follow-up patch though.

> Source/WebCore/dom/Document.cpp:2256
> +    NestingLevelIncrementer nestingLevelIncrementer(m_writeRecursionDepth);

I worry that the parser can destroy the document and then we'll be twiddling unallocated memory in this object's destructor.  If you look inside the parser, you'll see that it refs the document in some cases.  Some of the comments there or the svn blame for when those refs were added should give you some ideas for how to write a test to see this issue.

> Source/WebCore/dom/Document.cpp:2259
> +    m_writeRecursionIsTooDeep = (m_writeRecursionDepth > 1) && m_writeRecursionIsTooDeep;
> +    m_writeRecursionIsTooDeep = (m_writeRecursionDepth > cMaxWriteRecursionDepth) || m_writeRecursionIsTooDeep;

It's slightly strange that after we panic to the top of the stack m_writeRecursionIsTooDeep is still true even though there's not recursing on the stack.  m_writeRecursionIsTooDeep only gets cleared when write is finally called again with a clean stack.  I'm not sure I see a clean way of clearing the variable though...

> Source/WebCore/ChangeLog:7
> +        Self-replicating code makes Safari hang and eventually crash
> +        https://bugs.webkit.org/show_bug.cgi?id=15123
> +

It would be nice to explain more about why we're making this change.  For example, I would mention that we're trying to match Firefox, which is where these values and the "panic to the top of the stack" behavior come from.

[Adam Barth]

See HTMLDocumentParser::insert for the ref() issue.

[Adam Barth]

Here's the change where those refs were added:

http://trac.webkit.org/changeset/65692

We should test patterns like the ones tested in that patch together with this panic / unwinding code.

[chris reiss]

So if I understand you correctly, what's needed is this guard code : 

    RefPtr<Document> protect(this);
    {
       NestingLevelIncrementer nestingLevelIncrementer(m_writeRecursionDepth);

         m_writeRecursionIsTooDeep = (m_writeRecursionDepth > 1) && m_writeRecursionIsTooDeep;
         m_writeRecursionIsTooDeep = (m_writeRecursionDepth > cMaxWriteRecursionDepth) || m_writeRecursionIsTooDeep;

        if (m_writeRecursionIsTooDeep)
           return;
    }

and then essentially the same tests as for http://trac.webkit.org/changeset/65692

?

[Adam Barth]

(In reply to comment #32)
> So if I understand you correctly, what's needed is this guard code :

It's a question.  It might be the case that the parser gets blown away but the document remains.  In any case, we should add the tests.  If the test pass then we don't need to change the code.  If the tests crash, we'll want to not crash.  :)

[chris reiss]

Created attachment 80488 [details]
write recursion fix

added tests (non-crashing) and explanation to change-log.

[Adam Barth]

Comment on attachment 80488 [details]
write recursion fix

View in context: https://bugs.webkit.org/attachment.cgi?id=80488&action=review

Thanks for adding the extra tests!

> LayoutTests/fast/dom/Document/document-close-iframe-load.html:6
> +<!--iframe onload="document.open();document.close();" -->

Is there a reason this is commented out? This test doesn't seem like it tests very much...

> LayoutTests/fast/dom/Document/document-close-iframe-load-expected.txt:2
> +ALERT: PASS (just to make expected.txt non-empty)
> +

I'm not sure how this expected file gets generated here.

[chris reiss]

you're right, that shouldn't be commented out, shall i patch on top of it once this lands to correct that?  (i did test with the comments removed!)

[Adam Barth]

(In reply to comment #36)
> you're right, that shouldn't be commented out, shall i patch on top of it once this lands to correct that?  (i did test with the comments removed!)

I'd just upload a new version of the patch.  The commit-queue should reject the patch if the test fails.  :)

[WebKit Commit Bot]

Comment on attachment 80488 [details]
write recursion fix

Rejecting attachment 80488 [details] from commit-queue.

Failed to run "['./Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '--bot-id=cr-jail-8', 'build-..." exit_code: 2

Last 500 characters of output:
....................................................................................................................
fast/dom/Attr ....
fast/dom/CSSStyleDeclaration .....
fast/dom/DOMException ....
fast/dom/DOMImplementation .....
fast/dom/Document .....
fast/dom/Document/document-close-iframe-load.html -> failed

Exiting early after 1 failures. 7141 tests run.
150.05s total testing time

7140 test cases (99%) succeeded
1 test case (<1%) had incorrect layout
4 test cases (<1%) had stderr output

Full output: http://queues.webkit.org/results/7506476

[chris reiss]

Created attachment 80647 [details]
write recursion fix

Fixed layout test ...

[chris reiss]

Created attachment 80648 [details]
write recursion fix

fixed Layout test

[Eric Seidel (no email)]

Comment on attachment 80488 [details]
write recursion fix

Cleared Adam Barth's review+ from obsolete attachment 80488 [details] so that this bug does not appear in http://webkit.org/pending-commit.

[WebKit Commit Bot]

Comment on attachment 80648 [details]
write recursion fix

Rejecting attachment 80648 [details] from commit-queue.

Failed to run "['./Tools/Scripts/webkit-patch', '--status-host=queues.webkit.org', '--bot-id=cr-jail-8', 'build-..." exit_code: 2

Last 500 characters of output:
.................................................................................................................
fast/dom/Attr ....
fast/dom/CSSStyleDeclaration .....
fast/dom/DOMException ....
fast/dom/DOMImplementation .....
fast/dom/Document ..........
fast/dom/Document/document-write-recursion.html -> failed

Exiting early after 1 failures. 7149 tests run.
150.76s total testing time

7148 test cases (99%) succeeded
1 test case (<1%) had incorrect layout
4 test cases (<1%) had stderr output

Full output: http://queues.webkit.org/results/7685464

[chris reiss]

Created attachment 80827 [details]
write recursion fix

Another test fix.   Apologies to adam!

[WebKit Commit Bot]

Comment on attachment 80827 [details]
write recursion fix

Clearing flags on attachment: 80827

Committed r77333: <http://trac.webkit.org/changeset/77333>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Adam Barth]

Yay~

[Adam Barth]

*** Bug 18689 has been marked as a duplicate of this bug. ***