Skip to contentSkip to conversation

stricter register ID checking in regsafe()

PATCH Applied Eduard Zingerman 4 participants 21 messages Dec 9, 2022 – Dec 14, 2022

Subsystems (4)
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

cover stricter register ID checking in regsafe()

This patch-set consists of a series of bug fixes for register ID tracking in verifier.c:states_equal()/regsafe() functions:
- for registers of type PTR_TO_MAP_{KEY,VALUE}, PTR_TO_PACKET[_META] the regsafe() should call check_ids() even if registers are byte-to-byte equal;
- states_equal() must maintain idmap that covers all function frames in the state because functions like mark_ptr_or_null_regs() operate on all registers in the state;
- regsafe() must compare spin lock ids for PTR_TO_MAP_VALUE registers.

The last point covers issue reported by Kumar Kartikeya Dwivedi in [1], I borrowed the test commit from there.
Note, that there is also an issue with register id tracking for scalars described here [2], it would be addressed separately.

[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/

Eduard Zingerman (6):
bpf: regsafe() must not skip check_ids()
selftests/bpf: test cases for regsafe() bug skipping check_id()
bpf: states_equal() must build idmap for all function frames selftests/bpf: verify states_equal() maintains idmap across all frames
bpf: use check_ids() for active_lock comparison selftests/bpf: test case for relaxed prunning of active_lock.id

Kumar Kartikeya Dwivedi (1):
selftests/bpf: Add pruning test case for bpf_spin_lock

 include/linux/bpf_verifier.h                  |   4 +-
 kernel/bpf/verifier.c                         |  48 ++++----
 tools/testing/selftests/bpf/verifier/calls.c  |  82 +++++++++++++
 .../bpf/verifier/direct_packet_access.c       |  54 +++++++++
 .../selftests/bpf/verifier/spin_lock.c        | 114 ++++++++++++++++++
 .../selftests/bpf/verifier/value_or_null.c    |  49 ++++++++
 6 files changed, 324 insertions(+), 27 deletions(-)
Signature · 1 line
2.34.1
author maintainer
#1 lore raw

PATCH 1/7 bpf: regsafe() must not skip check_ids()

The verifier.c:regsafe() has the following shortcut:

	equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
	...
	if (equal)
		return true;

Which is executed regardless old register type. This is incorrect for register types that might have an ID checked by check_ids(), namely:
- PTR_TO_MAP_KEY
- PTR_TO_MAP_VALUE
- PTR_TO_PACKET_META
- PTR_TO_PACKET

The following pattern could be used to exploit this:

  0: r9 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=1.
  1: r8 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=2.
  2: r7 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  3: r6 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  4: if r6 > r7 goto +1         ; No new information about the state

; is derived from this check, thus ; produced verifier states differ only ; in 'insn_idx'.
5: r9 = r8 ; Optionally make r9.id == r8.id.
--- checkpoint --- ; Assume is_state_visisted() creates a
; checkpoint here.
6: if r9 == 0 goto <exit> ; Nullness info is propagated to all
; registers with matching ID.
7: r1 = *(u64 *) r8 ; Not always safe.

Verifier first visits path 1-7 where r8 is verified to be not null at (6). Later the jump from 4 to 6 is examined. The checkpoint for (6) looks as follows:
R8_rD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9_rwD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R10=fp0

The current state is:
R0=... R6=... R7=... fp-8=... R8=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9=map_value_or_null(id=1,off=0,ks=4,vs=8,imm=0) R10=fp0

Note that R8 states are byte-to-byte identical, so regsafe() would exit early and skip call to check_ids(), thus ID mapping 2->2 will not be added to 'idmap'. Next, states for R9 are compared: these are not identical and check_ids() is executed, but 'idmap' is empty, so check_ids() adds mapping 2->1 to 'idmap' and returns success.

This commit pushes the 'equal' down to register types that don't need check_ids().

---
 kernel/bpf/verifier.c | 29 ++++++++---------------------
 1 file changed, 8 insertions(+), 21 deletions(-)
kernel/bpf/verifier.c +8 -21
index 3194e9d9e4e4..d05c5d0344c6 100644
@@ -12926,15 +12926,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 
 	equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
 
-	if (rold->type == PTR_TO_STACK)
-		/* two stack pointers are equal only if they're pointing to
-		 * the same stack frame, since fp-8 in foo != fp-8 in bar
-		 */
-		return equal && rold->frameno == rcur->frameno;
-
-	if (equal)
-		return true;
-
 	if (rold->type == NOT_INIT)
 		/* explored state can't have used this */
 		return true;
@@ -12942,6 +12933,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		return false;
 	switch (base_type(rold->type)) {
 	case SCALAR_VALUE:
+		if (equal)
+			return true;
 		if (env->explore_alu_limits)
 			return false;
 		if (rcur->type == SCALAR_VALUE) {
@@ -13012,20 +13005,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		/* new val must satisfy old val knowledge */
 		return range_within(rold, rcur) &&
 		       tnum_in(rold->var_off, rcur->var_off);
-	case PTR_TO_CTX:
-	case CONST_PTR_TO_MAP:
-	case PTR_TO_PACKET_END:
-	case PTR_TO_FLOW_KEYS:
-	case PTR_TO_SOCKET:
-	case PTR_TO_SOCK_COMMON:
-	case PTR_TO_TCP_SOCK:
-	case PTR_TO_XDP_SOCK:
-		/* Only valid matches are exact, which memcmp() above
-		 * would have accepted
+	case PTR_TO_STACK:
+		/* two stack pointers are equal only if they're pointing to
+		 * the same stack frame, since fp-8 in foo != fp-8 in bar
 		 */
+		return equal && rold->frameno == rcur->frameno;
 	default:
-		/* Don't know what's going on, just say it's not safe */
-		return false;
+		/* Only valid matches are exact, which memcmp() */
+		return equal;
 	}
 
 	/* Shouldn't get here; if we do, say it's not safe */
Signature · 1 line
2.34.1
author maintainer
#5 lore raw

PATCH 2/7 selftests/bpf: test cases for regsafe() bug skipping check_id()

In reply to Eduard Zingerman

Under certain conditions it was possible for verifier.c:regsafe() to skip check_id() call. This commit adds negative test cases previously errorneously accepted as safe.

---
 .../bpf/verifier/direct_packet_access.c       | 54 +++++++++++++++++++
 .../selftests/bpf/verifier/value_or_null.c    | 49 +++++++++++++++++
 2 files changed, 103 insertions(+)
tools/testing/selftests/bpf/verifier/direct_packet_access.c +54 -0
index 11acd1855acf..dce2e28aeb43 100644
@@ -654,3 +654,57 @@
 	.result = ACCEPT,
 	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
 },
+{
+	"direct packet access: test30 (check_id() in regsafe(), bad access)",
+	.insns = {
+	/* r9 = ctx */
+	BPF_MOV64_REG(BPF_REG_9, BPF_REG_1),
+	/* 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),
+	/* r2 = ctx->data
+	 * r3 = ctx->data
+	 * r4 = ctx->data_end
+	 */
+	BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_9, offsetof(struct __sk_buff, data)),
+	BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_9, offsetof(struct __sk_buff, data)),
+	BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_9, offsetof(struct __sk_buff, data_end)),
+	/* if r6 > 100 goto exit
+	 * if r7 > 100 goto exit
+	 */
+	BPF_JMP_IMM(BPF_JGT, BPF_REG_6, 100, 9),
+	BPF_JMP_IMM(BPF_JGT, BPF_REG_7, 100, 8),
+	/* r2 += r6              ; this forces assignment of ID to r2
+	 * r2 += 1               ; get some fixed off for r2
+	 * r3 += r7              ; this forces assignment of ID to r3
+	 * r3 += 1               ; get some fixed off for r3
+	 */
+	BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_6),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, 1),
+	BPF_ALU64_REG(BPF_ADD, BPF_REG_3, BPF_REG_7),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 1),
+	/* if r6 > r7 goto +1    ; no new information about the state is derived from
+	 *                       ; this check, thus produced verifier states differ
+	 *                       ; only in 'insn_idx'
+	 * r2 = r3               ; optionally share ID between r2 and r3
+	 */
+	BPF_JMP_REG(BPF_JNE, BPF_REG_6, BPF_REG_7, 1),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_3),
+	/* if r3 > ctx->data_end goto exit */
+	BPF_JMP_REG(BPF_JGT, BPF_REG_3, BPF_REG_4, 1),
+	/* r5 = *(u8 *) (r2 - 1) ; access packet memory using r2,
+	 *                       ; this is not always safe
+	 */
+	BPF_LDX_MEM(BPF_B, BPF_REG_5, BPF_REG_2, -1),
+	/* exit(0) */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.flags = BPF_F_TEST_STATE_FREQ,
+	.result = REJECT,
+	.errstr = "invalid access to packet, off=0 size=1, R2",
+	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+},
tools/testing/selftests/bpf/verifier/value_or_null.c +49 -0

52 lines not on this page · raw message

Signature · 1 line
2.34.1
author maintainer
#6 lore raw

PATCH 3/7 bpf: states_equal() must build idmap for all function frames

In reply to Eduard Zingerman

verifier.c:states_equal() must maintain register ID mapping across all function frames. Otherwise the following example might be erroneously marked as safe:

main:

    fp[-24] = map_lookup_elem(...)  ; frame[0].fp[-24].id == 1
    fp[-32] = map_lookup_elem(...)  ; frame[0].fp[-32].id == 2
    r1 = &fp[-24]
    r2 = &fp[-32]
    call foo()
    r0 = 0
    exit

foo:
0: r9 = r1
1: r8 = r2
2: r7 = ktime_get_ns()
3: r6 = ktime_get_ns()
4: if (r6 > r7) goto skip_assign
5: r9 = r8

skip_assign: ; <--- checkpoint
6: r9 = *r9 ; (a) frame[1].r9.id == 2

                            ; (b) frame[1].r9.id == 1

7: if r9 == 0 goto exit: ; mark_ptr_or_null_regs() transfers != 0 info

                            ; for all regs sharing ID:
                            ;   (a) r9 != 0 => &frame[0].fp[-32] != 0
                            ;   (b) r9 != 0 => &frame[0].fp[-24] != 0

8: r8 = *r8 ; (a) r8 == &frame[0].fp[-32]

                            ; (b) r8 == &frame[0].fp[-32]

9: r0 = *r8 ; (a) safe
; (b) unsafe

exit:
10: exit

While processing call to foo() verifier considers the following execution paths:

(a) 0-10
(b) 0-4,6-10
(There is also path 0-7,10 but it is not interesting for the issue at
hand. (a) is verified first.)

Suppose that checkpoint is created at (6) when path (a) is verified, next path (b) is verified and (6) is reached.

If states_equal() maintains separate 'idmap' for each frame the mapping at (6) for frame[1] would be empty and regsafe(r9)::check_ids() would add a pair 2->1 and return true, which is an error.

If states_equal() maintains single 'idmap' for all frames the mapping at (6) would be { 1->1, 2->2 } and regsafe(r9)::check_ids() would return false when trying to add a pair 2->1.

This issue was suggested in the following discussion:
https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/

---
 include/linux/bpf_verifier.h | 4 ++--
 kernel/bpf/verifier.c        | 3 ++-
 2 files changed, 4 insertions(+), 3 deletions(-)
include/linux/bpf_verifier.h +2 -2
index 70d06a99f0b8..c1f769515beb 100644
@@ -273,9 +273,9 @@ struct bpf_id_pair {
 	u32 cur;
 };
 
-/* Maximum number of register states that can exist at once */
-#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)
 #define MAX_CALL_FRAMES 8
+/* Maximum number of register states that can exist at once */
+#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)
 struct bpf_verifier_state {
 	/* call stack tracking */
 	struct bpf_func_state *frame[MAX_CALL_FRAMES];
kernel/bpf/verifier.c +2 -1
index d05c5d0344c6..9188370a7ebe 100644
@@ -13122,7 +13122,6 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat
 {
 	int i;
 
-	memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch));
 	for (i = 0; i < MAX_BPF_REG; i++)
 		if (!regsafe(env, &old->regs[i], &cur->regs[i],
 			     env->idmap_scratch))
@@ -13146,6 +13145,8 @@ static bool states_equal(struct bpf_verifier_env *env,
 	if (old->curframe != cur->curframe)
 		return false;
 
+	memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch));
+
 	/* Verification state from speculative execution simulation
 	 * must never prune a non-speculative execution one.
 	 */
Signature · 1 line
2.34.1
author maintainer
#10 lore raw

PATCH 4/7 selftests/bpf: verify states_equal() maintains idmap across all frames

In reply to Eduard Zingerman

A test case that would erroneously pass verification if verifier.c:states_equal() maintains separate register ID mappings for call frames.

---
 tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++
 1 file changed, 82 insertions(+)
tools/testing/selftests/bpf/verifier/calls.c +82 -0
index 3193915c5ee6..bcd15b26dcee 100644
@@ -2305,3 +2305,85 @@
 	.errstr = "!read_ok",
 	.result = REJECT,
 },
+/* Make sure that verifier.c:states_equal() considers IDs from all
+ * frames when building 'idmap' for check_ids().
+ */
+{
+	"calls: check_ids() across call boundary",
+	.insns = {
+	/* Function main() */
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+	/* fp[-24] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+	BPF_LD_MAP_FD(BPF_REG_1,
+		      0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_0, -24),
+	/* fp[-32] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+	BPF_LD_MAP_FD(BPF_REG_1,
+		      0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_0, -32),
+	/* call foo(&fp[-24], &fp[-32])   ; both arguments have IDs in the current
+	 *                                ; stack frame
+	 */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_FP),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -24),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -32),
+	BPF_CALL_REL(2),
+	/* exit 0 */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	/* Function foo()
+	 *
+	 * r9 = &frame[0].fp[-24]  ; save arguments in the callee saved registers,
+	 * r8 = &frame[0].fp[-32]  ; arguments are pointers to pointers to map value
+	 */
+	BPF_MOV64_REG(BPF_REG_9, BPF_REG_1),
+	BPF_MOV64_REG(BPF_REG_8, BPF_REG_2),
+	/* 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      ; no new information about the state is derived from
+	 *                         ; this check, thus produced verifier states differ
+	 *                         ; only in 'insn_idx'
+	 * r9 = r8
+	 */
+	BPF_JMP_REG(BPF_JGT, BPF_REG_6, BPF_REG_7, 1),
+	BPF_MOV64_REG(BPF_REG_9, BPF_REG_8),
+	/* r9 = *r9                ; verifier get's to this point via two paths:
+	 *                         ; (I) one including r9 = r8, verified first;
+	 *                         ; (II) one excluding r9 = r8, verified next.
+	 *                         ; After load of *r9 to r9 the frame[0].fp[-24].id == r9.id.
+	 *                         ; Suppose that checkpoint is created here via path (I).
+	 *                         ; When verifying via (II) the r9.id must be compared against
+	 *                         ; frame[0].fp[-24].id, otherwise (I) and (II) would be
+	 *                         ; incorrectly deemed equivalent.
+	 * if r9 == 0 goto <exit>
+	 */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_9, BPF_REG_9, 0),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_9, 0, 1),
+	/* r8 = *r8                ; read map value via r8, this is not safe
+	 * r0 = *r8                ; because r8 might be not equal to r9.
+	 */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_8, 0),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_8, 0),
+	/* exit 0 */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.flags = BPF_F_TEST_STATE_FREQ,
+	.fixup_map_hash_8b = { 3, 9 },
+	.result = REJECT,
+	.errstr = "R8 invalid mem access 'map_value_or_null'",
+	.result_unpriv = REJECT,
+	.errstr_unpriv = "",
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+},
Signature · 1 line
2.34.1
author maintainer
#15 lore raw

PATCH 6/7 selftests/bpf: Add pruning test case for bpf_spin_lock

In reply to Eduard Zingerman

From: Kumar Kartikeya Dwivedi <[email protected]>

Test that when reg->id is not same for the same register of type PTR_TO_MAP_VALUE between current and old explored state, we currently return false from regsafe and continue exploring.

Without the fix in prior commit, the test case fails.

---
 .../selftests/bpf/verifier/spin_lock.c        | 39 +++++++++++++++++++
 1 file changed, 39 insertions(+)
tools/testing/selftests/bpf/verifier/spin_lock.c +39 -0
index 781621facae4..0a8dcfc37fc6 100644
@@ -331,3 +331,42 @@
 	.errstr = "inside bpf_spin_lock",
 	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
 },
+{
+	"spin_lock: regsafe compare reg->id for map value",
+	.insns = {
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
+	BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_6, offsetof(struct __sk_buff, mark)),
+	BPF_LD_MAP_FD(BPF_REG_1, 0),
+	BPF_MOV64_REG(BPF_REG_9, BPF_REG_1),
+	BPF_ST_MEM(BPF_W, BPF_REG_10, -4, 0),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_0),
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_9),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_MOV64_REG(BPF_REG_8, BPF_REG_0),
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_7),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 4),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_spin_lock),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 1),
+	BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+	BPF_MOV64_REG(BPF_REG_7, BPF_REG_8),
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_7),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 4),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_spin_unlock),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_spin_lock = { 2 },
+	.result = REJECT,
+	.errstr = "bpf_spin_unlock of different lock",
+	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+	.flags = BPF_F_TEST_STATE_FREQ,
+},
Signature · 1 line
2.34.1
author maintainer
#14 lore raw

PATCH 5/7 bpf: use check_ids() for active_lock comparison

In reply to Eduard Zingerman

An update for verifier.c:states_equal()/regsafe() to use check_ids() for active spin lock comparisons. This fixes the issue reported by Kumar Kartikeya Dwivedi in [1] using technique suggested by Edward Cree.

W/o this commit the verifier might be tricked to accept the following program working with a map containing spin locks:

  0: r9 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=1.
  1: r8 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=2.
  2: if r9 == 0 goto exit       ; r9 -> PTR_TO_MAP_VALUE.
  3: if r8 == 0 goto exit       ; r8 -> PTR_TO_MAP_VALUE.
  4: r7 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  5: r6 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  6: bpf_spin_lock(r8)          ; active_lock.id == 2.
  7: if r6 > r7 goto +1         ; No new information about the state
                                ; is derived from this check, thus
                                ; produced verifier states differ only
                                ; in 'insn_idx'.
  8: r9 = r8                    ; Optionally make r9.id == r8.id.
  --- checkpoint ---            ; Assume is_state_visisted() creates a
                                ; checkpoint here.
  9: bpf_spin_unlock(r9)        ; (a,b) active_lock.id == 2.
                                ; (a) r9.id == 2, (b) r9.id == 1.

10: exit(0)

Consider two verification paths:
(a) 0-10
(b) 0-7,9-10

The path (a) is verified first. If checkpoint is created at (8) the (b) would assume that (8) is safe because regsafe() does not compare register ids for registers of type PTR_TO_MAP_VALUE.

[1] https://lore.kernel.org/bpf/[email protected]/

---
 kernel/bpf/verifier.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +13 -3
index 9188370a7ebe..27caea773491 100644
@@ -12981,7 +12981,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		 */
 		return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
 		       range_within(rold, rcur) &&
-		       tnum_in(rold->var_off, rcur->var_off);
+		       tnum_in(rold->var_off, rcur->var_off) &&
+		       check_ids(rold->id, rcur->id, idmap);
 	case PTR_TO_PACKET_META:
 	case PTR_TO_PACKET:
 		if (rcur->type != rold->type)
@@ -13153,8 +13154,17 @@ static bool states_equal(struct bpf_verifier_env *env,
 	if (old->speculative && !cur->speculative)
 		return false;
 
-	if (old->active_lock.ptr != cur->active_lock.ptr ||
-	    old->active_lock.id != cur->active_lock.id)
+	if (old->active_lock.ptr != cur->active_lock.ptr)
+		return false;
+
+	/* Old and cur active_lock's have to be either both present
+	 * or both absent.
+	 */
+	if (!!old->active_lock.id != !!cur->active_lock.id)
+		return false;
+
+	if (old->active_lock.id &&
+	    !check_ids(old->active_lock.id, cur->active_lock.id, env->idmap_scratch))
 		return false;
 
 	if (old->active_rcu_lock != cur->active_rcu_lock)
Signature · 1 line
2.34.1
author maintainer
#17 lore raw

PATCH 7/7 selftests/bpf: test case for relaxed prunning of active_lock.id

In reply to Eduard Zingerman

Check that verifier.c:states_equal() uses check_ids() to match consistent active_lock/map_value configurations. This allows to prune states with active spin locks even if numerical values of active_lock ids do not match across compared states.

---
 .../selftests/bpf/verifier/spin_lock.c        | 75 +++++++++++++++++++
 1 file changed, 75 insertions(+)
tools/testing/selftests/bpf/verifier/spin_lock.c +75 -0
index 0a8dcfc37fc6..eaf114f07e2e 100644
@@ -370,3 +370,78 @@
 	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
 	.flags = BPF_F_TEST_STATE_FREQ,
 },
+/* Make sure that regsafe() compares ids for spin lock records using
+ * check_ids():
+ *  1: r9 = map_lookup_elem(...)  ; r9.id == 1
+ *  2: r8 = map_lookup_elem(...)  ; r8.id == 2
+ *  3: r7 = ktime_get_ns()
+ *  4: r6 = ktime_get_ns()
+ *  5: if r6 > r7 goto <9>
+ *  6: spin_lock(r8)
+ *  7: r9 = r8
+ *  8: goto <10>
+ *  9: spin_lock(r9)
+ * 10: spin_unlock(r9)             ; r9.id == 1 || r9.id == 2 and lock is active,
+ *                                 ; second visit to (10) should be considered safe
+ *                                 ; if check_ids() is used.
+ * 11: exit(0)
+ */
+{
+	"spin_lock: regsafe() check_ids() similar id mappings",
+	.insns = {
+	BPF_ST_MEM(BPF_W, BPF_REG_10, -4, 0),
+	/* r9 = map_lookup_elem(...) */
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4),
+	BPF_LD_MAP_FD(BPF_REG_1,
+		      0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 24),
+	BPF_MOV64_REG(BPF_REG_9, BPF_REG_0),
+	/* r8 = map_lookup_elem(...) */
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4),
+	BPF_LD_MAP_FD(BPF_REG_1,
+		      0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 18),
+	BPF_MOV64_REG(BPF_REG_8, BPF_REG_0),
+	/* 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 +5      ; no new information about the state is derived from
+	 *                         ; this check, thus produced verifier states differ
+	 *                         ; only in 'insn_idx'
+	 * spin_lock(r8)
+	 * r9 = r8
+	 * goto unlock
+	 */
+	BPF_JMP_REG(BPF_JGT, BPF_REG_6, BPF_REG_7, 5),
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_8),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 4),
+	BPF_EMIT_CALL(BPF_FUNC_spin_lock),
+	BPF_MOV64_REG(BPF_REG_9, BPF_REG_8),
+	BPF_JMP_A(3),
+	/* spin_lock(r9) */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_9),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 4),
+	BPF_EMIT_CALL(BPF_FUNC_spin_lock),
+	/* spin_unlock(r9) */
+	BPF_MOV64_REG(BPF_REG_1, BPF_REG_9),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 4),
+	BPF_EMIT_CALL(BPF_FUNC_spin_unlock),
+	/* exit(0) */
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_spin_lock = { 3, 10 },
+	.result = VERBOSE_ACCEPT,
+	.errstr = "28: safe",
+	.result_unpriv = REJECT,
+	.errstr_unpriv = "",
+	.prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+	.flags = BPF_F_TEST_STATE_FREQ,
+},
Signature · 1 line
2.34.1
#16 lore raw

Re: [PATCH bpf-next 6/7] selftests/bpf: Add pruning test case for bpf_spin_lock

In reply to Eduard Zingerman
Quoted 9 lines · Eduard Zingerman

From: Kumar Kartikeya Dwivedi <[email protected]>

Test that when reg->id is not same for the same register of type PTR_TO_MAP_VALUE between current and old explored state, we currently return false from regsafe and continue exploring.

Without the fix in prior commit, the test case fails.

Nice set of fixes. Thanks.
When you resend somebody else's patch please add your SOB. This time I did it while applying.

#18 lore raw
In reply to Eduard Zingerman
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 11 lines · On Fri, 9 Dec 2022 15:57:26 +0200 you wrote:

This patch-set consists of a series of bug fixes for register ID tracking in verifier.c:states_equal()/regsafe() functions:
- for registers of type PTR_TO_MAP_{KEY,VALUE}, PTR_TO_PACKET[_META] the regsafe() should call check_ids() even if registers are byte-to-byte equal;
- states_equal() must maintain idmap that covers all function frames in the state because functions like mark_ptr_or_null_regs() operate on all registers in the state;
- regsafe() must compare spin lock ids for PTR_TO_MAP_VALUE registers.

[...]

Here is the summary with links:
- [bpf-next,1/7] bpf: regsafe() must not skip check_ids()

    https://git.kernel.org/bpf/bpf-next/c/7c884339bbff
  - [bpf-next,2/7] selftests/bpf: test cases for regsafe() bug skipping check_id()
    https://git.kernel.org/bpf/bpf-next/c/cb578c1c9cf6
  - [bpf-next,3/7] bpf: states_equal() must build idmap for all function frames
    https://git.kernel.org/bpf/bpf-next/c/5dd9cdbc9dec
  - [bpf-next,4/7] selftests/bpf: verify states_equal() maintains idmap across all frames
    https://git.kernel.org/bpf/bpf-next/c/7d0579433087
  - [bpf-next,5/7] bpf: use check_ids() for active_lock comparison
    https://git.kernel.org/bpf/bpf-next/c/4ea2bb158bec
  - [bpf-next,6/7] selftests/bpf: Add pruning test case for bpf_spin_lock
    https://git.kernel.org/bpf/bpf-next/c/2026f2062df8
  - [bpf-next,7/7] selftests/bpf: test case for relaxed prunning of active_lock.id
    https://git.kernel.org/bpf/bpf-next/c/efd6286ff74a

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
#19 lore raw
In reply to Eduard Zingerman
Quoted 11 lines · Eduard Zingerman

This patch-set consists of a series of bug fixes for register ID tracking in verifier.c:states_equal()/regsafe() functions:
- for registers of type PTR_TO_MAP_{KEY,VALUE}, PTR_TO_PACKET[_META] the regsafe() should call check_ids() even if registers are byte-to-byte equal;
- states_equal() must maintain idmap that covers all function frames in the state because functions like mark_ptr_or_null_regs() operate on all registers in the state;
- regsafe() must compare spin lock ids for PTR_TO_MAP_VALUE registers.

Quoted 5 lines

The last point covers issue reported by Kumar Kartikeya Dwivedi in [1], I borrowed the test commit from there.
Note, that there is also an issue with register id tracking for scalars described here [2], it would be addressed separately.

Awesome set of patches, thanks for working on this! I left a few comments and suggestions, please take a look, and if they do make sense, consider sending follow up patches.

Let's really try to use asm() next time for selftests, though.

It would be awesome to somehow automatically move test_verifier's tests to this test_progs-based embedded assembly way, but that probably takes some Python hackery (awesome project for some curious soul, for sure).

Anyways, back to the point I wanted to make. Given you've clearly thought about all the ID checks a lot, consider checking refsafe() (not regsafe()!) as well. I think we should do check_ids() there as well. And you did all the preliminary work with making idmap persistent across all frames. Just something to improve (and looks straightforward, unlike many other things you've dealt with recently ;).

Anyways, great work, thanks!

Quoted 25 lines

[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/

Eduard Zingerman (6):
bpf: regsafe() must not skip check_ids()
selftests/bpf: test cases for regsafe() bug skipping check_id()
bpf: states_equal() must build idmap for all function frames selftests/bpf: verify states_equal() maintains idmap across all frames
bpf: use check_ids() for active_lock comparison selftests/bpf: test case for relaxed prunning of active_lock.id

Kumar Kartikeya Dwivedi (1):
selftests/bpf: Add pruning test case for bpf_spin_lock

 include/linux/bpf_verifier.h                  |   4 +-
 kernel/bpf/verifier.c                         |  48 ++++----
 tools/testing/selftests/bpf/verifier/calls.c  |  82 +++++++++++++
 .../bpf/verifier/direct_packet_access.c       |  54 +++++++++
 .../selftests/bpf/verifier/spin_lock.c        | 114 ++++++++++++++++++
 .../selftests/bpf/verifier/value_or_null.c    |  49 ++++++++
 6 files changed, 324 insertions(+), 27 deletions(-)

--
2.34.1

#2 lore raw

Re: [PATCH bpf-next 1/7] bpf: regsafe() must not skip check_ids()

In reply to Eduard Zingerman
Quoted 102 lines · Eduard Zingerman

The verifier.c:regsafe() has the following shortcut:

        equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
        ...
        if (equal)
                return true;

Which is executed regardless old register type. This is incorrect for register types that might have an ID checked by check_ids(), namely:
- PTR_TO_MAP_KEY
- PTR_TO_MAP_VALUE
- PTR_TO_PACKET_META
- PTR_TO_PACKET

The following pattern could be used to exploit this:

  0: r9 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=1.
  1: r8 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=2.
  2: r7 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  3: r6 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  4: if r6 > r7 goto +1         ; No new information about the state

; is derived from this check, thus ; produced verifier states differ only ; in 'insn_idx'.
5: r9 = r8 ; Optionally make r9.id == r8.id.
--- checkpoint --- ; Assume is_state_visisted() creates a
; checkpoint here.
6: if r9 == 0 goto <exit> ; Nullness info is propagated to all
; registers with matching ID.
7: r1 = *(u64 *) r8 ; Not always safe.

Verifier first visits path 1-7 where r8 is verified to be not null at (6). Later the jump from 4 to 6 is examined. The checkpoint for (6) looks as follows:
R8_rD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9_rwD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R10=fp0

The current state is:
R0=... R6=... R7=... fp-8=... R8=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9=map_value_or_null(id=1,off=0,ks=4,vs=8,imm=0) R10=fp0

Note that R8 states are byte-to-byte identical, so regsafe() would exit early and skip call to check_ids(), thus ID mapping 2->2 will not be added to 'idmap'. Next, states for R9 are compared: these are not identical and check_ids() is executed, but 'idmap' is empty, so check_ids() adds mapping 2->1 to 'idmap' and returns success.

This commit pushes the 'equal' down to register types that don't need check_ids().

---
 kernel/bpf/verifier.c | 29 ++++++++---------------------
 1 file changed, 8 insertions(+), 21 deletions(-)
kernel/bpf/verifier.c +2 -19
index 3194e9d9e4e4..d05c5d0344c6 100644
@@ -12926,15 +12926,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 
        equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
 
-       if (rold->type == PTR_TO_STACK)
-               /* two stack pointers are equal only if they're pointing to
-                * the same stack frame, since fp-8 in foo != fp-8 in bar
-                */
-               return equal && rold->frameno == rcur->frameno;
-
-       if (equal)
-               return true;
-
        if (rold->type == NOT_INIT)
                /* explored state can't have used this */
                return true;
@@ -12942,6 +12933,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
                return false;
        switch (base_type(rold->type)) {
        case SCALAR_VALUE:
+               if (equal)
+                       return true;
                if (env->explore_alu_limits)
                        return false;
                if (rcur->type == SCALAR_VALUE) {
@@ -13012,20 +13005,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
                /* new val must satisfy old val knowledge */
                return range_within(rold, rcur) &&
                       tnum_in(rold->var_off, rcur->var_off);
-       case PTR_TO_CTX:
-       case CONST_PTR_TO_MAP:
-       case PTR_TO_PACKET_END:
-       case PTR_TO_FLOW_KEYS:
-       case PTR_TO_SOCKET:
-       case PTR_TO_SOCK_COMMON:
-       case PTR_TO_TCP_SOCK:
-       case PTR_TO_XDP_SOCK:
-               /* Only valid matches are exact, which memcmp() above
-                * would have accepted

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

Quoted 10 lines
kernel/bpf/verifier.c +6 -2
+       case PTR_TO_STACK:
+               /* two stack pointers are equal only if they're pointing to
+                * the same stack frame, since fp-8 in foo != fp-8 in bar
                 */
+               return equal && rold->frameno == rcur->frameno;
        default:
-               /* Don't know what's going on, just say it's not safe */
-               return false;
+               /* Only valid matches are exact, which memcmp() */
+               return equal;

Is it safe to assume this for any possible register type? Wouldn't register types that use id and/or ref_obj_id need extra checks here? I think preexisting default was a safer approach, in which if we forgot to explicitly add support for some new or updated register type, the worst thing is that for that *new* register we'd have suboptimal verification performance, but not safety concerns.

Quoted 6 lines
kernel/bpf/verifier.c +0 -1
        }
 
        /* Shouldn't get here; if we do, say it's not safe */
--

2.34.1

#7 lore raw

Re: [PATCH bpf-next 3/7] bpf: states_equal() must build idmap for all function frames

In reply to Eduard Zingerman
Quoted 74 lines · Eduard Zingerman

verifier.c:states_equal() must maintain register ID mapping across all function frames. Otherwise the following example might be erroneously marked as safe:

main:

    fp[-24] = map_lookup_elem(...)  ; frame[0].fp[-24].id == 1
    fp[-32] = map_lookup_elem(...)  ; frame[0].fp[-32].id == 2
    r1 = &fp[-24]
    r2 = &fp[-32]
    call foo()
    r0 = 0
    exit

foo:
0: r9 = r1
1: r8 = r2
2: r7 = ktime_get_ns()
3: r6 = ktime_get_ns()
4: if (r6 > r7) goto skip_assign
5: r9 = r8

skip_assign: ; <--- checkpoint
6: r9 = *r9 ; (a) frame[1].r9.id == 2

                            ; (b) frame[1].r9.id == 1

7: if r9 == 0 goto exit: ; mark_ptr_or_null_regs() transfers != 0 info

                            ; for all regs sharing ID:
                            ;   (a) r9 != 0 => &frame[0].fp[-32] != 0
                            ;   (b) r9 != 0 => &frame[0].fp[-24] != 0

8: r8 = *r8 ; (a) r8 == &frame[0].fp[-32]

                            ; (b) r8 == &frame[0].fp[-32]

9: r0 = *r8 ; (a) safe
; (b) unsafe

exit:
10: exit

While processing call to foo() verifier considers the following execution paths:

(a) 0-10
(b) 0-4,6-10
(There is also path 0-7,10 but it is not interesting for the issue at
hand. (a) is verified first.)

Suppose that checkpoint is created at (6) when path (a) is verified, next path (b) is verified and (6) is reached.

If states_equal() maintains separate 'idmap' for each frame the mapping at (6) for frame[1] would be empty and regsafe(r9)::check_ids() would add a pair 2->1 and return true, which is an error.

If states_equal() maintains single 'idmap' for all frames the mapping at (6) would be { 1->1, 2->2 } and regsafe(r9)::check_ids() would return false when trying to add a pair 2->1.

This issue was suggested in the following discussion:
https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/

---
 include/linux/bpf_verifier.h | 4 ++--
 kernel/bpf/verifier.c        | 3 ++-
 2 files changed, 4 insertions(+), 3 deletions(-)
include/linux/bpf_verifier.h +0 -0
index 70d06a99f0b8..c1f769515beb 100644

include/linux/bpf_verifier.h struct bpf_id_pair { · line 278

Quoted 8 lines
include/linux/bpf_verifier.h +2 -2
@@ -273,9 +273,9 @@ struct bpf_id_pair {
        u32 cur;
 };
 
-/* Maximum number of register states that can exist at once */
-#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)
 #define MAX_CALL_FRAMES 8
+/* Maximum number of register states that can exist at once */
+#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)

this is overly pessimistic, the total number of stack slots doesn't change no matter how many call frames we have, it would be better to define this as:

#define BPF_ID_MAP_SIZE (MAX_BPF_REG * MAX_CALL_FRAMES + MAX_BPF_STACK / BPF_REG_SIZE)

Unless I missed something.

Quoted 27 lines
include/linux/bpf_verifier.h +0 -0
 struct bpf_verifier_state {
        /* call stack tracking */
        struct bpf_func_state *frame[MAX_CALL_FRAMES];
kernel/bpf/verifier.c +2 -2
index d05c5d0344c6..9188370a7ebe 100644
@@ -13122,7 +13122,6 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat
 {
        int i;
 
-       memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch));
        for (i = 0; i < MAX_BPF_REG; i++)
                if (!regsafe(env, &old->regs[i], &cur->regs[i],
                             env->idmap_scratch))
@@ -13146,6 +13145,8 @@ static bool states_equal(struct bpf_verifier_env *env,
        if (old->curframe != cur->curframe)
                return false;
 
+       memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch));
+
        /* Verification state from speculative execution simulation
         * must never prune a non-speculative execution one.
         */
--

2.34.1

#11 lore raw

Re: [PATCH bpf-next 4/7] selftests/bpf: verify states_equal() maintains idmap across all frames

In reply to Eduard Zingerman
Quoted 7 lines · Eduard Zingerman

A test case that would erroneously pass verification if verifier.c:states_equal() maintains separate register ID mappings for call frames.

---

It's so hard to read these tests. Moving forward, let's try adding new verifier tests like this using __naked functions and embedded assembly. With recent test loader changes ([0]), there isn't much that's needed, except for a few simple examples to get us started and perhaps __flags(BPF_F_TEST_STATE_FREQ) support. The upside is that using maps or global variables from assembly is now possible and easy, and doesn't require any custom loader support at all.

[0] https://patchwork.kernel.org/project/netdevbpf/list/?series=702713&state=*

Quoted 96 lines
 tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++
 1 file changed, 82 insertions(+)
tools/testing/selftests/bpf/verifier/calls.c +82 -1
index 3193915c5ee6..bcd15b26dcee 100644
@@ -2305,3 +2305,85 @@
        .errstr = "!read_ok",
        .result = REJECT,
 },
+/* Make sure that verifier.c:states_equal() considers IDs from all
+ * frames when building 'idmap' for check_ids().
+ */
+{
+       "calls: check_ids() across call boundary",
+       .insns = {
+       /* Function main() */
+       BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+       /* fp[-24] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */
+       BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+       BPF_LD_MAP_FD(BPF_REG_1,
+                     0),
+       BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+       BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_0, -24),
+       /* fp[-32] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */
+       BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+       BPF_LD_MAP_FD(BPF_REG_1,
+                     0),
+       BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+       BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_0, -32),
+       /* call foo(&fp[-24], &fp[-32])   ; both arguments have IDs in the current
+        *                                ; stack frame
+        */
+       BPF_MOV64_REG(BPF_REG_1, BPF_REG_FP),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -24),
+       BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -32),
+       BPF_CALL_REL(2),
+       /* exit 0 */
+       BPF_MOV64_IMM(BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       /* Function foo()
+        *
+        * r9 = &frame[0].fp[-24]  ; save arguments in the callee saved registers,
+        * r8 = &frame[0].fp[-32]  ; arguments are pointers to pointers to map value
+        */
+       BPF_MOV64_REG(BPF_REG_9, BPF_REG_1),
+       BPF_MOV64_REG(BPF_REG_8, BPF_REG_2),
+       /* 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      ; no new information about the state is derived from
+        *                         ; this check, thus produced verifier states differ
+        *                         ; only in 'insn_idx'
+        * r9 = r8
+        */
+       BPF_JMP_REG(BPF_JGT, BPF_REG_6, BPF_REG_7, 1),
+       BPF_MOV64_REG(BPF_REG_9, BPF_REG_8),
+       /* r9 = *r9                ; verifier get's to this point via two paths:
+        *                         ; (I) one including r9 = r8, verified first;
+        *                         ; (II) one excluding r9 = r8, verified next.
+        *                         ; After load of *r9 to r9 the frame[0].fp[-24].id == r9.id.
+        *                         ; Suppose that checkpoint is created here via path (I).
+        *                         ; When verifying via (II) the r9.id must be compared against
+        *                         ; frame[0].fp[-24].id, otherwise (I) and (II) would be
+        *                         ; incorrectly deemed equivalent.
+        * if r9 == 0 goto <exit>
+        */
+       BPF_LDX_MEM(BPF_DW, BPF_REG_9, BPF_REG_9, 0),
+       BPF_JMP_IMM(BPF_JEQ, BPF_REG_9, 0, 1),
+       /* r8 = *r8                ; read map value via r8, this is not safe
+        * r0 = *r8                ; because r8 might be not equal to r9.
+        */
+       BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_8, 0),
+       BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_8, 0),
+       /* exit 0 */
+       BPF_MOV64_IMM(BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       },
+       .flags = BPF_F_TEST_STATE_FREQ,
+       .fixup_map_hash_8b = { 3, 9 },
+       .result = REJECT,
+       .errstr = "R8 invalid mem access 'map_value_or_null'",
+       .result_unpriv = REJECT,
+       .errstr_unpriv = "",
+       .prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+},
--

2.34.1

author maintainer
#3 lore raw

Re: [PATCH bpf-next 1/7] bpf: regsafe() must not skip check_ids()

In reply to Andrii Nakryiko
Quoted 112 lines · Andrii Nakryiko
Quoted 111 lines · Eduard Zingerman

The verifier.c:regsafe() has the following shortcut:

        equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
        ...
        if (equal)
                return true;

Which is executed regardless old register type. This is incorrect for register types that might have an ID checked by check_ids(), namely:
- PTR_TO_MAP_KEY
- PTR_TO_MAP_VALUE
- PTR_TO_PACKET_META
- PTR_TO_PACKET

The following pattern could be used to exploit this:

  0: r9 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=1.
  1: r8 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=2.
  2: r7 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  3: r6 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  4: if r6 > r7 goto +1         ; No new information about the state

; is derived from this check, thus ; produced verifier states differ only ; in 'insn_idx'.
5: r9 = r8 ; Optionally make r9.id == r8.id.
--- checkpoint --- ; Assume is_state_visisted() creates a
; checkpoint here.
6: if r9 == 0 goto <exit> ; Nullness info is propagated to all
; registers with matching ID.
7: r1 = *(u64 *) r8 ; Not always safe.

Verifier first visits path 1-7 where r8 is verified to be not null at (6). Later the jump from 4 to 6 is examined. The checkpoint for (6) looks as follows:
R8_rD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9_rwD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R10=fp0

The current state is:
R0=... R6=... R7=... fp-8=... R8=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9=map_value_or_null(id=1,off=0,ks=4,vs=8,imm=0) R10=fp0

Note that R8 states are byte-to-byte identical, so regsafe() would exit early and skip call to check_ids(), thus ID mapping 2->2 will not be added to 'idmap'. Next, states for R9 are compared: these are not identical and check_ids() is executed, but 'idmap' is empty, so check_ids() adds mapping 2->1 to 'idmap' and returns success.

This commit pushes the 'equal' down to register types that don't need check_ids().

---
 kernel/bpf/verifier.c | 29 ++++++++---------------------
 1 file changed, 8 insertions(+), 21 deletions(-)
kernel/bpf/verifier.c +7 -21
index 3194e9d9e4e4..d05c5d0344c6 100644
@@ -12926,15 +12926,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 
        equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
 
-       if (rold->type == PTR_TO_STACK)
-               /* two stack pointers are equal only if they're pointing to
-                * the same stack frame, since fp-8 in foo != fp-8 in bar
-                */
-               return equal && rold->frameno == rcur->frameno;
-
-       if (equal)
-               return true;
-
        if (rold->type == NOT_INIT)
                /* explored state can't have used this */
                return true;
@@ -12942,6 +12933,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
                return false;
        switch (base_type(rold->type)) {
        case SCALAR_VALUE:
+               if (equal)
+                       return true;
                if (env->explore_alu_limits)
                        return false;
                if (rcur->type == SCALAR_VALUE) {
@@ -13012,20 +13005,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
                /* new val must satisfy old val knowledge */
                return range_within(rold, rcur) &&
                       tnum_in(rold->var_off, rcur->var_off);
-       case PTR_TO_CTX:
-       case CONST_PTR_TO_MAP:
-       case PTR_TO_PACKET_END:
-       case PTR_TO_FLOW_KEYS:
-       case PTR_TO_SOCKET:
-       case PTR_TO_SOCK_COMMON:
-       case PTR_TO_TCP_SOCK:
-       case PTR_TO_XDP_SOCK:
-               /* Only valid matches are exact, which memcmp() above
-                * would have accepted
+       case PTR_TO_STACK:
+               /* two stack pointers are equal only if they're pointing to
+                * the same stack frame, since fp-8 in foo != fp-8 in bar
                 */
+               return equal && rold->frameno == rcur->frameno;
        default:
-               /* Don't know what's going on, just say it's not safe */
-               return false;
+               /* Only valid matches are exact, which memcmp() */
Quoted 8 lines

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

Quoted 1 line
kernel/bpf/verifier.c +1 -0
+               return equal;

Is it safe to assume this for any possible register type? Wouldn't register types that use id and/or ref_obj_id need extra checks here? I think preexisting default was a safer approach, in which if we forgot to explicitly add support for some new or updated register type, the worst thing is that for that *new* register we'd have suboptimal verification performance, but not safety concerns.

Well, I don't think that this commit changes regsafe() behavior in this regard. Here is how the code was structured before this commit:

static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
struct bpf_reg_state *rcur, struct bpf_id_pair *idmap)

{
	bool equal;

	if (!(rold->live & REG_LIVE_READ))
		return true;
	equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
	if (rold->type == PTR_TO_STACK)
		return equal && rold->frameno == rcur->frameno;
--->	if (equal)
		return true;
	if (rold->type == NOT_INIT)
		return true;
	if (rcur->type == NOT_INIT)
		return false;
	switch (base_type(rold->type)) {
	case SCALAR_VALUE:
        	... it's own logic, always returns ...
	case PTR_TO_MAP_KEY:
	case PTR_TO_MAP_VALUE:
        	... it's own logic, always returns ...
	case PTR_TO_PACKET_META:
	case PTR_TO_PACKET:
        	... it's own logic, always returns ...
	case PTR_TO_CTX:
	case CONST_PTR_TO_MAP:
	case PTR_TO_PACKET_END:
	case PTR_TO_FLOW_KEYS:
	case PTR_TO_SOCKET:
	case PTR_TO_SOCK_COMMON:
	case PTR_TO_TCP_SOCK:
	case PTR_TO_XDP_SOCK:
	default:
		return false;
	}

	/* Shouldn't get here; if we do, say it's not safe */
	WARN_ON_ONCE(1);
	return false;
}

So the "safe if byte-to-byte equal" behavior was present already. I can add an explicit list of types to the "return equal;" branch and add a default "return false;" branch if you think that it is more fool-proof.

Quoted 8 lines
Quoted 8 lines
kernel/bpf/verifier.c +0 -1
        }
 
        /* Shouldn't get here; if we do, say it's not safe */
--

2.34.1

author maintainer
#8 lore raw

Re: [PATCH bpf-next 3/7] bpf: states_equal() must build idmap for all function frames

In reply to Andrii Nakryiko
Quoted 88 lines · Andrii Nakryiko
Quoted 74 lines · Eduard Zingerman

verifier.c:states_equal() must maintain register ID mapping across all function frames. Otherwise the following example might be erroneously marked as safe:

main:

    fp[-24] = map_lookup_elem(...)  ; frame[0].fp[-24].id == 1
    fp[-32] = map_lookup_elem(...)  ; frame[0].fp[-32].id == 2
    r1 = &fp[-24]
    r2 = &fp[-32]
    call foo()
    r0 = 0
    exit

foo:
0: r9 = r1
1: r8 = r2
2: r7 = ktime_get_ns()
3: r6 = ktime_get_ns()
4: if (r6 > r7) goto skip_assign
5: r9 = r8

skip_assign: ; <--- checkpoint
6: r9 = *r9 ; (a) frame[1].r9.id == 2

                            ; (b) frame[1].r9.id == 1

7: if r9 == 0 goto exit: ; mark_ptr_or_null_regs() transfers != 0 info

                            ; for all regs sharing ID:
                            ;   (a) r9 != 0 => &frame[0].fp[-32] != 0
                            ;   (b) r9 != 0 => &frame[0].fp[-24] != 0

8: r8 = *r8 ; (a) r8 == &frame[0].fp[-32]

                            ; (b) r8 == &frame[0].fp[-32]

9: r0 = *r8 ; (a) safe
; (b) unsafe

exit:
10: exit

While processing call to foo() verifier considers the following execution paths:

(a) 0-10
(b) 0-4,6-10
(There is also path 0-7,10 but it is not interesting for the issue at
hand. (a) is verified first.)

Suppose that checkpoint is created at (6) when path (a) is verified, next path (b) is verified and (6) is reached.

If states_equal() maintains separate 'idmap' for each frame the mapping at (6) for frame[1] would be empty and regsafe(r9)::check_ids() would add a pair 2->1 and return true, which is an error.

If states_equal() maintains single 'idmap' for all frames the mapping at (6) would be { 1->1, 2->2 } and regsafe(r9)::check_ids() would return false when trying to add a pair 2->1.

This issue was suggested in the following discussion:
https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/

---
 include/linux/bpf_verifier.h | 4 ++--
 kernel/bpf/verifier.c        | 3 ++-
 2 files changed, 4 insertions(+), 3 deletions(-)
include/linux/bpf_verifier.h +0 -0
index 70d06a99f0b8..c1f769515beb 100644

include/linux/bpf_verifier.h struct bpf_id_pair { · line 278

Quoted 8 lines
include/linux/bpf_verifier.h +2 -2
@@ -273,9 +273,9 @@ struct bpf_id_pair {
        u32 cur;
 };
 
-/* Maximum number of register states that can exist at once */
-#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)
 #define MAX_CALL_FRAMES 8
+/* Maximum number of register states that can exist at once */
+#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)

this is overly pessimistic, the total number of stack slots doesn't change no matter how many call frames we have, it would be better to define this as:

Quoted 4 lines

#define BPF_ID_MAP_SIZE (MAX_BPF_REG * MAX_CALL_FRAMES + MAX_BPF_STACK / BPF_REG_SIZE)

Unless I missed something.

Current bpf_check() mechanics looks as follows:
- do_check_{subprogs,main}() (indirectly):
- when a pseudo-function is called the call is processed by __check_func_call(), it allocates callee's struct bpf_func_state using kzalloc() and does not update ->stack and ->allocated_stack fields;
- when a stack write is processed by check_mem_access():
- check_stack_access_within_bounds() verifies that offset is within 0..-MAX_BPF_STACK;
- check_stack_write_{fixed,var}_off() calls grow_stack_state() which uses realloc_array() to increase ->stack as necessary;
- update_stack_depth() is used to increase env->subprog_info[...].stack_depth as appropriate;
- check_max_stack_depth() verifies that cumulative stack depth does not exceed MAX_BPF_STACK using env->subprog_info[...].stack_depth values.

This means that during do_check_*() we can have MAX_CALL_FRAMES functions each with a stack of size MAX_BPF_STACK. The following example could be used to verify the above assumptions:

{
	"check_max_depth",
	.insns = {
		BPF_ST_MEM(BPF_DW, BPF_REG_FP, -512, 0),
		BPF_CALL_REL(2),
		BPF_MOV64_IMM(BPF_REG_0, 0),
		BPF_EXIT_INSN(),

		BPF_ST_MEM(BPF_DW, BPF_REG_FP, -512, 0),
		BPF_MOV64_IMM(BPF_REG_0, 0),
		BPF_EXIT_INSN(),
	},
	.result = REJECT,
},

Here is the verifier log that shows that two frames both of size MAX_BPF_STACK slots were present during verification:

# ./test_verifier -vv 1030
#1030/p check_max_depth FAIL
Unexpected error message!
	EXP: (null)
	RES:
func#0 @0
func#1 @4
0: R1=ctx(off=0,imm=0) R10=fp0
0: (7a) *(u64 *)(r10 -512) = 0        ; R10=fp0 fp-512_w=mmmmmmmm
1: (85) call pc+2
caller:
 R10=fp0 fp-512_w=mmmmmmmm
callee:
 frame1: R1=ctx(off=0,imm=0) R10=fp0
4: (7a) *(u64 *)(r10 -512) = 0        ; frame1: R10=fp0 fp-512_w=mmmmmmmm
5: (b7) r0 = 0                        ; frame1: R0_w=0
6: (95) exit
returning from callee:
 frame1: R0_w=0 R1=ctx(off=0,imm=0) R10=fp0 fp-512_w=mmmmmmmm
to caller at 2:
 R0_w=0 R10=fp0 fp-512_w=mmmmmmmm

from 6 to 2: R0_w=0 R10=fp0 fp-512_w=mmmmmmmm
2: (b7) r0 = 0 ; R0_w=0
3: (95) exit
combined stack size of 2 calls is 1024. Too large
verification time 541 usec
stack depth 512+512

Quoted 30 lines
Quoted 30 lines
include/linux/bpf_verifier.h +0 -0
 struct bpf_verifier_state {
        /* call stack tracking */
        struct bpf_func_state *frame[MAX_CALL_FRAMES];
kernel/bpf/verifier.c +2 -2
index d05c5d0344c6..9188370a7ebe 100644
@@ -13122,7 +13122,6 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat
 {
        int i;
 
-       memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch));
        for (i = 0; i < MAX_BPF_REG; i++)
                if (!regsafe(env, &old->regs[i], &cur->regs[i],
                             env->idmap_scratch))
@@ -13146,6 +13145,8 @@ static bool states_equal(struct bpf_verifier_env *env,
        if (old->curframe != cur->curframe)
                return false;
 
+       memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch));
+
        /* Verification state from speculative execution simulation
         * must never prune a non-speculative execution one.
         */
--

2.34.1

author maintainer
#20 lore raw
In reply to Andrii Nakryiko
Quoted 29 lines · Andrii Nakryiko
Quoted 11 lines · Eduard Zingerman

This patch-set consists of a series of bug fixes for register ID tracking in verifier.c:states_equal()/regsafe() functions:
- for registers of type PTR_TO_MAP_{KEY,VALUE}, PTR_TO_PACKET[_META] the regsafe() should call check_ids() even if registers are byte-to-byte equal;
- states_equal() must maintain idmap that covers all function frames in the state because functions like mark_ptr_or_null_regs() operate on all registers in the state;
- regsafe() must compare spin lock ids for PTR_TO_MAP_VALUE registers.

Quoted 5 lines

The last point covers issue reported by Kumar Kartikeya Dwivedi in [1], I borrowed the test commit from there.
Note, that there is also an issue with register id tracking for scalars described here [2], it would be addressed separately.

Awesome set of patches, thanks for working on this! I left a few comments and suggestions, please take a look, and if they do make sense, consider sending follow up patches.

Let's really try to use asm() next time for selftests, though.

It would be awesome to somehow automatically move test_verifier's tests to this test_progs-based embedded assembly way, but that probably takes some Python hackery (awesome project for some curious soul, for sure).

Quoted 7 lines

Anyways, back to the point I wanted to make. Given you've clearly thought about all the ID checks a lot, consider checking refsafe() (not regsafe()!) as well. I think we should do check_ids() there as well. And you did all the preliminary work with making idmap persistent across all frames. Just something to improve (and looks straightforward, unlike many other things you've dealt with recently ;).

Makes sense, I'll work on it.

Quoted 2 lines

Anyways, great work, thanks!

Thank you.

Quoted 26 lines
Quoted 26 lines

[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/

Eduard Zingerman (6):
bpf: regsafe() must not skip check_ids()
selftests/bpf: test cases for regsafe() bug skipping check_id()
bpf: states_equal() must build idmap for all function frames selftests/bpf: verify states_equal() maintains idmap across all frames
bpf: use check_ids() for active_lock comparison selftests/bpf: test case for relaxed prunning of active_lock.id

Kumar Kartikeya Dwivedi (1):
selftests/bpf: Add pruning test case for bpf_spin_lock

 include/linux/bpf_verifier.h                  |   4 +-
 kernel/bpf/verifier.c                         |  48 ++++----
 tools/testing/selftests/bpf/verifier/calls.c  |  82 +++++++++++++
 .../bpf/verifier/direct_packet_access.c       |  54 +++++++++
 .../selftests/bpf/verifier/spin_lock.c        | 114 ++++++++++++++++++
 .../selftests/bpf/verifier/value_or_null.c    |  49 ++++++++
 6 files changed, 324 insertions(+), 27 deletions(-)

--
2.34.1

author maintainer
#12 lore raw

Re: [PATCH bpf-next 4/7] selftests/bpf: verify states_equal() maintains idmap across all frames

In reply to Andrii Nakryiko
Quoted 18 lines · Andrii Nakryiko
Quoted 7 lines · Eduard Zingerman

A test case that would erroneously pass verification if verifier.c:states_equal() maintains separate register ID mappings for call frames.

---

It's so hard to read these tests. Moving forward, let's try adding new verifier tests like this using __naked functions and embedded assembly. With recent test loader changes ([0]), there isn't much that's needed, except for a few simple examples to get us started and perhaps __flags(BPF_F_TEST_STATE_FREQ) support. The upside is that using maps or global variables from assembly is now possible and easy, and doesn't require any custom loader support at all.

Quoted 3 lines

[0] https://patchwork.kernel.org/project/netdevbpf/list/?series=702713&state=*

This is very nice, I'll try to use it for the next patch-set. How do you think it should look like for test_verifier kind of tests? The easiest way would be to just add new BPF sources under progs/ and have some prog_tests/verifier.c like this:

int test_verifier()
...
RUN_TESTS(array_access),
RUN_TESTS(scalar_ids)
...

Thus reusing the build mechanics for skeletons etc. However, it seems to break current logical separation between "unit" tests in test_verifier and "functional" tests in test_progs. But this may be ok.

Quoted 96 lines
Quoted 96 lines
 tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++
 1 file changed, 82 insertions(+)
tools/testing/selftests/bpf/verifier/calls.c +82 -1
index 3193915c5ee6..bcd15b26dcee 100644
@@ -2305,3 +2305,85 @@
        .errstr = "!read_ok",
        .result = REJECT,
 },
+/* Make sure that verifier.c:states_equal() considers IDs from all
+ * frames when building 'idmap' for check_ids().
+ */
+{
+       "calls: check_ids() across call boundary",
+       .insns = {
+       /* Function main() */
+       BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+       /* fp[-24] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */
+       BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+       BPF_LD_MAP_FD(BPF_REG_1,
+                     0),
+       BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+       BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_0, -24),
+       /* fp[-32] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */
+       BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+       BPF_LD_MAP_FD(BPF_REG_1,
+                     0),
+       BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+       BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_0, -32),
+       /* call foo(&fp[-24], &fp[-32])   ; both arguments have IDs in the current
+        *                                ; stack frame
+        */
+       BPF_MOV64_REG(BPF_REG_1, BPF_REG_FP),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -24),
+       BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -32),
+       BPF_CALL_REL(2),
+       /* exit 0 */
+       BPF_MOV64_IMM(BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       /* Function foo()
+        *
+        * r9 = &frame[0].fp[-24]  ; save arguments in the callee saved registers,
+        * r8 = &frame[0].fp[-32]  ; arguments are pointers to pointers to map value
+        */
+       BPF_MOV64_REG(BPF_REG_9, BPF_REG_1),
+       BPF_MOV64_REG(BPF_REG_8, BPF_REG_2),
+       /* 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      ; no new information about the state is derived from
+        *                         ; this check, thus produced verifier states differ
+        *                         ; only in 'insn_idx'
+        * r9 = r8
+        */
+       BPF_JMP_REG(BPF_JGT, BPF_REG_6, BPF_REG_7, 1),
+       BPF_MOV64_REG(BPF_REG_9, BPF_REG_8),
+       /* r9 = *r9                ; verifier get's to this point via two paths:
+        *                         ; (I) one including r9 = r8, verified first;
+        *                         ; (II) one excluding r9 = r8, verified next.
+        *                         ; After load of *r9 to r9 the frame[0].fp[-24].id == r9.id.
+        *                         ; Suppose that checkpoint is created here via path (I).
+        *                         ; When verifying via (II) the r9.id must be compared against
+        *                         ; frame[0].fp[-24].id, otherwise (I) and (II) would be
+        *                         ; incorrectly deemed equivalent.
+        * if r9 == 0 goto <exit>
+        */
+       BPF_LDX_MEM(BPF_DW, BPF_REG_9, BPF_REG_9, 0),
+       BPF_JMP_IMM(BPF_JEQ, BPF_REG_9, 0, 1),
+       /* r8 = *r8                ; read map value via r8, this is not safe
+        * r0 = *r8                ; because r8 might be not equal to r9.
+        */
+       BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_8, 0),
+       BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_8, 0),
+       /* exit 0 */
+       BPF_MOV64_IMM(BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       },
+       .flags = BPF_F_TEST_STATE_FREQ,
+       .fixup_map_hash_8b = { 3, 9 },
+       .result = REJECT,
+       .errstr = "R8 invalid mem access 'map_value_or_null'",
+       .result_unpriv = REJECT,
+       .errstr_unpriv = "",
+       .prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+},
--

2.34.1

#13 lore raw

Re: [PATCH bpf-next 4/7] selftests/bpf: verify states_equal() maintains idmap across all frames

Quoted 35 lines · Eduard Zingerman
Quoted 18 lines · Andrii Nakryiko
Quoted 7 lines · Eduard Zingerman

A test case that would erroneously pass verification if verifier.c:states_equal() maintains separate register ID mappings for call frames.

---

It's so hard to read these tests. Moving forward, let's try adding new verifier tests like this using __naked functions and embedded assembly. With recent test loader changes ([0]), there isn't much that's needed, except for a few simple examples to get us started and perhaps __flags(BPF_F_TEST_STATE_FREQ) support. The upside is that using maps or global variables from assembly is now possible and easy, and doesn't require any custom loader support at all.

Quoted 3 lines

[0] https://patchwork.kernel.org/project/netdevbpf/list/?series=702713&state=*

This is very nice, I'll try to use it for the next patch-set. How do you think it should look like for test_verifier kind of tests? The easiest way would be to just add new BPF sources under progs/ and have some prog_tests/verifier.c like this:

int test_verifier()
...
RUN_TESTS(array_access),
RUN_TESTS(scalar_ids)
...

Quoted 4 lines

Thus reusing the build mechanics for skeletons etc. However, it seems to break current logical separation between "unit" tests in test_verifier and "functional" tests in test_progs. But this may be ok.

Yes, reusing skeletons and stuff, of course. But I wouldn't necessarily make all of them as part of a single test_verifier test. I'd probably have multiple tests with logically grouped sets of tests.

The interesting part is whether we can somehow automatically convert macro-based test_verifier tests to this new embedded asm :) At least most of them, but it's not clear how much work that would be, so I just mentioned the possibility. I don't think we should manually rewrite 1000+ tests, of course.

Quoted 99 lines
Quoted 98 lines
Quoted 98 lines

 tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++
 1 file changed, 82 insertions(+)
tools/testing/selftests/bpf/verifier/calls.c +82 -1
index 3193915c5ee6..bcd15b26dcee 100644
@@ -2305,3 +2305,85 @@
        .errstr = "!read_ok",
        .result = REJECT,
 },
+/* Make sure that verifier.c:states_equal() considers IDs from all
+ * frames when building 'idmap' for check_ids().
+ */
+{
+       "calls: check_ids() across call boundary",
+       .insns = {
+       /* Function main() */
+       BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+       /* fp[-24] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */
+       BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+       BPF_LD_MAP_FD(BPF_REG_1,
+                     0),
+       BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+       BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_0, -24),
+       /* fp[-32] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */
+       BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+       BPF_LD_MAP_FD(BPF_REG_1,
+                     0),
+       BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+       BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_0, -32),
+       /* call foo(&fp[-24], &fp[-32])   ; both arguments have IDs in the current
+        *                                ; stack frame
+        */
+       BPF_MOV64_REG(BPF_REG_1, BPF_REG_FP),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -24),
+       BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP),
+       BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -32),
+       BPF_CALL_REL(2),
+       /* exit 0 */
+       BPF_MOV64_IMM(BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       /* Function foo()
+        *
+        * r9 = &frame[0].fp[-24]  ; save arguments in the callee saved registers,
+        * r8 = &frame[0].fp[-32]  ; arguments are pointers to pointers to map value
+        */
+       BPF_MOV64_REG(BPF_REG_9, BPF_REG_1),
+       BPF_MOV64_REG(BPF_REG_8, BPF_REG_2),
+       /* 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      ; no new information about the state is derived from
+        *                         ; this check, thus produced verifier states differ
+        *                         ; only in 'insn_idx'
+        * r9 = r8
+        */
+       BPF_JMP_REG(BPF_JGT, BPF_REG_6, BPF_REG_7, 1),
+       BPF_MOV64_REG(BPF_REG_9, BPF_REG_8),
+       /* r9 = *r9                ; verifier get's to this point via two paths:
+        *                         ; (I) one including r9 = r8, verified first;
+        *                         ; (II) one excluding r9 = r8, verified next.
+        *                         ; After load of *r9 to r9 the frame[0].fp[-24].id == r9.id.
+        *                         ; Suppose that checkpoint is created here via path (I).
+        *                         ; When verifying via (II) the r9.id must be compared against
+        *                         ; frame[0].fp[-24].id, otherwise (I) and (II) would be
+        *                         ; incorrectly deemed equivalent.
+        * if r9 == 0 goto <exit>
+        */
+       BPF_LDX_MEM(BPF_DW, BPF_REG_9, BPF_REG_9, 0),
+       BPF_JMP_IMM(BPF_JEQ, BPF_REG_9, 0, 1),
+       /* r8 = *r8                ; read map value via r8, this is not safe
+        * r0 = *r8                ; because r8 might be not equal to r9.
+        */
+       BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_8, 0),
+       BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_8, 0),
+       /* exit 0 */
+       BPF_MOV64_IMM(BPF_REG_0, 0),
+       BPF_EXIT_INSN(),
+       },
+       .flags = BPF_F_TEST_STATE_FREQ,
+       .fixup_map_hash_8b = { 3, 9 },
+       .result = REJECT,
+       .errstr = "R8 invalid mem access 'map_value_or_null'",
+       .result_unpriv = REJECT,
+       .errstr_unpriv = "",
+       .prog_type = BPF_PROG_TYPE_CGROUP_SKB,
+},
--

2.34.1

#9 lore raw

Re: [PATCH bpf-next 3/7] bpf: states_equal() must build idmap for all function frames

In reply to Eduard Zingerman
Quoted 154 lines · Eduard Zingerman
Quoted 88 lines · Andrii Nakryiko
Quoted 74 lines · Eduard Zingerman

verifier.c:states_equal() must maintain register ID mapping across all function frames. Otherwise the following example might be erroneously marked as safe:

main:

    fp[-24] = map_lookup_elem(...)  ; frame[0].fp[-24].id == 1
    fp[-32] = map_lookup_elem(...)  ; frame[0].fp[-32].id == 2
    r1 = &fp[-24]
    r2 = &fp[-32]
    call foo()
    r0 = 0
    exit

foo:
0: r9 = r1
1: r8 = r2
2: r7 = ktime_get_ns()
3: r6 = ktime_get_ns()
4: if (r6 > r7) goto skip_assign
5: r9 = r8

skip_assign: ; <--- checkpoint
6: r9 = *r9 ; (a) frame[1].r9.id == 2

                            ; (b) frame[1].r9.id == 1

7: if r9 == 0 goto exit: ; mark_ptr_or_null_regs() transfers != 0 info

                            ; for all regs sharing ID:
                            ;   (a) r9 != 0 => &frame[0].fp[-32] != 0
                            ;   (b) r9 != 0 => &frame[0].fp[-24] != 0

8: r8 = *r8 ; (a) r8 == &frame[0].fp[-32]

                            ; (b) r8 == &frame[0].fp[-32]

9: r0 = *r8 ; (a) safe
; (b) unsafe

exit:
10: exit

While processing call to foo() verifier considers the following execution paths:

(a) 0-10
(b) 0-4,6-10
(There is also path 0-7,10 but it is not interesting for the issue at
hand. (a) is verified first.)

Suppose that checkpoint is created at (6) when path (a) is verified, next path (b) is verified and (6) is reached.

If states_equal() maintains separate 'idmap' for each frame the mapping at (6) for frame[1] would be empty and regsafe(r9)::check_ids() would add a pair 2->1 and return true, which is an error.

If states_equal() maintains single 'idmap' for all frames the mapping at (6) would be { 1->1, 2->2 } and regsafe(r9)::check_ids() would return false when trying to add a pair 2->1.

This issue was suggested in the following discussion:
https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/

---
 include/linux/bpf_verifier.h | 4 ++--
 kernel/bpf/verifier.c        | 3 ++-
 2 files changed, 4 insertions(+), 3 deletions(-)
include/linux/bpf_verifier.h +0 -0
index 70d06a99f0b8..c1f769515beb 100644

include/linux/bpf_verifier.h struct bpf_id_pair { · line 278

Quoted 8 lines
include/linux/bpf_verifier.h +2 -2
@@ -273,9 +273,9 @@ struct bpf_id_pair {
        u32 cur;
 };
 
-/* Maximum number of register states that can exist at once */
-#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)
 #define MAX_CALL_FRAMES 8
+/* Maximum number of register states that can exist at once */
+#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)

this is overly pessimistic, the total number of stack slots doesn't change no matter how many call frames we have, it would be better to define this as:

Quoted 4 lines

#define BPF_ID_MAP_SIZE (MAX_BPF_REG * MAX_CALL_FRAMES + MAX_BPF_STACK / BPF_REG_SIZE)

Unless I missed something.

Current bpf_check() mechanics looks as follows:
- do_check_{subprogs,main}() (indirectly):
- when a pseudo-function is called the call is processed by __check_func_call(), it allocates callee's struct bpf_func_state using kzalloc() and does not update ->stack and ->allocated_stack fields;
- when a stack write is processed by check_mem_access():
- check_stack_access_within_bounds() verifies that offset is within 0..-MAX_BPF_STACK;
- check_stack_write_{fixed,var}_off() calls grow_stack_state() which uses realloc_array() to increase ->stack as necessary;
- update_stack_depth() is used to increase env->subprog_info[...].stack_depth as appropriate;
- check_max_stack_depth() verifies that cumulative stack depth does not exceed MAX_BPF_STACK using env->subprog_info[...].stack_depth values.

This means that during do_check_*() we can have MAX_CALL_FRAMES functions each with a stack of size MAX_BPF_STACK. The following example could be used to verify the above assumptions:

{
        "check_max_depth",
        .insns = {
                BPF_ST_MEM(BPF_DW, BPF_REG_FP, -512, 0),
                BPF_CALL_REL(2),
                BPF_MOV64_IMM(BPF_REG_0, 0),
                BPF_EXIT_INSN(),

                BPF_ST_MEM(BPF_DW, BPF_REG_FP, -512, 0),
                BPF_MOV64_IMM(BPF_REG_0, 0),
                BPF_EXIT_INSN(),
        },
        .result = REJECT,
},

Here is the verifier log that shows that two frames both of size MAX_BPF_STACK slots were present during verification:

# ./test_verifier -vv 1030
#1030/p check_max_depth FAIL
Unexpected error message!
        EXP: (null)
        RES:
func#0 @0
func#1 @4
0: R1=ctx(off=0,imm=0) R10=fp0
0: (7a) *(u64 *)(r10 -512) = 0        ; R10=fp0 fp-512_w=mmmmmmmm
1: (85) call pc+2
caller:
 R10=fp0 fp-512_w=mmmmmmmm
callee:
 frame1: R1=ctx(off=0,imm=0) R10=fp0
4: (7a) *(u64 *)(r10 -512) = 0        ; frame1: R10=fp0 fp-512_w=mmmmmmmm
5: (b7) r0 = 0                        ; frame1: R0_w=0
6: (95) exit
returning from callee:
 frame1: R0_w=0 R1=ctx(off=0,imm=0) R10=fp0 fp-512_w=mmmmmmmm
to caller at 2:
 R0_w=0 R10=fp0 fp-512_w=mmmmmmmm
Quoted 7 lines

from 6 to 2: R0_w=0 R10=fp0 fp-512_w=mmmmmmmm
2: (b7) r0 = 0 ; R0_w=0
3: (95) exit
combined stack size of 2 calls is 1024. Too large
verification time 541 usec
stack depth 512+512

It's all true, but I'm not clear on what point you are trying to make. BPF program did get rejected after using so much stack trace, right? So it should be ok to reduce idmap size.

It's the difference between maintaining 152 (which is already quite overpesimisstic for any real application) vs 600 entries (1216 bytes vs 4800 bytes). On each state equality check call. We can probably just drop that WARN_ON_ONCE(1) in check_ids and reduce the size of idmap, no more changes, right?

Quoted 31 lines
Quoted 30 lines
Quoted 30 lines
include/linux/bpf_verifier.h +0 -0
 struct bpf_verifier_state {
        /* call stack tracking */
        struct bpf_func_state *frame[MAX_CALL_FRAMES];
kernel/bpf/verifier.c +2 -2
index d05c5d0344c6..9188370a7ebe 100644
@@ -13122,7 +13122,6 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat
 {
        int i;
 
-       memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch));
        for (i = 0; i < MAX_BPF_REG; i++)
                if (!regsafe(env, &old->regs[i], &cur->regs[i],
                             env->idmap_scratch))
@@ -13146,6 +13145,8 @@ static bool states_equal(struct bpf_verifier_env *env,
        if (old->curframe != cur->curframe)
                return false;
 
+       memset(env->idmap_scratch, 0, sizeof(env->idmap_scratch));
+
        /* Verification state from speculative execution simulation
         * must never prune a non-speculative execution one.
         */
--

2.34.1

#4 lore raw

Re: [PATCH bpf-next 1/7] bpf: regsafe() must not skip check_ids()

In reply to Eduard Zingerman
Quoted 168 lines · Eduard Zingerman
Quoted 112 lines · Andrii Nakryiko
Quoted 111 lines · Eduard Zingerman

The verifier.c:regsafe() has the following shortcut:

        equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
        ...
        if (equal)
                return true;

Which is executed regardless old register type. This is incorrect for register types that might have an ID checked by check_ids(), namely:
- PTR_TO_MAP_KEY
- PTR_TO_MAP_VALUE
- PTR_TO_PACKET_META
- PTR_TO_PACKET

The following pattern could be used to exploit this:

  0: r9 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=1.
  1: r8 = map_lookup_elem(...)  ; Returns PTR_TO_MAP_VALUE_OR_NULL id=2.
  2: r7 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  3: r6 = ktime_get_ns()        ; Unbound SCALAR_VALUE.
  4: if r6 > r7 goto +1         ; No new information about the state

; is derived from this check, thus ; produced verifier states differ only ; in 'insn_idx'.
5: r9 = r8 ; Optionally make r9.id == r8.id.
--- checkpoint --- ; Assume is_state_visisted() creates a
; checkpoint here.
6: if r9 == 0 goto <exit> ; Nullness info is propagated to all
; registers with matching ID.
7: r1 = *(u64 *) r8 ; Not always safe.

Verifier first visits path 1-7 where r8 is verified to be not null at (6). Later the jump from 4 to 6 is examined. The checkpoint for (6) looks as follows:
R8_rD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9_rwD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R10=fp0

The current state is:
R0=... R6=... R7=... fp-8=... R8=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9=map_value_or_null(id=1,off=0,ks=4,vs=8,imm=0) R10=fp0

Note that R8 states are byte-to-byte identical, so regsafe() would exit early and skip call to check_ids(), thus ID mapping 2->2 will not be added to 'idmap'. Next, states for R9 are compared: these are not identical and check_ids() is executed, but 'idmap' is empty, so check_ids() adds mapping 2->1 to 'idmap' and returns success.

This commit pushes the 'equal' down to register types that don't need check_ids().

---
 kernel/bpf/verifier.c | 29 ++++++++---------------------
 1 file changed, 8 insertions(+), 21 deletions(-)
kernel/bpf/verifier.c +7 -21
index 3194e9d9e4e4..d05c5d0344c6 100644
@@ -12926,15 +12926,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 
        equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
 
-       if (rold->type == PTR_TO_STACK)
-               /* two stack pointers are equal only if they're pointing to
-                * the same stack frame, since fp-8 in foo != fp-8 in bar
-                */
-               return equal && rold->frameno == rcur->frameno;
-
-       if (equal)
-               return true;
-
        if (rold->type == NOT_INIT)
                /* explored state can't have used this */
                return true;
@@ -12942,6 +12933,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
                return false;
        switch (base_type(rold->type)) {
        case SCALAR_VALUE:
+               if (equal)
+                       return true;
                if (env->explore_alu_limits)
                        return false;
                if (rcur->type == SCALAR_VALUE) {
@@ -13012,20 +13005,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
                /* new val must satisfy old val knowledge */
                return range_within(rold, rcur) &&
                       tnum_in(rold->var_off, rcur->var_off);
-       case PTR_TO_CTX:
-       case CONST_PTR_TO_MAP:
-       case PTR_TO_PACKET_END:
-       case PTR_TO_FLOW_KEYS:
-       case PTR_TO_SOCKET:
-       case PTR_TO_SOCK_COMMON:
-       case PTR_TO_TCP_SOCK:
-       case PTR_TO_XDP_SOCK:
-               /* Only valid matches are exact, which memcmp() above
-                * would have accepted
+       case PTR_TO_STACK:
+               /* two stack pointers are equal only if they're pointing to
+                * the same stack frame, since fp-8 in foo != fp-8 in bar
                 */
+               return equal && rold->frameno == rcur->frameno;
        default:
-               /* Don't know what's going on, just say it's not safe */
-               return false;
+               /* Only valid matches are exact, which memcmp() */
Quoted 8 lines

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

Quoted 1 line
kernel/bpf/verifier.c +1 -0
+               return equal;

Is it safe to assume this for any possible register type? Wouldn't register types that use id and/or ref_obj_id need extra checks here? I think preexisting default was a safer approach, in which if we forgot to explicitly add support for some new or updated register type, the worst thing is that for that *new* register we'd have suboptimal verification performance, but not safety concerns.

Well, I don't think that this commit changes regsafe() behavior in this regard. Here is how the code was structured before this commit:

static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
struct bpf_reg_state *rcur, struct bpf_id_pair *idmap)

{
        bool equal;

        if (!(rold->live & REG_LIVE_READ))
                return true;
        equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
        if (rold->type == PTR_TO_STACK)
                return equal && rold->frameno == rcur->frameno;
--->    if (equal)
                return true;
        if (rold->type == NOT_INIT)
                return true;
        if (rcur->type == NOT_INIT)
                return false;
        switch (base_type(rold->type)) {
        case SCALAR_VALUE:
                ... it's own logic, always returns ...
        case PTR_TO_MAP_KEY:
        case PTR_TO_MAP_VALUE:
                ... it's own logic, always returns ...
        case PTR_TO_PACKET_META:
        case PTR_TO_PACKET:
                ... it's own logic, always returns ...
        case PTR_TO_CTX:
        case CONST_PTR_TO_MAP:
        case PTR_TO_PACKET_END:
        case PTR_TO_FLOW_KEYS:
        case PTR_TO_SOCKET:
        case PTR_TO_SOCK_COMMON:
        case PTR_TO_TCP_SOCK:
        case PTR_TO_XDP_SOCK:
        default:
                return false;
        }

        /* Shouldn't get here; if we do, say it's not safe */
        WARN_ON_ONCE(1);
        return false;
}
Quoted 4 lines

So the "safe if byte-to-byte equal" behavior was present already. I can add an explicit list of types to the "return equal;" branch and add a default "return false;" branch if you think that it is more fool-proof.

Sorry, I didn't claim you made it worse. But given we are refactoring this piece of code, let's make it more "safe-by-default".

So yeah, I think an explicit list of all the recognized register types would be better, IMO.

Quoted 10 lines
Quoted 9 lines
Quoted 9 lines
kernel/bpf/verifier.c +0 -1
        }
 
        /* Shouldn't get here; if we do, say it's not safe */
--

2.34.1