Skip to contentSkip to conversation

bpf: Compare stack frames in exact register states

PATCH Superseded Kumar Kartikeya Dwivedi 3 participants 6 messages Sep 14

Subsystems (3)

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Kumar Kartikeya Dwivedi

author maintainer
#0 lore raw

cover bpf: Compare stack frames in exact register states

regs_exact() compares the value-bearing portion of bpf_reg_state and its IDs, but excludes frameno. regsafe() compensates for that omission in its PTR_TO_STACK case. An EXACT comparison returns through regs_exact() before reaching that case, however, so infinite-loop detection can equate pointers to the same offset in different stack frames.

A finite loop can expose the problem by first reading zero from fp-8 in its caller, then changing its pointer to fp-8 in the callee, where the slot holds one. The current verifier reports an infinite loop at the second visit even though the next load makes the loop exit. A spilled pointer has the same problem.

Include frameno in regs_exact() so every caller observes it. Keep precise
excluded: a precision mark records whether pruning may
ignore scalar ranges, while exact comparison already compares those ranges unconditionally. Precision marks can also change through backtracking while an ancestor state is still active.

The second patch adds register and spill variants of the finite loop. Both are rejected with "infinite loop detected" before the fix and pass after it.

Kumar Kartikeya Dwivedi (2):
bpf: Compare stack frames in regs_exact() selftests/bpf: Cover frame changes in bounded loops

 kernel/bpf/states.c                           |  8 +--
 .../selftests/bpf/progs/verifier_loops1.c     | 66 +++++++++++++++++++
 2 files changed, 69 insertions(+), 5 deletions(-)

base-commit: ee363e055895364039bf28348ff13c615afad4ba

Signature · 1 line
2.53.0
author maintainer
#1 lore raw

PATCH 1/2 bpf: Compare stack frames in regs_exact()

regs_exact() compares the register state up to id, followed by the ID mappings, but does not compare frameno. The PTR_TO_STACK case in regsafe() checks frameno separately, which is bypassed when exact comparison is requested. Consequently, infinite-loop detection can treat pointers to different stack frames as the same pointer and reject a finite loop.

For example, initialize fp-8 to zero in the caller and to one in the callee, then pass the caller's fp-8 to the callee as r1:

    loop:
        r0 = *(u64 *)(r1 + 0);
        if r0 != 0 goto done;
        r1 = r10;
        r1 += -8;
        goto loop;
    done:
        exit;

The loop terminates after reading the callee's slot on its second iteration. At the loop header, however, the only relevant difference is r1's frameno, so exact comparison incorrectly reports an infinite loop. The same problem occurs when the pointer is spilled to the stack.

Include frameno in regs_exact() so both exact and ordinary stack-pointer comparisons enforce it. The field stays zero for other register types.

Continue to ignore precise. Precision marks control whether pruning may ignore scalar ranges; they do not change the represented values, and exact comparison already compares those ranges unconditionally. Marks can also change through backtracking while an ancestor state is still being explored.

Fixes d5b892fd607a ("bpf: make infinite loop detection in is_state_visited() exact")
---
 kernel/bpf/states.c | 8 +++-----
 1 file changed, 3 insertions(+), 5 deletions(-)
kernel/bpf/states.c +3 -5
index 66fb11b6c6a7..827038ec18b7 100644
@@ -491,7 +491,8 @@ static bool regs_exact(const struct bpf_reg_state *rold,
 {
 	return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
 	       check_ids(rold->id, rcur->id, idmap) &&
-	       check_ids(rold->parent_id, rcur->parent_id, idmap);
+	       check_ids(rold->parent_id, rcur->parent_id, idmap) &&
+	       rold->frameno == rcur->frameno;
 }
 
 enum exact_level {
@@ -639,10 +640,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		return range_within(rold, rcur) &&
 		       tnum_in(rold->var_off, rcur->var_off);
 	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 regs_exact(rold, rcur, idmap) && rold->frameno == rcur->frameno;
+		return regs_exact(rold, rcur, idmap);
 	case PTR_TO_ARENA:
 		return true;
 	case PTR_TO_INSN:
Signature · 1 line
2.53.0
maintainer
#2 lore raw

Re: [PATCH bpf v1 1/2] bpf: Compare stack frames in regs_exact()

Quoted 32 lines · Kumar Kartikeya Dwivedi

regs_exact() compares the register state up to id, followed by the ID mappings, but does not compare frameno. The PTR_TO_STACK case in regsafe() checks frameno separately, which is bypassed when exact comparison is requested. Consequently, infinite-loop detection can treat pointers to different stack frames as the same pointer and reject a finite loop.

For example, initialize fp-8 to zero in the caller and to one in the callee, then pass the caller's fp-8 to the callee as r1:

    loop:
        r0 = *(u64 *)(r1 + 0);
        if r0 != 0 goto done;
        r1 = r10;
        r1 += -8;
        goto loop;
    done:
        exit;

The loop terminates after reading the callee's slot on its second iteration. At the loop header, however, the only relevant difference is r1's frameno, so exact comparison incorrectly reports an infinite loop. The same problem occurs when the pointer is spilled to the stack.

Include frameno in regs_exact() so both exact and ordinary stack-pointer comparisons enforce it. The field stays zero for other register types.

Continue to ignore precise. Precision marks control whether pruning may ignore scalar ranges; they do not change the represented values, and exact comparison already compares those ranges unconditionally. Marks can also change through backtracking while an ancestor state is still being explored.

Quoted 4 lines
Fixes d5b892fd607a ("bpf: make infinite loop detection in is_state_visited() exact")

---

I'm going to land '[PATCH bpf v3 0/7] Misc bug fixes - part 5', which would be in conflict with this one.
After that, could you please respin, but try to move frameno inside the bpf_reg_state's union or near the delta field?

...

author maintainer
#3 lore raw

Re: [PATCH bpf v1 1/2] bpf: Compare stack frames in regs_exact()

Quoted 38 lines · Eduard Zingerman
Quoted 32 lines · Kumar Kartikeya Dwivedi

regs_exact() compares the register state up to id, followed by the ID mappings, but does not compare frameno. The PTR_TO_STACK case in regsafe() checks frameno separately, which is bypassed when exact comparison is requested. Consequently, infinite-loop detection can treat pointers to different stack frames as the same pointer and reject a finite loop.

For example, initialize fp-8 to zero in the caller and to one in the callee, then pass the caller's fp-8 to the callee as r1:

    loop:
        r0 = *(u64 *)(r1 + 0);
        if r0 != 0 goto done;
        r1 = r10;
        r1 += -8;
        goto loop;
    done:
        exit;

The loop terminates after reading the callee's slot on its second iteration. At the loop header, however, the only relevant difference is r1's frameno, so exact comparison incorrectly reports an infinite loop. The same problem occurs when the pointer is spilled to the stack.

Include frameno in regs_exact() so both exact and ordinary stack-pointer comparisons enforce it. The field stays zero for other register types.

Continue to ignore precise. Precision marks control whether pruning may ignore scalar ranges; they do not change the represented values, and exact comparison already compares those ranges unconditionally. Marks can also change through backtracking while an ancestor state is still being explored.

Quoted 4 lines
Fixes d5b892fd607a ("bpf: make infinite loop detection in is_state_visited() exact")

---

Quoted 6 lines

I'm going to land '[PATCH bpf v3 0/7] Misc bug fixes - part 5', which would be in conflict with this one.
After that, could you please respin, but try to move frameno inside the bpf_reg_state's union or near the delta field?

...

Makes sense, will do.

#4 lore raw

Re: [PATCH bpf v1 1/2] bpf: Compare stack frames in regs_exact()

In reply to Kumar Kartikeya Dwivedi
The frameno comparison is moved into regs_exact(), but regs_exact() is not PTR_TO_STACK-specific. It is called from two other places:

kernel/bpf/states.c static bool regs_exact(const struct bpf_reg_state *rold, · line 496

Quoted 12 lines
kernel/bpf/states.c +2 -1
index 66fb11b6c6a76..827038ec18b7a 100644
@@ -491,7 +491,8 @@ static bool regs_exact(const struct bpf_reg_state *rold,
 {
 	return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
 	       check_ids(rold->id, rcur->id, idmap) &&
-	       check_ids(rold->parent_id, rcur->parent_id, idmap);
+	       check_ids(rold->parent_id, rcur->parent_id, idmap) &&
+	       rold->frameno == rcur->frameno;
 }

The frameno comparison is moved into regs_exact(), but regs_exact() is not PTR_TO_STACK-specific. It is called from two other places:

states.c:509 if (exact == EXACT)

                       return regs_exact(rold, rcur, idmap);

states.c:650 default:

                       return regs_exact(rold, rcur, idmap);

The change depends on frameno staying zero for non-stack register types, as the changelog states. Can that invariant actually be maintained?

Looking at bpf_reg_state.frameno writes, there is exactly one assignment:

verifier.c:2284 regs[BPF_REG_FP].frameno = state->frameno;

and one clearing mechanism, the memset in
bpf_mark_reg_unknown_imprecise():

verifier.c:2193 void bpf_mark_reg_unknown_imprecise(struct bpf_reg_state *reg)

                 { memset(reg, 0, sizeof(*reg)); ... }

The other reset helper does NOT clear frameno, and deliberately clears only id and parent_id:

verifier.c:1860 static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)

                 {
                         /* Clear off and union(map_ptr, range) */
                         memset(((u8 *)reg) + sizeof(reg->type), 0,
                                offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
                         reg->id = 0;
                         reg->parent_id = 0;
                         ___mark_reg_known(reg, imm);
                 }

So any site that turns a register into a non-stack pointer with mark_reg_known_zero() followed by a type assignment carries over whatever frameno the register previously held. Is mark_btf_ld_reg() this shape?

verifier.c:2249 case PTR_TO_BTF_ID:

                         mark_reg_known_zero(env, regs, regno);
                         regs[regno].type = PTR_TO_BTF_ID | flag;

And the LDX destination is not cleared before that:

verifier.c:6666 err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);

Concrete path inside any subprogram (frameno == 1):

if r7 == 0 goto L1
r1 = r10 /* PTR_TO_STACK, frameno = 1 */
goto L2
L1: r1 = 0 /* DST_OP -> mark_reg_unknown -> memset -> frameno = 0 */
L2: r1 = *(u64 *)(r6 + 0) /* r6 is PTR_TO_BTF_ID; check_ptr_to_btf_access() ->
mark_btf_ld_reg(PTR_TO_BTF_ID) -> frameno survives */
... common tail using r1 ...

At the join point r1 is PTR_TO_BTF_ID with frameno == 1 on one path and frameno == 0 on the other. frameno is meaningless for PTR_TO_BTF_ID, yet regsafe()'s default: arm now rejects the pair. Before this patch regs_exact() ignored frameno there and the states pruned.

This is a pruning regression. The change is monotonically stricter, and the states_equal(..., EXACT) call sits inside if (sl->state.branches) whose every exit is goto miss, so a failed exact compare never falls through to pruning. The patch cannot cause an infinite loop to be accepted. The cost is duplicate state exploration, which for a program near the complexity limit turns a loadable program into one rejected as too complex.

Could frameno be kept in the PTR_TO_STACK arm of regsafe() and also added to the exact == EXACT early return? Or could frameno be normalized in __mark_reg_known() alongside id and parent_id?

[ ... ]

kernel/bpf/states.c static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, · line 646

Quoted 12 lines
kernel/bpf/states.c +1 -4
@@ -639,10 +640,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		return range_within(rold, rcur) &&
 		       tnum_in(rold->var_off, rcur->var_off);
 	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 regs_exact(rold, rcur, idmap) && rold->frameno == rcur->frameno;
+		return regs_exact(rold, rcur, idmap);
 	case PTR_TO_ARENA:
 		return true;
 	case PTR_TO_INSN:

[ ... ]

Regarding the commit message:

Quoted 2 lines

Include frameno in regs_exact() so both exact and ordinary stack-pointer comparisons enforce it. The field stays zero for other register types.

Is "The field stays zero for other register types" accurate?

bpf_reg_state.frameno is written in exactly one place (verifier.c:2284, R10 in init_reg_state()) and is only cleared as a side effect of the memset in bpf_mark_reg_unknown_imprecise() (verifier.c:2193).

__mark_reg_known() clears id and parent_id explicitly but leaves frameno alone (verifier.c:1860-1868), so mark_btf_ld_reg()'s PTR_TO_BTF_ID arm (verifier.c:2249-2253) produces a register with a stale non-zero frameno whenever the LDX destination previously held a stack pointer.

Non-stack register types do not keep frameno at zero. frameno is unmaintained for them, and only PTR_TO_STACK ever reads it.

Should the changelog either drop this claim and state the pruning consequence, or should the patch establish the invariant it asserts?

Also, Eduard Zingerman requested in the v1 review that frameno should be moved inside the bpf_reg_state's union or near the delta field for better struct layout. You agreed to make this change but it has not been implemented yet.

The v1 review comment:
https://lore.kernel.org/bpf/[email protected]/

Eduard wrote: "After that, could you please respin, but try to move frameno inside the bpf_reg_state's union or near the delta field?"

Currently, frameno is still at the end of the struct after parent_id, not inside the union or near delta. Are you planning to make this change?

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/34868467454

author maintainer
#5 lore raw

PATCH 2/2 selftests/bpf: Cover frame changes in bounded loops

In reply to Kumar Kartikeya Dwivedi

Add two finite loops whose progress is represented only by changing the frame number of a stack pointer. Each loop first reads zero from the caller's stack, switches to the same offset in the callee's stack, and exits after reading one on its next iteration.

Keep the pointer in a register in one test and spill it in the other to exercise both regsafe() and stacksafe() during exact state comparison. Force frequent checkpoints so the tests exercise infinite-loop detection, and check that both programs return one when run.

Without the frameno comparison in regs_exact(), both programs are rejected with an "infinite loop detected" diagnostic instead of loading successfully.

---
 .../selftests/bpf/progs/verifier_loops1.c     | 66 +++++++++++++++++++
 1 file changed, 66 insertions(+)
tools/testing/selftests/bpf/progs/verifier_loops1.c +66 -0
index d248ce877f14..f8b7ba1bf6b8 100644
@@ -303,4 +303,70 @@ __naked void maybe_exit_scc_bug1(void)
 	::: __clobber_all);
 }
 
+/*
+ * The loop reads zero from the caller's stack on its first iteration and
+ * one from the callee's stack on its second iteration. At the loop header,
+ * only the frame number of the pointer in r1 changes.
+ */
+static __naked __noinline __used
+void loop_stack_frames_reg(void)
+{
+	asm volatile ("*(u64 *)(r10 - 8) = 1;"
+	"1: r0 = *(u64 *)(r1 + 0);"
+	"if r0 != 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"goto 1b;"
+	"2: exit;"
+	::: __clobber_all);
+}
+
+SEC("xdp")
+__description("bounded loop changing stack frame in a register")
+__success __retval(1)
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void bounded_loop_stack_frames_reg(void)
+{
+	asm volatile ("*(u64 *)(r10 - 8) = 0;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call loop_stack_frames_reg;"
+	"exit;"
+	::: __clobber_all);
+}
+
+/*
+ * Exercise the same frame change through a spilled pointer. All registers
+ * at the loop header are identical, while fp-16 points to a different frame.
+ */
+static __naked __noinline __used
+void loop_stack_frames_spill(void)
+{
+	asm volatile ("*(u64 *)(r10 - 8) = 1;"
+	"*(u64 *)(r10 - 16) = r1;"
+	"1: r1 = *(u64 *)(r10 - 16);"
+	"r0 = *(u64 *)(r1 + 0);"
+	"if r0 != 0 goto 2f;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"*(u64 *)(r10 - 16) = r1;"
+	"goto 1b;"
+	"2: exit;"
+	::: __clobber_all);
+}
+
+SEC("xdp")
+__description("bounded loop changing stack frame in a spill")
+__success __retval(1)
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void bounded_loop_stack_frames_spill(void)
+{
+	asm volatile ("*(u64 *)(r10 - 8) = 0;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call loop_stack_frames_spill;"
+	"exit;"
+	::: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.53.0