Catching lightning in a VM

Note: This post is human-written (by me). I only used an LLM to fix grammar and typos at the end. I hope you find it interesting.

Back in January, while deciding on a project for my bachelor’s thesis, I had just gotten sucked into a YouTube rabbit hole on deterministic simulation testing (DST). Sitting somewhere between traditional “example-based” testing and formal methods (rarely seen outside academia), DST offered an enticing solution to making software more robust.

DST is essentially fuzzing + fault injection + deterministic simulation. Of the three parts, deterministic simulation remains the least mature. It’s really good at finding complex bugs and once it’s found them it can perfectly reproduce them.

“Old-school” deterministic simulation, popularised by FoundationDB in the 2010s, requires the simulator and the thing it simulates to be built together, or at least very tightly integrated. Since everything has to be simulated, this approach was basically only viable for things like databases because of their low tolerance for errors and relative lack of external dependencies.

Meet the deterministic hypervisor

For DST to gain widespread adoption, you would need a general-purpose solution instead. Something that’s just plug-and-play. Antithesis, founded by former FoundationDB employees, came up with a nifty solution: a deterministic hypervisor.

A hypervisor is a low-level program that manages virtual machines. By making the hypervisor deterministic, you in turn make everything you can stuff into a VM deterministic as well.¹

This lets you include all of your dependencies² in the simulation and even simulate multiple nodes in a distributed system by running them as containers inside the VM. It feels like something close to magic, if you ask me.

Antithesis’s “Determinator,” as they call it, was both one-of-a-kind and (probably because of that) proprietary and closed-source. While understandable, that was also unfortunate if it kept this wonderful idea from becoming mainstream.

So, I thought, what if someone (read: my collaborator Nicholas and me) made an open-source deterministic hypervisor? That’s probably pretty hard to do. But not that hard… right?

Oh, how naive I was.

(How) It works!

Behold dhyve: our open-source deterministic hypervisor based on FreeBSD’s bhyve. It’s still experimental and a little rough around the edges, but it works. Given the same initial snapshot, seed, and inputs, dhyve reproduces exact execution order and final memory and CPU register state across independent runs. Check it out on GitHub at https://github.com/pgraug/dhyve. I have lots of improvements planned for the future.

So dhyve runs on our FreeBSD server (the “host”), and inside it we run a Linux VM (the “guest”). While most of the work required to make the system deterministic happens in dhyve, we also apply a few patches to the Linux kernel running in our guest. Most aren’t required for determinism, but help with performance by skipping slow calibration steps during boot. We also disable a lot of features since we’re not interested in the guest accessing the internet or real disks (we use an in-memory filesystem instead).

Getting a head start

Building on top of FreeBSD might seem like an odd choice, given that we had no experience with FreeBSD or FreeBSD kernel development, but there’s a reason behind the madness.

You see, Antithesis also based its Determinator on bhyve. Although their code is private, they’ve shared snippets of how the system works in various blog posts and conference talks over the years.

Given the project’s four-month deadline and very limited budget,³ this was exactly the head start we needed. Because of those constraints, we also invested heavily in custom tooling to make development easier. Our dhv CLI handles deployment, builds, tests, and analysis of test results and divergence points, to name just a few things. If you’re considering going down this path, I highly recommend doing the same.⁴

And then there were the countless hours spent searching the web for papers on niche CPU behaviour or reading Intel’s massive Intel® 64 and IA-32 Architectures Software Developer’s Manual, primarily volume 3, which is about 1,600 pages of dense CPU documentation.

The leaky boat problem

Imagine, if you will, a boat with a hundred holes in its hull. Some small. Some big. The boat is the VM. The ocean is the outside world (or the “host”).

Even if you plug 99 of those holes, water is still leaking into your boat. It isn’t until all of them are plugged that the boat stays dry.

Determinism is the same way. It’s a binary property, so being “almost deterministic” is just not deterministic enough. Because of this, there’s a long period at the beginning when it feels like you’re getting nowhere. But then, suddenly, it all starts to work. For dhyve, this breakthrough happened about two months in, when I was on a long train trip right before the Easter holiday and it finally got through the full Linux boot process deterministically.

Making a computer do what you tell it to do sounds deceptively simple, but over the years, CPUs and operating systems have started taking shortcuts to make computers run faster. That’s fine for every use case except ours, which means we have to make the CPU do some weird things.

A refresher on modern virtualisation

Modern CPUs have special instruction set extensions that let you run virtual machines with minimal compute overhead. On Intel CPUs, which we’re targeting, this is called VMX or VT-x. These extensions let the hypervisor hand control of the CPU to the guest (a VM entry) and take it back when the guest tries to do certain things (a VM exit).

It’s similar to an airplane pilot letting the autopilot control the plane while in the air, then taking the controls during takeoff, landing, and certain bad conditions.

We use these special instructions to essentially lie to and deceive the guest whenever it tries to do something non-deterministic.

Want some random bytes? Here are some generated from a seed we define. How about the time? We control that too. Halting execution for a while? Forget it. It’s time to wake up again.

You get the picture.

Time and time again

Non-determinism seeps in from many directions, but most of them lead back to the underlying challenge of making time deterministic. There’s of course “absolute” time (e.g. asking, “What time is it?”), but that isn’t too hard to make deterministic. The hard part is making sure that “relative” or “delta” time is deterministic.

A memory read can take vastly different amounts of time depending on whether the data is already in the CPU’s cache, how much speculative execution the CPU has done, and what else it is doing at the time. But that’s the real world. In our simulation, it should always take the same amount of time.⁵

What we need is a model of time tied to something other than actual wall-clock time. Luckily, Intel provides a suite of performance-monitoring counters, including one that counts the number of instructions.⁶ It seems like a perfect fit: time progresses with execution, independent of how long a given instruction takes.

However, we learned from this paper that the counter wasn’t deterministic, so that was off the table. All hope was not lost though. The paper also offered an alternative that was deterministic: the conditional branch instruction counter. We use that instead. It isn’t as granular, but we can multiply the count by a constant and increment time every time the guest executes an RDTSC instruction, making it work wonderfully.

Note that this might no longer be necessary.

From reading the announcement post for Bedrock, an open-source deterministic hypervisor by Niklas Gögge, it seems that the instruction counter on modern Intel CPUs might actually be deterministic.

Unfortunately, a bare-metal server with a beefy Sapphire Rapids CPU is well outside our budget, so we’re stuck with the conditional branch count. However, it would be cool if someone ran the test suite used in the research paper on one of these CPUs to verify this.

Be pragmatic

Because the “density” of conditional branch instructions varies, our time gets slightly distorted in tight loops or long stretches without branching, but this doesn’t seem to cause any issues.

That’s something we’ve seen throughout this project. Your simulation doesn’t have to behave exactly like a normal computer because software is actually pretty forgiving at the scale we’re operating at. You can avoid a lot of headaches and performance overhead by accepting that your simulation is a tiny bit less “realistic.”

I’m still not sure what the right balance between pragmatism and perfection is, but it’s something I want to test.

Third time’s the charm

There’s actually a third thing we need time for: timers (and delivering interrupts in general).

We want the guest’s interrupts to arrive at an exact, deterministic time, but we also especially need it for when we want to pause the VM from the hypervisor. This is really useful when debugging the hypervisor: we can bisect virtual time to find the exact point at which something in memory or a CPU register first diverges between runs. Then, using the instruction pointer and logs, we can figure out where the bug is hiding.

We have the CPU fire an interrupt at a specific conditional branch count. Since it delivers these interrupts with a slight delay, we actually have it fire shortly before the target and then single-step through the final instructions until we reach the target conditional branch count.⁷

It works well, but single-stepping adds significant overhead because of the many VM exits it induces.⁸

Building on top of dhyve with Director

Now, a deterministic hypervisor isn’t that useful on its own. You need some way to control it. We built the Director API for this purpose, allowing others to build on dhyve as a new primitive. We provide the deterministic simulation; you build the rest.

Director lets you pause the VM when certain things happen, inspect and modify its memory and state, and “fork” it using snapshots to explore the effects of your modifications. By combining these features, you could, for example, build a deterministic coverage-guided fuzzer⁹ by instrumenting your own program with special breakpoints and modifying the VM’s CPU registers and memory to explore your program’s entire state space.

The API is still experimental, but I think the idea has a lot of potential.

Wrapping up

There’s much more to say about dhyve itself, the journey of building it, and all the other things we had to make deterministic, like memory access, scheduling, I/O, and time travel.

More improvements are coming, and I’m planning to write about them. Leave your email address at the bottom of the page if you want me to email you when I post in the future.

If you’re interested in learning more about deterministic simulation and hypervisors, I highly recommend some of Antithesis’s great conference talks and blog posts, as well as this post about Bedrock, which takes a different and fascinating approach.

Get in touch

On a final note, I just moved to Aarhus, Denmark’s second-largest city, so I’m looking for a new job starting in September. Get in touch at peter@graugaard.me if you’re interested in discussing that or meeting up for a chat. I’m open to in-office, hybrid, and remote work.

Footnotes

1. This is a nice shortcut to achieving deterministic Linux. Meta previously attempted to make a deterministic version of Linux (see Meta’s post about Hermit) but has since given up on the project. The nice thing about a hypervisor is that its surface area is significantly smaller and there are fewer gaps. ↩

2. This means that your application and, for example, its database, API server, and message queue can all be part of the same simulation. ↩

3. I think we’ve spent $200 or so in total, about equally split between server costs and tokens. ↩

4. Remember that good tools for people are often also good tools for agents. Just be sure to keep an eye on the agents and their output. This isn’t something you can just vibe-code. It’s about creating a tight feedback loop to help you or your AI iterate. ↩

5. Interestingly, it doesn’t matter all that much how long you decide something takes, as long as it’s always the same. Observations like this help you be more pragmatic about what matters and what’s good enough. ↩

6. Technically, it’s the number of retired instructions, meaning those that were actually executed rather than thrown away after speculative execution. ↩

7. Because we’re single-stepping and stopping on the “rising edge” of the counter, we always stop right at the conditional branch instruction. Not just somewhere between it and the next conditional branch instruction, as one might assume. This is really important for determinism. ↩

8. Once again, it seems that Bedrock has found another technique for modern CPUs that does this with almost no overhead. It uses “EPT-friendly PEBS,” which is really exciting. ↩

9. This is basically DST’s little brother. ↩