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

[Hao Sun]

On Wed, Nov 1, 2023 at 9:57 PM Andrii Nakryiko
<andrii.nakryiko@xxxxxxxxx> wrote:
>
> 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.
>

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