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