基于TLA+形式化规约的Raft协议测试
作者:
作者单位:

作者简介:

王栋(1996-), 男, 博士生, CCF学生会员, 主要研究领域为分布式系统测试, 形式化方法. ;窦文生(1984-), 男, 博士, 研究员, 博士生导师, CCF专业会员, 主要研究领域为软件工程, 分布式系统测试, 数据库测试. ;高钰(1992-), 女, 博士, CCF专业会员, 主要研究领域为软件工程, 系统测试, 系统可靠性. ;吴陈傲(1998-), 男, 硕士, 主要研究领域为形式化方法. ;魏峻(1970-), 男, 博士, 研究员, 博士生导师, CCF高级会员, 主要研究领域为软件工程, 网络分布式计算. ;黄涛(1965-), 男, 博士, 研究员, 博士生导师, CCF高级会员, 主要研究领域为网络分布式计算, 软件工程.

通讯作者:

窦文生, E-mail: wensheng@iscas.ac.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(62072444, 62302493); 国家自然科学基金联合基金(U20A6003)


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

Fund Project:

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

    Raft是最为流行的分布式共识协议之一. 自2014年被提出以来, Raft协议及其变体在各种分布式系统中被广泛应用. 为了证明Raft协议的正确性, 开发者使用TLA+形式化规约对协议设计进行了建模和验证. 但由于抽象的形式化规约与实际的系统实现源码间存在鸿沟, 基于Raft实现的分布式系统中仍然会违背协议设计并引入复杂的缺陷. 设计基于TLA+形式化规约的测试方法来检测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 practical implementation, distributed systems that implement the Raft protocol can still violate the protocol design and introduce intricate bugs. This study proposes a novel testing technique based on TLA+ formal specification to unearth bugs in Raft implementations. To be specific, the study maps the formal specification to the corresponding system implementation and then uses the specification-defined state space to guide the testing in the implementations. To evaluate the feasibility and effectiveness of the proposed approach, the study applies it on two different Raft implementations and finds 3 previously unknown bugs.

    参考文献
    相似文献
    引证文献
引用本文

王栋,窦文生,高钰,吴陈傲,魏峻,黄涛.基于TLA+形式化规约的Raft协议测试.软件学报,2024,35(12):5363-5381

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

京公网安备 11040202500063号