Received-SPF: pass (google.com: domain of linux-kernel+bounces-118314-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249;
Precedence: bulk
MIME-Version: 1.0
References: <0000000000003dc8e00614076ab6@google.com> <CAADnVQLORV5PT0iTAhRER+iLBTkByCYNBYyvBSgjN1T31K+gOw@mail.gmail.com>
 <CABWLsetXQ8Xj-RECoyC7mp4YrdSsPwmSvkS36Eq2JKLfAYULuw@mail.gmail.com>
 <CAADnVQJAa1SREsqz9LY+-1OnbazWC-=O=TPuq-VEWkzp1ckH1Q@mail.gmail.com>
 <CABWLseuLmAys-YuyFVeug+XR0_xjZROvgRTXz3U6cNiT+pBX0g@mail.gmail.com> <CAADnVQ+oqe6EtC8rc9TSFeUPE1Rbf11Oi-CfTyDxfXT9qM0Vpg@mail.gmail.com>
In-Reply-To: <CAADnVQ+oqe6EtC8rc9TSFeUPE1Rbf11Oi-CfTyDxfXT9qM0Vpg@mail.gmail.com>
From: Andrei Matei <andreimatei1@gmail.com>
Date: Mon, 25 Mar 2024 22:48:05 -0400
Message-ID: <CABWLses5ZpokYC==6cVKkAz25rYtgtMYn+GpxOd4TuJ7jwcNBw@mail.gmail.com>
Subject: Re: stack access issue. Re: [syzbot] [bpf?] UBSAN:
 array-index-out-of-bounds in check_stack_range_initialized
To: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: Edward Adam Davis <eadavis@qq.com>, Andrii Nakryiko <andrii@kernel.org>, 
	Alexei Starovoitov <ast@kernel.org>, bpf <bpf@vger.kernel.org>, 
	Daniel Borkmann <daniel@iogearbox.net>, Eddy Z <eddyz87@gmail.com>, Hao Luo <haoluo@google.com>, 
	John Fastabend <john.fastabend@gmail.com>, Jiri Olsa <jolsa@kernel.org>, 
	KP Singh <kpsingh@kernel.org>, LKML <linux-kernel@vger.kernel.org>, 
	Martin KaFai Lau <martin.lau@linux.dev>, Network Development <netdev@vger.kernel.org>, 
	Stanislav Fomichev <sdf@google.com>, Song Liu <song@kernel.org>, 
	syzkaller-bugs <syzkaller-bugs@googlegroups.com>, Yonghong Song <yonghong.song@linux.dev>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Fixing in https://lore.kernel.org/bpf/20240324230323.1097685-1-andreimatei1=
@gmail.com/

FWIW, I managed to decode the BPF program that syzkaller used:

0: (18) r0 =3D 0x0
2: (18) r1 =3D map[id:4]
4: (b7) r8 =3D 0
5: (7b) *(u64 *)(r10 -8) =3D r8
6: (bf) r2 =3D r10
7: (07) r2 +=3D -8
8: (b7) r3 =3D 8
9: (b7) r4 =3D 0
10: (85) call bloom_map_peek_elem#322320
11: (95) exit

Where the map is a bloom filter (as Alexei somehow already knew on the patc=
h
thread) with a humongous value size.

4: type 30  flags 0x0
        key 0B  value 2147483649B  max_entries 255  memlock 720B

On Sat, Mar 23, 2024 at 10:55=E2=80=AFPM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Sat, Mar 23, 2024 at 7:12=E2=80=AFPM Andrei Matei <andreimatei1@gmail.=
com> wrote:
> >
> > On Sat, Mar 23, 2024 at 8:52=E2=80=AFPM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Sat, Mar 23, 2024 at 5:50=E2=80=AFPM Andrei Matei <andreimatei1@gm=
ail.com> wrote:
> > > >
> > > > + Edward
> > > >
> > > > On Thu, Mar 21, 2024 at 3:33=E2=80=AFAM Alexei Starovoitov
> > > > <alexei.starovoitov@gmail.com> wrote:
> > > > >
> > > > > Hi Andrei,
> > > > >
> > > > > looks like the refactoring of stack access introduced a bug.
> > > > > See the reproducer below.
> > > > > positive offsets are not caught by check_stack_access_within_boun=
ds().
> > > >
> > > > check_stack_access_within_bounds() tries to catch positive offsets;
> > > > It does: [1]
> > > >
> > > > err =3D check_stack_slot_within_bounds(env, min_off, state, type);
> > > > if (!err && max_off > 0)
> > > >   err =3D -EINVAL; /* out of stack access into non-negative offsets=
 */
> > > >
> > > > Notice the max_off > 0 in there.
> > > > And we have various tests that seem to check that positive offsets =
are
> > > > rejected. Do you know what the bug is?
> > > > I'm thinking maybe there's some overflow going on, except that UBSA=
N
> > > > reported an index of -1 as being the problem.
> > > >
> > > > Edward, I see that you've been tickling the robot trying to narrow =
the issue;
> > > > perhaps you've figured it out?
> > > >
> > > > If the bug is not immediately apparent to anyone, I would really ap=
preciate a
> > > > bit of tutoring around how to reproduce and get verifier logs.
> > >
> > > The repro is right there in the email I forwarded:
> > >
> > > > C reproducer:   https://syzkaller.appspot.com/x/repro.c?x=3D15c3871=
1180000
> >
> > I understand, but how does one go from this to either BPF assembly,
> > or to running it in such a way that you also get verifier logs?
>
> Adding logs to repro.c is too hard, but you can
> hack the kernel with printk-s.
>
> Like the following:
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index de7813947981..d158b83ed16c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -7179,6 +7179,7 @@ static int check_stack_range_initialized(
>                         return -EFAULT;
>                 }
>
> +               printk("slot %d %d spi %d\n", slot, slot % BPF_REG_SIZE, =
spi);
>                 stype =3D &state->stack[spi].slot_type[slot % BPF_REG_SIZ=
E];
>
>
> shows that spi and slot get negative: -1, -2, ...