Compare stack frames in exact register states
Subsystems (4)
Kumar Kartikeya Dwivedi
maintainerv3 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 selftest keeps a stack pointer live in a register across a loop whose only change at the header is the pointer's frame number. On the unfixed tree, the program is rejected with "infinite loop detected". With the fix, it loads and returns the expected value.
Changelog:
----------
v2 -> v3
v2: https://lore.kernel.org/bpf/[email protected]
* Rebase on bpf/master.
* Drop the redundant spilled-pointer test, since existing tests already cover the stacksafe() -> regsafe() path. (Eduard)
* Place asm labels on their own line in the selftest. (Eduard)
* Collect Acked-by and Tested-by tags.
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 | 36 +++++++++++++++++++ 3 files changed, 46 insertions(+), 13 deletions(-)
base-commit: b4e875d397da451fb4e9c573ff4b86db53caba05
Signature · 1 line
2.53.0
Kumar Kartikeya Dwivedi
maintainerPATCH v3 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.
--- 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
@@ -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
@@ -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
[email protected]
AI reviewRe: [PATCH bpf v3 1/2] bpf: Compare stack frames in regs_exact()
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] bpf: Out-of-bounds array read in bpf_func() due to frameno aliasing --
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] bpf: Out-of-bounds array read in bpf_func() due to frameno aliasing --
commit e17b850ba98b74f1dac193b96d8c0646c06a22d0
Author: Kumar Kartikeya Dwivedi <[email protected]>
bpf: Compare stack frames in regs_exact()
This commit moves frameno into the type-specific metadata union, ahead of id, to compare stack frames in regs_exact(). It also moves the states_maybe_looping() boundary from frameno to precise.
Quoted 6 lines
include/linux/bpf_verifier.h +0
-0@@ -45,6 +45,14 @@ struct bpf_reg_state {union {
include/linux/bpf_verifier.h struct bpf_reg_state { · line 55
Quoted 10 lines
include/linux/bpf_verifier.h +8
-0/* 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;
[Severity: High]
Does moving frameno into this union cause an out-of-bounds array read in bpf_func()?
For non-stack registers (like PTR_TO_MAP_VALUE), frameno will now contain arbitrary aliased bytes (such as the lowest byte of a map address).
In kernel/bpf/verifier.c, functions like get_constant_map_key() and process_iter_arg() call bpf_func() unconditionally before verifying the register is a stack pointer:
kernel/bpf/verifier.c:get_constant_map_key() {
...
struct bpf_func_state *state = bpf_func(env, key);
...
if (key->type != PTR_TO_STACK)
return -EOPNOTSUPP;
...
}bpf_func() evaluates env->cur_state->frame[reg->frameno]:
include/linux/bpf_verifier.h:bpf_func() {
struct bpf_verifier_state *cur = env->cur_state;
return cur->frame[reg->frameno];
}If a BPF program passes a non-stack register as an argument, and frameno evaluates to a large value (e.g. 255) due to aliasing, it indexes far outside the frame array, causing an out-of-bounds read and potential KASAN panics during program verification.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf v3 1/2] bpf: Compare stack frames in regs_exact()
Quoted 58 lines · sashiko-bot
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] bpf: Out-of-bounds array read inbpf_func()due to frameno aliasing --commit
e17b850ba98b74f1dac193b96d8c0646c06a22d0
Author: Kumar Kartikeya Dwivedi <[email protected]>bpf: Compare stack frames in
regs_exact()This commit moves frameno into the type-specific metadata union, ahead of id, to compare stack frames in
regs_exact(). It also moves thestates_maybe_looping()boundary from frameno to precise.Quoted 6 lines
include/linux/bpf_verifier.h +0
-0@@ -45,6 +45,14 @@ struct bpf_reg_state {union {include/linux/bpf_verifier.h struct bpf_reg_state { · line 55
Quoted 10 lines
include/linux/bpf_verifier.h +8
-0/* 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;[Severity: High]
Does moving frameno into this union cause an out-of-bounds array read inbpf_func()?For non-stack registers (like
PTR_TO_MAP_VALUE), frameno will now contain arbitrary aliased bytes (such as the lowest byte of a map address).In
kernel/bpf/verifier.c, functions likeget_constant_map_key()andprocess_iter_arg()callbpf_func()unconditionally before verifying the register is a stack pointer:kernel/bpf/verifier.c:get_constant_map_key() { ... struct bpf_func_state *state = bpf_func(env, key); ... if (key->type != PTR_TO_STACK) return -EOPNOTSUPP; ... }
bpf_func()evaluates env->cur_state->frame[reg->frameno]:include/linux/bpf_verifier.h:bpf_func() { struct bpf_verifier_state *cur = env->cur_state; return cur->frame[reg->frameno]; }
Quoted 4 lines
If a BPF program passes a non-stack register as an argument, and frameno evaluates to a large value (e.g. 255) due to aliasing, it indexes far outside the frame array, causing an out-of-bounds read and potential KASAN panics during program verification.
This seems correct, will fix.
Kumar Kartikeya Dwivedi
maintainerPATCH v3 2/2 selftests/bpf: Cover frame changes in bounded loops
In reply to Kumar Kartikeya DwivediAdd a finite loop whose progress is represented only by changing the frame number of a stack pointer. The 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.
Force frequent checkpoints so the test exercises infinite-loop detection, and check that the program returns one when run.
Without the frameno comparison in regs_exact(), the program is rejected with an "infinite loop detected" diagnostic instead of loading successfully.
--- .../selftests/bpf/progs/verifier_loops1.c | 36 +++++++++++++++++++ 1 file changed, 36 insertions(+)
tools/testing/selftests/bpf/progs/verifier_loops1.c +36 -0
@@ -303,4 +303,40 @@ __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) +{ + asmvolatile ( +"*(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) +{ + asmvolatile ( +"*(u64 *)(r10 - 8) = 0;" +"r1 = r10;" +"r1 += -8;" +"call loop_stack_frames_reg;" +"exit;" + ::: __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.53.0
[email protected]
AI reviewRe: [PATCH bpf v3 2/2] selftests/bpf: Cover frame changes in bounded loops
This isn't a bug, but the subject says "Cover frame changes in bounded loops" (plural) and the test name ends with "_reg", which reads as one half of a pair. The verifier fix this accompanies…
Quoted 35 lines
tools/testing/selftests/bpf/progs/verifier_loops1.c +27
-0@@ -303,4 +303,40 @@ __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) +{ + asmvolatile ( +"*(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) +{
tools/testing/selftests/bpf/progs/verifier_loops1.c __naked void maybe_exit_scc_bug1(void) · line 342
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_loops1.c +9
-0+ asmvolatile ( +"*(u64 *)(r10 - 8) = 0;" +"r1 = r10;" +"r1 += -8;" +"call loop_stack_frames_reg;" +"exit;" + ::: __clobber_all); +} + char _license[] SEC("license") = "GPL";
This isn't a bug, but the subject says "Cover frame changes in bounded loops" (plural) and the test name ends with "_reg", which reads as one half of a pair. The verifier fix this accompanies (ccf21c431c086) explicitly notes "The same problem occurs when the pointer is spilled to the stack", and that spilled case goes through stacksafe() -> regsafe() -> regs_exact() on spilled_ptr - a different comparison entry point than the register case covered here.
Would it be worth adding the spilled-pointer variant too, so the spilled_ptr path through regs_exact() is covered as well?
---
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/35410977924