Abstract Kernel Support for Deterministic Redundant Execution of Shared Memory Workloads on Multiprocessor Systems

Motivated by future processors that will contain an abundance of execution cores, we believe redundant execution will be a practical method for increasing system security and reliability. However, redundant execution relies on the premise that duplicating external inputs identically to a set of replicas will produce identical outputs. Unfortunately, multi-threaded applications exhibit non-determinism that breaks this premise, especially on the multiprocessors that will be widely available in the future. This thesis presents a method for deterministically replicating the accesses to shared memory made by concurrent threads in a kernel level redundant execution system. Our approach relies on user space annotations, which define sequential regions in the applica-tion that the kernel will schedule deterministically. Further, we show that these annota-tions can be largely derived from the use of locks already present in the application and that replication can be achieved with only modest overhead. ii Acknowledgements I would first like to thank Professor David Lie for his tireless contributions to this thesis. Our many discussions and analysis sessions formed the foundation of my work. Thank you for pushing me to always be at my best. I also acknowledge the contributions of Ian Sin, with whom I worked on many aspects of this thesis. Our debates and time at the whiteboard were of great value to me and I will always look back on those times with fond regard