Index: tools/llvm-cfi-verify/CMakeLists.txt =================================================================== --- tools/llvm-cfi-verify/CMakeLists.txt +++ tools/llvm-cfi-verify/CMakeLists.txt @@ -13,5 +13,6 @@ add_llvm_tool(llvm-cfi-verify llvm-cfi-verify.cpp + GraphBuilder.cpp FileAnalysis.cpp ) Index: tools/llvm-cfi-verify/GraphBuilder.h =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/GraphBuilder.h @@ -0,0 +1,123 @@ +//===- GraphBuilder.h -------------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CFI_VERIFY_GRAPH_BUILDER_H +#define LLVM_CFI_VERIFY_GRAPH_BUILDER_H + +#include "FileAnalysis.h" + +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/COFF.h" +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" + +#include +#include +#include +#include + +using Instr = llvm::cfi_verify::FileAnalysis::Instr; + +namespace llvm { +namespace cfi_verify { + +extern uint64_t SearchLengthForUndef; +extern uint64_t SearchLengthForConditionalBranch; + +struct ControlFlowNode { + void print(unsigned depth, raw_ostream &os) const; + std::vector flatten() const; + + ControlFlowNode *Next; + uint64_t InstructionAddress; + uint64_t FlowLength; +}; + +struct ConditionalBranchNode { + void print(raw_ostream &os) const; + ControlFlowNode *Target; + ControlFlowNode *Fallthrough; + uint64_t InstructionAddress; + // Does this conditional branch implement CFI successfully? + bool CFIProtection; +}; + +struct GraphResult { + ~GraphResult(); + + uint64_t BaseInstructionAddress; + std::vector BranchNodes; + std::vector OrphanedNodes; +}; + +class GraphBuilder { +public: + // Build the control flow graph for a provided control flow node. This method + // will enumerate all branch nodes that can lead to this node, and provide + // them, fully evaulated, in GraphResult::BranchNodes. It will also provide + // any orphaned (i.e. did not make it to a branch node) flows to the provided + // node in GraphResult::OrphanedNodes. + static GraphResult buildFlowGraph(const FileAnalysis &Analysis, + uint64_t Address); + +private: + // Implementation function that actually builds the flow graph. Retrieves a + // list of cross references to instruction referenced in `Node`. If any of + // these XRefs are conditional branches, it will build the other potential + // path (fallthrough or target) using `buildFlowsToUndefined`. Otherwise, + // this function will recursively call itself where `Node` in the recursive + // call is now the XRef. If any XRef results in an error, the XRef in question + // is added to `OrphanedNodes`. An error is defined as any of the following: + // - The maximum search length `SearchLengthForConditionalBranch` has been + // reached. + // - The XRef cannot be calculated (e.g. it doesn't exist in the Analysis + // object). + // - The graph is cyclic. + static void + buildFlowGraphImpl(const FileAnalysis &Analysis, ControlFlowNode *Node, + std::vector *BranchNodes, + std::vector *OrphanedNodes); + + // Utilised by buildFlowGraphImpl to build the tree out from the provided + // conditional branch node to an undefined instruction. The provided + // conditional branch node must have exactly one of its subtrees set, and will + // update the node's CFIProtection field if a deterministic flow can be found + // to an undefined instruction. + static void buildFlowsToUndefined(const FileAnalysis &Analysis, + ConditionalBranchNode &BranchNode); + + // Creates a control flow node with the information from the parent, and links + // it to the provided child. + static ControlFlowNode *createParentNode(const Instr &ParentMeta, + ControlFlowNode *ChildNode); +}; + +} // end namespace cfi_verify +} // end namespace llvm + +#endif // LLVM_CFI_VERIFY_GRAPH_BUILDER_H Index: tools/llvm-cfi-verify/GraphBuilder.cpp =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/GraphBuilder.cpp @@ -0,0 +1,360 @@ +//===- GraphBuilder.cpp -----------------------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "GraphBuilder.h" + +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/COFF.h" +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/FormatVariadic.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" + +#include + +using Instr = llvm::cfi_verify::FileAnalysis::Instr; + +namespace llvm { +namespace cfi_verify { + +uint64_t SearchLengthForUndef; +uint64_t SearchLengthForConditionalBranch; + +static cl::opt SearchLengthForUndefArg( + "search-length-undef", + cl::desc("Specify the maximum amount of instructions " + "to inspect when searching for an undefined " + "instruction from a conditional branch."), + cl::location(SearchLengthForUndef), cl::init(2)); + +static cl::opt SearchLengthForConditionalBranchArg( + "search-length-cb", + cl::desc("Specify the maximum amount of instructions " + "to inspect when searching for a conditional " + "branch from an indirect control flow."), + cl::location(SearchLengthForConditionalBranch), cl::init(20)); + +void ControlFlowNode::print(unsigned depth, raw_ostream &os) const { + for (unsigned i = 0; i < depth; ++i) + os << " "; + + os << "[" << FlowLength << "] " << format_hex(InstructionAddress, 2) << "\n"; + if (Next) + Next->print(depth + 1, os); +} + +void ConditionalBranchNode::print(raw_ostream &os) const { + os << format_hex(InstructionAddress, 2) << "\n"; + os << " Target:\n"; + if (Target) + Target->print(1, os); + else + os << " ???\n"; + + os << " Fallthrough:\n"; + if (Fallthrough) + Fallthrough->print(1, os); + else + os << " ???\n"; +} + +std::vector ControlFlowNode::flatten() const { + std::vector Addresses; + const ControlFlowNode *Node = this; + while (Node != nullptr) { + Addresses.push_back(Node->InstructionAddress); + Node = Node->Next; + } + return Addresses; +} + +GraphResult::~GraphResult() { + std::set CFNs; + for (const auto &BranchNode : BranchNodes) { + for (ControlFlowNode *FlowNode = BranchNode.Target; FlowNode; + FlowNode = FlowNode->Next) + CFNs.insert(FlowNode); + + for (ControlFlowNode *FlowNode = BranchNode.Fallthrough; FlowNode; + FlowNode = FlowNode->Next) + CFNs.insert(FlowNode); + } + + for (auto &FlowNode : OrphanedNodes) { + while (FlowNode) { + CFNs.insert(FlowNode); + FlowNode = FlowNode->Next; + } + } + + for (const auto &Node : CFNs) + delete Node; +} + +GraphResult GraphBuilder::buildFlowGraph(const FileAnalysis &Analysis, + uint64_t Address) { + GraphResult Result; + Result.BaseInstructionAddress = Address; + + const auto &IndirectInstructions = Analysis.getIndirectInstructions(); + + if (IndirectInstructions.find(Address) == IndirectInstructions.end()) + return Result; + + ControlFlowNode *Node = new ControlFlowNode(); + Node->Next = nullptr; + Node->InstructionAddress = Address; + Node->FlowLength = 0; + + buildFlowGraphImpl(Analysis, Node, &Result.BranchNodes, + &Result.OrphanedNodes); + return Result; +} + +void GraphBuilder::buildFlowsToUndefined(const FileAnalysis &Analysis, + ConditionalBranchNode &BranchNode) { + assert(SearchLengthForUndef > 0 && + "Search length for undefined flow must be greater than zero."); + + // Resolve the metadata for the provided node. + const auto &BranchInstrMetaPtr = + Analysis.getInstruction(BranchNode.InstructionAddress); + if (!BranchInstrMetaPtr) { + errs() << "Failed to build flows from instruction with address" + << format_hex(BranchNode.InstructionAddress, 2) << ".\n"; + return; + } + const auto &BranchInstrMeta = *BranchInstrMetaPtr; + + // Start setting up the next node in the chain. + const Instr *NextMetaPtr; + ControlFlowNode *NextNode = new ControlFlowNode(); + NextNode->Next = nullptr; + NextNode->FlowLength = 1; + + // Find out the next instruction in the chain and add it to the new node. + if (BranchNode.Target && !BranchNode.Fallthrough) { + // We know the target of the branch, find the fallthrough. + NextMetaPtr = Analysis.getNextInstructionSequential(BranchInstrMeta); + if (!NextMetaPtr) { + errs() << "Failed to get next instruction from " + << format_hex(BranchNode.InstructionAddress, 2) << ".\n"; + delete NextNode; + return; + } + + NextNode->InstructionAddress = NextMetaPtr->VMAddress; + BranchNode.Fallthrough = NextNode; // Add the new node to the branch head. + } else if (BranchNode.Fallthrough && !BranchNode.Target) { + // We already know the fallthrough, evaluate the target. + uint64_t Target; + if (!Analysis.getMCInstrAnalysis()->evaluateBranch( + BranchInstrMeta.Instruction, BranchInstrMeta.VMAddress, + BranchInstrMeta.InstructionSize, Target)) { + errs() << "Failed to get branch target for conditional branch at address " + << format_hex(BranchInstrMeta.VMAddress, 2) << ".\n"; + delete NextNode; + return; + } + + // Resolve the meta pointer for the target of this branch. + NextMetaPtr = Analysis.getInstruction(Target); + if (!NextMetaPtr) { + errs() << "Failed to find instruction at address " + << format_hex(Target, 2) << ".\n"; + delete NextNode; + return; + } + + NextNode->InstructionAddress = Target; + BranchNode.Target = NextNode; // Add the new node to the branch head. + } else { + errs() << "ControlBranchNode supplied to buildFlowsToUndefined should " + "provide Target xor Fallthrough.\n"; + delete NextNode; + return; + } + + ControlFlowNode *CurrentNode = NextNode; + const Instr *CurrentMetaPtr = NextMetaPtr; + + // Now the branch head has been set properly, complete the rest of the chain. + for (uint64_t i = 1; i < SearchLengthForUndef; ++i) { + // Check to see whether the chain should die. + if (Analysis.isCFITrap(*CurrentMetaPtr)) { + BranchNode.CFIProtection = true; + return; + } + + // Find the metadata of the next instruction. + NextMetaPtr = Analysis.getDefiniteNextInstruction(*CurrentMetaPtr); + if (!NextMetaPtr) + return; + + // Setup the next node. + NextNode = new ControlFlowNode(); + NextNode->Next = nullptr; + NextNode->InstructionAddress = NextMetaPtr->VMAddress; + NextNode->FlowLength = CurrentNode->FlowLength + 1; + CurrentNode->Next = NextNode; + + // Move the 'current' pointers to the new tail of the chain. + CurrentMetaPtr = NextMetaPtr; + CurrentNode = NextNode; + } + + // Final check of the last thing we added to the chain. + if (Analysis.isCFITrap(*CurrentMetaPtr)) + BranchNode.CFIProtection = true; +} + +ControlFlowNode *GraphBuilder::createParentNode(const Instr &ParentMeta, + ControlFlowNode *ChildNode) { + assert(ChildNode && "Null pointer provided to createParentNode"); + ControlFlowNode *ParentNode = new ControlFlowNode(); + ParentNode->Next = ChildNode; + ParentNode->InstructionAddress = ParentMeta.VMAddress; + ParentNode->FlowLength = ChildNode->FlowLength + 1; + return ParentNode; +} + +void GraphBuilder::buildFlowGraphImpl( + const FileAnalysis &Analysis, ControlFlowNode *ChildNode, + std::vector *BranchNodes, + std::vector *OrphanedNodes) { + assert(ChildNode && BranchNodes && OrphanedNodes && + "Null pointer provided to buildFlowGraphImpl."); + + // If we've exceeded the flow length, terminate. + if (ChildNode->FlowLength >= SearchLengthForConditionalBranch) { + OrphanedNodes->push_back(ChildNode); + return; + } + + // Get the metadata for the node instruction. + const auto &InstrMetaPtr = + Analysis.getInstruction(ChildNode->InstructionAddress); + if (!InstrMetaPtr) { + errs() << "Failed to build flow graph for instruction at address " + << format_hex(ChildNode->InstructionAddress, 2) << ".\n"; + OrphanedNodes->push_back(ChildNode); + return; + } + const auto &ChildMeta = *InstrMetaPtr; + + std::set CFCrossRefs = + Analysis.getDirectControlFlowXRefs(ChildMeta); + + bool HasValidCrossRef = false; + + for (const auto *ParentMetaPtr : CFCrossRefs) { + assert(ParentMetaPtr && "CFCrossRefs returned nullptr."); + const auto &ParentMeta = *ParentMetaPtr; + const auto &ParentDesc = + Analysis.getMCInstrInfo()->get(ParentMeta.Instruction.getOpcode()); + + if (!ParentDesc.mayAffectControlFlow(ParentMeta.Instruction, + *Analysis.getRegisterInfo())) { + // If this cross reference doesn't affect CF, continue the graph. + buildFlowGraphImpl(Analysis, createParentNode(ParentMeta, ChildNode), + BranchNodes, OrphanedNodes); + HasValidCrossRef = true; + continue; + } + + // Evaluate the branch target to ascertain whether this XRef is the result + // of a fallthrough or the target of a branch. + uint64_t BranchTarget; + if (!Analysis.getMCInstrAnalysis()->evaluateBranch( + ParentMeta.Instruction, ParentMeta.VMAddress, + ParentMeta.InstructionSize, BranchTarget)) { + errs() << "Failed to evaluate branch target for instruction at address " + << format_hex(ParentMeta.VMAddress, 2) << ".\n"; + OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode)); + continue; + } + + // Allow unconditional branches to be part of the upwards traversal. + if (ParentDesc.isUnconditionalBranch()) { + // Ensures that the unconditional branch is actually an XRef to the child. + if (BranchTarget != ChildMeta.VMAddress) { + errs() << "Control flow to " << format_hex(ChildMeta.VMAddress, 2) + << ", but target resolution of " + << format_hex(ParentMeta.VMAddress, 2) + << " is not this address?\n"; + OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode)); + continue; + } + + // Stop if this graph is cyclic. + const auto &FlattenedList = ChildNode->flatten(); + if (std::find_if(FlattenedList.begin(), FlattenedList.end(), + [&ParentMeta](const uint64_t &Address) { + return Address == ParentMeta.VMAddress; + }) != FlattenedList.end()) { + OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode)); + continue; + } + + buildFlowGraphImpl(Analysis, createParentNode(ParentMeta, ChildNode), + BranchNodes, OrphanedNodes); + HasValidCrossRef = true; + continue; + } + + // Ensure that any unknown CFs are caught. + if (!ParentDesc.isConditionalBranch()) { + errs() << "Unknown control flow encountered when building graph at " + << format_hex(ChildMeta.VMAddress, 2) << "\n."; + OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode)); + continue; + } + + // Only direct conditional branches should be present at this point. Setup + // a conditional branch node and build flows to the ud2. + ConditionalBranchNode BranchNode; + BranchNode.InstructionAddress = ParentMeta.VMAddress; + BranchNode.Target = nullptr; + BranchNode.Fallthrough = nullptr; + BranchNode.CFIProtection = false; + + if (BranchTarget == ChildMeta.VMAddress) + BranchNode.Target = ChildNode; + else + BranchNode.Fallthrough = ChildNode; + + HasValidCrossRef = true; + buildFlowsToUndefined(Analysis, BranchNode); + BranchNodes->push_back(BranchNode); + } + + if (!HasValidCrossRef) + OrphanedNodes->push_back(ChildNode); +} + +} // namespace cfi_verify +} // namespace llvm Index: tools/llvm-cfi-verify/unittests/CMakeLists.txt =================================================================== --- tools/llvm-cfi-verify/unittests/CMakeLists.txt +++ tools/llvm-cfi-verify/unittests/CMakeLists.txt @@ -11,7 +11,8 @@ Support ) - - add_llvm_unittest(CFIVerifyTests - FileAnalysis.cpp ../FileAnalysis.cpp) + FileAnalysis.cpp + GraphBuilder.cpp + ../GraphBuilder.cpp + ../FileAnalysis.cpp) Index: tools/llvm-cfi-verify/unittests/FileAnalysis.cpp =================================================================== --- tools/llvm-cfi-verify/unittests/FileAnalysis.cpp +++ tools/llvm-cfi-verify/unittests/FileAnalysis.cpp @@ -63,16 +63,16 @@ class BasicFileAnalysisTest : public ::testing::Test { protected: virtual void SetUp() { - if (Verifier.initialiseDisassemblyMembers()) { + if (Analysis.initialiseDisassemblyMembers()) { FAIL() << "Failed to initialise FileAnalysis."; } } - ELFx86TestFileAnalysis Verifier; + ELFx86TestFileAnalysis Analysis; }; TEST_F(BasicFileAnalysisTest, BasicDisassemblyTraversalTest) { - Verifier.parseSectionContents( + Analysis.parseSectionContents( { 0x90, // 0: nop 0xb0, 0x00, // 1: mov $0x0, %al @@ -86,122 +86,122 @@ }, 0xDEADBEEF); - EXPECT_EQ(nullptr, Verifier.getInstruction(0x0)); - EXPECT_EQ(nullptr, Verifier.getInstruction(0x1000)); + EXPECT_EQ(nullptr, Analysis.getInstruction(0x0)); + EXPECT_EQ(nullptr, Analysis.getInstruction(0x1000)); // 0xDEADBEEF: nop - const auto *InstrMeta = Verifier.getInstruction(0xDEADBEEF); + const auto *InstrMeta = Analysis.getInstruction(0xDEADBEEF); EXPECT_NE(nullptr, InstrMeta); EXPECT_EQ(0xDEADBEEF, InstrMeta->VMAddress); EXPECT_EQ(1u, InstrMeta->InstructionSize); EXPECT_TRUE(InstrMeta->Valid); - const auto *NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta); - EXPECT_EQ(nullptr, Verifier.getPrevInstructionSequential(*InstrMeta)); + const auto *NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta); + EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta)); const auto *PrevInstrMeta = InstrMeta; // 0xDEADBEEF + 1: mov $0x0, %al - InstrMeta = Verifier.getInstruction(0xDEADBEEF + 1); + InstrMeta = Analysis.getInstruction(0xDEADBEEF + 1); EXPECT_NE(nullptr, InstrMeta); EXPECT_EQ(NextInstrMeta, InstrMeta); EXPECT_EQ(0xDEADBEEF + 1, InstrMeta->VMAddress); EXPECT_EQ(2u, InstrMeta->InstructionSize); EXPECT_TRUE(InstrMeta->Valid); - NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta); - EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta); + EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta)); PrevInstrMeta = InstrMeta; // 0xDEADBEEF + 3: mov %rsp, %rbp - InstrMeta = Verifier.getInstruction(0xDEADBEEF + 3); + InstrMeta = Analysis.getInstruction(0xDEADBEEF + 3); EXPECT_NE(nullptr, InstrMeta); EXPECT_EQ(NextInstrMeta, InstrMeta); EXPECT_EQ(0xDEADBEEF + 3, InstrMeta->VMAddress); EXPECT_EQ(3u, InstrMeta->InstructionSize); EXPECT_TRUE(InstrMeta->Valid); - NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta); - EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta); + EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta)); PrevInstrMeta = InstrMeta; // 0xDEADBEEF + 6: sub $0x18, %rsp - InstrMeta = Verifier.getInstruction(0xDEADBEEF + 6); + InstrMeta = Analysis.getInstruction(0xDEADBEEF + 6); EXPECT_NE(nullptr, InstrMeta); EXPECT_EQ(NextInstrMeta, InstrMeta); EXPECT_EQ(0xDEADBEEF + 6, InstrMeta->VMAddress); EXPECT_EQ(4u, InstrMeta->InstructionSize); EXPECT_TRUE(InstrMeta->Valid); - NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta); - EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta); + EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta)); PrevInstrMeta = InstrMeta; // 0xDEADBEEF + 10: movabs $0x4007c4, %rsi - InstrMeta = Verifier.getInstruction(0xDEADBEEF + 10); + InstrMeta = Analysis.getInstruction(0xDEADBEEF + 10); EXPECT_NE(nullptr, InstrMeta); EXPECT_EQ(NextInstrMeta, InstrMeta); EXPECT_EQ(0xDEADBEEF + 10, InstrMeta->VMAddress); EXPECT_EQ(10u, InstrMeta->InstructionSize); EXPECT_TRUE(InstrMeta->Valid); - EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta)); - EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta)); + EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta)); PrevInstrMeta = InstrMeta; // 0xDEADBEEF + 20: (bad) - InstrMeta = Verifier.getInstruction(0xDEADBEEF + 20); + InstrMeta = Analysis.getInstruction(0xDEADBEEF + 20); EXPECT_NE(nullptr, InstrMeta); EXPECT_EQ(0xDEADBEEF + 20, InstrMeta->VMAddress); EXPECT_EQ(1u, InstrMeta->InstructionSize); EXPECT_FALSE(InstrMeta->Valid); - EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta)); - EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta)); + EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta)); + EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta)); // 0xDEADBEEF + 21: rex.B (bad) - InstrMeta = Verifier.getInstruction(0xDEADBEEF + 21); + InstrMeta = Analysis.getInstruction(0xDEADBEEF + 21); EXPECT_NE(nullptr, InstrMeta); EXPECT_EQ(0xDEADBEEF + 21, InstrMeta->VMAddress); EXPECT_EQ(2u, InstrMeta->InstructionSize); EXPECT_FALSE(InstrMeta->Valid); - EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta)); - EXPECT_EQ(nullptr, Verifier.getPrevInstructionSequential(*InstrMeta)); + EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta)); + EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta)); // 0xDEADBEEF + 6: (bad) {%k1} - InstrMeta = Verifier.getInstruction(0xDEADBEEF + 23); + InstrMeta = Analysis.getInstruction(0xDEADBEEF + 23); EXPECT_NE(nullptr, InstrMeta); EXPECT_EQ(0xDEADBEEF + 23, InstrMeta->VMAddress); EXPECT_EQ(5u, InstrMeta->InstructionSize); EXPECT_FALSE(InstrMeta->Valid); - EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta)); - EXPECT_EQ(nullptr, Verifier.getPrevInstructionSequential(*InstrMeta)); + EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta)); + EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta)); } TEST_F(BasicFileAnalysisTest, PrevAndNextFromBadInst) { - Verifier.parseSectionContents( + Analysis.parseSectionContents( { 0x90, // 0: nop 0x2f, // 1: (bad) 0x90 // 2: nop }, 0xDEADBEEF); - const auto &BadInstrMeta = Verifier.getInstructionOrDie(0xDEADBEEF + 1); + const auto &BadInstrMeta = Analysis.getInstructionOrDie(0xDEADBEEF + 1); const auto *GoodInstrMeta = - Verifier.getPrevInstructionSequential(BadInstrMeta); + Analysis.getPrevInstructionSequential(BadInstrMeta); EXPECT_NE(nullptr, GoodInstrMeta); EXPECT_EQ(0xDEADBEEF, GoodInstrMeta->VMAddress); EXPECT_EQ(1u, GoodInstrMeta->InstructionSize); - GoodInstrMeta = Verifier.getNextInstructionSequential(BadInstrMeta); + GoodInstrMeta = Analysis.getNextInstructionSequential(BadInstrMeta); EXPECT_NE(nullptr, GoodInstrMeta); EXPECT_EQ(0xDEADBEEF + 2, GoodInstrMeta->VMAddress); EXPECT_EQ(1u, GoodInstrMeta->InstructionSize); } TEST_F(BasicFileAnalysisTest, CFITrapTest) { - Verifier.parseSectionContents( + Analysis.parseSectionContents( { 0x90, // 0: nop 0xb0, 0x00, // 1: mov $0x0, %al @@ -216,25 +216,25 @@ }, 0xDEADBEEF); - EXPECT_FALSE(Verifier.isCFITrap(Verifier.getInstructionOrDie(0xDEADBEEF))); + EXPECT_FALSE(Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF))); EXPECT_FALSE( - Verifier.isCFITrap(Verifier.getInstructionOrDie(0xDEADBEEF + 3))); + Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 3))); EXPECT_FALSE( - Verifier.isCFITrap(Verifier.getInstructionOrDie(0xDEADBEEF + 6))); + Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 6))); EXPECT_FALSE( - Verifier.isCFITrap(Verifier.getInstructionOrDie(0xDEADBEEF + 10))); + Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 10))); EXPECT_FALSE( - Verifier.isCFITrap(Verifier.getInstructionOrDie(0xDEADBEEF + 20))); + Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 20))); EXPECT_FALSE( - Verifier.isCFITrap(Verifier.getInstructionOrDie(0xDEADBEEF + 21))); + Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 21))); EXPECT_FALSE( - Verifier.isCFITrap(Verifier.getInstructionOrDie(0xDEADBEEF + 23))); + Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 23))); EXPECT_TRUE( - Verifier.isCFITrap(Verifier.getInstructionOrDie(0xDEADBEEF + 28))); + Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 28))); } TEST_F(BasicFileAnalysisTest, FallThroughTest) { - Verifier.parseSectionContents( + Analysis.parseSectionContents( { 0x90, // 0: nop 0xb0, 0x00, // 1: mov $0x0, %al @@ -250,29 +250,29 @@ 0xDEADBEEF); EXPECT_TRUE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF))); EXPECT_TRUE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 1))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 1))); EXPECT_FALSE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 3))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 3))); EXPECT_FALSE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 4))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 4))); EXPECT_FALSE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 6))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 6))); EXPECT_FALSE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 8))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 8))); EXPECT_FALSE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 10))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 10))); EXPECT_FALSE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 15))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 15))); EXPECT_TRUE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 17))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 17))); EXPECT_FALSE( - Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 19))); + Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 19))); } TEST_F(BasicFileAnalysisTest, DefiniteNextInstructionTest) { - Verifier.parseSectionContents( + Analysis.parseSectionContents( { 0x90, // 0: nop 0xb0, 0x00, // 1: mov $0x0, %al @@ -294,73 +294,73 @@ }, 0xDEADBEEF); - const auto *Current = Verifier.getInstruction(0xDEADBEEF); - const auto *Next = Verifier.getDefiniteNextInstruction(*Current); + const auto *Current = Analysis.getInstruction(0xDEADBEEF); + const auto *Next = Analysis.getDefiniteNextInstruction(*Current); EXPECT_NE(nullptr, Next); EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress); - Current = Verifier.getInstruction(0xDEADBEEF + 1); - EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Analysis.getInstruction(0xDEADBEEF + 1); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); - Current = Verifier.getInstruction(0xDEADBEEF + 3); - EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Analysis.getInstruction(0xDEADBEEF + 3); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); - Current = Verifier.getInstruction(0xDEADBEEF + 4); - EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Analysis.getInstruction(0xDEADBEEF + 4); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); - Current = Verifier.getInstruction(0xDEADBEEF + 6); - EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Analysis.getInstruction(0xDEADBEEF + 6); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); - Current = Verifier.getInstruction(0xDEADBEEF + 8); - Next = Verifier.getDefiniteNextInstruction(*Current); + Current = Analysis.getInstruction(0xDEADBEEF + 8); + Next = Analysis.getDefiniteNextInstruction(*Current); EXPECT_NE(nullptr, Next); EXPECT_EQ(0xDEADBEEF + 10, Next->VMAddress); - Current = Verifier.getInstruction(0xDEADBEEF + 10); - Next = Verifier.getDefiniteNextInstruction(*Current); + Current = Analysis.getInstruction(0xDEADBEEF + 10); + Next = Analysis.getDefiniteNextInstruction(*Current); EXPECT_NE(nullptr, Next); EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress); - Current = Verifier.getInstruction(0xDEADBEEF + 12); - Next = Verifier.getDefiniteNextInstruction(*Current); + Current = Analysis.getInstruction(0xDEADBEEF + 12); + Next = Analysis.getDefiniteNextInstruction(*Current); EXPECT_NE(nullptr, Next); EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress); - Current = Verifier.getInstruction(0xDEADBEEF + 17); + Current = Analysis.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); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); + Next = Analysis.getDefiniteNextInstruction(*Current); - Current = Verifier.getInstruction(0xDEADBEEF + 22); - Next = Verifier.getDefiniteNextInstruction(*Current); + Current = Analysis.getInstruction(0xDEADBEEF + 22); + Next = Analysis.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); + Current = Analysis.getInstruction(0xDEADBEEF + 27); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); + Current = Analysis.getInstruction(0xDEADBEEF + 29); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); + Current = Analysis.getInstruction(0xDEADBEEF + 31); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); + Current = Analysis.getInstruction(0xDEADBEEF + 33); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); + + Current = Analysis.getInstruction(0xDEADBEEF + 34); + Next = Analysis.getDefiniteNextInstruction(*Current); EXPECT_NE(nullptr, Next); EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress); - Current = Verifier.getInstruction(0xDEADBEEF + 36); - EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current)); + Current = Analysis.getInstruction(0xDEADBEEF + 36); + EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current)); - Current = Verifier.getInstruction(0xDEADBEEF + 38); - Next = Verifier.getDefiniteNextInstruction(*Current); + Current = Analysis.getInstruction(0xDEADBEEF + 38); + Next = Analysis.getDefiniteNextInstruction(*Current); EXPECT_NE(nullptr, Next); EXPECT_EQ(0xDEADBEEF + 4, Next->VMAddress); } TEST_F(BasicFileAnalysisTest, ControlFlowXRefsTest) { - Verifier.parseSectionContents( + Analysis.parseSectionContents( { 0x90, // 0: nop 0xb0, 0x00, // 1: mov $0x0, %al @@ -381,85 +381,85 @@ 0xeb, 0xdc, // 38: jmp 4 [-36] }, 0xDEADBEEF); - const auto *InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF); + const auto *InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF); std::set XRefs = - Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); + Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); EXPECT_TRUE(XRefs.empty()); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 1); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 1); + XRefs = Analysis.getDirectControlFlowXRefs(*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.getDirectControlFlowXRefs(*InstrMetaPtr); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 3); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); EXPECT_THAT(XRefs, UnorderedElementsAre( Field(&Instr::VMAddress, Eq(0xDEADBEEF + 1)), Field(&Instr::VMAddress, Eq(0xDEADBEEF + 36)))); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 4); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 4); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); EXPECT_THAT(XRefs, UnorderedElementsAre( Field(&Instr::VMAddress, Eq(0xDEADBEEF + 38)))); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 6); - EXPECT_TRUE(Verifier.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 6); + EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 8); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); - EXPECT_TRUE(Verifier.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 8); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 10); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 10); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); EXPECT_THAT(XRefs, UnorderedElementsAre( Field(&Instr::VMAddress, Eq(0xDEADBEEF + 8)))); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 12); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); - EXPECT_TRUE(Verifier.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 12); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 17); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 17); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); EXPECT_THAT(XRefs, UnorderedElementsAre( Field(&Instr::VMAddress, Eq(0xDEADBEEF + 10)), Field(&Instr::VMAddress, Eq(0xDEADBEEF + 12)))); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 22); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); - EXPECT_TRUE(Verifier.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 22); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 27); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); - EXPECT_TRUE(Verifier.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 27); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 29); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); - EXPECT_TRUE(Verifier.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 29); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 31); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 31); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); EXPECT_THAT(XRefs, UnorderedElementsAre( Field(&Instr::VMAddress, Eq(0xDEADBEEF + 22)), Field(&Instr::VMAddress, Eq(0xDEADBEEF + 29)))); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 33); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 33); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); EXPECT_THAT(XRefs, UnorderedElementsAre( Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31)))); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 34); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); - EXPECT_TRUE(Verifier.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 34); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 36); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); - EXPECT_TRUE(Verifier.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 36); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); - InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 38); - XRefs = Verifier.getDirectControlFlowXRefs(*InstrMetaPtr); - EXPECT_TRUE(Verifier.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); + InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 38); + XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr); + EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty()); } } // anonymous namespace Index: tools/llvm-cfi-verify/unittests/GraphBuilder.cpp =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/unittests/GraphBuilder.cpp @@ -0,0 +1,502 @@ +//===- llvm/tools/llvm-cfi-verify/unittests/GraphBuilder.cpp --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "../GraphBuilder.h" +#include "../FileAnalysis.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/COFF.h" +#include "llvm/Object/ELFObjectFile.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Support/raw_ostream.h" + +#include + +using Instr = ::llvm::cfi_verify::FileAnalysis::Instr; +using ::testing::Each; +using ::testing::ElementsAre; +using ::testing::Eq; +using ::testing::Field; +using ::testing::IsEmpty; +using ::testing::Property; +using ::testing::SizeIs; + +namespace llvm { +namespace cfi_verify { +// Custom node printers for gtest. +void PrintControlFlowNode(ControlFlowNode *Node, unsigned depth, + ::std::ostream *os) { + for (unsigned i = 0; i < depth; ++i) + *os << " "; + + if (Node == nullptr) { + *os << "nullptr"; + return; + } + + *os << "[" << Node->FlowLength << "] 0x" << std::hex + << Node->InstructionAddress << std::dec; + if (Node->Next) { + *os << "\n"; + PrintControlFlowNode(Node->Next, depth + 1, os); + } +} + +void PrintTo(ControlFlowNode *Node, ::std::ostream *os) { + *os << "\nControl Flow Node:\n"; + PrintControlFlowNode(Node, 0, os); +} + +void PrintTo(ConditionalBranchNode *Node, ::std::ostream *os) { + *os << "\nConditional Branch Node:\n"; + if (Node == nullptr) { + *os << "nullptr"; + return; + } + + *os << "0x" << std::hex << Node->InstructionAddress << std::dec << "\n"; + *os << " Target:\n"; + if (Node->Target) { + PrintControlFlowNode(Node->Target, 1, os); + *os << "\n"; + } else { + *os << " ???\n"; + } + + *os << " Fallthrough:\n"; + if (Node->Fallthrough) { + PrintControlFlowNode(Node->Fallthrough, 1, os); + } else { + *os << " ???"; + } +} + +namespace { +class ELFx86TestFileAnalysis : public FileAnalysis { +public: + ELFx86TestFileAnalysis() + : FileAnalysis(Triple("x86_64--"), SubtargetFeatures()) {} + + // Expose this method publicly for testing. + void parseSectionContents(ArrayRef SectionBytes, + uint64_t SectionAddress) { + FileAnalysis::parseSectionContents(SectionBytes, SectionAddress); + } + + Error initialiseDisassemblyMembers() { + return FileAnalysis::initialiseDisassemblyMembers(); + } +}; + +class BasicGraphBuilderTest : public ::testing::Test { +protected: + virtual void SetUp() { + if (Analysis.initialiseDisassemblyMembers()) { + exit(EXIT_FAILURE); + } + } + + ELFx86TestFileAnalysis Analysis; +}; + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathFallthroughUd2) { + Analysis.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0x0f, 0x0b, // 2: ud2 + 0xff, 0x10, // 4: callq *(%rax) + }, + 0xDEADBEEF); + const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4); + + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(1)); + EXPECT_THAT(Result.BranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT(Result.BranchNodes, + Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress, + Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 2))), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 4)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) { + Analysis.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0xff, 0x10, // 2: callq *(%rax) + 0x0f, 0x0b, // 4: ud2 + }, + 0xDEADBEEF); + const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2); + + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(1)); + EXPECT_THAT(Result.BranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT(Result.BranchNodes, + Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress, + Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 2))), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 4)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) { + Analysis.parseSectionContents( + { + 0x75, 0x03, // 0: jne 5 [+3] + 0x90, // 2: nop + 0xff, 0x10, // 3: callq *(%rax) + 0x0f, 0x0b, // 5: ud2 + 0x75, 0xf9, // 7: jne 2 [-7] + 0x0f, 0x0b, // 9: ud2 + }, + 0xDEADBEEF); + const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3); + + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(2)); + EXPECT_THAT(Result.BranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 5)))))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 7)), + Field( + &ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, ElementsAre(0xDEADBEEF + 9))), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) { + Analysis.parseSectionContents( + { + 0x75, 0x05, // 0: jne 7 [+5] + 0x90, // 2: nop + 0xff, 0x10, // 3: callq *(%rax) + 0x75, 0xfb, // 5: jne 2 [-5] + 0x0f, 0x0b, // 7: ud2 + }, + 0xDEADBEEF); + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3); + + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(2)); + EXPECT_THAT(Result.BranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 7)))))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 5)), + Field( + &ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, ElementsAre(0xDEADBEEF + 7))), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) { + Analysis.parseSectionContents( + { + 0x90, // 0: nop + 0x75, 0xfe, // 1: jne 1 [-2] + }, + 0xDEADBEEF); + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + + Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 1); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + + Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADC0DE); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) { + Analysis.parseSectionContents( + { + 0xeb, 0xfe, // 0: jmp 0 [-2] + 0xff, 0x10, // 2: callq *(%rax) + }, + 0xDEADBEEF); + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2); + EXPECT_THAT(Result.OrphanedNodes, SizeIs(1)); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + EXPECT_THAT(Result.OrphanedNodes, + Contains(AllOf(Field(&ControlFlowNode::InstructionAddress, + Eq(0xDEADBEEF + 2)), + Field(&ControlFlowNode::Next, Eq(nullptr))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) { + Analysis.parseSectionContents( + { + 0x75, 0xfe, // 0: jne 0 [-2] + 0xff, 0x10, // 2: callq *(%rax) + }, + 0xDEADBEEF); + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(1)); + EXPECT_THAT( + Result.BranchNodes, + Each(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(false)), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, ElementsAre(0xDEADBEEF))), + Field(&ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 2)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) { + Analysis.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0xeb, 0xfc, // 2: jmp 0 [-4] + 0xff, 0x10, // 4: callq *(%rax) + }, + 0xDEADBEEF); + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, SizeIs(1)); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 4)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) { + Analysis.parseSectionContents( + { + 0x75, 0x00, // 0: jne 2 [+0] + 0xeb, 0xfc, // 2: jmp 0 [-4] + 0xff, 0x10, // 4: callq *(%rax) + }, + 0xDEADBEEF); + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4); + EXPECT_THAT(Result.OrphanedNodes, SizeIs(1)); + EXPECT_THAT(Result.OrphanedNodes, + Contains(AllOf(Field(&ControlFlowNode::InstructionAddress, + Eq(0xDEADBEEF + 4)), + Field(&ControlFlowNode::Next, Eq(nullptr))))); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) { + Analysis.parseSectionContents( + { + 0x75, 0x06, // 0: jne 8 [+6] + 0x90, // 2: nop + 0x90, // 3: nop + 0x90, // 4: nop + 0x90, // 5: nop + 0xff, 0x10, // 6: callq *(%rax) + 0x0f, 0x0b, // 8: ud2 + }, + 0xDEADBEEF); + uint64_t PrevSearchLengthForConditionalBranch = + SearchLengthForConditionalBranch; + SearchLengthForConditionalBranch = 2; + + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 6); + EXPECT_THAT(Result.OrphanedNodes, SizeIs(1)); + EXPECT_THAT(Result.OrphanedNodes, + Each(Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5, + 0xDEADBEEF + 6)))); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + + SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch; +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) { + Analysis.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0xff, 0x10, // 2: callq *(%rax) + 0x90, // 4: nop + 0x90, // 5: nop + 0x90, // 6: nop + 0x90, // 7: nop + 0x0f, 0x0b, // 8: ud2 + }, + 0xDEADBEEF); + uint64_t PrevSearchLengthForUndef = SearchLengthForUndef; + SearchLengthForUndef = 2; + + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT( + Result.BranchNodes, + Each(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(false)), + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))), + Field(&ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, + ElementsAre(0xDEADBEEF + 2)))))); + + SearchLengthForUndef = PrevSearchLengthForUndef; +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) { + // The following code has this graph (in DOT format): + // digraph G { + // "0" -> "20" + // "0" -> "2" + // "20" -> "21" + // "4" -> "22 (ud2)" + // "21" -> "22 (ud2)" + // "4" -> "6" + // "6" -> "7" + // "2" -> "7" + // "7" -> "8" + // "8" -> "9 (indirect)" + // "13" -> "15 (error)" + // "13" -> "9 (indirect)" + // "11" -> "9 (indirect)" + // } + // Or, in image format: https://i.imgur.com/aX5fCoi.png + + Analysis.parseSectionContents( + { + 0x75, 0x12, // 0: jne 20 [+18] + 0xeb, 0x03, // 2: jmp 7 [+3] + 0x75, 0x10, // 4: jne 22 [+16] + 0x90, // 6: nop + 0x90, // 7: nop + 0x90, // 8: nop + 0xff, 0x10, // 9: callq *(%rax) + 0xeb, 0xfc, // 11: jmp 9 [-4] + 0x75, 0xfa, // 13: jne 9 [-6] + 0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678] + 0x90, // 20: nop + 0x90, // 21: nop + 0x0f, 0x0b, // 22: ud2 + }, + 0x1000); + uint64_t PrevSearchLengthForUndef = SearchLengthForUndef; + SearchLengthForUndef = 5; + + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0x1000 + 9); + + EXPECT_THAT(Result.OrphanedNodes, SizeIs(1)); + EXPECT_THAT(Result.BranchNodes, SizeIs(3)); + + EXPECT_THAT( + Result.OrphanedNodes, + Each(AllOf(Field(&ControlFlowNode::InstructionAddress, Eq(0x1000u + 11)), + Property(&ControlFlowNode::flatten, + ElementsAre(0x1000 + 11, 0x1000 + 9))))); + + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(true)), + Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u)), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, + ElementsAre(0x1000 + 20, 0x1000 + 21, 0x1000 + 22))), + Field(&ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, + ElementsAre(0x1000 + 2, 0x1000 + 7, 0x1000 + 8, + 0x1000 + 9)))))); + + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(true)), + Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u + 4)), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, ElementsAre(0x1000 + 22))), + Field(&ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, + ElementsAre(0x1000 + 6, 0x1000 + 7, 0x1000 + 8, + 0x1000 + 9)))))); + + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(false)), + Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u + 13)), + Field(&ConditionalBranchNode::Target, + Property(&ControlFlowNode::flatten, ElementsAre(0x1000 + 9))), + Field( + &ConditionalBranchNode::Fallthrough, + Property(&ControlFlowNode::flatten, ElementsAre(0x1000 + 15)))))); + + SearchLengthForUndef = PrevSearchLengthForUndef; +} + +} // anonymous namespace +} // end namespace cfi_verify +} // end namespace llvm