News for hackers. Stuff that matters.
Re:Bad JSON Parsers by kibwen on Friday November 08, 2019 @11:19AM (#21483655)
On the topic of malicious input, the serde_json example seems to be deliberately limiting recursion depth in order to head off DoS attacks:

"serde_json has a recursion limit to protect from malicious clients sending a deeply recursive structure and DOS-ing a server. However, it does have an optional feature unbounded_depth that disables this protection. It still uses the stack though, so it will still eventually blow the stack instead of using all available memory"

https://github.com/lovasoa/bad_json_parsers/issues/7

This begins to suggest that it may be downright desirable for servers to toss out deeply-nested JSON, regardless of the JSON specification.

Re:Bad JSON Parsers by shadowgovt on Friday November 08, 2019 @11:32AM (#21483810)
Google made a similar design decision regarding protobuffers (https://developers.google.com/protocol-buffers/docs/referenc...).
Re:Bad JSON Parsers by vbezhenar on Friday November 08, 2019 @11:23AM (#21483688)
Why not implement parsing without recursion? It doesn't look like a particularly hard task for me. Why restrict users with artificial limitations?
Re:Bad JSON Parsers by zamadatix on Friday November 08, 2019 @11:36AM (#21483857)
Why make something more complicated to add capability users aren't asking for.
Re:Bad JSON Parsers by vbezhenar on Saturday November 09, 2019 @10:26AM (#21492031)
Why do you decide for all users? I'm user and I'd like to have a reliable parser able to parse anything given sufficient memory. That's the point of library functions: provide flexibility for any use case.
Re:Bad JSON Parsers by tracker1 on Friday November 08, 2019 @12:12PM (#21484288)
If you have a service that takes in JSON from unknown sources then it's a pretty easy DDoS vector for abusing memory limits. Send a few hundred k of nested {"a":[{"a":[...]}]} that's easy to generate from a couple different CnC clients and you can kill a server pretty readily.

Similar for password login systems that don't restrict bad attempts by IP/Username. If you know a user exists you can send many requests for username:passphrase, and the hashing time has a cost... good passphrase hashing has a pretty high cost usually 1/10 of a second on a single core, or more. If you aren't tracking attempts, then you can easily topple a server with a few hundred simultaneous requests usually.

Anything that is an unguarded memory or compute hog can be used as a pretty easy DDoS vector unless otherwise mitigated somehow. I usually restrict 5-10k regardless, and chunk file uploads into separate requests. Restricting recursion for JSON predictable is a pretty great option as well.

Re:Bad JSON Parsers by loeg on Friday November 08, 2019 @07:25PM (#21488479)
Whether the stack is the implicit C stack or an explicit heap stack does not change anything about the argument you've made. I.e., your comment is not at all responsive to Grandparent's:

> Why not implement parsing without recursion?

Re:Bad JSON Parsers by Tomte on Friday November 08, 2019 @11:34AM (#21483821)
Because even if the stack doesn't run out, it still processes for a long time. Non-recursion doesn't help you there, you need to look at every byte, after all.
Re:Bad JSON Parsers by shadowgovt on Friday November 08, 2019 @11:36AM (#21483847)
And it's worth noting that many JSON parsers assume the problem domain is "shipping data over a network," where the input may be malicious. If the non-recursive parser has an N^2 piece of algorithm embedded in it, its ability to consume large data structures becomes a DOS liability.
Re:Bad JSON Parsers by marcosdumay on Friday November 08, 2019 @12:02PM (#21484171)
You'll need a stack anyway, because the structure is logically a tree. Better to use the call stack, that is already there and heavily optimized.
Re:Bad JSON Parsers by Spivak on Friday November 08, 2019 @12:14PM (#21484304)
Naive person here. Isn’t the call stack a lot heavier than pushing data structures on a std::stack?
Re:Bad JSON Parsers by MaulingMonkey on Friday November 08, 2019 @01:44PM (#21485370)
A recursive parsing call stack has the overhead of pushing/popping return addresses and maybe a couple other registers. Maybe a bit more if there are security protections like stack cookies that didn't get optimized away, or if shadow stacks are enabled. It's not free, but is pretty cheap. A non-recursive use of std::stack dodges some of that, but instead has the overhead of dynamic allocation, which I'm generally going to consider more expensive - but does have the advantage of being more of a once-off cost - so perhaps it'd be cheaper for long but shallow JSON objects? The cost of the call stack vs std::stack is probably dwarfed by the cost of allocating arrays/objects/strings and decoding in either case.

If you want to over-optimize for that specific case anyways, you can take a hybrid approach with smaller stacks kept on the stack in a single linear root blob, with larger stacks falling back onto the heap, using a non-recursive style.

However, if you're capping JSON depths as an anti-DoS measure anyways (your parser isn't the only thing possibly vulnerable to blowing the stack via recursion - anything dealing with the parsed result is also in danger if it can be recursive), the heap fallback may be entirely dead code anyways... so why bother coding it?

Re:Bad JSON Parsers by __david__ on Friday November 08, 2019 @01:52PM (#21485425)
It depends on how big the stack frame of the recursive function is vs how big the amount of data needs to be saved fore each recursion level.

But… most likely yes.

Re:Bad JSON Parsers by zeroimpl on Friday November 08, 2019 @02:11PM (#21485632)
You'll need a data structure to store the results to return to the caller. This data structure by definition cannot be the call stack. So using a call stack is technically redundant.