基于TLA+形式化规约的Raft系统测试
DOI:
作者:
作者单位:

中国科学院软件研究所

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金项目(面上项目,重点项目,重大项目)


Testing Raft Systems Based on TLA+ Formal Specification
Author:
Affiliation:

Fund Project:

The National Natural Science Foundation of China (General Program, Key Program, Major Research Plan)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    Raft是最为流行的分布式共识协议之一.自2014年被提出以来,Raft协议及其变体在各种分布式系统中被广泛应用.为了证明Raft协议的正确性,开发者使用TLA+形式化规约对协议设计进行了建模和验证.但由于抽象的形式化规约与实际的系统实现源码间存在鸿沟,实现Raft协议的分布式系统中仍然会违背协议设计并引入复杂的缺陷.本文设计了基于TLA+形式化规约的测试方法来检测Raft系统中的缺陷.具体而言,我们将形式化规约匹配到相应的Raft系统实现,并用形式化规约所定义的状态空间来指导Raft系统的测试过程.为了评估该方法的可行性和有效性,我们针对两个不同的Raft系统进行了系统化测试,并发现了3个未知缺陷.

    Abstract:

    Raft is one of the most popular distributed consensus protocols. Since it was proposed in 2014, Raft and its variants have been widely used in different kinds of distributed systems. To prove the correctness of the Raft protocol, developers use the TLA+ formal specification to model and verify its design. However, due to the gap between the abstract formal specification and its practical implementation, distributed systems that implement the Raft protocol (i.e., Raft systems) can still violate the protocol design and introduce intricate bugs. In this paper, we propose a novel testing technique based on TLA+ formal specification to unearth bugs in Raft systems. To be specific, we map Raft’s formal specification to the corresponding Raft system, and then use the specification-defined state space to guide the testing in the Raft system. To evaluate the feasibility and effectiveness of our approach, we apply it on two different Raft systems, and find 3 previously-unknown bugs.

    参考文献
    相似文献
    引证文献
引用本文
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2022-12-12
  • 最后修改日期:2023-06-28
  • 录用日期:2023-10-19
  • 在线发布日期:
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号