StackProtector.cpp revision ea44281d5da5096de50ce1cb358ff0c6f20e1a2a
1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org//===-- StackProtector.cpp - Stack Protector Insertion --------------------===// 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// The LLVM Compiler Infrastructure 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// This file is distributed under the University of Illinois Open Source 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// License. See LICENSE.TXT for details. 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org//===----------------------------------------------------------------------===// 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// This pass inserts stack protectors into functions which need them. A variable 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// with a random value in it is stored onto the stack before the local variables 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// are allocated. Upon exiting the block, the stored value is checked. If it's 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// changed, then there was some sort of violation and the program aborts. 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org// 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org//===----------------------------------------------------------------------===// 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define DEBUG_TYPE "stack-protector" 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/CodeGen/Passes.h" 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/ADT/SmallPtrSet.h" 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/ADT/Statistic.h" 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/ADT/Triple.h" 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/Analysis/Dominators.h" 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/Attributes.h" 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/Constants.h" 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/DataLayout.h" 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/DerivedTypes.h" 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/Function.h" 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/GlobalValue.h" 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/GlobalVariable.h" 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/Instructions.h" 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/Intrinsics.h" 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/IR/Module.h" 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/Pass.h" 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/Support/CommandLine.h" 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#include "llvm/Target/TargetLowering.h" 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgusing namespace llvm; 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgSTATISTIC(NumFunProtected, "Number of functions protected"); 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgSTATISTIC(NumAddrTaken, "Number of local variables that have their address" 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org " taken."); 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgnamespace { 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org class StackProtector : public FunctionPass { 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const TargetMachine *TM; 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// TLI - Keep a pointer of a TargetLowering to consult for determining 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// target type sizes. 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const TargetLoweringBase *TLI; 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org const Triple Trip; 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Function *F; 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Module *M; 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org DominatorTree *DT; 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// VisitedPHIs - The set of PHI nodes visited when determining 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// if a variable's reference has been taken. This set 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// is maintained to ensure we don't visit the same PHI node multiple 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// times. 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org SmallPtrSet<const PHINode*, 16> VisitedPHIs; 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// InsertStackProtectors - Insert code into the prologue and epilogue of 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// the function. 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// - The prologue code loads and stores the stack guard onto the stack. 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// - The epilogue checks the value stored in the prologue against the 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// original value. It calls __stack_chk_fail if they differ. 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool InsertStackProtectors(); 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// CreateFailBB - Create a basic block to jump to when the stack protector 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// check fails. 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BasicBlock *CreateFailBB(); 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// ContainsProtectableArray - Check whether the type either is an array or 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// contains an array of sufficient size so that we need stack protectors 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// for it. 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool ContainsProtectableArray(Type *Ty, bool Strong = false, 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool InStruct = false) const; 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// \brief Check whether a stack allocation has its address taken. 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool HasAddressTaken(const Instruction *AI); 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// RequiresStackProtector - Check whether or not this function needs a 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /// stack protector based upon the stack protector level. 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org bool RequiresStackProtector(); 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public: 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org static char ID; // Pass identification, replacement for typeid. 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org StackProtector() : FunctionPass(ID), TM(0), TLI(0) { 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org initializeStackProtectorPass(*PassRegistry::getPassRegistry()); 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org StackProtector(const TargetMachine *TM) 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org : FunctionPass(ID), TM(TM), TLI(0), Trip(TM->getTargetTriple()) { 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org initializeStackProtectorPass(*PassRegistry::getPassRegistry()); 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org virtual void getAnalysisUsage(AnalysisUsage &AU) const { 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org AU.addPreserved<DominatorTree>(); 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 100 virtual bool runOnFunction(Function &Fn); 101 }; 102} // end anonymous namespace 103 104char StackProtector::ID = 0; 105INITIALIZE_PASS(StackProtector, "stack-protector", 106 "Insert stack protectors", false, false) 107 108FunctionPass *llvm::createStackProtectorPass(const TargetMachine *TM) { 109 return new StackProtector(TM); 110} 111 112bool StackProtector::runOnFunction(Function &Fn) { 113 F = &Fn; 114 M = F->getParent(); 115 DT = getAnalysisIfAvailable<DominatorTree>(); 116 TLI = TM->getTargetLowering(); 117 118 if (!RequiresStackProtector()) return false; 119 120 ++NumFunProtected; 121 return InsertStackProtectors(); 122} 123 124/// ContainsProtectableArray - Check whether the type either is an array or 125/// contains a char array of sufficient size so that we need stack protectors 126/// for it. 127bool StackProtector::ContainsProtectableArray(Type *Ty, bool Strong, 128 bool InStruct) const { 129 if (!Ty) return false; 130 if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) { 131 // In strong mode any array, regardless of type and size, triggers a 132 // protector 133 if (Strong) 134 return true; 135 const TargetMachine &TM = TLI->getTargetMachine(); 136 if (!AT->getElementType()->isIntegerTy(8)) { 137 // If we're on a non-Darwin platform or we're inside of a structure, don't 138 // add stack protectors unless the array is a character array. 139 if (InStruct || !Trip.isOSDarwin()) 140 return false; 141 } 142 143 // If an array has more than SSPBufferSize bytes of allocated space, then we 144 // emit stack protectors. 145 if (TM.Options.SSPBufferSize <= TLI->getDataLayout()->getTypeAllocSize(AT)) 146 return true; 147 } 148 149 const StructType *ST = dyn_cast<StructType>(Ty); 150 if (!ST) return false; 151 152 for (StructType::element_iterator I = ST->element_begin(), 153 E = ST->element_end(); I != E; ++I) 154 if (ContainsProtectableArray(*I, Strong, true)) 155 return true; 156 157 return false; 158} 159 160bool StackProtector::HasAddressTaken(const Instruction *AI) { 161 for (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end(); 162 UI != UE; ++UI) { 163 const User *U = *UI; 164 if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { 165 if (AI == SI->getValueOperand()) 166 return true; 167 } else if (const PtrToIntInst *SI = dyn_cast<PtrToIntInst>(U)) { 168 if (AI == SI->getOperand(0)) 169 return true; 170 } else if (isa<CallInst>(U)) { 171 return true; 172 } else if (isa<InvokeInst>(U)) { 173 return true; 174 } else if (const SelectInst *SI = dyn_cast<SelectInst>(U)) { 175 if (HasAddressTaken(SI)) 176 return true; 177 } else if (const PHINode *PN = dyn_cast<PHINode>(U)) { 178 // Keep track of what PHI nodes we have already visited to ensure 179 // they are only visited once. 180 if (VisitedPHIs.insert(PN)) 181 if (HasAddressTaken(PN)) 182 return true; 183 } else if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 184 if (HasAddressTaken(GEP)) 185 return true; 186 } else if (const BitCastInst *BI = dyn_cast<BitCastInst>(U)) { 187 if (HasAddressTaken(BI)) 188 return true; 189 } 190 } 191 return false; 192} 193 194/// \brief Check whether or not this function needs a stack protector based 195/// upon the stack protector level. 196/// 197/// We use two heuristics: a standard (ssp) and strong (sspstrong). 198/// The standard heuristic which will add a guard variable to functions that 199/// call alloca with a either a variable size or a size >= SSPBufferSize, 200/// functions with character buffers larger than SSPBufferSize, and functions 201/// with aggregates containing character buffers larger than SSPBufferSize. The 202/// strong heuristic will add a guard variables to functions that call alloca 203/// regardless of size, functions with any buffer regardless of type and size, 204/// functions with aggregates that contain any buffer regardless of type and 205/// size, and functions that contain stack-based variables that have had their 206/// address taken. 207bool StackProtector::RequiresStackProtector() { 208 bool Strong = false; 209 if (F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 210 Attribute::StackProtectReq)) 211 return true; 212 else if (F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 213 Attribute::StackProtectStrong)) 214 Strong = true; 215 else if (!F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 216 Attribute::StackProtect)) 217 return false; 218 219 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { 220 BasicBlock *BB = I; 221 222 for (BasicBlock::iterator 223 II = BB->begin(), IE = BB->end(); II != IE; ++II) { 224 if (AllocaInst *AI = dyn_cast<AllocaInst>(II)) { 225 if (AI->isArrayAllocation()) { 226 // SSP-Strong: Enable protectors for any call to alloca, regardless 227 // of size. 228 if (Strong) 229 return true; 230 231 if (const ConstantInt *CI = 232 dyn_cast<ConstantInt>(AI->getArraySize())) { 233 unsigned BufferSize = TLI->getTargetMachine().Options.SSPBufferSize; 234 if (CI->getLimitedValue(BufferSize) >= BufferSize) 235 // A call to alloca with size >= SSPBufferSize requires 236 // stack protectors. 237 return true; 238 } else // A call to alloca with a variable size requires protectors. 239 return true; 240 } 241 242 if (ContainsProtectableArray(AI->getAllocatedType(), Strong)) 243 return true; 244 245 if (Strong && HasAddressTaken(AI)) { 246 ++NumAddrTaken; 247 return true; 248 } 249 } 250 } 251 } 252 253 return false; 254} 255 256/// InsertStackProtectors - Insert code into the prologue and epilogue of the 257/// function. 258/// 259/// - The prologue code loads and stores the stack guard onto the stack. 260/// - The epilogue checks the value stored in the prologue against the original 261/// value. It calls __stack_chk_fail if they differ. 262bool StackProtector::InsertStackProtectors() { 263 BasicBlock *FailBB = 0; // The basic block to jump to if check fails. 264 BasicBlock *FailBBDom = 0; // FailBB's dominator. 265 AllocaInst *AI = 0; // Place on stack that stores the stack guard. 266 Value *StackGuardVar = 0; // The stack guard variable. 267 268 for (Function::iterator I = F->begin(), E = F->end(); I != E; ) { 269 BasicBlock *BB = I++; 270 ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator()); 271 if (!RI) continue; 272 273 if (!FailBB) { 274 // Insert code into the entry block that stores the __stack_chk_guard 275 // variable onto the stack: 276 // 277 // entry: 278 // StackGuardSlot = alloca i8* 279 // StackGuard = load __stack_chk_guard 280 // call void @llvm.stackprotect.create(StackGuard, StackGuardSlot) 281 // 282 PointerType *PtrTy = Type::getInt8PtrTy(RI->getContext()); 283 unsigned AddressSpace, Offset; 284 if (TLI->getStackCookieLocation(AddressSpace, Offset)) { 285 Constant *OffsetVal = 286 ConstantInt::get(Type::getInt32Ty(RI->getContext()), Offset); 287 288 StackGuardVar = ConstantExpr::getIntToPtr(OffsetVal, 289 PointerType::get(PtrTy, AddressSpace)); 290 } else if (Trip.getOS() == llvm::Triple::OpenBSD) { 291 StackGuardVar = M->getOrInsertGlobal("__guard_local", PtrTy); 292 cast<GlobalValue>(StackGuardVar) 293 ->setVisibility(GlobalValue::HiddenVisibility); 294 } else { 295 StackGuardVar = M->getOrInsertGlobal("__stack_chk_guard", PtrTy); 296 } 297 298 BasicBlock &Entry = F->getEntryBlock(); 299 Instruction *InsPt = &Entry.front(); 300 301 AI = new AllocaInst(PtrTy, "StackGuardSlot", InsPt); 302 LoadInst *LI = new LoadInst(StackGuardVar, "StackGuard", false, InsPt); 303 304 Value *Args[] = { LI, AI }; 305 CallInst:: 306 Create(Intrinsic::getDeclaration(M, Intrinsic::stackprotector), 307 Args, "", InsPt); 308 309 // Create the basic block to jump to when the guard check fails. 310 FailBB = CreateFailBB(); 311 } 312 313 // For each block with a return instruction, convert this: 314 // 315 // return: 316 // ... 317 // ret ... 318 // 319 // into this: 320 // 321 // return: 322 // ... 323 // %1 = load __stack_chk_guard 324 // %2 = load StackGuardSlot 325 // %3 = cmp i1 %1, %2 326 // br i1 %3, label %SP_return, label %CallStackCheckFailBlk 327 // 328 // SP_return: 329 // ret ... 330 // 331 // CallStackCheckFailBlk: 332 // call void @__stack_chk_fail() 333 // unreachable 334 335 // Split the basic block before the return instruction. 336 BasicBlock *NewBB = BB->splitBasicBlock(RI, "SP_return"); 337 338 if (DT && DT->isReachableFromEntry(BB)) { 339 DT->addNewBlock(NewBB, BB); 340 FailBBDom = FailBBDom ? DT->findNearestCommonDominator(FailBBDom, BB) :BB; 341 } 342 343 // Remove default branch instruction to the new BB. 344 BB->getTerminator()->eraseFromParent(); 345 346 // Move the newly created basic block to the point right after the old basic 347 // block so that it's in the "fall through" position. 348 NewBB->moveAfter(BB); 349 350 // Generate the stack protector instructions in the old basic block. 351 LoadInst *LI1 = new LoadInst(StackGuardVar, "", false, BB); 352 LoadInst *LI2 = new LoadInst(AI, "", true, BB); 353 ICmpInst *Cmp = new ICmpInst(*BB, CmpInst::ICMP_EQ, LI1, LI2, ""); 354 BranchInst::Create(NewBB, FailBB, Cmp, BB); 355 } 356 357 // Return if we didn't modify any basic blocks. I.e., there are no return 358 // statements in the function. 359 if (!FailBB) return false; 360 361 if (DT && FailBBDom) 362 DT->addNewBlock(FailBB, FailBBDom); 363 364 return true; 365} 366 367/// CreateFailBB - Create a basic block to jump to when the stack protector 368/// check fails. 369BasicBlock *StackProtector::CreateFailBB() { 370 LLVMContext &Context = F->getContext(); 371 BasicBlock *FailBB = BasicBlock::Create(Context, "CallStackCheckFailBlk", F); 372 if (Trip.getOS() == llvm::Triple::OpenBSD) { 373 Constant *StackChkFail = M->getOrInsertFunction( 374 "__stack_smash_handler", Type::getVoidTy(Context), 375 Type::getInt8PtrTy(Context), NULL); 376 377 Constant *NameStr = ConstantDataArray::getString(Context, F->getName()); 378 Constant *FuncName = 379 new GlobalVariable(*M, NameStr->getType(), true, 380 GlobalVariable::PrivateLinkage, NameStr, "SSH"); 381 382 SmallVector<Constant *, 2> IdxList; 383 IdxList.push_back(ConstantInt::get(Type::getInt8Ty(Context), 0)); 384 IdxList.push_back(ConstantInt::get(Type::getInt8Ty(Context), 0)); 385 386 SmallVector<Value *, 1> Args; 387 Args.push_back(ConstantExpr::getGetElementPtr(FuncName, IdxList)); 388 389 CallInst::Create(StackChkFail, Args, "", FailBB); 390 } else { 391 Constant *StackChkFail = M->getOrInsertFunction( 392 "__stack_chk_fail", Type::getVoidTy(Context), NULL); 393 CallInst::Create(StackChkFail, "", FailBB); 394 } 395 new UnreachableInst(Context, FailBB); 396 return FailBB; 397} 398