Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]


On 6/9/21 11:20 AM, Kees Cook wrote:
On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:
On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
<alexei.starovoitov@xxxxxxxxx> wrote:
On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@xxxxxx> wrote:
On 6/5/21 8:01 AM, Kurt Manucredo wrote:
Syzbot detects a shift-out-of-bounds in ___bpf_prog_run()

This is not enough. We need more information on why this happens
so we can judge whether the patch indeed fixed the issue.

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid
missing them and return with error when detected.

Reported-and-tested-by: syzbot+bed360704c521841c85d@xxxxxxxxxxxxxxxxxxxxxxxxx
Signed-off-by: Kurt Manucredo <fuzzybritches0@xxxxxxxxx>

v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
       Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
       check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
       check in ___bpf_prog_run().


kind regards


   kernel/bpf/verifier.c | 30 +++++++++---------------------
   1 file changed, 9 insertions(+), 21 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
       u32_min_val = src_reg.u32_min_value;
       u32_max_val = src_reg.u32_max_value;

+     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+                     umax_val >= insn_bitness) {
+             /* Shifts greater than 31 or 63 are undefined.
+              * This includes shifts by a negative number.
+              */
+             verbose(env, "invalid shift %lld\n", umax_val);
+             return -EINVAL;
+     }

I think your fix is good. I would like to move after

I suspect such change will break valid programs that do shift by register.

the following code though:

          if (!src_known &&
              opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                  __mark_reg_unknown(env, dst_reg);
                  return 0;

       if (alu32) {
               src_known = tnum_subreg_is_const(src_reg.var_off);
               if ((src_known &&
@@ -7592,39 +7601,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
               scalar_min_max_xor(dst_reg, &src_reg);
       case BPF_LSH:
-             if (umax_val >= insn_bitness) {
-                     /* Shifts greater than 31 or 63 are undefined.
-                      * This includes shifts by a negative number.
-                      */
-                     mark_reg_unknown(env, regs, insn->dst_reg);
-                     break;
-             }

I think this is what happens. For the above case, we simply
marks the dst reg as unknown and didn't fail verification.
So later on at runtime, the shift optimization will have wrong
shift value (> 31/64). Please correct me if this is not right
analysis. As I mentioned in the early please write detailed
analysis in commit log.

The large shift is not wrong. It's just undefined.
syzbot has to ignore such cases.

Hi Alexei,

The report is produced by KUBSAN. I thought there was an agreement on
cleaning up KUBSAN reports from the kernel (the subset enabled on
syzbot at least).
What exactly cases should KUBSAN ignore?
+linux-hardening/kasan-dev for KUBSAN false positive

Can check_shl_overflow() be used at all? Best to just make things
readable and compiler-happy, whatever the implementation. :)

This is not a compile issue. If the shift amount is a constant,
compiler should have warned and user should fix the warning.

This is because user code has
something like
    a << s;
where s is a unknown variable and
verifier just marked the result of a << s as unknown value.
Verifier may not reject the code depending on how a << s result
is used.

If bpf program writer uses check_shl_overflow() or some kind
of checking for shift value and won't do shifting if the
shifting may cause an undefined result, there should not
be any kubsan warning.

[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]

  Powered by Linux