bpf: fix precision backtracking instruction iteration
cover bpf: fix precision backtracking instruction iteration
The first patch in this patchset was already backported before, as commit ecc2aeeaa08a, to address CVE-2023-52920 [1]. That backport was however later reverted in commit 199f04528737 because it reduced the efficiency of the BPF verifier, to the point that it rejected some previously-accepted programs.
This patchset backports commit 41f6f64e6999 ("bpf: support non-r10 register spill/fill to/from stack in precision tracking") again, but this time with the subsequent commits that improved the efficiency of the verifier. In addition, the last two commits fix and test a regression that was later found in commit 41f6f64e6999.
It took us a while with Shung-Hsi to come back to this because we felt we didn't have enough test coverage to backport this. That changed with the stable BPF CI Shung-Hsi built for v6.6, which successfully validated this patchset [2]. In addition, I tested the impact of this patchset on the verifier's efficiency with Cilium's BPF programs [3]:
it significantly improves, reducing the number of instructions the verifier has to analyze by up to 87% in some cases!
1: https://lore.kernel.org/linux-cve-announce/2024110518-CVE-2023-52920-17f6@gregkh/
2: https://github.com/pchaigno/stable-bpf-ci/actions/runs/25671397661/job/75357317078
3: https://pchaigno.github.io/test-verifier-complexity.html
Andrii Nakryiko (10):
bpf: support non-r10 register spill/fill to/from stack in precision
tracking
selftests/bpf: add stack access precision test
bpf: preserve STACK_ZERO slots on partial reg spills selftests/bpf: validate STACK_ZERO is preserved on subreg spill
bpf: preserve constant zero when doing partial register restore selftests/bpf: validate zero preservation for sub-slot loads
bpf: track aligned STACK_ZERO cases as imprecise spilled registers selftests/bpf: validate precision logic in
partial_stack_load_preserves_zeros
bpf: handle fake register spill to stack with BPF_ST_MEM instruction selftests/bpf: validate fake register spill/fill precision
backtracking logic
include/linux/bpf_verifier.h | 31 +- kernel/bpf/verifier.c | 233 +++++++++------ .../selftests/bpf/progs/verifier_spill_fill.c | 281 ++++++++++++++++++ .../bpf/progs/verifier_subprog_precision.c | 87 +++++- .../testing/selftests/bpf/verifier/precise.c | 38 ++- 5 files changed, 557 insertions(+), 113 deletions(-)
Signature · 1 line
2.43.0
PATCH 1/10 bpf: support non-r10 register spill/fill to/from stack in precision tracking
From: Andrii Nakryiko <[email protected]>
[ Upstream commit 41f6f64e6999a837048b1bd13a2f8742964eca6b ]
Use instruction (jump) history to record instructions that performed register spill/fill to/from stack, regardless if this was done through read-only r10 register, or any other register after copying r10 into it *and* potentially adjusting offset.
To make this work reliably, we push extra per-instruction flags into instruction history, encoding stack slot index (spi) and stack frame number in extra 10 bit flags we take away from prev_idx in instruction history. We don't touch idx field for maximum performance, as it's checked most frequently during backtracking.
This change removes basically the last remaining practical limitation of precision backtracking logic in BPF verifier. It fixes known deficiencies, but also opens up new opportunities to reduce number of verified states, explored in the subsequent patches.
There are only three differences in selftests' BPF object files according to veristat, all in the positive direction (less states).
File Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) -------------------------------------- ------------- --------- --------- ------------- ---------- ---------- ------------- test_cls_redirect_dynptr.bpf.linked3.o cls_redirect 2987 2864 -123 (-4.12%) 240 231 -9 (-3.75%) xdp_synproxy_kern.bpf.linked3.o syncookie_tc 82848 82661 -187 (-0.23%) 5107 5073 -34 (-0.67%) xdp_synproxy_kern.bpf.linked3.o syncookie_xdp 85116 84964 -152 (-0.18%) 5162 5130 -32 (-0.62%)
Note, I avoided renaming jmp_history to more generic insn_hist to minimize number of lines changed and potential merge conflicts between bpf and bpf-next trees.
Notice also cur_hist_entry pointer reset to NULL at the beginning of instruction verification loop. This pointer avoids the problem of relying on last jump history entry's insn_idx to determine whether we already have entry for current instruction or not. It can happen that we added jump history entry because current instruction is_jmp_point(), but also we need to add instruction flags for stack access. In this case, we don't want to entries, so we need to reuse last added entry, if it is present.
Relying on insn_idx comparison has the same ambiguity problem as the one that was fixed recently in [0], so we avoid that.
[0] https://patchwork.kernel.org/project/netdevbpf/patch/[email protected]/
[ Note: Adapted the expected log format for selftests as the map format
in verifier logs was changed in commits 1db747d75b1d and 0c95c9fdb696. ]
--- include/linux/bpf_verifier.h | 31 +++- kernel/bpf/verifier.c | 175 ++++++++++-------- .../bpf/progs/verifier_subprog_precision.c | 23 ++- .../testing/selftests/bpf/verifier/precise.c | 38 ++-- 4 files changed, 169 insertions(+), 98 deletions(-)
include/linux/bpf_verifier.h +27 -4
@@ -319,12 +319,34 @@ struct bpf_func_state {struct bpf_stack_state *stack; }; -struct bpf_idx_pair { -u32 prev_idx; +#define MAX_CALL_FRAMES 8 + +/* instruction history flags, used in bpf_jmp_history_entry.flags field */ +enum { +/* instruction references stack slot through PTR_TO_STACK register; +* we also store stack's frame number in lower 3 bits (MAX_CALL_FRAMES is 8) +* and accessed stack slot's index in next 6 bits (MAX_BPF_STACK is 512, +* 8 bytes per slot, so slot index (spi) is [0, 63]) +*/ +INSN_F_FRAMENO_MASK =0x7 ,/* 3 bits */ + +INSN_F_SPI_MASK =0x3f ,/* 6 bits */ +INSN_F_SPI_SHIFT =3 ,/* shifted 3 bits to the left */ + +INSN_F_STACK_ACCESS =BIT (9 ),/* we need 10 bits total */ +}; + +static_assert (INSN_F_FRAMENO_MASK +1 >=MAX_CALL_FRAMES ); +static_assert (INSN_F_SPI_MASK +1 >=MAX_BPF_STACK /8 ); + +struct bpf_jmp_history_entry {u32 idx; +/* insn idx can't be bigger than 1 million */ +u32 prev_idx :22 ; +/* special flags, e.g., whether insn is doing register stack spill/load */ +u32 flags :10 ; }; -#define MAX_CALL_FRAMES 8/* Maximum number of register states that can exist at once */ #define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)struct bpf_verifier_state {
@@ -407,7 +429,7 @@ struct bpf_verifier_state {* For most states jmp_history_cnt is [0-3]. * For loops can go up to ~40. */ -struct bpf_idx_pair *jmp_history; +struct bpf_jmp_history_entry *jmp_history;u32 jmp_history_cnt;u32 dfs_depth;u32 callback_unroll_depth;
@@ -641,6 +663,7 @@ struct bpf_verifier_env {int cur_stack; } cfg;struct backtrack_state bt; +struct bpf_jmp_history_entry *cur_hist_ent;u32 pass_cnt;/* number of times do_check() was called */ u32 subprog_cnt;/* number of instructions analyzed by the verifier */
kernel/bpf/verifier.c +102 -73
348 lines not on this page · raw message
tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +18 -5
@@ -541,11 +541,24 @@ static __u64 subprog_spill_reg_precise(void) SEC("?raw_tp") __success __log_level(2) -/* precision backtracking can't currently handle stack access not through r10, -* so we won't be able to mark stack slot fp-8 as precise, and so will -* fallback to forcing all as precise -*/ -__msg("mark_precise: frame0: falling back to forcing all scalars precise") +__msg("10: (0f) r1 += r7") +__msg("mark_precise: frame0: last_idx 10 first_idx 7 subseq_idx -1") +__msg("mark_precise: frame0: regs=r7 stack= before 9: (bf) r1 = r8") +__msg("mark_precise: frame0: regs=r7 stack= before 8: (27) r7 *= 4") +__msg("mark_precise: frame0: regs=r7 stack= before 7: (79) r7 = *(u64 *)(r10 -8)") +__msg("mark_precise: frame0: parent state regs= stack=-8: R0_w=2 R6_w=1 R8_rw=map_value(off=0,ks=4,vs=16,imm=0) R10=fp0 fp-8_rw=P1") +__msg("mark_precise: frame0: last_idx 18 first_idx 0 subseq_idx 7") +__msg("mark_precise: frame0: regs= stack=-8 before 18: (95) exit") +__msg("mark_precise: frame1: regs= stack= before 17: (0f) r0 += r2") +__msg("mark_precise: frame1: regs= stack= before 16: (79) r2 = *(u64 *)(r1 +0)") +__msg("mark_precise: frame1: regs= stack= before 15: (79) r0 = *(u64 *)(r10 -16)") +__msg("mark_precise: frame1: regs= stack= before 14: (7b) *(u64 *)(r10 -16) = r2") +__msg("mark_precise: frame1: regs= stack= before 13: (7b) *(u64 *)(r1 +0) = r2") +__msg("mark_precise: frame1: regs=r2 stack= before 6: (85) call pc+6") +__msg("mark_precise: frame0: regs=r2 stack= before 5: (bf) r2 = r6") +__msg("mark_precise: frame0: regs=r6 stack= before 4: (07) r1 += -8") +__msg("mark_precise: frame0: regs=r6 stack= before 3: (bf) r1 = r10") +__msg("mark_precise: frame0: regs=r6 stack= before 2: (b7) r6 = 1")__naked int subprog_spill_into_parent_stack_slot_precise (void ) { asm volatile (
tools/testing/selftests/bpf/verifier/precise.c +22 -16
@@ -140,10 +140,11 @@ .result = REJECT, }, { - "precise: ST insn causing spi > allocated_stack", + "precise: ST zero to stack insn is supported", .insns = {BPF_MOV64_REG (BPF_REG_3 ,BPF_REG_10 ),BPF_JMP_IMM (BPF_JNE ,BPF_REG_3 ,123 ,0 ), +/* not a register spill, so we stop precision propagation for R4 here */ BPF_ST_MEM (BPF_DW ,BPF_REG_3 ,-8 ,0 ),BPF_LDX_MEM (BPF_DW ,BPF_REG_4 ,BPF_REG_10 ,-8 ), BPF_MOV64_IMM(BPF_REG_0, -1),
@@ -157,11 +158,11 @@ mark_precise: frame0: last_idx 4 first_idx 2\ mark_precise: frame0: regs=r4 stack= before 4\ mark_precise: frame0: regs=r4 stack= before 3\ - mark_precise: frame0: regs= stack=-8 before 2\ - mark_precise: frame0: falling back to forcing all scalars precise\ - force_precise: frame0: forcing r0 to be precise\ mark_precise: frame0: last_idx 5 first_idx 5\ - mark_precise: frame0: parent state regs= stack=:", + mark_precise: frame0: parent state regs=r0 stack=:\ + mark_precise: frame0: last_idx 4 first_idx 2\ + mark_precise: frame0: regs=r0 stack= before 4\ + 5: R0=-1 R4=0", .result = VERBOSE_ACCEPT, .retval = -1, },
@@ -169,6 +170,8 @@ "precise: STX insn causing spi > allocated_stack", .insns = {BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_get_prandom_u32), +/* make later reg spill more interesting by having somewhat known scalar */ +BPF_ALU64_IMM (BPF_AND ,BPF_REG_0 ,0xff ),BPF_MOV64_REG (BPF_REG_3 ,BPF_REG_10 ),BPF_JMP_IMM (BPF_JNE ,BPF_REG_3 ,123 ,0 ), BPF_STX_MEM(BPF_DW, BPF_REG_3, BPF_REG_0, -8),
@@ -179,18 +182,21 @@ }, .prog_type = BPF_PROG_TYPE_XDP, .flags = BPF_F_TEST_STATE_FREQ, - .errstr ="mark_precise: frame0: last_idx 6 first_idx 6\ + .errstr ="mark_precise: frame0: last_idx 7 first_idx 7\ mark_precise: frame0: parent state regs=r4 stack=:\ -mark_precise: frame0: last_idx 5 first_idx 3\ -mark_precise: frame0: regs=r4 stack= before 5\ -mark_precise: frame0: regs=r4 stack= before 4\ -mark_precise: frame0: regs= stack=-8 before 3\ -mark_precise: frame0: falling back to forcing all scalars precise\ -force_precise: frame0: forcing r0 to be precise\ -force_precise: frame0: forcing r0 to be precise\ -force_precise: frame0: forcing r0 to be precise\ -force_precise: frame0: forcing r0 to be precise\ -mark_precise: frame0: last_idx 6 first_idx 6\ +mark_precise: frame0: last_idx 6 first_idx 4\ +mark_precise: frame0: regs=r4 stack= before 6: (b7) r0 = -1\ +mark_precise: frame0: regs=r4 stack= before 5: (79) r4 = *(u64 *)(r10 -8)\ +mark_precise: frame0: regs= stack=-8 before 4: (7b) *(u64 *)(r3 -8) = r0\ +mark_precise: frame0: parent state regs=r0 stack=:\ +mark_precise: frame0: last_idx 3 first_idx 3\ +mark_precise: frame0: regs=r0 stack= before 3: (55) if r3 != 0x7b goto pc+0\ +mark_precise: frame0: regs=r0 stack= before 2: (bf) r3 = r10\ +mark_precise: frame0: regs=r0 stack= before 1: (57) r0 &= 255\ +mark_precise: frame0: parent state regs=r0 stack=:\ +mark_precise: frame0: last_idx 0 first_idx 0\ +mark_precise: frame0: regs=r0 stack= before 0: (85) call bpf_get_prandom_u32#7\ +mark_precise: frame0: last_idx 7 first_idx 7\ mark_precise: frame0: parent state regs= stack=:", .result = VERBOSE_ACCEPT, .retval = -1,
Signature · 1 line
2.43.0
PATCH 2/10 selftests/bpf: add stack access precision test
In reply to Paul ChaignonFrom: Andrii Nakryiko <[email protected]>
[ Upstream commit 876301881c436bf38e83a2c0d276a24b642e4aab ]
Add a new selftests that validates precision tracking for stack access instruction, using both r10-based and non-r10-based accesses. For non-r10 ones we also make sure to have non-zero var_off to validate that final stack offset is tracked properly in instruction history information inside verifier.
--- .../bpf/progs/verifier_subprog_precision.c | 64 +++++++++++++++++-- 1 file changed, 59 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +59 -5
@@ -593,14 +593,68 @@ __naked int subprog_spill_into_parent_stack_slot_precise(void) ); } -__naked __noinline __used -static __u64 subprog_with_checkpoint(void) +SEC("?raw_tp") +__success __log_level(2) +__msg("17: (0f) r1 += r0") +__msg("mark_precise: frame0: last_idx 17 first_idx 0 subseq_idx -1") +__msg("mark_precise: frame0: regs=r0 stack= before 16: (bf) r1 = r7") +__msg("mark_precise: frame0: regs=r0 stack= before 15: (27) r0 *= 4") +__msg("mark_precise: frame0: regs=r0 stack= before 14: (79) r0 = *(u64 *)(r10 -16)") +__msg("mark_precise: frame0: regs= stack=-16 before 13: (7b) *(u64 *)(r7 -8) = r0") +__msg("mark_precise: frame0: regs=r0 stack= before 12: (79) r0 = *(u64 *)(r8 +16)") +__msg("mark_precise: frame0: regs= stack=-16 before 11: (7b) *(u64 *)(r8 +16) = r0") +__msg("mark_precise: frame0: regs=r0 stack= before 10: (79) r0 = *(u64 *)(r7 -8)") +__msg("mark_precise: frame0: regs= stack=-16 before 9: (7b) *(u64 *)(r10 -16) = r0") +__msg("mark_precise: frame0: regs=r0 stack= before 8: (07) r8 += -32") +__msg("mark_precise: frame0: regs=r0 stack= before 7: (bf) r8 = r10") +__msg("mark_precise: frame0: regs=r0 stack= before 6: (07) r7 += -8") +__msg("mark_precise: frame0: regs=r0 stack= before 5: (bf) r7 = r10") +__msg("mark_precise: frame0: regs=r0 stack= before 21: (95) exit") +__msg("mark_precise: frame1: regs=r0 stack= before 20: (bf) r0 = r1") +__msg("mark_precise: frame1: regs=r1 stack= before 4: (85) call pc+15") +__msg("mark_precise: frame0: regs=r1 stack= before 3: (bf) r1 = r6") +__msg("mark_precise: frame0: regs=r6 stack= before 2: (b7) r6 = 1") +__naked int stack_slot_aliases_precision (void ) { asmvolatile ( -"r0 = 0;" -/* guaranteed checkpoint if BPF_F_TEST_STATE_FREQ is used */ -"goto +0;" +"r6 = 1;" +/* pass r6 through r1 into subprog to get it back as r0; +* this whole chain will have to be marked as precise later +*/ +"r1 = r6;" +"call identity_subprog;" +/* let's setup two registers that are aliased to r10 */ +"r7 = r10;" +"r7 += -8;" /* r7 = r10 - 8 */ +"r8 = r10;" +"r8 += -32;" /* r8 = r10 - 32 */ +/* now spill subprog's return value (a r6 -> r1 -> r0 chain) +* a few times through different stack pointer regs, making +* sure to use r10, r7, and r8 both in LDX and STX insns, and +* *importantly* also using a combination of const var_off and +* insn->off to validate that we record final stack slot +* correctly, instead of relying on just insn->off derivation, +* which is only valid for r10-based stack offset +*/ +"*(u64 *)(r10 - 16) = r0;" +"r0 = *(u64 *)(r7 - 8);" /* r7 - 8 == r10 - 16 */ +"*(u64 *)(r8 + 16) = r0;" /* r8 + 16 = r10 - 16 */ +"r0 = *(u64 *)(r8 + 16);" +"*(u64 *)(r7 - 8) = r0;" +"r0 = *(u64 *)(r10 - 16);" +/* get ready to use r0 as an index into array to force precision */ +"r0 *= 4;" +"r1 = %[vals];" +/* here r0->r1->r6 chain is forced to be precise and has to be +* propagated back to the beginning, including through the +* subprog call and all the stack spills and loads +*/ +"r1 += r0;" +"r0 = *(u32 *)(r1 + 0);" "exit;" + : + : __imm_ptr(vals) + : __clobber_common, "r6" ); }
Signature · 1 line
2.43.0
PATCH 3/10 bpf: preserve STACK_ZERO slots on partial reg spills
In reply to Paul ChaignonFrom: Andrii Nakryiko <[email protected]>
[ Upstream commit eaf18febd6ebc381aeb61543705148b3e28c7c47 ]
Instead of always forcing STACK_ZERO slots to STACK_MISC, preserve it in situations where this is possible. E.g., when spilling register as 1/2/4-byte subslots on the stack, all the remaining bytes in the stack slot do not automatically become unknown. If we knew they contained zeroes, we can preserve those STACK_ZERO markers.
Add a helper mark_stack_slot_misc(), similar to scrub_spilled_slot(), but that doesn't overwrite either STACK_INVALID nor STACK_ZERO. Note that we need to take into account possibility of being in unprivileged mode, in which case STACK_INVALID is forced to STACK_MISC for correctness, as treating STACK_INVALID as equivalent STACK_MISC is only enabled in privileged mode.
--- kernel/bpf/verifier.c | 28 +++++++++++++++++++++++----- 1 file changed, 23 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +23 -5
@@ -1347,6 +1347,21 @@ static bool is_spilled_scalar_reg(const struct bpf_stack_state *stack) stack->spilled_ptr.type ==SCALAR_VALUE ; } +/* Mark stack slot as STACK_MISC, unless it is already STACK_INVALID, in which +* case they are equivalent, or it's STACK_ZERO, in which case we preserve +* more precise STACK_ZERO. +* Note, in uprivileged mode leaving STACK_INVALID is wrong, so we take +* env->allow_ptr_leaks into account and force STACK_MISC, if necessary. +*/ +static void mark_stack_slot_misc (struct bpf_verifier_env *env,u8 *stype) +{ +if (*stype ==STACK_ZERO ) +return ; +if (env->allow_ptr_leaks && *stype ==STACK_INVALID ) +return ; + *stype =STACK_MISC ; +} +static void scrub_spilled_slot (u8 *stype) {if (*stype !=STACK_INVALID )
@@ -4577,7 +4592,8 @@ static void copy_register_state(struct bpf_reg_state *dst, const struct bpf_reg_ dst->live = live; } -static void save_register_state (struct bpf_func_state *state, +static void save_register_state (struct bpf_verifier_env *env, +struct bpf_func_state *state,int spi,struct bpf_reg_state *reg,int size) {
@@ -4592,7 +4608,7 @@ static void save_register_state(struct bpf_func_state *state,/* size < 8 bytes spill */ for (; i; i--) -scrub_spilled_slot (&state->stack[spi].slot_type[i -1 ]); +mark_stack_slot_misc (env, &state->stack[spi].slot_type[i -1 ]); }static bool is_bpf_st_mem (struct bpf_insn *insn)
@@ -4652,7 +4668,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,mark_stack_slot_scratched (env, spi);if (reg && !(off %BPF_REG_SIZE ) &®ister_is_bounded (reg) && !register_is_null (reg) && env->bpf_capable) { -save_register_state (state, spi, reg, size); +save_register_state (env, state, spi, reg, size);/* Break the relation on a narrowing spill. */ if (fls64 (reg->umax_value) >BITS_PER_BYTE * size) state->stack[spi].spilled_ptr.id =0 ;
@@ -4662,7 +4678,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,__mark_reg_known (&fake_reg, insn->imm); fake_reg.type =SCALAR_VALUE ; -save_register_state (state, spi, &fake_reg, size); +save_register_state (env, state, spi, &fake_reg, size); insn_flags =0 ;/* not a register spill */ }else if (reg &&is_spillable_regtype (reg->type)) {/* register containing pointer is being spilled into stack */
@@ -4675,7 +4691,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,verbose (env,"cannot spill pointers to stack into stack frame of the caller\n" );return -EINVAL ; } -save_register_state (state, spi, reg, size); +save_register_state (env, state, spi, reg, size); }else {u8 type =STACK_MISC ;
@@ -4942,6 +4958,8 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,continue ;if (type ==STACK_MISC )continue ; +if (type ==STACK_ZERO ) +continue ;if (type ==STACK_INVALID && env->allow_uninit_stack)continue ; verbose(env, "invalid read from stack off %d+%d size %d\n",
Signature · 1 line
2.43.0
PATCH 4/10 selftests/bpf: validate STACK_ZERO is preserved on subreg spill
In reply to Paul ChaignonFrom: Andrii Nakryiko <[email protected]>
[ Upstream commit b33ceb6a3d2ee07fdd836373383a6d4783581324 ]
Add tests validating that STACK_ZERO slots are preserved when slot is partially overwritten with subregister spill.
--- .../selftests/bpf/progs/verifier_spill_fill.c | 40 +++++++++++++++++++ 1 file changed, 40 insertions(+)
tools/testing/selftests/bpf/progs/verifier_spill_fill.c +40 -0
@@ -4,6 +4,7 @@#include <linux/bpf.h> #include <bpf/bpf_helpers.h> #include "bpf_misc.h" +#include <../../../tools/include/linux/filter.h> struct { __uint(type, BPF_MAP_TYPE_RINGBUF);
@@ -450,4 +451,43 @@ l0_%=: r1 >>= 16; \ : __clobber_all); } +SEC("raw_tp") +__log_level(2) +__success +__msg("fp-8=0m??mmmm") +__msg("fp-16=00mm??mm") +__msg("fp-24=00mm???m") +__naked void spill_subregs_preserve_stack_zero (void ) +{ + asmvolatile ( +"call %[bpf_get_prandom_u32];" + +/* 32-bit subreg spill with ZERO, MISC, and INVALID */ +".8byte %[fp1_u8_st_zero];" /* ZERO, LLVM-18+: *(u8 *)(r10 -1) = 0; */ +"*(u8 *)(r10 -2) = r0;" /* MISC */ +/* fp-3 and fp-4 stay INVALID */ +"*(u32 *)(r10 -8) = r0;" + +/* 16-bit subreg spill with ZERO, MISC, and INVALID */ +".8byte %[fp10_u16_st_zero];" /* ZERO, LLVM-18+: *(u16 *)(r10 -10) = 0; */ +"*(u16 *)(r10 -12) = r0;" /* MISC */ +/* fp-13 and fp-14 stay INVALID */ +"*(u16 *)(r10 -16) = r0;" + +/* 8-bit subreg spill with ZERO, MISC, and INVALID */ +".8byte %[fp18_u16_st_zero];" /* ZERO, LLVM-18+: *(u16 *)(r18 -10) = 0; */ +"*(u16 *)(r10 -20) = r0;" /* MISC */ +/* fp-21, fp-22, and fp-23 stay INVALID */ +"*(u8 *)(r10 -24) = r0;" + +"r0 = 0;" +"exit;" + : + : __imm(bpf_get_prandom_u32), +__imm_insn (fp1_u8_st_zero,BPF_ST_MEM (BPF_B ,BPF_REG_FP ,-1 ,0 )), +__imm_insn (fp10_u16_st_zero,BPF_ST_MEM (BPF_H ,BPF_REG_FP ,-10 ,0 )), +__imm_insn (fp18_u16_st_zero,BPF_ST_MEM (BPF_H ,BPF_REG_FP ,-18 ,0 )) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.0
PATCH 5/10 bpf: preserve constant zero when doing partial register restore
In reply to Paul ChaignonFrom: Andrii Nakryiko <[email protected]>
[ Upstream commit e322f0bcb8d371f4606eaf141c7f967e1a79bcb7 ]
Similar to special handling of STACK_ZERO, when reading 1/2/4 bytes from stack from slot that has register spilled into it and that register has a constant value zero, preserve that zero and mark spilled register as precise for that. This makes spilled const zero register and STACK_ZERO cases equivalent in their behavior.
--- kernel/bpf/verifier.c | 25 +++++++++++++++++++++---- 1 file changed, 21 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +21 -4
@@ -4952,22 +4952,39 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env,copy_register_state (&state->regs[dst_regno], reg); state->regs[dst_regno].subreg_def = subreg_def; }else { +int spill_cnt =0 , zero_cnt =0 ; +for (i =0 ; i < size; i++) { type = stype[(slot - i) %BPF_REG_SIZE ]; -if (type ==STACK_SPILL ) +if (type ==STACK_SPILL ) { + spill_cnt++;continue ; + }if (type ==STACK_MISC )continue ; -if (type ==STACK_ZERO ) +if (type ==STACK_ZERO ) { + zero_cnt++;continue ; + }if (type ==STACK_INVALID && env->allow_uninit_stack)continue ;verbose (env,"invalid read from stack off %d+%d size %d\n" , off, i, size);return -EACCES ; } -mark_reg_unknown (env, state->regs, dst_regno); - insn_flags =0 ;/* not restoring original register state */ + +if (spill_cnt == size && +tnum_is_const (reg->var_off) && reg->var_off.value ==0 ) { +__mark_reg_const_zero (&state->regs[dst_regno]); +/* this IS register fill, so keep insn_flags */ + }else if (zero_cnt == size) { +/* similarly to mark_reg_stack_read(), preserve zeroes */ +__mark_reg_const_zero (&state->regs[dst_regno]); + insn_flags =0 ;/* not restoring original register state */ + }else { +mark_reg_unknown (env, state->regs, dst_regno); + insn_flags =0 ;/* not restoring original register state */ + } } state->regs[dst_regno].live |=REG_LIVE_WRITTEN ; }else if (dst_regno >=0 ) {
Signature · 1 line
2.43.0
PATCH 6/10 selftests/bpf: validate zero preservation for sub-slot loads
In reply to Paul ChaignonFrom: Andrii Nakryiko <[email protected]>
[ Upstream commit add1cd7f22e61756987865ada9fe95cd86569025 ]
Validate that 1-, 2-, and 4-byte loads from stack slots not aligned on 8-byte boundary still preserve zero, when loading from all-STACK_ZERO sub-slots, or when stack sub-slots are covered by spilled register with known constant zero value.
--- .../selftests/bpf/progs/verifier_spill_fill.c | 71 +++++++++++++++++++ 1 file changed, 71 insertions(+)
tools/testing/selftests/bpf/progs/verifier_spill_fill.c +71 -0
@@ -490,4 +490,75 @@ __naked void spill_subregs_preserve_stack_zero(void) : __clobber_all); } +char single_byte_buf[1] SEC(".data.single_byte_buf"); + +SEC("raw_tp") +__log_level(2) +__success +__naked void partial_stack_load_preserves_zeros (void ) +{ + asmvolatile ( +/* fp-8 is all STACK_ZERO */ +".8byte %[fp8_st_zero];" /* LLVM-18+: *(u64 *)(r10 -8) = 0; */ + +/* fp-16 is const zero register */ +"r0 = 0;" +"*(u64 *)(r10 -16) = r0;" + +/* load single U8 from non-aligned STACK_ZERO slot */ +"r1 = %[single_byte_buf];" +"r2 = *(u8 *)(r10 -1);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +/* load single U8 from non-aligned ZERO REG slot */ +"r1 = %[single_byte_buf];" +"r2 = *(u8 *)(r10 -9);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +/* load single U16 from non-aligned STACK_ZERO slot */ +"r1 = %[single_byte_buf];" +"r2 = *(u16 *)(r10 -2);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +/* load single U16 from non-aligned ZERO REG slot */ +"r1 = %[single_byte_buf];" +"r2 = *(u16 *)(r10 -10);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +/* load single U32 from non-aligned STACK_ZERO slot */ +"r1 = %[single_byte_buf];" +"r2 = *(u32 *)(r10 -4);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +/* load single U32 from non-aligned ZERO REG slot */ +"r1 = %[single_byte_buf];" +"r2 = *(u32 *)(r10 -12);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +/* for completeness, load U64 from STACK_ZERO slot */ +"r1 = %[single_byte_buf];" +"r2 = *(u64 *)(r10 -8);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +/* for completeness, load U64 from ZERO REG slot */ +"r1 = %[single_byte_buf];" +"r2 = *(u64 *)(r10 -16);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +"r0 = 0;" +"exit;" + : + : __imm_ptr(single_byte_buf), +__imm_insn (fp8_st_zero,BPF_ST_MEM (BPF_DW ,BPF_REG_FP ,-8 ,0 )) + : __clobber_common); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.0
PATCH 7/10 bpf: track aligned STACK_ZERO cases as imprecise spilled registers
In reply to Paul ChaignonFrom: Andrii Nakryiko <[email protected]>
[ Upstream commit 18a433b62061e3d787bfc3e670fa711fecbd7cb4 ]
Now that precision backtracing is supporting register spill/fill to/from stack, there is another oportunity to be exploited here: minimizing precise STACK_ZERO cases. With a simple code change we can rely on initially imprecise register spill tracking for cases when register spilled to stack was a known zero.
This is a very common case for initializing on the stack variables, including rather large structures. Often times zero has no special meaning for the subsequent BPF program logic and is often overwritten with non-zero values soon afterwards. But due to STACK_ZERO vs STACK_MISC tracking, such initial zero initialization actually causes duplication of verifier states as STACK_ZERO is clearly different than STACK_MISC or spilled SCALAR_VALUE register.
The effect of this (now) trivial change is huge, as can be seen below. These are differences between BPF selftests, Cilium, and Meta-internal BPF object files relative to previous patch in this series. You can see improvements ranging from single-digit percentage improvement for instructions and states, all the way to 50-60% reduction for some of Meta-internal host agent programs, and even some Cilium programs.
For Meta-internal ones I left only the differences for largest BPF object files by states/instructions, as there were too many differences in the overall output. All the differences were improvements, reducting number of states and thus instructions validated.
Note, Meta-internal BPF object file names are not printed below. Many copies of balancer_ingress are actually many different configurations of Katran, so they are different BPF programs, which explains state reduction going from -16% all the way to 31%, depending on BPF program logic complexity.
I also tooked a closer look at a few small-ish BPF programs to validate the behavior. Let's take bpf_iter_netrlink.bpf.o (first row below). While it's just 8 vs 5 states, verifier log is still pretty long to include it here. But the reduction in states is due to the following piece of C code:
unsigned long ino;
...
sk = s->sk_socket;
if (!sk) {
ino = 0;
} else {
inode = SOCK_INODE(sk);
bpf_probe_read_kernel(&ino, sizeof(ino), &inode->i_ino);
}
BPF_SEQ_PRINTF(seq, "%-8u %-8lu\n", s->sk_drops.counter, ino);
return 0;You can see that in some situations ino is zero-initialized, while in others it's unknown value filled out by bpf_probe_read_kernel(). Before this change code after if/else branches have to be validated twice. Once with (precise) ino == 0, due to eager STACK_ZERO logic, and then again for when ino is just STACK_MISC. But BPF_SEQ_PRINTF() doesn't care about precise value of ino, so with the change in this patch verifier is able to prune states from after one of the branches, reducing number of total states (and instructions) required for successful validation.
Similar principle applies to bigger real-world applications, just at a much larger scale.
SELFTESTS
=========
File Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) --------------------------------------- ----------------------- --------- --------- --------------- ---------- ---------- ------------- bpf_iter_netlink.bpf.linked3.o dump_netlink 148 104 -44 (-29.73%) 8 5 -3 (-37.50%) bpf_iter_unix.bpf.linked3.o dump_unix 8474 8404 -70 (-0.83%) 151 147 -4 (-2.65%) bpf_loop.bpf.linked3.o stack_check 560 324 -236 (-42.14%) 42 24 -18 (-42.86%) local_storage_bench.bpf.linked3.o get_local 120 77 -43 (-35.83%) 9 6 -3 (-33.33%) loop6.bpf.linked3.o trace_virtqueue_add_sgs 10167 9868 -299 (-2.94%) 226 206 -20 (-8.85%) pyperf600_bpf_loop.bpf.linked3.o on_event 4872 3423 -1449 (-29.74%) 322 229 -93 (-28.88%) strobemeta.bpf.linked3.o on_event 180697 176036 -4661 (-2.58%) 4780 4734 -46 (-0.96%) test_cls_redirect.bpf.linked3.o cls_redirect 65594 65401 -193 (-0.29%) 4230 4212 -18 (-0.43%) test_global_func_args.bpf.linked3.o test_cls 145 136 -9 (-6.21%) 10 9 -1 (-10.00%) test_l4lb.bpf.linked3.o balancer_ingress 4760 2612 -2148 (-45.13%) 113 102 -11 (-9.73%) test_l4lb_noinline.bpf.linked3.o balancer_ingress 4845 4877 +32 (+0.66%) 219 221 +2 (+0.91%) test_l4lb_noinline_dynptr.bpf.linked3.o balancer_ingress 2072 2087 +15 (+0.72%) 97 98 +1 (+1.03%) test_seg6_loop.bpf.linked3.o __add_egr_x 12440 9975 -2465 (-19.82%) 364 353 -11 (-3.02%) test_tcp_hdr_options.bpf.linked3.o estab 2558 2572 +14 (+0.55%) 179 180 +1 (+0.56%) test_xdp_dynptr.bpf.linked3.o _xdp_tx_iptunnel 645 596 -49 (-7.60%) 26 24 -2 (-7.69%) test_xdp_noinline.bpf.linked3.o balancer_ingress_v6 3520 3516 -4 (-0.11%) 216 216 +0 (+0.00%) xdp_synproxy_kern.bpf.linked3.o syncookie_tc 82661 81241 -1420 (-1.72%) 5073 5155 +82 (+1.62%) xdp_synproxy_kern.bpf.linked3.o syncookie_xdp 84964 82297 -2667 (-3.14%) 5130 5157 +27 (+0.53%)
META-INTERNAL
=============
Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) -------------------------------------- --------- --------- ----------------- ---------- ---------- --------------- balancer_ingress 27925 23608 -4317 (-15.46%) 1488 1482 -6 (-0.40%) balancer_ingress 31824 27546 -4278 (-13.44%) 1658 1652 -6 (-0.36%) balancer_ingress 32213 27935 -4278 (-13.28%) 1689 1683 -6 (-0.36%) balancer_ingress 32213 27935 -4278 (-13.28%) 1689 1683 -6 (-0.36%) balancer_ingress 31824 27546 -4278 (-13.44%) 1658 1652 -6 (-0.36%) balancer_ingress 38647 29562 -9085 (-23.51%) 2069 1835 -234 (-11.31%) balancer_ingress 38647 29562 -9085 (-23.51%) 2069 1835 -234 (-11.31%) balancer_ingress 40339 30792 -9547 (-23.67%) 2193 1934 -259 (-11.81%) balancer_ingress 37321 29055 -8266 (-22.15%) 1972 1795 -177 (-8.98%) balancer_ingress 38176 29753 -8423 (-22.06%) 2008 1831 -177 (-8.81%) balancer_ingress 29193 20910 -8283 (-28.37%) 1599 1422 -177 (-11.07%) balancer_ingress 30013 21452 -8561 (-28.52%) 1645 1447 -198 (-12.04%) balancer_ingress 28691 24290 -4401 (-15.34%) 1545 1531 -14 (-0.91%) balancer_ingress 34223 28965 -5258 (-15.36%) 1984 1875 -109 (-5.49%) balancer_ingress 35481 26158 -9323 (-26.28%) 2095 1806 -289 (-13.79%) balancer_ingress 35481 26158 -9323 (-26.28%) 2095 1806 -289 (-13.79%) balancer_ingress 35868 26455 -9413 (-26.24%) 2140 1827 -313 (-14.63%) balancer_ingress 35868 26455 -9413 (-26.24%) 2140 1827 -313 (-14.63%) balancer_ingress 35481 26158 -9323 (-26.28%) 2095 1806 -289 (-13.79%) balancer_ingress 35481 26158 -9323 (-26.28%) 2095 1806 -289 (-13.79%) balancer_ingress 34844 29485 -5359 (-15.38%) 2036 1918 -118 (-5.80%) fbflow_egress 3256 2652 -604 (-18.55%) 218 192 -26 (-11.93%) fbflow_ingress 1026 944 -82 (-7.99%) 70 63 -7 (-10.00%) sslwall_tc_egress 8424 7360 -1064 (-12.63%) 498 458 -40 (-8.03%) syar_accept_protect 15040 9539 -5501 (-36.58%) 364 220 -144 (-39.56%) syar_connect_tcp_v6 15036 9535 -5501 (-36.59%) 360 216 -144 (-40.00%) syar_connect_udp_v4 15039 9538 -5501 (-36.58%) 361 217 -144 (-39.89%) syar_connect_connect4_protect4 24805 15833 -8972 (-36.17%) 756 480 -276 (-36.51%) syar_lsm_file_open 167772 151813 -15959 (-9.51%) 1836 1667 -169 (-9.20%) syar_namespace_create_new 14805 9304 -5501 (-37.16%) 353 209 -144 (-40.79%) syar_python3_detect 17531 12030 -5501 (-31.38%) 391 247 -144 (-36.83%) syar_ssh_post_fork 16412 10911 -5501 (-33.52%) 405 261 -144 (-35.56%) syar_enter_execve 14728 9227 -5501 (-37.35%) 345 201 -144 (-41.74%) syar_enter_execveat 14728 9227 -5501 (-37.35%) 345 201 -144 (-41.74%) syar_exit_execve 16622 11121 -5501 (-33.09%) 376 232 -144 (-38.30%) syar_exit_execveat 16622 11121 -5501 (-33.09%) 376 232 -144 (-38.30%) syar_syscalls_kill 15288 9787 -5501 (-35.98%) 398 254 -144 (-36.18%) syar_task_enter_pivot_root 14898 9397 -5501 (-36.92%) 357 213 -144 (-40.34%) syar_syscalls_setreuid 16678 11177 -5501 (-32.98%) 429 285 -144 (-33.57%) syar_syscalls_setuid 16678 11177 -5501 (-32.98%) 429 285 -144 (-33.57%) syar_syscalls_process_vm_readv 14959 9458 -5501 (-36.77%) 364 220 -144 (-39.56%) syar_syscalls_process_vm_writev 15757 10256 -5501 (-34.91%) 390 246 -144 (-36.92%) do_uprobe 15519 10018 -5501 (-35.45%) 373 229 -144 (-38.61%) edgewall 179715 55783 -123932 (-68.96%) 12607 3999 -8608 (-68.28%) bictcp_state 7570 4131 -3439 (-45.43%) 496 269 -227 (-45.77%) cubictcp_state 7570 4131 -3439 (-45.43%) 496 269 -227 (-45.77%) tcp_rate_skb_delivered 447 272 -175 (-39.15%) 29 18 -11 (-37.93%) kprobe__bbr_set_state 4566 2615 -1951 (-42.73%) 209 124 -85 (-40.67%) kprobe__bictcp_state 4566 2615 -1951 (-42.73%) 209 124 -85 (-40.67%) inet_sock_set_state 1501 1337 -164 (-10.93%) 93 85 -8 (-8.60%) tcp_retransmit_skb 1145 981 -164 (-14.32%) 67 59 -8 (-11.94%) tcp_retransmit_synack 1183 951 -232 (-19.61%) 67 55 -12 (-17.91%) bpf_tcptuner 1459 1187 -272 (-18.64%) 99 80 -19 (-19.19%) tw_egress 801 776 -25 (-3.12%) 69 66 -3 (-4.35%) tw_ingress 795 770 -25 (-3.14%) 69 66 -3 (-4.35%) ttls_tc_ingress 19025 19383 +358 (+1.88%) 470 465 -5 (-1.06%) ttls_nat_egress 490 299 -191 (-38.98%) 33 20 -13 (-39.39%) ttls_nat_ingress 448 285 -163 (-36.38%) 32 21 -11 (-34.38%) tw_twfw_egress 511127 212071 -299056 (-58.51%) 16733 8504 -8229 (-49.18%) tw_twfw_ingress 500095 212069 -288026 (-57.59%) 16223 8504 -7719 (-47.58%) tw_twfw_tc_eg 511113 212064 -299049 (-58.51%) 16732 8504 -8228 (-49.18%) tw_twfw_tc_in 500095 212069 -288026 (-57.59%) 16223 8504 -7719 (-47.58%) tw_twfw_egress 12632 12435 -197 (-1.56%) 276 260 -16 (-5.80%) tw_twfw_ingress 12631 12454 -177 (-1.40%) 278 261 -17 (-6.12%) tw_twfw_tc_eg 12595 12435 -160 (-1.27%) 274 259 -15 (-5.47%) tw_twfw_tc_in 12631 12454 -177 (-1.40%) 278 261 -17 (-6.12%) tw_xdp_dump 266 209 -57 (-21.43%) 9 8 -1 (-11.11%)
CILIUM
=========
File Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) ------------- -------------------------------- --------- --------- ---------------- ---------- ---------- -------------- bpf_host.o cil_to_netdev 6047 4578 -1469 (-24.29%) 362 249 -113 (-31.22%) bpf_host.o handle_lxc_traffic 2227 1585 -642 (-28.83%) 156 103 -53 (-33.97%) bpf_host.o tail_handle_ipv4_from_netdev 2244 1458 -786 (-35.03%) 163 106 -57 (-34.97%) bpf_host.o tail_handle_nat_fwd_ipv4 21022 10479 -10543 (-50.15%) 1289 670 -619 (-48.02%) bpf_host.o tail_handle_nat_fwd_ipv6 15433 11375 -4058 (-26.29%) 905 643 -262 (-28.95%) bpf_host.o tail_ipv4_host_policy_ingress 2219 1367 -852 (-38.40%) 161 96 -65 (-40.37%) bpf_host.o tail_nodeport_nat_egress_ipv4 22460 19862 -2598 (-11.57%) 1469 1293 -176 (-11.98%) bpf_host.o tail_nodeport_nat_ingress_ipv4 5526 3534 -1992 (-36.05%) 366 243 -123 (-33.61%) bpf_host.o tail_nodeport_nat_ingress_ipv6 5132 4256 -876 (-17.07%) 241 219 -22 (-9.13%) bpf_host.o tail_nodeport_nat_ipv6_egress 3702 3542 -160 (-4.32%) 215 205 -10 (-4.65%) bpf_lxc.o tail_handle_nat_fwd_ipv4 21022 10479 -10543 (-50.15%) 1289 670 -619 (-48.02%) bpf_lxc.o tail_handle_nat_fwd_ipv6 15433 11375 -4058 (-26.29%) 905 643 -262 (-28.95%) bpf_lxc.o tail_ipv4_ct_egress 5073 3374 -1699 (-33.49%) 262 172 -90 (-34.35%) bpf_lxc.o tail_ipv4_ct_ingress 5093 3385 -1708 (-33.54%) 262 172 -90 (-34.35%) bpf_lxc.o tail_ipv4_ct_ingress_policy_only 5093 3385 -1708 (-33.54%) 262 172 -90 (-34.35%) bpf_lxc.o tail_ipv6_ct_egress 4593 3878 -715 (-15.57%) 194 151 -43 (-22.16%) bpf_lxc.o tail_ipv6_ct_ingress 4606 3891 -715 (-15.52%) 194 151 -43 (-22.16%) bpf_lxc.o tail_ipv6_ct_ingress_policy_only 4606 3891 -715 (-15.52%) 194 151 -43 (-22.16%) bpf_lxc.o tail_nodeport_nat_ingress_ipv4 5526 3534 -1992 (-36.05%) 366 243 -123 (-33.61%) bpf_lxc.o tail_nodeport_nat_ingress_ipv6 5132 4256 -876 (-17.07%) 241 219 -22 (-9.13%) bpf_overlay.o tail_handle_nat_fwd_ipv4 20524 10114 -10410 (-50.72%) 1271 638 -633 (-49.80%) bpf_overlay.o tail_nodeport_nat_egress_ipv4 22718 19490 -3228 (-14.21%) 1475 1275 -200 (-13.56%) bpf_overlay.o tail_nodeport_nat_ingress_ipv4 5526 3534 -1992 (-36.05%) 366 243 -123 (-33.61%) bpf_overlay.o tail_nodeport_nat_ingress_ipv6 5132 4256 -876 (-17.07%) 241 219 -22 (-9.13%) bpf_overlay.o tail_nodeport_nat_ipv6_egress 3638 3548 -90 (-2.47%) 209 203 -6 (-2.87%) bpf_overlay.o tail_rev_nodeport_lb4 4368 3820 -548 (-12.55%) 248 215 -33 (-13.31%) bpf_overlay.o tail_rev_nodeport_lb6 2867 2428 -439 (-15.31%) 167 140 -27 (-16.17%) bpf_sock.o cil_sock6_connect 1718 1703 -15 (-0.87%) 100 99 -1 (-1.00%) bpf_xdp.o tail_handle_nat_fwd_ipv4 12917 12443 -474 (-3.67%) 875 849 -26 (-2.97%) bpf_xdp.o tail_handle_nat_fwd_ipv6 13515 13264 -251 (-1.86%) 715 702 -13 (-1.82%) bpf_xdp.o tail_lb_ipv4 39492 36367 -3125 (-7.91%) 2430 2251 -179 (-7.37%) bpf_xdp.o tail_lb_ipv6 80441 78058 -2383 (-2.96%) 3647 3523 -124 (-3.40%) bpf_xdp.o tail_nodeport_ipv6_dsr 1038 901 -137 (-13.20%) 61 55 -6 (-9.84%) bpf_xdp.o tail_nodeport_nat_egress_ipv4 13027 12096 -931 (-7.15%) 868 809 -59 (-6.80%) bpf_xdp.o tail_nodeport_nat_ingress_ipv4 7617 5900 -1717 (-22.54%) 522 413 -109 (-20.88%) bpf_xdp.o tail_nodeport_nat_ingress_ipv6 7575 7395 -180 (-2.38%) 383 374 -9 (-2.35%) bpf_xdp.o tail_rev_nodeport_lb4 6808 6739 -69 (-1.01%) 403 396 -7 (-1.74%) bpf_xdp.o tail_rev_nodeport_lb6 16173 15847 -326 (-2.02%) 1010 990 -20 (-1.98%)
--- kernel/bpf/verifier.c | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +7 -3
@@ -4666,8 +4666,7 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,return err;mark_stack_slot_scratched (env, spi); -if (reg && !(off %BPF_REG_SIZE ) &®ister_is_bounded (reg) && - !register_is_null (reg) && env->bpf_capable) { +if (reg && !(off %BPF_REG_SIZE ) &®ister_is_bounded (reg) && env->bpf_capable) {save_register_state (env, state, spi, reg, size);/* Break the relation on a narrowing spill. */ if (fls64 (reg->umax_value) >BITS_PER_BYTE * size)
@@ -4716,7 +4715,12 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,/* when we zero initialize stack slots mark them as such */ if ((reg &®ister_is_null (reg)) || (!reg &&is_bpf_st_mem (insn) && insn->imm ==0 )) { -/* backtracking doesn't work for STACK_ZERO yet. */ +/* STACK_ZERO case happened because register spill +* wasn't properly aligned at the stack slot boundary, +* so it's not a register spill anymore; force +* originating register to be precise to make +* STACK_ZERO correct for subsequent states +*/ err =mark_chain_precision (env, value_regno);if (err)return err;
Signature · 1 line
2.43.0
PATCH 8/10 selftests/bpf: validate precision logic in partial_stack_load_preserves_zeros
In reply to Paul ChaignonFrom: Andrii Nakryiko <[email protected]>
[ Upstream commit 064e0bea19b356c5d5f48a4549d80a3c03ce898b ]
Enhance partial_stack_load_preserves_zeros subtest with detailed precision propagation log checks. We know expect fp-16 to be spilled, initially imprecise, zero const register, which is later marked as precise even when partial stack slot load is performed, even if it's not a register fill (!).
--- .../selftests/bpf/progs/verifier_spill_fill.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)
tools/testing/selftests/bpf/progs/verifier_spill_fill.c +16 -0
@@ -495,6 +495,22 @@ char single_byte_buf[1] SEC(".data.single_byte_buf"); SEC("raw_tp") __log_level(2) __success +/* make sure fp-8 is all STACK_ZERO */ +__msg("2: (7a) *(u64 *)(r10 -8) = 0 ; R10=fp0 fp-8_w=00000000") +/* but fp-16 is spilled IMPRECISE zero const reg */ +__msg ("4: (7b) *(u64 *)(r10 -16) = r0 ; R0_w=0 R10=fp0 fp-16_w=0" ) +/* and now check that precision propagation works even for such tricky case */ +__msg("10: (71) r2 = *(u8 *)(r10 -9) ; R2_w=P0 R10=fp0 fp-16_w=0") +__msg("11: (0f) r1 += r2") +__msg("mark_precise: frame0: last_idx 11 first_idx 0 subseq_idx -1") +__msg("mark_precise: frame0: regs=r2 stack= before 10: (71) r2 = *(u8 *)(r10 -9)") +__msg("mark_precise: frame0: regs= stack=-16 before 9: (bf) r1 = r6") +__msg("mark_precise: frame0: regs= stack=-16 before 8: (73) *(u8 *)(r1 +0) = r2") +__msg("mark_precise: frame0: regs= stack=-16 before 7: (0f) r1 += r2") +__msg("mark_precise: frame0: regs= stack=-16 before 6: (71) r2 = *(u8 *)(r10 -1)") +__msg("mark_precise: frame0: regs= stack=-16 before 5: (bf) r1 = r6") +__msg("mark_precise: frame0: regs= stack=-16 before 4: (7b) *(u64 *)(r10 -16) = r0") +__msg("mark_precise: frame0: regs=r0 stack= before 3: (b7) r0 = 0")__naked void partial_stack_load_preserves_zeros (void ) { asm volatile (
Signature · 1 line
2.43.0
PATCH 9/10 bpf: handle fake register spill to stack with BPF_ST_MEM instruction
In reply to Paul ChaignonFrom: Andrii Nakryiko <[email protected]>
[ Upstream commit 482d548d40b0af9af730e4869903d4433e44f014 ]
When verifier validates BPF_ST_MEM instruction that stores known constant to stack (e.g., *(u64 *)(r10 - 8) = 123), it effectively spills a fake register with a constant (but initially imprecise) value to a stack slot. Because read-side logic treats it as a proper register fill from stack slot, we need to mark such stack slot initialization as INSN_F_STACK_ACCESS instruction to stop precision backtracking from missing it.
--- kernel/bpf/verifier.c | 1 - 1 file changed, 1 deletion(-)
kernel/bpf/verifier.c +0 -1
@@ -4678,7 +4678,6 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,__mark_reg_known (&fake_reg, insn->imm); fake_reg.type =SCALAR_VALUE ;save_register_state (env, state, spi, &fake_reg, size); - insn_flags =0 ;/* not a register spill */ }else if (reg &&is_spillable_regtype (reg->type)) {/* register containing pointer is being spilled into stack */ if (size !=BPF_REG_SIZE ) {
Signature · 1 line
2.43.0
PATCH 10/10 selftests/bpf: validate fake register spill/fill precision backtracking logic
In reply to Paul ChaignonFrom: Andrii Nakryiko <[email protected]>
[ Upstream commit 7d8ed51bcb32716a40d71043fcd01c4118858c51 ]
Add two tests validating that verifier's precision backtracking logic handles BPF_ST_MEM instructions that produce fake register spill into register slot. This is happening when non-zero constant is written directly to a slot, e.g., *(u64 *)(r10 -8) = 123.
Add both full 64-bit register spill, as well as 32-bit "sub-spill".
[ Note: Adapted the expected log format for the selftests because it
changed later on in commits 67d43dfbb42d, 0c95c9fdb696, and 1db747d75b1d. ]
--- .../selftests/bpf/progs/verifier_spill_fill.c | 154 ++++++++++++++++++ 1 file changed, 154 insertions(+)
tools/testing/selftests/bpf/progs/verifier_spill_fill.c +154 -0
@@ -577,4 +577,158 @@ __naked void partial_stack_load_preserves_zeros(void) : __clobber_common); } +char two_byte_buf[2] SEC(".data.two_byte_buf"); + +SEC("raw_tp") +__log_level(2) __flag(BPF_F_TEST_STATE_FREQ) +__success +/* make sure fp-8 is IMPRECISE fake register spill */ +__msg ("3: (7a) *(u64 *)(r10 -8) = 1 ; R10=fp0 fp-8_w=1" ) +/* and fp-16 is spilled IMPRECISE const reg */ +__msg ("5: (7b) *(u64 *)(r10 -16) = r0 ; R0_w=1 R10=fp0 fp-16_w=1" ) +/* validate load from fp-8, which was initialized using BPF_ST_MEM */ +__msg("8: (79) r2 = *(u64 *)(r10 -8) ; R2_w=1 R10=fp0 fp-8=1") +__msg("9: (0f) r1 += r2") +__msg("mark_precise: frame0: last_idx 9 first_idx 7 subseq_idx -1") +__msg("mark_precise: frame0: regs=r2 stack= before 8: (79) r2 = *(u64 *)(r10 -8)") +__msg ("mark_precise: frame0: regs= stack=-8 before 7: (bf) r1 = r6" ) +/* note, fp-8 is precise, fp-16 is not yet precise, we'll get there */ +__msg("mark_precise: frame0: parent state regs= stack=-8: R0_w=1 R1=ctx(off=0,imm=0) R6_r=map_value(off=0,ks=4,vs=2,imm=0) R10=fp0 fp-8_rw=P1 fp-16_w=1") +__msg("mark_precise: frame0: last_idx 6 first_idx 3 subseq_idx 7") +__msg("mark_precise: frame0: regs= stack=-8 before 6: (05) goto pc+0") +__msg("mark_precise: frame0: regs= stack=-8 before 5: (7b) *(u64 *)(r10 -16) = r0") +__msg("mark_precise: frame0: regs= stack=-8 before 4: (b7) r0 = 1") +__msg("mark_precise: frame0: regs= stack=-8 before 3: (7a) *(u64 *)(r10 -8) = 1") +__msg ("10: R1_w=map_value(off=1,ks=4,vs=2,imm=0) R2_w=1" ) +/* validate load from fp-16, which was initialized using BPF_STX_MEM */ +__msg("12: (79) r2 = *(u64 *)(r10 -16) ; R2_w=1 R10=fp0 fp-16=1") +__msg("13: (0f) r1 += r2") +__msg("mark_precise: frame0: last_idx 13 first_idx 7 subseq_idx -1") +__msg("mark_precise: frame0: regs=r2 stack= before 12: (79) r2 = *(u64 *)(r10 -16)") +__msg("mark_precise: frame0: regs= stack=-16 before 11: (bf) r1 = r6") +__msg("mark_precise: frame0: regs= stack=-16 before 10: (73) *(u8 *)(r1 +0) = r2") +__msg("mark_precise: frame0: regs= stack=-16 before 9: (0f) r1 += r2") +__msg("mark_precise: frame0: regs= stack=-16 before 8: (79) r2 = *(u64 *)(r10 -8)") +__msg ("mark_precise: frame0: regs= stack=-16 before 7: (bf) r1 = r6" ) +/* now both fp-8 and fp-16 are precise, very good */ +__msg("mark_precise: frame0: parent state regs= stack=-16: R0_w=1 R1=ctx(off=0,imm=0) R6_r=map_value(off=0,ks=4,vs=2,imm=0) R10=fp0 fp-8_rw=P1 fp-16_rw=P1") +__msg("mark_precise: frame0: last_idx 6 first_idx 3 subseq_idx 7") +__msg("mark_precise: frame0: regs= stack=-16 before 6: (05) goto pc+0") +__msg("mark_precise: frame0: regs= stack=-16 before 5: (7b) *(u64 *)(r10 -16) = r0") +__msg("mark_precise: frame0: regs=r0 stack= before 4: (b7) r0 = 1") +__msg("14: R1_w=map_value(off=1,ks=4,vs=2,imm=0) R2_w=1") +__naked void stack_load_preserves_const_precision (void ) +{ + asmvolatile ( +/* establish checkpoint with state that has no stack slots; +* if we bubble up to this state without finding desired stack +* slot, then it's a bug and should be caught +*/ +"goto +0;" + +/* fp-8 is const 1 *fake* register */ +".8byte %[fp8_st_one];" /* LLVM-18+: *(u64 *)(r10 -8) = 1; */ + +/* fp-16 is const 1 register */ +"r0 = 1;" +"*(u64 *)(r10 -16) = r0;" + +/* force checkpoint to check precision marks preserved in parent states */ +"goto +0;" + +/* load single U64 from aligned FAKE_REG=1 slot */ +"r1 = %[two_byte_buf];" +"r2 = *(u64 *)(r10 -8);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +/* load single U64 from aligned REG=1 slot */ +"r1 = %[two_byte_buf];" +"r2 = *(u64 *)(r10 -16);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +"r0 = 0;" +"exit;" + : + : __imm_ptr(two_byte_buf), +__imm_insn (fp8_st_one,BPF_ST_MEM (BPF_DW ,BPF_REG_FP ,-8 ,1 )) + : __clobber_common); +} + +SEC("raw_tp") +__log_level(2) __flag(BPF_F_TEST_STATE_FREQ) +__success +/* make sure fp-8 is 32-bit FAKE subregister spill */ +__msg ("3: (62) *(u32 *)(r10 -8) = 1 ; R10=fp0 fp-8=1" ) +/* but fp-16 is spilled IMPRECISE zero const reg */ +__msg ("5: (63) *(u32 *)(r10 -16) = r0 ; R0_w=1 R10=fp0 fp-16=1" ) +/* validate load from fp-8, which was initialized using BPF_ST_MEM */ +__msg("8: (61) r2 = *(u32 *)(r10 -8) ; R2_w=1 R10=fp0 fp-8=1") +__msg("9: (0f) r1 += r2") +__msg("mark_precise: frame0: last_idx 9 first_idx 7 subseq_idx -1") +__msg("mark_precise: frame0: regs=r2 stack= before 8: (61) r2 = *(u32 *)(r10 -8)") +__msg("mark_precise: frame0: regs= stack=-8 before 7: (bf) r1 = r6") +__msg("mark_precise: frame0: parent state regs= stack=-8: R0_w=1 R1=ctx(off=0,imm=0) R6_r=map_value(off=0,ks=4,vs=2,imm=0) R10=fp0 fp-8_r=P1 fp-16=1") +__msg("mark_precise: frame0: last_idx 6 first_idx 3 subseq_idx 7") +__msg("mark_precise: frame0: regs= stack=-8 before 6: (05) goto pc+0") +__msg("mark_precise: frame0: regs= stack=-8 before 5: (63) *(u32 *)(r10 -16) = r0") +__msg("mark_precise: frame0: regs= stack=-8 before 4: (b7) r0 = 1") +__msg("mark_precise: frame0: regs= stack=-8 before 3: (62) *(u32 *)(r10 -8) = 1") +__msg ("10: R1_w=map_value(off=1,ks=4,vs=2,imm=0) R2_w=1" ) +/* validate load from fp-16, which was initialized using BPF_STX_MEM */ +__msg("12: (61) r2 = *(u32 *)(r10 -16) ; R2_w=1 R10=fp0 fp-16=1") +__msg("13: (0f) r1 += r2") +__msg("mark_precise: frame0: last_idx 13 first_idx 7 subseq_idx -1") +__msg("mark_precise: frame0: regs=r2 stack= before 12: (61) r2 = *(u32 *)(r10 -16)") +__msg("mark_precise: frame0: regs= stack=-16 before 11: (bf) r1 = r6") +__msg("mark_precise: frame0: regs= stack=-16 before 10: (73) *(u8 *)(r1 +0) = r2") +__msg("mark_precise: frame0: regs= stack=-16 before 9: (0f) r1 += r2") +__msg("mark_precise: frame0: regs= stack=-16 before 8: (61) r2 = *(u32 *)(r10 -8)") +__msg("mark_precise: frame0: regs= stack=-16 before 7: (bf) r1 = r6") +__msg("mark_precise: frame0: parent state regs= stack=-16: R0_w=1 R1=ctx(off=0,imm=0) R6_r=map_value(off=0,ks=4,vs=2,imm=0) R10=fp0 fp-8_r=P1 fp-16_r=P1") +__msg("mark_precise: frame0: last_idx 6 first_idx 3 subseq_idx 7") +__msg("mark_precise: frame0: regs= stack=-16 before 6: (05) goto pc+0") +__msg("mark_precise: frame0: regs= stack=-16 before 5: (63) *(u32 *)(r10 -16) = r0") +__msg("mark_precise: frame0: regs=r0 stack= before 4: (b7) r0 = 1") +__msg("14: R1_w=map_value(off=1,ks=4,vs=2,imm=0) R2_w=1") +__naked void stack_load_preserves_const_precision_subreg (void ) +{ + asmvolatile ( +/* establish checkpoint with state that has no stack slots; +* if we bubble up to this state without finding desired stack +* slot, then it's a bug and should be caught +*/ +"goto +0;" + +/* fp-8 is const 1 *fake* SUB-register */ +".8byte %[fp8_st_one];" /* LLVM-18+: *(u32 *)(r10 -8) = 1; */ + +/* fp-16 is const 1 SUB-register */ +"r0 = 1;" +"*(u32 *)(r10 -16) = r0;" + +/* force checkpoint to check precision marks preserved in parent states */ +"goto +0;" + +/* load single U32 from aligned FAKE_REG=1 slot */ +"r1 = %[two_byte_buf];" +"r2 = *(u32 *)(r10 -8);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +/* load single U32 from aligned REG=1 slot */ +"r1 = %[two_byte_buf];" +"r2 = *(u32 *)(r10 -16);" +"r1 += r2;" +"*(u8 *)(r1 + 0) = r2;" /* this should be fine */ + +"r0 = 0;" +"exit;" + : + : __imm_ptr(two_byte_buf), +__imm_insn (fp8_st_one,BPF_ST_MEM (BPF_W ,BPF_REG_FP ,-8 ,1 ))/* 32-bit spill */ + : __clobber_common); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.0
Quoted 5 lines · Paul Chaignon
This patchset backports commit
41f6f64e6999("bpf: support non-r10 register spill/fill to/from stack in precision tracking") again, but this time with the subsequent commits that improved the efficiency of the verifier. In addition, the last two commits fix and test a regression that was later found in commit41f6f64e6999.
Queued for 6.6, thanks.
I also separately picked up 69772f509e08 ("bpf: Don't mark STACK_INVALID as STACK_MISC in mark_stack_slot_misc") as a follow-up to patch 3/10 (eaf18febd6eb).
Signature · 2 lines
Thanks, Sasha
Quoted 7 lines · Sasha Levin
Quoted 5 lines · Paul Chaignon
This patchset backports commit
41f6f64e6999("bpf: support non-r10 register spill/fill to/from stack in precision tracking") again, but this time with the subsequent commits that improved the efficiency of the verifier. In addition, the last two commits fix and test a regression that was later found in commit41f6f64e6999.
Quoted 5 lines
Queued for 6.6, thanks.
I also separately picked up
69772f509e08("bpf: Don't markSTACK_INVALIDasSTACK_MISCinmark_stack_slot_misc") as a follow-up to patch 3/10 (eaf18febd6eb).
Thanks! I had missed that one. I can confirm v6.6 BPF selftests are still green with that additional patch:
https://github.com/pchaigno/stable-bpf-ci/actions/runs/25726612531/job/75540955361.
Quoted 4 lines
Signature · 3 lines
-- Thanks, Sasha
Quoted 11 lines · Paul Chaignon
The first patch in this patchset was already backported before, as commit
ecc2aeeaa08a, to address CVE-2023-52920 [1]. That backport was however later reverted in commit199f04528737because it reduced the efficiency of the BPF verifier, to the point that it rejected some previously-accepted programs.This patchset backports commit
41f6f64e6999("bpf: support non-r10 register spill/fill to/from stack in precision tracking") again, but this time with the subsequent commits that improved the efficiency of the verifier. In addition, the last two commits fix and test a regression that was later found in commit41f6f64e6999.
Thanks a lot!
I can confirm that the reproducer that originally led to the revert could load successfully with this patchset.
Best regards,
Levi
Quoted 35 lines
It took us a while with Shung-Hsi to come back to this because we felt we didn't have enough test coverage to backport this. That changed with the stable BPF CI Shung-Hsi built for v6.6, which successfully validated this patchset [2]. In addition, I tested the impact of this patchset on the verifier's efficiency with Cilium's BPF programs [3]:
it significantly improves, reducing the number of instructions the verifier has to analyze by up to 87% in some cases!1: https://lore.kernel.org/linux-cve-announce/2024110518-CVE-2023-52920-17f6@gregkh/
2: https://github.com/pchaigno/stable-bpf-ci/actions/runs/25671397661/job/75357317078
3: https://pchaigno.github.io/test-verifier-complexity.htmlAndrii Nakryiko (10):
bpf: support non-r10 register spill/fill to/from stack in precision
tracking
selftests/bpf: add stack access precision test
bpf: preserveSTACK_ZEROslots on partial reg spills selftests/bpf: validateSTACK_ZEROis preserved on subreg spill
bpf: preserve constant zero when doing partial register restore selftests/bpf: validate zero preservation for sub-slot loads
bpf: track alignedSTACK_ZEROcases as imprecise spilled registers selftests/bpf: validate precision logic in
partial_stack_load_preserves_zeros
bpf: handle fake register spill to stack withBPF_ST_MEMinstruction selftests/bpf: validate fake register spill/fill precision
backtracking logicinclude/linux/bpf_verifier.h | 31 +- kernel/bpf/verifier.c | 233 +++++++++------ .../selftests/bpf/progs/verifier_spill_fill.c | 281 ++++++++++++++++++ .../bpf/progs/verifier_subprog_precision.c | 87 +++++- .../testing/selftests/bpf/verifier/precise.c | 38 ++- 5 files changed, 557 insertions(+), 113 deletions(-)