[uclibc-ng-devel] Add Safe-Linking to Fast-Bins

Safe-Linking is a security mechanism that protects single-linked
lists (such as the fastbins) 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 bits
in the PAGE_SHIFT position), will be merged with the 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 attacker will directly fail 7
out of 8 times, and on 64 bit machines it will fail 15 out of 16
times.

The proposed solution adds 3-4 asm instructions per malloc()/free()
and therefore has only minor performance implications if it has
any. A similar protection was added to Chromium's version of TCMalloc
in 2013, and according to their documentation the performance overhead
was less than 2%.

For more information, feel free to check out our White Paper which can be
found here:
https://github.com/gperftools/gperftools/files/4023520/Safe-Linking-White-Paper.txt
---
 libc/stdlib/malloc-standard/free.c     |  5 +++--
 libc/stdlib/malloc-standard/mallinfo.c |  3 ++-
 libc/stdlib/malloc-standard/malloc.c   |  6 ++++--
 libc/stdlib/malloc-standard/malloc.h   | 12 ++++++++++++
 4 files changed, 21 insertions(+), 5 deletions(-)

   morecore_properties is a status word holding dynamically discovered
--
2.17.1

Hi,
Eyal Itkin wrote,

> Safe-Linking is a security mechanism that protects single-linked
> lists (such as the fastbins) 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.

The patch does not apply with git am ontop of uClibc-ng master.
What mail client do you use and could you try to use git
format-patch -s origin and send an e-Mail with the patch as
attachment so it does not get corrupted somehow.

best regards
 Waldemar

Hi,

Sorry for the formatting problem, I'm having trouble sending each open
source project the patch in their own format, and I probably mixed up
something.
The patch is now attached to this email.

In addition, I also attached the White Paper that describes this new
security mitigation.

Just as a side note: the patch is signed by eyalit@checkpoint.com but
I'm sending this from eyal.itkin@gmail.com due to mail issues with my
work e-mail (which is connected to my GitHub account).

Thanks again for your cooperation,
Eyal.

On Fri, Feb 14, 2020 at 11:40 AM Waldemar Brodkorb <wbx@uclibc-ng.org> wrote:
>
> Hi,
> Eyal Itkin wrote,
>
> > Safe-Linking is a security mechanism that protects single-linked
> > lists (such as the fastbins) 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.
>
> The patch does not apply with git am ontop of uClibc-ng master.
> What mail client do you use and could you try to use git
> format-patch -s origin and send an e-Mail with the patch as
> attachment so it does not get corrupted somehow.
>
> best regards
>  Waldemar
Safe-Linking - Blocking a 20 Year Old Exploit Primitive:
========================================================
Background:
-----------
From the early days of binary exploitation, the heap internal data
structures have been a prime target for attackers. By understanding
the way the heap malloc() and free() work, attackers were able to
leverage an initial vulnerability in a heap buffer, such as a linear
buffer overflow, into a stronger exploit primitive such as an
Arbitrary-Write.

One such detailed example is the Phrack article from 2001, "Vudo Malloc
Tricks" (http://phrack.org/issues/57/8.html). This article details the
internals of multiple heap implementations, and describes what is now
called "Unsafe-Unlinking." Attackers that modify the FD and BK pointers
of double-linked lists (such as the small bins for example) can use the
unlink() operation to trigger an Arbitrary-Write, and thus achieve code
execution over the target program.

And indeed, Glibc version 2.3.6 from 2005 embedded a fix to this known
exploit primitive  called "Safe-Unlinking." This elegant fix verifies
the integrity of the double-linked node before unlinking it from the
list, by checking that:

	p->FD->BK == p.

While this exploit primitive was blocked more than 14 years ago, at the
time no one came up with a similar solution to protect the pointers of
the single-linked lists. Leveraging this weak spot, attackers shifted
their focus to these unprotected single-linked lists such as fastbins,
and currently also tcache.

In 2013, Chromium integrated a new functionality dubbed "MaskPtr()",
which went relatively unnoticed. In the next section we will describe
our variant for this functionality, and the reasons behind it.

Introducing Safe-Linking:
-------------------------
In this white paper, we present a security mechanism to close this
almost 20 year old security gap. Safe-Linking is a security mechanism
to protect single-linked lists (such as the fastbins and tcache) from
tampering by attackers. The mechanism makes use of randomness from the
Address Space Layout Randomization (ASLR) that is now heavily deployed
in most modern operating systems to "sign" the list's pointers. When
combined with chunk alignment integrity checks, this new technique
protects the pointers from hijacking attempts.

Our solution protects against 3 common attacks regularly used in modern
day exploits:
  * Partial pointer override: Modifying the lower bytes (Little Endian).
  * Full pointer override: Hijacking the pointer to a chosen location.
  * Unaligned chunks: Pointing the list to an unaligned address.

Threat Modeling:
----------------
In our threat model, the attacker has the following capabilities:
* Controlled linear buffer overflow / underflow over a heap buffer.
* Relative Arbitrary-Write over a heap buffer.

It’s important to note that our attacker doesn't know where the heap is
located, as the heap's base address is randomized together with the
mmap_base by the ASLR (more on this topic on the next section).

Our solution raises the bar and blocks our attacker's heap-based
exploit attempts. Once deployed, attackers must have an additional
capability in the form of heap-leak / pointer-leak to be able to
successfully build an exploit.

An example scenario for our protection is a position-dependent binary
(loads without ASLR) that has a heap overflow when parsing incoming
user input. Until now, an attacker was able to exploit such targets
without any heap leak, and with only minimal control over the heap's
allocations, by depending solely on the fixed addresses of the binary
itself. We block such exploit attempts, and leverage the heap's ASLR to
gain randomness when redirecting heap allocations to fixed addresses in
such target binaries.

Protection:
-----------
On Linux machines, the heap is randomized via mmap_base which follows
the following logic:

	random_base = ((1 << rndbits) - 1) << PAGE_SHIFT)
	
While "rndbit" defaults to 8 on 32 bit Linux machines, and 28 on 64 bit
machines.

We denote the address in which the single-linked list pointer is stored
at as L. We now define the following calculation:

	Mask := (L >> PAGE_SHIFT)

According to the ASLR formula shown above, the shift positions the
first random bits from the memory address right at the LSBit of the
mask itself.

This leads us to our protection scheme. We denote the single-linked
list pointer with P and see how the scheme looks:
  * PROTECT(P) := (L >> PAGE_SHIFT) XOR (P)
  * *L = PROTECT(P)
  
Or in it's code version:

#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)

This way, the random bits from the address L are placed on top the LSB
of the stored protected pointer. This protection layer prevents an
attacker without the knowledge of the random ASLR bits from modifying
the pointer to a controlled value.

However, if you paid attention, you can easily see that we are at a
disadvantage against the "Safe-Unlinking" mechanism. In our solution,
the attacker can't properly hijack the pointer. However, we are also
limited as we can't check if a pointer modification occurred. This is
where an additional check takes place.

All allocated chunks in the heap are aligned to a known offset which is
usually 8 bytes on 32 bit machines, and 16 on 64 bit machines. By
checking that each "reveal()ed" pointer is aligned accordingly, we add
two important layers:
  * Attackers must correctly guess the alignment bits.
  * Attackers can't point chunks to unaligned memory addresses.
  
On 64 bit machines, this statistical protection causes an attack
attempt to fail 15 out of 16 times.

Even on its own, this alignment check prevents known exploit
primitives, such as the one described in:
https://quentinmeffre.fr/exploit/heap/2018/11/02/fastbin_attack.html

Example Implementation:
-----------------------
Here is a snippet from the proposed patched version from glibc 2.30:

 tcache_put (...)
 {
   ...
-  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]);
 }

 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(((size_t)e) & MALLOC_ALIGN_MASK))
+    malloc_printerr ("malloc(): un-aligned tcache chunk detected");
   return (void *) e;
 }
 
Benchmarking:
-------------
Benchmarking showed that the added code sums up to 2-3 asm instructions
for free() and 3-4 asm instructions for malloc(). On Glibc, the change
was negligible and wasn't measurable even when summing up 1 billion (!)
malloc()/free() operations on a single vCPU in GCP. The tests were made
on a 64 bit version of the library. The worst impact on TCMalloc's
benchmarking tests was 1.5%, while the average was a mere 0.02%.

These benchmarking results are due to the slim design of the proposed
mechanism:
  * The protection has no memory overhead.
  * The protection needs no initialization.
  * No special source of randomness is needed.
  * The protection uses only L and P which are both present at the time
    the pointer needs to be protect()ed or reveal()ed.
  
It is important to note, and is detailed in glibc's documentation, that
both the fastbins and the tcache use single-linked list to hold data.
They only support the put/get API, and no common functionality will
traverse the entire list and keep it intact.

While such functionality does exist, it is only used for gathering
malloc statistics (mallinfo), and so the added overhead for accessing
the single-linked pointer is negligible.

Revisiting our Threat Model:
----------------------------
The alignment check reduces the attack surface and mandates that a
fastbin or a tcache chunk points to an aligned memory address. This
directly blocks known exploit variants, as mentioned above.

Just like Safe-Unlinking (for double-linked lists), our protection
relies on the fact that the attacker doesn't know what legitimate
heap pointers look like. An attacker that can forge a memory struct
and knows what a valid heap pointer looks like can successfully forge
a valid FD/BK pointers that won't trigger an Arbitrary-Write primitive,
but will allow for a chunk at an attacker-controlled address. An
attacker without a pointer leak won't be able to fully control an
overridden pointer, due to the protection layer that relies on the
randomness inherited from the deployed ASLR.

The proposed PAGE_SHIFT places the random bits right over the first bit
of the stored pointer. Together with the alignment check, this
statistically blocks attackers from changing even the lowest bit / byte
(Little Endian) of the stored single-linked pointer.

Back to Chromium's MaskPtr():
-----------------------------
In 2013, Chromium added a similar functionality dubbed "MaskPtr()" to
be used only when the free list (FL) is a double-linked list. In their
variant, the code is as follows:

inline void* MaskPtr(void* p) {
  // Maximize ASLR entropy and guarantee the result is an invalid address.
  const uintptr_t mask =
      ~(reinterpret_cast<uintptr_t>(TCMalloc_SystemAlloc) >> 13);
  return reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(p) ^ mask);
}

We can see that they use a random pointer from the code section, and
not a heap location as is used in our implementation. In addition, they
shift the address by the hard coded value 13, and also invert the bits
of their mask. As we failed to find the documentation for their design
choices, we can read from the code that the bit inversion is used to
guarantee the result will be an invalid address.

Compared to our design, Chromium's implementation implies an additional
memory reference (to the code function) and an additional asm
instruction for the bit flipping. Not only so, their pointer masking
is used without the additional alignment check, therefore the code
can't catch in advance a pointer modification without crashing the
process.

Integration:
------------
We implemented, and tested the patches for successfully integrating the
proposed mitigation to the latest versions of glibc (ptmalloc), uClibc
(dlmalloc) and gperftools (TCMalloc). In addition, we also pointed
Chromium's development team to our version of Safe-Linking as was
submitted to gperftools, and we hope it will be included in all of
their free list (FL) implementations.

We believe that integrating Safe-Linking to these 3 dominant
libraries will lead to a wider adoption by other libraries, both in the
open source community and in closed source software in the industry.
The fact that a basic version of Safe-Linking was already embedded into
Chromium since 2013, proves the maturity of this solution.

Final Note:
-----------
Safe-Linking is not a magic bullet that will stop all exploit attempts
against modern day heap implementations. However, this is another step
in the right direction. By forcing an attacker to have a pointer leak
vulnerability before he can even start his heap-based exploit, we
gradually raise the bar.

From our past experience, this specific mitigation would have blocked
several major exploits that we have implemented throughout the years,
thus turning "broken" software products to "unexploitable" (at least
with the vulnerabilities we had at the time of the respective research
projects).

It is also important to note that our solution isn't limited only to
heap implementations. It also enables endangered data structures, with
single-linked list pointers that are located near user buffers, to get
integrity protection without any additional memory overhead, and with a
negligible run-time impact. The solution is easily extendable to every
single-linked list in a system with ASLR.

Hi,

Shouldn't this be a config option, since there is a performance hit?
On most embedded architectures the heap is in a fixed position, so the
there is
no randomness to extract from ASLR, thus they are only left with the
performance overhead.

Best regards,
Kjetil Oftedal


On Sun, 16 Feb 2020 at 07:02, Eyal Itkin <eyal.itkin@gmail.com> wrote:

> Hi,
>
> Sorry for the formatting problem, I'm having trouble sending each open
> source project the patch in their own format, and I probably mixed up
> something.
> The patch is now attached to this email.
>
> In addition, I also attached the White Paper that describes this new
> security mitigation.
>
> Just as a side note: the patch is signed by eyalit@checkpoint.com but
> I'm sending this from eyal.itkin@gmail.com due to mail issues with my
> work e-mail (which is connected to my GitHub account).
>
> Thanks again for your cooperation,
> Eyal.
>
> On Fri, Feb 14, 2020 at 11:40 AM Waldemar Brodkorb <wbx@uclibc-ng.org>
> wrote:
> >
> > Hi,
> > Eyal Itkin wrote,
> >
> > > Safe-Linking is a security mechanism that protects single-linked
> > > lists (such as the fastbins) 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.
> >
> > The patch does not apply with git am ontop of uClibc-ng master.
> > What mail client do you use and could you try to use git
> > format-patch -s origin and send an e-Mail with the patch as
> > attachment so it does not get corrupted somehow.
> >
> > best regards
> >  Waldemar
> _______________________________________________
> devel mailing list
> devel@uclibc-ng.org
> https://mailman.uclibc-ng.org/cgi-bin/mailman/listinfo/devel
>

We benchmarked it on glibc and the overhead wasn't even measurable. In
addition, the average overhead on TCMalloc's testsuite was 0.02%, so the
impact is quite negligible.

We've just finished a research when uClibc was used on a Linux OS and there
was ASLR for the heap. This protection would have blocked our exploit
completely, if it was already deployed.

I agree that on operating systems without ASLR, there isn't any added value
for this protection. If there is some way do automatically enable it for
ASLR enabled OSes it would be the preferred method. From my experience when
security is not opt-in by default, it never gets activated.

On Sun, 16 Feb 2020, 10:10 Kjetil Oftedal, <oftedal@gmail.com> wrote:

> Hi,
>
> Shouldn't this be a config option, since there is a performance hit?
> On most embedded architectures the heap is in a fixed position, so the
> there is
> no randomness to extract from ASLR, thus they are only left with the
> performance overhead.
>
> Best regards,
> Kjetil Oftedal
>
>
> On Sun, 16 Feb 2020 at 07:02, Eyal Itkin <eyal.itkin@gmail.com> wrote:
>
>> Hi,
>>
>> Sorry for the formatting problem, I'm having trouble sending each open
>> source project the patch in their own format, and I probably mixed up
>> something.
>> The patch is now attached to this email.
>>
>> In addition, I also attached the White Paper that describes this new
>> security mitigation.
>>
>> Just as a side note: the patch is signed by eyalit@checkpoint.com but
>> I'm sending this from eyal.itkin@gmail.com due to mail issues with my
>> work e-mail (which is connected to my GitHub account).
>>
>> Thanks again for your cooperation,
>> Eyal.
>>
>> On Fri, Feb 14, 2020 at 11:40 AM Waldemar Brodkorb <wbx@uclibc-ng.org>
>> wrote:
>> >
>> > Hi,
>> > Eyal Itkin wrote,
>> >
>> > > Safe-Linking is a security mechanism that protects single-linked
>> > > lists (such as the fastbins) 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.
>> >
>> > The patch does not apply with git am ontop of uClibc-ng master.
>> > What mail client do you use and could you try to use git
>> > format-patch -s origin and send an e-Mail with the patch as
>> > attachment so it does not get corrupted somehow.
>> >
>> > best regards
>> >  Waldemar
>> _______________________________________________
>> devel mailing list
>> devel@uclibc-ng.org
>> https://mailman.uclibc-ng.org/cgi-bin/mailman/listinfo/devel
>>
>

I checked in the code, and it looks like the correct macro for
enabling this feature only on Linux will be:
__UCLIBC_LINUX_SPECIFIC__.
Before I send an additional commit for correctly wrapping up this
feature, I just wanted to check with you, is this the correct flag to
be used?

I thought of setting the configuration as follows:
* A global configurable disable flag, that is off by default (I don't
know how to set one, and I will need your assistance)
* if __UCLIBC_LINUX_SPECIFIC__ is not defined, the disable flag will
be automatically defined (in the code level)

This way, the feature will be on by default only on Linux, and it
could be manually turned off by developers. In the future, if it will
be applicable to other environments as well, it will be easier to
modify the second condition accordingly.

Will be happy to hear what you think about this.
Eyal Itkin.

On Sun, Feb 16, 2020 at 10:18 AM Eyal Itkin <eyal.itkin@gmail.com> wrote:
>
> We benchmarked it on glibc and the overhead wasn't even measurable. In addition, the average overhead on TCMalloc's testsuite was 0.02%, so the impact is quite negligible.
>
> We've just finished a research when uClibc was used on a Linux OS and there was ASLR for the heap. This protection would have blocked our exploit completely, if it was already deployed.
>
> I agree that on operating systems without ASLR, there isn't any added value for this protection. If there is some way do automatically enable it for ASLR enabled OSes it would be the preferred method. From my experience when security is not opt-in by default, it never gets activated.
>
> On Sun, 16 Feb 2020, 10:10 Kjetil Oftedal, <oftedal@gmail.com> wrote:
>>
>> Hi,
>>
>> Shouldn't this be a config option, since there is a performance hit?
>> On most embedded architectures the heap is in a fixed position, so the there is
>> no randomness to extract from ASLR, thus they are only left with the performance overhead.
>>
>> Best regards,
>> Kjetil Oftedal
>>
>>
>> On Sun, 16 Feb 2020 at 07:02, Eyal Itkin <eyal.itkin@gmail.com> wrote:
>>>
>>> Hi,
>>>
>>> Sorry for the formatting problem, I'm having trouble sending each open
>>> source project the patch in their own format, and I probably mixed up
>>> something.
>>> The patch is now attached to this email.
>>>
>>> In addition, I also attached the White Paper that describes this new
>>> security mitigation.
>>>
>>> Just as a side note: the patch is signed by eyalit@checkpoint.com but
>>> I'm sending this from eyal.itkin@gmail.com due to mail issues with my
>>> work e-mail (which is connected to my GitHub account).
>>>
>>> Thanks again for your cooperation,
>>> Eyal.
>>>
>>> On Fri, Feb 14, 2020 at 11:40 AM Waldemar Brodkorb <wbx@uclibc-ng.org> wrote:
>>> >
>>> > Hi,
>>> > Eyal Itkin wrote,
>>> >
>>> > > Safe-Linking is a security mechanism that protects single-linked
>>> > > lists (such as the fastbins) 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.
>>> >
>>> > The patch does not apply with git am ontop of uClibc-ng master.
>>> > What mail client do you use and could you try to use git
>>> > format-patch -s origin and send an e-Mail with the patch as
>>> > attachment so it does not get corrupted somehow.
>>> >
>>> > best regards
>>> >  Waldemar
>>> _______________________________________________
>>> devel mailing list
>>> devel@uclibc-ng.org
>>> https://mailman.uclibc-ng.org/cgi-bin/mailman/listinfo/devel