Gradual verification of recursive heap data structures
Gradual verification of recursive heap data structures
复制标题
递归堆数据结构的逐步验证
DOI：
10.1145/3428296
复制
发表时间：
2020
影响因子：
--
通讯作者：
Sunshine, Joshua
中科院分区：
文献类型：
--
作者：
Wise, Jenna;Bader, Johannes;Wong, Cameron;Aldrich, Jonathan;Tanter, Éric;Sunshine, Joshua
当前的静态验证技术没有为增量提供良好的支持，这使得开发人员很难专注于指定和验证最重要的属性和组件。动态验证方法支持增量，但不能提供静态保证。为了弥补这一差距，以前的工作提出了渐进式验证，它通过允许每个断言是完整的，部分的或省略的来支持增量，并提供从动态到静态检查平滑扩展的可靠验证。然而，以前的逐步验证方法仅限于没有递归数据结构的程序。本文将逐步验证扩展到在堆上操作递归、可变数据结构的程序。我们解决了几个技术挑战，如语义连接等和等递归的抽象谓词的解释，并支持堆所有权的逐步验证。因此，这项工作奠定了基础，未来的工具，工作在现实的程序和支持验证的工程过程中，成本效益的权衡可以。
Current static verification techniques do not provide good support for incrementality, making it difficult for developers to focus on specifying and verifying the properties and components that are most important. Dynamic verification approaches support incrementality, but cannot provide static guarantees. To bridge this gap, prior work proposed gradual verification, which supports incrementality by allowing every assertion to be complete, partial, or omitted, and provides sound verification that smoothly scales from dynamic to static checking. The prior approach to gradual verification, however, was limited to programs without recursive data structures. This paper extends gradual verification to programs that manipulate recursive, mutable data structures on the heap. We address several technical challenges, such as semantically connecting iso- and equi-recursive interpretations of abstract predicates, and supporting gradual verification of heap ownership. This work thus lays the foundation for future tools that work on realistic programs and support verification within an engineering process in which cost-benefit trade-offs can be made.
登录
查看更多内容
影响因子：
3.6
作者：
Alexander J. Summers;S. Drossopoulou
通讯作者：
S. Drossopoulou
DOI：
10.1007/978-3-540-73589-2_2
发表时间：
2007-07
期刊：
--
影响因子：
--
作者：
Jeremy G. Siek;Walid Taha
通讯作者：
Jeremy G. Siek;Walid Taha
DOI：
10.1145/3009837.3009856
发表时间：
2017-01
期刊：
Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages
影响因子：
--
作者：
Nico Lehmann;É. Tanter
通讯作者：
Nico Lehmann;É. Tanter
抽象渐进式打字
DOI：
--
发表时间：
2016
期刊：
ACM-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
Ronald Garcia;Alison M. Clark;É. Tanter
通讯作者：
É. Tanter
逐步打字的细化标准
DOI：
--
发表时间：
2015
期刊：
Summit on Advances in Programming Languages
影响因子：
--
作者：
Jeremy G. Siek;Michael M. Vitousek;M. Cimini;J. Boyland
通讯作者：
J. Boyland