Pure User Mode Deterministic Replay on Windows

Abstract

The ability to record and replay program executions has many interesting applications such as debugging in the backwards direction, discovering and fixing the source of non-deterministic bugs and data races and retracing the steps of a system intrusion. Unfortunately, the power of deterministic replay tools is underutilized by the general public as the tools are either too difficult to deploy or unable to fulfill the performance and log size requirements of the user. As it happens, the majority of the research has been aimed at implementing such tools for Linux, and other platforms, including Windows, have mostly been neglected. In this thesis we look at whether it is possible to implement a deterministic replay tool for the Windows platform that is easily deployable (user mode only without operating system support – this entails no OS modifi- cations or drivers), can record all system calls and their side-effects (even if unknown), works on large programs (1 GB+ RAM), and has a high recording performance (≈2x slowdown). We found that the challenges deterministic replay tools are facing in user mode are exacerbated on Windows due to a lack of documentation and a more restrictive API. Despite this we came up with a design proposal that solves all the problems necessary to implement a deterministic replay tool that satisfies all our requirements for the Windows platform. We present novel techniques to record thread scheduling and non-deterministic instructions. We also describe in detail how to recreate the address space of a recorded program in which code can be executed and access resources directly without instrumentation or modifications just like in the original program. An alternative novel approach to this technique is also suggested. None of the methods rely on operating system support. Although the design proposal remains theoretical we have implemented two partial prototypes that were used to experiment on a small dummy program. Our findings show that it is reasonable to expect a recording slowdown on real programs in the range of 1-5x that will stay consistent even on programs with high memory usage. Regardless, the results are not conclusive and should be taken with a grain of salt.