Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) client-ip=2620:137:e000::3:7;
MIME-Version: 1.0
References: <CACkBjsY2q1_fUohD7hRmKGqv1MV=eP2f6XK8kjkYNw7BaiF8iQ@mail.gmail.com>
 <CACkBjsbYMC7PgoGDK71fnqJ3QMywrwoA5Ctzh84Ldp6U_+_Ygg@mail.gmail.com>
In-Reply-To: <CACkBjsbYMC7PgoGDK71fnqJ3QMywrwoA5Ctzh84Ldp6U_+_Ygg@mail.gmail.com>
From:   Hao Sun <sunhao.th@gmail.com>
Date:   Wed, 25 Oct 2023 15:20:29 +0200
Message-ID: <CACkBjsYHN2VGjRUV_KA+EBPYeOjBbOgysj4JVBFqd6pPBN-_0w@mail.gmail.com>
Subject: Re: bpf: shift-out-of-bounds in tnum_rshift()
To:     Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        John Fastabend <john.fastabend@gmail.com>,
        Andrii Nakryiko <andrii@kernel.org>,
        Martin KaFai Lau <martin.lau@linux.dev>,
        Song Liu <song@kernel.org>,
        Yonghong Song <yonghong.song@linux.dev>,
        KP Singh <kpsingh@kernel.org>,
        Stanislav Fomichev <sdf@google.com>,
        Hao Luo <haoluo@google.com>, Jiri Olsa <jolsa@kernel.org>
Cc:     bpf <bpf@vger.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Wed, Oct 25, 2023 at 2:31=E2=80=AFPM Hao Sun <sunhao.th@gmail.com> wrote=
:
>
> On Tue, Oct 24, 2023 at 2:40=E2=80=AFPM Hao Sun <sunhao.th@gmail.com> wro=
te:
> >
> > Hi,
> >
> > The following program can trigger a shift-out-of-bounds in
> > tnum_rshift(), called by scalar32_min_max_rsh():
> >
> > 0: (bc) w0 =3D w1
> > 1: (bf) r2 =3D r0
> > 2: (18) r3 =3D 0xd
> > 4: (bc) w4 =3D w0
> > 5: (bf) r5 =3D r0
> > 6: (bf) r7 =3D r3
> > 7: (bf) r8 =3D r4
> > 8: (2f) r8 *=3D r5
> > 9: (cf) r5 s>>=3D r5
> > 10: (a6) if w8 < 0xfffffffb goto pc+10
> > 11: (1f) r7 -=3D r5
> > 12: (71) r6 =3D *(u8 *)(r1 +17)
> > 13: (5f) r3 &=3D r8
> > 14: (74) w2 >>=3D 30
> > 15: (1f) r7 -=3D r5
> > 16: (5d) if r8 !=3D r6 goto pc+4
> > 17: (c7) r8 s>>=3D 5
> > 18: (cf) r0 s>>=3D r0
> > 19: (7f) r0 >>=3D r0
> > 20: (7c) w5 >>=3D w8         # shift-out-bounds here
> > 21: exit
> >
>
> Here are the c macros for the above program in case anyone needs this:
>
>         // 0: (bc) w0 =3D w1
>         BPF_MOV32_REG(BPF_REG_0, BPF_REG_1),
>         // 1: (bf) r2 =3D r0
>         BPF_MOV64_REG(BPF_REG_2, BPF_REG_0),
>         // 2: (18) r3 =3D 0xd
>         BPF_LD_IMM64(BPF_REG_3, 0xd),
>         // 4: (bc) w4 =3D w0
>         BPF_MOV32_REG(BPF_REG_4, BPF_REG_0),
>         // 5: (bf) r5 =3D r0
>         BPF_MOV64_REG(BPF_REG_5, BPF_REG_0),
>         // 6: (bf) r7 =3D r3
>         BPF_MOV64_REG(BPF_REG_7, BPF_REG_3),
>         // 7: (bf) r8 =3D r4
>         BPF_MOV64_REG(BPF_REG_8, BPF_REG_4),
>         // 8: (2f) r8 *=3D r5
>         BPF_ALU64_REG(BPF_MUL, BPF_REG_8, BPF_REG_5),
>         // 9: (cf) r5 s>>=3D r5
>         BPF_ALU64_REG(BPF_ARSH, BPF_REG_5, BPF_REG_5),
>         // 10: (a6) if w8 < 0xfffffffb goto pc+10
>         BPF_JMP32_IMM(BPF_JLT, BPF_REG_8, 0xfffffffb, 10),
>         // 11: (1f) r7 -=3D r5
>         BPF_ALU64_REG(BPF_SUB, BPF_REG_7, BPF_REG_5),
>         // 12: (71) r6 =3D *(u8 *)(r1 +17)
>         BPF_LDX_MEM(BPF_B, BPF_REG_6, BPF_REG_1, 17),
>         // 13: (5f) r3 &=3D r8
>         BPF_ALU64_REG(BPF_AND, BPF_REG_3, BPF_REG_8),
>         // 14: (74) w2 >>=3D 30
>         BPF_ALU32_IMM(BPF_RSH, BPF_REG_2, 30),
>         // 15: (1f) r7 -=3D r5
>         BPF_ALU64_REG(BPF_SUB, BPF_REG_7, BPF_REG_5),
>         // 16: (5d) if r8 !=3D r6 goto pc+4
>         BPF_JMP_REG(BPF_JNE, BPF_REG_8, BPF_REG_6, 4),
>         // 17: (c7) r8 s>>=3D 5
>         BPF_ALU64_IMM(BPF_ARSH, BPF_REG_8, 5),
>         // 18: (cf) r0 s>>=3D r0
>         BPF_ALU64_REG(BPF_ARSH, BPF_REG_0, BPF_REG_0),
>         // 19: (7f) r0 >>=3D r0
>         BPF_ALU64_REG(BPF_RSH, BPF_REG_0, BPF_REG_0),
>         // 20: (7c) w5 >>=3D w8
>         BPF_ALU32_REG(BPF_RSH, BPF_REG_5, BPF_REG_8),
>         BPF_EXIT_INSN()
>
> > After load:
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D
> > UBSAN: shift-out-of-bounds in kernel/bpf/tnum.c:44:9
> > shift exponent 255 is too large for 64-bit type 'long long unsigned int=
'
> > CPU: 2 PID: 8574 Comm: bpf-test Not tainted
> > 6.6.0-rc5-01400-g7c2f6c9fb91f-dirty #21
> > Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.15.0-1 04=
/01/2014
> > Call Trace:
> >  <TASK>
> >  __dump_stack lib/dump_stack.c:88 [inline]
> >  dump_stack_lvl+0x8e/0xb0 lib/dump_stack.c:106
> >  ubsan_epilogue lib/ubsan.c:217 [inline]
> >  __ubsan_handle_shift_out_of_bounds+0x15a/0x2f0 lib/ubsan.c:387
> >  tnum_rshift.cold+0x17/0x32 kernel/bpf/tnum.c:44
> >  scalar32_min_max_rsh kernel/bpf/verifier.c:12999 [inline]
> >  adjust_scalar_min_max_vals kernel/bpf/verifier.c:13224 [inline]
> >  adjust_reg_min_max_vals+0x1936/0x5d50 kernel/bpf/verifier.c:13338
> >  do_check kernel/bpf/verifier.c:16890 [inline]
> >  do_check_common+0x2f64/0xbb80 kernel/bpf/verifier.c:19563
> >  do_check_main kernel/bpf/verifier.c:19626 [inline]
> >  bpf_check+0x65cf/0xa9e0 kernel/bpf/verifier.c:20263
> >  bpf_prog_load+0x110e/0x1b20 kernel/bpf/syscall.c:2717
> >  __sys_bpf+0xfcf/0x4380 kernel/bpf/syscall.c:5365
> >  __do_sys_bpf kernel/bpf/syscall.c:5469 [inline]
> >  __se_sys_bpf kernel/bpf/syscall.c:5467 [inline]
> >  __x64_sys_bpf+0x73/0xb0 kernel/bpf/syscall.c:5467
> >  do_syscall_x64 arch/x86/entry/common.c:50 [inline]
> >  do_syscall_64+0x39/0xb0 arch/x86/entry/common.c:80
> >  entry_SYSCALL_64_after_hwframe+0x63/0xcd
> > RIP: 0033:0x5610511e23cd
> > Code: 24 80 00 00 00 48 0f 42 d0 48 89 94 24 68 0c 00 00 b8 41 01 00
> > 00 bf 05 00 00 00 ba 90 00 00 00 48 8d b44
> > RSP: 002b:00007f5357fc7820 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
> > RAX: ffffffffffffffda RBX: 0000000000000095 RCX: 00005610511e23cd
> > RDX: 0000000000000090 RSI: 00007f5357fc8410 RDI: 0000000000000005
> > RBP: 0000000000000000 R08: 00007f5357fca458 R09: 00007f5350005520
> > R10: 0000000000000000 R11: 0000000000000246 R12: 000000000000002b
> > R13: 0000000d00000000 R14: 000000000000002b R15: 000000000000002b
> >  </TASK>
> >

Here is another similar one, which can probably be fixed in the same
patch. Build the kernel with UBSAN and run the following repro can
easily reproduce this.

C reproducer: https://pastebin.com/raw/zNfHaBnj

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D
UBSAN: shift-out-of-bounds in kernel/bpf/verifier.c:13049:63
shift exponent 55 is too large for 32-bit type 'int'
CPU: 3 PID: 8614 Comm: poc Not tainted 6.6.0-rc5-01400-g7c2f6c9fb91f-dirty =
#22
Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.15.0-1 04/01/=
2014
Call Trace:
 <TASK>
 __dump_stack lib/dump_stack.c:88 [inline]
 dump_stack_lvl+0x8e/0xb0 lib/dump_stack.c:106
 ubsan_epilogue lib/ubsan.c:217 [inline]
 __ubsan_handle_shift_out_of_bounds+0x15a/0x2f0 lib/ubsan.c:387
 scalar32_min_max_arsh kernel/bpf/verifier.c:13049 [inline]
 adjust_scalar_min_max_vals kernel/bpf/verifier.c:13237 [inline]
 adjust_reg_min_max_vals.cold+0x116/0x353 kernel/bpf/verifier.c:13338
 do_check kernel/bpf/verifier.c:16890 [inline]
 do_check_common+0x2f64/0xbb80 kernel/bpf/verifier.c:19563
 do_check_main kernel/bpf/verifier.c:19626 [inline]
 bpf_check+0x65cf/0xa9e0 kernel/bpf/verifier.c:20263
 bpf_prog_load+0x110e/0x1b20 kernel/bpf/syscall.c:2717
 __sys_bpf+0xfcf/0x4380 kernel/bpf/syscall.c:5365
 __do_sys_bpf kernel/bpf/syscall.c:5469 [inline]
 __se_sys_bpf kernel/bpf/syscall.c:5467 [inline]
 __x64_sys_bpf+0x73/0xb0 kernel/bpf/syscall.c:5467
 do_syscall_x64 arch/x86/entry/common.c:50 [inline]
 do_syscall_64+0x39/0xb0 arch/x86/entry/common.c:80
 entry_SYSCALL_64_after_hwframe+0x63/0xcd
RIP: 0033:0x43b0a9
Code: 48 83 c4 28 c3 e8 17 1a 00 00 0f 1f 80 00 00 00 00 48 89 f8 48
89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 48
RSP: 002b:00007fffec705b18 EFLAGS: 00000202 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda RBX: 00007fffec705ff8 RCX: 000000000043b0a9
RDX: 0000000000000080 RSI: 00007fffec705b30 RDI: 0000000000000005
RBP: 00007fffec705c00 R08: 0000000400000002 R09: 0000003e00000000
R10: 00000000000000fc R11: 0000000000000202 R12: 0000000000000001
R13: 00007fffec705fe8 R14: 0000000000000001 R15: 0000000000000001
 </TASK>