diff mbox series

[bpf-next,v3,1/2] bpf: Fix a sdiv overflow issue

Message ID 20240913150326.1187788-1-yonghong.song@linux.dev (mailing list archive)
State Accepted
Commit 7dd34d7b7dcf9309fc6224caf4dd5b35bedddcb7
Delegated to: BPF
Headers show
Series [bpf-next,v3,1/2] bpf: Fix a sdiv overflow issue | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-PR success PR summary
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Unittests
bpf/vmtest-bpf-next-VM_Test-3 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-4 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-9 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-11 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-12 success Logs for s390x-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-16 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-next-VM_Test-15 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-17 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-18 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for x86_64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-20 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-28 success Logs for x86_64-llvm-17 / build-release / build for x86_64 with llvm-17-O2
bpf/vmtest-bpf-next-VM_Test-22 success Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-31 success Logs for x86_64-llvm-17 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-25 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-27 success Logs for x86_64-llvm-17 / build / build for x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-29 success Logs for x86_64-llvm-17 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-33 success Logs for x86_64-llvm-17 / veristat
bpf/vmtest-bpf-next-VM_Test-38 success Logs for x86_64-llvm-18 / test (test_progs_cpuv4, false, 360) / test_progs_cpuv4 on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-32 success Logs for x86_64-llvm-17 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-24 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-30 success Logs for x86_64-llvm-17 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-23 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-26 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-36 success Logs for x86_64-llvm-18 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-35 success Logs for x86_64-llvm-18 / build-release / build for x86_64 with llvm-18-O2
bpf/vmtest-bpf-next-VM_Test-37 success Logs for x86_64-llvm-18 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-39 success Logs for x86_64-llvm-18 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-21 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-41 success Logs for x86_64-llvm-18 / veristat
bpf/vmtest-bpf-next-VM_Test-40 success Logs for x86_64-llvm-18 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-34 success Logs for x86_64-llvm-18 / build / build for x86_64 with llvm-18
netdev/series_format success Single patches do not need cover letters
netdev/tree_selection success Clearly marked for bpf-next, async
netdev/ynl success Generated files up to date; no warnings/errors; no diff in generated;
netdev/fixes_present success Fixes tag not required for -next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 16 this patch: 16
netdev/build_tools success No tools touched, skip
netdev/cc_maintainers warning 8 maintainers not CCed: sdf@fomichev.me eddyz87@gmail.com haoluo@google.com jolsa@kernel.org song@kernel.org kpsingh@kernel.org martin.lau@linux.dev john.fastabend@gmail.com
netdev/build_clang success Errors and warnings before: 16 this patch: 16
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/deprecated_api success None detected
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 26 this patch: 26
netdev/checkpatch warning CHECK: multiple assignments should be avoided WARNING: line length of 81 exceeds 80 columns WARNING: line length of 83 exceeds 80 columns WARNING: line length of 84 exceeds 80 columns WARNING: line length of 86 exceeds 80 columns WARNING: line length of 87 exceeds 80 columns WARNING: line length of 88 exceeds 80 columns WARNING: line length of 90 exceeds 80 columns
netdev/build_clang_rust success No Rust files in patch. Skipping build
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-next-VM_Test-8 success Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-7 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-13 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc

Commit Message

Yonghong Song Sept. 13, 2024, 3:03 p.m. UTC 
Zac Ecob reported a problem where a bpf program may cause kernel crash due
to the following error:
  Oops: divide error: 0000 [#1] PREEMPT SMP KASAN PTI

The failure is due to the below signed divide:
  LLONG_MIN/-1 where LLONG_MIN equals to -9,223,372,036,854,775,808.
LLONG_MIN/-1 is supposed to give a positive number 9,223,372,036,854,775,808,
but it is impossible since for 64-bit system, the maximum positive
number is 9,223,372,036,854,775,807. On x86_64, LLONG_MIN/-1 will
cause a kernel exception. On arm64, the result for LLONG_MIN/-1 is
LLONG_MIN.

Further investigation found all the following sdiv/smod cases may trigger
an exception when bpf program is running on x86_64 platform:
  - LLONG_MIN/-1 for 64bit operation
  - INT_MIN/-1 for 32bit operation
  - LLONG_MIN%-1 for 64bit operation
  - INT_MIN%-1 for 32bit operation
where -1 can be an immediate or in a register.

On arm64, there are no exceptions:
  - LLONG_MIN/-1 = LLONG_MIN
  - INT_MIN/-1 = INT_MIN
  - LLONG_MIN%-1 = 0
  - INT_MIN%-1 = 0
where -1 can be an immediate or in a register.

Insn patching is needed to handle the above cases and the patched codes
produced results aligned with above arm64 result. The below are pseudo
codes to handle sdiv/smod exceptions including both divisor -1 and divisor 0
and the divisor is stored in a register.

sdiv:
      tmp = rX
      tmp += 1 /* [-1, 0] -> [0, 1]
      if tmp >(unsigned) 1 goto L2
      if tmp == 0 goto L1
      rY = 0
  L1:
      rY = -rY;
      goto L3
  L2:
      rY /= rX
  L3:

smod:
      tmp = rX
      tmp += 1 /* [-1, 0] -> [0, 1]
      if tmp >(unsigned) 1 goto L1
      if tmp == 1 (is64 ? goto L2 : goto L3)
      rY = 0;
      goto L2
  L1:
      rY %= rX
  L2:
      goto L4  // only when !is64
  L3:
      wY = wY  // only when !is64
  L4:

  [1] https://lore.kernel.org/bpf/tPJLTEh7S_DxFEqAI2Ji5MBSoZVg7_G-Py2iaZpAaWtM961fFTWtsnlzwvTbzBzaUzwQAoNATXKUlt0LZOFgnDcIyKCswAnAGdUF3LBrhGQ=@protonmail.com/

Reported-by: Zac Ecob <zacecob@protonmail.com>
Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
 kernel/bpf/verifier.c | 93 +++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 89 insertions(+), 4 deletions(-)

Changelogs:
  v2 -> v3:
    - Change sdiv/smod (r/r, r%r) patched insn to be more efficient
      for default case.
  v1 -> v2:
    - Handle more crash cases like 32bit operation and modules.
    - Add more tests to test new cases.

Comments

Andrii Nakryiko Sept. 13, 2024, 5:26 p.m. UTC | #1 
On Fri, Sep 13, 2024 at 8:03 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>
> Zac Ecob reported a problem where a bpf program may cause kernel crash due
> to the following error:
>   Oops: divide error: 0000 [#1] PREEMPT SMP KASAN PTI
>
> The failure is due to the below signed divide:
>   LLONG_MIN/-1 where LLONG_MIN equals to -9,223,372,036,854,775,808.
> LLONG_MIN/-1 is supposed to give a positive number 9,223,372,036,854,775,808,
> but it is impossible since for 64-bit system, the maximum positive
> number is 9,223,372,036,854,775,807. On x86_64, LLONG_MIN/-1 will
> cause a kernel exception. On arm64, the result for LLONG_MIN/-1 is
> LLONG_MIN.
>
> Further investigation found all the following sdiv/smod cases may trigger
> an exception when bpf program is running on x86_64 platform:
>   - LLONG_MIN/-1 for 64bit operation
>   - INT_MIN/-1 for 32bit operation
>   - LLONG_MIN%-1 for 64bit operation
>   - INT_MIN%-1 for 32bit operation
> where -1 can be an immediate or in a register.
>
> On arm64, there are no exceptions:
>   - LLONG_MIN/-1 = LLONG_MIN
>   - INT_MIN/-1 = INT_MIN
>   - LLONG_MIN%-1 = 0
>   - INT_MIN%-1 = 0
> where -1 can be an immediate or in a register.
>
> Insn patching is needed to handle the above cases and the patched codes
> produced results aligned with above arm64 result. The below are pseudo
> codes to handle sdiv/smod exceptions including both divisor -1 and divisor 0
> and the divisor is stored in a register.
>
> sdiv:
>       tmp = rX
>       tmp += 1 /* [-1, 0] -> [0, 1]
>       if tmp >(unsigned) 1 goto L2
>       if tmp == 0 goto L1
>       rY = 0
>   L1:
>       rY = -rY;
>       goto L3
>   L2:
>       rY /= rX
>   L3:
>
> smod:
>       tmp = rX
>       tmp += 1 /* [-1, 0] -> [0, 1]
>       if tmp >(unsigned) 1 goto L1
>       if tmp == 1 (is64 ? goto L2 : goto L3)
>       rY = 0;
>       goto L2
>   L1:
>       rY %= rX
>   L2:
>       goto L4  // only when !is64
>   L3:
>       wY = wY  // only when !is64
>   L4:
>
>   [1] https://lore.kernel.org/bpf/tPJLTEh7S_DxFEqAI2Ji5MBSoZVg7_G-Py2iaZpAaWtM961fFTWtsnlzwvTbzBzaUzwQAoNATXKUlt0LZOFgnDcIyKCswAnAGdUF3LBrhGQ=@protonmail.com/
>
> Reported-by: Zac Ecob <zacecob@protonmail.com>
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> ---
>  kernel/bpf/verifier.c | 93 +++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 89 insertions(+), 4 deletions(-)
>
> Changelogs:
>   v2 -> v3:
>     - Change sdiv/smod (r/r, r%r) patched insn to be more efficient
>       for default case.
>   v1 -> v2:
>     - Handle more crash cases like 32bit operation and modules.
>     - Add more tests to test new cases.
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index f35b80c16cda..69b8d91f5136 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -20499,13 +20499,46 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
>                         /* Convert BPF_CLASS(insn->code) == BPF_ALU64 to 32-bit ALU */
>                         insn->code = BPF_ALU | BPF_OP(insn->code) | BPF_SRC(insn->code);
>
> -               /* Make divide-by-zero exceptions impossible. */
> +               /* Make sdiv/smod divide-by-minus-one exceptions impossible. */
> +               if ((insn->code == (BPF_ALU64 | BPF_MOD | BPF_K) ||
> +                    insn->code == (BPF_ALU64 | BPF_DIV | BPF_K) ||
> +                    insn->code == (BPF_ALU | BPF_MOD | BPF_K) ||
> +                    insn->code == (BPF_ALU | BPF_DIV | BPF_K)) &&
> +                   insn->off == 1 && insn->imm == -1) {
> +                       bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
> +                       bool isdiv = BPF_OP(insn->code) == BPF_DIV;
> +                       struct bpf_insn *patchlet;
> +                       struct bpf_insn chk_and_sdiv[] = {
> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
> +                                            BPF_OP(BPF_NEG) | BPF_K, insn->dst_reg,
> +                                            0, 0, 0),
> +                       };
> +                       struct bpf_insn chk_and_smod[] = {
> +                               BPF_MOV32_IMM(insn->dst_reg, 0),
> +                       };
> +
> +                       patchlet = isdiv ? chk_and_sdiv : chk_and_smod;
> +                       cnt = isdiv ? ARRAY_SIZE(chk_and_sdiv) : ARRAY_SIZE(chk_and_smod);
> +
> +                       new_prog = bpf_patch_insn_data(env, i + delta, patchlet, cnt);
> +                       if (!new_prog)
> +                               return -ENOMEM;
> +
> +                       delta    += cnt - 1;
> +                       env->prog = prog = new_prog;
> +                       insn      = new_prog->insnsi + i + delta;
> +                       goto next_insn;
> +               }
> +
> +               /* Make divide-by-zero and divide-by-minus-one exceptions impossible. */
>                 if (insn->code == (BPF_ALU64 | BPF_MOD | BPF_X) ||
>                     insn->code == (BPF_ALU64 | BPF_DIV | BPF_X) ||
>                     insn->code == (BPF_ALU | BPF_MOD | BPF_X) ||
>                     insn->code == (BPF_ALU | BPF_DIV | BPF_X)) {
>                         bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
>                         bool isdiv = BPF_OP(insn->code) == BPF_DIV;
> +                       bool is_sdiv = isdiv && insn->off == 1;
> +                       bool is_smod = !isdiv && insn->off == 1;
>                         struct bpf_insn *patchlet;
>                         struct bpf_insn chk_and_div[] = {
>                                 /* [R,W]x div 0 -> 0 */
> @@ -20525,10 +20558,62 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
>                                 BPF_JMP_IMM(BPF_JA, 0, 0, 1),
>                                 BPF_MOV32_REG(insn->dst_reg, insn->dst_reg),
>                         };
> +                       struct bpf_insn chk_and_sdiv[] = {
> +                               /* [R,W]x sdiv 0 -> 0
> +                                * LLONG_MIN sdiv -1 -> LLONG_MIN
> +                                * INT_MIN sdiv -1 -> INT_MIN
> +                                */
> +                               BPF_MOV64_REG(BPF_REG_AX, insn->src_reg),
> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
> +                                            BPF_OP(BPF_ADD) | BPF_K, BPF_REG_AX,
> +                                            0, 0, 1),
> +                               BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
> +                                            BPF_JGT | BPF_K, BPF_REG_AX,
> +                                            0, 4, 1),
> +                               BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
> +                                            BPF_JEQ | BPF_K, BPF_REG_AX,
> +                                            0, 1, 0),
> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
> +                                            BPF_OP(BPF_MOV) | BPF_K, insn->dst_reg,
> +                                            0, 0, 0),
> +                               /* BPF_NEG(LLONG_MIN) == -LLONG_MIN == LLONG_MIN */
> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
> +                                            BPF_OP(BPF_NEG) | BPF_K, insn->dst_reg,
> +                                            0, 0, 0),
> +                               BPF_JMP_IMM(BPF_JA, 0, 0, 1),
> +                               *insn,
> +                       };
> +                       struct bpf_insn chk_and_smod[] = {
> +                               /* [R,W]x mod 0 -> [R,W]x */
> +                               /* [R,W]x mod -1 -> 0 */
> +                               BPF_MOV64_REG(BPF_REG_AX, insn->src_reg),
> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
> +                                            BPF_OP(BPF_ADD) | BPF_K, BPF_REG_AX,
> +                                            0, 0, 1),
> +                               BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
> +                                            BPF_JGT | BPF_K, BPF_REG_AX,
> +                                            0, 3, 1),
> +                               BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
> +                                            BPF_JEQ | BPF_K, BPF_REG_AX,
> +                                            0, 3 + (is64 ? 0 : 1), 1),
> +                               BPF_MOV32_IMM(insn->dst_reg, 0),
> +                               BPF_JMP_IMM(BPF_JA, 0, 0, 1),
> +                               *insn,
> +                               BPF_JMP_IMM(BPF_JA, 0, 0, 1),
> +                               BPF_MOV32_REG(insn->dst_reg, insn->dst_reg),
> +                       };
>
> -                       patchlet = isdiv ? chk_and_div : chk_and_mod;
> -                       cnt = isdiv ? ARRAY_SIZE(chk_and_div) :
> -                                     ARRAY_SIZE(chk_and_mod) - (is64 ? 2 : 0);
> +                       if (is_sdiv) {
> +                               patchlet = chk_and_sdiv;
> +                               cnt = ARRAY_SIZE(chk_and_sdiv);
> +                       } else if (is_smod) {
> +                               patchlet = chk_and_smod;
> +                               cnt = ARRAY_SIZE(chk_and_smod) - (is64 ? 2 : 0);
> +                       } else {
> +                               patchlet = isdiv ? chk_and_div : chk_and_mod;
> +                               cnt = isdiv ? ARRAY_SIZE(chk_and_div) :
> +                                             ARRAY_SIZE(chk_and_mod) - (is64 ? 2 : 0);
> +                       }

looking at how much isdiv vs ismod specific logic we have, it seems
like it would be cleaner (and would use less stack as well) to have
sdiv vs smod cases handled separately.

But the logic looks good to me, so

Acked-by: Andrii Nakryiko <andrii@kernel.org>

>
>                         new_prog = bpf_patch_insn_data(env, i + delta, patchlet, cnt);
>                         if (!new_prog)
> --
> 2.43.5
>
Alexei Starovoitov Sept. 13, 2024, 7:44 p.m. UTC | #2 
On Fri, Sep 13, 2024 at 8:03 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>
> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
> +                                            BPF_OP(BPF_ADD) | BPF_K, BPF_REG_AX,
> +                                            0, 0, 1),
> +                               BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
> +                                            BPF_JGT | BPF_K, BPF_REG_AX,
> +                                            0, 4, 1),
> +                               BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
> +                                            BPF_JEQ | BPF_K, BPF_REG_AX,
> +                                            0, 1, 0),
> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
> +                                            BPF_OP(BPF_MOV) | BPF_K, insn->dst_reg,
> +                                            0, 0, 0),
> +                               /* BPF_NEG(LLONG_MIN) == -LLONG_MIN == LLONG_MIN */
> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
> +                                            BPF_OP(BPF_NEG) | BPF_K, insn->dst_reg,

lgtm, but all of BPF_OP(..) are confusing.
What's the point?
We use BPF_OP(insn->code) to reuse the code when we create a new opcode,
but BPF_OP(BPF_NEG) == BPF_NEG and BPF_OP(BPF_MOV) == BPF_MOV, so why?

If I'm not missing anything I can remove these BPF_OP wrapping when applying.
wdyt?
Yonghong Song Sept. 13, 2024, 8 p.m. UTC | #3 
On 9/13/24 12:44 PM, Alexei Starovoitov wrote:
> On Fri, Sep 13, 2024 at 8:03 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
>> +                                            BPF_OP(BPF_ADD) | BPF_K, BPF_REG_AX,
>> +                                            0, 0, 1),
>> +                               BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
>> +                                            BPF_JGT | BPF_K, BPF_REG_AX,
>> +                                            0, 4, 1),
>> +                               BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
>> +                                            BPF_JEQ | BPF_K, BPF_REG_AX,
>> +                                            0, 1, 0),
>> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
>> +                                            BPF_OP(BPF_MOV) | BPF_K, insn->dst_reg,
>> +                                            0, 0, 0),
>> +                               /* BPF_NEG(LLONG_MIN) == -LLONG_MIN == LLONG_MIN */
>> +                               BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
>> +                                            BPF_OP(BPF_NEG) | BPF_K, insn->dst_reg,
> lgtm, but all of BPF_OP(..) are confusing.
> What's the point?
> We use BPF_OP(insn->code) to reuse the code when we create a new opcode,
> but BPF_OP(BPF_NEG) == BPF_NEG and BPF_OP(BPF_MOV) == BPF_MOV, so why?

Sorry, I focused on the algorithm and missed this one. Yes, changing
BPF_OP(BPF_NEG) to BPF_NEG and other similar cases are correct.

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 69b8d91f5136..068f763dcefb 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20510,7 +20510,7 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                         struct bpf_insn *patchlet;
                         struct bpf_insn chk_and_sdiv[] = {
                                 BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
-                                            BPF_OP(BPF_NEG) | BPF_K, insn->dst_reg,
+                                            BPF_NEG | BPF_K, insn->dst_reg,
                                              0, 0, 0),
                         };
                         struct bpf_insn chk_and_smod[] = {
@@ -20565,7 +20565,7 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                                  */
                                 BPF_MOV64_REG(BPF_REG_AX, insn->src_reg),
                                 BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
-                                            BPF_OP(BPF_ADD) | BPF_K, BPF_REG_AX,
+                                            BPF_ADD | BPF_K, BPF_REG_AX,
                                              0, 0, 1),
                                 BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
                                              BPF_JGT | BPF_K, BPF_REG_AX,
@@ -20574,11 +20574,11 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                                              BPF_JEQ | BPF_K, BPF_REG_AX,
                                              0, 1, 0),
                                 BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
-                                            BPF_OP(BPF_MOV) | BPF_K, insn->dst_reg,
+                                            BPF_MOV | BPF_K, insn->dst_reg,
                                              0, 0, 0),
                                 /* BPF_NEG(LLONG_MIN) == -LLONG_MIN == LLONG_MIN */
                                 BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
-                                            BPF_OP(BPF_NEG) | BPF_K, insn->dst_reg,
+                                            BPF_NEG | BPF_K, insn->dst_reg,
                                              0, 0, 0),
                                 BPF_JMP_IMM(BPF_JA, 0, 0, 1),
                                 *insn,
@@ -20588,7 +20588,7 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
                                 /* [R,W]x mod -1 -> 0 */
                                 BPF_MOV64_REG(BPF_REG_AX, insn->src_reg),
                                 BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
-                                            BPF_OP(BPF_ADD) | BPF_K, BPF_REG_AX,
+                                            BPF_ADD | BPF_K, BPF_REG_AX,
                                              0, 0, 1),
                                 BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |

>
> If I'm not missing anything I can remove these BPF_OP wrapping when applying.
> wdyt?

Yes, pelase do. Thanks!
patchwork-bot+netdevbpf@kernel.org Sept. 13, 2024, 8:20 p.m. UTC | #4 
Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Fri, 13 Sep 2024 08:03:26 -0700 you wrote:
> Zac Ecob reported a problem where a bpf program may cause kernel crash due
> to the following error:
>   Oops: divide error: 0000 [#1] PREEMPT SMP KASAN PTI
> 
> The failure is due to the below signed divide:
>   LLONG_MIN/-1 where LLONG_MIN equals to -9,223,372,036,854,775,808.
> LLONG_MIN/-1 is supposed to give a positive number 9,223,372,036,854,775,808,
> but it is impossible since for 64-bit system, the maximum positive
> number is 9,223,372,036,854,775,807. On x86_64, LLONG_MIN/-1 will
> cause a kernel exception. On arm64, the result for LLONG_MIN/-1 is
> LLONG_MIN.
> 
> [...]

Here is the summary with links:
  - [bpf-next,v3,1/2] bpf: Fix a sdiv overflow issue
    https://git.kernel.org/bpf/bpf-next/c/7dd34d7b7dcf
  - [bpf-next,v3,2/2] selftests/bpf: Add tests for sdiv/smod overflow cases
    https://git.kernel.org/bpf/bpf-next/c/a18062d54a0b

You are awesome, thank you!
diff mbox series

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index f35b80c16cda..69b8d91f5136 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20499,13 +20499,46 @@  static int do_misc_fixups(struct bpf_verifier_env *env)
 			/* Convert BPF_CLASS(insn->code) == BPF_ALU64 to 32-bit ALU */
 			insn->code = BPF_ALU | BPF_OP(insn->code) | BPF_SRC(insn->code);
 
-		/* Make divide-by-zero exceptions impossible. */
+		/* Make sdiv/smod divide-by-minus-one exceptions impossible. */
+		if ((insn->code == (BPF_ALU64 | BPF_MOD | BPF_K) ||
+		     insn->code == (BPF_ALU64 | BPF_DIV | BPF_K) ||
+		     insn->code == (BPF_ALU | BPF_MOD | BPF_K) ||
+		     insn->code == (BPF_ALU | BPF_DIV | BPF_K)) &&
+		    insn->off == 1 && insn->imm == -1) {
+			bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
+			bool isdiv = BPF_OP(insn->code) == BPF_DIV;
+			struct bpf_insn *patchlet;
+			struct bpf_insn chk_and_sdiv[] = {
+				BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
+					     BPF_OP(BPF_NEG) | BPF_K, insn->dst_reg,
+					     0, 0, 0),
+			};
+			struct bpf_insn chk_and_smod[] = {
+				BPF_MOV32_IMM(insn->dst_reg, 0),
+			};
+
+			patchlet = isdiv ? chk_and_sdiv : chk_and_smod;
+			cnt = isdiv ? ARRAY_SIZE(chk_and_sdiv) : ARRAY_SIZE(chk_and_smod);
+
+			new_prog = bpf_patch_insn_data(env, i + delta, patchlet, cnt);
+			if (!new_prog)
+				return -ENOMEM;
+
+			delta    += cnt - 1;
+			env->prog = prog = new_prog;
+			insn      = new_prog->insnsi + i + delta;
+			goto next_insn;
+		}
+
+		/* Make divide-by-zero and divide-by-minus-one exceptions impossible. */
 		if (insn->code == (BPF_ALU64 | BPF_MOD | BPF_X) ||
 		    insn->code == (BPF_ALU64 | BPF_DIV | BPF_X) ||
 		    insn->code == (BPF_ALU | BPF_MOD | BPF_X) ||
 		    insn->code == (BPF_ALU | BPF_DIV | BPF_X)) {
 			bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
 			bool isdiv = BPF_OP(insn->code) == BPF_DIV;
+			bool is_sdiv = isdiv && insn->off == 1;
+			bool is_smod = !isdiv && insn->off == 1;
 			struct bpf_insn *patchlet;
 			struct bpf_insn chk_and_div[] = {
 				/* [R,W]x div 0 -> 0 */
@@ -20525,10 +20558,62 @@  static int do_misc_fixups(struct bpf_verifier_env *env)
 				BPF_JMP_IMM(BPF_JA, 0, 0, 1),
 				BPF_MOV32_REG(insn->dst_reg, insn->dst_reg),
 			};
+			struct bpf_insn chk_and_sdiv[] = {
+				/* [R,W]x sdiv 0 -> 0
+				 * LLONG_MIN sdiv -1 -> LLONG_MIN
+				 * INT_MIN sdiv -1 -> INT_MIN
+				 */
+				BPF_MOV64_REG(BPF_REG_AX, insn->src_reg),
+				BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
+					     BPF_OP(BPF_ADD) | BPF_K, BPF_REG_AX,
+					     0, 0, 1),
+				BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
+					     BPF_JGT | BPF_K, BPF_REG_AX,
+					     0, 4, 1),
+				BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
+					     BPF_JEQ | BPF_K, BPF_REG_AX,
+					     0, 1, 0),
+				BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
+					     BPF_OP(BPF_MOV) | BPF_K, insn->dst_reg,
+					     0, 0, 0),
+				/* BPF_NEG(LLONG_MIN) == -LLONG_MIN == LLONG_MIN */
+				BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
+					     BPF_OP(BPF_NEG) | BPF_K, insn->dst_reg,
+					     0, 0, 0),
+				BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+				*insn,
+			};
+			struct bpf_insn chk_and_smod[] = {
+				/* [R,W]x mod 0 -> [R,W]x */
+				/* [R,W]x mod -1 -> 0 */
+				BPF_MOV64_REG(BPF_REG_AX, insn->src_reg),
+				BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
+					     BPF_OP(BPF_ADD) | BPF_K, BPF_REG_AX,
+					     0, 0, 1),
+				BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
+					     BPF_JGT | BPF_K, BPF_REG_AX,
+					     0, 3, 1),
+				BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
+					     BPF_JEQ | BPF_K, BPF_REG_AX,
+					     0, 3 + (is64 ? 0 : 1), 1),
+				BPF_MOV32_IMM(insn->dst_reg, 0),
+				BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+				*insn,
+				BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+				BPF_MOV32_REG(insn->dst_reg, insn->dst_reg),
+			};
 
-			patchlet = isdiv ? chk_and_div : chk_and_mod;
-			cnt = isdiv ? ARRAY_SIZE(chk_and_div) :
-				      ARRAY_SIZE(chk_and_mod) - (is64 ? 2 : 0);
+			if (is_sdiv) {
+				patchlet = chk_and_sdiv;
+				cnt = ARRAY_SIZE(chk_and_sdiv);
+			} else if (is_smod) {
+				patchlet = chk_and_smod;
+				cnt = ARRAY_SIZE(chk_and_smod) - (is64 ? 2 : 0);
+			} else {
+				patchlet = isdiv ? chk_and_div : chk_and_mod;
+				cnt = isdiv ? ARRAY_SIZE(chk_and_div) :
+					      ARRAY_SIZE(chk_and_mod) - (is64 ? 2 : 0);
+			}
 
 			new_prog = bpf_patch_insn_data(env, i + delta, patchlet, cnt);
 			if (!new_prog)