SIGSEGV on certain values

[ysimonson]

I think this is an issue with arbitrary, but let me know where I should move it if not.

I'm observing an issue where derived arbitrary types trigger a SIGSEGV when running cargo-fuzz. Here's a minimal example:

#![no_main]

use libfuzzer_sys::fuzz_target;
use arbitrary::Arbitrary;

#[derive(Arbitrary, Clone, Debug, PartialEq)]
pub enum Op {
    A(A),
    B(B),
}

#[derive(Arbitrary, Clone, Debug, PartialEq)]
pub enum A {
    Leaf,
    B(Box<B>),
}

#[derive(Arbitrary, Clone, Debug, PartialEq)]
pub enum B {
    Leaf,
    A(Box<A>),
}

fuzz_target!(|ops: Vec<Op>| {
});

Running this on the latest nightly (both mac and linux) triggers a SIGSEGV:

INFO: Seed: 3703294504
INFO: Loaded 1 modules   (17415 inline 8-bit counters): 17415 [0x10f5ef708, 0x10f5f3b0f), 
INFO: Loaded 1 PC tables (17415 PCs): 17415 [0x10f5f3b10,0x10f637b80), 
INFO:       59 files found in /Users/yusuf/Desktop/sandbox/fuzz-bug/fuzz/corpus/fuzz_target_1
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 4096 bytes
────────────────────────────────────────────────────────────────────────────────

Error: Fuzz target exited with signal: 11

Any of these changes will remove the segfault:

1. Changing the fuzz target's input from Vec<Op> to just Op.
2. Removing the B enum variant from A
3. Removing the A enum variant from B

[ysimonson]

It looks like implementing Arbitrary by hand rather than deriving it also fixes the issue.

[Manishearth]

Yeah it's a stack overflow. You can repro it by hand by just trying to construct Vec<Op> from Arbitrary

[Manishearth]

oh, size_hint doesn't work for recursive structures.

cc @fitzgen thoughts on how to fix this?

[Manishearth]

A potential route is to turn size_hint into a const fn (it's intended to const fold away anyway), and document that for recursive datastructures you should mark the struct with #[arbitrary::recursive] or something. The const fns will make it possible to catch this at compile time.

[fitzgen]

Another option would be to pass in (or have a thread local, ew) a HashSet<TypeId> and if this type's id is already in the set, then return an unknown upper bound, but if not, do what we do now and also add this type's id to the set for the future.

[fitzgen]

I tried making size_hint a const fn at first, but we can't match on or destructure the tuple to do the and and or operations inside a const context. Or at least, I don't know of a way to do that.

[Manishearth]

Another option would be to pass in (or have a thread local, ew) a HashSet and if this type's id is already in the set, then return an unknown upper bound, but if not, do what we do now and also add this type's id to the set for the future.

The hope is that this function const folds away, so I don't want to introduce global state

[Manishearth]

Yeah, i'm not sure how to make this work without const_if_match, but IIRC these things should stabilize soonish

[fitzgen]

We could probably preserve the const-folding-away by introducing a depth parameter, and if the depth is too big, say larger than 20, returning None for the upper bound.

[Manishearth]

maybe, sounds a bit precarious

[Manishearth]

I just want a type-level garbage collecter is that too much to ask for

[fitzgen]

#[derive(Arbitrary)]
struct Precarious {
    maybe: Option<Box<Precarious>>,
}