Ditto – Deterministic Execution Replay for the Java Virtual Machine on Multi-processors

Alongside the rise of multi-processor machines, concurrent programming models have grown to near ubiquity. Pro-grams built on these models are prone to bugs with rare pre-conditions, arising from unanticipated interactions between parallel tasks. Moreover, conventional debugging method-ologies are not well suited to deal with non-deterministic faults, leading to inefficient debugging efforts in which most resources are consumed in reproduction attempts. Deter-ministic replay tackles this problem by recording faulty ex-ecutions and using the traces to generate equivalent ones. Replayers can be efficient on uni-processor machines, but struggle with unreasonable overhead on multi-processors. We present Ditto, a deterministic replayer for concurrent JVM applications executed on multi-processor machines. By integrating state-of-the-art and novel techniques it manages to consistently out-perform previous deterministic replayers targeted at Java programs, in terms of recording overhead, replaying overhead and trace file size. The main contribu-tion of Ditto is a novel pair of recording and replaying al-gorithms that (a) leverage the semantic differences between load and store memory accesses, (b) serialize memory ac-cesses at the instance field level, (c) employ partial transitive reduction and program-order pruning on-the-fly, and (d) take advantage of TLO static analysis, escape analysis and JVM compiler optimizations to identify thread-local accesses. 1