1===============
2ShadowCallStack
3===============
4
5.. contents::
6   :local:
7
8Introduction
9============
10
11ShadowCallStack is an **experimental** instrumentation pass, currently only
12implemented for x86_64, that protects programs against return address
13overwrites (e.g. stack buffer overflows.) It works by saving a function's return
14address to a separately allocated 'shadow call stack' in the function prolog and
15checking the return address on the stack against the shadow call stack in the
16function epilog.
17
18Comparison
19----------
20
21To optimize for memory consumption and cache locality, the shadow call stack
22stores an index followed by an array of return addresses. This is in contrast
23to other schemes, like :doc:`SafeStack`, that mirror the entire stack and
24trade-off consuming more memory for shorter function prologs and epilogs with
25fewer memory accesses. Similarly, `Return Flow Guard`_ consumes more memory with
26shorter function prologs and epilogs than ShadowCallStack but suffers from the
27same race conditions (see `Security`_). Intel `Control-flow Enforcement Technology`_
28(CET) is a proposed hardware extension that would add native support to
29use a shadow stack to store/check return addresses at call/return time. It
30would not suffer from race conditions at calls and returns and not incur the
31overhead of function instrumentation, but it does require operating system
32support.
33
34.. _`Return Flow Guard`: https://xlab.tencent.com/en/2016/11/02/return-flow-guard/
35.. _`Control-flow Enforcement Technology`: https://software.intel.com/sites/default/files/managed/4d/2a/control-flow-enforcement-technology-preview.pdf
36
37Compatibility
38-------------
39
40ShadowCallStack currently only supports x86_64. A runtime is not currently
41provided in compiler-rt so one must be provided by the compiled application.
42
43Security
44========
45
46ShadowCallStack is intended to be a stronger alternative to
47``-fstack-protector``. It protects from non-linear overflows and arbitrary
48memory writes to the return address slot; however, similarly to
49``-fstack-protector`` this protection suffers from race conditions because of
50the call-return semantics on x86_64. There is a short race between the call
51instruction and the first instruction in the function that reads the return
52address where an attacker could overwrite the return address and bypass
53ShadowCallStack. Similarly, there is a time-of-check-to-time-of-use race in the
54function epilog where an attacker could overwrite the return address after it
55has been checked and before it has been returned to. Modifying the call-return
56semantics to fix this on x86_64 would incur an unacceptable performance overhead
57due to return branch prediction.
58
59The instrumentation makes use of the ``gs`` segment register to reference the
60shadow call stack meaning that references to the shadow call stack do not have
61to be stored in memory. This makes it possible to implement a runtime that
62avoids exposing the address of the shadow call stack to attackers that can read
63arbitrary memory. However, attackers could still try to exploit side channels
64exposed by the operating system `[1]`_ `[2]`_ or processor `[3]`_ to discover
65the address of the shadow call stack.
66
67.. _`[1]`: https://eyalitkin.wordpress.com/2017/09/01/cartography-lighting-up-the-shadows/
68.. _`[2]`: https://www.blackhat.com/docs/eu-16/materials/eu-16-Goktas-Bypassing-Clangs-SafeStack.pdf
69.. _`[3]`: https://www.vusec.net/projects/anc/
70
71Leaf functions are optimized to store the return address in a free register
72and avoid writing to the shadow call stack if a register is available. Very
73short leaf functions are uninstrumented if their execution is judged to be
74shorter than the race condition window intrinsic to the instrumentation.
75
76Usage
77=====
78
79To enable ShadowCallStack, just pass the ``-fsanitize=shadow-call-stack`` flag
80to both compile and link command lines.
81
82Low-level API
83-------------
84
85``__has_feature(shadow_call_stack)``
86~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
87
88In some cases one may need to execute different code depending on whether
89ShadowCallStack is enabled. The macro ``__has_feature(shadow_call_stack)`` can
90be used for this purpose.
91
92.. code-block:: c
93
94    #if defined(__has_feature)
95    #  if __has_feature(shadow_call_stack)
96    // code that builds only under ShadowCallStack
97    #  endif
98    #endif
99
100``__attribute__((no_sanitize("shadow-call-stack")))``
101~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
102
103Use ``__attribute__((no_sanitize("shadow-call-stack")))`` on a function
104declaration to specify that the shadow call stack instrumentation should not be
105applied to that function, even if enabled globally.
106
107Example
108=======
109
110The following example code:
111
112.. code-block:: c++
113
114    int foo() {
115      return bar() + 1;
116    }
117
118Generates the following x86_64 assembly when compiled with ``-O2``:
119
120.. code-block:: gas
121
122    push   %rax
123    callq  foo
124    add    $0x1,%eax
125    pop    %rcx
126    retq
127
128Adding ``-fsanitize=shadow-call-stack`` would output the following:
129
130.. code-block:: gas
131
132    mov    (%rsp),%r10
133    xor    %r11,%r11
134    addq   $0x8,%gs:(%r11)
135    mov    %gs:(%r11),%r11
136    mov    %r10,%gs:(%r11)
137    push   %rax
138    callq  foo
139    add    $0x1,%eax
140    pop    %rcx
141    xor    %r11,%r11
142    mov    %gs:(%r11),%r10
143    mov    %gs:(%r10),%r10
144    subq   $0x8,%gs:(%r11)
145    cmp    %r10,(%rsp)
146    jne    trap
147    retq
148
149    trap:
150    ud2
151