Use fewer input bytes for arbitrary_loop

[jameysharp]

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?

[fitzgen]

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?

This seems valuable to have even if it ends up consuming the same number of bytes, just from a convenience perspective.

Will it help the fuzzer explore the space more efficiently? No idea. Probably depends on how well you choose bounds.

[fitzgen]

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?

Unfortunately, we don't have any rigorous benchmark corpus of generators to use here, or any way to formally reason about this kind of change in general. I think the best approach (balancing practicality of running an experiment and trustworthyness of results) in these situations is to show the effect on coverage/time for some real, non-trivial Arbitrary generator program (e.g. wasm-smith) starting with an empty corpus with and without the proposed change.

To speculate about this PR's change a bit:

• Using less of the underlying input leaves more for subsequent queries on the Unstructured which lets us generate more interesting test cases.
• Using a bool per iteration makes it more likely that the fuzzer's random mutations to the input will change the number of iterations of the loop: with one length we have P(change iterations) = O(1)/N where as with a bool per iteration we have P(change iterations) = I/N where I is number of iterations and N is the length of the underlying data. Is maximizing P(change iterations) something we want to do? No idea! Again, I think the best thing in most of these scenarios is to just try it out and measure coverage/time for ~1 hour with and without the change.

[fitzgen]

LGTM, nice logic clean up too -- do you want to do an experiment on coverage/time?

[jameysharp]

I think the best approach (balancing practicality of running an experiment and trustworthyness of results) in these situations is to show the effect on coverage/time for some real, non-trivial Arbitrary generator program (e.g. wasm-smith) starting with an empty corpus with and without the proposed change.

That is already a better plan than I had: thanks!

LGTM, nice logic clean up too -- do you want to do an experiment on coverage/time?

Do you want that before merging, or is the logic clean-up good enough reason to merge this? I want to think about experiment setup a little.

I've been thinking about a bounded_arbitrary_len ...

This seems valuable to have even if it ends up consuming the same number of bytes, just from a convenience perspective.

I'll put together a PR for that at some point too then!

[fitzgen]

Do you want that before merging, or is the logic clean-up good enough reason to merge this? I want to think about experiment setup a little.

If you are going to do an experiment, we might as well wait for its results. FWIW, pretty much any experiment is better than none here, so I wouldn't stress experimental setup too much. Since this is unlikely to affect fuzzer throughput, you could do a fixed number of fuzz runs to even out the comparison and mitigate bias from noise on your system, if you wanted. (Pass -- -runs=N at the end of your cargo fuzz run)

If you don't have time to do an experiment at all, then maybe we will just merge based on the clean ups and this probably(?) not making too much of a difference on fuzzer exploration.

[jameysharp]

The wasm-tools validate-valid-module fuzz target uses wasm-smith, which has its own copy of arbitrary_loop. That copy is close enough to the version in the arbitrary crate so I'm using it as a stand-in for this PR.

I tested the existing version for 1,000,000 runs. I'm not testing on a machine configured for benchmarking, but it took roughly 5 minutes and ended with this result:

#1000000	DONE   cov: 30019 ft: 121399 corp: 8186/1043Kb lim: 269 exec/s: 3246 rss: 578Mb

Then I applied a patch to wasm-smith that's equivalent to this PR and spent 20 minutes getting this result:

#1000000	DONE   cov: 27678 ft: 113338 corp: 7503/1011Kb lim: 277 exec/s: 816 rss: 1804Mb

So... huh. That's interesting!

[jameysharp]

A second run with the patched wasm-smith took only 7 minutes and got a little closer to the unpatched coverage:

#1000000	DONE   cov: 28639 ft: 116140 corp: 7270/986Kb lim: 277 exec/s: 2439 rss: 1181Mb

While another run of the unpatched fuzz target still took 5 minutes but had lower coverage, closer to the patched case:

#1000000	DONE   cov: 29154 ft: 118921 corp: 8162/1006Kb lim: 261 exec/s: 3278 rss: 571Mb

So maybe I got extraordinarily unlucky with the RNG the first time?

[fitzgen]

I think that because

• this doesn't seem to have a large effect on coverage (and doing a proper experiment to really evaluate this would probably require 24 hours of fuzzing x 30 different RNG seeds for the current code vs the new code each, and doing a u-test, which seems like an unnecessarily high bar)
• it is a nice code clean up, and
• using the underlying bytes more efficiently is in general a Good Thing because it leaves more entropy for doing subsequent arbitrary generation

we can go ahead and merge this.

Thanks for digging into this!