Skip to contentSkip to conversation

bpf: Fix array bounds error with may_goto and add selftest

PATCH Superseded Jiayuan Chen 2 participants 4 messages Feb 12, 2025

Subsystems (4)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

cover bpf: Fix array bounds error with may_goto and add selftest

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(-)
Signature · 1 line
2.47.1
#1 lore raw

PATCH 1/2 bpf: Fix array bounds error with may_goto

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 [email protected]
Fixes 011832b97b311 ("bpf: Introduce may_goto instruction")
---
 kernel/bpf/core.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)
kernel/bpf/core.c +8 -3
index da729cbbaeb9..498b35284f81 100644
@@ -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
Signature · 1 line
2.47.1
#2 lore raw

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

Quoted 27 lines · 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 [email protected]
Fixes 011832b97b311 ("bpf: Introduce may_goto instruction")
---
 kernel/bpf/core.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)
kernel/bpf/core.c +1 -1
index da729cbbaeb9..498b35284f81 100644
@@ -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);

kernel/bpf/core.c static unsigned int (*interpreters[])(const void *ctx, · line 2271

Quoted 6 lines
kernel/bpf/core.c +1 -1
@@ -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:

kernel/bpf/verifier.c +1 -0
index 9971c03adfd5..028de7a6edfc 100644
@@ -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

#3 lore raw

PATCH 2/2 bpf/selftest: add selftest for may_goto

In reply to 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
...

---
 .../selftests/bpf/progs/verifier_stack_ptr.c  | 33 +++++++++++++++++++
 1 file changed, 33 insertions(+)
tools/testing/selftests/bpf/progs/verifier_stack_ptr.c +33 -0
index 417c61cd4b19..b2e84714e1bc 100644
@@ -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";
Signature · 1 line
2.47.1