cfi1

[hctim]

Summary

cfi2

cfi3

fixed warnings

Fixed unsigned warnings from gtest.

Fixed gtest unsigned/signed warnings.

Fix gtest unsigned/signed warnings.

Remove useless drop_front.

/s/FileVerifier/FileAnalysis, removed Instr::SectionName, other comments from vlad.tsyrklevich

Merge branch 'master' into cfi1

Merged cfi1

/s/FileVerifier/FileAnalysis

/s/Bad/!Valid

Fixed unconditional jump to invalid instruction.

Merged prev in stack.

Added file header.

Merge branch 'cfi1' into cfi2

Merge branch 'cfi2' into cfi3

vlad's comments

Added GraphBuilder.cpp header

Backported D38564

clang format

clang format

Vlad's comments round #2

Merge branch 'cfi1' into cfi2

Update from Vlad's comments

Merged cfi2

Vlad's comments.

backported usesRegisterOperand

Merged cfi1

Merge branch 'cfi2' into cfi3

Changed addInstruction to assert on duplicate instructions.

Merge branch 'cfi1' into cfi2

Merge branch 'cfi2' into cfi3

Moved unittests out of tools, and into /trunk/unittests. Resolved all the build targets.

Updated assertion to not unused variable warn when assert(..) is disabled.

/s/Verifier/Analysis

clang-format over everything

Merged cfi1

Merged cfi1

Merged cfi2.

Merge cfi2 #2.

Started refactor on GraphResult

GraphResult now is fully on-stack

Merged master

Fixed header for GraphBuilder unit tests.

Merge branch 'master' into cfi3

Added default true.

tools/llvm-cfi-verify/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   AllTargetsAsmPrinters
   AllTargetsAsmParsers
   AllTargetsDescs
   AllTargetsDisassemblers
   AllTargetsInfos
   MC
   MCParser
   Object
   Support
   )
 
 add_llvm_tool(llvm-cfi-verify
   llvm-cfi-verify.cpp
   lib/FileAnalysis.cpp
+  lib/GraphBuilder.cpp
   )
 
 add_subdirectory(lib)

tools/llvm-cfi-verify/lib/CMakeLists.txt

 add_llvm_library(LLVMCFIVerify
   FileAnalysis.cpp
   FileAnalysis.h
+  GraphBuilder.cpp
+  GraphBuilder.h
 
   LINK_COMPONENTS
   MC
   MCParser
   Object
   Support)

tools/llvm-cfi-verify/lib/FileAnalysis.h

 //===- FileAnalysis.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_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"
 #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"
private:
   std::unique_ptr<MCInstPrinter> Printer;
 
   // A mapping between the virtual memory address to the instruction metadata
   // struct.
   std::map<uint64_t, Instr> Instructions;
 
   // 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<uint64_t, std::vector<uint64_t>> StaticBranchTargetings;
+  DenseMap<uint64_t, std::vector<uint64_t>> StaticBranchTargetings;
 
   // A list of addresses of indirect control flow instructions.
   std::set<uint64_t> IndirectInstructions;
 };
 
 class UnsupportedDisassembly : public ErrorInfo<UnsupportedDisassembly> {
 public:
   static char ID;

tools/llvm-cfi-verify/lib/GraphBuilder.h

+//===- 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 <functional>
+#include <set>
+#include <string>
+#include <unordered_map>
+
+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 implement CFI successfully?
+  bool CFIProtection;
+};
+
+// The canonical graph result structure returned by GraphBuilder. The members
+// in this structure encapsulate all posible 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<uint64_t, uint64_t> 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<uint64_t> OrphanedNodes;
+
+  // A list of top-level conditional branches that exist at the top of any
+  // non-orphan paths from the base.
+  std::vector<ConditionalBranchNode> ConditionalBranchNodes;
+
+  // Returns an in-order list of the path between the address provided and the
+  // base. This function is only valid for
+  std::vector<uint64_t> 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 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 `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 acyclic-checking. If the path is found
+  // to be cyclic, it will be added to `Result.OrphanedNodes`.
+  static void buildFlowGraphImpl(const FileAnalysis &Analysis,
+                                 DenseSet<uint64_t> &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);
+};
+
+} // end namespace cfi_verify
+} // end namespace llvm
+
+#endif // LLVM_CFI_VERIFY_GRAPH_BUILDER_H

tools/llvm-cfi-verify/lib/GraphBuilder.cpp

+//===- 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 <functional>
+
+using Instr = llvm::cfi_verify::FileAnalysis::Instr;
+
+namespace llvm {
+namespace cfi_verify {
+
+uint64_t SearchLengthForUndef;
+uint64_t SearchLengthForConditionalBranch;
+
+static cl::opt<uint64_t, true> 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<uint64_t, true> 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<uint64_t> GraphResult::flattenAddress(uint64_t Address) const {
+  std::vector<uint64_t> 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<uint64_t> 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) {
+  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.Address);
+  if (!BranchInstrMetaPtr) {
+    errs() << "Failed to build flows from instruction with address"
+           << format_hex(BranchNode.Address, 2) << ".\n";
+    return;
+  }
+  const auto &BranchInstrMeta = *BranchInstrMetaPtr;
+
+  // Start setting up the next node in the chain.
+  uint64_t NextAddress = 0;
+  const Instr *NextMetaPtr;
+
+  // 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.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 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.
+    NextAddress = NextMetaPtr->VMAddress;
+
+    // Add this as an intermediate.
+    Result.IntermediateNodes[CurrentAddress] = NextAddress;
+
+    // Move the 'current' pointers to the new tail of the chain.
+    CurrentMetaPtr = NextMetaPtr;
+    CurrentAddress = NextAddress;
+  }
+
+  // Final check of the last thing we added to the chain.
+  if (Analysis.isCFITrap(*CurrentMetaPtr))
+    BranchNode.CFIProtection = true;
+}
+
+void GraphBuilder::buildFlowGraphImpl(const FileAnalysis &Analysis,
+                                      DenseSet<uint64_t> &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<const Instr *> 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);
+    Result.ConditionalBranchNodes.push_back(BranchNode);
+  }
+
+  if (!HasValidCrossRef)
+    Result.OrphanedNodes.push_back(Address);
+
+  OpenedNodes.erase(Address);
+}
+
+} // namespace cfi_verify
+} // namespace llvm

unittests/tools/llvm-cfi-verify/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   AllTargetsAsmPrinters
   AllTargetsAsmParsers
   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)
-endif()
+    FileAnalysis.cpp
+    GraphBuilder.cpp)

unittests/tools/llvm-cfi-verify/FileAnalysis.cpp

public:
   Error initialiseDisassemblyMembers() {
     return FileAnalysis::initialiseDisassemblyMembers();
   }
 };
 
 class BasicFileAnalysisTest : public ::testing::Test {
 protected:
   virtual void SetUp() {
+    SuccessfullyInitialised = true;
     if (Analysis.initialiseDisassemblyMembers()) {
-      FAIL() << "Failed to initialise FileAnalysis.";
+      SuccessfullyInitialised = false;
     }
   }
 
+  bool SuccessfullyInitialised;
   ELFx86TestFileAnalysis Analysis;
 };
 
 TEST_F(BasicFileAnalysisTest, BasicDisassemblyTraversalTest) {
+  if (!SuccessfullyInitialised)
+    return;
   Analysis.parseSectionContents(
       {
           0x90,                   // 0: nop
           0xb0, 0x00,             // 1: mov $0x0, %al
           0x48, 0x89, 0xe5,       // 3: mov %rsp, %rbp
           0x48, 0x83, 0xec, 0x18, // 6: sub $0x18, %rsp
           0x48, 0xbe, 0xc4, 0x07, 0x40,
           0x00, 0x00, 0x00, 0x00, 0x00, // 10: movabs $0x4007c4, %rsi
TEST_F(BasicFileAnalysisTest, BasicDisassemblyTraversalTest) {
   EXPECT_EQ(5u, InstrMeta->InstructionSize);
   EXPECT_FALSE(InstrMeta->Valid);
 
   EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta));
   EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta));
 }
 
 TEST_F(BasicFileAnalysisTest, PrevAndNextFromBadInst) {
+  if (!SuccessfullyInitialised)
+    return;
   Analysis.parseSectionContents(
       {
           0x90, // 0: nop
           0x2f, // 1: (bad)
           0x90  // 2: nop
       },
       0xDEADBEEF);
   const auto &BadInstrMeta = Analysis.getInstructionOrDie(0xDEADBEEF + 1);
   const auto *GoodInstrMeta =
       Analysis.getPrevInstructionSequential(BadInstrMeta);
   EXPECT_NE(nullptr, GoodInstrMeta);
   EXPECT_EQ(0xDEADBEEF, GoodInstrMeta->VMAddress);
   EXPECT_EQ(1u, GoodInstrMeta->InstructionSize);
 
   GoodInstrMeta = Analysis.getNextInstructionSequential(BadInstrMeta);
   EXPECT_NE(nullptr, GoodInstrMeta);
   EXPECT_EQ(0xDEADBEEF + 2, GoodInstrMeta->VMAddress);
   EXPECT_EQ(1u, GoodInstrMeta->InstructionSize);
 }
 
 TEST_F(BasicFileAnalysisTest, CFITrapTest) {
+  if (!SuccessfullyInitialised)
+    return;
   Analysis.parseSectionContents(
       {
           0x90,                   // 0: nop
           0xb0, 0x00,             // 1: mov $0x0, %al
           0x48, 0x89, 0xe5,       // 3: mov %rsp, %rbp
           0x48, 0x83, 0xec, 0x18, // 6: sub $0x18, %rsp
           0x48, 0xbe, 0xc4, 0x07, 0x40,
           0x00, 0x00, 0x00, 0x00, 0x00, // 10: movabs $0x4007c4, %rsi
EXPECT_FALSE(
       Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 21)));
   EXPECT_FALSE(
       Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 23)));
   EXPECT_TRUE(
       Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 28)));
 }
 
 TEST_F(BasicFileAnalysisTest, FallThroughTest) {
+  if (!SuccessfullyInitialised)
+    return;
   Analysis.parseSectionContents(
       {
           0x90,                         // 0: nop
           0xb0, 0x00,                   // 1: mov $0x0, %al
           0x2f,                         // 3: (bad)
           0x0f, 0x0b,                   // 4: ud2
           0xff, 0x20,                   // 6: jmpq *(%rax)
           0xeb, 0x00,                   // 8: jmp +0
EXPECT_FALSE(
       Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 15)));
   EXPECT_TRUE(
       Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 17)));
   EXPECT_FALSE(
       Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 19)));
 }
 
 TEST_F(BasicFileAnalysisTest, DefiniteNextInstructionTest) {
+  if (!SuccessfullyInitialised)
+    return;
   Analysis.parseSectionContents(
       {
           0x90,                         // 0: nop
           0xb0, 0x00,                   // 1: mov $0x0, %al
           0x2f,                         // 3: (bad)
           0x0f, 0x0b,                   // 4: ud2
           0xff, 0x20,                   // 6: jmpq *(%rax)
           0xeb, 0x00,                   // 8: jmp 10 [+0]
TEST_F(BasicFileAnalysisTest, DefiniteNextInstructionTest) {
 
   Current = Analysis.getInstruction(0xDEADBEEF + 38);
   Next = Analysis.getDefiniteNextInstruction(*Current);
   EXPECT_NE(nullptr, Next);
   EXPECT_EQ(0xDEADBEEF + 4, Next->VMAddress);
 }
 
 TEST_F(BasicFileAnalysisTest, ControlFlowXRefsTest) {
+  if (!SuccessfullyInitialised)
+    return;
   Analysis.parseSectionContents(
       {
           0x90,                         // 0: nop
           0xb0, 0x00,                   // 1: mov $0x0, %al
           0x2f,                         // 3: (bad)
           0x0f, 0x0b,                   // 4: ud2
           0xff, 0x20,                   // 6: jmpq *(%rax)
           0xeb, 0x00,                   // 8: jmp 10 [+0]

unittests/tools/llvm-cfi-verify/GraphBuilder.cpp

+//===- 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 <cstdlib>
+#include <sstream>
+
+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.
+template <typename Container>
+std::string HexStringifyContainer(const Container &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<Address: 0x" << std::hex << BranchNode.Address
+      << ", Target: 0x" << BranchNode.Target << ", Fallthrough: 0x"
+      << BranchNode.Fallthrough
+      << ", CFIProtection: " << BranchNode.CFIProtection << ">";
+}
+
+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<uint8_t> 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 (Analysis.initialiseDisassemblyMembers()) {
+      SuccessfullyInitialised = false;
+    }
+  }
+
+  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 (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.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