ОРИГИНАЛЬНАЯ СТАТЬЯ
ПЕРЕВЕДЕНО СПЕЦИАЛЬНО ДЛЯ xss.pro
$600 ---> bc1qhavqpqvfwasuhf53xnaypvqhhvz966upnk8zy7 для поднятия private нодs ETHEREUM и тестов
Сегодня я собираюсь объяснить важные концепции кучи и использовать ptmalloc в библиотеке Glibc 2.35 в качестве примера.
Куча - это красивый беспорядок
Мне очень нравится высказывание выше. Слово Heap мы всегда используем относительно динамически выделенному сегменту в пространстве виртуальной памяти процесса, но на самом деле это означает реализацию пула памяти (распределителя динамической памяти), который довольно сложен и может различаться на разных машинах, что дает нам шанс использовать его. Попробуем понять важные концепции кучи и использовать ptmalloc в библиотеке Glibc 2.35 в качестве примера.
Во-первых, начнём с однопоточного случая и представлю следующие моменты:
https://guyinatuxedo.github.io/25-heap/index.html
+--------------------+----------------------------+-----------------------+
| Bug Used | Bin Attack | House |
+--------------------+----------------------------+-----------------------+
| | Fast Bin Attack | House of Spirit |
| Double Free | tcache attack | House of Lore |
| Heap Overflow | Unsorted Bin Attck | House of Force |
| Use After Free | Small / Large Bin Attck | House of Einherjar |
| | Unsafe Unlink | House of Orange |
+--------------------+----------------------------+-----------------------+
Пулы — это распространенный шаблон проектирования в вычислительных технологиях, который включает в себя: предварительное выделение и хранение пула основных ресурсов, которые часто используются в программе, которые управляются программой самостоятельно, чтобы улучшить использование ресурсов и гарантировать, что программа имеет фиксированное количество ресурсов.
Пулы памяти — это метод динамического выделения памяти и управления ею. Как правило, программисты привыкли напрямую использовать такие API, как new, delete, malloc и free для выделения и освобождения памяти, что может привести к большому количеству фрагментов памяти с течением времени, когда программа выполняется в течение длительного времени, а размер выделенные блоки памяти не фиксируются, что снижает производительность программы и операционной системы.
Перед фактическим использованием памяти пул памяти предварительно выделяет большой блок памяти (пул памяти) в качестве резерва. Когда программист запрашивает память, блок динамически выделяется из пула. Когда программист освобождает память, она возвращается в пул и может быть использована снова по запросу, а также максимально объединяется с окружающими свободными блоками памяти. Если пула памяти недостаточно, пул памяти автоматически расширяется, и у операционной системы запрашивается больший пул памяти.
К преимуществам использования пулов памяти относятся:
В программе на C мы всегда используем встроенные функции, такие как malloc(), calloc(), и realloc(), которые действительно вызывают распределитель памяти ptmalloc, чтобы получить динамически выделяемое пространство памяти. ptmalloc— это реализация пула памяти в библиотеке Glibc, которая используется по умолчанию.
В реализации ptmalloc mallocиспользовать (s)brkили же mmapсистемный вызов для выделения памяти.
Согласно справочным страницам (s)brk :
Согласно справочным страницам mmap :
Короче оба (s)brkа также mmap- это системные вызовы, которые обеспечивают функциональность для создания нового пространства памяти (с пользовательскими разрешениями). Однако, (s)brkтолько может создать пространство памяти после .dataсегмент (изменить место остановки программы);
Вызов(ы)brk или mmap?
Согласно этой странице :
mallopt()можно установить параметры для управления поведением malloc(), и есть параметр с именем M_MMAP_THRESHOLD, в общем:
Значение параметра по умолчанию равно 128KB(в моей системе).
В распределителе памяти ptmalloc фрагменты различных размеров существуют в большей области памяти («куче»). Куча растет из нижнего адреса. Основная куча (куча, инициализированная основным потоком) начинается с выполнения .BSSсегмент (исходная точка останова программы).
куча - непрерывная область памяти, разделенная на выделяемые фрагменты.
Chunk
Небольшой диапазон памяти, который может быть выделен (принадлежит приложению), освобожден (принадлежит glibc) или объединен с соседними фрагментами в более крупные диапазоны. Обратите внимание, что фрагмент представляет собой оболочку вокруг блока памяти, который предоставляется приложению.
Метаданные кучи организованы с помощью следующих трех структур данных: malloc_chunk (заголовок фрагмента), malloc_state и heap_info.
Чанк — это наименьшая единица, выделяемая malloc. Чанки имеют два различных состояния: используются или свободны.
Используемый фрагмент состоит из 3 частей: размер предыдущего фрагмента или пользовательские данные предыдущего фрагмента, размер фрагмента (8 байт на 64-разрядных машинах), флаг AMP (3-бит) и пользовательские данные. Пользовательские данные будут дополнены до 16 байтов на 64-разрядных машинах, что означает, что последние три бита размера пользовательских данных в шестнадцатеричном формате всегда будут равны нулю. Следовательно, мы могли бы воспользоваться выравниванием и использовать их как флаги.
Пустой чанк состоит из 4 частей. Первые 16 байт остаются как есть. Теперь, когда этот фрагмент свободен, в него будут записаны две новые части (fwd и bkd) и одна (pre_size) в следующий фрагмент. Указатель вперед fwd хранит адрес следующего свободного фрагмента в списке и обратный указатель bkd сохраняет адрес предыдущего свободного чанка в списке, если он есть. Наконец, pre_size следующего чанка будет установлен равным размеру чанка этого чанка.
Интересным моментом здесь является то, что первые 8 байтов являются перекрывающейся частью предыдущего фрагмента. Если предыдущий фрагмент используется, то эта часть будет содержать предыдущие последние 8 байтов данных, а если предыдущий фрагмент свободен, он будет содержать предыдущий размер фрагмента.
AMP-флажки
A , Allocated Arena — основная часть использует кучу приложения. В других частях используются кучи mmap. Чтобы сопоставить чанк с кучей, вам нужно знать, какой случай применяется. Если этот бит равен 0, чанк исходит из основной арены и основной кучи. Если этот бит равен 1, чанк берется из памяти с помощью mmap, и местоположение кучи можно вычислить по адресу чанка.
M , чанк MMap'd — этот чанк был выделен одним вызовом mmap и вообще не является частью кучи.
P , Предыдущий фрагмент используется — если установлено, предыдущий фрагмент все еще используется приложением, и, таким образом, prev_size поле недействительно. Примечание. В некоторых чанках, например, в fastbins (см. ниже), этот бит будет установлен, несмотря на то, что приложение освободило их. Этот бит на самом деле означает, что предыдущий фрагмент не должен рассматриваться как кандидат на объединение — он «используется» либо приложением, либо какой-либо другой оптимизацией, наложенной поверх исходного кода malloc.
минимальный размер чанка
Чтобы гарантировать, что область полезной нагрузки фрагмента достаточно велика, чтобы вместить накладные расходы, необходимые malloc, минимальный размер фрагмента 4*sizeof(void*) (пока не size_t не такого размера, как void*). Минимальный размер может быть больше, если ABI платформы требует дополнительного выравнивания. Обратите внимание, что prev_size не увеличивает минимальный размер фрагмента до 5*sizeof(void*) потому что когда кусок маленький bk_nextsize указатель не используется, и когда фрагмент достаточно велик, чтобы его можно было использовать, в конце остается более чем достаточно места.
тип структуры malloc_chunk
Структура malloc_state содержит необходимые переменные для управления свободными участками памяти. Структура malloc_state основного потока (основной кучи) хранится в сегменте отображения памяти как глобальная переменная.
биннинг
Свободные блоки хранятся в различных свободных списках на основе размера и истории, чтобы распределитель мог быстро найти подходящие блоки для удовлетворения запросов на распределение. Фрилисты на самом деле называются бинами. Bins - это связанные структуры в памяти, которые отслеживают все освобожденные блоки.
Быстрые бины
Большинство программ часто запрашивают и освобождают относительно небольшие участки памяти. Если освободить несколько небольших кусков, найти и объединить соседний свободный чанк, то при следующем запросе чанка такого же размера его придется разделить, что значительно снижает эффективность использования кучи. Поэтому был предложен fastbin, чтобы обеспечить быстрый доступ, сохраняя минимальную логику.
По умолчанию используется 7 бинов, однако количество бинов в fastbins определяется NFASTBINS.
Быстрые бины представляют собой односвязные списки, и все чанки в каждом списке имеют одинаковый размер, а к чанкам в середине списка никогда не нужно обращаться.
На машинах x64 размеры по умолчанию варьируются от 0x20 до 0x80. Размер каждого чанка увеличивается на 0x10 байт. Таким образом, чанк размером 0x20-0x2f помещается в idx 0, чанк размером 0x30-0x3f - в idx 1, и так далее.
Флаг неиспользования чанков, добавленных в быстрый бин, всегда устанавливается в 1, чтобы они не объединялись с соседними чанками для сохранения быстрого доступа (отсюда и быстрые бины).
Способ LIFO
Несортированные бины
Bins[] фактически содержит 3 различных вида бинов: несортированный бин, малый бин и большой бин.
bins[1] - это несортированные бины (bins[0] не используется). Когда чанки освобождаются, они первоначально хранятся в одном бине. Они сортируются позже, в malloc, чтобы дать им один шанс на быстрое повторное использование. Это также означает, что логика сортировки должна существовать только в одной точке - все остальные просто кладут свободные куски в эту корзину, и они будут отсортированы позже. Несортированная корзина - это просто первая из обычных корзин.
Мы увидим, как несортированные бины будут использоваться позже в алгоритме распределения.
Малые бины
Существует 62 малых бина (индекс 2-63), и каждый бин представляет собой дважды связанный список;
Каждый бин (список) имеет одинаковый размер. Бин с индексом n имеет размер чанка (16n, 16n+16);
Максимальный размер малых бинов определяется MIN_LARGE_SIZE, который обычно составляет 1024B(1KB);
Способ FIFO;
Большие бины
Существует 63 малых бина (индекс 64-127), и каждый бин представляет собой дважды связанный список;
В конкретном большом бине есть чанки разных размеров, отсортированные в порядке убывания (т.е. самый большой кусок в "HEAD" и самый маленький в "TAIL").
Размер чанков в больших бинах составляет от 1024 Б до 128 КБ включительно (или любое значение, на которое установлен M_MMAP_THRESHOLD).
Вставки и удаления происходят в любой позиции списка.
1. низкоуровневое поведение malloc
2. алгоритм выделения чанков
Получение блокировки для области выделения для предотвращения многопоточных конфликтов.
Вычислить фактический размер участка памяти, который необходимо выделить.
Если размер чанка меньше максимального размера больших бинов (128 байт), попытайтесь найти подходящий чанк в больших бинах. Если таковой найден, выделение завершено. В противном случае перейдите к следующему шагу.
Если размер блока меньше максимального размера малых бинов (1 КБ), выполните поиск подходящего блока в малых бинах. Если таковой найден, выделение завершено. В противном случае перейдите к следующему шагу.
Приведите в порядок несортированные блоки памяти:
Ptmalloc сначала перебирает блоки в больших бинах, объединяя соседние блоки и связывая их с несортированным бином.
Затем выполняется перебор несортированных бинов. Если в несортированных бинах есть чанк большего размера, чем выделяемый, он будет разделен, а оставшийся чанк будет помещен обратно в несортированные бины. Если есть чанк того же размера, что и выделяемый, он будет возвращен и удален из несортированных бинов. Если чанк в несортированных бинах находится в диапазоне размеров малых бинов, он будет помещен в начало малых бинов. Если кусок в несортированных корзинах находится в диапазоне больших бинов по размеру, он будет помещен в подходящее место в больших бинах. (Единственное место в кодовой базе для размещения чанков в S/L бинах) Если распределение не удалось, перейдите к следующему шагу.
Поиск подходящего чанка в больших бинах, затем разделите его, выделив часть пользователю и поместив оставшуюся часть в несортированную бину.
Если подходящий чанк не найден в больших бинах или бинах, для распределения должен быть использован верхний кусок. Если объем верхнего блока превышает объем памяти, запрашиваемый пользователем, он будет разделен на две части: пользовательский блок и оставшийся блок. Оставшийся чанк становится новым верхним чанком.
Если верхний чанк все еще недостаточно велик для удовлетворения запрошенного пользователем размера, нам необходимо расширить его с помощью системных вызовов sbrk или mmap.
Если используется mmap, будет создан новый чанк с запрошенным размером, выровненным по 4 КБ, и добавлен к верхнему чанку. Затем верхний чанк будет расширен на запрошенный размер.
Если используется sbrk, верхний чанк будет расширен на запрошенную величину, а остаток будет добавлен в несортированную корзину. Однако, если вызов malloc в главном потоке выполняется впервые, необходимо выполнить инициализацию, чтобы выделить участок размером (chunk_size + 128KB), выравнивающий 4KB в качестве начальной кучи.
Снимите блокировку для области выделения.
Когда пользователь запрашивает выделение памяти с помощью malloc, кусок, найденный ptmalloc2, может быть не того же размера, что и запрашиваемая память. В этом случае оставшаяся после разбиения часть называется последним оставшимся куском и также хранится в несортированной корзине.
алгоритм освобождения чанка
Получение блокировки для области выделения для обеспечения безопасности потока.
Если освобождаемый указатель равен null, вернитесь и ничего не делайте.
Если размер чанка попадает в диапазон быстрых бинов, поместить его в быстрые бины.
Проверьте, является ли текущий чанк памятью, отображенной системным вызовом mmap. Если да, освободите его непосредственно с помощью munmap(). В структуре данных ранее использовавшегося чанка мы видим, что есть символ M, указывающий на то, что это память, отображаемая mmap.
Проверьте, является ли освобождаемый кусок соседним с другим свободным куском. Если да, то объедините их и поместите объединенный блок в несортированную корзину. Если размер объединенного блока больше, чем fastbin_coalsed_threshold (128B), запустите операцию fastbin merge, в ходе которой смежные свободные блоки будут объединены и помещены в несортированную корзину.
Проверьте, является ли чанк смежным с верхним чанком. Если да, то объедините его непосредственно с верхним блоком. Затем проверьте, не превышает ли размер верхнего блока пороговое значение mmap shrink (по умолчанию 128 КБ). Если да, то для основной области выделения попытается вернуть часть верхнего чанка операционной системе. Освобождение завершено.
Многопоточность
Общая схема расположения областей и куч
Область на поток
В реализации ptmalloc область - это большой, непрерывный кусок памяти для хранения кучи для каждого потока (пул памяти, которым управляет конкретная программа).
Используя следующий код, мы можем лучше понять поведение ptmalloc при работе с несколькими потоками.
Перед вызовом malloc в главном потоке мы видим, что сегмент кучи отсутствует.
Сегмент кучи будет создан после вызова malloc в главном потоке, и выделенный размер часто больше запрашиваемого размера, чтобы уменьшить время переключения между режимами ядра и пользователя, тем самым повышая эффективность программы. Эта непрерывная область памяти кучи называется областью. Поскольку эта область создается главным потоком, она называется главной областью. Дальнейшие запросы на выделение продолжают использовать эту арену до тех пор, пока на ней не закончится свободное место.
Например, в следующем случае ptmalloc2 создает сегмент размером 0x21000(132KB), хотя мы только запросили 0x1000(4KB) байт. Остальная память будет управляться ptmalloc2
После вызова функции free в главном потоке созданное пространство памяти (сегмент кучи) не будет освобождено напрямую, а будет снова управляться ptmalloc2. Когда последующая программа запросит память, ptmalloc2 выделит программе соответствующую память в соответствии с алгоритмом выделения кучи.
После вызова pthread_create для создания потока в сегменте отображения памяти для созданного потока выделяется память размером 8 МБ. У потока есть свой собственный стек, который расположен в этой области. Однако в настоящее время я понятия не имею, для чего используются верхние 4 КБ с разрешением ---p.
После вызова malloc в потоке 1 мы видим, что пространство памяти размером 21000 байт (132 КБ) снова было выделено ptmalloc, хотя мы запросили всего 1000 байт (4 КБ). Но на этот раз куча находится в сегменте отображения памяти, а не после точки разрыва программы. Эта непрерывная область памяти (132 КБ) называется областью потоков.
После вызова free в потоке 1 мы видим, что освобождение выделенной области памяти не освобождает память кучи для операционной системы. Вместо этого выделенная область памяти (размером 1000 байт) освобождается в ptmolloc, который добавляет этот освобожденный блок бину своего потока.
Другим важным моментом здесь является то, что это не ровно одна область на поток, как ожидалось, поскольку при наличии большого количества потоков это стало бы затратно. Следовательно, приложение arena limit is based on the number of cores присутствует в системе.
Фактическое поведение ptmalloc, когда взаимно однозначного сопоставления между потоками и обастями недостаточно, может стать намного сложнее, поэтому я бы остановился здесь в качестве отправной точки. Дополнительную информацию можно найти здесь:
https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/
https://sensepost.com/blog/2017/painless-intro-to-the-linux-userland-heap/
https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/heap-structure/
https://raydenchia.com/heaps-of-fun-with-glibc-malloc/
https://0x434b.dev/overview-of-glibc-heap-exploitation-techniques/
https://sourceware.org/glibc/wiki/MallocInternals
https://blog.csdn.net/weixin_37921201/article/details/119744197
https://heap-exploitation.dhavalkapil.com/attacks/double_free
ПЕРЕВЕДЕНО СПЕЦИАЛЬНО ДЛЯ xss.pro
$600 ---> bc1qhavqpqvfwasuhf53xnaypvqhhvz966upnk8zy7 для поднятия private нодs ETHEREUM и тестов
Сегодня я собираюсь объяснить важные концепции кучи и использовать ptmalloc в библиотеке Glibc 2.35 в качестве примера.
Куча - это красивый беспорядок
Мне очень нравится высказывание выше. Слово Heap мы всегда используем относительно динамически выделенному сегменту в пространстве виртуальной памяти процесса, но на самом деле это означает реализацию пула памяти (распределителя динамической памяти), который довольно сложен и может различаться на разных машинах, что дает нам шанс использовать его. Попробуем понять важные концепции кучи и использовать ptmalloc в библиотеке Glibc 2.35 в качестве примера.
Во-первых, начнём с однопоточного случая и представлю следующие моменты:
- высокоуровневое поведение позади malloc: sbrkа также mmap
- общая компоновка кучи и чанков
- структуры данных, используемые для управления: malloc_chunk, malloc_state а также binning
- низкоуровневое поведение malloc: алгоритмы выделения и освобождения фрагментов памяти ( создание, инициализация и удаление кучи)
- общая компоновка кучи
- обновление структур данных: malloc_state а также heap_info
- tcache
https://guyinatuxedo.github.io/25-heap/index.html
+--------------------+----------------------------+-----------------------+
| Bug Used | Bin Attack | House |
+--------------------+----------------------------+-----------------------+
| | Fast Bin Attack | House of Spirit |
| Double Free | tcache attack | House of Lore |
| Heap Overflow | Unsorted Bin Attck | House of Force |
| Use After Free | Small / Large Bin Attck | House of Einherjar |
| | Unsafe Unlink | House of Orange |
+--------------------+----------------------------+-----------------------+
Обзор кучи
Пулы — это распространенный шаблон проектирования в вычислительных технологиях, который включает в себя: предварительное выделение и хранение пула основных ресурсов, которые часто используются в программе, которые управляются программой самостоятельно, чтобы улучшить использование ресурсов и гарантировать, что программа имеет фиксированное количество ресурсов.
Пулы памяти — это метод динамического выделения памяти и управления ею. Как правило, программисты привыкли напрямую использовать такие API, как new, delete, malloc и free для выделения и освобождения памяти, что может привести к большому количеству фрагментов памяти с течением времени, когда программа выполняется в течение длительного времени, а размер выделенные блоки памяти не фиксируются, что снижает производительность программы и операционной системы.
Перед фактическим использованием памяти пул памяти предварительно выделяет большой блок памяти (пул памяти) в качестве резерва. Когда программист запрашивает память, блок динамически выделяется из пула. Когда программист освобождает память, она возвращается в пул и может быть использована снова по запросу, а также максимально объединяется с окружающими свободными блоками памяти. Если пула памяти недостаточно, пул памяти автоматически расширяется, и у операционной системы запрашивается больший пул памяти.
К преимуществам использования пулов памяти относятся:
- Уменьшение внутренней фрагментации с помощью слияния фрагментов, чтобы максимально минимизировать внутреннюю фрагментацию;
- Снижение внешней фрагментации за счет запроса большого блока памяти из памяти сразу;
- Повышение эффективности выделения памяти за счет одновременного запроса большого блока памяти из памяти и медленного его использования, избегая частых запросов к памяти для операций с памятью.
В программе на C мы всегда используем встроенные функции, такие как malloc(), calloc(), и realloc(), которые действительно вызывают распределитель памяти ptmalloc, чтобы получить динамически выделяемое пространство памяти. ptmalloc— это реализация пула памяти в библиотеке Glibc, которая используется по умолчанию.
Системные вызовы за malloc
В реализации ptmalloc mallocиспользовать (s)brkили же mmapсистемный вызов для выделения памяти.
Согласно справочным страницам (s)brk :
Согласно справочным страницам mmap :
Короче оба (s)brkа также mmap- это системные вызовы, которые обеспечивают функциональность для создания нового пространства памяти (с пользовательскими разрешениями). Однако, (s)brkтолько может создать пространство памяти после .dataсегмент (изменить место остановки программы);
Вызов(ы)brk или mmap?
Согласно этой странице :
mallopt()можно установить параметры для управления поведением malloc(), и есть параметр с именем M_MMAP_THRESHOLD, в общем:
- Если запрошенная память меньше ее, brk()будет использован;
- Если запрошенная память больше или равна ему, mmap()будет использован;
Значение параметра по умолчанию равно 128KB(в моей системе).
Общий макет кучи
В распределителе памяти ptmalloc фрагменты различных размеров существуют в большей области памяти («куче»). Куча растет из нижнего адреса. Основная куча (куча, инициализированная основным потоком) начинается с выполнения .BSSсегмент (исходная точка останова программы).
куча - непрерывная область памяти, разделенная на выделяемые фрагменты.
Chunk
Небольшой диапазон памяти, который может быть выделен (принадлежит приложению), освобожден (принадлежит glibc) или объединен с соседними фрагментами в более крупные диапазоны. Обратите внимание, что фрагмент представляет собой оболочку вокруг блока памяти, который предоставляется приложению.
Структуры данных для кучи
Метаданные кучи организованы с помощью следующих трех структур данных: malloc_chunk (заголовок фрагмента), malloc_state и heap_info.
- malloc_chunk: чанк — это наименьшая единица, выделенная malloc, и каждый чанк имеет свой собственный malloc_chunkструктура заголовка.
- malloc_state: кучи управляются одним malloc_stateструктура заголовка. Эта структура сообщает распределителю, где находится верхний блок (блок с наивысшим адресом), последний оставшийся блок, ячейки и т. д
malloc_chunk (заголовок фрагмента)
Чанк — это наименьшая единица, выделяемая malloc. Чанки имеют два различных состояния: используются или свободны.
Используемый фрагмент состоит из 3 частей: размер предыдущего фрагмента или пользовательские данные предыдущего фрагмента, размер фрагмента (8 байт на 64-разрядных машинах), флаг AMP (3-бит) и пользовательские данные. Пользовательские данные будут дополнены до 16 байтов на 64-разрядных машинах, что означает, что последние три бита размера пользовательских данных в шестнадцатеричном формате всегда будут равны нулю. Следовательно, мы могли бы воспользоваться выравниванием и использовать их как флаги.
Пустой чанк состоит из 4 частей. Первые 16 байт остаются как есть. Теперь, когда этот фрагмент свободен, в него будут записаны две новые части (fwd и bkd) и одна (pre_size) в следующий фрагмент. Указатель вперед fwd хранит адрес следующего свободного фрагмента в списке и обратный указатель bkd сохраняет адрес предыдущего свободного чанка в списке, если он есть. Наконец, pre_size следующего чанка будет установлен равным размеру чанка этого чанка.
Интересным моментом здесь является то, что первые 8 байтов являются перекрывающейся частью предыдущего фрагмента. Если предыдущий фрагмент используется, то эта часть будет содержать предыдущие последние 8 байтов данных, а если предыдущий фрагмент свободен, он будет содержать предыдущий размер фрагмента.
AMP-флажки
A , Allocated Arena — основная часть использует кучу приложения. В других частях используются кучи mmap. Чтобы сопоставить чанк с кучей, вам нужно знать, какой случай применяется. Если этот бит равен 0, чанк исходит из основной арены и основной кучи. Если этот бит равен 1, чанк берется из памяти с помощью mmap, и местоположение кучи можно вычислить по адресу чанка.
M , чанк MMap'd — этот чанк был выделен одним вызовом mmap и вообще не является частью кучи.
P , Предыдущий фрагмент используется — если установлено, предыдущий фрагмент все еще используется приложением, и, таким образом, prev_size поле недействительно. Примечание. В некоторых чанках, например, в fastbins (см. ниже), этот бит будет установлен, несмотря на то, что приложение освободило их. Этот бит на самом деле означает, что предыдущий фрагмент не должен рассматриваться как кандидат на объединение — он «используется» либо приложением, либо какой-либо другой оптимизацией, наложенной поверх исходного кода malloc.
минимальный размер чанка
Чтобы гарантировать, что область полезной нагрузки фрагмента достаточно велика, чтобы вместить накладные расходы, необходимые malloc, минимальный размер фрагмента 4*sizeof(void*) (пока не size_t не такого размера, как void*). Минимальный размер может быть больше, если ABI платформы требует дополнительного выравнивания. Обратите внимание, что prev_size не увеличивает минимальный размер фрагмента до 5*sizeof(void*) потому что когда кусок маленький bk_nextsize указатель не используется, и когда фрагмент достаточно велик, чтобы его можно было использовать, в конце остается более чем достаточно места.
тип структуры malloc_chunk
Код:
/*
This struct declaration is misleading (but accurate and necessary).
It declares a "view" into memory allowing access to necessary
fields at known offsets from a given base. See explanation below.
*/
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if 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 free. */
struct malloc_chunk* bk_nextsize;
};malloc_state
Структура malloc_state содержит необходимые переменные для управления свободными участками памяти. Структура malloc_state основного потока (основной кучи) хранится в сегменте отображения памяти как глобальная переменная.
Код:
struct malloc_state
{
/* Serialize access. */
__libc_lock_define (, mutex);
/* Flags (formerly in max_fast). */
int flags;
/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;
/* The remainder from the most recent split of a small request */
mchunkptr last_remainder;
/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];
/* Linked list */
struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized
by free_list_lock in arena.c. */
struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on
the free list. Access to this field is serialized by
free_list_lock in arena.c. */
INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};
typedef struct malloc_state *mstate;биннинг
Свободные блоки хранятся в различных свободных списках на основе размера и истории, чтобы распределитель мог быстро найти подходящие блоки для удовлетворения запросов на распределение. Фрилисты на самом деле называются бинами. Bins - это связанные структуры в памяти, которые отслеживают все освобожденные блоки.
Быстрые бины
Большинство программ часто запрашивают и освобождают относительно небольшие участки памяти. Если освободить несколько небольших кусков, найти и объединить соседний свободный чанк, то при следующем запросе чанка такого же размера его придется разделить, что значительно снижает эффективность использования кучи. Поэтому был предложен fastbin, чтобы обеспечить быстрый доступ, сохраняя минимальную логику.
По умолчанию используется 7 бинов, однако количество бинов в fastbins определяется NFASTBINS.
Быстрые бины представляют собой односвязные списки, и все чанки в каждом списке имеют одинаковый размер, а к чанкам в середине списка никогда не нужно обращаться.
На машинах x64 размеры по умолчанию варьируются от 0x20 до 0x80. Размер каждого чанка увеличивается на 0x10 байт. Таким образом, чанк размером 0x20-0x2f помещается в idx 0, чанк размером 0x30-0x3f - в idx 1, и так далее.
Флаг неиспользования чанков, добавленных в быстрый бин, всегда устанавливается в 1, чтобы они не объединялись с соседними чанками для сохранения быстрого доступа (отсюда и быстрые бины).
Способ LIFO
Несортированные бины
Bins[] фактически содержит 3 различных вида бинов: несортированный бин, малый бин и большой бин.
bins[1] - это несортированные бины (bins[0] не используется). Когда чанки освобождаются, они первоначально хранятся в одном бине. Они сортируются позже, в malloc, чтобы дать им один шанс на быстрое повторное использование. Это также означает, что логика сортировки должна существовать только в одной точке - все остальные просто кладут свободные куски в эту корзину, и они будут отсортированы позже. Несортированная корзина - это просто первая из обычных корзин.
Мы увидим, как несортированные бины будут использоваться позже в алгоритме распределения.
Малые бины
Существует 62 малых бина (индекс 2-63), и каждый бин представляет собой дважды связанный список;
Каждый бин (список) имеет одинаковый размер. Бин с индексом n имеет размер чанка (16n, 16n+16);
Максимальный размер малых бинов определяется MIN_LARGE_SIZE, который обычно составляет 1024B(1KB);
Способ FIFO;
Большие бины
Существует 63 малых бина (индекс 64-127), и каждый бин представляет собой дважды связанный список;
В конкретном большом бине есть чанки разных размеров, отсортированные в порядке убывания (т.е. самый большой кусок в "HEAD" и самый маленький в "TAIL").
Размер чанков в больших бинах составляет от 1024 Б до 128 КБ включительно (или любое значение, на которое установлен M_MMAP_THRESHOLD).
Вставки и удаления происходят в любой позиции списка.
1. низкоуровневое поведение malloc
2. алгоритм выделения чанков
Получение блокировки для области выделения для предотвращения многопоточных конфликтов.
Вычислить фактический размер участка памяти, который необходимо выделить.
Если размер чанка меньше максимального размера больших бинов (128 байт), попытайтесь найти подходящий чанк в больших бинах. Если таковой найден, выделение завершено. В противном случае перейдите к следующему шагу.
Если размер блока меньше максимального размера малых бинов (1 КБ), выполните поиск подходящего блока в малых бинах. Если таковой найден, выделение завершено. В противном случае перейдите к следующему шагу.
Приведите в порядок несортированные блоки памяти:
Ptmalloc сначала перебирает блоки в больших бинах, объединяя соседние блоки и связывая их с несортированным бином.
Затем выполняется перебор несортированных бинов. Если в несортированных бинах есть чанк большего размера, чем выделяемый, он будет разделен, а оставшийся чанк будет помещен обратно в несортированные бины. Если есть чанк того же размера, что и выделяемый, он будет возвращен и удален из несортированных бинов. Если чанк в несортированных бинах находится в диапазоне размеров малых бинов, он будет помещен в начало малых бинов. Если кусок в несортированных корзинах находится в диапазоне больших бинов по размеру, он будет помещен в подходящее место в больших бинах. (Единственное место в кодовой базе для размещения чанков в S/L бинах) Если распределение не удалось, перейдите к следующему шагу.
Поиск подходящего чанка в больших бинах, затем разделите его, выделив часть пользователю и поместив оставшуюся часть в несортированную бину.
Если подходящий чанк не найден в больших бинах или бинах, для распределения должен быть использован верхний кусок. Если объем верхнего блока превышает объем памяти, запрашиваемый пользователем, он будет разделен на две части: пользовательский блок и оставшийся блок. Оставшийся чанк становится новым верхним чанком.
Если верхний чанк все еще недостаточно велик для удовлетворения запрошенного пользователем размера, нам необходимо расширить его с помощью системных вызовов sbrk или mmap.
Код:
https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/
/* Per thread arena example. */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>
void* threadFunc(void* arg) {
printf("Before malloc in thread 1\n");
getchar();
char* addr = (char*) malloc(1000);
printf("After malloc and before free in thread 1\n");
getchar();
free(addr);
printf("After free in thread 1\n");
getchar();
}
int main() {
pthread_t t1;
void* s;
int ret;
char* addr;
printf("Welcome to per thread arena example::%d\n",getpid());
printf("Before malloc in main thread\n");
getchar();
addr = (char*) malloc(1000);
printf("After malloc and before free in main thread\n");
getchar();
free(addr);
printf("After free in main thread\n");
getchar();
ret = pthread_create(&t1, NULL, threadFunc, NULL);
if(ret)
{
printf("Thread creation error\n");
return -1;
}
ret = pthread_join(t1, &s);
if(ret)
{
printf("Thread join error\n");
return -1;
}
return 0;
}Если используется mmap, будет создан новый чанк с запрошенным размером, выровненным по 4 КБ, и добавлен к верхнему чанку. Затем верхний чанк будет расширен на запрошенный размер.
Если используется sbrk, верхний чанк будет расширен на запрошенную величину, а остаток будет добавлен в несортированную корзину. Однако, если вызов malloc в главном потоке выполняется впервые, необходимо выполнить инициализацию, чтобы выделить участок размером (chunk_size + 128KB), выравнивающий 4KB в качестве начальной кучи.
Снимите блокировку для области выделения.
Когда пользователь запрашивает выделение памяти с помощью malloc, кусок, найденный ptmalloc2, может быть не того же размера, что и запрашиваемая память. В этом случае оставшаяся после разбиения часть называется последним оставшимся куском и также хранится в несортированной корзине.
алгоритм освобождения чанка
Получение блокировки для области выделения для обеспечения безопасности потока.
Если освобождаемый указатель равен null, вернитесь и ничего не делайте.
Если размер чанка попадает в диапазон быстрых бинов, поместить его в быстрые бины.
Проверьте, является ли текущий чанк памятью, отображенной системным вызовом mmap. Если да, освободите его непосредственно с помощью munmap(). В структуре данных ранее использовавшегося чанка мы видим, что есть символ M, указывающий на то, что это память, отображаемая mmap.
Проверьте, является ли освобождаемый кусок соседним с другим свободным куском. Если да, то объедините их и поместите объединенный блок в несортированную корзину. Если размер объединенного блока больше, чем fastbin_coalsed_threshold (128B), запустите операцию fastbin merge, в ходе которой смежные свободные блоки будут объединены и помещены в несортированную корзину.
Проверьте, является ли чанк смежным с верхним чанком. Если да, то объедините его непосредственно с верхним блоком. Затем проверьте, не превышает ли размер верхнего блока пороговое значение mmap shrink (по умолчанию 128 КБ). Если да, то для основной области выделения попытается вернуть часть верхнего чанка операционной системе. Освобождение завершено.
Многопоточность
Общая схема расположения областей и куч
Область на поток
В реализации ptmalloc область - это большой, непрерывный кусок памяти для хранения кучи для каждого потока (пул памяти, которым управляет конкретная программа).
Используя следующий код, мы можем лучше понять поведение ptmalloc при работе с несколькими потоками.
Код:
https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/
/* Per thread arena example. */
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <sys/types.h>
void* threadFunc(void* arg) {
printf("Before malloc in thread 1\n");
getchar();
char* addr = (char*) malloc(1000);
printf("After malloc and before free in thread 1\n");
getchar();
free(addr);
printf("After free in thread 1\n");
getchar();
}
int main() {
pthread_t t1;
void* s;
int ret;
char* addr;
printf("Welcome to per thread arena example::%d\n",getpid());
printf("Before malloc in main thread\n");
getchar();
addr = (char*) malloc(1000);
printf("After malloc and before free in main thread\n");
getchar();
free(addr);
printf("After free in main thread\n");
getchar();
ret = pthread_create(&t1, NULL, threadFunc, NULL);
if(ret)
{
printf("Thread creation error\n");
return -1;
}
ret = pthread_join(t1, &s);
if(ret)
{
printf("Thread join error\n");
return -1;
}
return 0;
}Перед вызовом malloc в главном потоке мы видим, что сегмент кучи отсутствует.
Сегмент кучи будет создан после вызова malloc в главном потоке, и выделенный размер часто больше запрашиваемого размера, чтобы уменьшить время переключения между режимами ядра и пользователя, тем самым повышая эффективность программы. Эта непрерывная область памяти кучи называется областью. Поскольку эта область создается главным потоком, она называется главной областью. Дальнейшие запросы на выделение продолжают использовать эту арену до тех пор, пока на ней не закончится свободное место.
Например, в следующем случае ptmalloc2 создает сегмент размером 0x21000(132KB), хотя мы только запросили 0x1000(4KB) байт. Остальная память будет управляться ptmalloc2
После вызова функции free в главном потоке созданное пространство памяти (сегмент кучи) не будет освобождено напрямую, а будет снова управляться ptmalloc2. Когда последующая программа запросит память, ptmalloc2 выделит программе соответствующую память в соответствии с алгоритмом выделения кучи.
После вызова pthread_create для создания потока в сегменте отображения памяти для созданного потока выделяется память размером 8 МБ. У потока есть свой собственный стек, который расположен в этой области. Однако в настоящее время я понятия не имею, для чего используются верхние 4 КБ с разрешением ---p.
После вызова malloc в потоке 1 мы видим, что пространство памяти размером 21000 байт (132 КБ) снова было выделено ptmalloc, хотя мы запросили всего 1000 байт (4 КБ). Но на этот раз куча находится в сегменте отображения памяти, а не после точки разрыва программы. Эта непрерывная область памяти (132 КБ) называется областью потоков.
После вызова free в потоке 1 мы видим, что освобождение выделенной области памяти не освобождает память кучи для операционной системы. Вместо этого выделенная область памяти (размером 1000 байт) освобождается в ptmolloc, который добавляет этот освобожденный блок бину своего потока.
Другим важным моментом здесь является то, что это не ровно одна область на поток, как ожидалось, поскольку при наличии большого количества потоков это стало бы затратно. Следовательно, приложение arena limit is based on the number of cores присутствует в системе.
Код:
For 32 bit systems: Number of arena = 2 * number of cores.
For 64 bit systems: Number of arena = 8 * number of cores.https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/
https://sensepost.com/blog/2017/painless-intro-to-the-linux-userland-heap/
https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/heap-structure/
https://raydenchia.com/heaps-of-fun-with-glibc-malloc/
https://0x434b.dev/overview-of-glibc-heap-exploitation-techniques/
https://sourceware.org/glibc/wiki/MallocInternals
https://blog.csdn.net/weixin_37921201/article/details/119744197
https://heap-exploitation.dhavalkapil.com/attacks/double_free
Последнее редактирование:
