Full Report
-1 – Pre-Intro When looking at heap exploit tutorials most of the time I found myself lacking knowledge on the actual implementation and, soon, had the urge of knowing how it’s allocated and freed and why it’s done that way, memory wise. -0.9 – ptmalloc2 The best source of knowledge with regards to the implementation of the heap is itself, the source code. Do not fear it, thankfully it is widely commented!
Analysis Summary
# Research: Painless intro to the Linux userland heap
## Metadata
- Authors: Javier Jimenez
- Institution: SensePost (implied from website branding)
- Publication: SensePost Blog
- Date: 05 May 2017
## Abstract
This technical analysis provides an accessible introduction to the memory management implementation used in the Linux userland heap, specifically focusing on **ptmalloc2**. The author, motivated by a lack of practical understanding from existing heap exploitation tutorials, delves into the structure and mechanisms of `ptmalloc2` by examining its source code (specifically `malloc.c` from `glibc-2.25`). The paper explains core concepts such as Arenas, the Top chunk, and Bins (including Unsorted, Small, and Large chunks), illustrating memory allocation and deallocation flow. It concludes by briefly teasing common heap exploitation vectors derived from these underlying mechanisms.
## Research Objective
The primary objective is to bridge the knowledge gap faced by those learning heap exploitation by providing a foundational, clear understanding of how memory is allocated and freed within the Linux userland heap, using the ubiquitous `ptmalloc2` implementation as the focus.
## Methodology
### Approach
The approach is primarily based on source code analysis and conceptual explanation. The author uses direct excerpts and references from the `ptmalloc2` source code to detail its internal workings. The concepts are then clarified using human-readable, "l33t-graph style" diagrams illustrating memory layout and the state changes during allocation and freeing.
### Dataset/Environment
The primary subject of study is the `ptmalloc2` implementation found in the GNU C Library (glibc), specifically referencing version 2.25. The context is the standard Linux userland memory layout.
### Tools & Technologies
- **Source Code Inspection:** Direct analysis of `glibc-2.25/malloc/malloc.c` and `malloc/arena.c`.
- **Visualization:** Conceptual diagrams to represent memory structures (Heap growth direction, Arenas, Top, Bins).
## Key Findings
### Primary Results
1. **ptmalloc2 Foundation:** The modern Linux heap management relies on **ptmalloc2**, which builds upon Doug Lea’s Malloc (`dlmalloc`) but adds threading support.
2. **Arena Structure:** The heap is organized around **Arenas**, which store per-thread heaps. The number of Arenas is limited based on the number of processor cores detected (specifically using the formula `n * (sizeof(long) == 4 ? 2 : 8)`).
3. **Top Chunk and Wilderness:** New memory allocations are served first from the **Top** chunk of memory within an Arena. Memory requested beyond the Top chunk extends the heap into the **Wilderness**.
4. **Bin Organization:** Freed chunks are managed in **Bins**, which total 128 structures: one Unsorted chunk bin, 96 Small chunk bins, and 31 Large chunk bins.
5. **Chunk Management Differentiation:** Small chunks are stored in bins corresponding to their exact size, sorted by freeing time. Large chunks are stored in bins sorted strictly by size.
6. **Unlink Redundancy Checks:** Source code analysis reveals specific checks implemented (e.g., in the `unlink` macro context) to ensure performance and prevent immediate exploitation by avoiding the removal of the first entry in a size bin if possible, or by performing basic checks (`victim != last(bin) && chunksize(victim) == chunksize(victim->fd)`).
### Novel Contributions
- Providing a highly accessible, introductory breakdown of complex `ptmalloc2` structures (Arenas, Top, Bins) directly grounded in source code inspection, aimed at demystifying heap exploitation prerequisites.
- Highlighting specific, source-level defensive/performance code that modifies standard linked-list manipulation during chunk coalescing or removal (like the check before `unlink`).
## Technical Details
The article details the memory layout where the Heap grows towards higher addresses, contrasting with the Stack growing towards lower addresses. It focuses heavily on the structures within an Arena:
* **Top Chunk:** The boundary marker for extending memory. Initial allocation forces the Top chunk size to 0, triggering an OS request.
* **Bins:** Critical for fast retrieval of freed memory. When a large chunk is freed, it is placed in a **skip list** structure managed via `fd_nextsize` and `bk_nextsize` pointers if it's not the smallest/largest in its relevant large bin.
* **Unlinking Safety:** The discussion points out that while the `unlink` macro seems dangerous, `ptmalloc2` includes checks (lines 3622+) to avoid dereferencing uninitialized memory or causing null pointer references, especially for the first entry in a bin list, often requiring an attacker to satisfy conditions bypassing these safety mechanisms.
## Practical Implications
### For Security Practitioners
Understanding the exact state of memory structures (Arena location, Bin contents) is prerequisite knowledge for crafting reliable heap exploitation payloads, whether exploiting use-after-free, double-free, or heap buffer overflows.
### For Defenders
Defenders must be aware that heap exploitation often relies on manipulating these structures, especially related to the `unlink` operation or bypassing specific checks implemented in modern allocators like `ptmalloc2`. Exploitation vectors include:
1. Overwriting adjacent chunks (often bypassing redundancy checks).
2. Double-free vulnerabilities (if preconditions are met).
3. Small out-of-bounds writes used to flip the `PREV_INUSE` bit of the subsequent chunk header.
### For Researchers
This analysis serves as a foundational stepping stone. Researchers can use this knowledge to build upon existing mitigation techniques (like hardened `malloc` implementations) or explore more advanced heap manipulation techniques that successfully navigate the structure checks in `ptmalloc2`.
## Limitations
The author notes that an intended section detailing exploit scenarios was omitted due to length and density, indicating that practical exploitation techniques are not fully covered in this introductory piece. The discussion on the `unlink` macro, while insightful, quickly touches upon redundancy checks without providing a full, bypassed exploit path.
## Comparison to Prior Work
The paper explicitly positions itself as an update to older resources that focused on Doug Lea’s Malloc (`dlmalloc`). By focusing on **ptmalloc2**, the research addresses the contemporary standard used in threaded Linux environments, which differs significantly due to the necessity of managing multiple concurrent Arenas.
## Real-world Applications
- Developing proof-of-concept (PoC) exploits targeting vulnerabilities in software employing `malloc`/`free` on Linux systems running modern glibc.
- Debugging memory corruption issues by tracing allocation/deallocation calls against the known `ptmalloc2` state.
## Future Work
The author plans a future entry dedicated to concrete exploit scenarios, likely detailing how to bypass the mentioned redundancy checks and leverage bugs like double-frees or single-byte writes effectively within the `ptmalloc2` framework.
## References
- Doug Lea's Malloc documentation (`http://g.oswego.edu/dl/html/malloc.html`).
- Source code for `glibc-2.25` (`https://ftp.gnu.org/gnu/glibc/glibc-2.25.tar.bz2`).
- GitHub Repo for accompanying PoCs (`https://github.com/n30m1nd/painless_intro_ptmalloc2`).