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 if the bit
61vector is stored in memory:
62
63.. code-block:: none
64
65    159a:       48 8b 03                mov    (%rbx),%rax
66    159d:       48 8d 15 6c 33 00 00    lea    0x336c(%rip),%rdx
67    15a4:       48 89 c1                mov    %rax,%rcx
68    15a7:       48 29 d1                sub    %rdx,%rcx
69    15aa:       48 c1 c1 3d             rol    $0x3d,%rcx
70    15ae:       48 83 f9 51             cmp    $0x51,%rcx
71    15b2:       77 3b                   ja     15ef <main+0xcf>
72    15b4:       48 89 ca                mov    %rcx,%rdx
73    15b7:       48 c1 ea 05             shr    $0x5,%rdx
74    15bb:       48 8d 35 b8 07 00 00    lea    0x7b8(%rip),%rsi
75    15c2:       8b 14 96                mov    (%rsi,%rdx,4),%edx
76    15c5:       0f a3 ca                bt     %ecx,%edx
77    15c8:       73 25                   jae    15ef <main+0xcf>
78    15ca:       48 89 df                mov    %rbx,%rdi
79    15cd:       ff 10                   callq  *(%rax)
80    [...]
81    15ef:       0f 0b                   ud2
82
83Or if the bit vector fits in 32 bits:
84
85.. code-block:: none
86
87     dc2:       48 8b 03                mov    (%rbx),%rax
88     dc5:       48 8d 15 14 1e 00 00    lea    0x1e14(%rip),%rdx
89     dcc:       48 89 c1                mov    %rax,%rcx
90     dcf:       48 29 d1                sub    %rdx,%rcx
91     dd2:       48 c1 c1 3d             rol    $0x3d,%rcx
92     dd6:       48 83 f9 03             cmp    $0x3,%rcx
93     dda:       77 2f                   ja     e0b <main+0x9b>
94     ddc:       ba 09 00 00 00          mov    $0x9,%edx
95     de1:       0f a3 ca                bt     %ecx,%edx
96     de4:       73 25                   jae    e0b <main+0x9b>
97     de6:       48 89 df                mov    %rbx,%rdi
98     de9:       ff 10                   callq  *(%rax)
99    [...]
100     e0b:       0f 0b                   ud2
101
102Or if the bit vector fits in 64 bits:
103
104.. code-block:: none
105
106    11a6:       48 8b 03                mov    (%rbx),%rax
107    11a9:       48 8d 15 d0 28 00 00    lea    0x28d0(%rip),%rdx
108    11b0:       48 89 c1                mov    %rax,%rcx
109    11b3:       48 29 d1                sub    %rdx,%rcx
110    11b6:       48 c1 c1 3d             rol    $0x3d,%rcx
111    11ba:       48 83 f9 2a             cmp    $0x2a,%rcx
112    11be:       77 35                   ja     11f5 <main+0xb5>
113    11c0:       48 ba 09 00 00 00 00    movabs $0x40000000009,%rdx
114    11c7:       04 00 00
115    11ca:       48 0f a3 ca             bt     %rcx,%rdx
116    11ce:       73 25                   jae    11f5 <main+0xb5>
117    11d0:       48 89 df                mov    %rbx,%rdi
118    11d3:       ff 10                   callq  *(%rax)
119    [...]
120    11f5:       0f 0b                   ud2
121
122The compiler relies on co-operation from the linker in order to assemble
123the bit vector for the whole program. It currently does this using LLVM's
124`bit sets`_ mechanism together with link-time optimization.
125
126.. _address point: https://mentorembedded.github.io/cxx-abi/abi.html#vtable-general
127.. _bit sets: http://llvm.org/docs/BitSets.html
128