Introduction to Deterministic Simulation Testing

Problem

One of the biggest pushbacks against new kernels, unikernels and anything similar is that they are not easily testable and debuggable, so with Hardware Manager we decided to address it head-on. We wanted to be able to guarantee that both the app that is running on Hardware Manager and Hardware Manager itself won’t crash.

That sounds great in theory, but how do we prove it? Well, while testing, we throw any and every bad thing that can happen at the system and see what happens. This is where deterministic simulation testing (DST) comes into play.

TL;DR Deterministic Simulation Testing

The only thing more frustrating than buggy code is sometimes-buggy code. DST ensures that once you catch a bug, you can replay the exact circumstances that led to it, thus ensuring that you can recreate it every time and find the actual root cause.

Other than the ability to recreate a bug once it is found, using DST also increases the possibility of finding it in the first place. It enables simulating months of production workload in hours, giving us the advantage of finding any existing bugs before someone else does.

Instead of just relying on brute force search for the bugs, DST targets specific execution paths that are likely to crash. Reinforcement learning is used to guide the simulations towards paths that are less explored and evaluated as more interesting (higher probability of crashing).

The guided exploration is used in combination with purposeful fault injections. The system is exposed to different kinds of faults that can happen in production and is supposed to sustain them without failing. These range from the very common ones - like packet drops, to more rare ones - like half of the running nodes going down. No matter what faults are injected, the system always has to stay in the correct state.

Determinism

As the name Deterministic Simulation Testing suggests, the runtime must be deterministic, which means that all sources of non-determinism are removed from it, and therefore any state that was achieved once can be replayed whenever needed.

When a program is running in a regular system, there are a lot of outside factors that can affect its execution, and these can’t be controlled. A packet can get corrupted, the threads can get scheduled differently, the CPU can get downclocked because of the temperature, etc. All of these result in the program executing differently from run to run, and therefore the regular testing results being inconclusive or flaky.

The first step to creating a deterministic simulation testing environment is getting rid of all sources of non-determinism. This means that any communication to the outside has to be mocked. For example: the packets can’t reach the actual network, the outside time does not exist, unreliable disks can’t be trusted, we own the CPU frequency, etc. Every interrupt, scheduling order and decision in the system is controlled.

In order to achieve this, we needed to fork KVM and a type 2 hypervisor that together make for the deterministic system in which we test Hardware Manager. This architecture also enables us to test Linux, but more on that in a future blog post.

Now that everything in the system is controlled, we need to determine what drives it. The answer is the seed. A seed is fed into the system and every decision that is made is derived from it. This allows for the replay of everything that happens, as the seed is the only input and everything else is completely deterministic.

Intelligent search

Having this deterministic environment is just half of the story. Running a regular program in a perfectly well-behaved system is not very likely to result in a crash, unless there are some gaps in the logic of the code, but those are usually caught with regular unit and integration tests.

Things usually start to fall apart when unpredictable things happen. All the technical debt of doing the bare minimum for error handling, or unforeseen edge cases, suddenly comes to light.

The search is guided using reinforcement learning, which favors the paths less traveled (and that makes all the difference ;). Combining those with purposeful fault injections that affect everything (networking, memory, nodes, etc.) results in triggering the very paths that we secretly wish never get triggered in production.

To make searching for bugs as efficient as possible, DST enables branching. When a state is viewed as potentially interesting, multiple runs branch out from it, resulting in that execution path being more explored than if just a single run covered it.

How we use it

We test Hardware Manager in two different ways. The first is by using DST for the apps that are running on top of Hardware Manager, which simultaneously tests the base underneath them. But also, we test Hardware Manager directly, by simulating, for example, device faults. This helped us catch and fix bugs that would have happened years into production deployment instead.

If you want to work on things like this, check out open positions.