1 #include <asr/ASRPass.h> 2 #include <magic_common.h> 3 #include <magic/support/MagicUtil.h> 4 #include <llvm/Transforms/Utils/BasicBlockUtils.h> 5 6 #define MAGIC_IS_MAGIC_FUNC(M, F) (!StringRef((F)->getSection()).compare(MAGIC_STATIC_FUNCTIONS_SECTION)) 7 8 using namespace llvm; 9 10 11 // command-line arguments 12 13 static cl::opt<int> 14 seed("asr-seed", 15 cl::desc("Random seed integer value for ASRPass. '0' will use current time as seed"), 16 cl::init(DEFAULT_SEED), cl::NotHidden, cl::ValueRequired); 17 18 19 static cl::opt<int> 20 gv_max_offset("asr-gv-max-offset", 21 cl::desc(""), 22 cl::init(GV_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired); 23 24 static cl::opt<int> 25 gv_max_padding("asr-gv-max-padding", 26 cl::desc(""), 27 cl::init(GV_DEFAULT_MAX_PADDING), cl::NotHidden, cl::ValueRequired); 28 29 static cl::opt<int> 30 gv_do_permutate("asr-gv-do-permutate", 31 cl::desc(""), 32 cl::init(GV_DEFAULT_DO_PERMUTATE), cl::NotHidden, cl::ValueRequired); 33 34 35 static cl::opt<int> 36 func_max_offset("asr-func-max-offset", 37 cl::desc(""), 38 cl::init(FUNC_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired); 39 40 static cl::opt<int> 41 func_max_padding("asr-func-max-padding", 42 cl::desc(""), 43 cl::init(FUNC_DEFAULT_MAX_PADDING), cl::NotHidden, cl::ValueRequired); 44 45 static cl::opt<int> 46 func_max_bb_shift("asr-func-max-bb-shift", 47 cl::desc(""), 48 cl::init(FUNC_DEFAULT_MAX_BB_SHIFT), cl::NotHidden, cl::ValueRequired); 49 50 static cl::opt<int> 51 func_do_permutate("asr-func-do-permutate", 52 cl::desc(""), 53 cl::init(FUNC_DEFAULT_DO_PERMUTATE), cl::NotHidden, cl::ValueRequired); 54 55 56 static cl::opt<int> 57 stack_do_offset("asr-stack-do-offset", 58 cl::desc(""), 59 cl::init(STACK_DEFAULT_DO_OFFSET), cl::NotHidden, cl::ValueRequired); 60 61 static cl::opt<int> 62 stack_max_offset("asr-stack-max-offset", 63 cl::desc(""), 64 cl::init(STACK_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired); 65 66 67 static cl::opt<int> 68 stackframe_do_offset("asr-stackframe-do-offset", 69 cl::desc(""), 70 cl::init(STACKFRAME_DEFAULT_DO_OFFSET), cl::NotHidden, cl::ValueRequired); 71 72 static cl::opt<int> 73 stackframe_max_offset("asr-stackframe-max-offset", 74 cl::desc(""), 75 cl::init(STACKFRAME_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired); 76 77 static cl::opt<int> 78 stackframe_max_padding("asr-stackframe-max-padding", 79 cl::desc(""), 80 cl::init(STACKFRAME_DEFAULT_MAX_PADDING), cl::NotHidden, cl::ValueRequired); 81 82 static cl::opt<int> 83 stackframe_do_permutate("asr-stackframe-do-permutate", 84 cl::desc(""), 85 cl::init(STACKFRAME_DEFAULT_DO_PERMUTATE), cl::NotHidden, cl::ValueRequired); 86 87 static cl::opt<int> 88 stackframe_static_padding("asr-stackframe-static-padding", 89 cl::desc(""), 90 cl::init(STACKFRAME_DEFAULT_STATIC_PADDING), cl::NotHidden, cl::ValueRequired); 91 92 static cl::opt<int> 93 stackframe_caller_padding("asr-stackframe-caller-padding", 94 cl::desc(""), 95 cl::init(STACKFRAME_DEFAULT_CALLER_PADDING), cl::NotHidden, cl::ValueRequired); 96 97 static cl::opt<int> 98 heap_map_do_permutate("asr-heap-map-do-permutate", 99 cl::desc(""), 100 cl::init(HEAP_MAP_DEFAULT_DO_PERMUTATE), cl::NotHidden, cl::ValueRequired); 101 102 103 static cl::opt<int> 104 heap_max_offset("asr-heap-max-offset", 105 cl::desc(""), 106 cl::init(HEAP_DEFAULT_MAX_OFFSET), cl::NotHidden, cl::ValueRequired); 107 108 static cl::opt<int> 109 heap_max_padding("asr-heap-max-padding", 110 cl::desc(""), 111 cl::init(HEAP_DEFAULT_MAX_PADDING), cl::NotHidden, cl::ValueRequired); 112 113 114 static cl::opt<int> 115 map_max_offset_pages("asr-map-max-offset-pages", 116 cl::desc(""), 117 cl::init(MAP_DEFAULT_MAX_OFFSET_PAGES), cl::NotHidden, cl::ValueRequired); 118 119 static cl::opt<int> 120 map_max_padding_pages("asr-map-max-padding-pages", 121 cl::desc(""), 122 cl::init(MAP_DEFAULT_MAX_PADDING_PAGES), cl::NotHidden, cl::ValueRequired); 123 124 125 #define __X(P) #P 126 std::string magicMemFuncNames[] = { MAGIC_MEM_FUNC_NAMES }; 127 #undef __X 128 129 namespace llvm { 130 131 PASS_COMMON_INIT_ONCE(); 132 133 //===----------------------------------------------------------------------===// 134 // Constructors, destructor, and operators 135 //===----------------------------------------------------------------------===// 136 137 ASRPass::ASRPass() : ModulePass(ID) {} 138 //===----------------------------------------------------------------------===// 139 // Public methods 140 //===----------------------------------------------------------------------===// 141 142 void fillPermutationGenerator(std::vector<unsigned> &permutationGenerator){ 143 // This function returns a list of indices. In order to create a permutation of a list of elements, for each index, remove that element and place it at the end of the list. 144 unsigned size = permutationGenerator.size(); 145 for (unsigned i = 0; i < size; ++i) { 146 unsigned j = rand() % (size - i); 147 permutationGenerator[i] = j; 148 } 149 } 150 151 Function* getCalledFunctionFromCS(const CallSite &CS) { 152 assert(CS.getInstruction()); 153 Function *function = CS.getCalledFunction(); 154 if(function) { 155 return function; 156 } 157 158 //handle the weird case of bitcasted function call 159 ConstantExpr *CE = dyn_cast<ConstantExpr>(CS.getCalledValue()); 160 if(!CE) { 161 return NULL; 162 } 163 assert(CE && CE->getOpcode() == Instruction::BitCast && "Bitcast expected, something else found!"); 164 function = dyn_cast<Function>(CE->getOperand(0)); 165 assert(function); 166 167 return function; 168 } 169 170 #define ADVANCE_ITERATOR(IT, N_POS) for(unsigned __adv_it_count=0; __adv_it_count< N_POS; __adv_it_count++){ IT++;} 171 172 GlobalVariable *create_padding_gv(Module &M, GlobalVariable *InsertBefore, int n_bytes){ 173 174 ArrayType* ArrayTy = ArrayType::get(IntegerType::get(M.getContext(), 8), n_bytes); 175 176 GlobalVariable* padding_char_arr = new GlobalVariable(/*Module=*/M, 177 /*Type=*/ArrayTy, 178 /*isConstant=*/false, 179 /*Linkage=*/GlobalValue::InternalLinkage, 180 /*Initializer=*/ConstantAggregateZero::get(ArrayTy), 181 /*Name=*/"magic_asr_padding_gv", 182 /*InsertBefore=*/InsertBefore); 183 padding_char_arr->setAlignment(1); 184 padding_char_arr->setSection(InsertBefore->getSection()); 185 return padding_char_arr; 186 187 } 188 189 AllocaInst *create_padding_lv(Module &M, Instruction *InsertBefore, int n_bytes){ 190 191 ArrayType* ArrayTy = ArrayType::get(IntegerType::get(M.getContext(), 8), n_bytes); 192 AllocaInst* ptr_x = new AllocaInst(ArrayTy, "magic_asr_padding_lv", InsertBefore); 193 ptr_x->setAlignment(16); 194 195 /* Seems not to be necessary 196 197 ConstantInt* const_int64_0 = ConstantInt::get(M.getContext(), APInt(64, StringRef("0"), 10)); 198 ConstantInt* const_int8_0 = ConstantInt::get(M.getContext(), APInt(8, StringRef("97"), 10)); 199 200 std::vector<Value*> ptr_indices; 201 ptr_indices.push_back(const_int64_0); 202 ptr_indices.push_back(const_int64_0); 203 204 Instruction* ptr_8 = GetElementPtrInst::Create(ptr_x, ptr_indices.begin(), ptr_indices.end(), "", ptr_x->getParent()); 205 ptr_8->removeFromParent(); 206 ptr_8->insertAfter(ptr_x); 207 208 StoreInst* void_9 = new StoreInst(const_int8_0, ptr_8, true, ptr_x->getParent()); 209 void_9->setAlignment(16); 210 void_9->removeFromParent(); 211 void_9->insertAfter(ptr_8); 212 213 */ 214 215 return ptr_x; 216 217 } 218 219 Function *create_padding_func(Module &M, int n_ops){ 220 /* Places a padding function at the end of the function list */ 221 222 std::vector<TYPECONST Type*>FuncTy_0_args; 223 TYPECONST FunctionType* FuncTy_0 = FunctionType::get(Type::getVoidTy(M.getContext()), FuncTy_0_args, false); 224 225 Function* func_padding_func = Function::Create(FuncTy_0, GlobalValue::ExternalLinkage, "magic_asr_padding_func", &M); 226 func_padding_func->setCallingConv(CallingConv::C); 227 BasicBlock* bb = BasicBlock::Create(M.getContext(), "",func_padding_func,0); 228 229 ConstantInt* const_int32_0 = ConstantInt::get(M.getContext(), APInt(32, StringRef("0"), 10)); 230 ConstantInt* const_int32_1 = ConstantInt::get(M.getContext(), APInt(32, StringRef("1"), 10)); 231 232 AllocaInst* ptr_x = new AllocaInst(IntegerType::get(M.getContext(), 32), "x", bb); 233 ptr_x->setAlignment(4); 234 235 StoreInst* void_1 = new StoreInst(const_int32_0, ptr_x, true, bb); 236 void_1->setAlignment(4); 237 238 for(int i=0; i< n_ops; i++){ 239 LoadInst* load_x = new LoadInst(ptr_x, "", true, bb); 240 load_x->setAlignment(4); 241 242 BinaryOperator* add_x = BinaryOperator::Create(Instruction::Add, load_x, const_int32_1, "", bb); 243 244 StoreInst* void_2 = new StoreInst(add_x, ptr_x, true, bb); 245 void_2->setAlignment(4); 246 } 247 248 ReturnInst::Create(M.getContext(), bb); 249 250 return func_padding_func; 251 } 252 253 StringRef getStringRefFromInt(int i){ 254 std::stringstream stm; 255 stm << i; 256 return StringRef(*new std::string(stm.str())); 257 } 258 259 bool ASRPass::runOnModule(Module &M) { 260 261 Module::GlobalListType &globalList = M.getGlobalList(); 262 Module::FunctionListType &functionList = M.getFunctionList(); 263 int runtime_seed = seed; 264 265 Function *magicEntryPointFunc = M.getFunction(MAGIC_ENTRY_POINT); 266 if( !magicEntryPointFunc ){ 267 //if no valid entry point, we are not compiling a valid program, skip pass 268 return false; 269 } 270 271 Function *magicInitFunc = M.getFunction(MAGIC_INIT_FUNC_NAME); 272 if( !magicInitFunc ){ 273 outs() << "Error: no " << MAGIC_INIT_FUNC_NAME << "() found"; 274 exit(1); 275 } 276 277 { 278 // get random seed number, or use the current time if the seed number is set to 0. 279 if(!seed){ 280 seed = time(NULL); 281 } 282 srand(seed); 283 284 }{ 285 286 /* Randomly offset and permutate list of global variables, and insert random padding between neighbouring global variables */ 287 288 std::vector<unsigned> pg(globalList.size()); 289 fillPermutationGenerator(pg); 290 291 for(unsigned i=0; i < pg.size(); i++){ 292 Module::global_iterator it = globalList.begin(); 293 // get the next random global variable 294 ADVANCE_ITERATOR(it, pg[i]); 295 // skip certain variables 296 if(it->getName().startswith("llvm.") 297 || it->getLinkage() == GlobalValue::ExternalWeakLinkage){ 298 continue; 299 } 300 if(it->getLinkage() != GlobalValue::ExternalLinkage && it->getName().compare("environ")){ 301 // This prevents most public global variables (common linkage, but not external linkage) to be kept in the same order 302 it->setLinkage(GlobalValue::InternalLinkage); 303 } 304 if(gv_do_permutate){ 305 // randomize the order of variables, by removing the global variable, and putting it at the end of globalList 306 GlobalVariable *gv = globalList.remove(it); 307 globalList.push_back(gv); 308 it = --globalList.end(); 309 } 310 // put a padding variable between each two adjacent global variables, and place a big offset before the first global variable 311 int max_padding = i == 0 ? gv_max_offset : gv_max_padding; 312 if(max_padding > 0){ 313 create_padding_gv(M, it, (rand () % max_padding) + 1); 314 } 315 } 316 317 }{ 318 319 /* Randomly offset and permutate function list, and insert random padding between neighbouring functions. */ 320 321 std::vector<unsigned> pg(functionList.size()); 322 fillPermutationGenerator(pg); 323 324 for(unsigned i=0; i < pg.size(); i++){ 325 Module::iterator it = functionList.begin(); 326 if(func_do_permutate){ 327 /* randomize the order of functions, just like we did with the global variables if permutions is disabled, we end up with the same order of functions */ 328 ADVANCE_ITERATOR(it, pg[i]); 329 } 330 Function *F = functionList.remove(it); 331 functionList.push_back(F); 332 /* place a padding function at the end of the function list, behind the current function */ 333 int max_padding = i == 0 ? func_max_offset : func_max_padding; 334 if(max_padding > 0){ 335 create_padding_func(M, (rand () % (max_padding/2)) + (max_padding/2)); 336 } 337 } 338 339 }{ 340 341 342 /* permutate and pad local function variables, and create dynamically randomized stack and stack frame offsets */ 343 344 for (Module::iterator it = functionList.begin(); it != functionList.end(); ++it) { 345 Function *F = it; 346 347 /* skip certain functions */ 348 if(F->getBasicBlockList().size() == 0){ 349 continue; 350 } 351 if(MAGIC_IS_MAGIC_FUNC(M, F)){ 352 continue; 353 } 354 if(!F->getName().compare("rand")){ 355 continue; 356 } 357 358 359 /* find all allocation instructions in order to pad them. */ 360 361 /* Helper vectors to store all alloca instructions temporarily. 362 * Make two collections, depending on whether the address of the variable is taken and used as a pointer. 363 * (Because pointer dereferencing, buffer overflow, etc. add extra risks to those variables that have their addresses taken) 364 * We order the allocation instructions as follows: 365 * - First, we allocate the ones that don't have their address taken, only permutated. 366 * - Then, we allocate an stack frame offset (dynamically randomly sized). 367 * - After the stack frame offset, we allocate those that have their address taken, with permutation and padding. 368 * Because the majority doesn't have its address taken, most variables are allocated in the first basic block, before the stack frame offset allocation. 369 * This gives the extra advantages that those allocations are folded into the prolog/epilog code by the code generator, for extra performance. 370 * (See AllocaInst::isStaticAlloca() in llvm/Instructions.h) 371 * */ 372 std::vector<Instruction *> allocaAddressTaken, allocaNoAddressTaken; 373 374 /* Only the first basic block contains alloca instructions */ 375 BasicBlock *BB = F->getBasicBlockList().begin(); 376 377 /* with each iteration, one of these integers will be incremented/decremented */ 378 unsigned bb_size = BB->getInstList().size(); 379 unsigned pos = 0; 380 while(pos < bb_size){ 381 382 /* check if instruction at position <pos> is an allocation instruction. 383 * If, so remove and put in one of the helper vectors 384 * */ 385 386 BasicBlock::iterator it = BB->getInstList().begin(); 387 /* move to current position in instruction list */ 388 ADVANCE_ITERATOR(it, pos); 389 Instruction *inst = &(*it); 390 if (AllocaInst *allocaInst = dyn_cast<AllocaInst>(inst)){ 391 /* this is an allocation instruction. insert it at the front of of the right helper vector 392 * (last found allocation instruction will be at the front), and remove it from the basic block. 393 * */ 394 int hasAddressTaken = 0; 395 for (Value::user_iterator UI = allocaInst->user_begin(), E = allocaInst->user_end(); UI != E; ++UI) { 396 397 /* Loop through all the Uses of this allocation function. */ 398 399 User *U = *UI; 400 if(dyn_cast<LoadInst>(U) || dyn_cast<StoreInst>(U)){ 401 /* This is a load or store instruction, which does not 402 * indicate that a pointer of this variable is generated 403 * */ 404 continue; 405 }else if(CallInst *cInst = dyn_cast<CallInst>(U)){ 406 if(cInst->getCalledFunction() && MAGIC_IS_MAGIC_FUNC(M, cInst->getCalledFunction())){ 407 /* This is a function call instruction, but this 408 * concerns a magic library function, so it does not count as a generated pointer. 409 * Any other functions calls would have set hasAddressTaken to 1 */ 410 continue; 411 } 412 } 413 /* This instruction will (likely) create a pointer, because it is not a load, store or magic-function-call instruction */ 414 hasAddressTaken = 1; 415 break; 416 } 417 418 /* Put the alloca instruction in the right helper vector, and remove from the basic block. */ 419 if(hasAddressTaken){ 420 allocaAddressTaken.insert(allocaAddressTaken.begin(), it); 421 }else{ 422 allocaNoAddressTaken.insert(allocaNoAddressTaken.begin(), it); 423 } 424 it->removeFromParent(); 425 bb_size--; 426 }else{ 427 pos++; 428 } 429 } 430 431 /* Permutate and pad the alloca instructions whose addresses are taken. */ 432 433 std::vector<unsigned> pg(allocaAddressTaken.size()); 434 fillPermutationGenerator(pg); 435 for(unsigned i=0; i<pg.size(); i++){ 436 /* get the iterator for the first element of the helper vector */ 437 std::vector<Instruction *>::iterator it = allocaAddressTaken.begin(); 438 if(stackframe_do_permutate){ 439 /* get the iterator for the next random element. When permutation is disabled, it keeps pointing to the first element */ 440 ADVANCE_ITERATOR(it, pg[i]); 441 } 442 /* put the variable at the front of the basic block, and remove it from the helper vector. 443 * This way, the variable that is added last will be at the front 444 * */ 445 BB->getInstList().push_front(*it); 446 allocaAddressTaken.erase(it); 447 448 /* put a padding variable between each two adjacent local variables 449 * this is done by inserting a padding var at the front each time a 450 * var has been put at the front with push_front(). 451 * */ 452 int max_padding = (i==pg.size()-1 ? 0 : stackframe_max_padding); 453 if(max_padding > 0){ 454 create_padding_lv(M, BB->getInstList().begin(), (rand () % max_padding) + 1); 455 } 456 } 457 458 459 /* Create a global stack offset, and an offset for each stack frame. Both have a dynamic random size */ 460 461 /* Determine if we must pad or offset, and how much */ 462 int max_offset, do_offset=1; 463 if(F->getName().equals(MAGIC_ENTRY_POINT)){ 464 if(!stack_do_offset){ 465 do_offset=0; 466 } 467 /* give the entry function (first function) a large offset instead of an padding */ 468 max_offset = stack_max_offset; 469 }else{ 470 if(!stackframe_do_offset){ 471 do_offset=0; 472 } 473 max_offset = stackframe_max_offset; 474 } 475 476 /* Create a new block before the first block. Now, all the variable allocations whose addresses are taken are no longer 477 * in the first block, so CallInst::isStaticAlloca() does no longer apply to them. 478 * When isStaticAlloca() == true, the code generator will fold it into the prolog/epilog code, so it is basically free. 479 * This means that we now get less efficient code. 480 * This is necessary to prevent the variables whose address is taken from being allocated before the stack frame offset is allocated. 481 * Alternatively, we could allocate before the function call, instead of after. */ 482 483 BasicBlock *OldFirstBB = F->getBasicBlockList().begin(); 484 BasicBlock *NewFirstBB = BasicBlock::Create(M.getContext(), "newBB", F, OldFirstBB); 485 486 487 /* Permutate and insert the allocation instructions whose addresses are NOT taken into the new first block (dont apply padding). 488 * These must be allocated before the stack frame offset is allocated. */ 489 490 pg = std::vector<unsigned>(allocaNoAddressTaken.size()); 491 fillPermutationGenerator(pg); 492 for(unsigned i=0; i<pg.size(); i++){ 493 /* get the iterator for the first element of the helper vector */ 494 std::vector<Instruction *>::iterator it = allocaNoAddressTaken.begin(); 495 if(stackframe_do_permutate){ 496 /* get the iterator for the next random element. When permutation is disabled, it keeps pointing to the first element */ 497 ADVANCE_ITERATOR(it, pg[i]); 498 } 499 /* put the variable at the front of the basic block, and remove it from the helper vector. 500 * This way, the variable that is added last will be at the front 501 * */ 502 NewFirstBB->getInstList().push_front(*it); 503 allocaNoAddressTaken.erase(it); 504 } 505 506 if(do_offset){ 507 if(stackframe_static_padding) { 508 if(max_offset > 0) { 509 new AllocaInst(IntegerType::get(M.getContext(), 8), ConstantInt::get(M.getContext(), APInt(64, (rand() % max_offset) + 1, 10)), "", NewFirstBB); 510 } 511 } 512 else { 513 /* Now insert a dynamically randomized stackframe offset */ 514 Function *RandFunc = M.getFunction("rand"); 515 assert(RandFunc != NULL); 516 517 /* Call rand() */ 518 std::vector<Value*> args; 519 CallInst* RandFuncCall = PassUtil::createCallInstruction(RandFunc, args, "", NewFirstBB); 520 Instruction *nextInst = RandFuncCall; 521 522 if(max_offset > 0){ 523 /* limit the rand value: rand() % max_offet */ 524 ConstantInt* max_offset_const = ConstantInt::get(M.getContext(), APInt(32, max_offset, 10)); 525 BinaryOperator *Remainder = BinaryOperator::Create(Instruction::SRem, RandFuncCall, max_offset_const, "", NewFirstBB); 526 Remainder->removeFromParent(); 527 Remainder->insertAfter(RandFuncCall); 528 nextInst = Remainder; 529 } 530 531 /* Minimum rand value must be 1, so increment it. */ 532 ConstantInt* One = ConstantInt::get(M.getContext(), APInt(32, StringRef("1"), 10)); 533 BinaryOperator* AddOne = BinaryOperator::Create(Instruction::Add, nextInst, One, "", NewFirstBB); 534 AddOne->removeFromParent(); 535 AddOne->insertAfter(nextInst); 536 537 /* Allocate the offset/padding */ 538 AllocaInst* allocaInstruction = new AllocaInst(IntegerType::get(M.getContext(), 8), AddOne, "", NewFirstBB); 539 allocaInstruction->removeFromParent(); 540 allocaInstruction->insertAfter(AddOne); 541 542 /* Inline the rand() call. */ 543 InlineFunctionInfo IFI; 544 InlineFunction(RandFuncCall, IFI); 545 } 546 } 547 548 /* Go to the old first block */ 549 BranchInst *br = BranchInst::Create (OldFirstBB, NewFirstBB); 550 br->setSuccessor(0, OldFirstBB); 551 552 /* Static stack frame padding does not really need 2 basic blocks, but it may need call site instrumentation. */ 553 if(stackframe_static_padding) { 554 bool ret = MergeBlockIntoPredecessor(OldFirstBB, this); 555 assert(ret); 556 557 if(stackframe_caller_padding && max_offset > 0) { 558 std::vector<User*> Users(F->user_begin(), F->user_end()); 559 while (!Users.empty()) { 560 User *U = Users.back(); 561 Users.pop_back(); 562 if (Instruction *I = dyn_cast<Instruction>(U)) { 563 Function *parent = I->getParent()->getParent(); 564 /* XXX Skipping MAGIC_ENTRY_POINT shouldn't be necessary. Check why. */ 565 /* ..the reason is that main() typically contains the message loop, which loops 566 * forever making calls. These calls are getting padded, and AllocaInst causes a 567 * stack pointer adjustment every time a call is made. This stack memory is never 568 * released, since the function never returns. The result is that we eventually 569 * run out of stack. Since MINIX3 also uses user-level threads these days, the 570 * problem is not limited to main(), and for this reason I have disabled caller 571 * padding by default. -dcvmoole 572 */ 573 if(MAGIC_IS_MAGIC_FUNC(M, parent) || parent->getName().equals(MAGIC_ENTRY_POINT)) { 574 continue; 575 } 576 CallSite CS = PassUtil::getCallSiteFromInstruction(I); 577 if(!CS.getInstruction()) { 578 continue; 579 } 580 Function *calledFunction = getCalledFunctionFromCS(CS); 581 if (CS.getInstruction() && !CS.arg_empty() && (calledFunction == F || calledFunction == NULL)) { 582 new AllocaInst(IntegerType::get(M.getContext(), 8), ConstantInt::get(M.getContext(), APInt(64, (rand() % max_offset) + 1, 10)), "", I); 583 } 584 } 585 } 586 } 587 } 588 589 /* Basic block shifting. */ 590 if(func_max_bb_shift > 0) { 591 Instruction *I; 592 PassUtil::getAllocaInfo(F, NULL, &I); 593 BasicBlock *firstBB = F->getBasicBlockList().begin(); 594 BasicBlock *splitBB = firstBB->splitBasicBlock(I, "split"); 595 BasicBlock *dummyBB = BasicBlock::Create(M.getContext(), "dummy", F, splitBB); 596 if(!stackframe_caller_padding) { 597 firstBB = NewFirstBB; 598 } 599 600 /* Fill the dummy basic block with dummy instructions (using the prefetch intrinsic to emulate nop instructions), to shift the next basic block. */ 601 Function *prefetchIntrinsic = PassUtil::getIntrinsicFunction(M, Intrinsic::prefetch); 602 std::vector<Value*> args; 603 args.push_back(ConstantPointerNull::get(PointerType::get(IntegerType::get(M.getContext(), 8), 0))); 604 args.push_back(ConstantInt::get(M.getContext(), APInt(32, 0))); 605 args.push_back(ConstantInt::get(M.getContext(), APInt(32, 0))); 606 #if LLVM_VERSION >= 30 607 args.push_back(ConstantInt::get(M.getContext(), APInt(32, 0))); 608 #endif 609 unsigned shift = (rand() % func_max_bb_shift) + 1; 610 do { 611 PassUtil::createCallInstruction(prefetchIntrinsic, args, "", dummyBB); 612 shift--; 613 } while(shift > 0); 614 BranchInst *br = BranchInst::Create (splitBB, dummyBB); 615 br->setSuccessor(0, splitBB); 616 617 /* Place an opaque conditional branch (always unconditionally skips the dummy basic block). */ 618 Function *frameAddrIntrinsic = PassUtil::getIntrinsicFunction(M, Intrinsic::frameaddress); 619 std::vector<Value*> frameAddrArgs; 620 frameAddrArgs.push_back(ConstantInt::get(M.getContext(), APInt(32, 0))); 621 Value *frameAddr = PassUtil::createCallInstruction(frameAddrIntrinsic, frameAddrArgs, "", firstBB->getTerminator()); 622 TerminatorInst *OldTI = firstBB->getTerminator(); 623 IRBuilder<> Builder(firstBB); 624 ICmpInst* ExtraCase = new ICmpInst(OldTI, ICmpInst::ICMP_EQ, frameAddr, ConstantPointerNull::get(PointerType::get(IntegerType::get(M.getContext(), 8), 0)), ""); 625 Builder.CreateCondBr(ExtraCase, dummyBB, splitBB); 626 OldTI->eraseFromParent(); 627 } 628 } 629 630 }{ 631 632 633 #define __X(VAR) __XX(VAR) 634 #define __XX(VAR) #VAR 635 636 /* heap and map padding */ 637 638 { 639 640 /* Inject magic init call at the beginning of magic entry point function (before any allocaInsts). 641 * Magic_init will return immediately if called for the second time, so both the magic pass and 642 * this pass can insert call instructions into main 643 * */ 644 std::vector<Value*> args; 645 PassUtil::createCallInstruction(magicInitFunc, args, "", magicEntryPointFunc->getBasicBlockList().begin()->begin()); 646 647 }{ 648 649 /* set the global variables */ 650 651 Function *magicDataInitFunc = M.getFunction(MAGIC_DATA_INIT_FUNC_NAME); 652 if(!magicDataInitFunc){ 653 outs() <<"Error: no " << MAGIC_DATA_INIT_FUNC_NAME << "() found"; 654 exit(1); 655 } 656 Instruction *magicArrayBuildFuncInst = magicDataInitFunc->back().getTerminator(); 657 658 GlobalVariable* magicRootVar = M.getNamedGlobal(MAGIC_ROOT_VAR_NAME); 659 if(!magicRootVar) { 660 outs() << "Error: no " << MAGIC_ROOT_VAR_NAME << " variable found"; 661 exit(1); 662 } 663 664 Value *seedValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_SEED); 665 if(!seedValue) { 666 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_SEED << " field found"; 667 exit(1); 668 } 669 new StoreInst(ConstantInt::get(M.getContext(), APInt(32, runtime_seed)), seedValue, false, magicArrayBuildFuncInst); 670 671 Value *heapMapPermutateValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAP_DO_PERMUTATE); 672 if(!heapMapPermutateValue) { 673 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAP_DO_PERMUTATE << " field found"; 674 exit(1); 675 } 676 new StoreInst(ConstantInt::get(M.getContext(), APInt(32, heap_map_do_permutate)), heapMapPermutateValue, false, magicArrayBuildFuncInst); 677 678 679 Value *heapOffsetValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAX_OFFSET); 680 if(!heapOffsetValue) { 681 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAX_OFFSET << " field found"; 682 exit(1); 683 } 684 new StoreInst(ConstantInt::get(M.getContext(), APInt(32, heap_max_offset)), heapOffsetValue, false, magicArrayBuildFuncInst); 685 686 Value *heapPaddingValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAX_PADDING); 687 if(!heapPaddingValue) { 688 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_HEAP_MAX_PADDING << " field found"; 689 exit(1); 690 } 691 new StoreInst(ConstantInt::get(M.getContext(), APInt(32, heap_max_padding)), heapPaddingValue, false, magicArrayBuildFuncInst); 692 693 694 Value *mapOffsetValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_MAP_MAX_OFFSET_PAGES); 695 if(!mapOffsetValue) { 696 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_MAP_MAX_OFFSET_PAGES << " field found"; 697 exit(1); 698 } 699 new StoreInst(ConstantInt::get(M.getContext(), APInt(32, map_max_offset_pages)), mapOffsetValue, false, magicArrayBuildFuncInst); 700 701 Value *mapPaddingValue = MagicUtil::getMagicRStructFieldPtr(M, magicArrayBuildFuncInst, magicRootVar, MAGIC_RSTRUCT_FIELD_ASR_MAP_MAX_PADDING_PAGES); 702 if(!mapPaddingValue) { 703 outs() << "Error: no " << MAGIC_RSTRUCT_FIELD_ASR_MAP_MAX_PADDING_PAGES << " field found"; 704 exit(1); 705 } 706 new StoreInst(ConstantInt::get(M.getContext(), APInt(32, map_max_padding_pages)), mapPaddingValue, false, magicArrayBuildFuncInst); 707 708 709 710 } 711 712 } 713 714 return true; 715 } 716 717 } // end namespace 718 719 char ASRPass::ID = 1; 720 static RegisterPass<ASRPass> AP("asr", "Address Space Randomization Pass"); 721