Resources

AddressSanitizer and Undo are two tools that can be used to find bugs in your code. This article compares the two tools, and shows how they can be used together to debug issues more effectively that either tool alone.

What is AddressSanitizer?

AddressSanitizer (ASan) is a compiler extension and runtime library, originally developed by Google. It has since been integrated into many compilers, including Clang/LLVM and GCC. It can be enabled at compile time by compiling the application with the -fsanitize=address option.

AddressSanitizer works by conceptually dividing the applications address space into two regions: one that the application uses and a “shadow” region. The runtime library replaces the malloc and free operation such that for every memory map created in the application region, a corresponding map is created in the shadow region. When the application map is freed, the shadow map is filled with “poison” values. AddressSanitizer modifies how the compiler generates machine code so that whenever it reads/writes memory, it also checks that the shadow map doesn’t contain poison values. See the AddressSanitizer algorithm for more details.

This allows AddressSanitizer to detect a wide variety of memory access bugs, including use-after-free bugs, buffer overflow bugs, and memory leaks. When AddressSanitizer detects an issue, its default behavior is to print some diagnostics and make the program exit immediately.

Key takeaways

• AddressSanitizer can detect use-after-free, buffer overflows, memory leaks and other types of bugs.
• AddressSanitizer can be enabled using the -fsanitize=address flag in GCC/Clang.
• AddressSanitizer instruments the code to insert runtime checks before each memory access operation.

What is Undo?

Undo is a time travel debugging solution for large-scale enterprise applications. When there’s a bug in your software, you can use Undo to capture the bug in a recording file (capturing the full program execution in a single binary file) and to step back in the recording to examine the full state of the program at any point in time.

Undo comes with 2 components:

1. LiveRecorder: for recording the runtime behavior of an application and saving it as a portable recording.
2. UDB: for replaying recording files (or live debug sessions) back and forth in time to see what happened.

AddressSanitizer vs Undo: How do they compare?

ASan has to be enabled at compile time, and since the clang documentation recommends against using ASan in production, this usually means the application needs to be recompiled as an internal debug build to use ASan. 

Undo on the other hand works well on production applications (as long as symbols are available when replaying the recording), so a special build isn’t required.

ASan and Undo both require additional memory when running the application. The memory overhead of ASan largely depends on the memory allocations the application performs; fewer, larger maps have a lower overhead than many small maps. ASan also imposes a larger (up to 3x) memory overhead for stack memory. Additionally, ASan uses a very large (but mostly unused) memory map for the shadow region. This usually doesn’t matter, unless memory overcommit mode is disabled on the system. In that case, the system will run out of memory and kill the application when ASan tries to create the shadow map.

The memory overhead introduced by Undo is usually less than 2x. While Undo doesn’t require overcommit mode like ASan, we still recommend using it.

In terms of execution speed, Google’s documentation of ASan says “The average slowdown of the instrumented program is ~2x”.

The slowdown of Undo is highly workload dependent. Many real-world programs can be recorded running at better than half-speed. For those with more threads, expect 1.5 – 5x slowdown per thread. Undo’s dynamic just-in-time instrumentation captures only the minimum data required to replay the process – 99% of the program state can be reconstructed on demand, so only the non-deterministic inputs need to be recorded. (see performance benchmarks)

Detecting vs understanding errors

Perhaps the biggest difference between ASan and Undo is that, while they’re both tools for improving software quality and stability, they’re useful at different points in the process. ASan (and other sanitizers, like ThreadSanitizer) excel at detecting potential issues, but don’t offer much support for working out why the application tried to perform an invalid access memory.

In contrast, Undo does not detect that the program it’s recording is behaving incorrectly, but once you’ve recorded an occurrence of a bug, you can find out exactly the sequence of events that caused it to happen.

Therefore, the natural question to ask is:

Can Undo find the cause of issues that ASan has detected?

Using Undo and AddressSanitizer together

Let’s try an example of combining Undo and ASan to detect and root-cause a bug.

For this demonstration, we have created a simple program called malloc-var. The program is intended to allocate an integer on the heap, then increment it. However the program has a bug; let’s run the program to see it:

$> cd examples/
$> make malloc-var
$> ./malloc-var
Set the value to 42
Incremented value from 42 to 0

Well that’s not right, so we’ll try using ASan and Undo’s LiveRecorder tool to locate and root-cause the bug. (We’re also going to pretend we aren’t allowed to read the source code of malloc-var unless one of our tools tells us that a line is of interest. This is to simulate how we might debug a real application that we aren’t familiar with, rather than a 22 line example program).

First, we’ll recompile malloc-var with -fsanitize=address, and rerun it under LiveRecorder:

$> make CFLAGS='-fsanitize=address -g -O0' malloc-var
$> live-record -o malloc-var.undo ./malloc-var
live-record: Maximum event log size is 1G.
Set the value to 42
=================================================================
==571059==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000014 at pc 0x5602a42402d5 bp 0x7ffc3bac05a0 sp 0x7ffc3bac0590
READ of size 4 at 0x602000000014 thread T0
    #0 0x5602a42402d4 in increment_pointed_value /home/dstevenson/undo/release/examples/malloc-var.c:12
    #1 0x5602a4240373 in main /home/dstevenson/undo/release/examples/malloc-var.c:23
    #2 0x7f999a7d3082 in __libc_start_main ../csu/libc-start.c:308
    #3 0x5602a424018d in _start (/home/dstevenson/undo/release/examples/malloc-var+0x118d)

0x602000000014 is located 0 bytes to the right of 4-byte region [0x602000000010,0x602000000014)
allocated by thread T0 here:
    #0 0x7f999aaae808 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cc:144
    #1 0x5602a4240309 in main /home/dstevenson/undo/release/examples/malloc-var.c:18
    #2 0x7f999a7d3082 in __libc_start_main ../csu/libc-start.c:308

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/dstevenson/undo/release/examples/malloc-var.c:12 in increment_pointed_value
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa[04]fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: 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
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  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
  Shadow gap:              cc
==571059==ABORTING
live-record: Saving to /home/dstevenson/undo/release/examples/malloc-var.undo ...
live-record: Saving     99%

live-record: Termination recording written to /home/dstevenson/undo/release/examples/malloc-var.undo
live-record: Detaching...

This error message has a lot of information, but the main takeaway is that ASan detected a heap buffer overflow in malloc-var.c on line 12. If we peek at that line, we can infer that the memory referenced by ptr_to_value_to_increment must contain the value 0, but it’s not immediately obvious why:

printf("Incremented value from %d to %d\n", old, *ptr_to_value_to_increment);

However, we also saved a recording of the program, so let’s load that in Undo’s UDB debugger, jump to the end of the recording and look at the backtrace:

$> udb malloc-var.undo
[...]
start 1> ugo end
[...]
end 66,947,821> backtrace
#0  __sanitizer::internal__exit (exitcode=1) at ../../../../src/libsanitizer/sanitizer_common/sanitizer_linux.cc:429
#1  0x00007f999aad6e97 in __sanitizer::Die () at ../../../../src/libsanitizer/sanitizer_common/sanitizer_flags.h:37
#2  0x00007f999aab852c in __asan::ScopedInErrorReport::~ScopedInErrorReport (this=0x7ffc3babf926, __in_chrg=<optimised out>) at ../../../../src/libsanitizer/asan/asan_report.cc:185
#3  0x00007f999aab7fa3 in __asan::ReportGenericError (pc=94569343746773, bp=bp@entry=140721309615520, sp=sp@entry=140721309615504, addr=105690555219988, is_write=is_write@entry=false,
	access_size=access_size@entry=4, exp=0, fatal=true) at ../../../../src/libsanitizer/asan/asan_report.cc:458
#4  0x00007f999aab8ccb in __asan::__asan_report_load4 (addr=<optimised out>) at ../../../../src/libsanitizer/asan/asan_rtl.cc:118
#5  0x00005602a42402d5 in increment_pointed_value (ptr_to_value_to_increment=0x602000000014) at malloc-var.c:12
#6  0x00005602a4240374 in main () at malloc-var.c:23
end 66,947,821>

Most of the backtrace is the code ASan calls to report the error, but in stack frame #5 we’re on line 12 in our code. Let’s place a watchpoint on ptr_to_value_to_increment, and reverse to see where that pointer came from:

end 66,947,821> frame 5
end 66,947,821> watch ptr_to_value_to_increment
end 66,947,821> reverse-continue
Continuing.

Hardware watchpoint 1: ptr_to_value_to_increment

Was = (int *) 0x602000000014
Now = (int *) 0x602000000010
increment_pointed_value (ptr_to_value_to_increment=0x602000000010) at malloc-var.c:11
11		ptr_to_value_to_increment += 1;
0% 3,007>

Reversing has taken us back to line 11, where we increment the pointer. But from the name of the function (increment_pointed_value) and the intended behavior of the program we can infer that we actually wanted to increment the value on the heap, not the value of the pointer.

And with that, we’ve root-caused this (very simple) bug; the corrected source code of malloc-var is:

1	/* This is free and unencumbered software released into the public domain.
2	 * Refer to LICENSE.txt in this directory. */
3    
4	#include <stdio.h>
5	#include <stdlib.h>
6    
7	static void
8	increment_pointed_value(int *ptr_to_value_to_increment)
9	{
10		int old = *ptr_to_value_to_increment;
11 -	ptr_to_value_to_increment += 1;
   +	*ptr_to_value_to_increment += 1;
12		printf("Incremented value from %d to %d\n", old, *ptr_to_value_to_increment);
13	}
14    
15	int
16	main(void)
17	{
18		int *ptr = malloc(sizeof(int));
19    
20		*ptr = 42;
21		printf("Set the value to %d\n", *ptr);
22    
23		increment_pointed_value(ptr);
24    
25		free(ptr);
26    
27		return EXIT_SUCCESS;
28	}

We can also rerun malloc-var to prove that this fixes the bug:

$> ./malloc-var
Set the value to 42
Incremented value from 42 to 43

Caveats

Undo is compatible with ASan, but for some features a little configuration is required. Undo’s tools have the ability to attach to running processes, but in order to attach to applications that use Asynchronous I/O, the application must have been started with a special preload library. However, ASan’s runtime library must be loaded before all other shared libraries, and this has to be manually configured by setting the LD_PRELOAD environment variable.

# Compile examples/aio.c with AddressSanitizer
$> make CFLAGS=-fsanitize=address aio

# Start my-program, with the Undo Async I/O preload library
$> LD_PRELOAD=libasan.so:tools/libundo_aio_preload_x64.so ./my-program &

# Attach LiveRecorder to the process.
$> live-record -p $! -o recording.undo

Conclusion

In conclusion, AddressSanitizer and Undo are complementary tools that work well together to enhance developer productivity and improve the quality and correctness of applications developed with their help.

Interested in seeing Undo in action? Book a slot with one of our Solutions Engineers for a quick demo and determine whether this will work in your environment.