lately ive been horribly nerdsniped with building a deterministic hypervisor. half of this is because it’s a fun project, and i have some other ideas that having a deterministic hypervisor would be useful for. the other half of it is because i saw way too many people who read antithesis blog posts and decided to write their own deterministic hypervisor - which every time i would then skim the code for and see a half-dozen nondeterminism sources - and because there is no justice on earth thought i could probably do a better job at¹.

first, what even is a deterministic hypervisor? for our purposes, a hypervisor is a program that runs a kernel. specifically, i care about running a linux kernel, and preferably a most-normal kernel - it shouldn’t require substantial patches, although ours will require some. deterministic means that, given the same initial state and making the same set of choices, you end up in the same end state. it’s maybe not obvious why this is difficult - programs, after all, are just state machines. you should be able to model any program as a pure function from (input state, program) -> output state. what’s the issue?

the two main issues are to do with concurrency and hardware. a single thread may give you the same output given the same input, but if you have two threads executing at the same time that isn’t the case; if there’s a mutex both threads are trying to acquire, which thread acquires the mutex depends on which actually is able to successfully atomic compare-and-exchange itself as the mutex owner first. this not only depends on when threads start, but also small variation inside the execution. one thread could start first, but then end up performing a load that isn’t in cache and stall its instruction pipeline, so end up losing to the second thread anyway.

the second, hardware, is both simpler and more subtle. reads and writes to hardware will have behavior that depends on state which you may either not be able to guarantee is the same for your “same” initial state, or which evolves over time in ways that you don’t control. a trivial example is RDTSC, which returns the processor timestamp counter - a hardware counter which ticks periodically. worse, hardware nondeterminism also affects interrupts: linux uses a periodic timer for preemptive scheduling, but when that timer expires depends on real world timing that isn’t going to be the same across runs. attempting to instead preempt according to metrics that are entirely controlled by the cpu, such as with performance counters, will have “skid” for when the interrupt for the counter overflow happens and so actually be delivered some number of instructions later even though they are legitimately due.

antithesis and a few of the open source implementations work around this by using a modern Intel x86 feature which delivers “precise” interrupts according to a retired-instructions performance counter; they can arm a countdown for N instructions, and be reasonably sure that it will be delivered <N+M instructions later, and then singlestep up to the same N+M instruction boundary each time. this is unfortunately both Intel specific (and i have an AMD laptop), kinda sketchy, and depends on things like patching KVM or bhyve in order to implement.

it may surprise some hacker news readers but antithesis didn’t invent the concept of a deterministic hypervisor, however. in cybersecurity there’s a long tradition of using deterministic hypervisors for fuzzing: you want to run a program with some input and always get the same behavior, whether program coverage edges or “did the program crash”. historically these hypervisors are usually emulators, in that they emulate x86 instructions in software (e.g. QEMU TCG). the emulator can then “just” make every instruction execute deterministically, and have its implementation of e.g. RDTSC or periodic timer delivery always do the right thing. the solution for multithreading is the same solution as antithesis takes: just don’t do it! if you only ever run one vcpu at a time, then there can never legitimately be two threads of execution happening concurrently and so they can’t have nondeterministic interleavings; you just periodically switch which vcpu is active as part of a hypervisor scheduling policy.

much like the antithesis approach, this is also a kinda bad solution. for one, implementing an x86 emulator that is actually able to boot linux is a lot of work. and for two, emulator based hypervisors aren’t very fast - which is why QEMU has a KVM based backend in the first place, which reintroduces the exact same set of hardware-based nondeterminism that was the issue.

Cooperative Scheduling

the hypervisor i wrote sidesteps a lot of issues by being tightly scoped in a very stupid way, which is good enough for my uses: simply never interrupt the guest. instead of timer based preemptive scheduling, i do cooperative scheduling via hypercalls². the linux kernel actually already knows how to do some of this! there is a concept called paravirtualized spinlocks, which is important if you are a kernel which runs under a hypervisor. if you have a thread which is attempting to acquire a lock but it’s already locked, on native hardware you don’t want to immediately block on it etc. because most locks are held for a very short amount of time. you can instead spin on the lock for a while, which is a tight loop where you repeatedly try to acquire it again - while you’re executing the loop real life time is passing, and so other cores are also executing and the holder is likely to release the lock without you having to block and then get woken up. this isn’t the case under a hypervisor however! a hypervisor may run a guest with more vcpus than there are real cpus, or oversubscribe vcpus across multiple guests.

worse, the hypervisor may have its own scheduler on top of the guest kernel scheduler, and not know which locks are held by the vcpus at the time it interrupts their execution, and so the vcpu that holds the lock may be busy running in another guest that has higher priority and never be released unless the hypervisor is informed something is now blocking on that vcpu releasing its lock. in this case spinning on a lock may never make any progress, and is always wasted work. linux implements paravirtualized spinlocks through the pvspinlock feature, which is detected by a CPUID leaf indicating a hypervisor is present being set.

really, all scheduling decisions under the guest kernel can be thought of as a similar class of behavior: every thread runs a sequence of operations and then either completes, or ends up waiting on another thread or an external resource.

what we want is a way to have every synchronization point marked with a hypercall, so that we can do a context switch there to another thread or inject hypervisor managed timers. my solution was to patch the arch/x86 intrinsic for cpu_relax and HLT to issue a hypercall yield in a similar way to paravirtualized locks. the reasoning is that even non-paravirtualized spinlocks, which never halt, still are supposed to cpu_relax in order to hint to the cpu that they can’t progress without an external change; if there are instead kernel tasks which do block, then the base case of the kernel scheduler having no remaining things to run is it HLTs and waits for a timer interrupt to wake it up again.

by turning these into hypercall yields and only delivering due external interrupts at those same points, we can think of the guest kernel as executing one atomic operation section every time we resume it. it will run from its resume point to the next hypercall yield: we don’t have to worry about it running fewer or more instructions than previous runs, because the last instruction it ran is always going to be another yield³. although the guest userspace is completely uninstrumented, it also becomes deterministic: it is simply never preempted by the kernel for a context switch, and only switches to another thread by yielding back to the kernel via syscalls. this is bad in a few ways. crucially, a guest program which does a series of instructions without any syscalls in between will always execute the full set without any interleavings from other threads, and so while atomics execute deterministically you can’t force data races or some behavior that a normal linux userspace would be able to observe. as well, a guest which executes a bare spinlock with no yields to the kernel will livelock the entire guest. however, futex still executes a syscall along with sched_yield, so you can still force some interesting interleaving, and the baseline determinism model is good enough for my specific usecase.

the good side is that unlike the antithesis model, this is kind of shockingly easy to implement and sidesteps many annoying or hard hardware details because you don’t depend on hardware for scheduling decisions at all! my hypervisor runs on stock KVM, without requiring a custom host kernel or module to be loaded, which both makes my life a lot easier and simplifies deploying it places. it also means that it runs on both AMD and Intel, and doesn’t require any modern or high-end processors with specific hardware features.

once that is done, we just need to also disable all the nondeterministic hardware pieces. instead of using a native hardware periodic timer, we have linux use a virtual timer that it arms via another hypercall, and which we only advance the time of when we get hypercall yields. we also stub out the clocksource, instead having linux read a hypervisor published memory location with the same virtual time⁴. we mask out a bunch of CPUID leaves exposing hypervisor-provided data, which likewise would leak host nondeterministic information.⁵

we also turn IPIs into hypercalls for a similar reason. a core attempting to deliver an IPI to another via the native host hardware is mostly deterministic, but there are circumstances where they aren’t either. with a host AVIC, the ICR busy bit will stay set for a nondeterministic amount of time that depends on host hardware state and whether any VMExits happen between the write and read, which ends up causing apic_wait_icr_idle to occasionally spin one fewer cpu_relax and diverge in execution. turning them into hypercalls helps us anyway because it allows the hypervisor scheduler to keep track of which vcpus are enabled or not, so it’s not all bad.

When it breaks

time for some fun war stories. the worst issue to debug from this was one which took me 5 days to nail down in my free time. i have some differential testing harnesses that i use in order to verify that the hypervisor is deterministic: if you boot a hypervisor and snapshot it, run it to a user shell, and then restore the snapshot and run it to the user shell again, the end state should be the same every time. in order to test this you can run two forks from the same initial snapshot and then compare their end states exactly, by taking another pair of snapshots and then compare them to each other. i do this in a bunch of different ways, such as one hypervisor running all the way to the end while the second takes another snapshot or resets periodically, or taking a reservoir sampling subset of intermediate states and running each intermediate state to the end as well. these were very useful at tracking down issues.

one of these tests was periodically failing however. about 10% of the time, a test that two forks of an initial snapshot repeatedly booting in parallel on two threads would fail…with the busybox shell at the very end hitting an AddressSanitizer crash.

this is very weird to say the least? the point of these tests is to find nondeterminism events, but even being accidentally nondeterministic shouldn’t ever crash, and definitely not crash in userspace. even weirder, after some initial triage i discovered that even with only a single thread the same test harness would hit the same crash, but at a 0.6% failure rate instead.

a fun trick you can do with a deterministic hypervisor is timetravel. because you know the execution from any point on a timeline should end at the same end state, you can “step backwards” by just repeatedly running from 0->N, and then 0->N-1, etc. further, you can bisect even a nondeterministic crash like this because you know that there are two outcomes: either the run is exactly the same as a “golden” run, or the run is different in some way and a “mutant”. you can repeatedly run the guest from some point and then compare it against a golden run at the same point, and see if you ever see a mutant. if you have N states, you can do this at N/2, and then see if the mutant stops appearing: if so, then the divergence that causes mutant probably shows up before it, and you can try again at N/4. in reality it turns out it’s a bit more complicated than that (the mutant rate being so low means there’s false negatives, and some bugs have nondeterministic side effects that only show up some number of events later and bisecting inside that window makes it disappear, so you need backtracking), but it’s a cute trick that i’d been using previously to track down the exact hypervisor step that causes the state to diverge. once you bisect down to the individual step that diverges, you can then continue bisecting down with singlestepping inside that to the instruction that diverges.

the trick also didn’t work for this bug. nondeterminism means there’s something odd going on, and so running to the N pivot state or checking for the divergence in the first place would perturb conditions enough the bug stopped appearing. singlestepping for example is slow, and so i had to instead use execute breakpoints based on a full golden trace and how many times the instruction shows up prior to the pivot position. i fixed a half dozen other minor correctness bugs while trying to get the bisection working better⁶ . eventually i was able to get my bisection harness to a point where it could reliably bisect to the individual instruction that was crashing…which to my surprise was literally the busybox load of shadow memory for AddressSanitizer, and not some memory corruption previously that had a butterfly effect, or something related to interrupt delivery messing up. on the instruction after the load the register state in the mutant would contain eax=0xcccccccc while the golden runs would contain eax=416, despite a full memory snapshot at that point being exactly the same.

the answer, my friends, was related to TLBs. when i was doing snapshot save i was capturing memory and the value of all registers, including MSRs. on snapshot restore i was restoring all memory and resetting all of these registers in the current KVM state via ioctls - in order to have fast snapshot restore, we don’t create a new KVM instance and reuse an existing one. despite restoring the contents of the page table and the relevant MSRs, the snapshot restore wasn’t invalidating TLBs because cr0 and cr3 were the same value after the restore, and so KVM sees that nothing has changed in the guest. the busybox program just so happened to call mmap during its execution, and we were restoring the snapshot to a state where the page table was different and that mmap hadn’t been executed yet, but TLB was still present. this stale TLB was 0.6% of the time surviving through 1227 hypervisor steps up to another load at the same virtual address and then loading from the wrong physical. running multiple threads just made the bug show up more often because the thread was less likely to migrate across cores during execution. the solution turns out to do two KVM_SET_SREGS ioctls, one with an intentionally changed cr0 value in order to force KVM to do a TLB flush.

SSH

for fun i threw together a demo of the hypervisor so i could show it off to coworkers. the demo is an ssh server that can be connected to with a normal ssh client, using the russh crate. the ssh server boots an initial hypervisor to a shell and then snapshots it to use as a forkserver, and gives each connected client an independent copy of that state. i even added a stupid file upload feature for sftp over an ssh -oControlMaster session that adds the file to the mounted virtio-9p filesystem so you can upload programs to run in the virtual machine. i had an agent throw together a cute little TUI and timeline view and implemented keybinds so that you can take new snapshots or navigate backwards and forwards through them, including across branches in history. the demo is just a pexpect script driving ssh.

this took me a surprisingly large amount of time to get working, but for really dumb reasons. i thought my deterministic hypervisor was broken and not actually deterministic for way too long, because i kept getting different outputs from the intentionally-data-racey program. it turns out that even driving the guest with pexpect, when the scripted inputs were arriving was variable, and so the keypresses were being injected into the guest at different times and causing the guest state to differ - something that in hindsight is extremely obvious. of course external keypresses aren’t going to happen at the same time!

i ended up needing to implement a very stupid rendezvous protocol between the hypervisor and the ssh server that is driving it. at a deterministic point in execution (eg every 500 hypervisor steps or whatever, which is a counter that will always be the same across runs) we can potentially publish a sealed batch of user input. that batch contains all the user input that has been buffered since the last batch was sealed, and batches are only sealed when the user is idle and doesn’t type for a few milliseconds. this does a decent job at masking jitter in user keypress timings from the hypervisor, with the difference in which rendezvous point the batch gets published only changing if the accumulated timing differences across the entire batch is longer than the length between rendezvous windows.

i wanted to put this on the internet and give everyone at my company access to mess around, but then i remembered that there’s actually been like 3 different KVM hypervisor escapes in the past month (and someone at my company would definitely be the type of person to use an N-day hypervisor escape to mess with me) and also if you have a public SSH server on the internet it will be immediately spammed by bots. maybe i’ll setup tailscale or something.

The AI Part

talking about ai coding is basically the programming version of talking about a dream you had last night. no one really cares and it mostly doesn’t matter. however since this experiment half started due to ai, i feel like i should also mention that 1) i have been writing this mostly with ai 2) ai is stunningly bad at writing hypervisors, or really most precise systems software ive tried. to keep it brief and actionable, i basically knew exactly how i wanted to write this hypervisor with the exact mechanisms and behavior i wanted for all the stuff i explained above, and sat down and spent over a week just outlining all the hard behavior requirements for the system in terms of MUST/MUST NOT language before writing a single line of code. i also outlined an implementation plan step by step, plus at each step a series of tests that must be implemented - including for each a negative variant that injects the incorrect behavior to assert the positive test is actually able to catch it. i even used ai to implement a TLA+ model of the hypervisor scheduler (which was actually pretty useful because i don’t actually know TLA+, and it helped me tease out some nonobvious behavior that flowed into the requirements and plan).

and still at almost literally every step the ai has fucked up the implementation in severe ways. even with the most explicit and clear instructions i could think of giving it, with a formal model of the required behavior, using the existing rust-vmm crate that firecracker uses with explicit instructions to not from-scratch implement as much behavior as possible, with the vast majority of the work not novel and fairly “boring”, it will fail at implementing the prescribed requirements in the way i tell it to.

worse, most of the time it would implement behavior that appears correct, and usually even passes “the tests” that i outlined for it to write - until i discover that it is silently horribly wrong in ways that is only apparent days later when i read it again, because my code review was lacking (and the two rounds of ai code review, which i also am extremely explicit in outlining, also did not do 70% of their instructions and approved the patchset as well), and the tests i told it to write were not the tests it implemented. repeatedly these were things that i very clearly instructed it to do, because they were the implementation approach that i knew would work, and even explained in the plan why we must do X and not Y, only for the agent to not do X and wing it in a different way anyway.

most of these are not subtle, small things, but things like me literally enumerating functions for it to patch and then the ai only patching 2 of the 6 instead. because this is precise work i am intentionally trying to go as slowly and methodically as possible and my takeaway is that ai is categorically unable to do precise work, and for most of the implementation plan steps it overall would have been faster to do it myself. and because talking about ai coding is like the hazy, shifting world of a dream, the takeaway of people from will be more amorphous feedback that im just prompting it wrong, or im using too old of a model, or im using too new of a model, or i just didn’t use enough ai, or really it’s unreasonable to expect ai to write correct code. anyway ai part over.

Conclusion

all together it’s been really fun working on this, and honestly didn’t take me very long. including the week spent just outlining the entire thing, it only took me around 4 weeks of effort after work to implement - which is mostly because it really is conceptually a very simple approach. while still strictly less powerful than something like a QEMU based deterministic hypervisor, it being the type of thing you can throw together in a few weeks i think is very cute. having a nice api also means that i can use it for later side-projects easily even if they don’t actually need determinism, and it’s just fun to mess around with: i was able to implement an extension that stubs out functions by kernel symbol name using hardware execute breakpoints in like 20 minutes for example.

i plan on open sourcing most of this eventually. right now the code is, generously, awful to read - mostly because claude seemingly does not understand the concept of comments and just writes gobbledegook for tens of lines, no matter how strictly you tell it not to. i would want to clean up all the factually incorrect and overly verbose comments, as well as read over the entire thing again to fix all the obvious bugs that it definitely still snuck in, before that. i think the conceptual idea is simple enough that hopefully this post was informative and entertaining even without the code.

---

Footnote: