2005-2006

Project Members: Chetali Nandan, Chirag Jog, Ganesh Jaju, Leena Pachkawde

Exploits in dlmalloc

Glibc (LinuxC library) implementation makes use of a popular malloc algorithm known as Doug Lea’s algorithm. It keeps track of unused memory slices called chunks using a structure known as bins. The chunks allocated to any application store their own management information, such as lists of used or free blocks, sizes of memory blocks and other useful data “in-band”, i.e. right after and before the blocks of memory that are used by the application.
Many of the memory corruption issues are related to the following aspects of the malloc implementation, one being contiguous allocation of memory and second, there is no segregation between the metadata of the chunk and the data stored in it.
Some of the problems are:

  • Heap Overflows: Overwriting from one allocated chunk or page into another. This indicates that an application is allowed to access and hence write to memory space more than what is actually allocated.
  • Nasty chunk attack: Deals with corrupting the metadata stored in the chunk and hence exploiting the bin structure of Doug Lea’s malloc (). The bin structure can be exploited in a way that allows modification of function pointers of Glibc.
  • Double Freeing: Trying to free already freed memory
  • Accessing freed memory
  • Corruption of chunk level or page level Meta data used for heap management. Consequences are corrupting the metadata and hence loss of statistics about free and allocated memory.

MITHRIL has incorporated changes in malloc (), calloc () , realloc () and free () functions in Glibc. Along with this, changes made to kernel include, changes to the implementation of mmap () especially for allocating memory on heap and addition of different page fault handler. Mithril implements the following features:

Randomization:

Linux uses brk () system call which causes contiguous allocation. malloc () implementation in MITHRIL does not make use of brk () system call for extending memory. Instead, it uses a special implementation of mmap () system call for allocating pages. As this mmap () returns randomized addresses, it makes address prediction and hence brute force attempts of heap corruption extremely difficult.
MITHRIL implements is own version of mmap () which performs its own memory allocations on heap. Also whenever an allocated page is freed, it is ummaped from the process space and hence immediately returned back to the system.

Metadata Location:

One of the notable changes incorporated by MITHRIL is to separate the metadata and the actual data. MITHRIL stores the management information at the beginning of an allocated page. Whenever a process requests for memory greater than half a page i.e. 2Kb, MITHRIL allocates an entire page and this page does not contain any metadata. Any request less than 2Kb is satisfied within a previously allocated page or by allocating a new page depending upon the free space available on the already allocated pages. This page is divided into chunks and contains metadata. Each request less than 2 kb is rounded up to multiple of 8. (E.g. Request for 50 bytes is allocated a space of 56 bytes). In contrast to the current implementation, MITHRIL stores the chunk metadata in containers at the start of the page avoiding chunk level metadata corruption. The metadata describes information such as free chunks and used chunks, largest free chunk on the page and other information useful for further allocations.
MITHRIL makes use of an algorithm viz. incremental staircase algorithm which uses the information from the containers and updates it in a way so as to provide better space utilization and efficient searching for free memory.The malloc(),calloc(),realloc() and free() algorithms have been modified to suite to the taste of MITHRIL.

Guard Page:

Allocation of a single or multiple pages is followed by allocating a guard page i.e. an inaccessible page. Guard page is a special page with neither read nor write permission. Practically, to avoid allocating one physical page for every guard page, all guard pages are mapped to a single physical address.
Any process that tries to read or write beyond the allocated page shall end up accessing the guard page and such access is immediately identified and handled. This has a side-effect of reducing the addressable heap area of the process to half.

Changes to mmap:

The modification to mmap () includes allocating a guard page after every page allocation. Whenever a single or multiple pages are mmaped, an extra page is mmaped along with it. Traditionally in Linux, when a page is allocated, it is not immediately assigned physical memory but is mapped to a fixed physical page called ZERO_PAGE. On trying to write to this page, it is actually assigned some physical address. MITHRIL makes use of this ZERO_PAGE for mapping the guard page. All the guard pages are mapped to the physical address of this ZERO_PAGE

Page Fault Handler:

MITHRIL implements its page fault handler extension. This extension identifies accesses to the guard page and causes the application which tried to access the guard page to terminate.