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/FileAnalysis.h =================================================================== --- tools/llvm-cfi-verify/FileAnalysis.h +++ tools/llvm-cfi-verify/FileAnalysis.h @@ -103,6 +103,9 @@ std::set getControlFlowXRefs(const Instr &InstrMeta) const; const std::set &getIndirectInstructions() const; + const MCRegisterInfo *getRegisterInfo() const; + const MCInstrInfo *getMCInstrInfo() const; + const MCInstrAnalysis *getMCInstrAnalysis() const; const MCRegisterInfo *getRegisterInfo() const; const MCInstrInfo *getMCInstrInfo() const; Index: tools/llvm-cfi-verify/FileAnalysis.cpp =================================================================== --- tools/llvm-cfi-verify/FileAnalysis.cpp +++ tools/llvm-cfi-verify/FileAnalysis.cpp @@ -199,17 +199,17 @@ return IndirectInstructions; } -const MCRegisterInfo *FileAnalysis::getRegisterInfo() const { +const MCRegisterInfo *FileVerifier::getRegisterInfo() const { return RegisterInfo.get(); } -const MCInstrInfo *FileAnalysis::getMCInstrInfo() const { return MII.get(); } +const MCInstrInfo *FileVerifier::getMCInstrInfo() const { return MII.get(); } -const MCInstrAnalysis *FileAnalysis::getMCInstrAnalysis() const { +const MCInstrAnalysis *FileVerifier::getMCInstrAnalysis() const { return MIA.get(); } -Error FileAnalysis::initialiseDisassemblyMembers() { +Error FileVerifier::initialiseDisassemblyMembers() { std::string TripleName = ObjectTriple.getTriple(); ArchName = ""; MCPU = ""; Index: tools/llvm-cfi-verify/GraphBuilder.h =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/GraphBuilder.h @@ -0,0 +1,114 @@ +//===- 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 "FileVerifier.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::FileVerifier::Instr; + +namespace llvm { +namespace cfi_verify { + +extern uint64_t SearchLengthForUndef; +extern uint64_t SearchLengthForConditionalBranch; + +struct ControlFlowNode { + ControlFlowNode *Next; + uint64_t InstructionAddress; + uint64_t FlowLength; +}; + +struct ConditionalBranchNode { + ControlFlowNode *Target; + ControlFlowNode *Fallthrough; + uint64_t InstructionAddress; + // Does this conditional branch successfully instrument CFI protections. + bool CFIProtection; +}; + +// Print the provided node to standard output. +void printConditionalBranchNode(const ConditionalBranchNode *Node); +void printControlFlowNode(const ControlFlowNode *Node, unsigned depth); +std::vector +flattenControlFlowNodeAddresses(const ControlFlowNode *Node); + +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 FileVerifier &Verifier, + uint64_t Address); + +protected: + // Utilised by buildFlowGraph 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 FileVerifier &Verifier, + 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); + +private: + static void + buildFlowGraphImpl(const FileVerifier &Verifier, ControlFlowNode *Node, + std::vector *BranchNodes, + std::vector *OrphanedNodes); +}; + +} // 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,365 @@ +#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::FileVerifier::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)); + +GraphResult::~GraphResult() { + std::set CFNs; + std::set CBNs; + for (const auto &BranchNode : BranchNodes) { + CBNs.insert(BranchNode); + 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 (const auto &FlowNode : OrphanedNodes) + CFNs.insert(FlowNode); + + for (const auto &Node : CFNs) + delete Node; + + for (const auto &Node : CBNs) + delete Node; +} + +void printControlFlowNode(const ControlFlowNode *Node, unsigned depth) { + assert(Node && "Null pointer provided to printControlFlowNode."); + for (unsigned i = 0; i < depth; ++i) + outs() << " "; + + outs() << "[" << Node->FlowLength << "] " + << format_hex(Node->InstructionAddress, 2) << "\n"; + if (Node->Next) + printControlFlowNode(Node->Next, depth + 1); +} + +void printConditionalBranchNode(const ConditionalBranchNode *Node) { + assert(Node && "Null pointer provided to printConditionalBranchNode."); + outs() << format_hex(Node->InstructionAddress, 2) << "\n"; + outs() << " Target:\n"; + if (Node->Target) + printControlFlowNode(Node->Target, 1); + else + outs() << " ???\n"; + + outs() << " Fallthrough:\n"; + if (Node->Fallthrough) + printControlFlowNode(Node->Fallthrough, 1); + else + outs() << " ???\n"; +} + +std::vector +flattenControlFlowNodeAddresses(const ControlFlowNode *Node) { + std::vector Addresses; + while (Node != nullptr) { + Addresses.push_back(Node->InstructionAddress); + Node = Node->Next; + } + return Addresses; +} + +GraphResult GraphBuilder::buildFlowGraph(const FileVerifier &Verifier, + uint64_t Address) { + GraphResult Result; + Result.BaseInstructionAddress = Address; + + const auto &IndirectInstructions = Verifier.getIndirectInstructions(); + + if (IndirectInstructions.find(Address) == IndirectInstructions.end()) + return Result; + + ControlFlowNode *Node = new ControlFlowNode(); + Node->Next = nullptr; + Node->InstructionAddress = Address; + Node->FlowLength = 0; + + buildFlowGraphImpl(Verifier, Node, &Result.BranchNodes, + &Result.OrphanedNodes); + return Result; +} + +void GraphBuilder::buildFlowsToUndefined(const FileVerifier &Verifier, + ConditionalBranchNode *BranchNode) { + assert(BranchNode && "Null pointer provided to buildFlowsToUndefined."); + assert(SearchLengthForUndef > 0 && + "Search length for undefined flow must be greater than zero."); + + // Resolve the metadata for the provided node. + const auto &BranchInstrMetaPtr = + Verifier.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 = Verifier.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 (!Verifier.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 = Verifier.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 (Verifier.isUndefinedInstruction(*CurrentMetaPtr)) { + BranchNode->CFIProtection = true; + return; + } + + // Find the metadata of the next instruction. + NextMetaPtr = Verifier.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; + + // Finalise ready for the next loop. + CurrentMetaPtr = NextMetaPtr; + CurrentNode = NextNode; + } + + // Final check of the last thing we added to the chain. + if (Verifier.isUndefinedInstruction(*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 FileVerifier &Verifier, 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 = + Verifier.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 = Verifier.getControlFlowXRefs(ChildMeta); + + bool HasValidCrossRef = false; + + for (const auto *ParentMetaPtr : CFCrossRefs) { + assert(ParentMetaPtr && "CFCrossRefs returned nullptr."); + const auto &ParentMeta = *ParentMetaPtr; + const auto &ParentDesc = + Verifier.getMCInstrInfo()->get(ParentMeta.Instruction.getOpcode()); + + if (!ParentDesc.mayAffectControlFlow(ParentMeta.Instruction, + *Verifier.getRegisterInfo())) { + // If this cross reference doesn't affect CF, continue the graph. + buildFlowGraphImpl(Verifier, createParentNode(ParentMeta, ChildNode), + BranchNodes, OrphanedNodes); + HasValidCrossRef = true; + continue; + } else { + // 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 (!Verifier.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. + // Ensures that the unconditional branch is actually an XRef to the child. + if (ParentDesc.isUnconditionalBranch()) { + if (BranchTarget == ChildMeta.VMAddress) { + // Ensure the unconditional branch can't fall back on itself. Check + // the current tree. + bool IsUniqueInTree = true; + for (const auto &InstructionAddressInTree : + flattenControlFlowNodeAddresses(ChildNode)) { + if (InstructionAddressInTree == ParentMeta.VMAddress) { + IsUniqueInTree = false; + break; + } + } + + if (!IsUniqueInTree) { + OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode)); + continue; + } + + ControlFlowNode *NewNode = new ControlFlowNode(); + NewNode->Next = ChildNode; + NewNode->InstructionAddress = ParentMeta.VMAddress; + NewNode->FlowLength = ChildNode->FlowLength + 1; + + buildFlowGraphImpl(Verifier, NewNode, BranchNodes, OrphanedNodes); + HasValidCrossRef = true; + continue; + } else { + 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; + } + } + + // 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 = new ConditionalBranchNode(); + BranchNode->InstructionAddress = ParentMeta.VMAddress; + BranchNode->Target = nullptr; + BranchNode->Fallthrough = nullptr; + BranchNode->CFIProtection = false; + BranchNodes->push_back(BranchNode); + + if (BranchTarget == ChildMeta.VMAddress) + BranchNode->Target = ChildNode; + else + BranchNode->Fallthrough = ChildNode; + + HasValidCrossRef = true; + buildFlowsToUndefined(Verifier, 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 @@ -462,7 +462,6 @@ EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty()); } - } // anonymous namespace } // end namespace cfi_verify } // end namespace llvm Index: tools/llvm-cfi-verify/unittests/GraphBuilder.cpp =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/unittests/GraphBuilder.cpp @@ -0,0 +1,505 @@ +//===- 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 "../FileVerifier.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::FileVerifier::Instr; +using ::testing::Each; +using ::testing::ElementsAre; +using ::testing::Eq; +using ::testing::Field; +using ::testing::IsEmpty; +using ::testing::ResultOf; +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 ELFx86TestFileVerifier : public FileVerifier { +public: + ELFx86TestFileVerifier() + : FileVerifier(Triple("x86_64--"), SubtargetFeatures()) {} + + // Expose this method publicly for testing. + void parseSectionContents(ArrayRef SectionBytes, + uint64_t SectionAddress, StringRef SectionName) { + FileVerifier::parseSectionContents(SectionBytes, SectionAddress, + SectionName); + } + + Error initialiseDisassemblyMembers() { + return FileVerifier::initialiseDisassemblyMembers(); + } +}; + +class BasicGraphBuilderTest : public ::testing::Test { +protected: + virtual void SetUp() { + if (Verifier.initialiseDisassemblyMembers()) { + exit(EXIT_FAILURE); + } + } + + ELFx86TestFileVerifier Verifier; +}; + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathFallthroughUd2) { + Verifier.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0x0f, 0x0b, // 2: ud2 + 0xff, 0x10, // 4: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + const auto Result = GraphBuilder::buildFlowGraph(Verifier, 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, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) { + Verifier.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0xff, 0x10, // 2: callq *(%rax) + 0x0f, 0x0b, // 4: ud2 + }, + 0xDEADBEEF, "Test"); + const auto Result = GraphBuilder::buildFlowGraph(Verifier, 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, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) { + Verifier.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, "Test"); + const auto Result = GraphBuilder::buildFlowGraph(Verifier, 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, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 5)))))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 7)), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 9))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) { + Verifier.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, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 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, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 7)))))); + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 5)), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 7))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) { + Verifier.parseSectionContents( + { + 0x90, // 0: nop + 0x75, 0xfe, // 1: jne 1 [-2] + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + + Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 1); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + + Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADC0DE); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) { + Verifier.parseSectionContents( + { + 0xeb, 0xfe, // 0: jmp 0 [-2] + 0xff, 0x10, // 2: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 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) { + Verifier.parseSectionContents( + { + 0x75, 0xfe, // 0: jne 0 [-2] + 0xff, 0x10, // 2: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 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, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) { + Verifier.parseSectionContents( + { + 0x75, 0x02, // 0: jne 4 [+2] + 0xeb, 0xfc, // 2: jmp 0 [-4] + 0xff, 0x10, // 4: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 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, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4)))))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) { + Verifier.parseSectionContents( + { + 0x75, 0x00, // 0: jne 2 [+0] + 0xeb, 0xfc, // 2: jmp 0 [-4] + 0xff, 0x10, // 4: callq *(%rax) + }, + 0xDEADBEEF, "Test"); + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 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) { + Verifier.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, "Test"); + uint64_t PrevSearchLengthForConditionalBranch = + SearchLengthForConditionalBranch; + SearchLengthForConditionalBranch = 2; + + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 6); + EXPECT_THAT(Result.OrphanedNodes, SizeIs(1)); + EXPECT_THAT(Result.OrphanedNodes, + Each(ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5, + 0xDEADBEEF + 6)))); + EXPECT_THAT(Result.BranchNodes, IsEmpty()); + + SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch; +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) { + Verifier.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, "Test"); + uint64_t PrevSearchLengthForUndef = SearchLengthForUndef; + SearchLengthForUndef = 2; + + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 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, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + 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 + + Verifier.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, "Test"); + uint64_t PrevSearchLengthForUndef = SearchLengthForUndef; + SearchLengthForUndef = 5; + + GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 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)), + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 11, 0x1000 + 9))))); + + EXPECT_THAT( + Result.BranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(true)), + Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u)), + Field(&ConditionalBranchNode::Target, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 20, 0x1000 + 21, 0x1000 + 22))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + 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, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 22))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + 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, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 9))), + Field(&ConditionalBranchNode::Fallthrough, + ResultOf(flattenControlFlowNodeAddresses, + ElementsAre(0x1000 + 15)))))); + + SearchLengthForUndef = PrevSearchLengthForUndef; +} + +} // anonymous namespace +} // end namespace cfi_verify +} // end namespace llvm