使用 Apalache 对 Ben-Or 的拜占庭共识的安全性进行模型检查

主要观点:作者用 TLA+ 规范并通过 Apalache 模型检查 Ben-Or 的拜占庭共识协议,在不同情况下进行实验,包括正确行为、存在故障、检查一致性等,并介绍了多种技术如随机符号执行、归纳不变量等,还对比了不同技术的效果和特点。
关键信息

  • 协议参数包括总进程数 N、故障进程上限 T、实际故障进程数 F 等,还定义了各种类型和变量。
  • 规范了协议的初始状态、各步骤行为,包括发送接收消息、计数等操作。
  • 分别检查了无故障行为、存在故障时的行为,以及一致性等性质。
  • 介绍随机符号执行和归纳不变量技术,后者需大量工作但能保证无界执行的安全性。
    重要细节
  • Apalache 输出函数的表示方式,如 SetAsFun(S)
  • 对各种定义和操作的注释说明,如 Senders1Senders2 的定义考虑到集合大小和效率。
  • 不同实例下检查协议的结果,如坏实例能找到违反一致性的反例,好实例在一定长度内未找到但增加长度后仍需大量时间。
  • 随机符号执行的实现方式和特点,如无限并行化、可处理大量运行等,以及遇到死锁的情况和解决方法。
  • 归纳不变量的发现过程和具体的不变量形式,如包含多个引理的 IndInv
阅读 25
0 条评论