The current implementation, when it hits an invalid character, loops downward by one bit each time. This is slow, all of the invalid char values are between 0xD800 and 0xDFFF, or greater than 0x10ffff (already dealt with with the mask)

This means that we spend a lot of time just looping here, especially when creating strings. We should instead just replace these with null or decrement the fourth nibble.

Fixes https://github.com/rust-fuzz/arbitrary/issues/43

Note: This merges into a new branch staging-1.0 where we can put our changes prepping for a 1.0 release

To-do:

• [x] Remove Shrinkable
• [x] Fix Cow lifetime
• [x] Remove shrinking from README
• [x] Save shrinking code to a gist

So we have some nice improvements to this crate, and I think everything has technically been compatible with a 0.2.X release but I think it is a good time to revisit some of the public API and trait designs and make a 0.3.0 release. I figured it would be good to open an issue to talk about what we might want in it.

TODO

• [x] Fill out public API doc comments, and add examples to each of them
• [x] Better Arbitrary for String implementation (#17)
• [x] Should Arbitrary have Debug as a super trait? (#7)
• [x] Should Arbitrary have Clone as a super trait? This would allow easier/better shrinking implementations (e.g. for various collections)
• [x] Refactor Unstructured to look more like FuzzedDataProvider? In particular, maybe we should get lengths from the end of the buffer like that does.
• [x] Add Arbitrary::arbitrary_take_rest methods to consume the rest of an Unstructured. (#18)
• [x] Add Arbitrary::size_hint and refactor Unstructured::container_size into Unstructured::collection_len, as discussed in #18.
• [x] Add a fn arbitrary<A: Arbitrary>(&mut self) -> Result<A, Self::Error> helper method to Unstructured to shorten invoking nested-arbitrary calls, so you can just do let foo = u.arbitrary()?; and let type inference figure things out for you?

As we surface more things to be done for 0.3.0 in the comments, I'll add them to this list, so that we have a single place for everything.

+cc @Manishearth: what do you think? Anything we should add to or remove from this list?

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

Sometimes a field of a struct doesn't implement arbitrary and it is either impossible to do (because it is from another crate, for example) or undesired.

We should support some kind of attribute to either use the Default::default implementation for the type, when we "don't care" about that field, or supply an arbitrary function that has the same signature as Arbitrary::arbitrary to be used instead.

This is all possible to do when implementing Arbitrary by hand, in the sense that you can always stuff whatever code inside the impl. But this seems common enough and simple enough that we may want to support it in the custom derive.

Straw person syntax:

#[derive(Arbitrary)]
struct MyThing {
    // This doesn't actually matter, just a diagnostic message, so don't
    // waste input bytes on it.
    #[arbitrary(default)]
    diagnostic: String,

    // This is a type defined by a foreign crate and doesn't implement
    // Arbitrary. Because of orphan rules, we can't implement Arbitrary
    // for it, so instead we have a one-off function.
    #[arbitrary(arbitrary = arbitrary_foreign_type)]
    foreign: foreign_crate::ForeignType,
}

fn arbitrary_foreign_type(u: &mut Unstructured)
    -> Result<foreign_crate::ForeignType>
{
    // ...
}

The open question in my mind is how to deal with the other, optional Arbtirary methods? e.g. arbitrary_take_rest, shrink, and size_hint. Should we assume the default implementations in this case? Should we also allow providing custom implementations for them?

Any thoughts @Manishearth?

+cc @bnjbvr

This PR addresses https://github.com/rust-fuzz/arbitrary/issues/33 and enables the following syntax for derive:

#[derive(Arbitrary)]
pub struct Rgb {
    // set `r` to Default::default()
    #[arbitrary(default)]
    pub r: u8,

    // set `g` to 255
    #[arbitrary(value = 255)]
    pub g: u8,

    // generate `b` with a custom function
    #[arbitrary(with = arbitrary_b)]
    pub b: u8,
}

fn arbitrary_b(u: &mut Unstructured) -> arbitrary::Result<u8> {
    u.int_in_range(64..=128)
}

Note

In case of custom function the lower bound for hint_size is defined through core::mem::size_of::<T>() which is correct for the types allocated on stack, but not for the heap allocated types.

Asking for an arbitrary bool to decide whether the loop should keep going consumes a byte per loop iteration, while calling int_in_range instead consumes at most four bytes for any combination of arguments, and often less.

I'm trying to develop an intuition for what helps or hinders libFuzzer when driving a fuzz target that uses arbitrary, but I don't know enough. Do you suppose this is likely to work better? Do you have any advice on how to reason about questions like this?

I've been thinking about a bounded_arbitrary_len (or arbitrary_bounded_len? arbitrary_len_in_range?) that takes optional min/max bounds like arbitrary_loop does, but takes bytes from the end like arbitrary_len does. That similarly could consume fewer bytes than just calling arbitrary_len and clamping the result. Is that likely to help a fuzzer explore the state space more effectively?

Hi! A few notes to preface issue:

• I asked @Manishearth this question a few weeks back and said that I should open an issue.
• This is not meant to be judgement of the decisions made in this crate, especially since I am not aware of the constraints that y'all might have.

The question: why did y'all opt for a QuickCheck-style, trait-based approach over a Hypothesis/Proptest-style, explicit shrinking object/struct approach? For context, a Hypothesis/Proptest-style checker would have a shrinking strategy that returns a tree. This tree would values and shrinking/expansion strategies. I've noticed that the biggest win of Hypothesis/Proptest-style approaches is that shrinkers/generators can be implemented for completely arbitrary (no pun intended!) types so that orphan rules don't apply to generated code.

That being said, I suspect that fuzzers might have different constraints than property testing, so this entire question could be taken with a grain of salt.

If I recall correctly, @fitzgen mentioned to me that they preferred Quickcheck to Proptest-style systems at Strangeloop.

If the Unstructured is completely exhausted, returning a buffer completely filled with zeroes instead of indicating failure does not make sense. It also causes issues for any users of Arbitrary implementations for integers (which are based on this method) who rely on eventually getting a nonzero result to e.g. break recursion.

Fixes #107.

T: Default would remove all unsafes but it isn't currently possible for [T; N] and this bound limitation isn't desirable for stuff that don't implement Default.

If https://github.com/rust-lang/rust/pull/75644 is going to be accepted, then the auxiliary functions won't be necessary in the near future.

Broadly, there are two kinds of things Arbitrary generates. Fixed-size objects that map to a fixed set of integers, and variable size objects, which can use something like container_size().

Thing is, unlike, say, quickcheck, we already have a finite number of bytes as input. It would be nice if Arbitrary could be told "hey, I only have X bytes of data and you're my last consumer" as opposed to "slurp as much data as you want, I'll split the difference amongst the next consumers!"

This seems pretty tricky to design in the general case, but we could initially settle for types like String and Vec just filling directly.

It pulls in derive_arbitrary v1.1.6 which has the following build failure:

error[E0599]: no method named `len` found for reference `&Fields` in the current scope
   --> /home/runner/.cargo/registry/src/github.com-1ecc6299db9ec823/derive_arbitrary-1.1.6/src/lib.rs:219:30
    |
219 |         if idx + 1 == fields.len() {
    |                              ^^^ method not found in `&Fields`

Perhaps you could bump the derive_arbitrary requirement in arbitrary to 1.2.0 (it's presently 1.1.6) or yank the affected derive_arbitrary v1.1.6 release?

I am new to arbitrary and cargo-fuzz. I have some seed corpus in json and I need to describe them in raw bytes, so that my fuzzer can convert them to a struct derived arbitrary.

Hello! Bear with me as I am new to Arbitrary.

I have this type from juniper:

pub struct Arguments<'a, S> {
    pub items: Vec<(Spanning<&'a str>, Spanning<InputValue<S>>)>,
}

Spanning and InputValue successfully derive(arbitrary::Arbitrary)). When I try to derive on Arguments, I get the following error:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'a` due to conflicting requirements
  --> juniper/src/ast.rs:59:42
   |
59 | #[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
   |                                          ^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime `'a` as defined here...
  --> juniper/src/ast.rs:60:22
   |
60 | pub struct Arguments<'a, S> {
   |                      ^^
note: ...so that the types are compatible
  --> juniper/src/ast.rs:59:42
   |
59 | #[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
   |                                          ^^^^^^^^^^^^^^^^^^^^
   = note: expected `<&'a str as Arbitrary<'_>>`
              found `<&str as Arbitrary<'_>>`
note: but, the lifetime must be valid for the lifetime `'arbitrary` as defined here...
  --> juniper/src/ast.rs:59:42
   |
59 | #[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
   |                                          ^^^^^^^^^^^^^^^^^^^^
note: ...so that the types are compatible

Manually implenting it works:

impl<'a, S> arbitrary::Arbitrary<'a> for Arguments<'a, S>
where
    S: arbitrary::Arbitrary<'a>,
{
    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
        let items: Vec<(Spanning<&'a str>, Spanning<InputValue<S>>)> = u.arbitrary()?;
        Ok(Self { items })
    }
}

Even though I am unblocked, I figured I'd file as one would expect the derive to work in this case.

In our use case, we are not using Arbitrary for fuzzing, but simply for creating arbitrary fixture values in tests. Currently we create a 10MB static Vec<u8> of random noise and use that as our Unstructured data. However this is annoying since it requires 10MB of memory overhead, and sometimes even then we run out of bytes.

I am wondering if it would be valid to have two flavors of Unstructured, one backed by a byte slice, presumably for fuzzing, and one backed by an infinite iterator of bytes which can never be exhausted. I experimented with a PR for doing this and got some basic tests passing, but don't know how valid it is in the grand scheme. I did find that some functionality is indeed dependent on the fixed byte slice, so at the very least some extra UX effort would have to be made to provide slightly different interfaces for different Unstructured flavors.

I understand if this wouldn't be worth the effort but I guess I am primarily wondering from a motivational standpoint why Unstructured is backed by a byte array instead of an iterator, and only secondarily asking for some feedback on the feasibility of using infinite iterators. Note: I know next to nothing about fuzzing.

This PR solves issue #44 by implementing a dearbitrary function to create a byte buf, which can be used again with arbitrary to recreate the struct. It is not a one to one mapping, as e.g. bools only use the last bit of a byte value.

What works:

• [x] derive
• [x] integer/float/char/bools primitive types
• [x] tuples
• [x] ()
• [ ] AtomicBool
• [ ] AtomicIsize
• [ ] AtomicUsize
• [ ] Ranges
• [ ] Duration
• [ ] Option
• [ ] Result
• [ ] [T; N]
• [x] &'a [u8]
• [x] Vec
• [ ] BTreeMap
• [ ] BTreeSet
• [ ] BinaryHeap
• [ ] HashMap
• [ ] HashSet
• [ ] ... everything which uses an iterator
• [ ] &'a str
• [ ] String
• [x] Box
• [x] Box<[A]>
• [ ] ... many other things missing