Immediate memory corruption detection

• Download source code - 13 KB

Introduction

This article presents a method to detect invalid heap memory accesses in the code. First, we'll talk about the virtual address space of the process, what are the types of memory allocations, and what is invalid memory access.

Those who are familiar with these subjects may skip this and go directly to the immediate memory corruption detection section.

Process memory from the OS point of view

The virtual address space of a process consists of memory pages. Those pages have fixed size (4K on Win32), and every page has its access permissions (read/write/execute). When a process is created, its address space is initially empty and all the pages in it are initially inaccessible. Then, during the run, some pages eventually become allocated and accessible. Attempt to access a memory address which belongs to a page whose permissions are incompatible with the requested - results in an access violation exception.

Application may allocate/free memory pages directly using the virtual memory functions, such as VirtualAlloc, VirtualFree, etc. However usually there's no need to explicitly allocate 4k memory blocks, applications usually need variable-sized memory blocks of much smaller size. For this applications may use the traditional global/stack/heap memory as well, however those allocation types are actually implemented via the virtual memory mechanism as well, and they can be seen as some wrappers that do the partitioning of the memory pages inside the process's address space.

So, from the OS's point of view, the process allocates memory pages, and it doesn't bother about how those pages are actually used inside the process to hold the application variables.

In-process memory allocation

The term allocated memory block refers to the situation where you have a piece of memory that no one is allowed to touch besides you. You may read/write to it whatever you like. This memory is guaranteed not to be allocated for anything else until you free it.

There are several types of memory allocations:

• Global process memory (which actually may consist of different things, such as code, data, etc.). In particular, all the global variables are stored there.

When the executable is built by the compiler and linker - the size of all the global variables is calculated. This size and the initialization data are written in the executable, and when it's loaded, the OS allocates adequate number of memory pages and initializes them appropriately. When you access a global variable, the compiler actually generates a code that accesses some portion of this global memory block.

• Stack memory. Every thread is given its own stack by the OS. In particular, automatic variables and function parameters are stored there.

For every thread, the OS allocates a portion of the virtual address space (in fact, it's reserved and allocated on-the-fly, but this is not important). Whenever a thread enters a function with parameters and automatic (locally defined in a function) variables, the code generated by the compiler consumes more stack (moves the stack pointer). When you access a function parameter or an automatic variable, the compiler actually generates code that accesses the current stack position with some offset.

• Heap memory. It's allocated and freed explicitly by the appropriate functions and operators.

Unlike global memory and the stack, heap memory can be used to store objects whose lifetime is unpredictable at compile time. Those are the so-called dynamic allocations. Those are done via new/delete operators or functions such as malloc/free, HeapAlloc/HeapFree, and etc.

Heap allocations give maximum flexibility. However, this flexibility has its price:

• You are responsible to free all the allocated memory. Otherwise, there'll be memory leaks.
• Heap allocation is a relatively complex operation. It's very much heavier than stack allocation, hence it should not be used unless really needed.
• Heap allocations have significant memory overhead and produce memory fragmentation, unlike other allocation types where all the variables are closely-packed.

Actually, there're various implementations of the heap, and in fact, heap is not an integral part of C/C++. The new/delete operators are declared, but their implementation is not fixed. If you link with CRT libraries, they implement those operators via CRT heap code (which is also used in malloc/free). For MFC, there's another heap implementation. And, driver writers don't have the default implementation at all - they must define them themselves.

Invalid memory access

The term invalid memory access refers to a situation where some piece of code tries to access (i.e., read or write) a memory location which it's not allowed to access. As we already said, in order to access a memory location, it must be allocated. Below, we'll give some examples of improper memory access:

// Examples of improper memory access

char* sz = new char[20];
// 20 bytes allocated on the heap

sz[0] = 12;
// ok

sz[20] = 12;
// Error! We've written a value after the allocation end

char c = *(sz - 1);
// Error! We've read a value before the beginning of the allocation

delete[] sz;

char c = sz[2];
// Error! we're reading the memory after it was freed!

sz = (char*) 0x12345; // point to a random address
*sz = 2;
// Error! We're not allowed to write there

Now, what are the consequences of invalid memory access? Actually, there may happen several things:

1. The memory address belongs to an inaccessible memory page. This situation is the best, because your program crashes immediately (unless you handle this exception), and you have the exact place and callstack of the situation where the outlaw dared to access the forbidden memory. Then, you realize what's the problem and (hopefully) fix it.
2. The memory address belongs to an accessible page (which holds some data that is none of your business).

If this memory was read, it may contain anything (i.e., junk). If what was read is not going to affect your behavior, there's almost no problem. However if the read value is important, from now on, your program depends on some random junk.

If this memory was written, it is much worse, because you've just smashed someone's data, and you have no clue who was that. This damage is irreversible, and the program may crash or do something stupid any time.

Finding invalid memory access is a big challenge. Mostly, this is because the first situation (where you have an immediate crash) is pretty rare. Usually, the effect of memory corruption is not seen until the corrupted memory is eventually used.

Since this is a known problem, there're standard memory corruption detection methods. In particular, all the heap implementations I've seen (CRT, MFC, Win32) give an indication when the heap is corrupted. For example, Win32 heap functions (HeapAlloc/HeapFree), upon corruption, trigger a debug breakpoint and emit the following message:

HEAP[strt.exe]: Heap block at ..... modified at ..... past requested size of .....
Windows has triggered a breakpoint in .....exe.

This may be due to a corruption of the heap, and indicates a bug in ...

All those heap corruption methods work the same way: when you allocate a memory block, they internally allocate a bigger block, and surround the region allocated for you by some values. Then, when you free this memory, they verify that the decoration is not damaged.

This method is good to indicate a problem; however, it's not really helpful in finding it. You only see that the memory is corrupted when you try to release it, but you have no clue who is the violator and when and how the crime could happen.

Plus, you don't have an indication for invalid memory reads. Though not so much destructive, those must be found and fixed too.

Immediate invalid memory access detection

Now, we'll talk about our method. As its name suggests, it's aimed to:

• Detect any invalid memory access, not only write access.
• Give you an immediate detection of the invalid access. Catch the criminal on-hot.

This method implements heap in such a way that invalid memory access is guaranteed to result in an access violation. Hence, the goal is achieved. The rest - realizing and fixing the problem - is up to you.

We allocate/free memory directly through the VirtualAlloc/VirtualFree functions. Every returned memory address is padded so that there's an exact number of bytes that may be accessed; attempt to read one extra byte leads to access violation. The allocation may be done in two modes: one guarantees an access violation when you attempt to access memory after the permitted region, and the other mode - access violation when you attempt to access memory before the permitted region.

This is how memory is allocated in both modes:

The accessible page is marked by green, and the inaccessible page is marked by cyan; the allocated memory block (pointer to which is returned) is marked by blue.

As you can see, for every memory allocation, no matter how small it is, we reserve at least two memory pages in the address space. All of them except one are allocated, and the return address is padded appropriately. Furthermore, when you free the memory via our heap - it deal locates all the memory pages, but it does not immediately free them. Instead, it leaves them in the reserved state. In this state, they're inaccessible and they don't consume physical memory, and they're guaranteed not to become allocated eventually, hence they definitely will remain inaccessible. When the virtual size occupied by those reserved pages exceeds some number (which is 50MB by default), the heap starts to release the most recent pages.

Well, needless to say, this method wastes memory (both physical memory and the address space) in an extremely barbaric way. And, it may not be used in the applications shipped to the user. However, it's an excellent tool for finding invalid memory accesses at debug time. To enable it, put the following code lines:

// Enable invalid memory access detection mode
DbgHeap g_Heap; // the global debug heap object.

void* operator new (size_t nSize)
{
    // the last parameter - allocation alignment method
    void* pPtr = g_Heap.Allocate(nSize, true);
    // you may run your program with both methods to ensure everything's ok
    
    if (!pPtr)
    {
        // do whatever you want if no memory. Either return NULL pointer
        // or throw an exception. This is flexible.
    }
    return pPtr;
}

void operator delete (void* pPtr)
{
    g_Heap.Free(pPtr);
}

Similarly, you may hack other heap functions, such as malloc/free. You may get a linker error, but with some manipulation, you may get rid of it. And, using advanced hacking techniques (such as Richter's method for intercepting DLL calls), you may even try to hack all the heap functions in the process.

Let's summarize. This method detects:

• Any invalid memory access with immediate problem indication.
• Guaranteed to alert when you exceed the allocation bounds only from one side. Which side - is a parameter.

This method does not detect:

• Corruption when you exceed the other allocation bound.
• Invalid access in global memory, stack, and the memory allocated via all other heaps.

Conclusion

Well, I believe this method is awesome. Looking for the cause of the memory corruption is a real pain in the neck, sometimes it's just a nightmare. And, this method proved (at least for me) to be very useful. You may try to use this method and see how wonderfully your program crashes the moment you try to do something wrong.

When the program crashes exactly at the moment of the invalid memory access, this is a miracle! You should pray for this to happen. Because if it does not, you're screwed. It may take days to reproduce the problem and find its cause.

One more thing: if you intent to look at the code level of this method, I recommend reading the following articles:

• A Guard class for any object/resource type
• Superior container classes

Criticism and new ideas are welcome.