Scribd
Upload
15 views42 pages

Understanding Heap Memory Management

The document provides an overview of heap memory, including its purpose for dynamic memory allocation and the functions used such as malloc(), realloc(), and free(). It discusses various heap implementations in Linux and Windows, highlighting specific functions and management techniques. Additionally, it addresses heap vulnerabilities and the algorithms used for memory allocation and deallocation in Windows systems.

Uploaded by

Bruno DL
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views42 pages

Understanding Heap Memory Management

The document provides an overview of heap memory, including its purpose for dynamic memory allocation and the functions used such as malloc(), realloc(), and free(). It discusses various heap implementations in Linux and Windows, highlighting specific functions and management techniques. Additionally, it addresses heap vulnerabilities and the algorithms used for memory allocation and deallocation in Windows systems.

Uploaded by

Bruno DL
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Heap

! Heap  
" Sometimes  called  the  free  store  
" Dynamically  allocated  area  of  memory  
" Stores  global  variables  
" Stores  large  variables  
" Stores  dynamic  variables  
" Controlled  by  the  heap  manager  
" Heap  implementations  vary  from  system  to  
system  
! Heap  exploits  are  heap  implementation  specific  
! So,  heap  exploits  are  system  specific  

2
Dynamic  Memory  Allocation  

! malloc()  
" Allocate  a  chunk  of  memory  for  use  
! realloc()  
" Resizes  an  allocated  chunk  of  memory  
! free()  
" Return  a  chunk  of  allocated  memory  to  the  system  

3
Dynamic  Memory  Allocation  

! Properly  Used  Memory  Allocation  

4
Example  Heap  Vulnerabilities  

! Shellcoder’s  Handbook  (Second  Edition)  

5
Linux  malloc  

! Doug  Lea’s  malloc()  


" Called  dlmalloc  
" Unallocated  memory  is  grouped  into  “bins”  
! A  bin  is  a  linked  list  to  all  blocks  of  similar  sizes  
! Wolfram  Gloger’s  malloc()  
" Called  ptmalloc  
" Based  on  dlmalloc  
! glibc’s  malloc()  
" Modified  ptmalloc2  since  glibc  v2.3  
6
dlmalloc  

! Doug  Lea’s  malloc()  

[Link] 7
ptmalloc  

! Wolfram  Gloger’s  malloc()  


" Includes  fastbins  

[Link]
8
Windows  Private  Heaps  

! Private  Heaps  
" Every  process  has  a  default  heap  
" We  can  create  additional  private  heaps  
" HeapCreate()  
" HeapDestroy()  
" HeapAlloc()  
" HeapReAlloc()  
" HeapFree()  

9
Windows  Heaps  

! Process  Environment  Block  (PEB)  


PEB
0x0010 Default
Heap
0x0080 Heaps
Count
0x0090 Heap
List

0x70000 Default Heap

0x170000
2nd Heap

10
[Link]
Windows  Heap  

! Windows  
" Heap  is  allocated  into  8-­‐byte  chunks  
! Called  “allocation  units”  or  “indexes”  
" A  set  of  allocated  chunks  is  called  a  “block”  
! 18  bytes  are  needed,  how  large  is  our  block?  
" Block  headers  

11
Windows  Heap  

! Windows  Heap  Block  Headers  


" Size:  (size  of  block  +  header)  /  8  
" Segment  index:  memory  segment  for  block  
" Unused:  amount  of  free  (additional)  bytes  
" Flink/Blink:  pointer  to  next/previous  free  block  

12
Windows  Heap  

! Windows  Free  List  


" Free  blocks  are  recorded  in  an  array  of  128  doubly-­‐
linked  lists  
! Called  the  free  list  

13
Windows  Heap  

! Windows  Free  List  


" Index  of  0  holds  blocks  larger  than  127  chunks  
! And  less  than  512K  
! Sorted  from  smallest  to  largest  
" Index  of  1  is  unused  
! Cannot  have  an  8  byte  block  

14
Windows  Heap  

! Windows  Lookaside  List  


" Freed  blocks  (marked  as  busy)  are  recorded  in  an  
array  of  128  singly-­‐linked  lists  
! Called  the  lookaside  list,  used  for  fast  allocates  
" Blocks  are  added  to  the  lookaside  list  upon  free()  
! Lookaside  list  is  initially  empty  

15
Windows  Heap  

! Windows  Lookaside  List  


" Blocks  are  freed  to  the  lookaside  list  first  
! Each  lookaside  list  item  can  only  hold  4  blocks  
! Blocks  are  restored  to  the  free  list  if  the  lookaside  is  
full  
" Blocks  are  allocated  from  the  lookaside  list  first  

16
Windows  Heap  

! Windows  Free  Block  Heap  Management  


" From:  
[Link]  

17
Windows  Heap  

! Allocation  Algorithm  
" If  size  >=  512K,  virtual  memory  is  used  (not  on  heap)  
" If  <  1K,  first  check  the  Lookaside  lists.  If  there  are  no  free  
entries  on  the  Lookaside,  check  the  matching  free  list  
" If  >=  1K  or  no  matching  entry  was  found,  use  the  heap  
cache  (not  discussed  in  this  presentation).  
" If  >=  1K  and  no  free  entry  in  the  heap  cache,  use  
FreeLists[0]  (the  variable  sized  free  list)  
" If  a  free  entry  can’t  be  found,  extend  heap  as  needed  

[Link]
18
Windows  Heap  

! Free  Algorithm  
" If  the  chunk  <  512K,  it  is  returned  to  a  lookaside  or  
free  list  
" If  the  chunk  <  1K,  put  it  on  the  lookaside  (can  only  
hold  4  entries)  
" If  the  chunk  <  1K  and  the  lookaside  is  full,  put  it  on  
the  free  list  
" If  the  chunk  >  1K  put  it  on  heap  cache  (if  present)  
or  FreeLists[0]    

[Link]
19
Windows  Heap  

! Coalescing  
" Say,  two  adjacent  memory  blocks  are  freed  
" Windows  tries  to  combines  these  memory  blocks  
! Takes  time  
! Reduces  fragmentation  
" Combining  freed  memory  blocks  in  this  manner  is  
called  “coalescing”  
" Only  blocks  going  into  the  free  list  coalesce  

20
Windows  Heap  

! Free  to  Lookaside  Algorithm  


" Free  buffer  to  Lookaside  list  only  if:  
! The  lookaside  is  available  (e.g.,  present  and  
unlocked)  
! Requested  size  is  <  1K  (to  fit  the  table)  
! Lookaside  is  not  “full”  yet  (no  more  than  3  entries  
already)  
" To  add  an  entry  to  the  Lookaside:  
! Insert  into  appropriate  singly-­‐linked  list  
! Keep  the  buffer  flags  set  to  busy  (to  prevent  
coalescing)  
[Link]
21
Heap  Spraying  

! Heap  Spraying  
" Technique  developed  by  SkyLined  
" Attempts  to  “spray”  information  on  the  heap  
! Makes  position  of  allocated  object  predictable  
" Popular  for  browser  exploitation  (esp.  JavaScript)  

22
Heap  Spraying  

! Heap  Spraying  
" Load  many  NOP/shellcode  pairs  to  target  heap  
" Typically,  top  of  heap  is  allocated  out  first  
" So,  a  jump  into  this  memory  space  has  a  good  
chance  of  landing  in  a  NOP/shellcode  pair  

23
Heap  Spraying  

! Advanced  Heap  Spraying  


" Say,  we  can  overwrite  a  C++  object  on  the  heap  
" We  can  point  it  into  the  heap  
" Perform  our  heap  spray  
" Wait  for/invoke  a  virtual  function  call  
! Ex:  Virtual  function  at  [vtable  +  8]  is  called  

24
Heap  Feng  Shui  

! Heap  Feng  Shui  


" Techniques  that  manipulate  the  heap  layout  
! Often  dependent  on  size  of  blocks  
" Plunger  technique  
! Allocate  and  free  6  large  blocks  
! Clears  the  heap  cache    
" Defragmenting  the  heap  
! Allocate  blocks  that  are  the  size  of  our  exploit  
! All  available  “holes”  are  filled  and  new  blocks  are  
allocated  from  the  end  of  the  heap  
" …Many  others:  
[Link]  

25
Targets  for  a  Heap  Overflow    
! Control  Pointers  
" Global  offset  table  (GOT)  
" Global  function  pointers  
" Virtual  function  pointers  (vtable)  
" PEB  function  pointer  
" Thread  environment  block  (TEB)  
" Unhandled  exception  filter  (UEF)  
" Vectored  exception  handling  (VEH)  
" Destructors  (.DTORS)  
" atexit  handlers  
" Stack  values  
" Function  pointers  in  general  
! Global/Dynamically  Allocated  Data  
" Variables  on  the  heap  

26
Exploiting  Heap  Metadata  

! Coalesce-­‐on-­‐Free  4-­‐byte  Overwrite  


" Say,  we  have  an  allocated  block  (with  an  overflow)  
followed  by  a  free  block  in  memory  
" We  can  overwrite  Flink  and  Blink  

27
Exploiting  Heap  Metadata  

! Coalesce-­‐on-­‐Free  4-­‐byte  Overwrite  


" Say,  we  have  an  allocated  block  (with  an  overflow)  followed  
by  a  free  block  in  memory  
" We  can  overwrite  Flink  and  Blink  
" If  our  overflow  block  is  coalesced,  this  code  is  executed:  

" Meaning?  
! Arbitrary  32  bit  overwrite  (UEF  is  a  common  target)  
! Great  method  for  systems  <  XPSP2  

28
Exploiting  Heap  Metadata  

! Lookaside  List  Head  Overwrite  


" 4-­‐to-­‐n-­‐byte  overwrite  
" Overwrite  a  lookaside  list  head  
" Allocate  that  head  
" Allocated  chunk  points  to  value  of  overwrite  
" We  can  overwrite  whatever  we  want  
! It’s  like  having  access  to  raw  malloc  calls  
! Common  situation  for  heap  exploits  

29
Exploiting  Heap  Metadata  

! Lookaside  List  Head  Overwrite  (How-­‐to)  


" Use  the  Coalesce-­‐on-­‐Free  Overwrite,  with  these  values:  
! [Link]  =  &Lookaside[ChunkSize]  where  ChunkSize  is  a  
pretty  infrequently  allocated  size  
! [Link]  =  what  we  want  a  pointer  to  
" To  calculate  the  [Link]  value:  
! LookasideTable  =  HeapBase  +  0x688  
! Index  =  (ChunkSize/8)+1  
! [Link]  =  LookasideTable  +  Index  *  EntrySize  (0x30)  
" Set  [Link]  =  0x20,  [Link]  =  1-­‐63,  
[Link]  =  1,  [Link]  =  1  

[Link]
30
Exploiting  the  UEF  

! Unhandled  Exception  Filter  (UEF)  


" “Last  ditch  effort”  exception  handler  
" Our  goal  is  to  install  our  own  UEF  

31
Exploiting  the  UEF  

! Unhandled  Exception  Filter  (UEF)  


" Location  is  OS  and  SP  dependent  
" Find  the  location  by  disassembling  
SetUnhandledExceptionFilter()  
" NGSSoftware  example:  

77E7E5A1 mov ecx, dword ptr [esp+4]


77E7E5A5 mov eax, [77ED73B4h]
77E7E5AA mov dword ptr ds:[77ED73B4h], ecx
77E7E5B0 ret 4

" UEF  =  0x77ED73B4  

32
Exploiting  the  UEF  

! Unhandled  Exception  Filter  (UEF)  


" Windows  XP  
" EDI  contains  a  pointer  to  an  EXCEPTION_POINTERS  
structure  on  the  stack  when  UEF  is  called  
! 0x78  bytes  past  EDI  there’s  a  pointer  to  the  end  of  our  
buffer  (we  could  make  that  the  start  of  our  shellcode!)  
" Use  our  arbitrary  32-­‐bit  overwrite  to  patch  the  UEF  
address  to  point  to:  
! WinXP:  call  dword  ptr  [edi+0x78]  
! Found  in  [Link],  [Link],  [Link]  
! Win2000:  call  dword  ptr  [esi+0x4c]  
! Or:  call  dword  ptr  [ebp+0x74]  
" An  unhandled  exception  will  trigger  the  UEF  

33
Exploiting  the  VEH  

! Vectored  Exception  Handler  (VEH)  


" New  feature  starting  in  Windows  XP  
" Vectored  exception  handling  occurs  before  any  
frame-­‐based  handlers  (like  SEH)  
" Pointer  to  first  VEH  node  is  at  a  hardcoded  address  
! Our  goal  is  to  overwrite  this  pointer  

34
Exploiting  the  VEH  

! Vectored  Exception  Handler  (VEH)  


" _VECTORED_EXCEPTION_NODE  stored  on  
heap  
" Windows  XP  SP2,  0x77FC3210
! Pointer  to  first  _VECTORED_EXCEPTION_NODE

struct _VECTORED_EXCEPTION_NODE {
DWORD m_pNextNode;
DWORD m_pPreviousNode;
PVOID m_pfnVectorHandler;
}

35
Exploiting  the  VEH  

! Vectored  Exception  Handler  (VEH)  


" “Create”  our  own  VEH  structure  
! Fix  the  first  VEH  pointer  to  point  to  our  VEH  struct  
" We  find  a  pointer  to  our  buffer  on  the  stack  
! Set  the  first  VEH  pointer  to  [buf_ptr  -­‐  8]  

36
Exploiting  the  PEB  

! Process  Environment  Block  (PEB)  


" Stored  in  heap  
" Each  process  has  a  single  modifiable  PEB  
! Contains  function  pointers  to:  
! RtlEnterCriticalSection  (+0x20  in  PEB)  
" Called  FastPebLockRoutine  in  PEB  
! RtlExitCriticalSection  (+0x24  in  PEB)  
" Called  FastPebUnlockRoutine  in  PEB  
! Example  use:  
! ExitProcess()  #  RtlAcquirePebLock()  #  
[Link]  #  RtlEnterCriticalSection()  

37
Exploiting  the  PEB  

! Process  Environment  Block  (PEB)  


" The  PEB  address  is  predictable  
! In  WinXP,  NT4,  2000,  2003  
! Not  exploitable  in  Win2003  
! Function  pointers  are  randomized  
" Exploit  
! Overwrite  RtlEnterCriticalSection  with  pointer  to  
instruction  that  executes  the  back  of  our  buffer  

38
Exploiting  the  TEB  

! Thread  Environment  Block  (TEB)  


" TEB  exception  handler  pointer  
! First  TEB  has  a  base  address  of  0x7FFDE000
! Grows  towards  0x00000000
! Say  the  thread  exits  
! A  new  thread  will  be  assigned  the  old  thread’s  TEB  
address  
! Leads  to  a  “messy”  and  sometimes  unreliable  TEB  
! Reliable  if  the  address  is  predictable  
" Once  again,  replace  pointer  with  address  to  an  
instruction  that  will  execute  the  back  of  our  buffer  

39
Repairing  the  Heap  

! Repairing  the  Heap  


" Necessary  step  for  exploit  stability  
" Reset  the  heap  to  look  like  a  brand  new  heap  
! Generic,  reusable  method  
! All  allocated  blocks  will  stay  intact  
! New  allocations  are  still  possible  
! See  NGSSoftware  code  (asm-­‐repair-­‐heap)  

40
OllyDbg  HeapVis  Plugin  

41
Questions/Comments?  

42

You might also like