Tests for the BPF_FLAG_SUBREG_SEXT link, mostly built with the
div-by-zero-guard idiom: the div is unreachable iff the verifier deduces the
sign-extended register is 0, so a missed deduction turns __success into a
"div by zero" rejection.
Deduction through the link:
- sext_linked_low_narrow_to_zero, sext_linked_separate_dest_narrow_to_zero:
in-place and dst != src sign extension narrowed to 0 via the source's low
32 bits. The separate-dest case runs with BPF_F_TEST_STATE_FREQ so the
link has to survive state cleaning.
- sext_narrow_{branch_on_source,copied_back,inplace_pre_copy,spill_fill}:
variants derived from real "R0 ... should have been in [0, 1]" exit
rejections -- branch on source vs dest, copy-back, spill/fill across a
call.
- sext_resext_preserves_range: a redundant re-sext of a value clamped to
[-4095, 0] must keep the tight range (the errno-or-zero return pattern).
In-loop behaviour:
- sext_in_loop_converges: convergence regression test, reproducing the
bytecode bpf-gcc emits for a cond_break loop -- a counter incremented with
an ALU32 add (zero-extending the high half) then sign-extended in place
every iteration. Forming the link refreshes the linked scalar id and
BPF_FLAG_SUBREG_SEXT each iteration, so the loop-carried state never
repeats. It converges only because regsafe() demands a matching low-32
link just when the old state already has one: ~9 insns with that, versus
a load failure at 1,000,001 insns without.
- sext_in_loop_separate_dest_index: the companion case, a fresh in-loop temp
(a bounds-checked array index) that is dead across the back-edge. The link
is formed here too -- there is no liveness or loop-carried exclusion, the
gate is just (sz == 4) -- but because the temp is not loop-carried the link
costs nothing in convergence and simply buys precision: the narrowing
reaches it.
Interaction with the zero-extending link:
- zext_mov_from_sext_src_zero_extends: a 32-bit zero-extending mov (w2 = w1)
whose source is sign-extended (r1 = (s32)r6) must still zero-extend, i.e.
its link must be BPF_FLAG_SUBREG_ZEXT and must not inherit
BPF_FLAG_SUBREG_SEXT from the source. Otherwise sync_linked_regs() rebuilds
the destination with reconstruct_sext32() on a later low-32 narrowing,
computing a negative value for what is really a large positive
zero-extended one. After "if w6 s>= 0" falls through, r6's low 32 bits have
bit 31 set, so the zero-extended r2 is strictly positive and the guarded
div is reachable only on a mis-reconstruction.
Two more cases the earlier tests did not reach:
- sext_mov_keeps_add_const_src: mirror of zext_mov_keeps_add_const_src. A
sext whose source carries an ADD_CONST delta must not destroy that link.
Fails without the ADD_CONST source exclusion in the previous patch.
- sext_dest_driven_does_not_narrow_base: narrows the LINKED register and
requires the wide base is NOT narrowed, i.e. the "known_reg is
subreg-linked" continue in sync_linked_regs(). A __failure test -- the
div must stay reachable. Companion to the zero-extend version added by
the zero-extend selftest patch.
All are written in asm so the bytecode is identical regardless of the host
BPF compiler.
Signed-off-by: Vineet Gupta <[email protected]>
---
.../bpf/progs/verifier_linked_scalars.c | 412 ++++++++++++++++++
1 file changed, 412 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
index 2cc6f9e45aff..ff71e168d4cc 100644
--- a/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
+++ b/tools/testing/selftests/bpf/progs/verifier_linked_scalars.c
@@ -826,4 +826,416 @@ l_out_%=:
\
: __clobber_all);
}
+/*
+ * The tests below use the cpuv4 32-bit sign extension (r0 = (s32)r0), so they
+ * need a compiler that can emit it and a JIT that can run it. Same gate as
+ * verifier_movsx.c, except the compiler clause also accepts bpf-gcc, which
+ * does not define __clang_major__ but does define __BPF_FEATURE_MOVSX.
+ *
+ * The tests above do not need cpuv4, so the guard starts here rather than
+ * covering the whole file.
+ */
+#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \
+ (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) || \
+ defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \
+ defined(__TARGET_ARCH_loongarch)) && \
+ (__clang_major__ >= 18 || defined(__BPF_FEATURE_MOVSX))
+
+/*
+ * Sign-extension linked-register tracking, in-place narrow-to-zero.
+ *
+ * r1 = r0 ties r0,r1 with a shared id. r0 = (s32)r0 sign-extends r0's low 32
+ * bits; the helper return is a full 64-bit unknown so the sign bit isn't
+ * provably 0, and r0 keeps a BPF_FLAG_SUBREG_SEXT link to r1. On the w1 == 0
+ * fall-through, r1's low 32 bits are 0; r0's low 32 bits equal r1's and r0's
+ * upper bits are the sign-extension of that (0) -- so r0 == 0.
+ *
+ * The guarded div-by-zero is unreachable iff the verifier deduces r0 == 0.
+ */
+SEC("socket")
+__success
+__naked void sext_linked_low_narrow_to_zero(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r1 = r0; /* r1 == r0, shared id */ \
+ r0 = (s32)r0; /* r0 = sext32(r0) */ \
+ if w1 != 0 goto l0_%=; /* fall-through: w1 == 0 */ \
+ /* want deduced here: r0 == 0 */ \
+ if r0 == 0 goto l0_%=; /* always taken iff r0==0 known */ \
+ r0 /= 0; /* unreachable iff r0==0 deduced */ \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Separate-dest sign-extension: r3 = (s32)r2 (dst != src). r2,r3 share a base
+ * id (r3 with BPF_FLAG_SUBREG_SEXT). On the w2 == 0 fall-through, r2's low 32
bits are
+ * 0, so r3 = sext32(0) = 0 and the guarded div-by-zero is unreachable.
+ *
+ * Runs with BPF_F_TEST_STATE_FREQ to force checkpointing between the sext and
+ * the branch: the sext linkage (BPF_FLAG_SUBREG_SEXT) must survive state
+ * cleaning so sync_linked_regs() can still reconstruct r3.
bpf_clear_singular_ids()
+ * strips the link flags when counting base ids; otherwise r3's compound id
looks
+ * singular and gets cleared, and r3 stays wide.
+ */
+SEC("socket")
+__success
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void sext_linked_separate_dest_narrow_to_zero(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r2 = r0; /* r2,(r0) linked, id N */ \
+ r3 = (s32)r2; /* r3 = sext32(r2): SEXT link base N */ \
+ if w2 != 0 goto l0_%=; /* fall-through: w2 == 0 */ \
+ /* want deduced here: r3 == 0 */ \
+ if r3 == 0 goto l0_%=; /* always taken iff r3==0 known */ \
+ r0 /= 0; /* unreachable iff r3==0 deduced */ \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Coverage derived from real "R0 ... should have been in [0, 1]" exit
+ * rejections. Each sign-extends a value, then a branch proves its low 32 bits
+ * are 0 so the sext result must be 0. Expressed with the div-by-zero idiom
(same
+ * deduced range the return-code check reads): the div is unreachable iff the
+ * verifier deduces the sext register is 0.
+ */
+
+/* 1: branch on the SOURCE reg; separate dest (value stands in for a u32
load). */
+SEC("socket")
+__success
+__naked void sext_narrow_branch_on_source(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r2 = r0; /* r2 = value (proxy for u32 load) */ \
+ r0 = (s32)r2; /* r0 = sext32(r2) */ \
+ if w2 != 0 goto l0_%=; /* w2 != 0: r0 unknown, skip */ \
+ if r0 == 0 goto l0_%=; /* w2 == 0: r0 must be 0 */ \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/* 2: sext into r7, prove via w0, then copy r7 back into r0. */
+SEC("socket")
+__success
+__naked void sext_narrow_copied_back(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r7 = (s32)r0; /* r7 = sext32(r0) */ \
+ if w0 != 0 goto l0_%=; /* w0 != 0: skip */ \
+ r0 = r7; /* w0 == 0: r0 = r7 (must be 0) */ \
+ if r0 == 0 goto l0_%=; \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/* 3: in-place sext; branch on the pre-sext copy r1 (== direction). */
+SEC("socket")
+__success
+__naked void sext_narrow_inplace_pre_copy(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r1 = r0; /* pre-sext copy, linked */ \
+ r0 = (s32)r0; /* in-place sext32 */ \
+ if w1 == 0 goto l_chk_%=;/* w1 == 0: r0 must be 0 */ \
+ goto l0_%=; /* w1 != 0: nothing to check */ \
+l_chk_%=: \
+ if r0 == 0 goto l0_%=; \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/* 4: sext, prove via w0, spill to stack across a call, reload, use. */
+SEC("socket")
+__success
+__naked void sext_narrow_spill_fill(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r9 = (s32)r0; /* r9 = sext32(r0) */ \
+ if w0 != 0 goto l0_%=; /* w0 != 0: skip */ \
+ /* w0 == 0: r9 must be 0 */ \
+ *(u64 *)(r10 - 8) = r9; /* spill r9 */ \
+ call %[bpf_get_prandom_u32];/* clobbers r0-r5 */ \
+ r5 = *(u64 *)(r10 - 8); /* reload -> must be 0 */ \
+ if r5 == 0 goto l0_%=; \
+ r0 /= 0; \
+l0_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A redundant 32-bit sign-extension of an already-narrowed value must preserve
+ * the range. This is the errno-or-zero return pattern
(set_if_not_errno_or_zero()
+ * followed by "return ret" on an int): the value is clamped to [-4095, 0] and
+ * then sign-extended again, e.g. verify_pkcs7_sig / many lsm.s progs under
+ * bpf-gcc. coerce_reg_to_size_sx() bails to the full [S32_MIN, S32_MAX] range
+ * when the range straddles the sign boundary (smin<0, smax>=0), so without the
+ * sext-self reconstruction the final "r0 = (s32)r0" widens [-4095, 0] back to
+ * the full range and the program is rejected. Knowing the high half is the
+ * sign-extension of the low 32 bits lets the verifier rebuild the tight range.
+ */
+SEC("socket")
+__success
+__naked void sext_resext_preserves_range(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r0 = (s32)r0; /* r0 = [S32_MIN, S32_MAX] */ \
+ if r0 s> 0 goto l_out_%=; /* r0 <= 0 */ \
+ if r0 s< -4095 goto l_out_%=; /* r0 in [-4095, 0] */ \
+ r0 = (s32)r0; /* redundant re-sext (pkcs7 pattern) */ \
+ if r0 s>= -4095 goto l_lo_ok_%=;/* must hold if range kept */ \
+ r0 /= 0; /* reached only if lower bound lost */ \
+l_lo_ok_%=: \
+ if r0 s<= 0 goto l_out_%=; /* must hold if range kept */ \
+ r0 /= 0; /* reached only if upper bound lost */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A 32-bit sign-extension INSIDE a loop must verify and converge. This is the
+ * bytecode pattern bpf-gcc emits for a cond_break loop (see cond_break4): a
+ * counter is incremented with an ALU32 add (which zero-extends the high half)
+ * and then sign-extended in place every iteration.
+ *
+ * The verifier links dst<->src on a sign-extension. Doing that for a sext on a
+ * register carried across the loop back-edge mints/refreshes the linked scalar
+ * id and its BPF_FLAG_SUBREG_SEXT metadata each iteration; combined with the
+ * ALU32 add's BPF_FLAG_ADD_CONST delta the loop-carried state never repeats,
so state
+ * pruning can't converge and verification runs to the 1M instruction limit.
+ *
+ * The regsafe() guard on the low-32 link flags is what prevents this: it only
demands a
+ * match when the OLD state already carries a link (rold->id), so a register
that
+ * first picks up a sext link inside the loop can still match its pre-loop
state.
+ * Without that guard the loop-carried r2 never matches and the load fails at
+ * 1,000,001 insns, i.e. this __success flips to a load failure -- so this is
the
+ * regression test for it. (See sext_in_loop_separate_dest_index for the
+ * companion case, a fresh in-loop temp that keeps its link for precision.)
+ *
+ * The pattern is written in asm so the bytecode is identical regardless of the
+ * host BPF compiler.
+ */
+SEC("socket")
+__success
+__naked void sext_in_loop_converges(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r2 = r0; /* r2 = 64-bit unknown (helper ret) */ \
+l_body_%=: \
+ .byte 0xe5; /* may_goto l_exit (loop bound) */ \
+ .byte 0; \
+ .short 3; \
+ .long 0; \
+ w2 += 1; /* ALU32 add: low += 1, high = 0 */ \
+ r2 = (s32)r2; /* in-place in-loop sign-extend */ \
+ goto l_body_%=; \
+l_exit_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A separate-destination 32-bit sign extension INSIDE a loop keeps its low-32
+ * link, so a later bounds check on the source narrows the sign-extended
+ * destination too. This is the bytecode a bpf-gcc build emits for array
indexing
+ * in a bpf_for loop -- a fresh 32-bit index load, a separate "r1 = (s32)r0",
+ * then a bounds check on the index (verifier_global_subprogs'
syscall_array_bpf_for).
+ *
+ * Both in-loop cases form the link -- subreg_link is just (sz == 4), with no
+ * liveness or loop-carried exclusion. What differs is what the link buys. Here
+ * the destination is a fresh temp, dead across the back-edge, so the link is
+ * pure precision: "if w0 > 99" narrows r1 to [0, 99] and the guarded
+ * div-by-zero is unreachable. In sext_in_loop_converges the target is the
+ * loop-carried counter, so the link is re-formed every iteration and the
+ * question is convergence instead -- answered by the regsafe() rold->id guard,
+ * not by declining to link.
+ *
+ * Written in asm so the bytecode is identical regardless of the host BPF
+ * compiler.
+ */
+SEC("socket")
+__success
+__naked void sext_in_loop_separate_dest_index(void)
+{
+ asm volatile (" \
+l_body_%=: \
+ .byte 0xe5; /* may_goto l_exit (loop bound) */ \
+ .byte 0; \
+ .short 7; \
+ .long 0; \
+ call %[bpf_get_prandom_u32];/* r0 = fresh u32 each iter */ \
+ r1 = (s32)r0; /* in-loop separate-dest sext */ \
+ if w0 > 0x63 goto l_body_%=;/* fall-through: w0 <= 99 */ \
+ /* want r1 = sext32(r0 low) == [0, 99] here (needs the link) */ \
+ if r1 > 0x63 goto l_err_%=;/* taken unless r1 narrowed */ \
+ goto l_body_%=; \
+l_err_%=: \
+ r0 /= 0; /* reachable iff r1 not narrowed */ \
+ goto l_body_%=; \
+l_exit_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * A 32-bit zero-extending mov (w2 = w1) whose SOURCE is a sign-extended
register
+ * must still zero-extend: dst's high bits are 0, not the sign-extension of the
+ * low field. Regression test for the zext link clearing BPF_FLAG_SUBREG_SEXT
(otherwise
+ * dst would inherit SUBREG_SEXT from the sext'd source, and sync_linked_regs()
+ * would later rebuild it with reconstruct_sext32() -- computing a negative
value
+ * for what is actually a large positive zero-extended one).
+ *
+ * r1 = (s32)r6 makes r1 a sext-linked wide source; w2 = w1 forms the zext
link.
+ * After "if w6 s>= 0" falls through, r6's low 32 bits have bit 31 set, so the
+ * zero-extended r2 must be in [0x80000000, 0xffffffff]. Two guards assert that
+ * whole range, so the test needs the feature present, not merely the absence
of
+ * the sext-leak bug: "r2 s< 0" catches the leak (r2 rebuilt negative), and
+ * "w2 s>= 0" catches the low-32 link being absent entirely (r2 not narrowed to
+ * the high half, so bit 31 is not known set). Either makes the div reachable.
+ */
+SEC("socket")
+__success
+__naked void zext_mov_from_sext_src_zero_extends(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; /* r6 low = unknown u32 (callee-saved) */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown (width 64) */ \
+ r1 = (s32)r6; /* r1 = sext32(r6 low): SUBREG_SEXT, wide */ \
+ w2 = w1; /* zext mov from sext-linked wide src */ \
+ if w6 s>= 0 goto l_out_%=;/* fall-through: r6 low has bit 31 set */ \
+ /* r2 = zext32(r6 low) must be in [0x80000000, 0xffffffff]: */ \
+ if r2 s< 0 goto l_err_%=;/* sext leak: r2 wrongly negative */ \
+ if w2 s>= 0 goto l_err_%=;/* link absent: r2 low bit 31 not known set
*/ \
+ goto l_out_%=; \
+l_err_%=: \
+ r0 /= 0; /* r2 not proven in [0x80000000, 0xffffffff] */
\
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Mirror of zext_mov_keeps_add_const_src for the sign-extending mov: a sext
+ * whose source carries an ADD_CONST delta must not destroy that link.
+ *
+ * Forming a low-32 link calls assign_scalar_id_before_mov(), which clears an
+ * ADD_CONST src, so the sext arm excludes such a source exactly as the zext
+ * arm does. Without that exclusion r5 loses its base+delta relationship to r6
+ * here, "if r6 > 10" no longer narrows r5, and the guarded div becomes
+ * reachable.
+ */
+SEC("socket")
+__success
+__naked void sext_mov_keeps_add_const_src(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; /* r6 low = unknown u32 */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown (base) */ \
+ r5 = r6; /* r5, r6 linked (shared id) */ \
+ r5 += 3; /* r5 = base + 3: ADD_CONST, still wide */ \
+ r7 = (s32)r5; /* 32-bit sext mov, ADD_CONST src */ \
+ if r6 > 10 goto l_out_%=;/* r6 in [0, 10] */ \
+ /* r5 = r6 + 3 must be in [3, 13] here (needs the kept link) */ \
+ if r5 > 13 goto l_err_%=;/* taken only if r5 not narrowed */ \
+ goto l_out_%=; \
+l_err_%=: \
+ r0 /= 0; /* reachable iff r5's link was cleared */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+/*
+ * Dest-driven direction, sign-extend flavour: narrowing the LINKED register
+ * must not narrow the wide base.
+ *
+ * r7 = (s32)r6 shares only r6's low 32 bits. Learning r7 == 0 says nothing
+ * about r6's high half, so sync_linked_regs() must leave r6 alone -- that is
+ * the "known_reg is subreg-linked" continue. If it ever propagated, r6 would
+ * be known 0 here and the div would be treated as unreachable, so the program
+ * must be REJECTED.
+ */
+SEC("socket")
+__failure __msg("div by zero")
+__flag(BPF_F_TEST_STATE_FREQ)
+__naked void sext_dest_driven_does_not_narrow_base(void)
+{
+ asm volatile (" \
+ call %[bpf_get_prandom_u32]; \
+ r6 = r0; /* r6 low = unknown u32 */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 <<= 32; \
+ r6 |= r0; /* r6 = full 64-bit unknown (base) */ \
+ r7 = (s32)r6; /* low-32 SEXT link */ \
+ if r7 != 0 goto l_out_%=;/* r7 == 0: low 32 bits are 0 */ \
+ if r6 != 0 goto l_out_%=;/* r6 may still have high bits set */ \
+ r0 /= 0; /* must stay reachable */ \
+l_out_%=: \
+ r0 = 0; \
+ exit; \
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
+}
+
+#endif /* cpuv4 sign extension */
+
char _license[] SEC("license") = "GPL";
--
2.53.0-Meta
