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