1=======================================================
2Hardware-assisted AddressSanitizer Design Documentation
3=======================================================
4
5This page is a design document for
6**hardware-assisted AddressSanitizer** (or **HWASAN**)
7a tool similar to :doc:`AddressSanitizer`,
8but based on partial hardware assistance.
9
10The document is a draft, suggestions are welcome.
11
12
13Introduction
14============
15
16:doc:`AddressSanitizer`
17tags every 8 bytes of the application memory with a 1 byte tag (using *shadow memory*),
18uses *redzones* to find buffer-overflows and
19*quarantine* to find use-after-free.
20The redzones, the quarantine, and, to a less extent, the shadow, are the
21sources of AddressSanitizer's memory overhead.
22See the `AddressSanitizer paper`_ for details.
23
24AArch64 has the `Address Tagging`_ (or top-byte-ignore, TBI), a hardware feature that allows
25software to use 8 most significant bits of a 64-bit pointer as
26a tag. HWASAN uses `Address Tagging`_
27to implement a memory safety tool, similar to :doc:`AddressSanitizer`,
28but with smaller memory overhead and slightly different (mostly better)
29accuracy guarantees.
30
31Algorithm
32=========
33* Every heap/stack/global memory object is forcibly aligned by `N` bytes
34  (`N` is e.g. 16 or 64). We call `N` the **granularity** of tagging.
35* For every such object a random `K`-bit tag `T` is chosen (`K` is e.g. 4 or 8)
36* The pointer to the object is tagged with `T`.
37* The memory for the object is also tagged with `T`
38  (using a `N=>1` shadow memory)
39* Every load and store is instrumented to read the memory tag and compare it
40  with the pointer tag, exception is raised on tag mismatch.
41
42Instrumentation
43===============
44
45Memory Accesses
46---------------
47All memory accesses are prefixed with an inline instruction sequence that
48verifies the tags. Currently, the following sequence is used:
49
50
51.. code-block:: asm
52
53  // int foo(int *a) { return *a; }
54  // clang -O2 --target=aarch64-linux -fsanitize=hwaddress -c load.c
55  foo:
56       0:	08 dc 44 d3 	ubfx	x8, x0, #4, #52  // shadow address
57       4:	08 01 40 39 	ldrb	w8, [x8]         // load shadow
58       8:	09 fc 78 d3 	lsr	x9, x0, #56      // address tag
59       c:	3f 01 08 6b 	cmp	w9, w8           // compare tags
60      10:	61 00 00 54 	b.ne	#12              // jump on mismatch
61      14:	00 00 40 b9 	ldr	w0, [x0]         // original load
62      18:	c0 03 5f d6 	ret
63      1c:	40 20 40 d4 	hlt	#0x102           // halt
64      20:	00 00 40 b9 	ldr	w0, [x0]         // original load
65      24:	c0 03 5f d6 	ret
66
67
68Alternatively, memory accesses are prefixed with a function call.
69
70Heap
71----
72
73Tagging the heap memory/pointers is done by `malloc`.
74This can be based on any malloc that forces all objects to be N-aligned.
75`free` tags the memory with a different tag.
76
77Stack
78-----
79
80Stack frames are instrumented by aligning all non-promotable allocas
81by `N` and tagging stack memory in function prologue and epilogue.
82
83Tags for different allocas in one function are **not** generated
84independently; doing that in a function with `M` allocas would require
85maintaining `M` live stack pointers, significantly increasing register
86pressure. Instead we generate a single base tag value in the prologue,
87and build the tag for alloca number `M` as `ReTag(BaseTag, M)`, where
88ReTag can be as simple as exclusive-or with constant `M`.
89
90Stack instrumentation is expected to be a major source of overhead,
91but could be optional.
92
93Globals
94-------
95
96TODO: details.
97
98Error reporting
99---------------
100
101Errors are generated by the `HLT` instruction and are handled by a signal handler.
102
103Attribute
104---------
105
106HWASAN uses its own LLVM IR Attribute `sanitize_hwaddress` and a matching
107C function attribute. An alternative would be to re-use ASAN's attribute
108`sanitize_address`. The reasons to use a separate attribute are:
109
110  * Users may need to disable ASAN but not HWASAN, or vise versa,
111    because the tools have different trade-offs and compatibility issues.
112  * LLVM (ideally) does not use flags to decide which pass is being used,
113    ASAN or HWASAN are being applied, based on the function attributes.
114
115This does mean that users of HWASAN may need to add the new attribute
116to the code that already uses the old attribute.
117
118
119Comparison with AddressSanitizer
120================================
121
122HWASAN:
123  * Is less portable than :doc:`AddressSanitizer`
124    as it relies on hardware `Address Tagging`_ (AArch64).
125    Address Tagging can be emulated with compiler instrumentation,
126    but it will require the instrumentation to remove the tags before
127    any load or store, which is infeasible in any realistic environment
128    that contains non-instrumented code.
129  * May have compatibility problems if the target code uses higher
130    pointer bits for other purposes.
131  * May require changes in the OS kernels (e.g. Linux seems to dislike
132    tagged pointers passed from address space:
133    https://www.kernel.org/doc/Documentation/arm64/tagged-pointers.txt).
134  * **Does not require redzones to detect buffer overflows**,
135    but the buffer overflow detection is probabilistic, with roughly
136    `(2**K-1)/(2**K)` probability of catching a bug.
137  * **Does not require quarantine to detect heap-use-after-free,
138    or stack-use-after-return**.
139    The detection is similarly probabilistic.
140
141The memory overhead of HWASAN is expected to be much smaller
142than that of AddressSanitizer:
143`1/N` extra memory for the shadow
144and some overhead due to `N`-aligning all objects.
145
146
147Related Work
148============
149* `SPARC ADI`_ implements a similar tool mostly in hardware.
150* `Effective and Efficient Memory Protection Using Dynamic Tainting`_ discusses
151  similar approaches ("lock & key").
152* `Watchdog`_ discussed a heavier, but still somewhat similar
153  "lock & key" approach.
154* *TODO: add more "related work" links. Suggestions are welcome.*
155
156
157.. _Watchdog: http://www.cis.upenn.edu/acg/papers/isca12_watchdog.pdf
158.. _Effective and Efficient Memory Protection Using Dynamic Tainting: https://www.cc.gatech.edu/~orso/papers/clause.doudalis.orso.prvulovic.pdf
159.. _SPARC ADI: https://lazytyped.blogspot.com/2017/09/getting-started-with-adi.html
160.. _AddressSanitizer paper: https://www.usenix.org/system/files/conference/atc12/atc12-final39.pdf
161.. _Address Tagging: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0024a/ch12s05s01.html
162
163