bpf: fix calculation of subseq_idx during precision backtracking
Andrii Nakryiko
maintainerPATCH 1/1 bpf: fix calculation of subseq_idx during precision backtracking
Subsequent instruction index (subseq_idx) is an index of an instruction that was verified/executed by verifier after the currently processed instruction. It is maintained during precision backtracking processing and is used to detect various subprog calling conditions.
This patch fixes the bug with incorrectly resetting subseq_idx to -1 when going from child state to parent state during backtracking. If we don't maintain correct subseq_idx we can misidentify subprog calls leading to precision tracking bugs.
One such case was triggered by test_global_funcs/global_func9 test where global subprog call happened to be the very last instruction in parent state, leading to subseq_idx==-1, triggering WARN_ONCE:
[ 36.045754] verifier backtracking bug [ 36.045764] WARNING: CPU: 13 PID: 2073 at kernel/bpf/verifier.c:3503 __mark_chain_precision+0xcc6/0xde0 [ 36.046819] Modules linked in: aesni_intel(E) crypto_simd(E) cryptd(E) kvm_intel(E) kvm(E) irqbypass(E) i2c_piix4(E) serio_raw(E) i2c_core(E) crc32c_intel) [ 36.048040] CPU: 13 PID: 2073 Comm: test_progs Tainted: G W OE 6.3.0-07976-g4d585f48ee6b-dirty #972 [ 36.048783] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.12.0-59-gc9ba5276e321-prebuilt.qemu.org 04/01/2014 [ 36.049648] RIP: 0010:__mark_chain_precision+0xcc6/0xde0 [ 36.050038] Code: 3d 82 c6 05 bb 35 32 02 01 e8 66 21 ec ff 0f 0b b8 f2 ff ff ff e9 30 f5 ff ff 48 c7 c7 f3 61 3d 82 4c 89 0c 24 e8 4a 21 ec ff <0f> 0b 4c0
With the fix precision tracking across multiple states works correctly now:
mark_precise: frame0: last_idx 45 first_idx 38 subseq_idx -1mark_precise: frame0: regs=r8 stack= before 44: (61) r7 = *(u32 *)(r10 -4)mark_precise: frame0: regs=r8 stack= before 43: (85) call pc+41mark_precise: frame0: regs=r8 stack= before 42: (07) r1 += -48mark_precise: frame0: regs=r8 stack= before 41: (bf) r1 = r10mark_precise: frame0: regs=r8 stack= before 40: (63) *(u32 *)(r10 -48) = r1mark_precise: frame0: regs=r8 stack= before 39: (b4) w1 = 0mark_precise: frame0: regs=r8 stack= before 38: (85) call pc+38mark_precise: frame0: parent state regs=r8 stack=: R0_w=scalar() R1_w=map_value(off=4,ks=4,vs=8,imm=0) R6=1 R7_w=scalar() R8_r=P0 R10=fpmmark_precise: frame0: last_idx 36 first_idx 28 subseq_idx 38mark_precise: frame0: regs=r8 stack= before 36: (18) r1 = 0xffff888104f2ed14mark_precise: frame0: regs=r8 stack= before 35: (85) call pc+33mark_precise: frame0: regs=r8 stack= before 33: (18) r1 = 0xffff888104f2ed10mark_precise: frame0: regs=r8 stack= before 32: (85) call pc+36mark_precise: frame0: regs=r8 stack= before 31: (07) r1 += -4mark_precise: frame0: regs=r8 stack= before 30: (bf) r1 = r10mark_precise: frame0: regs=r8 stack= before 29: (63) *(u32 *)(r10 -4) = r7mark_precise: frame0: regs=r8 stack= before 28: (4c) w7 |= w0mark_precise: frame0: parent state regs=r8 stack=: R0_rw=scalar() R6=1 R7_rw=scalar() R8_rw=P0 R10=fp0 fp-48_r=mmmmmmmmmark_precise: frame0: last_idx 27 first_idx 16 subseq_idx 28mark_precise: frame0: regs=r8 stack= before 27: (85) call pc+31mark_precise: frame0: regs=r8 stack= before 26: (b7) r1 = 0mark_precise: frame0: regs=r8 stack= before 25: (b7) r8 = 0
Note how subseq_idx starts out as -1, then is preserved as 38 and then 28 as we go up the parent state chain.
--- kernel/bpf/verifier.c | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-)
kernel/bpf/verifier.c +8 -6
@@ -3864,10 +3864,11 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)struct bpf_verifier_state *st = env->cur_state;int first_idx = st->first_insn_idx;int last_idx = env->insn_idx; +int subseq_idx =-1 ;struct bpf_func_state *func;struct bpf_reg_state *reg;bool skip_first = true; -int i, prev_i, fr, err; +int i, fr, err;if (!env->bpf_capable)return 0 ;
@@ -3897,8 +3898,8 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)u32 history = st->jmp_history_cnt;if (env->log.level &BPF_LOG_LEVEL2 ) { -verbose (env,"mark_precise: frame%d: last_idx %d first_idx %d\n" , - bt->frame, last_idx, first_idx); +verbose (env,"mark_precise: frame%d: last_idx %d first_idx %d subseq_idx %d \n" , + bt->frame, last_idx, first_idx, subseq_idx); }if (last_idx <0 ) {
@@ -3930,12 +3931,12 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)return -EFAULT ; } -for (i = last_idx, prev_i =-1 ;;) { +for (i = last_idx;;) {if (skip_first) { err =0 ; skip_first = false; }else { - err =backtrack_insn (env, i, prev_i, bt); + err =backtrack_insn (env, i, subseq_idx, bt); }if (err == -ENOTSUPP ) {mark_all_scalars_precise (env, env->cur_state);
@@ -3952,7 +3953,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)return 0 ;if (i == first_idx)break ; - prev_i = i; + subseq_idx = i; i =get_prev_insn_idx (st, i, &history);if (i >= env->prog->len) {/* This can happen if backtracking reached insn 0
@@ -4031,6 +4032,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno)if (bt_empty (bt))return 0 ; + subseq_idx = first_idx; last_idx = st->last_insn_idx; first_idx = st->first_insn_idx; }
Signature · 1 line
2.34.1
This patch was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This patch was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 11 lines · On Mon, 15 May 2023 11:07:10 -0700 you wrote:
Subsequent instruction index (
subseq_idx) is an index of an instruction that was verified/executed by verifier after the currently processed instruction. It is maintained during precision backtracking processing and is used to detect various subprog calling conditions.This patch fixes the bug with incorrectly resetting
subseq_idxto -1 when going from child state to parent state during backtracking. If we don't maintain correctsubseq_idxwe can misidentify subprog calls leading to precision tracking bugs.[...]
Here is the summary with links:
- [bpf-next] bpf: fix calculation of subseq_idx during precision backtracking
https://git.kernel.org/bpf/bpf-next/c/d84b1a6708ee
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html