WOOT '13 - The Page-Fault Weird Machine: Lessons in Instruction-less Computation

Julian Bangert explains how to build a Turing-complete execution environment on x86 using only page faults and double faults without executing CPU instructions.

The Page-Fault Weird Machine: Lessons in Instruction-less Computation Julian Bangert, Sergey Bratus, Rebecca Shapiro, and Sean W. Smith, Dartmouth College Trust Analysis, i.e. determining that a system will not execute some class of computations, typically assumes that all computation is captured by an instruction trace. We show that powerful computation on x86 processors is possible without executing any CPU instructions. We demonstrate a Turing-complete execution environment driven solely by the IA32 architecture's interrupt handling and memory translation tables, in which the processor is trapped in a series of page faults and double faults, without ever successfully dispatching any instructions. The "hard-wired" logic of handling these faults is used to perform arithmetic and logic primitives, as well as memory reads and writes. This mechanism can also perform branches and loops if the memory is set up and mapped just right. We discuss the lessons of this execution model for future trustworthy architectures. View the full WOOT '13 Program at usenix.org/conference/woot13/tech-schedule/workshop-program