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> 37using namespace llvm; 38 39#define DEBUG_TYPE "stack-protector" 40 41STATISTIC(NumFunProtected, "Number of functions protected"); 42STATISTIC(NumAddrTaken, "Number of local variables that have their address" 43 " taken."); 44 45static cl::opt<bool> EnableSelectionDAGSP("enable-selectiondag-sp", 46 cl::init(true), cl::Hidden); 47 48char StackProtector::ID = 0; 49INITIALIZE_PASS(StackProtector, "stack-protector", "Insert stack protectors", 50 false, true) 51 52FunctionPass *llvm::createStackProtectorPass(const TargetMachine *TM) { 53 return new StackProtector(TM); 54} 55 56StackProtector::SSPLayoutKind 57StackProtector::getSSPLayout(const AllocaInst *AI) const { 58 return AI ? Layout.lookup(AI) : SSPLK_None; 59} 60 61void 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 82bool 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. 106bool 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 153bool 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. 198bool 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 264static 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. 278static 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. 336static 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. 372bool 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. 475BasicBlock *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