Randomized Testing of Byzantine Fault Tolerant Algorithms

Levin N. Winter, Florena Buşe, Daan de Graaf, Klaus von Gleissenthall, Burcu Kulahcioglu Ozkan

Research output: Contribution to journalArticleScientificpeer-review

104 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number101
Pages (from-to)757-788
Number of pages32
JournalPACMPL
Volume7
Issue numberOOPSLA(1)
DOIs
Publication statusPublished - 2023

Keywords

  • Distributed consensus
  • Byzantine fault-tolerance
  • Random testing

Fingerprint

Dive into the research topics of 'Randomized Testing of Byzantine Fault Tolerant Algorithms'. Together they form a unique fingerprint.
  • Distinguished Paper Award at OOPSLA'23

    Winter, Levin N. (Recipient), Buşe, Florena (Recipient), de Graaf, Daan (Recipient), von Gleissenthall, Klaus (Recipient) & Özkan, B. (Recipient), 2023

    Prize: Prize (including medals and awards)

    File
  • Ripple Bug Bounty Program Award

    Winter, Levin N. (Recipient), Buşe, Florena (Recipient) & Özkan, B. (Recipient), 2023

    Prize: Prize (including medals and awards)

Cite this