Created
January 7, 2024 08:11
-
-
Save MaskRay/3f6dc64495f842923d5367c410e070d0 to your computer and use it in GitHub Desktop.
Revisions
-
MaskRay created this gist
Jan 7, 2024 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,347 @@ AddressSanitizer (ASan) is a compiler technology that checks addressability-related memory errors with some add-on checks. It consists of two parts: compiler instrumentation and runtime library. To put it in the simplest way, * The compiler instruments global variables, stack frames, and heap allocations to track shadow memory. * The compiler instruments memory access instructions to check shadow memory. * In case of an error, the inserted code calls a callback (implemented in the runtime library) to report an error with a stack trace. Normally the program will exit after the error message is printed. Clang 3.1 [implemented]() AddressSanitizer in 2011. GCC 4.8 [integrated](https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=37d6f666cae62d9d44c5aef4b2185e43635d5091) AddressSanitizer in 2012. [MSVC](https://learn.microsoft.com/en-us/cpp/sanitizers/asan) (starting in Visual Studio 2019 version 16.9) added `/INFERASANLIBS`. `compiler-rt/lib/asan` provides the runtime library for Clang and GCC. In the Linux kernel, [kasan: add kernel address sanitizer infrastructure](https://git.kernel.org/linus/0b24becc810dc3be6e3f94103a866f214c282394) introduced a runtime implementation in 2015. <!-- more --> ## Usage ## Shadow memory The core is shadow memory. Things such as global variables, stack variables, and heap allocated memory are called addressable. 8 bytes are called a granularity. A granularity of bytes are mapped to a shadow byte. Many platforms use a fixed shadow offset. Some use a dynamic shadow offset loaded from `__asan_shadow_memory_dynamic_address`. Specify `-mllvm -asan-force-dynamic-shadow` to force using a dynamic shadow offset. Android AArch32 is special and uses `__asan_shadow` For a memory access of to the address `addr`, AddressSanitizer conceptually converts the following code ```c *addr = ...; // [addr, addr+size) ``` to ```c // after instrumentation if (isPoisoned((uintptr_t)addr, size)) { reportError(addr); __builtin_unreachable(); } *addr = ...; ``` When `size<=8` and the access is aligned (`align >= size`), `isPoisoned` can be implemented as: ```cpp bool isPoisoned(uintptr_t addr, uintptr_t size) { int8_t shadow = *(addr/granularity + shadow_offset); return shadow && int8_t(addr%granularity+size-1) >= shadow; } ``` With the default granularity (8 bytes), when `size == 8`, `int8_t(addr%granularity+size-1) >= shadow;` is tautological and the check can be simplified to `*(addr/8+offset) != 0`. When `size==16 && min(size, align) >= granularity` (the access is aligned by the granularity), a similar `isPoisoned` can be used as well. ```cpp bool isPoisoned(uintptr_t addr, uintptr_t size) { int16_t shadow = *(int16_t*)(addr/granularity + shadow_offset); return shadow; // as shadow<granularity<=size, addr%granularity+size-1 >= shadow is tautological. } ``` For other accesses (unaligned and `size<=8`, `size==16 && align < granularity`, or `size>16`), we can perform two checks, one at the first byte and the other at the last byte. Two shadow bytes, if different, cover a region of of `2*granularity` bytes. When `size > 2*granularity`, some middle bytes are not covered and the implementation may have false negatives. ```c bool isPoisoned(uintptr_t addr, uintptr_t size) { int8_t shadow = *(addr/granularity + shadow_offset); if (shadow && int8_t(addr%granularity+size-1) >= shadow) return true; addr += size-1; shadow = *(addr/granularity + shadow_offset); if (shadow && int8_t(addr%granularity+size-1) >= shadow) return true; return false; } ``` Shadow memory is checked by interceptors and instrumented memory operands. An instrumented memory operand typically expands to an inline code sequence, but you can customize `asan-instrumentation-with-call-threshold` (default: 7000). If the number of memory accesses in a function exceeds `asan-instrumentation-with-call-threshold`, AddressSanitizer will call a runtime function to check the shadow memory. (See `-fsanitize-address-outline-instrumentation` below.) ## Function instrumentation AddressSanitizer instruments certain intrinsics, and certain library function calls, and interesting memory operands. ASan instrumentation converts `MemIntrinsic` intrinsics to `__asan_memset`/`__asan_memcpy`/`__asan_memmove` callbacks. The callbacks check the full range using `ASAN_WRITE_RANGE`. Some library function that perform memory accesses are recognized as builtins (e.g. `strcpy`, `strlen`). They need to marked with the function attribute `nobuiltin` to prevent them from being optimized out. These functions will be intercepted by the runtime library. For an interesting memory operand, see `isPoisoned` in the beginning. When the address is unaligned, the access spans two shadow bytes, and we select the `isPoisoned` implementation that checks one shadow byte (`size <= 8 && addr % align && addr%granularity+size > granularity`), `isPoisoned` may have false negatives when the first shadow byte is zero. ```cpp // clang++ -O0 -fsanitize=alignment a.cc int main() { char a[8]; auto *p = (long *)(a+1); *p = 1; // out-of-bounds write is not detected with granularity==8 return *p; } ``` `-fsanitize=alignment` can catch some missing checks. However, certain cases still cannot be caught. For example, with `-O1` or above, the `memcpy` call below is not optimized out. `-fsanitize=alignment` does not instrument the code and the implementation checks just one shadow byte, leading to a false negative. ```cpp // clang++ -O1 -fsanitize=address,alignment a.cc #include <string.h> int main(int argc, char *argv[]) { char a[8]; auto *p = (long *)(a+1); memcpy(p, &argv, sizeof(long)); return a[7]; } ``` As an optimization, within a basic block, two addresses do not need to be instrumented repeatedly, unless they are separated by a call instruction (2011-11). ## Global variable instrumentation See [AddressSanitizer: Global variable instrumentation](https://maskray.me/blog/2023-10-15-address-sanitizer-global-variable-instrumentation). ## Stack instrumentation ASan collects stack variables (`AllocaInst`) and sorts them by descending alignment (from low address to high address). Variables are padded with redzones and are either placed on the stack or on the heap for use-after-return detection. The layout of stack variables and redzones looks like the following: ``` left_redzone var0 middle_redzone var1 middle_redzone var2 right_redzone ``` The left redzone holds 4 words: * a magic value (`kCurrentStackFrameMagic = 0x41B58AB3`) * the address of the frame description string * the function address * unused Multiple shadow bytes of the variables and redzones are defined to provide better diagnostics. * 0: a variable whose lifetime is alive * 0xf8 (`kAsanStackUseAfterScopeMagic`): a variable whose lifetime has ended * 0xf1: the left redzone * 0xf2: middle redzones * 0xf3: the right redzone * 0xca (`kAsanAllocaLeftMagic`): the left redzone of a dynamic alloca (see the next section) * 0xcb (`kAsanAllocaRightMagic`): the right redzone of a dynamic alloca (see the next section) For each stack varaible, `VarAndRedzoneSize` computes the total size of the variable and its red zone on the right. ```cpp static uint64_t VarAndRedzoneSize(uint64_t Size, uint64_t Granularity, uint64_t Alignment) { uint64_t Res = 0; if (Size <= 4) Res = 16; else if (Size <= 16) Res = 32; else if (Size <= 128) Res = Size + 32; else if (Size <= 512) Res = Size + 64; else if (Size <= 4096) Res = Size + 128; else Res = Size + 256; return alignTo(std::max(Res, 2 * Granularity), Alignment); } ``` If `-fsanitize-address-stack-use-after-scope` (default) is enabled, when a variable gets out of scope, its shadow memory is filled with 0xf8 (`kAsanStackUseAfterScopeMagic`). Accessing the variable will lead to a `stack-use-after-scope` error. When the stack frame is out of the scope, the magic value in the left redzone is set to `kRetiredStackFrameMagic = 0x45E0360E`. There are some heuristics to remove instructions for memory operands that are always safe. First, `AllocaInst`s that can be optimized by mem2reg do not need instrumentation (2015-02). ([Non-instrumented alloca instructions in the entry block before the first instrumented alloca should not be moved around](https://reviews.llvm.org/D11339), otherwise the debug information will be broken.) [Direct in-bounds accesses to stack variables](https://reviews.llvm.org/D7583) do not need instrumentation (`AddressSanitizer::isSafeAccess`). Second, `StackSafetyGlobalAnalysis` (`-mllvm -asan-use-stack-safety=1`) can identify stack variables that are always safely accessed, which do not need instrumentation, e.g. [`int x; foo(&x); return x;`](https://github.com/llvm/llvm-project/issues/77047) (`isAllocaPromotable` is false and does not optimize the case). ### Stack use after return Similar to `stack-use-after-scope` detection, ASan performs `stack-use-after-return` detection. `-fsanitize-address-use-after-return=` accepts one of the following values: * `runtime` (default): instrumented code checks a global variable `__asan_option_detect_stack_use_after_return` to decide whether a fake stack frame is used. * `always`: instrumented code unconditionally creates a fake stack frame. This saves code size. * `never`: don't detect use-after-return When the instrumentation decides to create a fake stack frame, it allocates one using `__asan_stack_malloc_{0..10}(uptr ptr, uptr size)`. The runtime function may return nullptr, in which case a fake stack frame is unavailable, and `alloca` will be used to allocate the local stack frame; otherwise, stack variables and associated redzones are allocated on the fake stack frame. The local stack base needs `llvm.dbg.declare` to provide [reliable debug info for local variables at `-O0`](https://reviews.llvm.org/D41034). [Function argument spills are also placed before the `__asan_stack_malloc_*` call](https://reviews.llvm.org/D77182). This is for two purposes: * Location information of function arguments is correct when `__asan_stack_malloc_*` is called. * At `-O0`, an argument does not need to be spilled before storing into the reserved alloca, saving a stack slot. When the stack frame is out of the scope, the shadow memory of the fake stack is filled with 0xf5 (`kAsanStackAfterReturnMagic`) bytes. Smaller stack frames use an inline code sequence while a larger frame calls `__asan_stack_free_*`. Instrumentation inserts stack shadow unpoisoning code before each `ret/resume/cleanupret` instruction. If a function calls a noreturn function, it needs to unpoison the stack shadow before the noreturn function; otherwise if the stack is reused by another process, there may be a false positive. <https://github.com/google/sanitizers/issues/37> Instrumentation inserts `__asan_handle_no_return` calls before some noreturn functions (e.g. `_exit`), Interceptors of some noreturn functions call `__asan_handle_no_return`. <!-- TODO swapcontext 8410a867eb96c9b93f004f5236d544991f2cd0cf --> ### Dynamic alloca `AllocaInst::isStaticAlloca` checks whether an alloca is in the entry block and has a constant size. Such alloca instructions can be folded into the prolog/epilog code. Other alloca instructions are called dynamic. AddressSanitizer instrumentation changes an interesting dynamic alloca instruction to allocate a larger space to cover left, possible partial right, and right redzones. ``` (alignment_padding) left_redzone var (partial_right_redzone) right_redzone var%32 == 0 && alignment_padding%32 == 0 ``` The start address of the variable (`new_alloca+alignment`) is aligned to at least 32. The address minus the alignment gives us the start address of the left redzone. If the alignment is greater than 32, there may be padding on the left of the left redzone. The instrumentation inserts an `__asan_alloca_poison(&var, size)` call to poison the redzones. The left zone gets 0xca (`kAsanAllocaLeftMagic`) bytes while the right redzone gets 0x0xcb (`kAsanAllocaRightMagic`) bytes. 0xca and 0xcb identify the runtime error type `dynamic-stack-buffer-overflow`. Uses of the dynamic alloca instruction are replaced with `left_redzone+alignment`. The most recent dynamic alloca's address is stored in a local variable `DynamicAllocaLayout`, whose address is larger than every dynamic alloca. The redzone needs to be unpoisoned when the function returns or when an `llvm.stackrestore` instruction is encountered; otherwise, accessing a different, future alloca may get a false positive. Before each `ret` instruction, the instrumentation inserta an `__asan_allocas_unpoison` call to unpoison the region `[*DynamicAllocaLayout, DynamicAllocaLayout)`. <!-- TODO resume/cleanupret> Before each `llvm.stackrestore` instruction (for C99 VLA), the instrumentation calls `__asan_allocas_unpoison` to unpoison the region `[*DynamicAllocaLayout, saved_stack+llvm.get.dynamic.area.offset.i64())`. The approach works quite well but does not detect out-of-scope VLA accesses when `llvm.stackrestore` is present. Note: with `-O1` or above, certain `llvm.stackrestore` intrinsics can be optimized out (by `InstCombinerImpl::visitCallInst`). ```c void foo(int index, int len) { if (index > len) { char str[len]; p = str; // p[index] = '1'; // detectable when index < align(len, 32) + 32 } p[index] = '1'; // undetectable when `llvm.stackrestore` is present (-O0), because str has been unpoisoned. GCC does not detect this. } ``` When the dynamic alloca uses `llvm.lifetime.start`/`llvm.lifetime.end` intrinsics, the enabled-by-default `asan-use-after-scope` instrumentation calls `__asan_poison_stack_memory` before `llvm.lifetime.start` to poison the variable with 0xf8 (`kAsanStackUseAfterScopeMagic`) and calls `__asan_unpoison_stack_memory` after `llvm.lifetime.end`. ### Stack safety analysis `llvm/lib/Analysis/StackSafetyAnalysis.cpp` ## Error reporting When `-fsantize-recover=address` is specified, `__asan_report_*` calls are replaced with `__asan_report_*_noabort`. This can be used together with `ASAN_OPTIONS=halt_on_error=0` to recover from an error. Functions like `__asan_report_exp_load1` are related to optimization experiments <http://reviews.llvm.org/D8198> ## allocator There are two allocator classes: sanitizer_allocator_primary32.h and sanitizer_allocator_primary64.h. sanitizer_allocator_primary32.h can be used with 64-bit targets but is slow for lsan (https://github.com/google/sanitizers/issues/703). On AArch64, if the kernel is configured with `CONFIG_ARM64_VA_BITS_39=y`, `SizeClassAllocator64` cannot be used. On Linux, this needs to prevent collision with the executable (`ELF_ET_DYN_BASE`). ## heap-use-after-free `sizeof(ChunkHeader)=16` The first 8 bytes after `ChunkHeader` stores `atomic_uint64_t ChunkBase::free_context_id`. This coincides with the first word of user memory. ## `-fsanitize-address-stack-use-after-scope=` Use a reference which refers to a destroyed temporary variable. ## `-fsanitize=pointer-compare` and `-fsanitize=pointer-subtract` Used along with `-fsanitize=address` or `-fsanitize=kernel-address`. Instrument comparison operation (<, <=, >, >=) with pointer operands. `ASAN_OPTIONS=detect_invalid_pointer_pairs=2` reports an error when comparing two pointers referecing different objects. `ASAN_OPTIONS=detect_invalid_pointer_pairs=1` ignores the cases when either pointer is null. ## API `__asan_region_is_poisoned` `__asan_poison_memory_region` `__sanitizer_annotate_contiguous_container` (container) ## Error reporting frame description ## Issue suppression env `suppressions` `__asan_default_suppressions` ## allocator ## Misc GCC integrated a related technology called Mudflap in 2004. GCC 4.8 removed Mudflap. ### `-fsanitize-address-outline-instrumentation` ```c void store(char *a, short *b, int *c, long *d, __int128 *e) { *e = *d = *c = *b = *a = 1; } ``` By default the shadow memory checks are inlined. If `-fsanitize-address-outline-instrumentation` is specified, AddressSanitizer instrumentation will call `__asan_store{1,2,4,8,16}` with a single argument (the address) to check shadow memory. If `-fsanitize-address-outline-instrumentation -mllvm=-asan-optimize-callbacks` is specified, AddressSanitizer instrumentation will call callbacks with a special calling convention to preserve most registers. ``` // lowered from llvm.asan.check.memaccess calls callq __asan_check_store_add_1_RDI movb $1, (%rdi) callq __asan_check_store_add_2_RSI movw $1, (%rsi) callq __asan_check_store_add_4_RDX movl $1, (%rdx) callq __asan_check_store_add_8_RCX movq $1, (%rcx) callq __asan_check_store_add_16_R8 ``` This current implementation is specific to x86-64 and utilizes `def GR64PLTSafe : RegisterClass<...>` which preserves every register except R10/R11. The callbacks are implemented as hidden symbols in `libclang_rt.asan_static.a` (`compiler-rt/lib/asan/asan_rtl_x86_64.S`), which is linked even for `-shared`. To support `-shared -Wl,-z,defs` links that don't define `__asan_report_load{1,2,4,8,16}`, `__asan_check_*` symbols reference `__asan_report_load{1,2,4,8,16}` as weak symbols. (https://reviews.llvm.org/D118813#3292073)