Re: bpf: incorrectly reject program with `back-edge insn from 7 to 8`
From: Andrii Nakryiko
Date: Thu Nov 02 2023 - 15:04:34 EST
On Thu, Nov 2, 2023 at 3:30 AM Hao Sun <sunhao.th@xxxxxxxxx> wrote:
>
> 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
Your instruction indices in your comments are wrong. Save yourself
time and confusion, use embedded assembly and llvm-objdump. You also
have a mismatch between 0x64 and actually specifying 0x68. Anyways, I
don't know how you got 7 to 8, but there does seem indeed to be a bug
in check_cfg() falsely detecting this as an infinite loop even in
privileged mode, which it should. I'll need to look deeper into how to
fix check_cfg(), it's not the easier to follow code, unfortunately.
But here's my log for your information.
$ git show
commit a343e644b8f3757a83f48b32b56ffc83943a62fa (HEAD -> temp-back-edge-test)
Author: Andrii Nakryiko <andrii@xxxxxxxxxx>
Date: Thu Nov 2 11:55:11 2023 -0700
selftests/bpf: trickier case of "bounded loop"
This should be accepted in privileged mode because r8 = 2 * r4 = 0x6a,
and so `if r8 < 0x64 goto -5;` is always false. Currently BPF verifier's
check_cfg() doesn't detect this properly.
Reported-by: Hao Sun <sunhao.th@xxxxxxxxx>
Signed-off-by: Andrii Nakryiko <andrii@xxxxxxxxxx>
diff --git a/tools/testing/selftests/bpf/progs/verifier_cfg.c
b/tools/testing/selftests/bpf/progs/verifier_cfg.c
index df7697b94007..f89dce7850f6 100644
--- a/tools/testing/selftests/bpf/progs/verifier_cfg.c
+++ b/tools/testing/selftests/bpf/progs/verifier_cfg.c
@@ -97,4 +97,26 @@ l0_%=: r2 = r0;
\
" ::: __clobber_all);
}
+SEC("socket")
+__description("conditional loop (2)")
+__success
+__failure_unpriv __msg_unpriv("back-edge from insn 10 to 11")
+__naked void conditional_loop2(void)
+{
+ asm volatile (" \
+ r9 = 2 ll; \
+ r3 = 0x20 ll; \
+ r4 = 0x35 ll; \
+ r8 = r4; \
+ goto l1_%=; \
+l0_%=: r9 -= r3; \
+ r9 -= r4; \
+ r9 -= r8; \
+l1_%=: r8 += r4; \
+ if r8 < 0x64 goto l0_%=; \
+ r0 = r9; \
+ exit; \
+" ::: __clobber_all);
+}
+
char _license[] SEC("license") = "GPL";
Here's disassembly (though I moved it to separate .bpf.c file to have
0-based instruction indices, my patch above adds test to other
existing tests):
$ llvm-objdump -d verifier_cfg1.bpf.o
verifier_cfg1.bpf.o: file format elf64-bpf
Disassembly of section socket:
0000000000000000 <conditional_loop2>:
0: 18 09 00 00 02 00 00 00 00 00 00 00 00 00 00 00 r9 = 0x2 ll
2: 18 03 00 00 20 00 00 00 00 00 00 00 00 00 00 00 r3 = 0x20 ll
4: 18 04 00 00 35 00 00 00 00 00 00 00 00 00 00 00 r4 = 0x35 ll
6: bf 48 00 00 00 00 00 00 r8 = r4
7: 05 00 03 00 00 00 00 00 goto +0x3 <l1_0>
0000000000000040 <l0_0>:
8: 1f 39 00 00 00 00 00 00 r9 -= r3
9: 1f 49 00 00 00 00 00 00 r9 -= r4
10: 1f 89 00 00 00 00 00 00 r9 -= r8
0000000000000058 <l1_0>:
11: 0f 48 00 00 00 00 00 00 r8 += r4
12: a5 08 fb ff 64 00 00 00 if r8 < 0x64 goto -0x5 <l0_0>
13: bf 90 00 00 00 00 00 00 r0 = r9
14: 95 00 00 00 00 00 00 00 exit
Then running test on latest bpf-next:
$ sudo ./test_progs -t verifier_cfg
...
run_subtest:PASS:obj_open_mem 0 nsec
libbpf: prog 'conditional_loop2': BPF program load failed: Invalid argument
libbpf: prog 'conditional_loop2': failed to load: -22
libbpf: failed to load object 'verifier_cfg'
run_subtest:FAIL:unexpected_load_failure unexpected error: -22 (errno 22)
VERIFIER LOG:
=============
10: asm volatile (" \
back-edge from insn 10 to 11
processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0
peak_states 0 mark_read 0
=============
#329/15 verifier_cfg/conditional loop (2):FAIL
#329/16 verifier_cfg/conditional loop (2) @unpriv:OK
#329 verifier_cfg:FAIL
I'll keep looking into this after taking care of other stuff I have on
TODO list, thanks.
>
> > 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