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 for Android: free password hash cracker in your pocket

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

Message-ID: <CAEf4BzbDK15myKbN4sM+cxFvfWCNjthJuFZf81k6OEBpaC124g@mail.gmail.com>
Date:   Wed, 1 Nov 2023 13:57:33 -0700
From:   Andrii Nakryiko <andrii.nakryiko@...il.com>
To:     Hao Sun <sunhao.th@...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 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.

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.

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