5 ms·

I assume the reason why this can happen is because the default implementation of malloc/free doesn't check if the pointer has already been free'ed right? And th

by jtchang 10y ago

I assume the reason why this can happen is because the default implementation of malloc/free doesn't check if the pointer has already been free'ed right? And the reason it doesn't check is because of performance reasons?

coldpie 10y ago
How do you detect a "pointer that has already been freed"?
- aseipp 10y ago
  You overwrite the page you just freed (e.g. point it entirely to a fixed page of junk bytes) or mark it as PROT_NONE immediately upon free().
- mikeash 10y ago
  You could keep a separate list of all live allocations. If free() is called with a pointer that's not on the list, it's an error. This won't immediately detect the case where you free, something else mallocs in that exact spot, and then you free again. It will eventually catch it when the something else tries to call free. It will catch cases where the second free call happens before the memory is reused, or when the memory is reused but the new chunk starts earlier. I assume this isn't done because maintaining and checking the list would cost too much.
  - xenadu02 10y ago
    If the bookkeeping weren't so massive you could cycle through the entire 64-bit address space before re-issuing the same memory address. That would be similar to a bump allocator; once all the allocations on a page were freed you could unmap it so except for pathological cases you couldn't explode the number of page table entries too horribly. At 1 TB/sec of allocations it would take 500 years to reach the end of the 64-bit address space in the kernel. (It's actually 544 years ignoring leap years and leap seconds, but subtract 44 years for reserved address ranges). The benefit would be making it impossible to use-after-free because the same address would never be re-used.
    - majewsky 10y ago
      The problem isn't the bookkeeping. It's the massive implicit memory leak that you get when there's only one 4-byte allocation left on your 4-KB page.
      - mikeash 10y ago
        One might reasonably describe the 4kB granularity of virtual memory as bookkeeping overhead, although it's probably not what people would usually think of if they heard that.
      - xenadu02 10y ago
        That's what I meant by "except for pathological cases". Existing memory allocators have the same problems with fragmentation.
- twoodfin 10y ago
  The answer to every problem in computer science is another level of indirection. Pointers point to descriptors that point to allocations. Of course, you can't dynamically manage descriptors without reintroducing the same problem, but the answer to every problem in computer science...
aseipp 10y ago
You can take a variety of approaches to fighting this but basically, TL;DR yes, it'll cost you somewhere. OpenBSD's malloc implementation for example actually will let you enable an option that instead marks unused pages in the freelist maintained by malloc as PROT_NONE, i.e. reuse of a page will cause a segfault. However, there are just various tradeoffs here. For example, OpenBSD's malloc does not guarantee that a `free` will immediately cause a freelist entry to become unused (AFAICS reading the man page -- option `F` vs `U`). So it will not immediately be marked as PROT_NONE, but only once a number of unused entries get 'flushed'. This is (presumably) an optimization so malloc can keep unused chunks around for quick-reuse, without having to do remappings. In the case of the Linux kernel, obviously it is using a different allocator, but the same basic ideas apply. For a protection against this particular exploit, you can look to grsecurity. In particular, I believe PAX_MEMORY_SANITIZE nullifies the major attack vector of this bug, immediately -- as it frees/erases all unused slab/memory pages immediately. If a page or object that is freed contains a pointer (i.e. the traditional mode of attack requires some pointer dereference, instead pointing to attacker-controlled code) -- this will trip PAX_MEMORY_SANITIZE as use of a freed pointer, and kill the kernel task. Other techniques for exploiting this are probably handled by similar defenses. (So I think this is like, kernel exploit #93,234,893 stopped immediately by a grsecurity feature?) EDIT: mikeash also points out another good bit I forgot, which is that the basic defenses don't immediately catch a kind of 'ABA-style' double free. e.g. you free, something else gets the allocation instantly after, then you cause another free again. You'll only crash later. But nullifying the attack vector is what's really important here, which is: you need to stop this from extending into an (almost arbitrary) read/write vector.
Paul-ish 10y ago
I'm not sure it would catch all the double free errors anyway. Imagine a case where we have x_1 = malloc(n) free(x_1) ... x_2 = malloc(n) // malloc returns the same address as x_1, ie x_1 == x_2 ... free(x_1) ... example_function(x_2) How would the runtime know the difference between a double free of x_1 and freeing x_1 then later x_2? And now we think x_2 points to valid data when it doesn't, which can lead to a use after free error.

by jtchang 10y ago

coldpie 10y ago

How do you detect a "pointer that has already been freed"?

aseipp 10y ago
You overwrite the page you just freed (e.g. point it entirely to a fixed page of junk bytes) or mark it as PROT_NONE immediately upon free().
mikeash 10y ago
You could keep a separate list of all live allocations. If free() is called with a pointer that's not on the list, it's an error. This won't immediately detect the case where you free, something else mallocs in that exact spot, and then you free again. It will eventually catch it when the something else tries to call free. It will catch cases where the second free call happens before the memory is reused, or when the memory is reused but the new chunk starts earlier. I assume this isn't done because maintaining and checking the list would cost too much.
- xenadu02 10y ago
  If the bookkeeping weren't so massive you could cycle through the entire 64-bit address space before re-issuing the same memory address. That would be similar to a bump allocator; once all the allocations on a page were freed you could unmap it so except for pathological cases you couldn't explode the number of page table entries too horribly. At 1 TB/sec of allocations it would take 500 years to reach the end of the 64-bit address space in the kernel. (It's actually 544 years ignoring leap years and leap seconds, but subtract 44 years for reserved address ranges). The benefit would be making it impossible to use-after-free because the same address would never be re-used.
  - majewsky 10y ago
    The problem isn't the bookkeeping. It's the massive implicit memory leak that you get when there's only one 4-byte allocation left on your 4-KB page.
    - mikeash 10y ago
      One might reasonably describe the 4kB granularity of virtual memory as bookkeeping overhead, although it's probably not what people would usually think of if they heard that.
    - xenadu02 10y ago
      That's what I meant by "except for pathological cases". Existing memory allocators have the same problems with fragmentation.
twoodfin 10y ago
The answer to every problem in computer science is another level of indirection. Pointers point to descriptors that point to allocations. Of course, you can't dynamically manage descriptors without reintroducing the same problem, but the answer to every problem in computer science...

aseipp 10y ago

You can take a variety of approaches to fighting this but basically, TL;DR yes, it'll cost you somewhere. OpenBSD's malloc implementation for example actually will let you enable an option that instead marks unused pages in the freelist maintained by malloc as PROT_NONE, i.e. reuse of a page will cause a segfault. However, there are just various tradeoffs here. For example, OpenBSD's malloc does not guarantee that a `free` will immediately cause a freelist entry to become unused (AFAICS reading the man page -- option `F` vs `U`). So it will not immediately be marked as PROT_NONE, but only once a number of unused entries get 'flushed'. This is (presumably) an optimization so malloc can keep unused chunks around for quick-reuse, without having to do remappings. In the case of the Linux kernel, obviously it is using a different allocator, but the same basic ideas apply. For a protection against this particular exploit, you can look to grsecurity. In particular, I believe PAX_MEMORY_SANITIZE nullifies the major attack vector of this bug, immediately -- as it frees/erases all unused slab/memory pages immediately. If a page or object that is freed contains a pointer (i.e. the traditional mode of attack requires some pointer dereference, instead pointing to attacker-controlled code) -- this will trip PAX_MEMORY_SANITIZE as use of a freed pointer, and kill the kernel task. Other techniques for exploiting this are probably handled by similar defenses. (So I think this is like, kernel exploit #93,234,893 stopped immediately by a grsecurity feature?) EDIT: mikeash also points out another good bit I forgot, which is that the basic defenses don't immediately catch a kind of 'ABA-style' double free. e.g. you free, something else gets the allocation instantly after, then you cause another free again. You'll only crash later. But nullifying the attack vector is what's really important here, which is: you need to stop this from extending into an (almost arbitrary) read/write vector.

Paul-ish 10y ago

I'm not sure it would catch all the double free errors anyway. Imagine a case where we have x_1 = malloc(n) free(x_1) ... x_2 = malloc(n) // malloc returns the same address as x_1, ie x_1 == x_2 ... free(x_1) ... example_function(x_2) How would the runtime know the difference between a double free of x_1 and freeing x_1 then later x_2? And now we think x_2 points to valid data when it doesn't, which can lead to a use after free error.