Prologue

We wanted to improve our password strength algorithm, and decided to go for the industry-standard zxcvbn, from the people at Dropbox. Our web front-end would use the default Javascript library, and for mobile and desktop, we chose to use the C implementation as it was the lowest common denominator for all platforms.

Bootstrapping all of this together was done pretty fast. I had toyed around with a few sample passwords so I decided to run it through the test suite we had for the previous password strength evaluator. The test generates a large number of random passwords according to different rules and expects the strength to be in a given range. But the test runner kept crashing with segmentation faults.

It turns out the library has a lot of buffer overflow cases that are usually "harmless", but eventually crash your program when you run the evaluator function too much. I started fixing the cases I could see, but reading someone else's algorithms to track down tiny memory errors got old pretty fast. I needed a tool to help me.

That's when I thought of Clang's Address Sanitizer.

Meet Asan

From the Clang documentation:

AddressSanitizer is a fast memory error detector. It consists of a compiler instrumentation module and a run-time library. The tool can detect the following types of bugs:

• Out-of-bounds accesses to heap, stack and globals
• Use-after-free
• Use-after-return
• Use-after-scope
• Double-free, invalid free
• Memory leaks (experimental)

That covers a large portion of the crashes I've faced in C. And its impact on performance?

Typical slowdown introduced by AddressSanitizer is 2x.

Perfectly acceptable in a lot of debugging contexts. Especially if it saves you hours of trying to find the proverbial needle in a corrupt stack.

First steps

Let's try the sanitizer on a simple program. We'll allocate a buffer on the heap, copy each character of a string into it, and print it to standard output.

int main() {
    const char* hello = "Hello, World!";
    char* str = malloc(13 * sizeof(char)); // "Hello, World!" is 13 characters long

    for (int i = 0; i < 13; i++) {
        str[i] = hello[i];
    }
    str[13] = 0; // Don't forget the terminating nul character

    printf("%s\n", str);

    return 0;
}

If you compile and run this program, chances are it will work as predicted.

$ clang -o clang-asan clang-asan.c
$ ./clang-asan
Hello, World!

But it shouldn't. Or it should. It's undefined.

When assigning 0 to the character at index 13, we're writing out of the array bounds, into unallocated memory. While harmless in this case, this is a classic buffer overflow error.

Let's try compiling it again with the address sanitizer.

$ clang -fsanitize=address -g -o clang-asan clang-asan.c
$ ./clang-asan

Wow. Such output. A E S T H E T I C !

What happened?

So what can we gather from that pile of hex? Let's go through it line by line.

==36293==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000ef3d
at pc 0x000105960da8 bp 0x7fff5a29fa30 sp 0x7fff5a29fa28

AddressSanitizer found a heap buffer overflow at 0x60200000ef3d, a seemingly valid address (not NULL or any other clearly faulty value). The rest of the addresses are the program counter, base pointer and stack pointer registers.

WRITE of size 1 at 0x60200000ef3d thread T0
    #0 0x105960da7 in main clang-asan.c:10
    #1 0x7fffa6c46254 in start (libdyld.dylib+0x5254)

Write of size 1 at line 10. What's line 10?

str[13] = 0;

We're writing outside of the heap in this instruction. And AddressSanitizer isn't having it.

0x60200000ef3d is located 0 bytes to the right of 13-byte region
[0x60200000ef30,0x60200000ef3d)

This is definitely one of my favorite indications. In addition to telling which line in the code failed and where in the memory the failure happened, you get a complete description of the closest allocated region in memory (which is probably the region you were trying to access).

Power to the debugger

We've seen that the address sanitizer has some pretty nifty tricks up its sleeve. The main benefit is that it will break your program on virtually any bad memory access. But its real power comes when used in conjunction with a debugger.

Let's run our program again, with lldb this time.

$ lldb -- ./clang-asan
(lldb) target create "./clang-asan"
Current executable set to './clang-asan' (x86_64)
(lldb) run

As expected, the program crashes again, at the same line. But let's look at what we get after the usual output.

(lldb) AddressSanitizer report breakpoint hit. Use 'thread info -s' to get extended information about the report.
Process 40049 stopped
* thread #1: tid = 0x13f073, 0x00000001000e30a0 libclang_rt.asan_osx_dynamic.dylib`__asan::AsanDie(), queue = 'com.apple.main-thread', stop reason = Heap buffer overflow detected
    frame #0: 0x00000001000e30a0 libclang_rt.asan_osx_dynamic.dylib`__asan::AsanDie()
libclang_rt.asan_osx_dynamic.dylib`__asan::AsanDie:
->  0x1000e30a0 <+0>: pushq  %rbp
    0x1000e30a1 <+1>: movq   %rsp, %rbp
    0x1000e30a4 <+4>: pushq  %rbx
    0x1000e30a5 <+5>: pushq  %rax

As we can see, the program doesn't stop on a segmentation fault in the main() function, but rather in a special __asan::AsanDie() function, in libclang_rt.asan_osx_dynamic.dylib. Obviously, AddressSanitizer is responsible for triggering the breakpoint. What is the actual stack trace?

(lldb) bt
* thread #1: tid = 0x13f073, 0x00000001000e30a0 libclang_rt.asan_osx_dynamic.dylib`__asan::AsanDie(), queue = 'com.apple.main-thread', stop reason = Heap buffer overflow detected
  * frame #0: 0x00000001000e30a0 libclang_rt.asan_osx_dynamic.dylib`__asan::AsanDie()
    frame #1: 0x00000001000e8198 libclang_rt.asan_osx_dynamic.dylib`__sanitizer::Die() + 88
    frame #2: 0x00000001000e0a29 libclang_rt.asan_osx_dynamic.dylib`__asan::ScopedInErrorReport::~ScopedInErrorReport() + 249
    frame #3: 0x00000001000e0151 libclang_rt.asan_osx_dynamic.dylib`__asan::ReportGenericError(unsigned long, unsigned long, unsigned long, unsigned long, bool, unsigned long, unsigned int, bool) + 3953
    frame #4: 0x00000001000e11e9 libclang_rt.asan_osx_dynamic.dylib`__asan_report_store1 + 57
    frame #5: 0x0000000100000da8 clang-asan`main + 328 at clang-asan.c:10
    frame #6: 0x00007fffa6c46255 libdyld.dylib`start + 1
(lldb) frame select 5
frame #5: 0x0000000100000da8 clang-asan`main + 328 at clang-asan.c:10
   7        for (int i = 0; i < 13; i++) {
   8            str[i] = hello[i];
   9        }
-> 10       str[13] = 0;
   11
   12       printf("%s\n", str);
   13

We can see that the asan library takes over as soon we attempt to store something into memory at line 10.

A couple other lines caught my attention. Let's start with:

AddressSanitizer report breakpoint hit. Use 'thread info -s' to get extended information about the report.

If we try it, we get a JSON output that nicely recaps the error, and that we can bring up if we need it again.

(lldb) thread info -s
thread #1: tid = 0x13f073, 0x00000001000e30a0 libclang_rt.asan_osx_dynamic.dylib`__asan::AsanDie(), queue = 'com.apple.main-thread', stop reason = Heap buffer overflow detected

{
  "access_size" : 1,
  "access_type" : 1,
  "address" : 105690555281181,
  "description" : "heap-buffer-overflow",
  "instrumentation_class" : "AddressSanitizer",
  "pc" : 4294970792,
  "stop_type" : "fatal_error"
}

The other line that piqued my interest was right after we launched the program:

AddressSanitizer debugger support is active. Memory error breakpoint has been installed and you can now use the 'memory history' command.

The documentation for the memory history command is:

(lldb) help memory history
     Print recorded stack traces for allocation/deallocation events associated with an address.

Syntax: memory history <address>

Sounds pretty powerful, let's give it a try.

(lldb) memory history str
  thread #4294967295: tid = 0x0001, 0x00000001000d8bf0 libclang_rt.asan_osx_dynamic.dylib`wrap_malloc + 192, name = 'Memory allocated by Thread 1'
    frame #0: 0x00000001000d8bf0 libclang_rt.asan_osx_dynamic.dylib`wrap_malloc + 192
    frame #1: 0x0000000100000c85 clang-asan`main + 37 at clang-asan.c:6
    frame #2: 0x00007fffa6c46254 libdyld.dylib`_dyld_process_info_notify_release + 44

We get the exact stack trace at the time this address in memory was allocated. In a more complex program, we would get the history of all the times the address was allocated and deallocated, making it a very powerful tool to understand cryptic memory bugs.

Putting it all to use

Back to my practical case, how did I put the address sanitizer to good use? I simply ran the test suite, compiled with the sanitizer, with lldb. Sure enough, it stopped on every line that could cause a crash. It turns out there were many cases where zxcvbn-c wrote past the end of allocated buffers, on the heap and on the stack. I fixed those cases in the C library and ran the tests again. Not a segfault in sight!

What next?

I've used memory tools in the past, but they were usually unwieldy, or put such a toll on performance that they were useless in any real-life case. Clang's address sanitizer turned out to be detailed, reliable, and surprisingly easy to use. I've heard of the miracles of Valgrind but macOS hardly supports it, making it a pain to use on my MacBook Pro.

Coupled with Clang's static analyzer, AddressSanitizer is going to become a mandatory stop for evaluating code quality. It's also going to be the first tool I grab when facing confusing memory issues. There are many more case where I could use early failure and memory history to debug my code. For example, if a program crashes when accessing member of a deallocated object, we could easily trace the event that caused the deallocation, saving hours of adding and reading logs to retrace just what happened.

Can you think of cases where the address sanitizer could be put to use? Cases where it would miss bugs or result in false positives? Tell me in the comments!