Fix record_func_key to perform backtracking on r3
Subsystems (6)
Daniel Borkmann
maintainercover Fix record_func_key to perform backtracking on r3
Fixes pruning behavior when record_func_key() is used. See main description in patch 1, test cases added in patch 2.
Thanks!
Daniel Borkmann (2):
bpf: Fix record_func_key to perform backtracking on r3
bpf: Add further test_verifier cases for record_func_key
kernel/bpf/verifier.c | 8 +- tools/testing/selftests/bpf/test_verifier.c | 43 ++--- .../selftests/bpf/verifier/ref_tracking.c | 6 +- .../selftests/bpf/verifier/runtime_jit.c | 151 ++++++++++++++++++ 4 files changed, 183 insertions(+), 25 deletions(-)
Signature · 1 line
2.21.0
Daniel Borkmann
maintainerPATCH 1/2 bpf: Fix record_func_key to perform backtracking on r3
While testing Cilium with /unreleased/ Linus' tree under BPF-based NodePort implementation, I noticed a strange BPF SNAT engine behavior from time to time. In some cases it would do the correct SNAT/DNAT service translation, but at a random point in time it would just stop and perform an unexpected translation after SYN, SYN/ACK and stack would send a RST back. While initially assuming that there is some sort of a race condition in BPF code, adding trace_printk()s for debugging purposes at some point seemed to have resolved the issue auto-magically.
Digging deeper on this Heisenbug and reducing the trace_printk() calls to an absolute minimum, it turns out that a single call would suffice to trigger / not trigger the seen RST issue, even though the logic of the program itself remains unchanged. Turns out the single call changed verifier pruning behavior to get everything to work. Reconstructing a minimal test case, the incorrect JIT dump looked as follows:
# bpftool p d j i 11346
0xffffffffc0cba96c:
[...]
21: movzbq 0x30(%rdi),%rax
26: cmp $0xd,%rax
2a: je 0x000000000000003a
2c: xor %edx,%edx
2e: movabs $0xffff89cc74e85800,%rsi
38: jmp 0x0000000000000049
3a: mov $0x2,%edx
3f: movabs $0xffff89cc74e85800,%rsi
49: mov -0x224(%rbp),%eax
4f: cmp $0x20,%eax
52: ja 0x0000000000000062
54: add $0x1,%eax
57: mov %eax,-0x224(%rbp)
5d: jmpq 0xffffffffffff6911
62: mov $0x1,%eax
[...]Hence, unexpectedly, JIT emitted a direct jump even though retpoline based one would have been needed since in line 2c and 3a we have different slot keys in BPF reg r3. Verifier log of the test case reveals what happened:
0: (b7) r0 = 14
1: (73) *(u8 *)(r1 +48) = r0
2: (71) r0 = *(u8 *)(r1 +48)
3: (15) if r0 == 0xd goto pc+4
R0_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=ctx(id=0,off=0,imm=0) R10=fp0
4: (b7) r3 = 0
5: (18) r2 = 0xffff89cc74d54a00
7: (05) goto pc+3
11: (85) call bpf_tail_call#12
12: (b7) r0 = 1
13: (95) exit
from 3 to 8: R0_w=inv13 R1=ctx(id=0,off=0,imm=0) R10=fp0
8: (b7) r3 = 2
9: (18) r2 = 0xffff89cc74d54a00
11: safe
processed 13 insns (limit 1000000) [...]
Second branch is pruned by verifier since considered safe, but issue is that record_func_key() couldn't have seen the index in line 3a and therefore decided that emitting a direct jump at this location was okay.
Fix this by reusing our backtracking logic for precise scalar verification in order to prevent pruning on the slot key. This means verifier will track content of r3 all the way backwards and only prune if both scalars were unknown in state equivalence check and therefore poisoned in the first place in record_func_key(). The range is [x,x] in record_func_key() case since the slot always would have to be constant immediate. Correct verification after fix:
0: (b7) r0 = 14
1: (73) *(u8 *)(r1 +48) = r0
2: (71) r0 = *(u8 *)(r1 +48)
3: (15) if r0 == 0xd goto pc+4
R0_w=invP(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=ctx(id=0,off=0,imm=0) R10=fp0
4: (b7) r3 = 0
5: (18) r2 = 0x0
7: (05) goto pc+3
11: (85) call bpf_tail_call#12
12: (b7) r0 = 1
13: (95) exit
from 3 to 8: R0_w=invP13 R1=ctx(id=0,off=0,imm=0) R10=fp0
8: (b7) r3 = 2
9: (18) r2 = 0x0
11: (85) call bpf_tail_call#12
12: (b7) r0 = 1
13: (95) exit
processed 15 insns (limit 1000000) [...]
And correct corresponding JIT dump:
# bpftool p d j i 11
0xffffffffc0dc34c4:
[...]
21: movzbq 0x30(%rdi),%rax
26: cmp $0xd,%rax
2a: je 0x000000000000003a
2c: xor %edx,%edx
2e: movabs $0xffff9928b4c02200,%rsi
38: jmp 0x0000000000000049
3a: mov $0x2,%edx
3f: movabs $0xffff9928b4c02200,%rsi
49: cmp $0x4,%rdx
4d: jae 0x0000000000000093
4f: and $0x3,%edx
52: mov %edx,%edx
54: cmp %edx,0x24(%rsi)
57: jbe 0x0000000000000093
59: mov -0x224(%rbp),%eax
5f: cmp $0x20,%eax
62: ja 0x0000000000000093
64: add $0x1,%eax
67: mov %eax,-0x224(%rbp)
6d: mov 0x110(%rsi,%rdx,8),%rax
75: test %rax,%rax
78: je 0x0000000000000093
7a: mov 0x30(%rax),%rax
7e: add $0x19,%rax
82: callq 0x000000000000008e
87: pause
89: lfence
8c: jmp 0x0000000000000087
8e: mov %rax,(%rsp)
92: retq
93: mov $0x1,%eax
[...]Also explicitly adding explicit env->allow_ptr_leaks to fixup_bpf_calls() since backtracking is enabled under former (direct jumps as well, but use different test). In case of only tracking different map pointers as in c93552c443eb ("bpf:
properly enforce index mask to prevent out-of-bounds speculation"), pruning cannot make such short-cuts, neither if there are paths with scalar and non-scalar types as r3. mark_chain_precision() is only needed after we know that register_is_const(). If it was not the case, we already poison the key on first path and non-const key in later paths are not matching the scalar range in regsafe() either. Cilium NodePort testing passes fine as well now. Note, released kernels not affected.
--- kernel/bpf/verifier.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +7 -1
@@ -4134,6 +4134,7 @@ record_func_key(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta,struct bpf_map *map = meta->map_ptr;struct tnum range;u64 val; +int err;if (func_id != BPF_FUNC_tail_call)return 0 ;
@@ -4150,6 +4151,10 @@ record_func_key(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta,return 0 ; } + err =mark_chain_precision (env,BPF_REG_3 ); +if (err) +return err; + val = reg->var_off.value;if (bpf_map_key_unseen (aux))bpf_map_key_store (aux, val);
@@ -9272,7 +9277,8 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env) insn->code =BPF_JMP |BPF_TAIL_CALL ; aux = &env->insn_aux_data[i + delta]; -if (prog->jit_requested && !expect_blinding && +if (env->allow_ptr_leaks && !expect_blinding && + prog->jit_requested && !bpf_map_key_poisoned (aux) && !bpf_map_ptr_poisoned (aux) && !bpf_map_ptr_unpriv (aux)) {
Signature · 1 line
2.21.0
Daniel Borkmann
maintainerPATCH 2/2 bpf: Add further test_verifier cases for record_func_key
In reply to Daniel BorkmannExpand dummy prog generation such that we can easily check on return codes and add few more test cases to make sure we keep on tracking pruning behavior.
# ./test_verifier [...] #1066/p XDP pkt read, pkt_data <= pkt_meta', bad access 1 OK #1067/p XDP pkt read, pkt_data <= pkt_meta', bad access 2 OK Summary: 1580 PASSED, 0 SKIPPED, 0 FAILED
Also verified that JIT dump of added test cases looks good.
--- tools/testing/selftests/bpf/test_verifier.c | 43 ++--- .../selftests/bpf/verifier/ref_tracking.c | 6 +- .../selftests/bpf/verifier/runtime_jit.c | 151 ++++++++++++++++++ 3 files changed, 176 insertions(+), 24 deletions(-)
tools/testing/selftests/bpf/test_verifier.c +22 -21
@@ -408,10 +408,10 @@ static void update_map(int fd, int index)assert (!bpf_map_update_elem (fd, &index, &value,0 )); } -static int create_prog_dummy1 (enum bpf_prog_type prog_type) +static int create_prog_dummy_simple (enum bpf_prog_type prog_type,int ret) {struct bpf_insn prog[] = { -BPF_MOV64_IMM (BPF_REG_0 ,42 ), +BPF_MOV64_IMM (BPF_REG_0 , ret),BPF_EXIT_INSN (), };
@@ -419,14 +419,15 @@ static int create_prog_dummy1(enum bpf_prog_type prog_type) ARRAY_SIZE(prog), "GPL", 0, NULL, 0); } -static int create_prog_dummy2 (enum bpf_prog_type prog_type,int mfd,int idx) +static int create_prog_dummy_loop (enum bpf_prog_type prog_type,int mfd, +int idx,int ret) {struct bpf_insn prog[] = {BPF_MOV64_IMM (BPF_REG_3 , idx),BPF_LD_MAP_FD (BPF_REG_2 , mfd),BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_tail_call), -BPF_MOV64_IMM (BPF_REG_0 ,41 ), +BPF_MOV64_IMM (BPF_REG_0 , ret),BPF_EXIT_INSN (), };
@@ -435,10 +436,9 @@ static int create_prog_dummy2(enum bpf_prog_type prog_type, int mfd, int idx) }static int create_prog_array (enum bpf_prog_type prog_type,uint32_t max_elem, -int p1key) +int p1key,int p2key,int p3key) { -int p2key =1 ; -int mfd, p1fd, p2fd; +int mfd, p1fd, p2fd, p3fd; mfd =bpf_create_map (BPF_MAP_TYPE_PROG_ARRAY ,sizeof (int ),sizeof (int ), max_elem,0 );
@@ -449,23 +449,24 @@ static int create_prog_array(enum bpf_prog_type prog_type, uint32_t max_elem,return -1 ; } - p1fd =create_prog_dummy1 (prog_type); - p2fd =create_prog_dummy2 (prog_type, mfd, p2key); -if (p1fd <0 || p2fd <0 ) - goto out; + p1fd =create_prog_dummy_simple (prog_type,42 ); + p2fd =create_prog_dummy_loop (prog_type, mfd, p2key,41 ); + p3fd =create_prog_dummy_simple (prog_type,24 ); +if (p1fd <0 || p2fd <0 || p3fd <0 ) + goto err;if (bpf_map_update_elem (mfd, &p1key, &p1fd,BPF_ANY ) <0 ) - goto out; + goto err;if (bpf_map_update_elem (mfd, &p2key, &p2fd,BPF_ANY ) <0 ) - goto out; + goto err; +if (bpf_map_update_elem (mfd, &p3key, &p3fd,BPF_ANY ) <0 ) { +err: +close (mfd); + mfd =-1 ; + } +close (p3fd);close (p2fd);close (p1fd); -return mfd; -out: -close (p2fd); -close (p1fd); -close (mfd); -return -1 ; }static int create_map_in_map (void )
@@ -684,7 +685,7 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_prog_type prog_type, }if (*fixup_prog1) { - map_fds[4 ] =create_prog_array (prog_type,4 ,0 ); + map_fds[4 ] =create_prog_array (prog_type,4 ,0 ,1 ,2 ); do { prog[*fixup_prog1].imm = map_fds[4]; fixup_prog1++;
@@ -692,7 +693,7 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_prog_type prog_type, }if (*fixup_prog2) { - map_fds[5 ] =create_prog_array (prog_type,8 ,7 ); + map_fds[5 ] =create_prog_array (prog_type,8 ,7 ,1 ,2 ); do { prog[*fixup_prog2].imm = map_fds[5]; fixup_prog2++;
tools/testing/selftests/bpf/verifier/ref_tracking.c +3 -3
@@ -455,7 +455,7 @@BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ),BPF_JMP_IMM (BPF_JNE ,BPF_REG_1 ,0 ,7 ),/* bpf_tail_call() */ -BPF_MOV64_IMM (BPF_REG_3 ,2 ), +BPF_MOV64_IMM (BPF_REG_3 ,3 ),BPF_LD_MAP_FD (BPF_REG_2 ,0 ),BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_7 ), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_tail_call),
@@ -478,7 +478,7 @@BPF_JMP_IMM (BPF_JEQ ,BPF_REG_1 ,0 ,1 ),BPF_EMIT_CALL (BPF_FUNC_sk_release),/* bpf_tail_call() */ -BPF_MOV64_IMM (BPF_REG_3 ,2 ), +BPF_MOV64_IMM (BPF_REG_3 ,3 ),BPF_LD_MAP_FD (BPF_REG_2 ,0 ),BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_7 ), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_tail_call),
@@ -497,7 +497,7 @@BPF_SK_LOOKUP (sk_lookup_tcp),/* bpf_tail_call() */ BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), -BPF_MOV64_IMM (BPF_REG_3 ,2 ), +BPF_MOV64_IMM (BPF_REG_3 ,3 ),BPF_LD_MAP_FD (BPF_REG_2 ,0 ),BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_7 ), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_tail_call),
tools/testing/selftests/bpf/verifier/runtime_jit.c +151 -0
165 lines not on this page · raw message
Signature · 1 line
2.21.0
Alexei Starovoitov
AppliedQuoted 3 lines · Daniel Borkmann
Fixes pruning behavior when
record_func_key()is used. See main description in patch 1, test cases added in patch 2.
Applied. Thanks