go-v.orgdoi

Mechanizing the CMP Abstraction for Parameterized Verification

Yongjian Li, Bohua Zhan, Jun Pang · Proceedings of the ACM on Programming Languages · 2024

  • DOI 10.1145/3649858
  • Publisher Association for Computing Machinery
  • Type article
  • Issued 2024

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

Proceedings of the ACM on Programming Languages · Association for Computing Machinery · article · 2024

Abstract

Parameterized verification is a challenging problem that is known to be undecidable in the general case. ‍is a widely-used method for parameterized verification, originally proposed by Chou, Mannava and Park in 2004. It involves abstracting the protocol to a small fixed number of nodes, and strengthening by auxiliary invariants to refine the abstraction. In most of the existing applications of CMP, the abstraction and strengthening procedures are carried out manually, which can be tedious and error-prone. Existing theoretical justification of the ‍method is also done at a high level, without detailed descriptions of abstraction and strengthening rules.

In this paper, we present a formally verified theory of ‍in Isabelle/HOL, with detailed, syntax-directed procedure for abstraction and strengthening that is proven correct. The formalization also includes correctness of symmetry reduction and assume-guarantee reasoning. We also describe a tool AutoCMP for automatically carrying out abstraction and strengthening in , as well as generating Isabelle proof scripts showing their correctness. We applied the tool to a number of parameterized protocols, and discovered some inaccuracies in previous manual applications of ‍to the FLASH cache coherence protocol.

Open the resolved locator · 10.1145/3649858

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-19 21:58 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1145/3649858
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.