FastVer2: A Provably Correct Monitor for Concurrent, Key-Value Stores - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

FastVer2: A Provably Correct Monitor for Concurrent, Key-Value Stores

Résumé

FastVer is a protocol that uses a variety of memory-checking techniques to monitor the integrity of key-value stores with only a modest runtime cost. Arasu et al. formalize the high-level design of FastVer in the F* proof assistant and prove it correct. However, their formalization did not yield a provably correct implementation---FastVer is implemented in unverified C++ code. In this work, we present FastVer2, a low-level, concurrent implementation of FastVer in Steel, an F* DSL based on concurrent separation logic that produces C code, and prove it correct with respect to FastVer's high-level specification. Our proof is the first end-to-end system proven using Steel, and in doing so we contribute new ghost-state constructions for reasoning about monotonic state. Our proof also uncovered a few bugs in the implementation of FastVer. We evaluate FastVer2 by comparing it against FastVer. Although our verified monitor is slower in absolute terms than the unverified code, its performance also scales linearly with the number of cores, yielding a throughput of more that 10M op/sec. We identify several opportunities for performance improvement, and expect to address these in the future.
Fichier principal
Vignette du fichier
fastver2.pdf (664.3 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04104143 , version 1 (25-05-2023)

Identifiants

Citer

Arvind Arasu, Tahina Ramananandro, Aseem Rastogi, Nikhil Swamy, Aymeric Fromherz, et al.. FastVer2: A Provably Correct Monitor for Concurrent, Key-Value Stores. CPP '23 - 12th ACM SIGPLAN International Conference on Certified Programs and Proofs, Jan 2023, Boston (MA), United States. pp.30-46, ⟨10.1145/3573105.3575687⟩. ⟨hal-04104143⟩

Collections

INRIA INRIA2
28 Consultations
19 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More