Skip to contentSkip to conversation

bpf: verify scalar ids mapping in regsafe() using check_ids()

RFC In review Eduard Zingerman 2 participants 7 messages Nov 28, 2022 – Dec 2, 2022

Subsystems (4)
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

cover bpf: verify scalar ids mapping in regsafe() using check_ids()

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] [email protected]: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
Signature · 1 line
2.34.1
author maintainer
#1 lore raw

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

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.

---
 kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 85 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +85 -2
index 6599d25dae38..8a5b7192514a 100644
@@ -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 */
Signature · 1 line
2.34.1
author maintainer
#6 lore raw

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

In reply to 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

---
 .../selftests/bpf/verifier/scalar_ids.c       | 61 +++++++++++++++++++
 1 file changed, 61 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/verifier/scalar_ids.c
tools/testing/selftests/bpf/verifier/scalar_ids.c new file +61 -0
new file mode 100644
index 000000000000..38a6959c93e5
@@ -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
Signature · 1 line
2.34.1
#2 lore raw
In reply to Eduard Zingerman
Quoted 22 lines · 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.

Quoted 7 lines

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?

Quoted 41 lines
---
 kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 85 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +17 -1
index 6599d25dae38..8a5b7192514a 100644
@@ -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}

kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 11474

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+ * 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?

kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 11478

Quoted 4 lines
kernel/bpf/verifier.c +4 -0
+ *
+ * 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.

Quoted 57 lines
kernel/bpf/verifier.c +43 -1
+ * - 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,

kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 12957

Quoted 8 lines
kernel/bpf/verifier.c +5 -0
@@ -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

Quoted 19 lines
kernel/bpf/verifier.c +6 -1
+
        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

author maintainer
#3 lore raw
Quoted 84 lines · Andrii Nakryiko
Quoted 22 lines · 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.

Quoted 7 lines

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?

Quoted 46 lines
---
 kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 85 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +22 -1
index 6599d25dae38..8a5b7192514a 100644
@@ -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;
Quoted 8 lines

kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 11474

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+ * - 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.

Quoted 9 lines

kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 11478

Quoted 5 lines
kernel/bpf/verifier.c +4 -0
+ *
+ * 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.

Quoted 5 lines

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.

Quoted 8 lines

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.

Quoted 71 lines
Quoted 59 lines
kernel/bpf/verifier.c +43 -1
+ * - 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,

kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 12957

Quoted 8 lines
kernel/bpf/verifier.c +5 -0
@@ -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)?

Quoted 2 lines

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/

Quoted 20 lines
Quoted 20 lines
kernel/bpf/verifier.c +6 -1
+
        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

author maintainer
#4 lore raw
Quoted 85 lines · Eduard Zingerman
Quoted 84 lines · Andrii Nakryiko
Quoted 22 lines · 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.

Quoted 7 lines

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?

Quoted 46 lines
---
 kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 85 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +22 -1
index 6599d25dae38..8a5b7192514a 100644
@@ -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;
Quoted 8 lines
Quoted 8 lines

kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 11474

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+ * - 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%)
------------------------  --------------------------------  ----------  ----------  --------------
Quoted 193 lines

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.

Quoted 9 lines

kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 11478

Quoted 5 lines
kernel/bpf/verifier.c +4 -0
+ *
+ * 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.

Quoted 5 lines

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.

Quoted 8 lines

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.

Quoted 71 lines
Quoted 59 lines
kernel/bpf/verifier.c +43 -1
+ * - 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,

kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 12957

Quoted 8 lines
kernel/bpf/verifier.c +5 -0
@@ -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)?

Quoted 2 lines

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/

Quoted 20 lines
Quoted 20 lines
kernel/bpf/verifier.c +6 -1
+
        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

author maintainer
#5 lore raw
Quoted 166 lines · Eduard Zingerman
Quoted 85 lines · Eduard Zingerman
Quoted 84 lines · Andrii Nakryiko
Quoted 22 lines · 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.

Quoted 7 lines

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?

Quoted 46 lines
---
 kernel/bpf/verifier.c | 87 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 85 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +22 -1
index 6599d25dae38..8a5b7192514a 100644
@@ -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;
Quoted 8 lines
Quoted 8 lines

kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 11474

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+ * - 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:

Quoted 5 lines

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.

Quoted 232 lines

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%)
------------------------  --------------------------------  ----------  ----------  --------------
Quoted 193 lines

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.

Quoted 9 lines

kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 11478

Quoted 5 lines
kernel/bpf/verifier.c +4 -0
+ *
+ * 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.

Quoted 5 lines

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.

Quoted 8 lines

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.

Quoted 71 lines
Quoted 59 lines
kernel/bpf/verifier.c +43 -1
+ * - 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,

kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 12957

Quoted 8 lines
kernel/bpf/verifier.c +5 -0
@@ -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)?

Quoted 2 lines

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/

Quoted 20 lines
Quoted 20 lines
kernel/bpf/verifier.c +6 -1
+
        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