linux-kernel - Re: bpf: incorrectly reject program with `back-edge insn from 7 to 8`

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Thu, 2 Nov 2023 11:30:07 +0100
From:   Hao Sun <sunhao.th@...il.com>
To:     Andrii Nakryiko <andrii.nakryiko@...il.com>
Cc:     Alexei Starovoitov <ast@...nel.org>,
        Daniel Borkmann <daniel@...earbox.net>,
        John Fastabend <john.fastabend@...il.com>,
        Andrii Nakryiko <andrii@...nel.org>,
        Martin KaFai Lau <martin.lau@...ux.dev>,
        Song Liu <song@...nel.org>,
        Yonghong Song <yonghong.song@...ux.dev>,
        KP Singh <kpsingh@...nel.org>,
        Stanislav Fomichev <sdf@...gle.com>,
        Hao Luo <haoluo@...gle.com>, Jiri Olsa <jolsa@...nel.org>,
        Mykola Lysenko <mykolal@...com>, Shuah Khan <shuah@...nel.org>,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        bpf <bpf@...r.kernel.org>
Subject: Re: bpf: incorrectly reject program with `back-edge insn from 7 to 8`

On Wed, Nov 1, 2023 at 9:57 PM Andrii Nakryiko
<andrii.nakryiko@...il.com> wrote:
>
> On Wed, Nov 1, 2023 at 6:56 AM Hao Sun <sunhao.th@...il.com> wrote:
> >
> > 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 = 2
> >    * 1: r3 = 0x20
> >    * 2: r4 = 0x35
> >    * 3: r8 = r4
> >    * 4: goto+3
> >    * 5: r9 -= r3
> >    * 6: r9 -= r4
> >    * 7: r9 -= r8
> >    * 8: r8 += r4
> >    * 9: if r8 < 0x64 goto-5
> >    * 10: r0 = 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