A Tale of Four Fuzzers(tigerbeetle.com) |
A Tale of Four Fuzzers(tigerbeetle.com) |
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.
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!
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.
The keyword to look up more details is "coupon collector's problem".
You could _implement_ non-determinism via probabilistic sampling, but you could also implement the same interface as exhaustive search.
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.
What work is being offloaded from computers to people? It's exactly the same thing with more determinism and no logarithmic overhead.
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.
pub fn shuffle(g: *Gen, T: type, slice: []T) void {
if (slice.len <= 1) return;
for (0..slice.len - 1) |i| {
const j = g.range_inclusive(u64, i, slice.len - 1);
std.mem.swap(T, &slice[i], &slice[j]);
}
}
pub fn shuffle(g: *Gen, T: type, slice: []T) void {
if (slice.len <= 1) return;
for (0..slice.len - 1) |i| {
const j = g.range_inclusive(u64, i, slice.len - 1);
std.mem.swap(T, &slice[i], &slice[j]);
}
}
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.