Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) client-ip=23.128.96.34;
Date:   Wed, 25 Oct 2023 22:09:27 +0800
From:   Shung-Hsi Yu <shung-hsi.yu@suse.com>
To:     Hao Sun <sunhao.th@gmail.com>
Cc:     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>,
        bpf <bpf@vger.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Subject: Re: bpf: shift-out-of-bounds in tnum_rshift()
Message-ID: <ZTkhlwP-LkPkOjK2@u94a>
References: <CACkBjsY2q1_fUohD7hRmKGqv1MV=eP2f6XK8kjkYNw7BaiF8iQ@mail.gmail.com>
 <CACkBjsbYMC7PgoGDK71fnqJ3QMywrwoA5Ctzh84Ldp6U_+_Ygg@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CACkBjsbYMC7PgoGDK71fnqJ3QMywrwoA5Ctzh84Ldp6U_+_Ygg@mail.gmail.com>
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?MTdhczBDUnlvN01YTmFYd2pCTmVmS3RNam5BL3p5bnFxSXYvSTJCVGZ5ZU9s?=
 =?utf-8?B?b0N3d2ZSUEx2RkVrUi9BNWJuNkxlazZYS3RHb0VmZnVVQWdDc1AyYUF1SVZC?=
 =?utf-8?B?MDRCYzdtSWpIZjZtYWhuY3p4Y0U1WFFNSlRSVXdicnAvMnZFUVIwZHp0aGpU?=
 =?utf-8?B?eTN3eVRZTnd5QkxqZzhHOEVXMmdXUTRTY0Fqc3l6RDNZNUVIbVRhUXJOS2xk?=
 =?utf-8?B?dFlubGkxMFR3VzZ6YmZKZlpHL2xzTFh6R2RIOS9iQzdqenVYeWNaUTdYSUQw?=
 =?utf-8?B?dFdaRnVIQlNBUHoyR09TWEJXWFpKTk5sMjhDa0w0VlhtVVljRlVZNEdwTWFW?=
 =?utf-8?B?NnBla0UyeU1sWEc2SDY4UTk5SUgyY0NLRitYcm1TU09CbStWbzRVa01Vb3c4?=
 =?utf-8?B?N1VLd0Y3aDlubzRzZGQxNE5ELzAyaU5VaURQR2NzVk1WdU83bmVoTFh1TXR2?=
 =?utf-8?B?Nm15c1hmcU5kWnZjK1FjWU1jK2dicFhCR3lBS2RkbWNKbVlIU3BiMHZpMGh3?=
 =?utf-8?B?UjlyYmMydHhVMlo5Ynd0c1FTM0F6ZER1amFLSDhsNzZLRHJnOGUwVzQxeUd6?=
 =?utf-8?B?VGtrbWszdHBPNkk5anFFMWd1dlBNbGlqejVqeTJYNWRoa3BLNncydkhMeVZR?=
 =?utf-8?B?K3kzbTB0VENub01tMUlaTkxHaXVTWGVmcDJCT2gvVWduRjZFWUNDY2lXQXZF?=
 =?utf-8?B?UnZ2bm9FNDRmNStwM3NDU2Y4ZHArR3VKUUZ6M29NVWFKRWhMR2Zjaml3NlFs?=
 =?utf-8?B?VFlpU0dwWU90RFEzTFR0YlZ3ajRxaGUrMEVmZkpEZDFsVjVUSHpMTjN2T0cv?=
 =?utf-8?B?K2FMNk5aNjZlNnRJR0wrSlpOb0NwVHhIQUhka2NLN3pwSytwSlFVUUpCeXhH?=
 =?utf-8?B?RHpjdWFMV3BCK2NnSk02dSs2N1ZUZng3YkduYnVwakttR1hMVDErOVZFK2xP?=
 =?utf-8?B?dGNDblVPZEhxTGxhbXBkM0xOczVNV3ZiUEtmZUZ6L1Y1a3hBSy9GREVUMjV0?=
 =?utf-8?B?aEVqd2hwL0tpTVNLZnJJMWJnYi9JRlBEbXFCKzlTNHBGK29uQUxud1k2YWVy?=
 =?utf-8?B?VFFDMVNRQm1jOE1NcFFqcU1yRkNtM2RFRkVyY3M1OHRKU3FoWHlJNXo3Mk5q?=
 =?utf-8?B?UVNJS0tBU0NEMGNrcGUwbnBwOWMxLzV4UDc0c0NiQUwra0tLQUMrUUgxZHdp?=
 =?utf-8?B?alMzbk1WS2IxVFVPMS8reTlqN0JlZHNzenVocnRkOHFjMThCcjB0VFlGaTd1?=
 =?utf-8?B?d3J5VnNpV3llVStRdlRMWklLeXRaRW4vak5JMlY3dEtQUDhDUFRtbk9rcWd3?=
 =?utf-8?B?YVNwRmNwQ1Fjb1BrV3RGSkcyS2ZVbkpzeS81TzRtUFFiNFVuWTg4Z1NiRW5R?=
 =?utf-8?B?eG5qK3RlZGptaUZWWThJcnVXblZFVTVveXU4N3FGVkxITmRIRGZNbGlxQmhC?=
 =?utf-8?B?TUZTMDIzNjRtV1UzNDN4T2o2QTRUbS84L3F1amtPNnZoLzFNRktxVTZwZ1Y3?=
 =?utf-8?B?bnhzL3pEQ2ZMbWQ2NzF5OGdjTGVoOFdtQ0EycUFmL2FWUFUrcllwcVJVRDdE?=
 =?utf-8?B?NlNOYUN5TVI3SmtzY29BVjczYVVZZ1BmREwwbXQ0RzZUM25KYlVvODh0Vm5K?=
 =?utf-8?B?RlB2ZkV0TVEzeEhnRFN5aU9DcTRZOXZxWUd4VlU0TjhrTWR4RWZOOXpjQ2dn?=
 =?utf-8?B?WWJUd1BFTjQ5TTlJZHlnazV1NTdSWk5QbnBUSDJPZzFoVm4wRy9VZGI5MTJP?=
 =?utf-8?B?OFNJVVZVcWRUalE4Z0Q0NU91ZEVjbnZ6M1BmTk9ndktVS3lVbnFBWjNMcXRh?=
 =?utf-8?B?Zk5tSmd1Q2h5RUVtTGdBczhIS0xMMWQ4ekVhbUhsNGJTQ0Vsb0RKQVh2dVdK?=
 =?utf-8?B?OGhaeFBKY1lxZk5rd1lDSmY3R2lUU2FkOWZLZnEvczFScGgzS2dTeFk3MEtS?=
 =?utf-8?B?R3hSS2EzRGQ5RDhoSzVYb1c3MXM4NEN5OWdiTEc2V2d4SUdiT1FqWTY0TUtk?=
 =?utf-8?B?VTJKRFpTMFNPL3doNEFCYjRyc3RsMXJUeEp3UjR3SXZzVHZJVnFDQmVJbERt?=
 =?utf-8?B?YTdwY0c2bVJaemt5OHUwYjBTN1B1WkJrSUxjYU9NY3Y2TXhKVmM1NEJvYnJy?=
 =?utf-8?Q?qPWuOx38MUqYvp7NhUdPg7V6x?=
X-OriginatorOrg: suse.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 50ad0da1-fbd8-41d5-b114-08dbd5640624
X-MS-Exchange-CrossTenant-AuthSource: AS8PR04MB9510.eurprd04.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 25 Oct 2023 14:09:38.2972
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: f7a17af6-1c5c-4a36-aa8b-f5be247aa4ba
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: tNShgXhRX10eLWQ6hRNEuW8icPoVF3GrHCREDSVpjhUINOs76Us1H4uqINBORhD2ALAKPoflwhL1pL4AHvdVNQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: GV1PR04MB9101
X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,
	SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no
	version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on howler.vger.email
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (howler.vger.email [0.0.0.0]); Wed, 25 Oct 2023 07:11:00 -0700 (PDT)

Hi Hao,

On Wed, Oct 25, 2023 at 02:31:02PM +0200, Hao Sun wrote:
> On Tue, Oct 24, 2023 at 2:40 PM Hao Sun <sunhao.th@gmail.com> wrote:
> >
> > Hi,
> >
> > The following program can trigger a shift-out-of-bounds in
> > tnum_rshift(), called by scalar32_min_max_rsh():
> >
> > 0: (bc) w0.
= w1
> > 1: (bf) r2 = r0
> > 2: (18) r3 = 0xd
> > 4: (bc) w4 = w0
> > 5: (bf) r5 = r0
> > 6: (bf) r7 = r3
> > 7: (bf) r8 = r4
> > 8: (2f) r8 *= r5
> > 9: (cf) r5 s>>= r5
> > 10: (a6) if w8 < 0xfffffffb goto pc+10
> > 11: (1f) r7 -= r5
> > 12: (71) r6 = *(u8 *)(r1 +17)
> > 13: (5f) r3 &= r8
> > 14: (74) w2 >>= 30
> > 15: (1f) r7 -= r5
> > 16: (5d) if r8 != r6 goto pc+4
> > 17: (c7) r8 s>>= 5
> > 18: (cf) r0 s>>= r0
> > 19: (7f) r0 >>= r0
> > 20: (7c) w5 >>= w8         # shift-out-bounds here
> > 21: exit
> >
> 
> Here are the c macros for the above program in case anyone needs this:
> 
>         // 0: (bc) w0 = w1
>         BPF_MOV32_REG(BPF_REG_0, BPF_REG_1),
>         // 1: (bf) r2 = r0
>         BPF_MOV64_REG(BPF_REG_2, BPF_REG_0),
>         // 2: (18) r3 = 0xd
>         BPF_LD_IMM64(BPF_REG_3, 0xd),
>         // 4: (bc) w4 = w0
>         BPF_MOV32_REG(BPF_REG_4, BPF_REG_0),
>         // 5: (bf) r5 = r0
>         BPF_MOV64_REG(BPF_REG_5, BPF_REG_0),
>         // 6: (bf) r7 = r3
>         BPF_MOV64_REG(BPF_REG_7, BPF_REG_3),
>         // 7: (bf) r8 = r4
>         BPF_MOV64_REG(BPF_REG_8, BPF_REG_4),
>         // 8: (2f) r8 *= r5
>         BPF_ALU64_REG(BPF_MUL, BPF_REG_8, BPF_REG_5),
>         // 9: (cf) r5 s>>= 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 -= r5
>         BPF_ALU64_REG(BPF_SUB, BPF_REG_7, BPF_REG_5),
>         // 12: (71) r6 = *(u8 *)(r1 +17)
>         BPF_LDX_MEM(BPF_B, BPF_REG_6, BPF_REG_1, 17),
>         // 13: (5f) r3 &= r8
>         BPF_ALU64_REG(BPF_AND, BPF_REG_3, BPF_REG_8),
>         // 14: (74) w2 >>= 30
>         BPF_ALU32_IMM(BPF_RSH, BPF_REG_2, 30),
>         // 15: (1f) r7 -= r5
>         BPF_ALU64_REG(BPF_SUB, BPF_REG_7, BPF_REG_5),
>         // 16: (5d) if r8 != r6 goto pc+4
>         BPF_JMP_REG(BPF_JNE, BPF_REG_8, BPF_REG_6, 4),
>         // 17: (c7) r8 s>>= 5
>         BPF_ALU64_IMM(BPF_ARSH, BPF_REG_8, 5),
>         // 18: (cf) r0 s>>= r0
>         BPF_ALU64_REG(BPF_ARSH, BPF_REG_0, BPF_REG_0),
>         // 19: (7f) r0 >>= r0
>         BPF_ALU64_REG(BPF_RSH, BPF_REG_0, BPF_REG_0),
>         // 20: (7c) w5 >>= w8
>         BPF_ALU32_REG(BPF_RSH, BPF_REG_5, BPF_REG_8),
>         BPF_EXIT_INSN()
> 
> > After load:
> > ================================================================================
> > 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>
> >
> > If remove insn #20, the verifier gives:
> >  -------- Verifier Log --------
> >  func#0 @0
> >  0: R1=ctx(off=0,imm=0) R10=fp0
> >  0: (bc) w0 = w1                       ;
> > R0_w=scalar(smin=0,smax=umax=4294967295,var_off=(0x0; 0xffffffff))
> > R1=ctx(off=0,
> >  imm=0)
> >  1: (bf) r2 = r0                       ;
> > R0_w=scalar(id=1,smin=0,smax=umax=4294967295,var_off=(0x0;
> > 0xffffffff))
> >  R2_w=scalar(id=1,smin=0,smax=umax=4294967295,var_off=(0x0; 0xffffffff))
> >  2: (18) r3 = 0xd                      ; R3_w=13
> >  4: (bc) w4 = w0                       ;
> > R0_w=scalar(id=1,smin=0,smax=umax=4294967295,var_off=(0x0;
> > 0xffffffff))
> >  R4_w=scalar(id=1,smin=0,smax=umax=4294967295,var_off=(0x0; 0xffffffff))
> >  5: (bf) r5 = r0                       ;
> > R0_w=scalar(id=1,smin=0,smax=umax=4294967295,var_off=(0x0;
> > 0xffffffff))
> >  R5_w=scalar(id=1,smin=0,smax=umax=4294967295,var_off=(0x0; 0xffffffff))
> >  6: (bf) r7 = r3                       ; R3_w=13 R7_w=13
> >  7: (bf) r8 = r4                       ;
> > R4_w=scalar(id=1,smin=0,smax=umax=4294967295,var_off=(0x0;
> > 0xffffffff))
> >  R8_w=scalar(id=1,smin=0,smax=umax=4294967295,var_off=(0x0; 0xffffffff))
> >  8: (2f) r8 *= r5                      ;
> > R5_w=scalar(id=1,smin=0,smax=umax=4294967295,var_off=(0x0;
> > 0xffffffff))
> >  R8_w=scalar()
> >  9: (cf) r5 s>>= r5                    ; R5_w=scalar()
> >  10: (a6) if w8 < 0xfffffffb goto pc+9         ;
> > R8_w=scalar(smin=-9223372032559808520,umin=4294967288,smin32=-5,smax32=-1,
> >  umin32=4294967291,var_off=(0xfffffff8; 0xffffffff00000007))
> >  11: (1f) r7 -= r5                     ; R5_w=scalar() R7_w=scalar()
> >  12: (71) r6 = *(u8 *)(r1 +17)         ; R1=ctx(off=0,imm=0)
> > R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,
> >  var_off=(0x0; 0xff))
> >  13: (5f) r3 &= r8                     ;
> > R3_w=scalar(smin=umin=smin32=umin32=8,smax=umax=smax32=umax32=13,var_off=(0x8;
> >  0x5)) R8_w=scalar(smin=-9223372032559808520,umin=4294967288,smin32=-5,smax32=-1,umin32=4294967291,var_off=(0xffff)
> >  14: (74) w2 >>= 30                    ;
> > R2_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=3,var_off=(0x0;
> > 0x3))
> >  15: (1f) r7 -= r5                     ; R5_w=scalar() R7_w=scalar()
> >  16: (5d) if r8 != r6 goto pc+3        ;
> > R6_w=scalar(smin=umin=umin32=4294967288,smax=umax=umax32=255,smin32=-8,smax32=-1,
> >  var_off=(0xfffffff8; 0x7))
> > R8_w=scalar(smin=umin=4294967288,smax=umax=255,smin32=-5,smax32=-1,umin32=4294967291)

Seems like the root cause is a bug with range tracking, before instruction
16, R8_w was

  R8_w=scalar(smin=-9223372032559808520,umin=4294967288,smin32=-5,smax32=-1,umin32=4294967291,var_off=(0xffff)

But after instruction 16 it becomes

  R8_w=scalar(smin=umin=4294967288,smax=umax=255,smin32=-5,smax32=-1,umin32=4294967291)

Where smin_value > smax_value, and umin_value > umax_value (among other
things). This should be the main problem.

The verifier operates on the assumption that smin_value <= smax_value and
umin_value <= umax_value, and if that assumption is not upheld then all kind
of things can go wrong.

Maybe Andrii may already has this worked out in the range-vs-range that he
has mentioned[1] he'll be sending soon.

1: https://lore.kernel.org/bpf/CAEf4BzbJ3hZCSt4nLCZCV4cxV60+kddiSMsy7-9ou_RaQV7B8A@mail.gmail.com/

> >  17: (c7) r8 s>>= 5                    ; R8_w=134217727
> >  18: (cf) r0 s>>= r0                   ; R0_w=scalar()
> >  19: (7f) r0 >>= r0                    ; R0=scalar()
> >  20: (95) exit
> >
> >  from 16 to 20: safe
> >
> >  from 10 to 20: safe
> >  processed 22 insns (limit 1000000) max_states_per_insn 0 total_states
> > 1 peak_states 1 mark_read 1
> > -------- End of Verifier Log --------
> >
> > In adjust_scalar_min_max_vals(), src_reg.umax_value is 7, thus pass
> > the check here:
> >          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;
> >          }
> >
> > However in scalar32_min_max_rsh(), both src_reg->u32_min_value and
> > src_reg->u32_max_value is 134217727, causing tnum_rsh() shit by 255.
> >
> > Should we check if(src_reg->u32_max_value < insn_bitness) before calling
> > scalar32_min_max_rsh(), rather than only checking umax_val? Or, is it
> > because issues somewhere else, incorrectly setting u32_min_value to
> > 34217727

Checking umax_val alone is be enough and we don't need to add a check for
u32_max_value, because (when we have correct range tracking) u32_max_value
should always be smaller than u32_value. So the fix needed here is to have
correct range tracking.

> > Best
> > Hao Sun