Various Integer Overflows in dlmalloc

Various Integer Overflows in dlmalloc

[Richard Weinberger]

Hi!

While inspecting various security aspects of U-Boot I noticed some
issues around dlmalloc and asking for your feedback, especially for the
first issue.
I'm CC'ing Barebox folks since Barebox seems to be based on the same
dlmalloc-implementation as U-Boot does.

1. Integer Overflow While Computing Allocation Size

malloc/realloc/memalign take an arbitrary request size and apply
padding.

First, the length is (imperfectly) checked and the the conversion happens:

  if ((long)bytes < 0) return NULL;

  nb = request2size(bytes);  /* padded request size; */

The problem is that the request2size() macro is casting the requested
size to an signed long and adds SIZE_SZ + MALLOC_ALIGN_MASK:

#define request2size(req) \
 (((long)((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) < \
  (long)(MINSIZE + MALLOC_ALIGN_MASK)) ? MINSIZE : \
   (((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) & ~(MALLOC_ALIGN_MASK)))

So, any allocation request between LONG_MAX - (SIZE_SZ + MALLOC_ALIGN_MASK) - 1 and LONG_MAX
will cause an overflow and as a consequence the caller will get
less memory than requested.

e.g. on an 32bits system malloc(2147483647) will succeed but allocates
only 16 bytes (MINSIZE). I've tested this with U-Boot on i386 and ARM.

This is a beefy vulnerability for exploit writers since unbound allocations
do happen. Like in the ext4 and squashfs symlink code, I'm sure there are more.
If you don't care about verified boot, it's less of an issue, though.

I'm not so sure what the best fix is.
Mostly because I'm not sure why request2size() is anyway casting to long.
The original dlmalloc.c implementation doesn't do so. It has also a more
sophisticated overflow check, which is also missing in both U-Boot and Barebox.
See https://research.cs.wisc.edu/sonar/projects/mnemosyne/resources/doc/html/malloc-original_2src_2dlmalloc_8c-source.html
Lines 01938 to 01962.

I tracked down the bug to ppcboot, it's there since day 0.
So I don't know what's the intention behind casting.

On the other hand, since over commit is not supported, we could also just fail
if the requested size is larger then the total amount of system memory.
I'm a little in fear that more overflows are lurking in the code.

2. Integer overflow in sbrk() (U-Boot only)

sbrk() does:
        ulong new = old + increment;

        /*
         * if we are giving memory back make sure we clear it out since
         * we set MORECORE_CLEARS to 1
         */
        if (increment < 0)
                memset((void *)new, 0, -increment);

        if ((new < mem_malloc_start) || (new > mem_malloc_end))
                return (void *)MORECORE_FAILURE;


If old + increment overflows (increment is a ptrdiff_t) then
sbrk() wrongly thinks we're shrinking the heap and memsets an invalid
range.

I propose as solution, applying memset() after the range check.

3. Wrong ptrdiff_t type (U-Boot only)

U-Boot defines __kernel_ptrdiff_t to int for both i386 and x86_64.
As a consequence, large allocations on x86_64 will overflow the increment
parameter of sbrk() and less than requested is allocated.
I suggest defining __kernel_ptrdiff_t on x86_64 to long.

Thanks,
//richard
-- 
​​​​​sigma star gmbh | Eduard-Bodem-Gasse 6, 6020 Innsbruck, AUT
UID/VAT Nr: ATU 66964118 | FN: 374287y

Re: Various Integer Overflows in dlmalloc

[Tom Rini]

[-- Attachment #1: Type: text/plain, Size: 3758 bytes --]

On Tue, Jul 16, 2024 at 11:16:27AM +0200, Richard Weinberger wrote:
> Hi!
> 
> While inspecting various security aspects of U-Boot I noticed some
> issues around dlmalloc and asking for your feedback, especially for the
> first issue.
> I'm CC'ing Barebox folks since Barebox seems to be based on the same
> dlmalloc-implementation as U-Boot does.

Thanks for digging in to all of this.

> 1. Integer Overflow While Computing Allocation Size
> 
> malloc/realloc/memalign take an arbitrary request size and apply
> padding.
> 
> First, the length is (imperfectly) checked and the the conversion happens:
> 
>   if ((long)bytes < 0) return NULL;
> 
>   nb = request2size(bytes);  /* padded request size; */
> 
> The problem is that the request2size() macro is casting the requested
> size to an signed long and adds SIZE_SZ + MALLOC_ALIGN_MASK:
> 
> #define request2size(req) \
>  (((long)((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) < \
>   (long)(MINSIZE + MALLOC_ALIGN_MASK)) ? MINSIZE : \
>    (((req) + (SIZE_SZ + MALLOC_ALIGN_MASK)) & ~(MALLOC_ALIGN_MASK)))
> 
> So, any allocation request between LONG_MAX - (SIZE_SZ + MALLOC_ALIGN_MASK) - 1 and LONG_MAX
> will cause an overflow and as a consequence the caller will get
> less memory than requested.
> 
> e.g. on an 32bits system malloc(2147483647) will succeed but allocates
> only 16 bytes (MINSIZE). I've tested this with U-Boot on i386 and ARM.
> 
> This is a beefy vulnerability for exploit writers since unbound allocations
> do happen. Like in the ext4 and squashfs symlink code, I'm sure there are more.
> If you don't care about verified boot, it's less of an issue, though.
> 
> I'm not so sure what the best fix is.
> Mostly because I'm not sure why request2size() is anyway casting to long.
> The original dlmalloc.c implementation doesn't do so. It has also a more
> sophisticated overflow check, which is also missing in both U-Boot and Barebox.
> See https://research.cs.wisc.edu/sonar/projects/mnemosyne/resources/doc/html/malloc-original_2src_2dlmalloc_8c-source.html
> Lines 01938 to 01962.
> 
> I tracked down the bug to ppcboot, it's there since day 0.
> So I don't know what's the intention behind casting.
> 
> On the other hand, since over commit is not supported, we could also just fail
> if the requested size is larger then the total amount of system memory.
> I'm a little in fear that more overflows are lurking in the code.

The "why" is likely lost due to time and I could only speculate and wave
my hands about funny compiler issues at the time. Since we don't support
overcommit, I'd be inclined to go with just failing if we're exceeding
SYS_MALLOC_LEN.

> 2. Integer overflow in sbrk() (U-Boot only)
> 
> sbrk() does:
>         ulong new = old + increment;
> 
>         /*
>          * if we are giving memory back make sure we clear it out since
>          * we set MORECORE_CLEARS to 1
>          */
>         if (increment < 0)
>                 memset((void *)new, 0, -increment);
> 
>         if ((new < mem_malloc_start) || (new > mem_malloc_end))
>                 return (void *)MORECORE_FAILURE;
> 
> 
> If old + increment overflows (increment is a ptrdiff_t) then
> sbrk() wrongly thinks we're shrinking the heap and memsets an invalid
> range.
> 
> I propose as solution, applying memset() after the range check.

OK, sounds good.

> 3. Wrong ptrdiff_t type (U-Boot only)
> 
> U-Boot defines __kernel_ptrdiff_t to int for both i386 and x86_64.
> As a consequence, large allocations on x86_64 will overflow the increment
> parameter of sbrk() and less than requested is allocated.
> I suggest defining __kernel_ptrdiff_t on x86_64 to long.

OK, sounds good.

-- 
Tom

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 659 bytes --]