SHF: Small: Integrating separation logic and SMT for better heap verification

SHF：小型：集成分离逻辑和 SMT 以实现更好的堆验证

• 批准号: 1320583
• 负责人: Thomas Wies
• 金额: $ 50万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320583&HistoricalAwards=false
• 关键词: SHF; Small; Integrating; separation; logic

Heap-allocated pointer structures are a common source of software errors. In particular, pointer safety errors, like memory leaks and dereferencing null or dangling pointers, often cause programs to fail or leave them vulnerable to be exploited by malware. Tools that are able to detect such errors at compile time have long been considered impractical because they scale badly to large programs. This has started to change recently with the advent of verification tools based on separation logic (SL), which scale to software components of industrial size. The aim of this project is to increase the degree of automation, precision, and soundness of today's SL-based verification tools and broaden the scope of tools that could use separation logic. Because heap-allocated data structures are among the most difficult software constructs to reason about, this work has the potential to make a significant impact on the reliability of software.SL-based tools depend on theorem provers for separation logic to automatically discharge proof obligations concerned with properties about pointer structures. Today's tools implement tailor-made provers for this task. However, the analysis of real-world programs involves reasoning about other data types including, for instance, integers, arrays, and bit-vectors. To cope with this, existing separation logic tools make simplifying (and in general unsound) assumptions, rely on interactive help from the user, or implement ad-hoc and incomplete extensions of their tailor-made provers. The PIs will investigate a more systematic approach towards combined reasoning about heap and other data types by integrating an SL theorem prover into a satisfiability modulo theories (SMT) solver. This research is motivated by the observation that reasoning about separation logic fragments can be reduced entirely to reasoning in decidable first-order theories that fit well into the SMT framework. Modern SMT solvers implement decision procedures for many first-order theories that are relevant in program verification, such as linear arithmetic, arrays, and bit-vectors. A reduction to first-order logic enables a seamless combination of separation logic with these theories. Moreover, SMT solvers are already an integral part in the tool chain of many existing verification tools. These tools could directly benefit from an integrated SL prover. In addition, we expect that specific capabilities added to the SMT solver as a result of the project will be useful to a broad set of SMT users.

堆分配的指针结构是软件错误的常见来源。特别是，指针安全错误，例如内存泄漏和删除无效的指针或悬空指针，通常会导致程序失败或使其容易受到恶意软件的利用。 能够在编译时间检测到此类错误的工具长期以来一直被认为是不切实际的，因为它们的扩展很差在大型程序上。 基于分离逻辑（SL）的验证工具的出现，最近开始改变这种情况，该工具扩展到工业大小的软件组件。 该项目的目的是提高当今基于SL的验证工具的自动化程度，精度和健全性，并扩大可以使用分离逻辑的工具范围。由于由堆分配的数据结构是最困难的软件构造之一，因此这项工作有可能对软件的可靠性产生重大影响。基于SLS的工具依赖于定理的抛光剂来使分离逻辑以自动放电证明与涉及指针结构有关的属性的证明义务。当今的工具为此任务实施量身定制的掠夺。但是，对现实世界程序的分析涉及对其他数据类型进行推理，例如，整数，数组和比特矢量。为了应对这一点，现有的分离逻辑工具可以简化（并且总的来说）假设，依靠用户的交互式帮助，或实现其量身定制的抛弃者的临时和不完整的扩展。 PI将通过将SL定理供款集成到满足性模量理论（SMT）求解器中，研究一种更系统的方法来结合有关堆和其他数据类型的合并推理。这项研究的激励是，观察到有关分离逻辑片段的推理可以完全减少到适合SMT框架中的可决定的一阶理论中的推理。现代SMT求解器针对许多与程序验证相关的一阶理论实施决策程序，例如线性算术，阵列和位向量。一阶逻辑的减少可以使分离逻辑与这些理论的无缝组合。此外，SMT求解器已经在许多现有验证工具的工具链中不可或缺。这些工具可以直接受益于集成的SL供体。此外，我们预计该项目的导致SMT求解器添加的特定功能将对大量的SMT用户有用。