[bpf,v1,1/2] bpf: Suppress warning for non-zero off raw_tp arg NULL check

Commit Message

Kumar Kartikeya Dwivedi Dec. 4, 2024, 2:41 a.m. UTC

The fixed commit began marking raw_tp arguments as PTR_MAYBE_NULL to
avoid dead code elimination in the verifier, since raw_tp arguments
may actually be NULL at runtime. However, to preserve compatibility,
it simulated the raw_tp accesses as if the NULL marking was not present.

One of the behaviors permitted by this simulation is offset modification
for NULL pointers. Typically, this pattern is rejected by the verifier,
and users make workarounds to prevent the compiler from producing such
patterns. However, now that it is allowed, when the compiler emits such
code, the offset modification is allowed and a PTR_MAYBE_NULL raw_tp arg
with non-zero off can be formed.

The failing example program had the following pseudo-code:

r0 = 1024;
r1 = ...; // r1 = trusted_or_null_(id=1)
r3 = r1;  // r3 = trusted_or_null_(id=1) r1 = trusted_or_null_(id=1)
r3 += r0; // r3 = trusted_or_null_(id=1, off=1024)
if r1 == 0 goto pc+X;

At this point, while mark_ptr_or_null_reg will see PTR_MAYBE_NULL and
off == 0 for r1, it will notice non-zero off for r3, and the
WARN_ON_ONCE will fire, as the condition checks excluding register types
do not include raw_tp argument type.

This is a pattern produced by LLVM, therefore it is hard to suppress it
everywhere in BPF programs.

The right "generic" fix for this issue in general, will be permitting
offset modification for PTR_MAYBE_NULL pointers everywhere, and
enforcing that the instruction operand of a conditional jump has the
offset as zero. It's other copies may still have non-zero offset, and
that is fine. But this is more involved and will take longer to
integrate.

Hence, for now, when we notice raw_tp args with off != 0 when unmarking
NULL modifier, simply allocate such pointer a fresh id and remove them
from the "id" set being currently operated on, and leave them as is
without removing PTR_MAYBE_NULL marking.

Dereferencing such pointers will still work as the fixed commit allowed
it for raw_tp args.

This will mean that still, all registers with a given id and off = 0
will be unmarked, even if a register with off != 0 is NULL checked, but
this shouldn't introducing any incorrectness. Just that any register
with off != 0 excludes itself from the marking exercise by reassigning
itself a new id.

Fixes: cb4158ce8ec8 ("bpf: Mark raw_tp arguments with PTR_MAYBE_NULL")
Reported-by: Manu Bretelle <[e-mail]>
Signed-off-by: Kumar Kartikeya Dwivedi <[e-mail]>
---
 kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 39 insertions(+), 5 deletions(-)

Comments

Alexei Starovoitov Dec. 4, 2024, 4:37 p.m. UTC | #1

On Tue, Dec 3, 2024 at 6:42 PM Kumar Kartikeya Dwivedi <[e-mail]> wrote:
>
> The fixed commit began marking raw_tp arguments as PTR_MAYBE_NULL to
> avoid dead code elimination in the verifier, since raw_tp arguments
> may actually be NULL at runtime. However, to preserve compatibility,
> it simulated the raw_tp accesses as if the NULL marking was not present.
>
> One of the behaviors permitted by this simulation is offset modification
> for NULL pointers. Typically, this pattern is rejected by the verifier,
> and users make workarounds to prevent the compiler from producing such
> patterns. However, now that it is allowed, when the compiler emits such
> code, the offset modification is allowed and a PTR_MAYBE_NULL raw_tp arg
> with non-zero off can be formed.
>
> The failing example program had the following pseudo-code:
>
> r0 = 1024;
> r1 = ...; // r1 = trusted_or_null_(id=1)
> r3 = r1;  // r3 = trusted_or_null_(id=1) r1 = trusted_or_null_(id=1)
> r3 += r0; // r3 = trusted_or_null_(id=1, off=1024)
> if r1 == 0 goto pc+X;
>
> At this point, while mark_ptr_or_null_reg will see PTR_MAYBE_NULL and
> off == 0 for r1, it will notice non-zero off for r3, and the
> WARN_ON_ONCE will fire, as the condition checks excluding register types
> do not include raw_tp argument type.
>
> This is a pattern produced by LLVM, therefore it is hard to suppress it
> everywhere in BPF programs.
>
> The right "generic" fix for this issue in general, will be permitting
> offset modification for PTR_MAYBE_NULL pointers everywhere, and
> enforcing that the instruction operand of a conditional jump has the
> offset as zero. It's other copies may still have non-zero offset, and
> that is fine. But this is more involved and will take longer to
> integrate.
>
> Hence, for now, when we notice raw_tp args with off != 0 when unmarking
> NULL modifier, simply allocate such pointer a fresh id and remove them
> from the "id" set being currently operated on, and leave them as is
> without removing PTR_MAYBE_NULL marking.
>
> Dereferencing such pointers will still work as the fixed commit allowed
> it for raw_tp args.
>
> This will mean that still, all registers with a given id and off = 0
> will be unmarked, even if a register with off != 0 is NULL checked, but
> this shouldn't introducing any incorrectness. Just that any register
> with off != 0 excludes itself from the marking exercise by reassigning
> itself a new id.
>
> Fixes: cb4158ce8ec8 ("bpf: Mark raw_tp arguments with PTR_MAYBE_NULL")
> Reported-by: Manu Bretelle <[e-mail]>
> Signed-off-by: Kumar Kartikeya Dwivedi <[e-mail]>
> ---
>  kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++++++++++++++-----
>  1 file changed, 39 insertions(+), 5 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 1c4ebb326785..37504095a0bc 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -15335,7 +15335,8 @@ static int reg_set_min_max(struct bpf_verifier_env *env,
>         return err;
>  }
>
> -static void mark_ptr_or_null_reg(struct bpf_func_state *state,
> +static void mark_ptr_or_null_reg(struct bpf_verifier_env *env,
> +                                struct bpf_func_state *state,
>                                  struct bpf_reg_state *reg, u32 id,
>                                  bool is_null)
>  {
> @@ -15352,6 +15353,38 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,
>                  */
>                 if (WARN_ON_ONCE(reg->smin_value || reg->smax_value || !tnum_equals_const(reg->var_off, 0)))
>                         return;
> +               /* Unlike the MEM_ALLOC and NON_OWN_REF cases explicitly tested
> +                * below, where verifier will set off != 0, we allow users to
> +                * modify offset of PTR_MAYBE_NULL raw_tp args to preserve
> +                * compatibility since they were not marked NULL in older
> +                * kernels. This however means we may see a non-zero offset
> +                * register when marking them non-NULL in verifier state.
> +                * This can happen for the operand of the instruction:
> +                *
> +                * r1 = trusted_or_null_(id=1);
> +                * if r1 == 0 goto X;
> +                *
> +                * or a copy when LLVM produces code like below:
> +                *
> +                * r1 = trusted_or_null_(id=1);
> +                * r3 = r1; // r3 = trusted_or_null(id=1)
> +                * r3 += K; // r3 = trusted_or_null_(id=1, off=K)
> +                * if r1 == 0 goto X; // see r3.off != 0 when unmarking _or_null
> +                *
> +                * The right fix would be more generic: lift the restriction on
> +                * modifying reg->off for PTR_MAYBE_NULL pointers, and only
> +                * enforce it for the instruction operand of a NULL check, while
> +                * allowing non-zero off for other registers, but this is future
> +                * work.
> +                */

I think the comment is too verbose.
Especially considering that we're going to remove this hack in bpf-next.

I can trim it to bare minimum while applying if you're ok ?

> +               if (mask_raw_tp_reg_cond(env, reg) && reg->off) {
> +                       /* We don't reset reg->id back to 0, as it's unexpected
> +                        * when PTR_MAYBE_NULL is set. Simply give this reg a
> +                        * new id in case user decides to NULL check it again.
> +                        */
> +                       reg->id = ++env->id_gen;
> +                       return;
> +               }
>                 if (!(type_is_ptr_alloc_obj(reg->type) || type_is_non_owning_ref(reg->type)) &&
>                     WARN_ON_ONCE(reg->off))
>                         return;
> @@ -15385,7 +15418,8 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,
>  /* The logic is similar to find_good_pkt_pointers(), both could eventually
>   * be folded together at some point.
>   */
> -static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,
> +static void mark_ptr_or_null_regs(struct bpf_verifier_env *env,
> +                                 struct bpf_verifier_state *vstate, u32 regno,
>                                   bool is_null)
>  {
>         struct bpf_func_state *state = vstate->frame[vstate->curframe];
> @@ -15401,7 +15435,7 @@ static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,
>                 WARN_ON_ONCE(release_reference_state(state, id));
>
>         bpf_for_each_reg_in_vstate(vstate, state, reg, ({
> -               mark_ptr_or_null_reg(state, reg, id, is_null);
> +               mark_ptr_or_null_reg(env, state, reg, id, is_null);
>         }));
>  }
>
> @@ -15827,9 +15861,9 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
>                 /* Mark all identical registers in each branch as either
>                  * safe or unknown depending R == 0 or R != 0 conditional.
>                  */
> -               mark_ptr_or_null_regs(this_branch, insn->dst_reg,
> +               mark_ptr_or_null_regs(env, this_branch, insn->dst_reg,
>                                       opcode == BPF_JNE);
> -               mark_ptr_or_null_regs(other_branch, insn->dst_reg,
> +               mark_ptr_or_null_regs(env, other_branch, insn->dst_reg,
>                                       opcode == BPF_JEQ);
>         } else if (!try_match_pkt_pointers(insn, dst_reg, &regs[insn->src_reg],
>                                            this_branch, other_branch) &&
> --
> 2.43.5
>

Kumar Kartikeya Dwivedi Dec. 4, 2024, 6:55 p.m. UTC | #2

On Wed, 4 Dec 2024 at 17:37, Alexei Starovoitov
<[e-mail]> wrote:
>
> On Tue, Dec 3, 2024 at 6:42 PM Kumar Kartikeya Dwivedi <[e-mail]> wrote:
> >
> > The fixed commit began marking raw_tp arguments as PTR_MAYBE_NULL to
> > avoid dead code elimination in the verifier, since raw_tp arguments
> > may actually be NULL at runtime. However, to preserve compatibility,
> > it simulated the raw_tp accesses as if the NULL marking was not present.
> >
> > One of the behaviors permitted by this simulation is offset modification
> > for NULL pointers. Typically, this pattern is rejected by the verifier,
> > and users make workarounds to prevent the compiler from producing such
> > patterns. However, now that it is allowed, when the compiler emits such
> > code, the offset modification is allowed and a PTR_MAYBE_NULL raw_tp arg
> > with non-zero off can be formed.
> >
> > The failing example program had the following pseudo-code:
> >
> > r0 = 1024;
> > r1 = ...; // r1 = trusted_or_null_(id=1)
> > r3 = r1;  // r3 = trusted_or_null_(id=1) r1 = trusted_or_null_(id=1)
> > r3 += r0; // r3 = trusted_or_null_(id=1, off=1024)
> > if r1 == 0 goto pc+X;
> >
> > At this point, while mark_ptr_or_null_reg will see PTR_MAYBE_NULL and
> > off == 0 for r1, it will notice non-zero off for r3, and the
> > WARN_ON_ONCE will fire, as the condition checks excluding register types
> > do not include raw_tp argument type.
> >
> > This is a pattern produced by LLVM, therefore it is hard to suppress it
> > everywhere in BPF programs.
> >
> > The right "generic" fix for this issue in general, will be permitting
> > offset modification for PTR_MAYBE_NULL pointers everywhere, and
> > enforcing that the instruction operand of a conditional jump has the
> > offset as zero. It's other copies may still have non-zero offset, and
> > that is fine. But this is more involved and will take longer to
> > integrate.
> >
> > Hence, for now, when we notice raw_tp args with off != 0 when unmarking
> > NULL modifier, simply allocate such pointer a fresh id and remove them
> > from the "id" set being currently operated on, and leave them as is
> > without removing PTR_MAYBE_NULL marking.
> >
> > Dereferencing such pointers will still work as the fixed commit allowed
> > it for raw_tp args.
> >
> > This will mean that still, all registers with a given id and off = 0
> > will be unmarked, even if a register with off != 0 is NULL checked, but
> > this shouldn't introducing any incorrectness. Just that any register
> > with off != 0 excludes itself from the marking exercise by reassigning
> > itself a new id.
> >
> > Fixes: cb4158ce8ec8 ("bpf: Mark raw_tp arguments with PTR_MAYBE_NULL")
> > Reported-by: Manu Bretelle <[e-mail]>
> > Signed-off-by: Kumar Kartikeya Dwivedi <[e-mail]>
> > ---
> >  kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++++++++++++++-----
> >  1 file changed, 39 insertions(+), 5 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 1c4ebb326785..37504095a0bc 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -15335,7 +15335,8 @@ static int reg_set_min_max(struct bpf_verifier_env *env,
> >         return err;
> >  }
> >
> > -static void mark_ptr_or_null_reg(struct bpf_func_state *state,
> > +static void mark_ptr_or_null_reg(struct bpf_verifier_env *env,
> > +                                struct bpf_func_state *state,
> >                                  struct bpf_reg_state *reg, u32 id,
> >                                  bool is_null)
> >  {
> > @@ -15352,6 +15353,38 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,
> >                  */
> >                 if (WARN_ON_ONCE(reg->smin_value || reg->smax_value || !tnum_equals_const(reg->var_off, 0)))
> >                         return;
> > +               /* Unlike the MEM_ALLOC and NON_OWN_REF cases explicitly tested
> > +                * below, where verifier will set off != 0, we allow users to
> > +                * modify offset of PTR_MAYBE_NULL raw_tp args to preserve
> > +                * compatibility since they were not marked NULL in older
> > +                * kernels. This however means we may see a non-zero offset
> > +                * register when marking them non-NULL in verifier state.
> > +                * This can happen for the operand of the instruction:
> > +                *
> > +                * r1 = trusted_or_null_(id=1);
> > +                * if r1 == 0 goto X;
> > +                *
> > +                * or a copy when LLVM produces code like below:
> > +                *
> > +                * r1 = trusted_or_null_(id=1);
> > +                * r3 = r1; // r3 = trusted_or_null(id=1)
> > +                * r3 += K; // r3 = trusted_or_null_(id=1, off=K)
> > +                * if r1 == 0 goto X; // see r3.off != 0 when unmarking _or_null
> > +                *
> > +                * The right fix would be more generic: lift the restriction on
> > +                * modifying reg->off for PTR_MAYBE_NULL pointers, and only
> > +                * enforce it for the instruction operand of a NULL check, while
> > +                * allowing non-zero off for other registers, but this is future
> > +                * work.
> > +                */
>
> I think the comment is too verbose.
> Especially considering that we're going to remove this hack in bpf-next.
>
> I can trim it to bare minimum while applying if you're ok ?

No objections.

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1c4ebb326785..37504095a0bc 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15335,7 +15335,8 @@  static int reg_set_min_max(struct bpf_verifier_env *env,
 	return err;
 }
 
-static void mark_ptr_or_null_reg(struct bpf_func_state *state,
+static void mark_ptr_or_null_reg(struct bpf_verifier_env *env,
+				 struct bpf_func_state *state,
 				 struct bpf_reg_state *reg, u32 id,
 				 bool is_null)
 {
@@ -15352,6 +15353,38 @@  static void mark_ptr_or_null_reg(struct bpf_func_state *state,
 		 */
 		if (WARN_ON_ONCE(reg->smin_value || reg->smax_value || !tnum_equals_const(reg->var_off, 0)))
 			return;
+		/* Unlike the MEM_ALLOC and NON_OWN_REF cases explicitly tested
+		 * below, where verifier will set off != 0, we allow users to
+		 * modify offset of PTR_MAYBE_NULL raw_tp args to preserve
+		 * compatibility since they were not marked NULL in older
+		 * kernels. This however means we may see a non-zero offset
+		 * register when marking them non-NULL in verifier state.
+		 * This can happen for the operand of the instruction:
+		 *
+		 * r1 = trusted_or_null_(id=1);
+		 * if r1 == 0 goto X;
+		 *
+		 * or a copy when LLVM produces code like below:
+		 *
+		 * r1 = trusted_or_null_(id=1);
+		 * r3 = r1; // r3 = trusted_or_null(id=1)
+		 * r3 += K; // r3 = trusted_or_null_(id=1, off=K)
+		 * if r1 == 0 goto X; // see r3.off != 0 when unmarking _or_null
+		 *
+		 * The right fix would be more generic: lift the restriction on
+		 * modifying reg->off for PTR_MAYBE_NULL pointers, and only
+		 * enforce it for the instruction operand of a NULL check, while
+		 * allowing non-zero off for other registers, but this is future
+		 * work.
+		 */
+		if (mask_raw_tp_reg_cond(env, reg) && reg->off) {
+			/* We don't reset reg->id back to 0, as it's unexpected
+			 * when PTR_MAYBE_NULL is set. Simply give this reg a
+			 * new id in case user decides to NULL check it again.
+			 */
+			reg->id = ++env->id_gen;
+			return;
+		}
 		if (!(type_is_ptr_alloc_obj(reg->type) || type_is_non_owning_ref(reg->type)) &&
 		    WARN_ON_ONCE(reg->off))
 			return;
@@ -15385,7 +15418,8 @@  static void mark_ptr_or_null_reg(struct bpf_func_state *state,
 /* The logic is similar to find_good_pkt_pointers(), both could eventually
  * be folded together at some point.
  */
-static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,
+static void mark_ptr_or_null_regs(struct bpf_verifier_env *env,
+				  struct bpf_verifier_state *vstate, u32 regno,
 				  bool is_null)
 {
 	struct bpf_func_state *state = vstate->frame[vstate->curframe];
@@ -15401,7 +15435,7 @@  static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,
 		WARN_ON_ONCE(release_reference_state(state, id));
 
 	bpf_for_each_reg_in_vstate(vstate, state, reg, ({
-		mark_ptr_or_null_reg(state, reg, id, is_null);
+		mark_ptr_or_null_reg(env, state, reg, id, is_null);
 	}));
 }
 
@@ -15827,9 +15861,9 @@  static int check_cond_jmp_op(struct bpf_verifier_env *env,
 		/* Mark all identical registers in each branch as either
 		 * safe or unknown depending R == 0 or R != 0 conditional.
 		 */
-		mark_ptr_or_null_regs(this_branch, insn->dst_reg,
+		mark_ptr_or_null_regs(env, this_branch, insn->dst_reg,
 				      opcode == BPF_JNE);
-		mark_ptr_or_null_regs(other_branch, insn->dst_reg,
+		mark_ptr_or_null_regs(env, other_branch, insn->dst_reg,
 				      opcode == BPF_JEQ);
 	} else if (!try_match_pkt_pointers(insn, dst_reg, &regs[insn->src_reg],
 					   this_branch, other_branch) &&