Efficient deterministic simulation in the Cloud

TL;DR: Antithesis uses a custom deterministic hypervisor and snapshot-based copy-on-write (COW) with subtree deduplication to perform large-scale, repeatable fuzz testing of full systems in the cloud. ## Background: What We're Doing I'm Alex Pishkin, an engineer at Antithesis. We do automated end-to-end software testing – we love inducing P99 events to find interesting bugs. Think of it like staging a massive car crash and watching how your software behaves in the most unusual circumstances. The domain is deterministic simulation testing and fuzzing. Deterministic simulation means taking any test (e.g., integration test) and running it in a simulated environment where you have full control over network, disk, and other components. You can inject faults artificially, much faster than in real life, and you get clean logs of those faults that would otherwise be invisible. Determinism adds repeatability and consistency, so you can explore a buggy state destructively and reproduce it infinitely. Our approach is heavily inspired by fuzzing, but we focus on "whole-system testing" – massive network events, concurrency, multi-faceted fault injection. That creates a problem: what is the input? What constitutes the state needed to create a specific system state? Our solution is to put everything inside a deterministic virtual machine. ## The Deterministic Hypervisor We built our own deterministic hypervisor. The key is to eliminate non-determinism, which usually comes from inconsistent side effects of consistent operations – cache misses, branch predictions, timing. We fake time. We make necessary simplifying assumptions: - Only target one architecture (a large CPU stack available in the cloud). - Only one physical core per VM. This eliminates a whole class of concurrency issues; we still simulate many concurrency bugs using a system simulator. This also fits the fuzzing model well – parallel exploration is fine, it's embarrassingly parallel. - We restrict to a tiny subset of real devices and I/O – because we simulate them. If the CPU is deterministic, we already solved making network and disk deterministic. ## Performance: Snapshot Challenges Performance is critical. Hardware virtualization (e.g., nested page tables, extended page tables) gives us copy-on-write for free: by marking everything read-only in the second-level page table, any write triggers a fault to the hypervisor, which does a COW. But snapshots become memory-hungry: each VM uses 10–30 GB, and we take many snapshots. Our "multiverse debugging" approach creates a tree of snapshots (history tree). COW naturally forms a tree where each snapshot is a diff from its parent. But this doesn't account for identical data in sibling snapshots – different execution paths can still share huge amounts of data. Deleting a snapshot becomes a messy inheritance problem. ## Subtree Deduplication Instead of page-level deduplication, we deduplicate at the **subtree** level. Page tables are already tree structures; program data, instructions, and heap tend to be local. By reference-counting entire subtrees, we avoid updating millions of reference counts on page-level deduplication. The cost becomes O(n) in the **change set size** (e.g., 10 KB of changes) instead of O(n) in total memory size. Specifically: - The page table is a multi-level tree mapping addresses to physical locations. - When we take a snapshot, we keep a list of dirty pages (the diff set). For each subtree, if nothing changed in that subtree, we just bump the refcount of the whole subtree – no need to copy or refcount individual leaf pages. - This reduces per-snapshot overhead dramatically, making large-scale parallel fuzzing feasible. ## Conclusion Antithesis’ approach combines a custom deterministic hypervisor with efficient snapshotting via subtree deduplication, enabling us to fuzz complex real-world systems at cloud scale. The key lesson: **work at the granularity of your data structures** – in this case, the page table subtrees – to keep reference counting costs proportional to the change set, not total memory. Source: [Video](https://youtu.be/DF3nGDi2-dc)