stricter register ID checking in regsafe()
Subsystems (4)
Eduard Zingerman
maintainercover stricter register ID checking in regsafe()
This patch-set consists of a series of bug fixes for register ID tracking in verifier.c:states_equal()/regsafe() functions:
- for registers of type PTR_TO_MAP_{KEY,VALUE}, PTR_TO_PACKET[_META] the regsafe() should call check_ids() even if registers are byte-to-byte equal;
- states_equal() must maintain idmap that covers all function frames in the state because functions like mark_ptr_or_null_regs() operate on all registers in the state;
- regsafe() must compare spin lock ids for PTR_TO_MAP_VALUE registers.
The last point covers issue reported by Kumar Kartikeya Dwivedi in [1], I borrowed the test commit from there.
Note, that there is also an issue with register id tracking for scalars described here [2], it would be addressed separately.
[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/
Eduard Zingerman (6):
bpf: regsafe() must not skip check_ids()
selftests/bpf: test cases for regsafe() bug skipping check_id()
bpf: states_equal() must build idmap for all function frames selftests/bpf: verify states_equal() maintains idmap across all frames
bpf: use check_ids() for active_lock comparison selftests/bpf: test case for relaxed prunning of active_lock.id
Kumar Kartikeya Dwivedi (1):
selftests/bpf: Add pruning test case for bpf_spin_lock
include/linux/bpf_verifier.h | 4 +- kernel/bpf/verifier.c | 48 ++++---- tools/testing/selftests/bpf/verifier/calls.c | 82 +++++++++++++ .../bpf/verifier/direct_packet_access.c | 54 +++++++++ .../selftests/bpf/verifier/spin_lock.c | 114 ++++++++++++++++++ .../selftests/bpf/verifier/value_or_null.c | 49 ++++++++ 6 files changed, 324 insertions(+), 27 deletions(-)
Signature · 1 line
2.34.1
Eduard Zingerman
maintainerPATCH 1/7 bpf: regsafe() must not skip check_ids()
The verifier.c:regsafe() has the following shortcut:
equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0; ... if (equal) return true;
Which is executed regardless old register type. This is incorrect for register types that might have an ID checked by check_ids(), namely:
- PTR_TO_MAP_KEY
- PTR_TO_MAP_VALUE
- PTR_TO_PACKET_META
- PTR_TO_PACKET
The following pattern could be used to exploit this:
0: r9 = map_lookup_elem(...) ; Returns PTR_TO_MAP_VALUE_OR_NULL id=1. 1: r8 = map_lookup_elem(...) ; Returns PTR_TO_MAP_VALUE_OR_NULL id=2. 2: r7 = ktime_get_ns() ; Unbound SCALAR_VALUE. 3: r6 = ktime_get_ns() ; Unbound SCALAR_VALUE. 4: if r6 > r7 goto +1 ; No new information about the state
; is derived from this check, thus ; produced verifier states differ only ; in 'insn_idx'.
5: r9 = r8 ; Optionally make r9.id == r8.id.
--- checkpoint --- ; Assume is_state_visisted() creates a
; checkpoint here.
6: if r9 == 0 goto <exit> ; Nullness info is propagated to all
; registers with matching ID.
7: r1 = *(u64 *) r8 ; Not always safe.
Verifier first visits path 1-7 where r8 is verified to be not null at (6). Later the jump from 4 to 6 is examined. The checkpoint for (6) looks as follows:
R8_rD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9_rwD=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R10=fp0
The current state is:
R0=... R6=... R7=... fp-8=... R8=map_value_or_null(id=2,off=0,ks=4,vs=8,imm=0) R9=map_value_or_null(id=1,off=0,ks=4,vs=8,imm=0) R10=fp0
Note that R8 states are byte-to-byte identical, so regsafe() would exit early and skip call to check_ids(), thus ID mapping 2->2 will not be added to 'idmap'. Next, states for R9 are compared: these are not identical and check_ids() is executed, but 'idmap' is empty, so check_ids() adds mapping 2->1 to 'idmap' and returns success.
This commit pushes the 'equal' down to register types that don't need check_ids().
--- kernel/bpf/verifier.c | 29 ++++++++--------------------- 1 file changed, 8 insertions(+), 21 deletions(-)
kernel/bpf/verifier.c +8 -21
@@ -12926,15 +12926,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, equal =memcmp (rold, rcur, offsetof(struct bpf_reg_state , parent)) ==0 ; -if (rold->type ==PTR_TO_STACK ) -/* two stack pointers are equal only if they're pointing to -* the same stack frame, since fp-8 in foo != fp-8 in bar -*/ -return equal && rold->frameno == rcur->frameno; - -if (equal) -return true; -if (rold->type ==NOT_INIT )/* explored state can't have used this */ return true;
@@ -12942,6 +12933,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,return false;switch (base_type (rold->type)) {case SCALAR_VALUE : +if (equal) +return true;if (env->explore_alu_limits)return false;if (rcur->type ==SCALAR_VALUE ) {
@@ -13012,20 +13005,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* new val must satisfy old val knowledge */ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off); -case PTR_TO_CTX : -case CONST_PTR_TO_MAP : -case PTR_TO_PACKET_END : -case PTR_TO_FLOW_KEYS : -case PTR_TO_SOCKET : -case PTR_TO_SOCK_COMMON : -case PTR_TO_TCP_SOCK : -case PTR_TO_XDP_SOCK : -/* Only valid matches are exact, which memcmp() above -* would have accepted +case PTR_TO_STACK : +/* two stack pointers are equal only if they're pointing to +* the same stack frame, since fp-8 in foo != fp-8 in bar */ +return equal && rold->frameno == rcur->frameno;default : -/* Don't know what's going on, just say it's not safe */ -return false; +/* Only valid matches are exact, which memcmp() */ +return equal; }/* Shouldn't get here; if we do, say it's not safe */
Signature · 1 line
2.34.1
Eduard Zingerman
maintainerPATCH 2/7 selftests/bpf: test cases for regsafe() bug skipping check_id()
In reply to Eduard ZingermanUnder certain conditions it was possible for verifier.c:regsafe() to skip check_id() call. This commit adds negative test cases previously errorneously accepted as safe.
--- .../bpf/verifier/direct_packet_access.c | 54 +++++++++++++++++++ .../selftests/bpf/verifier/value_or_null.c | 49 +++++++++++++++++ 2 files changed, 103 insertions(+)
tools/testing/selftests/bpf/verifier/direct_packet_access.c +54 -0
@@ -654,3 +654,57 @@ .result = ACCEPT, .prog_type = BPF_PROG_TYPE_SCHED_CLS, }, +{ + "direct packet access: test30 (check_id() in regsafe(), bad access)", + .insns = { +/* r9 = ctx */ +BPF_MOV64_REG (BPF_REG_9 ,BPF_REG_1 ), +/* r7 = ktime_get_ns() */ +BPF_EMIT_CALL (BPF_FUNC_ktime_get_ns), +BPF_MOV64_REG (BPF_REG_7 ,BPF_REG_0 ), +/* r6 = ktime_get_ns() */ +BPF_EMIT_CALL (BPF_FUNC_ktime_get_ns), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +/* r2 = ctx->data +* r3 = ctx->data +* r4 = ctx->data_end +*/ +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_9 , offsetof(struct __sk_buff , data)), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_9 , offsetof(struct __sk_buff , data)), +BPF_LDX_MEM (BPF_W ,BPF_REG_4 ,BPF_REG_9 , offsetof(struct __sk_buff , data_end)), +/* if r6 > 100 goto exit +* if r7 > 100 goto exit +*/ +BPF_JMP_IMM (BPF_JGT ,BPF_REG_6 ,100 ,9 ), +BPF_JMP_IMM (BPF_JGT ,BPF_REG_7 ,100 ,8 ), +/* r2 += r6 ; this forces assignment of ID to r2 +* r2 += 1 ; get some fixed off for r2 +* r3 += r7 ; this forces assignment of ID to r3 +* r3 += 1 ; get some fixed off for r3 +*/ +BPF_ALU64_REG (BPF_ADD ,BPF_REG_2 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,1 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_3 ,BPF_REG_7 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_3 ,1 ), +/* if r6 > r7 goto +1 ; no new information about the state is derived from +* ; this check, thus produced verifier states differ +* ; only in 'insn_idx' +* r2 = r3 ; optionally share ID between r2 and r3 +*/ +BPF_JMP_REG (BPF_JNE ,BPF_REG_6 ,BPF_REG_7 ,1 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_3 ), +/* if r3 > ctx->data_end goto exit */ +BPF_JMP_REG (BPF_JGT ,BPF_REG_3 ,BPF_REG_4 ,1 ), +/* r5 = *(u8 *) (r2 - 1) ; access packet memory using r2, +* ; this is not always safe +*/ +BPF_LDX_MEM (BPF_B ,BPF_REG_5 ,BPF_REG_2 ,-1 ), +/* exit(0) */ +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .flags =BPF_F_TEST_STATE_FREQ , + .result = REJECT, + .errstr = "invalid access to packet, off=0 size=1, R2", + .prog_type = BPF_PROG_TYPE_SCHED_CLS, +},
tools/testing/selftests/bpf/verifier/value_or_null.c +49 -0
52 lines not on this page · raw message
Signature · 1 line
2.34.1
Eduard Zingerman
maintainerPATCH 3/7 bpf: states_equal() must build idmap for all function frames
In reply to Eduard Zingermanverifier.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
exitfoo:
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] != 08: r8 = *r8 ; (a) r8 == &frame[0].fp[-32]
; (b) r8 == &frame[0].fp[-32]
9: r0 = *r8 ; (a) safe
; (b) unsafe
exit:
10: exit
While processing call to foo() verifier considers the following execution paths:
(a) 0-10
(b) 0-4,6-10
(There is also path 0-7,10 but it is not interesting for the issue at
hand. (a) is verified first.)
Suppose that checkpoint is created at (6) when path (a) is verified, next path (b) is verified and (6) is reached.
If states_equal() maintains separate 'idmap' for each frame the mapping at (6) for frame[1] would be empty and regsafe(r9)::check_ids() would add a pair 2->1 and return true, which is an error.
If states_equal() maintains single 'idmap' for all frames the mapping at (6) would be { 1->1, 2->2 } and regsafe(r9)::check_ids() would return false when trying to add a pair 2->1.
This issue was suggested in the following discussion:
https://lore.kernel.org/bpf/CAEf4BzbFB5g4oUfyxk9rHy-PJSLQ3h8q9mV=rVoXfr_JVm8+1Q@mail.gmail.com/
--- include/linux/bpf_verifier.h | 4 ++-- kernel/bpf/verifier.c | 3 ++- 2 files changed, 4 insertions(+), 3 deletions(-)
include/linux/bpf_verifier.h +2 -2
@@ -273,9 +273,9 @@ struct bpf_id_pair {u32 cur; }; -/* Maximum number of register states that can exist at once */ -#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)#define MAX_CALL_FRAMES 8 +/* Maximum number of register states that can exist at once */ +#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)struct bpf_verifier_state {/* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES ];
kernel/bpf/verifier.c +2 -1
@@ -13122,7 +13122,6 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat {int i; -memset (env->idmap_scratch,0 ,sizeof (env->idmap_scratch));for (i =0 ; i <MAX_BPF_REG ; i++)if (!regsafe (env, &old->regs[i], &cur->regs[i], env->idmap_scratch))
@@ -13146,6 +13145,8 @@ static bool states_equal(struct bpf_verifier_env *env,if (old->curframe != cur->curframe)return false; +memset (env->idmap_scratch,0 ,sizeof (env->idmap_scratch)); +/* Verification state from speculative execution simulation * must never prune a non-speculative execution one. */
Signature · 1 line
2.34.1
Eduard Zingerman
maintainerPATCH 4/7 selftests/bpf: verify states_equal() maintains idmap across all frames
In reply to Eduard ZingermanA test case that would erroneously pass verification if verifier.c:states_equal() maintains separate register ID mappings for call frames.
--- tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++ 1 file changed, 82 insertions(+)
tools/testing/selftests/bpf/verifier/calls.c +82 -0
@@ -2305,3 +2305,85 @@ .errstr = "!read_ok", .result = REJECT, }, +/* Make sure that verifier.c:states_equal() considers IDs from all +* frames when building 'idmap' for check_ids(). +*/ +{ + "calls: check_ids() across call boundary", + .insns = { +/* Function main() */ +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +/* fp[-24] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */ +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 , +0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_STX_MEM (BPF_DW ,BPF_REG_FP ,BPF_REG_0 ,-24 ), +/* fp[-32] = map_lookup_elem(...) ; get a MAP_VALUE_PTR_OR_NULL with some ID */ +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_LD_MAP_FD (BPF_REG_1 , +0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_STX_MEM (BPF_DW ,BPF_REG_FP ,BPF_REG_0 ,-32 ), +/* call foo(&fp[-24], &fp[-32]) ; both arguments have IDs in the current +* ; stack frame +*/ +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_FP ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,-24 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_FP ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-32 ), +BPF_CALL_REL (2 ), +/* exit 0 */ +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +/* Function foo() +* +* r9 = &frame[0].fp[-24] ; save arguments in the callee saved registers, +* r8 = &frame[0].fp[-32] ; arguments are pointers to pointers to map value +*/ +BPF_MOV64_REG (BPF_REG_9 ,BPF_REG_1 ), +BPF_MOV64_REG (BPF_REG_8 ,BPF_REG_2 ), +/* r7 = ktime_get_ns() */ +BPF_EMIT_CALL (BPF_FUNC_ktime_get_ns), +BPF_MOV64_REG (BPF_REG_7 ,BPF_REG_0 ), +/* r6 = ktime_get_ns() */ +BPF_EMIT_CALL (BPF_FUNC_ktime_get_ns), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +/* if r6 > r7 goto +1 ; no new information about the state is derived from +* ; this check, thus produced verifier states differ +* ; only in 'insn_idx' +* r9 = r8 +*/ +BPF_JMP_REG (BPF_JGT ,BPF_REG_6 ,BPF_REG_7 ,1 ), +BPF_MOV64_REG (BPF_REG_9 ,BPF_REG_8 ), +/* r9 = *r9 ; verifier get's to this point via two paths: +* ; (I) one including r9 = r8, verified first; +* ; (II) one excluding r9 = r8, verified next. +* ; After load of *r9 to r9 the frame[0].fp[-24].id == r9.id. +* ; Suppose that checkpoint is created here via path (I). +* ; When verifying via (II) the r9.id must be compared against +* ; frame[0].fp[-24].id, otherwise (I) and (II) would be +* ; incorrectly deemed equivalent. +* if r9 == 0 goto <exit> +*/ +BPF_LDX_MEM (BPF_DW ,BPF_REG_9 ,BPF_REG_9 ,0 ), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_9 ,0 ,1 ), +/* r8 = *r8 ; read map value via r8, this is not safe +* r0 = *r8 ; because r8 might be not equal to r9. +*/ +BPF_LDX_MEM (BPF_DW ,BPF_REG_8 ,BPF_REG_8 ,0 ), +BPF_LDX_MEM (BPF_DW ,BPF_REG_0 ,BPF_REG_8 ,0 ), +/* exit 0 */ +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .flags =BPF_F_TEST_STATE_FREQ , + .fixup_map_hash_8b = { 3, 9 }, + .result = REJECT, + .errstr = "R8 invalid mem access 'map_value_or_null'", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, +},
Signature · 1 line
2.34.1
Eduard Zingerman
maintainerPATCH 6/7 selftests/bpf: Add pruning test case for bpf_spin_lock
In reply to Eduard ZingermanFrom: Kumar Kartikeya Dwivedi <[email protected]>
Test that when reg->id is not same for the same register of type PTR_TO_MAP_VALUE between current and old explored state, we currently return false from regsafe and continue exploring.
Without the fix in prior commit, the test case fails.
--- .../selftests/bpf/verifier/spin_lock.c | 39 +++++++++++++++++++ 1 file changed, 39 insertions(+)
tools/testing/selftests/bpf/verifier/spin_lock.c +39 -0
@@ -331,3 +331,42 @@ .errstr = "inside bpf_spin_lock", .prog_type = BPF_PROG_TYPE_SCHED_CLS, }, +{ + "spin_lock: regsafe compare reg->id for map value", + .insns = { +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_6 ,BPF_REG_6 , offsetof(struct __sk_buff , mark)), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_MOV64_REG (BPF_REG_9 ,BPF_REG_1 ), +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_7 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_9 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_8 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_7 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_spin_lock), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_6 ,0 ,1 ), +BPF_JMP_IMM (BPF_JA ,0 ,0 ,1 ), +BPF_MOV64_REG (BPF_REG_7 ,BPF_REG_8 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_7 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 2 }, + .result = REJECT, + .errstr = "bpf_spin_unlock of different lock", + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .flags = BPF_F_TEST_STATE_FREQ, +},
Signature · 1 line
2.34.1
Eduard Zingerman
maintainerPATCH 5/7 bpf: use check_ids() for active_lock comparison
In reply to Eduard ZingermanAn update for verifier.c:states_equal()/regsafe() to use check_ids() for active spin lock comparisons. This fixes the issue reported by Kumar Kartikeya Dwivedi in [1] using technique suggested by Edward Cree.
W/o this commit the verifier might be tricked to accept the following program working with a map containing spin locks:
0: r9 = map_lookup_elem(...) ; Returns PTR_TO_MAP_VALUE_OR_NULL id=1.
1: r8 = map_lookup_elem(...) ; Returns PTR_TO_MAP_VALUE_OR_NULL id=2.
2: if r9 == 0 goto exit ; r9 -> PTR_TO_MAP_VALUE.
3: if r8 == 0 goto exit ; r8 -> PTR_TO_MAP_VALUE.
4: r7 = ktime_get_ns() ; Unbound SCALAR_VALUE.
5: r6 = ktime_get_ns() ; Unbound SCALAR_VALUE.
6: bpf_spin_lock(r8) ; active_lock.id == 2.
7: if r6 > r7 goto +1 ; No new information about the state
; is derived from this check, thus
; produced verifier states differ only
; in 'insn_idx'.
8: r9 = r8 ; Optionally make r9.id == r8.id.
--- checkpoint --- ; Assume is_state_visisted() creates a
; checkpoint here.
9: bpf_spin_unlock(r9) ; (a,b) active_lock.id == 2.
; (a) r9.id == 2, (b) r9.id == 1.10: exit(0)
Consider two verification paths:
(a) 0-10
(b) 0-7,9-10
The path (a) is verified first. If checkpoint is created at (8) the (b) would assume that (8) is safe because regsafe() does not compare register ids for registers of type PTR_TO_MAP_VALUE.
[1] https://lore.kernel.org/bpf/[email protected]/
--- kernel/bpf/verifier.c | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +13 -3
@@ -12981,7 +12981,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,*/ return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 &&range_within (rold, rcur) && -tnum_in (rold->var_off, rcur->var_off); +tnum_in (rold->var_off, rcur->var_off) && +check_ids (rold->id, rcur->id, idmap);case PTR_TO_PACKET_META :case PTR_TO_PACKET :if (rcur->type != rold->type)
@@ -13153,8 +13154,17 @@ static bool states_equal(struct bpf_verifier_env *env,if (old->speculative && !cur->speculative)return false; -if (old->active_lock.ptr != cur->active_lock.ptr || - old->active_lock.id != cur->active_lock.id) +if (old->active_lock.ptr != cur->active_lock.ptr) +return false; + +/* Old and cur active_lock's have to be either both present +* or both absent. +*/ +if (!!old->active_lock.id != !!cur->active_lock.id) +return false; + +if (old->active_lock.id && + !check_ids (old->active_lock.id, cur->active_lock.id, env->idmap_scratch))return false;if (old->active_rcu_lock != cur->active_rcu_lock)
Signature · 1 line
2.34.1
Eduard Zingerman
maintainerPATCH 7/7 selftests/bpf: test case for relaxed prunning of active_lock.id
In reply to Eduard ZingermanCheck that verifier.c:states_equal() uses check_ids() to match consistent active_lock/map_value configurations. This allows to prune states with active spin locks even if numerical values of active_lock ids do not match across compared states.
--- .../selftests/bpf/verifier/spin_lock.c | 75 +++++++++++++++++++ 1 file changed, 75 insertions(+)
tools/testing/selftests/bpf/verifier/spin_lock.c +75 -0
@@ -370,3 +370,78 @@ .prog_type = BPF_PROG_TYPE_SCHED_CLS, .flags = BPF_F_TEST_STATE_FREQ, }, +/* Make sure that regsafe() compares ids for spin lock records using +* check_ids(): +* 1: r9 = map_lookup_elem(...) ; r9.id == 1 +* 2: r8 = map_lookup_elem(...) ; r8.id == 2 +* 3: r7 = ktime_get_ns() +* 4: r6 = ktime_get_ns() +* 5: if r6 > r7 goto <9> +* 6: spin_lock(r8) +* 7: r9 = r8 +* 8: goto <10> +* 9: spin_lock(r9) +* 10: spin_unlock(r9) ; r9.id == 1 || r9.id == 2 and lock is active, +* ; second visit to (10) should be considered safe +* ; if check_ids() is used. +* 11: exit(0) +*/ +{ + "spin_lock: regsafe() check_ids() similar id mappings", + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +/* r9 = map_lookup_elem(...) */ +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 , +0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,24 ), +BPF_MOV64_REG (BPF_REG_9 ,BPF_REG_0 ), +/* r8 = map_lookup_elem(...) */ +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 , +0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,18 ), +BPF_MOV64_REG (BPF_REG_8 ,BPF_REG_0 ), +/* r7 = ktime_get_ns() */ +BPF_EMIT_CALL (BPF_FUNC_ktime_get_ns), +BPF_MOV64_REG (BPF_REG_7 ,BPF_REG_0 ), +/* r6 = ktime_get_ns() */ +BPF_EMIT_CALL (BPF_FUNC_ktime_get_ns), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +/* if r6 > r7 goto +5 ; no new information about the state is derived from +* ; this check, thus produced verifier states differ +* ; only in 'insn_idx' +* spin_lock(r8) +* r9 = r8 +* goto unlock +*/ +BPF_JMP_REG (BPF_JGT ,BPF_REG_6 ,BPF_REG_7 ,5 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_8 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_EMIT_CALL (BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_9 ,BPF_REG_8 ), +BPF_JMP_A (3 ), +/* spin_lock(r9) */ +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_9 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_EMIT_CALL (BPF_FUNC_spin_lock), +/* spin_unlock(r9) */ +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_9 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_EMIT_CALL (BPF_FUNC_spin_unlock), +/* exit(0) */ +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3, 10 }, + .result = VERBOSE_ACCEPT, + .errstr = "28: safe", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + .flags = BPF_F_TEST_STATE_FREQ, +},
Signature · 1 line
2.34.1
Re: [PATCH bpf-next 6/7] selftests/bpf: Add pruning test case for bpf_spin_lock
In reply to Eduard ZingermanQuoted 9 lines · Eduard Zingerman
From: Kumar Kartikeya Dwivedi <[email protected]>
Test that when
reg->idis not same for the same register of typePTR_TO_MAP_VALUEbetween 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 <[email protected]>
Nice set of fixes. Thanks.
When you resend somebody else's patch please add your SOB. This time I did it while applying.
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 11 lines · On Fri, 9 Dec 2022 15:57:26 +0200 you wrote:
This patch-set consists of a series of bug fixes for register ID tracking in verifier.c:states_equal()/regsafe() functions:
- for registers of type PTR_TO_MAP_{KEY,VALUE}, PTR_TO_PACKET[_META] theregsafe()should callcheck_ids()even if registers are byte-to-byte equal;
-states_equal()must maintain idmap that covers all function frames in the state because functions likemark_ptr_or_null_regs()operate on all registers in the state;
-regsafe()must compare spin lock ids forPTR_TO_MAP_VALUEregisters.[...]
Here is the summary with links:
- [bpf-next,1/7] bpf: regsafe() must not skip check_ids()
https://git.kernel.org/bpf/bpf-next/c/7c884339bbff - [bpf-next,2/7] selftests/bpf: test cases for regsafe() bug skipping check_id() https://git.kernel.org/bpf/bpf-next/c/cb578c1c9cf6 - [bpf-next,3/7] bpf: states_equal() must build idmap for all function frames https://git.kernel.org/bpf/bpf-next/c/5dd9cdbc9dec - [bpf-next,4/7] selftests/bpf: verify states_equal() maintains idmap across all frames https://git.kernel.org/bpf/bpf-next/c/7d0579433087 - [bpf-next,5/7] bpf: use check_ids() for active_lock comparison https://git.kernel.org/bpf/bpf-next/c/4ea2bb158bec - [bpf-next,6/7] selftests/bpf: Add pruning test case for bpf_spin_lock https://git.kernel.org/bpf/bpf-next/c/2026f2062df8 - [bpf-next,7/7] selftests/bpf: test case for relaxed prunning of active_lock.id https://git.kernel.org/bpf/bpf-next/c/efd6286ff74a
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html
Quoted 11 lines · Eduard Zingerman
This patch-set consists of a series of bug fixes for register ID tracking in verifier.c:states_equal()/regsafe() functions:
- for registers of type PTR_TO_MAP_{KEY,VALUE}, PTR_TO_PACKET[_META] theregsafe()should callcheck_ids()even if registers are byte-to-byte equal;
-states_equal()must maintain idmap that covers all function frames in the state because functions likemark_ptr_or_null_regs()operate on all registers in the state;
-regsafe()must compare spin lock ids forPTR_TO_MAP_VALUEregisters.
Quoted 5 lines
The last point covers issue reported by Kumar Kartikeya Dwivedi in [1], I borrowed the test commit from there.
Note, that there is also an issue with register id tracking for scalars described here [2], it would be addressed separately.
Awesome set of patches, thanks for working on this! I left a few comments and suggestions, please take a look, and if they do make sense, consider sending follow up patches.
Let's really try to use asm() next time for selftests, though.
It would be awesome to somehow automatically move test_verifier's tests to this test_progs-based embedded assembly way, but that probably takes some Python hackery (awesome project for some curious soul, for sure).
Anyways, back to the point I wanted to make. Given you've clearly thought about all the ID checks a lot, consider checking refsafe() (not regsafe()!) as well. I think we should do check_ids() there as well. And you did all the preliminary work with making idmap persistent across all frames. Just something to improve (and looks straightforward, unlike many other things you've dealt with recently ;).
Anyways, great work, thanks!
Quoted 25 lines
[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/Eduard Zingerman (6):
bpf:regsafe()must not skipcheck_ids()
selftests/bpf: test cases forregsafe()bug skippingcheck_id()
bpf:states_equal()must build idmap for all function frames selftests/bpf: verifystates_equal()maintains idmap across all frames
bpf: usecheck_ids()foractive_lockcomparison selftests/bpf: test case for relaxed prunning of active_lock.idKumar Kartikeya Dwivedi (1):
selftests/bpf: Add pruning test case forbpf_spin_lockinclude/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()
In reply to Eduard ZingermanQuoted 102 lines · Eduard Zingerman
The verifier.c:regsafe() has the following shortcut:
equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0; ... if (equal) return true;Which is executed regardless old register type. This is incorrect for register types that might have an ID checked by
check_ids(), namely:
-PTR_TO_MAP_KEY
-PTR_TO_MAP_VALUE
-PTR_TO_PACKET_META
-PTR_TO_PACKETThe 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 --- ; Assumeis_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=fp0The 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=fp0Note that R8 states are byte-to-byte identical, so
regsafe()would exit early and skip call tocheck_ids(), thus ID mapping 2->2 will not be added to 'idmap'. Next, states for R9 are compared: these are not identical andcheck_ids()is executed, but 'idmap' is empty, socheck_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 <[email protected]>--- kernel/bpf/verifier.c | 29 ++++++++--------------------- 1 file changed, 8 insertions(+), 21 deletions(-)kernel/bpf/verifier.c +2
-19@@ -12926,15 +12926,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, equal =memcmp (rold, rcur, offsetof(struct bpf_reg_state , parent)) ==0 ; -if (rold->type ==PTR_TO_STACK ) -/* two stack pointers are equal only if they're pointing to -* the same stack frame, since fp-8 in foo != fp-8 in bar -*/ -return equal && rold->frameno == rcur->frameno; - -if (equal) -return true; -if (rold->type ==NOT_INIT )/* explored state can't have used this */ return true;@@ -12942,6 +12933,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,return false;switch (base_type (rold->type)) {case SCALAR_VALUE : +if (equal) +return true;if (env->explore_alu_limits)return false;if (rcur->type ==SCALAR_VALUE ) {@@ -13012,20 +13005,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* new val must satisfy old val knowledge */ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off); -case PTR_TO_CTX : -case CONST_PTR_TO_MAP : -case PTR_TO_PACKET_END : -case PTR_TO_FLOW_KEYS : -case PTR_TO_SOCKET : -case PTR_TO_SOCK_COMMON : -case PTR_TO_TCP_SOCK : -case PTR_TO_XDP_SOCK : -/* Only valid matches are exact, which memcmp() above -* would have accepted
kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 13015
Quoted 10 lines
kernel/bpf/verifier.c +6
-2+case PTR_TO_STACK : +/* two stack pointers are equal only if they're pointing to +* the same stack frame, since fp-8 in foo != fp-8 in bar */ +return equal && rold->frameno == rcur->frameno;default : -/* Don't know what's going on, just say it's not safe */ -return false; +/* Only valid matches are exact, which memcmp() */ +return equal;
Is it safe to assume this for any possible register type? Wouldn't register types that use id and/or ref_obj_id need extra checks here? I think preexisting default was a safer approach, in which if we forgot to explicitly add support for some new or updated register type, the worst thing is that for that *new* register we'd have suboptimal verification performance, but not safety concerns.
Quoted 6 lines
kernel/bpf/verifier.c +0
-1}/* Shouldn't get here; if we do, say it's not safe */ --2.34.1
Re: [PATCH bpf-next 3/7] bpf: states_equal() must build idmap for all function frames
In reply to Eduard ZingermanQuoted 74 lines · Eduard Zingerman
verifier.c:states_equal() must maintain register ID mapping across all function frames. Otherwise the following example might be erroneously marked as safe:
main:
fp[-24] = map_lookup_elem(...) ; frame[0].fp[-24].id == 1 fp[-32] = map_lookup_elem(...) ; frame[0].fp[-32].id == 2 r1 = &fp[-24] r2 = &fp[-32] call foo() r0 = 0 exitfoo:
0: r9 = r1
1: r8 = r2
2: r7 =ktime_get_ns()
3: r6 =ktime_get_ns()
4: if (r6 > r7) gotoskip_assign
5: r9 = r8
skip_assign: ; <--- checkpoint
6: r9 = *r9 ; (a) frame[1].r9.id == 2; (b) frame[1].r9.id == 17: 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] != 08: r8 = *r8 ; (a) r8 == &frame[0].fp[-32]
; (b) r8 == &frame[0].fp[-32]9: r0 = *r8 ; (a) safe
; (b) unsafeexit:
10: exitWhile 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 <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 4 ++-- kernel/bpf/verifier.c | 3 ++- 2 files changed, 4 insertions(+), 3 deletions(-)include/linux/bpf_verifier.h +0
-0
include/linux/bpf_verifier.h struct bpf_id_pair { · line 278
Quoted 8 lines
include/linux/bpf_verifier.h +2
-2@@ -273,9 +273,9 @@ struct bpf_id_pair {u32 cur; }; -/* Maximum number of register states that can exist at once */ -#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)#define MAX_CALL_FRAMES 8 +/* Maximum number of register states that can exist at once */ +#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)
this is overly pessimistic, the total number of stack slots doesn't change no matter how many call frames we have, it would be better to define this as:
#define BPF_ID_MAP_SIZE (MAX_BPF_REG * MAX_CALL_FRAMES + MAX_BPF_STACK / BPF_REG_SIZE)
Unless I missed something.
Quoted 27 lines
include/linux/bpf_verifier.h +0
-0struct bpf_verifier_state {/* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES ];kernel/bpf/verifier.c +2
-2@@ -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
In reply to Eduard ZingermanQuoted 7 lines · Eduard Zingerman
A test case that would erroneously pass verification if verifier.c:states_equal() maintains separate register ID mappings for call frames.
Signed-off-by Eduard Zingerman <[email protected]>---
It's so hard to read these tests. Moving forward, let's try adding new verifier tests like this using __naked functions and embedded assembly. With recent test loader changes ([0]), there isn't much that's needed, except for a few simple examples to get us started and perhaps __flags(BPF_F_TEST_STATE_FREQ) support. The upside is that using maps or global variables from assembly is now possible and easy, and doesn't require any custom loader support at all.
[0] https://patchwork.kernel.org/project/netdevbpf/list/?series=702713&state=*
Quoted 96 lines
tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++ 1 file changed, 82 insertions(+)tools/testing/selftests/bpf/verifier/calls.c +82
-1@@ -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
Eduard Zingerman
maintainerRe: [PATCH bpf-next 1/7] bpf: regsafe() must not skip check_ids()
In reply to Andrii NakryikoQuoted 112 lines · Andrii Nakryiko
Quoted 111 lines · Eduard Zingerman
The verifier.c:regsafe() has the following shortcut:
equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0; ... if (equal) return true;Which is executed regardless old register type. This is incorrect for register types that might have an ID checked by
check_ids(), namely:
-PTR_TO_MAP_KEY
-PTR_TO_MAP_VALUE
-PTR_TO_PACKET_META
-PTR_TO_PACKETThe 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 --- ; Assumeis_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=fp0The 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=fp0Note that R8 states are byte-to-byte identical, so
regsafe()would exit early and skip call tocheck_ids(), thus ID mapping 2->2 will not be added to 'idmap'. Next, states for R9 are compared: these are not identical andcheck_ids()is executed, but 'idmap' is empty, socheck_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 <[email protected]>--- kernel/bpf/verifier.c | 29 ++++++++--------------------- 1 file changed, 8 insertions(+), 21 deletions(-)kernel/bpf/verifier.c +7
-21@@ -12926,15 +12926,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, equal =memcmp (rold, rcur, offsetof(struct bpf_reg_state , parent)) ==0 ; -if (rold->type ==PTR_TO_STACK ) -/* two stack pointers are equal only if they're pointing to -* the same stack frame, since fp-8 in foo != fp-8 in bar -*/ -return equal && rold->frameno == rcur->frameno; - -if (equal) -return true; -if (rold->type ==NOT_INIT )/* explored state can't have used this */ return true;@@ -12942,6 +12933,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,return false;switch (base_type (rold->type)) {case SCALAR_VALUE : +if (equal) +return true;if (env->explore_alu_limits)return false;if (rcur->type ==SCALAR_VALUE ) {@@ -13012,20 +13005,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* new val must satisfy old val knowledge */ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off); -case PTR_TO_CTX : -case CONST_PTR_TO_MAP : -case PTR_TO_PACKET_END : -case PTR_TO_FLOW_KEYS : -case PTR_TO_SOCKET : -case PTR_TO_SOCK_COMMON : -case PTR_TO_TCP_SOCK : -case PTR_TO_XDP_SOCK : -/* Only valid matches are exact, which memcmp() above -* would have accepted +case PTR_TO_STACK : +/* two stack pointers are equal only if they're pointing to +* the same stack frame, since fp-8 in foo != fp-8 in bar */ +return equal && rold->frameno == rcur->frameno;default : -/* Don't know what's going on, just say it's not safe */ -return false; +/* Only valid matches are exact, which memcmp() */
Quoted 8 lines
kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 13015
Quoted 1 line
kernel/bpf/verifier.c +1
-0+return equal;Is it safe to assume this for any possible register type? Wouldn't register types that use id and/or
ref_obj_idneed extra checks here? I think preexisting default was a safer approach, in which if we forgot to explicitly add support for some new or updated register type, the worst thing is that for that *new* register we'd have suboptimal verification performance, but not safety concerns.
Well, I don't think that this commit changes regsafe() behavior in this regard. Here is how the code was structured before this commit:
static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
struct bpf_reg_state *rcur, struct bpf_id_pair *idmap)
{
bool equal;
if (!(rold->live & REG_LIVE_READ))
return true;
equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
if (rold->type == PTR_TO_STACK)
return equal && rold->frameno == rcur->frameno;
---> if (equal)
return true;
if (rold->type == NOT_INIT)
return true;
if (rcur->type == NOT_INIT)
return false;
switch (base_type(rold->type)) {
case SCALAR_VALUE:
... it's own logic, always returns ...
case PTR_TO_MAP_KEY:
case PTR_TO_MAP_VALUE:
... it's own logic, always returns ...
case PTR_TO_PACKET_META:
case PTR_TO_PACKET:
... it's own logic, always returns ...
case PTR_TO_CTX:
case CONST_PTR_TO_MAP:
case PTR_TO_PACKET_END:
case PTR_TO_FLOW_KEYS:
case PTR_TO_SOCKET:
case PTR_TO_SOCK_COMMON:
case PTR_TO_TCP_SOCK:
case PTR_TO_XDP_SOCK:
default:
return false;
}
/* Shouldn't get here; if we do, say it's not safe */
WARN_ON_ONCE(1);
return false;
}So the "safe if byte-to-byte equal" behavior was present already. I can add an explicit list of types to the "return equal;" branch and add a default "return false;" branch if you think that it is more fool-proof.
Quoted 8 lines
Quoted 8 lines
kernel/bpf/verifier.c +0
-1}/* Shouldn't get here; if we do, say it's not safe */ --2.34.1
Eduard Zingerman
maintainerRe: [PATCH bpf-next 3/7] bpf: states_equal() must build idmap for all function frames
In reply to Andrii NakryikoQuoted 88 lines · Andrii Nakryiko
Quoted 74 lines · Eduard Zingerman
verifier.c:states_equal() must maintain register ID mapping across all function frames. Otherwise the following example might be erroneously marked as safe:
main:
fp[-24] = map_lookup_elem(...) ; frame[0].fp[-24].id == 1 fp[-32] = map_lookup_elem(...) ; frame[0].fp[-32].id == 2 r1 = &fp[-24] r2 = &fp[-32] call foo() r0 = 0 exitfoo:
0: r9 = r1
1: r8 = r2
2: r7 =ktime_get_ns()
3: r6 =ktime_get_ns()
4: if (r6 > r7) gotoskip_assign
5: r9 = r8
skip_assign: ; <--- checkpoint
6: r9 = *r9 ; (a) frame[1].r9.id == 2; (b) frame[1].r9.id == 17: 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] != 08: r8 = *r8 ; (a) r8 == &frame[0].fp[-32]
; (b) r8 == &frame[0].fp[-32]9: r0 = *r8 ; (a) safe
; (b) unsafeexit:
10: exitWhile 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 <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 4 ++-- kernel/bpf/verifier.c | 3 ++- 2 files changed, 4 insertions(+), 3 deletions(-)include/linux/bpf_verifier.h +0
-0include/linux/bpf_verifier.h struct bpf_id_pair { · line 278
Quoted 8 lines
include/linux/bpf_verifier.h +2
-2@@ -273,9 +273,9 @@ struct bpf_id_pair {u32 cur; }; -/* Maximum number of register states that can exist at once */ -#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)#define MAX_CALL_FRAMES 8 +/* Maximum number of register states that can exist at once */ +#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)this is overly pessimistic, the total number of stack slots doesn't change no matter how many call frames we have, it would be better to define this as:
Quoted 4 lines
#define
BPF_ID_MAP_SIZE(MAX_BPF_REG*MAX_CALL_FRAMES+MAX_BPF_STACK/BPF_REG_SIZE)Unless I missed something.
Current bpf_check() mechanics looks as follows:
- do_check_{subprogs,main}() (indirectly):
- when a pseudo-function is called the call is processed by __check_func_call(), it allocates callee's struct bpf_func_state using kzalloc() and does not update ->stack and ->allocated_stack fields;
- when a stack write is processed by check_mem_access():
- check_stack_access_within_bounds() verifies that offset is within 0..-MAX_BPF_STACK;
- check_stack_write_{fixed,var}_off() calls grow_stack_state() which uses realloc_array() to increase ->stack as necessary;
- update_stack_depth() is used to increase env->subprog_info[...].stack_depth as appropriate;
- check_max_stack_depth() verifies that cumulative stack depth does not exceed MAX_BPF_STACK using env->subprog_info[...].stack_depth values.
This means that during do_check_*() we can have MAX_CALL_FRAMES functions each with a stack of size MAX_BPF_STACK. The following example could be used to verify the above assumptions:
{
"check_max_depth",
.insns = {
BPF_ST_MEM(BPF_DW, BPF_REG_FP, -512, 0),
BPF_CALL_REL(2),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
BPF_ST_MEM(BPF_DW, BPF_REG_FP, -512, 0),
BPF_MOV64_IMM(BPF_REG_0, 0),
BPF_EXIT_INSN(),
},
.result = REJECT,
},Here is the verifier log that shows that two frames both of size MAX_BPF_STACK slots were present during verification:
# ./test_verifier -vv 1030 #1030/p check_max_depth FAIL Unexpected error message! EXP: (null) RES: func#0 @0 func#1 @4 0: R1=ctx(off=0,imm=0) R10=fp0 0: (7a) *(u64 *)(r10 -512) = 0 ; R10=fp0 fp-512_w=mmmmmmmm 1: (85) call pc+2 caller: R10=fp0 fp-512_w=mmmmmmmm callee: frame1: R1=ctx(off=0,imm=0) R10=fp0 4: (7a) *(u64 *)(r10 -512) = 0 ; frame1: R10=fp0 fp-512_w=mmmmmmmm 5: (b7) r0 = 0 ; frame1: R0_w=0 6: (95) exit returning from callee: frame1: R0_w=0 R1=ctx(off=0,imm=0) R10=fp0 fp-512_w=mmmmmmmm to caller at 2: R0_w=0 R10=fp0 fp-512_w=mmmmmmmm
from 6 to 2: R0_w=0 R10=fp0 fp-512_w=mmmmmmmm
2: (b7) r0 = 0 ; R0_w=0
3: (95) exit
combined stack size of 2 calls is 1024. Too large
verification time 541 usec
stack depth 512+512
Quoted 30 lines
Quoted 30 lines
include/linux/bpf_verifier.h +0
-0struct bpf_verifier_state {/* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES ];kernel/bpf/verifier.c +2
-2@@ -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
Eduard Zingerman
maintainerQuoted 29 lines · Andrii Nakryiko
Quoted 11 lines · Eduard Zingerman
This patch-set consists of a series of bug fixes for register ID tracking in verifier.c:states_equal()/regsafe() functions:
- for registers of type PTR_TO_MAP_{KEY,VALUE}, PTR_TO_PACKET[_META] theregsafe()should callcheck_ids()even if registers are byte-to-byte equal;
-states_equal()must maintain idmap that covers all function frames in the state because functions likemark_ptr_or_null_regs()operate on all registers in the state;
-regsafe()must compare spin lock ids forPTR_TO_MAP_VALUEregisters.Quoted 5 lines
The last point covers issue reported by Kumar Kartikeya Dwivedi in [1], I borrowed the test commit from there.
Note, that there is also an issue with register id tracking for scalars described here [2], it would be addressed separately.Awesome set of patches, thanks for working on this! I left a few comments and suggestions, please take a look, and if they do make sense, consider sending follow up patches.
Let's really try to use
asm()next time for selftests, though.It would be awesome to somehow automatically move test_verifier's tests to this test_progs-based embedded assembly way, but that probably takes some Python hackery (awesome project for some curious soul, for sure).
Quoted 7 lines
Anyways, back to the point I wanted to make. Given you've clearly thought about all the ID checks a lot, consider checking
refsafe()(notregsafe()!) as well. I think we should docheck_ids()there as well. And you did all the preliminary work with making idmap persistent across all frames. Just something to improve (and looks straightforward, unlike many other things you've dealt with recently ;).
Makes sense, I'll work on it.
Quoted 2 lines
Anyways, great work, thanks!
Thank you.
Quoted 26 lines
Quoted 26 lines
[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/Eduard Zingerman (6):
bpf:regsafe()must not skipcheck_ids()
selftests/bpf: test cases forregsafe()bug skippingcheck_id()
bpf:states_equal()must build idmap for all function frames selftests/bpf: verifystates_equal()maintains idmap across all frames
bpf: usecheck_ids()foractive_lockcomparison selftests/bpf: test case for relaxed prunning of active_lock.idKumar Kartikeya Dwivedi (1):
selftests/bpf: Add pruning test case forbpf_spin_lockinclude/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
Eduard Zingerman
maintainerRe: [PATCH bpf-next 4/7] selftests/bpf: verify states_equal() maintains idmap across all frames
In reply to Andrii NakryikoQuoted 18 lines · Andrii Nakryiko
Quoted 7 lines · Eduard Zingerman
A test case that would erroneously pass verification if verifier.c:states_equal() maintains separate register ID mappings for call frames.
Signed-off-by Eduard Zingerman <[email protected]>---
It's so hard to read these tests. Moving forward, let's try adding new verifier tests like this using
__nakedfunctions and embedded assembly. With recent test loader changes ([0]), there isn't much that's needed, except for a few simple examples to get us started and perhaps__flags(BPF_F_TEST_STATE_FREQ)support. The upside is that using maps or global variables from assembly is now possible and easy, and doesn't require any custom loader support at all.
Quoted 3 lines
[0] https://patchwork.kernel.org/project/netdevbpf/list/?series=702713&state=*
This is very nice, I'll try to use it for the next patch-set. How do you think it should look like for test_verifier kind of tests? The easiest way would be to just add new BPF sources under progs/ and have some prog_tests/verifier.c like this:
int test_verifier()
...
RUN_TESTS(array_access),
RUN_TESTS(scalar_ids)
...
Thus reusing the build mechanics for skeletons etc. However, it seems to break current logical separation between "unit" tests in test_verifier and "functional" tests in test_progs. But this may be ok.
Quoted 96 lines
Quoted 96 lines
tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++ 1 file changed, 82 insertions(+)tools/testing/selftests/bpf/verifier/calls.c +82
-1@@ -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
Quoted 35 lines · Eduard Zingerman
Quoted 18 lines · Andrii Nakryiko
Quoted 7 lines · Eduard Zingerman
A test case that would erroneously pass verification if verifier.c:states_equal() maintains separate register ID mappings for call frames.
Signed-off-by Eduard Zingerman <[email protected]>---
It's so hard to read these tests. Moving forward, let's try adding new verifier tests like this using
__nakedfunctions and embedded assembly. With recent test loader changes ([0]), there isn't much that's needed, except for a few simple examples to get us started and perhaps__flags(BPF_F_TEST_STATE_FREQ)support. The upside is that using maps or global variables from assembly is now possible and easy, and doesn't require any custom loader support at all.Quoted 3 lines
[0] https://patchwork.kernel.org/project/netdevbpf/list/?series=702713&state=*
This is very nice, I'll try to use it for the next patch-set. How do you think it should look like for
test_verifierkind of tests? The easiest way would be to just add new BPF sources under progs/ and have someprog_tests/verifier.clike this:int
test_verifier()
...
RUN_TESTS(array_access),
RUN_TESTS(scalar_ids)
...
Quoted 4 lines
Thus reusing the build mechanics for skeletons etc. However, it seems to break current logical separation between "unit" tests in
test_verifierand "functional" tests intest_progs. But this may be ok.
Yes, reusing skeletons and stuff, of course. But I wouldn't necessarily make all of them as part of a single test_verifier test. I'd probably have multiple tests with logically grouped sets of tests.
The interesting part is whether we can somehow automatically convert macro-based test_verifier tests to this new embedded asm :) At least most of them, but it's not clear how much work that would be, so I just mentioned the possibility. I don't think we should manually rewrite 1000+ tests, of course.
Quoted 99 lines
Quoted 98 lines
Quoted 98 lines
tools/testing/selftests/bpf/verifier/calls.c | 82 ++++++++++++++++++++ 1 file changed, 82 insertions(+)tools/testing/selftests/bpf/verifier/calls.c +82
-1@@ -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
In reply to Eduard ZingermanQuoted 154 lines · Eduard Zingerman
Quoted 88 lines · Andrii Nakryiko
Quoted 74 lines · Eduard Zingerman
verifier.c:states_equal() must maintain register ID mapping across all function frames. Otherwise the following example might be erroneously marked as safe:
main:
fp[-24] = map_lookup_elem(...) ; frame[0].fp[-24].id == 1 fp[-32] = map_lookup_elem(...) ; frame[0].fp[-32].id == 2 r1 = &fp[-24] r2 = &fp[-32] call foo() r0 = 0 exitfoo:
0: r9 = r1
1: r8 = r2
2: r7 =ktime_get_ns()
3: r6 =ktime_get_ns()
4: if (r6 > r7) gotoskip_assign
5: r9 = r8
skip_assign: ; <--- checkpoint
6: r9 = *r9 ; (a) frame[1].r9.id == 2; (b) frame[1].r9.id == 17: 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] != 08: r8 = *r8 ; (a) r8 == &frame[0].fp[-32]
; (b) r8 == &frame[0].fp[-32]9: r0 = *r8 ; (a) safe
; (b) unsafeexit:
10: exitWhile 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 <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 4 ++-- kernel/bpf/verifier.c | 3 ++- 2 files changed, 4 insertions(+), 3 deletions(-)include/linux/bpf_verifier.h +0
-0include/linux/bpf_verifier.h struct bpf_id_pair { · line 278
Quoted 8 lines
include/linux/bpf_verifier.h +2
-2@@ -273,9 +273,9 @@ struct bpf_id_pair {u32 cur; }; -/* Maximum number of register states that can exist at once */ -#define BPF_ID_MAP_SIZE (MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE)#define MAX_CALL_FRAMES 8 +/* Maximum number of register states that can exist at once */ +#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)this is overly pessimistic, the total number of stack slots doesn't change no matter how many call frames we have, it would be better to define this as:
Quoted 4 lines
#define
BPF_ID_MAP_SIZE(MAX_BPF_REG*MAX_CALL_FRAMES+MAX_BPF_STACK/BPF_REG_SIZE)Unless I missed something.
Current
bpf_check()mechanics looks as follows:
- do_check_{subprogs,main}() (indirectly):
- when a pseudo-function is called the call is processed by__check_func_call(), it allocates callee's structbpf_func_stateusingkzalloc()and does not update ->stack and ->allocated_stack fields;
- when a stack write is processed bycheck_mem_access():
-check_stack_access_within_bounds()verifies that offset is within 0..-MAX_BPF_STACK;
- check_stack_write_{fixed,var}_off() callsgrow_stack_state()which usesrealloc_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 exceedMAX_BPF_STACKusing env->subprog_info[...].stack_depth values.This means that during do_check_*() we can have
MAX_CALL_FRAMESfunctions each with a stack of sizeMAX_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_STACKslots were present during verification:# ./test_verifier -vv 1030 #1030/p check_max_depth FAIL Unexpected error message! EXP: (null) RES: func#0 @0 func#1 @4 0: R1=ctx(off=0,imm=0) R10=fp0 0: (7a) *(u64 *)(r10 -512) = 0 ; R10=fp0 fp-512_w=mmmmmmmm 1: (85) call pc+2 caller: R10=fp0 fp-512_w=mmmmmmmm callee: frame1: R1=ctx(off=0,imm=0) R10=fp0 4: (7a) *(u64 *)(r10 -512) = 0 ; frame1: R10=fp0 fp-512_w=mmmmmmmm 5: (b7) r0 = 0 ; frame1: R0_w=0 6: (95) exit returning from callee: frame1: R0_w=0 R1=ctx(off=0,imm=0) R10=fp0 fp-512_w=mmmmmmmm to caller at 2: R0_w=0 R10=fp0 fp-512_w=mmmmmmmm
Quoted 7 lines
from 6 to 2: R0_w=0 R10=fp0 fp-512_w=mmmmmmmm
2: (b7) r0 = 0 ; R0_w=0
3: (95) exit
combined stack size of 2 calls is 1024. Too large
verification time 541 usec
stack depth 512+512
It's all true, but I'm not clear on what point you are trying to make. BPF program did get rejected after using so much stack trace, right? So it should be ok to reduce idmap size.
It's the difference between maintaining 152 (which is already quite overpesimisstic for any real application) vs 600 entries (1216 bytes vs 4800 bytes). On each state equality check call. We can probably just drop that WARN_ON_ONCE(1) in check_ids and reduce the size of idmap, no more changes, right?
Quoted 31 lines
Quoted 30 lines
Quoted 30 lines
include/linux/bpf_verifier.h +0
-0struct bpf_verifier_state {/* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES ];kernel/bpf/verifier.c +2
-2@@ -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()
In reply to Eduard ZingermanQuoted 168 lines · Eduard Zingerman
Quoted 112 lines · Andrii Nakryiko
Quoted 111 lines · Eduard Zingerman
The verifier.c:regsafe() has the following shortcut:
equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0; ... if (equal) return true;Which is executed regardless old register type. This is incorrect for register types that might have an ID checked by
check_ids(), namely:
-PTR_TO_MAP_KEY
-PTR_TO_MAP_VALUE
-PTR_TO_PACKET_META
-PTR_TO_PACKETThe 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 --- ; Assumeis_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=fp0The 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=fp0Note that R8 states are byte-to-byte identical, so
regsafe()would exit early and skip call tocheck_ids(), thus ID mapping 2->2 will not be added to 'idmap'. Next, states for R9 are compared: these are not identical andcheck_ids()is executed, but 'idmap' is empty, socheck_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 <[email protected]>--- kernel/bpf/verifier.c | 29 ++++++++--------------------- 1 file changed, 8 insertions(+), 21 deletions(-)kernel/bpf/verifier.c +7
-21@@ -12926,15 +12926,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, equal =memcmp (rold, rcur, offsetof(struct bpf_reg_state , parent)) ==0 ; -if (rold->type ==PTR_TO_STACK ) -/* two stack pointers are equal only if they're pointing to -* the same stack frame, since fp-8 in foo != fp-8 in bar -*/ -return equal && rold->frameno == rcur->frameno; - -if (equal) -return true; -if (rold->type ==NOT_INIT )/* explored state can't have used this */ return true;@@ -12942,6 +12933,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,return false;switch (base_type (rold->type)) {case SCALAR_VALUE : +if (equal) +return true;if (env->explore_alu_limits)return false;if (rcur->type ==SCALAR_VALUE ) {@@ -13012,20 +13005,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* new val must satisfy old val knowledge */ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off); -case PTR_TO_CTX : -case CONST_PTR_TO_MAP : -case PTR_TO_PACKET_END : -case PTR_TO_FLOW_KEYS : -case PTR_TO_SOCKET : -case PTR_TO_SOCK_COMMON : -case PTR_TO_TCP_SOCK : -case PTR_TO_XDP_SOCK : -/* Only valid matches are exact, which memcmp() above -* would have accepted +case PTR_TO_STACK : +/* two stack pointers are equal only if they're pointing to +* the same stack frame, since fp-8 in foo != fp-8 in bar */ +return equal && rold->frameno == rcur->frameno;default : -/* Don't know what's going on, just say it's not safe */ -return false; +/* Only valid matches are exact, which memcmp() */ Quoted 8 lines
kernel/bpf/verifier.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 13015
Quoted 1 line
kernel/bpf/verifier.c +1
-0+return equal;Is it safe to assume this for any possible register type? Wouldn't register types that use id and/or
ref_obj_idneed 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, structbpf_reg_state*rold,
structbpf_reg_state*rcur, structbpf_id_pair*idmap){ bool equal; if (!(rold->live & REG_LIVE_READ)) return true; equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0; if (rold->type == PTR_TO_STACK) return equal && rold->frameno == rcur->frameno; ---> if (equal) return true; if (rold->type == NOT_INIT) return true; if (rcur->type == NOT_INIT) return false; switch (base_type(rold->type)) { case SCALAR_VALUE: ... it's own logic, always returns ... case PTR_TO_MAP_KEY: case PTR_TO_MAP_VALUE: ... it's own logic, always returns ... case PTR_TO_PACKET_META: case PTR_TO_PACKET: ... it's own logic, always returns ... case PTR_TO_CTX: case CONST_PTR_TO_MAP: case PTR_TO_PACKET_END: case PTR_TO_FLOW_KEYS: case PTR_TO_SOCKET: case PTR_TO_SOCK_COMMON: case PTR_TO_TCP_SOCK: case PTR_TO_XDP_SOCK: default: return false; } /* Shouldn't get here; if we do, say it's not safe */ WARN_ON_ONCE(1); return false; }
Quoted 4 lines
So the "safe if byte-to-byte equal" behavior was present already. I can add an explicit list of types to the "return equal;" branch and add a default "return false;" branch if you think that it is more fool-proof.
Sorry, I didn't claim you made it worse. But given we are refactoring this piece of code, let's make it more "safe-by-default".
So yeah, I think an explicit list of all the recognized register types would be better, IMO.
Quoted 10 lines
Quoted 9 lines
Quoted 9 lines
kernel/bpf/verifier.c +0
-1}/* Shouldn't get here; if we do, say it's not safe */ --2.34.1