Popek and Goldberg's theorem

Popek and Goldberg’s theorem, published in 1974, provides the theoretical foundation for understanding which computer architectures can be efficiently virtualized. The theorem defines the necessary conditions for building efficient Virtual Machine Monitors (VMMs).

The Theorem

The key statement of Popek and Goldberg’s theorem is:

“A virtual machine monitor may be constructed if the set of sensitive instructions for that computer is a subset of the set of privileged instructions.”

In other words, for efficient virtualization to be possible, any instruction that could affect the security or correct operation of the system (sensitive instructions) must trap when executed in user mode (privileged instructions).

Categories of Instructions

The theorem categorizes processor instructions into three types:

1. Privileged Instructions

• Instructions that trap when processor is in user mode
• Can only be executed in system mode (supervisor mode)
• Examples:
  • Load PSW (Processor Status Word) on IBM S/370
  • Set CPU Timer on IBM S/370
  • Instructions that modify control registers

2. Sensitive Instructions

These come in two types:

Control-Sensitive Instructions

• Instructions that attempt to change the configuration of resources in the system
• For example, changing memory mapping or disabling interrupts

Behavior-Sensitive Instructions

• Instructions whose behavior or result depends on the configuration of resources
• For example, instructions that read the clock or system configuration
• Example: “Load Real Address” on IBM S/370 which depends on the current memory mapping

3. Non-Sensitive Instructions

• Instructions that are neither privileged nor sensitive
• Regular computational instructions that don’t affect system state

Architectural Implications

When an architecture satisfies Popek and Goldberg’s theorem, a VMM can be built using the “trap and emulate” strategy:

1. Run privileged guest code in user mode
2. When privileged instructions are encountered, they trap to the hypervisor
3. The hypervisor emulates the instruction’s behavior in the context of the virtual machine

Issues with x86 Architecture

The x86 architecture (before hardware virtualization extensions) did not satisfy Popek and Goldberg’s requirements:

• It contained approximately 17 “critical instructions” (sensitive but not privileged)
• These instructions did not trap when executed in user mode, but had different semantics
• This made traditional “trap and emulate” virtualization impossible on x86

Common critical instructions in x86 include:

• SGDT, SIDT, SLDT (reading global/interrupt/local descriptor tables)
• POPF (popping flags register, which might modify interrupt flags)
• PUSH/POP segment registers
• Instructions that access sensitive registers without trapping

Workarounds for Non-Virtualizable Architectures

To overcome these limitations, virtualization solutions developed several approaches:

1. Full Virtualization with Binary Translation:

   • Identify critical instructions at runtime
   • Replace them with code that has the same effect but allows the VMM to maintain control

2. OS-Assisted Virtualization (Paravirtualization):

   • Modify the guest OS to avoid using critical instructions
   • Replace them with hypercalls that explicitly communicate with the VMM

3. Hardware-Assisted Virtualization:

   • CPU vendors added virtualization extensions
   • Intel VT-x and AMD-V introduced new processor modes specifically for virtualization
   • These extensions make x86 satisfy Popek and Goldberg’s requirements