paperbot · PL 论文追踪

全部论文 待读 收藏

P2 CEGAR-PT: A Tool for Abstraction by Program Transformation

CEGAR-PT:一种通过程序变换进行抽象的工具
ASE 2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE)2023匹配度 3/10 · 该论文属于程序验证与抽象解释工具(CEGAR、程序变换),与静态分析/形式化验证方向相邻,但完全没有涉及 LLM/Agent、浮点程序分析或贝叶斯程序分析等用户核心交叉方向。引用 3 inbox
Dirk Beyer, Marian Lingsch-Rosenfeld, Martin Spiessl
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:将抽象实现为程序变换,用 CEGAR 调节精度,并复用现成验证组件。

程序正确性证明常依赖抽象,但现有抽象实现难以复用与组合,成功技术往往需在新工具中反复重写。本文提出工具 CEGAR-PT,将抽象视为程序变换,并在不修改现有验证组件实现的前提下,把不同的现成验证组件集成起来,同时沿用 CEGAR 方法调节抽象精度。其抽象具有较强通用性:给定定义抽象层次的精度,只需将程序变换为另一程序;变换可对数据流做上近似(如 havoc 变量、使用更抽象类型),也可对控制流做上近似(如循环抽象、切片)。作者通过演示视频展示该工具。

问题
如何复用和组合不同验证组件中的抽象实现,避免成功的抽象技术在新工具中反复重实现。
方法
CEGAR-PT 将抽象建模为程序变换,给定精度将程序转换为另一程序,并用 CEGAR 调节精度,集成现成验证组件而不改其实现。
评估
通过演示视频展示工具的工作流程,并说明其可对数据流与控制流进行上近似抽象。
原文摘要(Abstract)

Abstraction is an important approach for proving the correctness of computer programs. There are many implementations of this approach available, but unfortunately, the various implementations are difficult to reuse and combine, and the successful techniques have to be re-implemented in new tools again and again. We address this problem by contributing the tool cegar-pt, which views abstraction as program transformation and integrates different verification components off-the-shelf. The idea is to use existing components without having to change their implementation, while still adjusting the precision of the abstraction using the successful CEGAR approach. The approach of cegar-pt is largely general: It only restricts the abstraction to transform, given a precision that defines the level of abstraction, one program into another program. The abstraction by program transformation can over-approximate the data flow (e.g., havoc some variables, use more abstract types) or the control flow (e.g., loop abstraction, slicing). To illustrate our tool, we provide a demonstration video, accessible at https://youtu.be/ASZ6hoq8asE.

链接与引用

DOI 原文 · PDF(开放获取) · DBLP

BibTeX
@inproceedings{BeyerRS23,
  title = {CEGAR-PT: A Tool for Abstraction by Program Transformation},
  author = {Dirk Beyer and Marian Lingsch-Rosenfeld and Martin Spiessl},
  booktitle = {ASE},
  year = {2023},
  doi = {10.1109/ase56229.2023.00215}
}