#include "llvm/Transforms/Instrumentation.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/Triple.h"
-#include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/CodeGen/Passes.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_os_ostream.h"
+#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ModuleUtils.h"
namespace {
-/// Check whether a given alloca instruction (AI) should be put on the safe
-/// stack or not. The function analyzes all uses of AI and checks whether it is
-/// only accessed in a memory safe way (as decided statically).
-bool IsSafeStackAlloca(const AllocaInst *AI) {
- // Go through all uses of this alloca and check whether all accesses to the
- // allocated object are statically known to be memory safe and, hence, the
- // object can be placed on the safe stack.
-
- SmallPtrSet<const Value *, 16> Visited;
- SmallVector<const Instruction *, 8> WorkList;
- WorkList.push_back(AI);
-
- // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
- while (!WorkList.empty()) {
- const Instruction *V = WorkList.pop_back_val();
- for (const Use &UI : V->uses()) {
- auto I = cast<const Instruction>(UI.getUser());
- assert(V == UI.get());
-
- switch (I->getOpcode()) {
- case Instruction::Load:
- // Loading from a pointer is safe.
- break;
- case Instruction::VAArg:
- // "va-arg" from a pointer is safe.
- break;
- case Instruction::Store:
- if (V == I->getOperand(0))
- // Stored the pointer - conservatively assume it may be unsafe.
- return false;
- // Storing to the pointee is safe.
- break;
-
- case Instruction::GetElementPtr:
- if (!cast<const GetElementPtrInst>(I)->hasAllConstantIndices())
- // GEP with non-constant indices can lead to memory errors.
- // This also applies to inbounds GEPs, as the inbounds attribute
- // represents an assumption that the address is in bounds, rather than
- // an assertion that it is.
- return false;
-
- // We assume that GEP on static alloca with constant indices is safe,
- // otherwise a compiler would detect it and warn during compilation.
-
- if (!isa<const ConstantInt>(AI->getArraySize()))
- // However, if the array size itself is not constant, the access
- // might still be unsafe at runtime.
- return false;
-
- /* fallthrough */
-
- case Instruction::BitCast:
- case Instruction::IntToPtr:
- case Instruction::PHI:
- case Instruction::PtrToInt:
- case Instruction::Select:
- // The object can be safe or not, depending on how the result of the
- // instruction is used.
- if (Visited.insert(I).second)
- WorkList.push_back(cast<const Instruction>(I));
- break;
-
- case Instruction::Call:
- case Instruction::Invoke: {
- // FIXME: add support for memset and memcpy intrinsics.
- ImmutableCallSite CS(I);
+/// Rewrite an SCEV expression for a memory access address to an expression that
+/// represents offset from the given alloca.
+///
+/// The implementation simply replaces all mentions of the alloca with zero.
+class AllocaOffsetRewriter : public SCEVRewriteVisitor<AllocaOffsetRewriter> {
+ const AllocaInst *AI;
- // LLVM 'nocapture' attribute is only set for arguments whose address
- // is not stored, passed around, or used in any other non-trivial way.
- // We assume that passing a pointer to an object as a 'nocapture'
- // argument is safe.
- // FIXME: a more precise solution would require an interprocedural
- // analysis here, which would look at all uses of an argument inside
- // the function being called.
- ImmutableCallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
- for (ImmutableCallSite::arg_iterator A = B; A != E; ++A)
- if (A->get() == V && !CS.doesNotCapture(A - B))
- // The parameter is not marked 'nocapture' - unsafe.
- return false;
- continue;
- }
+public:
+ AllocaOffsetRewriter(ScalarEvolution &SE, const AllocaInst *AI)
+ : SCEVRewriteVisitor(SE), AI(AI) {}
- default:
- // The object is unsafe if it is used in any other way.
- return false;
- }
- }
+ const SCEV *visitUnknown(const SCEVUnknown *Expr) {
+ if (Expr->getValue() == AI)
+ return SE.getZero(Expr->getType());
+ return Expr;
}
+};
- // All uses of the alloca are safe, we can place it on the safe stack.
- return true;
-}
-
-/// The SafeStack pass splits the stack of each function into the
-/// safe stack, which is only accessed through memory safe dereferences
-/// (as determined statically), and the unsafe stack, which contains all
-/// local variables that are accessed in unsafe ways.
+/// The SafeStack pass splits the stack of each function into the safe
+/// stack, which is only accessed through memory safe dereferences (as
+/// determined statically), and the unsafe stack, which contains all
+/// local variables that are accessed in ways that we can't prove to
+/// be safe.
class SafeStack : public FunctionPass {
+ const TargetMachine *TM;
+ const TargetLoweringBase *TL;
const DataLayout *DL;
+ ScalarEvolution *SE;
Type *StackPtrTy;
Type *IntPtrTy;
Type *Int32Ty;
Type *Int8Ty;
- Constant *UnsafeStackPtr;
+ Value *UnsafeStackPtr = nullptr;
/// Unsafe stack alignment. Each stack frame must ensure that the stack is
/// aligned to this value. We need to re-align the unsafe stack if the
/// might expect to appear on the stack on most common targets.
enum { StackAlignment = 16 };
- /// \brief Build a constant representing a pointer to the unsafe stack
- /// pointer.
- Constant *getOrCreateUnsafeStackPtr(Module &M);
+ /// \brief Build a value representing a pointer to the unsafe stack pointer.
+ Value *getOrCreateUnsafeStackPtr(IRBuilder<> &IRB, Function &F);
/// \brief Find all static allocas, dynamic allocas, return instructions and
/// stack restore points (exception unwind blocks and setjmp calls) in the
///
/// \returns A pointer to the top of the unsafe stack after all unsafe static
/// allocas are allocated.
- Value *moveStaticAllocasToUnsafeStack(Function &F,
+ Value *moveStaticAllocasToUnsafeStack(IRBuilder<> &IRB, Function &F,
ArrayRef<AllocaInst *> StaticAllocas,
ArrayRef<ReturnInst *> Returns);
/// \returns A local variable in which to maintain the dynamic top of the
/// unsafe stack if needed.
AllocaInst *
- createStackRestorePoints(Function &F,
+ createStackRestorePoints(IRBuilder<> &IRB, Function &F,
ArrayRef<Instruction *> StackRestorePoints,
Value *StaticTop, bool NeedDynamicTop);
AllocaInst *DynamicTop,
ArrayRef<AllocaInst *> DynamicAllocas);
+ bool IsSafeStackAlloca(const AllocaInst *AI);
+
+ bool IsMemIntrinsicSafe(const MemIntrinsic *MI, const Use &U,
+ const AllocaInst *AI);
+ bool IsAccessSafe(Value *Addr, uint64_t Size, const AllocaInst *AI);
+
public:
static char ID; // Pass identification, replacement for typeid.
- SafeStack() : FunctionPass(ID), DL(nullptr) {
+ SafeStack(const TargetMachine *TM)
+ : FunctionPass(ID), TM(TM), TL(nullptr), DL(nullptr) {
initializeSafeStackPass(*PassRegistry::getPassRegistry());
}
+ SafeStack() : SafeStack(nullptr) {}
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<AliasAnalysis>();
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.addRequired<ScalarEvolutionWrapperPass>();
}
- virtual bool doInitialization(Module &M) {
+ bool doInitialization(Module &M) override {
DL = &M.getDataLayout();
StackPtrTy = Type::getInt8PtrTy(M.getContext());
Int32Ty = Type::getInt32Ty(M.getContext());
Int8Ty = Type::getInt8Ty(M.getContext());
- UnsafeStackPtr = getOrCreateUnsafeStackPtr(M);
-
return false;
}
- bool runOnFunction(Function &F);
-
+ bool runOnFunction(Function &F) override;
}; // class SafeStack
-Constant *SafeStack::getOrCreateUnsafeStackPtr(Module &M) {
- // The unsafe stack pointer is stored in a global variable with a magic name.
- const char *kUnsafeStackPtrVar = "__safestack_unsafe_stack_ptr";
+bool SafeStack::IsAccessSafe(Value *Addr, uint64_t Size, const AllocaInst *AI) {
+ AllocaOffsetRewriter Rewriter(*SE, AI);
+ const SCEV *Expr = Rewriter.visit(SE->getSCEV(Addr));
+
+ uint64_t BitWidth = SE->getTypeSizeInBits(Expr->getType());
+ ConstantRange AccessStartRange = SE->getUnsignedRange(Expr);
+ ConstantRange SizeRange =
+ ConstantRange(APInt(BitWidth, 0), APInt(BitWidth, Size));
+ ConstantRange AccessRange = AccessStartRange.add(SizeRange);
+ ConstantRange AllocaRange = ConstantRange(
+ APInt(BitWidth, 0),
+ APInt(BitWidth, DL->getTypeStoreSize(AI->getAllocatedType())));
+ bool Safe = AllocaRange.contains(AccessRange);
+
+ DEBUG(dbgs() << "[SafeStack] Alloca " << *AI << "\n"
+ << " Access " << *Addr << "\n"
+ << " SCEV " << *Expr
+ << " U: " << SE->getUnsignedRange(Expr)
+ << ", S: " << SE->getSignedRange(Expr) << "\n"
+ << " Range " << AccessRange << "\n"
+ << " AllocaRange " << AllocaRange << "\n"
+ << " " << (Safe ? "safe" : "unsafe") << "\n");
+
+ return Safe;
+}
+
+bool SafeStack::IsMemIntrinsicSafe(const MemIntrinsic *MI, const Use &U,
+ const AllocaInst *AI) {
+ // All MemIntrinsics have destination address in Arg0 and size in Arg2.
+ if (MI->getRawDest() != U) return true;
+ const auto *Len = dyn_cast<ConstantInt>(MI->getLength());
+ // Non-constant size => unsafe. FIXME: try SCEV getRange.
+ if (!Len) return false;
+ return IsAccessSafe(U, Len->getZExtValue(), AI);
+}
+
+/// Check whether a given alloca instruction (AI) should be put on the safe
+/// stack or not. The function analyzes all uses of AI and checks whether it is
+/// only accessed in a memory safe way (as decided statically).
+bool SafeStack::IsSafeStackAlloca(const AllocaInst *AI) {
+ // Go through all uses of this alloca and check whether all accesses to the
+ // allocated object are statically known to be memory safe and, hence, the
+ // object can be placed on the safe stack.
+ SmallPtrSet<const Value *, 16> Visited;
+ SmallVector<const Instruction *, 8> WorkList;
+ WorkList.push_back(AI);
+
+ // A DFS search through all uses of the alloca in bitcasts/PHI/GEPs/etc.
+ while (!WorkList.empty()) {
+ const Instruction *V = WorkList.pop_back_val();
+ for (const Use &UI : V->uses()) {
+ auto I = cast<const Instruction>(UI.getUser());
+ assert(V == UI.get());
+
+ switch (I->getOpcode()) {
+ case Instruction::Load: {
+ if (!IsAccessSafe(UI, DL->getTypeStoreSize(I->getType()), AI))
+ return false;
+ break;
+ }
+ case Instruction::VAArg:
+ // "va-arg" from a pointer is safe.
+ break;
+ case Instruction::Store: {
+ if (V == I->getOperand(0)) {
+ // Stored the pointer - conservatively assume it may be unsafe.
+ DEBUG(dbgs() << "[SafeStack] Unsafe alloca: " << *AI
+ << "\n store of address: " << *I << "\n");
+ return false;
+ }
+
+ if (!IsAccessSafe(
+ UI, DL->getTypeStoreSize(I->getOperand(0)->getType()), AI))
+ return false;
+ break;
+ }
+ case Instruction::Ret: {
+ // Information leak.
+ return false;
+ }
+
+ case Instruction::Call:
+ case Instruction::Invoke: {
+ ImmutableCallSite CS(I);
+
+ if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+ if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
+ II->getIntrinsicID() == Intrinsic::lifetime_end)
+ continue;
+ }
+
+ if (const MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
+ if (!IsMemIntrinsicSafe(MI, UI, AI)) {
+ DEBUG(dbgs() << "[SafeStack] Unsafe alloca: " << *AI
+ << "\n unsafe memintrinsic: " << *I
+ << "\n");
+ return false;
+ }
+ continue;
+ }
+
+ // LLVM 'nocapture' attribute is only set for arguments whose address
+ // is not stored, passed around, or used in any other non-trivial way.
+ // We assume that passing a pointer to an object as a 'nocapture
+ // readnone' argument is safe.
+ // FIXME: a more precise solution would require an interprocedural
+ // analysis here, which would look at all uses of an argument inside
+ // the function being called.
+ ImmutableCallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end();
+ for (ImmutableCallSite::arg_iterator A = B; A != E; ++A)
+ if (A->get() == V)
+ if (!(CS.doesNotCapture(A - B) &&
+ (CS.doesNotAccessMemory(A - B) || CS.doesNotAccessMemory()))) {
+ DEBUG(dbgs() << "[SafeStack] Unsafe alloca: " << *AI
+ << "\n unsafe call: " << *I << "\n");
+ return false;
+ }
+ continue;
+ }
+
+ default:
+ if (Visited.insert(I).second)
+ WorkList.push_back(cast<const Instruction>(I));
+ }
+ }
+ }
+ // All uses of the alloca are safe, we can place it on the safe stack.
+ return true;
+}
+
+Value *SafeStack::getOrCreateUnsafeStackPtr(IRBuilder<> &IRB, Function &F) {
+ // Check if there is a target-specific location for the unsafe stack pointer.
+ if (TL)
+ if (Value *V = TL->getSafeStackPointerLocation(IRB))
+ return V;
+
+ // Otherwise, assume the target links with compiler-rt, which provides a
+ // thread-local variable with a magic name.
+ Module &M = *F.getParent();
+ const char *UnsafeStackPtrVar = "__safestack_unsafe_stack_ptr";
auto UnsafeStackPtr =
- dyn_cast_or_null<GlobalVariable>(M.getNamedValue(kUnsafeStackPtrVar));
+ dyn_cast_or_null<GlobalVariable>(M.getNamedValue(UnsafeStackPtrVar));
if (!UnsafeStackPtr) {
// The global variable is not defined yet, define it ourselves.
- // We use the initial-exec TLS model because we do not support the variable
- // living anywhere other than in the main executable.
+ // We use the initial-exec TLS model because we do not support the
+ // variable living anywhere other than in the main executable.
UnsafeStackPtr = new GlobalVariable(
- /*Module=*/M, /*Type=*/StackPtrTy,
- /*isConstant=*/false, /*Linkage=*/GlobalValue::ExternalLinkage,
- /*Initializer=*/0, /*Name=*/kUnsafeStackPtrVar,
- /*InsertBefore=*/nullptr,
- /*ThreadLocalMode=*/GlobalValue::InitialExecTLSModel);
+ M, StackPtrTy, false, GlobalValue::ExternalLinkage, nullptr,
+ UnsafeStackPtrVar, nullptr, GlobalValue::InitialExecTLSModel);
} else {
// The variable exists, check its type and attributes.
- if (UnsafeStackPtr->getValueType() != StackPtrTy) {
- report_fatal_error(Twine(kUnsafeStackPtrVar) + " must have void* type");
- }
-
- if (!UnsafeStackPtr->isThreadLocal()) {
- report_fatal_error(Twine(kUnsafeStackPtrVar) + " must be thread-local");
- }
+ if (UnsafeStackPtr->getValueType() != StackPtrTy)
+ report_fatal_error(Twine(UnsafeStackPtrVar) + " must have void* type");
+ if (!UnsafeStackPtr->isThreadLocal())
+ report_fatal_error(Twine(UnsafeStackPtrVar) + " must be thread-local");
}
-
return UnsafeStackPtr;
}
SmallVectorImpl<AllocaInst *> &DynamicAllocas,
SmallVectorImpl<ReturnInst *> &Returns,
SmallVectorImpl<Instruction *> &StackRestorePoints) {
- for (Instruction &I : inst_range(&F)) {
+ for (Instruction &I : instructions(&F)) {
if (auto AI = dyn_cast<AllocaInst>(&I)) {
++NumAllocas;
}
AllocaInst *
-SafeStack::createStackRestorePoints(Function &F,
+SafeStack::createStackRestorePoints(IRBuilder<> &IRB, Function &F,
ArrayRef<Instruction *> StackRestorePoints,
Value *StaticTop, bool NeedDynamicTop) {
if (StackRestorePoints.empty())
return nullptr;
- IRBuilder<> IRB(StaticTop
- ? cast<Instruction>(StaticTop)->getNextNode()
- : (Instruction *)F.getEntryBlock().getFirstInsertionPt());
-
// We need the current value of the shadow stack pointer to restore
// after longjmp or exception catching.
}
Value *
-SafeStack::moveStaticAllocasToUnsafeStack(Function &F,
+SafeStack::moveStaticAllocasToUnsafeStack(IRBuilder<> &IRB, Function &F,
ArrayRef<AllocaInst *> StaticAllocas,
ArrayRef<ReturnInst *> Returns) {
if (StaticAllocas.empty())
return nullptr;
- IRBuilder<> IRB(F.getEntryBlock().getFirstInsertionPt());
DIBuilder DIB(*F.getParent());
// We explicitly compute and set the unsafe stack layout for all unsafe
cast<Instruction>(NewAI)->takeName(AI);
// Replace alloc with the new location.
- replaceDbgDeclareForAlloca(AI, NewAI, DIB, /*Deref=*/true);
+ replaceDbgDeclareForAlloca(AI, BasePointer, DIB, /*Deref=*/true, -StaticOffset);
AI->replaceAllUsesWith(NewAI);
AI->eraseFromParent();
}
}
bool SafeStack::runOnFunction(Function &F) {
- auto AA = &getAnalysis<AliasAnalysis>();
-
DEBUG(dbgs() << "[SafeStack] Function: " << F.getName() << "\n");
if (!F.hasFnAttribute(Attribute::SafeStack)) {
return false;
}
+ TL = TM ? TM->getSubtargetImpl(F)->getTargetLowering() : nullptr;
+ SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+
{
// Make sure the regular stack protector won't run on this function
// (safestack attribute takes precedence).
AttributeSet::get(F.getContext(), AttributeSet::FunctionIndex, B));
}
- if (AA->onlyReadsMemory(&F)) {
- // XXX: we don't protect against information leak attacks for now.
- DEBUG(dbgs() << "[SafeStack] function only reads memory\n");
- return false;
- }
-
++NumFunctions;
SmallVector<AllocaInst *, 16> StaticAllocas;
if (!StackRestorePoints.empty())
++NumUnsafeStackRestorePointsFunctions;
+ IRBuilder<> IRB(&F.front(), F.begin()->getFirstInsertionPt());
+ UnsafeStackPtr = getOrCreateUnsafeStackPtr(IRB, F);
+
// The top of the unsafe stack after all unsafe static allocas are allocated.
- Value *StaticTop = moveStaticAllocasToUnsafeStack(F, StaticAllocas, Returns);
+ Value *StaticTop = moveStaticAllocasToUnsafeStack(IRB, F, StaticAllocas, Returns);
// Safe stack object that stores the current unsafe stack top. It is updated
// as unsafe dynamic (non-constant-sized) allocas are allocated and freed.
// FIXME: a better alternative might be to store the unsafe stack pointer
// before setjmp / invoke instructions.
AllocaInst *DynamicTop = createStackRestorePoints(
- F, StackRestorePoints, StaticTop, !DynamicAllocas.empty());
+ IRB, F, StackRestorePoints, StaticTop, !DynamicAllocas.empty());
// Handle dynamic allocas.
moveDynamicAllocasToUnsafeStack(F, UnsafeStackPtr, DynamicTop,
return true;
}
-} // end anonymous namespace
+} // anonymous namespace
char SafeStack::ID = 0;
-INITIALIZE_PASS_BEGIN(SafeStack, "safe-stack",
- "Safe Stack instrumentation pass", false, false)
-INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
-INITIALIZE_PASS_END(SafeStack, "safe-stack", "Safe Stack instrumentation pass",
- false, false)
+INITIALIZE_TM_PASS_BEGIN(SafeStack, "safe-stack",
+ "Safe Stack instrumentation pass", false, false)
+INITIALIZE_TM_PASS_END(SafeStack, "safe-stack",
+ "Safe Stack instrumentation pass", false, false)
-FunctionPass *llvm::createSafeStackPass() { return new SafeStack(); }
+FunctionPass *llvm::createSafeStackPass(const llvm::TargetMachine *TM) {
+ return new SafeStack(TM);
+}
projects / oota-llvm.git / blobdiff