The toddler’s introduction to Dynamic Memory Allocation

Heap vulnerabilities have dominated the interest of the security research community for quite long time due to their potential of finding innovative exploitation ways. Starting in 2001 with the Vudo Malloc Tricks and Once Upon A free() followed by the Advanced Doug Lea’s malloc exploits, the Malloc Maleficarum and so on, the list of heap-type exploitation techniques is long and the concepts seem hard to grasp.

Finding such techniques is often considered a form of dark art and the reader who dives into these areas without a solid background often gets lost, then frustrated …and finally quits. Although that it was tempting to maintain this convoluted-dark-artistic spirit in this post, I finally decided to give a lighter tone, in the context of my repulsion to those people in our area who intentionally try to complicate concepts that can be explained in a more simplistic way. This post will try to shed some light in the heap wilderness and reply to questions that usually you are embarrassed to ask.

Basic Concepts and Definitions

Lets start with some basic definitions:

Memory allocation: is the process of setting aside sections of memory in a program to be used to store variables, and instances of structures and classes [1].

There are two types of memory allocation:

Static Allocation:

https://www.cs.uah.edu/~rcoleman/Common/C_Reference/MemoryAlloc.html

Characteristics: Allocation is permanent and takes place before the program execution, uses a memory space called stack, no memory reusability.

Dynamic Allocation:

https://www.cs.uah.edu/~rcoleman/Common/C_Reference/MemoryAlloc.html

Characteristics: Allocation is happening during runtime and only when the program unit (where the variable declaration takes place) is activated, uses a memory space called heap, memory can be reused and freed when not required.

The Heap: A sub-region of a program’s memory space where “plots” can be bind or released dynamically. Each of these plots can be reference using a unique arithmetic address, assigned to special variables called pointers.

ptr is a variable which is saved @0x006FFA64 and its value is 0x009B54EB which is a memory address in the heap region.

A real life example

Imagine the heap as a huge parking lot where cars are coming and going out. Alice, who works there, has to keep track of the free places to direct the incomers to the right slot. Additionally as some cars may occupy more than one slots, she has to use the available space in a way that maximises the profit.

It is obvious to assume that maintaining a full record of which slots are allocated or not is a basic requirement to route the cars to the right directions and avoid the so called fragmentation:

Fragmentation is an unwanted problem where the memory blocks cannot be allocated to the processes due to their small size and the blocks remain unused. It can also be understood as when the processes are loaded and removed from the memory they create free space or hole in the memory and these small blocks cannot be allocated to new upcoming processes and results in inefficient use of memory [2].

Similarly, heap allocation requires such a record of what memory is allocated and what is not. Additionally a memory allocator will perform maintenance tasks such as defragmenting memory by moving allocated memory around, or garbage collecting — identifying at runtime when memory is no longer in scope and deallocating it.

Allocation in practice

During the program initialisation the mmap and brk system calls are used to set up the program’s memory. The heap region is delimited by the start_brk and brk variables of the mm_struct:

• When ASLR is turned off, and since the heap is empty, both the start_brk and brk variables will point to the end of the bss segment (represented by the end_data variable).
• When ASLR is turned on, start_brk and brk will be equal to end_data+x where x is a random offset.

https://sploitfun.wordpress.com/2015/02/11/syscalls-used-by-malloc/

The following C library functions can be used by the process to request and release dynamic memory [3]:

• malloc(size):Requests size bytes of dynamic memory; if the allocation succeeds, it returns the linear address of the first memory location.
• calloc(n,size):Requests an array consisting of n elements of size size; if the allocation succeeds, it initialises the array components to 0 and returns the linear address of the first element.
• free(addr):Releases the memory region allocated by malloc( ) or calloc( ) that has an initial address of addr.
• brk(addr):Modifies the size of the heap directly; the addr parameter specifies the new value of current->mm->brk, and the return value is the new ending address of the memory region.
• sbrk(incr):Similar to brk( ), except that the incr parameter specifies the increment or decrement of the heap size in bytes.

sbrk, brk in action

Implementations

Allocating memory in an efficient manner is critical thus many implementations have been used from time to time to tackle this issue:

• Doug Lea has developed the public domain dlmalloc (“Doug Lea’s Malloc”) as a general-purpose allocator, starting in 1987.
• The GNU C library (glibc) is derived from Wolfram Gloger’s ptmalloc (“pthreads malloc”), a fork of dlmalloc with threading-related improvements.
• Since FreeBSD 7.0 and NetBSD 5.0, the old malloc implementation (phkmalloc) was replaced by jemalloc (used in Android), written by Jason Evans
• OpenBSD’s implementation of the malloc function that makes use of mmap.

Other implementations include hoard malloc, mimalloc, tcmalloc DFWMalloc and so on… In the upcoming articles we are going to focus on the ptmalloc implementations and explore some heap exploitation techniques.

References:

[1] https://www.cs.uah.edu/~rcoleman/Common/C_Reference/MemoryAlloc.html

[2] https://afteracademy.com/blog/what-is-fragmentation-and-what-are-its-types

[3] https://www.oreilly.com/library/view/understanding-the-linux/0596002130/ch08s06.html

[4] https://en.wikipedia.org/wiki/C_dynamic_memory_allocation

[5] https://github.com/emeryberger/Malloc-Implementations/tree/master/allocators

GitHub - emeryberger/Malloc-Implementations: A collection of memory allocators

Heap Memory

GitHub - shellphish/how2heap: A repository for learning various heap exploitation techniques.

https://www.cs.uah.edu/~rcoleman/Common/C_Reference/MemoryAlloc.html