From: Qiliang Yuan The verifier queues its patches in a patch list. One commit builds the new image of the prog and gives each jump a new offset. Test the cases in which this offset can be incorrect. In most tests the patched insn is 'r0 /= r1', which gets a patch of 4 insns. - A jump to a patched insn lands on the first insn of its patch: forward, backward and with gotox. - The target of gotox is a ctx load that becomes a load and a mask. A patch in front of it changes its index, thus the entry of the insn array must move. Each incorrect landing gives a different return value. - A jump over patches gets a longer offset. One such jump is in the patch of may_goto and leaves its patch. - A jump over 8200 patches gets out of range, and the load fails. - A backward may_goto goes over 8191 patches. The conditional jump in its patch is out of range by 1. The verifier must select 'gotol' when it queues the patch, but the offset is final only at the commit. The test compares the final offset. The tests have may_goto as a raw insn. Thus the assembler does not have to know it. They run as a serial test, because other tests set net.core.bpf_jit_harden, and the blinding of constants changes the xlated insns. Signed-off-by: Qiliang Yuan Signed-off-by: Alexei Starovoitov --- .../selftests/bpf/prog_tests/verifier.c | 3 + .../selftests/bpf/progs/verifier_patch_list.c | 245 ++++++++++++++++++ 2 files changed, 248 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_patch_list.c diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c index 386ad81051a9..99f0551c8b59 100644 --- a/tools/testing/selftests/bpf/prog_tests/verifier.c +++ b/tools/testing/selftests/bpf/prog_tests/verifier.c @@ -96,6 +96,7 @@ #include "verifier_netfilter_retcode.skel.h" #include "verifier_bpf_fastcall.skel.h" #include "verifier_or_jmp32_k.skel.h" +#include "verifier_patch_list.skel.h" #include "verifier_percpu_addr.skel.h" #include "verifier_precision.skel.h" #include "verifier_prevent_map_lookup.skel.h" @@ -287,6 +288,8 @@ void test_verifier_netfilter_ctx(void) { RUN(verifier_netfilter_ctx); } void test_verifier_netfilter_retcode(void) { RUN(verifier_netfilter_retcode); } void test_verifier_bpf_fastcall(void) { RUN(verifier_bpf_fastcall); } void test_verifier_or_jmp32_k(void) { RUN(verifier_or_jmp32_k); } +/* Serial: the xlated code is another one while another test sets bpf_jit_harden */ +void serial_test_verifier_patch_list(void) { RUN(verifier_patch_list); } void test_verifier_percpu_addr(void) { RUN(verifier_percpu_addr); } void test_verifier_precision(void) { RUN(verifier_precision); } void test_verifier_prevent_map_lookup(void) { RUN(verifier_prevent_map_lookup); } diff --git a/tools/testing/selftests/bpf/progs/verifier_patch_list.c b/tools/testing/selftests/bpf/progs/verifier_patch_list.c new file mode 100644 index 000000000000..ffadd723f947 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/verifier_patch_list.c @@ -0,0 +1,245 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include +#include +#include "../../../include/linux/filter.h" +#include "bpf_misc.h" + +/* + * bpf_do_misc_fixups() guards each division by a register against division + * by zero with a 4 insn patch. Jumps to a patched insn must land on the + * first insn of its patch, other jumps must follow the insns they target. + * + * JITs that need explicit zero extensions, like s390x and riscv64, get one + * more insn behind the 'w0 ^= w0' of that patch. The tests that compare such + * code don't run there. + */ + +SEC("raw_tp") +__description("patch list: forward jumps to and over patched insns") +__arch_x86_64 +__arch_arm64 +__success +__xlated("0: call") +__xlated("1: r1 = r0") +__xlated("2: r0 = 7") +__xlated("3: if r1 > 0x5 goto pc+1") +__xlated("4: r0 = 9") +__xlated("5: if r1 != 0x0 goto pc+2") +__xlated("6: w0 ^= w0") +__xlated("7: goto pc+1") +__xlated("8: r0 /= r1") +__xlated("9: if r0 > 0x3 goto pc+4") +__xlated("10: if r1 != 0x0 goto pc+2") +__xlated("11: w0 ^= w0") +__xlated("12: goto pc+1") +__xlated("13: r0 /= r1") +__xlated("14: exit") +__naked void patch_list_forward(void) +{ + asm volatile ( + "call %[bpf_get_prandom_u32];" + "r1 = r0;" + "r0 = 7;" + "if r1 > 5 goto l0_%=;" + "r0 = 9;" +"l0_%=:" + "r0 /= r1;" + "if r0 > 3 goto l1_%=;" + "r0 /= r1;" +"l1_%=:" + "exit;" + : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("raw_tp") +__description("patch list: backward jump to a patched insn") +__arch_x86_64 +__arch_arm64 +__success +__xlated("0: call") +__xlated("1: r1 = r0") +__xlated("2: r2 = 0") +__xlated("3: if r1 != 0x0 goto pc+2") +__xlated("4: w0 ^= w0") +__xlated("5: goto pc+1") +__xlated("6: r0 /= r1") +__xlated("7: r2 += 1") +__xlated("8: if r2 < 0x3 goto pc-6") +__xlated("9: exit") +__naked void patch_list_backward(void) +{ + asm volatile ( + "call %[bpf_get_prandom_u32];" + "r1 = r0;" + "r2 = 0;" +"l0_%=:" + "r0 /= r1;" + "r2 += 1;" + "if r2 < 3 goto l0_%=;" + "exit;" + : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* The jump of may_goto leaves its own patch and crosses another one. */ +SEC("raw_tp") +__description("patch list: may_goto between patched insns") +__arch_x86_64 +__arch_arm64 +__success +__xlated("0: *(u64 *)(r10 -16) = 65535") +__xlated("1: *(u64 *)(r10 -8) = 0") +__xlated("2: call") +__xlated("3: r1 = r0") +__xlated("4: if r1 != 0x0 goto pc+2") +__xlated("5: w0 ^= w0") +__xlated("6: goto pc+1") +__xlated("7: r0 /= r1") +__xlated("8: r12 = *(u64 *)(r10 -16)") +__xlated("9: if r12 == 0x0 goto pc+9") +__xlated("...") +__xlated("15: if r1 != 0x0 goto pc+2") +__xlated("16: w0 ^= w0") +__xlated("17: goto pc+1") +__xlated("18: r0 /= r1") +__xlated("19: exit") +__naked void patch_list_may_goto(void) +{ + asm volatile ( + "call %[bpf_get_prandom_u32];" + "r1 = r0;" + "r0 /= r1;" + ".8byte %[may_goto];" + "r0 /= r1;" + "exit;" + : + : __imm(bpf_get_prandom_u32), + __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 1 /* offset */, 0)) + : __clobber_all); +} + +/* + * The conditional jump skips 8200 divisions, which their patches turn into + * 32800 insns, too far for its 16-bit offset. + */ +SEC("raw_tp") +__description("patch list: jump pushed out of range by patches") +__failure __msg("cannot be patched due to 16-bit range") +__naked void patch_list_jump_out_of_range(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + if r0 == 0 goto 0f; \ + .rept 8200; \ + r0 /= r1; \ + .endr; \ +0: r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* the JITs that support gotox, as in verifier_gotox.c */ +#if defined(__TARGET_ARCH_x86) || defined(__TARGET_ARCH_arm64) || \ + defined(__TARGET_ARCH_powerpc) || \ + (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) +/* + * An indirect jump to a patched insn must land on the first insn of its + * patch. The load of pkt_type, which is 0, becomes a load and a mask. Behind + * the load r0 still has bits of 255, and the result isn't 7. + * + * mark is 0, which the verifier doesn't know. So the division stays, never + * runs, and its patch moves the target by 3 insns. The old index of the target + * is the 'goto +1' of that patch, which goes to the exit with 255 in r0. + */ +SEC("socket") +__description("patch list: indirect jump to a patched insn") +__success __retval(7) +__load_if_JITed() +__naked void patch_list_indirect(void) +{ + asm volatile (" \ + .pushsection .jumptables,\"\",@progbits; \ +jt0_%=: \ + .quad l1_%= - socket; \ + .quad l0_%= - socket; \ + .size jt0_%=, 16; \ + .global jt0_%=; \ + .popsection; \ + r2 = *(u32 *)(r1 + %[mark]); \ + r2 &= 8; \ + r3 = jt0_%= ll; \ + r3 += r2; \ + r3 = *(u64 *)(r3 + 0); \ + r0 = 255; \ + .8byte %[gotox_r3]; \ +l0_%=: \ + r0 /= r2; \ + exit; \ +l1_%=: \ + r0 = *(u32 *)(r1 + %[pkt_type]); \ + r0 += 7; \ + exit; \ +" : + : __imm_const(mark, offsetof(struct __sk_buff, mark)), + __imm_const(pkt_type, offsetof(struct __sk_buff, pkt_type)), + __imm_insn(gotox_r3, BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_3, 0, 0, 0)) + : __clobber_all); +} +#else +SEC("socket") +__description("patch list: indirect jump to a patched insn") +__skip("the JIT does not support gotox") +__success +int patch_list_indirect(void) +{ + return 0; +} +#endif + +/* + * may_goto jumps back by 8195 insns, by 32768 once each of the 8191 + * divisions is guarded by a patch of 4 insns. That still fits the 16 bits of + * may_goto, but not the jump it expands to, which has to become gotol. Once + * the budget runs out, may_goto jumps back with r6 set and the program exits. + */ +SEC("raw_tp") +__description("patch list: backward may_goto expanded to gotol") +__arch_x86_64 +__arch_arm64 +__success +__xlated("8: if r6 != 0x0 goto pc-3") +__xlated("...") +__xlated("32776: if r12 != 0x0 goto pc+1") +__xlated("32777: gotol pc-32770") +__naked void patch_list_may_goto_gotol(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r6 = 0; \ + goto 0f; \ +1: r0 = 0; \ + exit; \ +0: if r6 != 0 goto 1b; \ + .rept 8191; \ + r0 /= r1; \ + .endr; \ + r2 = 0; \ + r6 = 1; \ + .8byte %[may_goto]; \ + r0 = 0; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32), + __imm_insn(may_goto, BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, -8195 /* offset */, 0)) + : __clobber_all); +} + +char _license[] SEC("license") = "GPL"; -- 2.55.0