TL;DR
Pathfinder is a new testing tool that solves the "state space explosion" in crash-consistency testing by identifying and testing only "representative" program behaviors. By grouping semantically related operations, it found 18 bugs (including 7 new ones) in production-ready systems like RocksDB and LevelDB, outperforming existing tools by 4x–8x in bug-finding efficiency.
What Problem Does This Paper Address?
When an application writes data to persistent storage (like a hard drive or persistent memory), it often assumes that if the system crashes, the data will remain in a consistent state. However, ensuring this "crash consistency" is notoriously difficult. Modern systems buffer writes in memory for performance, meaning the order in which data actually hits the disk might not match the order the programmer intended.
To find bugs, developers use crash-consistency testing tools that simulate crashes at every possible point in an execution. The problem is state-space explosion: if a program performs $N$ unsynced operations, there are $2^N$ possible crash states to check. For large applications, this number is astronomical. Existing tools either prune the search space too aggressively (missing deep bugs) or only skip identical states (failing to scale).
Methods
The authors introduce Representative Testing, implemented in a tool called Pathfinder. The core idea is that many crash states are "correlated"—meaning if one state is consistent, a whole group of similar states is likely consistent too.
Pathfinder works in five steps:
- Tracing: It records all persistence operations (syscalls in POSIX or memory stores in MMIO) during a normal program run.
- Persistence Graph: It builds a graph where nodes are updates and edges represent "happens-before" constraints (enforced by commands like
fsyncor memory fences). - Subgraph Creation: It breaks the large execution trace into smaller "update behaviors" using a novel heuristic.
- For POSIX: It uses the function call stack (backtrace) to group operations. If a group of writes happens inside the same function, they are treated as a single semantic behavior.
- For MMIO: It groups updates based on the data types being modified and their temporal proximity (epochs).
- Identifying Representatives: It formalizes a "represents" relation. If behavior A contains a superset of the updates in behavior B but has fewer ordering constraints, testing A effectively covers B. Pathfinder only tests the "representatives."
- Model Checking: It uses Dynamic Partial Order Reduction (DPOR) to exhaustively test the representative subgraphs and find inconsistencies.
Datasets
The authors evaluated Pathfinder across a diverse set of production-ready systems and benchmarks:
- POSIX-based Applications: LevelDB, RocksDB, and WiredTiger (the storage engine for MongoDB).
- MMIO-based Applications: PM-cached (a persistent memory port of Memcached), Redis, and HSE (Heterogeneous Memory Storage Engine).
- Microbenchmarks: 16 MMIO-based data structures and indices, including those from the PMDK and RECIPE libraries.
- Comparison Baselines: They compared Pathfinder against ALICE (for POSIX) and Jaaru and Witcher (for MMIO).
Key Insights and Ideas
- Semantic Correlation: The "aha moment" is that crash-consistency bugs are usually about ordering, not specific data values. Developers write code in semantic blocks (e.g., "inserting a key into a B-Tree"). If the ordering logic is broken in one instance of that block, it’s likely broken in all of them.
- Heuristics over Patterns: Unlike previous tools (like Witcher) that look for specific "buggy patterns," Pathfinder uses a general heuristic based on program structure. This allows it to find "non-pattern" bugs that other tools miss.
- Universal Abstraction: By using the Persistence Graph, Pathfinder provides a unified way to reason about both traditional file system calls (POSIX) and modern persistent memory (MMIO).
Key Results
- Bug Discovery: Pathfinder found 18 bugs total, 7 of which were previously unknown. These were found in heavily tested, production-ready systems.
- Superior Scalability: In a 2-hour testing window, Pathfinder found 4x more bugs in POSIX applications than ALICE and 8x more bugs in MMIO applications than Jaaru.
- Efficiency: Pathfinder reduced the number of crash states to test by 90% to 99% compared to exhaustive testing, while still maintaining the ability to find the same bugs.
- Coverage: It achieved higher code coverage significantly faster than prior state-of-the-art tools.
Limitations and Future Work
- Trace Dependency: Pathfinder can only find bugs in the code paths that are actually executed during the "tracing" phase. If a buggy code path isn't triggered by the initial test workload, Pathfinder won't see it.
- Oracle Quality: The tool relies on an "application-defined oracle" (like a recovery script or an assertion) to tell if a crash state is actually inconsistent. If the oracle is weak, Pathfinder might miss bugs.
- Distributed Systems: The authors suggest that "Representative Testing" could be generalized to other fields, such as testing message-ordering bugs in distributed systems, which also suffer from state-space explosion.
- Integration with Fuzzing: Future work could involve combining Pathfinder with fuzzing or symbolic execution to automatically generate more diverse execution traces to feed into the tool.
Summary updated