Machine Virtualization and the Popek-Goldberg Theorem

Every time you launch a cloud instance — an AWS EC2 box, an Azure VM, a throwaway VirtualBox guest on your laptop — you are handed something that looks and behaves exactly like a real computer: it boots its own kernel, thinks it owns the CPU, programs "its" MMU, talks to "its" disk. And yet it is one of dozens of such machines sharing a single physical host, none of them aware of the others, none able to touch the host or each other. That illusion — a whole machine, faithfully reproduced in software, safely multiplexed — is machine virtualization, and it is the foundation the entire cloud is built on.

You already know how an OS virtualizes the CPU and memory for a process. This module goes one level up: virtualizing the whole machine for an entire guest operating system. The program that pulls this off is the virtual machine monitor (VMM), also called a hypervisor. This first lesson asks the deepest question in the field: when is it even possible to virtualize a machine efficiently — and why the world's most popular CPU, the x86, infamously flunked the test for thirty years.

What the hypervisor sells: three properties

In 1974 Gerald Popek and Robert Goldberg wrote the paper that still defines the subject: "Formal Requirements for Virtualizable Third Generation Architectures." They pinned down what it even means for a piece of software to be a virtual machine monitor. A VMM is a program with three essential properties:

Fidelity (equivalence). A program running under the VMM behaves identically to how it would on bare hardware — same results — except for timing and for resource limits. The guest cannot tell it is virtualized by observing its own computation.
Performance (efficiency). The vast majority of guest instructions execute directly on the real CPU, with no VMM intervention. This is the line that rules out a pure emulator/interpreter (like QEMU's TCG or an old-school simulator): correct, but far too slow to count as efficient virtualization.
Safety (resource control). The VMM is in complete control of the real resources. A guest can never access hardware the VMM did not grant it, nor escape its sandbox, nor starve its neighbours by seizing the machine.

Fidelity and safety are also achievable by pure emulation; the hard, defining requirement is doing all three while letting most instructions run native. That "run native but stay in control" tension is the whole game — and it is exactly the limited-direct-execution idea you met for processes, now applied to a whole guest OS.

The trick: de-privilege the guest

Here is the mechanism the theorem is about. The guest OS was written to run in ring 0, the most privileged mode — it expects to disable interrupts, reload page tables, and issue I/O directly. The VMM will not allow that. Instead it runs the entire guest — including the guest kernel — at a lower privilege level (this is called ring compression or de-privileging). The guest kernel still thinks it is in ring 0, but it is not.

Now the plan is beautifully simple. Ordinary, harmless guest instructions (arithmetic, loads, branches) run directly on the CPU at full speed — that buys us performance. But the moment the de-privileged guest attempts a privileged operation, the hardware raises a fault — a trap — that lands in the VMM. The VMM then emulates what the instruction should have done to the virtual machine's state, and resumes the guest. This is trap-and-emulate (the whole of the next lesson). It preserves fidelity and safety while keeping almost everything native — provided every instruction that could break the illusion actually traps. That single proviso is the Popek-Goldberg theorem.

Two ways to classify every instruction

Popek and Goldberg cut the instruction set two different ways, and the whole theorem lives in how those two cuts overlap.

An instruction is privileged if, executed in user mode, it traps (raises a fault); executed in supervisor mode it just runs. This is a property of the hardware: does it trap or not? (Think \texttt{lgdt}, \texttt{hlt}, writing control register \texttt{cr3}.)
An instruction is sensitive if it can break virtualization. Two flavours: control-sensitive — it changes the configuration of resources (alters interrupt flags, the amount of memory, which mode the CPU is in); and behaviour-sensitive — its result depends on the real configuration (e.g. reads the true privilege level, or behaves differently in user vs kernel mode).
Everything else is innocuous — a plain \texttt{add} or \texttt{mov} between registers. These can always run native.

The diagram below is the heart of the lesson. For trap-and-emulate to work, every sensitive instruction must also be privileged — so that the hardware traps it and the VMM gets a chance to emulate. If any sensitive instruction is not privileged, it runs silently in the de-privileged guest, quietly reads or mutates real machine state, and the illusion shatters. That is the crescent labelled "THE LEAK".

The theorem

An architecture is (efficiently, trap-and-emulate) virtualizable if the set of sensitive instructions is a subset of the set of privileged instructions: \text{sensitive} \subseteq \text{privileged}.
Intuition: if every instruction that could break the illusion also traps, the VMM can intercept and emulate all of them — so it stays in control while everything else runs native.
A VMM must deliver all three: fidelity (equivalent behaviour), performance (most instructions run native), and safety (total resource control).
Corollary: any sensitive-but-unprivileged instruction is a leak — it neither traps nor is emulated — so a machine with even one is not classically virtualizable.

Why classic x86 failed — the 17 problem instructions

The IBM System/370 satisfied the theorem, which is why IBM had rock-solid VMs in the 1970s. The x86 did not. In 2000, John Scott Robin and Cynthia Irvine audited the Pentium instruction set and found 17 instructions that are sensitive but not privileged — they execute harmlessly (no trap) in user mode while quietly leaking or depending on real machine state. A few infamous examples:

Instruction	What it does	Why it's a leak
PUSHF / POPF	push / pop the FLAGS register (incl. the interrupt-enable flag IF)	in user mode, `popf` silently ignores writes to IF instead of trapping — the guest kernel's "disable interrupts" is lost with no fault
SGDT / SIDT / SLDT	store the GDT / IDT / LDT register	a de-privileged guest can read the real descriptor-table addresses — behaviour-sensitive, reveals it is virtualized
SMSW	store machine status word (part of CR0)	reads real control state from user mode without trapping
PUSH / POP with CS/SS, LAR/LSL, MOV from segment	read code/stack-segment selector or descriptor rights	the low 2 bits of a segment selector expose the current privilege level — the guest can literally see it is not in ring 0

The killer is the silent ones like \texttt{popf}. A guest kernel executing "disable interrupts" expects the machine to obey; on de-privileged x86 the write to the interrupt flag is discarded with no trap, so the VMM never learns the guest wanted interrupts off. There is nothing to intercept. This is precisely a sensitive-but-unprivileged instruction — and it is why, for decades, x86 could not be virtualized by textbook trap-and-emulate. The next lessons are the industry's two escape routes: binary translation (VMware) and hardware virtualization extensions (Intel VT-x / AMD-V).

Automate the test

The theorem is a set-membership check, so let's run it. Below, every instruction carries two boolean tags — is it sensitive, is it privileged. The machine is virtualizable exactly when no instruction is sensitive-yet-unprivileged. Add a leaky instruction and watch the verdict flip.

// Popek-Goldberg as a program: an ISA is virtualizable iff sensitive ⊆ privileged. interface Insn { name: string; sensitive: boolean; privileged: boolean; } // A tiny model ISA. The last few are the classic x86 "leaks". const isa: Insn[] = [ { name: "add", sensitive: false, privileged: false }, // innocuous { name: "mov", sensitive: false, privileged: false }, // innocuous { name: "lgdt", sensitive: true, privileged: true }, // sensitive AND traps -> safe { name: "hlt", sensitive: true, privileged: true }, // sensitive AND traps -> safe { name: "cli", sensitive: true, privileged: true }, // sensitive AND traps -> safe { name: "popf", sensitive: true, privileged: false }, // LEAK: silently drops IF { name: "sgdt", sensitive: true, privileged: false }, // LEAK: reads real GDT { name: "smsw", sensitive: true, privileged: false }, // LEAK: reads real CR0 ]; const leaks = isa.filter((i) => i.sensitive && !i.privileged); for (const i of isa) { const cls = !i.sensitive ? "innocuous (run native)" : i.privileged ? "sensitive+privileged (traps -> VMM emulates)" : "SENSITIVE, NOT privileged -> LEAK"; console.log(`${i.name.padEnd(6)} : ${cls}`); } console.log(`\nleaks found: ${leaks.length} [${leaks.map((l) => l.name).join(", ")}]`); console.log(leaks.length === 0 ? "=> sensitive ⊆ privileged: VIRTUALIZABLE by trap-and-emulate" : "=> NOT classically virtualizable (this is exactly classic x86's problem)");

Popek-Goldberg says trap-and-emulate can't virtualize x86 — it does not say x86 can't be virtualized at all. VMware's founders (Mendel Rosenblum's Stanford group, out of the Disco research VMM) simply refused to rely on traps. Their Workstation product used dynamic binary translation: as the guest kernel runs, the VMM scans its code just ahead of execution and rewrites the dangerous instructions — every \texttt{popf}, every \texttt{sgdt} — into safe sequences that call into the VMM. Innocuous code is copied through almost unchanged and still runs native. It was an engineering tour de force that turned a "non-virtualizable" CPU into the foundation of a multi-billion-dollar company — years before Intel and AMD fixed the hardware.

The single most common confusion here is treating "privileged" and "sensitive" as synonyms. They answer different questions. Privileged is about the hardware's reaction: does this instruction trap when run in user mode? Sensitive is about semantics: can this instruction observe or change real machine configuration? A well-designed ISA makes every sensitive instruction privileged, so the two sets line up. A badly designed one (classic x86) has sensitive instructions that are not privileged — and those, not the privileged ones, are the whole problem. The theorem is not "all sensitive instructions" or "all privileged instructions" — it is about the containment of one set inside the other.

Where this module goes

You now have the yardstick every later lesson is measured against. Next we build trap-and-emulate and the software workarounds (binary translation, paravirtualization) that made x86 usable; then hardware-assisted virtualization, where Intel and AMD finally made x86 satisfy the theorem in silicon; then memory and I/O virtualization; and finally the hypervisor architectures that package it all.