rust-fuzz / rust-fuzz/arbitrary

Limiting recursion thoughts

Open
#223 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
880
Forks
93
PR merge metrics
No merged PRs in 30d

Description

I invested some time looking through Arbitrary/libfuzzer-sys to determine the best way to limit recursion (in my case). I'm going to list what I looked at:

  1. https://docs.rs/libfuzzer-sys/0.4.7/src/libfuzzer_sys/lib.rs.html#262-270, how size_hint is used to bail out in case of "not enough data".
  2. https://github.com/rust-fuzz/arbitrary/issues/78#issuecomment-804414060, custom Arbitrary impl with depth, switch to non-recursive generation as the limit is surpassed.
  3. https://github.com/rust-fuzz/arbitrary/issues/217, coming breaking changes.
  4. https://github.com/search?q=repo%3Abytecodealliance%2Fwasm-tools%20impl%3C%27a%3E%20Arbitrary&type=code, wasm smith.

Questions I'm trying to answer:

  1. Isn't using size_hint faster than limiting with a custom arbitrary implementation? If you implement size_hint, you can set the size hint to something like u64::MAX, which will be interpreted by libfuzzer-sys as not generating this input. The check for supplied bytes being less than the hint returns -1. While this may not be ideal for varying recursion depths since it's currently hardcoded, there are workarounds.
    My thought is that calculating the hint is much faster than limiting while generating the data structure, especially if you know your boundaries and just want to go a bit higher.
  2. Has it been empirically found that continuously generating the non-recursive data structure improves coverage? (ref to point 2 in the previous list)

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the linked libfuzzer-sys source around size_hint, then read arbitrary issues 78 and 217 and inspect the wasm smith Arbitrary implementations. Compare size_hint-based rejection with depth-aware non-recursive generation, including the effect on coverage. Done means reaching an empirically supported recommendation for limiting recursion.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
testing-qa
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.