Lune

OOPSLA2024Top-tier venue

Mechanizing the CMP Abstraction for Parameterized Verification

Yongjian Li, Bohua Zhan, Jun Pang

Abstract

Parameterized verification is a challenging problem that is known to be undecidable in the general case. CMP 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 CMP 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 CMP 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 CMP, 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 CMP to the FLASH cache coherence protocol.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Formalising CXL Cache CoherenceChengsong Tan, Alastair F. Donaldson, John WickersonASPLOS 2025 · 12 citations
  2. Hemiola: A DSL and Verification Tools to Guide Design and Proof of Hierarchical Cache-Coherence ProtocolsJoonwon Choi, Adam Chlipala, ArvindCAV 2022 · 9 citations
  3. Complete Local Reasoning About Parameterized Programs Over TopologiesRuotong Cheng, Azadeh FarzanCAV 2026
  4. A Formally Verified IEEE 754 Floating-Point Implementation of Interval Iteration for MDPsBram Kohlen, Maximilian Schäffeler, Mohammad Abdulaziz, Arnd Hartmanns et al.CAV 2025 · 6 citations
  5. Commutativity Simplifies Proofs of Parameterized ProgramsAzadeh Farzan, Dominik Klumpp, Andreas PodelskiPOPL 2024 · 11 citations
Dusk over the sea between two cliffs drawn in fine vertical lines