First Fit

Reading time: 3 minutes

First Fit

Коли ви звільняєте пам'ять у програмі, використовуючи glibc, різні "контейнери" використовуються для управління шматками пам'яті. Ось спрощене пояснення двох поширених сценаріїв: несортовані контейнери та швидкі контейнери.

Несортовані Контейнери

Коли ви звільняєте шматок пам'яті, який не є швидким шматком, він потрапляє до несортованого контейнера. Цей контейнер діє як список, де нові звільнені шматки додаються на початок (на "голову"). Коли ви запитуєте новий шматок пам'яті, аллокатор дивиться на несортований контейнер ззаду (на "хвіст"), щоб знайти шматок, який достатньо великий. Якщо шматок з несортованого контейнера більший, ніж вам потрібно, він розділяється, причому передня частина повертається, а залишкова частина залишається в контейнері.

Приклад:

• Ви виділяєте 300 байт (a), потім 250 байт (b), звільняєте a і знову запитуєте 250 байт (c).
• Коли ви звільняєте a, він потрапляє до несортованого контейнера.
• Якщо ви потім знову запитуєте 250 байт, аллокатор знаходить a на хвості і розділяє його, повертаючи частину, яка відповідає вашому запиту, і залишаючи решту в контейнері.
• c буде вказувати на попереднє a і заповнене a's.

char *a = malloc(300);
char *b = malloc(250);
free(a);
char *c = malloc(250);

Fastbins

Fastbins використовуються для малих шматків пам'яті. На відміну від несортованих бінів, fastbins додають нові шматки на початок, створюючи поведінку останній прийшов - перший вийшов (LIFO). Якщо ви запитуєте малий шматок пам'яті, аллокатор витягне з голови fastbin.

Приклад:

• Ви виділяєте чотири шматки по 20 байт кожен (a, b, c, d).
• Коли ви звільняєте їх в будь-якому порядку, звільнені шматки додаються до голови fastbin.
• Якщо ви потім запитуєте шматок на 20 байт, аллокатор поверне найостанніший звільнений шматок з голови fastbin.

char *a = malloc(20);
char *b = malloc(20);
char *c = malloc(20);
char *d = malloc(20);
free(a);
free(b);
free(c);
free(d);
a = malloc(20);   // d
b = malloc(20);   // c
c = malloc(20);   // b
d = malloc(20);   // a

Інші посилання та приклади

• https://heap-exploitation.dhavalkapil.com/attacks/first_fit
• https://8ksec.io/arm64-reversing-and-exploitation-part-2-use-after-free/
• ARM64. Використання після звільнення: створити об'єкт користувача, звільнити його, створити об'єкт, який отримує звільнений шматок і дозволяє записувати в нього, перезаписуючи позицію user->password з попереднього. Повторно використати користувача, щоб обійти перевірку пароля
• https://ctf-wiki.mahaloz.re/pwn/linux/glibc-heap/use_after_free/#example
• Програма дозволяє створювати нотатки. Нотатка міститиме інформацію про нотатку в malloc(8) (з вказівником на функцію, яку можна викликати) і вказівник на інший malloc(<size>) з вмістом нотатки.
• Атака полягатиме в створенні 2 нотаток (note0 і note1) з більшим вмістом malloc, ніж розмір інформації про нотатку, а потім звільнити їх, щоб вони потрапили в швидкий бін (або tcache).
• Потім створити ще одну нотатку (note2) з розміром вмісту 8. Вміст буде в note1, оскільки шматок буде повторно використано, де ми можемо змінити вказівник функції, щоб вказувати на функцію win, а потім використати Use-After-Free для note1, щоб викликати новий вказівник функції.
• https://guyinatuxedo.github.io/26-heap_grooming/pico_areyouroot/index.html
• Можливо виділити пам'ять, записати бажане значення, звільнити його, повторно виділити, і оскільки попередні дані все ще там, їх оброблять відповідно до нової очікуваної структури в шматку, що робить можливим встановлення значення або отримання прапора.
• https://guyinatuxedo.github.io/26-heap_grooming/swamp19_heapgolf/index.html
• У цьому випадку потрібно записати 4 всередині конкретного шматка, який є першим, що виділяється (навіть після примусового звільнення всіх з них). У кожному новому виділеному шматку його номер у масиві зберігається. Потім виділити 4 шматки (+ початково виділений), останній буде містити 4 всередині, звільнити їх і примусово повторно виділити перший, який використовуватиме останній звільнений шматок, що містить 4 всередині.