OpenBSD Journal
Home : : Add Story : : Archives : : About : : Create Account : : Login :
Developer Blog: Ray: Multiplication Considered Harmful
Contributed by Ray Lai on Thu Mar 30 07:19:48 2006 (GMT)
from the dept.

Today we'll be talking about the dangers of multiplication integer overflows in C, the type of bug responsible for the OpenSSH hole of 2002.

Integer overflows occur when an operation causes a number grow or shrink out of bounds, resulting in a much smaller or much larger number than expected. For example, a char can only hold 256 values. If two chars are multiplied together, there is a possibility of overflow:

        char a, b;

        a = b = 127;
        a = a * b;      /* overflow */

Because arithmetic is done in code all over the place, adding checks can be very tedious and is often ignored. A common idiom to allocate memory is:

        size_t num, size;
        char *ptr;
        ...
        if ((ptr = malloc(num * size)) == NULL) /* overflow */
                return (NULL);

The multiplication can create a number larger than a size_t can hold, causing an integer overflow. The integer overflow in this case causes less memory to be allocated than the program expects. The program could then take user input and write past the actual small allocation into memory it thinks it owns, causing problems like a generic buffer overflow. This was the idiom used in the OpenSSH hole of 2002, demonstrating the severity of these bugs.

We recommend using calloc(3) whenever allocating multiple objects of the same size. The above code would be written as:

        size_t num, size;
        char *ptr;
        ...
        if ((ptr = calloc(num, size)) == NULL)
                return (NULL);

calloc(3) has checks to make sure the multiplication does not overflow.

Unfortunately there is no safe replacement for realloc(3). To prevent multiplication overflow, a check must be added:

        size_t newsize, num, size;
        char *newptr, *ptr;
        ...
        if (num && size && SIZE_T_MAX / num < size) {
                errno = ENOMEM;
                return (NULL);
        }
        newsize = num * size;
        if ((newptr = realloc(ptr, newsize)) == NULL)
                return (NULL);
        ptr = newptr;

This is a hassle, but it is important to add these safeguards, especially when doing multiplication, which can quickly overflow.

To lessen developer work and simplify code, an xrealloc() function was added to ssh. xrealloc() has a similar API to calloc(3), taking both a num parameter and a size parameter. The above example can be written using xrealloc() as:

        size_t num, size;
        char *newptr, *ptr;
        ...
        if ((newptr = xrealloc(ptr, num, size)) == NULL)
                return (NULL);
        ptr = newptr;

Due to its elegance, this API was also imported for OpenCVS.

For more information, please read a -current malloc(3) man page, which was recently updated with better usage examples.

[topicblog]

<< The Jem Report: Linux supporters fiddle while OpenSSH burns | Reply | Flattened | Expanded | Theo's interview on DaemonNews >>

Threshold: Help

Related Links
more by Ray Lai


  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod 1/11)
by Janne Johansson (130.237.95.193) (jj@inet6.se) on Thu Mar 30 08:06:33 2006 (GMT)
  It might be worth mentioning here that the malloc example can't be checked
inside malloc() since the mul is done (and overflowed) before it is called.

I compiled a simple version of your malloc overflow and the resulting
x86-asm for this [ptr=malloc(a*b);] looks like this just before the call:
movl -28(%ebp), %eax
imull -32(%ebp), %eax
pushl %eax
call malloc

If you could somehow shove a "check for integer overflow" (probably very
cpu-dependant but at least some cpus have such) between the imull and the
pushl+call you could (in theory) find and catch there kinds of errors in
very specific cases.

No, I have no such patch for gcc. 8-(
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod -1/9)
by Grégoire (81.188.2.90) on Thu Mar 30 08:19:34 2006 (GMT)
  Thanks for this explaination. I hope you'll share more like this with us in the future.
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod 8/16)
by veins (81.65.210.118) (veins@skreel.org) on Thu Mar 30 08:37:57 2006 (GMT)
http://lab.skreel.org/
  Nice post :)

I don't know if that's the bug, but there was an integer overflow a few years ago in OpenSSH hidden (caused in some sort) by ... a goto statement. It was hard to catch and very subtile, and in my opinion could be talked about as people tend to use gotos without too much thinking.

I like developers blog entries, I used to read undeadly once in a while (once every two/three months) and now I'm checking it many times a day, it makes the portal look more ... alive :-)
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod 6/8)
by Bernhard Leiner (128.130.39.94) on Thu Mar 30 10:19:37 2006 (GMT)
  Thanks a lot for this! I have wondered how those "integer overflow exploits" work, but always been to lazy to look it up. Now, at least the principle is clear.
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  xrealloc() in the base libc? (mod 9/11)
by Anonymous Coward (134.58.253.130) on Thu Mar 30 11:32:46 2006 (GMT)
  Any chance that this new xrealloc() function will ever make it into the base libc, like strlcpy() and friends?
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Book needed (mod 4/18)
by Anonymous Coward (216.220.225.229) on Thu Mar 30 14:14:28 2006 (GMT)
  I wish some OpenBSD developers (who hate when people start sentences with "I wish...) would write an intro C programming book so people could learn safe programming from the start. Right now, you take a C class and learn all the unsafe practices, and then spend more time trying to unlearn things like strcpy().
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]
      Re: Book needed (3/9) by Anonymous Coward on Thu Mar 30 15:24:10 2006 (GMT)
      Re: Book needed (-3/15) by Anonymous Coward on Thu Mar 30 16:41:36 2006 (GMT)
        Re: Book needed (2/8) by Matthias Kilian on Thu Mar 30 17:08:10 2006 (GMT)
          Re: Book needed (1/7) by Anonymous Coward on Thu Mar 30 19:18:08 2006 (GMT)
          Re: Book needed (0/6) by Anonymous Coward on Fri Mar 31 05:59:31 2006 (GMT)
          Re: Book needed (3/7) by Anonymous Coward on Thu Mar 30 18:05:31 2006 (GMT)
          Re: Book needed (-4/10) by Anonymous Coward on Thu Mar 30 20:02:53 2006 (GMT)
            Re: Book needed (-2/8) by Fábio Olivé Leite on Thu Mar 30 22:29:28 2006 (GMT)
              Re: Book needed (2/6) by Anonymous Coward on Fri Mar 31 02:20:13 2006 (GMT)
                Re: Book needed (-8/10) by Anonymous Coward on Fri Mar 31 02:22:06 2006 (GMT)
                  Re: Book needed (1/11) by Anonymous Coward on Fri Mar 31 18:45:54 2006 (GMT)
        Re: Book needed (2/10) by Anonymous Coward on Thu Mar 30 18:51:29 2006 (GMT)
          Re: Book needed (2/8) by Anonymous Coward on Thu Mar 30 21:40:53 2006 (GMT)
            Re: Book needed (5/9) by Anonymous Coward on Fri Mar 31 02:24:13 2006 (GMT)
              Re: Book needed (-1/7) by Anonymous Coward on Fri Mar 31 03:01:23 2006 (GMT)
              Re: Book needed (-1/11) by Anonymous Coward on Fri Mar 31 07:09:16 2006 (GMT)
                Re: Book needed (2/8) by Anonymous Coward on Fri Mar 31 18:47:45 2006 (GMT)
                    Re: Book needed (0/8) by Anonymous Coward on Fri Mar 31 20:45:08 2006 (GMT)
      Re: Book needed (0/8) by Anonymous Coward on Thu Mar 30 19:59:48 2006 (GMT)
      Re: Book needed (-5/7) by Anonymous Coward on Sat Apr 1 05:24:44 2006 (GMT)
        Re: Book needed (0/6) by Anonymous Coward on Sat Apr 1 13:16:53 2006 (GMT)
          Re: Book needed (0/8) by Anonymous Coward on Sat Apr 1 23:15:27 2006 (GMT)
        Re: Book needed (-1/5) by Robert C. Seacord on Sun Aug 6 15:53:30 2006 (GMT)

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod -3/5)
by Siju Oommen George (59.93.43.15) (sgeorge.ml@gmail.com) on Thu Mar 30 15:30:32 2006 (GMT)
  I should really really thankyou for these real life explanations with examples. It goes a long way educating the OpenBSD users like me who would like to learn more about these things but find puzzled on where to begin.

Of course reading code alone doesn't help me at this point but explanations like this do real help. I am looking forward to find more of these type of articles on Undeadly :-) Once again Thanks a million:-) and Good Luck :-)
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod -4/10)
by Corentin (81.56.152.193) on Thu Mar 30 17:20:25 2006 (GMT)
 
char a, b;

a = b = 127;
a = a * b;      /* overflow */
There is an additionnal problem with this code; a plain char can be handled by the compiler either as a signed type or as an unsigned type. signed char and unsigned char should be used instead to store small integer values (IMHO, uint8_t is even better).
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod 0/10)
by Anonymous Coward (63.237.125.201) on Thu Mar 30 21:52:50 2006 (GMT)
  Great article! Intelligent commentary. How could anything less be expected of the OpenBSD community?

Hey, do I smell a new project on the way?

OpenC?
lib-openc?
occ?
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod -2/8)
by Anonymous Coward (67.149.82.140) on Thu Mar 30 23:10:12 2006 (GMT)
  Is it possible to tell GCC to build binaries such that if an overflow occurs then the program should segfault (or do something similar)? If this were possible then it would be immediately clear where these problems exist. Any thoughts?
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod -3/9)
by Willy Wombat (195.8.190.164) on Fri Mar 31 13:09:45 2006 (GMT)
  Just out of interest, why is size tested for non-zero in this statement?

if (num && size && SIZE_T_MAX / num < size) {
errno = ENOMEM;
return (NULL);
}

num has to be tested to prevent possible division by zero.

Is size checked for zero just to avoid the (relatively) expensive division and comparison (since if size is zero, the multiplication won't overflow)?
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod -11/15)
by paldium (84.129.228.47) on Fri Mar 31 19:39:22 2006 (GMT)
  This is a great article, it is always interesting to get more information about these errors that are so easily overlooked.

Although I have a question ...

If I understand this issue the problem arises when the multiplicator (e.g. size) gets out of control. So is there a problem with a code that takes for example the size_t'd variable, increments, and calls realloc then (i.e. step by step allocating)? Running such a program would nearly allocate 4 gb of memory (if I am correct) and that's much more my system could handle (also the default ulimit would prevent that).

An example of this would be strfile (src/games/fortune/strfile/strfile.c), which uses a variable of type long for the counter (signed, but I would have to use more bytes I could allocate with malloc). Is this approach "safe" enough?
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

  Re: Developer Blog: Ray: Multiplication Considered Harmful (mod 1/7)
by Andrew Reilly (141.168.4.160) on Sat Apr 1 06:50:59 2006 (GMT)
  I like the xrealloc extension, to match calloc, but I hope that you're not testing for overflow that way. Division is generally really slow.

The main problem is that multiplication naturally requires type expansion, but C doesn't work that way. Many processors do allow expanding multiplies, though, and their C compiler will recognize the idiom (for example) int64_t result = (int64_t) a * (int64_t) b; where a and b are int32_t, for example, and generate the single 32 x 32 -> 64 multiply instruction that will produce the right result.

Doing an expanding multiply and then checking to see if the result will still fit into a size_t will almost certainly be faster than the division-based test in the example.

There is less complete coverage for 64 x 64 --> 128 bit multiplies in most processors, but a bit of code to do that using 32 x 32 --> 64 multiplies will still probably be faster than a division.

Of course, in the case of something like OpenSSL or OpenSSH, you have to ask if there weren't, perhaps, low-cost sanity checks that could be made on the arguments before the multiply? I doubt that either really has to deal with a vast number of memory-busting objects, such that there would be any fear of this overflow even being approached.

Just another note: C defines unsigned types (size_t, usually) to wrap around on overflow, but signed types have undefined behaviour on overflow, and some processors (most) allow signed integer overflows to be trapped or tested. That doesn't help you much in C, but other languages, like Ada, let you catch those.
  [ Show thread ] [ Reply to this comment ] [ Mod Up ] [ Mod Down ]

[ Home | Add Story | Archives | Polls | About ]

Copyright © 2004-2008 Daniel Hartmeier. All rights reserved. Articles and comments are copyright their respective authors, submission implies license to publish on this web site. Contents of the archive prior to April 2nd 2004 as well as images and HTML templates were copied from the fabulous original deadly.org with Jose's and Jim's kind permission. Some icons from slashdot.org used with permission from Kathleen. This journal runs as CGI with httpd(8) on OpenBSD, the source code is BSD licensed. Search engine is ht://Dig. undeadly \Un*dead"ly\, a. Not subject to death; immortal. [Obs.]