Fuzzamoto

Fuzzamoto provides a framework and fuzzing engine for coverage-guided fuzzing of Bitcoin full node implementations.

• Implementation Agnostic: The same tests can target different protocol implementations and compare their behavior (e.g. Bitcoin Core, btcd, libbitcoin, ...)
• Holistic: Tests are performed on the full system, not just isolated components, enabling the discovery of bugs that arise from the composition of different components
• Coverage-Guided: Fuzzing is guided by coverage feedback

It is not meant to be a replacement for traditional fuzzing of isolated components, but rather a complement to it.

Trophies

Snapshot Fuzzing

To achieve deterministic and performant fuzzing of one or more full node instances, snapshot fuzzing is used. With snapshot fuzzing, testcases are executed inside a special virtual machine that has the ability to take a snapshot of itself (CPU registers, memory, disk, other devices, ...) and also to reset itself quickly to that snapshot.

The rough architecture when fuzzing with fuzzamoto looks as follows:

                       Report bug                              
                           ▲                                   
                           │                                   
                           │                                   
                          Yes                                  
                           │                                   
                           │                                   
       ┌─────────────────►Bug?───────────────────────────────┐ 
       │                                                     │ 
       │                                                     │ 
       │                                                     │ 
┌──────┼──────────── Virtual Machine ───────────────────┐    │ 
│      │                                                │    │ 
│ ┌────┼─────┐                            ┌───────────┐ │    │ 
│ │ Scenario │◄───────p2p/rpc/...────────►│ Full Node │ │    No
│ └────▲─────┘                            └───────────┘ │    │ 
│      │                                                │    │ 
└──────┼────────────────────────────────────────────────┘    │ 
       │                                                     │ 
       │                                                     │ 
       │                                                     │ 
       └─────────Generate/Mutate testcase◄───────────────────┘ 

Inside the VM, a scenario runs that controls snapshot creation and receives inputs from the fuzzer to execute against the target(s). If a bug is detected, the scenario reports it to the fuzzer. If no crash is detected and the scenario finishes the execution of a testcase, it tells the fuzzer to reset the VM and provide another testcase.

Backends

Currently, snapshot fuzzing support is only implemented for Nyx but other backends could also be supported in the future.

The fuzzamoto-nyx-sys crate provides rust bindings to a nyx agent implementation written in C. The agent provides the interface for scenarios to communicate with the fuzzer through the Nyx hypercall API. The agent provides the following functionality:

• Taking a VM snapshot & receiving the next input from the fuzzer
• Reporting a crash to the fuzzer
• Resetting the VM to the snapshot
• Instructing the fuzzer to ignore the current testcase
• Dumping files to the host machine

The crate also comes with a LD_PRELOADable crash handler that reports application aborts directly to Nyx (See nyx-crash-handler.c).

Alternative Backends

In the future, using libafl_qemu and its full system capabilities would enable fuzzing on and of more architectures (Nyx only supports x86 at this time) as well enable fuzzing on non-bare metal hardware.

Coverage Feedback

Coverage data is collected using compile time instrumentation and communicated to the fuzzer using Nyx's compile-time instrumentation mode. Currently, only AFL++ coverage instrumentation is supported, which necessitates that targets are build with afl-clang-{fast,lto}.

Upon initialization, the Nyx agent creates a shared memory region large enough to fit the target's coverage map. The size of the map is previously determined by executing the target binary with the AFL_DUMP_MAP_SIZE=1 environment variable (see fuzzamoto-nyx-sys/build.rs). The agent then sets __AFL_SHM_ID and AFL_MAP_SIZE environment variables (recognized by AFL++'s instrumentation) to the shared memory region's id and size, respectively. It also informs Nyx of the address of the shared region, which in turn is communicated to the fuzzer for feedback evaluation. Once the target is executed, it writes the coverage data to the shared memory region.

Scenarios

Scenarios are a core concept in Fuzzamoto. They are fuzzing harnesses, responsible for snapshot state setup, controlling fuzz input execution and reporting results back to the fuzzer.

Each scenario needs to implement two functions:

• Scenario creation and snapshot state setup. This is where target full node processes are spawned and brought into the desired state for the fuzzing campaign.
• Testcase execution. This is where a fuzz input is executed in the context of the previously created state.

Each scenario is implemented to run as a standalone process inside the VM. A convience macro fuzzamoto_main exists to implement the main function for scenarios, which includes the necessary glue all scenarios need.

All scenarios are implemented in the fuzzamoto-scenarios crate. For example:

• HttpServerScenario: tests Bitcoin Core's http server. It receives raw bytes from the fuzzer and parses them into a sequence of operations (using Arbitrary) to be performed on the server.
• RpcScenario: generic scenario for testing Bitcoin Core's RPC interface. It receives a sequence of RPC calls (using Arbitrary) and executes them against the target.
• IrScenario: generic scenario for testing Bitcoin full nodes through the p2p interface. Primarily meant to be fuzzed using fuzzamoto-libafl (custom fuzzer for Fuzzamoto IR).

Fuzzamoto Intermediate Representation

At a high level, generic p2p testcases represent a sequence of actions performed against one or more target nodes:

• Changing system time
• Establishing a new p2p connection
• Sending protocol messages on an established connection

Protocol messages in particular are highly structured, as they are serialized using a custom format, contain various cryptographic primitives (hash commitments, signatures, checksums, ...) and must fullfil various other structural requirements to be considered valid, such as:

• Block headers must point to a prior block via its hash
• Transaction inputs must point to existing unspent transactions outputs via transaction identifiers
• blocktxn messages are only processed if requested (after a prior cmpctblock message)
• ...

Therefore, naively fuzzing a scenario with a byte-array fuzzer, using the following input format (with e.g. Arbitrary) will mostly result in fuzzing the message (de)serialization code and other easy to reach protocol flows.

#![allow(unused)]
fn main() {
pub enum Action {
    SetTime { ... },
    Connect { ... },
    SendMessage { ... },
}

pub struct TestCase {
    pub actions: Vec<Action>,
}
}

If we want to focus on fuzzing deeper logic instead, then we'll need to make input generation/mutation aware of the structural requirements. This is were an intermediate representation, that holds relevant type and structural information, becomes useful.

Fuzzamoto IR describes small programs that can be compiled into the simple testcase format from above (TestCase). For the purpose of mutation/generation, the fuzzer (fuzzamoto-libafl) operates on testcases encoded as the IR (as it contains relevant type and structural information) and only compiles it to the simple format for target execution.

┌───────────────────────────────────────Fuzzer───────────────────────────────────────┐
│                                                                                    │
│ ┌─────────────┐                  ┌────────┐                   ┌──────────────────┐ │
│ │ Corpus (IR) ├──────Select─────►│ Mutate ├──────Compile──────► Target Execution │ │
│ └─────────────┘                  └────────┘                   └──────────────────┘ │
│                                                                                    │
└────────────────────────────────────────────────────────────────────────────────────┘

Design

Fuzzamoto IR consists of a sequence of operations that take some input variables and produce variables as output. All variables are typed (see variable.rs) and operations expect variables of compatible type. The IR uses static single assignement form (SSA), which means every variable in the IR is assigned exactly once. SSA helps simplify define-use analysis, type inference and code generation/mutation among other things.

Each IR program is associated with a context that represents the snapshot state of the test VM:

• Mock time
• Number of nodes
• Number of existing connections made by the scenario
• Available transaction outputs (Used for LoadTxo instructions)
• Available block headers (Used for LoadHeader instructions)

Programs might not be valid/useful in a different context. E.g. a program that was generated within the context of 10 nodes and 200 connections might not be valid in a context with 1 nodes and 8 connections, as it might refer to non-existent nodes or connections.

In the following simple example, the IR describes the creation of a tx message from raw bytes that is then send to a node via one of the existing connections:

// Context: nodes=1 connections=8 timestamp=1296688802
v0 <- LoadConnection(5)
v1 <- LoadMsgType("tx")
v2 <- LoadBytes("fefe8520fefefe0000fffffe8520")
SendRawMessage(v0, v1, v2)

Note that this is a human readable representation and not the internal in-memory structure used by the fuzzer.

This example would compile into a single TestCase::SendMessage operation.

The next example is more complex and better demonstrates the strengths of the IR:

// Context: nodes=1 connections=8 timestamp=1296688802
v0 <- LoadBytes("5656565656565656567a7a7a7a7a7a7a7a7a7aa9ffff5656567a506464649b64596464f16463646464")
v1 <- LoadTxo(083666c9bf066f9d3a28ad30f5c0ed6fe463f7777e033783875b2523ef5214bb:0, 2500000000, 00204ae81572f06e1b88fd5ced7a1a000945432e83e1551e6f721ee9c00b8cc33260, , 51)
v2 <- LoadConnection(4)
v3 <- LoadTxVersion(2)
v4 <- LoadLockTime(144)
BeginBuildTx(v3, v4) -> v5
  BeginBuildTxInputs -> v6
    v7 <- LoadSequence(4294967295)
    AddTxInput(v6, v1, v7)
  v8 <- EndBuildTxInputs(v6)
  BeginBuildTxOutputs(v8) -> v9
    BeginWitnessStack -> v10
    v11 <- EndWitnessStack(v10)
    v12 <- BuildPayToWitnessScriptHash(v0, v11)
    v13 <- LoadAmount(100000000)
    AddTxOutput(v9, v12, v13)
  v14 <- EndBuildTxOutputs(v9)
v15 <- EndBuildTx(v5, v8, v14)
v16 <- TakeTxo(v15)
v17 <- LoadLockTime(508195987)
v18 <- LoadTxVersion(2)
BeginBuildTx(v18, v17) -> v19
  BeginBuildTxInputs -> v20
    v21 <- LoadSequence(4294967294)
    AddTxInput(v20, v16, v21)
  v22 <- EndBuildTxInputs(v20)
  BeginBuildTxOutputs(v22) -> v23
    v24 <- LoadBytes("51")
    BeginWitnessStack -> v25
    v26 <- EndWitnessStack(v25)
    v27 <- BuildPayToWitnessScriptHash(v24, v26)
    v28 <- LoadAmount(98500000)
    AddTxOutput(v23, v27, v28)
  v29 <- EndBuildTxOutputs(v23)
v30 <- EndBuildTx(v19, v22, v29)
SendTx(v2, v30)
SendTx(v2, v15)

Two transactions are build (v15, v30), that are then send to the node under test through connection v2. v15 spends from an output in the snapshot state v1 (loaded by LoadTxo). The relationship between the two transactions (i.e. v30 is the parent of v15) is encoded in the IR through the use of variables. v16 (output of TakeTxo) represents the output created by v15 and is added to v30 via the AddTxInput instruction in the BuildTxInputs block. v30 is sent before v15 potentially triggering 1P1C logic.

This example would compile into two TestCase::SendMessage operations, containing the correctly serialized transactions v15 and v30.

Table of Operations

Mutators

Several mutation strategies are available for IR programs:

• InputMutator: Replaces an instruction's input variable with another variable of compatible type. This mutation aims at changing the dataflow of a given program by making an instruction operate on a different value.
• OperationMutator: Mutate an operation, e.g. mutate the input values of a Load* operation.
• CombineMutator: Insert an entire IR program into another one at a random location. This mutation aims at changing a program's control flow by combining two programs into one.
• ConcatMutator: Append an entire IR program to another one at a random location. This mutation aims at changing a program's control flow by appending another program to it.

Generators offer further mutation strategies that involve the generation of new programs or new instructions into existing programs. They can be used to bootstrap an initial corpus as well as to mutate existing inputs during a fuzzing campaign. The following generators are available:

• SendMessageGenerator: Generates a new SendRawMessage instruction
• AdvanceTimeGenerator: Generates new AdvanceTime and SetTime instructions
• CompactFilterQueryGenerator: Generates new SendGetCFilters, SendGetCFHeaders and SendGetCFCheckpt instructions
• BlockGenerator: Generates instructions to build a block
• HeaderGenerator: Generates instructions to build a header
• AddTxToBlockGenerator: Generates instructions to add a transaction to a block
• OneParentOneChildGenerator: Generates instructions for building two new transactions (a 1-parent 1-child package) and sending them to a node
• ... see generators/

Minimizers

Minimizers are used to reduce the size of an interesting program (e.g. bug or new coverage). The following minimization strategies are available:

• Nopping: Attempt to nop out instructions in an effort to reduce the size of a program.
• Cutting: Attempt to cut out instructions of the end of a program in an effort to reduce the size of a program.
• BlockNopping: Attempt to nop out entire blocks of instructions in an effort to reduce the size of a program (e.g. nop all instructions between and including BeginBlockTransactions and EndBlockTransactions).

Fuzzing with AFL++

Make sure to understand the system requirements before running fuzzing campaigns.

All fuzzamoto scenarios can be fuzzed with AFL++'s nyx mode, except for the IR scenario (scenario-ir).

The Dockerfile at the root of the repository contains an example setup for running fuzzamoto fuzzing campaigns with AFL++.

Build the container image:

docker build -t fuzzamoto .

And then create a new container from it:

docker run --privileged -it fuzzamoto bash

--privileged is required to enable the use of kvm by Nyx.

Example: http-server

All commands in this example are supposed to be run inside the docker container.

AFL++ can't start from an empty corpus, so unless you already have a seed corpus available, you'll need to create or find at least one seed input (ideally this is a useful seed not just "AAA"):

mkdir /tmp/in && echo "AAA" > /tmp/in/A

Once the seed corpus is ready, you'll be able to start the fuzzing campaign:

/AFLplusplus/afl-fuzz -X -i /tmp/in -o /tmp/out -- /tmp/fuzzamoto_scenario-http-server

Multi-core campaigns

Running a multi-core campaign is best practice to make use of all available cores. This can be done with AFL_Runner (installed in the Dockerfile).

Example: http-server

aflr run --nyx-mode --target /tmp/fuzzamoto_scenario-http-server/ \
    --input-dir /tmp/http_in/ --output-dir /tmp/http_out/ \
    --runners 16

Fuzzing with fuzzamoto-libafl

Make sure to understand the system requirements before running fuzzing campaigns.

fuzzamoto-libafl is a LibAFL based fuzzer for Fuzzamoto operating on the fuzzamoto intermediate representation. This fuzzer exclusively operates on the IR scenario.

The Dockerfile.libafl at the root of the repository contains an example setup for running fuzzamoto fuzzing campaigns with libafl.

Build the container image:

docker build -f Dockerfile.libafl -t fuzzamoto-libafl .

And then create a new container from it (mounting the current directory to /fuzzamoto):

docker run --privileged -it fuzzamoto-libafl -v $PWD:/fuzzamoto bash

--privileged is required to enable the use of kvm by Nyx.

More instructions will follow soon, see the inline documentation in Dockerfile.libafl for now.

Reproducing Testcases

Crashing or other interesting inputs can be reproduced without the snapshotting VM, by building the scenario binary without the nyx feature and supplying it the input either through stdin or the FUZZAMOTO_INPUT environment variable.

Build all scenarios for reproduction purposes:

cargo build --release --package fuzzamoto-scenarios --features reproduce

--features reproduce is used to enable features useful for reproduction, e.g. inherit stdout from the target application, such that any logs, stack traces, etc. are printed to the terminal.

http-server example

Run the scneario with the input supplied through stdin and pass the right bitcoind binary:

cat ./testcase.dat | RUST_LOG=info ./target/release/scenario-http-server ./bitcoind
# Use "echo '<input base64>' | base64 --decode | ..." if you have the input as a base64 string

Or alternatively using FUZZAMOTO_INPUT:

FUZZAMOTO_INPUT=$PWD/testcase.dat RUST_LOG=info ./target/release/scenario-http-server ./bitcoind

Troubleshooting

• Make sure to not use the nyx feature or else you'll see:

  ...
  Segmentation fault (core dumped)
  

• If you see the following output, try killing any left over bitcoind instances or retry reproduction until it works:

  ...
  Error: Unable to bind to 127.0.0.1:34528 on this computer. Bitcoin Core is probably already running.
  Error: Failed to listen on any port. Use -listen=0 if you want this.
  
  thread 'main' panicked at /fuzzamoto/vendor/corepc-node/src/lib.rs:389:59:
  failed to create client: Io(Os { code: 2, kind: NotFound, message: "No such file or directory" })
  ...
  

• If an input does not reproduce, check that you are compiling with all necessary features relevant for your case, such as compile_in_vm, force_send_and_ping and reduced_pow (these should all be enabled if compiling with the reproduce feature). Also check that bitcoind was build with all required patches applied (see target-patches/ and Patches).

• If the input still does not reproduce (e.g. bitcoind does not crash), the crash might be non-deterministic. Have fun debugging!

Custom Target Patches

Certain targets require custom patches for effective fuzzing and testcase reproduction. These can be found in the target-patches directory.

Maintaining external patches should be avoided if possible, as it has several downsides:

• They might become outdated and require rebase
• They might not apply to a PR we would like to fuzz, in which case the patch needs to be adjusted just for the PR
• Testcases might not reproduce without the patches and it is on the user to make sure all patches were applied correctly

If a patch is necessary, then landing it in the target application is preferred but in the case of a fuzz blocker (e.g. checksum check in the target) the best solution is to make the harness/test produce valid inputs (if possible).

Current patches:

• bitcoin-core-rng.patch: Attempts to make Bitcoin Core's RNG deterministic
• bitcoin-core-aggressive-rng.patch: Same as bitcoin-core-rng.patch but more aggressive

Coverage Reports

It is possible to generate coverage reports for fuzzamoto scenarios by using the fuzzamoto-cli coverage command. The build steps for doing this are slightly different than if you were to run fuzzamoto-cli init:

• the bitcoind node must be compiled with llvm's source-based code coverage.
• fuzzamoto's nyx feature should be disabled as coverage tooling does not use snapshots.
• a corpus for the specific scenario is required

The Dockerfile.coverage file can be used to run a corpus against a specific scenario. Both a host directory and a corpus directory must be mounted.

Example:

docker build -t fuzzamoto-coverage -f Dockerfile.coverage .
docker run --privileged -it -v HOST_OUTPUT_DIR:/mnt/output -v HOST_CORPUS_DIR:/mnt/corpus fuzzamoto-coverage /fuzzamoto/target/release/scenario-compact-blocks

System Requirements

For testcase reproduction (see Reproducing Testcases), no hardware restrictions with regard to architecture should exist. A linux operating system is required.

For fuzzing, a bare metal x86_64 architecture and linux operating system are required. At least 32GB of RAM are recommended.

Fuzzamoto has been tested on the following hardware:

Hetzner AX 102:

• AMD Ryzen 9 7950X3D 16-Core Processor
• 128GB RAM

Intel machine:

• 13th Gen Intel(R) Core(TM) i9-13900K
• 128GB RAM

If you have a machine that you've successfully fuzzed with Fuzzamoto, please share it with us, so we can refine the system requirements!

VMware backdoor

Nyx requires the kvm vmware backdoor to be enabled. This can be done using the following commands on your host machine:

sudo modprobe -r kvm-intel # or kvm-amd
sudo modprobe -r kvm
sudo modprobe  kvm enable_vmware_backdoor=y
sudo modprobe  kvm-intel # or kvm-amd

Integrating New Targets

Writing New Scenarios

Extending Fuzzamoto IR