Automated Channel Fault Analysis with Tofu

Jacob Ginesin, Max von Hippel, Cristina Nita-Rotaru · 2026

Read Automated Channel Fault Analysis with Tofu by Jacob Ginesin, Max von Hippel, Cristina Nita-Rotaru (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-01721.txt.

Introduction

Jacob Ginesin, Max von Hippel, and Cristina Nita-Rotaru automate the hunt for attacks that live in the wires between machines. Distributed protocols assume channels can insert, drop, replay, or reorder messages, yet verification projects each hand-roll their own fault model and prove safety against that alone.

Their tool, Tofu, flips the workflow. Given a protocol stated in linear temporal logic, it searches the whole state space for channel-fault attack traces, synthesizing a concrete attack when one exists and certifying absence when the search exhausts. The analysis is claimed sound and complete against its stated fault model, and general across protocols rather than tuned per case. TCP, the transport workhorse of the internet, serves as the demonstration target. The authors frame automatic fault analysis as a missing routine step for protocol design.

Catalog record

CREATORJacob Ginesin, Max von Hippel, Cristina Nita-Rotaru
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.01721

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Automated Channel Fault Analysis with Tofu Jacob Ginesin, Max von Hippel, Cristina Nita-Rotaru Abstract Distributed protocols are the linchpin of the modern internet, underpinning every internet service. This has in turn motivated a massive body of research ensuring the security, reliability, and performance of distributed protocols. In these works, a wide-ranging assumption is that distributed protocols operate over faulty or attacker-controlled channels, where messages can be arbitrarily inserted, dropped, replayed, or reordered. Formal verification work targeting distributed protocols typically defines its own notion of faulty or malicious channels, then constructively proves their protocol is correct with respect to it. In this work we take a fundamentally different approach: we develop a rigorous methodology for automatically conducting channel fault analysis on distributed protocols, and we introduce Tofu , a generalizable tool that implements our methodology. Tofu provides sound, complete analysis, synthesizing channel fault-based attack traces on arbitrary linear temporal logic (LTL) protocol specifications or proving the absence of such through an exhaustive state-space search. We demonstrate the applicability of Tofu by employing it to study TCP. 1 Introduction Distributed protocols are the linchpin of the modern internet, representing the fundamental communication and coordination backbone of all modern services built on top of it. The vast importance of distributed protocols has motivated ample research in ensuring their security, reliability, and performance. In practice, the communication channels between distributed protocol endpoints are imperfect: messages can be dropped due to network congestion, replayed by adversaries, or reordered due to multi-path routing. These channel-level faults are a source of subtle bugs, denial-of-service vulnerabilities, and safety violations in distributed systems. Despite this, the landscape of tools for systematically analyzing channel faults remains fragmented and largely manual. On the practical side, several tools exist for testing network protocol implementations under adverse channels. Scapy [ 2 ] is a Python-based packet manipulation library enabling users to forge, send, and capture arbitrary network packets, Linux netem [ 10 ] provides kernel-level network emulation, PacketDrill [ 5 ] supports testing of TCP/UDP/IP implementations through injecting precisely-timed packet sequences, and TCP-Fuzz supports randomized testing and fuzzing approaches. These tools are invaluable in practice but share a fundamental limitation: they provide no completeness guarantees. That is, when these tools terminate without finding a bug, the user cannot conclude the absence of bugs. On the formal methods side, there has been significant work verifying distributed protocols under faulty communication channels, with the caveat that the capabilities of the attacker must be manually defined. von Hippel et al. presented an automated attack synthesis framework targeting communication channels for distributed systems, supporting an attacker that may only arbitrarily insert messages onto the victim channel [ 22 ] . This attack synthesis framework was later used to analyze the Stream Control Transmission Protocol, where Ginesin et al. modeled different types of attackers by specifying exact message types the different attackers may insert onto the channel [ 8 ] . Raft has been verified using mechanized proof assistants such as Rocq via the Verdi framework [ 24 ] , and Paxos has been verified using IronFleet [ 9 ] ; in both scenarios, ad-hoc presentations of channel faults are verified against. Cryptographic protocol verifiers such as Tamarin [ 15 ] and ProVerif [ 3 ] provide automated analysis of cryptographic properties when processes communicate over an untrusted channel, but do not target channel-level faults. Model checkers such as Spin [ 11 ] and TLA+ [ 13 ] have been applied to distributed protocols, but there exists very little systematic support for reasoning directly about channel faults. As it stands, the current formal methods-driven approaches for protocol validation lack support for automated channel fault analysis, while testing-driven approaches remain fundamentally incomplete. To fill in this gap in the literature, we propose a general methodology for the automated discovery of attack traces, counterexamples, and formal guarantees across various channel configurations. To realize our methodology we introduce Tofu , a highly generalizable tool for synthesizing attacks on the faulty communication channels of distributed protocols that supports attacker models capable of arbitrarily dropping, replaying, reordering messages. Tofu targets the communication channels between protocol endpoints and synthesizes attacks to violate general linear temporal logic (LTL) specifications. Tofu is designed to either synthesize an attack or prove the absence of such via an exhaustive state-space search. Tofu is sound and complete: if there exists an attack, Tofu will find it, and Tofu will never produce false positives. Tofu is also designed to be easy to use once the protocol model is constructed: all a user must do is select the victim channels, select the desired attacker models, and invoke Tofu . We summarize our contributions: • We present generalizable gadgets representing attackers capable of dropping, replaying, and reordering messages on communication channels of distributed protocols, and we formally describe their construction. • We present Tofu , a tool for synthesizing attacks against distributed communication protocols. Tofu supports three general attacker models: an attacker that can drop, replay, or reorder messages on a channel. • We provide an overview of Tofu and demonstrate its usage by walking through applying it to the transmission control protocol (TCP). We release our code and models as open source at https://github.com/JakeGinesin/tofu . 2 Preliminaries In this section we introduce the mathematical foundations underpinning Tofu . We define linear temporal logic and Büchi Automata, formalize distributed protocols as compositions of communicating processes, and state the attack synthesis problem. 2.1 Linear Temporal Logic and the Büchi Automata Linear Temporal Logic (LTL) [ 18 ] is a modal logic for specifying properties of infinite sequences of program states. LTL extends propositional logic with temporal operators that express how propositions evolve over time along an execution. Definition 1 (LTL Syntax) Given a finite set of atomic propositions AP , LTL formulas are defined inductively: \phi::=\top\mid p\mid\neg\phi\mid\phi_{1}\land\phi_{2}\mid\mathbf{X}\,\phi\mid\phi_{1}\,\mathbf{U}\,\phi_{2} where p\in AP , \mathbf{X} ( next ) asserts \phi holds in the next state, and \mathbf{U} ( until ) asserts \phi_{1} holds continuously until \phi_{2} holds. The standard LTL derived operators are defined as: \mathbf{F}\,\phi\equiv\top\,\mathbf{U}\,\phi ( eventually , asserting \phi holds at some future state), \mathbf{G}\,\phi\equiv\neg\mathbf{F}\,\neg\phi ( always , asserting \phi holds at every future state), and \phi_{1}\Rightarrow\phi_{2}\equiv\neg\phi_{1}\lor\phi_{2} ( implies ). LTL properties are commonly classified into safety and liveness . Safety properties assert that “a bad thing never happens” and can be violated by finite prefixes, while liveness properties assert that “a good thing eventually happens” and require infinite traces to be violated. This distinction is important for Tofu ’s gadget design, as we discuss in Section 3 . We say a program P models a property \phi , written P\models\phi , if \phi holds over every infinite execution trace of P . LTL model checking, the problem of deciding whether P\models\phi for a finite-state P , is decidable, and model checkers will always terminate given sufficient resources. LTL is fundamentally equivalent to the Büchi Automaton, which expresses languages over infinite words. Büchi Automata are defined as follows. Definition 2 (Büchi Automaton) A Büchi automaton (BA) is a tuple B=(Q,\Sigma,\delta,Q_{0},F) where: • Q is a finite set of states, • \Sigma is a finite alphabet, • \delta\subseteq Q\times\Sigma\times Q is a transition relation, • Q_{0}\subseteq Q is a set of initial states, • F\subseteq

Read the complete text