Stephen Hines | 0e2c34f | 2015-03-23 12:09:02 -0700 | [diff] [blame] | 1 | =========================================== |
| 2 | Control Flow Integrity Design Documentation |
| 3 | =========================================== |
| 4 | |
| 5 | This page documents the design of the :doc:`ControlFlowIntegrity` schemes |
| 6 | supported by Clang. |
| 7 | |
| 8 | Forward-Edge CFI for Virtual Calls |
| 9 | ================================== |
| 10 | |
| 11 | This scheme works by allocating, for each static type used to make a virtual |
| 12 | call, a region of read-only storage in the object file holding a bit vector |
| 13 | that maps onto to the region of storage used for those virtual tables. Each |
| 14 | set bit in the bit vector corresponds to the `address point`_ for a virtual |
| 15 | table compatible with the static type for which the bit vector is being built. |
| 16 | |
| 17 | For 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 | |
| 39 | The scheme will cause the virtual tables for A, B and C to be laid out |
| 40 | consecutively: |
| 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 | |
| 47 | The 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 | |
Pirama Arumuga Nainar | 3ea9e33 | 2015-04-08 08:57:32 -0700 | [diff] [blame] | 56 | Bit vectors are represented in the object file as byte arrays. By loading |
| 57 | from indexed offsets into the byte array and applying a mask, a program can |
| 58 | test bits from the bit set with a relatively short instruction sequence. Bit |
| 59 | vectors may overlap so long as they use different bits. For the full details, |
| 60 | see the `ByteArrayBuilder`_ class. |
| 61 | |
| 62 | In this case, assuming A is laid out at offset 0 in bit 0, B at offset 0 in |
| 63 | bit 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 | |
Stephen Hines | 0e2c34f | 2015-03-23 12:09:02 -0700 | [diff] [blame] | 69 | To emit a virtual call, the compiler will assemble code that checks that |
| 70 | the object's virtual table pointer is in-bounds and aligned and that the |
| 71 | relevant bit is set in the bit vector. |
| 72 | |
| 73 | For example on x86 a typical virtual call may look like this: |
| 74 | |
| 75 | .. code-block:: none |
| 76 | |
Pirama Arumuga Nainar | 3ea9e33 | 2015-04-08 08:57:32 -0700 | [diff] [blame] | 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) |
Stephen Hines | 0e2c34f | 2015-03-23 12:09:02 -0700 | [diff] [blame] | 88 | [...] |
Pirama Arumuga Nainar | 3ea9e33 | 2015-04-08 08:57:32 -0700 | [diff] [blame] | 89 | ca8511: 0f 0b ud2 |
Stephen Hines | 0e2c34f | 2015-03-23 12:09:02 -0700 | [diff] [blame] | 90 | |
| 91 | The compiler relies on co-operation from the linker in order to assemble |
| 92 | the 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 |
Pirama Arumuga Nainar | 3ea9e33 | 2015-04-08 08:57:32 -0700 | [diff] [blame] | 97 | .. _ByteArrayBuilder: http://llvm.org/docs/doxygen/html/structllvm_1_1ByteArrayBuilder.html |
Stephen Hines | 0e2c34f | 2015-03-23 12:09:02 -0700 | [diff] [blame] | 98 | |
| 99 | Optimizations |
| 100 | ------------- |
| 101 | |
| 102 | The scheme as described above is the fully general variant of the scheme. |
| 103 | Most of the time we are able to apply one or more of the following |
| 104 | optimizations to improve binary size or performance. |
| 105 | |
| 106 | In fact, if you try the above example with the current version of the |
| 107 | compiler, you will probably find that it will not use the described virtual |
| 108 | table layout or machine instructions. Some of the optimizations we are about |
| 109 | to introduce cause the compiler to use a different layout or a different |
| 110 | sequence of machine instructions. |
| 111 | |
| 112 | Stripping Leading/Trailing Zeros in Bit Vectors |
| 113 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 114 | |
| 115 | If a bit vector contains leading or trailing zeros, we can strip them from |
| 116 | the vector. The compiler will emit code to check if the pointer is in range |
| 117 | of the region covered by ones, and perform the bit vector check using a |
| 118 | truncated version of the bit vector. For example, the bit vectors for our |
| 119 | example 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 | |
| 128 | Short Inline Bit Vectors |
| 129 | ~~~~~~~~~~~~~~~~~~~~~~~~ |
| 130 | |
| 131 | If the vector is sufficiently short, we can represent it as an inline constant |
| 132 | on x86. This saves us a few instructions when reading the correct element |
| 133 | of the bit vector. |
| 134 | |
| 135 | If 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 | |
| 154 | Or 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 | |
| 174 | If the bit vector consists of a single bit, there is only one possible |
| 175 | virtual 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 | |
| 188 | Virtual Table Layout |
| 189 | ~~~~~~~~~~~~~~~~~~~~ |
| 190 | |
| 191 | The compiler lays out classes of disjoint hierarchies in separate regions |
| 192 | of the object file. At worst, bit vectors in disjoint hierarchies only |
| 193 | need to cover their disjoint hierarchy. But the closer that classes in |
| 194 | sub-hierarchies are laid out to each other, the smaller the bit vectors for |
| 195 | those sub-hierarchies need to be (see "Stripping Leading/Trailing Zeros in Bit |
| 196 | Vectors" above). The `GlobalLayoutBuilder`_ class is responsible for laying |
| 197 | out 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 | |
| 201 | Alignment |
| 202 | ~~~~~~~~~ |
| 203 | |
| 204 | If all gaps between address points in a particular bit vector are multiples |
| 205 | of powers of 2, the compiler can compress the bit vector by strengthening |
| 206 | the alignment requirements of the virtual table pointer. For example, given |
| 207 | this 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 | |
| 230 | The 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 | |
| 237 | Notice that each address point for A is separated by 4 words. This lets us |
| 238 | emit 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 | |
| 245 | At call sites, the compiler will strengthen the alignment requirements by |
| 246 | using a different rotate count. For example, on a 64-bit machine where the |
| 247 | address points are 4-word aligned (as in A from our example), the ``rol`` |
| 248 | instruction may look like this: |
| 249 | |
| 250 | .. code-block:: none |
| 251 | |
| 252 | dd2: 48 c1 c1 3b rol $0x3b,%rcx |
| 253 | |
| 254 | Padding to Powers of 2 |
| 255 | ~~~~~~~~~~~~~~~~~~~~~~ |
| 256 | |
| 257 | Of course, this alignment scheme works best if the address points are |
| 258 | in fact aligned correctly. To make this more likely to happen, we insert |
| 259 | padding between virtual tables that in many cases aligns address points to |
| 260 | a power of 2. Specifically, our padding aligns virtual tables to the next |
| 261 | highest power of 2 bytes; because address points for specific base classes |
| 262 | normally appear at fixed offsets within the virtual table, this normally |
| 263 | has the effect of aligning the address points as well. |
| 264 | |
| 265 | This scheme introduces tradeoffs between decreased space overhead for |
| 266 | instructions and bit vectors and increased overhead in the form of padding. We |
| 267 | therefore limit the amount of padding so that we align to no more than 128 |
| 268 | bytes. This number was found experimentally to provide a good tradeoff. |
| 269 | |
| 270 | Eliminating Bit Vector Checks for All-Ones Bit Vectors |
| 271 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 272 | |
| 273 | If the bit vector is all ones, the bit vector check is redundant; we simply |
| 274 | need to check that the address is in range and well aligned. This is more |
| 275 | likely to occur if the virtual tables are padded. |