OpenBSD Journal

Developer Blog: Ray: Multiplication Considered Harmful

Contributed by Ray Lai on 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.

(Comments are closed)


Comments
  1. By Janne Johansson (130.237.95.193) jj@inet6.se on

    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-(

    Comments
    1. By Otto Moerbeek (213.84.84.111) otto@drijf.net on

      Well to be frank, this is a stupid idea.

      Who is saying the multiplication is done right before the call to malloc?

      What if some other, overflowing but harmless computation is done before the call to malloc.

      etc etc etc

      Comments
      1. By Igor Sobrado (156.35.26.1) on

        Please, be more polite in your answers.

        Janne Johansson has observed that a compiler could add some checks to the assembler code in a processor-dependant manner. Ok, perhaps it is not easy to implement, nor portable and, indeed, there is a risk that a previous arithmetic operation can set the overflow flag (OF) on the flags register (again, x86-centric); but it is a good approach even if it is not perfect.

        That is not an "stupid" idea, at most it can be a not perfect one. But at least he proposed an idea, an interesting one.

        Comments
        1. By Anonymous Coward (128.171.90.200) on

          I'm sorry but the idea is just wrong.

          It is next to impossible for a compiler to be able to tell when an integer overflow is going to take place, there are so many corner cases which the compiler would not know about and so many instances where a legitimate overflow could be prevented from happening.

          Comments
          1. By Igor Sobrado (156.35.192.2) on

            I fully agree with you.

            It is not only impossible for a compiler to be able to detect if these events will happen but also to know the consequences of these events. An overflow can be a legitimate (but certainly ugly) event used by programmers---we cannot consider it an error in all cases. The only example I remind now is the ability of an arithmetic overflow to time wrap a Unix machine when its security level does not allow a legitimate time backward, but certainly it can be useful when coding real algorithms too.

            An overflow just before a memory allocation process is not a valid reason for believing that there is a security problem related with the call to malloc()---I agree with Otto Moerbeek on this point. Even worse, an overflow that provokes a wrong memory allocation can happen hundreds (thousands!) instructions before the call to malloc() and remain undetected by the compiler.

            I was only saying that, perhaps, the way Mr. Moerbeek replied to the post of Janne Johansson can make the author of the first post to get offended.
            He did a fine observation about the impossibility of detecting all arithmetic overflows that can make a memory allocation to fail and he mentioned that some overflows happening just before a memory allocation can be harmless ones. Sometimes, arithmetic overflows are legal operations used by programmers too.

            Cheers.

            Comments
            1. By Janne Johansson (130.237.95.193) jj@inet6.se on

              "I was only saying that, perhaps, the way Mr. Moerbeek replied to the post of Janne Johansson can make the author of the first post to get offended."

              I wasn't. I just thought out loud. It was an observation I made that it would be theoretically possible in this miniexample to find a spot (not necessarily _the_ spot) where such a test could be made.

    2. By Stefan (131.188.24.2) on http://www.rommel.stw.uni-erlangen.de/~guebbbi/

      Of course it's done before malloc is called. It's a C Compiler and does call by value, not by name. That is why calloc gets its parameters separately so they can by savely multiplied inside. You also mustn't shove in some checks, because it's C. Arithmetik is specified to be modular! What you can do is writing a inline function that sets errno if an overflow occures.

      int a=mul__size_t_size_t(b*c);

      if (errno==OVERFLOW) {
      //error handling
      }
      else {
      //alloc
      }


      But since you cannot overload function or even overload operators this is a hassle, too.

      Comments
      1. By Anonymous Coward (70.179.123.124) on

        #ifdef foo
        #undef foo
        foo()
        {
        /* function body */
        }
        #endif

        Or am I totally wrong here?

        Comments
        1. By Anonymous Coward (72.138.211.134) on

          That isn't overloading the function. That is just replacing a function.

    3. By Roman (169.200.215.15) on

      The way I understand it is that these are primarily runtime issues. The compiler would only be able to type-validate known values at compile time leaving many variables unchecked as they may be set and change during execution. I believe the solution is to be more attentive while coding.

      Someone please correct me if I am wrong.

  2. By Grégoire (81.188.2.90) on

    Thanks for this explaination. I hope you'll share more like this with us in the future.

  3. By veins (81.65.210.118) veins@skreel.org on 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 :-)

  4. By Bernhard Leiner (128.130.39.94) on

    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.

    Comments
  5. By Anonymous Coward (134.58.253.130) on

    Any chance that this new xrealloc() function will ever make it into the base libc, like strlcpy() and friends?

    Comments
    1. By Anonymous Coward (62.252.32.11) on

      Or better yet, can you just post the patch/code?

      Comments
      1. By Anonymous Coward (193.252.148.11) on

        you're a big boy and should be able to look up the cvsweb interface yourself.

        Comments
        1. By Anonymous Coward (128.171.90.200) on

          True, and I could do the patch also.

          Is there a particular reason it didn't make it into libc in the first place ?

    2. By Anonymous Coward (128.151.253.249) on

      The problem with that is that a lot of people define a function called "xrealloc" which behaves like realloc(), but checks the return value for NULL and aborts if the allocation failed. See <a href="http://www.comp.nus.edu.sg/~malin/materials/C_lib/libc_734.html">this</a>. I believe there is a package called "publib" that includes this function.

      So... If libc and others use an "xrealloc" which takes 3 args and some other software uses one with 2 args... You can see where that might be problematic.

      Comments
      1. By Anonymous Coward (128.171.90.200) on

        so can we rename it ?

        Comments
        1. By Anonymous Coward (70.31.84.121) on

          crealloc() kinda seems logical doesn't it? Or recalloc()?

  6. By Anonymous Coward (216.220.225.229) on

    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().

    Comments
    1. By Anonymous Coward (84.188.234.181) on

      Another Book to sell.. and I would buy it. :)

    2. By Anonymous Coward (70.124.65.113) on

      The first question you should ask yourself is, "do I really need to write this in C?" C is basically portable assembly, great for writing kernels but not necessarily the best choice for an ordinary application. If you can do what you want in a higher level language with automatic memory management, safe arithmetic, array bounds checking, etc. then why do it in C?

      This point of view is unpopular with those who think it's a sign of weakness as a programmer, but you only have to read the bugtraq archives to see how well that philosophy works.

      Comments
      1. By Paladdin (213.97.233.52) on

        As you say, it all depends on how much C is needed for a particular programmer. In my case, as mainly developing for limited resources embedded systems and Palms, I think this kind of book would be a Good Thing(tm) :) Although I'm absolutely happy reading little code samples from OpenBSD kernel to learn basic programming style.

        Not to be interpreted to be a flame -please!- but I also consider that learning low level programming is a must for any wannabe programmer. It helps to develop machine-like concepts that makes coders more ease on resources an so on. This new trend of let's-go-code-like-we-speak, with incredible layers of abstraction, suposses a big expend on resources and, albeit new computer are powerful, that doesn't mean we have to be bad coders -yes, I make a difference between a bad programmer, and a bad coder-. Maybe I say this because I'm tired of look for .NET platform bugs these days... but I'm really dissapointed with modern heavily overengineered languages.

      2. By Matthias Kilian (84.134.29.123) on

        Well, what language then?

        Java? Not free, not portable, incredibly bloated.

        Haskell? Doesn't (yet) run on enough platforms. And it's a little bit bloated, too.

        Perl, Python, Ruby, Lua etc.? May be, but they're scripted languages, are loosely type checked, and I want to be able to create BLOBS ;-)

        Lisp or Scheme? Hmm. As with the above-mentioned scripted languages, there's static type checking missing.

        YMMV.

        Comments
        1. By Anonymous Coward (70.124.65.113) on

          Well, you don't really explain your criteria except that you like static typing, but one language you leave out is Ada. A free compiler exists and if you can get past the bad (and undeserved) reputation, Ada is a pretty decent language.

        2. By Anonymous Coward (71.255.101.25) on

          Lisp compilers exist for many platforms. The real problem with using a Lisp for a any kind of reasonably low-level programming is that the lisp runtime slows things down considerably unless you have some pretty serious dedicated hardware to handle the basic functions (a la the LispMs of the eighties). Of course, this is the sort of thing that becomes less and less of a problem as computers get faster and faster, but really, who wants their tools or library to take 50-100% longer to do anything if they don't have to?

      3. By Ray (192.193.221.141) on http://cyth.net/~ray/

        It’s not just a problem with C, though. There’s a certain mindset that is required to code securely. A person needs to think of the limitations of the system and figure out if there are any exceptional cases that need to be taken care of.

        int we_need_this_much_space;
        
        we_need_this_much_space = getnumfromuser();
        while (we_need_this_much_space-- != 0)
        	allocate_more_space();
        

        This code (translated to Java or whatever language) has bugs no matter what language you use. Is it a limitation of the language that the programmer didn't know about negative numbers?

        Comments
        1. By Anonymous Coward (70.124.65.113) on

          I completely agree with your point -- yes, writing secure code in any language takes a cautious, paranoid mindset. Especially, untrusted input must be validated, no doubt about that.

          But it's just a fact that some languages completely eliminate certain classes of errors (barring, of course, language implementation errors), and often provide better semantics for handling the errors that do occur. The most common result when something bad or unexpected happens in C is undefined behavior: the program will likely just keep running, only in an incorrect state. And the C standard is chock full of such corner cases, so many that even veteran C programmers slip up now and then (often with type conversions or pointer arithmetic).

          For example, in Lisp an integer overflow attack is just plain impossible.

          (+ a b)
          will either produce the proper sum, or signal an error if the operands have the wrong type (i.e. they're not numbers). In no case will you simply get the wrong answer. In the most extreme cases there's not enough memory to represent the sum, and again you get an error signaled.

        2. By Anonymous Coward (128.171.90.200) on

          I'm not sure you're example is true for Java, unless you are using JNI, at which point you are back at C.

          Comments
          1. By Fábio Olivé Leite (15.227.249.72) on

            Actually, given that there are no unsigned numbers in Java, that example applies quite directly to it. If the function could be made to return an unsigned number, you'd be safe from allocating 2 billion more (as in more than the ones you'd already allocate if the user had sent you INT_MAX) objects before you hit zero. :)

            Comments
            1. By Anonymous Coward (128.171.90.200) on

              Ah, but you cannot allocate memory directly in Java.

              If you had a loop that created a billion objects, you would be more likely hit an OutOfMemoryException and exit.

              This is of course, unless you use JNI.

              Comments
              1. By Anonymous Coward (128.171.90.200) on

                This is not to say there isn't a possible integer overflow bug in the JVM that could be exploited from inside a Java class.

              2. By Ray (199.67.140.83) ray@ on http://cyth.net/~ray/

                So you’re saying that, in Java, running out of memory when a negative number is input is not a bug?

                Comments
                1. By Anonymous Coward (128.171.90.200) on

                  If the programmer *assumes* that the number will always be positive, or always within an acceptable range, then it is a bug.

                  It is worth pointing out that by default, you will run out of memory in a Java aplication within 64Mb, the JVM will then kill the application, so the you can get a denial of service for the application. The possibility for exploiting this functionality is greatly reduced by comparison to applications that run natively.

      4. By Anonymous Coward (71.201.247.141) on

        It may come as a shock to you, but some people actually like programming in C. For me, it is a lot of fun, and that is the main reason why I choose C instead of some other (crippled) language.

      5. By djm@ (203.217.30.86) on

        What bugtraq posts are you referring to? The constant stream of XSS/SQL injection attacks on applications written in supposedly "safe" languages?

        We write operating system components, therefore we use C.

        Comments
        1. By Anonymous Coward (70.124.65.113) on

          My original comment was directed not to OpenBSD developers, of course, but to somebody wanting to learn "safe" C programming.

          As to bugtraq, you only need to google for buffer/integer overflows, there's no shortage of examples. "PHP sucks too" isn't exactly a compelling defense of C's failings.

          I don't know whether to find it amusing or sad that the same problems will probably still be around when 32-bit time_t overflows (how's that for irony).

          Comments
          1. By Anonymous Coward (70.179.123.124) on

            How about this: there are times when it's appropriate to write C, and we would all be better off if people knew how to do it correctly when they need to.

            Hell, what are other languages written in? I do believe that it's C. If people can't write C correctly, they can't create a "safe" language.

            The argument you're making is pretty self-defeating; unless you can make perl/python/ruby/Visual Basic into a working interpreter.

            Comments
            1. By Anonymous Coward (128.171.90.200) on

              Although C can be written in C, GCC is written in a variety of languages.

            2. By Anonymous Coward (70.31.84.121) on

              There are jvms written in java. It hurts your head to think about it, but they do it. All it requires is a small bootstrap to get the jit going and then it can compile the rest of itself.

              Comments
              1. By Anonymous Coward (128.171.90.200) on

                Most JVMs are written in Java once you get above Object, Object tends to be written in C.

                Comments
                1. By tedu (69.12.168.114) on

                  the sun jvm, which i would wager is what a lot of people are using, is written in c++.

                  Comments
                  1. By Anonymous Coward (128.171.90.200) on

                    You are probably right, it probably is C++ and not C, everything below Object is anyway. Everything above *should* be Java.

    3. By Anonymous Coward (128.171.90.200) on

      There are books available, just not OpenBSD ones. Wether or not they are any good I couldn't tell you.

    4. By Krunch (139.165.82.240) on http://krunch.be/

      Wheeler is not an OBSD programmer (AFAIK) but his book seems to cover what you are looking for (and it's available online for free).
      http://www.dwheeler.com/secure-programs/

    5. By Anonymous Coward (128.151.92.148) on

      If you know C well, you know why strcpy() is a bad idea for most usage. I don't think the phrase "unlearn strcpy()" makes any sense; the manpages on all systems, as well as OpenBSD's linker, will tell you to check out strncpy() or strlcpy() anyway. So, a beginning programmer looks at the documentation or sees those warnings, and then instead of using strcpy() looks up the safer alternatives. How is this "unlearning"? strcpy(), actually, I think, would have it's (very limited) place: namely, those very few cases in which you are 100% certain your source data is at most the size of your buffer. Like this:

      size_t len = strlen(str);
      char *buf = malloc(len+1);
      if(len != SIZE_T_MAX) strcpy(buf, str); // this should be safe.

      Comments
      1. By Anonymous Coward (84.166.98.208) on

        You first should check, if malloc() returns an error / if malloc() allocated enough space. Then it looks safe... :-)

      2. By tedu (71.139.182.193) on

        -5 points for not using strdup.

        Comments
        1. By Anonymous Coward (128.151.92.148) on

          Yeah, I know about strdup. And the null pointer check. I was just trying to give a trivial example. ;-)

    6. By tedu (69.12.168.114) on

      "Secure Coding in C and C++" by Robert Seacord is probably the best book i've seen, though i've only skimmed it. it's certainly better than the 10 other "how to program real secure" books i've skimmed.

      http://www.amazon.com/gp/product/0321335724/sr=8-1/qid=1144103973/ref=sr_1_1/002-7492060-9752839?%5Fencoding=UTF8

      Comments
      1. By Robert C. Seacord (209.195.148.248) rcs at cert dot org on http://www.cert.org/books/secure-coding/

        > "Secure Coding in C and C++" by Robert Seacord is probably the best book i've seen, though i've only skimmed it. it's certainly better than the 10 other "how to program real secure" books i've skimmed.
        >
        > http://www.amazon.com/gp/product/0321335724/sr=8-1/qid=1144103973/ref=sr_1_1/002-7492060-9752839?%5Fencoding=UTF8

        Thanks, it is probably the best book I've ever written. 8^)

        BTW, if you are interested in this integer stuff the Integer Chapter from the book is available as a free download from http://www.cert.org/books/secure-coding/
        and elsewhere.

        We are also starting an effort to create a secure coding standard for C and C++. If you check out http://www.cert.org/secure-coding/ after September 1st we should have our Wiki up with some initial rules and recommendations.

        rCs

  7. By Siju Oommen George (59.93.43.15) sgeorge.ml@gmail.com on

    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 :-)

  8. By Corentin (81.56.152.193) on

    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).

    Comments
    1. By Anonymous Coward (213.196.253.42) on

      and characters are "int" (in C) anyway, not "char" (or one of
      the signed/unsigned char types).

      Comments
      1. By Otto Moerbeek (213.84.84.111) otto@drijf.net on Otto Moerbeek

        char vs int in C is much more complex than that.
        <p>
        Taking shortcuts in this is dangarous.

  9. By Anonymous Coward (63.237.125.201) on

    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?

    Comments
    1. By Nate (65.95.124.5) on

      There is already an OpenBSD libc, you're free to use it on other systems.

      The C language has already been extended with several OpenBSD-created functions, most of them are in-place within real Unix systems, only glibc ignores these enhancements.

      kencc may some day replace the gcc used in OpenBSD, but that is a ways away unless you've got some giant corporate sponsorship up your sleeve.

  10. By Anonymous Coward (67.149.82.140) on

    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?

    Comments
    1. By Sam Chill (68.53.209.134) on

      Intersting, this would be similar to the rewritting of malloc(3) in the 3.7 release to make use of mmap(2).

    2. By Anonymous Coward (128.171.90.200) on

      You cannot get GCC to do it, it's very much a runtime thing.

    3. By Anonymous Coward (70.179.123.124) on

      I'm not sure that this is possible in the way you want; after all, how is the program to handle it? Different programs need different error-handling semantics. An error output to STOUT may be fine as a default, but what processing needs to be rolled back?

      There are too many (no pun intended) variables to make it a standard part of C; better to become aware of and avoid the problem as a programmer.

      In a perfect world, yes a compiler could do so.
      In a perfect world, the only function I would ever have to call is do_shit(stuff); and everything would be taken care of.

    4. By Corentin (81.56.152.193) on

      I do not think it is very easy to detect such a class of run-time errors statically (at compile time). It should be easier using dynamic analysis (with a tool such as Valgrind[1]).

      [1] http://www.valgrind.org

      Comments
      1. By Anonymous Coward (128.171.90.200) on

        Valgrind is pretty cool, but unfortunatly not very portable ( though I am pleased to see they have a PPC port of it. )

        Comments
        1. By Anonymous Coward (128.151.92.148) on

          Recently, I found a bug in some third party software that was exposed by OpenBSD's malloc, but was not reproducable on Linux. I submitted upstream bug reports. They couldn't reproduce it. I told them to use valgrind, which exposed the problem, and it is now fixed upstream.

          Valgrind is great. Back when I used Linux, it helped me out of numerous binds and bizarre memory corruption bugs. I'd like to see it on OpenBSD. Last time I checked it doesn't run on it; am I right that that is still the case?

          Comments
          1. By Corentin (81.56.152.193) on

            You are right.
            Porting Valgrind to a new operating system and/or hardware architecture is a complex task.

    5. By Anonymous Coward (70.31.84.121) on

      Thoughts? Just that this is the exact same idea as the first post.

    6. By Andy (82.44.215.41) on

      Actually it is feasible to implement behaviour in GCC that would allow for overflow checking. It is NOT necessarily a good idea though.

      It would need to wrap specific operations that you were checking, hypothetically as shown below.. note it is not safe to plug in overflow detection using __asm__ following a multiplication operation because you cannot guarantee the flag state (because you can't guarantee what code is generated) between your C statement and the __asm__ block.. This would have to take the form of a patch to gcc and maybe binutils to specifically generate the overflow checks integrated with the compiler's object generation.

      /* This feature does NOT exist in gcc (or any other known C compiler) so don't bother trying it */
      #pragma OVERFLOW_HANDLER_ON
      a *= b;
      #pragma OVERFLOW_HANDLER_OFF


      On x86 this could generate the JO (Jump on Overflow) instruction... potentially like this..

      (a *= b;)
      MUL EBX
      JO OverFlowHandler


      most architectures do support overflow checks by a flag in this manner. This, however, would add a lot of additional and stuff to the C implementation that has not been ratified as a standard so is quite undesirable from that point of view. - after all if the feature doesn't exist do you forget about the necessary checks on all the systems that do not support it?? I think not - this ends up fixing the issue on some systems and not on others and an issue fixed on the primary system can be forgotten but nevertheless become a vulnerability and source of vector for other systems. - think like a 'cracker' your best birthday present is a vulnerability that people think is fixed but keeps cropping up because of implementation specifics.

      Furthermore implementing overflow detection as a default on such operations is definitely a no-no because some code specifically requires overflow conditions and discards overflowed information. Some checksumming functions for example.

      Comments
      1. By Anonymous Coward (128.171.90.200) on

        It is possible to do what you say, but unfortunatly how do you know which parts of the program to wrap ? The overflow could be completely legitimate and you would get a false positive, or if you only do it in certain places like function calls, how do you know that the overflow didn't occur previously ?

        Secondly it IS possible to do this in a portable way, we don't need to rely on a processor instruction, as we are wrapping, a bit of programming logic will suffice. This is how ProPolice works.

        Comments
        1. By Andy (82.44.215.41) on

          ok,

          Maybe you missed my major objection to this. If our developers originate a project and deal with potential exploits in this manner it buries the vulnerability.

          Comments
          1. By Anonymous Coward (128.171.90.200) on

            I think I my previous reply may have been posted as a respone to the wrong comment, sorry :(

            Anyway ..

            Would it bury the vulnerability ? or would it highlight it ?

      2. By Anonymous Coward (68.238.226.49) on

        Here's the problem. I think it's an interesting idea, and it might be nice if it were a required part of some C standard, but basically, the feature would have to be optional in order to allow legitimate overflows (like -1 + 1), and consequently you'd have to turn it on explicitly. But, the sort of people who understand why using such a compiler directive (or whatever the mechanism is) is a necessary security precaution are the same people who are cautious enough to do it in a platform-independent way if the directive were not available. The people who don't know why it's necessary won't use it, in the unlikely event they realize such a feature is available. The only way around this would be to make the feature always ON, and turn it OFF with an explicit directive. But that is just going to piss off the competent developers so much that they'll just tell people who have problems compiling programs with the new compiler that it's the compiler's fault and they should get one that doesn't mess with code so much. If C programmers weren't quite so picky about the language doing the obvious thing, even when the obvious thing is also obviously wrong, they wouldn't be using C in the first place.

        Comments
        1. By Andy (82.44.215.41) on

          Sure, I agree with the point that you make, however, overflow checks are computationally expensive without the ability to query the overflow flag. Maybe the example below isn't quite the most efficient example but even something far more efficient than this will still be inefficient compared to a simple overflow flag test... hmm, maybe it would be nice to see an Ansi C revision supporting an overflow flag test directive. I guess the next question is what would be a suitable means of selecing a vector for an overflow operation. My previous posting with the #pragma suggestion didn't take that into account.

          signed short safemul(signed short x, signed short y)
          {
          signed short r;
          signed short rr,xx,yy;
          r=x*y;
          /* Make negatives positive for overflow check */
          if (0>x) xx=-x; else xx=x;
          if (0>y) yy=-y; else yy=y;
          rr=xx*yy;
          if ( rr < yy || rr < xx ) {
          printf("Overflow occured\n");
          } else {
          printf("No overflow occured\n");
          }
          return(r);
          }

          Comments
          1. By Andy (82.44.215.41) on

            of course there's a logic flaw in this... damn sometimes it would be nice to be able to edit your posts :)

          2. By Anonymous Coward (72.154.140.130) on

            How about this instead?

            signed short safemul(signed short x, signed short y) {
                 signed short r = x * y;
                 if(r / x != y || r / y != x) {
                      puts("Overflow occured");
                 } else {
                      puts("No overflow occured");
                 }
                 return r;
            }

            Comments
            1. By Anonymous Coward (128.171.90.200) on

              Making the compiler fix it seems like a bad idea.

              I think the best you can do is issue a warning.

  11. By Willy Wombat (195.8.190.164) on

    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)?

    Comments
    1. By Anonymous Coward (195.68.31.231) on

      num is already tested.

      if num equals zero, the if condition is false.

    2. By tedu (71.139.182.193) on

      what type of object are you allocating that is 0 bytes in size?

      Comments
      1. By Otto Moerbeek (62.140.137.125) otto@drijf.net on Otto Moerbeek

        The developer of this piece of code decided that allocating objects of size 0 must be allowed, making the semantics the same as malloc(0).

        POSIX marks this as undefined (either return NULL ora unique pointer), but I think it is wise to have malloc and calloc act the same when trying to allocate 0 bytes.

        Comments
        1. By Otto Moerbeek (213.84.84.111) otto@drijf.net on

          Oh, but I forgat to mention, AFAIKS, the "&& size" is redundant.

    3. By djm@ (203.217.30.86) on

      No, it is to avoid a potential divide-by-zero error

      Comments
      1. By Anonymous Coward (66.11.66.41) on

        Its not dividing by size, its dividing by num.

  12. By paldium (84.129.228.47) on

    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?

    Comments
    1. By Ray (199.67.140.83) ray@cyth.net on http://cyth.net/~ray/

      The malloc operations in strfile.c look pretty bad. Please, nobody code like that!

      Incremental allocation as you described would be very inefficient and certainly doesn’t solve any problems.

      Comments
      1. By Ray (199.67.138.83) ray@cyth.net on http://cyth.net/~ray/

        To further explain, incremental allocation won’t solve anything because if the space you are trying to allocate is too big (due to a miscalculation) it will still run out of memory. It will just happen much slower because you keep calling realloc. (Be aware that if realloc cannot expand the currently allocated space to the new size, realloc will allocate a new block of memory and copy the old contents there. In addition to being slow, I think memory gets fragmented over time (though now that our malloc uses mmap, that may not be the case). Now imagine trying to allocate 4 GB of memory, in 1 KB increments.)

        If the space you are trying to allocate is too small (due to an overflow) and you successfully allocate it, you’re still screwed the moment you try to access the memory you thought you allocated.

        Comments
        1. By paldium (84.129.196.237) on

          Ah, finaly I caught the bug. I just found an example of wrong malloc allocation (not in openbsd source tree) which I was able to feed with bad values ... and how to fix it. Perhaps the maintainer will take the patch to circumvent a segmentation fault when an input file is 4 gb in size (but only the first few kbs have to be read in [page fault]).

          Thank you very much for your responses (and your article of course)!

  13. By Andrew Reilly (141.168.4.160) on

    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.

    Comments
    1. By tedu (71.139.182.193) on

      why do you think performing division is slower than allocating memory, copying a buffer, and then freeing the old buffer?

Credits

Copyright © - 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 as well as images and HTML templates were copied from the fabulous original deadly.org with Jose's and Jim's kind permission. This journal runs as CGI with httpd(8) on OpenBSD, the source code is BSD licensed. undeadly \Un*dead"ly\, a. Not subject to death; immortal. [Obs.]