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