C3: Finding Counting-related Crash Consistency Atomicity Bugs for Persistent Memory
Open Access
- 29 January 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Storage
- Vol. 22 (3) , 1-18
Abstract
Persistent Memory (PM) technologies provide fast, byte-addressable access to durable storage but face crash consistency challenges, motivating extensive work of testing and verification of PM programs. Central to PM testing tools is the specification of program properties for object persistence order and atomicity. Prior work on PM property inference has focused on ordering properties and offers limited support for reasoning about atomicity. This paper explores a class of important atomicity properties between the container-like arrays and their logical size variables, referred to as the counting correlation. These properties are prevalent in PM programs but are not adequately addressed by existing techniques. We introduce C3, a tool designed to infer these counting-related atomicity properties and detect related bugs in PM programs. Our approach begins by proposing invariants to capture the necessary behaviors of counting-correlated variables. We then utilize symbolic range analysis to extract PM program behaviors, and encode them into SMT constraints. These constraints are checked against the invariants to infer likely PM program properties. Our bug detection method is based on the existing output checking approach, but adapted to be aware of input properties to detect and confirm the atomicity bugs efficiently. Our evaluation shows that C3 has found 14 atomicity bugs (including 11 previously unknown ones) from real-world PM programs.Keywords
Funding Information
- City University of Hong Kong (9220148, and 9610598)
- Directorate for Computer and Information Science and Engineering (2105006)
- City University of Hong Kong (11216925)
This publication has 37 references indexed in Scilit:
- Programming Persistent Memory2020
- iDO: Compiler-Directed Failure Atomicity for Nonvolatile Memory2018
- A Survey of Recent Trends in Testing Concurrent Software SystemsIEEE Transactions on Software Engineering, 2017
- Satisfiability modulo theoriesCommunications of the ACM, 2011
- NV-HeapsACM SIGARCH Computer Architecture News, 2011
- CTrigger2009
- A Comprehensive Memory Modeling Tool and Its Application to the Design and Analysis of Future Memory HierarchiesACM SIGARCH Computer Architecture News, 2008
- Dynamic detection of atomic-set-serializability violations2008
- Z3: An Efficient SMT Solver2008
- A serializability violation detector for shared-memory server programsACM SIGPLAN Notices, 2005