* [PATCH bpf 1/2] bpf: backtrack_insn(): handle ld_{abs,ind} subprog exit edge
@ 2026-09-02 7:28 Eduard Zingerman
2026-09-02 7:28 ` [PATCH bpf 2/2] selftests/bpf: precision tracking across BPF_ABS subprog exit Eduard Zingerman
2026-09-02 14:10 ` [PATCH bpf 1/2] bpf: backtrack_insn(): handle ld_{abs,ind} subprog exit edge patchwork-bot+netdevbpf
0 siblings, 2 replies; 3+ messages in thread
From: Eduard Zingerman @ 2026-09-02 7:28 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, npc,
Eduard Zingerman
Nicholas Carlini reported a bug in precision backtracking mechanism
for BPF_LD | BPF_{IND,ABS} instructions. These instructions are
modelled as two branches:
- fallthrough;
- implicit exit from current subprogram.
The implicit exit case was not handled by the backtrack_insn()
function. When backtracking such a path backtrack_insn() did not call
bt_subprog_enter(), which meant that backtracking continued
manipulating precision marks in a caller frame, while looking at
instructions in a callee frame.
This lead to segmentation faults during verification
(see the selftest), or unsound state pruning.
Fixes: ee861486e377 ("bpf: Fix ld_{abs,ind} failure path analysis in subprogs")
Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/backtrack.c | 25 +++++++++++++++++++------
1 file changed, 19 insertions(+), 6 deletions(-)
diff --git a/kernel/bpf/backtrack.c b/kernel/bpf/backtrack.c
index a2b18a9f1694..eaf7438b9ebf 100644
--- a/kernel/bpf/backtrack.c
+++ b/kernel/bpf/backtrack.c
@@ -582,16 +582,29 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
*/
}
} else if (class == BPF_LD) {
- if (!bt_is_reg_set(bt, dreg))
- return 0;
- bt_clear_reg(bt, dreg);
/* It's ld_imm64 or ld_abs or ld_ind.
* For ld_imm64 no further tracking of precision
* into parent is necessary
*/
- if (mode == BPF_IND || mode == BPF_ABS)
- /* to be analyzed */
- return -ENOTSUPP;
+ if (mode == BPF_IMM) {
+ bt_clear_reg(bt, dreg);
+ return 0;
+ }
+ /*
+ * BPF_{IND,ABS} are modelled as two branches:
+ * - fallthrough;
+ * - implicit subprogram exit.
+ * It is necessary to switch current frame if
+ * implicit subprogram exit branch is backtracked.
+ */
+ if (mode == BPF_IND || mode == BPF_ABS) {
+ if (bt_is_reg_set(bt, dreg))
+ return -ENOTSUPP;
+ if (subseq_idx != idx + 1)
+ if (bt_subprog_enter(bt))
+ return -EFAULT;
+ return 0;
+ }
}
/* Propagate precision marks to linked registers, to account for
* registers marked as precise in this function.
--
2.53.0
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [PATCH bpf 2/2] selftests/bpf: precision tracking across BPF_ABS subprog exit
2026-09-02 7:28 [PATCH bpf 1/2] bpf: backtrack_insn(): handle ld_{abs,ind} subprog exit edge Eduard Zingerman
@ 2026-09-02 7:28 ` Eduard Zingerman
2026-09-02 14:10 ` [PATCH bpf 1/2] bpf: backtrack_insn(): handle ld_{abs,ind} subprog exit edge patchwork-bot+netdevbpf
1 sibling, 0 replies; 3+ messages in thread
From: Eduard Zingerman @ 2026-09-02 7:28 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, npc,
Eduard Zingerman
A test case checking that the verifier properly backtracks both
fallthrough and implicit subprogram exit paths modelled for
BPF_LD | BPF_ABS instruction.
Without the previous patch:
- the verifier did not call bt_subprog_enter() on the implicit
subprogram exit path;
- bpf_pseudo_call() branch in backtrack_insn() executed
'bpf_bt_set_frame_reg(bt, bt->frame - 1, i);' with bt->frame == 0;
- causing a segmentation fault.
Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
.../bpf/progs/verifier_subprog_precision.c | 51 ++++++++++++++++++++++
1 file changed, 51 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
index d21d32f6a676..e174a905c562 100644
--- a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
+++ b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
@@ -846,4 +846,55 @@ __naked int subprog_result_tail_call(void)
);
}
+__naked __noinline __used
+static int ld_abs_subprog(void)
+{
+ asm volatile (
+ "r6 = r1;"
+ "r7 = r1;"
+ ".8byte %[ld_abs];"
+ "exit;"
+ :
+ : __imm_insn(ld_abs, BPF_LD_ABS(BPF_W, 0))
+ : __clobber_all);
+}
+
+/*
+ * Buggy verifier did not properly backtrack early subprogram exit
+ * modelled for BPF_LD | BPF_ABS instruction, causing a segfault.
+ */
+SEC("socket")
+__success
+__log_level(2)
+/* early exit path */
+__msg("3: (0f) r1 += r7")
+__msg("mark_precise: frame0: regs=r7 stack= before 2: (bf) r1 = r10")
+__msg("mark_precise: frame0: regs=r7 stack= before 9: (20) r0 = *(u32 *)skb[0]")
+__msg("mark_precise: frame1: regs= stack= before 8: (bf) r7 = r1")
+__msg("mark_precise: frame1: regs= stack= before 7: (bf) r6 = r1")
+__msg("mark_precise: frame1: regs= stack= before 1: (85) call pc+5")
+__msg("mark_precise: frame0: regs=r7 stack= before 0: (b7) r7 = -8")
+/* fallthrough path */
+__msg("3: (0f) r1 += r7")
+__msg("mark_precise: frame0: regs=r7 stack= before 2: (bf) r1 = r10")
+__msg("mark_precise: frame0: regs=r7 stack= before 10: (95) exit")
+__msg("mark_precise: frame1: regs= stack= before 9: (20) r0 = *(u32 *)skb[0]")
+__msg("mark_precise: frame1: regs= stack= before 8: (bf) r7 = r1")
+__msg("mark_precise: frame1: regs= stack= before 7: (bf) r6 = r1")
+__msg("mark_precise: frame1: regs= stack= before 1: (85) call pc+5")
+__msg("mark_precise: frame0: regs=r7 stack= before 0: (b7) r7 = -8")
+__naked int ld_abs_backtrack_both_paths(void)
+{
+ asm volatile (
+ "r7 = -8;"
+ "call ld_abs_subprog;"
+ "r1 = r10;"
+ "r1 += r7;" /* mark r7 as precise */
+ "*(u64 *)(r1 + 0) = 0;"
+ "r0 = 0;"
+ "exit;"
+ ::: __clobber_all
+ );
+}
+
char _license[] SEC("license") = "GPL";
--
2.53.0
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH bpf 1/2] bpf: backtrack_insn(): handle ld_{abs,ind} subprog exit edge
2026-09-02 7:28 [PATCH bpf 1/2] bpf: backtrack_insn(): handle ld_{abs,ind} subprog exit edge Eduard Zingerman
2026-09-02 7:28 ` [PATCH bpf 2/2] selftests/bpf: precision tracking across BPF_ABS subprog exit Eduard Zingerman
@ 2026-09-02 14:10 ` patchwork-bot+netdevbpf
1 sibling, 0 replies; 3+ messages in thread
From: patchwork-bot+netdevbpf @ 2026-09-02 14:10 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
npc
Hello:
This series was applied to bpf/bpf.git (master)
by Daniel Borkmann <daniel@iogearbox.net>:
On Wed, 2 Sep 2026 00:28:34 -0700 you wrote:
> Nicholas Carlini reported a bug in precision backtracking mechanism
> for BPF_LD | BPF_{IND,ABS} instructions. These instructions are
> modelled as two branches:
> - fallthrough;
> - implicit exit from current subprogram.
>
> The implicit exit case was not handled by the backtrack_insn()
> function. When backtracking such a path backtrack_insn() did not call
> bt_subprog_enter(), which meant that backtracking continued
> manipulating precision marks in a caller frame, while looking at
> instructions in a callee frame.
>
> [...]
Here is the summary with links:
- [bpf,1/2] bpf: backtrack_insn(): handle ld_{abs,ind} subprog exit edge
https://git.kernel.org/bpf/bpf/c/387b1baefbb7
- [bpf,2/2] selftests/bpf: precision tracking across BPF_ABS subprog exit
https://git.kernel.org/bpf/bpf/c/ce6b9e5dd873
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2026-09-02 14:11 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-09-02 7:28 [PATCH bpf 1/2] bpf: backtrack_insn(): handle ld_{abs,ind} subprog exit edge Eduard Zingerman
2026-09-02 7:28 ` [PATCH bpf 2/2] selftests/bpf: precision tracking across BPF_ABS subprog exit Eduard Zingerman
2026-09-02 14:10 ` [PATCH bpf 1/2] bpf: backtrack_insn(): handle ld_{abs,ind} subprog exit edge patchwork-bot+netdevbpf
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox