Skip to contentSkip to conversation

Compare stack frames in exact register states

PATCH Superseded Kumar Kartikeya Dwivedi 2 participants 5 messages Sep 18

Subsystems (4)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Kumar Kartikeya Dwivedi

author maintainer
#0 lore raw

v2 cover Compare stack frames in exact register states

regs_exact() compares register values and their ID relationships, but it does not compare frameno. regsafe() checks frameno for ordinary PTR_TO_STACK comparisons, while its EXACT path returns through regs_exact() before reaching that check. Infinite-loop detection can therefore mistake pointers to the same offset in different stack frames for the same pointer and reject a finite loop.

Move frameno into bpf_reg_state's type-specific metadata union so the existing regs_exact() prefix comparison covers it. This avoids a separate PTR_TO_STACK case and keeps the structure at 80 bytes. Adjust the states_maybe_looping() comparison boundary for the new layout.

The selftests cover both a live register and a spilled stack pointer. On the unfixed tree, both programs are rejected with "infinite loop detected". With the fix, both load and return the expected value.

Changelog:
----------
v1 -> v2
v1: https://lore.kernel.org/bpf/[email protected]

* Rebase on bpf/master.
* Move frameno into the type-specific metadata union so regs_exact()'s existing prefix comparison covers it without growing bpf_reg_state.

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

 include/linux/bpf_verifier.h                  | 16 ++---
 kernel/bpf/states.c                           |  7 +-
 .../selftests/bpf/progs/verifier_loops1.c     | 70 +++++++++++++++++++
 3 files changed, 80 insertions(+), 13 deletions(-)

base-commit: 3b8e5d9f2ed7abf18ebe63b7a6a4a64e1a9c2203

Signature · 1 line
2.53.0
author maintainer
#1 lore raw

PATCH v2 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.

Move frameno into the type-specific metadata union, ahead of id, so the existing prefix comparison in regs_exact() covers it. Ordinary stack pointers do not use another union member. Iterator and IRQ stack-slot states use their dedicated union views and do not need a frame lookup. This also keeps bpf_reg_state at 80 bytes.

Move the states_maybe_looping() boundary from frameno to precise after the field relocation. Its prefix comparison continues to cover the complete value state and now includes frameno.

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")
---
 include/linux/bpf_verifier.h | 16 ++++++++--------
 kernel/bpf/states.c          |  7 ++-----
 2 files changed, 10 insertions(+), 13 deletions(-)
include/linux/bpf_verifier.h +8 -8
index a7202b44ab10..17be5f7df35a 100644
@@ -45,6 +45,14 @@ struct bpf_reg_state {
 	union {
 		/* valid when type == PTR_TO_PACKET */
 		int range;
+		/*
+		 * Inside the callee two registers can be both PTR_TO_STACK like
+		 * R1=fp-8 and R2=fp-8, but one of them points to this function stack
+		 * while another to the caller's stack. To differentiate them 'frameno'
+		 * is used which is an index in bpf_verifier_state->frame[] array
+		 * pointing to bpf_func_state.
+		 */
+		u8 frameno;
 
 		/*
 		 * For CONST_PTR_TO_MAP, PTR_TO_MAP_KEY, PTR_TO_MAP_VALUE and
@@ -155,14 +163,6 @@ struct bpf_reg_state {
 	 * during state comparisons.
 	 */
 	u32 map_uid;
-	/*
-	 * Inside the callee two registers can be both PTR_TO_STACK like
-	 * R1=fp-8 and R2=fp-8, but one of them points to this function stack
-	 * while another to the caller's stack. To differentiate them 'frameno'
-	 * is used which is an index in bpf_verifier_state->frame[] array
-	 * pointing to bpf_func_state.
-	 */
-	u8 frameno;
 	/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
 	bool precise;
 };
kernel/bpf/states.c +2 -5
index e4ec007f7fa6..012b82513a3b 100644
@@ -644,10 +644,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:
@@ -1126,7 +1123,7 @@ static bool states_maybe_looping(struct bpf_verifier_state *old,
 	fcur = cur->frame[fr];
 	for (i = 0; i < MAX_BPF_REG; i++)
 		if (memcmp(&fold->regs[i], &fcur->regs[i],
-			   offsetof(struct bpf_reg_state, frameno)))
+			   offsetof(struct bpf_reg_state, precise)))
 			return false;
 	return true;
 }
Signature · 1 line
2.53.0
maintainer Acked-by on v2 1/2
#2 lore raw

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

Quoted 39 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.

Move frameno into the type-specific metadata union, ahead of id, so the existing prefix comparison in regs_exact() covers it. Ordinary stack pointers do not use another union member. Iterator and IRQ stack-slot states use their dedicated union views and do not need a frame lookup. This also keeps bpf_reg_state at 80 bytes.

Move the states_maybe_looping() boundary from frameno to precise after the field relocation. Its prefix comparison continues to cover the complete value state and now includes frameno.

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")

---

...

author maintainer
#3 lore raw

PATCH v2 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     | 70 +++++++++++++++++++
 1 file changed, 70 insertions(+)
tools/testing/selftests/bpf/progs/verifier_loops1.c +70 -0
index d248ce877f14..ada7e1105a95 100644
@@ -303,4 +303,74 @@ __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
maintainer Tested-by on v2 2/2
#4 lore raw

Re: [PATCH bpf v2 2/2] selftests/bpf: Cover frame changes in bounded loops

Quoted 10 lines · 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.

Quoted 6 lines

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

---

Quoted 12 lines
 .../selftests/bpf/progs/verifier_loops1.c     | 70 +++++++++++++++++++
 1 file changed, 70 insertions(+)
tools/testing/selftests/bpf/progs/verifier_loops1.c +1 -0
index d248ce877f14..ada7e1105a95 100644
@@ -303,4 +303,74 @@ __naked void maybe_exit_scc_bug1(void)
 	::: __clobber_all);
 }
 
+/*

tools/testing/selftests/bpf/progs/verifier_loops1.c __naked void maybe_exit_scc_bug1(void) · line 316

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_loops1.c +10 -0
+ * 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);"

Nit: please use formatting as below:

"1:"

	"r0 = *(u64 *)(r1 + 0);"
Quoted 12 lines
tools/testing/selftests/bpf/progs/verifier_loops1.c +12 -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)

tools/testing/selftests/bpf/progs/verifier_loops1.c __naked void maybe_exit_scc_bug1(void) · line 338

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_loops1.c +10 -0
+__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);
+}

--- 8< ---

Quoted 27 lines
tools/testing/selftests/bpf/progs/verifier_loops1.c +27 -0
+/*
+ * 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)
+{

tools/testing/selftests/bpf/progs/verifier_loops1.c __naked void maybe_exit_scc_bug1(void) · line 376

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_loops1.c +9 -0
+	asm volatile (
+	"*(u64 *)(r10 - 8) = 0;"
+	"r1 = r10;"
+	"r1 += -8;"
+	"call loop_stack_frames_spill;"
+	"exit;"
+	::: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";

I think this test is redundant, existing tests should already cover the chain stack_safe -> regsafe.

--- >8 ---