[PATCH bpf-next v1 0/2] bpf: Fix array bounds error with may_goto and add selftest

[PATCH bpf-next v1 0/2] bpf: Fix array bounds error with may_goto and add selftest

[Jiayuan Chen]

Syzbot caught an array out-of-bounds bug [1]. It turns out that when the
BPF program runs through do_misc_fixups(), it allocates an extra 8 bytes
on the call stack, which eventually causes stack_depth to exceed 512.

I was able to reproduce this issue probabilistically by enabling
CONFIG_UBSAN=y and disabling CONFIG_BPF_JIT_ALWAYS_ON with the selfttest
I provide in second patch(although it doesn't happen every time - I didn't
dig deeper into why UBSAN behaves this way).

To fix this, I came up with three possible solutions:
1. Run check_max_stack_depth() again after do_misc_fixups(), but I don't
think it's fair to make users pay for the extra stack overhead caused by
our optimization. Especially when users write assembly code that directly
allocates 512 bytes (like my selftest), it's gonna fail and leave them
confused.

2. Force JIT when using may_goto, but that's not ideal if we want may_goto
to work with both interpreters and JIT.

3. Simply extend interpreters, which seems like the most reasonable
approach to me. And if I had to choose a second best, it would be option 1.


[1] https://syzkaller.appspot.com/bug?extid=d2a2c639d03ac200a4f1
---
Jiayuan Chen (2):
  bpf: Fix array bounds error with may_goto
  bpf/selftest: add selftest for may_goto

 kernel/bpf/core.c                             | 11 +++++--
 .../selftests/bpf/progs/verifier_stack_ptr.c  | 33 +++++++++++++++++++
 2 files changed, 41 insertions(+), 3 deletions(-)

-- 
2.47.1

[PATCH bpf-next v1 1/2] bpf: Fix array bounds error with may_goto

[Jiayuan Chen]

may_goto uses an additional 8 bytes on the stack, which causes the
interpreters[] array to go out of bounds when calculating index by
stack_size.

Reported-by: syzbot+d2a2c639d03ac200a4f1@syzkaller.appspotmail.com
Closes: https://lore.kernel.org/bpf/0000000000000f823606139faa5d@google.com/
Fixes: 011832b97b311 ("bpf: Introduce may_goto instruction")
Signed-off-by: Jiayuan Chen <mrpre@163.com>
---
 kernel/bpf/core.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index da729cbbaeb9..498b35284f81 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -2255,7 +2255,7 @@ static u64 PROG_NAME_ARGS(stack_size)(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5, \
 
 EVAL6(DEFINE_BPF_PROG_RUN, 32, 64, 96, 128, 160, 192);
 EVAL6(DEFINE_BPF_PROG_RUN, 224, 256, 288, 320, 352, 384);
-EVAL4(DEFINE_BPF_PROG_RUN, 416, 448, 480, 512);
+EVAL5(DEFINE_BPF_PROG_RUN, 416, 448, 480, 512, 544);
 
 EVAL6(DEFINE_BPF_PROG_RUN_ARGS, 32, 64, 96, 128, 160, 192);
 EVAL6(DEFINE_BPF_PROG_RUN_ARGS, 224, 256, 288, 320, 352, 384);
@@ -2267,8 +2267,11 @@ static unsigned int (*interpreters[])(const void *ctx,
 				      const struct bpf_insn *insn) = {
 EVAL6(PROG_NAME_LIST, 32, 64, 96, 128, 160, 192)
 EVAL6(PROG_NAME_LIST, 224, 256, 288, 320, 352, 384)
-EVAL4(PROG_NAME_LIST, 416, 448, 480, 512)
+EVAL5(PROG_NAME_LIST, 416, 448, 480, 512, 544)
 };
+
+#define MAX_INTERPRETERS_CALLBACK (sizeof(interpreters) / sizeof(*interpreters))
+
 #undef PROG_NAME_LIST
 #define PROG_NAME_LIST(stack_size) PROG_NAME_ARGS(stack_size),
 static __maybe_unused
@@ -2380,8 +2383,10 @@ 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);
+	u32 idx = (round_up(stack_depth, 32) / 32) - 1;
 
-	fp->bpf_func = interpreters[(round_up(stack_depth, 32) / 32) - 1];
+	WARN_ON_ONCE(idx >= MAX_INTERPRETERS_CALLBACK);
+	fp->bpf_func = interpreters[idx];
 #else
 	fp->bpf_func = __bpf_prog_ret0_warn;
 #endif
-- 
2.47.1

[PATCH bpf-next v1 2/2] bpf/selftest: add selftest for may_goto

[Jiayuan Chen]

Add test case to ensure normal operation when may_goto exists and the
stack size has already reached 512.

./test_progs -t verifier_stack_ptr
...
verifier_stack_ptr/PTR_TO_STACK max stack size > 512:OK
verifier_stack_ptr/PTR_TO_STACK max stack size 512 with may_goto:OK
...

Signed-off-by: Jiayuan Chen <mrpre@163.com>
---
 .../selftests/bpf/progs/verifier_stack_ptr.c  | 33 +++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c b/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c
index 417c61cd4b19..b2e84714e1bc 100644
--- a/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c
+++ b/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c
@@ -481,4 +481,37 @@ l1_%=:	r0 = 42;					\
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("PTR_TO_STACK max stack size > 512")
+__failure __msg("invalid write to stack R1 off=-520 size=8")
+__naked void stack_check_size_gt_512(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -520;"
+	"r0 = 42;"
+	"*(u64*)(r1 + 0) = r0;"
+	"exit;"
+	::: __clobber_all);
+}
+
+#ifdef __BPF_FEATURE_MAY_GOTO
+SEC("socket")
+__description("PTR_TO_STACK max stack size 512 with may_goto")
+__success
+__retval(42)
+__naked void stack_check_size_512_with_may_goto(void)
+{
+	asm volatile (
+	"r1 = r10;"
+	"r1 += -512;"
+	"r0 = 42;"
+	"*(u32*)(r1 + 0) = r0;"
+	"may_goto end;"
+	"r2 = 100;"
+"end:	exit;"
+	::: __clobber_all);
+}
+#endif
+
 char _license[] SEC("license") = "GPL";
-- 
2.47.1

Re: [PATCH bpf-next v1 1/2] bpf: Fix array bounds error with may_goto

[Alexei Starovoitov]

On Wed, Feb 12, 2025 at 5:53 AM Jiayuan Chen <mrpre@163.com> wrote:
>
> may_goto uses an additional 8 bytes on the stack, which causes the
> interpreters[] array to go out of bounds when calculating index by
> stack_size.
>
> Reported-by: syzbot+d2a2c639d03ac200a4f1@syzkaller.appspotmail.com
> Closes: https://lore.kernel.org/bpf/0000000000000f823606139faa5d@google.com/
> Fixes: 011832b97b311 ("bpf: Introduce may_goto instruction")
> Signed-off-by: Jiayuan Chen <mrpre@163.com>
> ---
>  kernel/bpf/core.c | 11 ++++++++---
>  1 file changed, 8 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> index da729cbbaeb9..498b35284f81 100644
> --- a/kernel/bpf/core.c
> +++ b/kernel/bpf/core.c
> @@ -2255,7 +2255,7 @@ static u64 PROG_NAME_ARGS(stack_size)(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5, \
>
>  EVAL6(DEFINE_BPF_PROG_RUN, 32, 64, 96, 128, 160, 192);
>  EVAL6(DEFINE_BPF_PROG_RUN, 224, 256, 288, 320, 352, 384);
> -EVAL4(DEFINE_BPF_PROG_RUN, 416, 448, 480, 512);
> +EVAL5(DEFINE_BPF_PROG_RUN, 416, 448, 480, 512, 544);
>
>  EVAL6(DEFINE_BPF_PROG_RUN_ARGS, 32, 64, 96, 128, 160, 192);
>  EVAL6(DEFINE_BPF_PROG_RUN_ARGS, 224, 256, 288, 320, 352, 384);
> @@ -2267,8 +2267,11 @@ static unsigned int (*interpreters[])(const void *ctx,
>                                       const struct bpf_insn *insn) = {
>  EVAL6(PROG_NAME_LIST, 32, 64, 96, 128, 160, 192)
>  EVAL6(PROG_NAME_LIST, 224, 256, 288, 320, 352, 384)
> -EVAL4(PROG_NAME_LIST, 416, 448, 480, 512)
> +EVAL5(PROG_NAME_LIST, 416, 448, 480, 512, 544)
>  };

That's two extra functions for a rare corner case.
Let's do something like the following instead:
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9971c03adfd5..028de7a6edfc 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -21884,6 +21884,10 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                        subprogs[cur_subprog].stack_extra = stack_depth_extra;
                        cur_subprog++;
                        stack_depth = subprogs[cur_subprog].stack_depth;
+                       if (stack_depth > MAX_BPF_STACK &&
!prog->jit_requested) {
+                               verbose(...);
+                               return -EINVAL;
+                       }


pw-bot: cr