Attacking delete and delete [] in C++

blog January 3rd, 2007

In C++, objects can be dynamically allocated at runtime using the new operator and deallocated using the delete operator. Arrays of objects, however, require the use of slightly different operators for allocation and deallocation: new [] and delete []. Although the corresponding pairs of operators look very similar in source code, the way they function is actually quite different. Consequently, they can’t be mixed and matched - allocating an array with new [] and then deallocating it with delete, for example, will produce "undefined" results. This can catch developers off-guard, because you can often use the wrong operator without triggering a compiler warning or even causing a run-time crash.

Here’s a quick example of an incorrect mix of operators:

int main(void)
{
   basebob *ba = (basebob *) new bob[4];
   dostuff(ba);
   delete ba;
}

As stated previously, array and scalar operators for dynamic allocation and deallocation of an object should not be mixed. The highlighted code should have read:

delete [] ba;

This is definitely bad code, but it’s a plausible enough mistake, especially if we imagine it hidden within layers of object-oriented cruft. So, what’s really going on behind the scenes here? The answer to this question depends on what implementation you examine. Here, we will consider g++/glibc (on an IA32/Linux platform) and Microsoft’s VC++ Runtime Library (Windows XP/SP2, Visual Studio 2005, MSVCR80.DLL).

First, let’s look at gcc. If you want to follow along with some equivalent-ish C code, check out libsupc++ in this g++ tarball. If you dig into delete, you find that it is pretty simple. It takes a pointer to an object. It calls the appropriate destructors, and then does a free() on the pointer. Here’s a rough sketch of what it does:

delete(obj *ptr)
{
  call_destructors(ptr);
  free(ptr);
}

This pseudo-code is an oversimplification of what you would see in a compiled binary, as much of the relevant code will be inlined. The destructor code will often be inlined into the function that calls delete, immediately followed by the actual deallocation of the object’s memory. In other cases, the destructor will be called directly, or accessed through a vtable. (In MS binaries, you’ll typically see this happen via a standardized function added by the compiler, usually with a name like classname___scalar_deleting_destructor_).

Arrays are a little different. The space for the array is all allocated in one contiguous block, and it is prefixed by a size_t count variable that contains the number of elements in the array. So, if you had an object bob that took up 12 bytes of memory, and you did a new bob[4], then the system is going to allocate 52 bytes of memory: 48 bytes to hold the bobs plus 4 bytes to hold the counter. (For this example, assume that a bob object has a vtable pointer and two int variables a and b.) There’s your usual padding and alignment to complicate things, but basically what you’ll see in memory is this:

This layout is common to both the MS and glibc implementations. So, the algorithm for delete [] is pretty interesting. Both the MS and glibc implementations take the pointer you pass to them and back it up to the counter variable. They then start with the last element in the array and work backwards, calling the destructors for each element. When they are done with this, they do a single free() on the pointer, which has been backed up to point to the right spot. Here’s a sketch of how it works:

delete_array(obj *ptr)
{
    size_t *tmpptr = ((size_t *)ptr) - 1;
    int num_elements = *tmpptr;

for (int i=num_elements-1; i>=0; i--) {     call_destructors(ptr[i]); } free(tmpptr); }

One key difference between the implementations, which will be important in the following section, is that the glibc implementation will use vtable pointers from the current object it is deleting as it walks through the array calling destructors. The MS implementation, however, will take the relevant vtable pointers from the first object in the array, and use them for each object it deallocates throughout the array.

 

Attacking delete[]

 

Ok, so we’ll consider two basic mistakes: using delete on a pointer to an array, and using delete [] on a pointer that doesn’t point to an array. We’ll start with the less likely mistake: using delete[] on a non-array pointer. Let’s say that you saw something like this:

int processrecords(int hcount, int dcount)
{
  basebob *ba, *ptr;
  int i;

ba = (basebob *) new bob[hcount + dcount];
for (i=0, ptr=ba; i < hcount; i++) { if (populate_hdr_record(ptr++) < 0) goto error; }
for (i=0; i < dcount; i++) { if (populate_data_record(ptr++) < 0) goto error; }
... more code ...
return 0;
error: delete [] ptr; return -1; }

So, the developers made a mistake in the error handling code. Instead of doing delete[] on ba, they did delete[] on ptr. Let’s assume that the attacker can close the connection after sending the first header record, causing an error. The code will perform a delete [] on ptr, which will be pointing at &ba[2]. delete [] is going to look for the element count directly behind the pointer it was provided, which means it will pull data out of ba[1], and mistakenly treat it as the object count. Assuming you could control the relevant data element in ba[1], you could provide an arbitrarily large element count, and thus have delete [] attempt to access out of bounds memory contents as if they were elements of the array. If you tell it the end of the array is somewhere in memory that you control, then you get to supply object data that it will run a destructor against.

Naturally, if the destructor manipulated memory, you could leverage that to exploit the process in many cases. If the classes had a virtual destructor, you’d definitely win in the g++ case, because you could give them a new vtable pointer and supply your own destructor function pointer. The attack would look something like this:

Like we said, however, this attack is less plausible on MS C++ applications, since the relevant vtables are accessed from element 0 of the array. However, the situation is not hopeless - depending on what destructors are called and what they do, it is likely that you will be able to trigger some sort of memory corruption. For example, consider a simple destructor like this:

class Buffer
{
private:
	unsigned char *m_Data;
	size_t m_Length;
public:
	... code ...

~Buffer() { free(m_Data); m_Length = 0; } }

This simple destructor deallocates a buffer, and sets the m_Length value to 0. If you were able to control the count parameter at the beginning of the array due to an incorrect use of delete[], you could adversely affect the process. The result of calling this destructor would include setting an arbitrary memory location to 0 and passing an arbitrary pointer to free(), both of which might carry serious consequences.     

 

Attacking delete

 

Ok, that’s interesting, but it would arguably take some fairly convoluted code for that to happen in practice. The more likely error is the one we mentioned initially: programmers using delete on an array instead of delete []. We looked at the algorithm for delete above, which was pretty simple: call the destructor and then free the object. Here’s what the mistake looks like again:

int main(void)
{
   basebob *ba = (basebob *) new bob[1024];
   dostuff(ba);
   delete ba;
}

So, the first problem with making this mistake is that the destructor is only going to get called for one element in the array, ba[0], and all the other elements aren’t going to get destructor-ized. There are probably situations where this would lead to exploitable conditions, but at a minimum, this is going to leak memory left and right.

The second problem with this mistake is a little more subtle: free() is called on an address that was never returned by a malloc(). Here’s a pretty picture (based on a glibc environment):

This is pretty interesting. free() is going to be a little bit confused by this address. Normally, free() would look for the malloc chunk header 8 bytes back in memory in order to figure out how to perform the free() operation. In this case, it will still look 8 bytes back, but it will be off by 4 bytes. Instead of seeing the real size of the memory set aside for the array, it will see count — the number of elements in the array. Also, it will interpret the real size of the array as its previous size.

So, let’s talk exploitation. First, if you can control the number of elements in the array, you have a lot more flexibility in the games you can play. If the lowest bit is set in the number of elements, then free() will attempt to coalesce the previous chunk, which can be useful if you’re into instant gratification. If the second lowest bit is set, then it’s going to treat it as an mmapped chunk, which probably won’t overly help you out. If you can’t control the number of elements, or the previous chunk coalescing is jerking you around, you can take advantage of the forward coalescing. This would require you to be able to control the memory inside the array, which is probably likely. Newer versions of glibc do stricter heap sanity checking, so you’ll probably need some serious computer hacking skills to win on those systems. We’ll leave that as an exercise to the reader. :>

The situation in an MS environment is almost identical, with the exception of the structure of the preceding chunk header. This exact structure requires some further explanation. The new operator used by MS binaries can take on a number of different behaviours, depending on the __active_heap value stored within the MS C runtime library. On a typical XP/SP2 install, you usually have a number of different runtime libraries installed, with various applications being linked against the different versions. We said earlier that we focused on MSVCR80.DLL, but many systems will have MSVCR71.DLL, MSVCR70.DLL, and MSVCRT.DLL (The CRT DLL). If the MSVCR70, MSVCR71, or MSVR80 DLL’s are used, the default behaviour is to use the system allocator to manage dynamic objects. In this case, the off-by-four scenario is rendered largely ineffective from an exploitability point of view, because addresses passed to RtlFreeHeap() are validated to ensure that they lie on an 8-byte boundary. Since the address passed to this function is (buffer + 4), it will never be aligned on an 8-byte boundary, and the free() routine does nothing with it. In the case where MSVCRT.DLL is used, an alternate allocator is employed to manage dynamic allocation and destruction of objects. This free() routine for this alternate allocator, the __sbh_free_block() function, contains some interesting possibilities, since it has no such checks for pointer alignment (and is also not hardened anywhere near as much as the system allocator). In this scenario, the array count would be mistakenly used as a block size, and exploitation seems very possible.

7 Responses to “Attacking delete and delete [] in C++”

  1. Matton 03 Jan 2007 at 10:20 pm

    Very nice post. Discussing it with a C++ guru of my acquaintance, though, raised the question of how often you actually see new[] in C++ written these days, given the myriad, generally better options afforded by the STL. If the answer is (as he claims) “not much,” it’s time to start banging on STL implementations, as hinted at by Thomas this morning over on Chargen :)

  2. Ben FrantzDaleon 03 Jan 2007 at 10:36 pm

    You make a good point, but overall I see this as yet another reason to use STL over C-style arrays. In my C++ code I essentially never call delete[] or delete or new[]; I sometimes call new but then hand the result off to an auto_ptr. In your example you have:

    int main(void)
     {
        basebob *ba = (basebob *)   new bob[1024];
        dostuff(ba);
        delete ba;
     }

    The C++ way to write this is:

    int main(void)
     {
       std::vector <bob> ba(1024);
       dostuff(&ba[0]); // An admitted wart in the std::vector interface, but it does the job.
     }

    In this C++ version, there is no way to mess up destruction. Even if dostuff throws an exception, we won’t leak memory. Of course, a problem with this is that dostuff(basebob* foo) might try to access foo[1], which is located at static_cast<void *>(foo) + sizeof(basebob) and not at static_cast<void *>(foo) + sizeof(bob). If we are allowed to change the signature of dostuff(), it could be even safer. The STL version, of course, would be:

    template <typename BasebobIterator>   void dostuff(BasebobIterator first, BasebobIterator last);

    Then we could call dostuff(ba.begin(), ba.end()); or if we had a bob* called bobptr, we could still use that by calling dostuff(bobptr, bobptr + 1024);

  3. Ben FrantzDaleon 03 Jan 2007 at 10:43 pm

    (The above post got mangled a bit (no preview?). In particular it ate the angle brackets. The std::vector is of type bob, the static_cast is to void*, and the templated function is templated on “typename BasebobIterator”.)

  4. jmon 03 Jan 2007 at 10:48 pm

    Sorry, our comment system is rubbish. :> When I get a chance, I’ll fix your comment and see if I can fix the system. At any rate, thanks for the feedback guys, and STL is definitely on our to-do list.

  5. markon 04 Jan 2007 at 3:39 am

    There is one pretty important detail we forgot to mention with regards to primitive types that I feel I should mention here. When arrays of primitive types are constructed, there is no count element preceding the objects in the block of memory allocated for the array. The reason for this is probably because no special destruction or construction needs to be done on those types, and so the count is not required. Therefore, using delete on an array of primitive types should work correctly, although I have yet to test it out.

  6. Alexon 11 Jan 2007 at 11:34 am

    I checked libsupc++ but didn’t find where delete[] is implemented. Could you point to a filename?

  7. jmon 11 Jan 2007 at 6:08 pm

    Sure, check out libstdc++-v3/libsupc++/vec.cc in the *vec_delete* functions.

Permanent Link | Trackback URI | Comments RSS

Leave a Reply