Heap Introducing

• nguồn : https://guyinatuxedo.github.io/25-heap/index.html
• ref : https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-bins/
• https://www.youtube.com/watch?v=A-Qf_Q_AeFw
• ytb : https://www.youtube.com/@JHTPwner
• NOTE này được viết ra để hiểu bằng tiếng việt 😗

Heap

• là vùng nhớ được khởi tạo động
  –-> dùng để lưu trữ dữ liệu –-> theo ý người lập trình
• được dùng trong suốt quá trình chương trình thực thi
• tạo bởi những hàm như malloc(), calloc(), realloc(), …
  ===> Ảnh hưởng lớn bởi các cuộc tấn công

info Calloc()

void *calloc(size_t nmemb, size_t size);

• “calloc” or “contiguous allocation”
• calloc() doesn't use Tcache

Info Realloc()

void *realloc(void *ptr, size_t size);

• ptr = NULL -> realloc = malloc(size)
• size = 0 -> realloc = free(ptr)

Dynamic Memory Allocation in C using malloc(), calloc(), free() and realloc() - GeeksforGeeks

Chunks (vùng nhớ)

• khi 1 chương trình thực thi hàm malloc() sẽ trả về 1 con trỏ
  –-> trỏ tới 1 chunk heap (còn được gọi là vùng nhớ)
• được phân làm 2 vùng chính (cấu trúc chung):
  • metadata
    • prev size : kích thước chunk trước
    • size : kích thước chunk hiện tại
  • content

gef➤  x/4xg 0x00000000021e62a0 - 0x10
0x21e6290:	0x0000000000000000	0x0000000000000041 #PREVSIZE      SIZE
0x21e62a0:	0x0000000000000000	0x0000000000000000 #CONTENT       CONTENT

trước con trỏ của chunk đó sẽ biểu diễn 2 loại thông tin
prev size và size –-> metadata
rồi ngay con trỏ chunk đó sẽ là content

64 bits	32 bits
heap metadata = 0x10	heap metadata = 0x8
vì 1 size = 8 bytes	vì 1 size = 4 bytes

• Size sẽ được làm tròn theo nguyên tắc
• ví dụ:

malloc(0x20) ---> size là 0x31
malloc(0x30) ---> size là 0x41

• thông thường sẽ làm tròn 0x10 (dữ liệu metadata)
• malloc bao nhiêu sẽ tạo chunk có size bao gồm cả metadata
• và sẽ được cộng 1 bit đánh dấu

0x1:     Previous in Use     - Specifies that the chunk before it in memory is in use
0x2:     Is MMAPPED          - Specifies that the chunk was obtained with mmap()
0x4:     Non Main Arena      - Specifies that the chunk was obtained from outside of the main arena

• nếu ta tạo vùng nhớ quá lớn –-> tạo vùng nhớ riêng ngoài heap –-> bit 0x2 bật cho mmap()

Heap có bộ nhớ tối đa là 0x21000

• ví dụ:

#include <stdio.h>
#include <stdlib.h>

int main()
{
	char* p1 = malloc(0x20);
	char* p2 = malloc(0x200);
	char* p3 = malloc(0x2000);
	char* p4 = malloc(0x20000); //gdb break ở đây
}

tạo pointer đến vùng nhớ riêng 0x007ffff7f7f010 (địa chỉ trắng)
mà không phải heap (địa chỉ màu xanh)

gef➤  p/x 0x0055555557a000 - 0x00555555559000    # [heap]
$1 = 0x21000
gef➤  vm 0x007ffff7f7f010
[ Legend:  Code | Heap | Stack ]
Start              End                Offset             Perm Path
0x007ffff7f7f000 0x007ffff7fa3000 0x00000000000000 rw- 

• metadata:

gef➤  x/20xg 0x007ffff7f7f010 - 0x10
0x7ffff7f7f000:	0x0000000000000000	0x0000000000021002 #bit 0x2
0x7ffff7f7f010:	0x0000000000000000	0x0000000000000000
0x7ffff7f7f020:	0x0000000000000000	0x0000000000000000
0x7ffff7f7f030:	0x0000000000000000	0x0000000000000000
0x7ffff7f7f040:	0x0000000000000000	0x0000000000000000
0x7ffff7f7f050:	0x0000000000000000	0x0000000000000000
0x7ffff7f7f060:	0x0000000000000000	0x0000000000000000
0x7ffff7f7f070:	0x0000000000000000	0x0000000000000000
0x7ffff7f7f080:	0x0000000000000000	0x0000000000000000
0x7ffff7f7f090:	0x0000000000000000	0x0000000000000000

• cú pháp gọi kiểm tra

gef➤ heap chunks
--

gef➤ heap chunk <addr>
--

Bin (ngăn xếp)

• chứa chunks đã được giải phóng ( bởi hàm free() )
• có 5 loại bins tất cả :
  • 62 doubly-linked small bins (up to 0x200 bytes)
  • 63 doubly-linked large bins (over 0x200 bytes)
  • 1 doubly-linked unsorted bin (not fit fastbins or tcache bins)
  • 7 singly-linked fast bins (0x20 to 0x80 bytes)
  • 64 singly-linked tcache bins per thread (0x20 to 0x410 bytes)

The small, large, and unsorted bins implement the basic recycling strategy of the heap
The fast bins and tcache bins are optimizations that layer on top of these.

Confusingly, the small, large, and unsorted bins all live together in the same array in the heap manager’s source code
Index 0 is unused, 1 is the unsorted bin, bins 2-64 are small bins and bins 65-127 are large bins

👀 fastbins

• đối với libc < 2.27 thì chi có fastbins, k có tcache
• không giới hạn chunk sau khi free()
• là 1 dslk đơn
• free 1 chunk có size từ 0x20 đến 0x80 (đã bao gồm heap metadata) –-> đưa vào fastbins
• ví dụ:

────────────────────── Fastbins for arena 0x7ffff7dd1b20 ──────────────────────
Fastbins[idx=0, size=0x10]  ←  Chunk(addr=0x602010, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x602030, size=0x20, flags=PREV_INUSE)
Fastbins[idx=1, size=0x20]  ←  Chunk(addr=0x602050, size=0x30, flags=PREV_INUSE)
Fastbins[idx=2, size=0x30]  ←  Chunk(addr=0x602080, size=0x40, flags=PREV_INUSE)
Fastbins[idx=3, size=0x40]  ←  Chunk(addr=0x6020c0, size=0x50, flags=PREV_INUSE)
Fastbins[idx=4, size=0x50]  ←  Chunk(addr=0x602110, size=0x60, flags=PREV_INUSE)
Fastbins[idx=5, size=0x60]  ←  Chunk(addr=0x602170, size=0x70, flags=PREV_INUSE)
Fastbins[idx=6, size=0x70]  ←  Chunk(addr=0x6021e0, size=0x80, flags=PREV_INUSE)

• khi malloc() lại cùng 1 size thì chương trình sẽ lấy cái chunk (cùng size) vừa free đó trả về sử dụng tiếp
• fastbins được tổ chức theo cơ chế LIFO (last in first out)
• cú pháp gọi kiểm tra

gef➤ heap bins
--

👀 tcache

• về cơ bản giống fastbins nhưng có vài điểm khác
• là loại ngăn xếp mới được giới thiệu ở libc 2.26 trở lên
• cũng là 1 dslk đơn
• mỗi thread là 1 tcache khác nhau
• chứa tối đa 7 chunks cùng 1 size (nhưng kích thước lớn hơn, đa dạng hơn)
• các chunk trong bin được liên kết với nhau thông qua fw_pointer
  ===> khi malloc() lại sẽ tuân theo quy tắc LIFO (last in first out)
  (chunk free() cuối cùng sẽ là chunk đầu trong bin)
  (được ra đầu tiên khi malloc() cùng size)
• khi free(), chunk được ưu tiên đưa vào tcache, khi đầy 7 chunks cùng 1 size trong tcache –-> đẩy xuống fastbins | unsortedbin | largebin | .v.v
• ví dụ

#include <stdlib.h>

void main(void)
{
  char *p0, *p1, *p2, *p3, *p4, *p5, *p6, *p7;

  p0 = malloc(0x10);
  p1 = malloc(0x10);
  p2 = malloc(0x10);
  p3 = malloc(0x10);
  p4 = malloc(0x10);
  p5 = malloc(0x10);
  p6 = malloc(0x10);
  p7 = malloc(0x10);

  malloc(10); // Here to avoid consolidation with Top Chunk

  free(p0);
  free(p1);
  free(p2);
  free(p3);
  free(p4);
  free(p5);
  free(p6);
  free(p7); // gdb break ở đây
}

• compile code C trên: gcc run.c -o run

───────────────────── Tcachebins for arena 0x7ffff7faec40 ─────────────────────
Tcachebins[idx=0, size=0x10] count=7  ←  Chunk(addr=0x555555559320, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559300, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x5555555592e0, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x5555555592c0, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x5555555592a0, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559280, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559260, size=0x20, flags=PREV_INUSE)
────────────────────── Fastbins for arena 0x7ffff7faec40 ──────────────────────
Fastbins[idx=0, size=0x10]  ←  Chunk(addr=0x555555559340, size=0x20, flags=PREV_INUSE)
Fastbins[idx=1, size=0x20] 0x00
Fastbins[idx=2, size=0x30] 0x00
Fastbins[idx=3, size=0x40] 0x00
Fastbins[idx=4, size=0x50] 0x00
Fastbins[idx=5, size=0x60] 0x00
Fastbins[idx=6, size=0x70] 0x00
───────────────────── Unsorted Bin for arena 'main_arena' ─────────────────────
[+] Found 0 chunks in unsorted bin.
────────────────────── Small Bins for arena 'main_arena' ──────────────────────
[+] Found 0 chunks in 0 small non-empty bins.
────────────────────── Large Bins for arena 'main_arena' ──────────────────────
[+] Found 0 chunks in 0 large non-empty bins.

• có thể chứa 64 tcache lists, với idx values khoảng 0-63, chunk sizes nằm giữa 0x20-0x410
• nhấn mạnh rằng count=7 là tối đa cho mỗi thread tcache, k phải đại diện cho tổng chunk trong tcache
• example: (14 chunks chia vào 2 bins)

─────────────────────────────────────────────────────────────────────────────────── Tcachebins for arena 0x7ffff7faec40 ───────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x10] count=7  ←  Chunk(addr=0x555555559320, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559300, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x5555555592e0, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x5555555592c0, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x5555555592a0, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559280, size=0x20, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559260, size=0x20, flags=PREV_INUSE)
Tcachebins[idx=1, size=0x20] count=7  ←  Chunk(addr=0x555555559460, size=0x30, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559430, size=0x30, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559400, size=0x30, flags=PREV_INUSE)  ←  Chunk(addr=0x5555555593d0, size=0x30, flags=PREV_INUSE)  ←  Chunk(addr=0x5555555593a0, size=0x30, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559370, size=0x30, flags=PREV_INUSE)  ←  Chunk(addr=0x555555559340, size=0x30, flags=PREV_INUSE)
──────────────────────────────────────────────────────────────────────────────────── Fastbins for arena 0x7ffff7faec40 ────────────────────────────────────────────────────────────────────────────────────
Fastbins[idx=0, size=0x10] 0x00
Fastbins[idx=1, size=0x20] 0x00
Fastbins[idx=2, size=0x30] 0x00
Fastbins[idx=3, size=0x40] 0x00
Fastbins[idx=4, size=0x50] 0x00
Fastbins[idx=5, size=0x60] 0x00
Fastbins[idx=6, size=0x70] 0x00
─────────────────────────────────────────────────────────────────────────────────── Unsorted Bin for arena 'main_arena' ───────────────────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in unsorted bin.
──────────────────────────────────────────────────────────────────────────────────── Small Bins for arena 'main_arena' ────────────────────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in 0 small non-empty bins.
──────────────────────────────────────────────────────────────────────────────────── Large Bins for arena 'main_arena' ────────────────────────────────────────────────────────────────────────────────────
[+] Found 0 chunks in 0 large non-empty bins.

---

đặc điểm chung

• fastbins và tcache đều là dslk đơn
• khi 1 chunk được đưa vào tcachebin hoặc fastbins sẽ có thêm 1 tham số:
  • fw (forward pointer): là 1 con trỏ trỏ tới thằng tiếp theo

fw của thằng 93c0 là 9390
tương tự thì fw của 9390 là 9360

---

👀 unsorted, large, small bins

• là dslk đôi
• về cơ bản chúng giống nhau

0x00:         Not Used
0x01:         Unsorted Bin
0x02 - 0x3f:  Small Bin
0x40 - 0x7e:  Large Bin

• là thằng sau trỏ tới thằng trước, thằng trước lại trỏ ra thằng sau
• khi free 1 chunk có size lớn hơn 0x410 (maximum của tcache và out of range fastbins) –-> đưa vào unsorted bin

#include <stdio.h>
#include <stdlib.h>

int main()
{
	char* p1[8];
	char* p2[8];

	for (int i=0; i<8; i++)
		p1[i] = malloc(0x20);  //0x28
	for (int i=0; i<8; i++)
		p2[i] = malloc(0x410); //0x420

	char* p3 = malloc(0x2000);
	char* p4 = malloc(0x20000);
	for (int i=0; i<8; i++)
		free(p1[i]); 
	for (int i=0; i<8; i++) //gdb break ở đây
		free(p2[i]); 
	free(p3);
	free(p4);
}

free p2[i] lần 1
chunk 9420, size=0x420

free p2[i] lần 2
chunk 9420, size=0x840

• ở đây k tạo cái chunk thứ 2 có size là 0x420 mà lại gộp chunk thành size 0x840 và sài chung 1 địa chỉ 9420. tại sao ?

---

🟥 unsorted bin sẽ có 3 dạng

👉 gộp chunks

• hiện tượng gộp chunk, dslk đôi sẽ cho ta 2 con trỏ fw (forward ptr) và bk (backward ptr) cùng trỏ tới 1 vùng, và vùng đó gọi là main_arena

👉 phân bổ chunks

• giả sử ta có 1 ubin (exploit trên libc2.23 không có tcache)

ubin 4020 có size 0xa1

• khi ta request 1 chunk có size khác 0x70 (tránh lấy lại fastbin) như là size 0x78
• thì sự phân bổ diễn ra như sau

xuất hiện ubin mới 40a0
chunk 4020 có size mình request là 0x80
(nếu không ow data nào thì fw_pointer vẫn là main_area)
ubin 40a0 có size còn lại từ size cũ (0xa0-0x80=0x20)

👉 trỏ tới chunk kế tiếp

#include <stdio.h>
#include <stdlib.h>

int main()
{
	char* p1[8];
	char* p2[8];

	for (int i=0; i<8; i++){
		p1[i] = malloc(0x20);  
		p2[i] = malloc(0x410); 
	}
	char* p3 = malloc(0x2000);
	char* p4 = malloc(0x20000);

	for (int i=0; i<8; i++){
		free(p1[i]);     // gdb break ở đây
		free(p2[i]); 
	}

	free(p3);
	free(p4);
}

• source code lúc này sẽ xen kẽ chunk nhỏ chunk lớn
• khi free chunk nhỏ –-> đưa vào tcachebins
• khi free chunk lớn –-> đưa vào unsorted bin
• tiếp tục loop, free chunk nhỏ rồi tới chunk lớn

khi free có chunk chen giữa, xảy ra hiện tượng trỏ
con trỏ fw và bk sẽ khác

• chunk đầu tiên là 9720, có fw trỏ tiếp thằng 92d0

thằng 92d0 là thằng 92c0 ngay x/20xg đầu tiên
chỉ là 92d0 trỏ ngay phần content, còn 92c0 trỏ ngay phần heap metadata

• có luôn bk trỏ về main_arena

• đặc biệt là chunk đầu trỏ về chunk sau và chunk sau lại trỏ về chunk đầu

9710 là phần heap metadata, 9720 là chunk đầu

===> Không gộp vì do giữa 2 chunk cùng size bị ngăn cách bới 1 chunk khác

---

🤌 small bins | large bins

#include <stdio.h>
#include <stdlib.h>

int main()
{
	char* p1[8];
	char* p2[8];

	for (int i=0; i<8; i++)
		p1[i] = malloc(0x20);  
	for (int i=0; i<8; i++)
		p2[i] = malloc(0x410);
	malloc(0x10);

	for (int i=0; i<8; i++)
		free(p1[i]);
	for (int i=0; i<2; i++)
		free(p2[i]); 

	malloc(0x200);  // gdb break ở đây
	malloc(0x2000);
}

lúc này khi free 2 lần của p2[i]

• tiếp tục malloc() có kích thước 0x200
• kiểm tra ở tcache và fastbin k có kích thước nào thoả –-> loại
• nhưng ở unsorted bin có 1 chunk size=0x840, lớn hơn 0x200
  –-> trích bớt 0x200+0x10 size
• lúc này unsorted bin còn 0x630

xem ở 2 dòng highlight

• nếu tiếp tục malloc() cho kích thước 0x2000
• cả tcache, fastbins, unsorted bin đều k thoả –-> lấy từ top chunk

before

after

• lúc này unsorted bin chứa chunk có size 0x630 , khi malloc() 1 kích thước còn lớn hơn cả unsorted bin thì từ unsorted thành sorted =)))))))))
• theo nghĩa tiếng anh là chunk size 0x630 ấy chưa dc phân loại, khi mà đc malloc() cho 1 chunk lớn hơn 0x630 thì lúc này sẽ phân chunk 0x630 ấy xuống large bins, còn chunk nhỏ 0x30 sẽ phân vào small bins

small bin lấy từ fastbins xuống

---

🟥 từ unsorted xuống large hoặc small

• khi unsorted bin chứa chunk có size < 0x410 đồng thời malloc() 1 chunk có size lớn hơn

–-> phân vào small bins
–-> còn lại lớn hơn 0x410 phân vào large bins

• source mẫu:

#include <stdio.h>
#include <stdlib.h>

int main()
{
	char* p1[8];
	char* p2[8];

	for (int i=0; i<8; i++)
		p1[i] = malloc(0x20);  
	for (int i=0; i<8; i++)
		p2[i] = malloc(0x410);
	malloc(0x10);

	for (int i=0; i<8; i++)
		free(p1[i]);
	for (int i=0; i<2; i++)
		free(p2[i]); 

	malloc(0x200);  
	malloc(0x200); 
	malloc(0x200);  // gdb break ở đây
	malloc(0x2000);
}

---

Consolidation (sự gộp chunk)

• nói đơn giản thì đây là 1 cái proctect combat fragmentation (chống tấn công phân mảnh)
• ví dụ: nếu allocate 1 đống chunk tiny khiến lãng phí –-> bộ nhớ chia làm nhiều phần
• và vấn đề xảy ra khi cố gắng malloc() để cấp phát 1 bộ nhớ khủng hơn nó –-> phải dùng bộ nhớ khác cho nó và lãng phí tài nguyên
• bằng cách gợp freed chunks liền kề thành 1 freed chunk lớn hơn –-> nhiều space có thể malloc() lại hơn

---

Top chunk

• là vùng bộ nhớ khi mình malloc() sẽ lấy từ top chunk ra
• có thể nói để giữ các khối bộ nhớ chưa được phân bổ
• khi các bin không thoả size, malloc() sẽ lấy từ top chunk cắt một đoạn để phân bổ bộ nhớ do yêu cầu của malloc()

🎯 Top chunk consolidation

• rất nhiều loại heap attack –-> chuyển qua list bin
• cần các freed chunks trong các bins
• gộp chunk với top chunk có thể ngăn chặn điều đó

🎯 ngăn gộp top chunk

• malloc() một đoạn nhỏ ở giữa các freed chunks và top chunk

Chunk(addr=0x55555555a8c0, size=0x420, flags=PREV_INUSE)
    [0x000055555555a8c0     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555ace0, size=0x420, flags=PREV_INUSE)
    [0x000055555555ace0     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555b100, size=0x420, flags=PREV_INUSE)
    [0x000055555555b100     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555b520, size=0x20, flags=PREV_INUSE)    #HERE
    [0x000055555555b520     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555b540, size=0x1ead0, flags=PREV_INUSE)
    [0x000055555555b540     00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00    ................]
Chunk(addr=0x55555555b540, size=0x1ead0, flags=PREV_INUSE)  ←  top chunk

---

Main Arena

• contains the head pointers for the bin lists

gef➤  heap bins
[+] No Tcache in this version of libc
────────────────────── Fastbins for arena 0x7ffff7dd1b20 ──────────────────────
Fastbins[idx=0, size=0x10]  ←  Chunk(addr=0x602010, size=0x20, flags=PREV_INUSE)
Fastbins[idx=1, size=0x20] 0x00
Fastbins[idx=2, size=0x30] 0x00
Fastbins[idx=3, size=0x40] 0x00
Fastbins[idx=4, size=0x50] 0x00
Fastbins[idx=5, size=0x60] 0x00
Fastbins[idx=6, size=0x70] 0x00
───────────────────── Unsorted Bin for arena 'main_arena' ─────────────────────
[+] Found 0 chunks in unsorted bin.
────────────────────── Small Bins for arena 'main_arena' ──────────────────────
[+] Found 0 chunks in 0 small non-empty bins.
────────────────────── Large Bins for arena 'main_arena' ──────────────────────
[+] Found 0 chunks in 0 large non-empty bins.
gef➤  x/20g 0x7ffff7dd1b20
0x7ffff7dd1b20 <main_arena>:  0x0 0x602000
0x7ffff7dd1b30 <main_arena+16>: 0x0 0x0
0x7ffff7dd1b40 <main_arena+32>: 0x0 0x0
0x7ffff7dd1b50 <main_arena+48>: 0x0 0x0
0x7ffff7dd1b60 <main_arena+64>: 0x0 0x0
0x7ffff7dd1b70 <main_arena+80>: 0x0 0x602120
0x7ffff7dd1b80 <main_arena+96>: 0x0 0x7ffff7dd1b78
0x7ffff7dd1b90 <main_arena+112>:  0x7ffff7dd1b78  0x7ffff7dd1b88
0x7ffff7dd1ba0 <main_arena+128>:  0x7ffff7dd1b88  0x7ffff7dd1b98
0x7ffff7dd1bb0 <main_arena+144>:  0x7ffff7dd1b98  0x7ffff7dd1ba8

---

Heap Exploitation

• https://hackmd.io/@trhoanglan04/heap_exploit

Deep understanding of heap implementation

• https://hackmd.io/@trhoanglan04/deeper_in_heap