Model checking for symbolic-heap separation logic with inductive predicates
Model checking for symbolic-heap separation logic with inductive predicates
复制标题
DOI：
10.1145/2837614.2837621
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
J. Brotherston;Nikos Gorogiannis;M. Kanovich;R. Rowe
中科院分区：
文献类型：
--
作者：
J. Brotherston;Nikos Gorogiannis;M. Kanovich;R. Rowe
我们研究了使用用户定义的归纳谓词的符号间隔逻辑的 *模型检查 *问题，即检查给定的堆栈内存状态是否满足该语言的给定公式，例如。在软件测试或运行时验证中。首先，我们证明问题是 *可决定的 *;具体而言，我们提出了一种自下而上的固定点算法，该算法决定问题并在问题实例的大小中以指数时间运行。其次，我们表明，尽管对完整语言的模型进行了指示，但当我们对定义电感谓词的架构施加自然的语法限制时，问题就会变得NP完整或ptime溶剂。我们还为这些受限片段提供了NP和PTIME算法。最后，我们报告了程序的实验性能，内容涉及从程序中提取的各种规格，进行多种句法限制组合。
We investigate the *model checking* problem for symbolic-heap separation logic with user-defined inductive predicates, i.e., the problem of checking that a given stack-heap memory state satisfies a given formula in this language, as arises e.g. in software testing or runtime verification. First, we show that the problem is *decidable*; specifically, we present a bottom-up fixed point algorithm that decides the problem and runs in exponential time in the size of the problem instance. Second, we show that, while model checking for the full language is EXPTIME-complete, the problem becomes NP-complete or PTIME-solvable when we impose natural syntactic restrictions on the schemata defining the inductive predicates. We additionally present NP and PTIME algorithms for these restricted fragments. Finally, we report on the experimental performance of our procedures on a variety of specifications extracted from programs, exercising multiple combinations of syntactic restrictions.