[Heap Exploitation] malloc & free(glibc 2.23)

Reference

It is a simple version of dhavalkapil's work
https://heap-exploitation.dhavalkapil.com/diving_into_glibc_heap/core_functions.html

glibc 2.23 code
http://repo.or.cz/glibc.git/commit/ab30899d880f9741a409cbc0d7a28399bdac21bf

Malloc

Malloc pseudo-code

//step 1 if) size == fastbin range     'return chunk' = chunk at the end of the the fastbin list     if) return chunk == null         move on to 'smallbin case'     else)         check 'the size of the chunk' == 'requested size'         ("malloc(): memory corruption (fast)") if) size == smallbin range     if) chunk of requested size doesn't exist in smallbin         call 'malloc_consolidate'         skip into different bins     else)         check victim→bk→fd == victim         ("malloc(): smallbin double linked list corrupted")         Sets the PREV_INSUSE bit for the next chunk if) size != smallbin range     if) av has fastchunks         call 'malloc_consolidate'     //step 2 : check unsorted chunks victim : one of the chunks in unsorted bin. while(MAX_ITERS (10000) times OR unsorted bin get exhausted) {     if) !(size >= minimum (2*SIZE_SZ) AND size <= maximum (av→system_mem))         Throw an error ("malloc(): memory corruption")     if) (size of requested chunk falls in smallbin range) and (victim is the last remainder chunk)          and (it is the only chunk in the unsorted bin) and (the chunks size >= the one requested)         split into 2 chunks. one for return, the other for last remainder chunk.     else)         Remove the chunk from the unsorted bin.         Add it to smallbin or largebin depends on the size. }     //step 3 : check largebins split the chunk into two chunks('return chunk' and 'unsorted bin chunk'). if) !( unsorted_chunks(av)->fd->bk == unsorted_chunks(av) )     ("malloc(): corrupted unsorted chunks") Otherwise, the entire victim chunk will be returned     //step 4 : check a single bin(fast or small) split it into 2 chunks.('return chunk' and 'unsorted bin chunk'). if) !( unsorted_chunks(av)->fd->bk == unsorted_chunks(av) )     ("malloc(): corrupted unsorted chunks 2")     //step 5 : top chunk split it into 2 chunks.('return chunk' and 'top chunk') if) has fastchunks     call 'malloc_consolidate'     return to step of 'check unsorted chunks'

Exception codes in Malloc

fastbin check

3381       if (victim != 0) 3382         {                                                                                        3383           if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))                   3384             { 3385               errstr = "malloc(): memory corruption (fast)";                                     3386             errout: 3387               malloc_printerr (check_action, errstr, chunk2mem (victim), av);                    3388               return NULL; 3389             } 3390           check_remalloced_chunk (av, victim, nb); 3391           void *p = chunk2mem (victim);                                                          3392           alloc_perturb (p, bytes); 3393           return p;                                 3394         }

smallbin check

3416               bck = victim->bk; 3417         if (__glibc_unlikely (bck->fd != victim)) 3418                 { 3419                   errstr = "malloc(): smallbin double linked list corrupted"; 3420                   goto errout; 3421                 } 3422               set_inuse_bit_at_offset (victim, nb); 3423               bin->bk = bck; 3424               bck->fd = bin;

 

Free

Free pseudo-code

if NOT) p is before p+chunksize(p)     error ("free(): invalid pointer")   if NOT) chunk >= MINSIZE OR multiple of MALLOC_ALIGNMENT     error ("free(): invalid size")    if) chunk's size == fastbin range     if NOT) minumum <= next chunk's size <= maximum(av->system_mem)         error ("free(): invalid next size (fast)")     if) the chunk at the top == the chunk we are going to add         error ("double free or corruption (fasttop)")     if NOT) the size of the chunk at the top == the size of the chunk we are adding.         error ("invalid fastbin entry (free)")     Insert the chunk at the top of the fastbin list and return.    if) chunk is not mmapped     if) the chunk == top chunk         error ("double free or corruption (top)")     if NOT) next chunk is within the boundaries of the arena         error ("double free or corruption (out)")     if NOT) next chunk's PREVIOUS_IN_USE bit is marked         error ("double free or corruption (!prev)")     if NOT) minumum <= next chunk's size <= maximum(av->system_mem)         error ("free(): invalid next size (normal)")        if) previous chunk is not in use         unlink(previous chunk)     if) next chunk != top chunk         if) next chunk is not in use             unlink(next chunk)         Merge the chunk with previous or next, if free         if NOT) unsorted_chunks(av)->fd->bk == unsorted_chunks(av)             error ("free(): corrupted unsorted chunks")         Add it to the head of unsorted bin     else) // not top chunk         Merge the chunk into a single top chunk    else)     call munmap_chunk

 

Exception codes in Free 

SIZE_SZ = sizeof(size_t)

if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)   || __builtin_expect (chunksize (chunk_at_offset (p, size))                >= av->system_mem, 0))     {   /* We might not have a lock at this point and concurrent modifications      of system_mem might have let to a false positive.  Redo the test      after getting the lock.  */   if (have_lock       || ({ assert (locked == 0);         mutex_lock(&av->mutex);         locked = 1;         chunk_at_offset (p, size)->size <= 2 * SIZE_SZ           || chunksize (chunk_at_offset (p, size)) >= av->system_mem;         }))     {       errstr = "free(): invalid next size (fast)";       goto errout;     }   if (! have_lock)     {       (void)mutex_unlock(&av->mutex);       locked = 0;     }     }     free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);     set_fastchunks(av);   unsigned int idx = fastbin_index(size);   fb = &fastbin (av, idx);     /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */   mchunkptr old = *fb, old2;   unsigned int old_idx = ~0u;   do     {   /* Check that the top of the bin is not the record we are going to add      (i.e., double free).  */   if (__builtin_expect (old == p, 0))     {       errstr = "double free or corruption (fasttop)";       goto errout;     }   /* Check that size of fastbin chunk at the top is the same as      size of the chunk that we are adding.  We can dereference OLD      only if we have the lock, otherwise it might have already been      deallocated.  See use of OLD_IDX below for the actual check.  */   if (have_lock && old != NULL)     old_idx = fastbin_index(chunksize(old));   p->fd = old2 = old;     }   while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2)) != old2);     if (have_lock && old != NULL && __builtin_expect (old_idx != idx, 0))     {   errstr = "invalid fastbin entry (free)";   goto errout;     } }   /*   Consolidate other non-mmapped chunks as they arrive. */   else if (!chunk_is_mmapped(p)) {   if (! have_lock) {     (void)mutex_lock(&av->mutex);     locked = 1;   }     nextchunk = chunk_at_offset(p, size);     /* Lightweight tests: check whether the block is already the      top block.  */   if (__glibc_unlikely (p == av->top))     {   errstr = "double free or corruption (top)";   goto errout;     }   /* Or whether the next chunk is beyond the boundaries of the arena.  */   if (__builtin_expect (contiguous (av)             && (char *) nextchunk             >= ((char *) av->top + chunksize(av->top)), 0))     {   errstr = "double free or corruption (out)";   goto errout;     }   /* Or whether the block is actually not marked used.  */   if (__glibc_unlikely (!prev_inuse(nextchunk)))     {   errstr = "double free or corruption (!prev)";   goto errout;     }     nextsize = chunksize(nextchunk);   if (__builtin_expect (nextchunk->size <= 2 * SIZE_SZ, 0)   || __builtin_expect (nextsize >= av->system_mem, 0))     {   errstr = "free(): invalid next size (normal)";   goto errout;     }     free_perturb (chunk2mem(p), size - 2 * SIZE_SZ);     /* consolidate backward */   if (!prev_inuse(p)) {     prevsize = p->prev_size;     size += prevsize;     p = chunk_at_offset(p, -((long) prevsize));     unlink(av, p, bck, fwd);   }     if (nextchunk != av->top) {     /* get and clear inuse bit */     nextinuse = inuse_bit_at_offset(nextchunk, nextsize);       /* consolidate forward */     if (!nextinuse) {   unlink(av, nextchunk, bck, fwd);   size += nextsize;     } else   clear_inuse_bit_at_offset(nextchunk, 0);       /*   Place the chunk in unsorted chunk list. Chunks are   not placed into regular bins until after they have   been given one chance to be used in malloc.     */       bck = unsorted_chunks(av);     fwd = bck->fd;     if (__glibc_unlikely (fwd->bk != bck))   {     errstr = "free(): corrupted unsorted chunks";     goto errout;   }