[PATCH bpf] bpf: Protect against int overflow for stack access size

[PATCH bpf] bpf: Protect against int overflow for stack access size

[Andrei Matei]

This patch re-introduces protection against the size of access to stack
memory being negative; the access size can appear negative as a result
of overflowing its signed int representation (the respective function
arguments is sometimes converted from a u32 and u64 without any overflow
checking), and causes out-of-bounds array accesses in
check_stack_range_initialized(). This patch causes the verification of a
program with such a non-sensical access size to fail.

This check used to exist in a more indirect way, but was inadvertendly
removed in a833a17a.

This omission was found by syzkaller. I have failed to actually create a
program that triggers the issue (different other protections kick in for
different code paths). The syzkaller program is opaque and I failed to
fully decipher it; from what I gather, it declares a map with a huge
value type (0x80000001 bytes, which is INT_MAX + 2), and somehow calls a
helper (bpf_map_peek_elem), and manages to pass to it a pointer to the
stack while, at the same time, the size of values in this map is being
used as the "access size".

Fixes: a833a17a ("bpf: Fix verification of indirect var-off stack access")
Reported-by: syzbot+33f4297b5f927648741a@syzkaller.appspotmail.com
Closes: https://lore.kernel.org/bpf/CAADnVQLORV5PT0iTAhRER+iLBTkByCYNBYyvBSgjN1T31K+gOw@mail.gmail.com/
---
 kernel/bpf/verifier.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0bfc0050db28..2019d6177969 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -6701,6 +6701,8 @@ static int check_stack_access_within_bounds(
 	err = check_stack_slot_within_bounds(env, min_off, state, type);
 	if (!err && max_off > 0)
 		err = -EINVAL; /* out of stack access into non-negative offsets */
+	if (!err && access_size < 0)
+		err = -EINVAL; /* invalid negative access size; integer overflow? */
 
 	if (err) {
 		if (tnum_is_const(reg->var_off)) {
-- 
2.40.1

Re: [PATCH bpf] bpf: Protect against int overflow for stack access size

[Alexei Starovoitov]

On Sun, Mar 24, 2024 at 4:04 PM Andrei Matei <andreimatei1@gmail.com> wrote:
>
> This patch re-introduces protection against the size of access to stack
> memory being negative; the access size can appear negative as a result
> of overflowing its signed int representation (the respective function
> arguments is sometimes converted from a u32 and u64 without any overflow
> checking), and causes out-of-bounds array accesses in
> check_stack_range_initialized(). This patch causes the verification of a
> program with such a non-sensical access size to fail.
>
> This check used to exist in a more indirect way, but was inadvertendly
> removed in a833a17a.
>
> This omission was found by syzkaller. I have failed to actually create a
> program that triggers the issue (different other protections kick in for
> different code paths). The syzkaller program is opaque and I failed to
> fully decipher it; from what I gather, it declares a map with a huge
> value type (0x80000001 bytes, which is INT_MAX + 2),

Is that a bloomfilter map?
Looks like it doesn't have a check for max value_size.
Pls send a patch to limit it to KMALLOC_MAX_SIZE like
we do for other maps.
Hashing over bigger values are pretty hard to do from the bpf side.

> and somehow calls a
> helper (bpf_map_peek_elem), and manages to pass to it a pointer to the
> stack while, at the same time, the size of values in this map is being
> used as the "access size".
>
> Fixes: a833a17a ("bpf: Fix verification of indirect var-off stack access")

The sha is too short. Pls use 12 chars.
See Documentation/process/submitting-patches.rst.

> Reported-by: syzbot+33f4297b5f927648741a@syzkaller.appspotmail.com
> Closes: https://lore.kernel.org/bpf/CAADnVQLORV5PT0iTAhRER+iLBTkByCYNBYyvBSgjN1T31K+gOw@mail.gmail.com/
> ---
>  kernel/bpf/verifier.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0bfc0050db28..2019d6177969 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -6701,6 +6701,8 @@ static int check_stack_access_within_bounds(
>         err = check_stack_slot_within_bounds(env, min_off, state, type);
>         if (!err && max_off > 0)
>                 err = -EINVAL; /* out of stack access into non-negative offsets */
> +       if (!err && access_size < 0)
> +               err = -EINVAL; /* invalid negative access size; integer overflow? */

This feels like a good place for such a check.
But it's not an overflow.
In few other places we have the check against
#define BPF_MAX_VAR_OFF (1 << 29)
but this path into check_stack_access_within_bounds()
didn't hit it.

Since map value_size is negative it is causing all sorts of issues
and probably not only here.
Once bloomfilter is fixed this check will not be hit anytime soon,
but let's add it anyway.
I would return -EFAULT here and add a comment that this is a bug.
No need for WARN though.

pw-bot: cr

Re: [PATCH bpf] bpf: Protect against int overflow for stack access size

[Andrei Matei]

On Sun, Mar 24, 2024 at 9:08 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Sun, Mar 24, 2024 at 4:04 PM Andrei Matei <andreimatei1@gmail.com> wrote:
> >
> > This patch re-introduces protection against the size of access to stack
> > memory being negative; the access size can appear negative as a result
> > of overflowing its signed int representation (the respective function
> > arguments is sometimes converted from a u32 and u64 without any overflow
> > checking), and causes out-of-bounds array accesses in
> > check_stack_range_initialized(). This patch causes the verification of a
> > program with such a non-sensical access size to fail.
> >
> > This check used to exist in a more indirect way, but was inadvertendly
> > removed in a833a17a.
> >
> > This omission was found by syzkaller. I have failed to actually create a
> > program that triggers the issue (different other protections kick in for
> > different code paths). The syzkaller program is opaque and I failed to
> > fully decipher it; from what I gather, it declares a map with a huge
> > value type (0x80000001 bytes, which is INT_MAX + 2),
>
> Is that a bloomfilter map?

It is! Did you know that from the 0x1e in the repro C code?

  *(uint32_t*)0x20000640 = 0x1e;
  *(uint32_t*)0x20000644 = 0;
  *(uint32_t*)0x20000648 = 0x80000001;
   ...
  res = syscall(__NR_bpf, /*cmd=*/0ul, /*arg=*/0x20000640ul, /*size=*/0x48ul);


> Looks like it doesn't have a check for max value_size.
> Pls send a patch to limit it to KMALLOC_MAX_SIZE like
> we do for other maps.
> Hashing over bigger values are pretty hard to do from the bpf side.
>
> > and somehow calls a
> > helper (bpf_map_peek_elem), and manages to pass to it a pointer to the
> > stack while, at the same time, the size of values in this map is being
> > used as the "access size".
> >
> > Fixes: a833a17a ("bpf: Fix verification of indirect var-off stack access")
>
> The sha is too short. Pls use 12 chars.
> See Documentation/process/submitting-patches.rst.
>
> > Reported-by: syzbot+33f4297b5f927648741a@syzkaller.appspotmail.com
> > Closes: https://lore.kernel.org/bpf/CAADnVQLORV5PT0iTAhRER+iLBTkByCYNBYyvBSgjN1T31K+gOw@mail.gmail.com/
> > ---
> >  kernel/bpf/verifier.c | 2 ++
> >  1 file changed, 2 insertions(+)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 0bfc0050db28..2019d6177969 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -6701,6 +6701,8 @@ static int check_stack_access_within_bounds(
> >         err = check_stack_slot_within_bounds(env, min_off, state, type);
> >         if (!err && max_off > 0)
> >                 err = -EINVAL; /* out of stack access into non-negative offsets */
> > +       if (!err && access_size < 0)
> > +               err = -EINVAL; /* invalid negative access size; integer overflow? */
>
> This feels like a good place for such a check.
> But it's not an overflow.

What do you mean by "it's not an overflow"? If this condition is ever hit again
after we fix the bloom filter map, it will be likely because of an overflow,
won't it?


> In few other places we have the check against
> #define BPF_MAX_VAR_OFF (1 << 29)
> but this path into check_stack_access_within_bounds()
> didn't hit it.
>
> Since map value_size is negative it is causing all sorts of issues
> and probably not only here.
> Once bloomfilter is fixed this check will not be hit anytime soon,
> but let's add it anyway.
> I would return -EFAULT here and add a comment that this is a bug.
> No need for WARN though.

Ack.
Do you think this will require a regression test?  If so, could you please
point me to an example for how a (test_progs ?) test would define a map with a
large value?


>
> pw-bot: cr