Towards Effective and Efficient Search-Based Deterministic Replay

Deterministic replay tools are a useful asset when it comes to pinpoint hard-to-reproduce bugs. However, no sweet spot has yet been found with respect to the trade-off between recording overhead and bug reproducibility, especially in the context of search-based deterministic replay techniques, which rely on inference mechanisms. In this paper, we argue that tracing the locking order, along with the local control-flow path affected by shared variables, allows to dramatically reduce the inference time to find a fault-inducing trace, while imposing only a slight in-crease in the overhead during production runs. Preliminary evaluation with a micro-benchmark and third-party bench-marks provides initial evidence that supports our claim