256 Lines or Less: Test Case Minimization
Property Based Testing and fuzzing are a deep and science-intensive topic. There are enough advanced techniques there for a couple of PhDs, a PBT daemon, and a client-server architecture . But I have this weird parlor-trick PBT library, implementable in a couple of hundred lines of code in one sitting. This week I’ve been thinking about a cool variation of a consensus algorithm. I implemented it on the weekend. And it took just a couple of hours to write a PBT library itself first, and then a test, that showed a deep algorithmic flaw in my thinking (after a dozen trivial flaws in my coding). So, I don’t get to write more about consensus yet, but I at least can write about the library. It is very simple, simplistic even. To use an old Soviet joke about Babel and Bebel , it’s Gogol rather than Hegel. But for just 256 lines, it’s one of the highest power-to-weight ratio tools in my toolbox. Read this post if: Zig works well here because it, too, is exceptional in its power-to-weight. The implementation is a single file, , because the core abstraction here is a Finite Random Number Generator — a PRNG where all numbers are pre-generated, and can run out. We start with standard boilerplate: In Zig, files are structs: you obviously need structs, and the language becomes simpler if structs are re-used for what files are. In the above assigns a conventional name to the file struct, and declares instance fields (only one here). and are “static” (container level) declarations. The only field we have is just a slice of raw bytes, our pre-generated random numbers. And the only error condition we can raise is . The simplest thing we can generate is a slice of bytes. Typically, API for this takes a mutable slice as an out parameter: But, due to pre-generated nature of FRNG, we can return the slice directly, provided that we have enough entropy. This is going to be our (sole) basis function, everything else is going to be a convenience helper on top: The next simplest thing is an array (a slice with a fixed size): Notice how Zig goes from runtime-known slice length, to comptime known array type. Because is a constant, slicing with returns a pointer to array, . We can re-interpret a 4-byte array into . But, because this is Zig, we can trivially generalize the function to work for any integer type, by passing in comptime parameter of type : This function is monomorphised for every type, so becomes a compile-time constant we can pass to . Production code would be endian-clean here, but, for simplicity, we encode our endianness assumption as a compile-time assertion. Note how Zig communicates information about endianness to the program. There isn’t any kind of side-channel or extra input to compilation, like flags. Instead, the compiler materializes all information about target CPU as Zig code. There’s a file somewhere in the compiler caches directory that contains This file can be accessed via and all the constants inspected at compile time. We can make an integer, and a boolean is even easier: Strictly speaking, we only need one bit, not one byte, but tracking individual bits is too much of a hassle. From an arbitrary int, we can generate an int in range. As per Random Numbers Included , we use a closed range, which makes the API infailable and is usually more convenient at the call-site: As a bit of PRNG trivia, while this could be implemented as , the result will be biased (not uniform). Consider the case where , and a call like . The numbers in are going to be twice as likely as the numbers in , because the last quarter of 256 range will be aliased with the first one. Generating an unbiased number is tricky and might require drawing arbitrary number of bytes from entropy. Refer to https://www.pcg-random.org/posts/bounded-rands.html for details. I didn’t, and copy-pasted code from the Zig standard library. Use at your own risk! Now we can generate an int bounded from above and below: Another common operation is picking a random element from a slice. If you want to return a pointer to a element, you’ll need a and versions of the function. A simpler and more general solution is to return an index: At the call site, doesn’t look too bad, is appropriately -polymorphic, and is also usable for multiple parallel arrays. So far, we’ve spent about 40% of our line budget implementing a worse random number generator that can fail with at any point in time. What is it good for? We use it to feed our system under test with random inputs, see how it reacts, and check that it does not crash. If we code our system to crash if anything unexpected happens and our random inputs cover the space of all possible inputs, we get a measure of confidence that bugs will be detected in testing. For my consensus simulation, I have a struct that holds a and a set of replicas: has methods like: I then select which method to call at random: Here, is another FRNG helper that selects an action at random, proportional to its weight. This helper needs quite a bit more reflection machinery than we’ve seen so far: is compile-time duck-typing. It means that our function is callable with any type, and each specific type creates a new monomorphised instance of a function. While we don’t explicitly name the type of , we can get it as . is a type-level function that takes a struct type: and turns it into an enum type, with a variant per-field, exactly what we want for the return type: Tip: if you want to quickly learn Zig’s reflection capabilities, study the implementation of and in Zig’s standard library. The built-in function accesses a field given field name. It’s exactly like Python’s / with an extra restriction that it must be evaluated at compile time. To add one more twist here, I always find it hard to figure out which weights are reasonable, and like to generate the weights themselves at random at the start of the test: (If you feel confused here, check out Swarm Testing Data Structures ) Now we have enough machinery to describe the shape of test overall: A test needs an (which ultimately determines the outcome) and an General Purpose Allocator for the . We start by creating a simulated with random action weights. If entropy is very low, we can run out of entropy even at this stage. We assume that the code is innocent until proven guilty — if we don’t have enough entropy to find a bug, this particular test returns success. Don’t worry, we’ll make sure that we have enough entropy elsewhere. We use to peel off error. I find that, whenever I handle errors in Zig, very often I want to discharge just a single error from the error set. I wish I could use parenthesis with a : Anyway, having created the , we step through it while we still have entropy left. If any step detects an internal inconsistency, the entire crashes with an assertion failure. If we got to the end of loop, we know that at least that particular slice of entropy didn’t uncover anything suspicious. Notice what isn’t there. We aren’t generating a complete list of actions up-front. Rather, we make random decisions as we go, and can freely use the current state of the to construct a menu of possible choices (e.g., when sending a message, we can consider only not currently crashed replicas). And here we can finally see the reason why we bothered writing a custom Finite PRNG, rather than using an off-the-shelf one. The amount of entropy in FRNG defines the complexity of the test. The fewer random bytes we start with, the faster we exit the step loop. And this gives us an ability to minimize test cases essentially for free. Suppose you know that a particular entropy slice makes the test fail (cluster enters split brain at the millionth step). Let’s say that the slice was 16KiB. The obvious next step is to see if just 8KiB would be enough to crash it. And, if 8KiB isn’t, than perhaps 12KiB? You can binary search the minimal amount of entropy that’s enough for the test to fail. And this works for any test, it doesn’t have to be a distributed system. If you can write the code to generate your inputs randomly, you can measure complexity of each particular input by measuring how many random bytes were drawn in its construction. And now the hilarious part — of course it seems that the way to minimize entropy is to start with a particular failing slice and apply genetic-algorithm mutations to it. But a much simpler approach seems to work in practice — just generated a fresh, shorter entropy slice. If you found some failure at random, then you should be able to randomly stumble into a smaller failing example, if one exists — there are much fewer small examples, so finding a failing one becomes easier when the goes down! The problem with binary searching for failing entropy is that a tripped assertion crashes the program. There’s no unwinding in Zig. For this reason, we’ll move the search code to a different process. So a single test will be a binary with a function, that takes entropy on . Zig’s new juicy main makes writing this easier than in any previous versions of Zig :D Main gets as an argument, which provides access to things like command line arguments, default allocator and a default implementation. These days, Zig eschews global ambient IO capabilities, and requires threading an Io instance whenever we need to make a syscall. Here, we need Io to read stdin. Now we will implement a harness to call this main. This will be : It will be spawning external processes, so it’ll need an . We also need a path to an executable with a test main function, a System Under Test. And we’ll need a buffer to hold the entropy. This driver will be communicating successes and failures to the users, so we also prepare a for textual output. How we get entropy to feed into ? Because we are only interested in entropy size, we won’t be storing the actual entropy bytes, and instead will generate it from a seed. In other words, just two numbres, entropy size and seed, are needed to reproduce a single run of the test: We use default deterministic PRNG to expand our short seed into entropy slice of the required size. Then we spawn proces, feeding the resulting entropy via stdin. Closing child’s stdin signals the end of entropy. We then return either or depending on child’s exit code. So, both explicit errors and crashes will be recognized as failures. Next, we implement the logic for checking if a particular seed size is sufficient to find a failure. Of course, we won’t be able to say that for sure in a finite amount of time, so we’ll settle for some user-specified amount of retries: The user passes us the number of to make, and we return if they all were successfull, or a specific failing seed if we found one: To generate a real seed we need “true” cryptographic non-deterministic randomness, which is provided by . Finally, the search for the size: Here, we are going to find a smallest entropy size that crashes . If we succeed, we return the seed and the size. The upper bound for the size is the space available in the pre-allocated entropy buffer. The search loop is essentially a binary search, with a twist — rather than using dichotomy on the directly, we will be doubling a we use to change the size between iterations. That is, we start with a small size and step, and, on every iteration, double the step and add it to the size, until we hit a failure (or run out of buffer for the entropy). Once we found a failure, we continue the serach in the other direction — halving the step and subtracting it from the , keeping the smaller if it still fails. On each step, we log the current size and outcome, and report the smallest failing size at the end. Finally, we wrap Driver’s functionality into main that works in two modes — either reproduces a given failure from seed and size, or searches for a minimal failure: Running the search routine looks like this in a terminal: Those final seed&size can then be used for , giving you a minimal reproducible failure for debugging! This … of course doesn’t look too exciting without visualizing a specific bug we can find this way, but the problem there is that interesting examples of systems to test in this way usually take more than 256 lines to implement. So I’ll leave it to your imagination, but you get the idea: if you can make a system fail under a “random” input, you can also systematically search the space of all inputs for the smallest counter-example, without adding knowledge about the system to the searcher. This article also provides a concrete (but somewhat verbose) example. Here’s the full code: https://gist.github.com/matklad/343d13547c8bfe9af310e2ca2fbfe109 You want to stretch your generative testing muscles. You are a do-it-yourself type, and wouldn’t want to pull a ginormous PBT library off the shelf. You would pull a library, but want to have a more informed opinion about available options, about essential and accidental complexity. You want some self-contained real-world Zig examples :P
Performance
Database
Testing
Ruby
Frontend
Web Development
AI
Programming
Open Source
Design
HTML
Java
Rust
DevOps
Vue
CSS
JavaScript
Security
Cloud
Python
API