1 //===-- StackProtector.cpp - Stack Protector Insertion --------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass inserts stack protectors into functions which need them. A variable 11 // with a random value in it is stored onto the stack before the local variables 12 // are allocated. Upon exiting the block, the stored value is checked. If it's 13 // changed, then there was some sort of violation and the program aborts. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/CodeGen/StackProtector.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/ValueTracking.h" 21 #include "llvm/CodeGen/Analysis.h" 22 #include "llvm/CodeGen/Passes.h" 23 #include "llvm/IR/Attributes.h" 24 #include "llvm/IR/Constants.h" 25 #include "llvm/IR/DataLayout.h" 26 #include "llvm/IR/DerivedTypes.h" 27 #include "llvm/IR/Function.h" 28 #include "llvm/IR/GlobalValue.h" 29 #include "llvm/IR/GlobalVariable.h" 30 #include "llvm/IR/IRBuilder.h" 31 #include "llvm/IR/Instructions.h" 32 #include "llvm/IR/IntrinsicInst.h" 33 #include "llvm/IR/Intrinsics.h" 34 #include "llvm/IR/Module.h" 35 #include "llvm/Support/CommandLine.h" 36 #include <cstdlib> 37 using namespace llvm; 38 39 #define DEBUG_TYPE "stack-protector" 40 41 STATISTIC(NumFunProtected, "Number of functions protected"); 42 STATISTIC(NumAddrTaken, "Number of local variables that have their address" 43 " taken."); 44 45 static cl::opt<bool> EnableSelectionDAGSP("enable-selectiondag-sp", 46 cl::init(true), cl::Hidden); 47 48 char StackProtector::ID = 0; 49 INITIALIZE_PASS(StackProtector, "stack-protector", "Insert stack protectors", 50 false, true) 51 52 FunctionPass *llvm::createStackProtectorPass(const TargetMachine *TM) { 53 return new StackProtector(TM); 54 } 55 56 StackProtector::SSPLayoutKind 57 StackProtector::getSSPLayout(const AllocaInst *AI) const { 58 return AI ? Layout.lookup(AI) : SSPLK_None; 59 } 60 61 void StackProtector::adjustForColoring(const AllocaInst *From, 62 const AllocaInst *To) { 63 // When coloring replaces one alloca with another, transfer the SSPLayoutKind 64 // tag from the remapped to the target alloca. The remapped alloca should 65 // have a size smaller than or equal to the replacement alloca. 66 SSPLayoutMap::iterator I = Layout.find(From); 67 if (I != Layout.end()) { 68 SSPLayoutKind Kind = I->second; 69 Layout.erase(I); 70 71 // Transfer the tag, but make sure that SSPLK_AddrOf does not overwrite 72 // SSPLK_SmallArray or SSPLK_LargeArray, and make sure that 73 // SSPLK_SmallArray does not overwrite SSPLK_LargeArray. 74 I = Layout.find(To); 75 if (I == Layout.end()) 76 Layout.insert(std::make_pair(To, Kind)); 77 else if (I->second != SSPLK_LargeArray && Kind != SSPLK_AddrOf) 78 I->second = Kind; 79 } 80 } 81 82 bool StackProtector::runOnFunction(Function &Fn) { 83 F = &Fn; 84 M = F->getParent(); 85 DominatorTreeWrapperPass *DTWP = 86 getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 87 DT = DTWP ? &DTWP->getDomTree() : nullptr; 88 TLI = TM->getTargetLowering(); 89 90 Attribute Attr = Fn.getAttributes().getAttribute( 91 AttributeSet::FunctionIndex, "stack-protector-buffer-size"); 92 if (Attr.isStringAttribute() && 93 Attr.getValueAsString().getAsInteger(10, SSPBufferSize)) 94 return false; // Invalid integer string 95 96 if (!RequiresStackProtector()) 97 return false; 98 99 ++NumFunProtected; 100 return InsertStackProtectors(); 101 } 102 103 /// \param [out] IsLarge is set to true if a protectable array is found and 104 /// it is "large" ( >= ssp-buffer-size). In the case of a structure with 105 /// multiple arrays, this gets set if any of them is large. 106 bool StackProtector::ContainsProtectableArray(Type *Ty, bool &IsLarge, 107 bool Strong, 108 bool InStruct) const { 109 if (!Ty) 110 return false; 111 if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) { 112 if (!AT->getElementType()->isIntegerTy(8)) { 113 // If we're on a non-Darwin platform or we're inside of a structure, don't 114 // add stack protectors unless the array is a character array. 115 // However, in strong mode any array, regardless of type and size, 116 // triggers a protector. 117 if (!Strong && (InStruct || !Trip.isOSDarwin())) 118 return false; 119 } 120 121 // If an array has more than SSPBufferSize bytes of allocated space, then we 122 // emit stack protectors. 123 if (SSPBufferSize <= TLI->getDataLayout()->getTypeAllocSize(AT)) { 124 IsLarge = true; 125 return true; 126 } 127 128 if (Strong) 129 // Require a protector for all arrays in strong mode 130 return true; 131 } 132 133 const StructType *ST = dyn_cast<StructType>(Ty); 134 if (!ST) 135 return false; 136 137 bool NeedsProtector = false; 138 for (StructType::element_iterator I = ST->element_begin(), 139 E = ST->element_end(); 140 I != E; ++I) 141 if (ContainsProtectableArray(*I, IsLarge, Strong, true)) { 142 // If the element is a protectable array and is large (>= SSPBufferSize) 143 // then we are done. If the protectable array is not large, then 144 // keep looking in case a subsequent element is a large array. 145 if (IsLarge) 146 return true; 147 NeedsProtector = true; 148 } 149 150 return NeedsProtector; 151 } 152 153 bool StackProtector::HasAddressTaken(const Instruction *AI) { 154 for (const User *U : AI->users()) { 155 if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { 156 if (AI == SI->getValueOperand()) 157 return true; 158 } else if (const PtrToIntInst *SI = dyn_cast<PtrToIntInst>(U)) { 159 if (AI == SI->getOperand(0)) 160 return true; 161 } else if (isa<CallInst>(U)) { 162 return true; 163 } else if (isa<InvokeInst>(U)) { 164 return true; 165 } else if (const SelectInst *SI = dyn_cast<SelectInst>(U)) { 166 if (HasAddressTaken(SI)) 167 return true; 168 } else if (const PHINode *PN = dyn_cast<PHINode>(U)) { 169 // Keep track of what PHI nodes we have already visited to ensure 170 // they are only visited once. 171 if (VisitedPHIs.insert(PN)) 172 if (HasAddressTaken(PN)) 173 return true; 174 } else if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 175 if (HasAddressTaken(GEP)) 176 return true; 177 } else if (const BitCastInst *BI = dyn_cast<BitCastInst>(U)) { 178 if (HasAddressTaken(BI)) 179 return true; 180 } 181 } 182 return false; 183 } 184 185 /// \brief Check whether or not this function needs a stack protector based 186 /// upon the stack protector level. 187 /// 188 /// We use two heuristics: a standard (ssp) and strong (sspstrong). 189 /// The standard heuristic which will add a guard variable to functions that 190 /// call alloca with a either a variable size or a size >= SSPBufferSize, 191 /// functions with character buffers larger than SSPBufferSize, and functions 192 /// with aggregates containing character buffers larger than SSPBufferSize. The 193 /// strong heuristic will add a guard variables to functions that call alloca 194 /// regardless of size, functions with any buffer regardless of type and size, 195 /// functions with aggregates that contain any buffer regardless of type and 196 /// size, and functions that contain stack-based variables that have had their 197 /// address taken. 198 bool StackProtector::RequiresStackProtector() { 199 bool Strong = false; 200 bool NeedsProtector = false; 201 if (F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 202 Attribute::StackProtectReq)) { 203 NeedsProtector = true; 204 Strong = true; // Use the same heuristic as strong to determine SSPLayout 205 } else if (F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 206 Attribute::StackProtectStrong)) 207 Strong = true; 208 else if (!F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 209 Attribute::StackProtect)) 210 return false; 211 212 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 213 BasicBlock *BB = I; 214 215 for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; 216 ++II) { 217 if (AllocaInst *AI = dyn_cast<AllocaInst>(II)) { 218 if (AI->isArrayAllocation()) { 219 // SSP-Strong: Enable protectors for any call to alloca, regardless 220 // of size. 221 if (Strong) 222 return true; 223 224 if (const ConstantInt *CI = 225 dyn_cast<ConstantInt>(AI->getArraySize())) { 226 if (CI->getLimitedValue(SSPBufferSize) >= SSPBufferSize) { 227 // A call to alloca with size >= SSPBufferSize requires 228 // stack protectors. 229 Layout.insert(std::make_pair(AI, SSPLK_LargeArray)); 230 NeedsProtector = true; 231 } else if (Strong) { 232 // Require protectors for all alloca calls in strong mode. 233 Layout.insert(std::make_pair(AI, SSPLK_SmallArray)); 234 NeedsProtector = true; 235 } 236 } else { 237 // A call to alloca with a variable size requires protectors. 238 Layout.insert(std::make_pair(AI, SSPLK_LargeArray)); 239 NeedsProtector = true; 240 } 241 continue; 242 } 243 244 bool IsLarge = false; 245 if (ContainsProtectableArray(AI->getAllocatedType(), IsLarge, Strong)) { 246 Layout.insert(std::make_pair(AI, IsLarge ? SSPLK_LargeArray 247 : SSPLK_SmallArray)); 248 NeedsProtector = true; 249 continue; 250 } 251 252 if (Strong && HasAddressTaken(AI)) { 253 ++NumAddrTaken; 254 Layout.insert(std::make_pair(AI, SSPLK_AddrOf)); 255 NeedsProtector = true; 256 } 257 } 258 } 259 } 260 261 return NeedsProtector; 262 } 263 264 static bool InstructionWillNotHaveChain(const Instruction *I) { 265 return !I->mayHaveSideEffects() && !I->mayReadFromMemory() && 266 isSafeToSpeculativelyExecute(I); 267 } 268 269 /// Identify if RI has a previous instruction in the "Tail Position" and return 270 /// it. Otherwise return 0. 271 /// 272 /// This is based off of the code in llvm::isInTailCallPosition. The difference 273 /// is that it inverts the first part of llvm::isInTailCallPosition since 274 /// isInTailCallPosition is checking if a call is in a tail call position, and 275 /// we are searching for an unknown tail call that might be in the tail call 276 /// position. Once we find the call though, the code uses the same refactored 277 /// code, returnTypeIsEligibleForTailCall. 278 static CallInst *FindPotentialTailCall(BasicBlock *BB, ReturnInst *RI, 279 const TargetLoweringBase *TLI) { 280 // Establish a reasonable upper bound on the maximum amount of instructions we 281 // will look through to find a tail call. 282 unsigned SearchCounter = 0; 283 const unsigned MaxSearch = 4; 284 bool NoInterposingChain = true; 285 286 for (BasicBlock::reverse_iterator I = std::next(BB->rbegin()), E = BB->rend(); 287 I != E && SearchCounter < MaxSearch; ++I) { 288 Instruction *Inst = &*I; 289 290 // Skip over debug intrinsics and do not allow them to affect our MaxSearch 291 // counter. 292 if (isa<DbgInfoIntrinsic>(Inst)) 293 continue; 294 295 // If we find a call and the following conditions are satisifed, then we 296 // have found a tail call that satisfies at least the target independent 297 // requirements of a tail call: 298 // 299 // 1. The call site has the tail marker. 300 // 301 // 2. The call site either will not cause the creation of a chain or if a 302 // chain is necessary there are no instructions in between the callsite and 303 // the call which would create an interposing chain. 304 // 305 // 3. The return type of the function does not impede tail call 306 // optimization. 307 if (CallInst *CI = dyn_cast<CallInst>(Inst)) { 308 if (CI->isTailCall() && 309 (InstructionWillNotHaveChain(CI) || NoInterposingChain) && 310 returnTypeIsEligibleForTailCall(BB->getParent(), CI, RI, *TLI)) 311 return CI; 312 } 313 314 // If we did not find a call see if we have an instruction that may create 315 // an interposing chain. 316 NoInterposingChain = 317 NoInterposingChain && InstructionWillNotHaveChain(Inst); 318 319 // Increment max search. 320 SearchCounter++; 321 } 322 323 return nullptr; 324 } 325 326 /// Insert code into the entry block that stores the __stack_chk_guard 327 /// variable onto the stack: 328 /// 329 /// entry: 330 /// StackGuardSlot = alloca i8* 331 /// StackGuard = load __stack_chk_guard 332 /// call void @llvm.stackprotect.create(StackGuard, StackGuardSlot) 333 /// 334 /// Returns true if the platform/triple supports the stackprotectorcreate pseudo 335 /// node. 336 static bool CreatePrologue(Function *F, Module *M, ReturnInst *RI, 337 const TargetLoweringBase *TLI, const Triple &Trip, 338 AllocaInst *&AI, Value *&StackGuardVar) { 339 bool SupportsSelectionDAGSP = false; 340 PointerType *PtrTy = Type::getInt8PtrTy(RI->getContext()); 341 unsigned AddressSpace, Offset; 342 if (TLI->getStackCookieLocation(AddressSpace, Offset)) { 343 Constant *OffsetVal = 344 ConstantInt::get(Type::getInt32Ty(RI->getContext()), Offset); 345 346 StackGuardVar = ConstantExpr::getIntToPtr( 347 OffsetVal, PointerType::get(PtrTy, AddressSpace)); 348 } else if (Trip.getOS() == llvm::Triple::OpenBSD) { 349 StackGuardVar = M->getOrInsertGlobal("__guard_local", PtrTy); 350 cast<GlobalValue>(StackGuardVar) 351 ->setVisibility(GlobalValue::HiddenVisibility); 352 } else { 353 SupportsSelectionDAGSP = true; 354 StackGuardVar = M->getOrInsertGlobal("__stack_chk_guard", PtrTy); 355 } 356 357 IRBuilder<> B(&F->getEntryBlock().front()); 358 AI = B.CreateAlloca(PtrTy, nullptr, "StackGuardSlot"); 359 LoadInst *LI = B.CreateLoad(StackGuardVar, "StackGuard"); 360 B.CreateCall2(Intrinsic::getDeclaration(M, Intrinsic::stackprotector), LI, 361 AI); 362 363 return SupportsSelectionDAGSP; 364 } 365 366 /// InsertStackProtectors - Insert code into the prologue and epilogue of the 367 /// function. 368 /// 369 /// - The prologue code loads and stores the stack guard onto the stack. 370 /// - The epilogue checks the value stored in the prologue against the original 371 /// value. It calls __stack_chk_fail if they differ. 372 bool StackProtector::InsertStackProtectors() { 373 bool HasPrologue = false; 374 bool SupportsSelectionDAGSP = 375 EnableSelectionDAGSP && !TM->Options.EnableFastISel; 376 AllocaInst *AI = nullptr; // Place on stack that stores the stack guard. 377 Value *StackGuardVar = nullptr; // The stack guard variable. 378 379 for (Function::iterator I = F->begin(), E = F->end(); I != E;) { 380 BasicBlock *BB = I++; 381 ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()); 382 if (!RI) 383 continue; 384 385 if (!HasPrologue) { 386 HasPrologue = true; 387 SupportsSelectionDAGSP &= 388 CreatePrologue(F, M, RI, TLI, Trip, AI, StackGuardVar); 389 } 390 391 if (SupportsSelectionDAGSP) { 392 // Since we have a potential tail call, insert the special stack check 393 // intrinsic. 394 Instruction *InsertionPt = nullptr; 395 if (CallInst *CI = FindPotentialTailCall(BB, RI, TLI)) { 396 InsertionPt = CI; 397 } else { 398 InsertionPt = RI; 399 // At this point we know that BB has a return statement so it *DOES* 400 // have a terminator. 401 assert(InsertionPt != nullptr && "BB must have a terminator instruction at " 402 "this point."); 403 } 404 405 Function *Intrinsic = 406 Intrinsic::getDeclaration(M, Intrinsic::stackprotectorcheck); 407 CallInst::Create(Intrinsic, StackGuardVar, "", InsertionPt); 408 409 } else { 410 // If we do not support SelectionDAG based tail calls, generate IR level 411 // tail calls. 412 // 413 // For each block with a return instruction, convert this: 414 // 415 // return: 416 // ... 417 // ret ... 418 // 419 // into this: 420 // 421 // return: 422 // ... 423 // %1 = load __stack_chk_guard 424 // %2 = load StackGuardSlot 425 // %3 = cmp i1 %1, %2 426 // br i1 %3, label %SP_return, label %CallStackCheckFailBlk 427 // 428 // SP_return: 429 // ret ... 430 // 431 // CallStackCheckFailBlk: 432 // call void @__stack_chk_fail() 433 // unreachable 434 435 // Create the FailBB. We duplicate the BB every time since the MI tail 436 // merge pass will merge together all of the various BB into one including 437 // fail BB generated by the stack protector pseudo instruction. 438 BasicBlock *FailBB = CreateFailBB(); 439 440 // Split the basic block before the return instruction. 441 BasicBlock *NewBB = BB->splitBasicBlock(RI, "SP_return"); 442 443 // Update the dominator tree if we need to. 444 if (DT && DT->isReachableFromEntry(BB)) { 445 DT->addNewBlock(NewBB, BB); 446 DT->addNewBlock(FailBB, BB); 447 } 448 449 // Remove default branch instruction to the new BB. 450 BB->getTerminator()->eraseFromParent(); 451 452 // Move the newly created basic block to the point right after the old 453 // basic block so that it's in the "fall through" position. 454 NewBB->moveAfter(BB); 455 456 // Generate the stack protector instructions in the old basic block. 457 IRBuilder<> B(BB); 458 LoadInst *LI1 = B.CreateLoad(StackGuardVar); 459 LoadInst *LI2 = B.CreateLoad(AI); 460 Value *Cmp = B.CreateICmpEQ(LI1, LI2); 461 B.CreateCondBr(Cmp, NewBB, FailBB); 462 } 463 } 464 465 // Return if we didn't modify any basic blocks. I.e., there are no return 466 // statements in the function. 467 if (!HasPrologue) 468 return false; 469 470 return true; 471 } 472 473 /// CreateFailBB - Create a basic block to jump to when the stack protector 474 /// check fails. 475 BasicBlock *StackProtector::CreateFailBB() { 476 LLVMContext &Context = F->getContext(); 477 BasicBlock *FailBB = BasicBlock::Create(Context, "CallStackCheckFailBlk", F); 478 IRBuilder<> B(FailBB); 479 if (Trip.getOS() == llvm::Triple::OpenBSD) { 480 Constant *StackChkFail = M->getOrInsertFunction( 481 "__stack_smash_handler", Type::getVoidTy(Context), 482 Type::getInt8PtrTy(Context), NULL); 483 484 B.CreateCall(StackChkFail, B.CreateGlobalStringPtr(F->getName(), "SSH")); 485 } else { 486 Constant *StackChkFail = M->getOrInsertFunction( 487 "__stack_chk_fail", Type::getVoidTy(Context), NULL); 488 B.CreateCall(StackChkFail); 489 } 490 B.CreateUnreachable(); 491 return FailBB; 492 } 493