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 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 = >_ggc_mx_tree_node, 592 .pchw = >_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 *)>_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