Skip to contentSkip to conversation

bpf: Don't trust r0 bounds after BPF to BPF call that tail_calls

PATCH In review Arthur Fabre 2 participants 2 messages Dec 12, 2024

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bpf: Don't trust r0 bounds after BPF to BPF call that tail_calls

When making BPF to BPF calls, the verifier propagates register bounds info for r0 from the callee to the caller.

For example loading:

    #include <linux/bpf.h>
    #include <bpf/bpf_helpers.h>

    static __attribute__((noinline)) int callee(struct xdp_md *ctx)
    {
            int ret;
            asm volatile("%0 = 23" : "=r"(ret));
            return ret;
    }

    static SEC("xdp") int caller(struct xdp_md *ctx)
    {
            int res = callee(ctx);
            if (res == 23) {
                    return XDP_PASS;
            }
            return XDP_DROP;
    }

The verifier logs:

    func#0 @0
    func#1 @6
    0: R1=ctx() R10=fp0
    ; int res = callee(ctx); @ test.c:15
    0: (85) call pc+5
    caller:
     R10=fp0
    callee:
     frame1: R1=ctx() R10=fp0
    6: frame1: R1=ctx() R10=fp0
    ; asm volatile("%0 = 23" : "=r"(ret)); @ test.c:9
    6: (b7) r0 = 23                       ; frame1: R0_w=23
    ; return ret; @ test.c:10
    7: (95) exit
    returning from callee:
     frame1: R0_w=23 R1=ctx() R10=fp0
    to caller at 1:
     R0_w=23 R10=fp0

    from 7 to 1: R0_w=23 R10=fp0
    ; int res = callee(ctx); @ test.c:15
    1: (bc) w1 = w0                       ; R0_w=23 R1_w=23
    2: (b4) w0 = 2                        ; R0_w=2
    ;  @ test.c:0
    3: (16) if w1 == 0x17 goto pc+1
    3: R1_w=23
    ; } @ test.c:20
    5: (95) exit
    processed 7 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0

And correctly tracks R0_w=23 from the callee through to the caller. This lets it completely prune the res != 23 branch, skipping over instruction 4.

But this isn't sound if the callee makes a bpf_tail_call(): if the tail call succeeds, callee() will directly return whatever the tail called program returns. We can't know what the bounds of r0 will be.

But the verifier still incorrectly tracks the bounds of r0, and assumes it's 23. Loading:

    #include <linux/bpf.h>
    #include <bpf/bpf_helpers.h>

    struct {
            __uint(type, BPF_MAP_TYPE_PROG_ARRAY);
            __uint(max_entries, 1);
            __uint(key_size, sizeof(__u32));
            __uint(value_size, sizeof(__u32));
    } tail_call_map SEC(".maps");

    static __attribute__((noinline)) int callee(struct xdp_md *ctx)
    {
            bpf_tail_call(ctx, &tail_call_map, 0);

            int ret;
            asm volatile("%0 = 23" : "=r"(ret));
            return ret;
    }

    static SEC("xdp") int caller(struct xdp_md *ctx)
    {
            int res = callee(ctx);
            if (res == 23) {
                    return XDP_PASS;
            }
            return XDP_DROP;
    }

The verifier logs:

    func#0 @0
    func#1 @6
    0: R1=ctx() R10=fp0
    ; int res = callee(ctx); @ test.c:24
    0: (85) call pc+5
    caller:
     R10=fp0
    callee:
     frame1: R1=ctx() R10=fp0
    6: frame1: R1=ctx() R10=fp0
    ; bpf_tail_call(ctx, &tail_call_map, 0); @ test.c:15
    6: (18) r2 = 0xffff8a9c82a75800       ; frame1: R2_w=map_ptr(map=tail_call_map,ks=4,vs=4)
    8: (b4) w3 = 0                        ; frame1: R3_w=0
    9: (85) call bpf_tail_call#12
    10: frame1:
    ; asm volatile("%0 = 23" : "=r"(ret)); @ test.c:18
    10: (b7) r0 = 23                      ; frame1: R0_w=23
    ; return ret; @ test.c:19
    11: (95) exit
    returning from callee:
     frame1: R0_w=23 R10=fp0
    to caller at 1:
     R0_w=23 R10=fp0

    from 11 to 1: R0_w=23 R10=fp0
    ; int res = callee(ctx); @ test.c:24
    1: (bc) w1 = w0                       ; R0_w=23 R1_w=23
    2: (b4) w0 = 2                        ; R0=2
    ;  @ test.c:0
    3: (16) if w1 == 0x17 goto pc+1
    3: R1=23
    ; } @ test.c:29
    5: (95) exit
    processed 10 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1

It still prunes the res != 23 branch, skipping over instruction 4. But the tail called program can return any value.

Aside from pruning incorrect branches, this can also be used to read and write arbitrary memory by using r0 as a index.

The added selftest fails without the fix:

#187/p calls: call with nested tail_call r0 bounds FAIL Unexpected success to load

Fixes e411901c0b77 ("bpf: allow for tailcalls in BPF subprograms for x64 JIT")
---
 kernel/bpf/verifier.c                        |  3 ++
 tools/testing/selftests/bpf/verifier/calls.c | 35 ++++++++++++++++++++
 2 files changed, 38 insertions(+)
kernel/bpf/verifier.c +3 -0
index c2e5d0e6e3d0..0ef3a3ce695a 100644
@@ -10359,6 +10359,9 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 				*insn_idx, callee->callsite);
 			return -EFAULT;
 		}
+	} else if (env->subprog_info[state->frame[state->curframe]->subprogno].has_tail_call) {
+		/* if tailcall succeeds, r0 could hold anything */
+		__mark_reg_unknown(env, &caller->regs[BPF_REG_0]);
 	} else {
 		/* return to the caller whatever r0 had in the callee */
 		caller->regs[BPF_REG_0] = *r0;
tools/testing/selftests/bpf/verifier/calls.c +35 -0
index 7afc2619ab14..1c6266deec7a 100644
@@ -1340,6 +1340,41 @@
 	.prog_type = BPF_PROG_TYPE_XDP,
 	.result = ACCEPT,
 },
+{
+	"calls: call with nested tail_call r0 bounds",
+	.insns = {
+	/* main prog */
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 4),
+	/* we shouldn't be able to index packet with r0, it could have any value */
+	BPF_LDX_MEM(BPF_W, BPF_REG_7, BPF_REG_6, offsetof(struct xdp_md, data)),
+	BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_0),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+
+	/* subprog */
+	BPF_LD_MAP_FD(BPF_REG_2, 0),
+	BPF_MOV64_IMM(BPF_REG_3, 1),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_tail_call),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.prog_type = BPF_PROG_TYPE_XDP,
+	.errstr = "math between pkt pointer and register with unbounded min value",
+	.result = REJECT,
+	.fixup_prog1 = { 6 },
+	.func_info = { { 0, 4 }, { 6, 4 } },
+	.func_info_cnt = 2,
+	.btf_strings = "\0int\0ctx\0main\0",
+	.btf_types = {
+		/* 1: int   */ BTF_TYPE_INT_ENC(1, BTF_INT_SIGNED, 0, 32, 4),
+		/* 2: void* */ BTF_PTR_ENC(0),
+		/* 3: int __(void*) */ BTF_FUNC_PROTO_ENC(1, 1),
+			BTF_FUNC_PROTO_ARG_ENC(5, 2),
+		/* 4 */ BTF_FUNC_ENC(9, 3),
+	BTF_END_RAW
+	},
+},
 {
 	"calls: ambiguous return value",
 	.insns = {
Signature · 1 line
2.34.1
#1 lore raw
Quoted 157 lines · Arthur Fabre

When making BPF to BPF calls, the verifier propagates register bounds info for r0 from the callee to the caller.

For example loading:

    #include <linux/bpf.h>
    #include <bpf/bpf_helpers.h>

    static __attribute__((noinline)) int callee(struct xdp_md *ctx)
    {
            int ret;
            asm volatile("%0 = 23" : "=r"(ret));
            return ret;
    }

    static SEC("xdp") int caller(struct xdp_md *ctx)
    {
            int res = callee(ctx);
            if (res == 23) {
                    return XDP_PASS;
            }
            return XDP_DROP;
    }

The verifier logs:

    func#0 @0
    func#1 @6
    0: R1=ctx() R10=fp0
    ; int res = callee(ctx); @ test.c:15
    0: (85) call pc+5
    caller:
     R10=fp0
    callee:
     frame1: R1=ctx() R10=fp0
    6: frame1: R1=ctx() R10=fp0
    ; asm volatile("%0 = 23" : "=r"(ret)); @ test.c:9
    6: (b7) r0 = 23                       ; frame1: R0_w=23
    ; return ret; @ test.c:10
    7: (95) exit
    returning from callee:
     frame1: R0_w=23 R1=ctx() R10=fp0
    to caller at 1:
     R0_w=23 R10=fp0

    from 7 to 1: R0_w=23 R10=fp0
    ; int res = callee(ctx); @ test.c:15
    1: (bc) w1 = w0                       ; R0_w=23 R1_w=23
    2: (b4) w0 = 2                        ; R0_w=2
    ;  @ test.c:0
    3: (16) if w1 == 0x17 goto pc+1
    3: R1_w=23
    ; } @ test.c:20
    5: (95) exit
    processed 7 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0

And correctly tracks R0_w=23 from the callee through to the caller. This lets it completely prune the res != 23 branch, skipping over instruction 4.

But this isn't sound if the callee makes a bpf_tail_call(): if the tail call succeeds, callee() will directly return whatever the tail called program returns. We can't know what the bounds of r0 will be.

But the verifier still incorrectly tracks the bounds of r0, and assumes it's 23. Loading:

    #include <linux/bpf.h>
    #include <bpf/bpf_helpers.h>

    struct {
            __uint(type, BPF_MAP_TYPE_PROG_ARRAY);
            __uint(max_entries, 1);
            __uint(key_size, sizeof(__u32));
            __uint(value_size, sizeof(__u32));
    } tail_call_map SEC(".maps");

    static __attribute__((noinline)) int callee(struct xdp_md *ctx)
    {
            bpf_tail_call(ctx, &tail_call_map, 0);

            int ret;
            asm volatile("%0 = 23" : "=r"(ret));
            return ret;
    }

    static SEC("xdp") int caller(struct xdp_md *ctx)
    {
            int res = callee(ctx);
            if (res == 23) {
                    return XDP_PASS;
            }
            return XDP_DROP;
    }

The verifier logs:

    func#0 @0
    func#1 @6
    0: R1=ctx() R10=fp0
    ; int res = callee(ctx); @ test.c:24
    0: (85) call pc+5
    caller:
     R10=fp0
    callee:
     frame1: R1=ctx() R10=fp0
    6: frame1: R1=ctx() R10=fp0
    ; bpf_tail_call(ctx, &tail_call_map, 0); @ test.c:15
    6: (18) r2 = 0xffff8a9c82a75800       ; frame1: R2_w=map_ptr(map=tail_call_map,ks=4,vs=4)
    8: (b4) w3 = 0                        ; frame1: R3_w=0
    9: (85) call bpf_tail_call#12
    10: frame1:
    ; asm volatile("%0 = 23" : "=r"(ret)); @ test.c:18
    10: (b7) r0 = 23                      ; frame1: R0_w=23
    ; return ret; @ test.c:19
    11: (95) exit
    returning from callee:
     frame1: R0_w=23 R10=fp0
    to caller at 1:
     R0_w=23 R10=fp0

    from 11 to 1: R0_w=23 R10=fp0
    ; int res = callee(ctx); @ test.c:24
    1: (bc) w1 = w0                       ; R0_w=23 R1_w=23
    2: (b4) w0 = 2                        ; R0=2
    ;  @ test.c:0
    3: (16) if w1 == 0x17 goto pc+1
    3: R1=23
    ; } @ test.c:29
    5: (95) exit
    processed 10 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1

It still prunes the res != 23 branch, skipping over instruction 4. But the tail called program can return any value.

Aside from pruning incorrect branches, this can also be used to read and write arbitrary memory by using r0 as a index.

The added selftest fails without the fix:

#187/p calls: call with nested tail_call r0 bounds FAIL Unexpected success to load

Fixes e411901c0b77 ("bpf: allow for tailcalls in BPF subprograms for x64 JIT")
---
 kernel/bpf/verifier.c                        |  3 ++
 tools/testing/selftests/bpf/verifier/calls.c | 35 ++++++++++++++++++++
 2 files changed, 38 insertions(+)
kernel/bpf/verifier.c +0 -0
index c2e5d0e6e3d0..0ef3a3ce695a 100644

kernel/bpf/verifier.c static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) · line 10364

Quoted 6 lines
kernel/bpf/verifier.c +3 -0
@@ -10359,6 +10359,9 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
                                *insn_idx, callee->callsite);
                        return -EFAULT;
                }
+       } else if (env->subprog_info[state->frame[state->curframe]->subprogno].has_tail_call) {
+               /* if tailcall succeeds, r0 could hold anything */
+               __mark_reg_unknown(env, &caller->regs[BPF_REG_0]);

The fix makes sense.
The has_ld_abs has the same issue.
Pls include it as well.

Quoted 23 lines
kernel/bpf/verifier.c +0 -0
        } else {
                /* return to the caller whatever r0 had in the callee */
                caller->regs[BPF_REG_0] = *r0;
tools/testing/selftests/bpf/verifier/calls.c +12 -0
index 7afc2619ab14..1c6266deec7a 100644
@@ -1340,6 +1340,41 @@
        .prog_type = BPF_PROG_TYPE_XDP,
        .result = ACCEPT,
 },
+{
+       "calls: call with nested tail_call r0 bounds",
+       .insns = {
+       /* main prog */
+       BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 4),
+       /* we shouldn't be able to index packet with r0, it could have any value */
+       BPF_LDX_MEM(BPF_W, BPF_REG_7, BPF_REG_6, offsetof(struct xdp_md, data)),
+       BPF_ALU64_REG(BPF_ADD, BPF_REG_7, BPF_REG_0),
+       BPF_MOV64_IMM(BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+

tools/testing/selftests/bpf/verifier/calls.c line 1364

Quoted 10 lines
tools/testing/selftests/bpf/verifier/calls.c +10 -0
+       /* subprog */
+       BPF_LD_MAP_FD(BPF_REG_2, 0),
+       BPF_MOV64_IMM(BPF_REG_3, 1),
+       BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_tail_call),
+       BPF_MOV64_IMM(BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       },
+       .prog_type = BPF_PROG_TYPE_XDP,
+       .errstr = "math between pkt pointer and register with unbounded min value",
+       .result = REJECT,

Pls split sefltest into separate patch and use inline asm instead of macros.
See verifier_map_ptr_mixing.c or verifier_unpriv.c

pw-bot: cr