Frequent status.OVERRUN due to max_choices / max_length limits

[cyberthirst]

Hello, at @vyperlang we're developing a hypothesis-based fuzzer for our compiler backend (fuzzer's available at: vyperlang/vyper#4686). We use a lot of nested @st.composite strategies.

We're hitting frequent max_choices / max_length limits which decreases the throughput. We tried increasing engine.BUFFER_SIZE internally, which helps with the length limit, but the max_choices cap still rejects many examples.

We're generating complex programs to exercise complex interactions between different parts of the compiler optimizer. We'd like to maintain the semantic coverage and not reduce the complexity of the examples.

We'd like to make the fuzzer-continuous and save the progress in a database.

We are ok with limiting the capabilities of the shrinker as the expected number of bugs found is low.

system info

python: Python 3.12.9
hypothesis: 6.135.16

questions

Is there a recommended pattern for large, structured fuzzers where high number of draws is required?
Can we easily patch some of the hypothesis internals to avoid the overruns? Or can they be made configurable?
Is the runtime overhead of increasing BUFFER_SIZE or max_choices roughly linear, or does it scale worse?

Any help or pointers would be appreciated, thank you.

[Zac-HD]

• the generation-time overhead of increasing BUFFER_SIZE and max_choices shouldn't be much worse than linear.
  • we impose these limits because (a) shrinking is at least quadratic, and (b) most bugs can be found with fairly small samples - although the net effect of restricting to small samples is under-studied imo.
  • I'd recommend trying to decrease the minimum and average size of generated programs, and also benchmark time taken to generate and to run programs by size. Ideally you'd have a principled basis for whatever size you choose.
  • it's possible that we should revisit these limits upstream; I don't think we've benchmarked since overhauling the choice sequence representation. @tybug for backlog?
• it sounds like https://hypofuzz.com/ could be very nice for you, especially if you add some hypothesis.event() calls to get semantic coverage of your search space.

[Liam-DeVoe]

I'm always excited to see fuzzing-style uses of Hypothesis!

• I agree that BUFFER_SIZE will be mostly linear, possibly with some nlogn sorting or tree costs thrown in. Increasing it should be quite safe for you. (We don't say that to everyone, or we'd increase it unconditionally, but a compiler-backend fuzzer is a place it makes sense!)
• As you've noted, Hypothesis retries examples which are too large. This is the max_length / BUFFER_SIZE cap.
• max_choices is different, and more internal than max_length. If max_choices overruns it's usually because we know that generating more than max_choices won't help. As a result, these retries are much cheaper than overrunning BUFFER_SIZE. It's certainly possible Hypothesis itself has some inefficiencies here for your particular strategies, so feel free to dig deeper, but there may not be easy wins like there were for BUFFER_SIZE.
• For visualizing and digging deeper into overrun reasons, I recommend tyche: https://github.com/tyche-pbt/tyche-extension.
• And I second https://hypofuzz.com/! If you try it out, I'd love to hear what you think about it.