Certifying the synthesis of heap-manipulating programs
Certifying the synthesis of heap-manipulating programs
复制标题
验证堆操作程序的综合
DOI：
10.1145/3473589
复制
发表时间：
2021
影响因子：
--
通讯作者：
Sergey, Ilya
中科院分区：
文献类型：
--
作者：
Watanabe, Yasunari;Gopinathan, Kiran;Pîrlea, George;Polikarpova, Nadia;Sergey, Ilya
自动演绎程序合成承诺从简洁的规范生成可执行程序，沿着可以使用第三方工具独立验证的正确性证明。然而，试图行使这一承诺，使用现有的证明认证框架揭示了显着的差异，证明推导如何构造两个不同的目的：程序合成和程序验证。这些差异使得它很难使用认证验证验证合成结果，迫使一个写一个特设的翻译过程，从合成证明正确性证明每个验证backend.In这项工作中，我们解决这个挑战的背景下，堆操作程序的合成和验证。我们提出了一种技术的演绎综合推导（又名原则翻译。源证明）转换为关于交互式程序验证器的逻辑中的合成程序的演绎目标证明。我们展示了我们的技术，通过实现三个不同的认证程序生成的SuSLik，一个分离逻辑为基础的工具，用于自动合成程序与指针，在基础验证框架嵌入Coq：霍尔类型理论（HTT），虹膜和验证软件工具链（VST），产生简洁高效的机器可检查的证明特征合成基准。
Automated deductive program synthesis promises to generate executable programs from concise specifications, along with proofs of correctness that can be independently verified using third-party tools. However, an attempt to exercise this promise using existing proof-certification frameworks reveals significant discrepancies in how proof derivations are structured for two different purposes: program synthesis and program verification. These discrepancies make it difficult to use certified verifiers to validate synthesis results, forcing one to write an ad-hoc translation procedure from synthesis proofs to correctness proofs for each verification backend.In this work, we address this challenge in the context of the synthesis and verification of heap-manipulating programs. We present a technique for principled translation of deductive synthesis derivations (a.k.a. source proofs) into deductive target proofs about the synthesised programs in the logics of interactive program verifiers. We showcase our technique by implementing three different certifiers for programs generated via SuSLik, a Separation Logic-based tool for automated synthesis of programs with pointers, in foundational verification frameworks embedded in Coq: Hoare Type Theory (HTT), Iris, and Verified Software Toolchain (VST), producing concise and efficient machine-checkable proofs for characteristic synthesis benchmarks.
登录
查看更多内容
DOI：
10.1145/238721.238781
发表时间：
1996-10
期刊：
--
影响因子：
--
作者：
G. Necula;Peter Lee
通讯作者：
G. Necula;Peter Lee
DOI：
10.1145/3319535.3363214
发表时间：
2019-11
期刊：
Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security
影响因子：
--
作者：
C. Skalka;J. Ring;David Darais;Minseok Kwon;Sahil Gupta;Kyle I. Diller;S. Smolka;Nate Foster
通讯作者：
C. Skalka;J. Ring;David Darais;Minseok Kwon;Sahil Gupta;Kyle I. Diller;S. Smolka;Nate Foster
影响因子：
3.5
作者：
A. Chlipala;Benjamin Delaware;Samuel Duchovni;Jason Gross;Clément Pit;Sorawit Suriyakarn;Peng Wang;Katherine Q. Ye
通讯作者：
Katherine Q. Ye
DOI：
10.1145/1411204.1411237
发表时间：
2008-09
期刊：
--
影响因子：
--
作者：
Aleksandar Nanevski;Greg Morrisett;Avraham Shinnar;Paul Govereau;L. Birkedal
通讯作者：
Aleksandar Nanevski;Greg Morrisett;Avraham Shinnar;Paul Govereau;L. Birkedal
程序逻辑 - 适用于经过认证的编译器
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
Andrew W. Appel
通讯作者：
Andrew W. Appel