HardwareAssistedAddressSanitizer Design Documentation

This page is a design document for HardwareAssistedAddressSanitizer (or HWASAN) a tool similar to AddressSanitizer, but based on partial hardware assistance.

The document is a draft, suggestions are welcome.

Introduction

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 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 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.