From: Alexei Starovoitov check_packet_access() accepts an access when umax + off + size <= range. Thus 'range - umax' bytes from a packet pointer are in the packet, and nothing can make umax smaller without a change of the range. For this reason commit b88822d2584f ("bpf: Fix packet range of pointers sharing an id") removed reg_bounds_sync() from the arithmetic on packet pointers. At the head of a counted loop scalar evolution gives new bounds to a packet pointer, in bpf_set_reg_range() and in bpf_reg_union(). The two functions call reg_bounds_sync(). Then the step or var_off makes umax smaller. r4 &= 0x38 if r4 > 50 goto 2f ; r4 is 0, 8 .. 48, but umax is 50 r6 = pkt r6 += r4 r5 = r6 r5 += 8 if r5 > pkt_end goto 2f ; 8 bytes from r6 are in the packet 1: r0 = *(u16 *)(r6 + 0) r6 += 8 r9 += 1 if r9 < 2 goto 1b r6 umax range valid bytes ----------------------- ---- ----- ------------ in front of the loop 50 58 8 in all iterations 58 58 0 after the step of 8 56 58 2, incorrect In the second iteration r6 can be pkt_end. The verifier accepts the prog, and the prog reads 2 bytes after the packet. A kernel without scalar evolution rejects it. Make the range smaller by the same number as umax. The range can also be a mark: the pointer is at pkt_end or beyond pkt_end. The mark is valid in the first iteration only. Remove it when the pointer is widened. This does not change a verdict. The arithmetic in the loop removes the mark too, so the state that returns to the head was not pruned, and the verifier made one more pass with the two branches of each compare. Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops") Closes: https://lore.kernel.org/bpf/sashiko-outbox-187068@kernel.org/ Signed-off-by: Alexei Starovoitov --- kernel/bpf/scev.c | 3 +++ kernel/bpf/verifier.c | 18 ++++++++++++++++-- 2 files changed, 19 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c index 7b82fd79f9cc..abc4ba5ec1a9 100644 --- a/kernel/bpf/scev.c +++ b/kernel/bpf/scev.c @@ -2837,6 +2837,9 @@ int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state bpf_log(log, "\n"); } scratch_widened_reg_id(env, reg); + /* "at pkt_end" and "beyond pkt_end" are not valid in all iterations */ + if (type_is_pkt_pointer(reg->type)) + reg->range = max(reg->range, 0); err = bpf_set_reg_range(env, reg, bounds.r64, bounds.r32, bounds.base, bounds.step); if (err) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 02b2915f0014..cf7b64de1a4d 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17739,6 +17739,20 @@ bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a, } } +/* + * 'range - umax' bytes from a packet pointer are in the packet. reg_bounds_sync() can make umax + * smaller: with a step of 8, or with 3 zero bits in var_off, 58 becomes 56. Make the range + * smaller by the same number, so that the number of bytes does not grow. + */ +static void sync_widened_reg(struct bpf_reg_state *reg) +{ + u64 umax = reg_umax(reg); + + reg_bounds_sync(reg); + if (type_is_pkt_pointer(reg->type) && reg->range > 0) + reg->range = max_t(s64, reg->range - (s64)(umax - reg_umax(reg)), 0); +} + int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg, struct cnum64 r64, struct cnum32 r32, u16 base, u16 step) { @@ -17747,7 +17761,7 @@ int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg, reg->step = step; reg->base = base; reg->var_off = tnum_unknown; - reg_bounds_sync(reg); /* this should infer the tnum alignment */ + sync_widened_reg(reg); /* this should infer the tnum alignment */ return reg_bounds_sanity_check(env, reg, "bpf_set_reg_range"); } @@ -17792,7 +17806,7 @@ int bpf_reg_union(struct bpf_verifier_env *env, struct bpf_reg_state *acc, acc->base = base; acc->step = step; } - reg_bounds_sync(acc); + sync_widened_reg(acc); return reg_bounds_sanity_check(env, acc, "bpf_reg_union"); } -- 2.55.0