From: Alexei Starovoitov arg_track follows pointers to the stack through registers and spills. Scalar evolution and the removal of dead slots rely on it to know which slots an insn reads and writes. arg_track assumes that a call does not change the pointers that are spilled in the frame of the caller. But a static subprog or a callback can store a pointer to other memory there, and the caller can use it: *(u64 *)(r10 - 16) = fp-8 r1 = fp-16, r2 = map_value call sub ; *(u64 *)(r1 + 0) = r2 r7 = *(u64 *)(r10 - 16) ; verifier: map_value. arg_track: fp-8 *(u64 *)(r10 - 8) = fp-24 *(u64 *)(r7 + 0) = 0 ; arg_track: fp-8 is overwritten r8 = *(u64 *)(r10 - 8) ; verifier: fp-24. arg_track: none loop: r1 = *(u64 *)(r10 - 24) ; the counter of the loop ... *(u64 *)(r8 + 0) = 4096 ; arg_track: not a write to fp-24 Scalar evolution does not see the last store. It gives the counter the range of a loop that only increments it. The prog loads, and it accesses a map value out of bounds. Valid progs are rejected as well. The store through r7 makes fp-8 dead, and a later read of fp-8 fails with "slot poisoned by dead code elimination". When a static subprog or a callback can get a pointer to the frame of its caller, join every slot of that frame with "not a pointer to the stack". Reads and possible writes through a filled pointer are still seen, but no store through it is a certain write. It has to be every slot: the callee reaches the whole frame from one pointer, and callees are analyzed after the caller. The price is precision: an 8-byte load through a filled pointer gives a value that can point to any frame. For a spilled copy of r10 this needs "bpf: Fix the join of fp+0 with a value that is not a pointer to stack". In selftests, Cilium and sched_ext the stack marks change in 4 of 12522 progs. Verdicts, insns and states do not change in any prog. one_fp_clear_stack_threshold and two_fp_clear_stack_threshold expect the fake offset fp+0 in the log now. Fixes: bf0c571f7feb ("bpf: introduce forward arg-tracking dataflow analysis") Signed-off-by: Alexei Starovoitov --- kernel/bpf/liveness.c | 52 ++++++++++++++----- .../selftests/bpf/progs/verifier_live_stack.c | 12 +++-- 2 files changed, 47 insertions(+), 17 deletions(-) diff --git a/kernel/bpf/liveness.c b/kernel/bpf/liveness.c index db01aecdffba..75d9af4921de 100644 --- a/kernel/bpf/liveness.c +++ b/kernel/bpf/liveness.c @@ -1383,6 +1383,31 @@ static struct arg_track arg_track_deref(struct bpf_verifier_env *env, struct bpf return (struct arg_track){ .frame = ARG_NONE }; } +/* + * True if the call at @insn_idx can pass a pointer to the frame at @depth to a static subprog + * or to a callback. They use it as a pointer to stack, a global subprog gets plain memory. + * It errs on the safe side: it looks at all argument registers and stack args, also at those + * that this callee doesn't take. + */ +static bool subprog_gets_local_fp(struct bpf_verifier_env *env, struct bpf_insn *insn, int insn_idx, + struct arg_track *at, int depth) +{ + int r; + + if (bpf_pseudo_call(insn)) { + r = bpf_find_subprog(env, insn_idx + insn->imm + 1); + if (r >= 0 && bpf_subprog_is_global(env, r)) + return false; + } else if (!bpf_is_callx(insn) && !bpf_calls_callback(env, insn_idx)) { + return false; + } + /* R1-R5 and stack args */ + for (r = BPF_REG_1; r < MAX_AT_TRACK_REGS; r++) + if ((r <= BPF_REG_5 || r >= MAX_BPF_REG) && can_be_local_fp(depth, r, &at[r])) + return true; + return false; +} + /* * Pure dataflow transfer function for arg_track state. * Updates at_out[] based on how the instruction modifies registers. @@ -1446,21 +1471,22 @@ static void arg_track_xfer(struct bpf_verifier_env *env, struct bpf_insn *insn, *dst = none; } else if (class == BPF_JMP && code == BPF_CALL) { /* - * at_stack_out[slot] is not cleared by the helper and subprog calls. - * The fill_from_stack() may return the stale spill — which is an FP-derived arg_track - * (the value that was originally spilled there). The loaded register then carries - * a phantom FP-derived identity that doesn't correspond to what's actually in the slot. - * This phantom FP pointer propagates forward, and wherever it's subsequently used - * (as a helper argument, another store, etc.), it sets stack liveness bits. - * Those bits correspond to stack accesses that don't actually happen. - * So the effect is over-reporting stack liveness — marking slots as live that aren't - * actually accessed. The verifier preserves more state than necessary across calls, - * which is conservative. + * Helpers, kfuncs and global subprogs can scratch stack slots. The verifier reads + * a scalar from a scratched slot, but at_stack_out[slot] is not cleared, and + * fill_from_stack() returns the stale spill: an FP-derived arg_track for a scalar. + * A scalar can't be dereferenced, so the stale value can only set liveness bits + * for stack accesses that don't happen. That is conservative. * - * helpers can scratch stack slots, but they won't make a valid pointer out of it. - * subprogs are allowed to write into parent slots, but they cannot write - * _any_ FP-derived pointer into it (either their own or parent's FP). + * Static subprogs and callbacks can't store an FP-derived pointer into the frame of + * the caller, but they can store any other pointer there. The caller can fill it + * and store through it. With the stale spill that store would be a definite write + * to a stack slot, and it doesn't touch the stack. Callees are analyzed after the + * caller, and they reach the whole frame from one pointer to it. So after the call + * every slot holds what it held before or a value that is not FP-derived. */ + if (subprog_gets_local_fp(env, insn, insn_idx, at_out, depth)) + for (slot = 0; slot < nslots; slot++) + at_stack_out[slot] = __arg_track_join(at_stack_out[slot], none); for (r = BPF_REG_0; r <= BPF_REG_5; r++) at_out[r] = none; } else if (class == BPF_LDX) { diff --git a/tools/testing/selftests/bpf/progs/verifier_live_stack.c b/tools/testing/selftests/bpf/progs/verifier_live_stack.c index b5ae4f0d4dc5..61833ea784d0 100644 --- a/tools/testing/selftests/bpf/progs/verifier_live_stack.c +++ b/tools/testing/selftests/bpf/progs/verifier_live_stack.c @@ -1943,11 +1943,15 @@ static __used __naked void grandchild_deref(void) ::: __clobber_all); } +/* + * The callee gets a pointer to the frame that holds the spills. It can store a pointer + * that is not FP-derived over them: after the call each of them is "fp-N or not FP-derived". + */ SEC("socket") __log_level(2) __success -__msg("14: (79) r1 = *(u64 *)(r10 -8) // r6=fp0-8 r7=fp1-16 fp-8=fp1-16 fp-16=fp0-8") -__msg("15: (79) r0 = *(u64 *)(r1 +0) // r1=fp1-16 r6=fp0-8 r7=fp1-16 fp-8=fp1-16 fp-16=fp0-8") +__msg("14: (79) r1 = *(u64 *)(r10 -8) // r6=fp0-8 r7=fp1-16 fp-8=fp1-16|fp1+0 fp-16=fp0-8|fp0+0") +__msg("15: (79) r0 = *(u64 *)(r1 +0) // r1=fp1-16|fp1+0 r6=fp0-8 r7=fp1-16 fp-8=fp1-16|fp1+0") __msg("stack use/def subprog#1 mid_two_fp_threshold (d1,cs2):") __msg("14: (79) r1 = *(u64 *)(r10 -8) ; use: fp1-8") __msg("15: (79) r0 = *(u64 *)(r1 +0) ; use: fp1-16") @@ -1992,8 +1996,8 @@ static __used __naked void inner_nop_fptest(void) SEC("socket") __log_level(2) __success -__msg("13: (79) r1 = *(u64 *)(r10 -8) // r6=fp0-8 r7=fp1-16 fp-8=fp1-16 fp-16=fp0-8") -__msg("14: (79) r0 = *(u64 *)(r1 +0) // r1=fp1-16 r6=fp0-8 r7=fp1-16 fp-8=fp1-16 fp-16=fp0-8") +__msg("13: (79) r1 = *(u64 *)(r10 -8) // r6=fp0-8 r7=fp1-16 fp-8=fp1-16|fp1+0 fp-16=fp0-8|fp0+0") +__msg("14: (79) r0 = *(u64 *)(r1 +0) // r1=fp1-16|fp1+0 r6=fp0-8 r7=fp1-16 fp-8=fp1-16|fp1+0") __msg("stack use/def subprog#1 mid_one_fp_threshold (d1,cs2):") __msg("13: (79) r1 = *(u64 *)(r10 -8) ; use: fp1-8") __msg("14: (79) r0 = *(u64 *)(r1 +0) ; use: fp1-16") -- 2.55.0