[RFC bpf-next 0/2] bpf: verify scalar ids mapping in regsafe() using check_ids()

[RFC bpf-next 0/2] bpf: verify scalar ids mapping in regsafe() using check_ids()

[Eduard Zingerman]

Currently the following test case is considered safe by the verifier:

 1: r9 = ... some pointer with range X ...
 2: r6 = ... unbound scalar ID=a ...
 3: r7 = ... unbound scalar ID=b ...
 4: if (r6 > r7) goto +1
 5: r6 = r7
 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
 7: r9 += r7
 8: *(u64 *)r9 = Y
 
This happens because function regsafe() used (indirectly) form
is_state_visited() does not compare id mapping for scalar registers.

The following patch makes two chages:
- regsafe() is updated to use check_ids() for scalar registers;
- registers that obtain their range via find_equal_scalars() are
  marked as read in the parent checkpoint states. See
  mark_equal_scalars_as_read() for detailed explanation.

However, I'm not sure if mark_equal_scalars_as_read() is sufficient or
mark_chain_precision() should be called / updated as well.

In current form the patch does not have a big impact on the tests
verification time, as checked on BPF object files listed in
tools/testing/selftests/bpf/veristat.cfg and Cilium object files
obtained from [1]:

./veristat -e file,prog,insns,states -f 'insns_diff!=0' -C master.log current.log
File         Program                  Insns (A)  Insns (B)  Insns    (DIFF)  States (A)  States (B)  States (DIFF)
-----------  -----------------------  ---------  ---------  ---------------  ----------  ----------  -------------
bpf_host.o   cil_from_host                  556        603     +47 (+8.45%)          37          41   +4 (+10.81%)
bpf_xdp.o    tail_lb_ipv4                 77248      77302     +54 (+0.07%)        4643        4646    +3 (+0.06%)
loop6.bpf.o  trace_virtqueue_add_sgs      15144      18594  +3450 (+22.78%)         337         403  +66 (+19.58%)

A tweak adding !tnum_is_const(src_reg->var_off) in check_alu_op() is
necessary to achieve this.

[1] git@github.com:anakryiko/cilium.git

Eduard Zingerman (2):
  bpf: verify scalar ids mapping in regsafe() using check_ids()
  selftests/bpf: verify that check_ids() is used for scalars in
    regsafe()

 kernel/bpf/verifier.c                         | 87 ++++++++++++++++++-
 .../selftests/bpf/verifier/scalar_ids.c       | 61 +++++++++++++
 2 files changed, 146 insertions(+), 2 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/verifier/scalar_ids.c

-- 
2.34.1

[RFC bpf-next 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()

[Eduard Zingerman]

Prior to this commit the following unsafe example passed verification:

1: r9 = ... some pointer with range X ...
2: r6 = ... unbound scalar ID=a ...
3: r7 = ... unbound scalar ID=b ...
4: if (r6 > r7) goto +1
5: r6 = r7
6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
7: r9 += r7
8: *(u64 *)r9 = Y

This example is unsafe because not all execution paths verify r7 range.
Because of the jump at (4) the verifier would arrive at (6) in two states:
I.  r6{.id=b}, r7{.id=b} via path 1-6;
II. r6{.id=a}, r7{.id=b} via path 1-4, 6.

Currently regsafe() does not call check_ids() for scalar registers,
thus from POV of regsafe() states (I) and (II) are identical. If the
path 1-6 is taken by verifier first and checkpoint is created at (6)
the path 1-4, 6 would be considered safe.

This commit makes the following changes:
- a call to check_ids() is added in regsafe() for scalar registers case;
- a function mark_equal_scalars_as_read() is added to ensure that
  registers with identical IDs are preserved in the checkpoint states
  in case when find_equal_scalars() updates register range for several
  registers sharing the same ID.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 85 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6599d25dae38..8a5b7192514a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 				/* case: R1 = R2
 				 * copy register state to dest reg
 				 */
-				if (src_reg->type == SCALAR_VALUE && !src_reg->id)
+				if (src_reg->type == SCALAR_VALUE && !src_reg->id &&
+				    !tnum_is_const(src_reg->var_off))
 					/* Assign src and dst registers the same ID
 					 * that will be used by find_equal_scalars()
 					 * to propagate min/max range.
+					 * Skip constants to avoid allocation of useless ID.
 					 */
 					src_reg->id = ++env->id_gen;
 				*dst_reg = *src_reg;
@@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
 	return true;
 }
 
+/* Scalar ID generation in check_alu_op() and logic of
+ * find_equal_scalars() make the following pattern possible:
+ *
+ * 1: r9 = ... some pointer with range X ...
+ * 2: r6 = ... unbound scalar ID=a ...
+ * 3: r7 = ... unbound scalar ID=b ...
+ * 4: if (r6 > r7) goto +1
+ * 5: r6 = r7
+ * 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
+ * 7: r9 += r7
+ * 8: *(u64 *)r9 = Y
+ *
+ * Because of the jump at (4) the verifier would arrive at (6) in two states:
+ * I.  r6{.id=b}, r7{.id=b}
+ * II. r6{.id=a}, r7{.id=b}
+ *
+ * Relevant facts:
+ * - regsafe() matches ID mappings for scalars using check_ids(), this makes
+ *   states (I) and (II) non-equal;
+ * - clean_func_state() removes registers not marked as REG_LIVE_READ from
+ *   checkpoint states;
+ * - mark_reg_read() modifies reg->live for reg->parent (and it's parents);
+ * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning
+ *   that parent pointers are copied as well.
+ *
+ * Thus, for execution path 1-6:
+ * - both r6->parent and r7->parent point to the same register in the parent state (r7);
+ * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark;
+ * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT).
+ *
+ * Consequently, when execution path 1-4, 6 reaches (6) in state (II)
+ * regsafe() won't be able to see a mismatch in ID mappings.
+ *
+ * To avoid this issue mark_equal_scalars_as_read() conservatively
+ * marks all registers with matching ID as REG_LIVE_READ, thus
+ * preserving r6 and r7 in the checkpoint state for the example above.
+ */
+static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id)
+{
+	struct bpf_verifier_state *st;
+	struct bpf_func_state *state;
+	struct bpf_reg_state *reg;
+	bool move_up;
+	int i = 0;
+
+	for (st = vstate, move_up = true; st && move_up; st = st->parent) {
+		move_up = false;
+		bpf_for_each_reg_in_vstate(st, state, reg, ({
+			if (reg->type == SCALAR_VALUE && reg->id == id &&
+			    !(reg->live & REG_LIVE_READ)) {
+				reg->live |= REG_LIVE_READ;
+				move_up = true;
+			}
+			++i;
+		}));
+	}
+}
+
 static void find_equal_scalars(struct bpf_verifier_state *vstate,
 			       struct bpf_reg_state *known_reg)
 {
 	struct bpf_func_state *state;
 	struct bpf_reg_state *reg;
+	int count = 0;
 
 	bpf_for_each_reg_in_vstate(vstate, state, reg, ({
-		if (reg->type == SCALAR_VALUE && reg->id == known_reg->id)
+		if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) {
 			*reg = *known_reg;
+			++count;
+		}
 	}));
+
+	/* Count equal to 1 means that find_equal_scalars have not
+	 * found any registers with the same ID (except self), thus
+	 * the range knowledge have not been transferred and there is
+	 * no need to preserve registers with the same ID in a parent
+	 * state.
+	 */
+	if (count > 1)
+		mark_equal_scalars_as_read(vstate->parent, known_reg->id);
 }
 
 static int check_cond_jmp_op(struct bpf_verifier_env *env,
@@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		 */
 		return equal && rold->frameno == rcur->frameno;
 
+	/* even if two registers are identical the id mapping might diverge
+	 * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2}
+	 */
+	if (equal && rold->type == SCALAR_VALUE && rold->id)
+		return check_ids(rold->id, rcur->id, idmap);
+
 	if (equal)
 		return true;
 
@@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		if (env->explore_alu_limits)
 			return false;
 		if (rcur->type == SCALAR_VALUE) {
+			/* id relations must be preserved, see comment in
+			 * mark_equal_scalars_as_read() for SCALAR_VALUE example.
+			 */
+			if (rold->id && !check_ids(rold->id, rcur->id, idmap))
+				return false;
 			if (!rold->precise)
 				return true;
 			/* new val must satisfy old val knowledge */
-- 
2.34.1

Re: [RFC bpf-next 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()

[Andrii Nakryiko]

On Mon, Nov 28, 2022 at 8:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Prior to this commit the following unsafe example passed verification:
>
> 1: r9 = ... some pointer with range X ...
> 2: r6 = ... unbound scalar ID=a ...
> 3: r7 = ... unbound scalar ID=b ...
> 4: if (r6 > r7) goto +1
> 5: r6 = r7
> 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
> 7: r9 += r7
> 8: *(u64 *)r9 = Y
>
> This example is unsafe because not all execution paths verify r7 range.
> Because of the jump at (4) the verifier would arrive at (6) in two states:
> I.  r6{.id=b}, r7{.id=b} via path 1-6;
> II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
>
> Currently regsafe() does not call check_ids() for scalar registers,
> thus from POV of regsafe() states (I) and (II) are identical. If the
> path 1-6 is taken by verifier first and checkpoint is created at (6)
> the path 1-4, 6 would be considered safe.
>
> This commit makes the following changes:
> - a call to check_ids() is added in regsafe() for scalar registers case;
> - a function mark_equal_scalars_as_read() is added to ensure that
>   registers with identical IDs are preserved in the checkpoint states
>   in case when find_equal_scalars() updates register range for several
>   registers sharing the same ID.
>

Fixes tag missing?

These are tricky changes with subtle details. Let's split check_ids()
change and all the liveness manipulations into separate patches? They
are conceptually completely independent, right?


> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 85 insertions(+), 2 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 6599d25dae38..8a5b7192514a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
>                                 /* case: R1 = R2
>                                  * copy register state to dest reg
>                                  */
> -                               if (src_reg->type == SCALAR_VALUE && !src_reg->id)
> +                               if (src_reg->type == SCALAR_VALUE && !src_reg->id &&
> +                                   !tnum_is_const(src_reg->var_off))
>                                         /* Assign src and dst registers the same ID
>                                          * that will be used by find_equal_scalars()
>                                          * to propagate min/max range.
> +                                        * Skip constants to avoid allocation of useless ID.
>                                          */
>                                         src_reg->id = ++env->id_gen;
>                                 *dst_reg = *src_reg;
> @@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
>         return true;
>  }
>
> +/* Scalar ID generation in check_alu_op() and logic of
> + * find_equal_scalars() make the following pattern possible:
> + *
> + * 1: r9 = ... some pointer with range X ...
> + * 2: r6 = ... unbound scalar ID=a ...
> + * 3: r7 = ... unbound scalar ID=b ...
> + * 4: if (r6 > r7) goto +1
> + * 5: r6 = r7
> + * 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
> + * 7: r9 += r7
> + * 8: *(u64 *)r9 = Y
> + *
> + * Because of the jump at (4) the verifier would arrive at (6) in two states:
> + * I.  r6{.id=b}, r7{.id=b}
> + * II. r6{.id=a}, r7{.id=b}
> + *
> + * Relevant facts:
> + * - regsafe() matches ID mappings for scalars using check_ids(), this makes
> + *   states (I) and (II) non-equal;
> + * - clean_func_state() removes registers not marked as REG_LIVE_READ from
> + *   checkpoint states;
> + * - mark_reg_read() modifies reg->live for reg->parent (and it's parents);
> + * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning
> + *   that parent pointers are copied as well.

not too familiar with liveness handling, but is this correct and
expected? Should this be fixed instead of REG_LIVE_READ manipulations?

> + *
> + * Thus, for execution path 1-6:
> + * - both r6->parent and r7->parent point to the same register in the parent state (r7);
> + * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark;

I'm trying to understand this. Clearly both r6 and r7 are read. r6 for
if (r6 > X) check, r7 for r9 manipulations. Why do we end up not
marking one of them as read using a normal logic?

I have this bad feeling I'm missing something very important here or
we have some bug somewhere else. So please help me understand which
one it is. This special liveness manipulation seems wrong.

My concern is that if I have some code like

r6 = r7;
r9 += r6;

and I never use r7 anymore after that, then we should be able to
forget r7 and treat it as NOT_INIT. But you are saying it's unsafe
right now and that doesn't make much sense to me.


> + * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT).
> + *
> + * Consequently, when execution path 1-4, 6 reaches (6) in state (II)
> + * regsafe() won't be able to see a mismatch in ID mappings.
> + *
> + * To avoid this issue mark_equal_scalars_as_read() conservatively
> + * marks all registers with matching ID as REG_LIVE_READ, thus
> + * preserving r6 and r7 in the checkpoint state for the example above.
> + */
> +static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id)
> +{
> +       struct bpf_verifier_state *st;
> +       struct bpf_func_state *state;
> +       struct bpf_reg_state *reg;
> +       bool move_up;
> +       int i = 0;
> +
> +       for (st = vstate, move_up = true; st && move_up; st = st->parent) {
> +               move_up = false;
> +               bpf_for_each_reg_in_vstate(st, state, reg, ({
> +                       if (reg->type == SCALAR_VALUE && reg->id == id &&
> +                           !(reg->live & REG_LIVE_READ)) {
> +                               reg->live |= REG_LIVE_READ;
> +                               move_up = true;
> +                       }
> +                       ++i;
> +               }));
> +       }
> +}
> +
>  static void find_equal_scalars(struct bpf_verifier_state *vstate,
>                                struct bpf_reg_state *known_reg)
>  {
>         struct bpf_func_state *state;
>         struct bpf_reg_state *reg;
> +       int count = 0;
>
>         bpf_for_each_reg_in_vstate(vstate, state, reg, ({
> -               if (reg->type == SCALAR_VALUE && reg->id == known_reg->id)
> +               if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) {
>                         *reg = *known_reg;
> +                       ++count;
> +               }
>         }));
> +
> +       /* Count equal to 1 means that find_equal_scalars have not
> +        * found any registers with the same ID (except self), thus
> +        * the range knowledge have not been transferred and there is
> +        * no need to preserve registers with the same ID in a parent
> +        * state.
> +        */
> +       if (count > 1)
> +               mark_equal_scalars_as_read(vstate->parent, known_reg->id);
>  }
>
>  static int check_cond_jmp_op(struct bpf_verifier_env *env,
> @@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
>                  */
>                 return equal && rold->frameno == rcur->frameno;
>
> +       /* even if two registers are identical the id mapping might diverge
> +        * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2}
> +        */
> +       if (equal && rold->type == SCALAR_VALUE && rold->id)
> +               return check_ids(rold->id, rcur->id, idmap);

nit: let's teach check_ids() to handle the id == 0 case properly
instead of guarding everything with `if (rold->id)`?

but also I think this applies not just to SCALARs, right? the memcmp()
check above has to be augmented with check_ids() for id and ref_obj_id

> +
>         if (equal)
>                 return true;
>
> @@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
>                 if (env->explore_alu_limits)
>                         return false;
>                 if (rcur->type == SCALAR_VALUE) {
> +                       /* id relations must be preserved, see comment in
> +                        * mark_equal_scalars_as_read() for SCALAR_VALUE example.
> +                        */
> +                       if (rold->id && !check_ids(rold->id, rcur->id, idmap))
> +                               return false;
>                         if (!rold->precise)
>                                 return true;
>                         /* new val must satisfy old val knowledge */
> --
> 2.34.1
>

Re: [RFC bpf-next 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()

[Eduard Zingerman]

On Wed, 2022-11-30 at 16:26 -0800, Andrii Nakryiko wrote:
> On Mon, Nov 28, 2022 at 8:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > Prior to this commit the following unsafe example passed verification:
> > 
> > 1: r9 = ... some pointer with range X ...
> > 2: r6 = ... unbound scalar ID=a ...
> > 3: r7 = ... unbound scalar ID=b ...
> > 4: if (r6 > r7) goto +1
> > 5: r6 = r7
> > 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
> > 7: r9 += r7
> > 8: *(u64 *)r9 = Y
> > 
> > This example is unsafe because not all execution paths verify r7 range.
> > Because of the jump at (4) the verifier would arrive at (6) in two states:
> > I.  r6{.id=b}, r7{.id=b} via path 1-6;
> > II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
> > 
> > Currently regsafe() does not call check_ids() for scalar registers,
> > thus from POV of regsafe() states (I) and (II) are identical. If the
> > path 1-6 is taken by verifier first and checkpoint is created at (6)
> > the path 1-4, 6 would be considered safe.
> > 
> > This commit makes the following changes:
> > - a call to check_ids() is added in regsafe() for scalar registers case;
> > - a function mark_equal_scalars_as_read() is added to ensure that
> >   registers with identical IDs are preserved in the checkpoint states
> >   in case when find_equal_scalars() updates register range for several
> >   registers sharing the same ID.
> > 
> 
> Fixes tag missing?
> 
> These are tricky changes with subtle details. Let's split check_ids()
> change and all the liveness manipulations into separate patches? They
> are conceptually completely independent, right?
> 
> 
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> >  kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
> >  1 file changed, 85 insertions(+), 2 deletions(-)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 6599d25dae38..8a5b7192514a 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
> >                                 /* case: R1 = R2
> >                                  * copy register state to dest reg
> >                                  */
> > -                               if (src_reg->type == SCALAR_VALUE && !src_reg->id)
> > +                               if (src_reg->type == SCALAR_VALUE && !src_reg->id &&
> > +                                   !tnum_is_const(src_reg->var_off))
> >                                         /* Assign src and dst registers the same ID
> >                                          * that will be used by find_equal_scalars()
> >                                          * to propagate min/max range.
> > +                                        * Skip constants to avoid allocation of useless ID.
> >                                          */
> >                                         src_reg->id = ++env->id_gen;
> >                                 *dst_reg = *src_reg;
> > @@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> >         return true;
> >  }
> > 
> > +/* Scalar ID generation in check_alu_op() and logic of
> > + * find_equal_scalars() make the following pattern possible:
> > + *
> > + * 1: r9 = ... some pointer with range X ...
> > + * 2: r6 = ... unbound scalar ID=a ...
> > + * 3: r7 = ... unbound scalar ID=b ...
> > + * 4: if (r6 > r7) goto +1
> > + * 5: r6 = r7
> > + * 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
> > + * 7: r9 += r7
> > + * 8: *(u64 *)r9 = Y
> > + *
> > + * Because of the jump at (4) the verifier would arrive at (6) in two states:
> > + * I.  r6{.id=b}, r7{.id=b}
> > + * II. r6{.id=a}, r7{.id=b}
> > + *
> > + * Relevant facts:
> > + * - regsafe() matches ID mappings for scalars using check_ids(), this makes
> > + *   states (I) and (II) non-equal;
> > + * - clean_func_state() removes registers not marked as REG_LIVE_READ from
> > + *   checkpoint states;
> > + * - mark_reg_read() modifies reg->live for reg->parent (and it's parents);
> > + * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning
> > + *   that parent pointers are copied as well.
> 
> not too familiar with liveness handling, but is this correct and
> expected? Should this be fixed instead of REG_LIVE_READ manipulations?

Well, that's what I wanted to ask, actually :)
Here is how current logic works:
- is_state_visited() has the following two loops in the end:

	for (j = 0; j <= cur->curframe; j++) {
		for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++)
			cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i];
		for (i = 0; i < BPF_REG_FP; i++)
			cur->frame[j]->regs[i].live = REG_LIVE_NONE;
	}

	/* all stack frames are accessible from callee, clear them all */
	for (j = 0; j <= cur->curframe; j++) {
		struct bpf_func_state *frame = cur->frame[j];
		struct bpf_func_state *newframe = new->frame[j];

		for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) {
			frame->stack[i].spilled_ptr.live = REG_LIVE_NONE;
			frame->stack[i].spilled_ptr.parent =
						&newframe->stack[i].spilled_ptr;
		}
	}

  These connect the bpf_reg_state members of the new state with
  corresponding (index-wise) members of the parent state.
- find_equal_scalars() looks as follows:
  static void find_equal_scalars(struct bpf_verifier_state *vstate,
                               struct bpf_reg_state *known_reg)
  {
	struct bpf_func_state *state;
	struct bpf_reg_state *reg;

	bpf_for_each_reg_in_vstate(vstate, state, reg, ({
		if (reg->type == SCALAR_VALUE && reg->id == known_reg->id)
			*reg = *known_reg;  // <--- full copy, incl. parent pointer
	}));
  }
- mark_reg_read() updates the ->live field of the *parent* register
  when called only if ->live field of the *current* register is not
  marked as written.
- in case if register is overwritten it's ->live field is marked as
  written, e.g. see check_stack_read_fixed_off().
  
Suppose we have an example:

---- checkpoint ----
r1 = r0               ; now r1.parent == &checkpoint->regs[0]
r2 = r1               ; now r2.parent == &checkpoint->regs[0]
if (r1 == 0) goto +42
...

Given the above logic only &checkpoint->regs[0] would receive read
marks. Although I'm not the original author but this behavior seem to
make sense.

> 
> > + *
> > + * Thus, for execution path 1-6:
> > + * - both r6->parent and r7->parent point to the same register in the parent state (r7);
> > + * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark;
> 
> I'm trying to understand this. Clearly both r6 and r7 are read. r6 for
> if (r6 > X) check, r7 for r9 manipulations. Why do we end up not
> marking one of them as read using a normal logic?

When (r6 > X) is processed find_equal_scalars() updates parent
pointers for all registers with the same ID as r6, in this case only
for r7. So, after find_equal_scalars() is done both current state r6
and r7 ->parent point to the r6 of the latest checkpoint state.

> 
> I have this bad feeling I'm missing something very important here or
> we have some bug somewhere else. So please help me understand which
> one it is. This special liveness manipulation seems wrong.
> 
> My concern is that if I have some code like
> 
> r6 = r7;
> r9 += r6;
> 
> and I never use r7 anymore after that, then we should be able to
> forget r7 and treat it as NOT_INIT. But you are saying it's unsafe
> right now and that doesn't make much sense to me.

It is unsafe because of the "spooky action at a distance" produced by
a combination of:
- allocation of scalar IDs for moves, see check_alu_op() case for
  64-bit move;
- find_equal_scalars() that propagates range, this one is only
  executed for conditional jumps.

> 
> 
> > + * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT).
> > + *
> > + * Consequently, when execution path 1-4, 6 reaches (6) in state (II)
> > + * regsafe() won't be able to see a mismatch in ID mappings.
> > + *
> > + * To avoid this issue mark_equal_scalars_as_read() conservatively
> > + * marks all registers with matching ID as REG_LIVE_READ, thus
> > + * preserving r6 and r7 in the checkpoint state for the example above.
> > + */
> > +static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id)
> > +{
> > +       struct bpf_verifier_state *st;
> > +       struct bpf_func_state *state;
> > +       struct bpf_reg_state *reg;
> > +       bool move_up;
> > +       int i = 0;
> > +
> > +       for (st = vstate, move_up = true; st && move_up; st = st->parent) {
> > +               move_up = false;
> > +               bpf_for_each_reg_in_vstate(st, state, reg, ({
> > +                       if (reg->type == SCALAR_VALUE && reg->id == id &&
> > +                           !(reg->live & REG_LIVE_READ)) {
> > +                               reg->live |= REG_LIVE_READ;
> > +                               move_up = true;
> > +                       }
> > +                       ++i;
> > +               }));
> > +       }
> > +}
> > +
> >  static void find_equal_scalars(struct bpf_verifier_state *vstate,
> >                                struct bpf_reg_state *known_reg)
> >  {
> >         struct bpf_func_state *state;
> >         struct bpf_reg_state *reg;
> > +       int count = 0;
> > 
> >         bpf_for_each_reg_in_vstate(vstate, state, reg, ({
> > -               if (reg->type == SCALAR_VALUE && reg->id == known_reg->id)
> > +               if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) {
> >                         *reg = *known_reg;
> > +                       ++count;
> > +               }
> >         }));
> > +
> > +       /* Count equal to 1 means that find_equal_scalars have not
> > +        * found any registers with the same ID (except self), thus
> > +        * the range knowledge have not been transferred and there is
> > +        * no need to preserve registers with the same ID in a parent
> > +        * state.
> > +        */
> > +       if (count > 1)
> > +               mark_equal_scalars_as_read(vstate->parent, known_reg->id);
> >  }
> > 
> >  static int check_cond_jmp_op(struct bpf_verifier_env *env,
> > @@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> >                  */
> >                 return equal && rold->frameno == rcur->frameno;
> > 
> > +       /* even if two registers are identical the id mapping might diverge
> > +        * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2}
> > +        */
> > +       if (equal && rold->type == SCALAR_VALUE && rold->id)
> > +               return check_ids(rold->id, rcur->id, idmap);
> 
> nit: let's teach check_ids() to handle the id == 0 case properly
> instead of guarding everything with `if (rold->id)`?
> 
> but also I think this applies not just to SCALARs, right? the memcmp()
> check above has to be augmented with check_ids() for id and ref_obj_id

Yes, it is the same issue as described in [1] as you pointed out.
I'll updated it for other branches, but I want the main issue to
be sorted out first.

[1] https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/

> 
> > +
> >         if (equal)
> >                 return true;
> > 
> > @@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> >                 if (env->explore_alu_limits)
> >                         return false;
> >                 if (rcur->type == SCALAR_VALUE) {
> > +                       /* id relations must be preserved, see comment in
> > +                        * mark_equal_scalars_as_read() for SCALAR_VALUE example.
> > +                        */
> > +                       if (rold->id && !check_ids(rold->id, rcur->id, idmap))
> > +                               return false;
> >                         if (!rold->precise)
> >                                 return true;
> >                         /* new val must satisfy old val knowledge */
> > --
> > 2.34.1
> > 

Re: [RFC bpf-next 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()

[Eduard Zingerman]

On Thu, 2022-12-01 at 03:14 +0200, Eduard Zingerman wrote:
> On Wed, 2022-11-30 at 16:26 -0800, Andrii Nakryiko wrote:
> > On Mon, Nov 28, 2022 at 8:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > 
> > > Prior to this commit the following unsafe example passed verification:
> > > 
> > > 1: r9 = ... some pointer with range X ...
> > > 2: r6 = ... unbound scalar ID=a ...
> > > 3: r7 = ... unbound scalar ID=b ...
> > > 4: if (r6 > r7) goto +1
> > > 5: r6 = r7
> > > 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
> > > 7: r9 += r7
> > > 8: *(u64 *)r9 = Y
> > > 
> > > This example is unsafe because not all execution paths verify r7 range.
> > > Because of the jump at (4) the verifier would arrive at (6) in two states:
> > > I.  r6{.id=b}, r7{.id=b} via path 1-6;
> > > II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
> > > 
> > > Currently regsafe() does not call check_ids() for scalar registers,
> > > thus from POV of regsafe() states (I) and (II) are identical. If the
> > > path 1-6 is taken by verifier first and checkpoint is created at (6)
> > > the path 1-4, 6 would be considered safe.
> > > 
> > > This commit makes the following changes:
> > > - a call to check_ids() is added in regsafe() for scalar registers case;
> > > - a function mark_equal_scalars_as_read() is added to ensure that
> > >   registers with identical IDs are preserved in the checkpoint states
> > >   in case when find_equal_scalars() updates register range for several
> > >   registers sharing the same ID.
> > > 
> > 
> > Fixes tag missing?
> > 
> > These are tricky changes with subtle details. Let's split check_ids()
> > change and all the liveness manipulations into separate patches? They
> > are conceptually completely independent, right?
> > 
> > 
> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > ---
> > >  kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
> > >  1 file changed, 85 insertions(+), 2 deletions(-)
> > > 
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 6599d25dae38..8a5b7192514a 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
> > >                                 /* case: R1 = R2
> > >                                  * copy register state to dest reg
> > >                                  */
> > > -                               if (src_reg->type == SCALAR_VALUE && !src_reg->id)
> > > +                               if (src_reg->type == SCALAR_VALUE && !src_reg->id &&
> > > +                                   !tnum_is_const(src_reg->var_off))
> > >                                         /* Assign src and dst registers the same ID
> > >                                          * that will be used by find_equal_scalars()
> > >                                          * to propagate min/max range.
> > > +                                        * Skip constants to avoid allocation of useless ID.
> > >                                          */
> > >                                         src_reg->id = ++env->id_gen;
> > >                                 *dst_reg = *src_reg;
> > > @@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> > >         return true;
> > >  }
> > > 
> > > +/* Scalar ID generation in check_alu_op() and logic of
> > > + * find_equal_scalars() make the following pattern possible:
> > > + *
> > > + * 1: r9 = ... some pointer with range X ...
> > > + * 2: r6 = ... unbound scalar ID=a ...
> > > + * 3: r7 = ... unbound scalar ID=b ...
> > > + * 4: if (r6 > r7) goto +1
> > > + * 5: r6 = r7
> > > + * 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
> > > + * 7: r9 += r7
> > > + * 8: *(u64 *)r9 = Y
> > > + *
> > > + * Because of the jump at (4) the verifier would arrive at (6) in two states:
> > > + * I.  r6{.id=b}, r7{.id=b}
> > > + * II. r6{.id=a}, r7{.id=b}
> > > + *
> > > + * Relevant facts:
> > > + * - regsafe() matches ID mappings for scalars using check_ids(), this makes
> > > + *   states (I) and (II) non-equal;
> > > + * - clean_func_state() removes registers not marked as REG_LIVE_READ from
> > > + *   checkpoint states;
> > > + * - mark_reg_read() modifies reg->live for reg->parent (and it's parents);
> > > + * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning
> > > + *   that parent pointers are copied as well.
> > 
> > not too familiar with liveness handling, but is this correct and
> > expected? Should this be fixed instead of REG_LIVE_READ manipulations?


TLDR:

- looks like it is safe to avoid bpf_reg_state->parent update when
  registers are copied, but it has some performance impact. If this
  impact is acceptable I'd like to move this way are remove
  mark_equal_scalars_as_read().

- unrelated question: does anything has to be done to
  __mark_chain_precision to make it know about shared scalar IDs?
  E.g. in the following case:
    ...
  --- checkpoint 1 --- r6 would be marked as precise here
  r6 = r7
    ...
  --- checkpoint 2 --- r6 won't be marked as precise here
    ...
  if r6 < 10
  --- checkpoint 3 ---
  fp[r7] = 42
  
  The additional precision marks could be inferred if additional info
  is added the jump stack.

-----
Long version about bpf_reg_state->parent.

All functions that copy register states:
- save_register_state()
  Register is copied to stack spill location.

- check_kfunc_mem_size_reg()
  Makes a tmp register copy, harmless.

- sanitize_ptr_alu()
  Register copy is visible in the speculative branch.

- check_alu_op()
  Register is copied when reg to reg MOV is processed.

- find_equal_scalars()
  Register is copied to the registers with the same ID.

Original commit introducing bpf_reg_state->parent:
- 679c782de14bd48c19dd74cd1af20a2bc05dd936 2018-08-30
  bpf/verifier: per-register parent pointers
  
  Updates mark_reg_read() and removes mark_stack_slot_read().
  Previous version accessed parent state registers directly using
  regno w/o any additional manipulations.

  In this commit:
  - save_register_state() - does not exist yet, its function is
    performed by check_stack_write(), has a direct register state copy
    as in save_register_state();
  - check_kfunc_mem_size_reg() - does not exist yet;
  - sanitize_ptr_alu() - does not exist yet;
  - check_alu_op() - has a direct register state copy unchanged for
    reg to reg MOV.

Commit introducing find_equal_scalars():
- 75748837b7e56919679e02163f45d5818c644d03 2020-10-09
  bpf: Propagate scalar ranges through register assignments.
  
  Has a direct register copy *reg = *known_reg.

It looks like that for places where registers are copied ->parent
change is an unintentional side effect. Removal of this side effect
might in theory lead to some additional register read marks, e.g. in
this case:

  r6 = r7
  if (r6 > X) goto +42
  r5 = r7              ; this would lead to a read mark on r7 not
                       ; present previously.

This should not hinder correctness.
However, there is some negative performance impact:

$ ./veristat -e file,prog,states -f 'states_pct!=0' -C master-baseline.log current.log 
File                      Program                           States (A)  States (B)  States  (DIFF)
------------------------  --------------------------------  ----------  ----------  --------------
bpf_host.o                cil_to_netdev                            358         455   +97 (+27.09%)
bpf_host.o                tail_handle_nat_fwd_ipv4                1746        1891   +145 (+8.30%)
bpf_host.o                tail_handle_nat_fwd_ipv6                 709         717     +8 (+1.13%)
bpf_host.o                tail_nodeport_ipv4_dsr                    31          42   +11 (+35.48%)
bpf_host.o                tail_nodeport_nat_egress_ipv4           2269        2274     +5 (+0.22%)
bpf_host.o                tail_nodeport_nat_ingress_ipv4           276         316   +40 (+14.49%)
bpf_host.o                tail_nodeport_nat_ingress_ipv6           243         254    +11 (+4.53%)
bpf_lxc.o                 tail_handle_nat_fwd_ipv4                1746        1891   +145 (+8.30%)
bpf_lxc.o                 tail_handle_nat_fwd_ipv6                 709         717     +8 (+1.13%)
bpf_lxc.o                 tail_ipv4_ct_egress                      248         251     +3 (+1.21%)
bpf_lxc.o                 tail_ipv4_ct_ingress                     248         251     +3 (+1.21%)
bpf_lxc.o                 tail_ipv4_ct_ingress_policy_only         248         251     +3 (+1.21%)
bpf_lxc.o                 tail_nodeport_ipv4_dsr                    31          42   +11 (+35.48%)
bpf_lxc.o                 tail_nodeport_nat_ingress_ipv4           276         316   +40 (+14.49%)
bpf_lxc.o                 tail_nodeport_nat_ingress_ipv6           243         254    +11 (+4.53%)
bpf_overlay.o             tail_handle_nat_fwd_ipv4                1082        1109    +27 (+2.50%)
bpf_overlay.o             tail_nodeport_ipv4_dsr                    31          42   +11 (+35.48%)
bpf_overlay.o             tail_nodeport_nat_egress_ipv4           2238        2243     +5 (+0.22%)
bpf_overlay.o             tail_nodeport_nat_ingress_ipv4           276         316   +40 (+14.49%)
bpf_overlay.o             tail_nodeport_nat_ingress_ipv6           243         254    +11 (+4.53%)
bpf_sock.o                cil_sock4_connect                         47          64   +17 (+36.17%)
bpf_sock.o                cil_sock4_sendmsg                         45          62   +17 (+37.78%)
bpf_xdp.o                 tail_handle_nat_fwd_ipv4                1461        1912  +451 (+30.87%)
bpf_xdp.o                 tail_lb_ipv4                            4643        4738    +95 (+2.05%)
bpf_xdp.o                 tail_nodeport_nat_egress_ipv4           1066        1069     +3 (+0.28%)
bpf_xdp.o                 tail_rev_nodeport_lb4                    404         411     +7 (+1.73%)
bpf_xdp.o                 tail_rev_nodeport_lb6                   1076        1083     +7 (+0.65%)
pyperf600_bpf_loop.bpf.o  on_event                                 285         287     +2 (+0.70%)
xdp_synproxy_kern.bpf.o   syncookie_tc                           22513       22564    +51 (+0.23%)
xdp_synproxy_kern.bpf.o   syncookie_xdp                          22207       24206  +1999 (+9.00%)
------------------------  --------------------------------  ----------  ----------  --------------

> 
> Well, that's what I wanted to ask, actually :)
> Here is how current logic works:
> - is_state_visited() has the following two loops in the end:
> 
> 	for (j = 0; j <= cur->curframe; j++) {
> 		for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++)
> 			cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i];
> 		for (i = 0; i < BPF_REG_FP; i++)
> 			cur->frame[j]->regs[i].live = REG_LIVE_NONE;
> 	}
> 
> 	/* all stack frames are accessible from callee, clear them all */
> 	for (j = 0; j <= cur->curframe; j++) {
> 		struct bpf_func_state *frame = cur->frame[j];
> 		struct bpf_func_state *newframe = new->frame[j];
> 
> 		for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) {
> 			frame->stack[i].spilled_ptr.live = REG_LIVE_NONE;
> 			frame->stack[i].spilled_ptr.parent =
> 						&newframe->stack[i].spilled_ptr;
> 		}
> 	}
> 
>   These connect the bpf_reg_state members of the new state with
>   corresponding (index-wise) members of the parent state.
> - find_equal_scalars() looks as follows:
>   static void find_equal_scalars(struct bpf_verifier_state *vstate,
>                                struct bpf_reg_state *known_reg)
>   {
> 	struct bpf_func_state *state;
> 	struct bpf_reg_state *reg;
> 
> 	bpf_for_each_reg_in_vstate(vstate, state, reg, ({
> 		if (reg->type == SCALAR_VALUE && reg->id == known_reg->id)
> 			*reg = *known_reg;  // <--- full copy, incl. parent pointer
> 	}));
>   }
> - mark_reg_read() updates the ->live field of the *parent* register
>   when called only if ->live field of the *current* register is not
>   marked as written.
> - in case if register is overwritten it's ->live field is marked as
>   written, e.g. see check_stack_read_fixed_off().
>   
> Suppose we have an example:
> 
> ---- checkpoint ----
> r1 = r0               ; now r1.parent == &checkpoint->regs[0]
> r2 = r1               ; now r2.parent == &checkpoint->regs[0]
> if (r1 == 0) goto +42
> ...
> 
> Given the above logic only &checkpoint->regs[0] would receive read
> marks. Although I'm not the original author but this behavior seem to
> make sense.
> 
> > 
> > > + *
> > > + * Thus, for execution path 1-6:
> > > + * - both r6->parent and r7->parent point to the same register in the parent state (r7);
> > > + * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark;
> > 
> > I'm trying to understand this. Clearly both r6 and r7 are read. r6 for
> > if (r6 > X) check, r7 for r9 manipulations. Why do we end up not
> > marking one of them as read using a normal logic?
> 
> When (r6 > X) is processed find_equal_scalars() updates parent
> pointers for all registers with the same ID as r6, in this case only
> for r7. So, after find_equal_scalars() is done both current state r6
> and r7 ->parent point to the r6 of the latest checkpoint state.
> 
> > 
> > I have this bad feeling I'm missing something very important here or
> > we have some bug somewhere else. So please help me understand which
> > one it is. This special liveness manipulation seems wrong.
> > 
> > My concern is that if I have some code like
> > 
> > r6 = r7;
> > r9 += r6;
> > 
> > and I never use r7 anymore after that, then we should be able to
> > forget r7 and treat it as NOT_INIT. But you are saying it's unsafe
> > right now and that doesn't make much sense to me.
> 
> It is unsafe because of the "spooky action at a distance" produced by
> a combination of:
> - allocation of scalar IDs for moves, see check_alu_op() case for
>   64-bit move;
> - find_equal_scalars() that propagates range, this one is only
>   executed for conditional jumps.
> 
> > 
> > 
> > > + * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT).
> > > + *
> > > + * Consequently, when execution path 1-4, 6 reaches (6) in state (II)
> > > + * regsafe() won't be able to see a mismatch in ID mappings.
> > > + *
> > > + * To avoid this issue mark_equal_scalars_as_read() conservatively
> > > + * marks all registers with matching ID as REG_LIVE_READ, thus
> > > + * preserving r6 and r7 in the checkpoint state for the example above.
> > > + */
> > > +static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id)
> > > +{
> > > +       struct bpf_verifier_state *st;
> > > +       struct bpf_func_state *state;
> > > +       struct bpf_reg_state *reg;
> > > +       bool move_up;
> > > +       int i = 0;
> > > +
> > > +       for (st = vstate, move_up = true; st && move_up; st = st->parent) {
> > > +               move_up = false;
> > > +               bpf_for_each_reg_in_vstate(st, state, reg, ({
> > > +                       if (reg->type == SCALAR_VALUE && reg->id == id &&
> > > +                           !(reg->live & REG_LIVE_READ)) {
> > > +                               reg->live |= REG_LIVE_READ;
> > > +                               move_up = true;
> > > +                       }
> > > +                       ++i;
> > > +               }));
> > > +       }
> > > +}
> > > +
> > >  static void find_equal_scalars(struct bpf_verifier_state *vstate,
> > >                                struct bpf_reg_state *known_reg)
> > >  {
> > >         struct bpf_func_state *state;
> > >         struct bpf_reg_state *reg;
> > > +       int count = 0;
> > > 
> > >         bpf_for_each_reg_in_vstate(vstate, state, reg, ({
> > > -               if (reg->type == SCALAR_VALUE && reg->id == known_reg->id)
> > > +               if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) {
> > >                         *reg = *known_reg;
> > > +                       ++count;
> > > +               }
> > >         }));
> > > +
> > > +       /* Count equal to 1 means that find_equal_scalars have not
> > > +        * found any registers with the same ID (except self), thus
> > > +        * the range knowledge have not been transferred and there is
> > > +        * no need to preserve registers with the same ID in a parent
> > > +        * state.
> > > +        */
> > > +       if (count > 1)
> > > +               mark_equal_scalars_as_read(vstate->parent, known_reg->id);
> > >  }
> > > 
> > >  static int check_cond_jmp_op(struct bpf_verifier_env *env,
> > > @@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > >                  */
> > >                 return equal && rold->frameno == rcur->frameno;
> > > 
> > > +       /* even if two registers are identical the id mapping might diverge
> > > +        * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2}
> > > +        */
> > > +       if (equal && rold->type == SCALAR_VALUE && rold->id)
> > > +               return check_ids(rold->id, rcur->id, idmap);
> > 
> > nit: let's teach check_ids() to handle the id == 0 case properly
> > instead of guarding everything with `if (rold->id)`?
> > 
> > but also I think this applies not just to SCALARs, right? the memcmp()
> > check above has to be augmented with check_ids() for id and ref_obj_id
> 
> Yes, it is the same issue as described in [1] as you pointed out.
> I'll updated it for other branches, but I want the main issue to
> be sorted out first.
> 
> [1] https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/
> 
> > 
> > > +
> > >         if (equal)
> > >                 return true;
> > > 
> > > @@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > >                 if (env->explore_alu_limits)
> > >                         return false;
> > >                 if (rcur->type == SCALAR_VALUE) {
> > > +                       /* id relations must be preserved, see comment in
> > > +                        * mark_equal_scalars_as_read() for SCALAR_VALUE example.
> > > +                        */
> > > +                       if (rold->id && !check_ids(rold->id, rcur->id, idmap))
> > > +                               return false;
> > >                         if (!rold->precise)
> > >                                 return true;
> > >                         /* new val must satisfy old val knowledge */
> > > --
> > > 2.34.1
> > > 
> 

Re: [RFC bpf-next 1/2] bpf: verify scalar ids mapping in regsafe() using check_ids()

[Eduard Zingerman]

On Thu, 2022-12-01 at 20:33 +0200, Eduard Zingerman wrote:
> On Thu, 2022-12-01 at 03:14 +0200, Eduard Zingerman wrote:
> > On Wed, 2022-11-30 at 16:26 -0800, Andrii Nakryiko wrote:
> > > On Mon, Nov 28, 2022 at 8:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > 
> > > > Prior to this commit the following unsafe example passed verification:
> > > > 
> > > > 1: r9 = ... some pointer with range X ...
> > > > 2: r6 = ... unbound scalar ID=a ...
> > > > 3: r7 = ... unbound scalar ID=b ...
> > > > 4: if (r6 > r7) goto +1
> > > > 5: r6 = r7
> > > > 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
> > > > 7: r9 += r7
> > > > 8: *(u64 *)r9 = Y
> > > > 
> > > > This example is unsafe because not all execution paths verify r7 range.
> > > > Because of the jump at (4) the verifier would arrive at (6) in two states:
> > > > I.  r6{.id=b}, r7{.id=b} via path 1-6;
> > > > II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
> > > > 
> > > > Currently regsafe() does not call check_ids() for scalar registers,
> > > > thus from POV of regsafe() states (I) and (II) are identical. If the
> > > > path 1-6 is taken by verifier first and checkpoint is created at (6)
> > > > the path 1-4, 6 would be considered safe.
> > > > 
> > > > This commit makes the following changes:
> > > > - a call to check_ids() is added in regsafe() for scalar registers case;
> > > > - a function mark_equal_scalars_as_read() is added to ensure that
> > > >   registers with identical IDs are preserved in the checkpoint states
> > > >   in case when find_equal_scalars() updates register range for several
> > > >   registers sharing the same ID.
> > > > 
> > > 
> > > Fixes tag missing?
> > > 
> > > These are tricky changes with subtle details. Let's split check_ids()
> > > change and all the liveness manipulations into separate patches? They
> > > are conceptually completely independent, right?
> > > 
> > > 
> > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > > ---
> > > >  kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
> > > >  1 file changed, 85 insertions(+), 2 deletions(-)
> > > > 
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index 6599d25dae38..8a5b7192514a 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -10638,10 +10638,12 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
> > > >                                 /* case: R1 = R2
> > > >                                  * copy register state to dest reg
> > > >                                  */
> > > > -                               if (src_reg->type == SCALAR_VALUE && !src_reg->id)
> > > > +                               if (src_reg->type == SCALAR_VALUE && !src_reg->id &&
> > > > +                                   !tnum_is_const(src_reg->var_off))
> > > >                                         /* Assign src and dst registers the same ID
> > > >                                          * that will be used by find_equal_scalars()
> > > >                                          * to propagate min/max range.
> > > > +                                        * Skip constants to avoid allocation of useless ID.
> > > >                                          */
> > > >                                         src_reg->id = ++env->id_gen;
> > > >                                 *dst_reg = *src_reg;
> > > > @@ -11446,16 +11448,86 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,
> > > >         return true;
> > > >  }
> > > > 
> > > > +/* Scalar ID generation in check_alu_op() and logic of
> > > > + * find_equal_scalars() make the following pattern possible:
> > > > + *
> > > > + * 1: r9 = ... some pointer with range X ...
> > > > + * 2: r6 = ... unbound scalar ID=a ...
> > > > + * 3: r7 = ... unbound scalar ID=b ...
> > > > + * 4: if (r6 > r7) goto +1
> > > > + * 5: r6 = r7
> > > > + * 6: if (r6 > X) goto ...   ; <-- suppose checkpoint state is created here
> > > > + * 7: r9 += r7
> > > > + * 8: *(u64 *)r9 = Y
> > > > + *
> > > > + * Because of the jump at (4) the verifier would arrive at (6) in two states:
> > > > + * I.  r6{.id=b}, r7{.id=b}
> > > > + * II. r6{.id=a}, r7{.id=b}
> > > > + *
> > > > + * Relevant facts:
> > > > + * - regsafe() matches ID mappings for scalars using check_ids(), this makes
> > > > + *   states (I) and (II) non-equal;
> > > > + * - clean_func_state() removes registers not marked as REG_LIVE_READ from
> > > > + *   checkpoint states;
> > > > + * - mark_reg_read() modifies reg->live for reg->parent (and it's parents);
> > > > + * - when r6 = r7 is process the bpf_reg_state is copied in full, meaning
> > > > + *   that parent pointers are copied as well.
> > > 
> > > not too familiar with liveness handling, but is this correct and
> > > expected? Should this be fixed instead of REG_LIVE_READ manipulations?
> 
> 
> TLDR:
> 
> - looks like it is safe to avoid bpf_reg_state->parent update when
>   registers are copied, but it has some performance impact. If this
>   impact is acceptable I'd like to move this way are remove
>   mark_equal_scalars_as_read().
> 
> - unrelated question: does anything has to be done to
>   __mark_chain_precision to make it know about shared scalar IDs?
>   E.g. in the following case:
>     ...
>   --- checkpoint 1 --- r6 would be marked as precise here
>   r6 = r7
>     ...
>   --- checkpoint 2 --- r6 won't be marked as precise here
>     ...
>   if r6 < 10
>   --- checkpoint 3 ---
>   fp[r7] = 42
>   
>   The additional precision marks could be inferred if additional info
>   is added the jump stack.
> 
> -----
> Long version about bpf_reg_state->parent.
> 
> All functions that copy register states:
> - save_register_state()
>   Register is copied to stack spill location.
> 
> - check_kfunc_mem_size_reg()
>   Makes a tmp register copy, harmless.
> 
> - sanitize_ptr_alu()
>   Register copy is visible in the speculative branch.
> 
> - check_alu_op()
>   Register is copied when reg to reg MOV is processed.
> 
> - find_equal_scalars()
>   Register is copied to the registers with the same ID.
> 
> Original commit introducing bpf_reg_state->parent:
> - 679c782de14bd48c19dd74cd1af20a2bc05dd936 2018-08-30
>   bpf/verifier: per-register parent pointers
>   
>   Updates mark_reg_read() and removes mark_stack_slot_read().
>   Previous version accessed parent state registers directly using
>   regno w/o any additional manipulations.
> 
>   In this commit:
>   - save_register_state() - does not exist yet, its function is
>     performed by check_stack_write(), has a direct register state copy
>     as in save_register_state();
>   - check_kfunc_mem_size_reg() - does not exist yet;
>   - sanitize_ptr_alu() - does not exist yet;
>   - check_alu_op() - has a direct register state copy unchanged for
>     reg to reg MOV.
> 
> Commit introducing find_equal_scalars():
> - 75748837b7e56919679e02163f45d5818c644d03 2020-10-09
>   bpf: Propagate scalar ranges through register assignments.
>   
>   Has a direct register copy *reg = *known_reg.
> 
> It looks like that for places where registers are copied ->parent
> change is an unintentional side effect. Removal of this side effect
> might in theory lead to some additional register read marks, e.g. in
> this case:
> 
>   r6 = r7
>   if (r6 > X) goto +42
>   r5 = r7              ; this would lead to a read mark on r7 not
>                        ; present previously.
> 

Upon detailed examination of the differences in tests behaviour with and without
preserving register parentage chains I came up with the following test case:
{
	"write tracking and register parent chain bug",
	.insns = {
	/* r6 = ktime_get_ns() */
	BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns),
	BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
	/* r0 = ktime_get_ns() */
	BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns),
	/* if r0 > r6 goto +1 */
	BPF_JMP_REG(BPF_JGT, BPF_REG_0, BPF_REG_6, 1),
	/* *(u64 *)(r10 - 8) = 0xdeadbeef */
	BPF_ST_MEM(BPF_DW, BPF_REG_FP, -8, 0xdeadbeef),
	/* r1 = 42 */
	BPF_MOV64_IMM(BPF_REG_1, 42),
	/* *(u8 *)(r10 - 8) = r1 */
	BPF_STX_MEM(BPF_B, BPF_REG_FP, BPF_REG_1, -8),
	/* r2 = *(u64 *)(r10 - 8) */
	BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_FP, -8),
	/* exit(0) */
	BPF_MOV64_IMM(BPF_REG_0, 0),
	BPF_EXIT_INSN(),
	},
	.flags = BPF_F_TEST_STATE_FREQ,
	.errstr = "invalid read from stack off -8+1 size 8",
	.result = REJECT,
},
This test case is currently marked as safe, which is not true, because the
write of 0xdeadbeef to fp[-8] might be omitted. The bug is caused by tossing
around the register parent pointers. So there is no real choice here, this
behaviour has to be changed.

I'll submit a separate patch shortly.


> This should not hinder correctness.
> However, there is some negative performance impact:
> 
> $ ./veristat -e file,prog,states -f 'states_pct!=0' -C master-baseline.log current.log 
> File                      Program                           States (A)  States (B)  States  (DIFF)
> ------------------------  --------------------------------  ----------  ----------  --------------
> bpf_host.o                cil_to_netdev                            358         455   +97 (+27.09%)
> bpf_host.o                tail_handle_nat_fwd_ipv4                1746        1891   +145 (+8.30%)
> bpf_host.o                tail_handle_nat_fwd_ipv6                 709         717     +8 (+1.13%)
> bpf_host.o                tail_nodeport_ipv4_dsr                    31          42   +11 (+35.48%)
> bpf_host.o                tail_nodeport_nat_egress_ipv4           2269        2274     +5 (+0.22%)
> bpf_host.o                tail_nodeport_nat_ingress_ipv4           276         316   +40 (+14.49%)
> bpf_host.o                tail_nodeport_nat_ingress_ipv6           243         254    +11 (+4.53%)
> bpf_lxc.o                 tail_handle_nat_fwd_ipv4                1746        1891   +145 (+8.30%)
> bpf_lxc.o                 tail_handle_nat_fwd_ipv6                 709         717     +8 (+1.13%)
> bpf_lxc.o                 tail_ipv4_ct_egress                      248         251     +3 (+1.21%)
> bpf_lxc.o                 tail_ipv4_ct_ingress                     248         251     +3 (+1.21%)
> bpf_lxc.o                 tail_ipv4_ct_ingress_policy_only         248         251     +3 (+1.21%)
> bpf_lxc.o                 tail_nodeport_ipv4_dsr                    31          42   +11 (+35.48%)
> bpf_lxc.o                 tail_nodeport_nat_ingress_ipv4           276         316   +40 (+14.49%)
> bpf_lxc.o                 tail_nodeport_nat_ingress_ipv6           243         254    +11 (+4.53%)
> bpf_overlay.o             tail_handle_nat_fwd_ipv4                1082        1109    +27 (+2.50%)
> bpf_overlay.o             tail_nodeport_ipv4_dsr                    31          42   +11 (+35.48%)
> bpf_overlay.o             tail_nodeport_nat_egress_ipv4           2238        2243     +5 (+0.22%)
> bpf_overlay.o             tail_nodeport_nat_ingress_ipv4           276         316   +40 (+14.49%)
> bpf_overlay.o             tail_nodeport_nat_ingress_ipv6           243         254    +11 (+4.53%)
> bpf_sock.o                cil_sock4_connect                         47          64   +17 (+36.17%)
> bpf_sock.o                cil_sock4_sendmsg                         45          62   +17 (+37.78%)
> bpf_xdp.o                 tail_handle_nat_fwd_ipv4                1461        1912  +451 (+30.87%)
> bpf_xdp.o                 tail_lb_ipv4                            4643        4738    +95 (+2.05%)
> bpf_xdp.o                 tail_nodeport_nat_egress_ipv4           1066        1069     +3 (+0.28%)
> bpf_xdp.o                 tail_rev_nodeport_lb4                    404         411     +7 (+1.73%)
> bpf_xdp.o                 tail_rev_nodeport_lb6                   1076        1083     +7 (+0.65%)
> pyperf600_bpf_loop.bpf.o  on_event                                 285         287     +2 (+0.70%)
> xdp_synproxy_kern.bpf.o   syncookie_tc                           22513       22564    +51 (+0.23%)
> xdp_synproxy_kern.bpf.o   syncookie_xdp                          22207       24206  +1999 (+9.00%)
> ------------------------  --------------------------------  ----------  ----------  --------------
> 
> > 
> > Well, that's what I wanted to ask, actually :)
> > Here is how current logic works:
> > - is_state_visited() has the following two loops in the end:
> > 
> > 	for (j = 0; j <= cur->curframe; j++) {
> > 		for (i = j < cur->curframe ? BPF_REG_6 : 0; i < BPF_REG_FP; i++)
> > 			cur->frame[j]->regs[i].parent = &new->frame[j]->regs[i];
> > 		for (i = 0; i < BPF_REG_FP; i++)
> > 			cur->frame[j]->regs[i].live = REG_LIVE_NONE;
> > 	}
> > 
> > 	/* all stack frames are accessible from callee, clear them all */
> > 	for (j = 0; j <= cur->curframe; j++) {
> > 		struct bpf_func_state *frame = cur->frame[j];
> > 		struct bpf_func_state *newframe = new->frame[j];
> > 
> > 		for (i = 0; i < frame->allocated_stack / BPF_REG_SIZE; i++) {
> > 			frame->stack[i].spilled_ptr.live = REG_LIVE_NONE;
> > 			frame->stack[i].spilled_ptr.parent =
> > 						&newframe->stack[i].spilled_ptr;
> > 		}
> > 	}
> > 
> >   These connect the bpf_reg_state members of the new state with
> >   corresponding (index-wise) members of the parent state.
> > - find_equal_scalars() looks as follows:
> >   static void find_equal_scalars(struct bpf_verifier_state *vstate,
> >                                struct bpf_reg_state *known_reg)
> >   {
> > 	struct bpf_func_state *state;
> > 	struct bpf_reg_state *reg;
> > 
> > 	bpf_for_each_reg_in_vstate(vstate, state, reg, ({
> > 		if (reg->type == SCALAR_VALUE && reg->id == known_reg->id)
> > 			*reg = *known_reg;  // <--- full copy, incl. parent pointer
> > 	}));
> >   }
> > - mark_reg_read() updates the ->live field of the *parent* register
> >   when called only if ->live field of the *current* register is not
> >   marked as written.
> > - in case if register is overwritten it's ->live field is marked as
> >   written, e.g. see check_stack_read_fixed_off().
> >   
> > Suppose we have an example:
> > 
> > ---- checkpoint ----
> > r1 = r0               ; now r1.parent == &checkpoint->regs[0]
> > r2 = r1               ; now r2.parent == &checkpoint->regs[0]
> > if (r1 == 0) goto +42
> > ...
> > 
> > Given the above logic only &checkpoint->regs[0] would receive read
> > marks. Although I'm not the original author but this behavior seem to
> > make sense.
> > 
> > > 
> > > > + *
> > > > + * Thus, for execution path 1-6:
> > > > + * - both r6->parent and r7->parent point to the same register in the parent state (r7);
> > > > + * - only *one* register in the checkpoint state would receive REG_LIVE_READ mark;
> > > 
> > > I'm trying to understand this. Clearly both r6 and r7 are read. r6 for
> > > if (r6 > X) check, r7 for r9 manipulations. Why do we end up not
> > > marking one of them as read using a normal logic?
> > 
> > When (r6 > X) is processed find_equal_scalars() updates parent
> > pointers for all registers with the same ID as r6, in this case only
> > for r7. So, after find_equal_scalars() is done both current state r6
> > and r7 ->parent point to the r6 of the latest checkpoint state.
> > 
> > > 
> > > I have this bad feeling I'm missing something very important here or
> > > we have some bug somewhere else. So please help me understand which
> > > one it is. This special liveness manipulation seems wrong.
> > > 
> > > My concern is that if I have some code like
> > > 
> > > r6 = r7;
> > > r9 += r6;
> > > 
> > > and I never use r7 anymore after that, then we should be able to
> > > forget r7 and treat it as NOT_INIT. But you are saying it's unsafe
> > > right now and that doesn't make much sense to me.
> > 
> > It is unsafe because of the "spooky action at a distance" produced by
> > a combination of:
> > - allocation of scalar IDs for moves, see check_alu_op() case for
> >   64-bit move;
> > - find_equal_scalars() that propagates range, this one is only
> >   executed for conditional jumps.
> > 
> > > 
> > > 
> > > > + * - clean_func_state() would remove r6 from checkpoint state (mark it NOT_INIT).
> > > > + *
> > > > + * Consequently, when execution path 1-4, 6 reaches (6) in state (II)
> > > > + * regsafe() won't be able to see a mismatch in ID mappings.
> > > > + *
> > > > + * To avoid this issue mark_equal_scalars_as_read() conservatively
> > > > + * marks all registers with matching ID as REG_LIVE_READ, thus
> > > > + * preserving r6 and r7 in the checkpoint state for the example above.
> > > > + */
> > > > +static void mark_equal_scalars_as_read(struct bpf_verifier_state *vstate, int id)
> > > > +{
> > > > +       struct bpf_verifier_state *st;
> > > > +       struct bpf_func_state *state;
> > > > +       struct bpf_reg_state *reg;
> > > > +       bool move_up;
> > > > +       int i = 0;
> > > > +
> > > > +       for (st = vstate, move_up = true; st && move_up; st = st->parent) {
> > > > +               move_up = false;
> > > > +               bpf_for_each_reg_in_vstate(st, state, reg, ({
> > > > +                       if (reg->type == SCALAR_VALUE && reg->id == id &&
> > > > +                           !(reg->live & REG_LIVE_READ)) {
> > > > +                               reg->live |= REG_LIVE_READ;
> > > > +                               move_up = true;
> > > > +                       }
> > > > +                       ++i;
> > > > +               }));
> > > > +       }
> > > > +}
> > > > +
> > > >  static void find_equal_scalars(struct bpf_verifier_state *vstate,
> > > >                                struct bpf_reg_state *known_reg)
> > > >  {
> > > >         struct bpf_func_state *state;
> > > >         struct bpf_reg_state *reg;
> > > > +       int count = 0;
> > > > 
> > > >         bpf_for_each_reg_in_vstate(vstate, state, reg, ({
> > > > -               if (reg->type == SCALAR_VALUE && reg->id == known_reg->id)
> > > > +               if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) {
> > > >                         *reg = *known_reg;
> > > > +                       ++count;
> > > > +               }
> > > >         }));
> > > > +
> > > > +       /* Count equal to 1 means that find_equal_scalars have not
> > > > +        * found any registers with the same ID (except self), thus
> > > > +        * the range knowledge have not been transferred and there is
> > > > +        * no need to preserve registers with the same ID in a parent
> > > > +        * state.
> > > > +        */
> > > > +       if (count > 1)
> > > > +               mark_equal_scalars_as_read(vstate->parent, known_reg->id);
> > > >  }
> > > > 
> > > >  static int check_cond_jmp_op(struct bpf_verifier_env *env,
> > > > @@ -12878,6 +12950,12 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > > >                  */
> > > >                 return equal && rold->frameno == rcur->frameno;
> > > > 
> > > > +       /* even if two registers are identical the id mapping might diverge
> > > > +        * e.g. rold{.id=1}, rcur{.id=1}, idmap{1->2}
> > > > +        */
> > > > +       if (equal && rold->type == SCALAR_VALUE && rold->id)
> > > > +               return check_ids(rold->id, rcur->id, idmap);
> > > 
> > > nit: let's teach check_ids() to handle the id == 0 case properly
> > > instead of guarding everything with `if (rold->id)`?
> > > 
> > > but also I think this applies not just to SCALARs, right? the memcmp()
> > > check above has to be augmented with check_ids() for id and ref_obj_id
> > 
> > Yes, it is the same issue as described in [1] as you pointed out.
> > I'll updated it for other branches, but I want the main issue to
> > be sorted out first.
> > 
> > [1] https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/
> > 
> > > 
> > > > +
> > > >         if (equal)
> > > >                 return true;
> > > > 
> > > > @@ -12891,6 +12969,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > > >                 if (env->explore_alu_limits)
> > > >                         return false;
> > > >                 if (rcur->type == SCALAR_VALUE) {
> > > > +                       /* id relations must be preserved, see comment in
> > > > +                        * mark_equal_scalars_as_read() for SCALAR_VALUE example.
> > > > +                        */
> > > > +                       if (rold->id && !check_ids(rold->id, rcur->id, idmap))
> > > > +                               return false;
> > > >                         if (!rold->precise)
> > > >                                 return true;
> > > >                         /* new val must satisfy old val knowledge */
> > > > --
> > > > 2.34.1
> > > > 
> > 
> 

[RFC bpf-next 2/2] selftests/bpf: verify that check_ids() is used for scalars in regsafe()

[Eduard Zingerman]

Verify that the following example is rejected by verifier:

r9 = ... some pointer with range X ...
r6 = ... unbound scalar ID=a ...
r7 = ... unbound scalar ID=b ...
if (r6 > r7) goto +1
r6 = r7
if (r6 > X) goto exit
r9 += r7
*(u64 *)r9 = Y

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../selftests/bpf/verifier/scalar_ids.c       | 61 +++++++++++++++++++
 1 file changed, 61 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/verifier/scalar_ids.c

diff --git a/tools/testing/selftests/bpf/verifier/scalar_ids.c b/tools/testing/selftests/bpf/verifier/scalar_ids.c
new file mode 100644
index 000000000000..38a6959c93e5
--- /dev/null
+++ b/tools/testing/selftests/bpf/verifier/scalar_ids.c
@@ -0,0 +1,61 @@
+/* Test cases for verifier.c:find_equal_scalars() and Co */
+
+/* Use a map lookup as a way to get a pointer to some valid memory
+ * location with size known to verifier.
+ */
+#define MAKE_POINTER_TO_48_BYTES(reg)			\
+	BPF_MOV64_IMM(BPF_REG_0, 0),			\
+	BPF_LD_MAP_FD(BPF_REG_1, 0),			\
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),		\
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),		\
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),		\
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),	\
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),		\
+	BPF_EXIT_INSN(),				\
+	BPF_MOV64_REG((reg), BPF_REG_0)
+
+/* See comment in verifier.c:mark_equal_scalars_as_read().
+ *
+ * r9 = ... some pointer with range X ...
+ * r6 = ... unbound scalar ID=a ...
+ * r7 = ... unbound scalar ID=b ...
+ * if (r6 > r7) goto +1
+ * r6 = r7
+ * if (r6 > X) goto exit
+ * r9 += r7
+ * *(u64 *)r9 = Y
+ */
+{
+	"scalar ids: ID mapping in regsafe()",
+	.insns = {
+	MAKE_POINTER_TO_48_BYTES(BPF_REG_9),
+	/* r7 = ktime_get_ns() */
+	BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	/* r6 = ktime_get_ns() */
+	BPF_EMIT_CALL(BPF_FUNC_ktime_get_ns),
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_0),
+	/* if r6 > r7 goto +1 */
+	BPF_JMP_REG(BPF_JGT, BPF_REG_6, BPF_REG_7, 1),
+	/* r6 = r7 */
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_7),
+	/* a noop to get to add new parent state */
+	BPF_MOV64_REG(BPF_REG_0, BPF_REG_0),
+	/* if r6 >= 10 exit(0) */
+	BPF_JMP_IMM(BPF_JGT, BPF_REG_6, 10, 2),
+	/* r9[r7] = 42 */
+	BPF_ALU64_REG(BPF_ADD, BPF_REG_9, BPF_REG_7),
+	BPF_ST_MEM(BPF_DW, BPF_REG_9, 0, 42),
+	/* exit(0) */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_48b = { 1 },
+	.flags = BPF_F_TEST_STATE_FREQ,
+	.errstr_unpriv = "register with unbounded min value",
+	.result_unpriv = REJECT,
+	.errstr = "register with unbounded min value",
+	.result = REJECT,
+},
+
+#undef MAKE_POINTER_TO_48_BYTES
-- 
2.34.1