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!
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.
pfdietz•2mo 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.
matklad•2mo ago
You could _implement_ non-determinism via probabilistic sampling, but you could also implement the same interface as exhaustive search.
pfdietz•2mo ago
An example is something like "pairwise testing" of arguments to a function. Just randomly generating values will hit all possible pairs of values to arguments, again with a logarithmic penalty.
AlotOfReading•2mo ago
pfdietz•2mo ago
AlotOfReading•2mo ago
What work is being offloaded from computers to people? It's exactly the same thing with more determinism and no logarithmic overhead.
pfdietz•2mo ago
Suppose that space of N points is partitioned into M relevant subsets, for now we assume of the same size. Then random sampling hits each of those subsets in O(M log M) time, even if we don't know what they are.
This sort of partitioning is long talked about in the testing literature, with the idea you should do it manually.
> what work is being offloaded
The need to write that program for explicitly enumerating the space.
matklad•2mo ago
https://github.com/tigerbeetle/tigerbeetle/blob/809fe06a2ffc...
then you get a random permutation. If it rather looks like this
https://github.com/tigerbeetle/tigerbeetle/blob/809fe06a2ffc...
you enumerate all permutations.
AlotOfReading•2mo ago
IngoBlechschmid•2mo ago
The keyword to look up more details is "coupon collector's problem".
pfdietz•2mo ago