Engineering Record and Replay for Deployability

The ability to record and replay program executions with low overhead enables many applications, such as reverse-execution debugging, debugging of hard-to-reproduce test failures, and "black box" forensic analysis of failures in deployed systems. Existing record-and-replay approaches limit deployability by recording an entire virtual machine (heavyweight), modifying the OS kernel (adding deployment and maintenance costs), requiring pervasive code instrumentation (imposing significant performance and complexity overhead), or modifying compilers and runtime systems (limiting generality). We investigated whether it is possible to build a practical record-and-replay system avoiding all these issues. The answer turns out to be yes - if the CPU and operating system meet certain non-obvious constraints. Fortunately modern Intel CPUs, Linux kernels and user-space frameworks do meet these constraints, although this has only become true recently. With some novel optimizations, our system 'rr' records and replays real-world low-parallelism workloads with low overhead, with an entirely user-space implementation, using stock hardware, compilers, runtimes and operating systems. "rr" forms the basis of an open-source reverse-execution debugger seeing significant use in practice. We present the design and implementation of 'rr', describe its performance on a variety of workloads, and identify constraints on hardware and operating system design required to support our approach.

• Publication year

  2017

• Venue

  USENIX Annual Technical Conference

• Publication date

  2017-05-16

• Fields of study

  Computer Science, Engineering

• Identifiers
  arXiv 1705.05937
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Towards Practical Default-On Multi-Core Record/Replay

  2017influential reference
• Abstractions for Practical Virtual Machine Replay

  2016cited by this paper
• Repeatable Reverse Engineering with PANDA

  2015influential reference
• Eidetic Systems

  2014influential reference
• Interactive record/replay for web application debugging

  2013cited by this paper
• Non-determinism and overcount on modern hardware performance counter implementations

  2013cited by this paper
• QuickRec: prototyping an intel architecture extension for record and replay of multithreaded programs

  2013cited by this paper
• AddressSanitizer: A Fast Address Sanity Checker

  2012cited by this paper
• Deterministic Replay of System's Execution with Multi-target QEMU Simulator for Dynamic Analysis and Reverse Debugging

  2012cited by this paper
• Software Techniques for Avoiding Hardware Virtualization Exits

  2012cited by this paper
• Transparent dynamic instrumentation

  2012influential reference
• A review of reverse debugging

  2012cited by this paper
• Dthreads: efficient deterministic multithreading

  2011cited by this paper
• Time-Traveling Forensic Analysis of VM-Based High-Interaction Honeypots

  2011cited by this paper
• DoublePlay: parallelizing sequential logging and replay

  2011cited by this paper
• Deterministic Process Groups in dOS

  2010cited by this paper
• Transparent, lightweight application execution replay on commodity multiprocessor operating systems

  2010cited by this paper
• PinPlay: a framework for deterministic replay and reproducible analysis of parallel programs

  2010influential reference
• Full-System Simulation from Embedded to High-Performance Systems

  2010cited by this paper
• ODR: output-deterministic replay for multicore debugging

  2009cited by this paper
• Reverse Debugging with the TotalView Debugger

  2009influential reference
• Kendo: efficient deterministic multithreading in software

  2009cited by this paper
• R2: An Application-Level Kernel for Record and Replay

  2008cited by this paper
• Execution replay of multiprocessor virtual machines

  2008influential reference
• Rerun: Exploiting Episodes for Lightweight Memory Race Recording

  2008cited by this paper
• DeLorean: Recording and Deterministically Replaying Shared-Memory Multiprocessor Execution Ef?ciently

  2008cited by this paper
• ReTrace : Collecting Execution Trace with Virtual Machine Deterministic Replay

  2007influential reference
• Replay Debugging for Distributed Applications (Awarded Best Paper!)

  2006cited by this paper
• Framework for instruction-level tracing and analysis of program executions

  2006influential reference
• Jockey: a user-space library for record-replay debugging

  2005cited by this paper
• A "flight data recorder" for enabling full-system multiprocessor deterministic replay

  2003cited by this paper
• ReVirt: enabling intrusion analysis through virtual-machine logging and replay

  2002influential reference
• A perturbation-free replay platform for cross-optimized multithreaded applications

  2001cited by this paper
• Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches

  1991cited by this paper

• Deterministic Client: Enforcing Determinism on Untrusted Machine Code

  2025cites this paper
• Tintin: A Unified Hardware Performance Profiling Infrastructure to Uncover and Manage Uncertainty

  2025cites this paper
• Execution-Aware Program Reduction for WebAssembly via Record and Replay

  2025cites this paper
• Blackbox Fuzzing of Distributed Systems with Multi-Dimensional Inputs and Symmetry-Based Feedback Pruning

  2025cites this paper
• Fray: An Efficient General-Purpose Concurrency Testing Platform for the JVM

  2025cites this paper
• Trace-Based Bytecode Interpreter Visualization for Compiler Construction Education

  2025cites this paper
• MIO: Multiverse Debugging in the Face of Input/Output

  2025cites this paper
• Black-Box Bug-Amplification for Multithreaded Software

  2025cites this paper
• KRR: Efficient and Scalable Kernel Record Replay

  2025influential citation
• LiveRec: Prototyping Probes by Framing Debug Protocols

  2024cites this paper
• EasyTracker: A Python Library for Controlling and Inspecting Program Execution

  2024cites this paper
• Extensible Tooling for Reactive Programming Based on Active Expressions

  2024cites this paper
• Accurate Coverage Metrics for Compiler-Generated Debugging Information

  2024cites this paper
• Causal-Consistent Reversible Debugging: Improving CauDEr

  2024cites this paper
• Benzene: A Practical Root Cause Analysis System with an Under-Constrained State Mutation

  2024influential citation
• Demystifying the Fight Against Complexity: A Comprehensive Study of Live Debugging Activities in Production Cloud Systems

  2024cites this paper
• Jmvx: Fast Multi-threaded Multi-version Execution and Record-Replay for Managed Languages

  2024influential citation
• Testing Concurrent Algorithms on JVM with Lincheck and IntelliJ IDEA

  2024cites this paper
• Source-Level Debugging of Compiler-Optimised Code: Ill-Posed, but Not Impossible

  2024cites this paper
• CarePlus: A general framework for hardware performance counter based malware detection under system resource competition

  2024cites this paper
• WEBRR: A Forensic System for Replaying and Investigating Web-Based Attacks in The Modern Web

  2024influential citation
• A Mixed Methods Study on the Implications of Unsafe Rust for Interoperation, Encapsulation, and Tooling

  2024cites this paper
• ChatDBG: Augmenting Debugging with Large Language Models

  2024cites this paper
• Vidi: Record Replay for Reconfigurable Hardware

  2023cites this paper
• Micro Replication

  2023cites this paper
• Automatic discovery of stateful variables in network protocol software based on replay analysis

  2023cites this paper
• Playable Quotes for Game Boy Games

  2023cites this paper
• Always-On Recording Framework for Serverless Computations: Opportunities and Challenges

  2023influential citation
• Alligator in Vest: A Practical Failure-Diagnosis Framework via Arm Hardware Features

  2023cites this paper
• Microservice Debugging with Checkpoint-Restart

  2023cites this paper
• R3: Record-Replay-Retroaction for Database-Backed Applications

  2023cites this paper
• DAMUS: Adaptively Updating Hardware Performance Counter Based Malware Detector Under System Resource Competition

  2023cites this paper
• HUND: Enhancing Hardware Performance Counter Based Malware Detection Under System Resource Competition Using Explanation Method

  2023cites this paper
• Pinky: A Modern Malware-oriented Dynamic Information Retrieval Tool

  2023cites this paper
• Causes and Effects of Unanticipated Numerical Deviations in Neural Network Inference Frameworks

  2023cites this paper
• Dynamic Slicing by On-demand Re-execution

  2022cites this paper
• CARE: Enabling Hardware Performance Counter based Malware Detection Resilient to System Resource Competition

  2022cites this paper
• Computation-centric networking

  2022cites this paper
• Stop and Look: A Novel Checkpointing and Debugging Flow for FPGAs

  2022cites this paper
• Reversible computing from a programming language perspective

  2022cites this paper
• CHEX: Multiversion Replay with Ordered Checkpoints

  2022cites this paper
• PacJam: Securing Dependencies Continuously via Package-Oriented Debloating

  2022cites this paper
• Works for Me! Cannot Reproduce – A Large Scale Empirical Study of Non-reproducible Bugs

  2022cites this paper
• Update with care: Testing candidate bug fixes and integrating selective updates through binary rewriting

  2022cites this paper
• Maniposynth: Bimodal Tangible Functional Programming

  2022cites this paper
• Riker: Always-Correct and Fast Incremental Builds from Simple Specifications

  2022cites this paper
• Permchecker: a toolchain for debugging memory managers with typestate

  2021cites this paper
• Execution reconstruction: harnessing failure reoccurrences for failure reproduction

  2021cites this paper
• Cloud-Scale Runtime Verification of Serverless Applications

  2021cites this paper
• LaForge: Always-Correct and Fast Incremental Builds from Simple Specifications

  2021cites this paper
• SyML: Guiding Symbolic Execution Toward Vulnerable States Through Pattern Learning

  2021cites this paper
• NOD4J: Near-omniscient debugging tool for Java using size-limited execution trace

  2021cites this paper
• C^2SR: Cybercrime Scene Reconstruction for Post-mortem Forensic Analysis

  2021cites this paper
• Capturing High-level Nondeterminism in Concurrent Programs for Practical Concurrency Model Agnostic Record & Replay

  2021influential citation
• Validating the Integrity of Audit Logs Against Execution Repartitioning Attacks

  2021cites this paper
• Reversibility in Message-Passing Systems

  2021cites this paper
• Feel Free to Interrupt

  2020cites this paper
• Reproducible Containers

  2020cites this paper
• Interactive debugging of concurrent programs under relaxed memory models

  2020cites this paper
• Assessing and Restoring Reproducibility of Jupyter Notebooks

  2020cites this paper
• Static analyzer debugging and quality assurance approaches

  2020cites this paper
• Debugging of RxJS-based applications

  2020cites this paper
• Why are Some Bugs Non-Reproducible? : –An Empirical Investigation using Data Fusion–

  2020cites this paper
• RIPT -- An Efficient Multi-Core Record-Replay System

  2020cites this paper
• Analyzing the Effects of Bugs on Software Interfaces

  2020cites this paper
• Bashing irreproducibility with shournal

  2020cites this paper
• Reversible Debugging in Logic Programming

  2020cites this paper
• Ad hoc Test Generation Through Binary Rewriting

  2020influential citation
• On another level: how to debug compiling query engines

  2020cites this paper
• Reverse Debugging of Kernel Failures in Deployed Systems

  2020cites this paper
• Non-intrusive Virtual Machine Analysis and Reverse Debugging with SWAT

  2020cites this paper
• Re-Animator: Versatile High-Fidelity Storage-System Tracing and Replaying

  2020cites this paper
• Metering Graphical Data Leakage with Snowman

  2020influential citation
• Reversible Computations in Logic Programming

  2020cites this paper
• StateMover: Combining Simulation and Hardware Execution for Efficient FPGA Debugging

  2020cites this paper
• Towards Three-Stage Parallelization of System Simulation

  2019cites this paper
• Replayable Execution Optimized for Page Sharing for a Managed Runtime Environment

  2019cites this paper
• SoK: The Challenges, Pitfalls, and Perils of Using Hardware Performance Counters for Security

  2019cites this paper
• RANDR: Record and Replay for Android Applications via Targeted Runtime Instrumentation

  2019cites this paper
• Different is Good: Detecting the Use of Uninitialized Variables through Differential Replay

  2019cites this paper
• Debugging support for multi-paradigm concurrent programs

  2019cites this paper
• Lightweight Record-and-Replay for Intermittent Tests Failures

  2019cites this paper
• BEEER: distributed record and replay for medical devices in hospital operating rooms

  2019cites this paper
• Sparse record and replay with controlled scheduling

  2019influential citation
• You can't debug what you can't see: Expanding observability with the OmniTable

  2019cites this paper
• Transparent tracing of microservice-based applications

  2019cites this paper
• Model Checking in a Development Workflow: A Study on a Concurrent C++ Hash Table

  2019cites this paper
• Automated Localization for Unreproducible Builds

  2018cites this paper
• Detecting Errors in a Humanoid Robot

  2018cites this paper
• Sledgehammer: Cluster-Fueled Debugging

  2018cites this paper
• McFly: Time-Travel Debugging for the Web

  2018cites this paper
• SysTaint: Assisting Reversing of Malicious Network Communications

  2018cites this paper
• Righting Web Development

  2018cites this paper
• iReplayer: in-situ and identical record-and-replay for multithreaded applications

  2018cites this paper
• Tintin: PMU Scheduling to Minimize Uncertainty

  year unknowncites this paper
• Feedback-guided Adaptive Testing of Distributed Systems Designs

  year unknowncites this paper
• Application-Integrated Record-Replay of Distributed Systems

  year unknowncites this paper
• Ensuring the Reliability and Robustness of Database Management Systems

  year unknowncites this paper
• This paper is included in the Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation.

  year unknowncites this paper