bpf: Fix array bounds error with may_goto and add selftest
Subsystems (4)
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
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.
--- kernel/bpf/core.c | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-)
kernel/bpf/core.c +8 -3
@@ -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
Re: [PATCH bpf-next v1 1/2] bpf: Fix array bounds error with may_goto
Quoted 27 lines · Jiayuan Chen
may_gotouses an additional 8 bytes on the stack, which causes the interpreters[] array to go out of bounds when calculating index bystack_size.Reported-by [email protected]Fixes 011832b97b311 ("bpf: Introduce may_goto instruction")Signed-off-by Jiayuan Chen <[email protected]>--- kernel/bpf/core.c | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-)kernel/bpf/core.c +1
-1@@ -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
@@ -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
PATCH 2/2 bpf/selftest: add selftest for may_goto
In reply to Jiayuan ChenAdd 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
@@ -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) +{ + asmvolatile ( +"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) +{ + asmvolatile ( +"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