Index: tools/llvm-cfi-verify/FileAnalysis.h =================================================================== --- tools/llvm-cfi-verify/FileAnalysis.h +++ tools/llvm-cfi-verify/FileAnalysis.h @@ -79,7 +79,29 @@ const Instr *getPrevInstructionSequential(const Instr &InstrMeta) const; const Instr *getNextInstructionSequential(const Instr &InstrMeta) const; - // Returns the list of indirect instructions. + // Returns whether this instruction is used by CFI to trap the program. + bool isCFITrap(const Instr &InstrMeta) const; + + // Returns whether this function can fall through to the next instruction. + // Undefined (and bad) instructions cannot fall through, and instruction that + // modify the control flow can only fall through if they are conditional + // branches or calls. + bool canFallThrough(const Instr &InstrMeta) const; + + // Returns the definitive next instruction. This is different from the next + // instruction sequentially as it will follow unconditional branches (assuming + // they can be resolved at compile time, i.e. not indirect). This method + // returns nullptr if the provided instruction does not transfer control flow + // to exactly one instruction that is known deterministically at compile time. + // Also returns nullptr if the deterministic target does not exist in this + // file. + const Instr *getDefiniteNextInstruction(const Instr &InstrMeta) const; + + // Get a list of deterministic control flows that lead to the provided + // instruction. This list includes all static control flow cross-references as + // well as the previous instruction if it can fall through. + std::set getControlFlowXRefs(const Instr &InstrMeta) const; + const std::set &getIndirectInstructions() const; const MCRegisterInfo *getRegisterInfo() const; Index: tools/llvm-cfi-verify/FileAnalysis.cpp =================================================================== --- tools/llvm-cfi-verify/FileAnalysis.cpp +++ tools/llvm-cfi-verify/FileAnalysis.cpp @@ -110,6 +110,91 @@ return InstrKV->second; } +bool FileAnalysis::isCFITrap(const Instr &InstrMeta) const { + return MII->getName(InstrMeta.Instruction.getOpcode()) == "TRAP"; +} + +bool FileAnalysis::canFallThrough(const Instr &InstrMeta) const { + if (!InstrMeta.Valid) + return false; + + if (isCFITrap(InstrMeta)) + return false; + + const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode()); + if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo)) + return InstrDesc.isConditionalBranch(); + + return true; +} + +const Instr * +FileAnalysis::getDefiniteNextInstruction(const Instr &InstrMeta) const { + if (!InstrMeta.Valid) + return nullptr; + + if (isCFITrap(InstrMeta)) + return nullptr; + + const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode()); + if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo)) { + if (InstrDesc.isConditionalBranch()) + return nullptr; + + uint64_t Target; + if (!MIA->evaluateBranch(InstrMeta.Instruction, InstrMeta.VMAddress, + InstrMeta.InstructionSize, Target)) + return nullptr; + + const auto &NextKV = Instructions.find(Target); + if (NextKV == Instructions.end()) + return nullptr; + + if (!NextKV->second.Valid) + return nullptr; + + return &NextKV->second; + } + + const auto &NextKV = + Instructions.find(InstrMeta.VMAddress + InstrMeta.InstructionSize); + if (NextKV == Instructions.end()) + return nullptr; + + if (!NextKV->second.Valid) + return nullptr; + + return &NextKV->second; +} + +std::set +FileAnalysis::getControlFlowXRefs(const Instr &InstrMeta) const { + std::set CFCrossReferences; + const Instr *PrevInstruction = getPrevInstructionSequential(InstrMeta); + + if (PrevInstruction && canFallThrough(*PrevInstruction)) + CFCrossReferences.insert(PrevInstruction); + + const auto &TargetRefsKV = StaticBranchTargetings.find(InstrMeta.VMAddress); + if (TargetRefsKV == StaticBranchTargetings.end()) + return CFCrossReferences; + + for (uint64_t SourceInstrAddress : TargetRefsKV->second) { + const auto &SourceInstrKV = Instructions.find(SourceInstrAddress); + if (SourceInstrKV == Instructions.end()) { + errs() << "Failed to find source instruction at address " + << format_hex(SourceInstrAddress, 2) + << " for the cross-reference to instruction at address " + << format_hex(InstrMeta.VMAddress, 2) << ".\n"; + continue; + } + + CFCrossReferences.insert(&SourceInstrKV->second); + } + + return CFCrossReferences; +} + const std::set &FileAnalysis::getIndirectInstructions() const { return IndirectInstructions; } Index: tools/llvm-cfi-verify/unittests/FileAnalysis.cpp =================================================================== --- tools/llvm-cfi-verify/unittests/FileAnalysis.cpp +++ tools/llvm-cfi-verify/unittests/FileAnalysis.cpp @@ -39,6 +39,7 @@ using Instr = ::llvm::cfi_verify::FileAnalysis::Instr; using ::testing::Eq; +using ::testing::Field; namespace llvm { namespace cfi_verify { @@ -199,6 +200,269 @@ EXPECT_EQ(1u, GoodInstrMeta->InstructionSize); } +TEST_F(BasicFileAnalysisTest, CFITrapTest) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0xb0, 0x00, // 1: mov $0x0, %al + 0x48, 0x89, 0xe5, // 3: mov %rsp, %rbp + 0x48, 0x83, 0xec, 0x18, // 6: sub $0x18, %rsp + 0x48, 0xbe, 0xc4, 0x07, 0x40, + 0x00, 0x00, 0x00, 0x00, 0x00, // 10: movabs $0x4007c4, %rsi + 0x2f, // 20: (bad) + 0x41, 0x0e, // 21: rex.B (bad) + 0x62, 0x72, 0x65, 0x61, 0x6b, // 23: (bad) {%k1} + 0x0f, 0x0b // 28: ud2 + }, + 0xDEADBEEF); + + EXPECT_FALSE(Verifier.isCFITrap( + Verifier.getInstructionOrDie(0xDEADBEEF))); + EXPECT_FALSE(Verifier.isCFITrap( + Verifier.getInstructionOrDie(0xDEADBEEF + 3))); + EXPECT_FALSE(Verifier.isCFITrap( + Verifier.getInstructionOrDie(0xDEADBEEF + 6))); + EXPECT_FALSE(Verifier.isCFITrap( + Verifier.getInstructionOrDie(0xDEADBEEF + 10))); + EXPECT_FALSE(Verifier.isCFITrap( + Verifier.getInstructionOrDie(0xDEADBEEF + 20))); + EXPECT_FALSE(Verifier.isCFITrap( + Verifier.getInstructionOrDie(0xDEADBEEF + 21))); + EXPECT_FALSE(Verifier.isCFITrap( + Verifier.getInstructionOrDie(0xDEADBEEF + 23))); + EXPECT_TRUE(Verifier.isCFITrap( + Verifier.getInstructionOrDie(0xDEADBEEF + 28))); +} + +TEST_F(BasicFileAnalysisTest, FallThroughTest) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0xb0, 0x00, // 1: mov $0x0, %al + 0x2f, // 3: (bad) + 0x0f, 0x0b, // 4: ud2 + 0xff, 0x20, // 6: jmpq *(%rax) + 0xeb, 0x00, // 8: jmp +0 + 0xe8, 0x45, 0xfe, 0xff, 0xff, // 10: callq [some loc] + 0xff, 0x10, // 15: callq *(rax) + 0x75, 0x00, // 17: jne +0 + 0xc3, // 19: retq + }, + 0xDEADBEEF); + + EXPECT_TRUE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF))); + EXPECT_TRUE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 1))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 3))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 4))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 6))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 8))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 10))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 15))); + EXPECT_TRUE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 17))); + EXPECT_FALSE( + Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 19))); +} + +TEST_F(BasicFileAnalysisTest, DefiniteNextInstructionTest) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0xb0, 0x00, // 1: mov $0x0, %al + 0x2f, // 3: (bad) + 0x0f, 0x0b, // 4: ud2 + 0xff, 0x20, // 6: jmpq *(%rax) + 0xeb, 0x00, // 8: jmp 10 [+0] + 0xeb, 0x05, // 10: jmp 17 [+5] + 0xe8, 0x00, 0x00, 0x00, 0x00, // 12: callq 17 [+0] + 0xe8, 0x78, 0x56, 0x34, 0x12, // 17: callq 0x1234569f [+0x12345678] + 0xe8, 0x04, 0x00, 0x00, 0x00, // 22: callq 31 [+4] + 0xff, 0x10, // 27: callq *(rax) + 0x75, 0x00, // 29: jne 31 [+0] + 0x75, 0xe0, // 31: jne 1 [-32] + 0xc3, // 33: retq + 0xeb, 0xdd, // 34: jmp 1 [-35] + 0xeb, 0xdd, // 36: jmp 3 [-35] + 0xeb, 0xdc, // 38: jmp 4 [-36] + }, + 0xDEADBEEF); + + const auto *Current = Verifier.getInstruction(0xDEADBEEF); + const auto *Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 1); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 3); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 4); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 6); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 8); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 10, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 10); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 12); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 17); + // Note, definite next instruction address is out of range and should fail. + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Next = Verifier.getDefiniteNextInstruction(*Current); + + Current = Verifier.getInstruction(0xDEADBEEF + 22); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 31, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 27); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Verifier.getInstruction(0xDEADBEEF + 29); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Verifier.getInstruction(0xDEADBEEF + 31); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Verifier.getInstruction(0xDEADBEEF + 33); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 34); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress); + + Current = Verifier.getInstruction(0xDEADBEEF + 36); + EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + + Current = Verifier.getInstruction(0xDEADBEEF + 38); + Next = Verifier.getDefiniteNextInstruction(*Current); + EXPECT_NE(nullptr, Next); + EXPECT_EQ(0xDEADBEEF + 4, Next->VMAddress); +} + +TEST_F(BasicFileAnalysisTest, ControlFlowXRefsTest) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0xb0, 0x00, // 1: mov $0x0, %al + 0x2f, // 3: (bad) + 0x0f, 0x0b, // 4: ud2 + 0xff, 0x20, // 6: jmpq *(%rax) + 0xeb, 0x00, // 8: jmp 10 [+0] + 0xeb, 0x05, // 10: jmp 17 [+5] + 0xe8, 0x00, 0x00, 0x00, 0x00, // 12: callq 17 [+0] + 0xe8, 0x78, 0x56, 0x34, 0x12, // 17: callq 0x1234569f [+0x12345678] + 0xe8, 0x04, 0x00, 0x00, 0x00, // 22: callq 31 [+4] + 0xff, 0x10, // 27: callq *(rax) + 0x75, 0x00, // 29: jne 31 [+0] + 0x75, 0xe0, // 31: jne 1 [-32] + 0xc3, // 33: retq + 0xeb, 0xdd, // 34: jmp 1 [-35] + 0xeb, 0xdd, // 36: jmp 3 [-35] + 0xeb, 0xdc, // 38: jmp 4 [-36] + }, + 0xDEADBEEF); + const auto *InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF); + std::set XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(XRefs.empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 1); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 34)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 3); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 1)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 36)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 4); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 38)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 6); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 8); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 10); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 8)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 12); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 17); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 10)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 12)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 22); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 27); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 29); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 31); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 22)), + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 29)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 33); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_THAT(XRefs, UnorderedElementsAre( + Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31)))); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 34); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 36); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); + + InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 38); + XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); +} + + } // anonymous namespace } // end namespace cfi_verify } // end namespace llvm