[musl] [PATCH] Add a safe dequeue integrity check for mallocng

[musl] [PATCH] Add a safe dequeue integrity check for mallocng

[James Raphael Tiovalen]

This commit adds an integrity check to allow for safer dequeuing of meta
structs in mallocng. If the unlikely condition is true due to some sort
of heap corruption, we print an error message and abort.

This approach is similar to the safe unlinking check performed by glibc.

While this check would not prevent more sophisticated attacks in more
specific scenarios, as shown by the historical exploitation efforts on
glibc, this check would prevent more basic heap corruption attacks from
being successfully executed.
---
 src/malloc/mallocng/meta.h | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/src/malloc/mallocng/meta.h b/src/malloc/mallocng/meta.h
index 61ec53f9..57946d01 100644
--- a/src/malloc/mallocng/meta.h
+++ b/src/malloc/mallocng/meta.h
@@ -2,9 +2,11 @@
 #define MALLOC_META_H
 
 #include <stdint.h>
+#include <stdio.h>
 #include <errno.h>
 #include <limits.h>
 #include "glue.h"
+#include "libm.h"
 
 __attribute__((__visibility__("hidden")))
 extern const uint16_t size_classes[];
@@ -90,6 +92,10 @@ static inline void queue(struct meta **phead, struct meta *m)
 static inline void dequeue(struct meta **phead, struct meta *m)
 {
 	if (m->next != m) {
+		if (predict_false(m->prev->next != m || m->next->prev != m)) {
+			fprintf(stderr, "Corrupted doubly-linked meta list\n");
+			abort();
+		}
 		m->prev->next = m->next;
 		m->next->prev = m->prev;
 		if (*phead == m) *phead = m->next;
-- 
2.42.0

Re: [musl] [PATCH] Add a safe dequeue integrity check for mallocng

[Rich Felker]

On Sat, Sep 09, 2023 at 01:49:39AM +0800, James Raphael Tiovalen wrote:
> This commit adds an integrity check to allow for safer dequeuing of meta
> structs in mallocng. If the unlikely condition is true due to some sort
> of heap corruption, we print an error message and abort.
> 
> This approach is similar to the safe unlinking check performed by glibc.
> 
> While this check would not prevent more sophisticated attacks in more
> specific scenarios, as shown by the historical exploitation efforts on
> glibc, this check would prevent more basic heap corruption attacks from
> being successfully executed.
> ---
>  src/malloc/mallocng/meta.h | 6 ++++++
>  1 file changed, 6 insertions(+)
> 
> diff --git a/src/malloc/mallocng/meta.h b/src/malloc/mallocng/meta.h
> index 61ec53f9..57946d01 100644
> --- a/src/malloc/mallocng/meta.h
> +++ b/src/malloc/mallocng/meta.h
> @@ -2,9 +2,11 @@
>  #define MALLOC_META_H
>  
>  #include <stdint.h>
> +#include <stdio.h>
>  #include <errno.h>
>  #include <limits.h>
>  #include "glue.h"
> +#include "libm.h"
>  
>  __attribute__((__visibility__("hidden")))
>  extern const uint16_t size_classes[];
> @@ -90,6 +92,10 @@ static inline void queue(struct meta **phead, struct meta *m)
>  static inline void dequeue(struct meta **phead, struct meta *m)
>  {
>  	if (m->next != m) {
> +		if (predict_false(m->prev->next != m || m->next->prev != m)) {
> +			fprintf(stderr, "Corrupted doubly-linked meta list\n");
> +			abort();
> +		}
>  		m->prev->next = m->next;
>  		m->next->prev = m->prev;
>  		if (*phead == m) *phead = m->next;
> -- 
> 2.42.0

This could and should be written with the assert macro, like all the
other safety assertions in mallocng, not pulling in stdio and abort.
But I think you're over-estimating the value of the check here. The
pointers in question are not part of "the heap" but are out-of-band,
intended not to be reachable except by an attacker who already has
arbitrary code execution or at least strong gadgets for modifying
memory they shouldn't with multiple levels of offsetting and
indirection, which could generally be used in lots of other ways to
obtain arbitrary code execution.

Rich

Re: [musl] [PATCH] Add a safe dequeue integrity check for mallocng

[James R T]

On Sat, Sep 9, 2023 at 8:48 AM Rich Felker <dalias@libc.org> wrote:
>
> This could and should be written with the assert macro, like all the
> other safety assertions in mallocng, not pulling in stdio and abort.

Understood. I was not able to find an assert with `predict_false` for
the condition. Should I add one assert function with `predict_false`
in `include/assert.h` or `src/exit/assert.c` or simply use the regular
assert?

> But I think you're over-estimating the value of the check here. The
> pointers in question are not part of "the heap" but are out-of-band,
> intended not to be reachable except by an attacker who already has
> arbitrary code execution or at least strong gadgets for modifying
> memory they shouldn't with multiple levels of offsetting and
> indirection, which could generally be used in lots of other ways to
> obtain arbitrary code execution.

Hmm so from what I understand, the `meta` struct is part of the
"metadata" of the heap which, while technically not part of the heap
itself, contains information about the actual heap memory "chunks". In
an application vulnerable to double-frees or use-after-frees, if an
attacker manages to control the `prev` and `next` pointers by
instructing the application to perform some allocation and free
sequences, they can turn those into an arbitrary write primitive. They
do not have to have arbitrary code execution to do this (and I am not
sure what qualifies as "strong" gadgets here). In fact, an attacker
can use this to gain arbitrary code execution (if the conditions are
right, of course).

There is some additional explanation from this CTF writeup for a DEF
CON CTF 2021 Qualifiers challenge:
https://github.com/cscosu/ctf-writeups/blob/master/2021/def_con_quals/mooosl/README.md

As shown in the writeup, without these integrity checks, attackers
could gain a semi-arbitrary write primitive which could then be
escalated into arbitrary code execution. Sure, adding this check would
not completely prevent such an attack, but it would minimize the
impact as the values that `prev` and `next` can take would be
restricted (and thus, could prevent attackers from obtaining truly
arbitrary write primitives).

While I acknowledge that these sorts of CTF challenges can be somewhat
simplistic, they serve as proofs-of-concept of potential attacks that
could happen in the wild. In my humble opinion, I still think that
this is a significant safety check that should be added to the code.
Do let me know your thoughts about this.

I can send a new version of this patch with the change to assert and
maybe add some more elaboration to the commit message if this seems
agreeable to you.

Best regards,
James Raphael Tiovalen

Re: [musl] [PATCH] Add a safe dequeue integrity check for mallocng

[Joakim Sindholt]

On Thu, 14 Sep 2023 13:13:23 +0800, James R T <jamestiotio@gmail.com> wrote:
> On Sat, Sep 9, 2023 at 8:48 AM Rich Felker <dalias@libc.org> wrote:
> >
> > This could and should be written with the assert macro, like all the
> > other safety assertions in mallocng, not pulling in stdio and abort.
> 
> Understood. I was not able to find an assert with `predict_false` for
> the condition. Should I add one assert function with `predict_false`
> in `include/assert.h` or `src/exit/assert.c` or simply use the regular
> assert?

It's a little confusing but assert() in mallocng is not real assert():
http://git.musl-libc.org/cgit/musl/tree/src/malloc/mallocng/glue.h#n33
The issue is that if memory is under control of an attacker then doing
anything at all, especially running the stdio machinery, is unsafe. To
that end musl uses a_crash() here which expands to a minimal set of
instructions to crash the process:
http://git.musl-libc.org/cgit/musl/tree/arch/x86_64/atomic_arch.h#n106

Furthermore, musl doesn't use any of thosed tagged branch tricks and I
personally doubt it would make any difference.

Re: [musl] [PATCH] Add a safe dequeue integrity check for mallocng

[Rich Felker]

On Thu, Sep 14, 2023 at 11:23:08AM +0200, Joakim Sindholt wrote:
> On Thu, 14 Sep 2023 13:13:23 +0800, James R T <jamestiotio@gmail.com> wrote:
> > On Sat, Sep 9, 2023 at 8:48 AM Rich Felker <dalias@libc.org> wrote:
> > >
> > > This could and should be written with the assert macro, like all the
> > > other safety assertions in mallocng, not pulling in stdio and abort.
> > 
> > Understood. I was not able to find an assert with `predict_false` for
> > the condition. Should I add one assert function with `predict_false`
> > in `include/assert.h` or `src/exit/assert.c` or simply use the regular
> > assert?
> 
> It's a little confusing but assert() in mallocng is not real assert():
> http://git.musl-libc.org/cgit/musl/tree/src/malloc/mallocng/glue.h#n33
> The issue is that if memory is under control of an attacker then doing
> anything at all, especially running the stdio machinery, is unsafe. To
> that end musl uses a_crash() here which expands to a minimal set of
> instructions to crash the process:
> http://git.musl-libc.org/cgit/musl/tree/arch/x86_64/atomic_arch.h#n106

Yes. mallocng is written such that you could use the normal assert
with it, but presently it's just expanding to a_crash(). At some point
this might be revamped to crash with a message string in a particular
register or argument slot or something so that you get a bit more
meaningful information if looking at it in a debugger. And indeed, the
reason not to do any message printing, etc. is that you're running in
a known-compromised process state where any further complex execution
is unsafe (e.g. if the out-of-band malloc metadata was clobbered, the
function pointers in stderr might also have been clobbered, since the
latter are *easier to reach* than the OOB metadata).

> Furthermore, musl doesn't use any of thosed tagged branch tricks and I
> personally doubt it would make any difference.

Yes, the only reason libm.h has them is because nsz is using the code
in other environments that want them, and it made sense to avoid
gratuitous differences. We don't generally use those in musl. If the
compiler isn't generating good code and puts the failure path as a hot
path, we probably should explore whether the compiler is missing that
it's a does-not-return thing (which should always be treated as cold).
But indeed I doubt it makes a difference.

Rich

Re: [musl] [PATCH] Add a safe dequeue integrity check for mallocng

[James R T]

On Thu, Sep 14, 2023 at 5:23 PM Joakim Sindholt <opensource@zhasha.com> wrote:
>
> It's a little confusing but assert() in mallocng is not real assert():
> http://git.musl-libc.org/cgit/musl/tree/src/malloc/mallocng/glue.h#n33
> The issue is that if memory is under control of an attacker then doing
> anything at all, especially running the stdio machinery, is unsafe. To
> that end musl uses a_crash() here which expands to a minimal set of
> instructions to crash the process:
> http://git.musl-libc.org/cgit/musl/tree/arch/x86_64/atomic_arch.h#n106
>
> Furthermore, musl doesn't use any of thosed tagged branch tricks and I
> personally doubt it would make any difference.
>

Ah okay, got it.

On Thu, Sep 14, 2023 at 8:18 PM Rich Felker <dalias@libc.org> wrote:
>
> Yes. mallocng is written such that you could use the normal assert
> with it, but presently it's just expanding to a_crash(). At some point
> this might be revamped to crash with a message string in a particular
> register or argument slot or something so that you get a bit more
> meaningful information if looking at it in a debugger. And indeed, the
> reason not to do any message printing, etc. is that you're running in
> a known-compromised process state where any further complex execution
> is unsafe (e.g. if the out-of-band malloc metadata was clobbered, the
> function pointers in stderr might also have been clobbered, since the
> latter are *easier to reach* than the OOB metadata).
>

Hmm sure, that makes sense.

>
> Yes, the only reason libm.h has them is because nsz is using the code
> in other environments that want them, and it made sense to avoid
> gratuitous differences. We don't generally use those in musl. If the
> compiler isn't generating good code and puts the failure path as a hot
> path, we probably should explore whether the compiler is missing that
> it's a does-not-return thing (which should always be treated as cold).
> But indeed I doubt it makes a difference.
>

Got it. I will send in a new patch to simply use an assertion instead then.

Thank you for the detailed explanations!

Best regards,
James Raphael Tiovalen