Graph builder implementation.

[hctim]

Summary

Implement a localised graph builder for indirect control flow instructions. Main interface is through GraphBuilder::buildFlowGraph, which will build a flow graph around an indirect CF instruction. Various modifications to FileVerifier are also made to const-expose some members needed for machine code analysis done by the graph builder.

[hctim]

Removed comments from CMakeLists.txt

[hctim]

Update to only diff the prev in stack.

[hctim]

Fix various warnings.

[vlad.tsyrklevich]

I'm having difficulty following this because you document what the GraphBuilder methods do but you never say how and I get lost before I figure that out. Maybe that could go in the GraphBuilder.cpp file header comments?

tools/llvm-cfi-verify/GraphBuilder.cpp

1 ↗

(On Diff #117450)

Missing header

tools/llvm-cfi-verify/GraphBuilder.h

49 ↗

(On Diff #117450)

Do these need to be externally visible?

67 ↗

(On Diff #117450)

Should be a method of ConditionalBranchNode (also, prefer to accept a raw_ostream& instead of hardcoding outs() for print methods, dump() typically writes to dbgs() I think)

68 ↗

(On Diff #117450)

ditto

76 ↗

(On Diff #117450)

Why are these pointers?

[hctim]

Merged changes from previous in stack, updated for vlad.tsyrklevich's comments.

[hctim]

Merged wrong CL, putting this back to the way it should be.

[hctim]

Merged changes from upstream.

[hctim]

Updated to fix vlad's comments.

[hctim]

tools/llvm-cfi-verify/GraphBuilder.h

49 ↗

(On Diff #117450)

They're modified by the tests in order to guarantee behaviour, even if the default change.

76 ↗

(On Diff #117450)

Don't want to mix storage (stack/heap) of nodes. Intermediate nodes cannot be stored on stack, as they are neither a branch node or an orphaned node. Consider the following:

[0x0: jmp 2]
       \
  [0x2: jmpq %rax]

0x2 is neither a branch node, nor an orphaned node. The only reference to it is via 0x0, which is a branch node.

Having all these nodes be heap-allocated makes the clean up much easier.

[hctim]

Added header to GraphBuilder.cpp

[hctim]

Backported D38564

[hctim]

format was from prev in stack, put it down there.

[vlad.tsyrklevich]

tools/llvm-cfi-verify/GraphBuilder.cpp

232 ↗

(On Diff #117881)

Reword this.

293 ↗

(On Diff #117881)

Since the if() statement continue;s as the end, place the below without an else statement to avoid nesting (makes it a bit easier to read and understand.)

310 ↗

(On Diff #117881)

Reword 'fall back on itself'

313 ↗

(On Diff #117881)

Replace with std::find_if() ?

326 ↗

(On Diff #117881)

Why not use createParentNode() here?

335 ↗

(On Diff #117881)

Place the error first, and also avoid the nesting here as well.

tools/llvm-cfi-verify/GraphBuilder.h

53 ↗

(On Diff #117881)

just print(

54 ↗

(On Diff #117881)

just flatten(

62 ↗

(On Diff #117881)

just print(

66 ↗

(On Diff #117881)

instrument CFI protection?

104 ↗

(On Diff #117881)

Would be nice to have a comment here that briefly explains the approach (e.g. there are some bits that build the graph backwards and some that build it forwards)

76 ↗

(On Diff #117450)

Would it make sense to just place ConditionalBranchNodes in a vector without dynamically allocating them so they don't have to be manually freed?

[hctim]

Updated with Vlad's comments.

tools/llvm-cfi-verify/GraphBuilder.h

76 ↗

(On Diff #117450)

Yep, done :)

[hctim]

Backported usesRegisterOperand.

[hctim]

Merged updates from stack.

[vlad.tsyrklevich]

tools/llvm-cfi-verify/GraphBuilder.h

75 ↗

(On Diff #118255)

Could we represent this as (1) a uint64_t SrcAddr -> uint64_t DstAddr mapping and (2) a std::vector<uint64_t> of orphaned nodes? Then you would not need the Next pointers, and presumably FlowLength can simply be maintained as an argument to buildFlowGraphImpl(). You could maintain O(1) lookup by using llvm::DenseMap which is hash-table based and lighter-weight than std::map (see http://llvm.org/docs/ProgrammersManual.html#llvm-adt-densemap-h) and that seems cleaner to me than the current structure, WDYT?

[hctim]

Patched in previous changes to unit tests.

[hctim]

Made GraphResult's members automatic storage duration.

[vlad.tsyrklevich]

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

97

Why not just pass this in?

109

s/chain/basic block/?

153

ditto s/chain/basic block/?

155

ditto

177

ditto

197

nit: eliminate braces

228

This is executed here, 240, 253, 260, and 270. Any reason it can't just be done once above? Is it to avoid the ConditionalBranchNode case?

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

58

Could this be reworded? I'm still not sure what it means.

87

Sentence cuts off

95

fully evaluated, or enumerated? Not sure what evaluated might refer to in this context.

109

s/acyclic/cycle/

[vlad.tsyrklevich]

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

63

type: posible

69

It's not all keys, just keys for all valid instructions in that range right?

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

61

Why template it just for std::vector?

132

This is never reached since an unhandled Error (e.g. at destruction time) cause an immediate failure.

454

???

+----------+     +--------------+
|    20    | <-- |      0       |
+----------+     +--------------+
  |                |
  |                |
  v                v
+----------+     +--------------+
|    21    |     |      2       |
+----------+     +--------------+
  |                |
  |                |
  v                v
+----------+     +--------------+
| 22 (ud2) |  +> |      7       |
+----------+  |  +--------------+
  ^           |    |
  |           |    |
  |           |    v
+----------+  |  +--------------+
|    4     |  |  |      8       |
+----------+  |  +--------------+
  |           |    |
  |           |    |
  v           |    v
+----------+  |  +--------------+     +------------+
|    6     | -+  | 9 (indirect) | <-- |     13     |
+----------+     +--------------+     +------------+
                   ^                    |
                   |                    |
                   |                    v
                 +--------------+     +------------+
                 |      11      |     | 15 (error) |
                 +--------------+     +------------+

[hctim]

Updated with Vlad's comments. Also patched the unit tests to succeed when x86 targets are not built, instead of not compiling.

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

109

I've changed them all /s/chain/block. These blocks may contain direct unconditional branches as well :)

228

Yep, don't want to add a conditional branch to IntermediateNodes. I can't really see a good way to not repeat this LOC without introcuding a status variable which results in the same reuse.

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

69

I think it's all keys, each key-value pair is built from the cross-references to the value. Invalid instructions (e.g. an indirect branch) will be an entry in OrphanedNodes, with a key-value pair between the invalid instruction -> its child.

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

61

Was initially using it to print IntermediateNodes (type: DenseMap) as well, now it's just printing vector's I'll remove the templating. Thanks!

454

It's beautiful!

[hctim]

Rebased over master. Forgot to add the unit test patches to this CL.

[vlad.tsyrklevich]

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

70

Could we (1) break the x86 test changes out into a follow-up CL and (2) check the error message to make sure we only skip tests for the specific error message we expect to see? I want to make sure we don't break something else in the future that accidentally disables unit tests without us realizing.

[hctim]

Patched out x86 test changes.

[skatkov]

This patch causes the same unittest compilation failure which was fixed in https://reviews.llvm.org/D39020.

Please fix it asap or revert the patch.

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

17 ↗

(On Diff #119928)

what is the reason you removed this line?

[skatkov]

Actually I took a liberty to submit https://reviews.llvm.org/rL316422 to unblock myself. Feel free to re-write it as you need but please ensure that it does not restore the issue.

tools/llvm-cfi-verify/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   AllTargetsAsmPrinters
   AllTargetsAsmParsers
   AllTargetsDescs
   AllTargetsDisassemblers
   AllTargetsInfos
+  CFIVerify
   MC
   MCParser
   Object
   Support
   )
 
 add_llvm_tool(llvm-cfi-verify
-  llvm-cfi-verify.cpp
-  lib/FileAnalysis.cpp
-  )
+  llvm-cfi-verify.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 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<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. The provided address must be part of this graph, and must not be a
+  // conditional branch.
+  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 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<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,
+                                    const Instr &BranchInstrMeta);
+};
+
+} // 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,
+                                         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<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, ParentMeta);
+    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.
+std::string HexStringifyContainer(const std::vector<uint64_t> &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:
+  //  +----------+      +--------------+
+  //  |    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