Inferring Simple Solutions to Recursion-free Horn Clauses via Sampling
Inferring Simple Solutions to Recursion-free Horn Clauses via Sampling
复制标题
通过采样推断无递归 Horn 子句的简单解
DOI：
10.1007/978-3-662-46681-0_10
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Tachio Terauchi.
中科院分区：
文献类型：
--
作者：
Hiroshi Unno;Tachio Terauchi.
无递归的Horn子句约束最近在验证界受到了广泛的关注。它扩展了克雷格插值，并提出作为一个统一的形式主义表示抽象细化。在抽象精化中，通常希望推断“简单”精化，并且研究人员已经研究了推断简单克雷格插值的技术。绘制的工作线上，本文提出了一种技术，用于推断简单的解决方案，递归自由霍恩子句约束。我们的贡献是一个约束求解算法，懒洋洋的样本片段的给定的约束，其解决方案空间被用来形成一个简单的解决方案。我们已经实现了一个原型的约束求解算法的验证工具，并已确认，它是能够推断出简单的解决方案，帮助验证过程。
Recursion-free Horn-clause constraints have received much recent attention in the verification community. It extends Craig interpolation, and is proposed as a unifying formalism for expressing abstraction refinement. In abstraction refinement, it is often desirable to infer “simple” refinements, and researchers have studied techniques for inferring simple Craig interpolants. Drawing on the line of work, this paper presents a technique for inferring simple solutions to recursion-free Hornclause constraints. Our contribution is a constraint solving algorithm that lazily samples fragments of the given constraints whose solution spaces are used to form a simple solution for the whole. We have implemented a prototype of the constraint solving algorithm in a verification tool, and have confirmed that it is able to infer simple solutions that aid the verification process.