Robustness Verification for Checking Crash Consistency of Non-volatile Memory

Non-volatile memory keeps your data through a power loss, but the hardware persists writes to it in an unpredictable order, so programmers must sprinkle in flush instructions to force writes out in the right sequence — and getting that wrong means a crash can leave the data in a broken state no recovery can fix; existing tools mostly test for such bugs dynamically and need human guidance, so they can miss cases; this paper (Tsinghua — Zhilei Han, Fei He) presents PMVerify, a fully automated verifier that checks a property called robustness by reducing the question of which post-crash persistent states are reachable to a validity check with extra ordering constraints, exploring all executions symbolically with an SMT solver built into the DPLL(T) loop, and matching the state-of-the-art dynamic tool PSan at finding violations on the PMDK benchmark while being a sound verification method rather than a test.

The argument in one glance

Problem

Non-volatile memory persists writes in the wrong order unless you flush carefully

Non-volatile memory (NVM) is memory that keeps its contents through a power loss, at speeds close to DRAM, so a program can store its data structures directly in memory and have them survive a crash — no files, no serialization. The catch is ordering. NVM has weak persistency: the order in which the hardware actually commits stores to the persistent medium is not the order the program issued them, so writes can reach durable memory out of order. To make sure the persistent state is recoverable after a crash, the developer must manually insert flush (and fence) instructions to force pending writes out in the right sequence. This is fiddly and error-prone, and a mistake is silent: the program runs fine until a crash happens at just the wrong moment, and then the persistent state is inconsistent in a way recovery cannot repair.
What people did

Test for crash-consistency bugs dynamically, with user guidance

The established way to catch these bugs is dynamic, testing-based tools such as PMTest and PSan. They run the program, observe its stores and flushes, and check for crash-consistency violations, often guided by user annotations about what the program intends. When they run an execution that exposes a missing or misplaced flush, they report it, and they are effective enough to be the state of the art.
Why it fell short

Testing only sees the executions it runs, and leans on the user

Because these tools are dynamic, they only examine the executions they actually run and the crash points they happen to try, so a crash-consistency bug that manifests only under an untested interleaving or crash timing can slip through — testing can find bugs but cannot prove their absence. They also rely on user guidance to know what the program is supposed to guarantee, which shifts burden and risk onto the developer. What is missing is a fully automated method that verifies crash consistency rather than sampling it: one that reasons over all executions and all crash points, so that if it reports no violation, none exists. Providing that guarantee, without demanding the developer hand-specify the intended behavior, is the gap.
This paper's idea

Verify robustness by reducing crash-state reachability to execution validity

PMVerify is a fully automated method to verify robustness, a property established for ensuring crash consistency of NVM programs. Its key observation is that whether a particular post-crash non-volatile state is reachable under a given pre-crash execution can be reduced to the validity of that pre-crash execution with additional ordering constraints — the constraints that would have forced exactly those stores to have persisted. This turns a question about crashes into a question about ordinary executions plus ordering, which a solver can answer. The robustness verification algorithm uses a search-based framework to explore all partial executions and states, checking whether any non-volatile state is reachable under some pre-crash execution; when it finds one, it further checks that state's reachability under the memory consistency model. PMVerify implements this with symbolic encoding of the program and an SMT solver to explore all executions and states efficiently, and integrates the check into the solver's DPLL(T) framework to optimize it. On the PMDK example benchmark, PMVerify is competitive with the state-of-the-art dynamic tool PSan at detecting robustness violations, while being a sound verification method rather than a test.

Why this problem is worth solving

Non-volatile memory promises to make persistence as simple as using memory, but only if the ordering is right, and the ordering is exactly what is hard.

A program that stores durable data must ensure that, no matter when a crash strikes, what remains in persistent storage is a state it can recover from — this is crash consistency. With traditional files this is managed through careful use of writes and syncs, but non-volatile memory changes the game by letting the program write persistent data with ordinary memory stores. The problem is that the hardware does not persist those stores in program order: to be fast, the processor and memory system buffer and reorder writes on their way to the durable medium, so at the moment of a crash some later stores may have persisted while some earlier ones have not. If the program has not forced an ordering, the surviving state can be one the program never intended and cannot recover from — for example, a pointer persisted before the object it points to, leaving a dangling reference in durable memory. To prevent this, the developer inserts flush instructions to push specific writes to durability and fences to order them, effectively hand-managing which writes must persist before which others. Getting every one of these right, across all the ways a program can be interrupted, is genuinely hard, and the failure mode is a corruption that appears only after an unlucky crash. That is why a rigorous way to check crash consistency matters so much: the bugs are subtle, silent, and catastrophic, and they are exactly the kind of thing humans and ordinary testing miss.

The reason verification, not just testing, is the goal is that crash-consistency bugs hide in the executions you did not try.

Dynamic crash-consistency tools work by running the program and inspecting the stores and flushes on that run, then reasoning about what could survive a crash at various points along it. This is valuable and finds real bugs, but it has two intrinsic limits. First, it is only as good as the executions and crash points it exercises: a program can behave differently under different thread interleavings, inputs, and precise crash timings, and a missing flush that only bites under one rare combination will go unseen unless that combination is run. So testing can demonstrate a bug’s presence but never its absence. Second, these tools typically need the developer to supply guidance about what the program is meant to guarantee, which is extra work and another place to make mistakes. A verification method changes both. By reasoning symbolically over all executions and all crash points at once — rather than sampling them — it can certify that no crash-consistency violation exists, turning “we tested and found nothing” into “we proved there is nothing.” And by checking a general property like robustness rather than a program-specific specification, it can be fully automatic. For a correctness property whose violations are rare, silent, and disastrous, that shift from sampling to proof is exactly what is worth the effort, which is what PMVerify sets out to provide.

What people did before, and where it broke

Manual flush placement and code review. Developers insert flushes and fences by hand and review the code for crash-consistency correctness. Where it broke. The reasoning is subtle and the failure mode is a rare crash timing, so humans miss cases, and there is no guarantee the placement is complete or correct.
Dynamic testing tools (PMTest). Instrument the program and check stores and flushes against user-provided assertions at run time. Where it broke. It only checks the executions run and relies heavily on the user to state what to check, so unexercised interleavings and crash points, and unstated intent, escape detection.
State-of-the-art dynamic detectors (PSan). Detect crash-consistency (robustness) violations dynamically with less annotation burden, the leading such tool. Where it broke. It remains dynamic, so it samples executions rather than covering all of them, and cannot prove the absence of violations.
Full functional verification with a specification. Prove the program meets a hand-written correctness spec across crashes. Where it broke. Writing and maintaining a full crash-recovery specification is heavy and program-specific, so it does not give an automatic, general check.
The gap. No method verified crash consistency fully automatically by reasoning over all executions and crash points — reducing which post-crash states are reachable to a solvable question about execution validity — so that a clean result means the property truly holds.

How PMVerify works

Verifying robustness by turning crash reachability into a solver query

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Check a general property, robustness, instead of a per-program specification. The first move that makes automation possible is choosing what to verify. Rather than asking a developer to write a full specification of what their crash-recovery code should do, PMVerify verifies robustness, a property established to capture crash consistency for NVM programs in a program-independent way — intuitively, that the weak, reordering persistency of the hardware never lets the program leave behind a persistent state that a correctly ordered execution would not. Because the property is general, checking it needs no bespoke spec, so the method can be fully automatic. Reasoning rigorously about how a program behaves under a relaxed hardware ordering model, and pinning down a property that captures correctness there, is the same concern the work on a scoped, buffered persistency model for GPUs covered elsewhere on this site is built on, formalizing exactly what the hardware guarantees about the order of persists. PMVerify builds a verifier on top of such a property for NVM programs.

Turn a question about crashes into a question a solver can answer. The technical heart is the reduction: asking whether some post-crash persistent state is reachable under a given execution is transformed into asking whether that execution is valid once you add the ordering constraints that would have made exactly those stores persist. This converts an awkward reasoning-about-crashes problem into a standard reasoning-about-executions problem, which PMVerify then encodes symbolically and hands to an SMT solver that explores all executions and states at once. Reducing a hard correctness question to a symbolic query that a solver can discharge over all cases, rather than checking cases one by one, is the same rigorous-analysis strategy the work on precise invariant-guided pointer analysis covered elsewhere on this site pursues, using formal machinery to reason about all program behaviors at once. PMVerify’s twist is the specific reduction from crash reachability to execution validity that makes crash consistency tractable for a solver.

Prove absence, not just find presence, of bugs. The payoff of going symbolic is completeness. A dynamic tool that samples executions can find a crash-consistency bug but never certify there are none; PMVerify’s search covers all partial executions and crash points, and when it reports no reachable bad state, none exists under its model. This matters precisely because getting persistence right on NVM is so error-prone that developers need assurance, not just spot checks, that their flushing is correct. Giving programmers confidence that a subtle, low-level correctness concern is actually handled — rather than leaving them to discover failures the hard way — is the same reliability goal the work on a software caching runtime for embedded non-volatile memory covered elsewhere on this site pursues, taking the burden of correct persistence off the developer. PMVerify pursues it through verification, replacing “we tested and found nothing” with “we checked all executions and there is nothing.”

Following a program through PMVerify

Verifying that an NVM program's flushes keep it crash-consistent

An illustrative trace, based on the paper's abstract, of how PMVerify verifies robustness. Internal details beyond the abstract were not available for this draft.

Step 1 of 5

Take the NVM program as input

PMVerify is given a program that persists data to non-volatile memory with stores, flushes, and fences. The goal is to verify robustness: that no crash at any point of any execution can leave an inconsistent persistent state.

No hand-written specification of intended behavior is required.

Why it works

A general property removes the need for a spec. Full crash-recovery verification needs a hand-written specification per program → but robustness captures crash consistency in a program-independent way → so the check can be fully automatic with no per-program spec.
The reduction makes crashes solver-friendly. Reasoning directly about crash timings is awkward for a solver → but reducing crash-state reachability to execution validity plus ordering constraints turns it into a standard query → so an SMT solver can decide it.
Symbolic search covers all executions. Dynamic testing only sees the runs it executes → but symbolic encoding represents all executions and states at once → so a clean result proves absence of violations, not just their non-appearance in tests.
The second consistency check keeps reports sound. A candidate bad state might be an artifact of over-approximation → but re-checking its reachability under the memory consistency model filters those out → so reported violations are genuine.
DPLL(T) integration keeps it fast. Bolting robustness checking on top of a solver would be slow → but integrating it into the DPLL(T) search loop optimizes the two together → so PMVerify stays competitive with a state-of-the-art dynamic tool despite doing full verification.

What it costs (trade-offs and scope)

This is a draft built from the paper’s abstract. The full paper was behind a publisher access wall for this draft (no arXiv version, no open-access or author copy located, and the ACM Digital Library returned a bot-verification challenge), so this account is assembled from the paper’s complete abstract plus standard background on non-volatile memory, persistency, and verification. The exact definition of robustness, the reduction and encoding, the DPLL(T) integration, and the evaluation details are not reproduced here and should be read from the paper.
Symbolic verification faces scalability limits. Reasoning over all executions with an SMT solver is powerful but can be expensive as programs grow; the abstract reports competitiveness with a dynamic tool on the PMDK example benchmark, but how PMVerify scales to large, complex programs beyond those examples is not detailed in this draft.
The guarantee is relative to the model. Verification certifies robustness under the memory and persistency models PMVerify encodes; the assurance is only as faithful as those models are to the real hardware, and behaviors outside the modeled scope are not covered.
It checks robustness, not full functional correctness. Robustness is a property for ensuring crash consistency, but it is not a complete specification of what a program should compute after recovery; a program can be robust and still be functionally wrong in ways outside the property’s scope.
The comparison is on a specific benchmark and baseline. Being competitive with PSan at violation detection is reported on the PMDK example benchmark; results on other programs, and the full trade-off between verification cost and dynamic testing speed, would need the paper’s complete evaluation.

The evaluation

Checking crash consistency of NVM programs

Property	Manual review	Dynamic testing (PSan)	PMVerify
Coverage of executions
Can prove absence of bugs
Needs user guidance
How it reasons
Reported outcome (per abstract)

A qualitative comparison based on the paper's abstract; the paper's main body, including the exact robustness definition, the reduction and encoding, and the full evaluation, was not available for this draft. The competitiveness with PSan on the PMDK example benchmark is the abstract's own reported result.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This is an honest draft assembled from the paper’s complete abstract plus standard background on non-volatile memory, crash consistency, persistency models, and SMT-based verification; the full text was not accessible (no arXiv preprint, no open-access or author copy found, and the ACM Digital Library version returned a bot-verification challenge), so the internal design is not reproduced. What is solid and comes directly from the abstract: NVM has weak store-persistence ordering, so developers must flush pending writes, an error-prone task, and crash consistency must be checked; most existing solutions are dynamic, testing-based, and rely on user guidance; PMVerify is a fully automated method to verify robustness, a property for ensuring crash consistency; its key observation is that reachability of a post-crash non-volatile state under a given pre-crash execution can be reduced to validity of the pre-crash execution with additional ordering constraints; its algorithm uses a search-based framework to explore all partial executions and states, checks whether any non-volatile state is reachable under some pre-crash execution, and then checks that state’s reachability under the memory consistency model; PMVerify uses symbolic encoding and an SMT solver, integrates the check into the DPLL(T) framework, and on the PMDK example benchmark is competitive with the state-of-the-art dynamic tool PSan at detecting robustness violations. The explanations of why NVM ordering is hard and why verification beats testing are standard background and the natural reading of the abstract, not claims about PMVerify’s specific internals. Read the exact robustness definition, the reduction, the encoding, and the evaluation in the paper itself; treat this page as a faithful account at the level of the abstract, not of the implementation.

Background

Why persistent memory turned ordering into a correctness problem

It helps to see PMVerify against a shift that non-volatile memory forced on systems programming. For decades, durability lived behind the file system: you wrote data, called a sync, and the operating system handled the messy details of getting bytes safely to disk. Non-volatile memory dissolved that boundary by letting programs make data durable with ordinary memory stores, which is wonderfully fast and simple in principle — but it exposed the raw truth that hardware does not persist writes in program order. Suddenly application programmers, not just file-system authors, had to reason about persistency ordering, inserting flushes and fences to control which writes survive a crash and in what order, and to get right the recovery logic that reconstructs a consistent state afterward. This is a genuinely hard, low-level correctness discipline, and the systems community has responded on many fronts: defining precise persistency models so the guarantees are unambiguous, building libraries and runtimes that hide the flushing, and creating tools to catch the bugs that slip through. The bugs matter enormously because persistent memory is used exactly where durability is critical, such as databases. That broader move to put persistent memory under real, correctness-sensitive workloads is the setting the work on persistent-memory disaggregation for cloud-native relational databases covered elsewhere on this site operates in, where a crash-consistency bug would corrupt a database. PMVerify addresses the correctness side, giving a way to prove the flushing is right rather than hoping testing found the holes.

If you remember only three things

1. Non-volatile memory keeps data through crashes at near-DRAM speed, but the hardware commits stores to the durable medium in a weak, reordered fashion, so developers must manually insert flush and fence instructions to guarantee a recoverable on-crash state. This is error-prone, and mistakes are silent: the program works until a crash at the wrong instant leaves the persistent state inconsistent. Existing checkers are mostly dynamic and testing-based, relying on user guidance and only covering the executions they run, so they can find crash-consistency bugs but cannot prove their absence.
2. PMVerify is a fully automated method that verifies robustness, a general property for ensuring crash consistency. Its key observation is that whether a given post-crash non-volatile state is reachable under a pre-crash execution can be reduced to whether that execution is valid with additional ordering constraints — turning a crash question into a solver-friendly execution question. It uses a search-based framework over all partial executions and states, confirms any candidate bad state against the memory consistency model, and implements this with symbolic encoding and an SMT solver integrated into the DPLL(T) loop.
3. On the PMDK example benchmark, PMVerify is competitive with the state-of-the-art dynamic tool PSan at detecting robustness violations, while being a sound verification method that reasons over all executions rather than sampling them. This explainer is a draft from the abstract, so the exact robustness definition, reduction, encoding, and evaluation should be confirmed against the paper; symbolic verification faces scalability limits, the guarantee is relative to the modeled hardware, and robustness is a crash-consistency property, not full functional correctness.

Check yourself

Check your understanding

1. Why is writing correct crash-consistent code hard on non-volatile memory?
2. What is PMVerify's core insight?
3. Why is PMVerify's verification approach stronger than dynamic testing tools?
4. What should a reader keep in mind about this explainer, and what did the paper report?

Sources

The paper is “Robustness Verification for Checking Crash Consistency of Non-volatile Memory” by Zhilei Han and Fei He (Tsinghua University), published at ASPLOS 2025, DOI 10.1145/3669940.3707269. The tool is named PMVerify. It is licensed CC BY.

This explainer is a draft. The paper’s main text was not accessible at the time of writing (there is no arXiv preprint, no open-access or author copy was located, and the ACM Digital Library PDF returned a bot-verification challenge), so it is written from the paper’s complete abstract together with standard background on non-volatile memory, crash consistency, persistency models, and SMT-based verification. The abstract supplies the problem and approach: emerging NVM technologies provide DRAM-competitive performance with persistence, but exhibit weak behaviour in the order stores are committed, so developers must flush pending writes, and it is crucial to rigorously check crash consistency; most existing solutions are testing-based and rely on user guidance to dynamically detect deficiencies; the paper presents a fully automated method to verify robustness, a newly established property for ensuring crash consistency; the method is based on the observation that reachability of a post-crash non-volatile state under a given pre-crash execution can be reduced to validity of the pre-crash execution with additional ordering constraints; the robustness verification algorithm employs a search-based framework to explore all partial executions and states and checks whether any non-volatile state is reachable under a certain pre-crash execution, then checks its reachability under the memory consistency model; the algorithm is implemented in the tool PMVerify, which uses symbolic encoding of the program and an SMT solver to efficiently explore all executions and states, integrated into the DPLL(T) framework to optimize the robustness checking; and experiments on the PMDK example benchmark show PMVerify is competitive with the state-of-the-art dynamic tool PSan in robustness violation detection. The explanations of why NVM ordering is hard and why verification improves on testing are standard background and the natural reading of the abstract, not claims about PMVerify’s specific internal design. The paper’s exact robustness definition, the reduction and encoding, the DPLL(T) integration, and the evaluation setup are not reproduced here and should be read from the paper. No numbers beyond the abstract’s have been introduced.