AddressSanitizer (ASan) is a C++ tool that finds memory bugs at runtime, such as use-after-free and out-of-bounds accesses. It is part of LLVM. At Google, we use ASan extensively. I just read the ASan paper to understand how it works. The paper itself is very readable. Here is a quick summary.
At compile time, ASan instruments memory accesses in the code, and at runtime it checks if the access is legitimate, by using shadow memory. ASan uses a custom allocator instead of malloc.
Shadow memory is memory allocated by the program such that every ordinary application address X has a corresponding shadow address Y, where metadata about X can be stored. You can map X to Y by a direct scale and offset, in which case the whole application address space is mapped to a single shadow address space, or you can map X to Y using table lookups (runs slower but is more flexible).
At compile time, ASan creates poisoned redzones around stack and global data. At runtime, it creates poisoned redzones around heap data. The addresses returned by the memory allocator are aligned (usually to 8 bytes). The alignment determines the minimum size of the redzones, and also the amount of compactness of the shadow memory (1/8th of the virtual address space).
For every byte, ASan records in shadow memory whether the byte is addressable or not. If the byte is not addressable, ASan also knows if the byte corresponds to a stack redzone, heap redzone, global redzone, or freed memory. At every memory access, ASan checks the shadow state for that address, and reports an error if the access is illegal.
The size of the redzone is somewhere between 32 and 128 bytes. If an access underflows or overflows by more than that, the error will not be detected.
The custom allocator picks blocks from the free list in FIFO order, so that each free block will stay free for as long as possible. This allows ASan to find use-after-free errors. Of course, if the use-after-free happens way later, when the freed block has been reallocated, then the bug won't be detected.
ASan's instrumentation happens right after LLVM optimizations, so it doesn't have to instrument accesses that are optimized away. Since the instrumentation is before register allocation, ASan doesn't instrument accesses due to register spills.
ASan uses shadow memory very efficiently, which allows it to find bugs with significantly less overhead than previous state-of-the-art tools.
A related tool (by the same team) is MSan, which finds use-of-uninitialized-memory bugs.
Comments
Post a Comment