[PATCH bpf-next 0/7] stricter register ID checking in regsafe()

[PATCH bpf-next 0/7] stricter register ID checking in regsafe()

[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.

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/20221111202719.982118-1-memxor@gmail.com/
[2] https://lore.kernel.org/bpf/20221128163442.280187-2-eddyz87@gmail.com/

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

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

[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().

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

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3194e9d9e4e4..d05c5d0344c6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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 */
-- 
2.34.1

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

[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.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../bpf/verifier/direct_packet_access.c       | 54 +++++++++++++++++++
 .../selftests/bpf/verifier/value_or_null.c    | 49 +++++++++++++++++
 2 files changed, 103 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/direct_packet_access.c b/tools/testing/selftests/bpf/verifier/direct_packet_access.c
index 11acd1855acf..dce2e28aeb43 100644
--- a/tools/testing/selftests/bpf/verifier/direct_packet_access.c
+++ b/tools/testing/selftests/bpf/verifier/direct_packet_access.c
@@ -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,
+},
diff --git a/tools/testing/selftests/bpf/verifier/value_or_null.c b/tools/testing/selftests/bpf/verifier/value_or_null.c
index 3ecb70a3d939..52a8bca14f03 100644
--- a/tools/testing/selftests/bpf/verifier/value_or_null.c
+++ b/tools/testing/selftests/bpf/verifier/value_or_null.c
@@ -169,3 +169,52 @@
 	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
 	.result = ACCEPT,
 },
+{
+	"MAP_VALUE_OR_NULL check_ids() in regsafe()",
+	.insns = {
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+	/* r9 = map_lookup_elem(...) */
+	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_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, -8),
+	BPF_LD_MAP_FD(BPF_REG_1,
+		      0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	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 +1    ; no new information about the state is derived from
+	 *                       ; this check, thus produced verifier states differ
+	 *                       ; only in 'insn_idx'
+	 * r9 = r8               ; optionally share ID between r9 and r8
+	 */
+	BPF_JMP_REG(BPF_JGT, BPF_REG_6, BPF_REG_7, 1),
+	BPF_MOV64_REG(BPF_REG_9, BPF_REG_8),
+	/* if r9 == 0 goto <exit> */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_9, 0, 1),
+	/* read map value via r8, this is not always
+	 * safe because r8 might be not equal to r9.
+	 */
+	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

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

[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/

Suggested-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/bpf_verifier.h | 4 ++--
 kernel/bpf/verifier.c        | 3 ++-
 2 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 70d06a99f0b8..c1f769515beb 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -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];
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d05c5d0344c6..9188370a7ebe 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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

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

[Eduard Zingerman]

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

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

diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
index 3193915c5ee6..bcd15b26dcee 100644
--- a/tools/testing/selftests/bpf/verifier/calls.c
+++ b/tools/testing/selftests/bpf/verifier/calls.c
@@ -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

[PATCH bpf-next 5/7] bpf: use check_ids() for active_lock comparison

[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/20221111202719.982118-1-memxor@gmail.com/

Reported-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Suggested-by: Edward Cree <ecree.xilinx@gmail.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9188370a7ebe..27caea773491 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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)
-- 
2.34.1

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

[Eduard Zingerman]

From: Kumar Kartikeya Dwivedi <memxor@gmail.com>

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.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 .../selftests/bpf/verifier/spin_lock.c        | 39 +++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/spin_lock.c b/tools/testing/selftests/bpf/verifier/spin_lock.c
index 781621facae4..0a8dcfc37fc6 100644
--- a/tools/testing/selftests/bpf/verifier/spin_lock.c
+++ b/tools/testing/selftests/bpf/verifier/spin_lock.c
@@ -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,
+},
-- 
2.34.1

[PATCH bpf-next 7/7] selftests/bpf: test case for relaxed prunning of active_lock.id

[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.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../selftests/bpf/verifier/spin_lock.c        | 75 +++++++++++++++++++
 1 file changed, 75 insertions(+)

diff --git a/tools/testing/selftests/bpf/verifier/spin_lock.c b/tools/testing/selftests/bpf/verifier/spin_lock.c
index 0a8dcfc37fc6..eaf114f07e2e 100644
--- a/tools/testing/selftests/bpf/verifier/spin_lock.c
+++ b/tools/testing/selftests/bpf/verifier/spin_lock.c
@@ -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,
+},
-- 
2.34.1

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

[Alexei Starovoitov]

On Fri, Dec 09, 2022 at 03:57:32PM +0200, Eduard Zingerman wrote:
> From: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> 
> 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.
> 
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

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

Re: [PATCH bpf-next 0/7] stricter register ID checking in regsafe()

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

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!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

Re: [PATCH bpf-next 0/7] stricter register ID checking in regsafe()

[Andrii Nakryiko]

On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> 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.
>
> 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!

> [1] https://lore.kernel.org/bpf/20221111202719.982118-1-memxor@gmail.com/
> [2] https://lore.kernel.org/bpf/20221128163442.280187-2-eddyz87@gmail.com/
>
> 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
>

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

[Andrii Nakryiko]

On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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().
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c | 29 ++++++++---------------------
>  1 file changed, 8 insertions(+), 21 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 3194e9d9e4e4..d05c5d0344c6 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -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;

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.


>         }
>
>         /* Shouldn't get here; if we do, say it's not safe */
> --
> 2.34.1
>

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

[Andrii Nakryiko]

On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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/
>
> Suggested-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  include/linux/bpf_verifier.h | 4 ++--
>  kernel/bpf/verifier.c        | 3 ++-
>  2 files changed, 4 insertions(+), 3 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 70d06a99f0b8..c1f769515beb 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -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.



>  struct bpf_verifier_state {
>         /* call stack tracking */
>         struct bpf_func_state *frame[MAX_CALL_FRAMES];
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index d05c5d0344c6..9188370a7ebe 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -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
>

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

[Andrii Nakryiko]

On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> A test case that would erroneously pass verification if
> verifier.c:states_equal() maintains separate register ID mappings for
> call frames.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---

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=*


>  tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++
>  1 file changed, 82 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
> index 3193915c5ee6..bcd15b26dcee 100644
> --- a/tools/testing/selftests/bpf/verifier/calls.c
> +++ b/tools/testing/selftests/bpf/verifier/calls.c
> @@ -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
>

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

[Eduard Zingerman]

On Tue, 2022-12-13 at 16:35 -0800, Andrii Nakryiko wrote:
> On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > 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().
> > 
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> >  kernel/bpf/verifier.c | 29 ++++++++---------------------
> >  1 file changed, 8 insertions(+), 21 deletions(-)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 3194e9d9e4e4..d05c5d0344c6 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -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;
> 
> 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.

> 
> 
> >         }
> > 
> >         /* Shouldn't get here; if we do, say it's not safe */
> > --
> > 2.34.1
> > 

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

[Eduard Zingerman]

On Tue, 2022-12-13 at 16:35 -0800, Andrii Nakryiko wrote:
> On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > 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/
> > 
> > Suggested-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> >  include/linux/bpf_verifier.h | 4 ++--
> >  kernel/bpf/verifier.c        | 3 ++-
> >  2 files changed, 4 insertions(+), 3 deletions(-)
> > 
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index 70d06a99f0b8..c1f769515beb 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -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.

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

> 
> 
> 
> >  struct bpf_verifier_state {
> >         /* call stack tracking */
> >         struct bpf_func_state *frame[MAX_CALL_FRAMES];
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index d05c5d0344c6..9188370a7ebe 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -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
> > 

Re: [PATCH bpf-next 0/7] stricter register ID checking in regsafe()

[Eduard Zingerman]

On Tue, 2022-12-13 at 16:34 -0800, Andrii Nakryiko wrote:
> On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> 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.
> > 
> > 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
> ;).

Makes sense, I'll work on it.

> 
> Anyways, great work, thanks!

Thank you.

> 
> > [1] https://lore.kernel.org/bpf/20221111202719.982118-1-memxor@gmail.com/
> > [2] https://lore.kernel.org/bpf/20221128163442.280187-2-eddyz87@gmail.com/
> > 
> > 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
> > 

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

[Eduard Zingerman]

On Tue, 2022-12-13 at 16:35 -0800, Andrii Nakryiko wrote:
> On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > A test case that would erroneously pass verification if
> > verifier.c:states_equal() maintains separate register ID mappings for
> > call frames.
> > 
> > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> 
> 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=*
> 
> 

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.


> >  tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++
> >  1 file changed, 82 insertions(+)
> > 
> > diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
> > index 3193915c5ee6..bcd15b26dcee 100644
> > --- a/tools/testing/selftests/bpf/verifier/calls.c
> > +++ b/tools/testing/selftests/bpf/verifier/calls.c
> > @@ -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
> > 

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

[Andrii Nakryiko]

On Wed, Dec 14, 2022 at 8:38 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2022-12-13 at 16:35 -0800, Andrii Nakryiko wrote:
> > On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > A test case that would erroneously pass verification if
> > > verifier.c:states_equal() maintains separate register ID mappings for
> > > call frames.
> > >
> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > ---
> >
> > 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=*
> >
> >
>
> 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.

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.

>
>
> > >  tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++
> > >  1 file changed, 82 insertions(+)
> > >
> > > diff --git a/tools/testing/selftests/bpf/verifier/calls.c b/tools/testing/selftests/bpf/verifier/calls.c
> > > index 3193915c5ee6..bcd15b26dcee 100644
> > > --- a/tools/testing/selftests/bpf/verifier/calls.c
> > > +++ b/tools/testing/selftests/bpf/verifier/calls.c
> > > @@ -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
> > >
>

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

[Andrii Nakryiko]

On Wed, Dec 14, 2022 at 7:33 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2022-12-13 at 16:35 -0800, Andrii Nakryiko wrote:
> > On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > 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/
> > >
> > > Suggested-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > ---
> > >  include/linux/bpf_verifier.h | 4 ++--
> > >  kernel/bpf/verifier.c        | 3 ++-
> > >  2 files changed, 4 insertions(+), 3 deletions(-)
> > >
> > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > > index 70d06a99f0b8..c1f769515beb 100644
> > > --- a/include/linux/bpf_verifier.h
> > > +++ b/include/linux/bpf_verifier.h
> > > @@ -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.
>
> 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
>

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?

> >
> >
> >
> > >  struct bpf_verifier_state {
> > >         /* call stack tracking */
> > >         struct bpf_func_state *frame[MAX_CALL_FRAMES];
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index d05c5d0344c6..9188370a7ebe 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -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
> > >
>

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

[Andrii Nakryiko]

On Wed, Dec 14, 2022 at 5:26 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2022-12-13 at 16:35 -0800, Andrii Nakryiko wrote:
> > On Fri, Dec 9, 2022 at 5:58 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > 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().
> > >
> > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> > > ---
> > >  kernel/bpf/verifier.c | 29 ++++++++---------------------
> > >  1 file changed, 8 insertions(+), 21 deletions(-)
> > >
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index 3194e9d9e4e4..d05c5d0344c6 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -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;
> >
> > 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.

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.


>
> >
> >
> > >         }
> > >
> > >         /* Shouldn't get here; if we do, say it's not safe */
> > > --
> > > 2.34.1
> > >
>