On Fri, Oct 27, 2023 at 2:06 AM Tao Lyu <tao.lyu@xxxxxxx> wrote:
>
> >>
> >> There is another issue about the backtracking.
> >> When uploading the following program under privilege mode,
> >> the verifier reports a "verifier backtracking bug".
> >>
> >> 0: R1=ctx(off=0,imm=0) R10=fp0
> >> 0: (85) call pc+2
> >> caller:
> >> R10=fp0
> >> callee:
> >> frame1: R1=ctx(off=0,imm=0) R10=fp0
> >> 3: frame1:
> >> 3: (bf) r3 = r10 ; frame1: R3_w=fp0 R10=fp0
> >> 4: (bc) w0 = w10 ; frame1: R0_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0
> >> 5: (0f) r3 += r0
> >> mark_precise: frame1: last_idx 5 first_idx 0 subseq_idx -1
> >> mark_precise: frame1: regs=r0 stack= before 4: (bc) w0 = w10
> >> mark_precise: frame1: regs=r10 stack= before 3: (bf) r3 = r10
> >> mark_precise: frame1: regs=r10 stack= before 0: (85) call pc+2
> >> BUG regs 400
> >>
> >> This bug is manifested by the following check:
> >>
> >> if (bt_reg_mask(bt) & ~BPF_REGMASK_ARGS) {
> >> verbose(env, "BUG regs %x\n", bt_reg_mask(bt));
> >> WARN_ONCE(1, "verifier backtracking bug");
> >> return -EFAULT;
> >> }
> >>
> >> Since the verifier allows add operation on stack pointers,
> >> it shouldn't show this WARNING and reject the program.
> >>
> >> I fixed it by skipping the warning if it's privilege mode and only r10 is marked as precise.
> >>
> >
> >See my reply to your other email. It would be nice if you can rewrite
> >your tests in inline assembly, it would be easier to follow and debug.
> >
>
> Sorry, I'm new to this community.
> Could you explain a little bit more about what the inline assembly is?
> I wrote the test confirming to the test cases under "tools/testing/selftests/bpf".
see progs/verifier_subprog_precision.c under
tools/testing/selftests/bpf, those examples show how we write verifier
tests using BPF assembly, instead of constructing BPF programs out of
BPF_XXX() macros (which are much harder to write and read)
>
> >I think your fix is papering over the fact that we don't recognize
> >non-r10 stack access. Once we fix that, we shouldn't need extra hacks.
> >So let's solve the underlying problem first.
>
> Sure, we can fix the non-r10 stack access first.
>
> However, the bug here is not related to the r10 stack access tracking, as there is no stack access in the test case.
> The root cause is that when meeting subprog calling instruction, the verifier asserts that r10 can't be marked as precise.
> However, under privileged mode, the verifier allows arithmetic operations (e.g., sub and add) on stack pointers, and thus, it's legal that r10 can be marked as precise.
> In this situation, the verifier might incorrectly reject programs.
>
> Solutions for this issue:
> 1) Never mark r10 as precise during backtracking
> 2) Modify this assertion so that under privileged mode, even if the verifier sees r10 is marked as precise, it does throw the WARNING.
>
I'm not entirely sure, but I think the right solution is to prevent
r10 and generally PTR_TO_STACK from being marked as precise. It should
be precise implicitly, just like any other non-SCALAR_VALUE register.
> The patch I provided is the second solution.
>
> >> Signed-off-by: Tao Lyu <tao.lyu@xxxxxxx>
> >> ---
> >> kernel/bpf/verifier.c | 4 +++-
> >> .../bpf/verifier/ret-without-checing-r10.c | 16 ++++++++++++++++
> >> 2 files changed, 19 insertions(+), 1 deletion(-)
> >> create mode 100644 tools/testing/selftests/bpf/verifier/ret-without-checing-r10.c
> >>
> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >> index e777f50401b6..1ce80cdc4f1d 100644
> >> --- a/kernel/bpf/verifier.c
> >> +++ b/kernel/bpf/verifier.c
> >> @@ -3495,6 +3495,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> >> u32 dreg = insn->dst_reg;
> >> u32 sreg = insn->src_reg;
> >> u32 spi, i;
> >> + u32 reg_mask;
> >>
> >> if (insn->code == 0)
> >> return 0;
> >> @@ -3621,7 +3622,8 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> >> * precise, r0 and r6-r10 or any stack slot in
> >> * the current frame should be zero by now
> >> */
> >> - if (bt_reg_mask(bt) & ~BPF_REGMASK_ARGS) {
> >> + reg_mask = bt_reg_mask(bt) & ~BPF_REGMASK_ARGS;
> >> + if (reg_mask && !((reg_mask == 1 << BPF_REG_10) && env->allow_ptr_leaks)) {
> >> verbose(env, "BUG regs %x\n", bt_reg_mask(bt));
> >> WARN_ONCE(1, "verifier backtracking bug");
> >> return -EFAULT;
> >> diff --git a/tools/testing/selftests/bpf/verifier/ret-without-checing-r10.c b/tools/testing/selftests/bpf/verifier/ret-without-checing-r10.c
> >> new file mode 100644
> >> index 000000000000..56e529cf922b
> >> --- /dev/null
> >> +++ b/tools/testing/selftests/bpf/verifier/ret-without-checing-r10.c
> >> @@ -0,0 +1,16 @@
> >> +{
> >> + "pointer arithmetic: when returning from subprog in priv, do not checking r10",
> >> + .insns = {
> >> + BPF_CALL_REL(2),
> >> + BPF_MOV64_IMM(BPF_REG_0, 0),
> >> + BPF_EXIT_INSN(),
> >> + BPF_MOV64_REG(BPF_REG_3, BPF_REG_10),
> >> + BPF_MOV32_REG(BPF_REG_0, BPF_REG_10),
> >> + BPF_ALU64_REG(BPF_ADD, BPF_REG_3, BPF_REG_0),
> >> + BPF_MOV64_IMM(BPF_REG_0, 0),
> >> + BPF_EXIT_INSN(),
> >> + },
> >> + .result = ACCEPT,
> >> + .result_unpriv = REJECT,
> >> + .errstr_unpriv = "loading/calling other bpf or kernel functions are allowed for CAP_BPF and CAP_SYS_ADMIN",
> >> +},
> >> --
> >> 2.25.1
> >>
