Bug 143511 – JSON.stringify should throw stack overflow error

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Chris J. Shull]

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.

[Geoffrey Garen]

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.

[Radar WebKit Bug Importer]

<rdar://problem/20491535>

[Alexey Shvayka]

Created attachment 397165 [details]
Patch

[Alexey Shvayka]

(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

[Darin Adler]

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?

[Darin Adler]

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".

[Yusuke Suzuki]

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.

[Alexey Shvayka]

Created attachment 397192 [details]
Patch

Revert HashSet change, drop `static`, and adjust StringBuilde test.

[Alexey Shvayka]

(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?

[Yusuke Suzuki]

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.

[Alexey Shvayka]

(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.

[Ross Kirsling]

Comment on attachment 397192 [details]
Patch

LGTM, but is there no test262 coverage for this?

[Ross Kirsling]

Comment on attachment 397192 [details]
Patch

Oh ack, I've no idea how I missed the whole thread here. Reversing r+ just for that reason.

[Ross Kirsling]

Comment on attachment 397192 [details]
Patch

Er sorry, those comments precede the current patch and are addressed. Reinstating.

[Mark Lam]

Comment on attachment 397192 [details]
Patch

Hold on.  Why doesn't the isSafeToRecurse() checks work?

[Yusuke Suzuki]

(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?

[Mark Lam]

(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.

[Mark Lam]

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 ...

[Mark Lam]

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).

[Alexey Shvayka]

Created attachment 400903 [details]
Patch

Rename var, use >=, add isSafeToRecurseSoft() check, and add 2 test cases.

[Mark Lam]

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"?

[Alexey Shvayka]

(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.

[Alexey Shvayka]

Created attachment 400928 [details]
Patch

Rename var to `maximumSideStackRecursion` and fix test.

[Mark Lam]

(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.

[Alexey Shvayka]

Created attachment 401028 [details]
Patch

Add ASSERT and explanation on recursion.

[EWS]

Committed r262727: <https://trac.webkit.org/changeset/262727>

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