Randomizing the Linux kernel heap freelists

Freelist usage

A freelist is a FIFO queue with each entry referencing a chunk of the heap. There is one freelist for multiple pages. When a new set of pages are initialized, the freelist order results in sequential allocations. SLUB and SLAB allocators design are different but their freelists are fairly similar.

Freelist state for new pages

Exploiting heap predictability

During a kernel heap overflow, an attacker doesn’t know the state of the heap. The heap might be fragmented with chunk spread in different places. An attacker must control the heap state to reliability exploit a heap overflow. It is true for user-mode or kernel-mode exploitation.

Differences between a heap default state and cleaned for an overflow

Freelist randomization

Randomizing a freelist is equivalent to shuffling a list of unique numbers. I picked the Fisher-Yates shuffle as a base:

Freelist randomization using template

Side note, SLAB freelist placement since 4.6-rc1

As a side note, a recent commit changed the placement of the freelist for the SLAB allocator. The freelist is now at the end of the reserved pages. A heap overflow might result in odd use-after-free condition as the freelist gets corrupted. Corrupting the freelist should be harder with randomization but not by much.

Heap hardening vs exploits vs performance

Heap hardening features are mainly protecting the heap against itself. Often they increase the chances of failure for an exploit by adding randomness. They don’t mitigate heap overflows. I think the main reason is the performance impact.

--

--

Security Architect. Worked at Google and Microsoft. Co-creator of Sysinternals Sysmon and Linux KRSI.

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Thomas Garnier

Thomas Garnier

Security Architect. Worked at Google and Microsoft. Co-creator of Sysinternals Sysmon and Linux KRSI.