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

2 ↗

(On Diff #124604)

I vote for HardwareAssistedAddressSanitizer, or hwasan.

24 ↗

(On Diff #124604)

remove "the"

101 ↗

(On Diff #124604)

Mention the system calls problem with tagged pointers.

[kcc]

addressed comments

[kcc]

docs/TaggedAddressSanitizerDesign.rst

2 ↗

(On Diff #124604)

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

101 ↗

(On Diff #124604)

added

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

[davidxl]

docs/TaggedAddressSanitizerDesign.rst

22 ↗

(On Diff #124637)

What is the overhead of redzones compared with shadow memory?

49 ↗

(On Diff #124637)

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

[kcc]

docs/TaggedAddressSanitizerDesign.rst

22 ↗

(On Diff #124637)

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

49 ↗

(On Diff #124637)

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

22 ↗

(On Diff #124637)

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/HardwareAssistedAddressSanitizerDesign.rst

+=====================================================
+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
+

docs/index.rst

 .. toctree::
    :maxdepth: 1
 
    InternalsManual
    DriverInternals
    PTHInternals
    PCHInternals
    ItaniumMangleAbiTags
+   HardwareAssistedAddressSanitizerDesign.rst
 
 
 Indices and tables
 ==================
 
 * :ref:`genindex`
 * :ref:`modindex`
 * :ref:`search`