netdev.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [syzbot] [bpf?] UBSAN: array-index-out-of-bounds in check_stack_range_initialized
@ 2024-03-19 18:12 syzbot
  2024-03-21  7:33 ` stack access issue. " Alexei Starovoitov
  0 siblings, 1 reply; 10+ messages in thread
From: syzbot @ 2024-03-19 18:12 UTC (permalink / raw)
  To: andrii, ast, bpf, daniel, eddyz87, haoluo, john.fastabend, jolsa,
	kpsingh, linux-kernel, martin.lau, netdev, sdf, song,
	syzkaller-bugs, yonghong.song

Hello,

syzbot found the following issue on:

HEAD commit:    0740b6427e90 Merge branch 'bpf-arena-followups'
git tree:       bpf
console+strace: https://syzkaller.appspot.com/x/log.txt?x=12fed769180000
kernel config:  https://syzkaller.appspot.com/x/.config?x=6fb1be60a193d440
dashboard link: https://syzkaller.appspot.com/bug?extid=33f4297b5f927648741a
compiler:       Debian clang version 15.0.6, GNU ld (GNU Binutils for Debian) 2.40
syz repro:      https://syzkaller.appspot.com/x/repro.syz?x=1763a479180000
C reproducer:   https://syzkaller.appspot.com/x/repro.c?x=15c38711180000

Downloadable assets:
disk image: https://storage.googleapis.com/syzbot-assets/c9e6e9f97566/disk-0740b642.raw.xz
vmlinux: https://storage.googleapis.com/syzbot-assets/78476a588b62/vmlinux-0740b642.xz
kernel image: https://storage.googleapis.com/syzbot-assets/50cd6fab9ead/bzImage-0740b642.xz

IMPORTANT: if you fix the issue, please add the following tag to the commit:
Reported-by: syzbot+33f4297b5f927648741a@syzkaller.appspotmail.com

------------[ cut here ]------------
UBSAN: array-index-out-of-bounds in kernel/bpf/verifier.c:7190:12
index -1 is out of range for type 'u8[8]' (aka 'unsigned char[8]')
CPU: 0 PID: 5071 Comm: syz-executor474 Not tainted 6.8.0-syzkaller-05226-g0740b6427e90 #0
Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 02/29/2024
Call Trace:
 <TASK>
 __dump_stack lib/dump_stack.c:88 [inline]
 dump_stack_lvl+0x1e7/0x2e0 lib/dump_stack.c:106
 ubsan_epilogue lib/ubsan.c:217 [inline]
 __ubsan_handle_out_of_bounds+0x121/0x150 lib/ubsan.c:415
 check_stack_range_initialized+0x1668/0x19a0 kernel/bpf/verifier.c:7190
 check_helper_mem_access+0x2eb/0xfa0 kernel/bpf/verifier.c:7294
 check_helper_call+0x263c/0x7220 kernel/bpf/verifier.c:10252
 do_check+0x9e29/0x10530 kernel/bpf/verifier.c:17801
 do_check_common+0x14bd/0x1dd0 kernel/bpf/verifier.c:20500
 do_check_main kernel/bpf/verifier.c:20591 [inline]
 bpf_check+0x136ab/0x19010 kernel/bpf/verifier.c:21261
 bpf_prog_load+0x1667/0x20f0 kernel/bpf/syscall.c:2895
 __sys_bpf+0x4ee/0x810 kernel/bpf/syscall.c:5631
 __do_sys_bpf kernel/bpf/syscall.c:5738 [inline]
 __se_sys_bpf kernel/bpf/syscall.c:5736 [inline]
 __x64_sys_bpf+0x7c/0x90 kernel/bpf/syscall.c:5736
 do_syscall_64+0xfb/0x240
 entry_SYSCALL_64_after_hwframe+0x6d/0x75
RIP: 0033:0x7f8416194629
Code: 48 83 c4 28 c3 e8 37 17 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 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 c7 c1 b8 ff ff ff f7 d8 64 89 01 48
RSP: 002b:00007ffdc6f0fdb8 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda RBX: 00007ffdc6f0ff88 RCX: 00007f8416194629
RDX: 0000000000000090 RSI: 00000000200000c0 RDI: 0000000000000005
RBP: 00007f8416207610 R08: 0000000000000000 R09: 00007ffdc6f0ff88
R10: 00000000fffffff8 R11: 0000000000000246 R12: 0000000000000001
R13: 00007ffdc6f0ff78 R14: 0000000000000001 R15: 0000000000000001
 </TASK>
---[ end trace ]---


---
This report is generated by a bot. It may contain errors.
See https://goo.gl/tpsmEJ for more information about syzbot.
syzbot engineers can be reached at syzkaller@googlegroups.com.

syzbot will keep track of this issue. See:
https://goo.gl/tpsmEJ#status for how to communicate with syzbot.

If the report is already addressed, let syzbot know by replying with:
#syz fix: exact-commit-title

If you want syzbot to run the reproducer, reply with:
#syz test: git://repo/address.git branch-or-commit-hash
If you attach or paste a git patch, syzbot will apply it before testing.

If you want to overwrite report's subsystems, reply with:
#syz set subsystems: new-subsystem
(See the list of subsystem names on the web dashboard)

If the report is a duplicate of another one, reply with:
#syz dup: exact-subject-of-another-report

If you want to undo deduplication, reply with:
#syz undup

^ permalink raw reply	[flat|nested] 10+ messages in thread
* Re: stack access issue. Re: [syzbot] [bpf?] UBSAN: array-index-out-of-bounds in check_stack_range_initialized
@ 2024-03-26 21:11 Kaiming Huang
  0 siblings, 0 replies; 10+ messages in thread
From: Kaiming Huang @ 2024-03-26 21:11 UTC (permalink / raw)
  To: Andrei Matei
  Cc: alexei.starovoitov, andrii, ast, bpf, daniel, eadavis, eddyz87,
	haoluo, john.fastabend, jolsa, kpsingh, linux-kernel, martin.lau,
	netdev, sdf, song, syzkaller-bugs, yonghong.song

Hi there,

I went across this bug using my static analysis tool as well and was
glad to find this email thread.

My understanding is that the root cause of this bug has not been
identified yet given the previous discussion in this thread.

This is the line of code that has the issue.

stype = &state->stack[spi].slot_type[slot % BPF_REG_SIZE];

Based on my analysis result, it is the part "slot_type[slot %
BPF_REG_SIZE]" may result in memory access with a negative index,
which should not be allowed. spi (as well as min_off, max_off, and
slot) is(are) supposed to be negative based on my understanding of the
workflow. But the index of slot_type is not supposed to be negative.

The slot_type is defined as below:

u8 slot_type[BPF_REG_SIZE];  //BPF_REG_SIZE is 8

So the type of slot_type is u8[8].

However, given "slot" can be negative, say -1. The result of slot %
BPF_REG_SIZE is -1. This might sound counter-intuitive as % always
gives positive results. But in C, % operation keeps the sign of
dividend (and thus that's why I'm not sure whether the fix will catch
this).

You can examine this by simply running this short piece of code. The
result of the modulo operation is -1 on my end, and that is the reason
that causes the OOB negative index, and this would be an off-by-one on
the u8[8].

#include <stdio.h>
#define BPF_REG_SIZE 8
int main() {
    int i = -1;
    unsigned int j = i % BPF_REG_SIZE;
    printf("%d\n", j);
    return 0;
}

A more severe scenario is when interpreting the j in the above example
as unsigned int, aka integer overflow/wrap-around, in that case, the
value of j will be 4,294,967,295. If it is the case, then it is a
classic OOB access on the u8[8].

Hopefully my illustration makes sense, please let me know if you see
any issues. Thanks.

Best regards,
Kaiming.

^ permalink raw reply	[flat|nested] 10+ messages in thread
* Re: stack access issue. Re: [syzbot] [bpf?] UBSAN: array-index-out-of-bounds in check_stack_range_initialized
@ 2024-03-26 22:06 Kaiming Huang
  0 siblings, 0 replies; 10+ messages in thread
From: Kaiming Huang @ 2024-03-26 22:06 UTC (permalink / raw)
  To: Andrei Matei
  Cc: alexei.starovoitov, andrii, ast, bpf, daniel, eadavis, eddyz87,
	haoluo, john.fastabend, jolsa, kpsingh, linux-kernel, martin.lau,
	netdev, sdf, song, syzkaller-bugs, yonghong.song, Kaiming Huang

Hi there,

Please discard my previous email as I figured it may be beneficial to
rephrase some of the content in it for clarity.

I went across this bug using my static analysis tool as well and was
glad to find this email thread.

My understanding is that the root cause of this bug has not been
identified yet given the previous discussion in this thread.

This is the line of code that has the issue.

stype = &state->stack[spi].slot_type[slot % BPF_REG_SIZE];

Based on my analysis result, it is the part "slot_type[slot %
BPF_REG_SIZE]" may result in memory access with a negative index,
which should not be allowed. min_off and max_off are supposed to be
negative based on my understanding of the
workflow. But the spi, slot, and the index of slot_type are not
supposed to be negative.

The slot_type is defined as below:

u8 slot_type[BPF_REG_SIZE];  //BPF_REG_SIZE is 8

So the type of slot_type is u8[8].

However, the bug may alter the "slot" to be negative, say -1. Then
this would cause the result of slot %
BPF_REG_SIZE is -1. This might sound counter-intuitive as % always
gives positive results. But in C, % operation keeps the sign of
the dividend. The applied check checks whether access_size is
negative, I'm not sure whether the fix will catch
this sufficiently). Could the fix be potentially directly applied to
"slot" to ensure it is positive?

You can examine this by simply running this short piece of code. The
result of the modulo operation is -1 on my end, and that is the reason
that causes the OOB negative index -1, which was reported by the Syzkaller.

#include <stdio.h>
#define BPF_REG_SIZE 8
int main() {
    int i = -1;
    unsigned int j = i % BPF_REG_SIZE;
    printf("%d\n", j);
    return 0;
}

A more severe scenario, if possible, is when interpreting the j in the
above example
as unsigned int, aka integer overflow/wrap-around, in that case, the
value of j will be 4,294,967,295. If this is the case, then it is a
classic OOB access on the u8[8]. I don't know whether this part is feasible.

Hopefully, my illustration makes sense, please let me know if you see
any issues. Thanks.

Best regards,
Kaiming.

^ permalink raw reply	[flat|nested] 10+ messages in thread
end of thread, other threads:[~2024-03-26 22:06 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-03-19 18:12 [syzbot] [bpf?] UBSAN: array-index-out-of-bounds in check_stack_range_initialized syzbot
2024-03-21  7:33 ` stack access issue. " Alexei Starovoitov
2024-03-21 14:07   ` Andrei Matei
2024-03-24  0:50   ` Andrei Matei
2024-03-24  0:52     ` Alexei Starovoitov
2024-03-24  2:12       ` Andrei Matei
2024-03-24  2:55         ` Alexei Starovoitov
2024-03-26  2:48           ` Andrei Matei
  -- strict thread matches above, loose matches on Subject: below --
2024-03-26 21:11 Kaiming Huang
2024-03-26 22:06 Kaiming Huang

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).