Towards Automatic Inference of Inductive Invariants
Towards Automatic Inference of Inductive Invariants
复制标题
走向归纳不变量的自动推理
DOI：
10.1145/3317550.3321451
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Sakallah, Karem A.
中科院分区：
文献类型：
--
作者：
Ma, Haojun;Goel, Aman;Jeannin, Jean-Baptiste;Kapritsos, Manos;Kasikci, Baris;Sakallah, Karem A.
众所周知，分布式系统很难正确设计和实现。形式验证提供了正确性证明，并已成功地应用于各种分布式系统。一个典型的形式验证的核心是一个计算机检查的证明与归纳不变。找到这个归纳不变是最困难的部分的证明：一部分，目前由开发人员手动进行，是负责与正式verified.In本文中，我们提出了一种新的方法：增量推理的归纳不变（I4），自动生成归纳不变的分布式协议。我们从一个简单的想法开始：协议的有限实例的归纳不变量必须是无限分布式协议的一般归纳不变量的实例。在I4中，我们实例化一个有限的协议实例，计算出这个实例的有限归纳不变量，然后计算出作为有限不变量的推广的一般归纳不变量。我们的实验表明，I4可以用最少的人力完成几个系统的正确性的一般证明。
Distributed systems are notoriously difficult to design and implement correctly. Formal verification provides correctness proofs, and has recently been successfully applied to various distributed systems. At the heart of a typical formal verification is a computer-checked proof with an inductive invariant. Finding this inductive invariant is the hardest part of the proof: a part that is currently undertaken manually by the developer and is responsible for most of the effort associated with formal verification.In this paper, we present a new approach: Incremental Inference of Inductive Invariants (I4), to automatically generate inductive invariants for distributed protocols. We start from a simple idea: the inductive invariant of a finite instance of the protocol must be an instance of a general inductive invariant for the infinite distributed protocol. In I4, we instantiate a finite instance of the protocol, work out the finite inductive invariant of this instance, then figure out the general inductive invariant as a generalization of the finite invariant. Our experiments show that I4 can finish the general proof of correctness of several systems with minimal human effort.
登录
查看更多内容
Verilog RTL 设计中基于 IC3 的模型检查技术的实证评估
DOI：
--
发表时间：
2019
期刊：
Design, Automation and Test in Europe
影响因子：
--
作者：
Aman Goel;K. Sakallah
通讯作者：
K. Sakallah
影响因子：
22.7
作者：
LIPTON, RJ
通讯作者：
LIPTON, RJ
通用不变量的属性导向推理或证明它们的不存在
DOI：
--
发表时间：
2015
期刊：
International Conference on Computer Aided Verification
影响因子：
--
作者：
Aleksandr Karbyshev;Nikolaj S. Bjørner;Shachar Itzhaky;N. Rinetzky;Sharon Shoham
通讯作者：
Sharon Shoham
使用具有语法引导抽象的 IC3 对 Verilog RTL 进行模型检查
影响因子：
7.4
作者：
Aman Goel;K. Sakallah
通讯作者：
K. Sakallah