[bpf,v2,1/2] bpf: Don't trust r0 bounds after BPF to BPF calls with abnormal returns

Commit Message

Arthur Fabre Dec. 13, 2024, 9:27 p.m. UTC

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 can return "abnormally" before an
exit instruction:
- If LD_ABS or LD_IND try to access data beyond the end of the packet,
  the callee returns 0 directly.
- If a tail_call succeeds, the return value of the tail called program
  will be returned directly.
We can't know what the bounds of r0 will be.

The verifier still incorrectly tracks the bounds of r0 in these cases. 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.

Fixes: e411901c0b77 ("bpf: allow for tailcalls in BPF subprograms for x64 JIT")
Signed-off-by: Arthur Fabre <[e-mail]>
Cc: [e-mail]
---
 kernel/bpf/verifier.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

Comments

Eduard Zingerman Dec. 13, 2024, 11:52 p.m. UTC | #1

On Fri, 2024-12-13 at 22:27 +0100, Arthur Fabre wrote:
> 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 can return "abnormally" before an
> exit instruction:
> - If LD_ABS or LD_IND try to access data beyond the end of the packet,
>   the callee returns 0 directly.
> - If a tail_call succeeds, the return value of the tail called program
>   will be returned directly.
> We can't know what the bounds of r0 will be.
> 
> The verifier still incorrectly tracks the bounds of r0 in these cases. 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.
> 
> Fixes: e411901c0b77 ("bpf: allow for tailcalls in BPF subprograms for x64 JIT")
> Signed-off-by: Arthur Fabre <[e-mail]>
> Cc: [e-mail]
> ---

Acked-by: Eduard Zingerman <[e-mail]>

[...]

> @@ -10359,6 +10364,10 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
>  				*insn_idx, callee->callsite);
>  			return -EFAULT;
>  		}
> +	} else if (has_abnormal_return(
> +		    &env->subprog_info[state->frame[state->curframe]->subprogno])) {
                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                       Nit: this is 'callee'

> +		/* callee can return before exit instruction, 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;
> @@ -16881,17 +16890,14 @@ static int check_cfg(struct bpf_verifier_env *env)
>  	return ret;
>  }
>  
> +

Nit: this empty line is not needed.

[...]

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c2e5d0e6e3d0..76c0008f6914 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -10314,6 +10314,11 @@  static bool retval_range_within(struct bpf_retval_range range, const struct bpf_
 		return range.minval <= reg->smin_value && reg->smax_value <= range.maxval;
 }
 
+static bool has_abnormal_return(struct bpf_subprog_info *subprog_info)
+{
+	return subprog_info->has_ld_abs || subprog_info->has_tail_call;
+}
+
 static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 {
 	struct bpf_verifier_state *state = env->cur_state, *prev_st;
@@ -10359,6 +10364,10 @@  static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 				*insn_idx, callee->callsite);
 			return -EFAULT;
 		}
+	} else if (has_abnormal_return(
+		    &env->subprog_info[state->frame[state->curframe]->subprogno])) {
+		/* callee can return before exit instruction, 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;
@@ -16881,17 +16890,14 @@  static int check_cfg(struct bpf_verifier_env *env)
 	return ret;
 }
 
+
 static int check_abnormal_return(struct bpf_verifier_env *env)
 {
 	int i;
 
 	for (i = 1; i < env->subprog_cnt; i++) {
-		if (env->subprog_info[i].has_ld_abs) {
-			verbose(env, "LD_ABS is not allowed in subprogs without BTF\n");
-			return -EINVAL;
-		}
-		if (env->subprog_info[i].has_tail_call) {
-			verbose(env, "tail_call is not allowed in subprogs without BTF\n");
+		if (has_abnormal_return(&env->subprog_info[i])) {
+			verbose(env, "LD_ABS/tail_call is not allowed in subprogs without BTF\n");
 			return -EINVAL;
 		}
 	}