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