Integer overflow in the new[] operator


Integer overflows are becoming a new security attack vector. Mike Howard's article discusses some of the ways you can protect yourself against integer overflow attacks.

One attack vector he neglects to mention is integer overflow in the new[] operator. This operator performs an implicit multiplication that is unchecked:

int *allocate_integers(int howmany)
{
    return new int[howmany];
}

If you study the code generation for this, it comes out to

  mov  eax, [esp+4] ; eax = howmany
  shl  eax, 2       ; eax = howmany * sizeof(int)
  push eax
  call operator new ; allocate that many bytes
  pop  ecx
  retd 4

Notice that the multiplication by sizeof(int) is not checked for overflow. Somebody can trick you into under-allocating memory by passing a value like howmany = 0x40000001. For larger structures, multiplication overflow happens sooner.

Let's look at a slightly longer example:

class MyClass {
public:
  MyClass(); // constructor
  int stuff[256];
};

MyClass *allocate_myclass(int howmany)
{
  return new MyClass[howmany];
}

This class also contains a constructor, so allocating an array of them involves two steps: allocate the memory, then construct each object. The allocate_myclass function compiles to this:

  mov  eax, [esp+4] ; howmany
  shl  eax, 10      ; howmany * sizeof(MyClass)
  push esi
  push eax
  call operator new ; allocate that many bytes
  mov  esi, eax
  test esi, esi
  pop  ecx
  je   fail
  push OFFSET MyClass::MyClass
  push [esp+12]     ; howmany
  push 1024         ; sizeof(MyClass)
  push esi          ; memory block
  call `vector constructor iterator`
  mov  eax, esi
  jmp  loop
fail:
  xor  eax, eax
done:
  pop  esi
  retd 4

This function does an unchecked multiplication of the size, then tries to allocate that many bytes, then tells the vector constructor iterator to call the constructor (MyClass::MyClass) that many times.

If somebody tricks you into calling allocate_myclass(0x200001), the multiplication overflows and only 1024 bytes are allocated. This allocation succeeds, and then the vector constructor tries to initialize 0x200001 of those items, even though in reality only one of them got allocated. So you walk off the end of the memory block and start corrupting memory.

That's a bad thing.

To protect against this, you can wrap an integer overflow check around the array allocation.

template<typename T>
T* NewArray(size_t n)
{
  if (n <= (size_t)-1 / sizeof(T))
    return new T[n];

  // n is too large - act as if we
  // ran out of memory
  return NULL;
}

Note: If you use a throwing "new", then replace the "return NULL" with an appropriate throw.

You can now use this template to allocate arrays in an overflow-safe manner.

MyClass *allocate_myclass(int howmany)
{
  return NewArray<MyClass>(howmany);
}

This generates the following code:

  push edi
  mov  edi, [esp+8] ; howmany
  cmp  edi, 4194303 ; overflow?
  ja   overflow

  mov  eax, edi
  shl  eax, 10
  push esi
  push eax
  call operator new
  mov  esi, eax
  test esi, esi
  pop  ecx
  je   failed
  push OFFSET MyClass::MyClass
  push edi
  push 1024
  push esi
  call    
  call `vector constructor iterator`
  mov  eax, esi
  jmp  done

failed:
  xor  eax, eax
done:
  pop  esi
  jmp  exit

overflow:
  xor     eax, eax
exit:
  pop  edi
  retd 4

Notice the new code that checks for a possible integer multiplication overflow.

But how could you get tricked into an overflow situation?

The most common way of doing this is by reading the value out of a file or some other storage location. For example, if your code is parsing a file that has a section whose format is "length followed by data", somebody could intentionally put an overflow-inducing value into the "length" field, then get somebody else to try to load the file.

This is particularly dangerous if the filetype is something that is generally considered "not dangerous", like a JPG.

Comments (21)
  1. Raymond wrote an excellent entry on how to integer overflow the new[] operator. I liked how he broke down the C++ code into assembly to hit the point home. He even provides a wrapper function to do the allocation check for you to use. Enjoy….

  2. David LeBlanc says:

    Actually, I just noted that in the discussion section on the SafeInt article earlier today.

  3. Mr. Chen, you kindly gave a link to an article written by Mr. LeBlanc as guest of Mr. Howard. Do you have any contact with Mr. LeBlanc?

    > Addition

    > The unsigned case is relatively easy. In

    > mathematical terms, all we need to do is

    > check to see if:

    > A + B > MAX_INT Error!

    Mr. LeBlanc meant UINT_MAX or ULONG_MAX or UCHAR_MAX or whatever.

    > In order to keep your test from depending on

    > an overflow, we can rewrite it as follows:

    > A > MAX_INT – B Error!

    Again Mr. LeBlanc meant UINT_MAX or ULONG_MAX or UCHAR_MAX or whatever.

    > Some of you might notice that:

    > MAX_INT – B == ~B

    > This is true if and only if B is unsigned

    > and is 32 bits and or larger.

    But this time Mr. LeBlanc really meant INT_MAX

    or LONG_MAX or SCHAR_MAX or whatever.

    At the bottom of Mr. LeBlanc’s article is a menu bar courtesy of MSDN:

    > Print E-Mail Discuss Add to Favorites

    When I click on Discuss, IE pops up the following window courtesy of MSDN:

    > This page requires an article reference for

    > functionality. Try entering user comments in

    > an article linked to from our home page

    > ‘oSqlData.oArticleInfo.firstChild’ is null

    > or not an object

    When I click on the home page link in the popup window, it displays the msdn image header at the top, followed by this courtesy of MSDN:

    > ‘oSqlData.oArticleInfo.firstChild’ is null

    > or not an object

    Maybe Microsoft should read this advice:

    > Although I’d asked some excellent

    > programmers to review the code, and they did

    > find some bugs and design problems, no one

    > found this problem, nor did they find

    > several others. What found the problem was

    > function-level testing, and stepping through

    > the code line by line. It was tedious and

    > hard work, but it paid off. It doesn’t

    > matter how many eyes look at a piece of

    > code. Even the best reviewers will miss

    > things, though code that has been reviewed

    > will be more solid than code that has not.

    > What matters is how many good eyes look at

    > the code, and how many detailed tests are

    > written to verify the code, preferably at

    > function level.

    Or maybe not. Microsoft’s usual policy is to let bugs be caught by customers instead of by Microsoft, because Microsoft gets to charge 4,200 yen from each customer who tries to report a bug. That is the situation yet again today with 4 Windows XP bugs for which Microsoft is refusing to let customers download updates and is telling customers to phone for support. (Yeah sure in English Microsoft says that fees might be waived if the updates are enough to really fix Microsoft’s bugs, which of course they aren’t. In Japanese Microsoft doesn’t even say this.) Well, sorry I’m not paying 4,200 yen per bug to report the above bugs to you, Mr. Chen. Perhaps you can find a way to report them upstream without paying fees.

  4. Raymond Chen says:

    Sorry. While I have met Mr. Howard, the name "LeBlanc" doesn’t ring a bell.

  5. Michael Howard says:

    Norman – email me, mikehow@microsoft.com, and I’ll hook you up with David LeBlanc.

  6. 1/29/2004 9:31 PM Norman Diamond:

    > > Some of you might notice that:

    > > MAX_INT – B == ~B

    > > This is true if and only if B is unsigned

    > > and is 32 bits and or larger.

    >

    > But this time Mr. LeBlanc really meant

    > INT_MAX or LONG_MAX or SCHAR_MAX or

    > whatever.

    What were you thinking of, you idiot? Mr. LeBlanc still meant UINT_MAX or ULONG_MAX or UCHAR_MAX or whatever, the same as he meant the other two times. Now I have to charge myself 4,200 yen for reporting my bug to myself. (I do wonder why no one else caught me on this.)

    1/30/2004 8:12 AM Raymond Chen:

    > Sorry. While I have met Mr. Howard, the

    > name "LeBlanc" doesn’t ring a bell.

    Mr. Chen, you kindly gave all readers a link to the MSDN article. Just take a glance at who wrote it and who wrote a short paragraph commenting on the guest author.

    1/30/2004 10:25 AM Michael Howard:

    Thank you for the offer Mr. Howard, and I’ll think about it. Of course I have much bigger general wishes for contacts, (1) I wish that victims could report Microsoft’s bugs without paying 4,200 yen per report, and (2) I wish that victims could download patches without paying 4,200 yen per support request for patches, when victims and Microsoft both know that the patches will not be enough to fix all of the bugs that affect the victims. If Microsoft would allow such contacts, that would be a much bigger benefit than being able to submit one bug report on one MSDN article to its author.

    Meanwhile, if you wish to forward my bug report (as posted 1/29/2004 9:31 PM plus the self-correction at the beginning of this posting), that’s no problem.

  7. Raymond Chen says:

    Yeah I neglected to read the author’s name.

    I thought patches were free downloads from the Windows Update web site. At least I don’t get charged for them. Maybe in Japan it’s a for-fee service?

  8. Patches from the Windows Update web site are free. Some Knowledge Base articles point to patches that Microsoft allows victims to download.

    Patches that aren’t listed for download require support calls. Some Knowledge Base articles describe the problem that Microsoft understood needs fixing, name the files that get updated by the patch, give the size and datestamp of the English language version of the patch, and say that a support call is required in order to get the download. For Windows XP these Knowledge Base articles say that support fees can be canceled if Microsoft determines that the victim’s problems will be fixed by the patch. However, the pages giving phone numbers and support policies (these in Japanese) say that support fees will be required unless the product was purchased retail (not OEM) and the call is within the 90-day period. For Windows 95, even the Knowledge Base articles did not assert that support fees could be canceled if Microsoft determined that the victim’s problems could be fixed by the patch. Furthermore for Windows 95, a Microsoft support manager already refused by e-mail to let me download patches, but he did point me to Microsoft’s legal department since Microsoft’s contracts with OEMs are a legal matter. So I sent letters to Microsoft’s legal department asking for either (1) proof that OEMs must supply Microsoft’s patches to customers or (2) instructions on how to download patches from Microsoft, but Microsoft’s legal department did not answer. Furthermore, for both Windows 95 and Windows XP, it’s pretty obvious that the patches would not solve all of my problems, the patches would only solve some of my problems. So in English Microsoft speaks out of both sides of its mouth about whether support fees would be required but then refuses to supply patches anyway, and in Japanese Microsoft clearly says that support fees would be required. To repeat, this is for cases where Microsoft figured out that patches are necessary but refused to put them on Windows Update or other public download sites.

  9. Raymond Chen says:

    Okay I didn’t know that. Unclear what you expect from me about it, though. Or are you just complaining to get it off your chest?

  10. 2/2/2004 7:21 AM Raymond Chen:

    > Okay I didn’t know that.

    That’s why I explained it to you.

    > Unclear what you expect from me about it,

    > though.

    Well, there’s a mixture of things. Partly it was to get it off my chest (except that it still remains on my chest, because every time I connect a USB hard disk or USB DVD+RW Microsoft still reminds me that Microsoft is still Microsoft). Partly it’s so you’ll know that your employer really doesn’t put customers first.

    Partly, although I’m still wondering if there would be anything to gain by personally disturbing Mr. LeBlanc at this point, I had to point out where there should be some priorities. Personal disturbances to report severe bugs really ought to be accepted, really shouldn’t get charged for, and really ought to get worked on. That’s far more important than this particular MSDN article. OK, there’s nothing you can do about your employer’s priorities either, but I couldn’t help wondering about it when it came up.

    Here’s why I was in a bad mood immediately prior to my posting

    1/29/2004 9:31 PM Norman Diamond.

    I had just finished reading these three knowledge base articles:

    http://support.microsoft.com/default.aspx?scid=kb;en-us;830752&Product=WinXP

    http://support.microsoft.com/default.aspx?scid=kb;en-us;825033&Product=WinXP

    http://support.microsoft.com/default.aspx?scid=kb;en-us;830638&Product=WinXP

    For more than 2 years, I’ve been waiting for fixes to these and some other problems. Microsoft finally admitted to being aware of these and has developed fixes but still isn’t letting customers download them unless we pay for support calls. I wonder when Microsoft will discover that Windows Server 2003 has the same problems.

    Here’s an example of a problem which the Knowledge base doesn’t seem to know yet: On Windows XP and Windows Server 2003, if Windows Explorer is open before connecting the USB hard disk, then on occasions when Windows Explorer allows access to the USB hard disk (instead of pretending that it doesn’t exist), it doesn’t let me move a long filename from one folder to another on the USB hard disk. It thinks the USB hard disk’s 120GB FAT32 partition only allows 8.3 filenames, even when it’s looking at the existing long filenames. In order to report this through official channels, I would have to pay 4,200 yen. And then I’d have no chance of getting refunds for support fees for the three patches mentioned above, because they don’t fix this problem.

    Your TweakUI did fix one problem as I’ve mentioned before. Without TweakUI, Windows XP and Windows Server 2003 wanted to scan the entire 120GB looking for files that it could open automatically. I do thank you for providing a helper for this nuisance.

  11. Raymond Chen says:

    Okay. I do what I can, but remember, I don’t run the place.

  12. Ken says:

    It seems to me this would be a QoI issue for the compiler/library. Shouldn’t the new[] operator throw a std::bad_alloc or something if you try to allocate more than size_t_max/sizeof(element)? Also, (size_t)-1 isn’t exactly portable, if you care.

  13. Ken says:

    Thinking about this even more, the C++ spec allows for the compiler/library to allocate "N*sizeof(element)+C" chars worth of space for a "new element[N]" pointer, where C is platform specific and can even vary from one allocation to the next. Since there’s no way to determine the value of C without knowing implementation details, it doesn’t seem like there’s any reliable, portable way to put an exact upper bound on N, meaning to be safe, the implementation needs to protect itself from overflow, rather than expecting the end user (in this case a developer) from attempting to do so.

  14. Raymond Chen says:

    Ken: Phooey – right you are.

Comments are closed.