Stack overflow when parsing lots of open square brackets

[frewsxcv]

Code

#![feature(plugin)]
#![plugin(afl_coverage_plugin)]

extern crate afl_coverage;

extern crate serde;

use std::io::{self, Read, Cursor};

use serde::json::{self, Value};


fn main() {
    let mut input = String::new();
    let result = io::stdin().read_to_string(&mut input);
    if result.is_ok() {
        if let Ok(j) = json::from_str::<json::Value>(&input) {
            let _ = json::to_string(&j);
        }
    }
}

Input

{"":"","":"😂","":"😂","":[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[0

Crash

root@vultr:~/afl-staging-area2# cargo run < newtest
     Running `target/debug/afl-staging-area2`

thread '<main>' has overflowed its stack
An unknown error occurred

To learn more, run the command again with --verbose.

This bug was found using https://github.com/kmcallister/afl.rs 👍

[oli-obk]

Parsing json and xml (I'm guessing YAML, too) without recursion requires keeping the stack manually in some heap structure. Since I've seen some FIXME's in the json code about removing heap allocations, I'm assuming that this is not the desired way to do things in serde.

[oli-obk]

This bug was found using https://github.com/kmcallister/afl.rs 👍

wheee, can you turn this into a (cargo-cfg enabled) integration test?

[frewsxcv]

can you turn this into a (cargo-cfg enabled) integration test?

Interesting idea. Would be pretty cool to get that working, but I'm probably not going to spend any time on it

[Byron]

As a general comment: When safety is concerned, and there is no control over the input of the program (or the input-source is untrusted), any algorithm using recursion can be considered unsafe unless it restricts its recursion depth explicitly to prevent overflows from the get-go. Even then it might fail in case the stack is smaller than expected.

This ticket should, at the very least, result in some red, bold text stating that untrusted input should be deserialized in a separate thread to prevent the main thread (and the process with it) from crashing in case manufactured input is encountered.

Before I started using Rust as primary language, I wasn't even aware of this, and outside of the Rust infrastructure, I wouldn't even care too much. However, since Rust ought to be save, anything that can crash a program should be something we at least make explicit.

Thinking about it: if we would implement a non-recursive algorithm which keeps data on the heap, the problem would just be offset, as the input needed to cause an out-of-memory situation would just have to be larger. The latter could be even worse on a server as it could affect other services.

Maybe a good way to deal with this is to provide an option during deserialization to specify the maximum allowed recursion depth. This comes with the benefit of being easy to implement as well.

[oli-obk]

Maybe a good way to deal with this is to provide an option during deserialization to specify the maximum allowed recursion depth.

I like it. The API should not break though, but it could offer new options for setting this depth, and set it to something reasonable by default.

However, since Rust ought to be save, anything that can crash a program should be something we at least make explicit.

I thought OOM is safe according to Rust's safety-rules? Crashing might not be desired behavior, but it is safe behavior.

[Byron]

However, since Rust ought to be save, anything that can crash a program should be something we at least make explicit.

I thought OOM is safe according to Rust's safety-rules? Crashing might not be desired behavior, but it is safe behavior.

I agree, let's stick to the terminology Rust setup already, which would make such a crash 'safe' indeed. Personally I'd like to extend that concept and try to write code that is also safe from 'manufactured input' attacks that can crash your program and thus make a service unavailable. Standard DOS attacks which bring a service down by brute force are still possible of course, but at least some effort has to be made to do it then (e.g. there is a difference between 1 node feeding 10 servers malicious input, and 1000 nodes trying to saturate the capacity of said servers).

[oli-obk]

stacker now has a remaining_stack function. Maybe we could check this at recursion boundaries and abort if there's less than a certain amount of stack space left.

[dtolnay]

This has been fixed in serde_json 0.8.4:

recursion limit exceeded at line 1 column 157

but most other formats are still vulnerable.

[dtolnay]

This no longer affects serde_json. Let's follow up in the issue trackers of individual formats as needed.