Join
Leakinfo
@leakinfo
April 10, 2022

Хакер - Круче кучи! Разбираем в подробностях проблемы heap allocation

https://t.me/hacker_frei

Вячеслав Москвин

Содержание статьи

  • Основы GDB
  • Структура чанков
  • Арена
  • Флаги
  • Bins
  • Тестовая программа
  • Практика
  • Fast bin Dup
  • Что еще почитать про кучу

Не­кото­рые уяз­вимос­ти воз­ника­ют из‑за оши­бок с управле­нием памятью, выделен­ной на куче. Механизм экс­плу­ата­ции этих уяз­вимос­тей слож­нее, чем обыч­ное перепол­нение на сте­ке, поэто­му не все уме­ют с ними работать. Даже курс Cracking the perimeter (OSCE) не заходил даль­ше три­виаль­ной переза­писи SEH. В этой статье я рас­ска­жу и на прак­тике покажу механи­ку работы кучи.

Прак­тиковать­ся мы будем на реали­зации кучи ptmalloc2, которая сей­час исполь­зует­ся по умол­чанию в glibc, поэто­му нам понадо­бят­ся машина с Linux и необ­ходимый софт. Уста­новим отладчик GDB, GCC (мож­но сра­зу пос­тавить весь пакет build-essential) и отла­доч­ную вер­сию биб­лиоте­ки libc, поз­воля­ющую видеть под­робную информа­цию о куче. Так­же пос­тавим pwngdb и его зависи­мость — peda, что­бы получить удоб­ные коман­ды vmmap, hexdump, heapinfo.

sudo apt install gdb build-essential libc6-dbg

git clone https://github.com/scwuaptx/Pwngdb.git ~/Pwngdb

cp ~/Pwngdb/.gdbinit ~/

git clone https://github.com/longld/peda.git ~/peda

ОСНОВЫ GDB

Для изу­чения работы наших тес­товых прог­рамм понадо­бит­ся зна­ние базовых команд GDB:

  • r[un] — запус­тить файл;
  • b[reak] *0x1234 — пос­тавить точ­ку оста­нова на адре­се 0x1234;
  • b[reak] 123 — пос­тавить точ­ку оста­нова на стро­ке 123 текуще­го исходно­го фай­ла;
  • b[reak] basic.c:123 — пос­тавить точ­ку оста­нова на стро­ке 123 исходно­го фай­ла basic.c;
  • c[ontinue] — про­дол­жить выпол­нение;
  • s[tep] — выпол­нить одну ассем­блер­ную инс­трук­цию;
  • n[ext] — выпол­нить одну строч­ку исходно­го фай­ла;
  • x/10xg 0x1234 — рас­печатать десять 8-бай­тных слов по адре­су 0x1234;
  • p[rint] a — рас­печатать зна­чение перемен­ной a;
  • p[rint] *((mchunkptr)0x555555756680) — взять содер­жимое памяти по адре­су 0x555555756680 как тип mchunkptr, задере­ферен­сить его и рас­печатать;
  • where — показать, на какой строч­ке исходно­го кода находит­ся выпол­нение прог­раммы.

Ко­ман­ды peda и pwngdb:

  • vmmap — вывес­ти кар­ту памяти;
  • hexdump — показать содер­жимое памяти по адре­су в виде hexdump;
  • heapinfo — пос­мотреть информа­цию о куче.

СТРУКТУРА ЧАНКОВ

Ког­да прог­рамма зап­рашива­ет буфер для дан­ных (нап­ример, раз­мером в 10 байт) с помощью malloc, на самом деле выделя­ется боль­ше памяти, так как для хра­нения метадан­ных необ­ходимо допол­нитель­ное прос­транс­тво. Такой кусок памяти, содер­жащий метадан­ные, называ­ют чан­ком (chunk).

Струк­тура чан­ка, исполь­зуемая в ptmalloc2, при­веде­на ниже. Из нее мож­но понять, что перед ука­зате­лем на выделен­ный буфер памяти, который воз­вра­щает­ся поль­зовате­лю (mem), рас­полага­ются еще два поля: раз­мер чан­ка и раз­мер пре­дыду­щего чан­ка.

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Size of previous chunk, if unallocated (P clear) |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Size of chunk, in bytes |A|M|P|

mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| User data starts here... .

. .

. (malloc_usable_size() bytes) .

. |

nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| (size of chunk, but used for application data) |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Size of next chunk, in bytes |A|0|1|

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Сам чанк име­ет такую струк­туру:

struct malloc_chunk {

INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk, if it is free. */

INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overhead. */

struct malloc_chunk* fd; /* double links — used only if this chunk is free. */

struct malloc_chunk* bk;

/* Only used for large blocks: pointer to next larger size. */

struct malloc_chunk* fd_nextsize; /* double links — used only if this chunk is free. */

struct malloc_chunk* bk_nextsize;

};

typedef struct malloc_chunk* mchunkptr;

Что­бы получить из ука­зате­ля на чанк (слу­жеб­ную струк­туру) ука­затель на буфер памяти, который мож­но исполь­зовать, к пер­вому при­бав­ляют зна­чение 2*SIZE_SZ. SIZE_SZ. Для архи­тек­туры x64 оно рав­но 8, а для x86 — 4. То есть на x64 user_mem = chunk + 16. И наобо­рот, что­бы из ука­зате­ля, который вер­нул malloc, получить ука­затель на чанк, необ­ходимо вычесть 2*SIZE_SZ из него. За это отве­чают сле­дующие мак­росы:

#define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ))

#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))

Важ­ный момент: поле mchunk_prev_size в сле­дующем чан­ке исполь­зует­ся для хра­нения поль­зователь­ских дан­ных пре­дыду­щего чан­ка.

Арена

Ста­рые менед­жеры кучи исполь­зовали одну кучу на весь про­цесс и син­хро­низи­рова­ли дос­туп к ней раз­ных потоков с помощью мьютек­сов. Как нес­ложно догадать­ся, положи­тель­но на про­изво­дитель­нос­ти это не ска­зыва­лось. Ptmalloc2 исполь­зует аре­ны — области памяти для того, что­бы каж­дый поток мог там хра­нить свою кучу.

Но пос­коль­ку на прак­тике потоков в при­ложе­нии может быть слиш­ком мно­го, мак­сималь­ное количес­тво соз­дава­емых арен вычис­ляет­ся по сле­дующей фор­муле (n — количес­тво про­цес­соров):

#define NARENAS_FROM_NCORES(n) ((n) * (**sizeof** (**long**) == 4 ? 2 : 8))

По­ка количес­тво арен мень­ше мак­сималь­ного, менед­жер кучи соз­дает новую аре­ну на каж­дый новый поток. Пос­ле это­го, увы, нес­коль­ким потокам при­дет­ся делить меж­ду собой одну аре­ну.

Пер­вая соз­данная менед­жером кучи аре­на называ­ется основной (main). Одно­поточ­ное при­ложе­ние исполь­зует толь­ко основную аре­ну.

Флаги

Ос­тановим­ся под­робнее на фла­гах чан­ка. Поле раз­мера пре­дыду­щего чан­ка (mchunk_size), кро­ме собс­твен­но раз­мера, хра­нит три фла­га: A, M, P. Это воз­можно за счет вырав­нивания раз­мера чан­ка. Так как раз­мер чан­ка всег­да кра­тен либо 8, либо 16 бай­там, пос­ледние 3 бита раз­мера не несут смыс­ловой наг­рузки, и их мож­но исполь­зовать для хра­нения фла­гов.

  • A (NON_MAIN_ARENA): 0 — чанк был выделен из основной аре­ны и основной кучи; 1 — чанк при­над­лежит одной из вто­рос­тепен­ных арен. Ког­да при­ложе­ние соз­дает допол­нитель­ные потоки, каж­дый из них получа­ет свою аре­ну (гру­бо говоря, свою кучу). В чан­ках, выделя­емых на этих аре­нах, уста­нов­лен бит A;
  • M (IS_MMAPPED): 1 — чанк получен с помощью вызова mmap. Осталь­ные фла­ги игно­риру­ются, потому что дан­ные чан­ки не рас­полага­ются в аре­не и к ним не при­мыка­ют дру­гие чан­ки;
  • P (PREV_INUSE): 0 — пре­дыду­щий чанк не исполь­зует­ся. Перед полем mchunk_size рас­полага­ется зна­чение раз­мера пре­дыду­щего чан­ка; 1 — пре­дыду­щий чанк исполь­зует­ся. Перед полем mchunk_size рас­полага­ются поль­зователь­ские дан­ные.

Bins

Для повыше­ния быс­тро­дей­ствия чан­ки исполь­зуют пов­торно (и имен­но эту осо­бен­ность учи­тыва­ют при экс­плу­ата­ции кучи). Ранее исполь­зован­ные и осво­бож­денные чан­ки скла­дыва­ют в бины (bins). В нашей реали­зации кучи сущес­тву­ет пять типов бинов:

  • small (62 шту­ки);
  • large (63 шту­ки);
  • unsorted (1 шту­ка);
  • fast (10 штук);
  • tcache (64 на поток).

Small bins

  • Чан­ки в каж­дом из small bin хра­нят­ся в двус­вязном спис­ке.
  • Встав­ка осво­бож­денных чан­ков в этот спи­сок про­изво­дит­ся с начала (head), уда­ление — с кон­ца (tail, FIFO). Для ведения это­го спис­ка исполь­зуют­ся ука­зате­ли fd и bk (см. струк­туру чан­ка).
  • Та­ких бинов 62 шту­ки. Каж­дый из small bins хра­нит чан­ки толь­ко одно­го раз­мера: 16, 24, ..., 504 байт для x86 и 1008 байт для x64.
  • Ес­ли в small bin попада­ют два сосед­них чан­ка, то они объ­еди­няют­ся и отправ­ляют­ся в unsorted bin.

Large bins

  • Чан­ки в каж­дом из large bin так­же хра­нят­ся в двус­вязном спис­ке.
  • Чан­ки в каж­дом из бинов име­ют диапа­зон раз­меров.
  • Чан­ки сор­тиру­ются сле­дующим обра­зом: самый боль­шой чанк находит­ся в head спис­ка, а самый малень­кий — в tail. Для это­го исполь­зуют­ся ука­зате­ли fd_nextsize и bk_nextsize.
  • Встав­ки и уда­ления про­исхо­дят на любой позиции.
  • Та­ких бинов 63 шту­ки, в них хра­нят­ся чан­ки раз­мером от 512 байт для x86 и от 1024 байт для x64.

Unsorted bin

Вмес­то того что­бы скла­дывать толь­ко что осво­бож­денные чан­ки в под­ходящий bin, менед­жер кучи соеди­няет их с соседя­ми и скла­дыва­ет их в unsorted bin. При сле­дующем вызове malloc каж­дый чанк из unsorted bin про­веря­ется: под­ходит он по раз­меру или нет. Если под­ходит, то malloc исполь­зует его. В про­тив­ном слу­чае чанк помеща­ется в под­ходящий bin: small или large.

Fast bins

  • Соз­даны для опти­миза­ции осво­бож­дения и алло­кации чан­ков малень­кого раз­мера.
  • Хра­нят чан­ки фик­сирован­ного раз­мера. Мак­сималь­ный раз­мер чан­ка для x86 88 байт, для x64 176 байт.
  • Чан­ки хра­нят­ся в односвяз­ном спис­ке (LIFO).
  • У чан­ков в fast bins не сни­мает­ся флаг P. Поэто­му сосед­ние осво­бож­денные чан­ки не сли­вают­ся. Это сде­лано для уве­личе­ния ско­рос­ти осво­бож­дения и выделе­ния чан­ков неболь­шого раз­мера.

Tcache bins

  • У каж­дого потока есть 64 tcache bin. Это сде­лано для еще боль­шей опти­миза­ции выделе­ния неболь­ших чан­ков. Они исполь­зуют­ся всег­да, ког­да количес­тво потоков пре­выша­ет мак­сималь­но допус­тимое чис­ло арен: в этом слу­чае каж­дый поток может сна­чала исполь­зовать свой кеш, а не ждать, пока осво­бодит­ся мьютекс син­хро­низа­ции дос­тупа к куче.
  • Чан­ки хра­нят­ся в односвяз­ном спис­ке.
  • В каж­дом bin — мак­симум семь чан­ков с оди­нако­вым раз­мером (12–516 на x86 и 24–1032 на x64).
  • Чан­ки при осво­бож­дении не сли­вают­ся и не осво­бож­дают­ся «по‑нас­тояще­му» (флаг P не сни­мает­ся).
  • При зап­росе памяти под­ходящий чанк сна­чала ищет­ся в tcache, а потом в осталь­ных bin.

ТЕСТОВАЯ ПРОГРАММА

На­пишем прос­тую тес­товую прог­рамму для демонс­тра­ции:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

int main()

{

puts("Basic allocation example.\n");

char* a = malloc(0x10);

strcpy(a, "AAAAAAAAAAAAAAA"); // A * 15

char* b = malloc(0x12);

memcpy(b, "BBBBBBBBBBBBBBBBBBBBBBBB", 24); // B * 23

char* c = malloc(496); // was 0x200

char* c = malloc(496); // was 0x200

char* d = malloc(0x500);

char* e = malloc(0x500);

char* f = malloc(0x500);

char* g = malloc(0x500);

char* h = malloc(0x500);

free(a);

free(b);

free(c);

free(d);

// free(e);

free(f);

free(h);

free(g);

puts("End.\n");

}

Ском­пилиру­ем ее с отла­доч­ной информа­цией с помощью такой коман­ды:

gcc basic.c -o basic -ggdb

ПРАКТИКА

Здесь и далее мы будем рас­смат­ривать плат­форму x64. Откро­ем нашу тес­товую прог­рамму в GDB и пос­тавим бряк на строч­ке 8: char* a = malloc(0x10): с помощью коман­ды b basic.c:8.

За­пус­тим выпол­нение прог­раммы коман­дой r и пос­мотрим, что в ней про­исхо­дит (коман­да heapinfo).

Пос­ле начала исполне­ния кода поль­зовате­ля куча ини­циали­зиру­ется, и мы можем уви­деть, по какому адре­су рас­положен вер­хний (top) чанк кучи: 0x5555555596a0.

INFO

Top chunk — чанк, находя­щий­ся на вер­шине кучи. Флаг P дан­ного чан­ка всег­да выс­тавлен.

С помощью коман­ды vmmap мы можем пос­мотреть кар­ту памяти про­цес­са и уви­деть, где находит­ся куча.

Те­перь мы зна­ем, что нас не обма­ныва­ют и вер­хний чанк кучи дей­стви­тель­но рас­положен в сег­менте кучи.

Ис­полним одну строч­ку прог­раммы char* a = malloc(0x10) с помощью коман­ды n. Мы уви­дим, что вер­хний чанк кучи смес­тился впе­ред на 0x20 байт, а дос­тупный раз­мер кучи умень­шил­ся соот­ветс­твен­но. Почему на 0x20, если мы зап­росили 0x10 байт? Оставши­еся 16 байт ушли на метадан­ные, рас­положен­ные перед ука­зате­лем a: mchunk_prev_size и mchunk_size.

Так­же мы можем уви­деть, что флаг P в поле mchunk_size равен 1, то есть пре­дыду­щий чанк занят. С помощью коман­ды p *((mchunkptr)(a-16)) мы можем рас­печатать поля чан­ка как струк­туры.

Да­же если мы зап­росим буфер раз­мером 1 байт, на куче будет выделен чанк раз­мером 0x20 байт, а поль­зовате­лю вер­нется ука­затель на буфер раз­мером 0x18 байт.

Вы­пол­ним строч­ку char* b = malloc(0x12). Менед­жер кучи выделит чанк раз­мером 0x20 байт. Поль­зователь все так же смо­жет исполь­зовать буфер раз­мером 0x18.

Ес­ли мы запишем в наш чанк буфер раз­мером 24 бай­та, то уви­дим, что пос­ледние 8 байт буфера «залезут» на сле­дующий чанк, но метадан­ные переза­писа­ны не будут.

В резуль­тате выпол­нения строч­ки char* c = malloc(496) выделя­ется чанк раз­мером 496 + 16 = 0x200 байт.

Те­перь перей­дем к изу­чению осво­бож­денных чан­ков. Для начала выпол­ним строч­ку 18 free(a);. Пос­коль­ку раз­мер чан­ка a мень­ше 1032 байт, осво­бож­денный чанк попадет в tcache.

Как мы уже зна­ем, чан­ки в tcache не осво­бож­дают­ся «по‑нас­тояще­му», и поэто­му у сле­дующе­го чан­ка все еще выс­тавлен флаг P.

Ос­вободим еще один чанк. Теперь в спи­сок чан­ков в tcache добавил­ся еще один.

По сме­щению 0x55555555*96d0* мы видим ука­затель на сле­дующий чанк в нашем бине, который отно­сит­ся к tcache. Если рас­печатать струк­туру чан­ка по 0x55555555*96c0, то ока­жет­ся, что поле fd (ука­затель на сле­дующий сво­бод­ный чанк в бине) рав­но 0x5555555596b0* — имен­но этот чанк мы осво­боди­ли строч­кой ранее. Зна­чения ука­зате­лей fd_nextsize и bk_nextsize неваж­ны для это­го чан­ка, так как они исполь­зуют­ся толь­ко для чан­ков, находя­щих­ся в large bin.

Пос­ле того как мы осво­бож­даем чанк раз­мером 0x200, он попада­ет в дру­гой бин (тот, который соот­ветс­тву­ет его раз­меру).

Пос­ле выпол­нения строч­ки 21 сво­бод­ный чанк опре­деля­ется в unsorted bin.

Строч­ка 23 осво­бож­дает еще один чанк раз­мером 0x500. Теперь в unsorted bin находят­ся два чан­ка, и мы можем пос­мотреть, как эти чан­ки хра­нят­ся в двус­вязном спис­ке.

Мы видим, что чанк 0x55555555a300 находит­ся в начале спис­ка. Поле fd ука­зыва­ет на сле­дующий чанк — 0x5555555598e0.

FAST BIN DUP

Те­перь, воору­жив­шись эти­ми зна­ниями, раз­берем прос­тей­шую ата­ку fastbin duplication. Суть такова: если в при­ложе­нии есть double-free, то мы можем зас­тавить malloc воз­вра­щать одни и те же чан­ки из fastbin. Эту тех­нику исполь­зуют, что­бы получить при­митив write-what-where (при­мер с 0ctf).

Раз­берем при­мер этой ата­ки из ре­пози­тория how2heap.

INFO

Я раз­беру код для libc 2.31, потому что имен­но эта вер­сия исполь­зует­ся в Ubuntu 20.04. Ты можешь выб­рать дру­гой, но прос­леди, что­бы вер­сия libc сов­падала с исполь­зуемой тво­ей прог­раммой.

В пер­вую оче­редь забива­ют tcache (как ты пом­нишь, в tcache хра­нит­ся мак­симум семь чан­ков одно­го раз­мера).

void *ptrs[8];

for (int i=0; i<8; i++) {

ptrs[i] = malloc(8);

}

for (int i=0; i<7; i++) {

free(ptrs[i]);

}

Де­лает­ся это по одной прос­той при­чине: в реали­зации tcache в libc 2.31 при­сутс­тву­ет защита от дан­ной ата­ки. Ког­да чанк кла­дет­ся в tcache, в него сох­раня­ется ука­затель на сам tcache.

typedef struct tcache_entry

{

struct tcache_entry *next;

/* This field exists to detect double frees. */

struct tcache_perthread_struct *key;

} tcache_entry;

//...

static __always_inline void

tcache_put (mchunkptr chunk, size_t tc_idx)

{

tcache_entry *e = (tcache_entry *) chunk2mem (chunk);

/* Mark this chunk as "in the tcache" so the test in _int_free will

detect a double free. */

e->key = tcache;

//...

}

А фун­кция free перед тем, как положить осво­бож­даемый чанк в tcache, про­веря­ет, не сох­ранен ли уже в этом чан­ке ука­затель на tcache. В таком слу­чае триг­герит­ся про­вер­ка на double free. К сло­ву, в акту­аль­ной вер­сии glibc эта про­вер­ка улуч­шена и вмес­то ука­зате­ля на tcache в качес­тве клю­ча исполь­зует­ся слу­чай­ное чис­ло.

if (__glibc_unlikely (e->key == tcache))

{

tcache_entry *tmp;

LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);

for (tmp = tcache->entries[tc_idx];

tmp;

tmp = tmp->next)

if (tmp == e)

malloc_printerr ("free(): double free detected in tcache 2");

/* If we get here, it was a coincidence. We’ve wasted a

few cycles, but don’t abort. */

}

Да­лее выделя­ются три буфера. Для выделе­ния исполь­зует­ся calloc, так как он не исполь­зует tcache. Знаю, в реаль­ной жиз­ни calloc встре­чает­ся реже malloc, но для учеб­ных целей сой­дет.

int *a = calloc(1, 8);

int *b = calloc(1, 8);

int *c = calloc(1, 8);

За­тем пос­ледова­тель­но осво­бож­дают­ся a и b.

free(a);

free(b);

По­ка что ничего кри­миналь­ного, наша куча выг­лядит вот так.

В fastbin[0] находят­ся два чан­ка, b→fd ука­зыва­ет на a.

Но если выпол­нить free(a) еще раз, мы уви­дим, что чанк a во вто­рой раз добавит­ся в fastbin[0].

И теперь, если мы выделим еще три буфера с помощью calloc, нам вер­нутся три оди­нако­вых ука­зате­ля, потому что все они берут­ся из fastbin[0]!

Раз­берем­ся, почему это сра­бота­ло. Чанк old в снип­пете ниже — это ста­рый чанк, находя­щий­ся на вер­шине fastbin, а p — это осво­бож­даемый чанк. И если мы пос­тара­емся осво­бодить чанк, находя­щий­ся на вер­шине fastbin, два раза (old == p), прог­рамма напишет нам «double free or corruption (fasttop)» и зак­роет­ся.

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;

//...

/* 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))

malloc_printerr ("double free or corruption (fasttop)");

p->fd = old2 = old;

Имен­но поэто­му мы не можем успешно выпол­нить free(a) два раза под­ряд. Но если помес­тить на вер­шину fastbin чанк b, то free успешно переза­пишет ука­затель fd чан­ка а (p->fd = old2 = old; на снип­пете выше) и добавит его в fastbin!

ЧТО ЕЩЕ ПОЧИТАТЬ ПРО КУЧУ

Ес­ли пос­ле про­читан­ного тебя заин­тересо­вала тема кучи, могу пореко­мен­довать озна­комить­ся с дру­гими клас­сичес­кими ата­ками из how2heap, открыв в сосед­ней вклад­ке malloc.c из иссле­дуемой тобой вер­сии glibc.

Читайте ещё больше платных статей бесплатно: https://t.me/hacker_frei

April 10, 2022, 20:05
0 views