• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
56Bit vectors are represented in the object file as byte arrays. By loading
57from indexed offsets into the byte array and applying a mask, a program can
58test bits from the bit set with a relatively short instruction sequence. Bit
59vectors may overlap so long as they use different bits. For the full details,
60see the `ByteArrayBuilder`_ class.
61
62In this case, assuming A is laid out at offset 0 in bit 0, B at offset 0 in
63bit 1 and C at offset 0 in bit 2, the byte array would look like this:
64
65.. code-block:: c++
66
67  char bits[] = { 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 0, 5, 0, 0 };
68
69To emit a virtual call, the compiler will assemble code that checks that
70the object's virtual table pointer is in-bounds and aligned and that the
71relevant bit is set in the bit vector.
72
73For example on x86 a typical virtual call may look like this:
74
75.. code-block:: none
76
77  ca7fbb:       48 8b 0f                mov    (%rdi),%rcx
78  ca7fbe:       48 8d 15 c3 42 fb 07    lea    0x7fb42c3(%rip),%rdx
79  ca7fc5:       48 89 c8                mov    %rcx,%rax
80  ca7fc8:       48 29 d0                sub    %rdx,%rax
81  ca7fcb:       48 c1 c0 3d             rol    $0x3d,%rax
82  ca7fcf:       48 3d 7f 01 00 00       cmp    $0x17f,%rax
83  ca7fd5:       0f 87 36 05 00 00       ja     ca8511
84  ca7fdb:       48 8d 15 c0 0b f7 06    lea    0x6f70bc0(%rip),%rdx
85  ca7fe2:       f6 04 10 10             testb  $0x10,(%rax,%rdx,1)
86  ca7fe6:       0f 84 25 05 00 00       je     ca8511
87  ca7fec:       ff 91 98 00 00 00       callq  *0x98(%rcx)
88    [...]
89  ca8511:       0f 0b                   ud2
90
91The compiler relies on co-operation from the linker in order to assemble
92the bit vectors for the whole program. It currently does this using LLVM's
93`bit sets`_ mechanism together with link-time optimization.
94
95.. _address point: https://mentorembedded.github.io/cxx-abi/abi.html#vtable-general
96.. _bit sets: http://llvm.org/docs/BitSets.html
97.. _ByteArrayBuilder: http://llvm.org/docs/doxygen/html/structllvm_1_1ByteArrayBuilder.html
98
99Optimizations
100-------------
101
102The scheme as described above is the fully general variant of the scheme.
103Most of the time we are able to apply one or more of the following
104optimizations to improve binary size or performance.
105
106In fact, if you try the above example with the current version of the
107compiler, you will probably find that it will not use the described virtual
108table layout or machine instructions. Some of the optimizations we are about
109to introduce cause the compiler to use a different layout or a different
110sequence of machine instructions.
111
112Stripping Leading/Trailing Zeros in Bit Vectors
113~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
114
115If a bit vector contains leading or trailing zeros, we can strip them from
116the vector. The compiler will emit code to check if the pointer is in range
117of the region covered by ones, and perform the bit vector check using a
118truncated version of the bit vector. For example, the bit vectors for our
119example class hierarchy will be emitted like this:
120
121.. csv-table:: Bit Vectors for A, B, C
122  :header: Class, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
123
124  A,  ,  , 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,  ,
125  B,  ,  ,  ,  ,  ,  ,  , 1,  ,  ,  ,  ,  ,  ,
126  C,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  , 1,  ,
127
128Short Inline Bit Vectors
129~~~~~~~~~~~~~~~~~~~~~~~~
130
131If the vector is sufficiently short, we can represent it as an inline constant
132on x86. This saves us a few instructions when reading the correct element
133of the bit vector.
134
135If the bit vector fits in 32 bits, the code looks like this:
136
137.. code-block:: none
138
139     dc2:       48 8b 03                mov    (%rbx),%rax
140     dc5:       48 8d 15 14 1e 00 00    lea    0x1e14(%rip),%rdx
141     dcc:       48 89 c1                mov    %rax,%rcx
142     dcf:       48 29 d1                sub    %rdx,%rcx
143     dd2:       48 c1 c1 3d             rol    $0x3d,%rcx
144     dd6:       48 83 f9 03             cmp    $0x3,%rcx
145     dda:       77 2f                   ja     e0b <main+0x9b>
146     ddc:       ba 09 00 00 00          mov    $0x9,%edx
147     de1:       0f a3 ca                bt     %ecx,%edx
148     de4:       73 25                   jae    e0b <main+0x9b>
149     de6:       48 89 df                mov    %rbx,%rdi
150     de9:       ff 10                   callq  *(%rax)
151    [...]
152     e0b:       0f 0b                   ud2
153
154Or if the bit vector fits in 64 bits:
155
156.. code-block:: none
157
158    11a6:       48 8b 03                mov    (%rbx),%rax
159    11a9:       48 8d 15 d0 28 00 00    lea    0x28d0(%rip),%rdx
160    11b0:       48 89 c1                mov    %rax,%rcx
161    11b3:       48 29 d1                sub    %rdx,%rcx
162    11b6:       48 c1 c1 3d             rol    $0x3d,%rcx
163    11ba:       48 83 f9 2a             cmp    $0x2a,%rcx
164    11be:       77 35                   ja     11f5 <main+0xb5>
165    11c0:       48 ba 09 00 00 00 00    movabs $0x40000000009,%rdx
166    11c7:       04 00 00
167    11ca:       48 0f a3 ca             bt     %rcx,%rdx
168    11ce:       73 25                   jae    11f5 <main+0xb5>
169    11d0:       48 89 df                mov    %rbx,%rdi
170    11d3:       ff 10                   callq  *(%rax)
171    [...]
172    11f5:       0f 0b                   ud2
173
174If the bit vector consists of a single bit, there is only one possible
175virtual table, and the check can consist of a single equality comparison:
176
177.. code-block:: none
178
179     9a2:   48 8b 03                mov    (%rbx),%rax
180     9a5:   48 8d 0d a4 13 00 00    lea    0x13a4(%rip),%rcx
181     9ac:   48 39 c8                cmp    %rcx,%rax
182     9af:   75 25                   jne    9d6 <main+0x86>
183     9b1:   48 89 df                mov    %rbx,%rdi
184     9b4:   ff 10                   callq  *(%rax)
185     [...]
186     9d6:   0f 0b                   ud2
187
188Virtual Table Layout
189~~~~~~~~~~~~~~~~~~~~
190
191The compiler lays out classes of disjoint hierarchies in separate regions
192of the object file. At worst, bit vectors in disjoint hierarchies only
193need to cover their disjoint hierarchy. But the closer that classes in
194sub-hierarchies are laid out to each other, the smaller the bit vectors for
195those sub-hierarchies need to be (see "Stripping Leading/Trailing Zeros in Bit
196Vectors" above). The `GlobalLayoutBuilder`_ class is responsible for laying
197out the globals efficiently to minimize the sizes of the underlying bitsets.
198
199.. _GlobalLayoutBuilder: http://llvm.org/viewvc/llvm-project/llvm/trunk/include/llvm/Transforms/IPO/LowerBitSets.h?view=markup
200
201Alignment
202~~~~~~~~~
203
204If all gaps between address points in a particular bit vector are multiples
205of powers of 2, the compiler can compress the bit vector by strengthening
206the alignment requirements of the virtual table pointer. For example, given
207this class hierarchy:
208
209.. code-block:: c++
210
211  struct A {
212    virtual void f1();
213    virtual void f2();
214  };
215
216  struct B : A {
217    virtual void f1();
218    virtual void f2();
219    virtual void f3();
220    virtual void f4();
221    virtual void f5();
222    virtual void f6();
223  };
224
225  struct C : A {
226    virtual void f1();
227    virtual void f2();
228  };
229
230The virtual tables will be laid out like this:
231
232.. csv-table:: Virtual Table Layout for A, B, C
233  :header: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
234
235  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
236
237Notice that each address point for A is separated by 4 words. This lets us
238emit a compressed bit vector for A that looks like this:
239
240.. csv-table::
241  :header: 2, 6, 10, 14
242
243  1, 1, 0, 1
244
245At call sites, the compiler will strengthen the alignment requirements by
246using a different rotate count. For example, on a 64-bit machine where the
247address points are 4-word aligned (as in A from our example), the ``rol``
248instruction may look like this:
249
250.. code-block:: none
251
252     dd2:       48 c1 c1 3b             rol    $0x3b,%rcx
253
254Padding to Powers of 2
255~~~~~~~~~~~~~~~~~~~~~~
256
257Of course, this alignment scheme works best if the address points are
258in fact aligned correctly. To make this more likely to happen, we insert
259padding between virtual tables that in many cases aligns address points to
260a power of 2. Specifically, our padding aligns virtual tables to the next
261highest power of 2 bytes; because address points for specific base classes
262normally appear at fixed offsets within the virtual table, this normally
263has the effect of aligning the address points as well.
264
265This scheme introduces tradeoffs between decreased space overhead for
266instructions and bit vectors and increased overhead in the form of padding. We
267therefore limit the amount of padding so that we align to no more than 128
268bytes. This number was found experimentally to provide a good tradeoff.
269
270Eliminating Bit Vector Checks for All-Ones Bit Vectors
271~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
272
273If the bit vector is all ones, the bit vector check is redundant; we simply
274need to check that the address is in range and well aligned. This is more
275likely to occur if the virtual tables are padded.
276
277Forward-Edge CFI for Indirect Function Calls
278============================================
279
280Under forward-edge CFI for indirect function calls, each unique function
281type has its own bit vector, and at each call site we need to check that the
282function pointer is a member of the function type's bit vector. This scheme
283works in a similar way to forward-edge CFI for virtual calls, the distinction
284being that we need to build bit vectors of function entry points rather than
285of virtual tables.
286
287Unlike when re-arranging global variables, we cannot re-arrange functions
288in a particular order and base our calculations on the layout of the
289functions' entry points, as we have no idea how large a particular function
290will end up being (the function sizes could even depend on how we arrange
291the functions). Instead, we build a jump table, which is a block of code
292consisting of one branch instruction for each of the functions in the bit
293set that branches to the target function, and redirect any taken function
294addresses to the corresponding jump table entry. In this way, the distance
295between function entry points is predictable and controllable. In the object
296file's symbol table, the symbols for the target functions also refer to the
297jump table entries, so that addresses taken outside the module will pass
298any verification done inside the module.
299
300In more concrete terms, suppose we have three functions ``f``, ``g``, ``h``
301which are members of a single bitset, and a function foo that returns their
302addresses:
303
304.. code-block:: none
305
306  f:
307  mov 0, %eax
308  ret
309
310  g:
311  mov 1, %eax
312  ret
313
314  h:
315  mov 2, %eax
316  ret
317
318  foo:
319  mov f, %eax
320  mov g, %edx
321  mov h, %ecx
322  ret
323
324Our jump table will (conceptually) look like this:
325
326.. code-block:: none
327
328  f:
329  jmp .Ltmp0 ; 5 bytes
330  int3       ; 1 byte
331  int3       ; 1 byte
332  int3       ; 1 byte
333
334  g:
335  jmp .Ltmp1 ; 5 bytes
336  int3       ; 1 byte
337  int3       ; 1 byte
338  int3       ; 1 byte
339
340  h:
341  jmp .Ltmp2 ; 5 bytes
342  int3       ; 1 byte
343  int3       ; 1 byte
344  int3       ; 1 byte
345
346  .Ltmp0:
347  mov 0, %eax
348  ret
349
350  .Ltmp1:
351  mov 1, %eax
352  ret
353
354  .Ltmp2:
355  mov 2, %eax
356  ret
357
358  foo:
359  mov f, %eax
360  mov g, %edx
361  mov h, %ecx
362  ret
363
364Because the addresses of ``f``, ``g``, ``h`` are evenly spaced at a power of
3652, and function types do not overlap (unlike class types with base classes),
366we can normally apply the `Alignment`_ and `Eliminating Bit Vector Checks
367for All-Ones Bit Vectors`_ optimizations thus simplifying the check at each
368call site to a range and alignment check.
369
370Shared library support
371======================
372
373**EXPERIMENTAL**
374
375The basic CFI mode described above assumes that the application is a
376monolithic binary; at least that all possible virtual/indirect call
377targets and the entire class hierarchy are known at link time. The
378cross-DSO mode, enabled with **-f[no-]sanitize-cfi-cross-dso** relaxes
379this requirement by allowing virtual and indirect calls to cross the
380DSO boundary.
381
382Assuming the following setup: the binary consists of several
383instrumented and several uninstrumented DSOs. Some of them may be
384dlopen-ed/dlclose-d periodically, even frequently.
385
386  - Calls made from uninstrumented DSOs are not checked and just work.
387  - Calls inside any instrumented DSO are fully protected.
388  - Calls between different instrumented DSOs are also protected, with
389     a performance penalty (in addition to the monolithic CFI
390     overhead).
391  - Calls from an instrumented DSO to an uninstrumented one are
392     unchecked and just work, with performance penalty.
393  - Calls from an instrumented DSO outside of any known DSO are
394     detected as CFI violations.
395
396In the monolithic scheme a call site is instrumented as
397
398.. code-block:: none
399
400   if (!InlinedFastCheck(f))
401     abort();
402   call *f
403
404In the cross-DSO scheme it becomes
405
406.. code-block:: none
407
408   if (!InlinedFastCheck(f))
409     __cfi_slowpath(CallSiteTypeId, f);
410   call *f
411
412CallSiteTypeId
413--------------
414
415``CallSiteTypeId`` is a stable process-wide identifier of the
416call-site type. For a virtual call site, the type in question is the class
417type; for an indirect function call it is the function signature. The
418mapping from a type to an identifier is an ABI detail. In the current,
419experimental, implementation the identifier of type T is calculated as
420follows:
421
422  -  Obtain the mangled name for "typeinfo name for T".
423  -  Calculate MD5 hash of the name as a string.
424  -  Reinterpret the first 8 bytes of the hash as a little-endian
425     64-bit integer.
426
427It is possible, but unlikely, that collisions in the
428``CallSiteTypeId`` hashing will result in weaker CFI checks that would
429still be conservatively correct.
430
431CFI_Check
432---------
433
434In the general case, only the target DSO knows whether the call to
435function ``f`` with type ``CallSiteTypeId`` is valid or not.  To
436export this information, every DSO implements
437
438.. code-block:: none
439
440   void __cfi_check(uint64 CallSiteTypeId, void *TargetAddr)
441
442This function provides external modules with access to CFI checks for
443the targets inside this DSO.  For each known ``CallSiteTypeId``, this
444functions performs an ``llvm.bitset.test`` with the corresponding bit
445set. It aborts if the type is unknown, or if the check fails.
446
447The basic implementation is a large switch statement over all values
448of CallSiteTypeId supported by this DSO, and each case is similar to
449the InlinedFastCheck() in the basic CFI mode.
450
451CFI Shadow
452----------
453
454To route CFI checks to the target DSO's __cfi_check function, a
455mapping from possible virtual / indirect call targets to
456the corresponding __cfi_check functions is maintained. This mapping is
457implemented as a sparse array of 2 bytes for every possible page (4096
458bytes) of memory. The table is kept readonly (FIXME: not yet) most of
459the time.
460
461There are 3 types of shadow values:
462
463  -  Address in a CFI-instrumented DSO.
464  -  Unchecked address (a “trusted” non-instrumented DSO). Encoded as
465     value 0xFFFF.
466  -  Invalid address (everything else). Encoded as value 0.
467
468For a CFI-instrumented DSO, a shadow value encodes the address of the
469__cfi_check function for all call targets in the corresponding memory
470page. If Addr is the target address, and V is the shadow value, then
471the address of __cfi_check is calculated as
472
473.. code-block:: none
474
475  __cfi_check = AlignUpTo(Addr, 4096) - (V + 1) * 4096
476
477This works as long as __cfi_check is aligned by 4096 bytes and located
478below any call targets in its DSO, but not more than 256MB apart from
479them.
480
481CFI_SlowPath
482------------
483
484The slow path check is implemented in compiler-rt library as
485
486.. code-block:: none
487
488  void __cfi_slowpath(uint64 CallSiteTypeId, void *TargetAddr)
489
490This functions loads a shadow value for ``TargetAddr``, finds the
491address of __cfi_check as described above and calls that.
492
493Position-independent executable requirement
494-------------------------------------------
495
496Cross-DSO CFI mode requires that the main executable is built as PIE.
497In non-PIE executables the address of an external function (taken from
498the main executable) is the address of that function’s PLT record in
499the main executable. This would break the CFI checks.
500