[PATCH] fix array-index-out-of-bounds in bpf_prog_select_runtime

[PATCH] fix array-index-out-of-bounds in bpf_prog_select_runtime

[Camila Alvarez]

The error indicates that the verifier is letting through a program with
a stack depth bigger than 512.

This is due to the verifier not checking the stack depth after
instruction rewrites are perfomed. For example, the MAY_GOTO instruction
adds 8 bytes to the stack, which means that if the stack at the moment
was already 512 bytes it would overflow after rewriting the instruction.

The fix involves adding a stack depth check after all instruction
rewrites are performed.

Reported-by: syzbot+d2a2c639d03ac200a4f1@syzkaller.appspotmail.com
Signed-off-by: Camila Alvarez <cam.alvarez.i@gmail.com>
---
 kernel/bpf/verifier.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 63749ad5ac6b..a9e23b6b8e8f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -21285,6 +21285,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 	if (ret == 0)
 		ret = do_misc_fixups(env);
 
+        /* max stack depth verification must be done after rewrites as well */
+        if (ret == 0)
+                ret = check_max_stack_depth(env);
+
 	/* do 32-bit optimization after insn patching has done so those patched
 	 * insns could be handled correctly.
 	 */
-- 
2.34.1

Re: [PATCH] fix array-index-out-of-bounds in bpf_prog_select_runtime

[Alexei Starovoitov]

On Sat, May 4, 2024 at 6:49 PM Camila Alvarez <cam.alvarez.i@gmail.com> wrote:
>
> The error indicates that the verifier is letting through a program with
> a stack depth bigger than 512.
>
> This is due to the verifier not checking the stack depth after
> instruction rewrites are perfomed. For example, the MAY_GOTO instruction
> adds 8 bytes to the stack, which means that if the stack at the moment
> was already 512 bytes it would overflow after rewriting the instruction.

This is by design. may_goto and other constructs like bpf_loop
inlining can consume a few words above 512 limit.

> The fix involves adding a stack depth check after all instruction
> rewrites are performed.
>
> Reported-by: syzbot+d2a2c639d03ac200a4f1@syzkaller.appspotmail.com

This syzbot report is likely unrelated.
It says that it bisected it to may_goto, but it has this report
before may_goto was introduced, so bisection is incorrect.

pw-bot: cr

> Signed-off-by: Camila Alvarez <cam.alvarez.i@gmail.com>
> ---
>  kernel/bpf/verifier.c | 4 ++++
>  1 file changed, 4 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 63749ad5ac6b..a9e23b6b8e8f 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -21285,6 +21285,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
>         if (ret == 0)
>                 ret = do_misc_fixups(env);
>
> +        /* max stack depth verification must be done after rewrites as well */
> +        if (ret == 0)
> +                ret = check_max_stack_depth(env);
> +
>         /* do 32-bit optimization after insn patching has done so those patched
>          * insns could be handled correctly.
>          */
> --
> 2.34.1
>

Re: [PATCH] fix array-index-out-of-bounds in bpf_prog_select_runtime

[Camila Alvarez Inostroza]

[-- Attachment #1: Type: text/plain, Size: 2377 bytes --]



On Sun, 5 May 2024, Alexei Starovoitov wrote:

> On Sat, May 4, 2024 at 6:49 PM Camila Alvarez <cam.alvarez.i@gmail.com> wrote:
>>
>> The error indicates that the verifier is letting through a program with
>> a stack depth bigger than 512.
>>
>> This is due to the verifier not checking the stack depth after
>> instruction rewrites are perfomed. For example, the MAY_GOTO instruction
>> adds 8 bytes to the stack, which means that if the stack at the moment
>> was already 512 bytes it would overflow after rewriting the instruction.
>
> This is by design. may_goto and other constructs like bpf_loop
> inlining can consume a few words above 512 limit.
>

Is this the only case where the verifier should allow the stack to go over 
the 512 limit? If that's the case, maybe we could use the extra stack 
depth to store how much the rewrites affect the stack depth? This would 
only be used to obtain the correct interpreter when 
CONFIG_BPF_JIT_ALWAYS_ON is not set.
That would allow choosing the interpreter by considering the stack depth 
before the rewrites.

>> The fix involves adding a stack depth check after all instruction
>> rewrites are performed.
>>
>> Reported-by: syzbot+d2a2c639d03ac200a4f1@syzkaller.appspotmail.com
>
> This syzbot report is likely unrelated.
> It says that it bisected it to may_goto, but it has this report
> before may_goto was introduced, so bisection is incorrect.
>
> pw-bot: cr

I can see that may_goto was introduced on march 6th, and the first report 
was on march 13th. Is there any report I'm missing?

>
>> Signed-off-by: Camila Alvarez <cam.alvarez.i@gmail.com>
>> ---
>>  kernel/bpf/verifier.c | 4 ++++
>>  1 file changed, 4 insertions(+)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 63749ad5ac6b..a9e23b6b8e8f 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -21285,6 +21285,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
>>         if (ret == 0)
>>                 ret = do_misc_fixups(env);
>>
>> +        /* max stack depth verification must be done after rewrites as well */
>> +        if (ret == 0)
>> +                ret = check_max_stack_depth(env);
>> +
>>         /* do 32-bit optimization after insn patching has done so those patched
>>          * insns could be handled correctly.
>>          */
>> --
>> 2.34.1
>>
>

Re: [PATCH] fix array-index-out-of-bounds in bpf_prog_select_runtime

[Alexei Starovoitov]

On Sun, May 5, 2024 at 4:18 PM Camila Alvarez Inostroza
<cam.alvarez.i@gmail.com> wrote:
>
>
>
> On Sun, 5 May 2024, Alexei Starovoitov wrote:
>
> > On Sat, May 4, 2024 at 6:49 PM Camila Alvarez <cam.alvarez.i@gmail.com> wrote:
> >>
> >> The error indicates that the verifier is letting through a program with
> >> a stack depth bigger than 512.
> >>
> >> This is due to the verifier not checking the stack depth after
> >> instruction rewrites are perfomed. For example, the MAY_GOTO instruction
> >> adds 8 bytes to the stack, which means that if the stack at the moment
> >> was already 512 bytes it would overflow after rewriting the instruction.
> >
> > This is by design. may_goto and other constructs like bpf_loop
> > inlining can consume a few words above 512 limit.
> >
>
> Is this the only case where the verifier should allow the stack to go over
> the 512 limit? If that's the case, maybe we could use the extra stack
> depth to store how much the rewrites affect the stack depth? This would
> only be used to obtain the correct interpreter when
> CONFIG_BPF_JIT_ALWAYS_ON is not set.
> That would allow choosing the interpreter by considering the stack depth
> before the rewrites.
>
> >> The fix involves adding a stack depth check after all instruction
> >> rewrites are performed.
> >>
> >> Reported-by: syzbot+d2a2c639d03ac200a4f1@syzkaller.appspotmail.com
> >
> > This syzbot report is likely unrelated.
> > It says that it bisected it to may_goto, but it has this report
> > before may_goto was introduced, so bisection is incorrect.
> >
> > pw-bot: cr
>
> I can see that may_goto was introduced on march 6th, and the first report
> was on march 13th. Is there any report I'm missing?

Could you please craft a selftest for this issue then?
It will be much easier to reason about the fix.
We can either add another interpreter to interpreters_args[]
or just gate may_goto with prog->jit_requested.

[PATCH] fix array-index-out-of-bounds in bpf_prog_select_runtime

[Camila Alvarez]

BPF documentation specifies that the maximum stack depth for a BPF
program is 512 bytes. This is not enforced when selecting a bpf
interpreter, thus casuing an index out of bounds error when trying to
obtain an interpreter with a bigger stack size.

This patch enforces the stack size to be not bigger than
512.

Reported-by: syzbot+d2a2c639d03ac200a4f1@syzkaller.appspotmail.com
Signed-off-by: Camila Alvarez <cam.alvarez.i@gmail.com>
---
 kernel/bpf/core.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 696bc55de8e8..8167b3a721e9 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -2196,7 +2196,7 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
 		BUG_ON(1);
 		return 0;
 }
-
+#define BPF_MAX_STACK_SIZE 512
 #define PROG_NAME(stack_size) __bpf_prog_run##stack_size
 #define DEFINE_BPF_PROG_RUN(stack_size) \
 static unsigned int PROG_NAME(stack_size)(const void *ctx, const struct bpf_insn *insn) \
@@ -2345,7 +2345,7 @@ static void bpf_prog_select_func(struct bpf_prog *fp)
 {
 #ifndef CONFIG_BPF_JIT_ALWAYS_ON
 	u32 stack_depth = max_t(u32, fp->aux->stack_depth, 1);
-
+	stack_depth = min_t(u32, stack_depth, BPF_MAX_STACK_SIZE);
 	fp->bpf_func = interpreters[(round_up(stack_depth, 32) / 32) - 1];
 #else
 	fp->bpf_func = __bpf_prog_ret0_warn;
-- 
2.34.1

Re: [PATCH] fix array-index-out-of-bounds in bpf_prog_select_runtime

[Alexei Starovoitov]

On Mon, Mar 25, 2024 at 5:41 PM Camila Alvarez <cam.alvarez.i@gmail.com> wrote:
>
> BPF documentation specifies that the maximum stack depth for a BPF
> program is 512 bytes. This is not enforced when selecting a bpf
> interpreter, thus casuing an index out of bounds error when trying to
> obtain an interpreter with a bigger stack size.
>
> This patch enforces the stack size to be not bigger than
> 512.
>
> Reported-by: syzbot+d2a2c639d03ac200a4f1@syzkaller.appspotmail.com
> Signed-off-by: Camila Alvarez <cam.alvarez.i@gmail.com>
> ---
>  kernel/bpf/core.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> index 696bc55de8e8..8167b3a721e9 100644
> --- a/kernel/bpf/core.c
> +++ b/kernel/bpf/core.c
> @@ -2196,7 +2196,7 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
>                 BUG_ON(1);
>                 return 0;
>  }
> -
> +#define BPF_MAX_STACK_SIZE 512
>  #define PROG_NAME(stack_size) __bpf_prog_run##stack_size
>  #define DEFINE_BPF_PROG_RUN(stack_size) \
>  static unsigned int PROG_NAME(stack_size)(const void *ctx, const struct bpf_insn *insn) \
> @@ -2345,7 +2345,7 @@ static void bpf_prog_select_func(struct bpf_prog *fp)
>  {
>  #ifndef CONFIG_BPF_JIT_ALWAYS_ON
>         u32 stack_depth = max_t(u32, fp->aux->stack_depth, 1);
> -
> +       stack_depth = min_t(u32, stack_depth, BPF_MAX_STACK_SIZE);
>         fp->bpf_func = interpreters[(round_up(stack_depth, 32) / 32) - 1];

That's not the root cause of the issue.
syzbot is saying: index 16 is out of range for type '<unknown> *[16]'

somehow stack depth got bigger than 512.
The bug is somewhere in the verifier.
Please debug it further.