ZlowCheck chews adagio

I’m working on a property-based and model testing library called ZlowCheck.

ZlowCheck uses a finite-entropy number generator (a.k.a PRNG).

Upon instantiation, the PRNG accepts a slice of bytes for use as seed. Everytime the prng gets called to produce a value, it consumes a byte of entropy from the slice. This means that it will run out of entropy once it has consumed all the bytes in the slice. When that happens, the PRNG returns an OutOfEntropy error.

const FinitePrng = @import("finite_prng");
// Create a fixed byte array as the entropy source
const bytes = [_]u8{ 0x12, 0x34, 0x56 };
// Initialize the PRNG with the byte array
var prng = FinitePrng.init(&bytes);
// Get a random generator from the PRNG
var random = prng.random();

const int_value = try random.int(i32); // better check for errors here

This is both its worst and best feature: you input some bytes into it, you pass it to the property-based tests, and it churns out data until it runs out. The length of the byte sequence determines for how long it can go - and incidentally describes how complex your program is. If no failures happen and the PRNG errors out, then you can cry victory and claim the tests don’t yield any bugs.

How hungry is the byte-cruncher ?

This brings up a problem, though:

When you use a PRNG, you want it to be able to produce values within limited ranges - those are the bread and butter of valid randomized inputs.

«Ok, this is fairly easy to do: just take the max value of the range, run a modulo with a rule of three and you’re done».

Not really: the modulo calculations produce biased results.

So, to avoid the bias, the PRNG has to do rejection sampling: it consumes entropy and rejects every output value until it finds one that’s in range. The issue with this is that, depending on the range and the bit-size of the value you’re trying to produce, the PRNG might have to churn through a lot of candidates before it finds a suitable one. In a context where the amount of available entropy is limited, this is a problem: you might burn through most of your byte input before you can actually produce a useful program.

As a work around, I decided to use the first rejected value as seed for a non-finite prng, and use that new prng to mutate the next byte in the sequence - until that next byte produces a suitable value.

Value1 = finite_prng.generate(bytes[1])

Value1 Rejected!

const std_prng = std.Random.prng(seed: Value1)

while()
  bytes[2] = std_prng.generateByte()
  Value2 = finite_prng.generate(bytes[2])
  if ( !rejected(Value2) ) break;

I blush everytime I think of this…

It’s ugly, it’s hacky, but it does the trick: the byte stream keeps on producing valid values, it doesn’t burn through them, and most importantly it’s deterministic - which means that it’s possible to reproduce the generated values from the underlying byte slice.

A word about reproducibility

Having a randomized reproducible input is paramount for simulation-testing frameworks: these frameworks aim to find failing cases that are as minimal as possible. «Minimal» means: as small input values as possible - short strings, small integers, small floats, short arrays, etc.

In order to do so, frameworks will generate long sequences of inputs in search for a failure, and then try to reproduce those failures using smaller versions of those sequences. It’s a common approach: cover a lot of ground, find a problem, then try to find a simplified version.

That reduction step, often referred to as shrinking, relies on reproducing progressively smaller chunks of the inital failing sequence. This is why it’s necessary to have reproducible data.

Now, in most cases, property-based testing libraries will NOT try to re-produce their values from the PRNG’s seed. Instead, they’ll record the generated values in a list as they produce them, and proceed to do the replays using that list.

Why keep on spitting out?

So either you use a finite-entropy PRNG, and you can replay from the byte-seed sequence, or you don’t, and you have to replay from the recorded output values.

The later approach is much more flexible than ZlowCheck’s, with a few downsides:

  1. you must use some memory to store the generated values. Not a big deal, though.
  2. if you want to store the generated sequence to disk, you must serialize it. That’s extra code and extra logic, which aren’t needed with a finite-prng: since you always know which of the bytes were used to generate the data which triggered the failure, the finite-prng acts as a de-serializer for test cases generated from the byte-sequence. The serialized version of your failure data is the byte sequence.

«But how can I reduce an error sequence from the byte-seed sequence?»

This, we’ll talk about in the next blog post.