AddressSanitization and Why You Should Use It

A quick guide on using AddressSanitization to find memory corruptions bugs at run-time.

tl;dr

AddressSanitization (ASAN) implements compile-time instrumentation and a run-time library to track memory use. It can detect faults such as out-of-bounds reads and writes (stack/heap/globals), use-after-free, and use-after-return.

I talked about ASAN briefly in a previous article on fuzzing and figured it would be cool to discuss it in depth.

What is ASAN?

AddressSanitization implements two nifty features:

• Instrumentation: creates a shadow memory and poisoned redzones around stack and global objects to detect out-of-bounds accesses.
• Run-time library: replaces memory operations (malloc, free, etc.) to create the poisoned redzones on the heap. Implements a new heap-allocator to quarantine free'd memory; also delays the reuse of free'd memory for as long as possible.

Shadow Memory

Shadow memory is simply metadata corresponding to actual memory addresses. When you allocate 8 bytes on the heap, ASAN creates one byte of shadow memory to store the state of that memory. The shadow memory state tells ASAN whether a given memory address is safe to access. The check is dead simple (for memory access 8 bytes wide):

/* Compute the address of the shadow memory on x86 platforms.
** Part of ASAN's innovation is how efficient this mapping is. */
ShadowAddr = (Addr >> 3) + Offset;
/* If the shadow address is anything other than 0, crash. */
if (*ShadowAddr != 0) {
    ReportAndCrash(Addr);
}

When actual memory addresses get poisoned, this means that the corresponding shadow byte representing that address gets written to with a special value.

Run-time Library

malloc (and family) and free have new implementations. In glibc, you get chunks aligned to 8 bytes when you malloc something. In ASAN’s implementation of malloc, more memory than necessary is also allocated. The extra space is called the redzone and is poisoned. The redzone is mapped to either side of the actual addressable space (i.e., there are poisoned values to the left or right on the heap). If the program tries to access something to the left, you have an underflow. To the right, an overflow.

I’m not a football person (or sports in general honestly), but I like to think of this in terms of kicking a field goal. The kicker’s job is to punt the ball in between the goalposts. Anything to the left or right is bad. Our program is the kicker; missing the field goal creates a segmentation fault.

free was reimplemented to poison the entire memory region of the address being free'd. These addresses are then placed in quarantine and are placed in a first-in, first-out queue. Unlike the default implementation of glibc's allocator, the intent is not to reuse a memory address unless necessary. This obviously has speed implications for memory-bound processes. Then again, so does most of ASAN’s implementation.

Finally, malloc and free write the function call stack to the left redzone. That way, if a fault occurs, it can retrieve this information to provide a meaningful backtrace. The larger the redzone, the larger the call stack can be.

Stack-based Accesses

To detect stack-based out-of-bounds accesses, redzones are similarly placed on the stack at instrumentation time. For example, if your program looks like this:

_Noreturn func(void) {
    char buf[8];
        exit(0);
}

When you compile with ASAN, your program will look something like this:

_Noreturn func(void) {
    char redzone1[32];
    char buf[8];
    char redzone2[24];
    char redzone3[32];
    int * shadow_base_address = /* Mapping to real memory done here. */
    /* Poison the first redzone. */
    shadow_base_address[0] = 0xffffffff;
    /* Posion most of redzone2. Allow 8-byte access for buf. */
    shadow_base_address[1] = 0xffffff00;
    /* Posion the last redzone. */
    shadow_base_address[2] = 0xffffffff;

    /* Unpoison the stack before function ends. */
    shadow_base_address[0] = 0x00000000;
    shadow_base_address[1] = 0x00000000;
    shadow_base_address[2] = 0x00000000;
    exit(0);    

Here you can see the redzones on the stack, so it’s much easier to visualize. In this example, buf is never accessed. If it were, it would check the shadow memory first.

/* Map the shadow address from `buf` */
ShadowAddr = (&buf >> 3) + Offset;
if (*ShadowAddr != 0) {
    ReportAndCrash(Addr);
}
/* Some read/write access follows. */
buf[...] = ...

Globals

Globals are very similar to the stack. At instrumentation time, redzones are implemented in a structure. So if you have a global int i, it might map to the following structure on x86.

/* Assumes 32-bit alignment. */
struct {
    int foo; // 4-bytes
    char redzone[60];
} bar;

Implementation

Implementation is easy with clang, gcc, or the Xcode compiler. Adding the -fsanitize=address to the compilation line does the trick for the former two. For Xcode, it is a selection when generating build targets under diagnostics.

Limitations

False Negatives

ASAN can’t catch everything. There are two notable cases. The first is unaligned memory access with their example:

int *a = new int[2]; // 8-aligned
int *u = (int*)((char*)a + 6);
*u = 1; // Access to range [6-9]

In this case, eight bytes are allocated to the address stored in a. u then points to a plus 6 bytes. The last line de-references that address setting the value to one. That address is not aligned with the original allocation and is partially out-of-bounds. Because shadow bytes are not mapped one-to-one with usable memory, this becomes difficult to track.

The next false negative comes from accesses so far out-of-bounds that they touch legitimate, accessible memory. The example the authors give is:

char *a = new char[100];
char *b = new char[1000];
a[500] = 0; // may end up somewhere in b

Let’s relate this back to the football example. It would be as if it did not matter which field post a kicker aimed for; they could go for the opponent’s or turn around and try to kick through their own.

False Positives

ASAN claims to have no false positives. However, accessing “wild” memory address that crosses between stack frames can confuse ASAN, and the function attribute no address safety analysis was added to address cases like these. ASAN is thread-safe and works with clone.

What’s the Catch?

Who wouldn’t want to catch bugs before production? Why isn’t ASAN all over the place?

• Code complexity and size.
  • Since the implementation is partly done at instrumentation time, the size of the compiled product can explode. Did you see how many lines of code our example with buf added?
• Compute.
  • ASAN has roughly a 2x slowdown. This is much better than something like Valgrind, but it is certainly a performance hit.
  • In many spheres (cloud), running cores = more money. Can your business afford that? Can you afford not to?
• RAM usage.
  • ASAN maps 1/8th of all addressable space for shadow memory. This doesn’t mean that all of it will actually be in use, but…
    • On 32-bit platforms, this is 0.5 GB
    • On 64-bit platforms, this is 16 TB.
  • Typical overall memory overhead is 2x or 4x, but it can be as high as 20x.

So yes, you’re taking a performance hit. It’s definitely not recommended for production. Some companies have used it to crowd-source bug-finding on nightly builds, though. Google shipped Chrome for Windows (canary channel) with it, and Mozilla has its own nightly ASAN build.

Conclusion

Simple. Use ASAN for debug builds when possible. It’ll help you find bugs faster. Maybe don’t use it in production.

Further Reading:

• The USENIX ASAN paper.
• A Google presentation introducing ASAN at an LLVM meetup.
• A great academic resource that covers ASAN.
• Unemployed Russian again coming in hot with a great Stack Overflow answer.
• A slideshow on hardware-implemented ASAN. Covers pros/cons of regular ASAN.