Re: [syzbot ci] Re: bpf: replace path-sensitive with path-insensitive live stack analysis

[Eduard Zingerman <eddyz87@gmail.com>]

On Thu, 2025-09-11 at 14:58 -0700, Alexei Starovoitov wrote:
> On Thu, Sep 11, 2025 at 2:09 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > On Wed, 2025-09-10 at 23:57 -0700, syzbot ci wrote:
> > > syzbot ci has tested the following series
> > > 
> > > [v1] bpf: replace path-sensitive with path-insensitive live stack analysis
> > > https://lore.kernel.org/all/20250911010437.2779173-1-eddyz87@gmail.com
> > > * [PATCH bpf-next v1 01/10] bpf: bpf_verifier_state->cleaned flag instead of REG_LIVE_DONE
> > > * [PATCH bpf-next v1 02/10] bpf: use compute_live_registers() info in clean_func_state
> > > * [PATCH bpf-next v1 03/10] bpf: remove redundant REG_LIVE_READ check in stacksafe()
> > > * [PATCH bpf-next v1 04/10] bpf: declare a few utility functions as internal api
> > > * [PATCH bpf-next v1 05/10] bpf: compute instructions postorder per subprogram
> > > * [PATCH bpf-next v1 06/10] bpf: callchain sensitive stack liveness tracking using CFG
> > > * [PATCH bpf-next v1 07/10] bpf: enable callchain sensitive stack liveness tracking
> > > * [PATCH bpf-next v1 08/10] bpf: signal error if old liveness is more conservative than new
> > > * [PATCH bpf-next v1 09/10] bpf: disable and remove registers chain based liveness
> > > * [PATCH bpf-next v1 10/10] bpf: table based bpf_insn_successors()
> > > 
> > > and found the following issue:
> > > KASAN: slab-out-of-bounds Write in compute_postorder
> > > 
> > > Full report is available here:
> > > https://ci.syzbot.org/series/c42e236b-f40c-4d72-8ae7-da4e21c37e17
> > > 
> > > ***
> > > 
> > > KASAN: slab-out-of-bounds Write in compute_postorder
> > > 
> > > tree:      bpf-next
> > > URL:       https://kernel.googlesource.com/pub/scm/linux/kernel/git/bpf/bpf-next.git
> > > base:      e12873ee856ffa6f104869b8ea10c0f741606f13
> > > arch:      amd64
> > > compiler:  Debian clang version 20.1.8 (++20250708063551+0c9f909b7976-1~exp1~20250708183702.136), Debian LLD 20.1.8
> > > config:    https://ci.syzbot.org/builds/6d2bc952-3d65-4bcd-9a84-1207b810a1b5/config
> > > C repro:   https://ci.syzbot.org/findings/338e6ce4-7207-484f-a508-9b00b3121701/c_repro
> > > syz repro: https://ci.syzbot.org/findings/338e6ce4-7207-484f-a508-9b00b3121701/syz_repro
> > > 
> > > ==================================================================
> > > BUG: KASAN: slab-out-of-bounds in compute_postorder+0x802/0xcb0 kernel/bpf/verifier.c:17840
> > > Write of size 4 at addr ffff88801f1d4b98 by task syz.0.17/5991
> > 
> > The error is caused by the following program:
> > 
> >   (e5) if r15 (null) 0xffffffff goto pc-1 <---- absence of DISCOVERED/EXPLORED mark here
> 
> (null) ?

The `code` byte is 0xe5, BPF_OP(0xe5) == 0xe0, which is an invalid
opcode.  But opcodes are verified after check_cfg()/compute_postorder().

> Is it jset again? but insn_successors() handles it already.
> Or pc-1 infinite loop caused it?
> but we have pc-1 selftest...

It's not infinite, but it causes instruction to be put twice on the
stack array, and this array is allocated expecting max prog->len
instructions. KASAN would only catch this error if program really
needs to consume full stack depth during postorder construction,
as far as I understand.

[...]