bpf: Fix sync_linked_regs regarding BPF_ADD_CONST32 zext propagation
Subsystems (4)
Daniel Borkmann
maintainerPATCH 1/2 bpf: Fix sync_linked_regs regarding BPF_ADD_CONST32 zext propagation
Jenny reported that in sync_linked_regs() the BPF_ADD_CONST32 flag is checked on known_reg (the register narrowed by a conditional branch) instead of reg (the linked target register created by an alu32 operation).
Example case with reg:
1. r6 = bpf_get_prandom_u32()
2. r7 = r6 (linked, same id)
3. w7 += 5 (alu32 -- r7 gets BPF_ADD_CONST32, zero-extended by CPU)
4. if w6 < 0xFFFFFFFC goto safe (narrows r6 to [0xFFFFFFFC, 0xFFFFFFFF])
5. sync_linked_regs() propagates to r7 but does NOT call zext_32_to_64()
6. Verifier thinks r7 is [0x100000001, 0x100000004] instead of [1, 4]
Since known_reg above does not have BPF_ADD_CONST32 set above, zext_32_to_64() is never called on alu32-derived linked registers. This causes the verifier to track incorrect 64-bit bounds, while the CPU correctly zero-extends the 32-bit result.
The code checking known_reg->id was correct however (see scalars_alu32_wrap selftest case), but the real fix needs to handle both directions - zext propagation should be done when either register has BPF_ADD_CONST32, since the linked relationship involves a 32-bit operation regardless of which side has the flag.
Example case with known_reg (exercised also by scalars_alu32_wrap):
1. r1 = r0; w1 += 0x100 (alu32 -- r1 gets BPF_ADD_CONST32)
2. if r1 > 0x80 - known_reg = r1 (has BPF_ADD_CONST32), reg = r0 (doesn't)
Hence, fix it by checking for (reg->id | known_reg->id) & BPF_ADD_CONST32.
Moreover, sync_linked_regs() also has a soundness issue when two linked registers used different ALU widths: one with BPF_ADD_CONST32 and the other with BPF_ADD_CONST64. The delta relationship between linked registers assumes the same arithmetic width though. When one register went through alu32 (CPU zero-extends the 32-bit result) and the other went through alu64 (no zero-extension), the propagation produces incorrect bounds.
Example:
r6 = bpf_get_prandom_u32() // fully unknown
if r6 >= 0x100000000 goto out // constrain r6 to [0, U32_MAX] r7 = r6
w7 += 1 // alu32: r7.id = N | BPF_ADD_CONST32
r8 = r6
r8 += 2 // alu64: r8.id = N | BPF_ADD_CONST64
if r7 < 0xFFFFFFFF goto out // narrows r7 to [0xFFFFFFFF, 0xFFFFFFFF]
At the branch on r7, sync_linked_regs() runs with known_reg=r7 (BPF_ADD_CONST32) and reg=r8 (BPF_ADD_CONST64). The delta path computes:
r8 = r7 + (delta_r8 - delta_r7) = 0xFFFFFFFF + (2 - 1) = 0x100000000
Then, because known_reg->id has BPF_ADD_CONST32, zext_32_to_64(r8) is called, truncating r8 to [0, 0]. But r8 used a 64-bit ALU op -- the CPU does NOT zero-extend it. The actual CPU value of r8 is 0xFFFFFFFE + 2 = 0x100000000, not 0. The verifier now underestimates r8's 64-bit bounds, which is a soundness violation.
Fix sync_linked_regs() by skipping propagation when the two registers have mixed ALU widths (one BPF_ADD_CONST32, the other BPF_ADD_CONST64).
Lastly, fix regsafe() used for path pruning: the existing checks used "& BPF_ADD_CONST" to test for offset linkage, which treated BPF_ADD_CONST32 and BPF_ADD_CONST64 as equivalent.
--- kernel/bpf/verifier.c | 21 +++++++++++++++------ 1 file changed, 15 insertions(+), 6 deletions(-)
kernel/bpf/verifier.c +15 -6
@@ -17415,6 +17415,12 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_scontinue ;if ((reg->id & ~BPF_ADD_CONST ) != (known_reg->id & ~BPF_ADD_CONST ))continue ; +/* +* Skip mixed 32/64-bit links: the delta relationship doesn't +* hold across different ALU widths. +*/ +if (((reg->id ^ known_reg->id) &BPF_ADD_CONST ) ==BPF_ADD_CONST ) +continue ;if ((!(reg->id &BPF_ADD_CONST ) && !(known_reg->id &BPF_ADD_CONST )) || reg->off == known_reg->off) {s32 saved_subreg_def = reg->subreg_def;
@@ -17442,7 +17448,7 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_sscalar32_min_max_add (reg, &fake_reg);scalar_min_max_add (reg, &fake_reg); reg->var_off =tnum_add (reg->var_off, fake_reg.var_off); -if (known_reg->id &BPF_ADD_CONST32 ) +if ((reg->id | known_reg->id) &BPF_ADD_CONST32 )zext_32_to_64 (reg);reg_bounds_sync (reg); }
@@ -19870,11 +19876,14 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,* Also verify that new value satisfies old value range knowledge. */ -/* ADD_CONST mismatch: different linking semantics */ -if ((rold->id &BPF_ADD_CONST ) && !(rcur->id &BPF_ADD_CONST )) -return false; - -if (rold->id && !(rold->id &BPF_ADD_CONST ) && (rcur->id &BPF_ADD_CONST )) +/* +* ADD_CONST flags must match exactly: BPF_ADD_CONST32 and +* BPF_ADD_CONST64 have different linking semantics in +* sync_linked_regs() (alu32 zero-extends, alu64 does not), +* so pruning across different flag types is unsafe. +*/ +if (rold->id && + (rold->id &BPF_ADD_CONST ) != (rcur->id &BPF_ADD_CONST ))return false;/* Both have offset linkage: offsets must match */
Signature · 1 line
2.43.0
Daniel Borkmann
maintainerPATCH 2/2 selftests/bpf: Add a test cases for sync_linked_regs regarding zext propagation
Add multiple test cases for linked register tracking with alu32 ops:
- Add a test that checks sync_linked_regs() regarding reg->id (the linked
target register) for BPF_ADD_CONST32 rather than known_reg->id (the
branch register).- Add a test case for linked register tracking that exposes the cross-type
sync_linked_regs() bug. One register uses alu32 (w7 += 1, BPF_ADD_CONST32)
and another uses alu64 (r8 += 2, BPF_ADD_CONST64), both linked to the
same base register. - Add a test case that exercises regsafe() path pruning when two execution paths reach the same program point with linked registers carrying different ADD_CONST flags (BPF_ADD_CONST32 from alu32 vs BPF_ADD_CONST64 from alu64). This particular test passes with and without the fix since the pruning will fail due to different ranges, but it would still be useful to carry this one as a regression test for the unreachable div by zero.
With the fix applied all the tests pass:
# LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t verifier_linked_scalars [...]
./test_progs -t verifier_linked_scalars
#602/1 verifier_linked_scalars/scalars: find linked scalars:OK #602/2 verifier_linked_scalars/sync_linked_regs_preserves_id:OK #602/3 verifier_linked_scalars/scalars_neg:OK #602/4 verifier_linked_scalars/scalars_neg_sub:OK #602/5 verifier_linked_scalars/scalars_neg_alu32_add:OK #602/6 verifier_linked_scalars/scalars_neg_alu32_sub:OK #602/7 verifier_linked_scalars/scalars_pos:OK #602/8 verifier_linked_scalars/scalars_sub_neg_imm:OK #602/9 verifier_linked_scalars/scalars_double_add:OK #602/10 verifier_linked_scalars/scalars_sync_delta_overflow:OK #602/11 verifier_linked_scalars/scalars_sync_delta_overflow_large_range:OK #602/12 verifier_linked_scalars/scalars_alu32_big_offset:OK #602/13 verifier_linked_scalars/scalars_alu32_basic:OK #602/14 verifier_linked_scalars/scalars_alu32_wrap:OK #602/15 verifier_linked_scalars/scalars_alu32_zext_linked_reg:OK #602/16 verifier_linked_scalars/scalars_alu32_alu64_cross_type:OK #602/17 verifier_linked_scalars/scalars_alu32_alu64_regsafe_pruning:OK #602/18 verifier_linked_scalars/alu32_negative_offset:OK #602/19 verifier_linked_scalars/spurious_precision_marks:OK #602 verifier_linked_scalars:OK
Summary: 1/19 PASSED, 0 SKIPPED, 0 FAILED
--- .../bpf/progs/verifier_linked_scalars.c | 108 ++++++++++++++++++ 1 file changed, 108 insertions(+)
tools/testing/selftests/bpf/progs/verifier_linked_scalars.c +108 -0
@@ -348,6 +348,114 @@ l0_%=: \ : __clobber_all); } +/* +* Test that sync_linked_regs() checks reg->id (the linked target register) +* for BPF_ADD_CONST32 rather than known_reg->id (the branch register). +*/ +SEC("socket") +__success +__naked void scalars_alu32_zext_linked_reg (void ) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w6 = w0; /* r6 in [0, 0xFFFFFFFF] */ \ +r7 = r6; /* linked: same id as r6 */ \ +w7 += 1; /* alu32: r7.id |= BPF_ADD_CONST32 */ \ +r8 = 0xFFFFffff ll; \ +if r6 < r8 goto l0_%=; \ +/* r6 in [0xFFFFFFFF, 0xFFFFFFFF] */ \ +/* sync_linked_regs: known_reg=r6, reg=r7 */ \ +/* CPU: w7 = (u32)(0xFFFFFFFF + 1) = 0, zext -> r7 = 0 */ \ +/* With fix: r7 64-bit = [0, 0] (zext applied) */ \ +/* Without fix: r7 64-bit = [0x100000000] (no zext) */ \ +r7 >>= 32; \ +if r7 == 0 goto l0_%=; \ +r0 /= 0; /* unreachable with fix */ \ +l0_%=: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* Test that sync_linked_regs() skips propagation when one register used +* alu32 (BPF_ADD_CONST32) and the other used alu64 (BPF_ADD_CONST64). +* The delta relationship doesn't hold across different ALU widths. +*/ +SEC("socket") +__failure __msg("div by zero") +__naked void scalars_alu32_alu64_cross_type(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w6 = w0; /* r6 in [0, 0xFFFFFFFF] */ \ +r7 = r6; /* linked: same id as r6 */ \ +w7 += 1; /* alu32: BPF_ADD_CONST32, delta = 1 */ \ +r8 = r6; /* linked: same id as r6 */ \ +r8 += 2; /* alu64: BPF_ADD_CONST64, delta = 2 */ \ +r9 = 0xFFFFffff ll; \ +if r7 < r9 goto l0_%=; \ +/* r7 = 0xFFFFFFFF */ \ +/* sync: known_reg=r7 (ADD_CONST32), reg=r8 (ADD_CONST64) */ \ +/* Without fix: r8 = zext(0xFFFFFFFF + 1) = 0 */ \ +/* With fix: r8 stays [2, 0x100000001] (r8 >= 2) */ \ +if r8 > 0 goto l1_%=; \ +goto l0_%=; \ +l1_%=: \ +r0 /= 0; /* div by zero */ \ +l0_%=: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* Test that regsafe() prevents pruning when two paths reach the same program +* point with linked registers carrying different ADD_CONST flags (one +* BPF_ADD_CONST32 from alu32, another BPF_ADD_CONST64 from alu64). +*/ +SEC("socket") +__failure __msg("div by zero") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void scalars_alu32_alu64_regsafe_pruning(void) +{ + asmvolatile (" \ +call %[bpf_get_prandom_u32]; \ +w6 = w0; /* r6 in [0, 0xFFFFFFFF] */ \ +r7 = r6; /* linked: same id as r6 */ \ +/* Get another random value for the path branch */ \ +call %[bpf_get_prandom_u32]; \ +if r0 > 0 goto l_pathb_%=; \ +/* Path A: alu32 */ \ +w7 += 1; /* BPF_ADD_CONST32, delta = 1 */\ +goto l_merge_%=; \ +l_pathb_%=: \ +/* Path B: alu64 */ \ +r7 += 1; /* BPF_ADD_CONST64, delta = 1 */\ +l_merge_%=: \ +/* Merge point: regsafe() compares path B against cached path A. */ \ +/* Narrow r6 to trigger sync_linked_regs for r7 */ \ +r9 = 0xFFFFffff ll; \ +if r6 < r9 goto l0_%=; \ +/* r6 = 0xFFFFFFFF */ \ +/* sync: r7 = 0xFFFFFFFF + 1 = 0x100000000 */ \ +/* Path A: zext -> r7 = 0 */ \ +/* Path B: no zext -> r7 = 0x100000000 */ \ +r7 >>= 32; \ +if r7 == 0 goto l0_%=; \ +r0 /= 0; /* div by zero on path B */ \ +l0_%=: \ +r0 = 0; \ +exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + SEC("socket") __successvoid alu32_negative_offset (void )
Signature · 1 line
2.43.0
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:
Quoted 6 lines · On Thu, 19 Mar 2026 22:15:06 +0100 you wrote:
Jenny reported that in
sync_linked_regs()theBPF_ADD_CONST32flag is checked onknown_reg(the register narrowed by a conditional branch) instead of reg (the linked target register created by an alu32 operation).Example case with reg:
Quoted 8 lines
1. r6 =
bpf_get_prandom_u32()
2. r7 = r6 (linked, same id)
3. w7 += 5 (alu32 -- r7 getsBPF_ADD_CONST32, zero-extended by CPU)
4. if w6 <0xFFFFFFFCgoto safe (narrows r6 to [0xFFFFFFFC,0xFFFFFFFF])
5.sync_linked_regs()propagates to r7 but does NOT callzext_32_to_64()
6. Verifier thinks r7 is [0x100000001,0x100000004] instead of [1, 4][...]
Here is the summary with links:
- [bpf,1/2] bpf: Fix sync_linked_regs regarding BPF_ADD_CONST32 zext propagation
https://git.kernel.org/bpf/bpf/c/bc308be380c1 - [bpf,2/2] selftests/bpf: Add a test cases for sync_linked_regs regarding zext propagation https://git.kernel.org/bpf/bpf/c/4a04d13576fd
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html