scripts/gcc-plugins/latent_entropy_plugin.c

   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 }