[syzbot] [btrfs?] UBSAN: array-index-out-of-bounds in FSE_decompress_wksp_body_bmi2

[syzbot]

Hello,

syzbot found the following issue on:

HEAD commit: 382d4cd18475 lib/clz_ctz.c: Fix __clzdi2() and __ctzdi2() ..
git tree: upstream
console output: https://syzkaller.appspot.com/x/log.txt?x=15979833a80000
kernel config: https://syzkaller.appspot.com/x/.config?x=1b32f62c755c3a9c
dashboard link: https://syzkaller.appspot.com/bug?extid=1f2eb3e8cd123ffce499
compiler: Debian clang version 15.0.6, GNU ld (GNU Binutils for Debian) 2.40

Unfortunately, I don't have any reproducer for this issue yet.

Downloadable assets:
disk image: https://storage.googleapis.com/syzbot-assets/57260ac283ce/disk-382d4cd1.raw.xz
vmlinux: https://storage.googleapis.com/syzbot-assets/8be20b71d903/vmlinux-382d4cd1.xz
kernel image: https://storage.googleapis.com/syzbot-assets/518fe2320c33/bzImage-382d4cd1.xz

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

================================================================================
UBSAN: array-index-out-of-bounds in lib/zstd/common/fse_decompress.c:345:30
index 33 is out of range for type 'FSE_DTable[1]' (aka 'unsigned int[1]')
CPU: 0 PID: 2895 Comm: kworker/u4:7 Not tainted 6.5.0-rc7-syzkaller-00164-g382d4cd18475 #0
Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 07/26/2023
Workqueue: btrfs-endio btrfs_end_bio_work
Call Trace:
<TASK>
__dump_stack lib/dump_stack.c:88 [inline]
dump_stack_lvl+0x1e7/0x2d0 lib/dump_stack.c:106
ubsan_epilogue lib/ubsan.c:217 [inline]
__ubsan_handle_out_of_bounds+0x11c/0x150 lib/ubsan.c:348
FSE_decompress_wksp_body lib/zstd/common/fse_decompress.c:345 [inline]
FSE_decompress_wksp_body_bmi2+0x2e8/0x3790 lib/zstd/common/fse_decompress.c:370
FSE_decompress_wksp_bmi2+0xc7/0x3670 lib/zstd/common/fse_decompress.c:378
HUF_readStats_body lib/zstd/common/entropy_common.c:289 [inline]
HUF_readStats_body_bmi2+0xba/0x620 lib/zstd/common/entropy_common.c:340
HUF_readDTableX1_wksp_bmi2+0x161/0x2740 lib/zstd/decompress/huf_decompress.c:353
HUF_decompress1X1_DCtx_wksp_bmi2+0x4e/0xe0 lib/zstd/decompress/huf_decompress.c:1693
ZSTD_decodeLiteralsBlock+0x1009/0x1560 lib/zstd/decompress/zstd_decompress_block.c:195
ZSTD_decompressBlock_internal+0x106/0xacc0 lib/zstd/decompress/zstd_decompress_block.c:1995
ZSTD_decompressContinue+0x571/0x1690 lib/zstd/decompress/zstd_decompress.c:1184
ZSTD_decompressContinueStream lib/zstd/decompress/zstd_decompress.c:1855 [inline]
ZSTD_decompressStream+0x208f/0x3080 lib/zstd/decompress/zstd_decompress.c:2036
zstd_decompress_bio+0x22b/0x570 fs/btrfs/zstd.c:573
compression_decompress_bio fs/btrfs/compression.c:131 [inline]
btrfs_decompress_bio fs/btrfs/compression.c:930 [inline]
end_compressed_bio_read+0x145/0x400 fs/btrfs/compression.c:178
btrfs_check_read_bio+0x138f/0x19b0 fs/btrfs/bio.c:324
process_one_work+0x92c/0x12c0 kernel/workqueue.c:2600
worker_thread+0xa63/0x1210 kernel/workqueue.c:2751
kthread+0x2b8/0x350 kernel/kthread.c:389
ret_from_fork+0x2e/0x60 arch/x86/kernel/process.c:145
ret_from_fork_asm+0x11/0x20 arch/x86/entry/entry_64.S:304
</TASK>
================================================================================


---
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 syzk...@googlegroups.com.

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

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

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

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

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

[Eric Biggers]

Hi Nick,

On Wed, Aug 30, 2023 at 12:49:53AM -0700, syzbot wrote:
> UBSAN: array-index-out-of-bounds in lib/zstd/common/fse_decompress.c:345:30
> index 33 is out of range for type 'FSE_DTable[1]' (aka 'unsigned int[1]')

Zstandard needs to be converted to use C99 flex-arrays instead of length-1
arrays. https://github.com/facebook/zstd/pull/3785 would fix this in upstream
Zstandard, though it doesn't work well with the fact that upstream Zstandard
supports C90. Not sure how you want to handle this.

- Eric

[Kees Cook]

For the kernel, we just need:

diff --git a/lib/zstd/common/fse_decompress.c b/lib/zstd/common/fse_decompress.c
index a0d06095be83..b11e87fff261 100644
--- a/lib/zstd/common/fse_decompress.c
+++ b/lib/zstd/common/fse_decompress.c
@@ -312,7 +312,7 @@ size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size

typedef struct {
short ncount[FSE_MAX_SYMBOL_VALUE + 1];
- FSE_DTable dtable[1]; /* Dynamically sized */
+ FSE_DTable dtable[]; /* Dynamically sized */
} FSE_DecompressWksp;


And if upstream wants to stay C89 compat, perhaps:

#if __STDC_VERSION__ >= 199901L
# define __FLEX_ARRAY_DIM /*C99*/
#else
# define __FLEX_ARRAY_DIM 0
#endif

and then use __FLEX_ARRAY_DIM as needed (and keep the other "-1" changes
in the github commit):

typedef struct {
short ncount[FSE_MAX_SYMBOL_VALUE + 1];
- FSE_DTable dtable[1]; /* Dynamically sized */
+ FSE_DTable dtable[__FLEX_ARRAY_DIM]; /* Dynamically sized */
} FSE_DecompressWksp;


--
Kees Cook

[Kees Cook]

On Thu, Oct 12, 2023 at 07:55:55PM +0000, Nick Terrell wrote:
>
> > On Oct 9, 2023, at 1:29 PM, Kees Cook <kees...@chromium.org> wrote:
> >
> > !-------------------------------------------------------------------|
> > This Message Is From an External Sender
> >
> > |-------------------------------------------------------------------!

> >
> > On Sat, Oct 07, 2023 at 02:05:56PM -0700, Eric Biggers wrote:
> >> Hi Nick,
> >>
> >> On Wed, Aug 30, 2023 at 12:49:53AM -0700, syzbot wrote:
> >>> UBSAN: array-index-out-of-bounds in lib/zstd/common/fse_decompress.c:345:30
> >>> index 33 is out of range for type 'FSE_DTable[1]' (aka 'unsigned int[1]')
> >>
> >> Zstandard needs to be converted to use C99 flex-arrays instead of length-1
> >> arrays. https://github.com/facebook/zstd/pull/3785 would fix this in upstream
> >> Zstandard, though it doesn't work well with the fact that upstream Zstandard
> >> supports C90. Not sure how you want to handle this.
> >
> > For the kernel, we just need:
> >
> > diff --git a/lib/zstd/common/fse_decompress.c b/lib/zstd/common/fse_decompress.c
> > index a0d06095be83..b11e87fff261 100644
> > --- a/lib/zstd/common/fse_decompress.c
> > +++ b/lib/zstd/common/fse_decompress.c
> > @@ -312,7 +312,7 @@ size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size
> >
> > typedef struct {
> > short ncount[FSE_MAX_SYMBOL_VALUE + 1];
> > - FSE_DTable dtable[1]; /* Dynamically sized */
> > + FSE_DTable dtable[]; /* Dynamically sized */
> > } FSE_DecompressWksp;
>

> Thanks Eric and Kees for the report and the fix! I am working on putting this
> patch up now, just need to test the fix myself to ensure I can reproduce the
> issue and the fix.
>
> In your opinion does this worth trying to get this patch into v6.6, or should it
> wait for v6.7?

For all these flex array conversions we're mostly on a "slow and steady"
route, so there's no rush really. I think waiting for v6.7 is fine. If
anyone ends up wanting to backport it, it should be pretty clean
I imagine.

Thanks for getting it all landed! :)

-Kees

--
Kees Cook

[Nick Terrell]

Sounds good, thanks for the context!

I’ll make sure the fix gets backported. Eric Biggers already has a PR up! [0]

[0] https://github.com/facebook/zstd/pull/3785

[Nick Terrell]

> On Oct 9, 2023, at 1:29 PM, Kees Cook <kees...@chromium.org> wrote:
>
> !-------------------------------------------------------------------|
> This Message Is From an External Sender
>
> |-------------------------------------------------------------------!
>

> On Sat, Oct 07, 2023 at 02:05:56PM -0700, Eric Biggers wrote:
>> Hi Nick,
>>
>> On Wed, Aug 30, 2023 at 12:49:53AM -0700, syzbot wrote:
>>> UBSAN: array-index-out-of-bounds in lib/zstd/common/fse_decompress.c:345:30
>>> index 33 is out of range for type 'FSE_DTable[1]' (aka 'unsigned int[1]')
>>
>> Zstandard needs to be converted to use C99 flex-arrays instead of length-1
>> arrays. https://github.com/facebook/zstd/pull/3785 would fix this in upstream
>> Zstandard, though it doesn't work well with the fact that upstream Zstandard
>> supports C90. Not sure how you want to handle this.
>
> For the kernel, we just need:
>
> diff --git a/lib/zstd/common/fse_decompress.c b/lib/zstd/common/fse_decompress.c
> index a0d06095be83..b11e87fff261 100644
> --- a/lib/zstd/common/fse_decompress.c
> +++ b/lib/zstd/common/fse_decompress.c
> @@ -312,7 +312,7 @@ size_t FSE_decompress_wksp(void* dst, size_t dstCapacity, const void* cSrc, size
>
> typedef struct {
> short ncount[FSE_MAX_SYMBOL_VALUE + 1];
> - FSE_DTable dtable[1]; /* Dynamically sized */
> + FSE_DTable dtable[]; /* Dynamically sized */
> } FSE_DecompressWksp;

Thanks Eric and Kees for the report and the fix! I am working on putting this
patch up now, just need to test the fix myself to ensure I can reproduce the
issue and the fix.

In your opinion does this worth trying to get this patch into v6.6, or should it
wait for v6.7?

Best,
Nick Terrell