1===========================================
2Control Flow Integrity Design Documentation
3===========================================
4
5This page documents the design of the :doc:`ControlFlowIntegrity` schemes
6supported by Clang.
7
8Forward-Edge CFI for Virtual Calls
9==================================
10
11This scheme works by allocating, for each static type used to make a virtual
12call, a region of read-only storage in the object file holding a bit vector
13that maps onto to the region of storage used for those virtual tables. Each
14set bit in the bit vector corresponds to the `address point`_ for a virtual
15table compatible with the static type for which the bit vector is being built.
16
17For example, consider the following three C++ classes:
18
19.. code-block:: c++
20
21  struct A {
22    virtual void f1();
23    virtual void f2();
24    virtual void f3();
25  };
26
27  struct B : A {
28    virtual void f1();
29    virtual void f2();
30    virtual void f3();
31  };
32
33  struct C : A {
34    virtual void f1();
35    virtual void f2();
36    virtual void f3();
37  };
38
39The scheme will cause the virtual tables for A, B and C to be laid out
40consecutively:
41
42.. csv-table:: Virtual Table Layout for A, B, C
43  :header: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
44
45  A::offset-to-top, &A::rtti, &A::f1, &A::f2, &A::f3, B::offset-to-top, &B::rtti, &B::f1, &B::f2, &B::f3, C::offset-to-top, &C::rtti, &C::f1, &C::f2, &C::f3
46
47The bit vector for static types A, B and C will look like this:
48
49.. csv-table:: Bit Vectors for A, B, C
50  :header: Class, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
51
52  A, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0
53  B, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0
54  C, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0
55
56To emit a virtual call, the compiler will assemble code that checks that
57the object's virtual table pointer is in-bounds and aligned and that the
58relevant bit is set in the bit vector.
59
60For example on x86 a typical virtual call may look like this:
61
62.. code-block:: none
63
64    159a:       48 8b 03                mov    (%rbx),%rax
65    159d:       48 8d 15 6c 33 00 00    lea    0x336c(%rip),%rdx
66    15a4:       48 89 c1                mov    %rax,%rcx
67    15a7:       48 29 d1                sub    %rdx,%rcx
68    15aa:       48 c1 c1 3d             rol    $0x3d,%rcx
69    15ae:       48 83 f9 51             cmp    $0x51,%rcx
70    15b2:       77 3b                   ja     15ef <main+0xcf>
71    15b4:       48 89 ca                mov    %rcx,%rdx
72    15b7:       48 c1 ea 05             shr    $0x5,%rdx
73    15bb:       48 8d 35 b8 07 00 00    lea    0x7b8(%rip),%rsi
74    15c2:       8b 14 96                mov    (%rsi,%rdx,4),%edx
75    15c5:       0f a3 ca                bt     %ecx,%edx
76    15c8:       73 25                   jae    15ef <main+0xcf>
77    15ca:       48 89 df                mov    %rbx,%rdi
78    15cd:       ff 10                   callq  *(%rax)
79    [...]
80    15ef:       0f 0b                   ud2
81
82The compiler relies on co-operation from the linker in order to assemble
83the bit vectors for the whole program. It currently does this using LLVM's
84`bit sets`_ mechanism together with link-time optimization.
85
86.. _address point: https://mentorembedded.github.io/cxx-abi/abi.html#vtable-general
87.. _bit sets: http://llvm.org/docs/BitSets.html
88
89Optimizations
90-------------
91
92The scheme as described above is the fully general variant of the scheme.
93Most of the time we are able to apply one or more of the following
94optimizations to improve binary size or performance.
95
96In fact, if you try the above example with the current version of the
97compiler, you will probably find that it will not use the described virtual
98table layout or machine instructions. Some of the optimizations we are about
99to introduce cause the compiler to use a different layout or a different
100sequence of machine instructions.
101
102Stripping Leading/Trailing Zeros in Bit Vectors
103~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
104
105If a bit vector contains leading or trailing zeros, we can strip them from
106the vector. The compiler will emit code to check if the pointer is in range
107of the region covered by ones, and perform the bit vector check using a
108truncated version of the bit vector. For example, the bit vectors for our
109example class hierarchy will be emitted like this:
110
111.. csv-table:: Bit Vectors for A, B, C
112  :header: Class, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
113
114  A,  ,  , 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,  ,
115  B,  ,  ,  ,  ,  ,  ,  , 1,  ,  ,  ,  ,  ,  ,
116  C,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , 1,  ,
117
118Short Inline Bit Vectors
119~~~~~~~~~~~~~~~~~~~~~~~~
120
121If the vector is sufficiently short, we can represent it as an inline constant
122on x86. This saves us a few instructions when reading the correct element
123of the bit vector.
124
125If the bit vector fits in 32 bits, the code looks like this:
126
127.. code-block:: none
128
129     dc2:       48 8b 03                mov    (%rbx),%rax
130     dc5:       48 8d 15 14 1e 00 00    lea    0x1e14(%rip),%rdx
131     dcc:       48 89 c1                mov    %rax,%rcx
132     dcf:       48 29 d1                sub    %rdx,%rcx
133     dd2:       48 c1 c1 3d             rol    $0x3d,%rcx
134     dd6:       48 83 f9 03             cmp    $0x3,%rcx
135     dda:       77 2f                   ja     e0b <main+0x9b>
136     ddc:       ba 09 00 00 00          mov    $0x9,%edx
137     de1:       0f a3 ca                bt     %ecx,%edx
138     de4:       73 25                   jae    e0b <main+0x9b>
139     de6:       48 89 df                mov    %rbx,%rdi
140     de9:       ff 10                   callq  *(%rax)
141    [...]
142     e0b:       0f 0b                   ud2
143
144Or if the bit vector fits in 64 bits:
145
146.. code-block:: none
147
148    11a6:       48 8b 03                mov    (%rbx),%rax
149    11a9:       48 8d 15 d0 28 00 00    lea    0x28d0(%rip),%rdx
150    11b0:       48 89 c1                mov    %rax,%rcx
151    11b3:       48 29 d1                sub    %rdx,%rcx
152    11b6:       48 c1 c1 3d             rol    $0x3d,%rcx
153    11ba:       48 83 f9 2a             cmp    $0x2a,%rcx
154    11be:       77 35                   ja     11f5 <main+0xb5>
155    11c0:       48 ba 09 00 00 00 00    movabs $0x40000000009,%rdx
156    11c7:       04 00 00
157    11ca:       48 0f a3 ca             bt     %rcx,%rdx
158    11ce:       73 25                   jae    11f5 <main+0xb5>
159    11d0:       48 89 df                mov    %rbx,%rdi
160    11d3:       ff 10                   callq  *(%rax)
161    [...]
162    11f5:       0f 0b                   ud2
163
164If the bit vector consists of a single bit, there is only one possible
165virtual table, and the check can consist of a single equality comparison:
166
167.. code-block:: none
168
169     9a2:   48 8b 03                mov    (%rbx),%rax
170     9a5:   48 8d 0d a4 13 00 00    lea    0x13a4(%rip),%rcx
171     9ac:   48 39 c8                cmp    %rcx,%rax
172     9af:   75 25                   jne    9d6 <main+0x86>
173     9b1:   48 89 df                mov    %rbx,%rdi
174     9b4:   ff 10                   callq  *(%rax)
175     [...]
176     9d6:   0f 0b                   ud2
177
178Virtual Table Layout
179~~~~~~~~~~~~~~~~~~~~
180
181The compiler lays out classes of disjoint hierarchies in separate regions
182of the object file. At worst, bit vectors in disjoint hierarchies only
183need to cover their disjoint hierarchy. But the closer that classes in
184sub-hierarchies are laid out to each other, the smaller the bit vectors for
185those sub-hierarchies need to be (see "Stripping Leading/Trailing Zeros in Bit
186Vectors" above). The `GlobalLayoutBuilder`_ class is responsible for laying
187out the globals efficiently to minimize the sizes of the underlying bitsets.
188
189.. _GlobalLayoutBuilder: http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Transforms/IPO/LowerBitSets.h?view=markup
190
191Alignment
192~~~~~~~~~
193
194If all gaps between address points in a particular bit vector are multiples
195of powers of 2, the compiler can compress the bit vector by strengthening
196the alignment requirements of the virtual table pointer. For example, given
197this class hierarchy:
198
199.. code-block:: c++
200
201  struct A {
202    virtual void f1();
203    virtual void f2();
204  };
205
206  struct B : A {
207    virtual void f1();
208    virtual void f2();
209    virtual void f3();
210    virtual void f4();
211    virtual void f5();
212    virtual void f6();
213  };
214
215  struct C : A {
216    virtual void f1();
217    virtual void f2();
218  };
219
220The virtual tables will be laid out like this:
221
222.. csv-table:: Virtual Table Layout for A, B, C
223  :header: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
224
225  A::offset-to-top, &A::rtti, &A::f1, &A::f2, B::offset-to-top, &B::rtti, &B::f1, &B::f2, &B::f3, &B::f4, &B::f5, &B::f6, C::offset-to-top, &C::rtti, &C::f1, &C::f2
226
227Notice that each address point for A is separated by 4 words. This lets us
228emit a compressed bit vector for A that looks like this:
229
230.. csv-table::
231  :header: 2, 6, 10, 14
232
233  1, 1, 0, 1
234
235At call sites, the compiler will strengthen the alignment requirements by
236using a different rotate count. For example, on a 64-bit machine where the
237address points are 4-word aligned (as in A from our example), the ``rol``
238instruction may look like this:
239
240.. code-block:: none
241
242     dd2:       48 c1 c1 3b             rol    $0x3b,%rcx
243
244Padding to Powers of 2
245~~~~~~~~~~~~~~~~~~~~~~
246
247Of course, this alignment scheme works best if the address points are
248in fact aligned correctly. To make this more likely to happen, we insert
249padding between virtual tables that in many cases aligns address points to
250a power of 2. Specifically, our padding aligns virtual tables to the next
251highest power of 2 bytes; because address points for specific base classes
252normally appear at fixed offsets within the virtual table, this normally
253has the effect of aligning the address points as well.
254
255This scheme introduces tradeoffs between decreased space overhead for
256instructions and bit vectors and increased overhead in the form of padding. We
257therefore limit the amount of padding so that we align to no more than 128
258bytes. This number was found experimentally to provide a good tradeoff.
259
260Eliminating Bit Vector Checks for All-Ones Bit Vectors
261~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
262
263If the bit vector is all ones, the bit vector check is redundant; we simply
264need to check that the address is in range and well aligned. This is more
265likely to occur if the virtual tables are padded.
266