StackProtector.cpp revision b99272a521ecffe8d021306713bd51fafc85721e
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#define DEBUG_TYPE "stack-protector" 18#include "llvm/CodeGen/Analysis.h" 19#include "llvm/CodeGen/Passes.h" 20#include "llvm/ADT/SmallPtrSet.h" 21#include "llvm/ADT/Statistic.h" 22#include "llvm/ADT/Triple.h" 23#include "llvm/Analysis/Dominators.h" 24#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. The difference 284/// is that it inverts the first part of llvm::isInTailCallPosition since 285/// isInTailCallPosition is checking if a call is in a tail call position, and 286/// we are searching for an unknown tail call that might be in the tail call 287/// position. Once we find the call though, the code uses the same refactored 288/// code, returnTypeIsEligibleForTailCall. 289static CallInst *FindPotentialTailCall(BasicBlock *BB, ReturnInst *RI, 290 const TargetLoweringBase *TLI) { 291 // Establish a reasonable upper bound on the maximum amount of instructions we 292 // will look through to find a tail call. 293 unsigned SearchCounter = 0; 294 const unsigned MaxSearch = 4; 295 bool NoInterposingChain = true; 296 297 for (BasicBlock::reverse_iterator I = llvm::next(BB->rbegin()), E = BB->rend(); 298 I != E && SearchCounter < MaxSearch; ++I) { 299 Instruction *Inst = &*I; 300 301 // Skip over debug intrinsics and do not allow them to affect our MaxSearch 302 // counter. 303 if (isa<DbgInfoIntrinsic>(Inst)) 304 continue; 305 306 // If we find a call and the following conditions are satisifed, then we 307 // have found a tail call that satisfies at least the target independent 308 // requirements of a tail call: 309 // 310 // 1. The call site has the tail marker. 311 // 312 // 2. The call site either will not cause the creation of a chain or if a 313 // chain is necessary there are no instructions in between the callsite and 314 // the call which would create an interposing chain. 315 // 316 // 3. The return type of the function does not impede tail call 317 // optimization. 318 if (CallInst *CI = dyn_cast<CallInst>(Inst)) { 319 if (CI->isTailCall() && 320 (InstructionWillNotHaveChain(CI) || NoInterposingChain) && 321 returnTypeIsEligibleForTailCall(BB->getParent(), CI, RI, *TLI)) 322 return CI; 323 } 324 325 // If we did not find a call see if we have an instruction that may create 326 // an interposing chain. 327 NoInterposingChain = NoInterposingChain && InstructionWillNotHaveChain(Inst); 328 329 // Increment max search. 330 SearchCounter++; 331 } 332 333 return 0; 334} 335 336/// Insert code into the entry block that stores the __stack_chk_guard 337/// variable onto the stack: 338/// 339/// entry: 340/// StackGuardSlot = alloca i8* 341/// StackGuard = load __stack_chk_guard 342/// call void @llvm.stackprotect.create(StackGuard, StackGuardSlot) 343/// 344/// Returns true if the platform/triple supports the stackprotectorcreate pseudo 345/// node. 346static bool CreatePrologue(Function *F, Module *M, ReturnInst *RI, 347 const TargetLoweringBase *TLI, const Triple &Trip, 348 AllocaInst *&AI, Value *&StackGuardVar) { 349 bool SupportsSelectionDAGSP = false; 350 PointerType *PtrTy = Type::getInt8PtrTy(RI->getContext()); 351 unsigned AddressSpace, Offset; 352 if (TLI->getStackCookieLocation(AddressSpace, Offset)) { 353 Constant *OffsetVal = 354 ConstantInt::get(Type::getInt32Ty(RI->getContext()), Offset); 355 356 StackGuardVar = ConstantExpr::getIntToPtr(OffsetVal, 357 PointerType::get(PtrTy, 358 AddressSpace)); 359 } else if (Trip.getOS() == llvm::Triple::OpenBSD) { 360 StackGuardVar = M->getOrInsertGlobal("__guard_local", PtrTy); 361 cast<GlobalValue>(StackGuardVar) 362 ->setVisibility(GlobalValue::HiddenVisibility); 363 } else { 364 SupportsSelectionDAGSP = true; 365 StackGuardVar = M->getOrInsertGlobal("__stack_chk_guard", PtrTy); 366 } 367 368 BasicBlock &Entry = F->getEntryBlock(); 369 Instruction *InsPt = &Entry.front(); 370 371 AI = new AllocaInst(PtrTy, "StackGuardSlot", InsPt); 372 LoadInst *LI = new LoadInst(StackGuardVar, "StackGuard", false, InsPt); 373 374 Value *Args[] = { LI, AI }; 375 CallInst:: 376 Create(Intrinsic::getDeclaration(M, Intrinsic::stackprotector), 377 Args, "", InsPt); 378 379 return SupportsSelectionDAGSP; 380} 381 382/// InsertStackProtectors - Insert code into the prologue and epilogue of the 383/// function. 384/// 385/// - The prologue code loads and stores the stack guard onto the stack. 386/// - The epilogue checks the value stored in the prologue against the original 387/// value. It calls __stack_chk_fail if they differ. 388bool StackProtector::InsertStackProtectors() { 389 bool HasPrologue = false; 390 bool SupportsSelectionDAGSP = false; 391 AllocaInst *AI = 0; // Place on stack that stores the stack guard. 392 Value *StackGuardVar = 0; // The stack guard variable. 393 394 for (Function::iterator I = F->begin(), E = F->end(); I != E; ) { 395 BasicBlock *BB = I++; 396 ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()); 397 if (!RI) continue; 398 399 if (!HasPrologue) { 400 HasPrologue = true; 401 SupportsSelectionDAGSP = CreatePrologue(F, M, RI, TLI, Trip, AI, 402 StackGuardVar); 403 } 404 405 if (EnableSelectionDAGSP && !TM->Options.EnableFastISel && 406 SupportsSelectionDAGSP) { 407 // Since we have a potential tail call, insert the special stack check 408 // intrinsic. 409 Instruction *InsertionPt = 0; 410 if (CallInst *CI = FindPotentialTailCall(BB, RI, TLI)) { 411 InsertionPt = CI; 412 } else { 413 InsertionPt = RI; 414 // At this point we know that BB has a return statement so it *DOES* 415 // have a terminator. 416 assert(InsertionPt != 0 && "BB must have a terminator instruction at " 417 "this point."); 418 } 419 420 Function *Intrinsic = 421 Intrinsic::getDeclaration(M, Intrinsic::stackprotectorcheck); 422 Value *Args[] = { StackGuardVar }; 423 CallInst::Create(Intrinsic, Args, "", InsertionPt); 424 425 } else { 426 // If we do not support SelectionDAG based tail calls, generate IR level 427 // tail calls. 428 // 429 // For each block with a return instruction, convert this: 430 // 431 // return: 432 // ... 433 // ret ... 434 // 435 // into this: 436 // 437 // return: 438 // ... 439 // %1 = load __stack_chk_guard 440 // %2 = load StackGuardSlot 441 // %3 = cmp i1 %1, %2 442 // br i1 %3, label %SP_return, label %CallStackCheckFailBlk 443 // 444 // SP_return: 445 // ret ... 446 // 447 // CallStackCheckFailBlk: 448 // call void @__stack_chk_fail() 449 // unreachable 450 451 // Create the FailBB. We duplicate the BB every time since the MI tail 452 // merge pass will merge together all of the various BB into one including 453 // fail BB generated by the stack protector pseudo instruction. 454 BasicBlock *FailBB = CreateFailBB(); 455 456 // Split the basic block before the return instruction. 457 BasicBlock *NewBB = BB->splitBasicBlock(RI, "SP_return"); 458 459 // Update the dominator tree if we need to. 460 if (DT && DT->isReachableFromEntry(BB)) { 461 DT->addNewBlock(NewBB, BB); 462 DT->addNewBlock(FailBB, BB); 463 } 464 465 // Remove default branch instruction to the new BB. 466 BB->getTerminator()->eraseFromParent(); 467 468 // Move the newly created basic block to the point right after the old 469 // basic block so that it's in the "fall through" position. 470 NewBB->moveAfter(BB); 471 472 // Generate the stack protector instructions in the old basic block. 473 LoadInst *LI1 = new LoadInst(StackGuardVar, "", false, BB); 474 LoadInst *LI2 = new LoadInst(AI, "", true, BB); 475 ICmpInst *Cmp = new ICmpInst(*BB, CmpInst::ICMP_EQ, LI1, LI2, ""); 476 BranchInst::Create(NewBB, FailBB, Cmp, BB); 477 } 478 } 479 480 // Return if we didn't modify any basic blocks. I.e., there are no return 481 // statements in the function. 482 if (!HasPrologue) 483 return false; 484 485 return true; 486} 487 488/// CreateFailBB - Create a basic block to jump to when the stack protector 489/// check fails. 490BasicBlock *StackProtector::CreateFailBB() { 491 LLVMContext &Context = F->getContext(); 492 BasicBlock *FailBB = BasicBlock::Create(Context, "CallStackCheckFailBlk", F); 493 if (Trip.getOS() == llvm::Triple::OpenBSD) { 494 Constant *StackChkFail = M->getOrInsertFunction( 495 "__stack_smash_handler", Type::getVoidTy(Context), 496 Type::getInt8PtrTy(Context), NULL); 497 498 Constant *NameStr = ConstantDataArray::getString(Context, F->getName()); 499 Constant *FuncName = 500 new GlobalVariable(*M, NameStr->getType(), true, 501 GlobalVariable::PrivateLinkage, NameStr, "SSH"); 502 503 SmallVector<Constant *, 2> IdxList; 504 IdxList.push_back(ConstantInt::get(Type::getInt8Ty(Context), 0)); 505 IdxList.push_back(ConstantInt::get(Type::getInt8Ty(Context), 0)); 506 507 SmallVector<Value *, 1> Args; 508 Args.push_back(ConstantExpr::getGetElementPtr(FuncName, IdxList)); 509 510 CallInst::Create(StackChkFail, Args, "", FailBB); 511 } else { 512 Constant *StackChkFail = M->getOrInsertFunction( 513 "__stack_chk_fail", Type::getVoidTy(Context), NULL); 514 CallInst::Create(StackChkFail, "", FailBB); 515 } 516 new UnreachableInst(Context, FailBB); 517 return FailBB; 518} 519