License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.46
URN: urn:nbn:de:0030-drops-148485
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14848/
Bano, Shehar ;
Sonnino, Alberto ;
Chursin, Andrey ;
Perelman, Dmitri ;
Li, Zekun ;
Ching, Avery ;
Malkhi, Dahlia
Brief Announcement: Twins – BFT Systems Made Robust
Abstract
Twins is an effective strategy for generating test scenarios with Byzantine [Lamport et al., 1982] nodes in order to find flaws in Byzantine Fault Tolerant (BFT) systems. Twins finds flaws in the design or implementation of BFT protocols that may cause correctness issues. The main idea of Twins is the following: running twin instances of a node that use correct, unmodified code and share the same network identity and credentials allows to emulate most interesting Byzantine behaviors. Because a twin executes normal, unmodified node code, building Twins only requires a thin wrapper over an existing distributed system designed for Byzantine tolerance. To emulate material, interesting scenarios with Byzantine nodes, it instantiates one or more twin copies of the node, giving the twins the same identities and network credentials as the original node. To the rest of the system, the node and all its twins appear indistinguishable from a single node behaving in a "questionable" manner. This approach generates many interesting Byzantine behaviors, including equivocation, double voting, and losing internal state, while forgoing uninteresting behavior scenarios that can be filtered at the transport layer, such as producing semantically invalid messages.
Building on configurations with twin nodes, Twins systematically generates scenarios with Byzantine nodes via enumeration over protocol rounds and communication patterns among nodes. Despite this being inherently exponential, one new flaw and several known flaws were materialized by Twins in the arena of BFT consensus protocols. In all cases, protocols break within fewer than a dozen protocol rounds, hence it is realistic for the Twins approach to expose the problems. In two of these cases, it took the community more than a decade to discover protocol flaws that Twins would have surfaced within minutes. Additionally, Twins has been incorporated into the continuous release testing process of a production setting (DiemBFT) in which it can execute 44M Twins-generated scenarios daily.
BibTeX - Entry
@InProceedings{bano_et_al:LIPIcs.DISC.2021.46,
author = {Bano, Shehar and Sonnino, Alberto and Chursin, Andrey and Perelman, Dmitri and Li, Zekun and Ching, Avery and Malkhi, Dahlia},
title = {{Brief Announcement: Twins – BFT Systems Made Robust}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {46:1--46:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-210-5},
ISSN = {1868-8969},
year = {2021},
volume = {209},
editor = {Gilbert, Seth},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14848},
URN = {urn:nbn:de:0030-drops-148485},
doi = {10.4230/LIPIcs.DISC.2021.46},
annote = {Keywords: Distributed Systems, Byzantine Fault Tolerance, Real-World Deployment}
}
Keywords: |
|
Distributed Systems, Byzantine Fault Tolerance, Real-World Deployment |
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
04.10.2021 |