On Mon, Nov 13, 2023 at 3:51 PM Andrei Matei <andreimatei1@xxxxxxxxx> wrote:
>
> Before this patch, writes to the stack using registers containing a
> variable offset (as opposed to registers with fixed, known values) were
> not properly contributing to the function's needed stack size. As a
> result, it was possible for a program to verify, but then to attempt to
> read out-of-bounds data at runtime because a too small stack had been
> allocated for it.
>
> Each function tracks the size of the stack it needs in
> bpf_subprog_info.stack_depth, which is maintained by
> update_stack_depth(). For regular memory accesses, check_mem_access()
> was calling update_state_depth() but it was passing in only the fixed
> part of the offset register, ignoring the variable offset. This was
> incorrect; the minimum possible value of that register should be used
> instead.
>
> This patch fixes it by pushing down the update_stack_depth() call into
> grow_stack_depth(), which then correctly uses the registers lower bound.
> grow_stack_depth() is responsible for tracking the maximum stack size
> for the current verifier state, so it seems like a good idea to couple
> it with also updating the per-function high-water mark. As a result of
> this re-arrangement, update_stack_depth() is no longer needlessly called
> for reads; it is now called only for writes (plus other cases like
> helper memory access). I think this is a good thing, as reads cannot
> possibly grow the needed stack.
I'm going to disagree. I think we should calculate max stack size both
on reads and writes. I'm not sure why it's ok for a BPF program to
access a stack with some big offset, but the BPF verifier not
rejecting this. What do I miss?
>
> Reported-by: Hao Sun <sunhao.th@xxxxxxxxx>
> Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
> Closes: https://lore.kernel.org/bpf/CABWLsev9g8UP_c3a=1qbuZUi20tGoUXoU07FPf-5FLvhOKOY+Q@xxxxxxxxxxxxxx/
> Signed-off-by: Andrei Matei <andreimatei1@xxxxxxxxx>
> ---
> kernel/bpf/verifier.c | 47 ++++++++++++++++++++++---------------------
> 1 file changed, 24 insertions(+), 23 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index a2267d5ed14e..303a3572b169 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1669,8 +1669,29 @@ static int resize_reference_state(struct bpf_func_state *state, size_t n)
> return 0;
> }
>
> -static int grow_stack_state(struct bpf_func_state *state, int size)
> +static int update_stack_depth(struct bpf_verifier_env *env,
> + const struct bpf_func_state *func,
> + int off)
> +{
> + u16 stack = env->subprog_info[func->subprogno].stack_depth;
> +
> + if (stack >= -off)
> + return 0;
> +
> + /* update known max for given subprogram */
> + env->subprog_info[func->subprogno].stack_depth = -off;
> + return 0;
> +}
given this is targeting bpf tree and will probably be backported to
stable kernels, let's minimize code movement. Can you just add
update_stack_depth forward declaration here instead?
> +
> +/* Possibly update state->allocated_stack to be at least size bytes. Also
> + * possibly update the function's high-water mark in its bpf_subprog_info.
> + */
> +static int grow_stack_state(struct bpf_verifier_env *env, struct bpf_func_state *state, int size)
> {
> + int err = update_stack_depth(env, state, -size);
> + if (err) {
> + return err;
> + }
> size_t old_n = state->allocated_stack / BPF_REG_SIZE, n = size / BPF_REG_SIZE;
>
> if (old_n >= n)
> @@ -4638,7 +4659,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
> struct bpf_reg_state *reg = NULL;
> u32 dst_reg = insn->dst_reg;
>
> - err = grow_stack_state(state, round_up(slot + 1, BPF_REG_SIZE));
> + err = grow_stack_state(env, state, round_up(slot + 1, BPF_REG_SIZE));
> if (err)
> return err;
> /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
> @@ -4796,7 +4817,7 @@ static int check_stack_write_var_off(struct bpf_verifier_env *env,
> (!value_reg && is_bpf_st_mem(insn) && insn->imm == 0))
> writing_zero = true;
>
> - err = grow_stack_state(state, round_up(-min_off, BPF_REG_SIZE));
> + err = grow_stack_state(env, state, round_up(-min_off, BPF_REG_SIZE));
> if (err)
> return err;
>
> @@ -5928,20 +5949,6 @@ static int check_ptr_alignment(struct bpf_verifier_env *env,
> strict);
> }
>
> -static int update_stack_depth(struct bpf_verifier_env *env,
> - const struct bpf_func_state *func,
> - int off)
> -{
> - u16 stack = env->subprog_info[func->subprogno].stack_depth;
> -
> - if (stack >= -off)
> - return 0;
> -
> - /* update known max for given subprogram */
> - env->subprog_info[func->subprogno].stack_depth = -off;
> - return 0;
> -}
> -
> /* starting from main bpf function walk all instructions of the function
> * and recursively walk all callees that given function can call.
> * Ignore jump and exit insns.
> @@ -6822,7 +6829,6 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
> {
> struct bpf_reg_state *regs = cur_regs(env);
> struct bpf_reg_state *reg = regs + regno;
> - struct bpf_func_state *state;
> int size, err = 0;
>
> size = bpf_size_to_bytes(bpf_size);
> @@ -6965,11 +6971,6 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
> if (err)
> return err;
>
> - state = func(env, reg);
> - err = update_stack_depth(env, state, off);
> - if (err)
> - return err;
> -
It *feels* like this stack depth update *and* growing allocated stack
slots should happen somewhere in check_stack_access_within_bounds() or
right after it. It shouldn't matter whether we read or write to the
stack slot: either way that slot becomes part of the verifier state
that we should take into account during state comparison. Eduard not
so long ago added a change that allows reading STACK_INVALID slots, so
it's completely valid to read something that was never written to (and
so grow_stack_state() wasn't called for that slot, as it is
implemented right now). So I think we should fix that.
Let's also add a test that will trigger this situation with both
direct stack slot read into register and through helper?
cc'ing Eduard just in case I'm missing some subtle detail here
> if (t == BPF_READ)
> err = check_stack_read(env, regno, off, size,
> value_regno);
> --
> 2.39.2
>
>
