Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:5 as permitted sender) client-ip=2620:137:e000::3:5;
MIME-Version: 1.0
References: <CACkBjsY3vMLVVO0zHd+CRcQPdykDhXv8-f2oD82+Jk5KJpq_8w@mail.gmail.com>
 <CAEf4BzbDK15myKbN4sM+cxFvfWCNjthJuFZf81k6OEBpaC124g@mail.gmail.com>
In-Reply-To: <CAEf4BzbDK15myKbN4sM+cxFvfWCNjthJuFZf81k6OEBpaC124g@mail.gmail.com>
From:   Hao Sun <sunhao.th@gmail.com>
Date:   Thu, 2 Nov 2023 11:30:07 +0100
Message-ID: <CACkBjsbpttp2L0=oi7-0+SLNC8wSxkPbG7ZYZuWOmurNxELT-Q@mail.gmail.com>
Subject: Re: bpf: incorrectly reject program with `back-edge insn from 7 to 8`
To:     Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc:     Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        John Fastabend <john.fastabend@gmail.com>,
        Andrii Nakryiko <andrii@kernel.org>,
        Martin KaFai Lau <martin.lau@linux.dev>,
        Song Liu <song@kernel.org>,
        Yonghong Song <yonghong.song@linux.dev>,
        KP Singh <kpsingh@kernel.org>,
        Stanislav Fomichev <sdf@google.com>,
        Hao Luo <haoluo@google.com>, Jiri Olsa <jolsa@kernel.org>,
        Mykola Lysenko <mykolal@fb.com>, Shuah Khan <shuah@kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        bpf <bpf@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Wed, Nov 1, 2023 at 9:57=E2=80=AFPM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Wed, Nov 1, 2023 at 6:56=E2=80=AFAM Hao Sun <sunhao.th@gmail.com> wrot=
e:
> >
> > Hi,
> >
> > The verifier incorrectly rejects the following prog in check_cfg() when
> > loading with root with confusing log `back-edge insn from 7 to 8`:
> >   /* 0: r9 =3D 2
> >    * 1: r3 =3D 0x20
> >    * 2: r4 =3D 0x35
> >    * 3: r8 =3D r4
> >    * 4: goto+3
> >    * 5: r9 -=3D r3
> >    * 6: r9 -=3D r4
> >    * 7: r9 -=3D r8
> >    * 8: r8 +=3D r4
> >    * 9: if r8 < 0x64 goto-5
> >    * 10: r0 =3D r9
> >    * 11: exit
> >    * */
> >   BPF_MOV64_IMM(BPF_REG_9, 2),
> >   BPF_MOV64_IMM(BPF_REG_3, 0x20),
> >   BPF_MOV64_IMM(BPF_REG_4, 0x35),
> >   BPF_MOV64_REG(BPF_REG_8, BPF_REG_4),
> >   BPF_JMP_IMM(BPF_JA, 0, 0, 3),
> >   BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_3),
> >   BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_4),
> >   BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_8),
> >   BPF_ALU64_REG(BPF_ADD, BPF_REG_8, BPF_REG_4),
> >   BPF_JMP32_IMM(BPF_JLT, BPF_REG_8, 0x68, -5),
> >   BPF_MOV64_REG(BPF_REG_0, BPF_REG_9),
> >   BPF_EXIT_INSN()
> >
> > -------- Verifier Log --------
> > func#0 @0
> > back-edge from insn 7 to 8
> > processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0
> > peak_states 0 mark_read 0
> >
> > This is not intentionally rejected, right?
>
> The way you wrote it, with goto +3, yes, it's intentional. Note that
> you'll get different results in privileged and unprivileged modes.
> Privileged mode allows "bounded loops" logic, so it doesn't
> immediately reject this program, and then later sees that r8 is always
> < 0x64, so program is correct.
>

I load the program with privileged mode, and goto-5 makes the program
run from #9 to #5, so r8 is updated and the program is not infinite loop.

> But in unprivileged mode the rules are different, and this conditional
> back edge is not allowed, which is probably what you are getting.
>
> It's actually confusing and your "back-edge from insn 7 to 8" is out
> of date and doesn't correspond to your program, you should see
> "back-edge from insn 11 to 7", please double check.
>

Yes it's also confusing to me, but "back-edge from insn 7 to 8" is what
I got. The execution path of the program is #4 to #8 (goto+3), so the
verifier see the #8 first. Then, the program then goes #9 to #5 (goto-5),
the verifier thus sees #7 to #8 and incorrectly concludes back-edge here.

This can is the verifier log I got from latest bpf-next, this C program can
reproduce this: https://pastebin.com/raw/Yug0NVwx

> Anyways, while I was looking into this, I realized that ldimm64 isn't
> handled exactly correctly in check_cfg(), so I just sent a fix. It
> also adds a nicer detection of jumping into the middle of the ldimm64
> instruction, which I believe is something you were advocating for.
>
> >
> > Best
> > Hao