CodeSport

In last month’s column, we had discussed a set of questions that could prove helpful to our student readers, as they prepare for interviews. While we have had a number of responses to the questions, I did not get answers to all, so I will keep the questions open for another month, and discuss the solutions in the next issue of LFY.

In my March column, I had discussed various programming errors that can lead to coding bugs. These included memory access/usage errors such as memory leaks and Uninitialised Memory Reads (UMR). A few readers had requested me to cover the tools to detect memory access errors. Hence, in this month’s column, I will discuss various memory related programming errors and the tools used to detect them.

What are the different types of memory errors?

An application’s data can be stored in global variables, function-local variables on the stack, or in dynamically allocated heap memory. Dynamically allocated heap memory allows the programmer to allocate the memory at runtime, depending on the actual application requirements — thereby providing considerable flexibility to the programmer. In programming languages without explicit garbage collection support like C/C++, the programmer makes the decisions about which point in the application to allocate memory on heap, how much memory to allocate, and when to free the memory once the intended use of the allocated memory is over.

The price for the programming flexibility provided by dynamically allocated heap memory is the increased possibility of the programmer introducing coding errors when handling heap memory. This is unlike statically allocated global data, which is not freed during the application lifetime, or function-local memory allocated on the stack, which is automatically freed on returning from the function.

Since programmers decide the lifetime of the dynamically allocated heap memory, they can make a number of errors, like freeing the memory too early (before it is fully used); forgetting to free the memory at all, which results in a memory leak; or using uninitialised heap memory in the application. The two major classes of memory errors that cause the most headaches for programmers are invalid memory access and memory leaks. The various classes of invalid memory access are:

1. Out-of-bound memory access, also known as buffer over-runs and under-runs.
2. Read/write to freed memory, known as “use after free” errors.
3. Attempting to free memory that is already freed; known as a “double free” error.
4. Attempting to free memory that is not dynamically allocated; known as “bad free”.
5. Uninitialised memory reads.
6. Mismatch in allocation/de-allocation calls to the memory allocator, such as trying to free a memory block allocated using “new”, or trying to “delete” memory allocated through malloc.
7. Overlapping of source and destination pointers in memcpy/memset/strcpy and other related functions.

First, let us look at a few examples of invalid memory accesses, and see if you can find and identify the issue in each of these cases.

foo() {
   char *buf;
   buf = malloc(100);
   buf[100] = 'D';
   putchar (buf[100]);
   buf[-1]='A';
   putchar(buf[-1]);
   free(buf);
}

In the above code snippet, the memory allocated through malloc is 100 bytes, which is addressable as buf[0] to buf[99]. However the code tries to write to buf[100] at line 4, which is an out-of-bound memory write. Similarly at line 5, it tries to read from buf[100], which is an out-of-bound memory read. These two errors are typically known as ‘buffer overrun’ errors, since we are accessing beyond the upper bounds of the dynamically allocated buffer buf.

At line 6, the code writes to buf[-1] and at line 7, it reads from buf[-1]. These are examples of buffer under-run issues, where the program accesses memory below the lower bound of the dynamically allocated buffer. Over-runs and under-runs typically occur due to incorrect loop index calculations, or due to the programmer writing a smaller size than actually required by the intended usage of the dynamically allocated memory.

Out-of-bound memory writes are dangerous, as they can silently corrupt other data by over-writing it. Typically, the memory allocator library stores meta-data information for each dynamically allocated block of memory just before, or after, the memory chunk allocated to the application. This meta-data is used by the dynamic memory allocator to keep track of the size of the block allocated, etc.

In the above example, the invalid memory writes beyond the boundary of the “malloced” block, which can corrupt the malloc header information, thereby causing silent corruption to the dynamic memory allocator meta-data. Therefore, detecting out-of-bound memory accesses is an important requirement of memory error detection tools.

#include <stdlib.h>
#include <unistd.h>
int main( void )
{
    char* buf1  = malloc(10);
    int*  buf2 = malloc(sizeof(int));
    write( 1 /* stdout */, buf1, 20 );
    exit(buf2[0]);
}

What are the issues with the above code snippet?  In line 8, the dynamically allocated buffer buf1 is passed as an argument to the write function, which tries to write 20 bytes from buf1 to stdout (1 stands for the file descriptor stdout). Note that buf1 was simply allocated through the call to malloc, and was not initialised with any value. Therefore, the above code snippet tries to write uninitialised data from buf1 to stdout, which is a software bug.

Next, look at line 9 where exit is called with the argument buf2[0]. Recall that the exit function takes as the first parameter the status of the exiting program. Here, it is being passed buf2[0], which is uninitialised. This is another example of the use of uninitialised values in the application, again leading to a coding bug.

In both the above cases, the arguments buf1 and buf2 are not initialised/defined by the application code after being dynamically allocated by the malloc function call.

What is shadow memory?

While it is important that such coding bugs need to be caught by memory error checking tools, it is not easy. Many runtime memory error checking tools simply intercept malloc/free calls made by the application to the memory allocator library. This information is not sufficient to detect the use of uninitialised/undefined dynamic memory locations.

In order to detect such uninitialised use of dynamically allocated memory, the tool needs to track every instruction before the use instruction, to see if any of the instructions initialise that memory chunk. This requires that the tool should maintain certain information/meta-data about every dynamic memory location, such as whether the location is defined or undefined; is it still valid or has it been freed already, etc.

Such meta-data, which tracks the state of each application memory location, is known as shadow memory. For every application memory location, there is a corresponding shadow memory location that contains information on it. This is known as memory shadowing, and the memory used to hold the meta-data information is known as shadow memory. Tools that use the information in shadow memory to detect programming errors are known as shadow value tools.

Maintaining and updating information in shadow memory is expensive. It requires comprehensive instrumentation, which tracks every instruction in the application that accesses memory. Memory shadowing also incurs considerable space overheads, since a shadow memory location is used to track every application memory allocation. The tracking granularity can be different for different purposes.

Consider a tool that shadows application memory at the granularity of a word. Basically, every word of application memory has meta-data associated with it, which says whether the memory word is initialised or uninitialised. Such a tool cannot detect uninitialised memory locations below the granularity of a word. Consider the following code snippet:

void set_one_bit_in_word(int* my_word, int pos)
{
     my_word[pos/32]  |= (1 << (pos%32));
}
int get_one_bit_in_word(int* my_word, int pos)
{
     return  (1 & ((my_word[pos/32]  >> (pos % 32));
}
int main(void)
{
      int* array = malloc(10 * sizeof(Int));
      set_one_bit_in_word(array, 177);
      printf("%d \n", get_one_bit_in_word(array, 178));
      return 0;
}

Assuming that the size of an integer is 32 bits, the functions set_one_bit_in_word and get_one_bit_in_word set a bit and return the value of a bit in the word. In the main function, the code allocates an array of 10 integers. It then sets a bit in the word represented by array[5], at the bit position 17.

It then calls printf and tries to print the value of the bit position 18 — which is undefined, since it was not set by the function set_one_bit_in_word. Therefore, the above code snippet suffers from the coding bug of using an uninitialised value in the call to printf. However, it is not easy to detect this issue.

Assume that the error detection tool maintains shadow memory information at word granularity. Hence, when the function set_one_bit_in_word was called, the tool updates the shadow memory corresponding to the memory location initialised in that function. Since the tracking is at word granularity, the tool records that the whole word (containing the bit that is being set) is initialised, when this is not correct. Therefore, the coding error in the next line, when the uninitialised bit value is passed to printf, cannot be caught by the tool.

In order to detect this error, we need to maintain shadow memory information at bit precision — that is, we need to be able to track every bit location in our dynamically allocated memory chunks by memory shadowing. This, in turn, imposes considerable memory overheads on the application, in order to support shadow memory at such a fine granularity of tracking.

There is a trade-off involved between having the ability to track application memory locations at bit precision, versus the space overheads imposed by the shadow memory for maintaining such precision. Many of the runtime analysis tools for detecting memory errors use memory shadowing for detecting errors involving the use of undefined values in the application.

Some popular tools that use shadow values are:

1. Memcheck, based on Valgrind‘s Dynamic Binary Instrumentation (DBI) framework
2. Rational Purify from IBM
3. PIN from Intel

While this discussion focused on using shadow memory to detect undefined values, there are a number of other uses of shadow memory, such as taint checking, race detection, etc. In next month’s column, I will discuss different techniques that are used to implement shadow memory efficiently, as well as the different usage of shadow memory in runtime analysis tools.

There has been considerable research on dynamic memory error detection. One of the current state-of-the-art research tools in this area is Dr.memory. If you are interested in learning more about it, read the in-depth introduction to this tool, available at here [PDF].

My ‘must-read book’ for this month

This month’s “must-read book” suggestion comes from one of our readers, Natarajan, who recommends Programming Language Pragmatics by Michael L. Scott. He says that this book gives an excellent overview of parsing, grammar, automata theory and other key language constructs, in a manner easily understandable by the student, with lots of examples.

One of the interesting aspects of this book is that it has a section on various programming models. This section covers functional languages, logical languages, scripting languages and concurrency in a concise manner. I agree that Scott’s book is a good one to read; however, the caveat is that this is a book that requires considerable concentration to grasp the subtle language concepts, and hence should not be considered as a light afternoon read. However, it’s definitely a must if you want to become a compiler developer.