Mutation in Linked Data Structures
Mutation in Linked Data Structures
复制标题
链接数据结构中的突变
DOI：
10.1007/978-3-642-24559-6_20
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Andrew Ireland
中科院分区：
文献类型：
--
作者：
E. Maclean;Andrew Ireland
开发了分离逻辑作为Hoare逻辑的扩展，目的是简化指针程序证明。逻辑的一个关键特征是，它将推理工作的重点放在与程序相关的堆的那些部分（所谓的本地推理）上。基于本地推理的基础是分开的连词和分离含义操作员。在这里，我们提出了一种称为突变的自动推理技术，该技术为分离逻辑证明提供指导。具体而言，鉴于在分离逻辑中指定的两个堆结构，突变尝试使用差减少策略来构建等效性。该策略的关键是一种广义分解操作员，在与堆结构匹配时至关重要。我们展示了突变如何提供有效的策略来证明在最弱的前提分析的背景下迭代和递归程序的功能正确性。当前，在我们的核心程序验证系统中将突变作为证明计划实施。 Core将形状分析的结果与我们在不变生成和证明计划方面的工作结合在一起。我们在核心系统的背景下提出了突变的结果。
Separation logic was developed as an extension to Hoare logic with the aim of simplifying pointer program proofs. A key feature of the logic is that it focuses the reasoning effort on only those parts of the heap that are relevant to a program - so called local reasoning. Underpinning this local reasoning are the separating conjunction and separating implication operators. Here we present an automated reasoning technique called mutation that provides guidance for separation logic proofs. Specifically, given two heap structures specified within separation logic, mutation attempts to construct an equivalence proof using a difference reduction strategy. Pivotal to this strategy is a generalised decomposition operator which is essential when matching heap structures. We show how mutation provides an effective strategy for proving the functional correctness of iterative and recursive programs within the context of weakest precondition analysis. Currently, mutation is implemented as a proof plan within our CORE program verification system. CORE combines results from shape analysis with our work on invariant generation and proof planning. We present our results for mutation within the context of the CORE system.
CORE系统：指针程序的动画和功能正确性
DOI：
10.1109/ase.2011.6100132
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Maclean E
通讯作者：
Maclean E
具有分离逻辑的摊销资源分析
影响因子：
0.6
作者：
Atkey R
通讯作者：
Atkey R