Memory Allocator Attack and Defense
Richard [email protected]@microsoft.com
The memory manager is responsible for tracking a program’s dynamic data storage.Unlike stacks which work based upon a simple FIFO/LIFO concepts, heaps require management routines to track the location of free and allocated memory chunks
Dynamic Memory Management
What approaches to dynamic memory management have been developed?What are the security profiles of memory managers used in mainstream OS’s today?What is the impact of security research on memory manager design?
Dynamic Memory Management
Today we will consider the following OS’s and their memory allocators:WindowsLinuxApple OS XOpenBSD
Dynamic Memory Management
Today we will consider the following OS’s and their memory allocators:WindowsWindows Heap ManagerRockallAllocatorLinuxDoug LeaMallocApple OS XPoul-Henning KampMallocOpenBSDOpenBSDMalloc
Dynamic Memory Management
The primary difference between the memory managers is how they track free buffersWe will split them into systems that inline management data on each chunk and those that do notManagement datainlinedin the heap is susceptible to modification when a memory corruption occurs
What’s the Difference?
Heaps withinlinedmanagementstructsexpose user APIs that walk linked lists of buffers to locate the appropriate bufferDoug LeaWindows Heap ManagerHeaps withoutinlinedmanagement data try to take advantage of kernel-supplied memory management APIs and utilize array indexing to locate buffersPoul-Henning KampOpenBSDMallocRockall
What’s the Difference?
Offensive security researchers focus on adding reliability to exploitation methods or finding new ways to manipulate management routines to gain controllable memory corruptionDefensive security researchers aim to mitigate known attacks or (rarely) attempt new heap manager designs
Security Research on Heap Allocators
dlmalloc2001 Michel "MaXX"Kaempf/ Anonymous2005 Phantasmal PhantasmagoriaWindows Heap2002 David Litchfield2004 Matt Conover /OdedHorovitz2005SecurityPatrol
Security Research on Heap Allocators
PHKMalloc2005 YvesYounanet alOpenBSDMalloc2006 BenHawkes
Security Research onHeapAllocators
Basic mechanics:A region of memory is allocated to contain buffersAn array of doubly linked lists tracking free buffers in multiples of a fixed size (usually 8) is createdOn allocation a free chunk is unlinked from the doubly linked list and the address is returned to the programOn free, a 8 byte header is written to the beginning of a buffer and the chunk is added back to the listWhen two free buffers are adjacent they will be merged into one larger chunk of free memoryLookasidelists*
Heaps with inline data
AttacksUnlinkFree buffer is removed from doubly linked list with corrupted forward and backward pointersAttacker writes 4 bytes of controlled data to a controlled locationCoalesceManipulating the flag indicating whether the previous chunk is in use can be used with a fake chunk header to cause a 4 byte write to a controlled locationLookasidelistThe head of alookasidelist can be overwritten to later return a controlled address to the next allocation of that size
Heaps with inline data
Unlink AttackScenario: Heap-based buffer overflow allows for writing into adjacent free heap blockAttack: Overwrite FLINK and BLINK values and wait for next allocationResult: Allows one or more 4-byte writes to controlled locations
Heaps with inline data
FREE HEAP BLOCK_HEAP_ENTRY+0x000 Size+0x002PreviousSize+0x004SmallTagIndex+0x005 Flags+0x006UnusedBytes+0x007SegmentIndex_LIST_ENTRY+0x000Flink+0x004 Blink
movdwordptr[ecx],eaxmovdwordptr[eax+4],ecxEAX =Flink,ECX= Blink
LookasideAttackScenario: Heap-based buffer overflow allows for control oflookasidelist management structureAttack:First heap overwrite takes control ofFlinkvalue in a free chunk with alookasidelist entryAllocation of the corrupted chunk puts the corruptFlinkvalue into thelookasidelistNextHeapAlloc() of the same sized chunk will return the corrupted pointerResult: Returns corrupted pointer from the next allocation from thelookasidelist which allows for arbitrary length overwrites
Heaps with inline data
Basic mechanics:Relies on and optimized for kernel provided virtual memory management systemHeap manager tracks allocated pages, allocated chunks and free pages in a series of directoriesAll chunks in a page are typically of the same sizeAdjacent free pages are coalesced
Heaps without inline data
Attacksfree()Control of a pointer passed to free can be abused to free memory that contains one of the heap management structures.pginfo/pgfreeManipulate the value returned by an allocation
Heaps without inline data
free() attackScenario: Heap-based buffer overflow allows for control of pointers later passed to free()Attack: Free pages with control structures on themResult: Later allocations will eventually return the page with the control structures and allow for further exploitation
Heaps without inline data
pginfoattackScenario: Heap-based buffer overflow allows for control of thepginfostructure leading to arbitrary memory corruptionAttack: Heap overflow allows for modification of thepginfo->free page pointer.Overwrite bits array to make pages seem freeResult: Allocation requests walk thestructsto find the appropriate sized buffers so returning corrupted pointer allows for writes to arbitrary locations.
Heaps without inline data
PGFREEstructpgfree{structpgfree*next;structpgfree*prev;// free pagesvoid *page;// base page dirvoid *pdir;// bytes freesize_tsize;};
PGINFOstructpginfo{structpginfo*next;void*page;ushortsize;ushortshift;ushortfree;ushorttotal;uintbits[];};
dlmallocglibcadded safe unlinkingWindows HeapSafe unlinkingChecksum for size and flagsXOR size, flags, checksum, andprevsizefieldsLookasidelist replaced by LFH in Vista
Heap Allocator Defense
phkmallocNadaOpenBSDmallocNadaSystem defenses such as ASLR and NX also apply but are not part of the heap manager’s architecture
Heap Allocator Defense
So what’s next?
“The Month of Kernel Bugs is a serious wake-up call about the vulnerability of the most fundamental element of the operating system. Begin preparing now for more, and more damaging, attacks against the OS kernel.”Rich Mogul – Gartner Nov. 2006http://www.gartner.com/resources/144700/144700/learn_from_month_of_kernel_b_144700.pdf
Windows Kernel Pool Manager
2005SoBeIt“How to exploit Windows kernel memory pool”Basic unlink() technique applies to the kernel pool
Windows Kernel Pool Manager
Pools are managed by a pool descriptor, chunks are managed by a pool chunk headerlkd>dt-v -rnt!POOL_DESCRIPTORstruct_POOL_DESCRIPTOR, 14 elements, 0x1034 bytes+0x000PoolType:Enum_POOL_TYPE+0x004PoolIndex: Uint4B+0x008RunningAllocs: Int4B+0x00cRunningDeAllocs: Int4B+0x010TotalPages: Int4B+0x014TotalBigPages: Int4B+0x018 Threshold : Uint4B+0x01cLockAddress: Ptr32 to Void+0x020PendingFrees: Ptr32 to Ptr32 to Void+0x024ThreadsProcessingDeferrals: Int4B+0x028PendingFreeDepth: Int4B+0x02cTotalBytes: Uint4B+0x030 Spare0 : Uint4B+0x034ListHeads: [512]struct_LIST_ENTRY, 2 elements, 0x8 bytes+0x000Flink: Ptr32 tostruct_LIST_ENTRY, 2 elements, 0x8 bytes+0x000Flink: Ptr32 tostruct_LIST_ENTRY, 2 elements, 0x8 bytes+0x004 Blink : Ptr32 tostruct_LIST_ENTRY, 2 elements, 0x8 bytes+0x004 Blink : Ptr32 tostruct_LIST_ENTRY, 2 elements, 0x8 bytes+0x000Flink: Ptr32 tostruct_LIST_ENTRY, 2 elements, 0x8 bytes+0x004 Blink : Ptr32 tostruct_LIST_ENTRY, 2 elements, 0x8 bytes
Windows Kernel Pool Manager
lkd>dt-v -rnt!POOL_HEADERstruct_POOL_HEADER, 8 elements, 0x8 bytes+0x000PreviousSize:BitfieldPos 0, 9 Bits+0x000PoolIndex:BitfieldPos 9, 7 Bits+0x002BlockSize:BitfieldPos 0, 9 Bits+0x002PoolType:BitfieldPos 9, 7 Bits+0x000 Ulong1 : Uint4B+0x004PoolTag: Uint4B+0x004AllocatorBackTraceIndex: Uint2B+0x006PoolTagHash: Uint2B
The good newsWe’re active researching how to add appropriate mitigations to the kernel memory management codeThe bad newsUnlike user heaps, the kernel pool is globally managedThere aren’t any free bytes to use for checksums and cookiesPerformance and compatibility concerns sometimes trump security
Windows Kernel Pool Manager
You can help. Contact us [email protected] you are interested in this research and want your ideas heard!
Windows Kernel Pool Manager
Questions?
0
Embed
Upload