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

[Andrii Nakryiko]

On Wed, Nov 1, 2023 at 6:56 AM Hao Sun <sunhao.th@xxxxxxxxx> 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