LLVM 工具系列 - Address Sanitizer 实现原理(2)

JoeyBlue

发布于 2023-01-08 09:15:10

5670

发布于 2023-01-08 09:15:10

上篇文章「Address Sanitizer 基本原理介绍及案例分析」里我们简单地介绍了一下 Address Sanitizer 基础的工作原理，这里我们再继续深挖一下深层次的原理。

从上篇文章中我们也了解到，对一个内存地址的读和写操作：

*address = ...;  // 写操作
... = *address;  // 读操作

当开启 Address Sanitizer 之后，运行时库将会替换掉 malloc 和 free 函数，在 malloc 分配的内存区域前后设置“投毒”(poisoned)区域, 使用 free 释放之后的内存也会被隔离并投毒，poisoned 区域也被称为 redzone。

上面的内存地址访问的代码，编译器会帮我们修改为这样的代码：

if (IsPoisoned(address)) {
  ReportError(address, kAccessSize, kIsWrite);
}
*address = ...;  // or: ... = *address;

这样对内存的访问，编译器会在编译期自动在所有内存访问之前通过判断 IsPoisoned(address) 做一下 check 是否被“投毒”。

那么实现且高效地实现 IsPoisoned()，并使得 ReportError() 函数比较紧凑就十分重要。

在深入了解之前，我们先了解 Shadow 内存，以及主应用内存区和shadow 内存映射。

Shadow 内存 & 主应用内存区和 shadow 内存间的映射

首先，虚拟内存地址被分配了两段不连续的区域：主应用内存区和 shadow内存区域。

主应用内存区（Main Application Memory, or Mem for short)，其实就是在应用里分配的常规内存。

Shadow 内存区，它包含了主内存区状态的 meta 信息，也称之为 shadow value（影子值）。主应用内存区和 shadow 内存区有一个映射关系，当应用内存被“投毒”（poisoned），会在 shadow 内存区记录一个值作为体现。这样就可以通过查询 shadow 内存区的值，来判断应用内存是否被“投毒”。

为了节省内存占用，AddressSanitizer 会把 8 bytes 的应用内存会映射到 1 byte 的 shadow 内存。这样的话，这 1byte 的 shadown 内存会有 9 种值对应应用内存的状态：

负值，当 8 字节的应用内存全都被 poisoned 时；
0 值，当且仅当 8 字节的应用内存都没有被 poisoned 时；
1-7 值，为 k 的意思为 “前 k 个字节都没有被 poisoned，后 8-k 个字节被 poisoned”，这个是由 malloc 分配的内存总是 8 字节对齐作为前提来作为保证的。这样的话，当 malloc(13) 时，得到的是前一个完整的 qword（8字节，未被 poisoned）加上后一个 qword 的前 5 个 byte（未被 poisoned）

如何检查是否在“投毒区”（poisoned/redzone）？

这样的话，我们就可以根据 shadow 内存的 9 种值来判断引用内存的状态了。

if (IsPoisoned(address)) {
  ReportError(address, kAccessSize, kIsWrite);
}

扩展为：

// 拿到主应用内存地址对应的 Shadow 内存地址
byte *shadow_address = MemToShadow(address);

// 检查 shadow 内存值，如果为 0，肯定没有被 poison，因为可以跳过
// 如果不为 0，需要进一步检查是否访问的字节是否被 poisoned
byte shadow_value = *shadow_address;
if (shadow_value) {
  // 进一步检查访问的内存大小是否被 poisoned
  if (SlowPathCheck(shadow_value, address, kAccessSize)) {
    ReportError(address, kAccessSize, kIsWrite);
  }
}

// Check the cases where we access first k bytes of the qword
// and these k bytes are unpoisoned.
bool SlowPathCheck(shadow_value, address, kAccessSize) {
  last_accessed_byte = (address & 7) + kAccessSize - 1;
  return (last_accessed_byte >= shadow_value);
}

SlowPathCheck() 里，检查是否当前访问的地址的前若干个字节是否被 poisoned 了，因为是 8bytes 的应用内存映射到 1byte 的 shadow 上，首先要知道偏移，偏移+长度就是最后一个字节的位置，shadow_value <= 这个位置 - 1，说明被投毒了。

来看个例子。

比如应用内存 0x1000 - 0x1007 对应 shadow 的 0xF000 的地址

0x1000, 0x1001, 0x1002, 0x1003, 0x1004, 0x1005, 0x1006, 0x1007,

如果 0xF000 的值为 2，就说明 0x1000, 0x1001 未被 poisoned，0x1002 到 0x1007 是被 poisoned 的。

那么，如果有一个 int 值在 0x1002 上，长度是4字节，那么我就需要检查 0x1005 以及之前（也就是前6个字节）是否被投毒，也就是检查 shadow value 是否 <= 5，如果小于等于 5，就说明只有前 5 个或者更少未被 poisoned，第6个字节一定被 poisoned 了，也就是这个 int 值肯定是被 poisoned 了。

再来看计算公式：

last_accessed_byte = 0x1002 & 7 + 4 - 1 = 5,

如果 5 >= shadow value, 即认为被 poisoned，和上述解释是一致的。

LLVM 里的实现源码

实际上，LLVM 是通过自定义 LLVM Pass 来生成指令并配合运行时库来完成上面的操作的。

具体的源码可以参考 AddressSanitizer.cpp

源码超级长，我们只挑和上面相关的，首先定义了 static const uint64_t kDefaultShadowScale = 3;

， 1 << 3 == 8，因此就作为映射的粒度。

AddressSanitizerLegacyPass 继承自 FunctionPass，override 了 runOnFunction(Function &F)，也就可以对所有的函数进行修改和操作。runOnFunction 实现内部，创建了 AddressSanitizer 的实例，并调用了其 instrumentFunction(F, TLI) 方法。

class AddressSanitizerLegacyPass : public FunctionPass {
public:
  static char ID;

  explicit AddressSanitizerLegacyPass(
      bool CompileKernel = false, bool Recover = false,
      bool UseAfterScope = false,
      AsanDetectStackUseAfterReturnMode UseAfterReturn =
          AsanDetectStackUseAfterReturnMode::Runtime)
      : FunctionPass(ID), CompileKernel(CompileKernel), Recover(Recover),
        UseAfterScope(UseAfterScope), UseAfterReturn(UseAfterReturn) {
    initializeAddressSanitizerLegacyPassPass(*PassRegistry::getPassRegistry());
  }

  // ...

  bool runOnFunction(Function &F) override {
    GlobalsMetadata &GlobalsMD =
        getAnalysis<ASanGlobalsMetadataWrapperPass>().getGlobalsMD();
    const StackSafetyGlobalInfo *const SSGI =
        ClUseStackSafety
            ? &getAnalysis<StackSafetyGlobalInfoWrapperPass>().getResult()
            : nullptr;
    const TargetLibraryInfo *TLI =
        &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);

    //️ ⬇️️️⬇️⬇️
    AddressSanitizer ASan(*F.getParent(), &GlobalsMD, SSGI, CompileKernel,
                          Recover, UseAfterScope, UseAfterReturn);
    return ASan.instrumentFunction(F, TLI);
  }

AddressSanitizer::instrumentFunction 内容很长，

bool AddressSanitizer::instrumentFunction(Function &F,
                                          const TargetLibraryInfo *TLI) {
  ...

  // We want to instrument every address only once per basic block (unless there
  // are calls between uses).
  SmallPtrSet<Value *, 16> TempsToInstrument;
  SmallVector<InterestingMemoryOperand, 16> OperandsToInstrument;
  SmallVector<MemIntrinsic *, 16> IntrinToInstrument;
  SmallVector<Instruction *, 8> NoReturnCalls;
  SmallVector<BasicBlock *, 16> AllBlocks;
  SmallVector<Instruction *, 16> PointerComparisonsOrSubtracts;


  // Fill the set of memory operations to instrument.
  // 遍历 函数里的每一个 block
  for (auto &BB : F) {
    AllBlocks.push_back(&BB);
    TempsToInstrument.clear();
    int NumInsnsPerBB = 0;

    // 遍历 block 里的每一条指令 (Instruction)
    for (auto &Inst : BB) {
      if (LooksLikeCodeInBug11395(&Inst)) return false;
      SmallVector<InterestingMemoryOperand, 1> InterestingOperands;

      🌟🌟🌟
      // 寻找感兴趣的内存操作数（store/load，那他们的操作数当然也就是内存地址了）
      getInterestingMemoryOperands(&Inst, InterestingOperands);

      if (!InterestingOperands.empty()) {
        for (auto &Operand : InterestingOperands) {
          ...
          // 存到 vector 里
          OperandsToInstrument.push_back(Operand);
          NumInsnsPerBB++;
        }
      }
      ...
    }
  }
  ...
  // Instrument.
  int NumInstrumented = 0;
  for (auto &Operand : OperandsToInstrument) {
    if (!suppressInstrumentationSiteForDebug(NumInstrumented))
      // 对于找到的指令进行修改
      instrumentMop(ObjSizeVis, Operand, UseCalls,
                    F.getParent()->getDataLayout());
    FunctionModified = true;
  }

  ...

  LLVM_DEBUG(dbgs() << "ASAN done instrumenting: " << FunctionModified << " "
                    << F << "\n");

  return FunctionModified;
}

AddressSanitizer::instrumentMop()

Calls

void doInstrumentAddress()

Calls

AddressSanitizer::instrumentAddress() 是插入前面提到的内存判断的地方，函数比较长，这里省略掉不太影响理解的代码。

void AddressSanitizer::instrumentAddress(Instruction *OrigIns,
                                         Instruction *InsertBefore, Value *Addr,
                                         uint32_t TypeSize, bool IsWrite,
                                         Value *SizeArgument, bool UseCalls,
                                         uint32_t Exp) {
  Value *AddrLong = IRB.CreatePointerCast(Addr, IntptrTy);

  Type *ShadowTy =
      IntegerType::get(*C, std::max(8U, TypeSize >> Mapping.Scale));
  Type *ShadowPtrTy = PointerType::get(ShadowTy, 0);

  // 🌟🌟🌟
  Value *ShadowPtr = memToShadow(AddrLong, IRB);
  Value *CmpVal = Constant::getNullValue(ShadowTy);
  Value *ShadowValue =
      IRB.CreateLoad(ShadowTy, IRB.CreateIntToPtr(ShadowPtr, ShadowPtrTy));

  // 🌟🌟🌟
  // 创建比较指令，shadow_value != 0
  Value *Cmp = IRB.CreateICmpNE(ShadowValue, CmpVal);
  size_t Granularity = 1ULL << Mapping.Scale;
  Instruction *CrashTerm = nullptr;

  if (ClAlwaysSlowPath || (TypeSize < 8 * Granularity)) {
    // We use branch weights for the slow path check, to indicate that the slow
    // path is rarely taken. This seems to be the case for SPEC benchmarks.
    Instruction *CheckTerm = SplitBlockAndInsertIfThen(
        Cmp, InsertBefore, false, MDBuilder(*C).createBranchWeights(1, 100000));
    assert(cast<BranchInst>(CheckTerm)->isUnconditional());
    BasicBlock *NextBB = CheckTerm->getSuccessor(0);
    IRB.SetInsertPoint(CheckTerm);

    // 🌟🌟🌟
    // SlowPathCmp
    Value *Cmp2 = createSlowPathCmp(IRB, AddrLong, ShadowValue, TypeSize);
    if (Recover) {
      CrashTerm = SplitBlockAndInsertIfThen(Cmp2, CheckTerm, false);
    } else {
      BasicBlock *CrashBlock =
        BasicBlock::Create(*C, "", NextBB->getParent(), NextBB);
      CrashTerm = new UnreachableInst(*C, CrashBlock);
      BranchInst *NewTerm = BranchInst::Create(CrashBlock, NextBB, Cmp2);
      ReplaceInstWithInst(CheckTerm, NewTerm);
    }
  } else {
    CrashTerm = SplitBlockAndInsertIfThen(Cmp, InsertBefore, !Recover);
  }

  Instruction *Crash = generateCrashCode(CrashTerm, AddrLong, IsWrite,
                                         AccessSizeIndex, SizeArgument, Exp);
  Crash->setDebugLoc(OrigIns->getDebugLoc());
}

Value *AddressSanitizer::createSlowPathCmp()

Value *AddressSanitizer::createSlowPathCmp(IRBuilder<> &IRB, Value *AddrLong,
                                           Value *ShadowValue,
                                           uint32_t TypeSize) {
  size_t Granularity = static_cast<size_t>(1) << Mapping.Scale;
  // Addr & (Granularity - 1)
  Value *LastAccessedByte =
      IRB.CreateAnd(AddrLong, ConstantInt::get(IntptrTy, Granularity - 1));
  // (Addr & (Granularity - 1)) + size - 1
  if (TypeSize / 8 > 1)
    LastAccessedByte = IRB.CreateAdd(
        LastAccessedByte, ConstantInt::get(IntptrTy, TypeSize / 8 - 1));
  // (uint8_t) ((Addr & (Granularity-1)) + size - 1)
  LastAccessedByte =
      IRB.CreateIntCast(LastAccessedByte, ShadowValue->getType(), false);
  // ((uint8_t) ((Addr & (Granularity-1)) + size - 1)) >= ShadowValue
  return IRB.CreateICmpSGE(LastAccessedByte, ShadowValue);
}