Tuesday, January 26, 2010

Glibc 2.11 stops the House of Mind

I was reading malloc.c from the Glibc 2.11 sources and I noticed a new check in the _int_free() function:
[4965]      bck = unsorted_chunks(av);
[4966] fwd = bck->fd;
[4967] if (__builtin_expect (fwd->bk != bck, 0))
[4968] {
[4969] errstr = "free(): corrupted unsorted chunks";
[4970] goto errout;
[4971] }
[4972] p->fd = fwd;
[4973] p->bk = bck;
[4974] if (!in_smallbin_range(size))
[4975] {
[4976] p->fd_nextsize = NULL;
[4977] p->bk_nextsize = NULL;
[4978] }
[4979] bck->fd = p;
[4980] fwd->bk = p;
The check starting on line 4967 appears to have been added this past June. If you're not a security person then let me bring you up to date. Corrupting heap meta data traditionally allows you to execute arbitrary code. There are plenty of papers out there you can read to catch up on the subject, but theres one important fact you should be aware of. Most of these techniques no longer work within 1 to 2 years of publication. This is because the libc maintainers add small bits of code like the one above to save you from yourself. This particular new patch is checking to see whether the arena's bin contains a location that points to a valid chunk. If that check wasn't there (as is the case in glibc 2.10.1) then the 'fwd->bk = p' line can be used to write the address of 'p' anywhere. If that didn't make sense to you then you're probably not a glibc maintainer or a neurotic security researcher, consider yourself normal.
If you're not familiar with the House of Mind then you should read 'The Malloc Maleficarum' written by Phantasmal Phantasmagoria:
"The method used involves tricking the wrapper invoked by free(),
called public_fREe(), into supplying the _int_free() internal
function with a designer controlled arena. This can subsequently
lead to an arbitrary memory overwrite. A call to free() actually
invokes a wrapper called public_fREe():"
I won't be covering these techniques in great detail here but essentially what can happen is through a single call to free() on a chunk we can overflow we can fool ptmalloc into using an arena structure we control. Certain members of the arena structure allow for arbitrary code execution to occur if the right conditions can be met. This technique currently still works in Ubuntu 9.10. The short story is: the new validation added to Glibc 2.11 stops the House of Mind technique.

... or does it?

The Malloc Maleficarum covers a second House of Mind technique which, unlike the first one, requires we place our arena at the location we want to overwrite. It still leverages a single call to free() and the trust the allocator has in the arena structure (its also been covered in other papers, see the bottom of this post) but the difference in the second technique is that the arenas 'fastbinY' container is used instead of 'bins'. This takes _int_free down a different code path, a far less constrained one. However the pointer exchange is not quite the same in this code path and so in order to gain code execution we need to place the start of our arena just before the data we want to overwrite. We can gain control of execution because we get a value of our choice written back to arena->fastbin[X] It's not an ideal situation, but it should still work in Glibc 2.11.

[4879] p->fd = *fb;
[4880] *fb = p; // This is how we get an arbitrary 4 byte overwrite

Perhaps more importantly then what does work is what will fix it. Because this technique is somewhat unreliable it may not make sense to further burden the allocator with yet another integrity check. But we should explore our options. We could try to stop all arena based attacks by inspecting where the arena itself resides, but this is a rather clumsy way of approaching the problem, and with ASLR enabled, it probably won't be too successful. A better solution might be to first check whether the chunk 'fb' points to contains a valid forward pointer to the next chunk in its list. But fastbin pointers are only singly linked, thus a subsequent check of the next chunks bwk pointer would not work. The reason they are not doubly linked is because they are never removed from these lists and consolidated with other free chunks, this of course helps performance of smaller, frequently allocated/free'd chunks. Another potential fix might be to check the current fastbin (the one that will be overwritten) entries chunk size, because the arena has to be placed near/on the region of memory we want to overwrite, the attacker most likely can not control what the size is. This partially validates that the 1) the location is valid (its mapped) and 2) has a size between 0 and MAX_FASTBIN. It might look something like this:

--- malloc.c 2009-10-30 13:17:08.000000000 -0400
+++ malloc-a.c 2010-01-20 08:28:36.000000000 -0500
@@ -4852,6 +4852,12 @@
fb = &fastbin (av, fastbin_index(size));
+ if (*fb->size > get_max_fast())
+ {
+ errstr = "invalid fastbin entry (free)";
+ goto errout;
+ }
mchunkptr fd;
mchunkptr old = *fb;

This of course is not fool proof, but its the best I've come up with in the short time I've thought about it. After a private conversation with a friend of mine who coincidentally happens to be doing some similar research, I'm not sure the integrity of the fastbin can be %100 verified in its current form.

FWIW: I emailed Glibc maintainers with my idea (as bad as it is) and did not receive a response.

Further reading on the subject:
malloc.c diff showing the new changes
MallocMaleficarum - The original paper
Aware Article - A good overview of the House of Mind with example code
A real exploit utilizing the first House of Mind 'bins' technique


Alfred said...

5 Years response time is better than infinite I suppose.

Chris Rohlf said...


True, I probably should have mentioned in the post that this did take 5 years to 'fix'. Several changes have been made to malloc.c over those 5 years that suggest the glibc developers had read the Malloc Maleficarum and were aware of the techniques.

Nate McFeters said...

Very excellent, and appreciate the historical references to provide context.

I do most my research on Windows, but I have to admit that I'm somewhat surprised that these unlink checks haven't been in glibc sooner...

Chris Rohlf said...


The original 'unlink' techniques have been patched for quite some time, but yah, these techniques remained alive for far too long!