[PATCH] Add Safe-Linking to fastbins and tcache
Eyal Itkin
eyal.itkin@gmail.com
Fri Mar 20 19:45:22 GMT 2020
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Add-Safe-Linking-to-fastbins-and-tcache.patch
Type: application/octet-stream
Size: 9242 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20200320/bfe1c6f0/attachment.obj>
More information about the Libc-alpha
mailing list