json_decode() fails on nested input of around 10000 characters.

[maksverver]

Description

The following code:

<?php

function test($i, $s) {
  try {
    json_decode($s, false, 999999999, JSON_THROW_ON_ERROR);
    echo "Test $i passed\n";
  } catch (Exception $e) {
    echo "Test $i FAILED: $e\n";
  }
}

// String like [[[[...1...]]]] fails at length 9999, nesting depth 4999.
test(1, str_repeat('[', 4998) . '1' . str_repeat(']', 4998)); // pass
test(2, str_repeat('[', 4999) . '1' . str_repeat(']', 4999)); // FAIL

// String like [1,[1,[1,...1...]]] fails at length 10001, nesting depth 2499.
test(3, str_repeat('[1,', 2499) . '1' . str_repeat(']', 2499)); // pass
test(4, str_repeat('[1,', 2500) . '1' . str_repeat(']', 2500)); // FAIL

// Flat string like [[1],[1],[1]...] passes even at much greater length.
test(5, '[' . str_repeat('[1],', 9999) . '1]'); // pass

?>

Resulted in this output:

Test 1 passed
Test 2 FAILED: JsonException: Syntax error in json_decode_bug.php:5
Stack trace:
#0 json_decode_bug.php(5): json_decode()
#1 json_decode_bug.php(14): test()
#2 {main}
Test 3 passed
Test 4 FAILED: JsonException: Syntax error in json_decode_bug.php:5
Stack trace:
#0 json_decode_bug.php(5): json_decode()
#1 json_decode_bug.php(18): test()
#2 {main}
Test 5 passed

(I've removed the directory names from the stack trace for brevity.)

But I expected this output instead:

Test 1 passed
Test 2 passed
Test 3 passed
Test 4 passed
Test 5 passed

Note that the exception message ("Syntax error') is different from what I get when I reduce the maximum depth argument from 999999999 to 999. Then I get JsonException: Maximum stack depth exceeded instead (which is expected).

So it looks like the parser hits an undocumented limit when the input string reaches 10,000 characters, but only for the heavily-nested input.

PHP Version

PHP 8.1.13

Operating System

Arch Linux (x86_64)

[cmb69]

This is due to the parser using the default of YYMAXDEPTH which is 10000 (see the generated json_parser.tab.c). Increasing that limit would pass the other tests, but:

However, do not allow YYMAXDEPTH to be a value so large that arithmetic overflow could occur when calculating the size of the stack space.

So while it would be possible to increase the current limit, I wonder whether that actually makes sense. Does such deeply nested JSON really exist? This seems more like an academic issue. Instead of increasing the limit, it might make more sense to constrain the $depth in the first place.

Anyhow, @bukka, what do you think about this issue?

[maksverver]

Nice job figuring out the root cause!

For context, this bug surfaced when someone tried to solve (a custom input for) an Advent of Code problem. Not exactly an important production issue, but also not entirely academic in the sense that nobody would hit this problem without looking to break stuff.

In my opinion, it's most important that the behavior of the function matches its specification. Currently the documentation says that $depth can be up to 2,147,483,647, but that's clearly not the case. So either the documentation or the implementation should be fixed so the two are in agreement.

Looking into it a bit further, it seems like bison uses alloca() to allocate stack space (i.e., it's not just the parser stack, this takes up space on the C call stack). This probably makes it infeasible to increase YYMAXDEPTH significantly.

That leaves a few reasonable options:

1. Figure out exactly what limits YYMAXDEPTH imposes on the types of JSON data being parsed, and document that. This is not as simple as it seems: from my examples, it's clear that it's about more than nesting depth alone, but if you can narrow it down to something like “with YYMAXDEPTH = 10000 we can parse anything up to a nesting depth of 2500” that might be good, and you could limit $depth to that (and document it!). That way, at least people know what to expect.

2. Rewrite the parser to not need so much stack space in the first place! According to the Bison documentation you linked to, stack space linear in the input is needed to support right-recursion, but it seems it should be possible to rewrite the grammar to use left-recursion. Sorry, that's not the problem here. It needs stack space to be able to recognize the closing ']' or '}' for arrays and objects. I don't think there is any way around that: so long as you are using Bison to parse nested structures it will need stack space corresponding with the nesting depth.

[nielsdos]

Looking into it a bit further, it seems like bison uses alloca() to allocate stack space (i.e., it's not just the parser stack, this takes up space on the C call stack). This probably makes it infeasible to increase YYMAXDEPTH significantly.

From https://www.gnu.org/software/bison/manual/html_node/Memory-Management.html:

The stack space allowed is not necessarily allocated. If you specify a large value for YYMAXDEPTH, the parser normally allocates a small stack at first, and then makes it bigger by stages as needed. This increasing allocation happens automatically and silently. Therefore, you do not need to make YYMAXDEPTH painfully small merely to save space for ordinary inputs that do not need much stack.

So it starts with a small stack, and it only uses alloca if you set YYSTACK_USE_ALLOCA, so I don' t think it's that big of a problem. So the "only" concern is we should make sure that we don't overflow anything.

[maksverver]

So it starts with a small stack, and it only uses alloca if you set YYSTACK_USE_ALLOCA

I see. I think if the parser stack isn't allocated with alloca(), then it's reasonable to let it grow larger.

So the "only" concern is we should make sure that we don't overflow anything.

Could you explain this concern to me? The parser stack is not a call stack. The way I understand how the generated parser works is that it adds symbols to the parser stack and uses a state machine to determine when it can reduce the top N symbols on the parser stack, using one of the reduction rules. No code is called recursively, so there is no risk of stack overflow due to excessive recursion.

(By the way, why the quotes around "only"?)

[nielsdos]

So the "only" concern is we should make sure that we don't overflow anything.

Could you explain this concern to me? The parser stack is not a call stack. The way I understand how the generated parser works is that it adds symbols to the parser stack and uses a state machine to determine when it can reduce the top N symbols on the parser stack, using one of the reduction rules. No code is called recursively, so there is no risk of stack overflow due to excessive recursion.

(By the way, why the quotes around "only"?)

I should've been more clear. I did not mean a call stack overflow, you're right about how it works. I meant the overflow mentioned in the docs:

However, do not allow YYMAXDEPTH to be a value so large that arithmetic overflow could occur when calculating the size of the stack space.

This is the only concern. The reason I put quotes around "only" is that the docs (or at least that one page) isn't very clear about the overflow condition. So we must be careful.

I dug a bit deeper in this issue and found the following:

The only overflow would be possible right here (source from json_parser.tab.c):

      /* Extend the stack our own way.  */
      if (YYMAXDEPTH <= yystacksize)
        YYNOMEM;
      yystacksize *= 2;
      if (YYMAXDEPTH < yystacksize)
        yystacksize = YYMAXDEPTH;

So we know that the stack size is always multiplied by 2, and that is the one that must not overflow. yystacksize is of type ptrdiff_t, so it's a 32-bit signed int on 32-bit systems and a 64-bit signed int on 64-bit systems. It starts at a value of YYINITDEPTH which is 200 by default.

The largest possible $depth is 2147483647 (=INT_MAX), and we must choose a YYMAXDEPTH and YYINITDEPTH such that all valid inputs within $depth's constraint are possible.

I'll assume a 32-bit system for these calculations here. The longest, deepest nested input possible with $depth=2147483647 is `1073741823 times [ follow by 1073741823 times ]'. The parser stack must thus be able to hold 1073741823 elements. We must choose YYINITDEPTH and YYMAXDEPTH such that a repeated multiplication of 2 of YYINITDEPTH becomes equal to YYMAXDEPTH without overflowing. If we set YYMAXDEPTH=1073741823+1 and YYINITDEPTH=128 or 256 (chosen close to the default of 200), there are no overflows possible and this still allow all valid inputs to be parsed.
For 64-bit systems we can use the same values for YYMAXDEPTH and YYINITDEPTH because the max value of $depth is the same.
EDIT: I'm not so sure anymore that my reasoning about what the longest, deepest nested input is correct. It seems that the parser stack might also push some states with values as can be seen in OP's second example. Still, increasing it until the value I proposed would be the maximum possible I think.

Even though this might seem an academic-ish issue, I still think it makes sense to change YYINITDEPTH and YYMAXDEPTH to the values I proposed here, because I think there are no negative consequences:

1. The parser stack is allocated on the heap, so we don't risk overflowing the call stack
2. The parser stack is only extended when it needs to be extended
3. The maximum value of $depth can't be reached now, so it's kinda confusing for users

[iluuu1994]

To me, it doesn't seem like making changes and potentially introducing bugs for a theoretical issue is worth it. I'd much rather fix the documentation.