一句话：提出 ByzzFuzz，通过小范围消息变异注入网络与进程故障，随机化测试拜占庭容错算法实现并发现多个真实缺陷。
拜占庭容错（BFT）算法理论上能在部分进程任意偏离时保证一致性，但协议设计与实现缺陷仍会导致实际错误。本文提出 ByzzFuzz，一种简单而有效的随机化测试方法，通过向执行中注入随机生成的网络与进程故障来检测容错错误。为有效探索进程故障空间，ByzzFuzz 引入小范围消息变异：对协议消息内容做微小改动，如按值修改（如递增轮次编号）或按时间修改（如重复此前消息中的提案值）。结合测试与 fuzzing 文献的经验，该方法能揭示真实系统中的协议逻辑与实现缺陷。作者实现并测试了 Tendermint、Ripple 的生产实现及 PBFT 实现，发现 PBFT 中多个 bug、Tendermint 的潜在活性违规、Ripple XRP Ledger 共识算法中两个理论已知漏洞，以及一个此前未知、已被开发者确认并修复的容错 bug。
Byzantine fault-tolerant algorithms promise agreement on a correct value, even if a subset of processes can deviate from the algorithm arbitrarily. While these algorithms provide strong guarantees in theory, in practice, protocol bugs and implementation mistakes may still cause them to go wrong. This paper introduces ByzzFuzz, a simple yet effective method for automatically finding errors in implementations of Byzantine fault-tolerant algorithms through randomized testing. ByzzFuzz detects fault-tolerance bugs by injecting randomly generated network and process faults into their executions. To navigate the space of possible process faults, ByzzFuzz introduces small-scope message mutations which mutate the contents of the protocol messages by applying small changes to the original message either in value (e.g., by incrementing the round number) or in time (e.g., by repeating a proposal value from a previous message). We find that small-scope mutations, combined with insights from the testing and fuzzing literature, are effective at uncovering protocol logic and implementation bugs in real-world fault-tolerant systems.We implemented ByzzFuzz and applied it to test the production implementations of two popular blockchain systems, Tendermint and Ripple, and an implementation of the seminal PBFT protocol. ByzzFuzz detected several bugs in the implementation of PBFT, a potential liveness violation in Tendermint, and materialized two theoretically described vulnerabilities in Ripple’s XRP Ledger Consensus Algorithm. Moreover, we discovered a previously unknown fault-tolerance bug in the production implementation of Ripple, which is confirmed by the developers and fixed.
@article{paperbot2029,
title = {Randomized Testing of Byzantine Fault Tolerant Algorithms},
author = {Levin N. Winter and Florena Buse and Daan de Graaf and Klaus von Gleissenthall and Burcu Kulahcioglu Ozkan},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA1},
year = {2023},
doi = {10.1145/3586053}
}