Automatic Heap Layout Manipulation for Exploitation

Sean Heelan, Tom Melham, Daniel Kroening

Abstract

Heap Layout Manipulation (HLM), colloquially known as "Heap Feng Shui," is a sophisticated technique required to exploit heap-based memory corruption vulnerabilities. Traditionally, this process involves manually crafting program inputs to achieve a specific memory state, a task that is both tedious and expert-dependent. This paper introduces SHRIKE, the first automated approach to HLM. SHRIKE utilizes a pseudo-random black-box search algorithm to navigate the complex state space of heap allocators. By identifying useful code fragments from existing regression tests, SHRIKE can automatically generate scripts that produce desired heap layouts. Our evaluation demonstrates that SHRIKE successfully resolved 21 out of 30 real-world layout problems in the PHP interpreter, often in under ten minutes, transforming a manual art into a programmable science.

Introduction

Exploiting heap-based buffer overflows is significantly more challenging than exploiting stack-based vulnerabilities. While the stack follows a predictable layout, heap memory is managed by complex allocators (e.g., malloc, tcmalloc) that determine object placement based on a hidden internal state. To exploit a heap vulnerability, an attacker must ensure a "source" buffer (the overflow point) is positioned adjacent to a "destination" buffer (containing sensitive data like function pointers).

Achieving this precise alignment—Heap Feng Shui—requires deep knowledge of allocator internals and the target application's memory behavior. As software complexity grows, manual HLM becomes increasingly impractical. This research addresses this gap by proposing a search-based automation framework.

The SHRIKE System

The authors developed SHRIKE, a specialized tool designed to automate HLM for complex software like the PHP interpreter. SHRIKE operates through a multi-phase pipeline that avoids the need for complex mathematical modeling of the allocator's state.

The SHRIKE system architecture, illustrating the flow from regression tests to the final layout solution.

The process begins with Discovery, where a fuzzer analyzes PHP's regression tests to find "fragments"—sequences of code that trigger specific heap allocations or deallocations. Next, Identification locates PHP structures containing sensitive data suitable for corruption. Finally, the Search phase uses a pseudo-random algorithm to assemble these fragments into a script. By executing candidate scripts and measuring the resulting distance between target buffers, SHRIKE iteratively converges on a successful layout.

Visualizing Heap Layout Manipulation

The core challenge of HLM is manipulating the "holes" in memory created by deallocations to force the allocator to place new objects in specific locations.

A step-by-step visualization of heap layout manipulation, showing how sequences of creation and destruction operations can align target buffers.

As shown in the figure above, the process involves a sequence of operations:

  1. Initial Allocation: Creating multiple objects to fill existing gaps.
  2. Strategic Deallocation: Destroying specific objects to create precisely sized free blocks.
  3. Target Placement: Allocating the source and destination objects such that they occupy the newly created gaps in the desired order.

Key Results and Insights

SHRIKE was evaluated against both synthetic benchmarks and real-world vulnerabilities (CVEs) in the PHP interpreter.

  • Effectiveness in PHP: SHRIKE solved 21 out of 30 real-world layout problems. In successful cases, it found a solution in an average of 571 seconds after testing approximately 720,000 candidates.
  • The Power of Randomness: A key finding is that simple pseudo-random search is surprisingly effective. The "solution space" for heap layouts exhibits high symmetry, meaning many different allocation sequences can lead to the same physical layout.
  • Impact of "Noise": The authors quantified "interaction noise"—unintended allocations occurring as side effects of API calls. Noise is the primary factor increasing HLM difficulty, yet SHRIKE maintained a 31-41% success rate even in high-noise environments.
  • Allocator Defenses: The study confirmed that modern "segregated storage" allocators (like tcmalloc) significantly complicate exploitation by grouping similar-sized objects, making it harder to place different types of objects adjacently.

Conclusion

This work demonstrates that automated Heap Layout Manipulation is feasible even for complex, real-world applications. By treating the heap allocator as a black box and using search-based techniques, SHRIKE effectively automates what was previously a manual expert task. Future work aims to extend this approach to non-deterministic environments where background threads or address space layout randomization (ASLR) introduce additional uncertainty into the heap state.

Summary updated

BibTeX
@inproceedings{heelan2018automatic,
  author = {Sean Heelan and Tom Melham and Daniel Kroening},
  title = {{Automatic Heap Layout Manipulation for Exploitation}},
  booktitle = {USENIX Security},
  year = {2018},
  url = {https://openreview.net/forum?id=mJ9tm9uGsrz},
}
Figure