bpf: Keep the valid bytes of a packet pointer in scalar evolution

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 the largest offset.

The largest offset is smax, not umax. With 'r6 += -8' in the loop the
offset can be negative. Then umax is U64_MAX before and after
reg_bounds_sync(). The verifier rejects an access through such r6. It
accepts an access through 'r5 = r6; r5 += 8', and r5 has the range of r6.

All registers of a union have the same range, and bpf_reg_union() makes
sure of that for each register. Thus change the range one time, after the
last register. The range goes with the largest offset of all registers.

The range can also be a mark: the pointer is at pkt_end or beyond pkt_end.
The mark is for the pointer at the entry of the loop, not for all
iterations. Remove it when the pointer is widened. The arithmetic in the
loop removes the mark too. Thus the state that returns to the head was not
pruned, and the verifier made one more pass with the two branches of each
compare. Now the first pass examines the two branches. The verdict can
change only when no state returned to the head: the mark sent each path out
of the loop, and the other insns of the loop were dead code.

Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20261030210950.1904640-2-alexei.starovoitov@gmail.com
Closes: https://lore.kernel.org/bpf/sashiko-outbox-187068@kernel.org/

0 files changed, 0 insertions, 0 deletions