[PATCH bpf v3 0/2] bpf: fix verification of indirect var-off stack access

[PATCH bpf v3 0/2] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

V2 to V3:
  - simplify checks for max_off (don't call
    check_stack_slot_within_bounds for it)
  - append a commit to protect against overflow in the addition of the
    register and the offset

V1 to V2:
  - fix max_off calculation for access size = 0

Andrei Matei (2):
  bpf: fix verification of indirect var-off stack access
  bpf: guard stack limits against 32bit overflow

 kernel/bpf/verifier.c | 20 +++++++-------------
 1 file changed, 7 insertions(+), 13 deletions(-)

-- 
2.39.2

[PATCH bpf v3 1/2] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

This patch fixes a bug around the verification of possibly-zero-sized
stack accesses. When the access was done through a var-offset stack
pointer, check_stack_access_within_bounds was incorrectly computing the
maximum-offset of a zero-sized read to be the same as the register's min
offset. Instead, we have to take in account the register's maximum
possible value.

The bug was allowing accesses to erroneously pass the
check_stack_access_within_bounds() checks, only to later crash in
check_stack_range_initialized() when all the possibly-affected stack
slots are iterated (this time with a correct max offset).
check_stack_range_initialized() is relying on
check_stack_access_within_bounds() for its accesses to the
stack-tracking vector to be within bounds; in the case of zero-sized
accesses, we were essentially only verifying that the lowest possible
slot was within bounds. We would crash when the max-offset of the stack
pointer was >= 0 (which shouldn't pass verification, and hopefully is
not something anyone's code attempts to do in practice).

Thanks Hao for reporting!

Reported-by: Hao Sun <sunhao.th@gmail.com>
Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/
Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
---
 kernel/bpf/verifier.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index af2819d5c8ee..29d39ebac196 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6804,10 +6804,7 @@ static int check_stack_access_within_bounds(
 
 	if (tnum_is_const(reg->var_off)) {
 		min_off = reg->var_off.value + off;
-		if (access_size > 0)
-			max_off = min_off + access_size - 1;
-		else
-			max_off = min_off;
+		max_off = min_off + access_size;
 	} else {
 		if (reg->smax_value >= BPF_MAX_VAR_OFF ||
 		    reg->smin_value <= -BPF_MAX_VAR_OFF) {
@@ -6816,15 +6813,12 @@ static int check_stack_access_within_bounds(
 			return -EACCES;
 		}
 		min_off = reg->smin_value + off;
-		if (access_size > 0)
-			max_off = reg->smax_value + off + access_size - 1;
-		else
-			max_off = min_off;
+		max_off = reg->smax_value + off + access_size;
 	}
 
 	err = check_stack_slot_within_bounds(min_off, state, type);
-	if (!err)
-		err = check_stack_slot_within_bounds(max_off, state, type);
+	if (!err && max_off > 0)
+		err = -EINVAL; /* out of stack access into non-negative offsets */
 
 	if (err) {
 		if (tnum_is_const(reg->var_off)) {
-- 
2.39.2

Re: [PATCH bpf v3 1/2] bpf: fix verification of indirect var-off stack access

[Eduard Zingerman]

On Tue, 2023-12-05 at 14:32 -0500, Andrei Matei wrote:
> This patch fixes a bug around the verification of possibly-zero-sized
> stack accesses. When the access was done through a var-offset stack
> pointer, check_stack_access_within_bounds was incorrectly computing the
> maximum-offset of a zero-sized read to be the same as the register's min
> offset. Instead, we have to take in account the register's maximum
> possible value.
> 
> The bug was allowing accesses to erroneously pass the
> check_stack_access_within_bounds() checks, only to later crash in
> check_stack_range_initialized() when all the possibly-affected stack
> slots are iterated (this time with a correct max offset).
> check_stack_range_initialized() is relying on
> check_stack_access_within_bounds() for its accesses to the
> stack-tracking vector to be within bounds; in the case of zero-sized
> accesses, we were essentially only verifying that the lowest possible
> slot was within bounds. We would crash when the max-offset of the stack
> pointer was >= 0 (which shouldn't pass verification, and hopefully is
> not something anyone's code attempts to do in practice).
> 
> Thanks Hao for reporting!
> 
> Reported-by: Hao Sun <sunhao.th@gmail.com>
> Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access")
> Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/
> Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
> ---

Seems good, thank you for fixing this.

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

[PATCH bpf v3 2/2] bpf: guard stack limits against 32bit overflow

[Andrei Matei]

This patch promotes the arithmetic around checking stack bounds to be
done in the 64-bit domain, instead of the current 32bit. The arithmetic
implies adding together a 64-bit register with a int offset. The
register was checked to be below 1<<29 when it was variable, but not
when it was fixed. The offset either comes from an instruction (in which
case it is 16 bit), from another register (in which case the caller
checked it to be below 1<<29 [1]), or from the size of an argument to a
kfunc (in which case it can be a u32 [2]). Between the register being
inconsistently checked to be below 1<<29, and the offset being up to an
u32, it appears that we were open to overflowing the `int`s which were
currently used for arithmetic.

[1] https://github.com/torvalds/linux/blob/815fb87b753055df2d9e50f6cd80eb10235fe3e9/kernel/bpf/verifier.c#L7494-L7498
[2] https://github.com/torvalds/linux/blob/815fb87b753055df2d9e50f6cd80eb10235fe3e9/kernel/bpf/verifier.c#L11904

Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
Reported-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
---
 kernel/bpf/verifier.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 29d39ebac196..ebebbb8feb17 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6761,7 +6761,7 @@ static int check_ptr_to_map_access(struct bpf_verifier_env *env,
  * The minimum valid offset is -MAX_BPF_STACK for writes, and
  * -state->allocated_stack for reads.
  */
-static int check_stack_slot_within_bounds(int off,
+static int check_stack_slot_within_bounds(s64 off,
 					  struct bpf_func_state *state,
 					  enum bpf_access_type t)
 {
@@ -6790,7 +6790,7 @@ static int check_stack_access_within_bounds(
 	struct bpf_reg_state *regs = cur_regs(env);
 	struct bpf_reg_state *reg = regs + regno;
 	struct bpf_func_state *state = func(env, reg);
-	int min_off, max_off;
+	s64 min_off, max_off;
 	int err;
 	char *err_extra;
 
@@ -6803,7 +6803,7 @@ static int check_stack_access_within_bounds(
 		err_extra = " write to";
 
 	if (tnum_is_const(reg->var_off)) {
-		min_off = reg->var_off.value + off;
+		min_off = (s64)reg->var_off.value + off;
 		max_off = min_off + access_size;
 	} else {
 		if (reg->smax_value >= BPF_MAX_VAR_OFF ||
-- 
2.39.2

Re: [PATCH bpf v3 0/2] bpf: fix verification of indirect var-off stack access

[Eduard Zingerman]

On Tue, 2023-12-05 at 14:32 -0500, Andrei Matei wrote:
> V2 to V3:
>   - simplify checks for max_off (don't call
>     check_stack_slot_within_bounds for it)
>   - append a commit to protect against overflow in the addition of the
>     register and the offset
> 
> V1 to V2:
>   - fix max_off calculation for access size = 0
> 
> Andrei Matei (2):
>   bpf: fix verification of indirect var-off stack access
>   bpf: guard stack limits against 32bit overflow
> 
>  kernel/bpf/verifier.c | 20 +++++++-------------
>  1 file changed, 7 insertions(+), 13 deletions(-)
> 

I think we also need a selftest, at-least for patch #1.

Re: [PATCH bpf v3 0/2] bpf: fix verification of indirect var-off stack access

[Alexei Starovoitov]

On Tue, Dec 5, 2023 at 3:35 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2023-12-05 at 14:32 -0500, Andrei Matei wrote:
> > V2 to V3:
> >   - simplify checks for max_off (don't call
> >     check_stack_slot_within_bounds for it)
> >   - append a commit to protect against overflow in the addition of the
> >     register and the offset
> >
> > V1 to V2:
> >   - fix max_off calculation for access size = 0
> >
> > Andrei Matei (2):
> >   bpf: fix verification of indirect var-off stack access
> >   bpf: guard stack limits against 32bit overflow
> >
> >  kernel/bpf/verifier.c | 20 +++++++-------------
> >  1 file changed, 7 insertions(+), 13 deletions(-)
> >
>
> I think we also need a selftest, at-least for patch #1.

Also pls target bpf-next.
It's a fix, but it's getting non obvious.
We only push absolutely necessary fixes to bpf tree.
Everything non trivial goes via bpf-next to prove itself.

Re: [PATCH bpf v3 0/2] bpf: fix verification of indirect var-off stack access

[Andrei Matei]

On Tue, Dec 5, 2023 at 6:35 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2023-12-05 at 14:32 -0500, Andrei Matei wrote:
> > V2 to V3:
> >   - simplify checks for max_off (don't call
> >     check_stack_slot_within_bounds for it)
> >   - append a commit to protect against overflow in the addition of the
> >     register and the offset
> >
> > V1 to V2:
> >   - fix max_off calculation for access size = 0
> >
> > Andrei Matei (2):
> >   bpf: fix verification of indirect var-off stack access
> >   bpf: guard stack limits against 32bit overflow
> >
> >  kernel/bpf/verifier.c | 20 +++++++-------------
> >  1 file changed, 7 insertions(+), 13 deletions(-)
> >
>
> I think we also need a selftest, at-least for patch #1.

Yeah... I was wondering in a message on v1 [1] if a test like what I had
prototyped there was warranted. I personally still think it's not because of
how many other variations of variable-offset stack access tests we already
have, and how random the zero-sized read case is (even though we had a bug in
there) - so protecting against this particular regression didn't seem worth it
to me. I'm now including the test in v4 but if you change your mind about it
when you see it in context, let me know and I'll take it out.

[1] https://lore.kernel.org/bpf/CABWLsevk47Xa1a+h0UK--94zEuxScrmyt0-D8YShq1UgvVvf5g@mail.gmail.com/

Re: [PATCH bpf v3 0/2] bpf: fix verification of indirect var-off stack access

[Eduard Zingerman]

On Wed, 2023-12-06 at 11:57 -0500, Andrei Matei wrote:
[...]
> > I think we also need a selftest, at-least for patch #1.
> 
> Yeah... I was wondering in a message on v1 [1] if a test like what I had
> prototyped there was warranted. I personally still think it's not because of
> how many other variations of variable-offset stack access tests we already
> have, and how random the zero-sized read case is (even though we had a bug in
> there) - so protecting against this particular regression didn't seem worth it
> to me. I'm now including the test in v4 but if you change your mind about it
> when you see it in context, let me know and I'll take it out.
> 
> [1] https://lore.kernel.org/bpf/CABWLsevk47Xa1a+h0UK--94zEuxScrmyt0-D8YShq1UgvVvf5g@mail.gmail.com/

The reproducer is a small and non-contrived program, so I think there
is no harm in adding it.