Leaf

Welcome to project Leaf, a tool to dynamic analysis for Rust programs by MIR instrumentation.

Leaf aims to be robust, extensible, and easily-integrable within real world Rust testing stacks.

Please refer to Introduction for more details about the workflow of the tool, and try to perform your first dynamic analysis with Leaf to get a hands-on experience.

Introduction

Leaf is a framework for dynamic analysis of Rust programs built around MIR instrumentation. Instead of analyzing source code directly, Leaf compiles a program through leafc, rewrites the relevant MIR, and runs the resulting binary with a runtime backend attached.

That split keeps the responsibilities clear:

• the compiler frontend prepares the program for analysis,
• the runtime receives execution events and records or reacts to them, and
• higher-level tooling can orchestrate repeated runs or more advanced workflows.

At a high level, the workflow looks like this:

1. write or choose a Rust program,
2. compile it with Leaf’s instrumentation pipeline,
3. run the instrumented binary with the desired backend, and
4. inspect the emitted traces or analysis results.

This book starts with a practical getting-started guide, then moves into recipes and configuration details for common workflows. Use it as a reference when you need to understand how Leaf’s compiler, runtime, and orchestration pieces fit together.

First Dynamic Analysis with Leaf

Leaf is a Rust-oriented framework for dynamic analysis built around MIR instrumentation. The workflow is:

1. compile and instrument a target program with leafc, and
2. provide a runtime backend that receives callbacks from the instrumented program,
3. run the instrumented program with the backend plugged in.

Requirements

• Rust
• Python
• A working C toolchain and linker

Installing Leaf

1. Clone the repository and enter the workspace.

   $ git clone https://github.com/sfu-rsl/leaf.git
   $ cd leaf
   

2. Install the compiler frontend.

   $ cargo install --path ./compiler
   

Preparing Dynamic Analysis

1. Build a runtime backend, for example symbolic execution.

   $ cargo build -p runtime_symex
   

2. Make the runtime shared library discoverable to the instrumented binary.

   $ mkdir -p target/debug/runtime_symex
   $ ln -sf "$(find target/debug -maxdepth 1 -name 'libleafrt*.so' | head -n 1)" target/debug/runtime_symex/libleafrt.so
   $ export LD_LIBRARY_PATH="$PWD/target/debug/runtime_symex:$LD_LIBRARY_PATH"
   

Analyzing a Program

Leaf ships with sample programs under the samples/ directory. A minimal example is the hello_world sample.

fn main() {
    let x: u8 = core::hint::black_box(10);
    #[cfg(leafc)]
    let x: u8 = {
        use leaf::annotations::*;
        x.mark_symbolic()
    };

    if x < 5 {
        println!("Hello, world!");
    }
}

1. Compile the sample with leafc.

   $ leafc samples/hello_world.rs
   

2. Enable logging for the runtime.

   $ export LEAF_LOG="info"
   

3. Run the generated binary.

   $ ./hello_world
   

You should see runtime events emitted by the active backend. The exact output depends on the chosen backend and logging configuration, but the execution should complete and produce instrumentation traces or analysis data. With the example symbolic execution backend in effect, an output similar to the following is expected.

2024-12-10 00:40:55  INFO leafrt Initializing runtime library
2024-12-10 00:40:55  INFO leafrt::pri::basic::instance Initializing basic backend
2024-12-10 00:40:55  INFO leafrt::backends::basic::outgen Setting up binary output writing to directory: output
2024-12-10 00:40:55  INFO leafrt::pri::basic::instance Basic backend initialized
2024-12-10 00:40:55  INFO leafrt::backends::basic::sym_vars Added a new symbolic variable: <Var1: u8> = 10u8
2024-12-10 00:40:55  INFO leafrt::trace::log Notified about constraint {!(<(<Var1: u8>, 5u8))} at step Def(0:5)[2]
2024-12-10 00:40:55  INFO leafrt::outgen Found a solution:
{
    "1": 0u8,
}

Next steps

The rest of the book covers the compiler pipeline, runtime backends, and more advanced analysis workflows in greater detail.

Write a Counter Backend

This tutorial shows how to write a minimal Leaf backend and plug it into an instrumented program.

Goal

You will build a backend that counts assignments and run it through a Leaf-instrumented target.

The backend reports:

• total assignments
• unary assignment counts by UnaryOp
• binary assignment counts by BinaryOp

You will do this in five steps:

1. Define a minimal RuntimeBackend.
2. Define an AssignmentHandler that performs counting.
3. Add an InstanceManager for the backend.
4. Package the backend as a dynamic library.
5. Run an instrumented sample and verify the output.

Backend Design

Before starting the implementation, it helps to identify the core pieces of the backend.

The backend reports the total number of assignments, plus binary and unary assignment counts grouped by operation.

State

The information that a backend maintains about the running program is its state. For this backend, the state looks like this:

use std::collections::HashMap;
use leaf_runtime::abs::{BinaryOp, UnaryOp};

#[derive(Default)]
struct AssignStats {
    total_assignments: u64,
    binary_by_op: HashMap<BinaryOp, u64>,
    unary_by_op: HashMap<UnaryOp, u64>,
}

Updating the State

We need to:

• increment total_assignments for every assignment
• increment the appropriate map for every unary or binary assignment

This behavior can be represented as follows:

struct Counter<'a> {
    stats: &'a mut AssignStats,
}

impl Counter<'_> {
    fn binary_op_between(mut self, op: BinaryOp) {
        *self.stats.binary_by_op.entry(op).or_default() += 1;
        self.some()
    }

    fn unary_op_on(mut self, op: UnaryOp) {
        *self.stats.unary_by_op.entry(op).or_default() += 1;
        self.some()
    }

    fn some(mut self) {
        self.stats.total_assignments += 1;
    }
}

This is the core functionality that the backend must provide. Next, we map it to Leaf’s backend model.

Realizing the Backend

Step 1: Define a Backend

Tip

Boilerplate code is hidden by default, which can be displayed by clicking on the eyeball () button.

An implementation of a backend follows the contract defined by RuntimeBackend. Define the backend as follows:

use leaf_runtime::{
    abs::{AssignmentId, BasicBlockIndex, BinaryOp, PlaceUsage, UnaryOp, backend::Shutdown},
    pri::fluent::backend::{RuntimeBackend, shared::noop::*},
};

struct CounterBackend {
    // Components that will live during the execution.
}

impl RuntimeBackend for CounterBackend {
    // TODO
   type PlaceHandler<'a> = /* ... */
   where
       Self: 'a;

   type OperandHandler<'a> = /* ... */
   where
       Self: 'a;

   type AssignmentHandler<'a> = /* ... */
   where
       Self: 'a;

   type MemoryHandler<'a> = /* ... */
   where
       Self: 'a;

   type RawMemoryHandler<'a> = /* ... */
   where
       Self: 'a;

   type ConstraintHandler<'a> = /* ... */
   where
       Self: 'a;

   type CallHandler<'a> = /* ... */
   where
       Self: 'a;

   type DropHandler<'a> = /* ... */
   where
       Self: 'a;

   type AnnotationHandler<'a> = /* ... */
   where
       Self: 'a;

   type PlaceInfo = /* ... */;
   type Place = /* ... */;
   type DiscriminablePlace = /* ... */;
   type Operand = /* ... */;

   fn place<'a>(&'a mut self, _usage: PlaceUsage) -> Self::PlaceHandler<'a> {
       Default::default()
   }

   fn operand<'a>(&'a mut self) -> Self::OperandHandler<'a> {
       Default::default()
   }

   fn assign_to<'a>(
       &'a mut self, _id: AssignmentId, _dest: Self::Place,
   ) -> Self::AssignmentHandler<'a> {
       Default::default()
   }

   fn memory<'a>(&'a mut self) -> Self::MemoryHandler<'a> {
       Default::default()
   }

   fn raw_memory<'a>(&'a mut self) -> Self::RawMemoryHandler<'a> {
       Default::default()
   }

   fn constraint_at<'a>(&'a mut self, _loc: BasicBlockIndex) -> Self::ConstraintHandler<'a> {
       Default::default()
   }

   fn call_control<'a>(&'a mut self) -> Self::CallHandler<'a> {
       Default::default()
   }

   fn dropping<'a>(&'a mut self) -> Self::DropHandler<'a> {
       Default::default()
   }

   fn annotate<'a>(&'a mut self) -> Self::AnnotationHandler<'a> {
       Default::default()
   }
}

MIR contains several kinds of events that a backend can handle. This backend only needs assignments, so no-op definitions are sufficient for the other event types.

type PlaceHandler<'a>
    = NoOpPlaceHandler
where
    Self: 'a;

// Similar for other associated types
type OperandHandler<'a>
    = NoOpOperandHandler
where
    Self: 'a;

type AssignmentHandler<'a>
    = NoOpAssignmentHandler
where
    Self: 'a;

type MemoryHandler<'a>
    = NoOpLifetimeHandler
where
    Self: 'a;

type RawMemoryHandler<'a>
    = NoOpRawMemoryHandler
where
    Self: 'a;

type ConstraintHandler<'a>
    = NoOpConstraintHandler
where
    Self: 'a;

type CallHandler<'a>
    = NoOpCallHandler
where
    Self: 'a;

type DropHandler<'a>
    = NoOpDropHandler
where
    Self: 'a;

type AnnotationHandler<'a>
    = NoOpAnnotationHandler
where
    Self: 'a;


type PlaceInfo = NullPlaceInfo;
type Place = NullPlace;
type DiscriminablePlace = NullPlace;

type Operand = NullOperand;

Note

We explain each element elsewhere in the book. To keep this tutorial focused, treat these associated types and methods as holes filled by no-op definitions.

The backend instance owns the state, so add it:

#[derive(Default)]
struct CounterBackend { 
    stats: AssignStats,
}

Print the statistics when the runtime shuts down:

impl Shutdown for CounterBackend {
    fn shutdown(&mut self) {
        println!(
            "total assignments: {}\nbinary: {:?}\nunary: {:?}",
            self.stats.total_assignments, self.stats.binary_by_op, self.stats.unary_by_op,
        );
    }
}

Step 2: Handling Assignments

Now we add the counting behavior shown earlier as an implementation for AssignmentHandler.

struct CounterAssignmentHandler<'a> {
  stats: &'a mut AssignStats,
}

impl AssignmentHandler for CounterAssignmentHandler<'_> {
  type Place = NullPlace;
  type Operand = NullOperand;

    fn binary_op_between(self, op: BinaryOp, _a: Self::Operand, _b: Self::Operand) {
    *self.stats.binary_by_op.entry(op).or_default() += 1;
    self.some()
  }

    fn unary_op_on(self, op: UnaryOp, _operand: Self::Operand) {
    *self.stats.unary_by_op.entry(op).or_default() += 1;
    self.some()
  }

  // Catch-all for other assignment forms.
    fn some(self) {
    self.stats.total_assignments += 1;
  }
}

Then installing it in the backend:

impl RuntimeBackend for CounterBackend {
    type AssignmentHandler<'a>
        = CounterAssignmentHandler<'a>
    where
        Self: 'a;

    fn assign_to<'a>(
        &'a mut self,
        _id: AssignmentId,
        _dest: Self::Place,
    ) -> CounterAssignmentHandler<'a> {
        CounterAssignmentHandler { stats: &mut self.stats }
    }
}

A few details are worth mentioning, although they are not specific to this backend:

• The traits to implement for a backend and its handlers are defined for working in FluentPri.
• The parameters given in an interface call chain provide the representation of the pieces in the original MIR event. For instance, in an assignment based on a unary operation like _5 = Neg(move _4);, a call chain of assign_to(ID_X, p_dest).unary_op_on(UnaryOp::Neg, p_operand) is expected where ID_X corresponds to the unique id for this assignment in its parent body, p_dest and p_operand correspond to place representations for locals _5 and _4.
• Handler components of a backend are designed to be short-lived instances that provide the expected interface. All durable information (e.g., program state) should be owned by the backend itself and borrowed by the handlers.

Step 3: Add an InstanceManager and Pri

InstanceManager

An instance manager constructs, provides access to, and destroys backend instances for probes. Probes can run at any point during execution and in any function in the program. In many cases, a simple instance manager that wraps a globally allocated backend instance suffices.

This tutorial does not explain the lower-level details of this trait. Use the following implementation as a template, and see the rest of the book for details.

mod instance {
    use std::sync::{Mutex, Once};

    use leaf_runtime::pri::{fluent::InstanceManager, refs::NoOpRefManager};

    use super::*;

    static BACKEND: Mutex<Option<CounterBackend>> = Mutex::new(None);
    static mut PLACE_REF_MANAGER: NoOpRefManager<NullPlace> = NoOpRefManager::new(());
    static mut OPERAND_REF_MANAGER: NoOpRefManager<NullOperand> = NoOpRefManager::new(());

    static INIT: Once = Once::new();

    pub(crate) struct CounterInstanceManager;

    impl InstanceManager for CounterInstanceManager {
        type PlaceInfo = NullPlace;
        type Place = NullPlace;
        type Operand = NullOperand;

        type Backend = CounterBackend;

        type PlaceBuilder = NoOpPlaceBuilder<NullPlace, NullPlace>;

        type PlaceRefManager = NoOpRefManager<NullPlace>;

        type OperandRefManager = NoOpRefManager<NullOperand>;

        fn init() {
            INIT.call_once(|| {
                let mut guard = BACKEND.lock().unwrap();
                let backend = CounterBackend::default();
                *guard = Some(backend);
            });
        }

        fn deinit() {}

        fn perform_on_backend<T>(action: impl for<'a> FnOnce(&'a mut Self::Backend) -> T) -> T {
            let mut guard = BACKEND.lock().unwrap();
            let backend = guard.as_mut().expect("Runtime is not initialized.");
            action(backend)
        }

        #[allow(static_mut_refs)]
        fn perform_on_place_ref_manager<T>(
            action: impl FnOnce(&mut Self::PlaceRefManager) -> T,
        ) -> T {
            action(unsafe { &mut PLACE_REF_MANAGER })
        }

        #[allow(static_mut_refs)]
        fn perform_on_operand_ref_manager<T>(
            action: impl FnOnce(&mut Self::OperandRefManager) -> T,
        ) -> T {
            action(unsafe { &mut OPERAND_REF_MANAGER })
        }
    }
}

Exporting a PRI

The final step in the backend crate is to define the PRI implementation that the flavor exports through Leaf’s C ABI.

pub mod interface {
    use leaf_runtime::pri::fluent::FluentPri;

    type CounterPri = FluentPri<super::instance::CounterInstanceManager>;

    leaf_runtime::make_late_init_pri_of!(CounterPri);

    pub type DefaultPri = CounterPriLateInit;
}

Step 4: Package as a Dynamic Library

To publish the backend as libleafrt.so, which can be loaded by an instrumented program, define a flavor as a separate crate and use the project template.

For this tutorial, copy an existing flavor under runtime/flavors and point its backend dependency at the backend crate in Cargo.toml.

[package]
name = "runtime_counter"
license = { workspace = true }
version = { workspace = true }
edition = "2021"

[lib]
name = "leafrt_counter"
crate-type = ["cdylib"]

[dependencies]
common = { workspace = true }
backend = { path = "../../backends/counter", package = "runtime_backend_counter" }

The flavor’s build.rs sets the shared library’s SONAME to libleafrt.so, and its src/lib.rs exports the backend through the common FFI template:

include!("../shared_build.rs");

fn main() {
    set_so_name();
}

type PriImpl = backend::interface::DefaultPri;

include!("../../ffi_template.rs");

Step 5: Run and inspect output

Build the flavor from the repository root:

$ cargo build -p runtime_counter

Follow the same steps as in the other tutorial to load the dynamic library.

Now compile and run the instrumented sample with leafc:

For example, instrument the following program.

fn main() {
let mut x: i8 = core::hint::black_box(20);

if x < 5 {
    x += 1;
} else {
    x -= 1;
}
x = -x;

core::hint::black_box(x);
}

Save the example as counter_sample.rs, then run:

$ leafc counter_sample.rs
$ ./counter_sample

fn main() -> () {
    let mut _0: ();
    let mut _1: i8;
    let mut _2: bool;
    let mut _3: i8;
    let mut _4: i8;
    let _5: i8;
    scope 1 {
        debug x => _1;
        scope 3 (inlined std::hint::black_box::<i8>) {
            debug dummy => _1;
        }
    }
    scope 2 (inlined std::hint::black_box::<i8>) {
        debug dummy => const 20_i8;
    }

    bb0: {
        _1 = std::intrinsics::black_box::<i8>(const 20_i8) -> [return: bb4, unwind unreachable];
    }

    bb1: {
        StorageDead(_3);
        _1 = Add(copy _1, const 1_i8);
        goto -> bb3;
    }

    bb2: {
        StorageDead(_3);
        _1 = Sub(copy _1, const 1_i8);
        goto -> bb3;
    }

    bb3: {
        StorageDead(_2);
        StorageLive(_4);
        _4 = copy _1;
        _1 = Neg(move _4);
        StorageDead(_4);
        StorageLive(_5);
        _5 = std::intrinsics::black_box::<i8>(move _1) -> [return: bb5, unwind unreachable];
    }

    bb4: {
        StorageLive(_2);
        StorageLive(_3);
        _3 = copy _1;
        _2 = Lt(move _3, const 5_i8);
        switchInt(move _2) -> [0: bb2, otherwise: bb1];
    }

    bb5: {
        StorageDead(_5);
        return;
    }
}

Then run it with the counter backend. For this input, the output is similar to:

total assignment: 7
binary: {Lt: 1, Sub: 1}
unary: {Neg: 1}

Build a Cargo Package with Leaf

As mentioned before, you can look at leafc as a wrapper around rustc and it should be work in any command using rustc.

Building packages is no exception. As supported by cargo you can set build.rust configuration key to override the compiler.

$ export RUSTC=leafc
$ cargo build

Leaf’s Modifications

leafc is slightly specialized when used by cargo for compiling crate’s dependencies. (TODO)

Diverging Input Generation

Important

This document is currently obsolete and will be removed with further developments of the book. The orchestrators mentioned in this tutorial are currently moved out of the project.

Each instance of concolic execution of a program, records a trace of the constraints put on symbolic variables at each step of the execution. Conditional branches are the major source of these constraints and whether they are held or not determines the target of the branch. Therefore, concolic execution can be used to find concrete values for the symbolic variables such that the execution diverges at conditional branches compared to the previous execution. We refer to these concrete values as diverging inputs, counterexamples, or generally answers.

The current default configuration of Leaf tries to find a diverging input whenever a new constraint is observed. For instance, in the following program, the input (x = 10) does not satisfy the branch condition (x < 5), which the backend reports as {!(<(<Var1: u8>, 5u8))}. It tries to find an input that would satisfy it (so the execution would diverge at this point), and reports back value 0u8 as a possible one.

Diverging Standard Input Generation

If all symbolic variables are from u8, the default configuration puts the found answers in binary files in which each byte corresponds to a symbolic variable ordered by when they were marked as symbolic.

This is mainly meant for situations where we want to mark a file symbolic, e.g., standard input.

Although the backend (and execution of the instrumented program) is enough to obtain the diverging standard input, the one-time orchestrator is provided to facilitate this process with further control.

You can install it by running the following command in Leaf’s root folder.

leaf$ cargo install --path ./orchestrator

Then you provide the path to the instrumented program and the desired path to put the diverging inputs at. For example,

$ leafo_onetime --program ./hello_world --outdir ./next
next/diverging_0.bin

It runs the target program, and prints the names of the files generated as diverging input.

Pure Concolic Testing

By repeating the above procedure for each generated input, more possible paths in the target program will be covered. We use the term pure concolic testing, as used by SymCC for this method of testing.

If you are interested in finding possible crashes in your program using pure concolic testing, the project comes with a utility named leaff_pure_conc, which runs the loop for programs and captures those that cause a crash in them. Currently, it only supports programs with symbolic standard input (uses the one-time orchestrator).

To run pure concolic testing loop for a target:

1. Install the tool.

   leaf$ cargo install --path ./integration/libafl/fuzzers/pure_concolic
   

2. Build your program with leafc.
3. Pass the executable path to the tool. e.g.,

   $ leaff_pure_conc --conc-program ./hello_world
   

4. The loop stops if no more new distinct input is found to be given to the program (can possibly run forever).

We recommend looking at the options available for tuning the loop by passing --help.

Fuzzing

Important

This document is currently obsolete and will be removed with further developments of the book. The orchestrators mentioned in this tutorial are currently moved out of the project.

One of the use cases of concolic execution, which is demonstrated to be effective, is hybrid fuzzing, in which fuzzing is aided with solver-found inputs generated by symbolic execution to take certain paths inside the program that other techniques are inefficient to find.

Leaf is aimed to be suitable for this purpose and comes with a built-in support for LibAFL, a customizable fuzzing framework with modern architecture written in Rust. Crate libafl_leaf contains facilities for using Leaf-instrumented programs with the fuzzers written using this library.

Hybrid Fuzzing for libFuzzer

In an abstract manner, hybrid fuzzing for LibAFL-based fuzzers is achievable using a stage that generates diverging inputs from the current test case. This stage should perform the concolic execution using the current test case to derive the diverging inputs and offer them to the fuzzer for evaluation. Thus, the following steps are presumable for an execution-based concolic executor like Leaf.

1. Build an executable equivalent to the fuzz target, which is suitable for concolic execution.
2. Define a mutator stage that runs the built executable and obtains new inputs.
3. Add the stage to the fuzzer.

The mentioned ingredients are provided by Leaf; leafc instruments your target program, leafo_onetime helps with collecting the diverging inputs, and libafl_leaf provides the stage. As libFuzzer (through cargo-fuzz) is one the most-used tools to perform fuzzing for Rust projects, a rudimentary support is also provided for harnesses written based on libfuzzer-sys to upgrade them to a hybrid fuzzer. It is developed as an extension of LibAFL’s implementation of libFuzzer, so the same instructions and options apply.

Recipe

With an understanding of the general procedure above, you can follow the instruction below to upgrade your existing fuzzer to a hybrid one.

• Prerequisites

  1. The one-time orchestrator (leafo_onetime) is installed in your environment. If not, install it similarly to leafc using the following command in Leaf’s root folder.

     leaf$ cargo install --path ./orchestrator
     

  2. You have a fuzzer written using libfuzzer-sys. We assume it is named fuzz_target_1 and has the following template.

     #![no_main]
     
     use libfuzzer_sys::fuzz_target;
     
     fuzz_target!(|data: &[u8]| {
         // fuzzed code goes here
     });

1. Replace libfuzzer-sys source to Leaf’s implementation in Cargo.toml of your fuzz project.

   # From
   libfuzzer-sys = { version = "...", features = ["your", "features", "here"] }
   
   # To
   libfuzzer-sys = { git = "https://github.com/sfu-rsl/leaf.git", package = "libafl_libfuzzer", features = ["your", "features", "here"]}
   

2. Change fuzz_target macro invocation to hybrid_fuzz_target, and make no_main attribute conditional based on compilation with leafc.

   #![cfg_attr(not(leafc), no_main)]
   
   use libfuzzer_sys::hybrid_fuzz_target;
   
   hybrid_fuzz_target!(|data: &[u8]| {
       // fuzzed code goes here
   });

   (hybrid_fuzz_target additionally writes a program with a main function that reads the whole standard input, marks it as symbolic, and passes to the closure.)

3. Build your fuzz target with leafc in a separate cargo target directory like below.

   fuzz$ RUSTC=leafc cargo build --bin fuzz_target_1 --target-dir ./target/leaf
   

4. Build your fuzzer normally, e.g.,

   fuzz$ cargo fuzz build fuzz_target_1
   

5. Run your fuzzer with the additional argument conc_program which points to the instrumented executable built using leafc.

   fuzz$ cargo fuzz run fuzz_target_1 -- -conc_program=./target/leaf/debug/fuzz_target_1
   

Please refer to the technical documentation for further details about the components and steps mentioned above.

Samples Reference

Map

Here is a map of sample programs put under samples in the work tree of the project.