]>
Commit | Line | Data |
---|---|---|
551935d1 | 1 | /* Control flow redundancy hardening |
a945c346 | 2 | Copyright (C) 2022-2024 Free Software Foundation, Inc. |
551935d1 AO |
3 | Contributed by Alexandre Oliva <oliva@adacore.com> |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 3, or (at your option) any later | |
10 | version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | Under Section 7 of GPL version 3, you are granted additional | |
18 | permissions described in the GCC Runtime Library Exception, version | |
19 | 3.1, as published by the Free Software Foundation. | |
20 | ||
21 | You should have received a copy of the GNU General Public License and | |
22 | a copy of the GCC Runtime Library Exception along with this program; | |
23 | see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
24 | <http://www.gnu.org/licenses/>. */ | |
25 | ||
26 | /* Avoid infinite recursion. */ | |
27 | #pragma GCC optimize ("-fno-harden-control-flow-redundancy") | |
28 | ||
29 | #include <stddef.h> | |
30 | #include <stdbool.h> | |
31 | ||
32 | /* This should be kept in sync with gcc/gimple-harden-control-flow.cc. */ | |
33 | #if __CHAR_BIT__ >= 28 | |
34 | # define VWORDmode __QI__ | |
35 | #elif __CHAR_BIT__ >= 14 | |
36 | # define VWORDmode __HI__ | |
37 | #else | |
38 | # define VWORDmode __SI__ | |
39 | #endif | |
40 | ||
41 | typedef unsigned int __attribute__ ((__mode__ (VWORDmode))) vword; | |
42 | ||
43 | /* This function is optionally called at the end of a function to verify that | |
44 | the VISITED array represents a sensible execution path in the CFG. It is | |
45 | always expected to pass; the purpose is to detect attempts to subvert | |
46 | execution by taking unexpected paths, or other execution errors. The | |
47 | function, instrumented by pass_harden_control_flow_redundancy at a time in | |
48 | which it had BLOCKS basic blocks (not counting ENTER and EXIT, so block 2 | |
49 | maps to index 0, the first bit of the first VWORD), sets a bit in the bit | |
50 | array VISITED as it enters the corresponding basic block. CFG holds a | |
51 | representation of the control flow graph at the time of the instrumentation: | |
52 | an array of VWORDs holding, for each block, a sequence of predecessors, and | |
53 | a sequence of successors. Each pred and succ sequence is represented as a | |
54 | sequence of pairs (mask, index), terminated by an index-less all-zero mask. | |
55 | If the bit corresponding to the block is set, then at least one of the pred | |
56 | masks, and at least one of the succ masks, must have a bit set in | |
57 | VISITED[index]. An ENTRY block predecessor and an EXIT block successor are | |
58 | represented in a (mask, index) pair that tests the block's own bit. */ | |
59 | extern void __hardcfr_check (size_t blocks, | |
60 | vword const *visited, | |
61 | vword const *cfg); | |
62 | ||
63 | /* Compute the MASK for the bit representing BLOCK in WORDIDX's vword in a | |
64 | visited blocks bit array. */ | |
65 | static inline void | |
66 | block2mask (size_t const block, vword *const mask, size_t *const wordidx) | |
67 | { | |
68 | size_t wbits = __CHAR_BIT__ * sizeof (vword); | |
69 | *wordidx = block / wbits; | |
70 | *mask = (vword)1 << (block % wbits); | |
71 | } | |
72 | ||
73 | /* Check whether the bit corresponding to BLOCK is set in VISITED. */ | |
74 | static inline bool | |
75 | visited_p (size_t const block, vword const *const visited) | |
76 | { | |
77 | vword mask; | |
78 | size_t wordidx; | |
79 | block2mask (block, &mask, &wordidx); | |
80 | vword w = visited[wordidx]; | |
81 | return (w & mask) != 0; | |
82 | } | |
83 | ||
84 | /* Check whether any VISITED bits that would correspond to blocks after BLOCKS | |
85 | are set. */ | |
86 | static inline bool | |
87 | excess_bits_set_p (size_t const blocks, vword const *const visited) | |
88 | { | |
89 | vword mask; | |
90 | size_t wordidx; | |
91 | block2mask (blocks - 1, &mask, &wordidx); | |
92 | mask = -mask - mask; | |
93 | vword w = visited[wordidx]; | |
94 | return (w & mask) != 0; | |
95 | } | |
96 | ||
97 | /* Read and consume a mask from **CFG_IT. (Consume meaning advancing the | |
98 | iterator to the next word). If the mask is zero, return FALSE. Otherwise, | |
99 | also read and consume an index, and set *MASK and/or *WORDIDX, whichever are | |
100 | nonNULL, to the corresponding read values, and finally return TRUE. */ | |
101 | static inline bool | |
102 | next_pair (vword const **const cfg_it, | |
103 | vword *const mask, | |
104 | size_t *const wordidx) | |
105 | { | |
106 | vword m = **cfg_it; | |
107 | ++*cfg_it; | |
108 | if (!m) | |
109 | return false; | |
110 | ||
111 | if (mask) | |
112 | *mask = m; | |
113 | ||
114 | size_t word = **cfg_it; | |
115 | ++*cfg_it; | |
116 | ||
117 | if (wordidx) | |
118 | *wordidx = word; | |
119 | ||
120 | return true; | |
121 | } | |
122 | ||
123 | /* Return TRUE iff any of the bits in MASK is set in VISITED[WORDIDX]. */ | |
124 | static inline bool | |
125 | test_mask (vword const *const visited, | |
126 | vword const mask, size_t const wordidx) | |
127 | { | |
128 | return (visited[wordidx] & mask) != 0; | |
129 | } | |
130 | ||
131 | /* Scan a sequence of pairs (mask, index) at **CFG_IT until its terminator is | |
132 | reached and consumed. */ | |
133 | static inline void | |
134 | consume_seq (vword const **const cfg_it) | |
135 | { | |
136 | while (next_pair (cfg_it, NULL, NULL)) | |
137 | /* Do nothing. */; | |
138 | } | |
139 | ||
140 | /* Check that at least one of the MASK bits in a sequence of pairs (mask, | |
141 | index) at **CFG_IT is set in the corresponding VISITED[INDEX] word. Trap if | |
142 | we reach the terminator without finding any. Consume the entire sequence | |
143 | otherwise, so that *CFG_IT points just past the terminator, which may be the | |
144 | beginning of the next sequence. */ | |
145 | static inline bool | |
146 | check_seq (vword const *const visited, vword const **const cfg_it) | |
147 | { | |
148 | vword mask; | |
149 | size_t wordidx; | |
150 | ||
151 | /* If the block was visited, check that at least one of the | |
152 | preds/succs was also visited. */ | |
153 | do | |
154 | /* If we get to the end of the sequence without finding any | |
155 | match, something is amiss. */ | |
156 | if (!next_pair (cfg_it, &mask, &wordidx)) | |
157 | return false; | |
158 | /* Keep searching until we find a match, at which point the | |
159 | condition is satisfied. */ | |
160 | while (!test_mask (visited, mask, wordidx)); | |
161 | ||
162 | /* Consume the remaining entries in the sequence, whether we found a match or | |
163 | skipped the block, so as to position the iterator at the beginning of the | |
164 | next . */ | |
165 | consume_seq (cfg_it); | |
166 | ||
167 | return true; | |
168 | } | |
169 | ||
170 | /* Print out the CFG with BLOCKS blocks, presumed to be associated with CALLER. | |
171 | This is expected to be optimized out entirely, unless the verbose part of | |
172 | __hardcfr_check_fail is enabled. */ | |
173 | static inline void | |
174 | __hardcfr_debug_cfg (size_t const blocks, | |
175 | void const *const caller, | |
176 | vword const *const cfg) | |
177 | { | |
178 | __builtin_printf ("CFG at %p, for %p", cfg, caller); | |
179 | vword const *cfg_it = cfg; | |
180 | for (size_t i = 0; i < blocks; i++) | |
181 | { | |
182 | vword mask; size_t wordidx; | |
183 | block2mask (i, &mask, &wordidx); | |
184 | __builtin_printf ("\nblock %lu (%lu/0x%lx)\npreds: ", | |
185 | (unsigned long)i, | |
186 | (unsigned long)wordidx, (unsigned long)mask); | |
187 | while (next_pair (&cfg_it, &mask, &wordidx)) | |
188 | __builtin_printf (" (%lu/0x%lx)", | |
189 | (unsigned long)wordidx, (unsigned long)mask); | |
190 | __builtin_printf ("\nsuccs: "); | |
191 | while (next_pair (&cfg_it, &mask, &wordidx)) | |
192 | __builtin_printf (" (%lu/0x%lx)", | |
193 | (unsigned long)wordidx, (unsigned long)mask); | |
194 | } | |
195 | __builtin_printf ("\n"); | |
196 | } | |
197 | ||
198 | #ifndef ATTRIBUTE_UNUSED | |
199 | # define ATTRIBUTE_UNUSED __attribute__ ((__unused__)) | |
200 | #endif | |
201 | ||
202 | /* This is called when an out-of-line hardcfr check fails. All the arguments | |
203 | are ignored, and it just traps, unless HARDCFR_VERBOSE_FAIL is enabled. IF | |
204 | it is, it prints the PART of the CFG, expected to have BLOCKS blocks, that | |
205 | failed at CALLER's BLOCK, and the VISITED bitmap. When the verbose mode is | |
206 | enabled, it also forces __hardcfr_debug_cfg (above) to be compiled into an | |
207 | out-of-line function, that could be called from a debugger. | |
208 | */ | |
2eb83353 JM |
209 | |
210 | #ifdef __BPF__ | |
211 | __attribute__((__always_inline__)) | |
212 | #endif | |
551935d1 AO |
213 | static inline void |
214 | __hardcfr_check_fail (size_t const blocks ATTRIBUTE_UNUSED, | |
215 | vword const *const visited ATTRIBUTE_UNUSED, | |
216 | vword const *const cfg ATTRIBUTE_UNUSED, | |
217 | size_t const block ATTRIBUTE_UNUSED, | |
218 | int const part ATTRIBUTE_UNUSED, | |
219 | void const *const caller ATTRIBUTE_UNUSED) | |
220 | { | |
221 | #if HARDCFR_VERBOSE_FAIL | |
222 | static const char *parts[] = { "preds", "succs", "no excess" }; | |
223 | ||
224 | vword mask; size_t wordidx; | |
225 | block2mask (block, &mask, &wordidx); | |
226 | if (part == 2) | |
227 | mask = -mask - mask; | |
228 | __builtin_printf ("hardcfr fail at %p block %lu (%lu/0x%lx), expected %s:", | |
229 | caller, (unsigned long)block, | |
230 | (unsigned long)wordidx, (unsigned long)mask, | |
231 | parts[part]); | |
232 | ||
233 | if (part != 2) | |
234 | { | |
235 | /* Skip data for previous blocks. */ | |
236 | vword const *cfg_it = cfg; | |
237 | for (size_t i = block; i--; ) | |
238 | { | |
239 | consume_seq (&cfg_it); | |
240 | consume_seq (&cfg_it); | |
241 | } | |
242 | for (size_t i = part; i--; ) | |
243 | consume_seq (&cfg_it); | |
244 | ||
245 | while (next_pair (&cfg_it, &mask, &wordidx)) | |
246 | __builtin_printf (" (%lu/0x%lx)", | |
247 | (unsigned long)wordidx, (unsigned long)mask); | |
248 | } | |
249 | ||
250 | __builtin_printf ("\nvisited:"); | |
251 | block2mask (blocks - 1, &mask, &wordidx); | |
252 | for (size_t i = 0; i <= wordidx; i++) | |
253 | __builtin_printf (" (%lu/0x%lx)", | |
254 | (unsigned long)i, (unsigned long)visited[i]); | |
255 | __builtin_printf ("\n"); | |
256 | ||
257 | /* Reference __hardcfr_debug_cfg so that it's output out-of-line, so that it | |
258 | can be called from a debugger. */ | |
259 | if (!caller || caller == __hardcfr_debug_cfg) | |
260 | return; | |
261 | #endif | |
262 | __builtin_trap (); | |
263 | } | |
264 | ||
265 | /* Check that, for each of the BLOCKS basic blocks, if its bit is set in | |
266 | VISITED, at least one of its predecessors in CFG is also set, and at also | |
267 | that at least one of its successors in CFG is also set. */ | |
268 | void | |
269 | __hardcfr_check (size_t const blocks, | |
270 | vword const *const visited, | |
271 | vword const *const cfg) | |
272 | { | |
273 | vword const *cfg_it = cfg; | |
274 | for (size_t i = 0; i < blocks; i++) | |
275 | { | |
276 | bool v = visited_p (i, visited); | |
277 | ||
278 | /* For each block, there are two sequences of pairs (mask, index), each | |
279 | sequence terminated by a single all-zero mask (no index). The first | |
280 | sequence is for predecessor blocks, the second is for successors. At | |
281 | least one of each must be set. */ | |
282 | if (!v) | |
283 | { | |
284 | /* Consume predecessors. */ | |
285 | consume_seq (&cfg_it); | |
286 | /* Consume successors. */ | |
287 | consume_seq (&cfg_it); | |
288 | } | |
289 | else | |
290 | { | |
291 | /* Check predecessors. */ | |
292 | if (!check_seq (visited, &cfg_it)) | |
293 | __hardcfr_check_fail (blocks, visited, cfg, i, 0, | |
294 | __builtin_return_address (0)); | |
295 | /* Check successors. */ | |
296 | if (!check_seq (visited, &cfg_it)) | |
297 | __hardcfr_check_fail (blocks, visited, cfg, i, 1, | |
298 | __builtin_return_address (0)); | |
299 | } | |
300 | } | |
301 | if (excess_bits_set_p (blocks, visited)) | |
302 | __hardcfr_check_fail (blocks, visited, cfg, blocks - 1, 2, | |
303 | __builtin_return_address (0)); | |
304 | } |