Debugging operating systems with time-traveling virtual machines

Operating systems are among the most difcult of soft-ware systems to debug with traditional cyclic debugging. They are non-deterministic; they run for long periods of time; their state and code is large and complex; and their state is easily perturbed by the act of debugging. This pa-per describes a time-traveling virtual machine that over-comes many of the difculties associated with debugging operating systems. By time travel, we mean the ability to navigate backward and forward arbitrarily through the execution history of a particular run and to replay arbi-trary segments of the past execution. We integrate time travel into a general-purpose debugger to enable a pro-grammer to debug an OS in reverse, implementing com-mands such as reverse breakpoint, reverse watchpoint, and reverse single step. The space and time overheads needed to support time travel are reasonable for debug-ging, and movements in time are fast enough to support interactive debugging. We demonstrate the value of our time-traveling virtual machine by using it to understand and x several OS bugs that are difcult to nd with stan-dard debugging tools. 1