Refinement Selection
Refinement Selection
复制标题
细化选择
DOI：
10.1007/978-3-319-23404-5_3
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Philipp Wendler
中科院分区：
文献类型：
--
作者：
Dirk Beyer;Stefan Löwe;Philipp Wendler
反例引导抽象精化（CEGAR）是一种面向属性的方法，用于自动构造给定系统的抽象模型。该方法从不可行的错误路径中学习信息，以改进抽象模型。我们解决的问题selectingwhich信息学习从一个给定的不可行的错误path.In以前的工作中，我们提出了一种方法thatenablesrefinement选择通过提取一组切片前缀从一个给定的不可行的错误路径，其中每一个代表一个不同的原因不可行的错误路径，因此，一种可能的方式来细化抽象模型。在这项工作中，我们（1）定义并研究了几种有前途的启发式方法，用于选择适当的细化精度，以及（2）提出了值分析和谓词分析的新组合，该分析不仅可以找出从不可行的错误路径中学习哪些信息，而且可以自动决定哪些分析应该优先进行细化。这些贡献允许一个更系统的细化战略CEGAR为基础的分析。我们评估了软件验证的想法。我们在验证框架中提供了新概念的实现 并将其公之于众在一个彻底的实验研究，我们表明，细化选择往往避免状态空间爆炸，现有的方法分歧，它可以更强大，如果应用在更高的水平，它决定哪一个组合的分析应该有利于细化。
Counterexample-guided abstraction refinement (CEGAR) is a property-directed approach for the automatic construction of an abstract model for a given system. The approach learns information from infeasible error paths in order to refine the abstract model. We address the problem of selectingwhichinformation to learn from a given infeasible error path. In previous work, we presented a method thatenablesrefinement selection by extracting a set of sliced prefixes from a given infeasible error path, each of which represents a different reason for infeasibility of the error path and thus, a possible way to refine the abstract model. In this work, we (1) define and investigate several promising heuristics for selecting an appropriate precision for refinement, and (2) propose a new combination of a value analysis and a predicate analysis that does not only find outwhich informationto learn from an infeasible error path, but automatically decideswhich analysisshould be preferred for a refinement. These contributions allow a more systematic refinement strategy for CEGAR-based analyses. We evaluated the idea on software verification. We provide an implementation of the new concepts in the verification framework and make it publicly available. In a thorough experimental study, we show that refinement selection often avoids state-space explosion where existing approaches diverge, and that it can be even more powerful if applied on a higher level, where it decides which analysis of a combination should be favored for a refinement.