design document for a hardware-assisted memory safety (HWAMS) tool, similar to AddressSanitizer

[kcc]

Summary

preliminary design document for a hardware-assisted memory safety (HWAMS) tool, similar to AddressSanitizer
The name TaggedAddressSanitizer and the rest of the document, are early draft, suggestions are welcome.

The code will follow shortly.

[kcc]

minor edit (explained shadow)

[eugenis]

docs/TaggedAddressSanitizerDesign.rst

3

I vote for HardwareAssistedAddressSanitizer, or hwasan.

25

remove "the"

102

Mention the system calls problem with tagged pointers.

[kcc]

addressed comments

[kcc]

docs/TaggedAddressSanitizerDesign.rst

3

Added hwasan as an alternative.
I dislike it less then tasan.
Let's wait for other suggestions before renaming.

102

added

May require changes in the OS kernels (e.g. Linux seems to dislike
 tagged pointers passed from address space).

[davidxl]

docs/TaggedAddressSanitizerDesign.rst

23

What is the overhead of redzones compared with shadow memory?

50

a real runtime call or it will be lowered into inline sequence?

[kcc]

docs/TaggedAddressSanitizerDesign.rst

23

depends.
shadow is 1/9 of all memory.
redzones largely depend on the allocation patterns.
If most heap allocations are big, the combined redzones are tiny, and vise versa

50

at least in the initial implementation -- yes.
Since this is aarc64-specific, the call/ret should be relatively cheap.
But of course nothing prevents us from inlining if we see a need for it.

[kcc]

mention alternatives for memory access instrumentation

[eugenis]

docs/TaggedAddressSanitizerDesign.rst

23

It's worth mentioning that typical ASan memory overhead of 2x to 3x, mainly from redzones and quarantine.

This new tool will have only the shadow, which is a tiny fraction of the original memory footprint, and some overhead from over-aligning everything. The latter is expected to be small, especially if N (see below) is reduced to 16 or even 8, in which case the shadow grows to 1/16th or 1/8th, respectively. In any case, I'd expect less than 25% RAM overhead, hopefully way less.

[kcc]

rephrase the sources of asan overhead

[kcc]

Rename the new tool to HWASAN

[eugenis]

Looks great!

docs/TaggedAddressSanitizerDesign.rst

+===========================================
+TaggedAddressSanitizer Design Documentation
+===========================================
+
+This page is a preliminary design document for
+a **hardware-assisted memory safety** (HWAMS) tool,
+similar to :doc:`AddressSanitizer`.
+
+The name **TaggedAddressSanitizer** or TASAN
+(alternative: **HardwareAssistedAddressSanitizer** or HWASAN)
+and the rest of the document,
+are *early 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 shadow, the redzones, and the quarantine are the
+major 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. TaggedAddressSanitizer 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. `__hwams_load4(void *ptr)`;
+it loads the memory tag, compares it with the
+pointer tag, and executes `__builtin_trap` (or calls `__hwams_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
+================================
+
+TaggedAddressSanitizer:
+  * 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 TaggedAddressSanitizer 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
+