| Message ID | 20231206165802.380626-2-andreimatei1@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | BPF |
| Headers | show |
| Series | bpf: fix verification of indirect var-off stack access | expand |
On Wed, 2023-12-06 at 11:58 -0500, Andrei Matei wrote: [...] > diff --git a/tools/testing/selftests/bpf/progs/verifier_var_off.c b/tools/testing/selftests/bpf/progs/verifier_var_off.c You would probably be asked to split this patch in two. Usually selftests are submitted as separate patches with 'selftests/bpf:' tag. Tests are updated in 'bpf:' patches only if changes to verifier make some tests invalid (so that it is possible to do bisects over commit ranges). Otherwise, lgtm, thank you for adding the test and please add my ack for the test if v5 would be submitted. > index 83a90afba785..9fb32b292017 100644 > --- a/tools/testing/selftests/bpf/progs/verifier_var_off.c > +++ b/tools/testing/selftests/bpf/progs/verifier_var_off.c > @@ -224,6 +224,35 @@ __naked void access_max_out_of_bound(void) > : __clobber_all); > } > > +/* Similar to the test above, but this time check the special case of a > + * zero-sized stack access. We used to have a bug causing crashes for zero-sized > + * out-of-bounds accesses. > + */ > +SEC("socket") > +__description("indirect variable-offset stack access, zero-sized, max out of bound") > +__failure __msg("invalid variable-offset indirect access to stack R1") > +__naked void zero_sized_access_max_out_of_bound(void) > +{ > + asm volatile (" \ > + r0 = 0; \ > + /* Fill some stack */ \ > + *(u64*)(r10 - 16) = r0; \ > + *(u64*)(r10 - 8) = r0; \ > + /* Get an unknown value */ \ > + r1 = *(u32*)(r1 + 0); \ > + r1 &= 64; \ > + r1 += -16; \ > + /* r1 is now anywhere in [-16,48)*/ \ > + r1 += r10; \ > + r2 = 0; \ > + r3 = 0; \ > + call %[bpf_probe_read_kernel]; \ > + exit; \ > +" : > + : __imm(bpf_probe_read_kernel) > + : __clobber_all); > +} > + > SEC("lwt_in") > __description("indirect variable-offset stack access, min out of bound") > __failure __msg("invalid variable-offset indirect access to stack R2")
On Wed, Dec 6, 2023 at 8:58 AM Andrei Matei <andreimatei1@gmail.com> wrote: > > This patch fixes a bug around the verification of possibly-zero-sized > stack accesses. When the access was done through a var-offset stack > pointer, check_stack_access_within_bounds was incorrectly computing the > maximum-offset of a zero-sized read to be the same as the register's min > offset. Instead, we have to take in account the register's maximum > possible value. The patch also simplifies how the max offset is checked; > the check is now simpler than for min offset. > > The bug was allowing accesses to erroneously pass the > check_stack_access_within_bounds() checks, only to later crash in > check_stack_range_initialized() when all the possibly-affected stack > slots are iterated (this time with a correct max offset). > check_stack_range_initialized() is relying on > check_stack_access_within_bounds() for its accesses to the > stack-tracking vector to be within bounds; in the case of zero-sized > accesses, we were essentially only verifying that the lowest possible > slot was within bounds. We would crash when the max-offset of the stack > pointer was >= 0 (which shouldn't pass verification, and hopefully is > not something anyone's code attempts to do in practice). > > Thanks Hao for reporting! > > Reported-by: Hao Sun <sunhao.th@gmail.com> > Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access") > Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/ > Signed-off-by: Andrei Matei <andreimatei1@gmail.com> > --- > kernel/bpf/verifier.c | 14 +++------ > .../selftests/bpf/progs/verifier_var_off.c | 29 +++++++++++++++++++ > 2 files changed, 33 insertions(+), 10 deletions(-) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index e5ce530641ba..137240681fa9 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -6620,10 +6620,7 @@ static int check_stack_access_within_bounds( > > if (tnum_is_const(reg->var_off)) { > min_off = reg->var_off.value + off; > - if (access_size > 0) > - max_off = min_off + access_size - 1; > - else > - max_off = min_off; > + max_off = min_off + access_size; > } else { > if (reg->smax_value >= BPF_MAX_VAR_OFF || > reg->smin_value <= -BPF_MAX_VAR_OFF) { > @@ -6632,15 +6629,12 @@ static int check_stack_access_within_bounds( > return -EACCES; > } > min_off = reg->smin_value + off; > - if (access_size > 0) > - max_off = reg->smax_value + off + access_size - 1; > - else > - max_off = min_off; > + max_off = reg->smax_value + off + access_size; > } > > err = check_stack_slot_within_bounds(min_off, state, type); > - if (!err) > - err = check_stack_slot_within_bounds(max_off, state, type); > + if (!err && max_off > 0) > + err = -EINVAL; /* out of stack access into non-negative offsets */ > this part looks good to me, please add my ack on resubmission Acked-by: Andrii Nakryiko <andrii@kernel.org> > if (err) { > if (tnum_is_const(reg->var_off)) { > diff --git a/tools/testing/selftests/bpf/progs/verifier_var_off.c b/tools/testing/selftests/bpf/progs/verifier_var_off.c > index 83a90afba785..9fb32b292017 100644 > --- a/tools/testing/selftests/bpf/progs/verifier_var_off.c > +++ b/tools/testing/selftests/bpf/progs/verifier_var_off.c > @@ -224,6 +224,35 @@ __naked void access_max_out_of_bound(void) > : __clobber_all); > } > > +/* Similar to the test above, but this time check the special case of a > + * zero-sized stack access. We used to have a bug causing crashes for zero-sized > + * out-of-bounds accesses. > + */ > +SEC("socket") > +__description("indirect variable-offset stack access, zero-sized, max out of bound") > +__failure __msg("invalid variable-offset indirect access to stack R1") > +__naked void zero_sized_access_max_out_of_bound(void) as Eduard mentioned, please split off selftests from kernel-side changes > +{ > + asm volatile (" \ > + r0 = 0; \ > + /* Fill some stack */ \ > + *(u64*)(r10 - 16) = r0; \ > + *(u64*)(r10 - 8) = r0; \ > + /* Get an unknown value */ \ > + r1 = *(u32*)(r1 + 0); \ > + r1 &= 64; \ did you mean 63 here? and if yes, why does the test work? :) > + r1 += -16; \ > + /* r1 is now anywhere in [-16,48)*/ \ nit: space before */ ? > + r1 += r10; \ > + r2 = 0; \ > + r3 = 0; \ > + call %[bpf_probe_read_kernel]; \ > + exit; \ > +" : > + : __imm(bpf_probe_read_kernel) > + : __clobber_all); > +} > + > SEC("lwt_in") > __description("indirect variable-offset stack access, min out of bound") > __failure __msg("invalid variable-offset indirect access to stack R2") > -- > 2.39.2 >
On Wed, Dec 6, 2023 at 1:56 PM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Wed, Dec 6, 2023 at 8:58 AM Andrei Matei <andreimatei1@gmail.com> wrote: > > > > This patch fixes a bug around the verification of possibly-zero-sized > > stack accesses. When the access was done through a var-offset stack > > pointer, check_stack_access_within_bounds was incorrectly computing the > > maximum-offset of a zero-sized read to be the same as the register's min > > offset. Instead, we have to take in account the register's maximum > > possible value. The patch also simplifies how the max offset is checked; > > the check is now simpler than for min offset. > > > > The bug was allowing accesses to erroneously pass the > > check_stack_access_within_bounds() checks, only to later crash in > > check_stack_range_initialized() when all the possibly-affected stack > > slots are iterated (this time with a correct max offset). > > check_stack_range_initialized() is relying on > > check_stack_access_within_bounds() for its accesses to the > > stack-tracking vector to be within bounds; in the case of zero-sized > > accesses, we were essentially only verifying that the lowest possible > > slot was within bounds. We would crash when the max-offset of the stack > > pointer was >= 0 (which shouldn't pass verification, and hopefully is > > not something anyone's code attempts to do in practice). > > > > Thanks Hao for reporting! > > > > Reported-by: Hao Sun <sunhao.th@gmail.com> > > Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access") > > Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/ > > Signed-off-by: Andrei Matei <andreimatei1@gmail.com> > > --- > > kernel/bpf/verifier.c | 14 +++------ > > .../selftests/bpf/progs/verifier_var_off.c | 29 +++++++++++++++++++ > > 2 files changed, 33 insertions(+), 10 deletions(-) > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > index e5ce530641ba..137240681fa9 100644 > > --- a/kernel/bpf/verifier.c > > +++ b/kernel/bpf/verifier.c > > @@ -6620,10 +6620,7 @@ static int check_stack_access_within_bounds( > > > > if (tnum_is_const(reg->var_off)) { > > min_off = reg->var_off.value + off; > > - if (access_size > 0) > > - max_off = min_off + access_size - 1; > > - else > > - max_off = min_off; > > + max_off = min_off + access_size; > > } else { > > if (reg->smax_value >= BPF_MAX_VAR_OFF || > > reg->smin_value <= -BPF_MAX_VAR_OFF) { > > @@ -6632,15 +6629,12 @@ static int check_stack_access_within_bounds( > > return -EACCES; > > } > > min_off = reg->smin_value + off; > > - if (access_size > 0) > > - max_off = reg->smax_value + off + access_size - 1; > > - else > > - max_off = min_off; > > + max_off = reg->smax_value + off + access_size; > > } > > > > err = check_stack_slot_within_bounds(min_off, state, type); > > - if (!err) > > - err = check_stack_slot_within_bounds(max_off, state, type); > > + if (!err && max_off > 0) > > + err = -EINVAL; /* out of stack access into non-negative offsets */ > > > > this part looks good to me, please add my ack on resubmission > > Acked-by: Andrii Nakryiko <andrii@kernel.org> > > > > if (err) { > > if (tnum_is_const(reg->var_off)) { > > diff --git a/tools/testing/selftests/bpf/progs/verifier_var_off.c b/tools/testing/selftests/bpf/progs/verifier_var_off.c > > index 83a90afba785..9fb32b292017 100644 > > --- a/tools/testing/selftests/bpf/progs/verifier_var_off.c > > +++ b/tools/testing/selftests/bpf/progs/verifier_var_off.c > > @@ -224,6 +224,35 @@ __naked void access_max_out_of_bound(void) > > : __clobber_all); > > } > > > > +/* Similar to the test above, but this time check the special case of a > > + * zero-sized stack access. We used to have a bug causing crashes for zero-sized > > + * out-of-bounds accesses. > > + */ > > +SEC("socket") > > +__description("indirect variable-offset stack access, zero-sized, max out of bound") > > +__failure __msg("invalid variable-offset indirect access to stack R1") > > +__naked void zero_sized_access_max_out_of_bound(void) > > as Eduard mentioned, please split off selftests from kernel-side changes > > > +{ > > + asm volatile (" \ > > + r0 = 0; \ > > + /* Fill some stack */ \ > > + *(u64*)(r10 - 16) = r0; \ > > + *(u64*)(r10 - 8) = r0; \ > > + /* Get an unknown value */ \ > > + r1 = *(u32*)(r1 + 0); \ > > + r1 &= 64; \ > > did you mean 63 here? and if yes, why does the test work? :) I did mean 63, thanks. But the test worked either way, not much difference. `r1 &= 64` gives you a positive value that's either 0 or 64 (i.e. all the bits except one are known), so for the relevant verification code path, it's pretty equivalent to [0, 64) -- all that matters are the bounds. > > > + r1 += -16; \ > > + /* r1 is now anywhere in [-16,48)*/ \ > > nit: space before */ ? > > > + r1 += r10; \ > > + r2 = 0; \ > > + r3 = 0; \ > > + call %[bpf_probe_read_kernel]; \ > > + exit; \ > > +" : > > + : __imm(bpf_probe_read_kernel) > > + : __clobber_all); > > +} > > + > > SEC("lwt_in") > > __description("indirect variable-offset stack access, min out of bound") > > __failure __msg("invalid variable-offset indirect access to stack R2") > > -- > > 2.39.2 > >
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index e5ce530641ba..137240681fa9 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6620,10 +6620,7 @@ static int check_stack_access_within_bounds( if (tnum_is_const(reg->var_off)) { min_off = reg->var_off.value + off; - if (access_size > 0) - max_off = min_off + access_size - 1; - else - max_off = min_off; + max_off = min_off + access_size; } else { if (reg->smax_value >= BPF_MAX_VAR_OFF || reg->smin_value <= -BPF_MAX_VAR_OFF) { @@ -6632,15 +6629,12 @@ static int check_stack_access_within_bounds( return -EACCES; } min_off = reg->smin_value + off; - if (access_size > 0) - max_off = reg->smax_value + off + access_size - 1; - else - max_off = min_off; + max_off = reg->smax_value + off + access_size; } err = check_stack_slot_within_bounds(min_off, state, type); - if (!err) - err = check_stack_slot_within_bounds(max_off, state, type); + if (!err && max_off > 0) + err = -EINVAL; /* out of stack access into non-negative offsets */ if (err) { if (tnum_is_const(reg->var_off)) { diff --git a/tools/testing/selftests/bpf/progs/verifier_var_off.c b/tools/testing/selftests/bpf/progs/verifier_var_off.c index 83a90afba785..9fb32b292017 100644 --- a/tools/testing/selftests/bpf/progs/verifier_var_off.c +++ b/tools/testing/selftests/bpf/progs/verifier_var_off.c @@ -224,6 +224,35 @@ __naked void access_max_out_of_bound(void) : __clobber_all); } +/* Similar to the test above, but this time check the special case of a + * zero-sized stack access. We used to have a bug causing crashes for zero-sized + * out-of-bounds accesses. + */ +SEC("socket") +__description("indirect variable-offset stack access, zero-sized, max out of bound") +__failure __msg("invalid variable-offset indirect access to stack R1") +__naked void zero_sized_access_max_out_of_bound(void) +{ + asm volatile (" \ + r0 = 0; \ + /* Fill some stack */ \ + *(u64*)(r10 - 16) = r0; \ + *(u64*)(r10 - 8) = r0; \ + /* Get an unknown value */ \ + r1 = *(u32*)(r1 + 0); \ + r1 &= 64; \ + r1 += -16; \ + /* r1 is now anywhere in [-16,48)*/ \ + r1 += r10; \ + r2 = 0; \ + r3 = 0; \ + call %[bpf_probe_read_kernel]; \ + exit; \ +" : + : __imm(bpf_probe_read_kernel) + : __clobber_all); +} + SEC("lwt_in") __description("indirect variable-offset stack access, min out of bound") __failure __msg("invalid variable-offset indirect access to stack R2")
This patch fixes a bug around the verification of possibly-zero-sized stack accesses. When the access was done through a var-offset stack pointer, check_stack_access_within_bounds was incorrectly computing the maximum-offset of a zero-sized read to be the same as the register's min offset. Instead, we have to take in account the register's maximum possible value. The patch also simplifies how the max offset is checked; the check is now simpler than for min offset. The bug was allowing accesses to erroneously pass the check_stack_access_within_bounds() checks, only to later crash in check_stack_range_initialized() when all the possibly-affected stack slots are iterated (this time with a correct max offset). check_stack_range_initialized() is relying on check_stack_access_within_bounds() for its accesses to the stack-tracking vector to be within bounds; in the case of zero-sized accesses, we were essentially only verifying that the lowest possible slot was within bounds. We would crash when the max-offset of the stack pointer was >= 0 (which shouldn't pass verification, and hopefully is not something anyone's code attempts to do in practice). Thanks Hao for reporting! Reported-by: Hao Sun <sunhao.th@gmail.com> Fixes: 01f810ace9ed3 ("bpf: Allow variable-offset stack access") Closes: https://lore.kernel.org/bpf/CACkBjsZGEUaRCHsmaX=h-efVogsRfK1FPxmkgb0Os_frnHiNdw@mail.gmail.com/ Signed-off-by: Andrei Matei <andreimatei1@gmail.com> --- kernel/bpf/verifier.c | 14 +++------ .../selftests/bpf/progs/verifier_var_off.c | 29 +++++++++++++++++++ 2 files changed, 33 insertions(+), 10 deletions(-)