Bug 143511 - JSON.stringify should throw stack overflow error
Summary: JSON.stringify should throw stack overflow error
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Minor
Assignee: Alexey Shvayka
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2015-04-07 21:16 PDT by Chris J. Shull
Modified: 2020-06-11 03:41 PDT (History)
12 users (show)

See Also:


Attachments
Patch (7.88 KB, patch)
2020-04-21 21:35 PDT, Alexey Shvayka
no flags Details | Formatted Diff | Diff
Patch (6.94 KB, patch)
2020-04-22 08:15 PDT, Alexey Shvayka
no flags Details | Formatted Diff | Diff
Patch (7.77 KB, patch)
2020-06-02 23:47 PDT, Alexey Shvayka
no flags Details | Formatted Diff | Diff
Patch (7.76 KB, patch)
2020-06-03 09:21 PDT, Alexey Shvayka
no flags Details | Formatted Diff | Diff
Patch (8.28 KB, patch)
2020-06-04 09:15 PDT, Alexey Shvayka
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Chris J. Shull 2015-04-07 21:16:02 PDT
The following line of code will hang WebKit. 
Don't even get a "Maximum call stack size exceeded" error.

JSON.stringify({ toJSON: function () { return { foo: this }; } });

Reproduces in Safari Version 8.0.5 (10600.5.9), as well as nightly build r182472.

Expected: a "TypeError: JSON.stringify cannot serialize cyclic structures." should be thrown.
Comment 1 Geoffrey Garen 2015-04-09 16:36:05 PDT
Two problems here:

(1) The stringifier checks for recursion, but not inside appendNextProperty.

(2) The recursion check walks the whole stack, so it is worst case O(N^2). We should use a hash instead.
Comment 2 Radar WebKit Bug Importer 2015-04-09 16:38:57 PDT
<rdar://problem/20491535>
Comment 3 Alexey Shvayka 2020-04-21 21:35:00 PDT
Created attachment 397165 [details]
Patch
Comment 4 Alexey Shvayka 2020-04-21 22:02:42 PDT
(In reply to Chris J. Shull from comment #0)
> JSON.stringify({ toJSON: function () { return { foo: this }; } });
> 
> Expected: a "TypeError: JSON.stringify cannot serialize cyclic structures."
> should be thrown.

Please note that `toJSON` creates a new object on every call, so JSON.stringify never reaches `this` to throw TypeError per spec.

Proposed patch throws stack overflow error like other runtimes do.
Cold runs, --outer 8:

                                            TipOfTree              patch

json-stringify-deep-stack                868.4032+-7.1116     833.3949+-9.5908
Comment 5 Darin Adler 2020-04-21 22:19:52 PDT
Comment on attachment 397165 [details]
Patch

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

> Source/JavaScriptCore/ChangeLog:17
> +        b) Significantly improves performance of cyclic structures checks by using
> +        HashSet: 4.2% speed-up on provided microbenchmark that tests serialization
> +        of deeply nested object.

Before we used a MarkedArgumentBuffer. Is it OK that the HashSet is not marked? Garbage collection will scan a MarkedArgumentBuffer, but not a HashSet. If it is OK, why?
Comment 6 Darin Adler 2020-04-21 22:23:08 PDT
Comment on attachment 397165 [details]
Patch

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

> Source/JavaScriptCore/runtime/JSONObject.cpp:319
> +static constexpr unsigned maximumRecursion = 40000;

I don’t think we need "static" with "constexpr".
Comment 7 Yusuke Suzuki 2020-04-21 22:56:44 PDT
Comment on attachment 397165 [details]
Patch

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

> Source/JavaScriptCore/runtime/JSONObject.cpp:-134
> -    MarkedArgumentBuffer m_objectStack;

Using MarkedArgumentBuffer is necessary. Otherwise, sophisticated input can cause GC crash.
Comment 8 Alexey Shvayka 2020-04-22 08:15:01 PDT
Created attachment 397192 [details]
Patch

Revert HashSet change, drop `static`, and adjust StringBuilde test.
Comment 9 Alexey Shvayka 2020-04-22 08:20:35 PDT
(In reply to Yusuke Suzuki from comment #7)
> Using MarkedArgumentBuffer is necessary. Otherwise, sophisticated input can
> cause GC crash.

I had a sense there is good reason why `m_objectStack` duplicates `m_holderStack`, now I got it!
I wonder if WeakSet can be used instead of MarkedArgumentBuffer here?
Comment 10 Yusuke Suzuki 2020-05-30 23:24:34 PDT
Comment on attachment 397192 [details]
Patch

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

Nice, I have suggestion about this check.

> Source/JavaScriptCore/runtime/JSONObject.cpp:414
> +    if (UNLIKELY(m_holderStack.size() > maximumRecursion)) {
> +        throwStackOverflowError(m_globalObject, scope);
> +        return StringifyFailed;
> +    }
> +

For these entry-point of recursive calls, how about using  `if (UNLIKELY(!vm.isSafeToRecurseSoft()))` check instead?
Since isSafeToRecurseSoft reads current stack-pointer, it offers better stack handling I think.

> Source/JavaScriptCore/runtime/JSONObject.cpp:652
> +                if (UNLIKELY(markedStack.size() > maximumRecursion))

Ditto.

> Source/JavaScriptCore/runtime/JSONObject.cpp:705
> +                if (UNLIKELY(markedStack.size() > maximumRecursion))

Ditto.
Comment 11 Alexey Shvayka 2020-06-02 07:47:22 PDT
(In reply to Yusuke Suzuki from comment #10)
> For these entry-point of recursive calls, how about using  `if
> (UNLIKELY(!vm.isSafeToRecurseSoft()))` check instead?
> Since isSafeToRecurseSoft reads current stack-pointer, it offers better
> stack handling I think.

I've tried vm.isSafeToRecurseSoft(), vm.isSafeToRecurse(), and m_stackCheck.isSafeToRecurse(): none of them passes the test as (I suspect) recursion happens in C++ code, while VM stack is empty.
Comment 12 Ross Kirsling 2020-06-02 08:23:29 PDT
Comment on attachment 397192 [details]
Patch

LGTM, but is there no test262 coverage for this?
Comment 13 Ross Kirsling 2020-06-02 08:24:31 PDT Comment hidden (obsolete)
Comment 14 Ross Kirsling 2020-06-02 08:25:37 PDT Comment hidden (obsolete)
Comment 15 Mark Lam 2020-06-02 09:06:24 PDT
Comment on attachment 397192 [details]
Patch

Hold on.  Why doesn't the isSafeToRecurse() checks work?
Comment 16 Yusuke Suzuki 2020-06-02 09:18:03 PDT
(In reply to Mark Lam from comment #15)
> Comment on attachment 397192 [details]
> Patch
> 
> Hold on.  Why doesn't the isSafeToRecurse() checks work?

Yeah, this sounds very strange. isSafeToRecurse etc. is using C stack pointer.

1123     bool isSafeToRecurse(void* stackLimit) const
1124     {
1125         void* curr = currentStackPointer();
1126         return curr >= stackLimit;
1127     }

So, it should work on C++ / JS. Can you investigate why isSafeToRecurse is not working?
Comment 17 Mark Lam 2020-06-02 09:21:02 PDT
(In reply to Yusuke Suzuki from comment #16)
> (In reply to Mark Lam from comment #15)
> > Comment on attachment 397192 [details]
> > Patch
> > 
> > Hold on.  Why doesn't the isSafeToRecurse() checks work?
> 
> Yeah, this sounds very strange. isSafeToRecurse etc. is using C stack
> pointer.
> 
> 1123     bool isSafeToRecurse(void* stackLimit) const
> 1124     {
> 1125         void* curr = currentStackPointer();
> 1126         return curr >= stackLimit;
> 1127     }
> 
> So, it should work on C++ / JS. Can you investigate why isSafeToRecurse is
> not working?

I think I know what the issue here is: you're not seeing a stack overflow with the isSafeToRecurse() check because the test never actually overflowed, and we still have ample stack to run with.  V8 and FF may have placed an artificial lower bounds on the depth of the parse so that they can throw a stack overflow error even though the real stack never overflowed.

With that in mind, let me think of the proper way to address this, and if we want to address it.
Comment 18 Mark Lam 2020-06-02 09:56:39 PDT
Comment on attachment 397192 [details]
Patch

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

> JSTests/stress/json-stringify-stack-overflow.js:29
> +{
> +    const obj = {};
> +    obj.toJSON = function() { return {key: obj}; };
> +
> +    shouldThrow(function() {
> +        JSON.stringify(obj);
> +    });
> +
> +    shouldThrow(function() {
> +        JSON.stringify({a: {b: obj}});
> +    });
> +}

This case is interesting in motivating this investigation.  From JS' perspective, this looks like infinite recursion.  But if we look at bottom of Stringifier::appendStringifiedValue(), we'll see that we do our parsing using a side stack m_holderStack which is aches codetually a Vector.

Stepping thru the code, I see that we're stuck here:

    do {
        while (m_holderStack.last().appendNextProperty(*this, builder)) // <========== this never returns false because we have an infinite number of objects to add.
            RETURN_IF_EXCEPTION(scope, StringifyFailed);

So, this code will happily iterate in that while loop until m_holderStack overflows.  Since m_holderStack is a Vector, it will only overflow when its size is > UINT_MAX.  UINT_MAX is 4G worth of elements.  The script can run a very long time before it gets there.

With this in mind, Alexey's solution of imposing a cap on m_holderStack growth is a correct solution.  However, I'd like to give a bit more thought to how and where that check should go.  More feedback in a bit ...
Comment 19 Mark Lam 2020-06-02 10:26:27 PDT
Comment on attachment 397192 [details]
Patch

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

r=me with fixes.

> Source/JavaScriptCore/runtime/JSONObject.cpp:319
> +constexpr unsigned maximumRecursion = 40000;

Let's call this "maximumHolderStackRecursion".  "maximumRecursion" can logically work, but is just too misleading as it strongly suggests that it has to do with native stack recursion instead of the side stack.

> Source/JavaScriptCore/runtime/JSONObject.cpp:410
> +    if (UNLIKELY(m_holderStack.size() > maximumRecursion)) {

Let's make this "m_holderStack.size() >= maximumRecursion" instead of ">".  The reason is that we're about to add one more entry below.  If we check for "> max", then we'll end up allow max + 1 entries which is not what the name says.  Technically, "== max" is sufficient, but ">= max" is a stronger guarantee in case bugs creep in later.

Additionally, since Stringifier::appendStringifiedValue() can call Stringifier::Holder::appendNextProperty(), and Stringifier::Holder::appendNextProperty() can call Stringifier::appendStringifiedValue(), we have the makings of true native stack recursion.  Though I don't think your tests will take this path of recursion (and I didn't work on it enough to figure out to get there), we should add a real stack recursion check.  Let's add the following to the top of Stringifier::appendStringifiedValue() after the declaration of the ThrowScope:

    if (UNLIKELY(!vm.isSafeToRecurseSoft())) {
        throwStackOverflowError(m_globalObject, scope);
        return StringifyFailed;
    }

Would be nice if you can figure out a test for this overflow too, but I won't insist on that.  If you do add just a test, I recommend that at the top of the test JS file, insert the following line:
//@ requireOptions("--maxPerThreadStackUsage=204800")

That will allow the test to run with a smaller stack, and cause vm.isSafeToRecurseSoft() to return false sooner.  In this example, I specified a stack size of 200 KB.  Please adjust it as needed to allow your test to run (in case it's too small or too big).
Comment 20 Alexey Shvayka 2020-06-02 23:47:51 PDT
Created attachment 400903 [details]
Patch

Rename var, use >=, add isSafeToRecurseSoft() check, and add 2 test cases.
Comment 21 Mark Lam 2020-06-02 23:59:22 PDT
Comment on attachment 400903 [details]
Patch

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

> Source/JavaScriptCore/runtime/JSONObject.cpp:652
> +                if (UNLIKELY(markedStack.size() >= maximumHolderStackRecursion))

The "maximumHolderStackRecursion" name doesn't work here since there's no holderStack in this function.  If you want to use this same symbol for both cases, how about renaming it to something like "maximumSideStackRecursion"?
Comment 22 Alexey Shvayka 2020-06-03 09:21:41 PDT
(In reply to Ross Kirsling from comment #12)
> Comment on attachment 397192 [details]
> Patch
> 
> LGTM, but is there no test262 coverage for this?

Please see https://github.com/tc39/test262/pull/2517.

(In reply to Mark Lam from comment #19)
> Comment on attachment 397192 [details]
> Patch

Thank you for thorough investigation, Mark.

> Would be nice if you can figure out a test for this overflow too, but I
> won't insist on that.

I took some time to fiddle with various inputs and am quite positive that !vm.isSafeToRecurseSoft() check never passes:
Stringifier was carefully designed to prevent its methods from recursing.
The check will be useful in case of refactoring though.
Comment 23 Alexey Shvayka 2020-06-03 09:21:55 PDT
Created attachment 400928 [details]
Patch

Rename var to `maximumSideStackRecursion` and fix test.
Comment 24 Mark Lam 2020-06-03 10:02:04 PDT
(In reply to Alexey Shvayka from comment #22)
> (In reply to Ross Kirsling from comment #12)
> > Comment on attachment 397192 [details]
> > Patch
> > 
> > LGTM, but is there no test262 coverage for this?
> 
> Please see https://github.com/tc39/test262/pull/2517.
> 
> (In reply to Mark Lam from comment #19)
> > Comment on attachment 397192 [details]
> > Patch
> 
> Thank you for thorough investigation, Mark.
> 
> > Would be nice if you can figure out a test for this overflow too, but I
> > won't insist on that.
> 
> I took some time to fiddle with various inputs and am quite positive that
> !vm.isSafeToRecurseSoft() check never passes:
> Stringifier was carefully designed to prevent its methods from recursing.
> The check will be useful in case of refactoring though.

I can believe that though I can't say it with confidence since I don't understand yet how it achieves this.  Best practices for something like this would be to explain in the ChangeLog how the mechanism works to guarantee this, and then add an ASSERT or RELEASE_ASSERT on vm.isSafeToRecurseSoft() to document and enforce that guarantee in case someone breaks the mechanism with some edit in the future.

In terms of performance cost, the check you've added costs the same as the check for the assertion (unless we go with a debug ASSERT).  One alternative you can do is keep the runtime check in case of bugs, and add a debug ASSERT(vm.isSafeToRecurseSoft()) before it so that if the mechanism breaks, our testing might catch it.  Probably needs a brief comment there to document that the runtime check is a conservative fail safe backup in case the mechanism that enforces no runaway recursion breaks.
Comment 25 Alexey Shvayka 2020-06-04 09:15:33 PDT
Created attachment 401028 [details]
Patch

Add ASSERT and explanation on recursion.
Comment 26 EWS 2020-06-08 11:11:05 PDT
Committed r262727: <https://trac.webkit.org/changeset/262727>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 401028 [details].