From: Joanne Koong <joannelkoong@gmail.com>
To: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Cc: bpf@vger.kernel.org, Alexei Starovoitov <ast@kernel.org>,
Andrii Nakryiko <andrii@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Martin KaFai Lau <martin.lau@kernel.org>,
David Vernet <void@manifault.com>,
Eduard Zingerman <eddyz87@gmail.com>
Subject: Re: [PATCH bpf-next v1 3/8] bpf: Fix partial dynptr stack slot reads/writes
Date: Thu, 12 Jan 2023 10:51:49 -0800 [thread overview]
Message-ID: <CAJnrk1b30vAs-pcgLF31Zr996w2GQD1ObkR2Lvp9ohT4SJ2+rQ@mail.gmail.com> (raw)
In-Reply-To: <20230109113049.2pft4sfxsayqcvw6@apollo>
On Mon, Jan 9, 2023 at 3:30 AM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
>
> On Sat, Jan 07, 2023 at 12:46:23AM IST, Joanne Koong wrote:
> > On Sun, Jan 1, 2023 at 12:34 AM Kumar Kartikeya Dwivedi
> > <memxor@gmail.com> wrote:
> > >
> > > Currently, while reads are disallowed for dynptr stack slots, writes are
> > > not. Reads don't work from both direct access and helpers, while writes
> > > do work in both cases, but have the effect of overwriting the slot_type.
> > >
> > > While this is fine, handling for a few edge cases is missing. Firstly,
> > > a user can overwrite the stack slots of dynptr partially.
> > >
> > > Consider the following layout:
> > > spi: [d][d][?]
> > > 2 1 0
> > >
> > > First slot is at spi 2, second at spi 1.
> > > Now, do a write of 1 to 8 bytes for spi 1.
> > >
> > > This will essentially either write STACK_MISC for all slot_types or
> > > STACK_MISC and STACK_ZERO (in case of size < BPF_REG_SIZE partial write
> > > of zeroes). The end result is that slot is scrubbed.
> > >
> > > Now, the layout is:
> > > spi: [d][m][?]
> > > 2 1 0
> > >
> > > Suppose if user initializes spi = 1 as dynptr.
> > > We get:
> > > spi: [d][d][d]
> > > 2 1 0
> > >
> > > But this time, both spi 2 and spi 1 have first_slot = true.
> > >
> > > Now, when passing spi 2 to dynptr helper, it will consider it as
> > > initialized as it does not check whether second slot has first_slot ==
> > > false. And spi 1 should already work as normal.
> > >
> > > This effectively replaced size + offset of first dynptr, hence allowing
> > > invalid OOB reads and writes.
> > >
> > > Make a few changes to protect against this:
> > > When writing to PTR_TO_STACK using BPF insns, when we touch spi of a
> > > STACK_DYNPTR type, mark both first and second slot (regardless of which
> > > slot we touch) as STACK_INVALID. Reads are already prevented.
> > >
> > > Second, prevent writing to stack memory from helpers if the range may
> > > contain any STACK_DYNPTR slots. Reads are already prevented.
> > >
> > > For helpers, we cannot allow it to destroy dynptrs from the writes as
> > > depending on arguments, helper may take uninit_mem and dynptr both at
> > > the same time. This would mean that helper may write to uninit_mem
> > > before it reads the dynptr, which would be bad.
> > >
> > > PTR_TO_MEM: [?????dd]
> > >
> > > Depending on the code inside the helper, it may end up overwriting the
> > > dynptr contents first and then read those as the dynptr argument.
> > >
> > > Verifier would only simulate destruction when it does byte by byte
> > > access simulation in check_helper_call for meta.access_size, and
> > > fail to catch this case, as it happens after argument checks.
> > >
> > > The same would need to be done for any other non-trivial objects created
> > > on the stack in the future, such as bpf_list_head on stack, or
> > > bpf_rb_root on stack.
> > >
> > > A common misunderstanding in the current code is that MEM_UNINIT means
> > > writes, but note that writes may also be performed even without
> > > MEM_UNINIT in case of helpers, in that case the code after handling meta
> > > && meta->raw_mode will complain when it sees STACK_DYNPTR. So that
> > > invalid read case also covers writes to potential STACK_DYNPTR slots.
> > > The only loophole was in case of meta->raw_mode which simulated writes
> > > through instructions which could overwrite them.
> > >
> > > A future series sequenced after this will focus on the clean up of
> > > helper access checks and bugs around that.
> > >
> > > Fixes: 97e03f521050 ("bpf: Add verifier support for dynptrs")
> > > Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> > > ---
> > > kernel/bpf/verifier.c | 73 +++++++++++++++++++++++++++++++++++++++++++
> > > 1 file changed, 73 insertions(+)
> > >
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index ca970f80e395..b985d90505cc 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -769,6 +769,8 @@ static void mark_dynptr_cb_reg(struct bpf_reg_state *reg,
> > > __mark_dynptr_reg(reg, type, true);
> > > }
> > >
> > > +static void destroy_stack_slots_dynptr(struct bpf_verifier_env *env,
> > > + struct bpf_func_state *state, int spi);
> > >
> > > static int mark_stack_slots_dynptr(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
> > > enum bpf_arg_type arg_type, int insn_idx)
> > > @@ -858,6 +860,44 @@ static int unmark_stack_slots_dynptr(struct bpf_verifier_env *env, struct bpf_re
> > > return 0;
> > > }
> > >
> > > +static void destroy_stack_slots_dynptr(struct bpf_verifier_env *env,
> > > + struct bpf_func_state *state, int spi)
> > > +{
> > > + int i;
> > > +
> > > + /* We always ensure that STACK_DYNPTR is never set partially,
> > > + * hence just checking for slot_type[0] is enough. This is
> > > + * different for STACK_SPILL, where it may be only set for
> > > + * 1 byte, so code has to use is_spilled_reg.
> > > + */
> > > + if (state->stack[spi].slot_type[0] != STACK_DYNPTR)
> > > + return;
> >
> > nit: an empty line here helps readability
> >
>
> Ok.
>
> > > + /* Reposition spi to first slot */
> > > + if (!state->stack[spi].spilled_ptr.dynptr.first_slot)
> > > + spi = spi + 1;
> > > +
> > > + mark_stack_slot_scratched(env, spi);
> > > + mark_stack_slot_scratched(env, spi - 1);
> > > +
> > > + /* Writing partially to one dynptr stack slot destroys both. */
> > > + for (i = 0; i < BPF_REG_SIZE; i++) {
> > > + state->stack[spi].slot_type[i] = STACK_INVALID;
> > > + state->stack[spi - 1].slot_type[i] = STACK_INVALID;
> > > + }
> > > +
> > > + /* Do not release reference state, we are destroying dynptr on stack,
> > > + * not using some helper to release it. Just reset register.
> > > + */
> >
> > I agree with Andrii's point - I think it'd be more helpful if we error
> > out here if the dynptr is refcounted. It'd be easy to check too, we
> > already have dynptr_type_refcounted().
> >
>
> Ack, I'll change it to return an error early.
>
> > > + __mark_reg_not_init(env, &state->stack[spi].spilled_ptr);
> > > + __mark_reg_not_init(env, &state->stack[spi - 1].spilled_ptr);
> > > +
> > > + /* Same reason as unmark_stack_slots_dynptr above */
> > > + state->stack[spi].spilled_ptr.live |= REG_LIVE_WRITTEN;
> > > + state->stack[spi - 1].spilled_ptr.live |= REG_LIVE_WRITTEN;
> > > +
> > > + return;
> >
> > I think we should also invalidate any data slices associated with the
> > dynptrs? It seems natural that once a dynptr is invalidated, none of
> > its data slices should be usable.
> >
>
> Great catch, will fix.
>
> > > +}
> > > +
> > > static bool is_dynptr_reg_valid_uninit(struct bpf_verifier_env *env, struct bpf_reg_state *reg)
> > > {
> > > struct bpf_func_state *state = func(env, reg);
> > > @@ -3384,6 +3424,8 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
> > > env->insn_aux_data[insn_idx].sanitize_stack_spill = true;
> > > }
> > >
> > > + destroy_stack_slots_dynptr(env, state, spi);
> > > +
> > > mark_stack_slot_scratched(env, spi);
> > > if (reg && !(off % BPF_REG_SIZE) && register_is_bounded(reg) &&
> > > !register_is_null(reg) && env->bpf_capable) {
> > > @@ -3497,6 +3539,13 @@ static int check_stack_write_var_off(struct bpf_verifier_env *env,
> > > if (err)
> > > return err;
> > >
> > > + for (i = min_off; i < max_off; i++) {
> > > + int slot, spi;
> > > +
> > > + slot = -i - 1;
> > > + spi = slot / BPF_REG_SIZE;
> >
> > I think you can just use __get_spi() here
> >
>
> Ack.
>
> > > + destroy_stack_slots_dynptr(env, state, spi);
> >
> > I think here too,
> >
> > if (state->stack[spi].slot_type[0] == STACK_DYNPTR)
> > destroy_stack_slots_dynptr(env, state, spi)
> >
> > makes it more readable.
> >
> > And if it is a STACK_DYNPTR, we can also fast-forward i.
> >
>
> No issues with such a change, but it's going to precede almost every call to
> this function. I don't have a strong preference, but we could also call it
> destroy_if_dynptr_stack_slot to make it more clear the destructon is conditional
> and move it inside the function.
I don't have a strong preference either. Calling it
destroy_if_dynptr_stack_slot() sounds good as well.
>
> > [...]
next prev parent reply other threads:[~2023-01-12 19:09 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-01-01 8:33 [PATCH bpf-next v1 0/8] Dynptr fixes Kumar Kartikeya Dwivedi
2023-01-01 8:33 ` [PATCH bpf-next v1 1/8] bpf: Fix state pruning for STACK_DYNPTR stack slots Kumar Kartikeya Dwivedi
2023-01-02 19:28 ` Eduard Zingerman
2023-01-09 10:59 ` Kumar Kartikeya Dwivedi
2023-01-04 22:24 ` Andrii Nakryiko
2023-01-09 11:05 ` Kumar Kartikeya Dwivedi
2023-01-12 0:47 ` Andrii Nakryiko
2023-01-06 0:18 ` Joanne Koong
2023-01-09 11:17 ` Kumar Kartikeya Dwivedi
2023-01-01 8:33 ` [PATCH bpf-next v1 2/8] bpf: Fix missing var_off check for ARG_PTR_TO_DYNPTR Kumar Kartikeya Dwivedi
2023-01-04 22:32 ` Andrii Nakryiko
2023-01-09 11:18 ` Kumar Kartikeya Dwivedi
2023-01-06 0:57 ` Joanne Koong
2023-01-06 17:56 ` Joanne Koong
2023-01-09 11:21 ` Kumar Kartikeya Dwivedi
2023-01-01 8:33 ` [PATCH bpf-next v1 3/8] bpf: Fix partial dynptr stack slot reads/writes Kumar Kartikeya Dwivedi
2023-01-04 22:42 ` Andrii Nakryiko
2023-01-09 11:26 ` Kumar Kartikeya Dwivedi
2023-01-05 3:06 ` Alexei Starovoitov
2023-01-09 11:52 ` Kumar Kartikeya Dwivedi
2023-01-10 2:19 ` Alexei Starovoitov
2023-01-06 19:16 ` Joanne Koong
2023-01-06 19:31 ` Joanne Koong
2023-01-09 11:30 ` Kumar Kartikeya Dwivedi
2023-01-12 18:51 ` Joanne Koong [this message]
2023-01-01 8:33 ` [PATCH bpf-next v1 4/8] bpf: Allow reinitializing unreferenced dynptr stack slots Kumar Kartikeya Dwivedi
2023-01-04 22:44 ` Andrii Nakryiko
2023-01-06 19:33 ` Joanne Koong
2023-01-09 11:40 ` Kumar Kartikeya Dwivedi
2023-01-01 8:33 ` [PATCH bpf-next v1 5/8] selftests/bpf: Add dynptr pruning tests Kumar Kartikeya Dwivedi
2023-01-04 22:49 ` Andrii Nakryiko
2023-01-09 11:44 ` Kumar Kartikeya Dwivedi
2023-01-01 8:34 ` [PATCH bpf-next v1 6/8] selftests/bpf: Add dynptr var_off tests Kumar Kartikeya Dwivedi
2023-01-01 8:34 ` [PATCH bpf-next v1 7/8] selftests/bpf: Add dynptr partial slot overwrite tests Kumar Kartikeya Dwivedi
2023-01-01 8:34 ` [PATCH bpf-next v1 8/8] selftests/bpf: Add dynptr helper tests Kumar Kartikeya Dwivedi
2023-01-04 22:51 ` [PATCH bpf-next v1 0/8] Dynptr fixes Andrii Nakryiko
2023-01-12 1:08 ` Kumar Kartikeya Dwivedi
2023-01-13 22:31 ` Andrii Nakryiko
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAJnrk1b30vAs-pcgLF31Zr996w2GQD1ObkR2Lvp9ohT4SJ2+rQ@mail.gmail.com \
--to=joannelkoong@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=eddyz87@gmail.com \
--cc=martin.lau@kernel.org \
--cc=memxor@gmail.com \
--cc=void@manifault.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).