[PATCH] Add Safe-Linking to fastbins and tcache
Adhemerval Zanella
adhemerval.zanella@linaro.org
Fri Mar 20 18:00:14 GMT 2020
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
More information about the Libc-alpha
mailing list