Skip to contentSkip to conversation

bpf: fix tracking of stack size for var-off access

PATCH In review Andrei Matei 4 participants 8 messages Nov 13, 2023 – Nov 22, 2023

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

PATCH 1/1 bpf: fix tracking of stack size for var-off access

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.

---
 kernel/bpf/verifier.c | 47 ++++++++++++++++++++++---------------------
 1 file changed, 24 insertions(+), 23 deletions(-)
kernel/bpf/verifier.c +24 -23
index a2267d5ed14e..303a3572b169 100644
@@ -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;
+}
+
+/* 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;
-
 		if (t == BPF_READ)
 			err = check_stack_read(env, regno, off, size,
 					       value_regno);
Signature · 1 line
2.39.2
#1 lore raw
Quoted 16 lines · Andrei Matei

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.

Quoted 9 lines

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?

Quoted 21 lines
---
 kernel/bpf/verifier.c | 47 ++++++++++++++++++++++---------------------
 1 file changed, 24 insertions(+), 23 deletions(-)
kernel/bpf/verifier.c +3 -1
index a2267d5ed14e..303a3572b169 100644
@@ -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)

kernel/bpf/verifier.c static int resize_reference_state(struct bpf_func_state *state, size_t n) · line 1684

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+{
+       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?

Quoted 61 lines
kernel/bpf/verifier.c +11 -17
+
+/* 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);

kernel/bpf/verifier.c static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn · line 6972

Quoted 8 lines
kernel/bpf/verifier.c +0 -5
@@ -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

Quoted 7 lines
kernel/bpf/verifier.c +0 -1
                if (t == BPF_READ)
                        err = check_stack_read(env, regno, off, size,
                                               value_regno);
--

2.39.2

#2 lore raw
Quoted 12 lines · Andrii Nakryiko

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.

Agree. The following cases are currently confusing to me.

The verifier accepts the following program, which goes from #4 to #8 and directly read the stack at runtime without any previous write:
func#0 @0
0: R1=ctx() R10=fp0

0: (bf) r6 = r10                      ; R6_w=fp0 R10=fp0
1: (85) call bpf_get_prandom_u32#7    ; R0_w=scalar()
2: (bf) r3 = r0                       ; R0_w=scalar(id=1) R3_w=scalar(id=1)
3: (bf) r8 = r0                       ; R0_w=scalar(id=1) R8_w=scalar(id=1)
4: (4e) if w0 & w3 goto pc+3          ; R0_w=scalar(id=1) R3_w=scalar(id=1)
5: (63) *(u32 *)(r6 -196) = r3        ; R3_w=scalar(id=1) R6_w=fp0

fp-200=mmmm????
6: (18) r7 = 0x19 ; R7=25
8: (61) r7 = *(u32 *)(r6 -200) ; R6=fp0
R7_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) fp-200=mmmm????
9: (95) exit

from 4 to 8: safe
verification time 358 usec
stack depth 200
processed 10 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1

The state is pruned, because of this:
static bool stacksafe(...)

         ....
         if (env->allow_uninit_stack &&
             old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC)
             continue;

Yet, the sample direct read would be rejected:

func#0 @0
0: R1=ctx() R10=fp0
0: (bf) r6 = r10 ; R6_w=fp0 R10=fp0
1: (61) r7 = *(u32 *)(r6 -200)
invalid read from stack R6 off=-200 size=4

Eduard, you added support for reading uninit slots, should we also add something like the following:

kernel/bpf/verifier.c +1 -1
index 8c2d31aa3d31..aa861d2da240 100644
@@ -6446,7 +6446,7 @@ static int check_stack_slot_within_bounds(int off,
 {
        int min_valid_off;
 
-       if (t == BPF_WRITE)
+       if (t == BPF_WRITE || env->allow_uninit_stack)
                min_valid_off = -MAX_BPF_STACK;
        else
                min_valid_off = -state->allocated_stack;
#3 lore raw
Quoted 16 lines · Hao Sun
Quoted 12 lines · Andrii Nakryiko

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.

Quoted 1 line

Agree. The following cases are currently confusing to me.

Like Hao, I'm also confused about when reads from unitialized stack slots are supposed to be allowed and when they're not. For example, the "uninitialized stack1" test ([0]) seems to check that at least some type of uninitialized read is not permitted. The reason why the respective access is rejected and this test currently passes is the following check in check_stack_range_initialized:
[1]. We summarily reject the access to slots beyond state->allocated_stack. If we were to not reject them there, and instead treat the slots as STACK_INVALID, then the test's access would be allowed just below, through the combination of env->allow_uninit_stack and clobber.

So, assuming that this tests (and a few others) are sane, Andrii's suggestion of calling grow_stack_state()/update_stack_depth() in check_stack_access_within_bounds() does not immediately work: doing so would change
the behavior in check_stack_range_initialized() and allow the access.

On the other hand, perhaps the test is not sane and the access should be permitted, in the spirit of allowing reads of uninitialized stack? Perhaps the different treatment of slots beyond state->allocated_stack and STACK_INVALID slots is not intentional. Though, I am fairly confused about the idea of allowing such reads in general - don't they allow leaking of kernel memory from the uninit stack to user space? Even if restricted to root, is the leak ok?

To also state the obvious - I'm happy to continue working on this patch and fix a bug I've caused. However, if someone who actually knows the deal wants to take over, I'm certainly not attached to anything :).

[0] https://github.com/torvalds/linux/blob/98b1cc82c4affc16f5598d4fa14b1858671b2263/tools/testing/selftests/bpf/progs/verifier_basic_stack.c#L28-L44
[1] https://github.com/torvalds/linux/blob/98b1cc82c4affc16f5598d4fa14b1858671b2263/kernel/bpf/verifier.c#L7280

Quoted 55 lines

The verifier accepts the following program, which goes from #4 to #8 and directly read the stack at runtime without any previous write:
func#0 @0
0: R1=ctx() R10=fp0

0: (bf) r6 = r10                      ; R6_w=fp0 R10=fp0
1: (85) call bpf_get_prandom_u32#7    ; R0_w=scalar()
2: (bf) r3 = r0                       ; R0_w=scalar(id=1) R3_w=scalar(id=1)
3: (bf) r8 = r0                       ; R0_w=scalar(id=1) R8_w=scalar(id=1)
4: (4e) if w0 & w3 goto pc+3          ; R0_w=scalar(id=1) R3_w=scalar(id=1)
5: (63) *(u32 *)(r6 -196) = r3        ; R3_w=scalar(id=1) R6_w=fp0

fp-200=mmmm????
6: (18) r7 = 0x19 ; R7=25
8: (61) r7 = *(u32 *)(r6 -200) ; R6=fp0
R7_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) fp-200=mmmm????
9: (95) exit

from 4 to 8: safe
verification time 358 usec
stack depth 200
processed 10 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1

The state is pruned, because of this:
static bool stacksafe(...)

         ....
         if (env->allow_uninit_stack &&
             old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC)
             continue;

Yet, the sample direct read would be rejected:

func#0 @0
0: R1=ctx() R10=fp0
0: (bf) r6 = r10 ; R6_w=fp0 R10=fp0
1: (61) r7 = *(u32 *)(r6 -200)
invalid read from stack R6 off=-200 size=4

Eduard, you added support for reading uninit slots, should we also add something like the following:

kernel/bpf/verifier.c +1 -1
index 8c2d31aa3d31..aa861d2da240 100644
@@ -6446,7 +6446,7 @@ static int check_stack_slot_within_bounds(int off,
 {
        int min_valid_off;
 
-       if (t == BPF_WRITE)
+       if (t == BPF_WRITE || env->allow_uninit_stack)
                min_valid_off = -MAX_BPF_STACK;
        else
                min_valid_off = -state->allocated_stack;
#4 lore raw
Quoted 20 lines · Andrei Matei
Quoted 16 lines · Hao Sun
Quoted 12 lines · Andrii Nakryiko

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.

Quoted 1 line

Agree. The following cases are currently confusing to me.

Quoted 9 lines

Like Hao, I'm also confused about when reads from unitialized stack slots are supposed to be allowed and when they're not. For example, the "uninitialized stack1" test ([0]) seems to check that at least some type of uninitialized read is not permitted. The reason why the respective access is rejected and this test currently passes is the following check in check_stack_range_initialized:
[1]. We summarily reject the access to slots beyond state->allocated_stack. If we were to not reject them there, and instead treat the slots as STACK_INVALID, then the test's access would be allowed just below, through the combination of env->allow_uninit_stack and clobber.

And that seems like a consistent and sane behavior if bpf_allow_uninit_stack() is true, so I vote for fixing the test and make the logic consistent.

Quoted 10 lines

So, assuming that this tests (and a few others) are sane, Andrii's suggestion of calling grow_stack_state()/update_stack_depth() in check_stack_access_within_bounds() does not immediately work: doing so would change
the behavior in check_stack_range_initialized() and allow the access.

On the other hand, perhaps the test is not sane and the access should be permitted, in the spirit of allowing reads of uninitialized stack? Perhaps the different treatment of slots beyond state->allocated_stack and STACK_INVALID

yes, I think this divergence is not intentional, but maybe Eduard remembers some other quirks and why it is what it is, let's see.

Quoted 3 lines

slots is not intentional. Though, I am fairly confused about the idea of allowing such reads in general - don't they allow leaking of kernel memory from the uninit stack to user space? Even if restricted to root, is the leak ok?

This is guarded by bpf_allow_uninit_stack(), which check CAP_PERFMON. Once BPF program has CAP_PERFMON, it can do bpf_probe_read_kernel() and generally can leak whatever kernel memory. So that's why STACK_INVALID is allowed to be read in such case. There is also bpf_allow_ptr_leaks() which also checks CAP_PERFMON.

Quoted 4 lines

To also state the obvious - I'm happy to continue working on this patch and fix a bug I've caused. However, if someone who actually knows the deal wants to take over, I'm certainly not attached to anything :).

It would be great if you can finish this, absolutely! Thanks!

Quoted 55 lines

[0] https://github.com/torvalds/linux/blob/98b1cc82c4affc16f5598d4fa14b1858671b2263/tools/testing/selftests/bpf/progs/verifier_basic_stack.c#L28-L44
[1] https://github.com/torvalds/linux/blob/98b1cc82c4affc16f5598d4fa14b1858671b2263/kernel/bpf/verifier.c#L7280

Quoted 50 lines

The verifier accepts the following program, which goes from #4 to #8 and directly read the stack at runtime without any previous write:
func#0 @0
0: R1=ctx() R10=fp0

0: (bf) r6 = r10                      ; R6_w=fp0 R10=fp0
1: (85) call bpf_get_prandom_u32#7    ; R0_w=scalar()
2: (bf) r3 = r0                       ; R0_w=scalar(id=1) R3_w=scalar(id=1)
3: (bf) r8 = r0                       ; R0_w=scalar(id=1) R8_w=scalar(id=1)
4: (4e) if w0 & w3 goto pc+3          ; R0_w=scalar(id=1) R3_w=scalar(id=1)
5: (63) *(u32 *)(r6 -196) = r3        ; R3_w=scalar(id=1) R6_w=fp0

fp-200=mmmm????
6: (18) r7 = 0x19 ; R7=25
8: (61) r7 = *(u32 *)(r6 -200) ; R6=fp0
R7_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) fp-200=mmmm????
9: (95) exit

from 4 to 8: safe
verification time 358 usec
stack depth 200
processed 10 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1

The state is pruned, because of this:
static bool stacksafe(...)

         ....
         if (env->allow_uninit_stack &&
             old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_MISC)
             continue;

Yet, the sample direct read would be rejected:

func#0 @0
0: R1=ctx() R10=fp0
0: (bf) r6 = r10 ; R6_w=fp0 R10=fp0
1: (61) r7 = *(u32 *)(r6 -200)
invalid read from stack R6 off=-200 size=4

Eduard, you added support for reading uninit slots, should we also add something like the following:

kernel/bpf/verifier.c +0 -0
index 8c2d31aa3d31..aa861d2da240 100644
@@ -6446,7 +6446,7 @@ static int check_stack_slot_within_bounds(int off,
 {
        int min_valid_off;
 
Quoted 5 lines

kernel/bpf/verifier.c static int check_stack_slot_within_bounds(int off, · line 6452

Quoted 5 lines
kernel/bpf/verifier.c +1 -1
-       if (t == BPF_WRITE)
+       if (t == BPF_WRITE || env->allow_uninit_stack)
                min_valid_off = -MAX_BPF_STACK;
        else
                min_valid_off = -state->allocated_stack;

as I mentioned above, yes, I think the behavior should be consistent and such accesses should be allowed, just as if it was STACK_INVALID

maintainer
#5 lore raw

On Tue, 2023-11-21 at 13:55 -0800, Andrii Nakryiko wrote:
[...]

Quoted 6 lines
Quoted 6 lines

So, assuming that this tests (and a few others) are sane, Andrii's suggestion of calling grow_stack_state()/update_stack_depth() in check_stack_access_within_bounds() does not immediately work: doing so would change
the behavior in check_stack_range_initialized() and allow the access.

Quoted 6 lines
Quoted 3 lines

On the other hand, perhaps the test is not sane and the access should be permitted, in the spirit of allowing reads of uninitialized stack? Perhaps the different treatment of slots beyond state->allocated_stack and STACK_INVALID

yes, I think this divergence is not intentional, but maybe Eduard remembers some other quirks and why it is what it is, let's see.

Yes, this is probably an overlook from my side.
I should have allowed reads beyond allocated stack in this case when doing changes for STACK_INVALID.
Sorry for delayed response.

[...]

maintainer
#6 lore raw
In reply to Hao Sun

On Tue, 2023-11-21 at 18:16 +0100, Hao Sun wrote:
[...]

Quoted 16 lines

Yet, the sample direct read would be rejected:

func#0 @0
0: R1=ctx() R10=fp0
0: (bf) r6 = r10 ; R6_w=fp0 R10=fp0
1: (61) r7 = *(u32 *)(r6 -200)
invalid read from stack R6 off=-200 size=4

Eduard, you added support for reading uninit slots, should we also add something like the following:

kernel/bpf/verifier.c +0 -0
index 8c2d31aa3d31..aa861d2da240 100644

kernel/bpf/verifier.c static int check_stack_slot_within_bounds(int off, · line 6452

Quoted 8 lines
kernel/bpf/verifier.c +1 -1
@@ -6446,7 +6446,7 @@ static int check_stack_slot_within_bounds(int off,
 {
        int min_valid_off;
 
-       if (t == BPF_WRITE)
+       if (t == BPF_WRITE || env->allow_uninit_stack)
                min_valid_off = -MAX_BPF_STACK;
        else
                min_valid_off = -state->allocated_stack;

I agree with your logic and this change seems reasonable. Sorry for delayed response.

#7 lore raw
In reply to Andrii Nakryiko
Quoted 28 lines · Andrii Nakryiko
Quoted 16 lines · Andrei Matei

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.

Quoted 9 lines

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.

Quoted 4 lines

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?

My intention was certainly not to change any verification behavior. I was relying on reads to uninit stack not being allowed regardless of the tracked stacked bounds; I now see that things don't work that way.