6 ms·

Linux kernel heap quarantine versus use-after-free exploits

119 points by kmwyard 6y ago

SCHiM 6y ago
I'm quite impressed with Windows 10's userland heap randomization. I never do any work on Linux, and especially not in the kernel. But maybe the authors can take some inspiration from the work there? https://www.blackhat.com/docs/us-16/materials/us-16-Yason-Windows-10-Segment-Heap-Internals-wp.pdf https://www.blackhat.com/docs/us-16/materials/us-16-Yason-Wi... https://www.blackhat.com/docs/us-16/materials/us-16-Yason-Windows-10-Segment-Heap-Internals.pdf https://www.blackhat.com/docs/us-16/materials/us-16-Yason-Wi... It's still not perfect, given the predictable nature of block coalescence. But it's quite a departure from the old manager.
- saagarjha 6y ago
  The Windows heap seems to have fairly straightforward security features; there doesn't seem to be a lot of randomization other than the heap base. Did I miss something in those two documents?
  - SCHiM 6y ago
    After 18 allocations on the backend allocator LFH will kick in. The LFH will randomize returned chunks of the same size, doesn't matter if they were freed in the meantime or not. That makes it hard to exploit, you need to groom the heap before LFH kicks in because afterwards the unpredictability becomes too large. If you change the size of your request you will go either to another bucket or the backend allocator. So that makes type confusions slightly harder if you don't control variably sized buffers. Even before those 18 allocations, the specific tricks that used to work on the old manager, which is very similar to the behavior of linux kernel apparently, no longer work. It used to be that you could reliably get the same memory address if you allocated a same sized structure immediately after freeing another. But that no longer works. The only technique that I currently know of is that the merging of free blocks on the backend allocator is still deterministic. But to use that you must be sure your target has not already triggered LFH for the sizes that you're using while grooming.
- klodolph 6y ago
  Linux has had this a little longer, since 2005 or so: https://en.wikipedia.org/wiki/Address_space_layout_randomization https://en.wikipedia.org/wiki/Address_space_layout_randomiza... However, even if the “heap is randomized”, that typically just means that the underlying blocks of memory (e.g. what mmap returns) have randomized virtual addresses. The allocator you use will still have to carve up those blocks from the OS—your kernel does not provide malloc(), after all.
  - jacobush 6y ago
    Maybe it should.
    - im3w1l 6y ago
      I think the current design comes from the fact that calling the kernel is expensive so it's best not to do it too often. Maybe with the new ways of interacting with the kernel, like io_uring it can be cheaper.
      - pritambaral 6y ago
        Well, io_uring is cheaper (significantly!) precisely because its for async operations, which can be pipelined. Application logic almost never uses malloc() in asynchronous, pipelineable fashion.
        jacobush 6y ago
        I’d argue that’s exactly what happens, especially during object initialisation in C++.
      - jacobush 6y ago
        Still, it would eliminate a whole class of bugs, even with insecure languages such as C.
        tsimionescu 6y ago
- mehrdadn 6y ago
  Wow, I didn't realize they've introduced a newer heap implementation (seems to be in Windows 10 version 2004). For anyone else wondering, it seems to be possible to turn on via a manifest: https://chromium.googlesource.com/chromium/src/+/1a9f684dad2f2620c5b88b3cea41c87143cd3c28%5E%21/#F2 https://chromium.googlesource.com/chromium/src/+/1a9f684dad2... Now I'm curious if there's any way to turn it on dynamically from inside a traditional Win32 process.
  - delfinom 6y ago
    Nope. It's been requested though https://github.com/microsoft/WinDev/issues/39 https://github.com/microsoft/WinDev/issues/39 You can also just edit the embedded manifest of traditional win32 processes as a hack before runtime :/
sargun 6y ago
Jann Horn is a genius. The sheer amount of productivity he has is off the charts.
- rurban 6y ago
  Sure. But this is Alex Popov's work
  - appleflaxen 6y ago
    Yet the accolades are not misplaced, when calling out a particular contribution > And the main kudos go to Jann Horn, who reviewed the > security properties of my slab quarantine mitigation and > created a counter-attack that re-enabled UAF exploitation > in the Linux kernel.
sanxiyn 6y ago
Kernel should adopt something like Chromium's PartitionAlloc. Jann's idea about type is basically the same idea. https://chromium.googlesource.com/chromium/src/+/refs/heads/master/base/allocator/partition_allocator/PartitionAlloc.md https://chromium.googlesource.com/chromium/src/+/refs/heads/...
- bennofs 6y ago
  How is that different from the different caches already present in the linux kernel? For example, `struct cred` is always allocated in the `cred_jar` cache and nothing else goes there.
  - sanxiyn 6y ago
    Oh, I wasn't aware. Yes, it's the same thing.
LockAndLol 6y ago
Respect for publishing the results of something that didn't work. Now somebody will be able to either look for another type of solution or try to improve this one without wasting time on reimplementing the same thing again. Good job. If I'm not mistaken, science publishing doesn't work like this. Only good results are published - successful failures aren't.
Foxboron 6y ago
Correct me if I'm wrong, but I believe Kees Cook has been livestreaming some of the patch reviews of this work on Twitch. https://www.twitch.tv/keescook https://www.twitch.tv/keescook Past recordings can be found on youtube: https://www.youtube.com/channel/UC6zmTkbgwe2q6l6TNjABSCg/videos https://www.youtube.com/channel/UC6zmTkbgwe2q6l6TNjABSCg/vid... EDIT: I realized it's mentioned in the blog post! But more airtime doesn't hurt :)
ori_b 6y ago
This sounds a lot like what OpenBSD malloc has been doing, but via a different mechanism. OpenBSD malloc also tries to avoid handing out the same memory after a free. https://ftp.openbsd.org/papers/eurobsdcon2009/otto-malloc.pdf https://ftp.openbsd.org/papers/eurobsdcon2009/otto-malloc.pd...

119 points by kmwyard 6y ago

I'm quite impressed with Windows 10's userland heap randomization. I never do any work on Linux, and especially not in the kernel. But maybe the authors can take some inspiration from the work there? https://www.blackhat.com/docs/us-16/materials/us-16-Yason-Windows-10-Segment-Heap-Internals-wp.pdf https://www.blackhat.com/docs/us-16/materials/us-16-Yason-Wi... https://www.blackhat.com/docs/us-16/materials/us-16-Yason-Windows-10-Segment-Heap-Internals.pdf https://www.blackhat.com/docs/us-16/materials/us-16-Yason-Wi... It's still not perfect, given the predictable nature of block coalescence. But it's quite a departure from the old manager.

saagarjha 6y ago
The Windows heap seems to have fairly straightforward security features; there doesn't seem to be a lot of randomization other than the heap base. Did I miss something in those two documents?
- SCHiM 6y ago
  After 18 allocations on the backend allocator LFH will kick in. The LFH will randomize returned chunks of the same size, doesn't matter if they were freed in the meantime or not. That makes it hard to exploit, you need to groom the heap before LFH kicks in because afterwards the unpredictability becomes too large. If you change the size of your request you will go either to another bucket or the backend allocator. So that makes type confusions slightly harder if you don't control variably sized buffers. Even before those 18 allocations, the specific tricks that used to work on the old manager, which is very similar to the behavior of linux kernel apparently, no longer work. It used to be that you could reliably get the same memory address if you allocated a same sized structure immediately after freeing another. But that no longer works. The only technique that I currently know of is that the merging of free blocks on the backend allocator is still deterministic. But to use that you must be sure your target has not already triggered LFH for the sizes that you're using while grooming.
klodolph 6y ago
Linux has had this a little longer, since 2005 or so: https://en.wikipedia.org/wiki/Address_space_layout_randomization https://en.wikipedia.org/wiki/Address_space_layout_randomiza... However, even if the “heap is randomized”, that typically just means that the underlying blocks of memory (e.g. what mmap returns) have randomized virtual addresses. The allocator you use will still have to carve up those blocks from the OS—your kernel does not provide malloc(), after all.
- jacobush 6y ago
  Maybe it should.
  - im3w1l 6y ago
    I think the current design comes from the fact that calling the kernel is expensive so it's best not to do it too often. Maybe with the new ways of interacting with the kernel, like io_uring it can be cheaper.
    - pritambaral 6y ago
      Well, io_uring is cheaper (significantly!) precisely because its for async operations, which can be pipelined. Application logic almost never uses malloc() in asynchronous, pipelineable fashion.
      - jacobush 6y ago
        I’d argue that’s exactly what happens, especially during object initialisation in C++.
    - jacobush 6y ago
      Still, it would eliminate a whole class of bugs, even with insecure languages such as C.
      - tsimionescu 6y ago
mehrdadn 6y ago
Wow, I didn't realize they've introduced a newer heap implementation (seems to be in Windows 10 version 2004). For anyone else wondering, it seems to be possible to turn on via a manifest: https://chromium.googlesource.com/chromium/src/+/1a9f684dad2f2620c5b88b3cea41c87143cd3c28%5E%21/#F2 https://chromium.googlesource.com/chromium/src/+/1a9f684dad2... Now I'm curious if there's any way to turn it on dynamically from inside a traditional Win32 process.
- delfinom 6y ago
  Nope. It's been requested though https://github.com/microsoft/WinDev/issues/39 https://github.com/microsoft/WinDev/issues/39 You can also just edit the embedded manifest of traditional win32 processes as a hack before runtime :/

sargun 6y ago

Jann Horn is a genius. The sheer amount of productivity he has is off the charts.

rurban 6y ago
Sure. But this is Alex Popov's work
- appleflaxen 6y ago
  Yet the accolades are not misplaced, when calling out a particular contribution > And the main kudos go to Jann Horn, who reviewed the > security properties of my slab quarantine mitigation and > created a counter-attack that re-enabled UAF exploitation > in the Linux kernel.

sanxiyn 6y ago

Kernel should adopt something like Chromium's PartitionAlloc. Jann's idea about type is basically the same idea. https://chromium.googlesource.com/chromium/src/+/refs/heads/master/base/allocator/partition_allocator/PartitionAlloc.md https://chromium.googlesource.com/chromium/src/+/refs/heads/...

bennofs 6y ago
How is that different from the different caches already present in the linux kernel? For example, `struct cred` is always allocated in the `cred_jar` cache and nothing else goes there.
- sanxiyn 6y ago
  Oh, I wasn't aware. Yes, it's the same thing.

LockAndLol 6y ago

Respect for publishing the results of something that didn't work. Now somebody will be able to either look for another type of solution or try to improve this one without wasting time on reimplementing the same thing again. Good job. If I'm not mistaken, science publishing doesn't work like this. Only good results are published - successful failures aren't.

Foxboron 6y ago

Correct me if I'm wrong, but I believe Kees Cook has been livestreaming some of the patch reviews of this work on Twitch. https://www.twitch.tv/keescook https://www.twitch.tv/keescook Past recordings can be found on youtube: https://www.youtube.com/channel/UC6zmTkbgwe2q6l6TNjABSCg/videos https://www.youtube.com/channel/UC6zmTkbgwe2q6l6TNjABSCg/vid... EDIT: I realized it's mentioned in the blog post! But more airtime doesn't hurt :)

ori_b 6y ago

This sounds a lot like what OpenBSD malloc has been doing, but via a different mechanism. OpenBSD malloc also tries to avoid handing out the same memory after a free. https://ftp.openbsd.org/papers/eurobsdcon2009/otto-malloc.pdf https://ftp.openbsd.org/papers/eurobsdcon2009/otto-malloc.pd...