14 ms·

The question isn't necessarily what might be found in nature, but what might be intentionally constructed in order to attack something. Without knowing more, th

The question isn't necessarily what might be found in nature, but what might be intentionally constructed in order to attack something. Without knowing more, the segfault in the C++ library is somewhat alarming.

kibwen 7y ago
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 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.
- vbezhenar 7y ago
  Why not implement parsing without recursion? It doesn't look like a particularly hard task for me. Why restrict users with artificial limitations?
  - Tomte 7y ago
    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.
    - shadowgovt 7y ago
      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.
  - zamadatix 7y ago
    Why make something more complicated to add capability users aren't asking for.
    - vbezhenar 7y ago
      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.
  - marcosdumay 7y ago
    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.
    - Spivak 7y ago
      Naive person here. Isn’t the call stack a lot heavier than pushing data structures on a std::stack?
      - MaulingMonkey 7y ago
        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?
      - __david__ 7y ago
        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.
    - zeroimpl 7y ago
      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.
  - tracker1 7y ago
    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.
    - loeg 7y ago
      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?
- shadowgovt 7y ago
  Google made a similar design decision regarding protobuffers (https://developers.google.com/protocol-buffers/docs/reference/cpp/google.protobuf.io.coded_stream#recursion-limit https://developers.google.com/protocol-buffers/docs/referenc...).
lovasoa 7y ago
Exactly. Another example is python's standard library json parser that is documented to throw a JSONDecodeError on invalid input. But if the invalid json contains deeply nested structures, it raises a RecursionError, and this is not documented anywhere. It's easy to imagine how a code that only catches JSONDecodeError while decoding untrusted inputs could be exploited by an attacker.
- anoncake 7y ago
  Documented or not, you shouldn't rely on the lib only throwing JSONDecodeError in security-critical code.
  - Spivak 7y ago
    But what can you do instead? It’s a really hard problem to validate generic JSON without accidentally parsing it.
    - zeroimpl 7y ago
      Validation better be done by the parser. Otherwise, subtle differences between the validator and the parser can lead to security flaws. Your solution is to make sure you use a good parser.
- Spivak 7y ago
  Ugh Python exceptions are always a source of anxiety for me. Without combing through the source and locking yourself to specific versions it’s nigh impossible to be sure you’ve caught everything without a “catch everything” block.
thegeomaster 7y ago
When the OS-provided stack is overflown, the program accesses a "guard page" (or several) which is explicitly non-readable by the process, which in turn triggers a segfault. It's not an exploitable issue, but in the interest of robustness, the library probably should've failed more gracefully instead of blowing through the stack.
saagarjha 7y ago
Is it any more alarming than the other results?

kibwen 7y ago

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

vbezhenar 7y ago
Why not implement parsing without recursion? It doesn't look like a particularly hard task for me. Why restrict users with artificial limitations?
- Tomte 7y ago
  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.
  - shadowgovt 7y ago
    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.
- zamadatix 7y ago
  Why make something more complicated to add capability users aren't asking for.
  - vbezhenar 7y ago
    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.
- marcosdumay 7y ago
  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.
  - Spivak 7y ago
    Naive person here. Isn’t the call stack a lot heavier than pushing data structures on a std::stack?
    - MaulingMonkey 7y ago
      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?
    - __david__ 7y ago
      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.
  - zeroimpl 7y ago
    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.
- tracker1 7y ago
  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.
  - loeg 7y ago
    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?
shadowgovt 7y ago
Google made a similar design decision regarding protobuffers (https://developers.google.com/protocol-buffers/docs/reference/cpp/google.protobuf.io.coded_stream#recursion-limit https://developers.google.com/protocol-buffers/docs/referenc...).

lovasoa 7y ago

Exactly. Another example is python's standard library json parser that is documented to throw a JSONDecodeError on invalid input. But if the invalid json contains deeply nested structures, it raises a RecursionError, and this is not documented anywhere. It's easy to imagine how a code that only catches JSONDecodeError while decoding untrusted inputs could be exploited by an attacker.

anoncake 7y ago
Documented or not, you shouldn't rely on the lib only throwing JSONDecodeError in security-critical code.
- Spivak 7y ago
  But what can you do instead? It’s a really hard problem to validate generic JSON without accidentally parsing it.
  - zeroimpl 7y ago
    Validation better be done by the parser. Otherwise, subtle differences between the validator and the parser can lead to security flaws. Your solution is to make sure you use a good parser.
Spivak 7y ago
Ugh Python exceptions are always a source of anxiety for me. Without combing through the source and locking yourself to specific versions it’s nigh impossible to be sure you’ve caught everything without a “catch everything” block.

thegeomaster 7y ago

When the OS-provided stack is overflown, the program accesses a "guard page" (or several) which is explicitly non-readable by the process, which in turn triggers a segfault. It's not an exploitable issue, but in the interest of robustness, the library probably should've failed more gracefully instead of blowing through the stack.

saagarjha 7y ago

Is it any more alarming than the other results?