[PATCH] xdr_array and calloc security fix

[PATCH] xdr_array and calloc security fix

[Jakub Jelinek]

Hi!

2002-08-02  Jakub Jelinek  <jakub@redhat.com>

	* malloc/malloc.c (public_cALLOc): Check for overflow on
	multiplication.
	* sunrpc/xdr_array.c (xdr_array): Likewise.
	* sunrpc/rpc/types.h (mem_free): Add comment.
	Patch by Solar Designer <solar@openwall.com>.

--- libc/malloc/malloc.c.jj	2002-06-21 11:37:55.000000000 +0200
+++ libc/malloc/malloc.c	2002-08-02 00:58:16.000000000 +0200
@@ -3452,16 +3452,23 @@ public_cALLOc(size_t n, size_t elem_size
 {
   mstate av;
   mchunkptr oldtop, p;
-  INTERNAL_SIZE_T sz, csz, oldtopsize;
+  INTERNAL_SIZE_T bytes, sz, csz, oldtopsize;
   Void_t* mem;
   unsigned long clearsize;
   unsigned long nclears;
   INTERNAL_SIZE_T* d;
-
   __malloc_ptr_t (*hook) __MALLOC_PMT ((size_t, __const __malloc_ptr_t)) =
     __malloc_hook;
+
+  /* size_t is unsigned so the behavior on overflow is defined.  */
+  bytes = n * elem_size;
+  if (bytes / elem_size != n) {
+    MALLOC_FAILURE_ACTION;
+    return 0;
+  }
+
   if (hook != NULL) {
-    sz = n * elem_size;
+    sz = bytes;
     mem = (*hook)(sz, RETURN_ADDRESS (0));
     if(mem == 0)
       return 0;
@@ -3473,8 +3480,7 @@ public_cALLOc(size_t n, size_t elem_size
 #endif
   }
 
-  /* FIXME: check for overflow on multiplication.  */
-  sz = n * elem_size;
+  sz = bytes;
 
   arena_get(av, sz);
   if(!av)
--- libc/sunrpc/rpc/types.h.jj	2001-06-25 10:34:46.000000000 +0200
+++ libc/sunrpc/rpc/types.h	2002-08-02 00:59:16.000000000 +0200
@@ -58,6 +58,10 @@ typedef unsigned long rpcport_t;
 
 #include <stdlib.h>		/* For malloc decl.  */
 #define mem_alloc(bsize)	malloc(bsize)
+/*
+ * XXX: This must not use the second argument, or code in xdr_array.c needs
+ * to be modified.
+ */
 #define mem_free(ptr, bsize)	free(ptr)
 
 #ifndef makedev /* ie, we haven't already included it */
--- libc/sunrpc/xdr_array.c.jj	2002-02-28 12:32:13.000000000 +0100
+++ libc/sunrpc/xdr_array.c	2002-08-02 01:00:39.000000000 +0200
@@ -45,6 +45,7 @@ static char sccsid[] = "@(#)xdr_array.c 
 #include <rpc/types.h>
 #include <rpc/xdr.h>
 #include <libintl.h>
+#include <limits.h>
 
 #ifdef USE_IN_LIBIO
 # include <wchar.h>
@@ -81,7 +82,11 @@ xdr_array (xdrs, addrp, sizep, maxsize, 
       return FALSE;
     }
   c = *sizep;
-  if ((c > maxsize) && (xdrs->x_op != XDR_FREE))
+  /*
+   * XXX: Let the overflow possibly happen with XDR_FREE because mem_free()
+   * doesn't actually use its second argument anyway.
+   */
+  if ((c > maxsize || c > UINT_MAX / elsize) && (xdrs->x_op != XDR_FREE))
     {
       return FALSE;
     }

	Jakub

Re: [PATCH] xdr_array and calloc security fix

[Ulrich Drepper]

Jakub Jelinek wrote:

> 2002-08-02  Jakub Jelinek  <jakub@redhat.com>
> 
> 	* malloc/malloc.c (public_cALLOc): Check for overflow on
> 	multiplication.
> 	* sunrpc/xdr_array.c (xdr_array): Likewise.
> 	* sunrpc/rpc/types.h (mem_free): Add comment.

I've applied the patch.  Thanks,

-- 
---------------.                          ,-.   1325 Chesapeake Terrace
Ulrich Drepper  \    ,-------------------'   \  Sunnyvale, CA 94089 USA
Red Hat          `--' drepper at redhat.com   `------------------------

Re: [PATCH] xdr_array and calloc security fix

[Wolfram Gloger]

Hi,

> +  /* size_t is unsigned so the behavior on overflow is defined.  */
> +  bytes = n * elem_size;
> +  if (bytes / elem_size != n) {
> +    MALLOC_FAILURE_ACTION;
> +    return 0;
> +  }

This is of course correct, but some (long) time ago I've measured that
the cost for the division is quite noticeable, for say, the very
common calloc(1, small_size).

I've given up on being able to do this fast _and_ portably.

Do we already have some system-specific mechanism to detect the rare
overflow case for a 32bit-multiplication without having to perform a
division?

Regards,
Wolfram.

Re: [PATCH] xdr_array and calloc security fix

[Ulrich Drepper]

Wolfram Gloger wrote:

> Do we already have some system-specific mechanism to detect the rare
> overflow case for a 32bit-multiplication without having to perform a
> division?

It should be possible to have something like

   ((a | b) > (a * b))

for unsigned values.  I'm not 100% sure, though.


-- 
---------------.                          ,-.   1325 Chesapeake Terrace
Ulrich Drepper  \    ,-------------------'   \  Sunnyvale, CA 94089 USA
Red Hat          `--' drepper at redhat.com   `------------------------

Re: [PATCH] xdr_array and calloc security fix

[Ulrich Drepper]

Ulrich Drepper wrote:

> It should be possible to have something like
> 
>   ((a | b) > (a * b))
> 
> for unsigned values.  I'm not 100% sure, though.

I mean, this is an approximation which lets us avoid the division in 
many (most?) cases.

-- 
---------------.                          ,-.   1325 Chesapeake Terrace
Ulrich Drepper  \    ,-------------------'   \  Sunnyvale, CA 94089 USA
Red Hat          `--' drepper at redhat.com   `------------------------

Re: [PATCH] xdr_array and calloc security fix

[Jakub Jelinek]

On Fri, Aug 02, 2002 at 02:50:40AM -0700, Ulrich Drepper wrote:
> Ulrich Drepper wrote:
> 
> > It should be possible to have something like
> > 
> >   ((a | b) > (a * b))
> > 
> > for unsigned values.  I'm not 100% sure, though.
> 
> I mean, this is an approximation which lets us avoid the division in 
> many (most?) cases.

Many. a=1 b=2 -> is this overflow?
a=0x6000000 b=64 -> this would signal no overflow, while in fact
it overflowed. Etc.
I think the only way is to put the multiply + check for overflow into some
macro and optimize it per-architecture...

	Jakub

Re: [PATCH] xdr_array and calloc security fix

[Andreas Schwab]

Jakub Jelinek <jakub@redhat.com> writes:

|> On Fri, Aug 02, 2002 at 02:50:40AM -0700, Ulrich Drepper wrote:
|> > Ulrich Drepper wrote:
|> > 
|> > > It should be possible to have something like
|> > > 
|> > >   ((a | b) > (a * b))
|> > > 
|> > > for unsigned values.  I'm not 100% sure, though.
|> > 
|> > I mean, this is an approximation which lets us avoid the division in 
|> > many (most?) cases.
|> 
|> Many. a=1 b=2 -> is this overflow?
|> a=0x6000000 b=64 -> this would signal no overflow, while in fact

But (a > a * b || b > a * b) should work, shouldn't it?

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux AG, Deutschherrnstr. 15-19, D-90429 Nürnberg
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: [PATCH] xdr_array and calloc security fix

[Jakub Jelinek]

On Fri, Aug 02, 2002 at 01:07:53PM +0200, Andreas Schwab wrote:
> Jakub Jelinek <jakub@redhat.com> writes:
> 
> |> On Fri, Aug 02, 2002 at 02:50:40AM -0700, Ulrich Drepper wrote:
> |> > Ulrich Drepper wrote:
> |> > 
> |> > > It should be possible to have something like
> |> > > 
> |> > >   ((a | b) > (a * b))
> |> > > 
> |> > > for unsigned values.  I'm not 100% sure, though.
> |> > 
> |> > I mean, this is an approximation which lets us avoid the division in 
> |> > many (most?) cases.
> |> 
> |> Many. a=1 b=2 -> is this overflow?
> |> a=0x6000000 b=64 -> this would signal no overflow, while in fact
> 
> But (a > a * b || b > a * b) should work, shouldn't it?

No. For a=1 b=2 this will give the correct answer (no overflow), but
for a=0x6000000 b=64 it will give incorrect one (no overflow, while
0x180000000LL certainly doesn't fit into 32-bits (but 0x80000000 is
still bigger than any of the operands).

	Jakub

Re: [PATCH] xdr_array and calloc security fix

[Wolfram Gloger]

> > But (a > a * b || b > a * b) should work, shouldn't it?
> 
> No. For a=1 b=2 this will give the correct answer (no overflow), but
> for a=0x6000000 b=64 it will give incorrect one (no overflow, while
> 0x180000000LL certainly doesn't fit into 32-bits (but 0x80000000 is
> still bigger than any of the operands).

Ok, if we're going to have two comparisions anyway, I'd suggest we
assume at least 32bits and use

a >= 46340 || b >= 46340

(46340 <= sqrt(2^31), if I did my math correctly)
Of course this will detect some cases as overflow which actually
aren't, but that is harmless.

Regards,
Wolfram.

Re: [PATCH] xdr_array and calloc security fix

[Jakub Jelinek]

On Fri, Aug 02, 2002 at 11:57:29AM -0000, Wolfram Gloger wrote:
> > > But (a > a * b || b > a * b) should work, shouldn't it?
> > 
> > No. For a=1 b=2 this will give the correct answer (no overflow), but
> > for a=0x6000000 b=64 it will give incorrect one (no overflow, while
> > 0x180000000LL certainly doesn't fit into 32-bits (but 0x80000000 is
> > still bigger than any of the operands).
> 
> Ok, if we're going to have two comparisions anyway, I'd suggest we
> assume at least 32bits and use
> 
> a >= 46340 || b >= 46340
> 
> (46340 <= sqrt(2^31), if I did my math correctly)
> Of course this will detect some cases as overflow which actually
> aren't, but that is harmless.

Why not 2^32? size_t is unsigned.

So you mean something like:
  bytes = n * elem_size;
  if (__builtin_expect ((a | b) >= 65536, 0)) {
    if (bytes / elem_size != n) {
      MALLOC_FAILURE_ACTION;
      return 0;
    }
  }

(ie. do the division only in the unlikely case)?

	Jakub

Re: [PATCH] xdr_array and calloc security fix

[Wolfram Gloger]

> Why not 2^32? size_t is unsigned.

Yes, however malloc can only handle chunks of a little less than 2^31
currently, so the _int_malloc later will fail anyway...  But that is
ok, having a power of two as the compared value wins against this
micro-optimisation:

> So you mean something like:
>   bytes = n * elem_size;
>   if (__builtin_expect ((a | b) >= 65536, 0)) {
>     if (bytes / elem_size != n) {
>       MALLOC_FAILURE_ACTION;
>       return 0;
>     }
>   }

Hey, nice, avoids the second comparision and ||.  Looks like we have a
winner?

Regards,
Wolfram.

[PATCH] optimize calloc

[Jakub Jelinek]

On Fri, Aug 02, 2002 at 12:13:21PM -0000, Wolfram Gloger wrote:
> > Why not 2^32? size_t is unsigned.
> 
> Yes, however malloc can only handle chunks of a little less than 2^31
> currently, so the _int_malloc later will fail anyway...  But that is
> ok, having a power of two as the compared value wins against this
> micro-optimisation:
> 
> > So you mean something like:
> >   bytes = n * elem_size;
> >   if (__builtin_expect ((a | b) >= 65536, 0)) {
> >     if (bytes / elem_size != n) {
> >       MALLOC_FAILURE_ACTION;
> >       return 0;
> >     }
> >   }
> 
> Hey, nice, avoids the second comparision and ||.  Looks like we have a
> winner?

Ok, here is the patch:

2002-08-03  Jakub Jelinek  <jakub@redhat.com>

	* malloc/malloc.c (public_cALLOc): Only divide if one of arguments
	is bigger than 65535.

--- libc/malloc/malloc.c.jj	2002-08-02 11:47:41.000000000 +0200
+++ libc/malloc/malloc.c	2002-08-03 13:47:50.000000000 +0200
@@ -488,6 +488,9 @@ Void_t *(*__morecore)(ptrdiff_t) = __def
 #endif /* _LIBC */
 #endif /* USE_DL_PREFIX */
 
+#ifndef _LIBC
+#define __builtin_expect(expr, val)	(expr)
+#endif
 
 /*
   HAVE_MEMCPY should be defined if you are not otherwise using
@@ -3466,9 +3469,11 @@ public_cALLOc(size_t n, size_t elem_size
 
   /* size_t is unsigned so the behavior on overflow is defined.  */
   bytes = n * elem_size;
-  if (bytes / elem_size != n) {
-    MALLOC_FAILURE_ACTION;
-    return 0;
+  if (__builtin_expect ((n | elem_size) >= 65536, 0)) {
+    if (bytes / elem_size != n) {
+      MALLOC_FAILURE_ACTION;
+      return 0;
+    }
   }
 
   if (hook != NULL) {


	Jakub

Re: [PATCH] optimize calloc

[Ulrich Drepper]

Jakub Jelinek wrote:

> 2002-08-03  Jakub Jelinek  <jakub@redhat.com>
> 
> 	* malloc/malloc.c (public_cALLOc): Only divide if one of arguments
> 	is bigger than 65535.

I've checked in a slightly changed patch.  We should unnecessarily 
punish 64-bit platforms.

-- 
---------------.                          ,-.   1325 Chesapeake Terrace
Ulrich Drepper  \    ,-------------------'   \  Sunnyvale, CA 94089 USA
Red Hat          `--' drepper at redhat.com   `------------------------