Witcher: Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores

Xinwei Fu; Wook Hee Kim; Ajay Paddayuru Shreepathi; Mohannad Ismail; Sunny Wadkar; Dongyoon Lee; Changwoo Min

doi:10.1145/3477132.3483556

Witcher: Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores

Xinwei Fu
, Wook Hee Kim
, Ajay Paddayuru Shreepathi
, Mohannad Ismail
, Sunny Wadkar
, Dongyoon Lee
, Changwoo Min

Computer Science

Virginia Polytechnic Institute and State University
Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

35 Scopus citations

Abstract

The advent of non-volatile main memory (NVM) enables the development of crash-consistent software without paying storage stack overhead. However, building a correct crash-consistent program remains very challenging in the presence of a volatile cache. This paper presents Witcher, a systematic crash consistency testing framework, which detects both correctness and performance bugs in NVM-based persistent key-value stores and underlying NVM libraries, without test space explosion and without manual annotations or crash consistency checkers. To detect correctness bugs, Witcher automatically infers likely correctness conditions by analyzing data and control dependencies between NVM accesses. Then Witcher validates if any violation of them is a true crash consistency bug by checking output equivalence between executions with and without a crash. Moreover, Witcher detects performance bugs by analyzing the execution traces. Evaluation with 20 NVM key-value stores based on Intel's PMDK library shows that Witcher discovers 47 (36 new) correctness consistency bugs and 158 (113 new) performance bugs in both applications and PMDK.

Original language	English
Title of host publication	SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles
Publisher	Association for Computing Machinery, Inc
Pages	100-115
Number of pages	16
ISBN (Electronic)	9781450387095
DOIs	https://doi.org/10.1145/3477132.3483556
State	Published - Oct 26 2021
Event	28th ACM Symposium on Operating Systems Principles, SOSP 2021 - Virtual, Online, Germany Duration: Oct 26 2021 → Oct 29 2021

Publication series

Name	SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles

Conference

Conference	28th ACM Symposium on Operating Systems Principles, SOSP 2021
Country/Territory	Germany
City	Virtual, Online
Period	10/26/21 → 10/29/21

Keywords

Crash Consistency
Debugging
Non-volatile Memory
Testing

Access to Document

10.1145/3477132.3483556

Cite this

Fu, X., Kim, W. H., Shreepathi, A. P., Ismail, M., Wadkar, S., Lee, D., & Min, C. (2021). Witcher: Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores. In SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles (pp. 100-115). (SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles). Association for Computing Machinery, Inc. https://doi.org/10.1145/3477132.3483556

Fu, Xinwei ; Kim, Wook Hee ; Shreepathi, Ajay Paddayuru et al. / Witcher : Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores. SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles. Association for Computing Machinery, Inc, 2021. pp. 100-115 (SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles).

@inproceedings{b75d0ac59d824ae999e1a30f6877defe,

title = "Witcher: Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores",

abstract = "The advent of non-volatile main memory (NVM) enables the development of crash-consistent software without paying storage stack overhead. However, building a correct crash-consistent program remains very challenging in the presence of a volatile cache. This paper presents Witcher, a systematic crash consistency testing framework, which detects both correctness and performance bugs in NVM-based persistent key-value stores and underlying NVM libraries, without test space explosion and without manual annotations or crash consistency checkers. To detect correctness bugs, Witcher automatically infers likely correctness conditions by analyzing data and control dependencies between NVM accesses. Then Witcher validates if any violation of them is a true crash consistency bug by checking output equivalence between executions with and without a crash. Moreover, Witcher detects performance bugs by analyzing the execution traces. Evaluation with 20 NVM key-value stores based on Intel's PMDK library shows that Witcher discovers 47 (36 new) correctness consistency bugs and 158 (113 new) performance bugs in both applications and PMDK.",

keywords = "Crash Consistency, Debugging, Non-volatile Memory, Testing",

author = "Xinwei Fu and Kim, \{Wook Hee\} and Shreepathi, \{Ajay Paddayuru\} and Mohannad Ismail and Sunny Wadkar and Dongyoon Lee and Changwoo Min",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 28th ACM Symposium on Operating Systems Principles, SOSP 2021 ; Conference date: 26-10-2021 Through 29-10-2021",

year = "2021",

month = oct,

day = "26",

doi = "10.1145/3477132.3483556",

language = "English",

series = "SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles",

publisher = "Association for Computing Machinery, Inc",

pages = "100--115",

booktitle = "SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles",

}

Fu, X, Kim, WH, Shreepathi, AP, Ismail, M, Wadkar, S, Lee, D & Min, C 2021, Witcher: Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores. in SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles. SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles, Association for Computing Machinery, Inc, pp. 100-115, 28th ACM Symposium on Operating Systems Principles, SOSP 2021, Virtual, Online, Germany, 10/26/21. https://doi.org/10.1145/3477132.3483556

Witcher: Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores. / Fu, Xinwei; Kim, Wook Hee; Shreepathi, Ajay Paddayuru et al.
SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles. Association for Computing Machinery, Inc, 2021. p. 100-115 (SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Witcher

T2 - 28th ACM Symposium on Operating Systems Principles, SOSP 2021

AU - Fu, Xinwei

AU - Kim, Wook Hee

AU - Shreepathi, Ajay Paddayuru

AU - Ismail, Mohannad

AU - Wadkar, Sunny

AU - Lee, Dongyoon

AU - Min, Changwoo

PY - 2021/10/26

Y1 - 2021/10/26

N2 - The advent of non-volatile main memory (NVM) enables the development of crash-consistent software without paying storage stack overhead. However, building a correct crash-consistent program remains very challenging in the presence of a volatile cache. This paper presents Witcher, a systematic crash consistency testing framework, which detects both correctness and performance bugs in NVM-based persistent key-value stores and underlying NVM libraries, without test space explosion and without manual annotations or crash consistency checkers. To detect correctness bugs, Witcher automatically infers likely correctness conditions by analyzing data and control dependencies between NVM accesses. Then Witcher validates if any violation of them is a true crash consistency bug by checking output equivalence between executions with and without a crash. Moreover, Witcher detects performance bugs by analyzing the execution traces. Evaluation with 20 NVM key-value stores based on Intel's PMDK library shows that Witcher discovers 47 (36 new) correctness consistency bugs and 158 (113 new) performance bugs in both applications and PMDK.

AB - The advent of non-volatile main memory (NVM) enables the development of crash-consistent software without paying storage stack overhead. However, building a correct crash-consistent program remains very challenging in the presence of a volatile cache. This paper presents Witcher, a systematic crash consistency testing framework, which detects both correctness and performance bugs in NVM-based persistent key-value stores and underlying NVM libraries, without test space explosion and without manual annotations or crash consistency checkers. To detect correctness bugs, Witcher automatically infers likely correctness conditions by analyzing data and control dependencies between NVM accesses. Then Witcher validates if any violation of them is a true crash consistency bug by checking output equivalence between executions with and without a crash. Moreover, Witcher detects performance bugs by analyzing the execution traces. Evaluation with 20 NVM key-value stores based on Intel's PMDK library shows that Witcher discovers 47 (36 new) correctness consistency bugs and 158 (113 new) performance bugs in both applications and PMDK.

KW - Crash Consistency

KW - Debugging

KW - Non-volatile Memory

KW - Testing

UR - https://www.scopus.com/pages/publications/85119096778

U2 - 10.1145/3477132.3483556

DO - 10.1145/3477132.3483556

M3 - Conference contribution

AN - SCOPUS:85119096778

T3 - SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles

SP - 100

EP - 115

BT - SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles

PB - Association for Computing Machinery, Inc

Y2 - 26 October 2021 through 29 October 2021

ER -

Fu X, Kim WH, Shreepathi AP, Ismail M, Wadkar S, Lee D et al. Witcher: Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores. In SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles. Association for Computing Machinery, Inc. 2021. p. 100-115. (SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles). doi: 10.1145/3477132.3483556

Witcher: Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this