bpf: arg tracking for imprecise/multi-offset BPF_ST/STX
Subsystems (3)
Eduard Zingerman
maintainercover bpf: arg tracking for imprecise/multi-offset BPF_ST/STX
When the static arg tracking analysis encounters a store through a pointer with imprecise or multi-offset destination, it must use weak updates (join) instead of strong updates (overwrite) for the affected at_stack slots. At runtime only one slot is actually written; the others retain their old values.
Two cases are addressed:
- BPF_STX, handled by spill_to_stack(). It was gated on dst_is_local_fp = (frame == depth), which missed ARG_IMPRECISE pointers entirely.
- BPF_ST, handled by clear_stack_for_all_offs(). It delegates to clear_overlapping_stack_slots() which unconditionally set at_stack[i] = none. Change to at_stack[i] = join(old, none) when multiple candidate slots exist (cnt != 1), so that untouched slots preserve their tracked values.
No veristat diff compared to current master when tested on selftests, sched_ext, cilium and a set of Meta internal programs.
This addresses issues reported by sashiko for patch #7 in [1].
[1] https://sashiko.dev/#/patchset/20260410-patch-set-v4-0-5d4eecb343db%40gmail.com
---
Eduard Zingerman (3):
bpf: fix arg tracking for BPF_STX through imprecise ptrs
bpf: fix arg tracking for BPF_ST through imprecise/multi-offset ptrs selftests/bpf: arg tracking for imprecise/multi-offset BPF_ST/STX
kernel/bpf/liveness.c | 67 ++++--- .../selftests/bpf/progs/verifier_live_stack.c | 194 +++++++++++++++++++++ 2 files changed, 232 insertions(+), 29 deletions(-)
---
base-commit: 71b500afd2f7336f5b6c6026f2af546fc079be26
change-id: 20260413-stacklive-fixes-42e258cf0397
Eduard Zingerman
maintainerPATCH 1/3 bpf: fix arg tracking for BPF_STX through imprecise ptrs
BPF_STX through ARG_IMPRECISE dst should be recognized as a local spill and join at_stack with the written value. For example, consider the following situation:
// r1 = ARG_IMPRECISE{mask=BIT(0)|BIT(1)}
*(u64 *)(r1 + 0) = r8
Here the analysis should produce an equivalent of
at_stack[*] = join(old, r8)
--- kernel/bpf/liveness.c | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-)
kernel/bpf/liveness.c +8 -3
@@ -1042,6 +1042,12 @@ static void arg_track_log(struct bpf_verifier_env *env, struct bpf_insn *insn, iverbose (env,"\n" ); } +static bool can_be_local_fp (int depth,int regno,struct arg_track *at) +{ +return regno ==BPF_REG_FP || at->frame == depth || + (at->frame ==ARG_IMPRECISE && (at->mask &BIT (depth))); +} +/* * Pure dataflow transfer function for arg_track state. * Updates at_out[] based on how the instruction modifies registers.
@@ -1111,8 +1117,7 @@ static void arg_track_xfer(struct bpf_verifier_env *env, struct bpf_insn *insn, at_out[r] = none; }else if (class ==BPF_LDX ) {u32 sz =bpf_size_to_bytes (BPF_SIZE (insn->code)); -bool src_is_local_fp = insn->src_reg ==BPF_REG_FP || src->frame == depth || - (src->frame ==ARG_IMPRECISE && (src->mask &BIT (depth))); +bool src_is_local_fp =can_be_local_fp (depth, insn->src_reg, src);/* * Reload from callee stack: if src is current-frame FP-derived
@@ -1147,7 +1152,7 @@ static void arg_track_xfer(struct bpf_verifier_env *env, struct bpf_insn *insn,bool dst_is_local_fp;/* Track spills to current-frame FP-derived callee stack */ - dst_is_local_fp = insn->dst_reg ==BPF_REG_FP || dst->frame == depth; + dst_is_local_fp =can_be_local_fp (depth, insn->dst_reg, dst);if (dst_is_local_fp &&BPF_MODE (insn->code) ==BPF_MEM )spill_to_stack (insn, at_out, insn->dst_reg, at_stack_out, src, sz);
Signature · 1 line
2.53.0
Eduard Zingerman
maintainerPATCH 2/3 bpf: fix arg tracking for BPF_ST through imprecise/multi-offset ptrs
In reply to Eduard ZingermanBPF_ST through multi-offset or imprecise dst should join at_stack with none instead of overwriting the slots. For example, consider the following situation:
// r1 = ARG_IMPRECISE{mask=BIT(0)|BIT(1)}
*(u64 *)(r1 + 0) = 0
Here the analysis should produce an equivalent of
at_stack[*r1] = join(old, none).
Move the definition clear_overlapping_stack_slots() in order to have __arg_track_join() visible.
--- kernel/bpf/liveness.c | 56 +++++++++++++++++++++++++++------------------------ 1 file changed, 30 insertions(+), 26 deletions(-)
kernel/bpf/liveness.c +30 -26
@@ -622,28 +622,6 @@ static bool arg_is_fp(const struct arg_track *at)return at->frame >=0 || at->frame ==ARG_IMPRECISE ; } -/* -* Clear all tracked callee stack slots overlapping the byte range -* [off, off+sz-1] where off is a negative FP-relative offset. -*/ -static void clear_overlapping_stack_slots (struct arg_track *at_stack,s16 off,u32 sz) -{ -struct arg_track none = { .frame =ARG_NONE }; - -if (off ==OFF_IMPRECISE ) { -for (int i =0 ; i <MAX_ARG_SPILL_SLOTS ; i++) - at_stack[i] = none; -return ; - } -for (int i =0 ; i <MAX_ARG_SPILL_SLOTS ; i++) { -int slot_start = -((i +1 ) *8 ); -int slot_end = slot_start +8 ; - -if (slot_start < off + (int )sz && slot_end > off) - at_stack[i] = none; - } -} -static void verbose_arg_track (struct bpf_verifier_env *env,struct arg_track *at) {int i;
@@ -980,6 +958,32 @@ static void spill_to_stack(struct bpf_insn *insn, struct arg_track *at_out, } } +/* +* Clear all tracked callee stack slots overlapping the byte range +* [off, off+sz-1] where off is a negative FP-relative offset. +*/ +static void clear_overlapping_stack_slots (struct arg_track *at_stack,s16 off,u32 sz,int cnt) +{ +struct arg_track none = { .frame =ARG_NONE }; + +if (off ==OFF_IMPRECISE ) { +for (int i =0 ; i <MAX_ARG_SPILL_SLOTS ; i++) + at_stack[i] =__arg_track_join (at_stack[i], none); +return ; + } +for (int i =0 ; i <MAX_ARG_SPILL_SLOTS ; i++) { +int slot_start = -((i +1 ) *8 ); +int slot_end = slot_start +8 ; + +if (slot_start < off + (int )sz && slot_end > off) { +if (cnt ==1 ) + at_stack[i] = none; +else + at_stack[i] =__arg_track_join (at_stack[i], none); + } + } +} +/* * Clear stack slots overlapping all possible FP offsets in @reg. */
@@ -990,18 +994,18 @@ static void clear_stack_for_all_offs(struct bpf_insn *insn,int cnt, i;if (reg ==BPF_REG_FP ) { -clear_overlapping_stack_slots (at_stack_out, insn->off, sz); +clear_overlapping_stack_slots (at_stack_out, insn->off, sz,1 );return ; } cnt = at_out[reg].off_cnt;if (cnt ==0 ) { -clear_overlapping_stack_slots (at_stack_out,OFF_IMPRECISE , sz); +clear_overlapping_stack_slots (at_stack_out,OFF_IMPRECISE , sz, cnt);return ; }for (i =0 ; i < cnt; i++) {s16 fp_off =arg_add (at_out[reg].off[i], insn->off); -clear_overlapping_stack_slots (at_stack_out, fp_off, sz); +clear_overlapping_stack_slots (at_stack_out, fp_off, sz, cnt); } }
@@ -1171,7 +1175,7 @@ static void arg_track_xfer(struct bpf_verifier_env *env, struct bpf_insn *insn, } }else if (class ==BPF_ST &&BPF_MODE (insn->code) ==BPF_MEM ) {u32 sz =bpf_size_to_bytes (BPF_SIZE (insn->code)); -bool dst_is_local_fp = insn->dst_reg ==BPF_REG_FP || dst->frame == depth; +bool dst_is_local_fp =can_be_local_fp (depth, insn->dst_reg, dst);/* BPF_ST to FP-derived dst: clear overlapping stack slots */ if (dst_is_local_fp)
Signature · 1 line
2.53.0
Eduard Zingerman
maintainerPATCH 3/3 selftests/bpf: arg tracking for imprecise/multi-offset BPF_ST/STX
In reply to Eduard ZingermanAdd test cases for clear_stack_for_all_offs and dst_is_local_fp handling of multi-offset and ARG_IMPRECISE stack pointers:
- st_imm_join_with_multi_off: BPF_ST through multi-offset dst should join at_stack with none instead of overwriting both candidate slots.
- st_imm_join_with_imprecise_off: BPF_ST through offset-imprecise dst should join at_stack with none instead of clearing all slots.
- st_imm_join_with_single_off: a canary checking that BPF_ST with a known offset overwrites slot instead of joining.
- imprecise_dst_spill_join: BPF_STX through ARG_IMPRECISE dst should be recognized as a local spill and join at_stack with the written value.
--- .../selftests/bpf/progs/verifier_live_stack.c | 194 +++++++++++++++++++++ 1 file changed, 194 insertions(+)
tools/testing/selftests/bpf/progs/verifier_live_stack.c +194 -0
@@ -2647,3 +2647,197 @@ __naked void spill_join_with_imprecise_off(void)"exit;" ::: __clobber_all); } + +/* +* Same as spill_join_with_multi_off but the write is BPF_ST (store +* immediate) instead of BPF_STX. BPF_ST goes through +* clear_stack_for_all_offs() rather than spill_to_stack(), and that +* path also needs to join instead of overwriting. +* +* fp-8 = &fp-24 +* fp-16 = &fp-32 +* r1 = fp-8 or fp-16 (two offsets from branch) +* *(u64 *)(r1 + 0) = 0 -- BPF_ST with immediate +* r0 = *(u64 *)(r10 - 16) -- fill from fp-16 +* r0 = *(u64 *)(r0 + 0) -- deref: should produce use +*/ +SEC("socket") +__log_level(2) +__failure +__msg("15: (7a) *(u64 *)(r1 +0) = 0 fp-8: fp0-24 -> fp0-24|fp0+0 fp-16: fp0-32 -> fp0-32|fp0+0") +__msg("17: (79) r0 = *(u64 *)(r0 +0) ; use: fp0-32") +__naked void st_imm_join_with_multi_off (void ) +{ + asmvolatile ( +"*(u64 *)(r10 - 24) = 0;" +"*(u64 *)(r10 - 32) = 0;" +"r1 = r10;" +"r1 += -24;" +"*(u64 *)(r10 - 8) = r1;" +"r1 = r10;" +"r1 += -32;" +"*(u64 *)(r10 - 16) = r1;" +/* create r1 with two candidate offsets: fp-8 or fp-16 */ +"call %[bpf_get_prandom_u32];" +"if r0 == 0 goto 1f;" +"r1 = r10;" +"r1 += -8;" +"goto 2f;" +"1:" +"r1 = r10;" +"r1 += -16;" +"2:" +/* BPF_ST: store immediate through multi-offset r1 */ +"*(u64 *)(r1 + 0) = 0;" +/* read back fp-16 and deref */ +"r0 = *(u64 *)(r10 - 16);" +"r0 = *(u64 *)(r0 + 0);" +"r0 = 0;" +"exit;" + :: __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* Check that BPF_ST with a known offset fully overwrites stack slot +* from the arg tracking point of view. +*/ +SEC("socket") +__log_level(2) +__success +__msg("5: (7a) *(u64 *)(r1 +0) = 0 fp-8: fp0-16 -> _{{$}}") +__naked void st_imm_join_with_single_off(void) +{ + asmvolatile ( +"r2 = r10;" +"r2 += -16;" +"*(u64 *)(r10 - 8) = r2;" +"r1 = r10;" +"r1 += -8;" +"*(u64 *)(r1 + 0) = 0;" +"r0 = 0;" +"exit;" + :: __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* +* Same as spill_join_with_imprecise_off but the write is BPF_ST. +* Use "r2 = -8; r1 += r2" to make arg tracking lose offset +* precision while the main verifier keeps r1 as fixed-offset. +* +* fp-8 = &fp-24 +* fp-16 = &fp-32 +* r1 = fp-8 (imprecise to arg tracking) +* *(u64 *)(r1 + 0) = 0 -- BPF_ST with immediate +* r0 = *(u64 *)(r10 - 16) -- fill from fp-16 +* r0 = *(u64 *)(r0 + 0) -- deref: should produce use +*/ +SEC("socket") +__log_level(2) +__success +__msg("13: (79) r0 = *(u64 *)(r0 +0) ; use: fp0-32") +__naked void st_imm_join_with_imprecise_off(void) +{ + asmvolatile ( +"*(u64 *)(r10 - 24) = 0;" +"*(u64 *)(r10 - 32) = 0;" +"r1 = r10;" +"r1 += -24;" +"*(u64 *)(r10 - 8) = r1;" +"r1 = r10;" +"r1 += -32;" +"*(u64 *)(r10 - 16) = r1;" +/* r1 = fp-8 but arg tracking sees off_cnt == 0 */ +"r1 = r10;" +"r2 = -8;" +"r1 += r2;" +/* store immediate through imprecise r1 */ +"*(u64 *)(r1 + 0) = 0;" +/* read back fp-16 */ +"r0 = *(u64 *)(r10 - 16);" +/* deref: should produce use */ +"r0 = *(u64 *)(r0 + 0);" +"r0 = 0;" +"exit;" + ::: __clobber_all); +} + +/* +* Test that spilling through an ARG_IMPRECISE pointer joins with +* existing at_stack values. Subprog receives r1 = fp0-24 and +* r2 = map_value, creates an ARG_IMPRECISE pointer by joining caller +* and callee FP on two branches. +* +* Setup: callee spills &fp1-16 to fp1-8 (precise, tracked). +* Then writes map_value through ARG_IMPRECISE r1 — on path A +* this hits fp1-8, on path B it hits caller stack. +* Since spill_to_stack is skipped for ARG_IMPRECISE dst, +* fp1-8 tracking isn't joined with none. +* +* Expected after the imprecise write: +* - arg tracking should show fp1-8 = fp1-16|fp1+0 (joined with none) +* - read from fp1-8 and deref should produce use for fp1-16 +* - write through it should NOT produce def for fp1-16 +*/ +SEC("socket") +__log_level(2) +__success +__msg("26: (79) r0 = *(u64 *)(r10 -8) // r1=IMP3 r6=fp0-24 r7=fp1-16 fp-8=fp1-16|fp1+0") +__naked void imprecise_dst_spill_join(void) +{ + asmvolatile ( +"*(u64 *)(r10 - 24) = 0;" +/* map lookup for a valid non-FP pointer */ +"*(u32 *)(r10 - 32) = 0;" +"r1 = %[map] ll;" +"r2 = r10;" +"r2 += -32;" +"call %[bpf_map_lookup_elem];" +"if r0 == 0 goto 1f;" +/* r1 = &caller_fp-24, r2 = map_value */ +"r1 = r10;" +"r1 += -24;" +"r2 = r0;" +"call imprecise_dst_spill_join_sub;" +"1:" +"r0 = 0;" +"exit;" + :: __imm_addr(map), +__imm (bpf_map_lookup_elem) + : __clobber_all); +} + +static __used __naked void imprecise_dst_spill_join_sub (void ) +{ + asmvolatile ( +/* r6 = &caller_fp-24 (frame=0), r8 = map_value */ +"r6 = r1;" +"r8 = r2;" +/* spill &fp1-16 to fp1-8: at_stack[0] = fp1-16 */ +"*(u64 *)(r10 - 16) = 0;" +"r7 = r10;" +"r7 += -16;" +"*(u64 *)(r10 - 8) = r7;" +/* branch to create ARG_IMPRECISE pointer */ +"call %[bpf_get_prandom_u32];" +/* path B: r1 = caller fp-24 (frame=0) */ +"r1 = r6;" +"if r0 == 0 goto 1f;" +/* path A: r1 = callee fp-8 (frame=1) */ +"r1 = r10;" +"r1 += -8;" +"1:" +/* r1 = ARG_IMPRECISE{mask=BIT(0)|BIT(1)}. +* Write map_value (non-FP) through r1. On path A this overwrites fp1-8. +* Should join at_stack[0] with none: fp1-16|fp1+0. +*/ +"*(u64 *)(r1 + 0) = r8;" +/* read fp1-8: should be fp1-16|fp1+0 (joined) */ +"r0 = *(u64 *)(r10 - 8);" +"*(u64 *)(r0 + 0) = 42;" +"r0 = 0;" +"exit;" + :: __imm(bpf_get_prandom_u32) + : __clobber_all); +}
Signature · 1 line
2.53.0