ext4: fix off-by-one error in do_split

[PATCH] ext4: fix off-by-one error in do_split

Posted by Artem Sadovnikov 10 months, 1 week ago

Syzkaller detected a use-after-free issue in ext4_insert_dentry that was
caused by out-of-bounds access due to incorrect splitting in do_split.

BUG: KASAN: use-after-free in ext4_insert_dentry+0x36a/0x6d0 fs/ext4/namei.c:2109
Write of size 251 at addr ffff888074572f14 by task syz-executor335/5847

CPU: 0 UID: 0 PID: 5847 Comm: syz-executor335 Not tainted 6.12.0-rc6-syzkaller-00318-ga9cda7c0ffed #0
Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 10/30/2024
Call Trace:
 <TASK>
 __dump_stack lib/dump_stack.c:94 [inline]
 dump_stack_lvl+0x241/0x360 lib/dump_stack.c:120
 print_address_description mm/kasan/report.c:377 [inline]
 print_report+0x169/0x550 mm/kasan/report.c:488
 kasan_report+0x143/0x180 mm/kasan/report.c:601
 kasan_check_range+0x282/0x290 mm/kasan/generic.c:189
 __asan_memcpy+0x40/0x70 mm/kasan/shadow.c:106
 ext4_insert_dentry+0x36a/0x6d0 fs/ext4/namei.c:2109
 add_dirent_to_buf+0x3d9/0x750 fs/ext4/namei.c:2154
 make_indexed_dir+0xf98/0x1600 fs/ext4/namei.c:2351
 ext4_add_entry+0x222a/0x25d0 fs/ext4/namei.c:2455
 ext4_add_nondir+0x8d/0x290 fs/ext4/namei.c:2796
 ext4_symlink+0x920/0xb50 fs/ext4/namei.c:3431
 vfs_symlink+0x137/0x2e0 fs/namei.c:4615
 do_symlinkat+0x222/0x3a0 fs/namei.c:4641
 __do_sys_symlink fs/namei.c:4662 [inline]
 __se_sys_symlink fs/namei.c:4660 [inline]
 __x64_sys_symlink+0x7a/0x90 fs/namei.c:4660
 do_syscall_x64 arch/x86/entry/common.c:52 [inline]
 do_syscall_64+0xf3/0x230 arch/x86/entry/common.c:83
 entry_SYSCALL_64_after_hwframe+0x77/0x7f
 </TASK>

The following loop is located right above 'if' statement.

for (i = count-1; i >= 0; i--) {
	/* is more than half of this entry in 2nd half of the block? */
	if (size + map[i].size/2 > blocksize/2)
		break;
	size += map[i].size;
	move++;
}

'i' in this case could go down to -1, in which case sum of active entries
wouldn't exceed half the block size, but previous behaviour would also do
split in half if sum would exceed at the very last block, which in case of
having too many long name files in a single block could lead to
out-of-bounds access and following use-after-free.

Found by Linux Verification Center (linuxtesting.org) with Syzkaller.

Cc: stable@vger.kernel.org
Fixes: 5872331b3d91 ("ext4: fix potential negative array index in do_split()")
Signed-off-by: Artem Sadovnikov <a.sadovnikov@ispras.ru>
---
 fs/ext4/namei.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
index cb5cb33b1d91..e9712e64ec8f 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -1971,7 +1971,7 @@ static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
 	 * split it in half by count; each resulting block will have at least
 	 * half the space free.
 	 */
-	if (i > 0)
+	if (i >= 0)
 		split = count - move;
 	else
 		split = count/2;
-- 
2.43.0

Re: [PATCH] ext4: fix off-by-one error in do_split

Posted by Theodore Ts'o 9 months, 2 weeks ago

On Fri, 04 Apr 2025 08:28:05 +0000, Artem Sadovnikov wrote:
> Syzkaller detected a use-after-free issue in ext4_insert_dentry that was
> caused by out-of-bounds access due to incorrect splitting in do_split.
> 
> BUG: KASAN: use-after-free in ext4_insert_dentry+0x36a/0x6d0 fs/ext4/namei.c:2109
> Write of size 251 at addr ffff888074572f14 by task syz-executor335/5847
> 
> CPU: 0 UID: 0 PID: 5847 Comm: syz-executor335 Not tainted 6.12.0-rc6-syzkaller-00318-ga9cda7c0ffed #0
> Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 10/30/2024
> Call Trace:
>  <TASK>
>  __dump_stack lib/dump_stack.c:94 [inline]
>  dump_stack_lvl+0x241/0x360 lib/dump_stack.c:120
>  print_address_description mm/kasan/report.c:377 [inline]
>  print_report+0x169/0x550 mm/kasan/report.c:488
>  kasan_report+0x143/0x180 mm/kasan/report.c:601
>  kasan_check_range+0x282/0x290 mm/kasan/generic.c:189
>  __asan_memcpy+0x40/0x70 mm/kasan/shadow.c:106
>  ext4_insert_dentry+0x36a/0x6d0 fs/ext4/namei.c:2109
>  add_dirent_to_buf+0x3d9/0x750 fs/ext4/namei.c:2154
>  make_indexed_dir+0xf98/0x1600 fs/ext4/namei.c:2351
>  ext4_add_entry+0x222a/0x25d0 fs/ext4/namei.c:2455
>  ext4_add_nondir+0x8d/0x290 fs/ext4/namei.c:2796
>  ext4_symlink+0x920/0xb50 fs/ext4/namei.c:3431
>  vfs_symlink+0x137/0x2e0 fs/namei.c:4615
>  do_symlinkat+0x222/0x3a0 fs/namei.c:4641
>  __do_sys_symlink fs/namei.c:4662 [inline]
>  __se_sys_symlink fs/namei.c:4660 [inline]
>  __x64_sys_symlink+0x7a/0x90 fs/namei.c:4660
>  do_syscall_x64 arch/x86/entry/common.c:52 [inline]
>  do_syscall_64+0xf3/0x230 arch/x86/entry/common.c:83
>  entry_SYSCALL_64_after_hwframe+0x77/0x7f
>  </TASK>
> 
> [...]

Applied, thanks!

[1/1] ext4: fix off-by-one error in do_split
      commit: 7e50bbb134aba1df0854f171b596b3a42d35605a

(Apologies for sending this late; I've been dealing with a family
medical emergency.  In any case, the patch landed in v6.16-rc2.)

Best regards,
-- 
Theodore Ts'o <tytso@mit.edu>

Re: [PATCH] ext4: fix off-by-one error in do_split

Posted by Jan Kara 10 months ago

On Fri 04-04-25 08:28:05, Artem Sadovnikov wrote:
> Syzkaller detected a use-after-free issue in ext4_insert_dentry that was
> caused by out-of-bounds access due to incorrect splitting in do_split.
> 
> BUG: KASAN: use-after-free in ext4_insert_dentry+0x36a/0x6d0 fs/ext4/namei.c:2109
> Write of size 251 at addr ffff888074572f14 by task syz-executor335/5847
> 
> CPU: 0 UID: 0 PID: 5847 Comm: syz-executor335 Not tainted 6.12.0-rc6-syzkaller-00318-ga9cda7c0ffed #0
> Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 10/30/2024
> Call Trace:
>  <TASK>
>  __dump_stack lib/dump_stack.c:94 [inline]
>  dump_stack_lvl+0x241/0x360 lib/dump_stack.c:120
>  print_address_description mm/kasan/report.c:377 [inline]
>  print_report+0x169/0x550 mm/kasan/report.c:488
>  kasan_report+0x143/0x180 mm/kasan/report.c:601
>  kasan_check_range+0x282/0x290 mm/kasan/generic.c:189
>  __asan_memcpy+0x40/0x70 mm/kasan/shadow.c:106
>  ext4_insert_dentry+0x36a/0x6d0 fs/ext4/namei.c:2109
>  add_dirent_to_buf+0x3d9/0x750 fs/ext4/namei.c:2154
>  make_indexed_dir+0xf98/0x1600 fs/ext4/namei.c:2351
>  ext4_add_entry+0x222a/0x25d0 fs/ext4/namei.c:2455
>  ext4_add_nondir+0x8d/0x290 fs/ext4/namei.c:2796
>  ext4_symlink+0x920/0xb50 fs/ext4/namei.c:3431
>  vfs_symlink+0x137/0x2e0 fs/namei.c:4615
>  do_symlinkat+0x222/0x3a0 fs/namei.c:4641
>  __do_sys_symlink fs/namei.c:4662 [inline]
>  __se_sys_symlink fs/namei.c:4660 [inline]
>  __x64_sys_symlink+0x7a/0x90 fs/namei.c:4660
>  do_syscall_x64 arch/x86/entry/common.c:52 [inline]
>  do_syscall_64+0xf3/0x230 arch/x86/entry/common.c:83
>  entry_SYSCALL_64_after_hwframe+0x77/0x7f
>  </TASK>
> 
> The following loop is located right above 'if' statement.
> 
> for (i = count-1; i >= 0; i--) {
> 	/* is more than half of this entry in 2nd half of the block? */
> 	if (size + map[i].size/2 > blocksize/2)
> 		break;
> 	size += map[i].size;
> 	move++;
> }
> 
> 'i' in this case could go down to -1, in which case sum of active entries
> wouldn't exceed half the block size, but previous behaviour would also do
> split in half if sum would exceed at the very last block, which in case of
> having too many long name files in a single block could lead to
> out-of-bounds access and following use-after-free.

Thanks for debugging this! The fix looks good, but I'm still failing to see
the use-after-free / end-of-buffer issue. If we wrongly split to two parts
count/2 each, then dx_move_dirents() and dx_pack_dirents() seem to still
work correctly. Just they will make too small amount of space in bh but
still at least one dir entry gets moved? Following add_dirent_to_buf() is
more likely to fail due to ENOSPC but still I don't see the buffer overrun
issue? Can you please tell me what I'm missing? Thanks!

Anyway, since the fix looks obviously correct feel free to add:

Reviewed-by: Jan Kara <jack@suse.cz>


								Honza
> 
> Found by Linux Verification Center (linuxtesting.org) with Syzkaller.
> 
> Cc: stable@vger.kernel.org
> Fixes: 5872331b3d91 ("ext4: fix potential negative array index in do_split()")
> Signed-off-by: Artem Sadovnikov <a.sadovnikov@ispras.ru>
> ---
>  fs/ext4/namei.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
> index cb5cb33b1d91..e9712e64ec8f 100644
> --- a/fs/ext4/namei.c
> +++ b/fs/ext4/namei.c
> @@ -1971,7 +1971,7 @@ static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
>  	 * split it in half by count; each resulting block will have at least
>  	 * half the space free.
>  	 */
> -	if (i > 0)
> +	if (i >= 0)
>  		split = count - move;
>  	else
>  		split = count/2;
> -- 
> 2.43.0
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

Re: [PATCH] ext4: fix off-by-one error in do_split

Posted by Artem Sadovnikov 10 months ago

On 07.04.2025 16:02, Jan Kara wrote:
> Thanks for debugging this! The fix looks good, but I'm still failing to see
> the use-after-free / end-of-buffer issue. If we wrongly split to two parts
> count/2 each, then dx_move_dirents() and dx_pack_dirents() seem to still
> work correctly. Just they will make too small amount of space in bh but
> still at least one dir entry gets moved? Following add_dirent_to_buf() is
> more likely to fail due to ENOSPC but still I don't see the buffer overrun
> issue? Can you please tell me what I'm missing? Thanks!

add_dirent_to_buf() only checks for available space if its de parameter is NULL, but make_indexed_dir() provides a non-NULL de, so that space check is skipped entirely. add_dirent_to_buf() then calls ext4_insert_dentry() which will write a filename that's potentially larger than entry size and will cause an out-of-bounds write.

Re: [PATCH] ext4: fix off-by-one error in do_split

Posted by Jan Kara 10 months ago

On Tue 08-04-25 16:38:36, Artem Sadovnikov wrote:
> On 07.04.2025 16:02, Jan Kara wrote:
> > Thanks for debugging this! The fix looks good, but I'm still failing to see
> > the use-after-free / end-of-buffer issue. If we wrongly split to two parts
> > count/2 each, then dx_move_dirents() and dx_pack_dirents() seem to still
> > work correctly. Just they will make too small amount of space in bh but
> > still at least one dir entry gets moved? Following add_dirent_to_buf() is
> > more likely to fail due to ENOSPC but still I don't see the buffer overrun
> > issue? Can you please tell me what I'm missing? Thanks!
> 
> add_dirent_to_buf() only checks for available space if its de parameter
> is NULL, but make_indexed_dir() provides a non-NULL de, so that space
> check is skipped entirely. add_dirent_to_buf() then calls
> ext4_insert_dentry() which will write a filename that's potentially
> larger than entry size and will cause an out-of-bounds write.

Indeed. I didn't notice this detail. Thanks for explanation!

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR