Using mmap with address hint causes ASAN to leak shadow memory

[landaire]

Context

While working on some changes to one of our fuzzers, we observed that the fuzzer was failing our health check and was quickly exceeding our 5GB RSS limit.

We eventually narrowed it down to our new allocator. The harness crashed when the new allocator was used but RSS plateaued when using malloc.

The new allocator uses mmap() with a random page hint to ensure that there's a very low likelihood of the same page being returned twice when allocating. This is to ensure that when the memory is deallocated and we munmap() it, any UAFs on that address range will fail fast.

We also realized that this only occurred when running under ASAN but did not occur under other sanitizers like MSAN.

The Bug

Summary

If you mmap() a lot of memory and those mmap() calls frequently return new addresses (such as through the address hint), the shadow memory for that address is not cleaned up after an munmap().

There may be an additional gap here that the memory is marked as addressable up to the nearest page boundary even if you did not mmap() with a len % PAGE_SIZE == 0. The memory will always be poisoned with the value 0, meaning that ASAN will never detect a memory violation except via the SIGSEGV deadly signal handler if the memory has been munmap()'d.

Full Details

I had a guess that maybe the OOM had something to do with the allocator's mmap page hint and produced the following MRE which clearly showed that when a page hint is used we crash. When NULL is provided for the page hint the memory usage mostly plateaus. In both cases this behavior only surfaces when compiled with ASAN enabled:

// clang test.c -fsanitize=fuzzer,address && ./a.out

#include <sys/time.h>
#include <sys/mman.h>
#include <stddef.h>
#include <stdint.h>
#include <limits.h>
#include <stdio.h>
#include <unistd.h>

uint64_t seed = 0xc0ffee;

uint64_t rand_uint64(void) {
  if (seed == 0) {
    struct timeval tv;
    gettimeofday(&tv,NULL);
    seed = 1000000 * tv.tv_sec + tv.tv_usec;
  }
  seed += 0x5d6447c8df9375b5;
  __uint128_t tmp = (__uint128_t)seed * 0x3c5829f2fb3c3eef;
  uint64_t m1 = (tmp >> 64) ^ tmp;
  tmp = (__uint128_t)m1 * 0x4f38e4ccc1b0ea59;
  return (tmp >> 64) ^ tmp;
}

static void* get_page_hint(void) {
  uint64_t r = rand_uint64();
  return (void*)((uintptr_t)((uint32_t)r >> 2) << 16);
}

void do_some_mapping(size_t count) {
    int prot = PROT_READ | PROT_WRITE;
    int flags = MAP_ANONYMOUS | MAP_PRIVATE;
    size_t size = 4096;
    for (size_t i = 0; i < count; i++) {
        // Use a page hint for an OOM
        void* page_hint = get_page_hint();
        // Use NULL page hint for no OOM
        //void* page_hint = NULL;

        volatile char* addr = (volatile char*)mmap(page_hint, size, prot, flags, -1, 0);
        *addr = 0;
        munmap((void*)addr, size);
    }
}

int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
    do_some_mapping(100);
    return 0;
}

Compiling without ASAN did not reproduce this behavior.

I then put together this other example which logged addresses returned from mmap(), which showed that the same address was being returned thousands of times when the page hint is NULL and was likely masking a bug that only occurs when a different address is returned:

// clang++ test.c -fsanitize=address && ./a.out

#include <sys/time.h>
#include <sys/mman.h>
#include <stddef.h>
#include <stdint.h>
#include <limits.h>
#include <stdio.h>
#include <unistd.h>
#include <map>
#include <optional>

// For RSS info
#include <sys/sysctl.h>
#include <mach/mach.h>

#define DEBUG_MAPPED_ADDRESSES 0

uint64_t seed = 0xc0ffee;

#if DEBUG_MAPPED_ADDRESSES
static std::map<uintptr_t, size_t> mapped_addresses;
#endif

std::optional<size_t> get_rss() {
    struct task_basic_info info;
  unsigned count = TASK_BASIC_INFO_COUNT;
  kern_return_t result =
      task_info(mach_task_self(), TASK_BASIC_INFO, (task_info_t)&info, &count);
  if (result != KERN_SUCCESS) {
    return {};
  }
  return info.resident_size;
}

uint64_t rand_uint64(void) {
  if (seed == 0) {
    struct timeval tv;
    gettimeofday(&tv,NULL);
    seed = 1000000 * tv.tv_sec + tv.tv_usec;
  }
  seed += 0x5d6447c8df9375b5;
  __uint128_t tmp = (__uint128_t)seed * 0x3c5829f2fb3c3eef;
  uint64_t m1 = (tmp >> 64) ^ tmp;
  tmp = (__uint128_t)m1 * 0x4f38e4ccc1b0ea59;
  return (tmp >> 64) ^ tmp;
}

static void* get_page_hint(void) {
  uint64_t r = rand_uint64();
  return (void*)((uintptr_t)((uint32_t)r >> 2) << 16);
}

void do_some_mapping(size_t count) {
    int prot = PROT_READ | PROT_WRITE;
    int flags = MAP_ANONYMOUS | MAP_PRIVATE;
    size_t size = 4096;
    for (size_t i = 0; i < count; i++) {
        // Use a page hint for an OOM
        //void* page_hint = get_page_hint();
        // Use NULL page hint for no OOM
        void* page_hint = NULL;

        volatile char* addr = (volatile char*)mmap(page_hint, size, prot, flags, -1, 0);
        *addr = 0;

#if DEBUG_MAPPED_ADDRESSES
        uintptr_t addr_ptr = (uintptr_t)addr;
        if (auto match = mapped_addresses.find(addr_ptr) ; match != mapped_addresses.end()) {
            mapped_addresses[addr_ptr] += 1;
            printf("Mapped 0x%zx %zu times\n", addr_ptr, mapped_addresses[addr_ptr]);
        } else {
            mapped_addresses[addr_ptr] = 1;
        }
#endif

        if (auto rss = get_rss()) {
            printf("RSS has grown to: %zu MiB\n", *rss / (1024 * 1024));
        }

        munmap((void*)addr, size);
    }
}

//  extern "C" int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
int main() {
    do_some_mapping(50000);
    printf("Sleeping...\n");
    while(1) {
        sleep(1);
    }
    return 0;
}

// With NULL page hint
Mapped 0x107000020000 29761 times
Mapped 0x107000020000 29762 times
Mapped 0x7000000000 681 times

Here is what I think is happening:

1. The sanitizers work by hooking various functions, including mmap() and munmap(). The munmap() code path poisons the memory in the same exact manner as mmap() which is a bit suspicious: https://github.com/llvm/llvm-project/blob/ccdce045e22b9d36cc4f41a5e35f6006c9c0fba5/compiler-rt/lib/asan/asan_interceptors.cpp#L152-L179

2. PoisonShadow() will call FastPoisonShadow() which in turn attempts to allocate shadow memory for this memory range: https://github.com/llvm/llvm-project/blob/ccdce045e22b9d36cc4f41a5e35f6006c9c0fba5/compiler-rt/lib/asan/asan_poisoning.h#L70. When using the random page hint, you're almost always going to get a brand new memory range returned from mmap() so ASAN will allocate more shadow memory to describe this memory range.

3. munmap() just calls PoisonShadow() and the shadow mapping is written back to the poison value (0), but the shadow mapping is never released.

The third point is kind of interesting because we don't even really get any value of poisoning with 0. If you attempt to read from this address you receive a SIGSEGV and ASAN just says it doesn't know anything about this address. ASAN also marks the entire [addr, RoundToNearestPageBoundary(addr+size)) range as addressable, so if you request less than PAGE_SIZE bytes and read beyond addr + size the "out of bounds" read isn't detected. Technically this memory is addressable, but I'd consider reading the slack between size and page boundary a logic bug. This is especially true when mmaping files.

Assuming I didn't miss something obvious, I confirmed that the munmap() calls PoisonShadow()

Which just does a memest()

And then we call munmap() and do nothing else with the shadow memory.

Mitigating

I couldn't find anything about this on the ASAN bug tracker but thought it was worth highlighting. I'm not sure exactly how to go about fixing this in ASAN as I'm not sure if shadow memory was ever meant to be removed, but it's probably possible.

For our case we're able to mitigate the issue by disabling the mmap() page hint in the allocator when ASAN is enabled:

#if defined(__has_feature)
#  if __has_feature(address_sanitizer)
#define HAS_ASAN 1
#  endif
#endif

#if HAS_ASAN
page_hint = NULL;
#else
page_hint = get_page_hint()
#endif

[vitalybuka]

Would you like to try to hint 32k aligned allocations of 32k size?

[vitalybuka]

There may be an additional gap here that the memory is marked as addressable up to the nearest page boundary even if you did not mmap() with a len % PAGE_SIZE == 0. The memory will always be poisoned with the value 0, meaning that ASAN will never detect a memory violation except via the SIGSEGV deadly signal handler if the memory has been munmap()'d.

With mmap interceptors we have no goal to detect anything. This is outside of C/C++, so it up to the user if they want to poison for detection. E.g. you can implement poisoning in custom allocator.

The goal of theses interceptors avoid false positives when we mmap memory region which was somehow left out poisoned.

[landaire]

Would you like to try to hint 32k aligned allocations of 32k size?

I can, but what outputs are you looking for?

The goal of theses interceptors avoid false positives when we mmap memory region which was somehow left out poisoned.

This makes sense. Is it intentional to leave the shadow memory for the mapping around? FWIW I don't know much about the shadow memory internals, so maybe it's not so simple to just make it go away

[vitalybuka]

I can, but what outputs are you looking for?

Asan is 1 to 8 mapping. 4k of mmap is just 4k/8 of shadow. if can not do anything about 1/8 of the page. I believe asan uses NOT_NEEDED on full pages, 32k should result in full shadow pages.