Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:3 as permitted sender) client-ip=2620:137:e000::3:3;
MIME-Version: 1.0
References: <CACkBjsbj4y4EhqpV-ZVt645UtERJRTxfEab21jXD1ahPyzH4_g@mail.gmail.com>
 <CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com> <CACkBjsaEQxCaZ0ERRnBXduBqdw3MXB5r7naJx_anqxi0Wa-M_Q@mail.gmail.com>
In-Reply-To: <CACkBjsaEQxCaZ0ERRnBXduBqdw3MXB5r7naJx_anqxi0Wa-M_Q@mail.gmail.com>
From:   Andrii Nakryiko <andrii.nakryiko@gmail.com>
Date:   Wed, 13 Dec 2023 15:30:10 -0800
Message-ID: <CAEf4BzbGSrU4NgM1Ps0g_ch8G68CWEsP50Y+Wy8-SfYnpHwVGA@mail.gmail.com>
Subject: Re: [Bug Report] bpf: incorrectly pruning runtime execution path
To:     Hao Sun <sunhao.th@gmail.com>
Cc:     Alexei Starovoitov <ast@kernel.org>,
        Andrii Nakryiko <andrii@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        bpf <bpf@vger.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        Eduard Zingerman <eddyz87@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Wed, Dec 13, 2023 at 2:25=E2=80=AFAM Hao Sun <sunhao.th@gmail.com> wrote=
:
>
> On Wed, Dec 13, 2023 at 1:51=E2=80=AFAM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Dec 11, 2023 at 7:31=E2=80=AFAM Hao Sun <sunhao.th@gmail.com> w=
rote:
> > >
> > > Hi,
> > >
> > > The verifier incorrectly prunes a path expected to be executed at
> > > runtime. In the following program, the execution path is:
> > >     from 6 to 8 (taken) -> from 11 to 15 (taken) -> from 18 to 22
> > > (taken) -> from 26 to 27 (fall-through) -> from 29 to 30
> > > (fall-through)
> > > The verifier prunes the checking path at #26, skipping the actual
> > > execution path.
> > >
> > >    0: (18) r2 =3D 0x1a000000be
> > >    2: (bf) r5 =3D r1
> > >    3: (bf) r8 =3D r2
> > >    4: (bc) w4 =3D w5
> > >    5: (85) call bpf_get_current_cgroup_id#680112
> > >    6: (36) if w8 >=3D 0x69 goto pc+1
> > >    7: (95) exit
> > >    8: (18) r4 =3D 0x52
> > >   10: (84) w4 =3D -w4
> > >   11: (45) if r0 & 0xfffffffe goto pc+3
> > >   12: (1f) r8 -=3D r4
> > >   13: (0f) r0 +=3D r0
> > >   14: (2f) r4 *=3D r4
> > >   15: (18) r3 =3D 0x1f00000034
> > >   17: (c4) w4 s>>=3D 29
> > >   18: (56) if w8 !=3D 0xf goto pc+3
> > >   19: r3 =3D bswap32 r3
> > >   20: (18) r2 =3D 0x1c
> > >   22: (67) r4 <<=3D 2
> > >   23: (bf) r5 =3D r8
> > >   24: (18) r2 =3D 0x4
> > >   26: (7e) if w8 s>=3D w0 goto pc+5
> > >   27: (4f) r8 |=3D r8
> > >   28: (0f) r8 +=3D r8
> > >   29: (d6) if w5 s<=3D 0x1d goto pc+2
> > >   30: (18) r0 =3D 0x4 ; incorrectly pruned here
> >
> >
> >
> > >   32: (95) exit
> > >

[...]

> > >
> > > Here is a reduced C repro, maybe someone else can shed some light on =
this.
> > > C repro: https://pastebin.com/raw/chrshhGQ
> >
> > So you claim is that
> >
> > 30: (18) r0 =3D 0x4 ; incorrectly pruned here
> >
> >
> > Can you please show a detailed code patch in which we do reach 30
> > actually? I might have missed it, but so far it look like verifier is
> > doing everything right.
> >
>
> I tried to convert the repro to a valid test case in inline asm, but seem=
s
> JSET (if r0 & 0xfffffffe goto pc+3) is currently not supported in clang-1=
7.
> Will try after clang-18 is released.

JSET has nothing to do with the issue, it's just a distraction, I'm
not sure why you bring JSET into the discussion at all.

Your repro can be actually much smaller, as it was really hard to
follow which parts are important and which weren't. If you can try to
minimize repros, it will definitely help with analysis for future
issues.

>
> #30 is expected to be executed, see below where everything after ";" is
> the runtime value:
>    ...
>    6: (36) if w8 >=3D 0x69 goto pc+1    ; w8 =3D 0xbe, always taken
>    ...
>   11: (45) if r0 & 0xfffffffe goto pc+3  ; r0 =3D 0x616, taken
>   ...
>   18: (56) if w8 !=3D 0xf goto pc+3     ; w8 not touched, taken
>   ...
>   23: (bf) r5 =3D r8     ; w5 =3D 0xbe
>   24: (18) r2 =3D 0x4
>   26: (7e) if w8 s>=3D w0 goto pc+5    ; non-taken
>   27: (4f) r8 |=3D r8
>   28: (0f) r8 +=3D r8
>   29: (d6) if w5 s<=3D 0x1d goto pc+2  ; non-taken
>   30: (18) r0 =3D 0x4      ; executed
>
> Since the verifier prunes at #26, #30 is dead and eliminated. So, #30
> is executed after manually commenting out the dead code rewrite pass.
>
> From my understanding, I think r0 should be marked as precise when
> first backtrack from #29, because r5 range at this point depends on w0
> as r8 and r5 share the same id at #26.

Yes, thanks, the execution trace above was helpful. Let's try to
minimize the example here, I'll keep original instruction indices,
though:

   23: (bf) r5 =3D r8                   ; here we link r5 and r8 together
   26: (7e) if w8 s>=3D w0 goto pc+5    ; here it's not always/never
taken, so w8 and w0 remain imprecise
   28: (0f) r8 +=3D r8                  ; here link between r8 and r5 is br=
oken
   29: (d6) if w5 s<=3D 0x1d goto pc+2  ; here we know value of w5 and
so it's always/never taken, r5 is marked precise

Now, if we look at r5's precision log at this instruction:

29: (d6) if w5 s<=3D 0x1d goto pc+2
mark_precise: frame0: last_idx 29 first_idx 26 subseq_idx -1
mark_precise: frame0: regs=3Dr5 stack=3D before 28: (0f) r8 +=3D r8
mark_precise: frame0: regs=3Dr5 stack=3D before 27: (4f) r8 |=3D r8
mark_precise: frame0: regs=3Dr5 stack=3D before 26: (7e) if w8 s>=3D w0 got=
o pc+5

Note how at this instruction r5 and r8 *WERE* linked together, but we
already lost this information for backtracking. So we don't mark w8 as
precise. That's one part of the problem.

The second part is that even if we knew that w8/r8 is precise, should
we mark w0/r0 as precise? I actually need to think about this some
more. Right now for conditional jumps we eagerly mark precision for
both registers only in always/never taken scenarios.

For now just narrowing down the issue, as I'm sure not many people
followed all the above stuff carefully.


P.S. For solving tracking of linked registers we can probably utilize
instruction history, though technically they can be spread across
multiple frames, between registers and stack slots, so that's a bit
tricky.