6 ms·

At what level are you looking to cause the crash? Some options: Compiler - insert code and memory usage to show area as free/not-free and check on malloc/free.

At what level are you looking to cause the crash? Some options: Compiler - insert code and memory usage to show area as free/not-free and check on malloc/free. Data has to be recorded at runtime because the type system does not provide enough information to be sure. Static analysis can only guess with C. OS - Every malloc would need to be in a separate page Libc - could do something similar to compiler They all come with overhead in performance and/or memory usage, unless you change the technology stack in some way. Garbage collection is one approach. Adding extra type information to make it clear from static analysis (so you get something like Rust) is another. Or, some hardware support that gives more granular permissions.

viraptor 7y ago
I guess the naive solution would be to walk the freelist/tree on free() to avoid duplicates. I have no idea what the real world impact would be though. Probably very workload-dependent. At least checking for duplicate would be free on insert in a tree, but in a list that's both a long walk and lots of thrashing.
- gpderetta 7y ago
  It would completely defeat the purpose of using a free list.
  - josefx 7y ago
    A call to free could write a gravestone into the freed memory, each free call could check for it and only check the free list if it sees that value. This would make a check of the free list rare, especially if malloc overrides the value again.
    - anon4242 7y ago
      How would you know it's a gravestone? What if what you consider a gravestone is a perfectly legit byte sequence for a certain program?
      - josefx 7y ago
        That is the reason you check the freelist in the unlikely case that you see it, the cost would average to near nothing except for the memory accesses to set, check and clear the value. You could also xor the memory location into the marker to avoid multiple collisions for applications that allocate a large amount of similar objects.
        laughinghan 7y ago
        Besides, what's the minimum chunk size? Can't be less than the 64-bit word size can it? The chances of a random 8-byte gravestone appearing in legit memory is practically nil. If free() took only 1ns to run and you called it 2^64 times, that would take >500 years.
    - viraptor 7y ago
      Thats a really cool idea!
- rkangel 7y ago
  It also wouldn't work at all when free space is coalesced. Memory allocations vary in size (obviously). The simplest algorithm would be to take the block of memory and start allocating chunks from the beginning. The problem is that if your app does a lot of small allocations, frees them and then wants to do a large allocation, the free list might not contain a block large enough. The job of your allocator is to manage that fragmentation. There are a lot of approaches, but fundamentally at some point it has to put two deallocations 'back together' to make a larger one. If you free a chunk, and then that chunk is coalesced with some data just before it, then the free list will no longer contain a pointer that matches the one that you then try to double free.
  - viraptor 7y ago
    I get that, but I believe this issue doesn't apply in this case (I could be wrong of course). Specifically this double-allocation seems to come directly from a freelist for a specific allocation size. Going with the description from the link I posted about the allocator, this exploit should work only if the freed space is not coalesced - otherwise you wouldn't be guaranteed that the same memory is returned twice.
- Someone 7y ago
  free on insert in a tree isn’t really free, as the only reason to replace insert in a list by insert in a tree would be this check. I think it also would make the memory manager less cache-friendly, as reusing just freed memory blocks would be impossible.
DoofusOfDeath 7y ago
One solution is to check each release candidate using extra instrumentation and/or enabled expensive checks.
- pjmlp 7y ago
  It won't help now, but because of issues like this, memory tagging is going to be a requirement for native code in Android. https://security.googleblog.com/2019/08/adopting-arm-memory-tagging-extension.html https://security.googleblog.com/2019/08/adopting-arm-memory-...
Diggsey 7y ago
Using Rust may be the easiest option because there are existing crates for decoding GIF files (and other image formats) for example: https://crates.io/crates/image https://crates.io/crates/image It should be straightforward to swap out the vulnerable C library with a thin wrapper around the above crate.
- pjmlp 7y ago
  The safest option would have been to use JNI to call Android hardened codecs instead of using their own decoding library in process.
  - pcwalton 7y ago
    But it was pointed out upthread that animated GIFs aren't fully supported by the native Android libraries. So Rust would actually be a reasonable solution here. It's true that there are costs associated with using Rust in the build process and so forth, but WhatsApp is trying to be a secure messenger and is FAANG-backed. The challenges can be overcome.
    - pjmlp 7y ago
      Indeed, however Android does support other image formats with animation, which could have been another solution, much cheaper than introducing yet another language not directly supported by the OS SDK tooling.
      - bluejekyll 7y ago
        > not directly supported by the OS SDK tooling. If that's an issue, I bet the Rust community is interested in making it easier and better supported.
        pjmlp 7y ago
        Think about the Android development experience, using Android Studio, Gradle + CMake/ndk-build, mixed mode debugging across Java/Kotlin and native, Android Studio project templates for native code, packaging Android libraries, Bundles and Instant Apps, NDK APIs and Google libraries for Android intended for NDK consumption like Oboe. This are the expectations that any external language should meet versus what platform languages offer out of the box.
mixedbit 7y ago
Perhaps malloc() could allocate 1 byte extra at the start of the allocated block with some magic number written to it and free() could assert that the number is correct and change the number to mark the block as freed.
- deleted 7y ago
  [deleted]
- vardump 7y ago
  Problems: double free might still happen, except now some innocent memory block can be corrupted as well, which just happened to have the magic value in that address. All memory allocations are now misaligned, decreasing performance. On some platforms misaligned access causes a bus error exception. The marker would generally need to be at least 8 bytes. This would alleviate the problems, but also cause pretty significant overhead.
  - saagarjha 7y ago
    I feel like the allocation header might already have a flags bit field where this might go.
  - laughinghan 7y ago
    On the other hand, the chances of an innocent memory block having a random 8-byte magic value is vanishingly small, so that would work even better. If free() took only 1ns to run and you called it 2^64 times, that would take >500 years.
- bluecalm 7y ago
  Why not just always set the pointer to NULL after free is called in it? It would be fantastic if the operation is atomic as well but even if it isn't I like doing it. Freed address is not something you ever want to just again anyway.
  - mixedbit 7y ago
    There can be many pointers pointing to the same allocated memory. For example, if you have a cyclic list with two elements head.next and head.prev pointers will both point to the second element and free(head.next); free(head.prev); would be double-free.

viraptor 7y ago

I guess the naive solution would be to walk the freelist/tree on free() to avoid duplicates. I have no idea what the real world impact would be though. Probably very workload-dependent. At least checking for duplicate would be free on insert in a tree, but in a list that's both a long walk and lots of thrashing.

gpderetta 7y ago
It would completely defeat the purpose of using a free list.
- josefx 7y ago
  A call to free could write a gravestone into the freed memory, each free call could check for it and only check the free list if it sees that value. This would make a check of the free list rare, especially if malloc overrides the value again.
  - anon4242 7y ago
    How would you know it's a gravestone? What if what you consider a gravestone is a perfectly legit byte sequence for a certain program?
    - josefx 7y ago
      That is the reason you check the freelist in the unlikely case that you see it, the cost would average to near nothing except for the memory accesses to set, check and clear the value. You could also xor the memory location into the marker to avoid multiple collisions for applications that allocate a large amount of similar objects.
      - laughinghan 7y ago
        Besides, what's the minimum chunk size? Can't be less than the 64-bit word size can it? The chances of a random 8-byte gravestone appearing in legit memory is practically nil. If free() took only 1ns to run and you called it 2^64 times, that would take >500 years.
  - viraptor 7y ago
    Thats a really cool idea!
rkangel 7y ago
It also wouldn't work at all when free space is coalesced. Memory allocations vary in size (obviously). The simplest algorithm would be to take the block of memory and start allocating chunks from the beginning. The problem is that if your app does a lot of small allocations, frees them and then wants to do a large allocation, the free list might not contain a block large enough. The job of your allocator is to manage that fragmentation. There are a lot of approaches, but fundamentally at some point it has to put two deallocations 'back together' to make a larger one. If you free a chunk, and then that chunk is coalesced with some data just before it, then the free list will no longer contain a pointer that matches the one that you then try to double free.
- viraptor 7y ago
  I get that, but I believe this issue doesn't apply in this case (I could be wrong of course). Specifically this double-allocation seems to come directly from a freelist for a specific allocation size. Going with the description from the link I posted about the allocator, this exploit should work only if the freed space is not coalesced - otherwise you wouldn't be guaranteed that the same memory is returned twice.
Someone 7y ago
free on insert in a tree isn’t really free, as the only reason to replace insert in a list by insert in a tree would be this check. I think it also would make the memory manager less cache-friendly, as reusing just freed memory blocks would be impossible.

DoofusOfDeath 7y ago

One solution is to check each release candidate using extra instrumentation and/or enabled expensive checks.

pjmlp 7y ago
It won't help now, but because of issues like this, memory tagging is going to be a requirement for native code in Android. https://security.googleblog.com/2019/08/adopting-arm-memory-tagging-extension.html https://security.googleblog.com/2019/08/adopting-arm-memory-...

Diggsey 7y ago

Using Rust may be the easiest option because there are existing crates for decoding GIF files (and other image formats) for example: https://crates.io/crates/image https://crates.io/crates/image It should be straightforward to swap out the vulnerable C library with a thin wrapper around the above crate.

pjmlp 7y ago
The safest option would have been to use JNI to call Android hardened codecs instead of using their own decoding library in process.
- pcwalton 7y ago
  But it was pointed out upthread that animated GIFs aren't fully supported by the native Android libraries. So Rust would actually be a reasonable solution here. It's true that there are costs associated with using Rust in the build process and so forth, but WhatsApp is trying to be a secure messenger and is FAANG-backed. The challenges can be overcome.
  - pjmlp 7y ago
    Indeed, however Android does support other image formats with animation, which could have been another solution, much cheaper than introducing yet another language not directly supported by the OS SDK tooling.
    - bluejekyll 7y ago
      > not directly supported by the OS SDK tooling. If that's an issue, I bet the Rust community is interested in making it easier and better supported.
      - pjmlp 7y ago
        Think about the Android development experience, using Android Studio, Gradle + CMake/ndk-build, mixed mode debugging across Java/Kotlin and native, Android Studio project templates for native code, packaging Android libraries, Bundles and Instant Apps, NDK APIs and Google libraries for Android intended for NDK consumption like Oboe. This are the expectations that any external language should meet versus what platform languages offer out of the box.

mixedbit 7y ago

Perhaps malloc() could allocate 1 byte extra at the start of the allocated block with some magic number written to it and free() could assert that the number is correct and change the number to mark the block as freed.

deleted 7y ago
[deleted]
vardump 7y ago
Problems: double free might still happen, except now some innocent memory block can be corrupted as well, which just happened to have the magic value in that address. All memory allocations are now misaligned, decreasing performance. On some platforms misaligned access causes a bus error exception. The marker would generally need to be at least 8 bytes. This would alleviate the problems, but also cause pretty significant overhead.
- saagarjha 7y ago
  I feel like the allocation header might already have a flags bit field where this might go.
- laughinghan 7y ago
  On the other hand, the chances of an innocent memory block having a random 8-byte magic value is vanishingly small, so that would work even better. If free() took only 1ns to run and you called it 2^64 times, that would take >500 years.
bluecalm 7y ago
Why not just always set the pointer to NULL after free is called in it? It would be fantastic if the operation is atomic as well but even if it isn't I like doing it. Freed address is not something you ever want to just again anyway.
- mixedbit 7y ago
  There can be many pointers pointing to the same allocated memory. For example, if you have a cyclic list with two elements head.next and head.prev pointers will both point to the second element and free(head.next); free(head.prev); would be double-free.