Mercurial > hg > CbC > CbC_llvm

comparison tools/clang/docs/ControlFlowIntegrityDesign.rst @ 95:afa8332a0e37 LLVM3.8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.8
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Tue, 13 Oct 2015 17:48:58 +0900
parents
children 7d135dc70f03
comparison
equal deleted inserted replaced
84:f3e34b893a5f 95:afa8332a0e37
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
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
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
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
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
97 .. _ByteArrayBuilder: http://llvm.org/docs/doxygen/html/structllvm_1_1ByteArrayBuilder.html
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.
276
277 Forward-Edge CFI for Indirect Function Calls
278 ============================================
279
280 Sorry, no documentation yet, but see the comments at the top of
281 ``LowerBitSets::buildBitSetsFromFunctions`` in `LowerBitSets.cpp`_.
282
283 .. _LowerBitSets.cpp: http://llvm.org/klaus/llvm/blob/master/lib/Transforms/IPO/LowerBitSets.cpp