Bug 15123 - Self-replicating code makes Safari hang and eventually crash
Summary: Self-replicating code makes Safari hang and eventually crash
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P1 Normal
Assignee: Nobody
URL:
Keywords: HasReduction, InRadar
: 18689 (view as bug list)
Depends on:
Blocks:
 
Reported: 2007-08-31 05:44 PDT by mitz
Modified: 2011-02-03 09:33 PST (History)
10 users (show)

See Also:


Attachments
Test case (will crash) (83 bytes, text/html)
2007-08-31 05:45 PDT, mitz
no flags Details
defense against infinite recursion in document.write( ) (3.64 KB, patch)
2011-01-14 14:50 PST, chris reiss
abarth: review-
Details | Formatted Diff | Diff
updated fix to infinite recursion in document.write( ) (3.95 KB, patch)
2011-01-17 13:55 PST, chris reiss
no flags Details | Formatted Diff | Diff
updated fix w/ tabs(!) removed (3.95 KB, patch)
2011-01-17 14:07 PST, chris reiss
kling: review-
Details | Formatted Diff | Diff
multiple style fixes, layout tests removed, changelogs updated (4.51 KB, patch)
2011-01-19 11:24 PST, chris reiss
no flags Details | Formatted Diff | Diff
fix for document write recursion (4.51 KB, patch)
2011-01-24 14:11 PST, chris reiss
no flags Details | Formatted Diff | Diff
same as above, updated to merge cleanly (4.67 KB, patch)
2011-01-25 10:23 PST, chris reiss
no flags Details | Formatted Diff | Diff
write recursion fix (8.04 KB, patch)
2011-01-28 13:09 PST, chris reiss
no flags Details | Formatted Diff | Diff
write recursion fix (8.08 KB, text/plain)
2011-01-31 09:27 PST, chris reiss
no flags Details
write recursion fix (8.08 KB, patch)
2011-01-31 09:32 PST, chris reiss
abarth: review+
commit-queue: commit-queue-
Details | Formatted Diff | Diff
write recursion fix (7.78 KB, patch)
2011-02-01 14:22 PST, chris reiss
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description mitz 2007-08-31 05:44:20 PDT
The attached test case makes Safari hang and eventually crash.
Comment 1 mitz 2007-08-31 05:45:17 PDT
Created attachment 16168 [details]
Test case (will crash)

Causes Firefox to hang, too.
Comment 2 David Kilzer (:ddkilzer) 2007-08-31 07:29:24 PDT
<rdar://problem/5453375>
Comment 3 David Kilzer (:ddkilzer) 2007-08-31 07:34:36 PDT
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

Comment 4 chris reiss 2011-01-05 08:38:52 PST
I've started working on this ...
Comment 5 chris reiss 2011-01-10 13:10:02 PST
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 ...
Comment 6 chris reiss 2011-01-10 14:26:17 PST
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.
Comment 7 chris reiss 2011-01-11 07:41:57 PST
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 ...
Comment 8 chris reiss 2011-01-11 08:59:37 PST
bug 18689 appears to be a duplicate of this one.
Comment 9 Alexey Proskuryakov 2011-01-11 09:08:12 PST
> (not 150, sorry.)

Why not 150?
Comment 10 chris reiss 2011-01-11 09:25:27 PST
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
Comment 11 chris reiss 2011-01-14 14:50:30 PST
Created attachment 79006 [details]
defense against infinite recursion in document.write( )
Comment 12 WebKit Review Bot 2011-01-14 14:53:36 PST
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.
Comment 13 Adam Barth 2011-01-14 17:05:32 PST
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.
Comment 14 chris reiss 2011-01-17 10:36:46 PST
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.
Comment 15 Adam Barth 2011-01-17 13:00:02 PST
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?
Comment 16 chris reiss 2011-01-17 13:34:35 PST
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 ...
Comment 17 Adam Barth 2011-01-17 13:40:07 PST
(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.
Comment 18 chris reiss 2011-01-17 13:55:57 PST
Created attachment 79213 [details]
updated fix to infinite recursion in document.write( )
Comment 19 WebKit Review Bot 2011-01-17 13:57:49 PST
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.
Comment 20 chris reiss 2011-01-17 14:07:44 PST
Created attachment 79215 [details]
updated fix w/ tabs(!) removed
Comment 21 WebKit Review Bot 2011-01-17 14:17:10 PST
Attachment 79213 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7548176
Comment 22 Andreas Kling 2011-01-17 14:18:37 PST
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 ;)
Comment 23 Alexey Proskuryakov 2011-01-17 14:20:04 PST
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.
Comment 24 WebKit Review Bot 2011-01-17 14:29:14 PST
Attachment 79215 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/7595185
Comment 25 chris reiss 2011-01-19 11:24:10 PST
Created attachment 79455 [details]
multiple style fixes, layout tests removed, changelogs updated
Comment 26 chris reiss 2011-01-24 14:11:15 PST
Created attachment 79975 [details]
fix for document write recursion

Changed max recursion depth by 1 so output exactly matches that of Firefox.
Comment 27 chris reiss 2011-01-24 14:20:14 PST
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.
Comment 28 chris reiss 2011-01-25 10:23:24 PST
Created attachment 80078 [details]
same as above, updated to merge cleanly
Comment 29 Adam Barth 2011-01-25 21:29:25 PST
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.
Comment 30 Adam Barth 2011-01-25 21:30:34 PST
See HTMLDocumentParser::insert for the ref() issue.
Comment 31 Adam Barth 2011-01-25 21:31:52 PST
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.
Comment 32 chris reiss 2011-01-28 11:03:14 PST
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

?
Comment 33 Adam Barth 2011-01-28 11:43:54 PST
(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.  :)
Comment 34 chris reiss 2011-01-28 13:09:22 PST
Created attachment 80488 [details]
write recursion fix

added tests (non-crashing) and explanation to change-log.
Comment 35 Adam Barth 2011-01-28 13:56:22 PST
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.
Comment 36 chris reiss 2011-01-28 15:21:28 PST
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!)
Comment 37 Adam Barth 2011-01-28 15:22:52 PST
(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.  :)
Comment 38 WebKit Commit Bot 2011-01-29 02:28:00 PST
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
Comment 39 chris reiss 2011-01-31 09:27:22 PST
Created attachment 80647 [details]
write recursion fix

Fixed layout test ...
Comment 40 chris reiss 2011-01-31 09:32:42 PST
Created attachment 80648 [details]
write recursion fix

fixed Layout test
Comment 41 Eric Seidel (no email) 2011-01-31 16:05:53 PST
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.
Comment 42 WebKit Commit Bot 2011-01-31 23:12:27 PST
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
Comment 43 chris reiss 2011-02-01 14:22:22 PST
Created attachment 80827 [details]
write recursion fix

Another test fix.   Apologies to adam!
Comment 44 WebKit Commit Bot 2011-02-01 16:23:04 PST
Comment on attachment 80827 [details]
write recursion fix

Clearing flags on attachment: 80827

Committed r77333: <http://trac.webkit.org/changeset/77333>
Comment 45 WebKit Commit Bot 2011-02-01 16:23:13 PST
All reviewed patches have been landed.  Closing bug.
Comment 46 Adam Barth 2011-02-01 16:29:08 PST
Yay~
Comment 47 Adam Barth 2011-02-03 09:33:55 PST
*** Bug 18689 has been marked as a duplicate of this bug. ***