A New Way to Detect Integer Overflows?

Published 27 October 04 09:53 PM

David LeBlanc and I have written a good deal about Integer Overflow issues, including the following:

A couple of days ago I saw some code from someone outside of Microsoft claiming they had found a new (read: cheap) way to detect integer overflow errors, here's the code snippet:

void *p= NULL;
size_t cb  = z + (x * y);
if ((int)cb > 0 && cb < MAX)
   p=malloc(cb);

Basically, you cast the result to signed, and if it’s negative, then there must be an overflow… right?

I had no spare cycles, so I asked David to look at it. He shot the code down in about 15secs. So what's wrong with the code?

by michael_HOWARD
Filed under:

Comments

# Dean Harding said on October 27, 2004 10:20 PM:
Well, it's possible that the value could actually wrap around "twice" (i.e. back into positive), as in:

unsigned int x = MAX - 1;
unsigned int y = MAX - 1;
unsigned int z = MAX - 1;

size_t cb = z + (x * y);

Will yield cb = 2...
# Ilya said on October 27, 2004 11:05 PM:
if ((cb > z) && (cb < MAX))
# oshkosh said on October 28, 2004 7:17 AM:
In a recent security conference (http://esorics04.eurecom.fr/program.html), there was a paper which addressed integer overflow attacks in their own way. Here is the URL (post-googling) of the paper:

http://www.cse.buffalo.edu/~rc27/publications/chinchani-ESORICS04-final.pdf

There are some nice ideas, which you might find useful for your work.
# Michael Howard said on October 28, 2004 10:10 AM:
Dean hit it on the head! x*y could result in a value >2^31, which would be treated as negative, then adding z would swing the result back into the positive column. oops!
# Thomas said on October 29, 2004 5:30 AM:
The code as we see it here is ok.

size_t is unsigned int, malloc() takes an unsigned int argument.
(multiple wrap arounds doesnt matter, BTW)

but the interessting code part is missing: the copying to the buffer.

my suggested test code:

size_t tmp;

if( x >= UINT_MAX / y)
exit()
if( (x * y) >= (UINT_MAX - z) )
exit()

# Michael Howard said on October 29, 2004 11:52 AM:
Personally, i would not use a divide as it's very expensive; if i can avoid using it i will. You should look at how LeBlanc does this without doing divides in SafeInt.hpp
# Thomas said on October 29, 2004 12:12 PM:
But LeBlanc also wrotes:
"For a 64-bit integer, you have no other choice than to perform the division, ..."

And 64 bit systems become more and more common. Espacially in the Unix sector.

size_t will become 64 bit there, and in the open source community you have to make the checks bulletproof on every architecture because the code is often widely used... from x86_32, over 31 bit s390, to ppc64.

But thanks for the hint and for the links to the papers. :)

Thomas
# Michael Howard said on October 31, 2004 1:58 PM:
I totally agree with your comments about 64-bit. It also turns out a div is sometimes not so expensive, in the case of, say n/2, most compilers will turn this into n >>= 2.
# 厚重之刀 said on November 1, 2004 2:00 AM:
I hope to see more new methods!
# Albert [MSFT] said on November 16, 2004 4:39 PM:
Thomas... Should you make sure that y isn't zero? (divide by zero error)
New Comments to this post are disabled
Page view tracker