Index: docs/HardwareAssistedAddressSanitizerDesign.rst =================================================================== --- /dev/null +++ docs/HardwareAssistedAddressSanitizerDesign.rst @@ -0,0 +1,123 @@ +===================================================== +HardwareAssistedAddressSanitizer Design Documentation +===================================================== + +This page is a design document for +**HardwareAssistedAddressSanitizer** (or HWASAN) +a tool similar to :doc:`AddressSanitizer`, +but based on partial hardware assistance. + +The document is a draft, suggestions are welcome. + + +Introduction +============ + +:doc:`AddressSanitizer` +tags every 8 bytes of the application memory with a 1 byte tag (using *shadow memory*), +uses *redzones* to find buffer-overflows and +*quarantine* to find use-after-free. +The redzones, the quarantine, and, to a less extent, the shadow, are the +sources of AddressSanitizer's memory overhead. +See the `AddressSanitizer paper`_ for details. + +AArch64 has the `Address Tagging`_, a hardware feature that allows +software to use 8 most significant bits of a 64-bit pointer as +a tag. HardwareAssistedAddressSanitizer uses `Address Tagging`_ +to implement a memory safety tool, similar to :doc:`AddressSanitizer`, +but with smaller memory overhead and slightly different (mostly better) +accuracy guarantees. + +Algorithm +========= +* Every heap/stack/global memory object is forcibly aligned by `N` bytes + (`N` is e.g. 16 or 64) +* For every such object a random `K`-bit tag `T` is chosen (`K` is e.g. 4 or 8) +* The pointer to the object is tagged with `T`. +* The memory for the object is also tagged with `T` + (using a `N=>1` shadow memory) +* Every load and store is instrumented to read the memory tag and compare it + with the pointer tag, exception is raised on tag mismatch. + +Instrumentation +=============== + +Memory Accesses +--------------- +All memory accesses are prefixed with a call to a run-time function. +The function encodes the type and the size of access in its name; +it receives the address as a parameter, e.g. `__hwasan_load4(void *ptr)`; +it loads the memory tag, compares it with the +pointer tag, and executes `__builtin_trap` (or calls `__hwasan_error_load4(void *ptr)`) on mismatch. + +It's possible to inline this callback too. + +Heap +---- + +Tagging the heap memory/pointers is done by `malloc`. +This can be based on any malloc that forces all objects to be N-aligned. + +Stack +----- + +Special compiler instrumentation is required to align the local variables +by N, tag the memory and the pointers. +Stack instrumentation is expected to be a major source of overhead, +but could be optional. +TODO: details. + +Globals +------- + +TODO: details. + +Error reporting +--------------- + +Errors are generated by `__builtin_trap` and are handled by a signal handler. + + +Comparison with AddressSanitizer +================================ + +HardwareAssistedAddressSanitizer: + * Is less portable than :doc:`AddressSanitizer` + as it relies on hardware `Address Tagging`_ (AArch64). + Address Tagging can be emulated with compiler instrumentation, + but it will require the instrumentation to remove the tags before + any load or store, which is infeasible in any realistic environment + that contains non-instrumented code. + * May have compatibility problems if the target code uses higher + pointer bits for other purposes. + * May require changes in the OS kernels (e.g. Linux seems to dislike + tagged pointers passed from address space). + * **Does not require redzones to detect buffer overflows**, + but the buffer overflow detection is probabilistic, with roughly + `(2**K-1)/(2**K)` probability of catching a bug. + * **Does not require quarantine to detect heap-use-after-free, + or stack-use-after-return**. + The detection is similarly probabilistic. + +The memory overhead of HardwareAssistedAddressSanitizer is expected to be much smaller +than that of AddressSanitizer: +`1/N` extra memory for the shadow +and some overhead due to `N`-aligning all objects. + + +Related Work +============ +* `SPARC ADI`_ implements a similar tool mostly in hardware. +* `Effective and Efficient Memory Protection Using Dynamic Tainting`_ discusses + similar approaches ("lock & key"). +* `Watchdog`_ discussed a heavier, but still somewhat similar + "lock & key" approach. +* *TODO: add more "related work" links. Suggestions are welcome.* + + +.. _Watchdog: http://www.cis.upenn.edu/acg/papers/isca12_watchdog.pdf +.. _Effective and Efficient Memory Protection Using Dynamic Tainting: https://www.cc.gatech.edu/~orso/papers/clause.doudalis.orso.prvulovic.pdf +.. _SPARC ADI: https://lazytyped.blogspot.com/2017/09/getting-started-with-adi.html +.. _AddressSanitizer paper: https://www.usenix.org/system/files/conference/atc12/atc12-final39.pdf +.. _Address Tagging: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0024a/ch12s05s01.html + Index: docs/index.rst =================================================================== --- docs/index.rst +++ docs/index.rst @@ -84,6 +84,7 @@ PTHInternals PCHInternals ItaniumMangleAbiTags + HardwareAssistedAddressSanitizerDesign.rst Indices and tables