* bpf: shift-out-of-bounds in tnum_rshift()
@ 2023-10-24 12:40 Hao Sun
2023-10-25 12:31 ` Hao Sun
2023-10-25 17:34 ` Eduard Zingerman
0 siblings, 2 replies; 13+ messages in thread
From: Hao Sun @ 2023-10-24 12:40 UTC (permalink / raw)
To: Alexei Starovoitov, Daniel Borkmann, John Fastabend,
Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song,
KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa
Cc: bpf, Linux Kernel Mailing List
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
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)
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
Best
Hao Sun
^ permalink raw reply [flat|nested] 13+ messages in thread* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-24 12:40 bpf: shift-out-of-bounds in tnum_rshift() Hao Sun @ 2023-10-25 12:31 ` Hao Sun 2023-10-25 13:20 ` Hao Sun 2023-10-25 14:09 ` Shung-Hsi Yu 2023-10-25 17:34 ` Eduard Zingerman 1 sibling, 2 replies; 13+ messages in thread From: Hao Sun @ 2023-10-25 12:31 UTC (permalink / raw) To: Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa Cc: bpf, Linux Kernel Mailing List 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) > 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 > > Best > Hao Sun ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-25 12:31 ` Hao Sun @ 2023-10-25 13:20 ` Hao Sun 2023-10-25 14:09 ` Shung-Hsi Yu 1 sibling, 0 replies; 13+ messages in thread From: Hao Sun @ 2023-10-25 13:20 UTC (permalink / raw) To: Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa Cc: bpf, Linux Kernel Mailing List On Wed, Oct 25, 2023 at 2:31 PM Hao Sun <sunhao.th@gmail.com> 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> > > 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 ================================================================================ 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> ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-25 12:31 ` Hao Sun 2023-10-25 13:20 ` Hao Sun @ 2023-10-25 14:09 ` Shung-Hsi Yu 2023-10-25 14:18 ` Shung-Hsi Yu 2023-10-25 21:59 ` Eduard Zingerman 1 sibling, 2 replies; 13+ messages in thread From: Shung-Hsi Yu @ 2023-10-25 14:09 UTC (permalink / raw) To: Hao Sun Cc: Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, Linux Kernel Mailing List 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 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-25 14:09 ` Shung-Hsi Yu @ 2023-10-25 14:18 ` Shung-Hsi Yu 2023-10-25 21:59 ` Eduard Zingerman 1 sibling, 0 replies; 13+ messages in thread From: Shung-Hsi Yu @ 2023-10-25 14:18 UTC (permalink / raw) To: Hao Sun Cc: Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, Linux Kernel Mailing List On Wed, Oct 25, 2023 at 10:09:27PM +0800, Shung-Hsi Yu wrote: > 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. Since you are running fuzzer on BPF verifier, it may be be helpful to check that the following conditions are always met: - umin <= umax - smin <= smax - u32_min <= u32_max - s32_min <= s32_max - u32_max <= umax - smin <= s32_min - s32_max <= smax If any of these condition is not upheld then it should be a range tracking bug. > > > Best > > > Hao Sun ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-25 14:09 ` Shung-Hsi Yu 2023-10-25 14:18 ` Shung-Hsi Yu @ 2023-10-25 21:59 ` Eduard Zingerman 2023-10-26 6:44 ` Shung-Hsi Yu 1 sibling, 1 reply; 13+ messages in thread From: Eduard Zingerman @ 2023-10-25 21:59 UTC (permalink / raw) To: Shung-Hsi Yu, Hao Sun Cc: Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, Linux Kernel Mailing List On Wed, 2023-10-25 at 22:09 +0800, Shung-Hsi Yu wrote: > 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. Hello, Sorry, I haven't noticed your reply when replying in a sibling thread. I agree with your analysis, I think the culprit here is inability of __reg_combine_min_max() to deal with non-overlapping ranges. Consider example below: SEC("?tp") __success __retval(0) __naked void large_shifts(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \ r8 = r0; \ r6 = r0; \ r6 &= 0x00f; \ r8 &= 0xf00; \ r8 |= 0x0ff; \ if r8 != r6 goto +1; \ w0 >>= w8; /* shift-out-bounds here */ \ exit; \ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } Here the ranges before 'if' are {0,15} for R6 and {255,4095} for R8. And here is the code of __reg_combine_min_max(): ... src_reg->umin_value = dst_reg->umin_value = max(src_reg->umin_value, dst_reg->umin_value); src_reg->umax_value = dst_reg->umax_value = min(src_reg->umax_value, dst_reg->umax_value); ... This code would be executed when 'if' is processed from the following call-chain: - check_cond_jmp_op - reg_combine_min_max - __reg_combine_min_max The src_reg is R6 and dst_reg is R8, the min/max assignments above would produce umin_value > umax_value for any ranges {a,b}, {c,d} where a < b < c < d. Non-overlapping ranges can get to reg_combine_min_max() because check_cond_jmp_op() does predictions only when one of the operands of the comparison is constant. I think the way to fix this bug is to: - teach check_cond_jmp_op() to do predictions when ranges of operands do not overlap; - add assertion to __reg_combine_min_max() to make sure that only operands with overlapping ranges are passed as arguments. wdyt? ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-25 21:59 ` Eduard Zingerman @ 2023-10-26 6:44 ` Shung-Hsi Yu 2023-10-26 21:53 ` Andrii Nakryiko 0 siblings, 1 reply; 13+ messages in thread From: Shung-Hsi Yu @ 2023-10-26 6:44 UTC (permalink / raw) To: Andrii Nakryiko Cc: Eduard Zingerman, Hao Sun, Alexei Starovoitov, Daniel Borkmann, John Fastabend, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, Linux Kernel Mailing List Hi Andrii, The fix needed here to address the "non-overlapping ranges in __reg_combine_min_max()" issue sounds like something you'd already have in the range-vs-range series you mentioned previously. Maybe you've already got a patch for this? On Thu, Oct 26, 2023 at 12:59:19AM +0300, Eduard Zingerman wrote: > On Wed, 2023-10-25 at 22:09 +0800, Shung-Hsi Yu wrote: > > 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. > > Hello, > > Sorry, I haven't noticed your reply when replying in a sibling thread. That's something I struggle with too :) > I agree with your analysis, I think the culprit here is inability of > __reg_combine_min_max() to deal with non-overlapping ranges. > > Consider example below: > > SEC("?tp") > __success __retval(0) > __naked void large_shifts(void) > { > asm volatile (" \ > call %[bpf_get_prandom_u32]; \ > r8 = r0; \ > r6 = r0; \ > r6 &= 0x00f; \ > r8 &= 0xf00; \ > r8 |= 0x0ff; \ > if r8 != r6 goto +1; \ > w0 >>= w8; /* shift-out-bounds here */ \ > exit; \ > " : > : __imm(bpf_get_prandom_u32) > : __clobber_all); > } > > Here the ranges before 'if' are {0,15} for R6 and {255,4095} for R8. > > And here is the code of __reg_combine_min_max(): > > ... > src_reg->umin_value = dst_reg->umin_value = max(src_reg->umin_value, > dst_reg->umin_value); > src_reg->umax_value = dst_reg->umax_value = min(src_reg->umax_value, > dst_reg->umax_value); > ... > > This code would be executed when 'if' is processed from the following call-chain: > - check_cond_jmp_op > - reg_combine_min_max > - __reg_combine_min_max > > The src_reg is R6 and dst_reg is R8, the min/max assignments above > would produce umin_value > umax_value for any ranges {a,b}, {c,d} > where a < b < c < d. > > Non-overlapping ranges can get to reg_combine_min_max() because > check_cond_jmp_op() does predictions only when one of the operands of > the comparison is constant. > > I think the way to fix this bug is to: > - teach check_cond_jmp_op() to do predictions when ranges of operands > do not overlap; > - add assertion to __reg_combine_min_max() to make sure that only > operands with overlapping ranges are passed as arguments. > > wdyt? Agree on both points above. For the assertion in __reg_combine_min_max() I think verbose("BUG...") plus __mark_reg_unknown() on both src_reg and dst_reg should be enough. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-26 6:44 ` Shung-Hsi Yu @ 2023-10-26 21:53 ` Andrii Nakryiko 0 siblings, 0 replies; 13+ messages in thread From: Andrii Nakryiko @ 2023-10-26 21:53 UTC (permalink / raw) To: Shung-Hsi Yu Cc: Andrii Nakryiko, Eduard Zingerman, Hao Sun, Alexei Starovoitov, Daniel Borkmann, John Fastabend, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, Linux Kernel Mailing List On Wed, Oct 25, 2023 at 11:44 PM Shung-Hsi Yu <shung-hsi.yu@suse.com> wrote: > > Hi Andrii, > > The fix needed here to address the "non-overlapping ranges in > __reg_combine_min_max()" issue sounds like something you'd already have in > the range-vs-range series you mentioned previously. Maybe you've already got > a patch for this? > > On Thu, Oct 26, 2023 at 12:59:19AM +0300, Eduard Zingerman wrote: > > On Wed, 2023-10-25 at 22:09 +0800, Shung-Hsi Yu wrote: > > > 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. Yes, I think so. I did add few more conditions to BPF_JEQ/BPF_JNE to prevent situations where we have to "combine" non-overlapping regions. I don't know if my changes fix this specific condition, so having a nice and short repro from Eduard is great. I intend to submit a full series for reg bounds improvements in the next few working days. > > > > > > 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. > > > > Hello, > > > > Sorry, I haven't noticed your reply when replying in a sibling thread. > > That's something I struggle with too :) > > > I agree with your analysis, I think the culprit here is inability of > > __reg_combine_min_max() to deal with non-overlapping ranges. > > > > Consider example below: > > > > SEC("?tp") > > __success __retval(0) > > __naked void large_shifts(void) > > { > > asm volatile (" \ > > call %[bpf_get_prandom_u32]; \ > > r8 = r0; \ > > r6 = r0; \ > > r6 &= 0x00f; \ > > r8 &= 0xf00; \ > > r8 |= 0x0ff; \ > > if r8 != r6 goto +1; \ > > w0 >>= w8; /* shift-out-bounds here */ \ > > exit; \ > > " : > > : __imm(bpf_get_prandom_u32) > > : __clobber_all); > > } > > > > Here the ranges before 'if' are {0,15} for R6 and {255,4095} for R8. > > > > And here is the code of __reg_combine_min_max(): > > > > ... > > src_reg->umin_value = dst_reg->umin_value = max(src_reg->umin_value, > > dst_reg->umin_value); > > src_reg->umax_value = dst_reg->umax_value = min(src_reg->umax_value, > > dst_reg->umax_value); > > ... > > > > This code would be executed when 'if' is processed from the following call-chain: > > - check_cond_jmp_op > > - reg_combine_min_max > > - __reg_combine_min_max > > > > The src_reg is R6 and dst_reg is R8, the min/max assignments above > > would produce umin_value > umax_value for any ranges {a,b}, {c,d} > > where a < b < c < d. > > > > Non-overlapping ranges can get to reg_combine_min_max() because > > check_cond_jmp_op() does predictions only when one of the operands of > > the comparison is constant. > > > > I think the way to fix this bug is to: > > - teach check_cond_jmp_op() to do predictions when ranges of operands > > do not overlap; > > - add assertion to __reg_combine_min_max() to make sure that only > > operands with overlapping ranges are passed as arguments. > > > > wdyt? > > Agree on both points above. For the assertion in __reg_combine_min_max() I > think verbose("BUG...") plus __mark_reg_unknown() on both src_reg and > dst_reg should be enough. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-24 12:40 bpf: shift-out-of-bounds in tnum_rshift() Hao Sun 2023-10-25 12:31 ` Hao Sun @ 2023-10-25 17:34 ` Eduard Zingerman 2023-10-27 17:51 ` Andrii Nakryiko 1 sibling, 1 reply; 13+ messages in thread From: Eduard Zingerman @ 2023-10-25 17:34 UTC (permalink / raw) To: Hao Sun, Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa Cc: bpf, Linux Kernel Mailing List On Tue, 2023-10-24 at 14:40 +0200, Hao Sun 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 is a simplified example: SEC("?tp") __success __retval(0) __naked void large_shifts(void) { asm volatile (" \ call %[bpf_get_prandom_u32]; \n\ r8 = r0; \n\ r6 = r0; \n\ r6 &= 0xf; \n\ if w8 < 0xffffffff goto +2; \n\ if r8 != r6 goto +1; \n\ w0 >>= w8; /* shift-out-bounds here */ \n\ exit; \n\ " : : __imm(bpf_get_prandom_u32) : __clobber_all); } The issue is caused by an invalid range assigned to R8 after R8 != R6 check, here is GDB log: (gdb) bt #0 scalar32_min_max_rsh ... at kernel/bpf/verifier.c:13368 #1 0xffffffff81295236 in adjust_scalar_min_max_vals ... at kernel/bpf/verifier.c:13592 #2 adjust_reg_min_max_vals .... at kernel/bpf/verifier.c:13706 #3 0xffffffff8128701f in check_alu_op ... at kernel/bpf/verifier.c:13938 #4 do_check ... at kernel/bpf/verifier.c:17327 (gdb) p *src_reg $2 = { type = SCALAR_VALUE, ... smin_value = 4294967295, smax_value = 15, umin_value = 4294967295, umax_value = 15, s32_min_value = -1, s32_max_value = -1, u32_min_value = 4294967295, u32_max_value = 4294967295, ... } The invalid range is assigned within reg_combine_min_max() function in BPF_JNE branch. The following diff removes the error: diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 857d76694517..3d140bf85282 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -14485,7 +14485,7 @@ static void reg_combine_min_max(struct bpf_reg_state *true_src, __reg_combine_min_max(true_src, true_dst); break; case BPF_JNE: - __reg_combine_min_max(false_src, false_dst); + //__reg_combine_min_max(false_src, false_dst); break; } } I do not understand what BPF_JNE branch logically means in reg_combine_min_max(), does anyone has any insight? > 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) > 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 > > Best > Hao Sun > ^ permalink raw reply related [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-25 17:34 ` Eduard Zingerman @ 2023-10-27 17:51 ` Andrii Nakryiko 2023-11-01 9:52 ` Hao Sun 0 siblings, 1 reply; 13+ messages in thread From: Andrii Nakryiko @ 2023-10-27 17:51 UTC (permalink / raw) To: Eduard Zingerman Cc: Hao Sun, Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, Linux Kernel Mailing List On Wed, Oct 25, 2023 at 10:34 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Tue, 2023-10-24 at 14:40 +0200, Hao Sun 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 is a simplified example: > > SEC("?tp") > __success __retval(0) > __naked void large_shifts(void) > { > asm volatile (" \ > call %[bpf_get_prandom_u32]; \n\ > r8 = r0; \n\ > r6 = r0; \n\ > r6 &= 0xf; \n\ > if w8 < 0xffffffff goto +2; \n\ > if r8 != r6 goto +1; \n\ > w0 >>= w8; /* shift-out-bounds here */ \n\ > exit; \n\ > " : > : __imm(bpf_get_prandom_u32) > : __clobber_all); > } > With my changes the verifier does correctly derive that r8 != r6 will always happen, and thus skips w0 >>= w8. But the test itself with __retval(0) is not a valid test, so it would be good to construct something that will correctly return 0 at runtime (or use some other check). So I won't put this test into my patch set and will live it as a follow up for someone. But here's the log for anyone curious: VERIFIER LOG: ============= func#0 @0 0: R1=ctx(off=0,imm=0) R10=fp0 ; asm volatile (" \ 0: (85) call bpf_get_prandom_u32#7 ; R0_w=scalar() 1: (bf) r8 = r0 ; R0_w=scalar(id=1) R8_w=scalar(id=1) 2: (bf) r6 = r0 ; R0_w=scalar(id=1) R6_w=scalar(id=1) 3: (57) r6 &= 15 ; R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; 0xf)) 4: (a6) if w8 < 0xffffffff goto pc+2 ; R8_w=scalar(id=1,smin=-9223372032559808513,umin=umin32=4294967295,smin32=-1,smax32=-1,var_off=(0xffffffff; 0xffffffff00000000)) 5: (5d) if r8 != r6 goto pc+1 mark_precise: frame0: last_idx 5 first_idx 0 subseq_idx -1 mark_precise: frame0: regs=r0,r8 stack= before 4: (a6) if w8 < 0xffffffff goto pc+2 mark_precise: frame0: regs=r0,r8 stack= before 3: (57) r6 &= 15 mark_precise: frame0: regs=r0,r8 stack= before 2: (bf) r6 = r0 mark_precise: frame0: regs=r0,r8 stack= before 1: (bf) r8 = r0 mark_precise: frame0: regs=r0 stack= before 0: (85) call bpf_get_prandom_u32#7 mark_precise: frame0: last_idx 5 first_idx 0 subseq_idx -1 mark_precise: frame0: regs=r6 stack= before 4: (a6) if w8 < 0xffffffff goto pc+2 mark_precise: frame0: regs=r6 stack= before 3: (57) r6 &= 15 mark_precise: frame0: regs=r6 stack= before 2: (bf) r6 = r0 mark_precise: frame0: regs=r0 stack= before 1: (bf) r8 = r0 mark_precise: frame0: regs=r0 stack= before 0: (85) call bpf_get_prandom_u32#7 5: R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; 0xf)) R8_w=scalar(id=1,smin=-9223372032559808513,umin=umin32=4294967295,smin32=-1,smax32=-1,var_off=(0xffffffff; 0xffffffff00000000)) 7: (95) exit from 4 to 7: R0=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) R6=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; 0xf)) R8=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) R10=fp0 7: R0=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) R6=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; 0xf)) R8=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) R10=fp0 7: (95) exit processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1 ============= at insn #4, simulating a FALSE condition, verifier knows that r6 is [0, 15], while w8 is exactly 0xffffffff, so at insn #5 it can tell that 0xffffffff can never be equal to a value in [0, 15] range, and thus skips the shift instruction. > The issue is caused by an invalid range assigned to R8 after R8 != R6 > check, here is GDB log: > > (gdb) bt > #0 scalar32_min_max_rsh ... at kernel/bpf/verifier.c:13368 > #1 0xffffffff81295236 in adjust_scalar_min_max_vals ... at kernel/bpf/verifier.c:13592 > #2 adjust_reg_min_max_vals .... at kernel/bpf/verifier.c:13706 > #3 0xffffffff8128701f in check_alu_op ... at kernel/bpf/verifier.c:13938 > #4 do_check ... at kernel/bpf/verifier.c:17327 > (gdb) p *src_reg > $2 = { > type = SCALAR_VALUE, > ... > smin_value = 4294967295, > smax_value = 15, > umin_value = 4294967295, > umax_value = 15, > s32_min_value = -1, > s32_max_value = -1, > u32_min_value = 4294967295, > u32_max_value = 4294967295, > ... > } > > The invalid range is assigned within reg_combine_min_max() function in > BPF_JNE branch. The following diff removes the error: > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 857d76694517..3d140bf85282 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -14485,7 +14485,7 @@ static void reg_combine_min_max(struct bpf_reg_state *true_src, > __reg_combine_min_max(true_src, true_dst); > break; > case BPF_JNE: > - __reg_combine_min_max(false_src, false_dst); > + //__reg_combine_min_max(false_src, false_dst); > break; > } > } > > I do not understand what BPF_JNE branch logically means in > reg_combine_min_max(), does anyone has any insight? Not equal check? When you have either `if r1 == r2 goto ` or `if r1 != r2`, verifier simulates both TRUE and FALSE conditions, so basically both BPF_JEQ and BPF_JNE, depending on the branch. > > > 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) > > 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 > > > > Best > > Hao Sun > > > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-10-27 17:51 ` Andrii Nakryiko @ 2023-11-01 9:52 ` Hao Sun 2023-11-01 22:45 ` Andrii Nakryiko 0 siblings, 1 reply; 13+ messages in thread From: Hao Sun @ 2023-11-01 9:52 UTC (permalink / raw) To: Andrii Nakryiko Cc: Eduard Zingerman, Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, Linux Kernel Mailing List On Fri, Oct 27, 2023 at 7:51 PM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Wed, Oct 25, 2023 at 10:34 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > On Tue, 2023-10-24 at 14:40 +0200, Hao Sun 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 is a simplified example: > > > > SEC("?tp") > > __success __retval(0) > > __naked void large_shifts(void) > > { > > asm volatile (" \ > > call %[bpf_get_prandom_u32]; \n\ > > r8 = r0; \n\ > > r6 = r0; \n\ > > r6 &= 0xf; \n\ > > if w8 < 0xffffffff goto +2; \n\ > > if r8 != r6 goto +1; \n\ > > w0 >>= w8; /* shift-out-bounds here */ \n\ > > exit; \n\ > > " : > > : __imm(bpf_get_prandom_u32) > > : __clobber_all); > > } > > > > With my changes the verifier does correctly derive that r8 != r6 will > always happen, and thus skips w0 >>= w8. But the test itself with A similar issue can be triggered after your patch for JNE/JEQ. For the following case, the verifier would shift out of bound: // 0: r0 = -2 BPF_MOV64_IMM(BPF_REG_0, -2), // 1: r0 /= 1 BPF_ALU64_IMM(BPF_DIV, BPF_REG_0, 1), // 2: r8 = r0 BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), // 3: if w8 != 0xfffffffe goto+4 BPF_JMP32_IMM(BPF_JNE, BPF_REG_8, 0xfffffffe, 4), // 4: if r8 s> 0xd goto+3 BPF_JMP_IMM(BPF_JSGT, BPF_REG_8, 0xd, 3), // 5: r4 = 0x2 BPF_MOV64_IMM(BPF_REG_4, 0x2), // 6: if r8 s<= r4 goto+1 BPF_JMP_REG(BPF_JSLE, BPF_REG_8, BPF_REG_4, 1), // 7: w8 s>>= w0 # shift out of bound here BPF_ALU32_REG(BPF_ARSH, BPF_REG_8, BPF_REG_0), // 8: exit BPF_EXIT_INSN(), -------- Verifier Log -------- func#0 @0 0: R1=ctx(off=0,imm=0) R10=fp0 0: (b7) r0 = -2 ; R0_w=-2 1: (37) r0 /= 1 ; R0_w=scalar() 2: (bf) r8 = r0 ; R0_w=scalar(id=1) R8_w=scalar(id=1) 3: (56) if w8 != 0xfffffffe goto pc+4 ; R8_w=scalar(id=1,smin=-9223372032559808514,smax=9223372036854775806,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2, umax32=4294967294,var_off=(0xfffffffe; 0xffffffff00000000)) 4: (65) if r8 s> 0xd goto pc+3 ; R8_w=scalar(id=1,smin=-9223372032559808514,smax=13,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2,umax32=4294967294, var_off=(0xfffffffe; 0xffffffff00000000)) 5: (b7) r4 = 2 ; R4_w=2 6: (dd) if r8 s<= r4 goto pc+1 ; R4_w=2 R8_w=4294967294 7: (cc) w8 s>>= w0 ; R0=4294967294 R8=4294967295 8: (95) exit Here, after #6, reg range is incorrect, seems to be an issue in JSLE case in is_branch_taken(). Is this issue fixed in your patch series? > __retval(0) is not a valid test, so it would be good to construct > something that will correctly return 0 at runtime (or use some other > check). So I won't put this test into my patch set and will live it as > a follow up for someone. But here's the log for anyone curious: > > VERIFIER LOG: > ============= > func#0 @0 > 0: R1=ctx(off=0,imm=0) R10=fp0 > ; asm volatile (" \ > 0: (85) call bpf_get_prandom_u32#7 ; R0_w=scalar() > 1: (bf) r8 = r0 ; R0_w=scalar(id=1) R8_w=scalar(id=1) > 2: (bf) r6 = r0 ; R0_w=scalar(id=1) R6_w=scalar(id=1) > 3: (57) r6 &= 15 ; > R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; > 0xf)) > 4: (a6) if w8 < 0xffffffff goto pc+2 ; > R8_w=scalar(id=1,smin=-9223372032559808513,umin=umin32=4294967295,smin32=-1,smax32=-1,var_off=(0xffffffff; > 0xffffffff00000000)) > 5: (5d) if r8 != r6 goto pc+1 > mark_precise: frame0: last_idx 5 first_idx 0 subseq_idx -1 > mark_precise: frame0: regs=r0,r8 stack= before 4: (a6) if w8 < > 0xffffffff goto pc+2 > mark_precise: frame0: regs=r0,r8 stack= before 3: (57) r6 &= 15 > mark_precise: frame0: regs=r0,r8 stack= before 2: (bf) r6 = r0 > mark_precise: frame0: regs=r0,r8 stack= before 1: (bf) r8 = r0 > mark_precise: frame0: regs=r0 stack= before 0: (85) call bpf_get_prandom_u32#7 > mark_precise: frame0: last_idx 5 first_idx 0 subseq_idx -1 > mark_precise: frame0: regs=r6 stack= before 4: (a6) if w8 < 0xffffffff goto pc+2 > mark_precise: frame0: regs=r6 stack= before 3: (57) r6 &= 15 > mark_precise: frame0: regs=r6 stack= before 2: (bf) r6 = r0 > mark_precise: frame0: regs=r0 stack= before 1: (bf) r8 = r0 > mark_precise: frame0: regs=r0 stack= before 0: (85) call bpf_get_prandom_u32#7 > 5: R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; > 0xf)) R8_w=scalar(id=1,smin=-9223372032559808513,umin=umin32=4294967295,smin32=-1,smax32=-1,var_off=(0xffffffff; > 0xffffffff00000000)) > 7: (95) exit > > from 4 to 7: R0=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) > R6=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; 0xf)) > R8=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) > R10=fp0 > 7: R0=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) > R6=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; 0xf)) > R8=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) > R10=fp0 > 7: (95) exit > processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1 > peak_states 1 mark_read 1 > ============= > > at insn #4, simulating a FALSE condition, verifier knows that r6 is > [0, 15], while w8 is exactly 0xffffffff, so at insn #5 it can tell > that 0xffffffff can never be equal to a value in [0, 15] range, and > thus skips the shift instruction. > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-11-01 9:52 ` Hao Sun @ 2023-11-01 22:45 ` Andrii Nakryiko 2023-11-02 14:17 ` Hao Sun 0 siblings, 1 reply; 13+ messages in thread From: Andrii Nakryiko @ 2023-11-01 22:45 UTC (permalink / raw) To: Hao Sun Cc: Eduard Zingerman, Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, Linux Kernel Mailing List On Wed, Nov 1, 2023 at 2:53 AM Hao Sun <sunhao.th@gmail.com> wrote: > > On Fri, Oct 27, 2023 at 7:51 PM Andrii Nakryiko > <andrii.nakryiko@gmail.com> wrote: > > > > On Wed, Oct 25, 2023 at 10:34 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > On Tue, 2023-10-24 at 14:40 +0200, Hao Sun 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 is a simplified example: > > > > > > SEC("?tp") > > > __success __retval(0) > > > __naked void large_shifts(void) > > > { > > > asm volatile (" \ > > > call %[bpf_get_prandom_u32]; \n\ > > > r8 = r0; \n\ > > > r6 = r0; \n\ > > > r6 &= 0xf; \n\ > > > if w8 < 0xffffffff goto +2; \n\ > > > if r8 != r6 goto +1; \n\ > > > w0 >>= w8; /* shift-out-bounds here */ \n\ > > > exit; \n\ > > > " : > > > : __imm(bpf_get_prandom_u32) > > > : __clobber_all); > > > } > > > > > > > With my changes the verifier does correctly derive that r8 != r6 will > > always happen, and thus skips w0 >>= w8. But the test itself with > > A similar issue can be triggered after your patch for JNE/JEQ. > > For the following case, the verifier would shift out of bound: > // 0: r0 = -2 > BPF_MOV64_IMM(BPF_REG_0, -2), > // 1: r0 /= 1 > BPF_ALU64_IMM(BPF_DIV, BPF_REG_0, 1), > // 2: r8 = r0 > BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), > // 3: if w8 != 0xfffffffe goto+4 > BPF_JMP32_IMM(BPF_JNE, BPF_REG_8, 0xfffffffe, 4), > // 4: if r8 s> 0xd goto+3 > BPF_JMP_IMM(BPF_JSGT, BPF_REG_8, 0xd, 3), > // 5: r4 = 0x2 > BPF_MOV64_IMM(BPF_REG_4, 0x2), > // 6: if r8 s<= r4 goto+1 > BPF_JMP_REG(BPF_JSLE, BPF_REG_8, BPF_REG_4, 1), > // 7: w8 s>>= w0 # shift out of bound here > BPF_ALU32_REG(BPF_ARSH, BPF_REG_8, BPF_REG_0), > // 8: exit > BPF_EXIT_INSN(), > > -------- Verifier Log -------- > func#0 @0 > 0: R1=ctx(off=0,imm=0) R10=fp0 > 0: (b7) r0 = -2 ; R0_w=-2 > 1: (37) r0 /= 1 ; R0_w=scalar() > 2: (bf) r8 = r0 ; R0_w=scalar(id=1) R8_w=scalar(id=1) > 3: (56) if w8 != 0xfffffffe goto pc+4 ; > R8_w=scalar(id=1,smin=-9223372032559808514,smax=9223372036854775806,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2, > umax32=4294967294,var_off=(0xfffffffe; 0xffffffff00000000)) > 4: (65) if r8 s> 0xd goto pc+3 ; > R8_w=scalar(id=1,smin=-9223372032559808514,smax=13,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2,umax32=4294967294, > var_off=(0xfffffffe; 0xffffffff00000000)) > 5: (b7) r4 = 2 ; R4_w=2 > 6: (dd) if r8 s<= r4 goto pc+1 ; R4_w=2 R8_w=4294967294 > 7: (cc) w8 s>>= w0 ; R0=4294967294 R8=4294967295 > 8: (95) exit > > Here, after #6, reg range is incorrect, seems to be an issue in JSLE case > in is_branch_taken(). Is this issue fixed in your patch series? I don't know, but you can easily check by applying my patches on top of bpf-next and then trying your change. > > > __retval(0) is not a valid test, so it would be good to construct > > something that will correctly return 0 at runtime (or use some other > > check). So I won't put this test into my patch set and will live it as > > a follow up for someone. But here's the log for anyone curious: > > > > VERIFIER LOG: > > ============= > > func#0 @0 > > 0: R1=ctx(off=0,imm=0) R10=fp0 > > ; asm volatile (" \ > > 0: (85) call bpf_get_prandom_u32#7 ; R0_w=scalar() > > 1: (bf) r8 = r0 ; R0_w=scalar(id=1) R8_w=scalar(id=1) > > 2: (bf) r6 = r0 ; R0_w=scalar(id=1) R6_w=scalar(id=1) > > 3: (57) r6 &= 15 ; > > R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; > > 0xf)) > > 4: (a6) if w8 < 0xffffffff goto pc+2 ; > > R8_w=scalar(id=1,smin=-9223372032559808513,umin=umin32=4294967295,smin32=-1,smax32=-1,var_off=(0xffffffff; > > 0xffffffff00000000)) > > 5: (5d) if r8 != r6 goto pc+1 > > mark_precise: frame0: last_idx 5 first_idx 0 subseq_idx -1 > > mark_precise: frame0: regs=r0,r8 stack= before 4: (a6) if w8 < > > 0xffffffff goto pc+2 > > mark_precise: frame0: regs=r0,r8 stack= before 3: (57) r6 &= 15 > > mark_precise: frame0: regs=r0,r8 stack= before 2: (bf) r6 = r0 > > mark_precise: frame0: regs=r0,r8 stack= before 1: (bf) r8 = r0 > > mark_precise: frame0: regs=r0 stack= before 0: (85) call bpf_get_prandom_u32#7 > > mark_precise: frame0: last_idx 5 first_idx 0 subseq_idx -1 > > mark_precise: frame0: regs=r6 stack= before 4: (a6) if w8 < 0xffffffff goto pc+2 > > mark_precise: frame0: regs=r6 stack= before 3: (57) r6 &= 15 > > mark_precise: frame0: regs=r6 stack= before 2: (bf) r6 = r0 > > mark_precise: frame0: regs=r0 stack= before 1: (bf) r8 = r0 > > mark_precise: frame0: regs=r0 stack= before 0: (85) call bpf_get_prandom_u32#7 > > 5: R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; > > 0xf)) R8_w=scalar(id=1,smin=-9223372032559808513,umin=umin32=4294967295,smin32=-1,smax32=-1,var_off=(0xffffffff; > > 0xffffffff00000000)) > > 7: (95) exit > > > > from 4 to 7: R0=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) > > R6=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; 0xf)) > > R8=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) > > R10=fp0 > > 7: R0=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) > > R6=scalar(smin=smin32=0,smax=umax=smax32=umax32=15,var_off=(0x0; 0xf)) > > R8=scalar(id=1,smax=9223372036854775806,umax=18446744073709551614,umax32=4294967294) > > R10=fp0 > > 7: (95) exit > > processed 8 insns (limit 1000000) max_states_per_insn 0 total_states 1 > > peak_states 1 mark_read 1 > > ============= > > > > at insn #4, simulating a FALSE condition, verifier knows that r6 is > > [0, 15], while w8 is exactly 0xffffffff, so at insn #5 it can tell > > that 0xffffffff can never be equal to a value in [0, 15] range, and > > thus skips the shift instruction. > > ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: bpf: shift-out-of-bounds in tnum_rshift() 2023-11-01 22:45 ` Andrii Nakryiko @ 2023-11-02 14:17 ` Hao Sun 0 siblings, 0 replies; 13+ messages in thread From: Hao Sun @ 2023-11-02 14:17 UTC (permalink / raw) To: Andrii Nakryiko Cc: Eduard Zingerman, Alexei Starovoitov, Daniel Borkmann, John Fastabend, Andrii Nakryiko, Martin KaFai Lau, Song Liu, Yonghong Song, KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, Linux Kernel Mailing List On Wed, Nov 1, 2023 at 11:45 PM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Wed, Nov 1, 2023 at 2:53 AM Hao Sun <sunhao.th@gmail.com> wrote: > > > > On Fri, Oct 27, 2023 at 7:51 PM Andrii Nakryiko > > <andrii.nakryiko@gmail.com> wrote: > > > > > > On Wed, Oct 25, 2023 at 10:34 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > > > On Tue, 2023-10-24 at 14:40 +0200, Hao Sun 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 is a simplified example: > > > > > > > > SEC("?tp") > > > > __success __retval(0) > > > > __naked void large_shifts(void) > > > > { > > > > asm volatile (" \ > > > > call %[bpf_get_prandom_u32]; \n\ > > > > r8 = r0; \n\ > > > > r6 = r0; \n\ > > > > r6 &= 0xf; \n\ > > > > if w8 < 0xffffffff goto +2; \n\ > > > > if r8 != r6 goto +1; \n\ > > > > w0 >>= w8; /* shift-out-bounds here */ \n\ > > > > exit; \n\ > > > > " : > > > > : __imm(bpf_get_prandom_u32) > > > > : __clobber_all); > > > > } > > > > > > > > > > With my changes the verifier does correctly derive that r8 != r6 will > > > always happen, and thus skips w0 >>= w8. But the test itself with > > > > A similar issue can be triggered after your patch for JNE/JEQ. > > > > For the following case, the verifier would shift out of bound: > > // 0: r0 = -2 > > BPF_MOV64_IMM(BPF_REG_0, -2), > > // 1: r0 /= 1 > > BPF_ALU64_IMM(BPF_DIV, BPF_REG_0, 1), > > // 2: r8 = r0 > > BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), > > // 3: if w8 != 0xfffffffe goto+4 > > BPF_JMP32_IMM(BPF_JNE, BPF_REG_8, 0xfffffffe, 4), > > // 4: if r8 s> 0xd goto+3 > > BPF_JMP_IMM(BPF_JSGT, BPF_REG_8, 0xd, 3), > > // 5: r4 = 0x2 > > BPF_MOV64_IMM(BPF_REG_4, 0x2), > > // 6: if r8 s<= r4 goto+1 > > BPF_JMP_REG(BPF_JSLE, BPF_REG_8, BPF_REG_4, 1), > > // 7: w8 s>>= w0 # shift out of bound here > > BPF_ALU32_REG(BPF_ARSH, BPF_REG_8, BPF_REG_0), > > // 8: exit > > BPF_EXIT_INSN(), > > > > -------- Verifier Log -------- > > func#0 @0 > > 0: R1=ctx(off=0,imm=0) R10=fp0 > > 0: (b7) r0 = -2 ; R0_w=-2 > > 1: (37) r0 /= 1 ; R0_w=scalar() > > 2: (bf) r8 = r0 ; R0_w=scalar(id=1) R8_w=scalar(id=1) > > 3: (56) if w8 != 0xfffffffe goto pc+4 ; > > R8_w=scalar(id=1,smin=-9223372032559808514,smax=9223372036854775806,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2, > > umax32=4294967294,var_off=(0xfffffffe; 0xffffffff00000000)) > > 4: (65) if r8 s> 0xd goto pc+3 ; > > R8_w=scalar(id=1,smin=-9223372032559808514,smax=13,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2,umax32=4294967294, > > var_off=(0xfffffffe; 0xffffffff00000000)) > > 5: (b7) r4 = 2 ; R4_w=2 > > 6: (dd) if r8 s<= r4 goto pc+1 ; R4_w=2 R8_w=4294967294 > > 7: (cc) w8 s>>= w0 ; R0=4294967294 R8=4294967295 > > 8: (95) exit > > > > Here, after #6, reg range is incorrect, seems to be an issue in JSLE case > > in is_branch_taken(). Is this issue fixed in your patch series? > > I don't know, but you can easily check by applying my patches on top > of bpf-next and then trying your change. > After applying your change, the verifier does not shift out of bound, but the range is still not correct. See this verifier log: -------- Verifier Log -------- func#0 @0 0: R1=ctx(off=0,imm=0) R10=fp0 0: (b7) r0 = -2 ; R0_w=-2 1: (37) r0 /= 1 ; R0_w=scalar() 2: (bf) r8 = r0 ; R0_w=scalar(id=1) R8_w=scalar(id=1) 3: (56) if w8 != 0xfffffffe goto pc+4 ; R8_w=scalar(id=1,smin=-9223372032559808514,smax=9223372036854775806,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2,umax32=4294967294,var_off=(0xfffffffe; 0xffffffff00000000)) 4: (65) if r8 s> 0xd goto pc+3 ; R8_w=scalar(id=1,smin=-9223372032559808514,smax=13,umin=umin32=4294967294,umax=18446744073709551614,smin32=-2,smax32=-2,umax32=4294967294,var_off=(0xfffffffe; 0xffffffff00000000)) 5: (b7) r4 = 2 ; R4_w=2 6: (dd) if r8 s<= r4 goto pc+1 ; R4_w=2 R8_w=4294967294 7: (cc) w8 s>>= w0 ; R0=4294967294 R8=scalar() 8: (77) r0 >>= 32 ; R0_w=0 9: (57) r0 &= 1 ; R0_w=0 10: (95) exit from 6 to 8: safe from 4 to 8: safe from 3 to 8: safe processed 14 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1 -------- Test Run Log -------- RetVal: 1 At #9, the verifier thinks the value of R0 is 0, but it's 1, because r0 is -2 all the time before #8. The test run also shows return value is 1. This program can reproduce the above: https://pastebin.com/raw/a0WuXaKh ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2023-11-02 14:17 UTC | newest] Thread overview: 13+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2023-10-24 12:40 bpf: shift-out-of-bounds in tnum_rshift() Hao Sun 2023-10-25 12:31 ` Hao Sun 2023-10-25 13:20 ` Hao Sun 2023-10-25 14:09 ` Shung-Hsi Yu 2023-10-25 14:18 ` Shung-Hsi Yu 2023-10-25 21:59 ` Eduard Zingerman 2023-10-26 6:44 ` Shung-Hsi Yu 2023-10-26 21:53 ` Andrii Nakryiko 2023-10-25 17:34 ` Eduard Zingerman 2023-10-27 17:51 ` Andrii Nakryiko 2023-11-01 9:52 ` Hao Sun 2023-11-01 22:45 ` Andrii Nakryiko 2023-11-02 14:17 ` Hao Sun
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox