Hardware-assisted AddressSanitizer Design Documentation¶

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

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 Address Tagging (or top-byte-ignore, TBI), a hardware feature that allows software to use the 8 most significant bits of a 64-bit pointer as a tag. HWASAN uses Address Tagging to implement a memory safety tool, similar to AddressSanitizer, but with smaller memory overhead and slightly different (mostly better) accuracy guarantees.

Intel’s Linear Address Masking (LAM) also provides address tagging for x86_64, though it is not widely available in hardware yet. For x86_64, HWASAN has a limited implementation using page aliasing instead.

Algorithm¶

Every heap/stack/global memory object is forcibly aligned by TG bytes (TG is e.g. 16 or 64). We call TG the tagging granularity.
For every such object a random TS-bit tag T is chosen (TS, or tag size, 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 TG=>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.

For a more detailed discussion of this approach see https://arxiv.org/pdf/1802.09517.pdf

Short granules¶

A short granule is a granule of size between 1 and TG-1 bytes. The size of a short granule is stored at the location in shadow memory where the granule’s tag is normally stored, while the granule’s actual tag is stored in the last byte of the granule. This means that in order to verify that a pointer tag matches a memory tag, HWASAN must check for two possibilities:

the pointer tag is equal to the memory tag in shadow memory, or
the shadow memory tag is actually a short granule size, the value being loaded is in bounds of the granule and the pointer tag is equal to the last byte of the granule.

Pointer tags between 1 to TG-1 are possible and are as likely as any other tag. This means that these tags in memory have two interpretations: the full tag interpretation (where the pointer tag is between 1 and TG-1 and the last byte of the granule is ordinary data) and the short tag interpretation (where the pointer tag is stored in the granule).

When HWASAN detects an error near a memory tag between 1 and TG-1, it will show both the memory tag and the last byte of the granule. Currently, it is up to the user to disambiguate the two possibilities.

Instrumentation¶

Memory Accesses¶

In the majority of cases, memory accesses are prefixed with a call to an outlined instruction sequence that verifies the tags. The code size and performance overhead of the call is reduced by using a custom calling convention that

preserves most registers, and
is specialized to the register containing the address, and the type and size of the memory access.

Currently, the following sequence is used:

// int foo(int *a) { return *a; }
// clang -O2 --target=aarch64-linux-android30 -fsanitize=hwaddress -S -o - load.c
[...]
foo:
      stp     x30, x20, [sp, #-16]!
      adrp    x20, :got:__hwasan_shadow               // load shadow address from GOT into x20
      ldr     x20, [x20, :got_lo12:__hwasan_shadow]
      bl      __hwasan_check_x0_2_short_v2            // call outlined tag check
                                                      // (arguments: x0 = address, x20 = shadow base;
                                                      // "2" encodes the access type and size)
      ldr     w0, [x0]                                // inline load
      ldp     x30, x20, [sp], #16
      ret

[...]
__hwasan_check_x0_2_short_v2:
      sbfx    x16, x0, #4, #52                        // shadow offset
      ldrb    w16, [x20, x16]                         // load shadow tag
      cmp     x16, x0, lsr #56                        // extract address tag, compare with shadow tag
      b.ne    .Ltmp0                                  // jump to short tag handler on mismatch
.Ltmp1:
      ret
.Ltmp0:
      cmp     w16, #15                                // is this a short tag?
      b.hi    .Ltmp2                                  // if not, error
      and     x17, x0, #0xf                           // find the address's position in the short granule
      add     x17, x17, #3                            // adjust to the position of the last byte loaded
      cmp     w16, w17                                // check that position is in bounds
      b.ls    .Ltmp2                                  // if not, error
      orr     x16, x0, #0xf                           // compute address of last byte of granule
      ldrb    w16, [x16]                              // load tag from it
      cmp     x16, x0, lsr #56                        // compare with pointer tag
      b.eq    .Ltmp1                                  // if matches, continue
.Ltmp2:
      stp     x0, x1, [sp, #-256]!                    // save original x0, x1 on stack (they will be overwritten)
      stp     x29, x30, [sp, #232]                    // create frame record
      mov     x1, #2                                  // set x1 to a constant indicating the type of failure
      adrp    x16, :got:__hwasan_tag_mismatch_v2      // call runtime function to save remaining registers and report error
      ldr     x16, [x16, :got_lo12:__hwasan_tag_mismatch_v2] // (load address from GOT to avoid potential register clobbers in delay load handler)
      br      x16

Heap¶

Tagging the heap memory/pointers is done by malloc. This can be based on any malloc that forces all objects to be TG-aligned. free tags the memory with a different tag.

Stack¶

Stack frames are instrumented by aligning all non-promotable allocas by TG and tagging stack memory in function prologue and epilogue.

Tags for different allocas in one function are not generated independently; doing that in a function with M allocas would require maintaining M live stack pointers, significantly increasing register pressure. Instead we generate a single base tag value in the prologue, and build the tag for alloca number M as ReTag(BaseTag, M), where ReTag can be as simple as exclusive-or with constant M.

Stack instrumentation is expected to be a major source of overhead, but could be optional.

Globals¶

Most globals in HWASAN instrumented code are tagged. This is accomplished using the following mechanisms:

The address of each global has a static tag associated with it. The first defined global in a translation unit has a pseudorandom tag associated with it, based on the hash of the file path. Subsequent global tags are incremental from the previously-assigned tag.

The global’s tag is added to its symbol address in the object file’s symbol table. This causes the global’s address to be tagged when its address is taken.

When the address of a global is taken directly (i.e. not via the GOT), a special instruction sequence needs to be used to add the tag to the address, because the tag would otherwise take the address outside of the small code model (4GB on AArch64). No changes are required when the address is taken via the GOT because the address stored in the GOT will contain the tag.

An associated hwasan_globals section is emitted for each tagged global, which indicates the address of the global, its size and its tag. These sections are concatenated by the linker into a single hwasan_globals section that is enumerated by the runtime (via an ELF note) when a binary is loaded and the memory is tagged accordingly.<