Userland heap management

In 1996, OpenBSD adopted FreeBSD’s phkmalloc, written by Poul-Henning Kamp, thanks to Thorsten Lockert. It used sbrk, growing a contiguous region of memory, managed pages with a simple index, and chunks with a bitmap.

In October 2003, Ted Unangst added support for guard pages, based on Bruce Perens’ Electric fence. It was never was enabled by default, since it murders the performances, and causes important fragmentation issues.

With linked-list based allocator, unlink-attack were quite common. Apparently, Stefan Esser had a private version of safe-unlink around mid-2002, published it on bugtraq in December 2003, and (re?) added it in his Hardened-PHP patch 0.2.7 in April 2004.

The 1^st August 2001, Thierry Deval added mmmap-based randomization to malloc.

In August 2004, Windows XP SP2 was released, with safe-unlinking for the Windows heap allocator.

In April 2005, GLIBC 2.3.5 was released, also with safe-unlink.

The 28^th of July 2008, Otto Moerbeek wrote an “almost complete rewrite of malloc”, named after its creator’s name: otto malloc.

Contrary to phkmalloc, it uses mmap instead of sbrk, returns pages at random offsets, manages regions and their size in a hashtable (instead of a linked-list), and free’ed regions are stored in a cache with a randomized re-use to make UAF harder to exploit. All the metadata are completely out of band, making them harder to corrupt. It was also possible to mark pages in the cache as PROT_NONE, but it wasn’t enabled by default because of the monstrous performance impact. It also came with optional support for guard pages, based on Ted Unangst’s implementation, consisting in mapping a zone of a configurable length PROT_NONE, right behind the buffer. It would be nice to be able to have guard pages only between large chunks, as a middle ground between “no guards” and “no performances”. Otto-malloc landed in OpenBSD 4.4, on November 2008.

Damien Miller marked, in January 2009, malloc’s configuration options as read-only after their initialization.

Around 2013, Google published PartitionAlloc as part of the WebKit Template Framework, based on WebKit’s RenderArena’s custom allocator, to use in Google Chrome, based on the cool idea of partitioning allocations by types/sizes/lifetime. It has been kinda replaced in 2015 by Oilpan.

In December 2015, Daniel Micay added added a check for the integrity of the junk in free’ed chunks placed in quarantine, before effectively free’ing them, to catch use-after-frees. He also implemented canaries at the end of allocations, for small allocations, to detect linear heap overflows, put behind an option since it slightly increases memory consumption. That implementation had the drawback that some meta data ended up next to the allocated region itself, so Moerbeek rewrote the canary code for small allocations to use out-of-band data only and also added canaries for large objects.

Amusingly, the canaries behind posix_memalign weren’t correctly initialised until April 2017.

Since September 2017, Otto Moerbeek made delayed free mandatory. He also added optional kinda-deterministic double-free checks, probabilistic being the default.

In October 2020, Otto Moerbeek made the canaries used in the allocator random; they were static (and thus useless security-wise) before.

Amusingly, in 2023, Qualys tried to exploit CVE-2023-25136, a double-free in OpenSSH, and said the following regarding glibc’s malloc and otto-malloc:

We started our investigation on Debian bookworm (which uses glibc’s malloc), but we eventually switched to OpenBSD 7.2, because OpenBSD’s malloc (despite its very defensive programming) has two features that make it especially interesting for this particular double-free bug:

• Free chunks of memory are sorted (according to their size) into buckets that are spaced at power-of-two intervals; i.e., any object whose size is between 256 and 512 bytes can re-allocate the memory that was occupied by options.kex_algorithms. This gives us considerable freedom. (On the other hand, glibc’s malloc sorts free chunks of memory into buckets that are spaced at 16-byte intervals; i.e., only an object whose size is almost exactly 266 bytes can re-allocate the memory that was occupied by options.kex_algorithms. This leaves us with little freedom of choice.)

• OpenBSD’s malloc() function picks a free chunk at random from several (4) pages of memory; i.e., most of the time it will not pick the chunk where options.kex_algorithms was allocated, but at least sometimes it will (with a probability of ~1/(4*4096/512)=1/32). (On the other hand, glibc’s malloc() function behaves like a strict LIFO (last in, first out); i.e., it will never pick the chunk where options.kex_algorithms was allocated unless we precisely control the sequence of malloc() and free() calls in sshd, which is something we have been unable to do so far.)

In September 2023, Otto Moerbeek gave a talk at EuroBSDCon 2023, about How OpenBSD’s malloc helps the developer.

Later in 2023, in OpenBSD 7.4, otto-malloc is now checking all chunks in the delayed free list for write-after-free, which isn’t really a security mitigation, but it’ll likely catch bugs.

Scudo, mainly written my Kostya Kortchinsky, isn’t based on otto’s malloc, but on LLVM Sanitizer’s CombinedAllocator, and was born in 2016. It makes used of GWP-ASAN, as explained by Dmitry Vyukov during his Linux Plumbers 2019 presentation. It has partitions for its fast path (small allocations), and guard page on the slow one (large allocations), as well as quarantines for delayed frees, as well as various other cool stuff. It isn’t as secure as OpenBSD’s one, but it’s deliberate trade-off for massive performances, since it’s Android 11+ default allocator. For example, it’s using inline metadata with checksumming, to improve data locality. Rodrigo Branco published a nice article on its internal and properties the 21^st of September 2023 on L3Harris’ blog.

GrapheneOS’s hardened_malloc is heavily based on OpenBSD’s otto’s malloc, and in August 2019, Shawn Webb announced that he was planning on integrating hardened_malloc in HardenedBSD to replace jemalloc.

Nowadays, all serious allocators (at least the ones from Webkit, Apple Microsoft, Google Clang, …) are implementing security mitigations, like junking on free and on malloc, randomisation, forced alignment, quarantine/delayed frees, … but are usually less secure than Otto malloc, since they care more about performances than security.

Interestingly, otto malloc isn’t really tailored for environment where an attacker has scripting abilities, like in web-browsers, which are arguably one of the biggest/softest attack surface nowadays: It’s lacking defenses like WebKit’s Gigacage, or type-based isolation. But since browsers are usually coming with their own custom allocator, it wouldn’t change much anyway.

Otto malloc is an impressive piece of software, one the first seriously hardened allocator, and still the most secure one publicly deployed in production.

It’ll be interesting to see what will happen in the next following years, with the democratisation of things like memory tagging and GWP-ASAN. Something else that would be nice to have is comments on other allocator mitigations, like Apple’s IsoHeap, Gigacage, branch-less checks via pointers poisoning, … and why otto-malloc isn’t implementing them.