From 7c884339bbff80250bfc11d56b5cf48640e6ebdb Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Fri, 9 Dec 2022 15:57:27 +0200 Subject: bpf: regsafe() must not skip check_ids() The verifier.c:regsafe() has the following shortcut: equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0; ... if (equal) return true; Which is executed regardless old register type. This is incorrect for register types that might have an ID checked by check_ids(), namely: - PTR_TO_MAP_KEY - PTR_TO_MAP_VALUE - PTR_TO_PACKET_META - PTR_TO_PACKET The following pattern could be used to exploit this: 0: r9 = map_lookup_elem(...) ; Returns PTR_TO_MAP_VALUE_OR_NULL id=1. 1: r8 = map_lookup_elem(...) ; Returns PTR_TO_MAP_VALUE_OR_NULL id=2. 2: r7 = ktime_get_ns() ; Unbound SCALAR_VALUE. 3: r6 = ktime_get_ns() ; Unbound SCALAR_VALUE. 4: if r6 > r7 goto +1 ; No new information about the state ; is derived from this check, thus ; produced verifier states differ only ; in 'insn_idx'. 5: r9 = r8 ; Optionally make r9.id == r8.id. --- checkpoint --- ; Assume is_state_visisted() creates a ; checkpoint here. 6: if r9 == 0 goto ; 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 Link: https://lore.kernel.org/r/20221209135733.28851-2-eddyz87@gmail.com Signed-off-by: Alexei Starovoitov --- 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 9791788071d5..97645f767354 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13064,15 +13064,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; @@ -13080,6 +13071,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) { @@ -13150,20 +13143,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 */ -- cgit From cb578c1c9cf60275f258b5af7929c2a54a188f66 Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Fri, 9 Dec 2022 15:57:28 +0200 Subject: selftests/bpf: test cases for regsafe() bug skipping check_id() 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 Link: https://lore.kernel.org/r/20221209135733.28851-3-eddyz87@gmail.com Signed-off-by: Alexei Starovoitov --- .../selftests/bpf/verifier/direct_packet_access.c | 54 ++++++++++++++++++++++ .../testing/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 */ + 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, +}, -- cgit From 5dd9cdbc9dec3e99b19e483767e247d15ca8cc0d Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Fri, 9 Dec 2022 15:57:29 +0200 Subject: bpf: states_equal() must build idmap for all function frames 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 Signed-off-by: Eduard Zingerman Link: https://lore.kernel.org/r/20221209135733.28851-4-eddyz87@gmail.com Signed-off-by: Alexei Starovoitov --- 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 df0cb825e0e3..53d175cbaa02 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 97645f767354..00c8e0a28203 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13260,7 +13260,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)) @@ -13284,6 +13283,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. */ -- cgit From 7d05794330877986f605c1618534d7478030f5b8 Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Fri, 9 Dec 2022 15:57:30 +0200 Subject: selftests/bpf: verify states_equal() maintains idmap across all frames 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 Link: https://lore.kernel.org/r/20221209135733.28851-5-eddyz87@gmail.com Signed-off-by: Alexei Starovoitov --- 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 babcec123251..9d993926bf0e 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 + */ + 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, +}, -- cgit From 4ea2bb158bec2fe171e7e07c033dcf208d86e274 Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Fri, 9 Dec 2022 15:57:31 +0200 Subject: bpf: use check_ids() for active_lock comparison 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 Suggested-by: Edward Cree Signed-off-by: Eduard Zingerman Link: https://lore.kernel.org/r/20221209135733.28851-6-eddyz87@gmail.com Signed-off-by: Alexei Starovoitov --- 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 00c8e0a28203..a5255a0dcbb6 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13119,7 +13119,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) @@ -13291,8 +13292,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) -- cgit From 2026f2062df860e5d282ffd4962ea5d5ed53dc51 Mon Sep 17 00:00:00 2001 From: Kumar Kartikeya Dwivedi Date: Fri, 9 Dec 2022 15:57:32 +0200 Subject: selftests/bpf: Add pruning test case for bpf_spin_lock 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 Signed-off-by: Eduard Zingerman Link: https://lore.kernel.org/r/20221209135733.28851-7-eddyz87@gmail.com Signed-off-by: Alexei Starovoitov --- tools/testing/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, +}, -- cgit From efd6286ff74a2fa2b45ed070d344cc0822b8ea6e Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Fri, 9 Dec 2022 15:57:33 +0200 Subject: selftests/bpf: test case for relaxed prunning of active_lock.id 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 Link: https://lore.kernel.org/r/20221209135733.28851-8-eddyz87@gmail.com Signed-off-by: Alexei Starovoitov --- tools/testing/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, +}, -- cgit