Index: tools/llvm-cfi-verify/CMakeLists.txt =================================================================== --- tools/llvm-cfi-verify/CMakeLists.txt +++ tools/llvm-cfi-verify/CMakeLists.txt @@ -13,6 +13,7 @@ add_llvm_tool(llvm-cfi-verify llvm-cfi-verify.cpp lib/FileAnalysis.cpp + lib/GraphBuilder.cpp ) add_subdirectory(lib) Index: tools/llvm-cfi-verify/lib/CMakeLists.txt =================================================================== --- tools/llvm-cfi-verify/lib/CMakeLists.txt +++ tools/llvm-cfi-verify/lib/CMakeLists.txt @@ -1,6 +1,8 @@ add_llvm_library(LLVMCFIVerify FileAnalysis.cpp FileAnalysis.h + GraphBuilder.cpp + GraphBuilder.h LINK_COMPONENTS MC Index: tools/llvm-cfi-verify/lib/GraphBuilder.h =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/lib/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/lib/GraphBuilder.cpp =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/lib/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: unittests/tools/llvm-cfi-verify/CMakeLists.txt =================================================================== --- unittests/tools/llvm-cfi-verify/CMakeLists.txt +++ unittests/tools/llvm-cfi-verify/CMakeLists.txt @@ -12,4 +12,5 @@ ) add_llvm_unittest(CFIVerifyTests - FileAnalysis.cpp) + FileAnalysis.cpp + GraphBuilder.cpp) Index: unittests/tools/llvm-cfi-verify/GraphBuilder.cpp =================================================================== --- /dev/null +++ unittests/tools/llvm-cfi-verify/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 "../tools/llvm-cfi-verify/lib/GraphBuilder.h" +#include "../tools/llvm-cfi-verify/lib/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