Bound Allocas

References:

Overview

A Module pass with instruction visitor: class CheriBoundAllocas : public ModulePass, public InstVisitor<CheriBoundAllocas>

Initialization: initializeCheriBoundAllocaPass()

  • declared in llvm/include/llvm/InitializePasses.h
  • impl in llvm/lib/CodeGen/CheriBoundAllocas.cpp: INITIALIZE_PASS(…)
  • called in:
    • llvm/lib/CodeGen/CheriBoundAllocas.cpp: CheriBoundAllocas()
    • llvm/lib/CodeGen/CodeGen.cpp: initializeCodeGen()
    • llvm/tools/opt/opt.cpp: main()

Pass Creation: createCheriBoundAllocasPass()

  • declared in llvm/include/llvm/CodeGen/Passes.h
  • called in
    • Mips: llvm/lib/Target/Mips/MipsTargetMachine.cpp: MipsPassConfig::addIRPasses()
    • RISCV: llvm/lib/Target/RISCV/RISCVTargetMachine.cpp: RISCVPassConfig::addIRPasses()

Adding bound instruction:

  • Get intrinsic: Intrinsic::getDeclaration(M, Intrinsic::cheri_cap_bounds_set, SizeTy);

    // llvm/lib/CodeGen/CheriBoundAllocas.cpp

// Intrinsic handle as function
Function *SetBoundsIntrin = Intrinsic::getDeclaration(M, Intrinsic::cheri_cap_bounds_set,
                                  SizeTy);

Intrinsic::ID BoundedStackCap = UseRematerializableIntrinsic
                                ? Intrinsic::cheri_bounded_stack_cap
                                : Intrinsic::cheri_cap_bounds_set;
Function *BoundedStackFn = Intrinsic::getDeclaration(M, BoundedStackCap, SizeTy);

// Use intrinsic to create IR instruction
LLVMContext &C = M->getContext();
IRBuilder<> B(C);

// one version
// convert to i8 for the intrinsic
Instruction *AllocaI8 = cast<Instruction>(B.CreateBitCast(AI, I8CapTy));
Value *SingleBoundedAlloc = B.CreateCall(SetBoundsIntrin, {AllocaI8, Size});
SingleBoundedAlloc = B.CreateBitCast(SingleBoundedAlloc, AllocaTy);

// another version
auto WithBounds = B.CreateCall(SetBoundsIntrin, {AllocaI8, Size});
const_cast<Use *>(U)->set(B.CreateBitCast(WithBounds, AllocaTy));

Functions/Steps:

  • runOnModule: Iterate over all functions and call runOnFunction
  • runOnFunction:
    • visit(F) -> visitAllocaInst(): Store All AllocaInst in this function in vector Allocas
    • For every AllocaInst in the function:
    • Set the (AllocaInst + 1) as insertion point, so will be inserted immediately after the alloca.
    • Check the type of AllocaInst, i.e. the type of data being allocated.
    • Check if CHERI has precise bounds (TLI: TargetLowering), and determine the final bounds of the alloca object.
    • Collect a set of Uses of the AllocaInst that needs to be inserted with a Bound instruction.
      • enum StackBoundsMethod has different modes: Never/AllUses/IfNeeded...
      • class CheriNeedBoundsChecker finds the uses that needs bound check.
    • If alloca is dynamic alloca (!AI->isStaticAlloca()): use single intrinsic cheri_cap_bounds_set. If static, use cheri_bounded_stack_cap or cher_cap_bounds_set.
    • For every uses of AllocaInst (I = cast<Instruction>(U->getUser())):
      • Check if reuse the result of a single csetbounds intrinsic
      • Reuse only when we are at -O0 or there are more than N users of this bounded stack capability.
      • If reuse the result of a single csetbounds intrinsic:
        • const_cast<Use *>(U)->set(SingleBoundedAlloc): Update the user as the user of the SingleBoundedAlloc instruction instead of the AllocaInst.
      • If not reusing the single intrinsic call:
      • Locate the Insertion point:
        • If the user instruction is is a PHINode, insert point is the terminator of the incoming basic block corresponding to the User instruction.
        • Otherwise, the insert point is the current user instruction.
      • Do Insertion of bounding instruction:
        • Create BitCast Instruction B.CreateBitCast(AI, I8CapTy)
        • Create Call Instruction B.CreateCall(SetBoundsIntrin, {AllocaI8, Size})
        • Create BitCast Instruction and set the AllocaInst as the user of this BitCast Inst:
        • const_cast<User *>(U)->set(B.CreateBitCast(WithBounds, AllocaTy))

Summary

Check all alloca instructions in a function, insert cheri_cap_bounds_set or cheri_bounded_stack_cap instruction to proper location to set/check the bound of alloca’d object.

If alloca’d object is non-pointer type, convert it to a pointer type, set the bounds, so that it can be checked in CHERI, and convert it back for normal use.

CheriBoundAllocas

More

Created Sep 30, 2020 // Last Updated Oct 2, 2020

If you could revise
the fundmental principles of
computer system design
to improve security...

... what would you change?