Hacker News Reader

Comment by viraptor | Hacker News Reader

> In Android, a double-free of a memory with size N leads to two subsequent memory-allocation of size N returning the same address.

I get that freelists are fast and great for small chunk reuse, (I'm guessing that's the implementation that allows double return) but is there no way to protect against double-free here? I wish it crashed instead.

Edit: it does indeed look like a form of a freelist - https://blog.nsogroup.com/a-tale-of-two-mallocs-on-android-l...

View on HN

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.

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.

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.

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.

I feel like the allocation header might already have a flags bit field where this might go.

The metadata (size of allocated block, and whether it is in use) is already there. I really wonder why this is not checked. In a normal libc you should get a "double free" panic.

malloc() doesn't give you memory on the granularity of bytes. On x86_64 for example malloc has to assume you'll use the memory for 16-byte aligned access (say, movdqa). So your allocating an extra byte could become 16 extra bytes.

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.

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.

When many pointers point to the same memory then naked free shouldn't be used. Instead you implement a counter and decrease it (and free at zero when the last pointer dies). Imo code where a free is called on something other pointers point to is just a basic level design error.

Because in this case the problem is a second pointer to the same chunk of data. Nulling the first doesn't null the second.

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.

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.

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.

It would completely defeat the purpose of using a free list.

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.

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?

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.

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.

Thats a really cool idea!

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.

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

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-...

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

It should be straightforward to swap out the vulnerable C library with a thin wrapper around the above crate.

The safest option would have been to use JNI to call Android hardened codecs instead of using their own decoding library in process.

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.

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.

Changing to a different image format may not be possible because WhatsApp still needs to show historical images, and these images are not stored on a central server where they can be migrated.

Also, it's called the "Android NDK" and not the "Android C SDK" - a big part of what the NDK gives you is not C-specific. It makes almost no difference whether you compile your code with GCC vs rustc, at the end of the day you're creating a native shared library and loading it from a java application.

For example, these instructions from 2017 show how little work is involved https://mozilla.github.io/firefox-browser-architecture/exper... and support has only improved since then.

Using static analysis tooling on C/C++ code is more work than the above to set up, so I really do believe that Rust is the easiest way to reduce the chance of these kinds of bugs happening again.

Then they could add a memory safe Java library dependency like Glide.

Yes it is called the NDK and the workflow that you describe doesn't support the bullet points I described.

If Rust wants to be embraced by Android developers it needs to up its game in Android Studio tooling, Binder generation and FFI integration.

Those instructions from 2017 are completely outdated given Android 3.5 and NDK r20.

GCC is no longer around, C++ support has improved quite substantially, static analysis tooling is integrated into NDK, Android Studio 3.7 (planned for next year) will bring support for mixed mode NDK libraries in AAR format.

> 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.

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.

I haven't done any android dev in a while so it may have changed in between, but it sounds that your expectations are higher than what the Android experience looks like when JNI is involved.

My expectations are what an Android developer using Studio 3.5 with NDK r20 would expect.

While the experience is still found lacking versus what iOS or UWP tooling are capable of, it still is much better than any third party language integration.

Sure, the “easiest” option is bringing in a whole new language and its toolchain just to decode gifs. Lol!

Seems like you could use an invertible bloom filter or similar, but I'm not sure what the performance hit would look like.

Address sanitizer can detect this sort of thing, so yes, you can protect against it. It comes at a performance cost, though.

ASAN was designed for debugging, not for hardening:

https://seclists.org/oss-sec/2016/q1/363

You wouldn't release with that on, and for testing you would have needed to craft a relevant input to detect it or fuzzed it.

Why wouldn't you release with sanitizers on? The performance impact really is negligible depending on the workload. It's basically like that tiny slowdown when you go from C++ to Java. If you have benchmarks showing the slowdown is acceptable, just ship with it enabled. Saves lots of headaches.

Might be true for UBSan and LSan, that have a moderate impact, but not for ASan and certainly not for MSan or TSan.

(as a _very_ crude approximation, with UBSan on, you have the performance of Java or Go, and with the other sanitizers you get closer to Ruby territory)

You can't combine the sanitizers anyway. They're really designed to be enabled for a testsuite and debug builds.

Is it though? I suspect that the cost of the sanitizer is significantly higher than the overhead of switching, say, to Java.

Not that I don't appreciate sanitizers, I just used asan to find the cause of a memory corruption bug just a couple of hours ago and it was great. In the past I would have used valgrind which is significantly slower.

This is actually a good point. I suspect using asan on this lib as it used by WA would have had a negligble performance impact on the overall UX.

(That is, assuming asan would have really captured this specific instance).

Sure you would. This kind of attacks keep forcing Google security team to increasingly lock down Android native code, including shipping some sanitizers enabled in production devices.

https://security.googleblog.com/2019/05/queue-hardening-enha...

free() could be wrapped in a macro, but it would not catch the case where multiple copies of the pointer is stored.

#define my_free(x) { free(x); (x) = NULL; }

Note that the extra assignment will often be optimized away because

(a) the pointer is assigned to a malloc() after the call to my_free() OR

(b) the pointer goes out of scope e.g. is popped off the stack.

I guess it's better than nothing but that won't work if x is some temporary local variable instead of the long term storage location. It also won't help much if there are several pointers to the resource. As such I wonder if a macro is better that just explicitly nulling the pointer after free, at least there's no obfuscation of what's going on.

Generally I agree with you though, setting pointers to NULL after free is good practice and probably worth enforcing in the coding style.

Well, if there are several pointers to the same memory you need some kind of logic to handle the number anyway. I don't think using free is a good idea in such cases. You need a wrapper which checks for the counter and then decreases it and frees on zero.

Reply on news.ycombinator.com