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

Up to now, most students in COMP1917 and COMP1927 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.

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, which can much more reliably catch out-of-bounds heap, stack, and global accesses, double free(3), invalid free(3), use after free(3), use after return, and use after scope errors. It’s significantly faster (and more reliable!) than Valgrind Memcheck, and produces clearer output.

AddressSanitizer, usually shortened to ASan, requires compiler awareness, as it must be compiled into the resultant executable; both GCC and Clang are able to do this. Add the flag -fsanitize=address to enable ASan; you likely also want debugging symbols and -fno-omit-frame-pointer to ensure the resultant output, particularly the backtraces, are intact.

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 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? Given this information, it’s difficult to determine precisely what. 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 //llvm/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)
    #3 0x8006d5fff  (<unknown module>)

previously allocated by thread T0 here:
    #0 0x45edc3 in calloc //llvm/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)
    #3 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. We get stack traces of the erroneous memory’s allocation, freeing, and subsequent use, as well as a “shadow memory” map: ASan stores a ⅛-scale model of memory high up in the virtual memory space, and its interceptors check and update this.

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 superior 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 easily spot 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 developed by Google and the LLVM Project. The others are

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.