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