A Record-Replay-Based State Recovery Approach for Variants in an MVX System

TL;DR

This paper introduces a novel record-replay-based approach for recovering compromised variants in Multi-Variant Execution (MVX) systems. By decoupling state recovery from normal execution and employing parallel recovery groups, the system ensures uninterrupted service and high recovery accuracy with minimal overhead, addressing key limitations of existing MVX techniques.

What Problem Does This Paper Address?

Software homogenization, where multiple identical software instances are vulnerable to the same exploits, is a significant security concern. Multi-Variant Execution (MVX) is an active defense technique that mitigates this by running diverse program variants simultaneously. However, when one variant is compromised, recovering its state to match the others without disrupting the entire system has been a major challenge. Existing MVX approaches often resort to terminating or restarting compromised variants, leading to service interruptions and potential loss of progress. Furthermore, directly applying traditional fault recovery methods to MVX is difficult due to the inherent heterogeneity among variants. This paper tackles the critical need for an efficient, non-disruptive state recovery mechanism for compromised MVX variants.

Methods

The core of the proposed solution is a Syscall Coordinator (SSC), a new component integrated into the MVX system. The SSC comprises three modules:

• Recording Module: During synchronized execution, after variants have voted and their outputs are deemed consistent, the SSC records validated system calls. This recording is optimized using a two-phase logging mechanism to reduce overhead.
• Classification Module: During the state recovery phase, this module categorizes system calls into four types: non-deterministic, sensitive, external input, and process-related. This categorization is crucial for determining the appropriate replay strategy.
• Replay Module: Based on the classification, this module deterministically replays system calls using the recorded data. Special handling is implemented for different call types, such as skipping non-deterministic calls or replaying external inputs to ensure state consistency. A novel virtual process identifier (VPID) mechanism is introduced to handle process-related calls like fork without breaking program logic.

The system also features a Synchronization and Voting Algorithm managed by a Monitor component. This algorithm synchronizes variants, performs majority voting on their outputs, and identifies discrepancies. When an anomaly is detected, the Monitor removes the faulty variant and triggers the SSC for recovery.

A key innovation is the Parallel Grouped Recovery Mechanism. This design decouples the recovery process from the main execution flow. Compromised variants are placed into independent Recovery Groups, each with its own replay buffer and SSC instance. This allows multiple variants to recover concurrently and in parallel with the ongoing execution of healthy variants, ensuring uninterrupted system service.

Datasets

The paper evaluates its approach using two types of workloads:

• SPEC CPU 2006 Benchmark: This is a standard suite of computationally demanding real-world programs used to measure the performance overhead of the recording and recovery processes.
• Server Applications: Widely used server applications like lighttpd, nginx, and redis were tested to evaluate the system's practicality in long-running, high-throughput services.

Key Insights and Ideas

• Decoupling is Key: The fundamental insight is that separating the state recovery process from the main synchronized execution flow is essential for achieving uninterrupted service. This allows healthy variants to continue processing requests while compromised ones are being restored.
• Parallel Recovery Groups: The concept of independent Recovery Groups, each handling a single failed variant and operating in parallel, is crucial for scalability and preventing recovery bottlenecks.
• Intelligent System Call Replay: The classification of system calls and the tailored replay strategies (e.g., skipping certain calls, replaying inputs) are vital for ensuring accurate state reconstruction without introducing new inconsistencies.
• Virtual Process IDs (VPIDs): The VPID mechanism is an elegant solution to a common challenge in replay systems: handling process-related calls like fork where PIDs are critical but differ between variants. This prevents false positives during voting and ensures correct replay.
• Low Overhead Achieved: Despite adding a complex recovery mechanism, the system demonstrates surprisingly low overhead for both recording and replay phases, making it practical for real-world deployment.

Key Results

• Performance Overhead: The system incurs an average recording overhead of 6.96% and a replay overhead of 8.98% on the SPEC CPU 2006 benchmark. This is competitive with or better than existing record-replay systems like Scribe and Jmvx.
• Uninterrupted Execution: The system achieves Level 2 availability (normal operation with successful recovery and reintegration) in the vast majority of test cases, even when faults are injected at different points in program execution. Level 1 (service continues but recovery fails) was only observed in rare cases with short-running benchmarks where recovery couldn't complete before termination.
• Recovery Correctness: The system demonstrates 100% replay Accuracy on deterministic SPEC CPU benchmarks and maintains over 95% accuracy on server applications under realistic workloads, indicating high fidelity in state restoration.
• Security: The system effectively defends against common memory corruption attacks (stack overflows, heap overflows, integer overflows) by leveraging MVX's core divergence detection and its own recovery mechanism.

Limitations and Future Work

• Limitations:
  • The paper notes that for very short-running benchmark programs, recovery might not complete before the program terminates, leading to a Level 1 outcome. This is considered an artifact of testing short programs and unlikely for long-running server applications.
• While the system is tested against common memory corruption attacks, the paper doesn't explicitly detail its resilience against all possible advanced attack vectors.
• Future Work:
  • The authors suggest future work will focus on enhancing the security of the Monitor component. This is identified as a critical part of the MVX system, and ensuring its integrity during runtime is seen as a way to further improve the overall system security.

@article{zhong2025record,
  author = {Xu Zhong and Xinjian Zhao and Bo Zhang and June Li and Yifan Wang and Yu Li},
  title = {{A Record-Replay-Based State Recovery Approach for Variants in an MVX System}},
  journal = {Inf.},
  year = {2025},
  doi = {10.3390/info16100826},
}