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