Loading...
Note: File does not exist in v3.15.
1/*
2 * Copyright 2012-2016 by the PaX Team <pageexec@freemail.hu>
3 * Copyright 2016 by Emese Revfy <re.emese@gmail.com>
4 * Licensed under the GPL v2
5 *
6 * Note: the choice of the license means that the compilation process is
7 * NOT 'eligible' as defined by gcc's library exception to the GPL v3,
8 * but for the kernel it doesn't matter since it doesn't link against
9 * any of the gcc libraries
10 *
11 * This gcc plugin helps generate a little bit of entropy from program state,
12 * used throughout the uptime of the kernel. Here is an instrumentation example:
13 *
14 * before:
15 * void __latent_entropy test(int argc, char *argv[])
16 * {
17 * if (argc <= 1)
18 * printf("%s: no command arguments :(\n", *argv);
19 * else
20 * printf("%s: %d command arguments!\n", *argv, args - 1);
21 * }
22 *
23 * after:
24 * void __latent_entropy test(int argc, char *argv[])
25 * {
26 * // latent_entropy_execute() 1.
27 * unsigned long local_entropy;
28 * // init_local_entropy() 1.
29 * void *local_entropy_frameaddr;
30 * // init_local_entropy() 3.
31 * unsigned long tmp_latent_entropy;
32 *
33 * // init_local_entropy() 2.
34 * local_entropy_frameaddr = __builtin_frame_address(0);
35 * local_entropy = (unsigned long) local_entropy_frameaddr;
36 *
37 * // init_local_entropy() 4.
38 * tmp_latent_entropy = latent_entropy;
39 * // init_local_entropy() 5.
40 * local_entropy ^= tmp_latent_entropy;
41 *
42 * // latent_entropy_execute() 3.
43 * if (argc <= 1) {
44 * // perturb_local_entropy()
45 * local_entropy += 4623067384293424948;
46 * printf("%s: no command arguments :(\n", *argv);
47 * // perturb_local_entropy()
48 * } else {
49 * local_entropy ^= 3896280633962944730;
50 * printf("%s: %d command arguments!\n", *argv, args - 1);
51 * }
52 *
53 * // latent_entropy_execute() 4.
54 * tmp_latent_entropy = rol(tmp_latent_entropy, local_entropy);
55 * latent_entropy = tmp_latent_entropy;
56 * }
57 *
58 * TODO:
59 * - add ipa pass to identify not explicitly marked candidate functions
60 * - mix in more program state (function arguments/return values,
61 * loop variables, etc)
62 * - more instrumentation control via attribute parameters
63 *
64 * BUGS:
65 * - none known
66 *
67 * Options:
68 * -fplugin-arg-latent_entropy_plugin-disable
69 *
70 * Attribute: __attribute__((latent_entropy))
71 * The latent_entropy gcc attribute can be only on functions and variables.
72 * If it is on a function then the plugin will instrument it. If the attribute
73 * is on a variable then the plugin will initialize it with a random value.
74 * The variable must be an integer, an integer array type or a structure
75 * with integer fields.
76 */
77
78#include "gcc-common.h"
79
80__visible int plugin_is_GPL_compatible;
81
82static GTY(()) tree latent_entropy_decl;
83
84static struct plugin_info latent_entropy_plugin_info = {
85 .version = "201606141920vanilla",
86 .help = "disable\tturn off latent entropy instrumentation\n",
87};
88
89static unsigned HOST_WIDE_INT seed;
90/*
91 * get_random_seed() (this is a GCC function) generates the seed.
92 * This is a simple random generator without any cryptographic security because
93 * the entropy doesn't come from here.
94 */
95static unsigned HOST_WIDE_INT get_random_const(void)
96{
97 unsigned int i;
98 unsigned HOST_WIDE_INT ret = 0;
99
100 for (i = 0; i < 8 * sizeof(ret); i++) {
101 ret = (ret << 1) | (seed & 1);
102 seed >>= 1;
103 if (ret & 1)
104 seed ^= 0xD800000000000000ULL;
105 }
106
107 return ret;
108}
109
110static tree tree_get_random_const(tree type)
111{
112 unsigned long long mask;
113
114 mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(type)) - 1);
115 mask = 2 * (mask - 1) + 1;
116
117 if (TYPE_UNSIGNED(type))
118 return build_int_cstu(type, mask & get_random_const());
119 return build_int_cst(type, mask & get_random_const());
120}
121
122static tree handle_latent_entropy_attribute(tree *node, tree name,
123 tree args __unused,
124 int flags __unused,
125 bool *no_add_attrs)
126{
127 tree type;
128 vec<constructor_elt, va_gc> *vals;
129
130 switch (TREE_CODE(*node)) {
131 default:
132 *no_add_attrs = true;
133 error("%qE attribute only applies to functions and variables",
134 name);
135 break;
136
137 case VAR_DECL:
138 if (DECL_INITIAL(*node)) {
139 *no_add_attrs = true;
140 error("variable %qD with %qE attribute must not be initialized",
141 *node, name);
142 break;
143 }
144
145 if (!TREE_STATIC(*node)) {
146 *no_add_attrs = true;
147 error("variable %qD with %qE attribute must not be local",
148 *node, name);
149 break;
150 }
151
152 type = TREE_TYPE(*node);
153 switch (TREE_CODE(type)) {
154 default:
155 *no_add_attrs = true;
156 error("variable %qD with %qE attribute must be an integer or a fixed length integer array type or a fixed sized structure with integer fields",
157 *node, name);
158 break;
159
160 case RECORD_TYPE: {
161 tree fld, lst = TYPE_FIELDS(type);
162 unsigned int nelt = 0;
163
164 for (fld = lst; fld; nelt++, fld = TREE_CHAIN(fld)) {
165 tree fieldtype;
166
167 fieldtype = TREE_TYPE(fld);
168 if (TREE_CODE(fieldtype) == INTEGER_TYPE)
169 continue;
170
171 *no_add_attrs = true;
172 error("structure variable %qD with %qE attribute has a non-integer field %qE",
173 *node, name, fld);
174 break;
175 }
176
177 if (fld)
178 break;
179
180 vec_alloc(vals, nelt);
181
182 for (fld = lst; fld; fld = TREE_CHAIN(fld)) {
183 tree random_const, fld_t = TREE_TYPE(fld);
184
185 random_const = tree_get_random_const(fld_t);
186 CONSTRUCTOR_APPEND_ELT(vals, fld, random_const);
187 }
188
189 /* Initialize the fields with random constants */
190 DECL_INITIAL(*node) = build_constructor(type, vals);
191 break;
192 }
193
194 /* Initialize the variable with a random constant */
195 case INTEGER_TYPE:
196 DECL_INITIAL(*node) = tree_get_random_const(type);
197 break;
198
199 case ARRAY_TYPE: {
200 tree elt_type, array_size, elt_size;
201 unsigned int i, nelt;
202 HOST_WIDE_INT array_size_int, elt_size_int;
203
204 elt_type = TREE_TYPE(type);
205 elt_size = TYPE_SIZE_UNIT(TREE_TYPE(type));
206 array_size = TYPE_SIZE_UNIT(type);
207
208 if (TREE_CODE(elt_type) != INTEGER_TYPE || !array_size
209 || TREE_CODE(array_size) != INTEGER_CST) {
210 *no_add_attrs = true;
211 error("array variable %qD with %qE attribute must be a fixed length integer array type",
212 *node, name);
213 break;
214 }
215
216 array_size_int = TREE_INT_CST_LOW(array_size);
217 elt_size_int = TREE_INT_CST_LOW(elt_size);
218 nelt = array_size_int / elt_size_int;
219
220 vec_alloc(vals, nelt);
221
222 for (i = 0; i < nelt; i++) {
223 tree cst = size_int(i);
224 tree rand_cst = tree_get_random_const(elt_type);
225
226 CONSTRUCTOR_APPEND_ELT(vals, cst, rand_cst);
227 }
228
229 /*
230 * Initialize the elements of the array with random
231 * constants
232 */
233 DECL_INITIAL(*node) = build_constructor(type, vals);
234 break;
235 }
236 }
237 break;
238
239 case FUNCTION_DECL:
240 break;
241 }
242
243 return NULL_TREE;
244}
245
246static struct attribute_spec latent_entropy_attr = { };
247
248static void register_attributes(void *event_data __unused, void *data __unused)
249{
250 latent_entropy_attr.name = "latent_entropy";
251 latent_entropy_attr.decl_required = true;
252 latent_entropy_attr.handler = handle_latent_entropy_attribute;
253
254 register_attribute(&latent_entropy_attr);
255}
256
257static bool latent_entropy_gate(void)
258{
259 tree list;
260
261 /* don't bother with noreturn functions for now */
262 if (TREE_THIS_VOLATILE(current_function_decl))
263 return false;
264
265 /* gcc-4.5 doesn't discover some trivial noreturn functions */
266 if (EDGE_COUNT(EXIT_BLOCK_PTR_FOR_FN(cfun)->preds) == 0)
267 return false;
268
269 list = DECL_ATTRIBUTES(current_function_decl);
270 return lookup_attribute("latent_entropy", list) != NULL_TREE;
271}
272
273static tree create_var(tree type, const char *name)
274{
275 tree var;
276
277 var = create_tmp_var(type, name);
278 add_referenced_var(var);
279 mark_sym_for_renaming(var);
280 return var;
281}
282
283/*
284 * Set up the next operation and its constant operand to use in the latent
285 * entropy PRNG. When RHS is specified, the request is for perturbing the
286 * local latent entropy variable, otherwise it is for perturbing the global
287 * latent entropy variable where the two operands are already given by the
288 * local and global latent entropy variables themselves.
289 *
290 * The operation is one of add/xor/rol when instrumenting the local entropy
291 * variable and one of add/xor when perturbing the global entropy variable.
292 * Rotation is not used for the latter case because it would transmit less
293 * entropy to the global variable than the other two operations.
294 */
295static enum tree_code get_op(tree *rhs)
296{
297 static enum tree_code op;
298 unsigned HOST_WIDE_INT random_const;
299
300 random_const = get_random_const();
301
302 switch (op) {
303 case BIT_XOR_EXPR:
304 op = PLUS_EXPR;
305 break;
306
307 case PLUS_EXPR:
308 if (rhs) {
309 op = LROTATE_EXPR;
310 /*
311 * This code limits the value of random_const to
312 * the size of a long for the rotation
313 */
314 random_const %= TYPE_PRECISION(long_unsigned_type_node);
315 break;
316 }
317
318 case LROTATE_EXPR:
319 default:
320 op = BIT_XOR_EXPR;
321 break;
322 }
323 if (rhs)
324 *rhs = build_int_cstu(long_unsigned_type_node, random_const);
325 return op;
326}
327
328static gimple create_assign(enum tree_code code, tree lhs, tree op1,
329 tree op2)
330{
331 return gimple_build_assign_with_ops(code, lhs, op1, op2);
332}
333
334static void perturb_local_entropy(basic_block bb, tree local_entropy)
335{
336 gimple_stmt_iterator gsi;
337 gimple assign;
338 tree rhs;
339 enum tree_code op;
340
341 op = get_op(&rhs);
342 assign = create_assign(op, local_entropy, local_entropy, rhs);
343 gsi = gsi_after_labels(bb);
344 gsi_insert_before(&gsi, assign, GSI_NEW_STMT);
345 update_stmt(assign);
346}
347
348static void __perturb_latent_entropy(gimple_stmt_iterator *gsi,
349 tree local_entropy)
350{
351 gimple assign;
352 tree temp;
353 enum tree_code op;
354
355 /* 1. create temporary copy of latent_entropy */
356 temp = create_var(long_unsigned_type_node, "temp_latent_entropy");
357
358 /* 2. read... */
359 add_referenced_var(latent_entropy_decl);
360 mark_sym_for_renaming(latent_entropy_decl);
361 assign = gimple_build_assign(temp, latent_entropy_decl);
362 gsi_insert_before(gsi, assign, GSI_NEW_STMT);
363 update_stmt(assign);
364
365 /* 3. ...modify... */
366 op = get_op(NULL);
367 assign = create_assign(op, temp, temp, local_entropy);
368 gsi_insert_after(gsi, assign, GSI_NEW_STMT);
369 update_stmt(assign);
370
371 /* 4. ...write latent_entropy */
372 assign = gimple_build_assign(latent_entropy_decl, temp);
373 gsi_insert_after(gsi, assign, GSI_NEW_STMT);
374 update_stmt(assign);
375}
376
377static bool handle_tail_calls(basic_block bb, tree local_entropy)
378{
379 gimple_stmt_iterator gsi;
380
381 for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
382 gcall *call;
383 gimple stmt = gsi_stmt(gsi);
384
385 if (!is_gimple_call(stmt))
386 continue;
387
388 call = as_a_gcall(stmt);
389 if (!gimple_call_tail_p(call))
390 continue;
391
392 __perturb_latent_entropy(&gsi, local_entropy);
393 return true;
394 }
395
396 return false;
397}
398
399static void perturb_latent_entropy(tree local_entropy)
400{
401 edge_iterator ei;
402 edge e, last_bb_e;
403 basic_block last_bb;
404
405 gcc_assert(single_pred_p(EXIT_BLOCK_PTR_FOR_FN(cfun)));
406 last_bb_e = single_pred_edge(EXIT_BLOCK_PTR_FOR_FN(cfun));
407
408 FOR_EACH_EDGE(e, ei, last_bb_e->src->preds) {
409 if (ENTRY_BLOCK_PTR_FOR_FN(cfun) == e->src)
410 continue;
411 if (EXIT_BLOCK_PTR_FOR_FN(cfun) == e->src)
412 continue;
413
414 handle_tail_calls(e->src, local_entropy);
415 }
416
417 last_bb = single_pred(EXIT_BLOCK_PTR_FOR_FN(cfun));
418 if (!handle_tail_calls(last_bb, local_entropy)) {
419 gimple_stmt_iterator gsi = gsi_last_bb(last_bb);
420
421 __perturb_latent_entropy(&gsi, local_entropy);
422 }
423}
424
425static void init_local_entropy(basic_block bb, tree local_entropy)
426{
427 gimple assign, call;
428 tree frame_addr, rand_const, tmp, fndecl, udi_frame_addr;
429 enum tree_code op;
430 unsigned HOST_WIDE_INT rand_cst;
431 gimple_stmt_iterator gsi = gsi_after_labels(bb);
432
433 /* 1. create local_entropy_frameaddr */
434 frame_addr = create_var(ptr_type_node, "local_entropy_frameaddr");
435
436 /* 2. local_entropy_frameaddr = __builtin_frame_address() */
437 fndecl = builtin_decl_implicit(BUILT_IN_FRAME_ADDRESS);
438 call = gimple_build_call(fndecl, 1, integer_zero_node);
439 gimple_call_set_lhs(call, frame_addr);
440 gsi_insert_before(&gsi, call, GSI_NEW_STMT);
441 update_stmt(call);
442
443 udi_frame_addr = fold_convert(long_unsigned_type_node, frame_addr);
444 assign = gimple_build_assign(local_entropy, udi_frame_addr);
445 gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
446 update_stmt(assign);
447
448 /* 3. create temporary copy of latent_entropy */
449 tmp = create_var(long_unsigned_type_node, "temp_latent_entropy");
450
451 /* 4. read the global entropy variable into local entropy */
452 add_referenced_var(latent_entropy_decl);
453 mark_sym_for_renaming(latent_entropy_decl);
454 assign = gimple_build_assign(tmp, latent_entropy_decl);
455 gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
456 update_stmt(assign);
457
458 /* 5. mix local_entropy_frameaddr into local entropy */
459 assign = create_assign(BIT_XOR_EXPR, local_entropy, local_entropy, tmp);
460 gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
461 update_stmt(assign);
462
463 rand_cst = get_random_const();
464 rand_const = build_int_cstu(long_unsigned_type_node, rand_cst);
465 op = get_op(NULL);
466 assign = create_assign(op, local_entropy, local_entropy, rand_const);
467 gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
468 update_stmt(assign);
469}
470
471static bool create_latent_entropy_decl(void)
472{
473 varpool_node_ptr node;
474
475 if (latent_entropy_decl != NULL_TREE)
476 return true;
477
478 FOR_EACH_VARIABLE(node) {
479 tree name, var = NODE_DECL(node);
480
481 if (DECL_NAME_LENGTH(var) < sizeof("latent_entropy") - 1)
482 continue;
483
484 name = DECL_NAME(var);
485 if (strcmp(IDENTIFIER_POINTER(name), "latent_entropy"))
486 continue;
487
488 latent_entropy_decl = var;
489 break;
490 }
491
492 return latent_entropy_decl != NULL_TREE;
493}
494
495static unsigned int latent_entropy_execute(void)
496{
497 basic_block bb;
498 tree local_entropy;
499
500 if (!create_latent_entropy_decl())
501 return 0;
502
503 /* prepare for step 2 below */
504 gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
505 bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
506 if (!single_pred_p(bb)) {
507 split_edge(single_succ_edge(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
508 gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
509 bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
510 }
511
512 /* 1. create the local entropy variable */
513 local_entropy = create_var(long_unsigned_type_node, "local_entropy");
514
515 /* 2. initialize the local entropy variable */
516 init_local_entropy(bb, local_entropy);
517
518 bb = bb->next_bb;
519
520 /*
521 * 3. instrument each BB with an operation on the
522 * local entropy variable
523 */
524 while (bb != EXIT_BLOCK_PTR_FOR_FN(cfun)) {
525 perturb_local_entropy(bb, local_entropy);
526 bb = bb->next_bb;
527 }
528
529 /* 4. mix local entropy into the global entropy variable */
530 perturb_latent_entropy(local_entropy);
531 return 0;
532}
533
534static void latent_entropy_start_unit(void *gcc_data __unused,
535 void *user_data __unused)
536{
537 tree type, id;
538 int quals;
539
540 seed = get_random_seed(false);
541
542 if (in_lto_p)
543 return;
544
545 /* extern volatile unsigned long latent_entropy */
546 quals = TYPE_QUALS(long_unsigned_type_node) | TYPE_QUAL_VOLATILE;
547 type = build_qualified_type(long_unsigned_type_node, quals);
548 id = get_identifier("latent_entropy");
549 latent_entropy_decl = build_decl(UNKNOWN_LOCATION, VAR_DECL, id, type);
550
551 TREE_STATIC(latent_entropy_decl) = 1;
552 TREE_PUBLIC(latent_entropy_decl) = 1;
553 TREE_USED(latent_entropy_decl) = 1;
554 DECL_PRESERVE_P(latent_entropy_decl) = 1;
555 TREE_THIS_VOLATILE(latent_entropy_decl) = 1;
556 DECL_EXTERNAL(latent_entropy_decl) = 1;
557 DECL_ARTIFICIAL(latent_entropy_decl) = 1;
558 lang_hooks.decls.pushdecl(latent_entropy_decl);
559}
560
561#define PASS_NAME latent_entropy
562#define PROPERTIES_REQUIRED PROP_gimple_leh | PROP_cfg
563#define TODO_FLAGS_FINISH TODO_verify_ssa | TODO_verify_stmts | TODO_dump_func \
564 | TODO_update_ssa
565#include "gcc-generate-gimple-pass.h"
566
567__visible int plugin_init(struct plugin_name_args *plugin_info,
568 struct plugin_gcc_version *version)
569{
570 bool enabled = true;
571 const char * const plugin_name = plugin_info->base_name;
572 const int argc = plugin_info->argc;
573 const struct plugin_argument * const argv = plugin_info->argv;
574 int i;
575
576 static const struct ggc_root_tab gt_ggc_r_gt_latent_entropy[] = {
577 {
578 .base = &latent_entropy_decl,
579 .nelt = 1,
580 .stride = sizeof(latent_entropy_decl),
581 .cb = >_ggc_mx_tree_node,
582 .pchw = >_pch_nx_tree_node
583 },
584 LAST_GGC_ROOT_TAB
585 };
586
587 PASS_INFO(latent_entropy, "optimized", 1, PASS_POS_INSERT_BEFORE);
588
589 if (!plugin_default_version_check(version, &gcc_version)) {
590 error(G_("incompatible gcc/plugin versions"));
591 return 1;
592 }
593
594 for (i = 0; i < argc; ++i) {
595 if (!(strcmp(argv[i].key, "disable"))) {
596 enabled = false;
597 continue;
598 }
599 error(G_("unknown option '-fplugin-arg-%s-%s'"), plugin_name, argv[i].key);
600 }
601
602 register_callback(plugin_name, PLUGIN_INFO, NULL,
603 &latent_entropy_plugin_info);
604 if (enabled) {
605 register_callback(plugin_name, PLUGIN_START_UNIT,
606 &latent_entropy_start_unit, NULL);
607 register_callback(plugin_name, PLUGIN_REGISTER_GGC_ROOTS,
608 NULL, (void *)>_ggc_r_gt_latent_entropy);
609 register_callback(plugin_name, PLUGIN_PASS_MANAGER_SETUP, NULL,
610 &latent_entropy_pass_info);
611 }
612 register_callback(plugin_name, PLUGIN_ATTRIBUTES, register_attributes,
613 NULL);
614
615 return 0;
616}