On AddressSanitizer

two documents glued together:

a quick scribbling for jas on ASan
written 2016-10-17 19:49:00

a reply-to-public to a student question
written 2018-01-29 11:10:06

What does the address sanitizer do and why does it pick up stuff that valgrind doesn’t? I copied the dryrun tests and ran it under valgrind and it doesn’t detect any errors, but the address sanitizer does.

Up until now, students in ~~COMP1917~~COMP1511 and in ~~COMP1927~~COMP2521 haven’t really learned much about chasing down memory errors, beyond “the memory leaked” or “the pointer was invalid”. For those purposes, they’ve used Valgrind’s Memcheck tool, and GNU gdb, respectively. (More recently, they’ve used dcc, a wrapper around Clang+ASan.)

However, Valgrind can fail to recognise some memory errors, and trying to trace such issues through gdb can be painful without much skill in its (ab)use.

Enter AddressSanitizer, a memory error detector. It detects use-after-free, -return, and -scope, heap-, stack-, and global buffer under- and over-flows, double- and invalid free(3), initialisation ordering bugs, and memory leaks. It’s significantly faster (and more reliable!) than Valgrind Memcheck, and produces clearer output. (If you’ve used dcc before, that’s what does its memory error management.)

Valgrind takes any executable, and instead of running it on the machine directly, it has a great big switch statement in it that interprets each instruction, checks it, and then runs it. Along the way, it replaces calls to some functions, including memory allocation and memory and string manipulation functions, with its own book-keeping versions of them.

AddressSanitizer, by comparison, uses a very different approach: it must be compiled into a program (which is why the binaries produced when you compile with ASan or dcc are ~1.5 MB, and without them are tens of kilobytes), and it slots into the compiler’s code generation pass: it also replaces memory allocator and some string and memory functions, but also inserts function calls to check against its shadow memory, a ⅛-scale model of memory high up in the virtual memory space, describing what memory is accessible and why, and these intercepting functions check and update this. On memory errors, you’ll see a dump of the shadow memory around what you tried to access.

Both GCC and Clang are able to do this, with the flag -fsanitize=address to enable ASan; you likely also want debugging symbols, and -fno-omit-frame-pointer and -fno-optimize-sibling-calls to ensure the resultant output, particularly the backtraces, are intact.

(If you’re interested, there’s much more excruciating detail on the Sanitizers wiki: https://github.com/google/sanitizers/wiki.)

A Simple Example

A simple, and not particularly excellent example: on any crash, ASan attempts to unwind the stack and print a backtrace.


ASAN:SIGSEGV
=================================================================
==18311==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x000000485387 bp 0x7fffffffe150 sp 0x7fffffffc910 T0)
    #0 0x485386 in main bin/testDracView/../../src/tests/testDracView.c:320:3
    #1 0x40b9ce in _start (bin/testDracView/testDracView.full+0x40b9ce)
    #2 0x8006d0fff  (<unknown module>)

AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: SEGV bin/testDracView/../../src/tests/testDracView.c:320:3 in main
==18311==ABORTING

That’s a hopelessly boring example: it’s fairly obvious there’s some sort of NULL dereference happening here, so it remains to look at line 320 of testDracView.c to work out what’s happened.

A More Complex Example

Here’s a much more interesting example; first, with Valgrind:


$ valgrind bin/tapGameView/tapGameView.full
==3943== Memcheck, a memory error detector
==3943== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==3943== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==3943== Command: bin/tapGameView/tapGameView.full
1..77
[... output elided ...]
ok 77 # disposed gameview
==3943== Invalid read of size 8
==3943==    at 0x402FCE: disposeGameView (GameView.c:48)
==3943==    by 0x402E5E: main (tapGameView.c:353)
==3943==  Address 0x5429f50 is 32 bytes inside a block of size 48 free'd
==3943==    at 0x4C252AC: free (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==3943==    by 0x402FEE: disposeGameView (GameView.c:51)
==3943==    by 0x402E16: main (tapGameView.c:351)
==3943==
==3943== Invalid read of size 8
==3943==    at 0x402FDB: disposeGameView (GameView.c:49)
==3943==    by 0x402E5E: main (tapGameView.c:353)
==3943==  Address 0x5429f30 is 0 bytes inside a block of size 48 free'd
==3943==    at 0x4C252AC: free (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==3943==    by 0x402FEE: disposeGameView (GameView.c:51)
==3943==    by 0x402E16: main (tapGameView.c:351)
==3943==
==3943== Invalid free() / delete / delete[] / realloc()
==3943==    at 0x4C252AC: free (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==3943==    by 0x402FE2: disposeGameView (GameView.c:49)
==3943==    by 0x402E5E: main (tapGameView.c:353)
==3943==  Address 0x5429fa0 is 0 bytes inside a block of size 1 free'd
==3943==    at 0x4C252AC: free (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==3943==    by 0x402FE2: disposeGameView (GameView.c:49)
==3943==    by 0x402E16: main (tapGameView.c:351)
==3943==
==3943== Invalid free() / delete / delete[] / realloc()
==3943==    at 0x4C252AC: free (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==3943==    by 0x402FEE: disposeGameView (GameView.c:51)
==3943==    by 0x402E5E: main (tapGameView.c:353)
==3943==  Address 0x5429f30 is 0 bytes inside a block of size 48 free'd
==3943==    at 0x4C252AC: free (in /usr/local/lib/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==3943==    by 0x402FEE: disposeGameView (GameView.c:51)
==3943==    by 0x402E16: main (tapGameView.c:351)

It’s fairly apparent that something’s gone horribly wrong, but what? Valgrind also unwinds the stack at both the point of read and of deallocation, but that’s not always useful; given just this information, it’s difficult to determine precisely what’s broken. Notably, though, execution just plows straight on.

Recompiling with ASan, we try again:


$ bin/tapGameView/tapGameView.full
1..77
[... output elided ...]
ok 77 # disposed gameview
=================================================================
==79714==ERROR: AddressSanitizer: heap-use-after-free on address 0x60400000de30 at pc 0x000000485ebc bp 0x7fffffffcb00 sp 0x7fffffffcaf8
READ of size 8 at 0x60400000de30 thread T0
    #0 0x485ebb in disposeGameView bin/tapGameView/../../src/view/GameView.c:48:25
    #1 0x485ab6 in main bin/tapGameView/../../src/tests/tapGameView.c:353:3
    #2 0x40b9ce in _start (bin/tapGameView/tapGameView.full+0x40b9ce)
    #3 0x8006d5fff  (<unknown module>)

0x60400000de30 is located 32 bytes inside of 48-byte region [0x60400000de10,0x60400000de40)
freed by thread T0 here:
    #0 0x45e92b in __interceptor_free /wrkdirs/usr/ports/devel/llvm37/work/llvm-3.7.1.src/tools/compiler-rt/lib/asan/asan_malloc_linux.cc:30:3
    #1 0x485f0d in disposeGameView bin/tapGameView/../../src/view/GameView.c:51:2
    #2 0x485a6e in main bin/tapGameView/../../src/tests/tapGameView.c:351:3
    #3 0x40b9ce in _start (bin/tapGameView/tapGameView.full+0x40b9ce)
    #4 0x8006d5fff  (<unknown module>)

previously allocated by thread T0 here:
    #0 0x45edc3 in calloc /wrkdirs/usr/ports/devel/llvm37/work/llvm-3.7.1.src/tools/compiler-rt/lib/asan/asan_malloc_linux.cc:56:3
    #1 0x485c68 in newGameView bin/tapGameView/../../src/view/GameView.c:32:24
    #2 0x4848fa in main bin/tapGameView/../../src/tests/tapGameView.c:272:17
    #3 0x40b9ce in _start (bin/tapGameView/tapGameView.full+0x40b9ce)
    #4 0x8006d5fff  (<unknown module>)

SUMMARY: AddressSanitizer: heap-use-after-free bin/tapGameView/../../src/view/GameView.c:48:25 in disposeGameView
Shadow bytes around the buggy address:
  0x4c0800001b70: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x4c0800001b80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x4c0800001b90: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x4c0800001ba0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x4c0800001bb0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x4c0800001bc0: fa fa fd fd fd fd[fd]fd fa fa fd fd fd fd fd fd
  0x4c0800001bd0: fa fa fd fd fd fd fd fd fa fa fd fd fd fd fd fd
  0x4c0800001be0: fa fa fd fd fd fd fd fd fa fa fd fd fd fd fd fa
  0x4c0800001bf0: fa fa fd fd fd fd fd fd fa fa fd fd fd fd fd fd
  0x4c0800001c00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x4c0800001c10: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==79714==ABORTING

By default, when ASan intercepts a memory error, it aborts to avoid errors snowballing, unlike Valgrind, which just keeps spewing errors. (That’s configurable, though usually a bad idea.) We get stack traces of the erroneous memory’s allocation, freeing, and subsequent use, as well as the shadow memory map.

So, it’s now obvious that we’re looking at a heap use after free error: we’ve attempted to read 8 bytes of memory, 32 bytes inside a 48-byte struct allocated in newGameView.

It looks, for all the world, like the code is executing backwards: our error is on line 48 of disposeGameView, but we’ve free(3)‘d on line 51 … and then you actually read the backtrace: tapGameView.c calls disposeGameView twice on the same GameView, once on line 351, and once on line 353, and it’s short work to fix and check again.

ASan and the Sanitizers

In combination with Clang’s powerful semantic analysis capabilities, ASan makes a formidable tool for finding errors that other compilers and memory checking tools don’t find.

ASan’s memory map can make it easy to spot some errors, too; with unusual allocation sizes, the map shows a partially-addressable region, making it possible to actually see code that writes off the end of arrays, particularly strings.

ASan integrates with both the GDB and LLDB debuggers, too; one can set breakpoints in the interceptors and on the error reporter hook to get into the program as a memory error occurs, and provides the function __asan_describe_address which generates ASan’s reports on demand.

ASan also has good integration with software that does evil tricks with memory, such as database engines and web browsers. Firefox, Chromium, and PostgreSQL, among others, are ASan-aware, and can leverage ASan’s memory protections on their own sub-allocators.

ASan is a part of the Sanitizer family, a suite of tools under active development by Google and the LLVM Project; others include:

ThreadSanitizer (TSan), which detects data races in C++ and Go;
MemorySanitizer (MSan), which detects uninitialised memory access;
UndefinedBehaviourSanitizer (UBSan), which detects — you guessed it! — undefined behaviour;
LeakSanitizer (LSan), which detects memory leaks (enabled by default with ASan); and
SanitizerCoverage (SanCov), which does code coverage and profiling analysis.

An old version of Clang, with ASan and UBSan, powers dcc’s memory error and undefined behaviour detection.

The Sanitizers are portable: the examples came from my FreeBSD/amd64 workstation, but my systems running Linux/amd64, Darwin/amd64, and FreeBSD/i386 all produce the same output. ASan even runs, albeit not well, on Windows.

Because ASan has a quite different algorithm, a fairly different approach, and is under very active development (by Google, who use it to whack memory bugs in Chrome) you’ll often find it picks up a very different set of bugs to Valgrind. The flip-side is that ASan is necessarily invasive: it uses additional system resources, notably non-trivial amounts of memory at run-time, and increases executable size.