Automatic cyclic termination proofs for recursive procedures in separation logic
Automatic cyclic termination proofs for recursive procedures in separation logic
复制标题
DOI：
10.1145/3018610.3018623
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
R. Rowe;J. Brotherston
中科院分区：
文献类型：
--
作者：
R. Rowe;J. Brotherston
我们描述了一个正式的验证框架和工具实现，循环证明的基础上，证明安全终止的命令式指针程序与递归过程。我们的断言是符号堆分离逻辑与用户定义的归纳谓词，我们采用显式近似这些谓词作为我们的终止措施。这使我们能够扩展循环证明程序与程序相关的这些措施的前，后条件的过程调用。我们提供了一个实现我们的形式证明系统中的循环定理证明框架，并评估其性能的范围内的例子从文献中的程序终止。我们的实现扩展了目前最先进的循环证明为基础的程序验证，使自动终止证明的一组更大的程序比以前可能的。
We describe a formal verification framework and tool implementation, based upon cyclic proofs, for certifying the safe termination of imperative pointer programs with recursive procedures. Our assertions are symbolic heaps in separation logic with user defined inductive predicates; we employ explicit approximations of these predicates as our termination measures. This enables us to extend cyclic proof to programs with procedures by relating these measures across the pre- and postconditions of procedure calls. We provide an implementation of our formal proof system in the Cyclist theorem proving framework, and evaluate its performance on a range of examples drawn from the literature on program termination. Our implementation extends the current state-of-the-art in cyclic proof-based program verification, enabling automatic termination proofs of a larger set of programs than previously possible.