[uclibc-ng-devel] malloc-standard: Fix truncation problem in malloc

From: Marius Melzer <marius.melzer@kernkonzept.com>

This fixes a bug that can lead to the calculation of a wrong bin `idx`,
which in turn leads to a too small chunk of memory being chosen for the
number of bytes (`nb`) to be allocated. This leads to a fault (or
possibly to memory being written in the wrong location) when using the
offset `nb` on top of the chunk for a write operation.

malloc() takes the number of bytes to allocate as size_t, but the
calculation of the global bin index idx is done via
malloc_largebin_index() which takes as parameter and calculates
internally with unsigned int. This leads, for large allocations, to a
truncation of the value and consequently to the idx being wrongly
calculated.

idx is an index into the bins which are sorted in ascending order of
size range of its including chunks (e.g. 8-16, 16-32, 32-64,...).
The malloc() algorithm depends on the idx being calculated such that
we begin searching only at a bin whose chunks are always large enough
to include the memory size to be allocated (nb).

If the idx is too small (as can happen due to the described integer
overflow), this code will lead to a write to a wrong
address (remainder->bk resp. remainder->fd) (lines from malloc.c):

1086    size = chunksize(victim);
1087
1088    /* We know the first chunk in this bin is big enough to use. */
1089    assert((unsigned long)(size) >= (unsigned long)(nb));

1108    remainder = chunk_at_offset(victim, nb);

1111    remainder->bk = remainder->fd = unsorted_chunks(av);

The chunk victim should normally be from a bin of a range where each
chunk is at least of the size nb. Since it's not, its size may be
smaller than nb. With assertions enabled the assertion in 1089 would
fail. Without assertions we add nb as an offset to the chunk but since
the size of the chunk is a lot smaller than nb, this will point to an
address somewhere else.

Signed-off-by: Marcus Haehnel <marcus.haehnel@kernkonzept.com>
---
 libc/stdlib/malloc-standard/malloc.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

Hi,

thanks for the detailed commit message, applied and pushed.

best regards
 Waldemar

Marcus Haehnel wrote,

> From: Marius Melzer <marius.melzer@kernkonzept.com>
> 
> This fixes a bug that can lead to the calculation of a wrong bin `idx`,
> which in turn leads to a too small chunk of memory being chosen for the
> number of bytes (`nb`) to be allocated. This leads to a fault (or
> possibly to memory being written in the wrong location) when using the
> offset `nb` on top of the chunk for a write operation.
> 
> malloc() takes the number of bytes to allocate as size_t, but the
> calculation of the global bin index idx is done via
> malloc_largebin_index() which takes as parameter and calculates
> internally with unsigned int. This leads, for large allocations, to a
> truncation of the value and consequently to the idx being wrongly
> calculated.
> 
> idx is an index into the bins which are sorted in ascending order of
> size range of its including chunks (e.g. 8-16, 16-32, 32-64,...).
> The malloc() algorithm depends on the idx being calculated such that
> we begin searching only at a bin whose chunks are always large enough
> to include the memory size to be allocated (nb).
> 
> If the idx is too small (as can happen due to the described integer
> overflow), this code will lead to a write to a wrong
> address (remainder->bk resp. remainder->fd) (lines from malloc.c):
> 
> 1086    size = chunksize(victim);
> 1087
> 1088    /* We know the first chunk in this bin is big enough to use. */
> 1089    assert((unsigned long)(size) >= (unsigned long)(nb));
> 
> 1108    remainder = chunk_at_offset(victim, nb);
> 
> 1111    remainder->bk = remainder->fd = unsorted_chunks(av);
> 
> The chunk victim should normally be from a bin of a range where each
> chunk is at least of the size nb. Since it's not, its size may be
> smaller than nb. With assertions enabled the assertion in 1089 would
> fail. Without assertions we add nb as an offset to the chunk but since
> the size of the chunk is a lot smaller than nb, this will point to an
> address somewhere else.
> 
> Signed-off-by: Marcus Haehnel <marcus.haehnel@kernkonzept.com>
> ---
>  libc/stdlib/malloc-standard/malloc.c | 10 +++++-----
>  1 file changed, 5 insertions(+), 5 deletions(-)
> 
> diff --git a/libc/stdlib/malloc-standard/malloc.c b/libc/stdlib/malloc-standard/malloc.c
> index cecea87ecf..e51bc6610c 100644
> --- a/libc/stdlib/malloc-standard/malloc.c
> +++ b/libc/stdlib/malloc-standard/malloc.c
> @@ -29,7 +29,7 @@ __UCLIBC_MUTEX_INIT(__malloc_lock, PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP);
>  struct malloc_state __malloc_state;  /* never directly referenced */
>  
>  /* forward declaration */
> -static int __malloc_largebin_index(unsigned int sz);
> +static int __malloc_largebin_index(unsigned long sz);
>  
>  #ifdef __UCLIBC_MALLOC_DEBUGGING__
>  
> @@ -755,10 +755,10 @@ static void* __malloc_alloc(size_t nb, mstate av)
>    Compute index for size. We expect this to be inlined when
>    compiled with optimization, else not, which works out well.
>  */
> -static int __malloc_largebin_index(unsigned int sz)
> +static int __malloc_largebin_index(unsigned long sz)
>  {
> -    unsigned int  x = sz >> SMALLBIN_WIDTH;
> -    unsigned int m;            /* bit position of highest set bit of m */
> +    unsigned long  x = sz >> SMALLBIN_WIDTH;
> +    unsigned long m;            /* bit position of highest set bit of m */
>  
>      if (x >= 0x10000) return NBINS-1;
>  
> @@ -776,7 +776,7 @@ static int __malloc_largebin_index(unsigned int sz)
>  	   S. Warren Jr's book "Hacker's Delight".
>  	   */
>  
> -	unsigned int n = ((x - 0x100) >> 16) & 8;
> +	unsigned long n = ((x - 0x100) >> 16) & 8;
>  	x <<= n;
>  	m = ((x - 0x1000) >> 16) & 4;
>  	n += m;
> -- 
> 2.47.1
> 
> _______________________________________________
> devel mailing list -- devel@uclibc-ng.org
> To unsubscribe send an email to devel-leave@uclibc-ng.org
>