Do not look directly at the Address Sanitizer Map

Photo by Joshua Sortino on Unsplash

This article talks about the challenges of dealing with Address Sanitizer’s memory use in Undo’s LiveRecorder time travel debug system — but it’s really a glimpse into how clever ASAN is and what magic you can achieve with some creative use of Linux userspace APIs.

It’s also a tenuous excuse to revisit Episode III: The Backstroke of the West and the later Backstroke of the West Redux.

(NB. Console output in this article has small edits for readability but the general results should all be repeatable)

Address Sanitizer (ASAN)

ASAN is a technology for catching a variety of memory access bugs. It uses compile time instrumentation of code, plus a runtime library to identify some common programming bugs (relating to memory use) at runtime.

See the Clang Address Sanitizer Docs for some more details.

We’re going to look briefly at how ASAN itself uses memory and then talk about the fun that causes for time travel debugging (in particular, for saving recordings of program history).

ASAN maps a lot of (virtual) memory.

To start off, we’ll run a simple Hello World-style program, compiled for ASAN, under GDB (the GNU debugger):

$> gdb hello_asan 
[...]
(gdb) start
Temporary breakpoint 1 at 0x401225
Starting program: [...]/hello_asan 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".

Temporary breakpoint 1, 0x0000000000401225 in main ()

The start command in GDB runs the program up to the start of its main function. At this point, the C runtime has been set up and we’re ready to run the program itself. The libasan library has also been initialized, including the setup of memory maps it uses internally.

We can ask GDB to list all the program’s memory maps for us. This will show, amongst other details, the memory addresses that are available and the permissions with which they can be accessed:

(gdb) info proc mappings 
process 767978
Mapped address spaces:

          Start Addr           End Addr       Size     Offset  Perms  objfile
            0x400000           0x401000     0x1000        0x0  r--p   [...]/hello_asan
[... various normal-looking maps here ...]
          0x7fff7000         0x8fff7000 0x10000000        0x0  rw-p   
          0x8fff7000      0x2008fff7000 0x20000000000     0x0  ---p   
       0x2008fff7000     0x10007fff8000 0xdfff0001000     0x0  rw-p   
      0x600000000000     0x603000000000 0x3000000000      0x0  ---p   
      0x603000000000     0x603000010000    0x10000        0x0  rw-p   
      0x603000010000     0x603e00000000 0xdffff0000       0x0  ---p   
      0x603e00000000     0x603e00010000    0x10000        0x0  rw-p   
[... more maps follow ...]

Well, that all seems reasonable … wait, what!? Some of those Size values (corresponding to the number of bytes mapped) look really, really big. For example:

Start Addr           End Addr       Size          Offset Perms  objfile
[ ... ]
0x2008fff7000        0x10007fff8000 0xdfff0001000 0x0    rw-p
[ ... ]

That is 14 Terabytes of data!

That single range of memory is over 400 times larger than the physical RAM available in my laptop. It’s almost 50 times larger than the /home volume on its SSD.

ASAN *really* maps a lot of (virtual) memory.

Whilst the amount of data this implies seems scary, the RSS (Resident Set Size) tells a different story (remember, ps lists sizes in KB):

$> ps -p 767978 -o pid,user,rss,size,cmd
    PID USER       RSS        SIZE CMD
 249298 mwillia+  5948 15032405748 [...]/hello_asan

Only about 6MB of physical memory is being used, even though the overall size in virtual memory is around 15TB. We might guess that the data is currently paged out to disk — but that can’t be the answer, it wouldn’t even fit on my disk!

What is it doing with all that space? ASAN magic.

The details of what’s going on in there are beyond the scope of this article but it is really cool stuff.

ASAN allocates large amounts of shadow memory to store metadata relating to the program’s memory use. This reserves lots of address space so its instrumentation can use more efficient code when accessing the metadata. For full details, see the AddressSanitizer paper.

We’re going to concentrate, instead, on the problems this poses when we want to represent that state on disk.

A large quantity of nothing

Isn’t this still a ridiculous memory footprint? When your application is running normally it’s actually not at all. There’s a lot of virtual address space in use but the vast majority of it will never be touched.

ASAN only needs to access areas of its shadow memory that relate to the program’s actual memory accesses. Even for a demanding program, that will rarely make up a significant fraction of the total available address space. As a result, most of the shadow memory will not be touched either.

Anonymous memory maps (such as ASAN’s shadow memory) nominally contain zeroes until they are initialized — but until they’re accessed they don’t need physical memory allocated at all. The kernel knows the memory is logically zero; it can provide some real zeroes on demand if they turn out to be wanted.

The result is that the physical memory used by the ASAN map is far more likely to be measured in kilobytes or megabytes than in terabytes.

Most of the data in ASAN’s big map is trivially zero because it is never set.

Storing a large quantity of nothing

LiveRecorder is a time travel debugging product. It creates a recording file that contains the complete history of a program’s execution.

This recording can be replayed later at any time, even on another machine, and debugged forwards and backwards in time to understand what it did.

A recording file from LiveRecorder needs to store:

• Initial program state (registers and memory)
• What non deterministic events happen during program history
• (as an optimization) some interim snapshots throughout time

For most of the initial memory state (and interim snapshots) we can just store the contents of memory maps directly into the recording file, compressing them using LZ4. Memory maps are not generally huge but we routinely handle maps in the tens of GB (and will happily go higher where needed).

Nonetheless, naively saving a 14 TB map is going to be pretty slow, even with compression.

Our ASAN map is going to drag on performance. Moreover, it’s mostly zeroes, so it seems a bit of a waste to store it all — this is an opportunity to be Clever.

We can store that ASAN map! Somehow…

Option 1: Just compress it

Compression eliminates redundancy in data, so we might hope to just throw those zeroes into a compression algorithm and have it take care of everything.

Unfortunately that doesn’t work out as well as we might hope. Firstly, that’s still a lot of data to process (even if zeroes are very boring data) so it’ll take quite a bit of CPU time to compress it.

Secondly, LZ4 isn’t optimized for directly processing this amount of identical data — it’s simply not going to notice all the opportunities for compression.

To see this play out, we can construct a smaller example on the console:

$> dd if=/dev/zero of=zero.bin bs=1G count=14
14+0 records in
14+0 records out
15032385536 bytes (15 GB, 14 GiB) copied, 28.1574 s, 534 MB/s
$> time lz4 zero.bin 
Compressed filename will be : zero.bin.lz4 
Compressed 15032385536 bytes into 59003407 bytes ==> 0.39%                     

real    0m33.110s
user    0m7.111s
sys     0m11.453s

We’ve created a 14GB file full of only zeros and compressed it. LZ4 is a very fast compression algorithm but even so it took 33 seconds on my laptop to compress all these zeros. The resulting file is 59MB in size.

Assuming this will scale linearly with input size, our experiment suggests the ASAN map, at 14TB, should require 9 hours of compression and 56GB of storage, just to represent all the zeros it contains.

This would not be viable for a product that is regularly run in CI test suites, which themselves could quite reasonably run many ASAN-enabled binaries.

We need to do better.

This approach to compression is not acceptable.

Option 2: Filter out the zeroes ourselves

The first obvious improvement would be to improve how we represent the data before compression. We have special knowledge that there will be large runs of zeros, so we could transform them into some other form.

For instance, we might apply run length encoding to relevant portions of the data before using LZ4 compression.

This would solve our output size problems. It would also probably reduce our CPU overhead somewhat — but 14TB is still a lot of memory to iterate through all the bytes in.

We still don’t have a viable answer.

We need a fundamentally different approach, rather than directly examining all the zero data.

Option 3: Skip the zero regions entirely

There’s another shortcut we can take here — one that will enable us to avoid even reading the zero values we need to represent.

Our giant ASAN map is allocated as anonymous memory, so we know it will all start out at zero and remain that way until the program writes to it. In fact, most of the map will never be accessed by the program. Pages that have never been accessed can certainly not have been written.

If we could inspect our giant map and rule out all pages that were never accessed we would be able to skip a lot of zero-checking!

Since one zero is much the same as another, this knowledge would let us effectively build the run-length encoding we mentioned above but without the bother of actually counting the zeros.

This approach might give us the advantage we need.

Our algorithm for compressing program memory would look something like this pseudocode:

for map in program_memory_maps:
    for page in map:
        if not accessed(page):
            # just store an "empty page" record, no need to retrieve the data
            # or compress it
            write_placeholder_to_file(page)
        else:
            # fetch the real data
            data = fetch_page(page)
            # compress and store the data
            write_data_to_file(data)

An aside — the /proc filesystem

The Linux /proc filesystem contains (amongst other system state) directories for each process running on the system, one for each integer Process ID (PID).

For instance, the /proc/1234/maps file would contains a list of all the memory ranges currently mapped in process 1234. This is actually what GDB reads in order to provide the info proc mappings output we saw above.

Here’s how it looks for an instance of top:

$> cat /proc/1302967/maps
561a30a8d000-561a30a91000 r--p 00000000 fd:01 1847867    /usr/bin/top
561a30a91000-561a30aa5000 r-xp 00004000 fd:01 1847867    /usr/bin/top
561a30aa5000-561a30aac000 r--p 00018000 fd:01 1847867    /usr/bin/top
561a30aac000-561a30aad000 r--p 0001e000 fd:01 1847867    /usr/bin/top
561a30aad000-561a30aae000 rw-p 0001f000 fd:01 1847867    /usr/bin/top
561a30aae000-561a30ae0000 rw-p 00000000 00:00 0 
561a31959000-561a31a27000 rw-p 00000000 00:00 0          [heap]
7f0b0d000000-7f0b1a5b7000 r--p 00000000 fd:01 1853146    /usr/lib/locale/locale-archive
7f0b1a5bb000-7f0b1a5dc000 rw-p 00000000 00:00 0 
7f0b1a5dc000-7f0b1a5df000 r--p 00000000 fd:01 1860410    /usr/lib64/libnuma.so.1.0.0
7f0b1a5df000-7f0b1a5e5000 r-xp 00003000 fd:01 1860410    /usr/lib64/libnuma.so.1.0.0
7f0b1a5e5000-7f0b1a5e7000 r--p 00009000 fd:01 1860410    /usr/lib64/libnuma.so.1.0.0
7f0b1a5e7000-7f0b1a5e8000 ---p 0000b000 fd:01 1860410    /usr/lib64/libnuma.so.1.0.0
7f0b1a5e8000-7f0b1a5e9000 r--p 0000b000 fd:01 1860410    /usr/lib64/libnuma.so.1.0.0
7f0b1a5e9000-7f0b1a5ea000 rw-p 0000c000 fd:01 1860410    /usr/lib64/libnuma.so.1.0.0
7f0b1a5ea000-7f0b1a5ee000 r--p 00000000 fd:01 1849445    /usr/lib64/libgpg-error.so.0.33.0

Some files (like the above) are human-readable ASCII, some are ASCII but designed for easy parsing (e.g. the alternate smaps representation of the above data) and some are binary data.

These files provide a huge variety of process metadata of interest to a curious sysadmin or developer. Sometimes, it’s surprising what information is actually available…

Finding zero pages without even looking at them

This brings us back to the title of this article: we have a need to find lots of pages full of zeros but we don’t actually want to have the overhead of reading them.

Fortunately, Linux supplies the mechanisms we need to find this out — given some lateral thinking, of course. The answer is within the /proc filesystem and a little-known file called pagemap.

This will give us an approach to tackle our original problem by helping us infer where the zeroes are.

Ready to strike back against giant areas of zero data.

The pagemap file contains a series of 64-bit words, one for each page in the address space of that process. Each word is a bit field: by reading the (binary) data from this file we can determine which pages are backed by genuine storage and which are essentially empty.

In particular, see bits 62 (“page swapped”) and 63 (“page present”). If we know a page is within a range of anonymous memory then we can expect that either:

• It is present in memory (present)
• It is on disk, swapped out
• It has no physical storage because it has never been set to non-zero

Since a page is typically (on x86, at least) 4KB in size this allows us to check for empty pages in our ASAN map orders of magnitude faster than by accessing the memory directly (and without incurring the overhead of accessing the data using ptrace or similar).

Putting it together — storing that nothing

Now we have our efficient source of information about zero pages, we can make Option 3 a reality.

As we save the memory state of a program out to disk, we can cut up regions of memory that are (or might be) populated with data and regions that definitely aren’t.

We dice up the memory so we process only the (potentially) interesting parts.

We can avoid the overhead of just trying to compress everything whilst still avoiding the time penalty of inspecting all the data directly. Our pseudocode from above ends up looking like this:

for map in program_memory_maps:
    for page in map:
        if anonymous(page) and not (swapped(page) or present(page)):
            # the page is anonymous memory and must still contain zeroes:
            # just store an "empty page" record, no need to retrieve the data
            # or compress it
            write_placeholder_to_file(page)
        else:
            # fetch the real data
            data = fetch_page(page)
            # compress and store the data
            write_data_to_file(data)

Using UDB to save a recording with ASAN maps

This is, in fact, the exact approach used by LiveRecorder and UDB.

We can demonstrate the success of this technique by saving a recording in UDB. We’ll start our hello_asan program in deferred recording mode to let libasan initialize, then enable recording. This ensures that the giant shadow map will be present right at the start of recorded history.

$> udb --defer-recording ./hello_asan
[ ... ]
not running> start
[ ... ]
Temporary breakpoint 1, 0x0000000000401225 in main ()
not recording> urecord

No more reverse-execution history.
Have reached start of recorded history.
0x0000000000401225 in main ()
recording 1> 

We’ve started recording and we know the ASAN map is already in memory (exactly the same as for the plain GDB example above). We’re at the start of recorded history (hence the 1, our current internal timebase value, in the prompt).

Normally we’d record some program activity but we’re only interested in the initial state here. Lets save the recording and see how we get on — remember, we’d expect 9 hours of compression work and about 56GB of storage if we were just naively compressing:

recording 1> usave hello_asan.undo

Running the above command takes around 30 seconds on my laptop. That’s certainly not fast. For a program this size but without ASAN we’d probably expect less than 1 second. Still, we’ve achieved a speedup of over 1000x compared to just compressing.

Lets check how big the resulting file is:

$> ls -lh hello_asan.undo
-rw-r--r--. 1 mwilliamson sysadmin 8.1M Feb  8 18:20 hello_asan.undo

Not bad at all — roughly a 7000x improvement in size compared to LZ4 compression alone. And, incidentally, as this is a LiveRecorder recording this file also contains other data (not just zeroes!)

With that solved, we’re free get back to work. Time to start solving all our memory allocation bugs.

Come on, use-after-free isn’t that bad, is it?