Patch to further harden glibc malloc metadata against 1-byte overflows

Hi,

[This is a resend of a private conversation started with Florian]

Back in 2014, we landed a malloc hardening measure against 1-byte
overflows. Here is a reference:

https://www.sourceware.org/ml/glibc-bugs/2014-09/msg00181.html

Since then, there's been this really interesting piece of work that
exploited Chrome OS using a 1-byte overflow to attack glibc malloc()
metadata in a different way:

https://googleprojectzero.blogspot.com/2016/12/chrome-os-exploit-one-byte-overflow-and.html

It has been bothering me that there's still a known, generic way to
attack 1-byte overflows in glibc malloc(). So I put some thought into
whether the situation can be cleanly detected and prevented.
It can. I've attached a 2-line patch (malloc.c.diff) that cleanly
detects and aborts on the condition. I've also attached an old test
case I had for this issue
(shrink_free_hole_alloc_overlap_consolidate_backward.c). Without the
patch, the program exits normally, having aliased a couple of heap
chunks. With the patch, the program exits with something like "***
Error in `./a.out': corrupted size vs. prev_size: 0x00000000022a0400
***"

I would be very excited to see this patch land :) I think it shuts
down a known, significant mitigation bypass. I also worry that if
there remain any serious bugs in important Linux services, they are
likely to bias towards subtle "1-byte overflows" and the like, which
can currently be exploited as demonstrated by the blog post above.
This patch can't defend against more powerful corruption primitives,
such as more arbitrary overflows or multiple overflows, but I think
it's a step forward for 1-byte overflows and particularly 1-byte NUL
overflows.


Cheers
Chris

I'll review this in three parts: correctness, performance, and nitpicks.

Correctness: I think this patch is correct.  All uses of the unlink()
macro are for the regular bins (which includes unsorted, but that's OK);
fastbins are handled separately, as are the sentinels and top chunks. 
Since next_chunk->prev_size is part of the current chunk, it's always
available to check.  This patch doesn't cover removing chunks from
fastbins, but that doesn't reduce the correctness of this patch.

Performance: I was unable to detect any significant performance
degradation due to the extra code, although obviously "more checking"
means "slower" to a certain extent.  This code is generally limited to
the slower paths through malloc anyway, and I think any performance
issues are too small to worry about.

Nitpicks: the patch doesn't apply as-is, at least in the recent tree I
tested against, as prev_size is not the current field name.  Also,
please use the prev_size() macro instead of a direct access.  I would
like to see "in unlink" in the crash text, but that would make the
message inconsistent with the other ones.  At least the message is
unique within malloc ;-)  Lastly, please make sure the trailing
backslashes all line up when using GNU-standard tabstops.

Overall, I think this patch is acceptable and should be applied, with
the nitpicks fixed, of course.  If you can't commit it yourself, please
post an updated patch (cc me) and I'll apply it for you.

Thanks!

DJ

Thanks, DJ.

I'm traveling in the boonies for a few days and will address these
items upon return.


Cheers
Chris

On Thu, Mar 16, 2017 at 1:42 PM, DJ Delorie <dj@redhat.com> wrote:
> I'll review this in three parts: correctness, performance, and nitpicks.
>
> Correctness: I think this patch is correct.  All uses of the unlink()
> macro are for the regular bins (which includes unsorted, but that's OK);
> fastbins are handled separately, as are the sentinels and top chunks.
> Since next_chunk->prev_size is part of the current chunk, it's always
> available to check.  This patch doesn't cover removing chunks from
> fastbins, but that doesn't reduce the correctness of this patch.
>
> Performance: I was unable to detect any significant performance
> degradation due to the extra code, although obviously "more checking"
> means "slower" to a certain extent.  This code is generally limited to
> the slower paths through malloc anyway, and I think any performance
> issues are too small to worry about.
>
> Nitpicks: the patch doesn't apply as-is, at least in the recent tree I
> tested against, as prev_size is not the current field name.  Also,
> please use the prev_size() macro instead of a direct access.  I would
> like to see "in unlink" in the crash text, but that would make the
> message inconsistent with the other ones.  At least the message is
> unique within malloc ;-)  Lastly, please make sure the trailing
> backslashes all line up when using GNU-standard tabstops.
>
> Overall, I think this patch is acceptable and should be applied, with
> the nitpicks fixed, of course.  If you can't commit it yourself, please
> post an updated patch (cc me) and I'll apply it for you.
>
> Thanks!
>
> DJ
>
>
>

Thanks! What a nice treat to read upon surviving the boonies :-)

As a follow up question: is there any appetite for any additional
glibc malloc metadata checks? While studying the code, I noticed a few
extra checks that could be added here and there. I don't think any of
them would be as useful as security defenses, but maybe they could
trap heap corruptions closer to the time they occurred. Any interest?


Cheers
Chris

On Fri, Mar 17, 2017 at 12:46 PM, DJ Delorie <dj@redhat.com> wrote:
>
> Chris Evans <scarybeasts@gmail.com> writes:
>> I'm traveling in the boonies for a few days and will address these
>> items upon return.
>
> In that case, I've checked it in for you.  Enjoy the boonies :-)

Hi,

I've been working on additional integrity checks in the malloc code
and had some discussion with Florian about it. Now seems to be as good
a time as any to submit them as an RFC.

A few notes on the patches:
* the main goal was to break currently known exploitation techniques
with the simplest changes.
* they passed the tests in November, now I only had time to check if
they apply to master. All do, except
0002-malloc-Harden-unlink-further.patch, which trivially conflicts
with the patch from Chris. The two address different issues, though.
* there was no profiling done.
* 0005-malloc-Harden-the-forward-and-backward-coalescing-in.patch is a
subset of the patch that started this thread, so it can be ignored.


A spreadsheet summarizing glibc heap exploitation techniques and the
integrity checks/ideas implemented can be found here:
https://docs.google.com/spreadsheets/d/1Xu1sqg0S4D5fKp0XDGCRnwIjCMT3QItQZyrABZokzLI/pubhtml
I've uploaded the patch series here:
https://gist.github.com/andigena/d16f6ceb724de241f19a6818c5122229
The commit hashes can be cross-referenced with the table.

I would like to apologize for not following the patch submission
guidelines but I'm really busy at the moment and wanted to get this
out now to get feedback and possibly avoid duplicate work. If there's
interest, I will submit them properly (I completed copyright
assignment previously).

Other than integrity checks, what I really think would be important is
the elimination of some determinism from the allocator. In
exploitation scenarios where leaking information from the target is
not realistic (which I believe is pretty typical for glibc malloc),
any determinism is useful for the attacker, especially if
brute-forcing is not an option.
* offsets of chunks into their heap and page are deterministic. For
example, Chris relied on this in his impressive exploit here:
http://scarybeastsecurity.blogspot.hu/2016/11/0day-exploit-advancing-exploitation.html
(trick #2). Adding a random-sized allocation on heap creation seems
like a cheap way to mess with the offsets.
* the ordering of chunks is deterministic. While I can see many ways
to address this, I'm not really qualified to judge their possible
impact on performance. Something simple could work, like randomly
choosing the front or back chunk from bins when allocating, or
randomly giving up best-fit and splitting larger chunks.

Also I'm unsure how the per-thread caching proposal will fit into
this, didn't have the chance to look at it yet.

Regards,
Istvan

On Wed, Mar 22, 2017 at 12:14 AM, DJ Delorie <dj@redhat.com> wrote:
>
> Chris Evans <scarybeasts@gmail.com> writes:
> > As a follow up question: is there any appetite for any additional
> > glibc malloc metadata checks? While studying the code, I noticed a few
> > extra checks that could be added here and there. I don't think any of
> > them would be as useful as security defenses, but maybe they could
> > trap heap corruptions closer to the time they occurred. Any interest?
>
> I'm open to more malloc hardening, sure.  Better to fix the holes
> *before* they're turned into exploits, as long as performance doesn't
> suffer too much.
>
> If you're going to be a regular contributor now, though, we might
> consider streamlining the process a bit ;-)

Hi Istvan,

On Thu, Mar 23, 2017 at 6:52 AM, Istvan Kurucsai <pistukem@gmail.com> wrote:
> Hi,
>
> I've been working on additional integrity checks in the malloc code and had
> some discussion with Florian about it. Now seems to be as good a time as any
> to submit them as an RFC.

This is really good and interesting work. I'd like to help, perhaps by
providing notes on what likely would and would not inconvenience
exploits. Perhaps this could help prioritize which changes to focus on
landing?

>
> A few notes on the patches:
> * the main goal was to break currently known exploitation techniques with
> the simplest changes.

Sounds like a good goal. Within this goal, I wonder if there's some
form of prioritizion that could be applied? e.g.:

1) Fix outright bugs in glibc malloc(), such as the integer underflow
in realloc() and the failure to check return value of munmap()
2) Fix inconsistencies in existing checks (e.g. malloc_consolidate
seems to be missing checks present in other paths, as you've noted).
3) Breaking known exploitation techniques that can help defeat a
process running with good mitigations (e.g. x64 + ASLR + DEP etc.).
For example, something like "unsafe unlinking" seems to require
knowledge of an existing pointer value, unless I'm missing some
partial overwrite trick, so could be de-prioritized.

When it comes to extra metadata protections, I think there's are
broader questions to be asked: is it time to consider going all in and
doing something simple and generic, such as adding a cookie to the
metadata structure? Super fast cookie checking schemes exist.

> * they passed the tests in November, now I only had time to check if they
> apply to master. All do, except 0002-malloc-Harden-unlink-further.patch,
> which trivially conflicts with the patch from Chris. The two address
> different issues, though.
> * there was no profiling done.
> * 0005-malloc-Harden-the-forward-and-backward-coalescing-in.patch is a
> subset of the patch that started this thread, so it can be ignored.
>
>
> A spreadsheet summarizing glibc heap exploitation techniques and the
> integrity checks/ideas implemented can be found here:
> https://docs.google.com/spreadsheets/d/1Xu1sqg0S4D5fKp0XDGCRnwIjCMT3QItQZyrABZokzLI/pubhtml
> I've uploaded the patch series here:
> https://gist.github.com/andigena/d16f6ceb724de241f19a6818c5122229
> The commit hashes can be cross-referenced with the table.
>
> I would like to apologize for not following the patch submission guidelines
> but I'm really busy at the moment and wanted to get this out now to get
> feedback and possibly avoid duplicate work. If there's interest, I will
> submit them properly (I completed copyright assignment previously).
>
> Other than integrity checks, what I really think would be important is the
> elimination of some determinism from the allocator. In exploitation
> scenarios where leaking information from the target is not realistic (which
> I believe is pretty typical for glibc malloc), any determinism is useful for
> the attacker, especially if brute-forcing is not an option.

Agreed. I'm actually not a fan of randomizing freelist handling in
allocators as I think the attacker often has enough control to restore
determinism by using carefully crafted allocation sequences. Is the
added complexity and performance hit (cache coldness etc.) worth it?
Hard to say; I lean towards no.

I am however a big fan of randomizing the larger chunks, such as
mmap() for new arena and mmap() for large individual allocations. I've
been hitting tons and tons of conditions recently where deterministic
stacking of glibc malloc() related mmap()s is super useful, e.g.
https://scarybeastsecurity.blogspot.com/2016/12/1day-poc-with-rip-deterministic-linux.html
And I also have another example in the works. We need to kill this
primitive with fire. I'll note that Chrome's PartitionAlloc allocator
randomizes both types of mmap() (arenas and large individual
allocations) across most of the x64 address space with no known issues
and no performance problems noted in the development history.

> * offsets of chunks into their heap and page are deterministic. For example,
> Chris relied on this in his impressive exploit here:
> http://scarybeastsecurity.blogspot.hu/2016/11/0day-exploit-advancing-exploitation.html
> (trick #2). Adding a random-sized allocation on heap creation seems like a
> cheap way to mess with the offsets.

Yeah, that's a good idea. A thread + thread heap is a pretty heavy
allocation so tossing a small random number bytes to defeat the
partial pointer overwrite trick seems reasonable. I wonder how many
bytes is reasonable?


Cheers
Chris

> * the ordering of chunks is deterministic. While I can see many ways to
> address this, I'm not really qualified to judge their possible impact on
> performance. Something simple could work, like randomly choosing the front
> or back chunk from bins when allocating, or randomly giving up best-fit and
> splitting larger chunks.
>
> Also I'm unsure how the per-thread caching proposal will fit into this,
> didn't have the chance to look at it yet.
>
> Regards,
> Istvan
>
> On Wed, Mar 22, 2017 at 12:14 AM, DJ Delorie <dj@redhat.com> wrote:
>>
>> Chris Evans <scarybeasts@gmail.com> writes:
>> > As a follow up question: is there any appetite for any additional
>> > glibc malloc metadata checks? While studying the code, I noticed a few
>> > extra checks that could be added here and there. I don't think any of
>> > them would be as useful as security defenses, but maybe they could
>> > trap heap corruptions closer to the time they occurred. Any interest?
>>
>> I'm open to more malloc hardening, sure.  Better to fix the holes
>> *before* they're turned into exploits, as long as performance doesn't
>> suffer too much.
>>
>> If you're going to be a regular contributor now, though, we might
>> consider streamlining the process a bit ;-)
>
>