gcc/asan.c

   1 /* AddressSanitizer, a fast memory error detector.
   2    Copyright (C) 2012 Free Software Foundation, Inc.
   3    Contributed by Kostya Serebryany <kcc@google.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "gimple.h"
  26 #include "tree-iterator.h"
  27 #include "tree-flow.h"
  28 #include "tree-pass.h"
  29 #include "asan.h"
  30 #include "gimple-pretty-print.h"
  31 #include "target.h"
  32
  33 /*
  34  AddressSanitizer finds out-of-bounds and use-after-free bugs
  35  with <2x slowdown on average.
  36
  37  The tool consists of two parts:
  38  instrumentation module (this file) and a run-time library.
  39  The instrumentation module adds a run-time check before every memory insn.
  40    For a 8- or 16- byte load accessing address X:
  41      ShadowAddr = (X >> 3) + Offset
  42      ShadowValue = *(char*)ShadowAddr;  // *(short*) for 16-byte access.
  43      if (ShadowValue)
  44        __asan_report_load8(X);
  45    For a load of N bytes (N=1, 2 or 4) from address X:
  46      ShadowAddr = (X >> 3) + Offset
  47      ShadowValue = *(char*)ShadowAddr;
  48      if (ShadowValue)
  49        if ((X & 7) + N - 1 > ShadowValue)
  50          __asan_report_loadN(X);
  51  Stores are instrumented similarly, but using __asan_report_storeN functions.
  52  A call too __asan_init() is inserted to the list of module CTORs.
  53
  54  The run-time library redefines malloc (so that redzone are inserted around
  55  the allocated memory) and free (so that reuse of free-ed memory is delayed),
  56  provides __asan_report* and __asan_init functions.
  57
  58  Read more:
  59  http://code.google.com/p/address-sanitizer/wiki/AddressSanitizerAlgorithm
  60
  61  Future work:
  62  The current implementation supports only detection of out-of-bounds and
  63  use-after-free bugs in heap.
  64  In order to support out-of-bounds for stack and globals we will need
  65  to create redzones for stack and global object and poison them.
  66 */
  67
  68 /* Pointer types to 1 resp. 2 byte integers in shadow memory.  A separate
  69    alias set is used for all shadow memory accesses.  */
  70 static GTY(()) tree shadow_ptr_types[2];
  71
  72 /* Construct a function tree for __asan_report_{load,store}{1,2,4,8,16}.
  73    IS_STORE is either 1 (for a store) or 0 (for a load).
  74    SIZE_IN_BYTES is one of 1, 2, 4, 8, 16.  */
  75
  76 static tree
  77 report_error_func (bool is_store, int size_in_bytes)
  78 {
  79   tree fn_type;
  80   tree def;
  81   char name[100];
  82
  83   sprintf (name, "__asan_report_%s%d",
  84            is_store ? "store" : "load", size_in_bytes);
  85   fn_type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
  86   def = build_fn_decl (name, fn_type);
  87   TREE_NOTHROW (def) = 1;
  88   TREE_THIS_VOLATILE (def) = 1;  /* Attribute noreturn. Surprise!  */
  89   DECL_ATTRIBUTES (def) = tree_cons (get_identifier ("leaf"),
  90                                      NULL, DECL_ATTRIBUTES (def));
  91   DECL_ASSEMBLER_NAME (def);
  92   return def;
  93 }
  94
  95 /* Construct a function tree for __asan_init().  */
  96
  97 static tree
  98 asan_init_func (void)
  99 {
 100   tree fn_type;
 101   tree def;
 102
 103   fn_type = build_function_type_list (void_type_node, NULL_TREE);
 104   def = build_fn_decl ("__asan_init", fn_type);
 105   TREE_NOTHROW (def) = 1;
 106   DECL_ASSEMBLER_NAME (def);
 107   return def;
 108 }
 109
 110
 111 #define PROB_VERY_UNLIKELY      (REG_BR_PROB_BASE / 2000 - 1)
 112 #define PROB_ALWAYS             (REG_BR_PROB_BASE)
 113
 114 /* Instrument the memory access instruction BASE.
 115    Insert new statements before ITER.
 116    LOCATION is source code location.
 117    IS_STORE is either 1 (for a store) or 0 (for a load).
 118    SIZE_IN_BYTES is one of 1, 2, 4, 8, 16.  */
 119
 120 static void
 121 build_check_stmt (tree base,
 122                   gimple_stmt_iterator *iter,
 123                   location_t location, bool is_store, int size_in_bytes)
 124 {
 125   gimple_stmt_iterator gsi;
 126   basic_block cond_bb, then_bb, else_bb;
 127   edge e;
 128   tree t, base_addr, shadow;
 129   gimple g;
 130   tree shadow_ptr_type = shadow_ptr_types[size_in_bytes == 16 ? 1 : 0];
 131   tree shadow_type = TREE_TYPE (shadow_ptr_type);
 132   tree uintptr_type
 133     = build_nonstandard_integer_type (TYPE_PRECISION (TREE_TYPE (base)), 1);
 134
 135   /* We first need to split the current basic block, and start altering
 136      the CFG.  This allows us to insert the statements we're about to
 137      construct into the right basic blocks.  */
 138
 139   cond_bb = gimple_bb (gsi_stmt (*iter));
 140   gsi = *iter;
 141   gsi_prev (&gsi);
 142   if (!gsi_end_p (gsi))
 143     e = split_block (cond_bb, gsi_stmt (gsi));
 144   else
 145     e = split_block_after_labels (cond_bb);
 146   cond_bb = e->src;
 147   else_bb = e->dest;
 148
 149   /* A recap at this point: else_bb is the basic block at whose head
 150      is the gimple statement for which this check expression is being
 151      built.  cond_bb is the (possibly new, synthetic) basic block the
 152      end of which will contain the cache-lookup code, and a
 153      conditional that jumps to the cache-miss code or, much more
 154      likely, over to else_bb.  */
 155
 156   /* Create the bb that contains the crash block.  */
 157   then_bb = create_empty_bb (cond_bb);
 158   e = make_edge (cond_bb, then_bb, EDGE_TRUE_VALUE);
 159   e->probability = PROB_VERY_UNLIKELY;
 160   make_single_succ_edge (then_bb, else_bb, EDGE_FALLTHRU);
 161
 162   /* Mark the pseudo-fallthrough edge from cond_bb to else_bb.  */
 163   e = find_edge (cond_bb, else_bb);
 164   e->flags = EDGE_FALSE_VALUE;
 165   e->count = cond_bb->count;
 166   e->probability = PROB_ALWAYS - PROB_VERY_UNLIKELY;
 167
 168   /* Update dominance info.  Note that bb_join's data was
 169      updated by split_block.  */
 170   if (dom_info_available_p (CDI_DOMINATORS))
 171     {
 172       set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb);
 173       set_immediate_dominator (CDI_DOMINATORS, else_bb, cond_bb);
 174     }
 175
 176   base = unshare_expr (base);
 177
 178   gsi = gsi_last_bb (cond_bb);
 179   g = gimple_build_assign_with_ops (TREE_CODE (base),
 180                                     make_ssa_name (TREE_TYPE (base), NULL),
 181                                     base, NULL_TREE);
 182   gimple_set_location (g, location);
 183   gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 184
 185   g = gimple_build_assign_with_ops (NOP_EXPR,
 186                                     make_ssa_name (uintptr_type, NULL),
 187                                     gimple_assign_lhs (g), NULL_TREE);
 188   gimple_set_location (g, location);
 189   gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 190   base_addr = gimple_assign_lhs (g);
 191
 192   /* Build
 193      (base_addr >> ASAN_SHADOW_SHIFT) + targetm.asan_shadow_offset ().  */
 194
 195   t = build_int_cst (uintptr_type, ASAN_SHADOW_SHIFT);
 196   g = gimple_build_assign_with_ops (RSHIFT_EXPR,
 197                                     make_ssa_name (uintptr_type, NULL),
 198                                     base_addr, t);
 199   gimple_set_location (g, location);
 200   gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 201
 202   t = build_int_cst (uintptr_type, targetm.asan_shadow_offset ());
 203   g = gimple_build_assign_with_ops (PLUS_EXPR,
 204                                     make_ssa_name (uintptr_type, NULL),
 205                                     gimple_assign_lhs (g), t);
 206   gimple_set_location (g, location);
 207   gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 208
 209   g = gimple_build_assign_with_ops (NOP_EXPR,
 210                                     make_ssa_name (shadow_ptr_type, NULL),
 211                                     gimple_assign_lhs (g), NULL_TREE);
 212   gimple_set_location (g, location);
 213   gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 214
 215   t = build2 (MEM_REF, shadow_type, gimple_assign_lhs (g),
 216               build_int_cst (shadow_ptr_type, 0));
 217   g = gimple_build_assign_with_ops (MEM_REF,
 218                                     make_ssa_name (shadow_type, NULL),
 219                                     t, NULL_TREE);
 220   gimple_set_location (g, location);
 221   gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 222   shadow = gimple_assign_lhs (g);
 223
 224   if (size_in_bytes < 8)
 225     {
 226       /* Slow path for 1, 2 and 4 byte accesses.
 227          Test (shadow != 0)
 228               & ((base_addr & 7) + (size_in_bytes - 1)) >= shadow).  */
 229       g = gimple_build_assign_with_ops (NE_EXPR,
 230                                         make_ssa_name (boolean_type_node,
 231                                                        NULL),
 232                                         shadow,
 233                                         build_int_cst (shadow_type, 0));
 234       gimple_set_location (g, location);
 235       gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 236       t = gimple_assign_lhs (g);
 237
 238       g = gimple_build_assign_with_ops (BIT_AND_EXPR,
 239                                         make_ssa_name (uintptr_type,
 240                                                        NULL),
 241                                         base_addr,
 242                                         build_int_cst (uintptr_type, 7));
 243       gimple_set_location (g, location);
 244       gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 245
 246       g = gimple_build_assign_with_ops (NOP_EXPR,
 247                                         make_ssa_name (shadow_type,
 248                                                        NULL),
 249                                         gimple_assign_lhs (g), NULL_TREE);
 250       gimple_set_location (g, location);
 251       gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 252
 253       if (size_in_bytes > 1)
 254         {
 255           g = gimple_build_assign_with_ops (PLUS_EXPR,
 256                                             make_ssa_name (shadow_type,
 257                                                            NULL),
 258                                             gimple_assign_lhs (g),
 259                                             build_int_cst (shadow_type,
 260                                                            size_in_bytes - 1));
 261           gimple_set_location (g, location);
 262           gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 263         }
 264
 265       g = gimple_build_assign_with_ops (GE_EXPR,
 266                                         make_ssa_name (boolean_type_node,
 267                                                        NULL),
 268                                         gimple_assign_lhs (g),
 269                                         shadow);
 270       gimple_set_location (g, location);
 271       gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 272
 273       g = gimple_build_assign_with_ops (BIT_AND_EXPR,
 274                                         make_ssa_name (boolean_type_node,
 275                                                        NULL),
 276                                         t, gimple_assign_lhs (g));
 277       gimple_set_location (g, location);
 278       gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 279       t = gimple_assign_lhs (g);
 280     }
 281   else
 282     t = shadow;
 283
 284   g = gimple_build_cond (NE_EXPR, t, build_int_cst (TREE_TYPE (t), 0),
 285                          NULL_TREE, NULL_TREE);
 286   gimple_set_location (g, location);
 287   gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 288
 289   /* Generate call to the run-time library (e.g. __asan_report_load8).  */
 290   gsi = gsi_start_bb (then_bb);
 291   g = gimple_build_call (report_error_func (is_store, size_in_bytes),
 292                          1, base_addr);
 293   gimple_set_location (g, location);
 294   gsi_insert_after (&gsi, g, GSI_NEW_STMT);
 295
 296   *iter = gsi_start_bb (else_bb);
 297 }
 298
 299 /* If T represents a memory access, add instrumentation code before ITER.
 300    LOCATION is source code location.
 301    IS_STORE is either 1 (for a store) or 0 (for a load).  */
 302
 303 static void
 304 instrument_derefs (gimple_stmt_iterator *iter, tree t,
 305                   location_t location, bool is_store)
 306 {
 307   tree type, base;
 308   HOST_WIDE_INT size_in_bytes;
 309
 310   type = TREE_TYPE (t);
 311   switch (TREE_CODE (t))
 312     {
 313     case ARRAY_REF:
 314     case COMPONENT_REF:
 315     case INDIRECT_REF:
 316     case MEM_REF:
 317       break;
 318     default:
 319       return;
 320     }
 321
 322   size_in_bytes = int_size_in_bytes (type);
 323   if ((size_in_bytes & (size_in_bytes - 1)) != 0
 324       || (unsigned HOST_WIDE_INT) size_in_bytes - 1 >= 16)
 325     return;
 326
 327   /* For now just avoid instrumenting bit field acceses.
 328      Fixing it is doable, but expected to be messy.  */
 329
 330   HOST_WIDE_INT bitsize, bitpos;
 331   tree offset;
 332   enum machine_mode mode;
 333   int volatilep = 0, unsignedp = 0;
 334   get_inner_reference (t, &bitsize, &bitpos, &offset,
 335                        &mode, &unsignedp, &volatilep, false);
 336   if (bitpos != 0 || bitsize != size_in_bytes * BITS_PER_UNIT)
 337     return;
 338
 339   base = build_fold_addr_expr (t);
 340   build_check_stmt (base, iter, location, is_store, size_in_bytes);
 341 }
 342
 343 /* asan: this looks too complex. Can this be done simpler? */
 344 /* Transform
 345    1) Memory references.
 346    2) BUILTIN_ALLOCA calls.
 347 */
 348
 349 static void
 350 transform_statements (void)
 351 {
 352   basic_block bb;
 353   gimple_stmt_iterator i;
 354   int saved_last_basic_block = last_basic_block;
 355
 356   FOR_EACH_BB (bb)
 357     {
 358       if (bb->index >= saved_last_basic_block) continue;
 359       for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
 360         {
 361           gimple s = gsi_stmt (i);
 362           if (!gimple_assign_single_p (s))
 363             continue;
 364           instrument_derefs (&i, gimple_assign_lhs (s),
 365                              gimple_location (s), true);
 366           instrument_derefs (&i, gimple_assign_rhs1 (s),
 367                              gimple_location (s), false);
 368         }
 369     }
 370 }
 371
 372 /* Module-level instrumentation.
 373    - Insert __asan_init() into the list of CTORs.
 374    - TODO: insert redzones around globals.
 375  */
 376
 377 void
 378 asan_finish_file (void)
 379 {
 380   tree ctor_statements = NULL_TREE;
 381   append_to_statement_list (build_call_expr (asan_init_func (), 0),
 382                             &ctor_statements);
 383   cgraph_build_static_cdtor ('I', ctor_statements,
 384                              MAX_RESERVED_INIT_PRIORITY - 1);
 385 }
 386
 387 /* Initialize shadow_ptr_types array.  */
 388
 389 static void
 390 asan_init_shadow_ptr_types (void)
 391 {
 392   alias_set_type set = new_alias_set ();
 393   shadow_ptr_types[0] = build_distinct_type_copy (signed_char_type_node);
 394   TYPE_ALIAS_SET (shadow_ptr_types[0]) = set;
 395   shadow_ptr_types[0] = build_pointer_type (shadow_ptr_types[0]);
 396   shadow_ptr_types[1] = build_distinct_type_copy (short_integer_type_node);
 397   TYPE_ALIAS_SET (shadow_ptr_types[1]) = set;
 398   shadow_ptr_types[1] = build_pointer_type (shadow_ptr_types[1]);
 399 }
 400
 401 /* Instrument the current function.  */
 402
 403 static unsigned int
 404 asan_instrument (void)
 405 {
 406   if (shadow_ptr_types[0] == NULL_TREE)
 407     asan_init_shadow_ptr_types ();
 408   transform_statements ();
 409   return 0;
 410 }
 411
 412 static bool
 413 gate_asan (void)
 414 {
 415   return flag_asan != 0;
 416 }
 417
 418 struct gimple_opt_pass pass_asan =
 419 {
 420  {
 421   GIMPLE_PASS,
 422   "asan",                               /* name  */
 423   OPTGROUP_NONE,                        /* optinfo_flags */
 424   gate_asan,                            /* gate  */
 425   asan_instrument,                      /* execute  */
 426   NULL,                                 /* sub  */
 427   NULL,                                 /* next  */
 428   0,                                    /* static_pass_number  */
 429   TV_NONE,                              /* tv_id  */
 430   PROP_ssa | PROP_cfg | PROP_gimple_leh,/* properties_required  */
 431   0,                                    /* properties_provided  */
 432   0,                                    /* properties_destroyed  */
 433   0,                                    /* todo_flags_start  */
 434   TODO_verify_flow | TODO_verify_stmts
 435   | TODO_update_ssa                     /* todo_flags_finish  */
 436  }
 437 };
 438
 439 static bool
 440 gate_asan_O0 (void)
 441 {
 442   return flag_asan != 0 && !optimize;
 443 }
 444
 445 struct gimple_opt_pass pass_asan_O0 =
 446 {
 447  {
 448   GIMPLE_PASS,
 449   "asan0",                              /* name  */
 450   OPTGROUP_NONE,                        /* optinfo_flags */
 451   gate_asan_O0,                         /* gate  */
 452   asan_instrument,                      /* execute  */
 453   NULL,                                 /* sub  */
 454   NULL,                                 /* next  */
 455   0,                                    /* static_pass_number  */
 456   TV_NONE,                              /* tv_id  */
 457   PROP_ssa | PROP_cfg | PROP_gimple_leh,/* properties_required  */
 458   0,                                    /* properties_provided  */
 459   0,                                    /* properties_destroyed  */
 460   0,                                    /* todo_flags_start  */
 461   TODO_verify_flow | TODO_verify_stmts
 462   | TODO_update_ssa                     /* todo_flags_finish  */
 463  }
 464 };
 465
 466 #include "gt-asan.h"