Index: tools/llvm-cfi-verify/CMakeLists.txt =================================================================== --- tools/llvm-cfi-verify/CMakeLists.txt +++ tools/llvm-cfi-verify/CMakeLists.txt @@ -4,6 +4,7 @@ AllTargetsDescs AllTargetsDisassemblers AllTargetsInfos + CFIVerify MC MCParser Object @@ -11,8 +12,6 @@ ) add_llvm_tool(llvm-cfi-verify - llvm-cfi-verify.cpp - lib/FileAnalysis.cpp - ) + llvm-cfi-verify.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,7 +1,9 @@ add_library(LLVMCFIVerify STATIC FileAnalysis.cpp - FileAnalysis.h) + FileAnalysis.h + GraphBuilder.cpp + GraphBuilder.h) llvm_update_compile_flags(LLVMCFIVerify) llvm_map_components_to_libnames(libs Index: tools/llvm-cfi-verify/lib/FileAnalysis.h =================================================================== --- tools/llvm-cfi-verify/lib/FileAnalysis.h +++ tools/llvm-cfi-verify/lib/FileAnalysis.h @@ -10,6 +10,7 @@ #ifndef LLVM_CFI_VERIFY_FILE_ANALYSIS_H #define LLVM_CFI_VERIFY_FILE_ANALYSIS_H +#include "llvm/ADT/DenseMap.h" #include "llvm/BinaryFormat/ELF.h" #include "llvm/MC/MCAsmInfo.h" #include "llvm/MC/MCContext.h" @@ -161,7 +162,7 @@ // Contains a mapping between a specific address, and a list of instructions // that use this address as a branch target (including call instructions). - std::unordered_map> StaticBranchTargetings; + DenseMap> StaticBranchTargetings; // A list of addresses of indirect control flow instructions. std::set IndirectInstructions; Index: tools/llvm-cfi-verify/lib/GraphBuilder.h =================================================================== --- /dev/null +++ tools/llvm-cfi-verify/lib/GraphBuilder.h @@ -0,0 +1,133 @@ +//===- 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/ADT/DenseMap.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 ConditionalBranchNode { + uint64_t Address; + uint64_t Target; + uint64_t Fallthrough; + // Does this conditional branch look like it's used for CFI protection? i.e. + // - The exit point of a basic block whos entry point is {target|fallthrough} + // is a CFI trap, and... + // - The exit point of the other basic block is an undirect CF instruction. + bool CFIProtection; +}; + +// The canonical graph result structure returned by GraphBuilder. The members +// in this structure encapsulate all possible code paths to the instruction +// located at `BaseAddress`. +struct GraphResult { + uint64_t BaseAddress; + + // Map between an instruction address, and the address of the next instruction + // that will be executed. This map will contain all keys in the range: + // - [orphaned node, base address) + // - [conditional branch node {target|fallthrough}, base address) + DenseMap IntermediateNodes; + + // A list of orphaned nodes. A node is an 'orphan' if it meets any of the + // following criteria: + // - The length of the path from the base to this node has exceeded + // `SearchLengthForConditionalBranch`. + // - The node has no cross references to it. + // - The path from the base to this node is cyclic. + std::vector OrphanedNodes; + + // A list of top-level conditional branches that exist at the top of any + // non-orphan paths from the base. + std::vector ConditionalBranchNodes; + + // Returns an in-order list of the path between the address provided and the + // base. The provided address must be part of this graph, and must not be a + // conditional branch. + std::vector flattenAddress(uint64_t Address) const; +}; + +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 place them + // into GraphResult::ConditionalBranchNodes. It will also provide any orphaned + // (i.e. the upwards traversal 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 `Address`. 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 `Address` in the recursive call + // is now the XRef. If any XRef is an orphan, it is added to + // `Result.OrphanedNodes`. `OpenedNodes` keeps track of the list of nodes + // in the current path and is used for cycle-checking. If the path is found + // to be cyclic, it will be added to `Result.OrphanedNodes`. + static void buildFlowGraphImpl(const FileAnalysis &Analysis, + DenseSet &OpenedNodes, + GraphResult &Result, uint64_t Address, + uint64_t Depth); + + // 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, + GraphResult &Result, + ConditionalBranchNode &BranchNode, + const Instr &BranchInstrMeta); +}; + +} // 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,291 @@ +//===- 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)); + +std::vector GraphResult::flattenAddress(uint64_t Address) const { + std::vector Addresses; + + auto It = IntermediateNodes.find(Address); + Addresses.push_back(Address); + + while (It != IntermediateNodes.end()) { + Addresses.push_back(It->second); + It = IntermediateNodes.find(It->second); + } + return Addresses; +} + +GraphResult GraphBuilder::buildFlowGraph(const FileAnalysis &Analysis, + uint64_t Address) { + GraphResult Result; + Result.BaseAddress = Address; + DenseSet OpenedNodes; + + const auto &IndirectInstructions = Analysis.getIndirectInstructions(); + + if (IndirectInstructions.find(Address) == IndirectInstructions.end()) + return Result; + + buildFlowGraphImpl(Analysis, OpenedNodes, Result, Address, 0); + return Result; +} + +void GraphBuilder::buildFlowsToUndefined(const FileAnalysis &Analysis, + GraphResult &Result, + ConditionalBranchNode &BranchNode, + const Instr &BranchInstrMeta) { + assert(SearchLengthForUndef > 0 && + "Search length for undefined flow must be greater than zero."); + + // Start setting up the next node in the block. + uint64_t NextAddress = 0; + const Instr *NextMetaPtr; + + // Find out the next instruction in the block 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.Address, 2) << ".\n"; + return; + } + + NextAddress = NextMetaPtr->VMAddress; + BranchNode.Fallthrough = + NextMetaPtr->VMAddress; // 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"; + 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"; + return; + } + + NextAddress = Target; + BranchNode.Target = + NextMetaPtr->VMAddress; // Add the new node to the branch head. + } else { + errs() << "ControlBranchNode supplied to buildFlowsToUndefined should " + "provide Target xor Fallthrough.\n"; + return; + } + + uint64_t CurrentAddress = NextAddress; + const Instr *CurrentMetaPtr = NextMetaPtr; + + // Now the branch head has been set properly, complete the rest of the block. + for (uint64_t i = 1; i < SearchLengthForUndef; ++i) { + // Check to see whether the block 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. + NextAddress = NextMetaPtr->VMAddress; + + // Add this as an intermediate. + Result.IntermediateNodes[CurrentAddress] = NextAddress; + + // Move the 'current' pointers to the new tail of the block. + CurrentMetaPtr = NextMetaPtr; + CurrentAddress = NextAddress; + } + + // Final check of the last thing we added to the block. + if (Analysis.isCFITrap(*CurrentMetaPtr)) + BranchNode.CFIProtection = true; +} + +void GraphBuilder::buildFlowGraphImpl(const FileAnalysis &Analysis, + DenseSet &OpenedNodes, + GraphResult &Result, uint64_t Address, + uint64_t Depth) { + // If we've exceeded the flow length, terminate. + if (Depth >= SearchLengthForConditionalBranch) { + Result.OrphanedNodes.push_back(Address); + return; + } + + // Ensure this flow is acyclic. + if (OpenedNodes.count(Address)) + Result.OrphanedNodes.push_back(Address); + + // If this flow is already explored, stop here. + if (Result.IntermediateNodes.count(Address)) + return; + + // Get the metadata for the node instruction. + const auto &InstrMetaPtr = Analysis.getInstruction(Address); + if (!InstrMetaPtr) { + errs() << "Failed to build flow graph for instruction at address " + << format_hex(Address, 2) << ".\n"; + Result.OrphanedNodes.push_back(Address); + return; + } + const auto &ChildMeta = *InstrMetaPtr; + + OpenedNodes.insert(Address); + 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, OpenedNodes, Result, ParentMeta.VMAddress, + Depth + 1); + Result.IntermediateNodes[ParentMeta.VMAddress] = Address; + 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"; + Result.IntermediateNodes[ParentMeta.VMAddress] = Address; + Result.OrphanedNodes.push_back(ParentMeta.VMAddress); + 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 != Address) { + errs() << "Control flow to " << format_hex(Address, 2) + << ", but target resolution of " + << format_hex(ParentMeta.VMAddress, 2) + << " is not this address?\n"; + Result.IntermediateNodes[ParentMeta.VMAddress] = Address; + Result.OrphanedNodes.push_back(ParentMeta.VMAddress); + continue; + } + + buildFlowGraphImpl(Analysis, OpenedNodes, Result, ParentMeta.VMAddress, + Depth + 1); + Result.IntermediateNodes[ParentMeta.VMAddress] = Address; + HasValidCrossRef = true; + continue; + } + + // Ensure that any unknown CFs are caught. + if (!ParentDesc.isConditionalBranch()) { + errs() << "Unknown control flow encountered when building graph at " + << format_hex(Address, 2) << "\n."; + Result.IntermediateNodes[ParentMeta.VMAddress] = Address; + Result.OrphanedNodes.push_back(ParentMeta.VMAddress); + 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.Address = ParentMeta.VMAddress; + BranchNode.Target = 0; + BranchNode.Fallthrough = 0; + BranchNode.CFIProtection = false; + + if (BranchTarget == Address) + BranchNode.Target = Address; + else + BranchNode.Fallthrough = Address; + + HasValidCrossRef = true; + buildFlowsToUndefined(Analysis, Result, BranchNode, ParentMeta); + Result.ConditionalBranchNodes.push_back(BranchNode); + } + + if (!HasValidCrossRef) + Result.OrphanedNodes.push_back(Address); + + OpenedNodes.erase(Address); +} + +} // 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 @@ -4,15 +4,13 @@ AllTargetsDescs AllTargetsDisassemblers AllTargetsInfos + CFIVerify MC MCParser Object Support ) -list(FIND LLVM_TARGETS_TO_BUILD "X86" x86_idx) -if (NOT x86_idx LESS 0) - add_llvm_unittest(CFIVerifyTests - FileAnalysis.cpp) - target_link_libraries(CFIVerifyTests LLVMCFIVerify) -endif() +add_llvm_unittest(CFIVerifyTests + FileAnalysis.cpp + GraphBuilder.cpp) Index: unittests/tools/llvm-cfi-verify/FileAnalysis.cpp =================================================================== --- unittests/tools/llvm-cfi-verify/FileAnalysis.cpp +++ unittests/tools/llvm-cfi-verify/FileAnalysis.cpp @@ -63,15 +63,22 @@ class BasicFileAnalysisTest : public ::testing::Test { protected: virtual void SetUp() { - if (Analysis.initialiseDisassemblyMembers()) { - FAIL() << "Failed to initialise FileAnalysis."; + SuccessfullyInitialised = true; + if (auto Err = Analysis.initialiseDisassemblyMembers()) { + handleAllErrors(std::move(Err), [](const ErrorInfoBase &E) {}); + SuccessfullyInitialised = false; + outs() << "Note: CFIVerifyTests are disabled due to lack of x86 support " + "on this build.\n"; } } + bool SuccessfullyInitialised; ELFx86TestFileAnalysis Analysis; }; TEST_F(BasicFileAnalysisTest, BasicDisassemblyTraversalTest) { + if (!SuccessfullyInitialised) + return; Analysis.parseSectionContents( { 0x90, // 0: nop @@ -180,6 +187,8 @@ } TEST_F(BasicFileAnalysisTest, PrevAndNextFromBadInst) { + if (!SuccessfullyInitialised) + return; Analysis.parseSectionContents( { 0x90, // 0: nop @@ -201,6 +210,8 @@ } TEST_F(BasicFileAnalysisTest, CFITrapTest) { + if (!SuccessfullyInitialised) + return; Analysis.parseSectionContents( { 0x90, // 0: nop @@ -234,6 +245,8 @@ } TEST_F(BasicFileAnalysisTest, FallThroughTest) { + if (!SuccessfullyInitialised) + return; Analysis.parseSectionContents( { 0x90, // 0: nop @@ -272,6 +285,8 @@ } TEST_F(BasicFileAnalysisTest, DefiniteNextInstructionTest) { + if (!SuccessfullyInitialised) + return; Analysis.parseSectionContents( { 0x90, // 0: nop @@ -360,6 +375,8 @@ } TEST_F(BasicFileAnalysisTest, ControlFlowXRefsTest) { + if (!SuccessfullyInitialised) + return; Analysis.parseSectionContents( { 0x90, // 0: nop Index: unittests/tools/llvm-cfi-verify/GraphBuilder.cpp =================================================================== --- /dev/null +++ unittests/tools/llvm-cfi-verify/GraphBuilder.cpp @@ -0,0 +1,583 @@ +//===- llvm/unittests/llvm-cfi-verify/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 +#include + +using Instr = ::llvm::cfi_verify::FileAnalysis::Instr; +using ::testing::AllOf; +using ::testing::Each; +using ::testing::ElementsAre; +using ::testing::Eq; +using ::testing::Field; +using ::testing::IsEmpty; +using ::testing::Matches; +using ::testing::Pair; +using ::testing::PrintToString; +using ::testing::Property; +using ::testing::SizeIs; +using ::testing::UnorderedElementsAre; +using ::testing::Value; + +namespace llvm { +namespace cfi_verify { +// Printing helpers for gtest. +std::string HexStringifyContainer(const std::vector &C) { + std::stringstream Stream; + if (C.empty()) { + return "{ }"; + } + + Stream << "{ "; + const auto &LastElemIt = std::end(C) - 1; + + for (auto It = std::begin(C); It != LastElemIt; ++It) { + Stream << "0x" << std::hex << *It << ", "; + } + Stream << "0x" << std::hex << *LastElemIt << " }"; + return Stream.str(); +} + +void PrintTo(const ConditionalBranchNode &BranchNode, ::std::ostream *os) { + *os << "ConditionalBranchNode"; +} + +void PrintTo(const GraphResult &Result, ::std::ostream *os) { + *os << "Result BaseAddress: 0x" << std::hex << Result.BaseAddress << "\n"; + + if (Result.ConditionalBranchNodes.empty()) + *os << " (No conditional branch nodes)\n"; + + for (const auto &Node : Result.ConditionalBranchNodes) { + *os << " "; + PrintTo(Node, os); + *os << "\n Fallthrough Path: " << std::hex + << HexStringifyContainer(Result.flattenAddress(Node.Fallthrough)) + << "\n"; + *os << " Target Path: " << std::hex + << HexStringifyContainer(Result.flattenAddress(Node.Target)) << "\n"; + } + + if (Result.OrphanedNodes.empty()) + *os << " (No orphaned nodes)"; + + for (const auto &Orphan : Result.OrphanedNodes) { + *os << " Orphan (0x" << std::hex << Orphan + << ") Path: " << HexStringifyContainer(Result.flattenAddress(Orphan)) + << "\n"; + } +} + +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() { + SuccessfullyInitialised = true; + if (auto Err = Analysis.initialiseDisassemblyMembers()) { + handleAllErrors(std::move(Err), [](const ErrorInfoBase &E) {}); + SuccessfullyInitialised = false; + outs() << "Note: CFIVerifyTests are disabled due to lack of x86 support " + "on this build.\n"; + } + } + + bool SuccessfullyInitialised; + ELFx86TestFileAnalysis Analysis; +}; + +MATCHER_P2(HasPath, Result, Matcher, "has path " + PrintToString(Matcher)) { + const auto &Path = Result.flattenAddress(arg); + *result_listener << "the path is " << PrintToString(Path); + return Matches(Matcher)(Path); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathFallthroughUd2) { + if (!SuccessfullyInitialised) + return; + 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.ConditionalBranchNodes, SizeIs(1)); + EXPECT_THAT(Result.ConditionalBranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains(AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 4))), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 2)))))) + << PrintToString(Result); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) { + if (!SuccessfullyInitialised) + return; + 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.ConditionalBranchNodes, SizeIs(1)); + EXPECT_THAT(Result.ConditionalBranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains(AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 4))), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 2)))))) + << PrintToString(Result); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) { + if (!SuccessfullyInitialised) + return; + 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.ConditionalBranchNodes, SizeIs(2)); + EXPECT_THAT(Result.ConditionalBranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 5)))))) + << PrintToString(Result); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 7)), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 9))), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3)))))) + << PrintToString(Result); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) { + if (!SuccessfullyInitialised) + return; + 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.ConditionalBranchNodes, SizeIs(2)); + EXPECT_THAT(Result.ConditionalBranchNodes, + Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true)))); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 7)))))) + << PrintToString(Result); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 7))), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3)))))) + << PrintToString(Result); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) { + if (!SuccessfullyInitialised) + return; + 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.ConditionalBranchNodes, IsEmpty()); + + Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 1); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty()); + + Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADC0DE); + EXPECT_THAT(Result.OrphanedNodes, IsEmpty()); + EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty()); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) { + if (!SuccessfullyInitialised) + return; + Analysis.parseSectionContents( + { + 0xeb, 0xfe, // 0: jmp 0 [-2] + 0xff, 0x10, // 2: callq *(%rax) + }, + 0xDEADBEEF); + GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2); + EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty()); + EXPECT_THAT(Result.OrphanedNodes, ElementsAre(0xDEADBEEF + 2)); + EXPECT_THAT(Result.IntermediateNodes, IsEmpty()); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) { + if (!SuccessfullyInitialised) + return; + 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.ConditionalBranchNodes, SizeIs(1)); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Each(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF))), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 2)))))) + << PrintToString(Result); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) { + if (!SuccessfullyInitialised) + return; + 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.ConditionalBranchNodes, SizeIs(1)); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains( + AllOf(Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 4)))))) + << PrintToString(Result); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) { + if (!SuccessfullyInitialised) + return; + 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, ElementsAre(0xDEADBEEF + 4)); + EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty()); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) { + if (!SuccessfullyInitialised) + return; + 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(HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5, + 0xDEADBEEF + 6)))) + << PrintToString(Result); + EXPECT_THAT(Result.ConditionalBranchNodes, IsEmpty()); + + SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch; +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) { + if (!SuccessfullyInitialised) + return; + 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.ConditionalBranchNodes, + Each(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(false)), + Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 2)))))) + << PrintToString(Result); + + SearchLengthForUndef = PrevSearchLengthForUndef; +} + +// This test ensures when avoiding doing repeated work we still generate the +// paths correctly. We don't need to recalculate the flow from 0x2 -> 0x3 as it +// should only need to be generated once. +TEST_F(BasicGraphBuilderTest, BuildFlowGraphWithRepeatedWork) { + if (!SuccessfullyInitialised) + return; + 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.ConditionalBranchNodes, SizeIs(2)); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(true)), + Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF)), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 7))), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3)))))) + << PrintToString(Result); + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(true)), + Field(&ConditionalBranchNode::Address, Eq(0xDEADBEEF + 5)), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0xDEADBEEF + 7)))))) + << PrintToString(Result); + EXPECT_THAT(Result.IntermediateNodes, SizeIs(1)); + EXPECT_THAT(Result.IntermediateNodes, + UnorderedElementsAre(Pair(0xDEADBEEF + 2, 0xDEADBEEF + 3))); +} + +TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) { + if (!SuccessfullyInitialised) + return; + // The following code has this graph: + // +----------+ +--------------+ + // | 20 | <--- | 0 | + // +----------+ +--------------+ + // | | + // v v + // +----------+ +--------------+ + // | 21 | | 2 | + // +----------+ +--------------+ + // | | + // v v + // +----------+ +--------------+ + // | 22 (ud2) | +-> | 7 | + // +----------+ | +--------------+ + // ^ | | + // | | v + // +----------+ | +--------------+ + // | 4 | | | 8 | + // +----------+ | +--------------+ + // | | | + // v | v + // +----------+ | +--------------+ +------------+ + // | 6 | -+ | 9 (indirect) | <- | 13 | + // +----------+ +--------------+ +------------+ + // ^ | + // | v + // +--------------+ +------------+ + // | 11 | | 15 (error) | + // +--------------+ +------------+ + // 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.ConditionalBranchNodes, SizeIs(3)); + + EXPECT_THAT( + Result.OrphanedNodes, + Each(AllOf(Eq(0x1000u + 11), + HasPath(Result, ElementsAre(0x1000 + 11, 0x1000 + 9))))) + << PrintToString(Result); + + EXPECT_THAT(Result.ConditionalBranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(true)), + Field(&ConditionalBranchNode::Address, Eq(0x1000u)), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0x1000 + 20, 0x1000 + 21, + 0x1000 + 22))), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0x1000 + 2, 0x1000 + 7, + 0x1000 + 8, 0x1000 + 9)))))) + << PrintToString(Result); + + EXPECT_THAT(Result.ConditionalBranchNodes, + Contains(AllOf( + Field(&ConditionalBranchNode::CFIProtection, Eq(true)), + Field(&ConditionalBranchNode::Address, Eq(0x1000u + 4)), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0x1000 + 22))), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0x1000 + 6, 0x1000 + 7, + 0x1000 + 8, 0x1000 + 9)))))) + << PrintToString(Result); + + EXPECT_THAT( + Result.ConditionalBranchNodes, + Contains(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)), + Field(&ConditionalBranchNode::Address, Eq(0x1000u + 13)), + Field(&ConditionalBranchNode::Target, + HasPath(Result, ElementsAre(0x1000 + 9))), + Field(&ConditionalBranchNode::Fallthrough, + HasPath(Result, ElementsAre(0x1000 + 15)))))) + << PrintToString(Result); + + SearchLengthForUndef = PrevSearchLengthForUndef; +} + +} // anonymous namespace +} // end namespace cfi_verify +} // end namespace llvm