Scalable and Accurate Application-Level Crash-Consistency Testing via Representative Testing

Yile Gu, Ian Neal, Jiexiao Xu, Shaun Christopher Lee, Ayman Said, Musa Haydar, Jacob Van Geffen, Rohan Kadekodi, Andrew Quinn, Baris Kasikci

Abstract

Crash consistency is essential for applications that must persist data. Crash-consistency testing has been commonly applied to find crash-consistency bugs in applications. The crash-state space grows exponentially as the number of operations in the program increases, necessitating techniques for pruning the search space. However, state-of-the-art crash-state space pruning is far from ideal. Some techniques look for known buggy patterns or bound the exploration for efficiency, but they sacrifice coverage and may miss bugs lodged deep within applications. Other techniques eliminate redundancy in the search space by skipping identical crash states, but they still fail to scale to larger applications. In this work, we propose representative testing: a new crash-state space reduction strategy that achieves high scalability and high coverage. Our key observation is that the consistency of crash states is often correlated, even if those crash states are not identical. We build Pathfinder, a crash-consistency testing tool that implements an update behaviors-based heuristic to approximate a small set of representative crash states. We evaluate Pathfinder on POSIX-based and MMIO-based applications, where it finds 18 (7 new) bugs across 8 production-ready systems. Pathfinder scales more effectively to large applications than prior works and finds 4x more bugs in POSIX-based applications and 8x more bugs in MMIO-based applications compared to state-of-the-art systems.

Introduction

When an application writes data to persistent storage—whether a traditional hard drive or modern persistent memory—it relies on the assumption that data will remain consistent following a system crash. However, ensuring "crash consistency" is a significant challenge in systems programming. Modern hardware and operating systems buffer writes in memory to optimize performance, which often results in the order of data persistence differing from the order of program execution.

To identify vulnerabilities, developers utilize crash-consistency testing tools that simulate failures at various points during execution. However, these tools face a fundamental hurdle: state-space explosion. For a program performing $N$ unsynchronized operations, there are $2^N$ possible crash states to evaluate. In large-scale production applications, this number becomes computationally intractable. Existing solutions either prune the search space too aggressively, missing deep-seated bugs, or focus only on eliminating identical states, which fails to provide the necessary scalability for complex systems.

Representative Testing with Pathfinder

This paper introduces Representative Testing, a novel strategy implemented in a tool called Pathfinder. The core insight is that many crash states are semantically correlated. If a specific state is found to be consistent, a large group of related states is likely consistent as well. Rather than testing every possible permutation, Pathfinder identifies and tests only the "representative" behaviors of the program.

Pathfinder operates through a five-stage pipeline:

  1. Tracing: The tool records all persistence operations, such as system calls in POSIX environments or memory stores in Memory-Mapped I/O (MMIO) environments, during a standard execution run.
  2. Persistence Graph Construction: It builds a directed graph where nodes represent updates and edges represent "happens-before" constraints enforced by synchronization primitives like fsync or memory fences.
  3. Subgraph Creation: Pathfinder partitions the execution trace into smaller "update behaviors" using specialized heuristics:
  4. POSIX Heuristic: It utilizes the function call stack (backtrace) to group operations. Writes occurring within the same function context are treated as a single semantic unit.
  5. MMIO Heuristic: It groups updates based on the data types being modified and their temporal proximity within execution epochs.
  6. Identifying Representatives: The tool formalizes a "represents" relation. If behavior A contains a superset of the updates in behavior B but possesses fewer ordering constraints, testing A effectively covers the logic of B. Pathfinder filters the set to test only these representative subgraphs.
  7. Model Checking: Finally, it employs Dynamic Partial Order Reduction (DPOR) to exhaustively test the representative subgraphs and identify inconsistencies.

Evaluation and Key Results

Pathfinder was evaluated against a suite of production-ready systems, including POSIX-based storage engines like LevelDB, RocksDB, and WiredTiger, as well as MMIO-based applications like Redis and the Heterogeneous Memory Storage Engine (HSE).

Bug Discovery and Scalability

Pathfinder successfully identified 18 bugs, 7 of which were previously unknown, in heavily tested and mature codebases. When compared to state-of-the-art tools within a fixed two-hour testing window, Pathfinder's efficiency was markedly higher:

  • POSIX Applications: Found 4x more bugs than ALICE.
  • MMIO Applications: Found 8x more bugs than Jaaru.

Efficiency Gains

By focusing on representative states, Pathfinder reduced the required crash-state test space by 90% to 99% compared to exhaustive testing methods. Crucially, this reduction did not come at the cost of efficacy; the tool maintained the ability to find the same bugs as exhaustive methods while achieving higher code coverage significantly faster.

Discussion and Future Work

While Pathfinder represents a significant leap in testing scalability, it is subject to certain limitations. Its effectiveness is inherently tied to the quality of the initial execution trace; if a buggy code path is not triggered during the tracing phase, the tool cannot analyze it. Furthermore, it relies on application-defined oracles (such as recovery scripts) to detect inconsistencies.

Future research may explore the integration of Pathfinder with fuzzing or symbolic execution to automatically generate more diverse execution traces. Additionally, the principles of Representative Testing could be extended to other domains plagued by state-space explosion, such as testing message-ordering consistency in distributed systems.

Summary updated

Abstract

Crash consistency is essential for applications that must persist data. Crash-consistency testing has been commonly applied to find crash-consistency bugs in applications. The crash-state space grows exponentially as the number of operations in the program increases, necessitating techniques for pruning the search space. However, state-of-the-art crash-state space pruning is far from ideal. Some techniques look for known buggy patterns or bound the exploration for efficiency, but they sacrifice coverage and may miss bugs lodged deep within applications. Other techniques eliminate redundancy in the search space by skipping identical crash states, but they still fail to scale to larger applications. In this work, we propose representative testing: a new crash-state space reduction strategy that achieves high scalability and high coverage. Our key observation is that the consistency of crash states is often correlated, even if those crash states are not identical. We build Pathfinder, a crash-consistency testing tool that implements an update behaviors-based heuristic to approximate a small set of representative crash states. We evaluate Pathfinder on POSIX-based and MMIO-based applications, where it finds 18 (7 new) bugs across 8 production-ready systems. Pathfinder scales more effectively to large applications than prior works and finds 4x more bugs in POSIX-based applications and 8x more bugs in MMIO-based applications compared to state-of-the-art systems.
BibTeX
@inproceedings{gu2025scalable,
  author = {Yile Gu and Ian Neal and Jiexiao Xu and Shaun Christopher Lee and Ayman Said and Musa Haydar and Jacob Van Geffen and Rohan Kadekodi and Andrew Quinn and Baris Kasikci},
  title = {{Scalable and Accurate Application-Level Crash-Consistency Testing via Representative Testing}},
  booktitle = {Proceedings of the ACM on Programming Languages},
  year = {2025},
  url = {https://openreview.net/forum?id=uxfVqOXApJ},
}
Figure