* Re: [PATCH] Add Safe-Linking to fastbins and tcache
@ 2020-03-19 13:32 Wilco Dijkstra
2020-03-19 15:09 ` Eyal Itkin
0 siblings, 1 reply; 33+ messages in thread
From: Wilco Dijkstra @ 2020-03-19 13:32 UTC (permalink / raw)
To: 'GNU C Library', eyal.itkin
Hi,
I tried applying your patch - there seem to be issues with formatting:
@@ -327,6 +327,15 @@ __malloc_assert (const char *assertion, const
char *file, unsigned int line,
# define MAX_TCACHE_COUNT UINT16_MAX
and
+#define PROTECT_PTR(pos, ptr, type) ((type)((((size_t)pos) >>
PAGE_SHIFT) ^ ((size_t)ptr)))
It seems something cut off those lines as being too long...
+ if (__glibc_unlikely(!aligned_OK(p)))
There should be spaces before each '('. See the GLIBC coding style:
https://www.gnu.org/prep/standards/standards.html#Formatting
Did you run the GLIBC malloc benchmarks before/after this change?
Cheers,
Wilco
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-19 13:32 [PATCH] Add Safe-Linking to fastbins and tcache Wilco Dijkstra
@ 2020-03-19 15:09 ` Eyal Itkin
2020-03-19 18:15 ` Eyal Itkin
0 siblings, 1 reply; 33+ messages in thread
From: Eyal Itkin @ 2020-03-19 15:09 UTC (permalink / raw)
To: Wilco Dijkstra; +Cc: GNU C Library
Hi,
Thanks for the feedback, I'll will work on it now and send an updated version.
I passed all of GLIBC's tests and also benchmakred the results in a
test I made. I wasn't aware of the fact that there is already a
benchmarking suite for malloc in GLIBC, and I will now try to use it.
In the assembly level, it adds 3/4 assembly instructions per malloc()
/ free(), and we had great benchmarking results for this feature in
all of the tests we made thus far so I am not worried about it, but I
will use your benchmarking suite as well and send you back the
results.
Thanks again,
Eyal.
On Thu, Mar 19, 2020 at 3:33 PM Wilco Dijkstra <Wilco.Dijkstra@arm.com> wrote:
>
> Hi,
>
> I tried applying your patch - there seem to be issues with formatting:
>
> @@ -327,6 +327,15 @@ __malloc_assert (const char *assertion, const
> char *file, unsigned int line,
> # define MAX_TCACHE_COUNT UINT16_MAX
>
> and
>
> +#define PROTECT_PTR(pos, ptr, type) ((type)((((size_t)pos) >>
> PAGE_SHIFT) ^ ((size_t)ptr)))
>
> It seems something cut off those lines as being too long...
>
> + if (__glibc_unlikely(!aligned_OK(p)))
>
> There should be spaces before each '('. See the GLIBC coding style:
> https://www.gnu.org/prep/standards/standards.html#Formatting
>
> Did you run the GLIBC malloc benchmarks before/after this change?
>
> Cheers,
> Wilco
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-19 15:09 ` Eyal Itkin
@ 2020-03-19 18:15 ` Eyal Itkin
2020-03-20 0:10 ` Wilco Dijkstra
2020-03-20 2:53 ` DJ Delorie
0 siblings, 2 replies; 33+ messages in thread
From: Eyal Itkin @ 2020-03-19 18:15 UTC (permalink / raw)
To: Wilco Dijkstra; +Cc: GNU C Library
[-- Attachment #1: Type: text/plain, Size: 3655 bytes --]
Hi,
I went over the patch and fixed it to conform to the coding standards.
I'm also added it as an attachment, hoping that this way lines won't
break during the transmission of the email.
Regarding the benchmarks, I've just ran them on a simple GCP instance
(1 vCPU) before and after the patch. As you can see below, the change
isn't measurable in the "malloc-simple" tests. Sometimes the vanilla
version is faster (as it should be), but sometimes the patched version
is faster, which usually means that the change is lower than the noise
level on the testing server.
malloc-simple-128 (before patch):
{
"timing_type": "hp_timing",
"functions": {
"malloc": {
"": {
"malloc_block_size": 128,
"max_rss": 1676,
"main_arena_st_allocs_0025_time": 77.511,
"main_arena_st_allocs_0100_time": 94.4398,
"main_arena_st_allocs_0400_time": 93.528,
"main_arena_st_allocs_1600_time": 161.315,
"main_arena_mt_allocs_0025_time": 117.634,
"main_arena_mt_allocs_0100_time": 144.564,
"main_arena_mt_allocs_0400_time": 159.591,
"main_arena_mt_allocs_1600_time": 230.882,
"thread_arena__allocs_0025_time": 120.277,
"thread_arena__allocs_0100_time": 146.871,
"thread_arena__allocs_0400_time": 157.205,
"thread_arena__allocs_1600_time": 223.46
}
}
}
}
malloc-simple-128 (with the patch):
{
"timing_type": "hp_timing",
"functions": {
"malloc": {
"": {
"malloc_block_size": 128,
"max_rss": 1672,
"main_arena_st_allocs_0025_time": 81.6073,
"main_arena_st_allocs_0100_time": 94.0351,
"main_arena_st_allocs_0400_time": 97.1118,
"main_arena_st_allocs_1600_time": 159.065,
"main_arena_mt_allocs_0025_time": 123.422,
"main_arena_mt_allocs_0100_time": 146.074,
"main_arena_mt_allocs_0400_time": 151.536,
"main_arena_mt_allocs_1600_time": 215.798,
"thread_arena__allocs_0025_time": 116.577,
"thread_arena__allocs_0100_time": 142.024,
"thread_arena__allocs_0400_time": 158.38,
"thread_arena__allocs_1600_time": 233.216
}
}
}
}
Will be more than happy to help if there are more questions or
additional fixes needed.
Thanks for your time,
Eyal.
On Thu, Mar 19, 2020 at 5:09 PM Eyal Itkin <eyal.itkin@gmail.com> wrote:
>
> Hi,
>
> Thanks for the feedback, I'll will work on it now and send an updated version.
> I passed all of GLIBC's tests and also benchmakred the results in a
> test I made. I wasn't aware of the fact that there is already a
> benchmarking suite for malloc in GLIBC, and I will now try to use it.
>
> In the assembly level, it adds 3/4 assembly instructions per malloc()
> / free(), and we had great benchmarking results for this feature in
> all of the tests we made thus far so I am not worried about it, but I
> will use your benchmarking suite as well and send you back the
> results.
>
> Thanks again,
> Eyal.
>
> On Thu, Mar 19, 2020 at 3:33 PM Wilco Dijkstra <Wilco.Dijkstra@arm.com> wrote:
> >
> > Hi,
> >
> > I tried applying your patch - there seem to be issues with formatting:
> >
> > @@ -327,6 +327,15 @@ __malloc_assert (const char *assertion, const
> > char *file, unsigned int line,
> > # define MAX_TCACHE_COUNT UINT16_MAX
> >
> > and
> >
> > +#define PROTECT_PTR(pos, ptr, type) ((type)((((size_t)pos) >>
> > PAGE_SHIFT) ^ ((size_t)ptr)))
> >
> > It seems something cut off those lines as being too long...
> >
> > + if (__glibc_unlikely(!aligned_OK(p)))
> >
> > There should be spaces before each '('. See the GLIBC coding style:
> > https://www.gnu.org/prep/standards/standards.html#Formatting
> >
> > Did you run the GLIBC malloc benchmarks before/after this change?
> >
> > Cheers,
> > Wilco
[-- Attachment #2: 0001-Add-Safe-Linking-to-fastbins-and-tcache.patch --]
[-- Type: application/octet-stream, Size: 9117 bytes --]
From efd94f8d72e903fa1638ff2a28aa23f14c4b0f0d Mon Sep 17 00:00:00 2001
From: Eyal Itkin <eyalit@checkpoint.com>
Date: Thu, 19 Mar 2020 18:06:07 +0200
Subject: [PATCH] Add Safe-Linking to fastbins and tcache
Safe-Linking is a security mechanism that protects single-linked
lists (such as the fastbin and tcache) from being tampered by attackers.
The mechanism makes use of randomness from ASLR (mmap_base), and when
combined with chunk alignment integrity checks, it protects the
pointers from being hijacked by an attacker.
While Safe-Unlinking protects double-linked lists (such as the small
bins), there wasn't any similar protection for attacks against
single-linked lists. This solution protects against 3 common attacks:
* Partial pointer override: modifies the lower bytes (Little Endian)
* Full pointer override: hijacks the pointer to an attacker's location
* Unaligned chunks: pointing the list to an unaligned address
The design assumes an attacker doesn't know where the heap is located,
and uses the ASLR randomness to "sign" the single-linked pointers. We
mark the pointer as P and the location in which it is stored as L, and
the calculation will be:
* PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
* *L = PROTECT(P)
This way, the random bits from the address L (which start at the bit
in the PAGE_SHIFT position), will be merged with LSB of the stored
protected pointer. This protection layer prevents an attacker from
modifying the pointer into a controlled value.
An additional check that the chunks are MALLOC_ALIGNed adds an
important layer:
* Attackers can't point to illegal (unaligned) memory addresses
* Attackers must guess correctly the alignment bits
On standard 32 bit Linux machines, an attack will directly fail 7
out of 8 times, and on 64 bit machines it will fail 15 out of 16
times.
This proposed patch was benchmarked and it's effect on the overall
performance of the heap was negligible and couldn't be distinguished
from the default variance between tests on the vanilla version. A
similar protection was added to Chromium's version of TCMalloc
in 2012, and according to their documentation it had an overhead of
less than 2%.
---
malloc/malloc.c | 64 +++++++++++++++++++++++++++++++++++++++----------
1 file changed, 51 insertions(+), 13 deletions(-)
diff --git a/malloc/malloc.c b/malloc/malloc.c
index 7d7d30bb13..5dbb8e7487 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -327,6 +327,16 @@ __malloc_assert (const char *assertion, const char *file, unsigned int line,
# define MAX_TCACHE_COUNT UINT16_MAX
#endif
+/*
+ Safe-Linking:
+ Use randomness from ASLR (mmap_base) to protect single-linked lists
+ of Fast-Bins and TCache. Together with allocation alignment checks, this
+ mechanism reduces the risk of pointer hijacking, as was done with
+ Safe-Unlinking in the double-linked lists of Small-Bins.
+*/
+#define PROTECT_PTR(pos, ptr, type) \
+ ((type)((((size_t)pos) >> PAGE_SHIFT) ^ ((size_t)ptr)))
+#define REVEAL_PTR(pos, ptr, type) PROTECT_PTR (pos, ptr, type)
/*
REALLOC_ZERO_BYTES_FREES should be set if a call to
@@ -2157,12 +2167,14 @@ do_check_malloc_state (mstate av)
while (p != 0)
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("do_check_malloc_state(): un-aligned fastbin chunk detected");
/* each chunk claims to be inuse */
do_check_inuse_chunk (av, p);
total += chunksize (p);
/* chunk belongs in this bin */
assert (fastbin_index (chunksize (p)) == i);
- p = p->fd;
+ p = REVEAL_PTR (&p->fd, p->fd, mchunkptr);
}
}
@@ -2923,7 +2935,7 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
detect a double free. */
e->key = tcache;
- e->next = tcache->entries[tc_idx];
+ e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx], tcache_entry *);
tcache->entries[tc_idx] = e;
++(tcache->counts[tc_idx]);
}
@@ -2934,9 +2946,11 @@ static __always_inline void *
tcache_get (size_t tc_idx)
{
tcache_entry *e = tcache->entries[tc_idx];
- tcache->entries[tc_idx] = e->next;
+ tcache->entries[tc_idx] = REVEAL_PTR (&e->next, e->next, tcache_entry *);
--(tcache->counts[tc_idx]);
e->key = NULL;
+ if (__glibc_unlikely (!aligned_OK (e)))
+ malloc_printerr ("malloc(): un-aligned tcache chunk detected");
return (void *) e;
}
@@ -2960,7 +2974,9 @@ tcache_thread_shutdown (void)
while (tcache_tmp->entries[i])
{
tcache_entry *e = tcache_tmp->entries[i];
- tcache_tmp->entries[i] = e->next;
+ if (__glibc_unlikely (!aligned_OK (e)))
+ malloc_printerr ("tcache_thread_shutdown(): un-aligned tcache chunk detected");
+ tcache_tmp->entries[i] = REVEAL_PTR (&e->next, e->next, tcache_entry *);
__libc_free (e);
}
}
@@ -3570,8 +3586,11 @@ _int_malloc (mstate av, size_t bytes)
victim = pp; \
if (victim == NULL) \
break; \
+ pp = REVEAL_PTR (&victim->fd, victim->fd, mfastbinptr); \
+ if (__glibc_unlikely (!aligned_OK (pp))) \
+ malloc_printerr ("malloc(): un-aligned fastbin chunk detected"); \
} \
- while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \
+ while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
!= victim); \
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
@@ -3583,8 +3602,11 @@ _int_malloc (mstate av, size_t bytes)
if (victim != NULL)
{
+ if (__glibc_unlikely (!aligned_OK (victim)))
+ malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
+
if (SINGLE_THREAD_P)
- *fb = victim->fd;
+ *fb = REVEAL_PTR (&victim->fd, victim->fd, mfastbinptr);
else
REMOVE_FB (fb, pp, victim);
if (__glibc_likely (victim != NULL))
@@ -3605,8 +3627,10 @@ _int_malloc (mstate av, size_t bytes)
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = *fb) != NULL)
{
+ if (__glibc_unlikely (!aligned_OK (tc_victim)))
+ malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
if (SINGLE_THREAD_P)
- *fb = tc_victim->fd;
+ *fb = REVEAL_PTR (&tc_victim->fd, tc_victim->fd, mfastbinptr);
else
{
REMOVE_FB (fb, pp, tc_victim);
@@ -4196,11 +4220,15 @@ _int_free (mstate av, mchunkptr p, int have_lock)
LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
for (tmp = tcache->entries[tc_idx];
tmp;
- tmp = tmp->next)
+ tmp = REVEAL_PTR (&tmp->next, tmp->next, tcache_entry *))
+ {
+ if (__glibc_unlikely (!aligned_OK (tmp)))
+ malloc_printerr ("free(): un-aligned chunk detected in tcache 2");
if (tmp == e)
malloc_printerr ("free(): double free detected in tcache 2");
/* If we get here, it was a coincidence. We've wasted a
few cycles, but don't abort. */
+ }
}
if (tcache->counts[tc_idx] < mp_.tcache_count)
@@ -4264,7 +4292,7 @@ _int_free (mstate av, mchunkptr p, int have_lock)
add (i.e., double free). */
if (__builtin_expect (old == p, 0))
malloc_printerr ("double free or corruption (fasttop)");
- p->fd = old;
+ p->fd = PROTECT_PTR (&p->fd, old, mchunkptr);
*fb = p;
}
else
@@ -4274,7 +4302,8 @@ _int_free (mstate av, mchunkptr p, int have_lock)
add (i.e., double free). */
if (__builtin_expect (old == p, 0))
malloc_printerr ("double free or corruption (fasttop)");
- p->fd = old2 = old;
+ old2 = old;
+ p->fd = PROTECT_PTR (&p->fd, old, mchunkptr);
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
!= old2);
@@ -4472,13 +4501,16 @@ static void malloc_consolidate(mstate av)
if (p != 0) {
do {
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("malloc_consolidate(): un-aligned fastbin chunk detected");
+
unsigned int idx = fastbin_index (chunksize (p));
if ((&fastbin (av, idx)) != fb)
malloc_printerr ("malloc_consolidate(): invalid chunk size");
}
check_inuse_chunk(av, p);
- nextp = p->fd;
+ nextp = REVEAL_PTR (&p->fd, p->fd, mchunkptr);
/* Slightly streamlined version of consolidation code in free() */
size = chunksize (p);
@@ -4896,8 +4928,12 @@ int_mallinfo (mstate av, struct mallinfo *m)
for (i = 0; i < NFASTBINS; ++i)
{
- for (p = fastbin (av, i); p != 0; p = p->fd)
+ for (p = fastbin (av, i);
+ p != 0;
+ p = REVEAL_PTR (&p->fd, p->fd, mchunkptr))
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("int_mallinfo(): un-aligned fastbin chunk detected");
++nfastblocks;
fastavail += chunksize (p);
}
@@ -5437,8 +5473,10 @@ __malloc_info (int options, FILE *fp)
while (p != NULL)
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("__malloc_info(): un-aligned fastbin chunk detected");
++nthissize;
- p = p->fd;
+ p = REVEAL_PTR (&p->fd, p->fd, mchunkptr);
}
fastavail += nthissize * thissize;
--
2.17.1
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-19 18:15 ` Eyal Itkin
@ 2020-03-20 0:10 ` Wilco Dijkstra
2020-03-20 2:49 ` Carlos O'Donell
2020-03-20 2:53 ` DJ Delorie
1 sibling, 1 reply; 33+ messages in thread
From: Wilco Dijkstra @ 2020-03-20 0:10 UTC (permalink / raw)
To: Eyal Itkin; +Cc: GNU C Library
Hi Eyal,
> I went over the patch and fixed it to conform to the coding standards.
> I'm also added it as an attachment, hoping that this way lines won't
> break during the transmission of the email.
Thanks, it now applied fine. There are still a few long lines over 80 chars:
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("do_check_malloc_state(): un-aligned fastbin chunk detected");
There is a build issue in that PAGE_SHIFT is not defined. I'm not sure whether
this should come from a Linux header, but it only seems to be set by a few
targets with no generic default defined.
> Regarding the benchmarks, I've just ran them on a simple GCP instance
> (1 vCPU) before and after the patch. As you can see below, the change
> isn't measurable in the "malloc-simple" tests. Sometimes the vanilla
> version is faster (as it should be), but sometimes the patched version
> is faster, which usually means that the change is lower than the noise
> level on the testing server.
Yes, ideally you need an unshared machine with turbo turned off if.
I tried it on a Neoverse N1 and the results look pretty much identical.
The perf profile shows it doesn't affect the hottest paths and only adds a
few extra instructions. So from a performance viewpoint it looks good.
Cheers,
Wilco
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-20 0:10 ` Wilco Dijkstra
@ 2020-03-20 2:49 ` Carlos O'Donell
0 siblings, 0 replies; 33+ messages in thread
From: Carlos O'Donell @ 2020-03-20 2:49 UTC (permalink / raw)
To: Wilco Dijkstra, Eyal Itkin; +Cc: GNU C Library
On 3/19/20 8:10 PM, Wilco Dijkstra wrote:
> Hi Eyal,
>
>> I went over the patch and fixed it to conform to the coding standards.
>> I'm also added it as an attachment, hoping that this way lines won't
>> break during the transmission of the email.
>
> Thanks, it now applied fine. There are still a few long lines over 80 chars:
>
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("do_check_malloc_state(): un-aligned fastbin chunk detected");
>
> There is a build issue in that PAGE_SHIFT is not defined. I'm not sure whether
> this should come from a Linux header, but it only seems to be set by a few
> targets with no generic default defined.
>
>> Regarding the benchmarks, I've just ran them on a simple GCP instance
>> (1 vCPU) before and after the patch. As you can see below, the change
>> isn't measurable in the "malloc-simple" tests. Sometimes the vanilla
>> version is faster (as it should be), but sometimes the patched version
>> is faster, which usually means that the change is lower than the noise
>> level on the testing server.
>
> Yes, ideally you need an unshared machine with turbo turned off if.
> I tried it on a Neoverse N1 and the results look pretty much identical.
> The perf profile shows it doesn't affect the hottest paths and only adds a
> few extra instructions. So from a performance viewpoint it looks good.
Thanks, that's good to know, and would have been an upfront blocker to
accepting the patches.
--
Cheers,
Carlos.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-19 18:15 ` Eyal Itkin
2020-03-20 0:10 ` Wilco Dijkstra
@ 2020-03-20 2:53 ` DJ Delorie
2020-03-20 9:35 ` Eyal Itkin
1 sibling, 1 reply; 33+ messages in thread
From: DJ Delorie @ 2020-03-20 2:53 UTC (permalink / raw)
To: Eyal Itkin; +Cc: Wilco.Dijkstra, libc-alpha
Eyal Itkin <eyal.itkin@gmail.com> writes:
> Safe-Linking is a security mechanism that protects single-linked
> lists (such as the fastbin and tcache) from being tampered by attackers.
> The mechanism makes use of randomness from ASLR (mmap_base), and when
> combined with chunk alignment integrity checks, it protects the
> pointers from being hijacked by an attacker.
Based on the patch, it seems that protected pointers are only used in
chunks, not in the heap-global structures (i.e. the fastbins themselves
aren't protected, only the "next" pointer in each chunk). If this is
so, could you add such a note to the comment before PROTECT_PTR ?
> * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
> * *L = PROTECT(P)
I.e. any stored pointer's value is XOR'd with the pointer's address
bits.
> +#define PROTECT_PTR(pos, ptr, type) \
> + ((type)((((size_t)pos) >> PAGE_SHIFT) ^ ((size_t)ptr)))
> +#define REVEAL_PTR(pos, ptr, type) PROTECT_PTR (pos, ptr, type)
Style: whitespace after casts
Bug: PAGE_SHIFT is an obsolete macro these days. Not sure what to use
but I wouldn't be opposed to just putting "12" in there.
Suggestion1: since the "type" can be determined using __typeof, there's
no need to pass it explicitly. I.e.
#define PROTECT_PTR(pos, ptr) \
((__typeof ptr)((((size_t)pos) >> PAGE_SHIFT) ^ ((size_t)ptr)))
Suggestion2: REVEAL_PTR is always called with "&foo,foo" so it can be
further reduced:
#define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)
The rest of the patch looks good to me, but I think the above changes
will make the new code much more readable.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-20 2:53 ` DJ Delorie
@ 2020-03-20 9:35 ` Eyal Itkin
2020-03-20 18:00 ` Adhemerval Zanella
0 siblings, 1 reply; 33+ messages in thread
From: Eyal Itkin @ 2020-03-20 9:35 UTC (permalink / raw)
To: DJ Delorie; +Cc: Wilco Dijkstra, GNU C Library
[-- Attachment #1: Type: text/plain, Size: 2560 bytes --]
Thanks for all of the feedback.
1. I handled lines longer than 80 characters, there shouldn't be any
of those now.
2. Took your suggestion and removed PAGE_SHIFT in favor of 12. It
would have been cleaner if there was a proper POSIX-defined static way
of inferring this size. Anyway, 12 is the most common value, and in
some cases it is 13 or 14 which only means we will lose 1-2 bits of
protection, which isn't that bad.
3. I implemented all of the coding convention suggestions.
4. I clarified the comment to specifically mention that the mechanism
protects the "next" pointers of the single-linked lists of the
Fast-Bin and TCache. Also updated the commit message accordingly.
The patch indeed looks cleaner now (attached), feel free to add more
comments/suggestions if needed.
Thanks again for your help with this patch.
Eyal.
On Fri, Mar 20, 2020 at 4:53 AM DJ Delorie <dj@redhat.com> wrote:
>
> Eyal Itkin <eyal.itkin@gmail.com> writes:
> > Safe-Linking is a security mechanism that protects single-linked
> > lists (such as the fastbin and tcache) from being tampered by attackers.
> > The mechanism makes use of randomness from ASLR (mmap_base), and when
> > combined with chunk alignment integrity checks, it protects the
> > pointers from being hijacked by an attacker.
>
> Based on the patch, it seems that protected pointers are only used in
> chunks, not in the heap-global structures (i.e. the fastbins themselves
> aren't protected, only the "next" pointer in each chunk). If this is
> so, could you add such a note to the comment before PROTECT_PTR ?
>
> > * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
> > * *L = PROTECT(P)
>
> I.e. any stored pointer's value is XOR'd with the pointer's address
> bits.
>
> > +#define PROTECT_PTR(pos, ptr, type) \
> > + ((type)((((size_t)pos) >> PAGE_SHIFT) ^ ((size_t)ptr)))
> > +#define REVEAL_PTR(pos, ptr, type) PROTECT_PTR (pos, ptr, type)
>
> Style: whitespace after casts
>
> Bug: PAGE_SHIFT is an obsolete macro these days. Not sure what to use
> but I wouldn't be opposed to just putting "12" in there.
>
> Suggestion1: since the "type" can be determined using __typeof, there's
> no need to pass it explicitly. I.e.
>
> #define PROTECT_PTR(pos, ptr) \
> ((__typeof ptr)((((size_t)pos) >> PAGE_SHIFT) ^ ((size_t)ptr)))
>
> Suggestion2: REVEAL_PTR is always called with "&foo,foo" so it can be
> further reduced:
>
> #define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)
>
>
> The rest of the patch looks good to me, but I think the above changes
> will make the new code much more readable.
>
[-- Attachment #2: 0001-Add-Safe-Linking-to-fastbins-and-tcache.patch --]
[-- Type: application/octet-stream, Size: 9283 bytes --]
From a691f4c1bf8da83c5150b792b5715bb744d42a56 Mon Sep 17 00:00:00 2001
From: Eyal Itkin <eyalit@checkpoint.com>
Date: Fri, 20 Mar 2020 11:15:25 +0200
Subject: [PATCH] Add Safe-Linking to fastbins and tcache
Safe-Linking is a security mechanism that protects single-linked
lists (such as the fastbin and tcache) from being tampered by attackers.
The mechanism makes use of randomness from ASLR (mmap_base), and when
combined with chunk alignment integrity checks, it protects the "next"
pointers from being hijacked by an attacker.
While Safe-Unlinking protects double-linked lists (such as the small
bins), there wasn't any similar protection for attacks against
single-linked lists. This solution protects against 3 common attacks:
* Partial pointer override: modifies the lower bytes (Little Endian)
* Full pointer override: hijacks the pointer to an attacker's location
* Unaligned chunks: pointing the list to an unaligned address
The design assumes an attacker doesn't know where the heap is located,
and uses the ASLR randomness to "sign" the single-linked pointers. We
mark the pointer as P and the location in which it is stored as L, and
the calculation will be:
* PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
* *L = PROTECT(P)
This way, the random bits from the address L (which start at the bit
in the PAGE_SHIFT position), will be merged with LSB of the stored
protected pointer. This protection layer prevents an attacker from
modifying the pointer into a controlled value.
An additional check that the chunks are MALLOC_ALIGNed adds an
important layer:
* Attackers can't point to illegal (unaligned) memory addresses
* Attackers must guess correctly the alignment bits
On standard 32 bit Linux machines, an attack will directly fail 7
out of 8 times, and on 64 bit machines it will fail 15 out of 16
times.
This proposed patch was benchmarked and it's effect on the overall
performance of the heap was negligible and couldn't be distinguished
from the default variance between tests on the vanilla version. A
similar protection was added to Chromium's version of TCMalloc
in 2012, and according to their documentation it had an overhead of
less than 2%.
---
malloc/malloc.c | 73 ++++++++++++++++++++++++++++++++++++++++---------
1 file changed, 60 insertions(+), 13 deletions(-)
diff --git a/malloc/malloc.c b/malloc/malloc.c
index 7d7d30bb13..39f35f8864 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -327,6 +327,20 @@ __malloc_assert (const char *assertion, const char *file, unsigned int line,
# define MAX_TCACHE_COUNT UINT16_MAX
#endif
+/*
+ Safe-Linking:
+ Use randomness from ASLR (mmap_base) to protect single-linked lists
+ of Fast-Bins and TCache. That is, mask the "next" pointers of the
+ lists' chunks, and also perform allocation alignment checks on them.
+ This mechanism reduces the risk of pointer hijacking, as was done with
+ Safe-Unlinking in the double-linked lists of Small-Bins.
+ Using ASLR_BASE_SHIFT since PAGE_SHIFT is obsolete, and I'm not sure there
+ is a proper static POSIX-defined way of deriving the PAGE_SIZE.
+*/
+#define ASLR_BASE_SHIFT 12
+#define PROTECT_PTR(pos, ptr) \
+ ((__typeof (ptr)) ((((size_t) pos) >> ASLR_BASE_SHIFT) ^ ((size_t) ptr)))
+#define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)
/*
REALLOC_ZERO_BYTES_FREES should be set if a call to
@@ -2157,12 +2171,15 @@ do_check_malloc_state (mstate av)
while (p != 0)
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("do_check_malloc_state(): " \
+ "un-aligned fastbin chunk detected");
/* each chunk claims to be inuse */
do_check_inuse_chunk (av, p);
total += chunksize (p);
/* chunk belongs in this bin */
assert (fastbin_index (chunksize (p)) == i);
- p = p->fd;
+ p = REVEAL_PTR (p->fd);
}
}
@@ -2923,7 +2940,7 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
detect a double free. */
e->key = tcache;
- e->next = tcache->entries[tc_idx];
+ e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
tcache->entries[tc_idx] = e;
++(tcache->counts[tc_idx]);
}
@@ -2934,9 +2951,11 @@ static __always_inline void *
tcache_get (size_t tc_idx)
{
tcache_entry *e = tcache->entries[tc_idx];
- tcache->entries[tc_idx] = e->next;
+ tcache->entries[tc_idx] = REVEAL_PTR (e->next);
--(tcache->counts[tc_idx]);
e->key = NULL;
+ if (__glibc_unlikely (!aligned_OK (e)))
+ malloc_printerr ("malloc(): un-aligned tcache chunk detected");
return (void *) e;
}
@@ -2960,7 +2979,10 @@ tcache_thread_shutdown (void)
while (tcache_tmp->entries[i])
{
tcache_entry *e = tcache_tmp->entries[i];
- tcache_tmp->entries[i] = e->next;
+ if (__glibc_unlikely (!aligned_OK (e)))
+ malloc_printerr ("tcache_thread_shutdown(): " \
+ "un-aligned tcache chunk detected");
+ tcache_tmp->entries[i] = REVEAL_PTR (e->next);
__libc_free (e);
}
}
@@ -3570,8 +3592,11 @@ _int_malloc (mstate av, size_t bytes)
victim = pp; \
if (victim == NULL) \
break; \
+ pp = REVEAL_PTR (victim->fd); \
+ if (__glibc_unlikely (!aligned_OK (pp))) \
+ malloc_printerr ("malloc(): un-aligned fastbin chunk detected"); \
} \
- while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \
+ while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
!= victim); \
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
@@ -3583,8 +3608,11 @@ _int_malloc (mstate av, size_t bytes)
if (victim != NULL)
{
+ if (__glibc_unlikely (!aligned_OK (victim)))
+ malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
+
if (SINGLE_THREAD_P)
- *fb = victim->fd;
+ *fb = REVEAL_PTR (victim->fd);
else
REMOVE_FB (fb, pp, victim);
if (__glibc_likely (victim != NULL))
@@ -3605,8 +3633,10 @@ _int_malloc (mstate av, size_t bytes)
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = *fb) != NULL)
{
+ if (__glibc_unlikely (!aligned_OK (tc_victim)))
+ malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
if (SINGLE_THREAD_P)
- *fb = tc_victim->fd;
+ *fb = REVEAL_PTR (tc_victim->fd);
else
{
REMOVE_FB (fb, pp, tc_victim);
@@ -4196,11 +4226,15 @@ _int_free (mstate av, mchunkptr p, int have_lock)
LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
for (tmp = tcache->entries[tc_idx];
tmp;
- tmp = tmp->next)
+ tmp = REVEAL_PTR (tmp->next))
+ {
+ if (__glibc_unlikely (!aligned_OK (tmp)))
+ malloc_printerr ("free(): un-aligned chunk detected in tcache 2");
if (tmp == e)
malloc_printerr ("free(): double free detected in tcache 2");
/* If we get here, it was a coincidence. We've wasted a
few cycles, but don't abort. */
+ }
}
if (tcache->counts[tc_idx] < mp_.tcache_count)
@@ -4264,7 +4298,7 @@ _int_free (mstate av, mchunkptr p, int have_lock)
add (i.e., double free). */
if (__builtin_expect (old == p, 0))
malloc_printerr ("double free or corruption (fasttop)");
- p->fd = old;
+ p->fd = PROTECT_PTR (&p->fd, old);
*fb = p;
}
else
@@ -4274,7 +4308,8 @@ _int_free (mstate av, mchunkptr p, int have_lock)
add (i.e., double free). */
if (__builtin_expect (old == p, 0))
malloc_printerr ("double free or corruption (fasttop)");
- p->fd = old2 = old;
+ old2 = old;
+ p->fd = PROTECT_PTR (&p->fd, old);
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
!= old2);
@@ -4472,13 +4507,17 @@ static void malloc_consolidate(mstate av)
if (p != 0) {
do {
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("malloc_consolidate(): " \
+ "un-aligned fastbin chunk detected");
+
unsigned int idx = fastbin_index (chunksize (p));
if ((&fastbin (av, idx)) != fb)
malloc_printerr ("malloc_consolidate(): invalid chunk size");
}
check_inuse_chunk(av, p);
- nextp = p->fd;
+ nextp = REVEAL_PTR (p->fd);
/* Slightly streamlined version of consolidation code in free() */
size = chunksize (p);
@@ -4896,8 +4935,13 @@ int_mallinfo (mstate av, struct mallinfo *m)
for (i = 0; i < NFASTBINS; ++i)
{
- for (p = fastbin (av, i); p != 0; p = p->fd)
+ for (p = fastbin (av, i);
+ p != 0;
+ p = REVEAL_PTR (p->fd))
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("int_mallinfo(): " \
+ "un-aligned fastbin chunk detected");
++nfastblocks;
fastavail += chunksize (p);
}
@@ -5437,8 +5481,11 @@ __malloc_info (int options, FILE *fp)
while (p != NULL)
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("__malloc_info(): " \
+ "un-aligned fastbin chunk detected");
++nthissize;
- p = p->fd;
+ p = REVEAL_PTR (p->fd);
}
fastavail += nthissize * thissize;
--
2.17.1
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-20 9:35 ` Eyal Itkin
@ 2020-03-20 18:00 ` Adhemerval Zanella
2020-03-20 19:45 ` Eyal Itkin
0 siblings, 1 reply; 33+ messages in thread
From: Adhemerval Zanella @ 2020-03-20 18:00 UTC (permalink / raw)
To: libc-alpha, eyal.itkin
On 20/03/2020 06:35, Eyal Itkin via Libc-alpha wrote:
> Thanks for all of the feedback.
>
> 1. I handled lines longer than 80 characters, there shouldn't be any
> of those now.
> 2. Took your suggestion and removed PAGE_SHIFT in favor of 12. It
> would have been cleaner if there was a proper POSIX-defined static way
> of inferring this size. Anyway, 12 is the most common value, and in
> some cases it is 13 or 14 which only means we will lose 1-2 bits of
> protection, which isn't that bad.
> 3. I implemented all of the coding convention suggestions.
> 4. I clarified the comment to specifically mention that the mechanism
> protects the "next" pointers of the single-linked lists of the
> Fast-Bin and TCache. Also updated the commit message accordingly.
>
> The patch indeed looks cleaner now (attached), feel free to add more
> comments/suggestions if needed.
>
> Thanks again for your help with this patch.
> Eyal.
Thanks for working on this, I would only ask if you could send next
iteration inline instead of as an attachment (it helps a lot reviewed
with most email readers and it is the default for tools like
git send-email).
> From a691f4c1bf8da83c5150b792b5715bb744d42a56 Mon Sep 17 00:00:00 2001
> From: Eyal Itkin <eyalit@checkpoint.com>
> Date: Fri, 20 Mar 2020 11:15:25 +0200
> Subject: [PATCH] Add Safe-Linking to fastbins and tcache
>
> Safe-Linking is a security mechanism that protects single-linked
> lists (such as the fastbin and tcache) from being tampered by attackers.
> The mechanism makes use of randomness from ASLR (mmap_base), and when
> combined with chunk alignment integrity checks, it protects the "next"
> pointers from being hijacked by an attacker.
>
> While Safe-Unlinking protects double-linked lists (such as the small
> bins), there wasn't any similar protection for attacks against
> single-linked lists. This solution protects against 3 common attacks:
> * Partial pointer override: modifies the lower bytes (Little Endian)
> * Full pointer override: hijacks the pointer to an attacker's location
> * Unaligned chunks: pointing the list to an unaligned address
>
> The design assumes an attacker doesn't know where the heap is located,
> and uses the ASLR randomness to "sign" the single-linked pointers. We
> mark the pointer as P and the location in which it is stored as L, and
> the calculation will be:
> * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
> * *L = PROTECT(P)
>
> This way, the random bits from the address L (which start at the bit
> in the PAGE_SHIFT position), will be merged with LSB of the stored
> protected pointer. This protection layer prevents an attacker from
> modifying the pointer into a controlled value.
>
> An additional check that the chunks are MALLOC_ALIGNed adds an
> important layer:
> * Attackers can't point to illegal (unaligned) memory addresses
> * Attackers must guess correctly the alignment bits
>
> On standard 32 bit Linux machines, an attack will directly fail 7
> out of 8 times, and on 64 bit machines it will fail 15 out of 16
> times.
>
> This proposed patch was benchmarked and it's effect on the overall
> performance of the heap was negligible and couldn't be distinguished
> from the default variance between tests on the vanilla version. A
> similar protection was added to Chromium's version of TCMalloc
> in 2012, and according to their documentation it had an overhead of
> less than 2%.
The idea seems good although I have comments below. It is unfortunate
that for thread workloads, this mitigation is greatly reduced without
the fix of arena entropy (BZ#22853). My idea is to see I can come up
with a testcase for BZ#22853 and submit the patch on comment 5.
[1] https://sourceware.org/bugzilla/show_bug.cgi?id=22853
> ---
> malloc/malloc.c | 73 ++++++++++++++++++++++++++++++++++++++++---------
> 1 file changed, 60 insertions(+), 13 deletions(-)
>
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 7d7d30bb13..39f35f8864 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -327,6 +327,20 @@ __malloc_assert (const char *assertion, const char *file, unsigned int line,
> # define MAX_TCACHE_COUNT UINT16_MAX
> #endif
>
> +/*
> + Safe-Linking:
> + Use randomness from ASLR (mmap_base) to protect single-linked lists
> + of Fast-Bins and TCache. That is, mask the "next" pointers of the
Use double space after a period.
> + lists' chunks, and also perform allocation alignment checks on them.
> + This mechanism reduces the risk of pointer hijacking, as was done with
> + Safe-Unlinking in the double-linked lists of Small-Bins.
> + Using ASLR_BASE_SHIFT since PAGE_SHIFT is obsolete, and I'm not sure there
> + is a proper static POSIX-defined way of deriving the PAGE_SIZE.
> +*/
Some systems (aarch64, powerpc64le, m68k, etc) may have different page
size depending of the kernel configuration, thus providing a PAGE_SHIFT
for such architecture does not make sense. That's why it should not
mention it. I would suggest something like:
It assumes a minimum page size of 4096 KB. System with large pages
provide less entropy, although the pointer mangling still works.
> +#define ASLR_BASE_SHIFT 12
> +#define PROTECT_PTR(pos, ptr) \
> + ((__typeof (ptr)) ((((size_t) pos) >> ASLR_BASE_SHIFT) ^ ((size_t) ptr)))
> +#define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)
I think it would be better if we use proper static inline function
for newer code.
>
> /*
> REALLOC_ZERO_BYTES_FREES should be set if a call to
> @@ -2157,12 +2171,15 @@ do_check_malloc_state (mstate av)
>
> while (p != 0)
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("do_check_malloc_state(): " \
> + "un-aligned fastbin chunk detected");
'un-aligned' seemed wrong, should it be unaligned?
> /* each chunk claims to be inuse */
> do_check_inuse_chunk (av, p);
> total += chunksize (p);
> /* chunk belongs in this bin */
> assert (fastbin_index (chunksize (p)) == i);
> - p = p->fd;
> + p = REVEAL_PTR (p->fd);
> }
> }
>
> @@ -2923,7 +2940,7 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
> detect a double free. */
> e->key = tcache;
>
> - e->next = tcache->entries[tc_idx];
> + e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
> tcache->entries[tc_idx] = e;
> ++(tcache->counts[tc_idx]);
> }> @@ -2934,9 +2951,11 @@ static __always_inline void *
> tcache_get (size_t tc_idx)
> {
> tcache_entry *e = tcache->entries[tc_idx];
> - tcache->entries[tc_idx] = e->next;
> + tcache->entries[tc_idx] = REVEAL_PTR (e->next);
> --(tcache->counts[tc_idx]);
> e->key = NULL;
> + if (__glibc_unlikely (!aligned_OK (e)))
> + malloc_printerr ("malloc(): un-aligned tcache chunk detected");
> return (void *) e;
> }
>
> @@ -2960,7 +2979,10 @@ tcache_thread_shutdown (void)
> while (tcache_tmp->entries[i])
> {
> tcache_entry *e = tcache_tmp->entries[i];
> - tcache_tmp->entries[i] = e->next;
> + if (__glibc_unlikely (!aligned_OK (e)))
> + malloc_printerr ("tcache_thread_shutdown(): " \
> + "un-aligned tcache chunk detected");
> + tcache_tmp->entries[i] = REVEAL_PTR (e->next);
> __libc_free (e);
> }
> }
> @@ -3570,8 +3592,11 @@ _int_malloc (mstate av, size_t bytes)
> victim = pp; \
> if (victim == NULL) \
> break; \
> + pp = REVEAL_PTR (victim->fd); \
> + if (__glibc_unlikely (!aligned_OK (pp))) \
> + malloc_printerr ("malloc(): un-aligned fastbin chunk detected"); \
> } \
> - while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \
> + while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
> != victim); \
>
> if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
> @@ -3583,8 +3608,11 @@ _int_malloc (mstate av, size_t bytes)
>
> if (victim != NULL)
> {
> + if (__glibc_unlikely (!aligned_OK (victim)))
> + malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
> +
> if (SINGLE_THREAD_P)
> - *fb = victim->fd;
> + *fb = REVEAL_PTR (victim->fd);
> else
> REMOVE_FB (fb, pp, victim);
> if (__glibc_likely (victim != NULL))
> @@ -3605,8 +3633,10 @@ _int_malloc (mstate av, size_t bytes)
> while (tcache->counts[tc_idx] < mp_.tcache_count
> && (tc_victim = *fb) != NULL)
> {
> + if (__glibc_unlikely (!aligned_OK (tc_victim)))
> + malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
> if (SINGLE_THREAD_P)
> - *fb = tc_victim->fd;
> + *fb = REVEAL_PTR (tc_victim->fd);
> else
> {
> REMOVE_FB (fb, pp, tc_victim);
> @@ -4196,11 +4226,15 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
> for (tmp = tcache->entries[tc_idx];
> tmp;
> - tmp = tmp->next)
> + tmp = REVEAL_PTR (tmp->next))
> + {
> + if (__glibc_unlikely (!aligned_OK (tmp)))
> + malloc_printerr ("free(): un-aligned chunk detected in tcache 2");
> if (tmp == e)
> malloc_printerr ("free(): double free detected in tcache 2");
> /* If we get here, it was a coincidence. We've wasted a
> few cycles, but don't abort. */
> + }
> }
>
> if (tcache->counts[tc_idx] < mp_.tcache_count)
> @@ -4264,7 +4298,7 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> add (i.e., double free). */
> if (__builtin_expect (old == p, 0))
> malloc_printerr ("double free or corruption (fasttop)");
> - p->fd = old;
> + p->fd = PROTECT_PTR (&p->fd, old);
> *fb = p;
> }
> else
> @@ -4274,7 +4308,8 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> add (i.e., double free). */
> if (__builtin_expect (old == p, 0))
> malloc_printerr ("double free or corruption (fasttop)");
> - p->fd = old2 = old;
> + old2 = old;
> + p->fd = PROTECT_PTR (&p->fd, old);
> }
> while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
> != old2);
> @@ -4472,13 +4507,17 @@ static void malloc_consolidate(mstate av)
> if (p != 0) {
> do {
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("malloc_consolidate(): " \
> + "un-aligned fastbin chunk detected");
> +
> unsigned int idx = fastbin_index (chunksize (p));
> if ((&fastbin (av, idx)) != fb)
> malloc_printerr ("malloc_consolidate(): invalid chunk size");
> }
>
> check_inuse_chunk(av, p);
> - nextp = p->fd;
> + nextp = REVEAL_PTR (p->fd);
>
> /* Slightly streamlined version of consolidation code in free() */
> size = chunksize (p);
> @@ -4896,8 +4935,13 @@ int_mallinfo (mstate av, struct mallinfo *m)
>
> for (i = 0; i < NFASTBINS; ++i)
> {
> - for (p = fastbin (av, i); p != 0; p = p->fd)
> + for (p = fastbin (av, i);
> + p != 0;
> + p = REVEAL_PTR (p->fd))
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("int_mallinfo(): " \
> + "un-aligned fastbin chunk detected");
> ++nfastblocks;
> fastavail += chunksize (p);
> }
> @@ -5437,8 +5481,11 @@ __malloc_info (int options, FILE *fp)
>
> while (p != NULL)
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("__malloc_info(): " \
> + "un-aligned fastbin chunk detected");
> ++nthissize;
> - p = p->fd;
> + p = REVEAL_PTR (p->fd);
> }
>
> fastavail += nthissize * thissize;
> --
> 2.17.1
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-20 18:00 ` Adhemerval Zanella
@ 2020-03-20 19:45 ` Eyal Itkin
2020-03-20 23:58 ` DJ Delorie
` (2 more replies)
0 siblings, 3 replies; 33+ messages in thread
From: Eyal Itkin @ 2020-03-20 19:45 UTC (permalink / raw)
To: Adhemerval Zanella; +Cc: GNU C Library
[-- Attachment #1: Type: text/plain, Size: 14130 bytes --]
I really am sorry to send the patch as an attachment again, however I
had too many difficulties in using git's send-email and convincing him
to send it as a proper reply to this ongoing thread. I wish Gmail's
client won't auto-wrap the lines and break the patch, but sadly they
refuse to implement this feature for over a decade now.
Regarding the previous feedback, I implemented all of the comments,
aside from transforming the macros to static inline functions.
I did try to switch to static functions, but this meant that I had to
change back the signature of REVEAL_PTR to once again receive two
arguments for "pos" and "ptr", as using &ptr could no longer work.
Since this change would have contradicted the previous comment about
the readability of the code, I undid the change and stayed with macros
in sake of readability. Using macros also have the benefit of using
correctly typed objects instead of generic void* types in the api of
the functions.
Thanks again for your help with this.
Eyal.
On Fri, Mar 20, 2020 at 8:00 PM Adhemerval Zanella
<adhemerval.zanella@linaro.org> wrote:
>
>
>
> On 20/03/2020 06:35, Eyal Itkin via Libc-alpha wrote:
> > Thanks for all of the feedback.
> >
> > 1. I handled lines longer than 80 characters, there shouldn't be any
> > of those now.
> > 2. Took your suggestion and removed PAGE_SHIFT in favor of 12. It
> > would have been cleaner if there was a proper POSIX-defined static way
> > of inferring this size. Anyway, 12 is the most common value, and in
> > some cases it is 13 or 14 which only means we will lose 1-2 bits of
> > protection, which isn't that bad.
> > 3. I implemented all of the coding convention suggestions.
> > 4. I clarified the comment to specifically mention that the mechanism
> > protects the "next" pointers of the single-linked lists of the
> > Fast-Bin and TCache. Also updated the commit message accordingly.
> >
> > The patch indeed looks cleaner now (attached), feel free to add more
> > comments/suggestions if needed.
> >
> > Thanks again for your help with this patch.
> > Eyal.
>
> Thanks for working on this, I would only ask if you could send next
> iteration inline instead of as an attachment (it helps a lot reviewed
> with most email readers and it is the default for tools like
> git send-email).
>
> > From a691f4c1bf8da83c5150b792b5715bb744d42a56 Mon Sep 17 00:00:00 2001
> > From: Eyal Itkin <eyalit@checkpoint.com>
> > Date: Fri, 20 Mar 2020 11:15:25 +0200
> > Subject: [PATCH] Add Safe-Linking to fastbins and tcache
> >
> > Safe-Linking is a security mechanism that protects single-linked
> > lists (such as the fastbin and tcache) from being tampered by attackers.
> > The mechanism makes use of randomness from ASLR (mmap_base), and when
> > combined with chunk alignment integrity checks, it protects the "next"
> > pointers from being hijacked by an attacker.
> >
> > While Safe-Unlinking protects double-linked lists (such as the small
> > bins), there wasn't any similar protection for attacks against
> > single-linked lists. This solution protects against 3 common attacks:
> > * Partial pointer override: modifies the lower bytes (Little Endian)
> > * Full pointer override: hijacks the pointer to an attacker's location
> > * Unaligned chunks: pointing the list to an unaligned address
> >
> > The design assumes an attacker doesn't know where the heap is located,
> > and uses the ASLR randomness to "sign" the single-linked pointers. We
> > mark the pointer as P and the location in which it is stored as L, and
> > the calculation will be:
> > * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
> > * *L = PROTECT(P)
> >
> > This way, the random bits from the address L (which start at the bit
> > in the PAGE_SHIFT position), will be merged with LSB of the stored
> > protected pointer. This protection layer prevents an attacker from
> > modifying the pointer into a controlled value.
> >
> > An additional check that the chunks are MALLOC_ALIGNed adds an
> > important layer:
> > * Attackers can't point to illegal (unaligned) memory addresses
> > * Attackers must guess correctly the alignment bits
> >
> > On standard 32 bit Linux machines, an attack will directly fail 7
> > out of 8 times, and on 64 bit machines it will fail 15 out of 16
> > times.
> >
> > This proposed patch was benchmarked and it's effect on the overall
> > performance of the heap was negligible and couldn't be distinguished
> > from the default variance between tests on the vanilla version. A
> > similar protection was added to Chromium's version of TCMalloc
> > in 2012, and according to their documentation it had an overhead of
> > less than 2%.
>
> The idea seems good although I have comments below. It is unfortunate
> that for thread workloads, this mitigation is greatly reduced without
> the fix of arena entropy (BZ#22853). My idea is to see I can come up
> with a testcase for BZ#22853 and submit the patch on comment 5.
>
> [1] https://sourceware.org/bugzilla/show_bug.cgi?id=22853
>
> > ---
> > malloc/malloc.c | 73 ++++++++++++++++++++++++++++++++++++++++---------
> > 1 file changed, 60 insertions(+), 13 deletions(-)
> >
> > diff --git a/malloc/malloc.c b/malloc/malloc.c
> > index 7d7d30bb13..39f35f8864 100644
> > --- a/malloc/malloc.c
> > +++ b/malloc/malloc.c
> > @@ -327,6 +327,20 @@ __malloc_assert (const char *assertion, const char *file, unsigned int line,
> > # define MAX_TCACHE_COUNT UINT16_MAX
> > #endif
> >
> > +/*
> > + Safe-Linking:
> > + Use randomness from ASLR (mmap_base) to protect single-linked lists
> > + of Fast-Bins and TCache. That is, mask the "next" pointers of the
>
> Use double space after a period.
>
> > + lists' chunks, and also perform allocation alignment checks on them.
> > + This mechanism reduces the risk of pointer hijacking, as was done with
> > + Safe-Unlinking in the double-linked lists of Small-Bins.
> > + Using ASLR_BASE_SHIFT since PAGE_SHIFT is obsolete, and I'm not sure there
> > + is a proper static POSIX-defined way of deriving the PAGE_SIZE.
> > +*/
>
> Some systems (aarch64, powerpc64le, m68k, etc) may have different page
> size depending of the kernel configuration, thus providing a PAGE_SHIFT
> for such architecture does not make sense. That's why it should not
> mention it. I would suggest something like:
>
> It assumes a minimum page size of 4096 KB. System with large pages
> provide less entropy, although the pointer mangling still works.
>
> > +#define ASLR_BASE_SHIFT 12
> > +#define PROTECT_PTR(pos, ptr) \
> > + ((__typeof (ptr)) ((((size_t) pos) >> ASLR_BASE_SHIFT) ^ ((size_t) ptr)))
> > +#define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)
>
> I think it would be better if we use proper static inline function
> for newer code.
>
> >
> > /*
> > REALLOC_ZERO_BYTES_FREES should be set if a call to
> > @@ -2157,12 +2171,15 @@ do_check_malloc_state (mstate av)
> >
> > while (p != 0)
> > {
> > + if (__glibc_unlikely (!aligned_OK (p)))
> > + malloc_printerr ("do_check_malloc_state(): " \
> > + "un-aligned fastbin chunk detected");
>
> 'un-aligned' seemed wrong, should it be unaligned?
>
> > /* each chunk claims to be inuse */
> > do_check_inuse_chunk (av, p);
> > total += chunksize (p);
> > /* chunk belongs in this bin */
> > assert (fastbin_index (chunksize (p)) == i);
> > - p = p->fd;
> > + p = REVEAL_PTR (p->fd);
> > }
> > }
> >
> > @@ -2923,7 +2940,7 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
> > detect a double free. */
> > e->key = tcache;
> >
> > - e->next = tcache->entries[tc_idx];
> > + e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
> > tcache->entries[tc_idx] = e;
> > ++(tcache->counts[tc_idx]);
> > }> @@ -2934,9 +2951,11 @@ static __always_inline void *
> > tcache_get (size_t tc_idx)
> > {
> > tcache_entry *e = tcache->entries[tc_idx];
> > - tcache->entries[tc_idx] = e->next;
> > + tcache->entries[tc_idx] = REVEAL_PTR (e->next);
> > --(tcache->counts[tc_idx]);
> > e->key = NULL;
> > + if (__glibc_unlikely (!aligned_OK (e)))
> > + malloc_printerr ("malloc(): un-aligned tcache chunk detected");
> > return (void *) e;
> > }
> >
> > @@ -2960,7 +2979,10 @@ tcache_thread_shutdown (void)
> > while (tcache_tmp->entries[i])
> > {
> > tcache_entry *e = tcache_tmp->entries[i];
> > - tcache_tmp->entries[i] = e->next;
> > + if (__glibc_unlikely (!aligned_OK (e)))
> > + malloc_printerr ("tcache_thread_shutdown(): " \
> > + "un-aligned tcache chunk detected");
> > + tcache_tmp->entries[i] = REVEAL_PTR (e->next);
> > __libc_free (e);
> > }
> > }
> > @@ -3570,8 +3592,11 @@ _int_malloc (mstate av, size_t bytes)
> > victim = pp; \
> > if (victim == NULL) \
> > break; \
> > + pp = REVEAL_PTR (victim->fd); \
> > + if (__glibc_unlikely (!aligned_OK (pp))) \
> > + malloc_printerr ("malloc(): un-aligned fastbin chunk detected"); \
> > } \
> > - while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \
> > + while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
> > != victim); \
> >
> > if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
> > @@ -3583,8 +3608,11 @@ _int_malloc (mstate av, size_t bytes)
> >
> > if (victim != NULL)
> > {
> > + if (__glibc_unlikely (!aligned_OK (victim)))
> > + malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
> > +
> > if (SINGLE_THREAD_P)
> > - *fb = victim->fd;
> > + *fb = REVEAL_PTR (victim->fd);
> > else
> > REMOVE_FB (fb, pp, victim);
> > if (__glibc_likely (victim != NULL))
> > @@ -3605,8 +3633,10 @@ _int_malloc (mstate av, size_t bytes)
> > while (tcache->counts[tc_idx] < mp_.tcache_count
> > && (tc_victim = *fb) != NULL)
> > {
> > + if (__glibc_unlikely (!aligned_OK (tc_victim)))
> > + malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
> > if (SINGLE_THREAD_P)
> > - *fb = tc_victim->fd;
> > + *fb = REVEAL_PTR (tc_victim->fd);
> > else
> > {
> > REMOVE_FB (fb, pp, tc_victim);
> > @@ -4196,11 +4226,15 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> > LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
> > for (tmp = tcache->entries[tc_idx];
> > tmp;
> > - tmp = tmp->next)
> > + tmp = REVEAL_PTR (tmp->next))
> > + {
> > + if (__glibc_unlikely (!aligned_OK (tmp)))
> > + malloc_printerr ("free(): un-aligned chunk detected in tcache 2");
> > if (tmp == e)
> > malloc_printerr ("free(): double free detected in tcache 2");
> > /* If we get here, it was a coincidence. We've wasted a
> > few cycles, but don't abort. */
> > + }
> > }
> >
> > if (tcache->counts[tc_idx] < mp_.tcache_count)
> > @@ -4264,7 +4298,7 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> > add (i.e., double free). */
> > if (__builtin_expect (old == p, 0))
> > malloc_printerr ("double free or corruption (fasttop)");
> > - p->fd = old;
> > + p->fd = PROTECT_PTR (&p->fd, old);
> > *fb = p;
> > }
> > else
> > @@ -4274,7 +4308,8 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> > add (i.e., double free). */
> > if (__builtin_expect (old == p, 0))
> > malloc_printerr ("double free or corruption (fasttop)");
> > - p->fd = old2 = old;
> > + old2 = old;
> > + p->fd = PROTECT_PTR (&p->fd, old);
> > }
> > while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
> > != old2);
> > @@ -4472,13 +4507,17 @@ static void malloc_consolidate(mstate av)
> > if (p != 0) {
> > do {
> > {
> > + if (__glibc_unlikely (!aligned_OK (p)))
> > + malloc_printerr ("malloc_consolidate(): " \
> > + "un-aligned fastbin chunk detected");
> > +
> > unsigned int idx = fastbin_index (chunksize (p));
> > if ((&fastbin (av, idx)) != fb)
> > malloc_printerr ("malloc_consolidate(): invalid chunk size");
> > }
> >
> > check_inuse_chunk(av, p);
> > - nextp = p->fd;
> > + nextp = REVEAL_PTR (p->fd);
> >
> > /* Slightly streamlined version of consolidation code in free() */
> > size = chunksize (p);
> > @@ -4896,8 +4935,13 @@ int_mallinfo (mstate av, struct mallinfo *m)
> >
> > for (i = 0; i < NFASTBINS; ++i)
> > {
> > - for (p = fastbin (av, i); p != 0; p = p->fd)
> > + for (p = fastbin (av, i);
> > + p != 0;
> > + p = REVEAL_PTR (p->fd))
> > {
> > + if (__glibc_unlikely (!aligned_OK (p)))
> > + malloc_printerr ("int_mallinfo(): " \
> > + "un-aligned fastbin chunk detected");
> > ++nfastblocks;
> > fastavail += chunksize (p);
> > }
> > @@ -5437,8 +5481,11 @@ __malloc_info (int options, FILE *fp)
> >
> > while (p != NULL)
> > {
> > + if (__glibc_unlikely (!aligned_OK (p)))
> > + malloc_printerr ("__malloc_info(): " \
> > + "un-aligned fastbin chunk detected");
> > ++nthissize;
> > - p = p->fd;
> > + p = REVEAL_PTR (p->fd);
> > }
> >
> > fastavail += nthissize * thissize;
> > --
> > 2.17.1
[-- Attachment #2: 0001-Add-Safe-Linking-to-fastbins-and-tcache.patch --]
[-- Type: application/octet-stream, Size: 9242 bytes --]
From 73210d07ae44920b6645cf05f821069a4bfcda00 Mon Sep 17 00:00:00 2001
From: Eyal Itkin <eyalit@checkpoint.com>
Date: Fri, 20 Mar 2020 21:19:17 +0200
Subject: [PATCH] Add Safe-Linking to fastbins and tcache
Safe-Linking is a security mechanism that protects single-linked
lists (such as the fastbin and tcache) from being tampered by attackers.
The mechanism makes use of randomness from ASLR (mmap_base), and when
combined with chunk alignment integrity checks, it protects the "next"
pointers from being hijacked by an attacker.
While Safe-Unlinking protects double-linked lists (such as the small
bins), there wasn't any similar protection for attacks against
single-linked lists. This solution protects against 3 common attacks:
* Partial pointer override: modifies the lower bytes (Little Endian)
* Full pointer override: hijacks the pointer to an attacker's location
* Unaligned chunks: pointing the list to an unaligned address
The design assumes an attacker doesn't know where the heap is located,
and uses the ASLR randomness to "sign" the single-linked pointers. We
mark the pointer as P and the location in which it is stored as L, and
the calculation will be:
* PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
* *L = PROTECT(P)
This way, the random bits from the address L (which start at the bit
in the PAGE_SHIFT position), will be merged with LSB of the stored
protected pointer. This protection layer prevents an attacker from
modifying the pointer into a controlled value.
An additional check that the chunks are MALLOC_ALIGNed adds an
important layer:
* Attackers can't point to illegal (unaligned) memory addresses
* Attackers must guess correctly the alignment bits
On standard 32 bit Linux machines, an attack will directly fail 7
out of 8 times, and on 64 bit machines it will fail 15 out of 16
times.
This proposed patch was benchmarked and it's effect on the overall
performance of the heap was negligible and couldn't be distinguished
from the default variance between tests on the vanilla version. A
similar protection was added to Chromium's version of TCMalloc
in 2012, and according to their documentation it had an overhead of
less than 2%.
---
malloc/malloc.c | 73 ++++++++++++++++++++++++++++++++++++++++---------
1 file changed, 60 insertions(+), 13 deletions(-)
diff --git a/malloc/malloc.c b/malloc/malloc.c
index 7d7d30bb13..2e25a85029 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -327,6 +327,20 @@ __malloc_assert (const char *assertion, const char *file, unsigned int line,
# define MAX_TCACHE_COUNT UINT16_MAX
#endif
+/*
+ Safe-Linking:
+ Use randomness from ASLR (mmap_base) to protect single-linked lists
+ of Fast-Bins and TCache. That is, mask the "next" pointers of the
+ lists' chunks, and also perform allocation alignment checks on them.
+ This mechanism reduces the risk of pointer hijacking, as was done with
+ Safe-Unlinking in the double-linked lists of Small-Bins.
+ It assumes a minimum page size of 4096 bytes (12 bits). Systems with
+ larger pages provide less entropy, although the pointer mangling
+ still works.
+*/
+#define PROTECT_PTR(pos, ptr) \
+ ((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))
+#define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)
/*
REALLOC_ZERO_BYTES_FREES should be set if a call to
@@ -2157,12 +2171,15 @@ do_check_malloc_state (mstate av)
while (p != 0)
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("do_check_malloc_state(): " \
+ "unaligned fastbin chunk detected");
/* each chunk claims to be inuse */
do_check_inuse_chunk (av, p);
total += chunksize (p);
/* chunk belongs in this bin */
assert (fastbin_index (chunksize (p)) == i);
- p = p->fd;
+ p = REVEAL_PTR (p->fd);
}
}
@@ -2923,7 +2940,7 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
detect a double free. */
e->key = tcache;
- e->next = tcache->entries[tc_idx];
+ e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
tcache->entries[tc_idx] = e;
++(tcache->counts[tc_idx]);
}
@@ -2934,9 +2951,11 @@ static __always_inline void *
tcache_get (size_t tc_idx)
{
tcache_entry *e = tcache->entries[tc_idx];
- tcache->entries[tc_idx] = e->next;
+ tcache->entries[tc_idx] = REVEAL_PTR (e->next);
--(tcache->counts[tc_idx]);
e->key = NULL;
+ if (__glibc_unlikely (!aligned_OK (e)))
+ malloc_printerr ("malloc(): unaligned tcache chunk detected");
return (void *) e;
}
@@ -2960,7 +2979,10 @@ tcache_thread_shutdown (void)
while (tcache_tmp->entries[i])
{
tcache_entry *e = tcache_tmp->entries[i];
- tcache_tmp->entries[i] = e->next;
+ if (__glibc_unlikely (!aligned_OK (e)))
+ malloc_printerr ("tcache_thread_shutdown(): " \
+ "unaligned tcache chunk detected");
+ tcache_tmp->entries[i] = REVEAL_PTR (e->next);
__libc_free (e);
}
}
@@ -3570,8 +3592,11 @@ _int_malloc (mstate av, size_t bytes)
victim = pp; \
if (victim == NULL) \
break; \
+ pp = REVEAL_PTR (victim->fd); \
+ if (__glibc_unlikely (!aligned_OK (pp))) \
+ malloc_printerr ("malloc(): unaligned fastbin chunk detected"); \
} \
- while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \
+ while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
!= victim); \
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
@@ -3583,8 +3608,11 @@ _int_malloc (mstate av, size_t bytes)
if (victim != NULL)
{
+ if (__glibc_unlikely (!aligned_OK (victim)))
+ malloc_printerr ("malloc(): unaligned fastbin chunk detected");
+
if (SINGLE_THREAD_P)
- *fb = victim->fd;
+ *fb = REVEAL_PTR (victim->fd);
else
REMOVE_FB (fb, pp, victim);
if (__glibc_likely (victim != NULL))
@@ -3605,8 +3633,10 @@ _int_malloc (mstate av, size_t bytes)
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = *fb) != NULL)
{
+ if (__glibc_unlikely (!aligned_OK (tc_victim)))
+ malloc_printerr ("malloc(): unaligned fastbin chunk detected");
if (SINGLE_THREAD_P)
- *fb = tc_victim->fd;
+ *fb = REVEAL_PTR (tc_victim->fd);
else
{
REMOVE_FB (fb, pp, tc_victim);
@@ -4196,11 +4226,15 @@ _int_free (mstate av, mchunkptr p, int have_lock)
LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
for (tmp = tcache->entries[tc_idx];
tmp;
- tmp = tmp->next)
+ tmp = REVEAL_PTR (tmp->next))
+ {
+ if (__glibc_unlikely (!aligned_OK (tmp)))
+ malloc_printerr ("free(): unaligned chunk detected in tcache 2");
if (tmp == e)
malloc_printerr ("free(): double free detected in tcache 2");
/* If we get here, it was a coincidence. We've wasted a
few cycles, but don't abort. */
+ }
}
if (tcache->counts[tc_idx] < mp_.tcache_count)
@@ -4264,7 +4298,7 @@ _int_free (mstate av, mchunkptr p, int have_lock)
add (i.e., double free). */
if (__builtin_expect (old == p, 0))
malloc_printerr ("double free or corruption (fasttop)");
- p->fd = old;
+ p->fd = PROTECT_PTR (&p->fd, old);
*fb = p;
}
else
@@ -4274,7 +4308,8 @@ _int_free (mstate av, mchunkptr p, int have_lock)
add (i.e., double free). */
if (__builtin_expect (old == p, 0))
malloc_printerr ("double free or corruption (fasttop)");
- p->fd = old2 = old;
+ old2 = old;
+ p->fd = PROTECT_PTR (&p->fd, old);
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
!= old2);
@@ -4472,13 +4507,17 @@ static void malloc_consolidate(mstate av)
if (p != 0) {
do {
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("malloc_consolidate(): " \
+ "unaligned fastbin chunk detected");
+
unsigned int idx = fastbin_index (chunksize (p));
if ((&fastbin (av, idx)) != fb)
malloc_printerr ("malloc_consolidate(): invalid chunk size");
}
check_inuse_chunk(av, p);
- nextp = p->fd;
+ nextp = REVEAL_PTR (p->fd);
/* Slightly streamlined version of consolidation code in free() */
size = chunksize (p);
@@ -4896,8 +4935,13 @@ int_mallinfo (mstate av, struct mallinfo *m)
for (i = 0; i < NFASTBINS; ++i)
{
- for (p = fastbin (av, i); p != 0; p = p->fd)
+ for (p = fastbin (av, i);
+ p != 0;
+ p = REVEAL_PTR (p->fd))
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("int_mallinfo(): " \
+ "unaligned fastbin chunk detected");
++nfastblocks;
fastavail += chunksize (p);
}
@@ -5437,8 +5481,11 @@ __malloc_info (int options, FILE *fp)
while (p != NULL)
{
+ if (__glibc_unlikely (!aligned_OK (p)))
+ malloc_printerr ("__malloc_info(): " \
+ "unaligned fastbin chunk detected");
++nthissize;
- p = p->fd;
+ p = REVEAL_PTR (p->fd);
}
fastavail += nthissize * thissize;
--
2.17.1
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-20 19:45 ` Eyal Itkin
@ 2020-03-20 23:58 ` DJ Delorie
2020-03-21 2:47 ` Carlos O'Donell
2020-03-30 8:01 ` Andreas Schwab
2 siblings, 0 replies; 33+ messages in thread
From: DJ Delorie @ 2020-03-20 23:58 UTC (permalink / raw)
To: Eyal Itkin; +Cc: adhemerval.zanella, libc-alpha
This last patch looks good to me. Any further comments from anyone else?
Reviewed-by: DJ Delorie <dj@redhat.com>
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-20 19:45 ` Eyal Itkin
2020-03-20 23:58 ` DJ Delorie
@ 2020-03-21 2:47 ` Carlos O'Donell
2020-03-23 13:52 ` Adhemerval Zanella
2020-03-29 17:04 ` Carlos O'Donell
2020-03-30 8:01 ` Andreas Schwab
2 siblings, 2 replies; 33+ messages in thread
From: Carlos O'Donell @ 2020-03-21 2:47 UTC (permalink / raw)
To: Eyal Itkin, Adhemerval Zanella, DJ Delorie, Wilco Dijkstra,
Florian Weimer
Cc: GNU C Library
On 3/20/20 3:45 PM, Eyal Itkin via Libc-alpha wrote:
> I really am sorry to send the patch as an attachment again, however I
> had too many difficulties in using git's send-email and convincing him
> to send it as a proper reply to this ongoing thread. I wish Gmail's
> client won't auto-wrap the lines and break the patch, but sadly they
> refuse to implement this feature for over a decade now.
>
> Regarding the previous feedback, I implemented all of the comments,
> aside from transforming the macros to static inline functions.
>
> I did try to switch to static functions, but this meant that I had to
> change back the signature of REVEAL_PTR to once again receive two
> arguments for "pos" and "ptr", as using &ptr could no longer work.
> Since this change would have contradicted the previous comment about
> the readability of the code, I undid the change and stayed with macros
> in sake of readability. Using macros also have the benefit of using
> correctly typed objects instead of generic void* types in the api of
> the functions.
Sometimes you will get conflicting advice from reviewers. We are not
a homogeneous set of individuals ;-)
I like that we might extend Safe-Linking to all lists, including the
exit_function_list which is a prime target of attack since it has
a singly linked list and could be written to in order to execute
arbitrary function pointers (requires also the probability of guessing
PTR_MANGLE results). Unlike malloc, in other less performance
sensitive functions we can use bits of randomness from a global
variable.
Reviews so far:
- Wilco Dijkstra (Arm)
- DJ Delorie (Red Hat)
- Adhemerval Zanella (Linaro)
- Carlos O'Donell (Red Hat)
If Adhemerval, DJ, and Wilco want to give their Reviewed-by, then I'll
add those too.
I see one remaining issue to discuss and it is the emacs dumped heap
state. The rest looks good to me too.
I'm TO'ing Florian here in case he wants to comment. A few years ago
(time flies! 2016!) Florian had an idea to protect the chunk metadata
with xor and some randomness (size and prevsize):
https://sourceware.org/legacy-ml/libc-alpha/2016-10/msg00531.html
So the emacs dumped heap issue is that emacs would previously use
malloc_get_state to dump the heap, and the restore it again with
malloc_set_State. This was a serious impediment to improving the
malloc implementation and so we stopped supporting malloc_get_state,
but there are still emacs binaries that use malloc_set_state to
restore a dumped heap.
The way we restore a dumped heap means we need to be careful we
don't restore anything that we might expect should have been been
protected with Safe-Linking.
I have reviewed the code in hooks.c, particularly malloc_set_state
and we iterate via chunk sizes so nothing is looking at the forward
pointer, and even better we make them all into fake mmap'd chunks
and never free them. Therefore I think we should be fine with the
dumped emacs state.
If nobody objects I'll push this next week after giving people some
more time to review.
Lastly, do you think it's possible to write a test case that
exercise the failure for tcache and fastbins? You can see in
malloc/tst-dynarray-at-fail.c an example where the test runs in
a subprocess and it's stderr is compared to see if it triggers
the expected failure. It would be good to know the code we expect
to protect the chunk is functioning correctly.
The test case an be reviewed as a distinct commit if we want to
keep things moving.
Reviewed-by: Carlos O'Donell <carlos@redhat.com>
> From 73210d07ae44920b6645cf05f821069a4bfcda00 Mon Sep 17 00:00:00 2001
> From: Eyal Itkin <eyalit@checkpoint.com>
> Date: Fri, 20 Mar 2020 21:19:17 +0200
> Subject: [PATCH] Add Safe-Linking to fastbins and tcache
>
> Safe-Linking is a security mechanism that protects single-linked
> lists (such as the fastbin and tcache) from being tampered by attackers.
> The mechanism makes use of randomness from ASLR (mmap_base), and when
> combined with chunk alignment integrity checks, it protects the "next"
> pointers from being hijacked by an attacker.
>
> While Safe-Unlinking protects double-linked lists (such as the small
> bins), there wasn't any similar protection for attacks against
> single-linked lists. This solution protects against 3 common attacks:
> * Partial pointer override: modifies the lower bytes (Little Endian)
> * Full pointer override: hijacks the pointer to an attacker's location
> * Unaligned chunks: pointing the list to an unaligned address
>
> The design assumes an attacker doesn't know where the heap is located,
> and uses the ASLR randomness to "sign" the single-linked pointers. We
> mark the pointer as P and the location in which it is stored as L, and
> the calculation will be:
> * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
> * *L = PROTECT(P)
>
> This way, the random bits from the address L (which start at the bit
> in the PAGE_SHIFT position), will be merged with LSB of the stored
> protected pointer. This protection layer prevents an attacker from
> modifying the pointer into a controlled value.
>
> An additional check that the chunks are MALLOC_ALIGNed adds an
> important layer:
> * Attackers can't point to illegal (unaligned) memory addresses
> * Attackers must guess correctly the alignment bits
>
> On standard 32 bit Linux machines, an attack will directly fail 7
> out of 8 times, and on 64 bit machines it will fail 15 out of 16
> times.
>
> This proposed patch was benchmarked and it's effect on the overall
> performance of the heap was negligible and couldn't be distinguished
> from the default variance between tests on the vanilla version. A
> similar protection was added to Chromium's version of TCMalloc
> in 2012, and according to their documentation it had an overhead of
> less than 2%.
> ---
> malloc/malloc.c | 73 ++++++++++++++++++++++++++++++++++++++++---------
> 1 file changed, 60 insertions(+), 13 deletions(-)
>
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 7d7d30bb13..2e25a85029 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -327,6 +327,20 @@ __malloc_assert (const char *assertion, const char *file, unsigned int line,
> # define MAX_TCACHE_COUNT UINT16_MAX
> #endif
>
> +/*
> + Safe-Linking:
> + Use randomness from ASLR (mmap_base) to protect single-linked lists
> + of Fast-Bins and TCache. That is, mask the "next" pointers of the
> + lists' chunks, and also perform allocation alignment checks on them.
> + This mechanism reduces the risk of pointer hijacking, as was done with
> + Safe-Unlinking in the double-linked lists of Small-Bins.
> + It assumes a minimum page size of 4096 bytes (12 bits). Systems with
OK. Comment explains the magic number 12 below.
> + larger pages provide less entropy, although the pointer mangling
> + still works.
> +*/
This should be:
/* Safe-Linking:
... */
To follow comment style for the project (not the style of malloc's older code).
I've fixed this up.
I also fixed up some tab vs. spaces.
> +#define PROTECT_PTR(pos, ptr) \
> + ((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))
> +#define REVEAL_PTR(ptr) PROTECT_PTR (&ptr, ptr)
>
> /*
> REALLOC_ZERO_BYTES_FREES should be set if a call to
> @@ -2157,12 +2171,15 @@ do_check_malloc_state (mstate av)
>
> while (p != 0)
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("do_check_malloc_state(): " \
> + "unaligned fastbin chunk detected");
OK.
> /* each chunk claims to be inuse */
> do_check_inuse_chunk (av, p);
> total += chunksize (p);
> /* chunk belongs in this bin */
> assert (fastbin_index (chunksize (p)) == i);
> - p = p->fd;
> + p = REVEAL_PTR (p->fd);
OK.
> }
> }
>
> @@ -2923,7 +2940,7 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
> detect a double free. */
> e->key = tcache;
>
> - e->next = tcache->entries[tc_idx];
> + e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
OK.
> tcache->entries[tc_idx] = e;
> ++(tcache->counts[tc_idx]);
> }
> @@ -2934,9 +2951,11 @@ static __always_inline void *
> tcache_get (size_t tc_idx)
> {
> tcache_entry *e = tcache->entries[tc_idx];
> - tcache->entries[tc_idx] = e->next;
> + tcache->entries[tc_idx] = REVEAL_PTR (e->next);
> --(tcache->counts[tc_idx]);
> e->key = NULL;
> + if (__glibc_unlikely (!aligned_OK (e)))
> + malloc_printerr ("malloc(): unaligned tcache chunk detected");
OK.
> return (void *) e;
> }
>
> @@ -2960,7 +2979,10 @@ tcache_thread_shutdown (void)
> while (tcache_tmp->entries[i])
> {
> tcache_entry *e = tcache_tmp->entries[i];
> - tcache_tmp->entries[i] = e->next;
> + if (__glibc_unlikely (!aligned_OK (e)))
> + malloc_printerr ("tcache_thread_shutdown(): " \
> + "unaligned tcache chunk detected");
> + tcache_tmp->entries[i] = REVEAL_PTR (e->next);
OK.
> __libc_free (e);
> }
> }
> @@ -3570,8 +3592,11 @@ _int_malloc (mstate av, size_t bytes)
> victim = pp; \
> if (victim == NULL) \
> break; \
> + pp = REVEAL_PTR (victim->fd); \
> + if (__glibc_unlikely (!aligned_OK (pp))) \
> + malloc_printerr ("malloc(): unaligned fastbin chunk detected"); \
OK.
> } \
> - while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \
> + while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
OK.
> != victim); \
>
> if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
> @@ -3583,8 +3608,11 @@ _int_malloc (mstate av, size_t bytes)
>
> if (victim != NULL)
> {
> + if (__glibc_unlikely (!aligned_OK (victim)))
> + malloc_printerr ("malloc(): unaligned fastbin chunk detected");
> +
> if (SINGLE_THREAD_P)
> - *fb = victim->fd;
> + *fb = REVEAL_PTR (victim->fd);
OK.
> else
> REMOVE_FB (fb, pp, victim);
> if (__glibc_likely (victim != NULL))
> @@ -3605,8 +3633,10 @@ _int_malloc (mstate av, size_t bytes)
> while (tcache->counts[tc_idx] < mp_.tcache_count
> && (tc_victim = *fb) != NULL)
> {
> + if (__glibc_unlikely (!aligned_OK (tc_victim)))
> + malloc_printerr ("malloc(): unaligned fastbin chunk detected");
> if (SINGLE_THREAD_P)
> - *fb = tc_victim->fd;
> + *fb = REVEAL_PTR (tc_victim->fd);
OK.
> else
> {
> REMOVE_FB (fb, pp, tc_victim);
> @@ -4196,11 +4226,15 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
> for (tmp = tcache->entries[tc_idx];
> tmp;
> - tmp = tmp->next)
> + tmp = REVEAL_PTR (tmp->next))
> + {
> + if (__glibc_unlikely (!aligned_OK (tmp)))
> + malloc_printerr ("free(): unaligned chunk detected in tcache 2");
OK.
> if (tmp == e)
> malloc_printerr ("free(): double free detected in tcache 2");
> /* If we get here, it was a coincidence. We've wasted a
> few cycles, but don't abort. */
> + }
OK.
> }
>
> if (tcache->counts[tc_idx] < mp_.tcache_count)
> @@ -4264,7 +4298,7 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> add (i.e., double free). */
> if (__builtin_expect (old == p, 0))
> malloc_printerr ("double free or corruption (fasttop)");
> - p->fd = old;
> + p->fd = PROTECT_PTR (&p->fd, old);
OK.
> *fb = p;
> }
> else
> @@ -4274,7 +4308,8 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> add (i.e., double free). */
> if (__builtin_expect (old == p, 0))
> malloc_printerr ("double free or corruption (fasttop)");
> - p->fd = old2 = old;
> + old2 = old;
> + p->fd = PROTECT_PTR (&p->fd, old);
OK.
> }
> while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
> != old2);
> @@ -4472,13 +4507,17 @@ static void malloc_consolidate(mstate av)
> if (p != 0) {
> do {
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("malloc_consolidate(): " \
> + "unaligned fastbin chunk detected");
OK.
> +
> unsigned int idx = fastbin_index (chunksize (p));
> if ((&fastbin (av, idx)) != fb)
> malloc_printerr ("malloc_consolidate(): invalid chunk size");
> }
>
> check_inuse_chunk(av, p);
> - nextp = p->fd;
> + nextp = REVEAL_PTR (p->fd);
OK.
>
> /* Slightly streamlined version of consolidation code in free() */
> size = chunksize (p);
> @@ -4896,8 +4935,13 @@ int_mallinfo (mstate av, struct mallinfo *m)
>
> for (i = 0; i < NFASTBINS; ++i)
> {
> - for (p = fastbin (av, i); p != 0; p = p->fd)
> + for (p = fastbin (av, i);
> + p != 0;
> + p = REVEAL_PTR (p->fd))
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("int_mallinfo(): " \
> + "unaligned fastbin chunk detected");
OK.
> ++nfastblocks;
> fastavail += chunksize (p);
> }
> @@ -5437,8 +5481,11 @@ __malloc_info (int options, FILE *fp)
>
> while (p != NULL)
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("__malloc_info(): " \
> + "unaligned fastbin chunk detected");
OK.
> ++nthissize;
> - p = p->fd;
> + p = REVEAL_PTR (p->fd);
OK.
> }
>
> fastavail += nthissize * thissize;
> --
> 2.17.1
>
--
Cheers,
Carlos.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-21 2:47 ` Carlos O'Donell
@ 2020-03-23 13:52 ` Adhemerval Zanella
2020-03-23 16:11 ` DJ Delorie
2020-03-29 17:04 ` Carlos O'Donell
1 sibling, 1 reply; 33+ messages in thread
From: Adhemerval Zanella @ 2020-03-23 13:52 UTC (permalink / raw)
To: Carlos O'Donell, Eyal Itkin, DJ Delorie, Wilco Dijkstra,
Florian Weimer
Cc: GNU C Library
On 20/03/2020 23:47, Carlos O'Donell wrote:
> I like that we might extend Safe-Linking to all lists, including the
> exit_function_list which is a prime target of attack since it has
> a singly linked list and could be written to in order to execute
> arbitrary function pointers (requires also the probability of guessing
> PTR_MANGLE results). Unlike malloc, in other less performance
> sensitive functions we can use bits of randomness from a global
> variable.
>
> Reviews so far:
> - Wilco Dijkstra (Arm)
> - DJ Delorie (Red Hat)
> - Adhemerval Zanella (Linaro)
> - Carlos O'Donell (Red Hat)
>
> If Adhemerval, DJ, and Wilco want to give their Reviewed-by, then I'll
> add those too.
Ok, thanks.
>
> I see one remaining issue to discuss and it is the emacs dumped heap
> state. The rest looks good to me too.
>
> I'm TO'ing Florian here in case he wants to comment. A few years ago
> (time flies! 2016!) Florian had an idea to protect the chunk metadata
> with xor and some randomness (size and prevsize):
> https://sourceware.org/legacy-ml/libc-alpha/2016-10/msg00531.html
I forgot about this one. With ASLR entropy we are bounded by two
factor:
1. architecture must provide ARCH_HAS_ELF_RANDOMIZE.
2. the mmap entropy provided bits.
For 1. it seems not all architectures does provide it (based on
kernel Documentation/features/vm/ELF-ASLR/arch-support.txt with
some edits to remove architecture not support by glibc), which
makes this mitigation work solely on such architectures.
-----------------------
| arch |status|
-----------------------
| alpha: | TODO |
| arc: | TODO |
| arm: | ok |
| arm64: | ok |
| csky: | TODO |
| ia64: | TODO |
| m68k: | TODO |
| microblaze: | TODO |
| mips: | ok |
| nios2: | TODO |
| parisc: | ok |
| powerpc: | ok |
| riscv: | ok |
| s390: | ok |
| sh: | TODO |
| sparc: | ok |
| x86: | ok |
-----------------------
(Linux internal documentation is in fact outdated, both sparc and
riscv does support ASLR).
Also, the mmap entropy vary largely over architectures and kernel
configurations, as table below where I extended the information
compiled on BZ#22853 . Some architectures also provides a kernel
config that can increase the maximum mmpa random bits (which is
only accessible by admin and system-defined).
+-----------------+----------------+-------------------+
| System | mmap rnd bits | MMAP_RND_BITS_MAX |
+-----------------+----------------+-------------------+
| x86_64 | 28 | 32 |
| i386 / x32 | 8 | 16 |
| arm | 8 [2] | 16 [3] |
| aarch64 | 18 [4] | 33 [5] |
| powerpc64 | 14 [6] | 29 [7] |
| powerpc | 7 [8] | 13 [9] |
| s390x | 11 | - |
| s390 | 11 | - |
| hppa | 13 | - |
| mips64 | 12 | 18 |
| mips | 8 | 15 |
| riscv64 | 18 | 24 |
| riscv32 | 8 | 17 |
| sparc64 | 16 | - |
| sparc32 | 11 | - |
+-----------------+----------------+-------------------+
So although this patch does help improve the situation, I think we should
move to a more robust and arch neutral way to obtain entropy for malloc
hardnening.
Florian suggestion basically uses AT_RANDOM which provides 128-bits.
It is *way better* than rely on ASLR, but I am not sure if SHA256
the AT_RANDOM does improve things significantly, specially over the
tradeoff of text and data increase on loader (on some architecture we
might replace with hardware optimizations).
[1] https://sourceware.org/pipermail/libc-alpha/2016-October/075546.html
[2] 15 for 16k pages, and 14 for 64k pages.
[3] 14 for PAGE_OFFSET=0x40000000 and 15 for PAGE_OFFSET=0x80000000.
[4] 18 for 4k pages.
[5] 19 for 36-bit VMA, 24 for 39-bit VMA, 27 for 42-bit VMA,
30 for 47-bit VMA, 29 for 48-bit VMA / 64k pages, 31 for
48-bit and 16k pages, 31 for 47-bit VMA / 4k pages, 14 for 64k
pages, and 16 for 16k pages.
[6] 18 for 4k pages.
[7] 33 for 4k pages.
[8] 5 for 256k pages, 9 for 16k pages, and 11 for 4k pages
[9] 11 for 256k pages, 15 for 16k pages, and 17 for 4k pages.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-23 13:52 ` Adhemerval Zanella
@ 2020-03-23 16:11 ` DJ Delorie
2020-03-23 16:23 ` Carlos O'Donell
` (2 more replies)
0 siblings, 3 replies; 33+ messages in thread
From: DJ Delorie @ 2020-03-23 16:11 UTC (permalink / raw)
To: Adhemerval Zanella
Cc: carlos, eyal.itkin, Wilco.Dijkstra, fweimer, libc-alpha
Adhemerval Zanella <adhemerval.zanella@linaro.org> writes:
> So although this patch does help improve the situation, I think we should
> move to a more robust and arch neutral way to obtain entropy for malloc
> hardnening.
Can we agree to approve this patch, and replace the "12" with something
better later? That way we'll at least make incremental progress.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-23 16:11 ` DJ Delorie
@ 2020-03-23 16:23 ` Carlos O'Donell
2020-03-23 16:26 ` Adhemerval Zanella
2020-03-24 13:44 ` Wilco Dijkstra
2 siblings, 0 replies; 33+ messages in thread
From: Carlos O'Donell @ 2020-03-23 16:23 UTC (permalink / raw)
To: DJ Delorie, Adhemerval Zanella
Cc: eyal.itkin, Wilco.Dijkstra, fweimer, libc-alpha
On 3/23/20 12:11 PM, DJ Delorie wrote:
> Adhemerval Zanella <adhemerval.zanella@linaro.org> writes:
>> So although this patch does help improve the situation, I think we should
>> move to a more robust and arch neutral way to obtain entropy for malloc
>> hardnening.
>
> Can we agree to approve this patch, and replace the "12" with something
> better later? That way we'll at least make incremental progress.
I agree.
I'm fine with using ASLR/12-shift to get entropy.
I think the next logical step is to revive Florian's patch to harden prev
and prevsize and storing entropy in a global.
So I see this as two steps.
--
Cheers,
Carlos.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-23 16:11 ` DJ Delorie
2020-03-23 16:23 ` Carlos O'Donell
@ 2020-03-23 16:26 ` Adhemerval Zanella
2020-03-24 13:44 ` Wilco Dijkstra
2 siblings, 0 replies; 33+ messages in thread
From: Adhemerval Zanella @ 2020-03-23 16:26 UTC (permalink / raw)
To: DJ Delorie; +Cc: carlos, eyal.itkin, Wilco.Dijkstra, fweimer, libc-alpha
On 23/03/2020 13:11, DJ Delorie wrote:
> Adhemerval Zanella <adhemerval.zanella@linaro.org> writes:
>> So although this patch does help improve the situation, I think we should
>> move to a more robust and arch neutral way to obtain entropy for malloc
>> hardnening.
>
> Can we agree to approve this patch, and replace the "12" with something
> better later? That way we'll at least make incremental progress.
>
Sorry if I wasn't clear, I am ok this patch (I reply with OK to add
my reviewed-by).
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-23 16:11 ` DJ Delorie
2020-03-23 16:23 ` Carlos O'Donell
2020-03-23 16:26 ` Adhemerval Zanella
@ 2020-03-24 13:44 ` Wilco Dijkstra
2 siblings, 0 replies; 33+ messages in thread
From: Wilco Dijkstra @ 2020-03-24 13:44 UTC (permalink / raw)
To: DJ Delorie, Adhemerval Zanella; +Cc: carlos, eyal.itkin, fweimer, libc-alpha
Hi,
>Adhemerval Zanella <adhemerval.zanella@linaro.org> writes:
>> So although this patch does help improve the situation, I think we should
>> move to a more robust and arch neutral way to obtain entropy for malloc
>> hardnening.
Well I'm wondering whether it will ever be possible to harden properly - the key
problem is storing internal pointers in user data which may be corrupted. A more
safe approach would be to use separate arrays/bitmaps to store the free list.
This may even be faster due to better locality.
> Can we agree to approve this patch, and replace the "12" with something
> better later? That way we'll at least make incremental progress.
Agreed. The latest version of the patch looks good to me.
Wilco
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-21 2:47 ` Carlos O'Donell
2020-03-23 13:52 ` Adhemerval Zanella
@ 2020-03-29 17:04 ` Carlos O'Donell
2020-03-30 6:30 ` Eyal Itkin
2020-03-30 7:56 ` Andreas Schwab
1 sibling, 2 replies; 33+ messages in thread
From: Carlos O'Donell @ 2020-03-29 17:04 UTC (permalink / raw)
To: Eyal Itkin, Adhemerval Zanella, DJ Delorie, Wilco Dijkstra,
Florian Weimer
Cc: GNU C Library
On 3/20/20 10:47 PM, Carlos O'Donell wrote:
> If nobody objects I'll push this next week after giving people some
> more time to review.
Pushed.
Eyal, Thank you for the high quality submission.
--
Cheers,
Carlos.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-29 17:04 ` Carlos O'Donell
@ 2020-03-30 6:30 ` Eyal Itkin
2020-03-30 7:56 ` Andreas Schwab
1 sibling, 0 replies; 33+ messages in thread
From: Eyal Itkin @ 2020-03-30 6:30 UTC (permalink / raw)
To: Carlos O'Donell
Cc: Adhemerval Zanella, DJ Delorie, Wilco Dijkstra, Florian Weimer,
GNU C Library
Thanks a lot for the help with this patch, I really appreciate it.
I am now working on converting my tests for Safe-Linking into a test
suitable for glibc's testsuite, and I will submit it as an additional
patch, as was suggested by Carlos.
Thanks again,
Eyal.
On Sun, Mar 29, 2020 at 8:04 PM Carlos O'Donell <carlos@redhat.com> wrote:
>
> On 3/20/20 10:47 PM, Carlos O'Donell wrote:
> > If nobody objects I'll push this next week after giving people some
> > more time to review.
>
> Pushed.
>
> Eyal, Thank you for the high quality submission.
>
> --
> Cheers,
> Carlos.
>
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-29 17:04 ` Carlos O'Donell
2020-03-30 6:30 ` Eyal Itkin
@ 2020-03-30 7:56 ` Andreas Schwab
1 sibling, 0 replies; 33+ messages in thread
From: Andreas Schwab @ 2020-03-30 7:56 UTC (permalink / raw)
To: Carlos O'Donell via Libc-alpha
Cc: Eyal Itkin, Adhemerval Zanella, DJ Delorie, Wilco Dijkstra,
Florian Weimer, Carlos O'Donell
https://build.opensuse.org/package/live_build_log/home:Andreas_Schwab:glibc/glibc/f/i586
https://build.opensuse.org/package/live_build_log/home:Andreas_Schwab:glibc/glibc/p/ppc
[ 1025s] malloc_consolidate(): unaligned fastbin chunk detected
Andreas.
--
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE 1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-20 19:45 ` Eyal Itkin
2020-03-20 23:58 ` DJ Delorie
2020-03-21 2:47 ` Carlos O'Donell
@ 2020-03-30 8:01 ` Andreas Schwab
2020-03-30 8:44 ` Eyal Itkin
2 siblings, 1 reply; 33+ messages in thread
From: Andreas Schwab @ 2020-03-30 8:01 UTC (permalink / raw)
To: Eyal Itkin via Libc-alpha
On Mär 20 2020, Eyal Itkin via Libc-alpha wrote:
> @@ -2960,7 +2979,10 @@ tcache_thread_shutdown (void)
> while (tcache_tmp->entries[i])
> {
> tcache_entry *e = tcache_tmp->entries[i];
> - tcache_tmp->entries[i] = e->next;
> + if (__glibc_unlikely (!aligned_OK (e)))
> + malloc_printerr ("tcache_thread_shutdown(): " \
> + "unaligned tcache chunk detected");
> + tcache_tmp->entries[i] = REVEAL_PTR (e->next);
> __libc_free (e);
Wrong indentation, extra backslash.
> @@ -4196,11 +4226,15 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
> for (tmp = tcache->entries[tc_idx];
> tmp;
> - tmp = tmp->next)
> + tmp = REVEAL_PTR (tmp->next))
> + {
> + if (__glibc_unlikely (!aligned_OK (tmp)))
> + malloc_printerr ("free(): unaligned chunk detected in tcache 2");
> if (tmp == e)
> malloc_printerr ("free(): double free detected in tcache 2");
> /* If we get here, it was a coincidence. We've wasted a
> few cycles, but don't abort. */
> + }
Wrong indentation.
> @@ -4896,8 +4935,13 @@ int_mallinfo (mstate av, struct mallinfo *m)
>
> for (i = 0; i < NFASTBINS; ++i)
> {
> - for (p = fastbin (av, i); p != 0; p = p->fd)
> + for (p = fastbin (av, i);
> + p != 0;
> + p = REVEAL_PTR (p->fd))
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("int_mallinfo(): " \
> + "unaligned fastbin chunk detected");
Extra backslash.
> @@ -5437,8 +5481,11 @@ __malloc_info (int options, FILE *fp)
>
> while (p != NULL)
> {
> + if (__glibc_unlikely (!aligned_OK (p)))
> + malloc_printerr ("__malloc_info(): " \
> + "unaligned fastbin chunk detected");
> ++nthissize;
Wrong indentation, extra backslash.
Andreas.
--
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE 1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-30 8:01 ` Andreas Schwab
@ 2020-03-30 8:44 ` Eyal Itkin
2020-03-30 13:56 ` Carlos O'Donell
0 siblings, 1 reply; 33+ messages in thread
From: Eyal Itkin @ 2020-03-30 8:44 UTC (permalink / raw)
To: Andreas Schwab; +Cc: Eyal Itkin via Libc-alpha, Adhemerval Zanella
Sorry about the indentations. The file has mixed tabs and spaces, sometimes
even in the same code line, which makes it hard to know what's right. In
each case I tried to mimick the behavior of the lines before / after my
addition.
Regarding the new issue in malloc_consolidate, I'm going over it now as it
didn't happen on my intel x64 environment. Will update you soon about it.
On Mon, 30 Mar 2020, 11:01 Andreas Schwab, <schwab@suse.de> wrote:
> On Mär 20 2020, Eyal Itkin via Libc-alpha wrote:
>
> > @@ -2960,7 +2979,10 @@ tcache_thread_shutdown (void)
> > while (tcache_tmp->entries[i])
> > {
> > tcache_entry *e = tcache_tmp->entries[i];
> > - tcache_tmp->entries[i] = e->next;
> > + if (__glibc_unlikely (!aligned_OK (e)))
> > + malloc_printerr ("tcache_thread_shutdown(): " \
> > + "unaligned tcache chunk detected");
> > + tcache_tmp->entries[i] = REVEAL_PTR (e->next);
> > __libc_free (e);
>
> Wrong indentation, extra backslash.
>
> > @@ -4196,11 +4226,15 @@ _int_free (mstate av, mchunkptr p, int have_lock)
> > LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
> > for (tmp = tcache->entries[tc_idx];
> > tmp;
> > - tmp = tmp->next)
> > + tmp = REVEAL_PTR (tmp->next))
> > + {
> > + if (__glibc_unlikely (!aligned_OK (tmp)))
> > + malloc_printerr ("free(): unaligned chunk detected in
> tcache 2");
> > if (tmp == e)
> > malloc_printerr ("free(): double free detected in tcache
> 2");
> > /* If we get here, it was a coincidence. We've wasted a
> > few cycles, but don't abort. */
> > + }
>
> Wrong indentation.
>
> > @@ -4896,8 +4935,13 @@ int_mallinfo (mstate av, struct mallinfo *m)
> >
> > for (i = 0; i < NFASTBINS; ++i)
> > {
> > - for (p = fastbin (av, i); p != 0; p = p->fd)
> > + for (p = fastbin (av, i);
> > + p != 0;
> > + p = REVEAL_PTR (p->fd))
> > {
> > + if (__glibc_unlikely (!aligned_OK (p)))
> > + malloc_printerr ("int_mallinfo(): " \
> > + "unaligned fastbin chunk detected");
>
> Extra backslash.
>
> > @@ -5437,8 +5481,11 @@ __malloc_info (int options, FILE *fp)
> >
> > while (p != NULL)
> > {
> > + if (__glibc_unlikely (!aligned_OK (p)))
> > + malloc_printerr ("__malloc_info(): " \
> > + "unaligned fastbin chunk detected");
> > ++nthissize;
>
> Wrong indentation, extra backslash.
>
> Andreas.
>
> --
> Andreas Schwab, SUSE Labs, schwab@suse.de
> GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE 1748 E4D4 88E3 0EEA B9D7
> "And now for something completely different."
>
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-30 8:44 ` Eyal Itkin
@ 2020-03-30 13:56 ` Carlos O'Donell
2020-03-30 17:19 ` Eyal Itkin
2020-10-31 13:33 ` H.J. Lu
0 siblings, 2 replies; 33+ messages in thread
From: Carlos O'Donell @ 2020-03-30 13:56 UTC (permalink / raw)
To: Eyal Itkin, Andreas Schwab; +Cc: Eyal Itkin via Libc-alpha
On 3/30/20 4:44 AM, Eyal Itkin via Libc-alpha wrote:
> Sorry about the indentations. The file has mixed tabs and spaces, sometimes
> even in the same code line, which makes it hard to know what's right. In
> each case I tried to mimick the behavior of the lines before / after my
> addition.
No worries, this is entirely my fault. I thought I'd fixed all of those up
during my import of your patch. That's my responsibility really. I'll correct
them and push the cleanup.
> Regarding the new issue in malloc_consolidate, I'm going over it now as it
> didn't happen on my intel x64 environment. Will update you soon about it.
Thanks!
--
Cheers,
Carlos.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-30 13:56 ` Carlos O'Donell
@ 2020-03-30 17:19 ` Eyal Itkin
2020-10-31 13:33 ` H.J. Lu
1 sibling, 0 replies; 33+ messages in thread
From: Eyal Itkin @ 2020-03-30 17:19 UTC (permalink / raw)
To: Carlos O'Donell; +Cc: Andreas Schwab, Eyal Itkin via Libc-alpha
Submitted a separate patch to fix the bug which crashed on 32 bit architectures.
Also fixed the redundant '\' chars at the end of lines as requested by Andreas.
Sorry for the troubles with my patch,
Eyal.
On Mon, Mar 30, 2020 at 4:56 PM Carlos O'Donell <carlos@redhat.com> wrote:
>
> On 3/30/20 4:44 AM, Eyal Itkin via Libc-alpha wrote:
> > Sorry about the indentations. The file has mixed tabs and spaces, sometimes
> > even in the same code line, which makes it hard to know what's right. In
> > each case I tried to mimick the behavior of the lines before / after my
> > addition.
>
> No worries, this is entirely my fault. I thought I'd fixed all of those up
> during my import of your patch. That's my responsibility really. I'll correct
> them and push the cleanup.
>
> > Regarding the new issue in malloc_consolidate, I'm going over it now as it
> > didn't happen on my intel x64 environment. Will update you soon about it.
>
> Thanks!
>
> --
> Cheers,
> Carlos.
>
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-30 13:56 ` Carlos O'Donell
2020-03-30 17:19 ` Eyal Itkin
@ 2020-10-31 13:33 ` H.J. Lu
2020-10-31 14:49 ` Eyal Itkin
1 sibling, 1 reply; 33+ messages in thread
From: H.J. Lu @ 2020-10-31 13:33 UTC (permalink / raw)
To: Carlos O'Donell; +Cc: Eyal Itkin, Andreas Schwab, Eyal Itkin via Libc-alpha
On Mon, Mar 30, 2020 at 6:56 AM Carlos O'Donell via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> On 3/30/20 4:44 AM, Eyal Itkin via Libc-alpha wrote:
> > Sorry about the indentations. The file has mixed tabs and spaces, sometimes
> > even in the same code line, which makes it hard to know what's right. In
> > each case I tried to mimick the behavior of the lines before / after my
> > addition.
>
> No worries, this is entirely my fault. I thought I'd fixed all of those up
> during my import of your patch. That's my responsibility really. I'll correct
> them and push the cleanup.
>
> > Regarding the new issue in malloc_consolidate, I'm going over it now as it
> > didn't happen on my intel x64 environment. Will update you soon about it.
>
This caused:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96504
https://sourceware.org/bugzilla/show_bug.cgi?id=26826
--
H.J.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-10-31 13:33 ` H.J. Lu
@ 2020-10-31 14:49 ` Eyal Itkin
2020-10-31 15:27 ` H.J. Lu
0 siblings, 1 reply; 33+ messages in thread
From: Eyal Itkin @ 2020-10-31 14:49 UTC (permalink / raw)
To: H.J. Lu; +Cc: Carlos O'Donell, Andreas Schwab, Eyal Itkin via Libc-alpha
Thanks for the notification about this issue.
Going over https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96504, it
seems that a bug was fixed in gcc between gcc-10.2.0 and gcc version
11.0.0 20201029, and I traced this bug to the following commit:
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=f6615c213354fd3ec7fc6238e61cc26bb1830464.
Essentially, the test "co-ret-17-void-ret-coro.C" had an error that
was caught using fsanitize=address, and this is why the test does not
crash for gcc-11.0.0.
In a way, fsanitize=address catches memory errors (use-after-free),
and Safe-Linking is a mechanism that will prevent improper use of
freed heap buffers. And so, it seems that just like Safe-Linking
prompted about the faulty test "co-ret-17-void-ret-coro.C" in
gcc-10.2.0, it also warns about the similar test: "pr95519-05-gro.C".
I went over the code of the said test, and it seems that both tests
are very similar, and that the test indeed suffers from the same
"use-after-free" in line 53 "if (!f.done())". I would recommend
testing the test using fsanitize=address, and probably also patching
it using a similar patch to the one that fixed
"co-ret-17-void-ret-coro.C":
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=f6615c213354fd3ec7fc6238e61cc26bb1830464.
Eyal.
On Sat, Oct 31, 2020 at 3:33 PM H.J. Lu <hjl.tools@gmail.com> wrote:
>
> On Mon, Mar 30, 2020 at 6:56 AM Carlos O'Donell via Libc-alpha
> <libc-alpha@sourceware.org> wrote:
> >
> > On 3/30/20 4:44 AM, Eyal Itkin via Libc-alpha wrote:
> > > Sorry about the indentations. The file has mixed tabs and spaces, sometimes
> > > even in the same code line, which makes it hard to know what's right. In
> > > each case I tried to mimick the behavior of the lines before / after my
> > > addition.
> >
> > No worries, this is entirely my fault. I thought I'd fixed all of those up
> > during my import of your patch. That's my responsibility really. I'll correct
> > them and push the cleanup.
> >
> > > Regarding the new issue in malloc_consolidate, I'm going over it now as it
> > > didn't happen on my intel x64 environment. Will update you soon about it.
> >
>
> This caused:
>
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96504
> https://sourceware.org/bugzilla/show_bug.cgi?id=26826
>
> --
> H.J.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-10-31 14:49 ` Eyal Itkin
@ 2020-10-31 15:27 ` H.J. Lu
0 siblings, 0 replies; 33+ messages in thread
From: H.J. Lu @ 2020-10-31 15:27 UTC (permalink / raw)
To: Eyal Itkin; +Cc: Carlos O'Donell, Andreas Schwab, Eyal Itkin via Libc-alpha
On Sat, Oct 31, 2020 at 7:49 AM Eyal Itkin <eyal.itkin@gmail.com> wrote:
>
> Thanks for the notification about this issue.
>
> Going over https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96504, it
> seems that a bug was fixed in gcc between gcc-10.2.0 and gcc version
> 11.0.0 20201029, and I traced this bug to the following commit:
> https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=f6615c213354fd3ec7fc6238e61cc26bb1830464.
> Essentially, the test "co-ret-17-void-ret-coro.C" had an error that
> was caught using fsanitize=address, and this is why the test does not
> crash for gcc-11.0.0.
>
> In a way, fsanitize=address catches memory errors (use-after-free),
> and Safe-Linking is a mechanism that will prevent improper use of
> freed heap buffers. And so, it seems that just like Safe-Linking
> prompted about the faulty test "co-ret-17-void-ret-coro.C" in
> gcc-10.2.0, it also warns about the similar test: "pr95519-05-gro.C".
>
> I went over the code of the said test, and it seems that both tests
> are very similar, and that the test indeed suffers from the same
> "use-after-free" in line 53 "if (!f.done())". I would recommend
> testing the test using fsanitize=address, and probably also patching
> it using a similar patch to the one that fixed
> "co-ret-17-void-ret-coro.C":
> https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=f6615c213354fd3ec7fc6238e61cc26bb1830464.
>
It is a use after free bug in GCC:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96504#c3
--
H.J.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-18 21:28 ` Carlos O'Donell
@ 2020-03-19 6:41 ` Eyal Itkin
0 siblings, 0 replies; 33+ messages in thread
From: Eyal Itkin @ 2020-03-19 6:41 UTC (permalink / raw)
To: Carlos O'Donell; +Cc: Carlos O'Donell, GNU C Library
Happy to hear that all the legal issues have been resolved.
What are the next steps? Have you read the white paper?
(https://github.com/gperftools/gperftools/files/4023520/Safe-Linking-White-Paper.txt)
It should contain a detailed explanation for the reasons behind this
feature, and also explain how it works.
The patch itself simply applies the single-linked-list pointer masking
(and alignment checks) to both the Fast Bins and TCache lists.
Will be happy to assist in any way I can,
Eyal.
On Wed, Mar 18, 2020 at 11:28 PM Carlos O'Donell <carlos@redhat.com> wrote:
>
> On Wed, Mar 4, 2020 at 10:30 PM Carlos O'Donell <carlos@redhat.com> wrote:
> >
> > On 3/4/20 8:19 PM, Eyal Itkin wrote:
> > > It took some time, but I signed all the forms, and just received back
> > > the mutually signed FSF form.
> >
> > This is great news!
> >
> > I have reviewed the results, and unfortunately I have a question for
> > the FSF which I hope gets resolved quickly. Once it's resolved we can
> > start reviewing the patches (looks like a typo).
>
> OK, the typo has been fixed, sorry for this.
>
> > > What is needed now in order to proceed with the patch that I've submitted?
> >
> > Once I get confirmation from the FSF about the issue then I can review the
> > patch starting with the high-level architecture.
>
> Now we can start the review!
>
> Cheers,
> Carlos.
>
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-05 3:30 ` Carlos O'Donell
@ 2020-03-18 21:28 ` Carlos O'Donell
2020-03-19 6:41 ` Eyal Itkin
0 siblings, 1 reply; 33+ messages in thread
From: Carlos O'Donell @ 2020-03-18 21:28 UTC (permalink / raw)
To: Eyal Itkin, Carlos O'Donell; +Cc: GNU C Library
On Wed, Mar 4, 2020 at 10:30 PM Carlos O'Donell <carlos@redhat.com> wrote:
>
> On 3/4/20 8:19 PM, Eyal Itkin wrote:
> > It took some time, but I signed all the forms, and just received back
> > the mutually signed FSF form.
>
> This is great news!
>
> I have reviewed the results, and unfortunately I have a question for
> the FSF which I hope gets resolved quickly. Once it's resolved we can
> start reviewing the patches (looks like a typo).
OK, the typo has been fixed, sorry for this.
> > What is needed now in order to proceed with the patch that I've submitted?
>
> Once I get confirmation from the FSF about the issue then I can review the
> patch starting with the high-level architecture.
Now we can start the review!
Cheers,
Carlos.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-03-05 1:19 ` Eyal Itkin
@ 2020-03-05 3:30 ` Carlos O'Donell
2020-03-18 21:28 ` Carlos O'Donell
0 siblings, 1 reply; 33+ messages in thread
From: Carlos O'Donell @ 2020-03-05 3:30 UTC (permalink / raw)
To: Eyal Itkin, Carlos O'Donell; +Cc: libc-alpha
On 3/4/20 8:19 PM, Eyal Itkin wrote:
> It took some time, but I signed all the forms, and just received back
> the mutually signed FSF form.
This is great news!
I have reviewed the results, and unfortunately I have a question for
the FSF which I hope gets resolved quickly. Once it's resolved we can
start reviewing the patches (looks like a typo).
> What is needed now in order to proceed with the patch that I've submitted?
Once I get confirmation from the FSF about the issue then I can review the
patch starting with the high-level architecture.
> Thanks again for your cooperation,
Thank you for working through the contribution process!
--
Cheers,
Carlos.
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-02-03 19:48 ` Eyal Itkin
@ 2020-03-05 1:19 ` Eyal Itkin
2020-03-05 3:30 ` Carlos O'Donell
0 siblings, 1 reply; 33+ messages in thread
From: Eyal Itkin @ 2020-03-05 1:19 UTC (permalink / raw)
To: Carlos O'Donell; +Cc: libc-alpha
It took some time, but I signed all the forms, and just received back
the mutually signed FSF form.
What is needed now in order to proceed with the patch that I've submitted?
Thanks again for your cooperation,
Eyal Itkin.
On Mon, 3 Feb 2020, 21:47 Eyal Itkin, <eyal.itkin@gmail.com> wrote:
>
> Thanks for your fast response.
> I've just sent an assignment using your supplied form.
>
> If anything else is needed I will be more than happy to assist.
>
> Eyal.
>
> On Mon, Feb 3, 2020 at 8:10 PM Carlos O'Donell <codonell@redhat.com> wrote:
> >
> > On 2/2/20 4:43 AM, Eyal Itkin wrote:
> > > Safe-Linking is a security mechanism that protects single-linked
> > > lists (such as the fastbin and tcache) from being tampered by attackers.
> > > The mechanism makes use of randomness from ASLR (mmap_base), and
> > > when combined with chunk alignment integrity checks, it protects the
> > > pointers from being hijacked by an attacker.
> > >
> > > While Safe-Unlinking protects double-linked lists (such as the small
> > > bins), there wasn't any similar protection for attacks against
> > > single-linked lists. This solution protects against 3 common attacks:
> > > * Partial pointer override: modifies the lower bytes (Little Endian)
> > > * Full pointer override: hijacks the pointer to an attacker's location
> > > * Unaligned chunks: pointing the list to an unaligned address
> > >
> > > The design assumes an attacker doesn't know where the heap is located,
> > > and uses the ASLR randomness to "sign" the single-linked pointers. We
> > > mark the pointer as P and the location in which it is stored as L, and
> > > the calculation will be:
> > > * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
> > > * *L = PROTECT(P)
> > >
> > > This way, the random bits from the address L (which start at the bit
> > > in the PAGE_SHIFT position), will be merged with LSB of the stored
> > > protected pointer. This protection layer prevents an attacker from
> > > modifying the pointer into a controlled value.
> > >
> > > An additional check that the chunks are MALLOC_ALIGNed adds an
> > > important layer:
> > > * Attackers can't point to illegal (unaligned) memory addresses
> > > * Attackers must guess correctly the alignment bits
> > >
> > > On standard 32 bit Linux machines, an attack will directly fail 7
> > > out of 8 times, and on 64 bit machines it will fail 15 out of 16
> > > times.
> > >
> > > This proposed patch was benchmarked and it's effect on the overall
> > > performance of the heap was negligible and couldn't be distinguished
> > > from the default variance between tests on the vanilla version. A
> > > similar protection was added to Chromium's version of TCMalloc
> > > in 2013, and according to their documentation it had an overhead of
> > > less than 2%.
> > >
> > > For more information, please read out White Paper which can be
> > > found here:
> > > https://github.com/gperftools/gperftools/files/4023520/Safe-Linking-White-Paper.txt
> >
> > The concept behind your patch looks really interesting, thank you for
> > working on this patch!
> >
> > One of the things we'll need from you is a copyright assignment
> > before the glibc project can accept the patches.
> >
> > Please have a look at our "Contribution Checklist"
> > https://sourceware.org/glibc/wiki/Contribution%20checklist
> >
> > "FSF Copyright Assignment"
> > https://sourceware.org/glibc/wiki/Contribution%20checklist#FSF_copyright_Assignment
> >
> > I always suggest a futures assignment so we can accept this patch
> > and all future patches you submit to glibc:
> > http://git.savannah.gnu.org/cgit/gnulib.git/plain/doc/Copyright/request-assign.future
> >
> > Thank you for your contribution!
> >
> > --
> > Cheers,
> > Carlos.
> >
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-02-03 18:10 ` Carlos O'Donell
@ 2020-02-03 19:48 ` Eyal Itkin
2020-03-05 1:19 ` Eyal Itkin
0 siblings, 1 reply; 33+ messages in thread
From: Eyal Itkin @ 2020-02-03 19:48 UTC (permalink / raw)
To: Carlos O'Donell; +Cc: libc-alpha
Thanks for your fast response.
I've just sent an assignment using your supplied form.
If anything else is needed I will be more than happy to assist.
Eyal.
On Mon, Feb 3, 2020 at 8:10 PM Carlos O'Donell <codonell@redhat.com> wrote:
>
> On 2/2/20 4:43 AM, Eyal Itkin wrote:
> > Safe-Linking is a security mechanism that protects single-linked
> > lists (such as the fastbin and tcache) from being tampered by attackers.
> > The mechanism makes use of randomness from ASLR (mmap_base), and
> > when combined with chunk alignment integrity checks, it protects the
> > pointers from being hijacked by an attacker.
> >
> > While Safe-Unlinking protects double-linked lists (such as the small
> > bins), there wasn't any similar protection for attacks against
> > single-linked lists. This solution protects against 3 common attacks:
> > * Partial pointer override: modifies the lower bytes (Little Endian)
> > * Full pointer override: hijacks the pointer to an attacker's location
> > * Unaligned chunks: pointing the list to an unaligned address
> >
> > The design assumes an attacker doesn't know where the heap is located,
> > and uses the ASLR randomness to "sign" the single-linked pointers. We
> > mark the pointer as P and the location in which it is stored as L, and
> > the calculation will be:
> > * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
> > * *L = PROTECT(P)
> >
> > This way, the random bits from the address L (which start at the bit
> > in the PAGE_SHIFT position), will be merged with LSB of the stored
> > protected pointer. This protection layer prevents an attacker from
> > modifying the pointer into a controlled value.
> >
> > An additional check that the chunks are MALLOC_ALIGNed adds an
> > important layer:
> > * Attackers can't point to illegal (unaligned) memory addresses
> > * Attackers must guess correctly the alignment bits
> >
> > On standard 32 bit Linux machines, an attack will directly fail 7
> > out of 8 times, and on 64 bit machines it will fail 15 out of 16
> > times.
> >
> > This proposed patch was benchmarked and it's effect on the overall
> > performance of the heap was negligible and couldn't be distinguished
> > from the default variance between tests on the vanilla version. A
> > similar protection was added to Chromium's version of TCMalloc
> > in 2013, and according to their documentation it had an overhead of
> > less than 2%.
> >
> > For more information, please read out White Paper which can be
> > found here:
> > https://github.com/gperftools/gperftools/files/4023520/Safe-Linking-White-Paper.txt
>
> The concept behind your patch looks really interesting, thank you for
> working on this patch!
>
> One of the things we'll need from you is a copyright assignment
> before the glibc project can accept the patches.
>
> Please have a look at our "Contribution Checklist"
> https://sourceware.org/glibc/wiki/Contribution%20checklist
>
> "FSF Copyright Assignment"
> https://sourceware.org/glibc/wiki/Contribution%20checklist#FSF_copyright_Assignment
>
> I always suggest a futures assignment so we can accept this patch
> and all future patches you submit to glibc:
> http://git.savannah.gnu.org/cgit/gnulib.git/plain/doc/Copyright/request-assign.future
>
> Thank you for your contribution!
>
> --
> Cheers,
> Carlos.
>
^ permalink raw reply [flat|nested] 33+ messages in thread
* Re: [PATCH] Add Safe-Linking to fastbins and tcache
2020-02-02 9:43 Eyal Itkin
@ 2020-02-03 18:10 ` Carlos O'Donell
2020-02-03 19:48 ` Eyal Itkin
0 siblings, 1 reply; 33+ messages in thread
From: Carlos O'Donell @ 2020-02-03 18:10 UTC (permalink / raw)
To: Eyal Itkin, libc-alpha
On 2/2/20 4:43 AM, Eyal Itkin wrote:
> Safe-Linking is a security mechanism that protects single-linked
> lists (such as the fastbin and tcache) from being tampered by attackers.
> The mechanism makes use of randomness from ASLR (mmap_base), and
> when combined with chunk alignment integrity checks, it protects the
> pointers from being hijacked by an attacker.
>
> While Safe-Unlinking protects double-linked lists (such as the small
> bins), there wasn't any similar protection for attacks against
> single-linked lists. This solution protects against 3 common attacks:
> * Partial pointer override: modifies the lower bytes (Little Endian)
> * Full pointer override: hijacks the pointer to an attacker's location
> * Unaligned chunks: pointing the list to an unaligned address
>
> The design assumes an attacker doesn't know where the heap is located,
> and uses the ASLR randomness to "sign" the single-linked pointers. We
> mark the pointer as P and the location in which it is stored as L, and
> the calculation will be:
> * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
> * *L = PROTECT(P)
>
> This way, the random bits from the address L (which start at the bit
> in the PAGE_SHIFT position), will be merged with LSB of the stored
> protected pointer. This protection layer prevents an attacker from
> modifying the pointer into a controlled value.
>
> An additional check that the chunks are MALLOC_ALIGNed adds an
> important layer:
> * Attackers can't point to illegal (unaligned) memory addresses
> * Attackers must guess correctly the alignment bits
>
> On standard 32 bit Linux machines, an attack will directly fail 7
> out of 8 times, and on 64 bit machines it will fail 15 out of 16
> times.
>
> This proposed patch was benchmarked and it's effect on the overall
> performance of the heap was negligible and couldn't be distinguished
> from the default variance between tests on the vanilla version. A
> similar protection was added to Chromium's version of TCMalloc
> in 2013, and according to their documentation it had an overhead of
> less than 2%.
>
> For more information, please read out White Paper which can be
> found here:
> https://github.com/gperftools/gperftools/files/4023520/Safe-Linking-White-Paper.txt
The concept behind your patch looks really interesting, thank you for
working on this patch!
One of the things we'll need from you is a copyright assignment
before the glibc project can accept the patches.
Please have a look at our "Contribution Checklist"
https://sourceware.org/glibc/wiki/Contribution%20checklist
"FSF Copyright Assignment"
https://sourceware.org/glibc/wiki/Contribution%20checklist#FSF_copyright_Assignment
I always suggest a futures assignment so we can accept this patch
and all future patches you submit to glibc:
http://git.savannah.gnu.org/cgit/gnulib.git/plain/doc/Copyright/request-assign.future
Thank you for your contribution!
--
Cheers,
Carlos.
^ permalink raw reply [flat|nested] 33+ messages in thread
* [PATCH] Add Safe-Linking to fastbins and tcache
@ 2020-02-02 9:43 Eyal Itkin
2020-02-03 18:10 ` Carlos O'Donell
0 siblings, 1 reply; 33+ messages in thread
From: Eyal Itkin @ 2020-02-02 9:43 UTC (permalink / raw)
To: libc-alpha
Safe-Linking is a security mechanism that protects single-linked
lists (such as the fastbin and tcache) from being tampered by attackers.
The mechanism makes use of randomness from ASLR (mmap_base), and
when combined with chunk alignment integrity checks, it protects the
pointers from being hijacked by an attacker.
While Safe-Unlinking protects double-linked lists (such as the small
bins), there wasn't any similar protection for attacks against
single-linked lists. This solution protects against 3 common attacks:
* Partial pointer override: modifies the lower bytes (Little Endian)
* Full pointer override: hijacks the pointer to an attacker's location
* Unaligned chunks: pointing the list to an unaligned address
The design assumes an attacker doesn't know where the heap is located,
and uses the ASLR randomness to "sign" the single-linked pointers. We
mark the pointer as P and the location in which it is stored as L, and
the calculation will be:
* PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
* *L = PROTECT(P)
This way, the random bits from the address L (which start at the bit
in the PAGE_SHIFT position), will be merged with LSB of the stored
protected pointer. This protection layer prevents an attacker from
modifying the pointer into a controlled value.
An additional check that the chunks are MALLOC_ALIGNed adds an
important layer:
* Attackers can't point to illegal (unaligned) memory addresses
* Attackers must guess correctly the alignment bits
On standard 32 bit Linux machines, an attack will directly fail 7
out of 8 times, and on 64 bit machines it will fail 15 out of 16
times.
This proposed patch was benchmarked and it's effect on the overall
performance of the heap was negligible and couldn't be distinguished
from the default variance between tests on the vanilla version. A
similar protection was added to Chromium's version of TCMalloc
in 2013, and according to their documentation it had an overhead of
less than 2%.
For more information, please read out White Paper which can be
found here:
https://github.com/gperftools/gperftools/files/4023520/Safe-Linking-White-Paper.txt
---
malloc/malloc.c | 61 ++++++++++++++++++++++++++++++++++++++-----------
1 file changed, 48 insertions(+), 13 deletions(-)
diff --git a/malloc/malloc.c b/malloc/malloc.c
index 7d7d30bb13..25a745df9a 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -327,6 +327,15 @@ __malloc_assert (const char *assertion, const
char *file, unsigned int line,
# define MAX_TCACHE_COUNT UINT16_MAX
#endif
+/*
+ Safe-Linking:
+ Use randomness from ASLR (mmap_base) to protect single-linked lists
+ of Fast-Bins and TCache. Together with allocation alignment checks, this
+ mechanism reduces the risk of pointer hijacking, as was done with
+ Safe-Unlinking in the double-linked lists of Small-Bins.
+*/
+#define PROTECT_PTR(pos, ptr, type) ((type)((((size_t)pos) >>
PAGE_SHIFT) ^ ((size_t)ptr)))
+#define REVEAL_PTR(pos, ptr, type) PROTECT_PTR(pos, ptr, type)
/*
REALLOC_ZERO_BYTES_FREES should be set if a call to
@@ -2157,12 +2166,14 @@ do_check_malloc_state (mstate av)
while (p != 0)
{
+ if (__glibc_unlikely(!aligned_OK(p)))
+ malloc_printerr ("do_check_malloc_state(): un-aligned
fastbin chunk detected");
/* each chunk claims to be inuse */
do_check_inuse_chunk (av, p);
total += chunksize (p);
/* chunk belongs in this bin */
assert (fastbin_index (chunksize (p)) == i);
- p = p->fd;
+ p = REVEAL_PTR(&p->fd, p->fd, mchunkptr);
}
}
@@ -2923,7 +2934,7 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
detect a double free. */
e->key = tcache;
- e->next = tcache->entries[tc_idx];
+ e->next = PROTECT_PTR(&e->next, tcache->entries[tc_idx], tcache_entry *);
tcache->entries[tc_idx] = e;
++(tcache->counts[tc_idx]);
}
@@ -2934,9 +2945,11 @@ static __always_inline void *
tcache_get (size_t tc_idx)
{
tcache_entry *e = tcache->entries[tc_idx];
- tcache->entries[tc_idx] = e->next;
+ tcache->entries[tc_idx] = REVEAL_PTR(&e->next, e->next, tcache_entry *);
--(tcache->counts[tc_idx]);
e->key = NULL;
+ if (__glibc_unlikely(!aligned_OK(e)))
+ malloc_printerr ("malloc(): un-aligned tcache chunk detected");
return (void *) e;
}
@@ -2960,7 +2973,9 @@ tcache_thread_shutdown (void)
while (tcache_tmp->entries[i])
{
tcache_entry *e = tcache_tmp->entries[i];
- tcache_tmp->entries[i] = e->next;
+ if (__glibc_unlikely(!aligned_OK(e)))
+ malloc_printerr ("tcache_thread_shutdown(): un-aligned tcache
chunk detected");
+ tcache_tmp->entries[i] = REVEAL_PTR(&e->next, e->next, tcache_entry *);
__libc_free (e);
}
}
@@ -3570,8 +3585,11 @@ _int_malloc (mstate av, size_t bytes)
victim = pp; \
if (victim == NULL) \
break; \
+ pp = REVEAL_PTR(&victim->fd, victim->fd, mfastbinptr); \
+ if (__glibc_unlikely(!aligned_OK(pp))) \
+ malloc_printerr ("malloc(): un-aligned fastbin chunk detected"); \
} \
- while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim)) \
+ while ((pp = catomic_compare_and_exchange_val_acq (fb, pp, victim)) \
!= victim); \
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
@@ -3583,8 +3601,11 @@ _int_malloc (mstate av, size_t bytes)
if (victim != NULL)
{
+ if (__glibc_unlikely(!aligned_OK(victim)))
+ malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
+
if (SINGLE_THREAD_P)
- *fb = victim->fd;
+ *fb = REVEAL_PTR(&victim->fd, victim->fd, mfastbinptr);
else
REMOVE_FB (fb, pp, victim);
if (__glibc_likely (victim != NULL))
@@ -3605,8 +3626,10 @@ _int_malloc (mstate av, size_t bytes)
while (tcache->counts[tc_idx] < mp_.tcache_count
&& (tc_victim = *fb) != NULL)
{
+ if (__glibc_unlikely(!aligned_OK(tc_victim)))
+ malloc_printerr ("malloc(): un-aligned fastbin chunk detected");
if (SINGLE_THREAD_P)
- *fb = tc_victim->fd;
+ *fb = REVEAL_PTR(&tc_victim->fd, tc_victim->fd, mfastbinptr);
else
{
REMOVE_FB (fb, pp, tc_victim);
@@ -4196,11 +4219,15 @@ _int_free (mstate av, mchunkptr p, int have_lock)
LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
for (tmp = tcache->entries[tc_idx];
tmp;
- tmp = tmp->next)
+ tmp = REVEAL_PTR(&tmp->next, tmp->next, tcache_entry *))
+ {
+ if (__glibc_unlikely(!aligned_OK(tmp)))
+ malloc_printerr ("free(): un-aligned chunk detected in tcache 2");
if (tmp == e)
malloc_printerr ("free(): double free detected in tcache 2");
/* If we get here, it was a coincidence. We've wasted a
few cycles, but don't abort. */
+ }
}
if (tcache->counts[tc_idx] < mp_.tcache_count)
@@ -4264,7 +4291,7 @@ _int_free (mstate av, mchunkptr p, int have_lock)
add (i.e., double free). */
if (__builtin_expect (old == p, 0))
malloc_printerr ("double free or corruption (fasttop)");
- p->fd = old;
+ p->fd = PROTECT_PTR(&p->fd, old, mchunkptr);
*fb = p;
}
else
@@ -4274,7 +4301,8 @@ _int_free (mstate av, mchunkptr p, int have_lock)
add (i.e., double free). */
if (__builtin_expect (old == p, 0))
malloc_printerr ("double free or corruption (fasttop)");
- p->fd = old2 = old;
+ old2 = old;
+ p->fd = PROTECT_PTR(&p->fd, old, mchunkptr);
}
while ((old = catomic_compare_and_exchange_val_rel (fb, p, old2))
!= old2);
@@ -4472,13 +4500,16 @@ static void malloc_consolidate(mstate av)
if (p != 0) {
do {
{
+ if (__glibc_unlikely(!aligned_OK(p)))
+ malloc_printerr ("malloc_consolidate(): un-aligned fastbin chunk
detected");
+
unsigned int idx = fastbin_index (chunksize (p));
if ((&fastbin (av, idx)) != fb)
malloc_printerr ("malloc_consolidate(): invalid chunk size");
}
check_inuse_chunk(av, p);
- nextp = p->fd;
+ nextp = REVEAL_PTR(&p->fd, p->fd, mchunkptr);
/* Slightly streamlined version of consolidation code in free() */
size = chunksize (p);
@@ -4896,8 +4927,10 @@ int_mallinfo (mstate av, struct mallinfo *m)
for (i = 0; i < NFASTBINS; ++i)
{
- for (p = fastbin (av, i); p != 0; p = p->fd)
+ for (p = fastbin (av, i); p != 0; p = REVEAL_PTR(&p->fd, p->fd,
mchunkptr))
{
+ if (__glibc_unlikely(!aligned_OK(p)))
+ malloc_printerr ("int_mallinfo(): un-aligned fastbin
chunk detected");
++nfastblocks;
fastavail += chunksize (p);
}
@@ -5437,8 +5470,10 @@ __malloc_info (int options, FILE *fp)
while (p != NULL)
{
+ if (__glibc_unlikely(!aligned_OK(p)))
+ malloc_printerr ("__malloc_info(): un-aligned fastbin
chunk detected");
++nthissize;
- p = p->fd;
+ p = REVEAL_PTR(&p->fd, p->fd, mchunkptr);
}
fastavail += nthissize * thissize;
--
2.17.1
^ permalink raw reply [flat|nested] 33+ messages in thread
end of thread, other threads:[~2020-10-31 15:28 UTC | newest]
Thread overview: 33+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-03-19 13:32 [PATCH] Add Safe-Linking to fastbins and tcache Wilco Dijkstra
2020-03-19 15:09 ` Eyal Itkin
2020-03-19 18:15 ` Eyal Itkin
2020-03-20 0:10 ` Wilco Dijkstra
2020-03-20 2:49 ` Carlos O'Donell
2020-03-20 2:53 ` DJ Delorie
2020-03-20 9:35 ` Eyal Itkin
2020-03-20 18:00 ` Adhemerval Zanella
2020-03-20 19:45 ` Eyal Itkin
2020-03-20 23:58 ` DJ Delorie
2020-03-21 2:47 ` Carlos O'Donell
2020-03-23 13:52 ` Adhemerval Zanella
2020-03-23 16:11 ` DJ Delorie
2020-03-23 16:23 ` Carlos O'Donell
2020-03-23 16:26 ` Adhemerval Zanella
2020-03-24 13:44 ` Wilco Dijkstra
2020-03-29 17:04 ` Carlos O'Donell
2020-03-30 6:30 ` Eyal Itkin
2020-03-30 7:56 ` Andreas Schwab
2020-03-30 8:01 ` Andreas Schwab
2020-03-30 8:44 ` Eyal Itkin
2020-03-30 13:56 ` Carlos O'Donell
2020-03-30 17:19 ` Eyal Itkin
2020-10-31 13:33 ` H.J. Lu
2020-10-31 14:49 ` Eyal Itkin
2020-10-31 15:27 ` H.J. Lu
-- strict thread matches above, loose matches on Subject: below --
2020-02-02 9:43 Eyal Itkin
2020-02-03 18:10 ` Carlos O'Donell
2020-02-03 19:48 ` Eyal Itkin
2020-03-05 1:19 ` Eyal Itkin
2020-03-05 3:30 ` Carlos O'Donell
2020-03-18 21:28 ` Carlos O'Donell
2020-03-19 6:41 ` Eyal Itkin
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).