The title of the blog post downplays the absolute masterclass that this post is. It should be called "A Tale of Four Fuzzers: Best Practices for Advanced Fuzzing."
And if you don't have time, just go to the bullet point list at the end; that's all of the best practices, and they are fantastic.
> If you wrote a function that takes a PRNG and generates a random object, you already have a function capable of enumerating all objects.
Something often forgotten here: if your PRNG only takes e.g. a 32-bit seed, you can generate at most 2^32 unique objects. Which you might chew through in seconds of fuzzing.
Edit: this is addressed later in the article/in a reference where they talk about using an exhaustive implementation of a PRNG interface. Neat!
> If you wrote a function that takes a PRNG and generates a random object, you already have a function capable of enumerating all objects.
More specifically: if you uniformly sample from a space of size N, then in O(N log N) tries you can expect to sample every point in the space. There's a logarithmic cost to this random sampling, but that's not too bad.
Just a tiny addition: Yes, N log N is the average time, but the distribution is heavily long-tailed, the variance is quite high, so in many instances it might take quite some time till every item has been visited (in contrast to merely most items).
The keyword to look up more details is "coupon collector's problem".
It is much better than this. You can _directly_ enumerate all the objects, without any probabilities involved. There's nothing about probabilities in the interface of a PRNG, it's just non-determinism!
You could _implement_ non-determinism via probabilistic sampling, but you could also implement the same interface as exhaustive search.
gavinhoward|3 months ago
And if you don't have time, just go to the bullet point list at the end; that's all of the best practices, and they are fantastic.
atn34|3 months ago
Something often forgotten here: if your PRNG only takes e.g. a 32-bit seed, you can generate at most 2^32 unique objects. Which you might chew through in seconds of fuzzing.
Edit: this is addressed later in the article/in a reference where they talk about using an exhaustive implementation of a PRNG interface. Neat!
pfdietz|3 months ago
More specifically: if you uniformly sample from a space of size N, then in O(N log N) tries you can expect to sample every point in the space. There's a logarithmic cost to this random sampling, but that's not too bad.
IngoBlechschmid|3 months ago
The keyword to look up more details is "coupon collector's problem".
matklad|3 months ago
You could _implement_ non-determinism via probabilistic sampling, but you could also implement the same interface as exhaustive search.
efilife|3 months ago
captainhorst|3 months ago
philipwhiuk|3 months ago