Add FileVerifier::isCFIProtected().

[hctim]

Summary

Add a CFI protection check that is implemented by building a graph and inspecting the output to deduce if the indirect CF instruction is CFI protected. Also added the output of this instruction to printIndirectInstructions().

[hctim]

Update to only diff with prev in stack.

[hctim]

Fixed warnings.

[vlad.tsyrklevich]

On a mechanical note, you should add -U999999 to your git diff options to include full files in the diff (makes scrolling below/above added/removed lines possible in the web view)

tools/llvm-cfi-verify/FileVerifier.cpp

102

This is checked in two different places, might be worth having a helper function?

112

This would be a surprising reason to see 'Protected? No.' Perhaps worth making this an enum return value with no/yes/could-not-be-determined?

[hctim]

Fixed issues from Vlad's comments.

[hctim]

tools/llvm-cfi-verify/FileVerifier.cpp

112

I'm not sure it would be surprising. Orphaned nodes are those which have no static cross-references to them, meaning the control flow graph dies with them.

[0x0: ud2]                   [0x1000: movb $0x1, %rax]
    |                               |
[0x1: nop] <-----------------[0x1002: callq %rax]
    |
[0x2: jmpq %rax]

In this example, the graph starts at 0x2, building up to 0x1. There are no xrefs to 0x1 (as 0x0 cannot fall through, and 0x1002's target is non-static), and hence 0x1 is added as an "orphaned node".

My assumption is that, in order for an indirect CF to be CFI protected, all possible ways to reach the indirect CF must be CFI protected. If a vcall then immediately makes another vcall without CFI checking (emulated in the example above), shouldn't it be flagged?

You have a better understanding of this than me though, feel free to correct me :)

[hctim]

Backported D38564

[hctim]

clang-format

[hctim]

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

[vlad.tsyrklevich]

tools/llvm-cfi-verify/FileAnalysis.cpp

168 ↗

(On Diff #118112)

Place this in the first CL where you can also use it.

tools/llvm-cfi-verify/FileAnalysis.h

72 ↗

(On Diff #118112)

isCFIProtectedIndirectBranch ?

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

35

Only print this line for indirect branches?

[hctim]

Updated from Vlad's comments.

[hctim]

tools/llvm-cfi-verify/FileAnalysis.h

72 ↗

(On Diff #118112)

Related to https://reviews.llvm.org/D38379#inline-337653.

Covers indirect calls as well, LMK if you want this change.

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

35

Related to https://reviews.llvm.org/D38379#inline-337653.

This currently only prints indirect calls + jumps. Should this be changed?

[hctim]

Merged updates from stack.

[vlad.tsyrklevich]

tools/llvm-cfi-verify/FileAnalysis.h

72 ↗

(On Diff #118112)

How about isIndirectInstructionCFIProtected() ?

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

35

Ah, I just mis-read the loop condition here.

[hctim]

Vlad's comments & merged changes from the stack.

[hctim]

Added successful initialisation checks.

[hctim]

Patched in changes from master.

[hctim]

Merged master in preparation for submission.

tools/llvm-cfi-verify/CMakeLists.txt

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

tools/llvm-cfi-verify/FileVerifier.h

+//===- FileVerifier.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_VERIFIER_H
+#define LLVM_CFI_VERIFY_FILE_VERIFIER_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>
+
+namespace llvm {
+namespace cfi_verify {
+
+// This class is used to verify CFI instrumentation of a single file.
+class FileVerifier {
+public:
+  // A metadata struct for an instruction.
+  struct Instr {
+    uint64_t VMAddress;       // Virtual memory address of this instruction.
+    MCInst Instruction;       // Instruction.
+    uint64_t InstructionSize; // Size of this instruction.
+    std::string SectionName;  // Section this instruction is found in.
+    bool Bad; // Is this instruction bad (in which case, Instr::Instruction is
+              // invalid).
+  };
+
+  // Construct a FileVerifier from a file path.
+  static Expected<FileVerifier> Create(StringRef Filename);
+
+  // Construct and take ownership of the supplied object. Do not use this
+  // constructor, prefer to use FileVerifier::Create instead.
+  FileVerifier(object::OwningBinary<object::Binary> Binary);
+  FileVerifier() = delete;
+  FileVerifier(const FileVerifier &) = delete;
+  FileVerifier(FileVerifier &&Other) = default;
+
+  Error printIndirectCFInstructions() const;
+
+  // Check whether the provided instruction is CFI protected in this file.
+  // Returns false if this instruction doesn't exist in this file, if it's not
+  // an indirect control flow instruction, or isn't CFI protected. Returns true
+  // otherwise.
+  bool isCFIProtected(uint64_t Address) const;
+
+  // Returns the instruction at the provided address. Returns nullptr if there
+  // is no instruction at the provided address.
+  const Instr *getInstruction(uint64_t Address) const;
+
+  // Returns the instruction at the provided adress, dying if the instruction is
+  // not found.
+  const Instr &getInstructionOrDie(uint64_t Address) const;
+
+  // Returns a pointer to the previous/next instruction in sequence,
+  // respectively. Retusn nullptr if the next/prev instruction doesn't exist, or
+  // if the provided instruction doesn't exist.
+  const Instr *getPrevInstructionSequential(const Instr &InstrMeta) const;
+  const Instr *getNextInstructionSequential(const Instr &InstrMeta) const;
+
+  // Returns whether this instruction is an undefined instruction (used in
+  // branch-to-undefined CFI protections).
+  bool isUndefinedInstruction(const Instr &InstrMeta) const;
+
+  // Returns whether this function can fall through to the next instruction.
+  // Undefined (and bad) instructions cannot fall through, and instruction that
+  // modify the control flow can only flow through if they are conditional
+  // branches or calls.
+  bool canFallThrough(const Instr &InstrMeta) const;
+
+  // Returns the definitive next instruction. This is different from the next
+  // instruction sequantially as it will follow unconditional branches (assuming
+  // they can be resolved at compile time, i.e. not indirect). This instruction
+  // returns nullptr if the provided instruction does not transfer control flow
+  // to exactly one instruction that is known deterministically at compile time.
+  // Also returns nullptr if the deterministic target does not exist in this
+  // file.
+  const Instr *getDefiniteNextInstruction(const Instr &InstrMeta) const;
+
+  // Get a list of deterministic control flows that lead to the provided
+  // instruction. This list includes all static control flow cross-references as
+  // well as the previous instruction if it can fall through.
+  std::set<const Instr *> getControlFlowXRefs(const Instr &InstrMeta) const;
+
+  const std::set<uint64_t> &getIndirectInstructions() const;
+  const MCRegisterInfo *getRegisterInfo() const;
+  const MCInstrInfo *getMCInstrInfo() const;
+  const MCInstrAnalysis *getMCInstrAnalysis() const;
+
+protected:
+  // Construct a blank object with the provided triple and features. Used in
+  // testing, where a sub class will dependency inject protected methods to
+  // allow analysis of raw binary, without requiring a fully valid ELF file.
+  FileVerifier(const Triple &ObjectTriple, const SubtargetFeatures &Features);
+
+  // Add an instruction to this object.
+  void addInstruction(const Instr &Instruction);
+
+  // Disassemble and parse the provided bytes into this object. Instruction
+  // address calculation is done relative to the provided SectionAddress, and
+  // instruction metadata is populated with the given section name.
+  void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                            uint64_t SectionAddress, StringRef SectionName);
+
+  // Constructs and initialises members required for disassembly.
+  Error initialiseDisassemblyMembers();
+
+  // Parses code sections from the internal object file. Saves them into the
+  // internal members. Should only be called once by Create().
+  Error parseCodeSections();
+
+private:
+  // Members that describe the input file.
+  object::OwningBinary<object::Binary> Binary;
+  const object::ObjectFile *Object = nullptr;
+  Triple ObjectTriple;
+  std::string ArchName;
+  std::string MCPU;
+  const Target *ObjectTarget = nullptr;
+  SubtargetFeatures Features;
+
+  // Members required for disassembly.
+  std::unique_ptr<const MCRegisterInfo> RegisterInfo;
+  std::unique_ptr<const MCAsmInfo> AsmInfo;
+  std::unique_ptr<MCSubtargetInfo> SubtargetInfo;
+  std::unique_ptr<const MCInstrInfo> MII;
+  MCObjectFileInfo MOFI;
+  std::unique_ptr<MCContext> Context;
+  std::unique_ptr<const MCDisassembler> Disassembler;
+  std::unique_ptr<const MCInstrAnalysis> MIA;
+  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;
+
+  // A list of addresses of indirect control flow instructions.
+  std::set<uint64_t> IndirectInstructions;
+};
+
+class UnsupportedDisassembly : public ErrorInfo<UnsupportedDisassembly> {
+public:
+  static char ID;
+
+  void log(raw_ostream &OS) const override;
+  std::error_code convertToErrorCode() const override;
+};
+
+} // namespace cfi_verify
+} // namespace llvm
+
+#endif // LLVM_CFI_VERIFY_FILE_VERIFIER_H

tools/llvm-cfi-verify/FileVerifier.cpp

+#include "FileVerifier.h"
+#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::FileVerifier::Instr;
+
+namespace llvm {
+namespace cfi_verify {
+
+Expected<FileVerifier> FileVerifier::Create(StringRef Filename) {
+  // Open the filename provided.
+  Expected<object::OwningBinary<object::Binary>> BinaryOrErr =
+      object::createBinary(Filename);
+  if (!BinaryOrErr)
+    return BinaryOrErr.takeError();
+
+  // Construct the object and allow it to take ownership of the binary.
+  object::OwningBinary<object::Binary> Binary = std::move(BinaryOrErr.get());
+  FileVerifier Verifier(std::move(Binary));
+
+  Verifier.Object = dyn_cast<object::ObjectFile>(Verifier.Binary.getBinary());
+  if (!Verifier.Object)
+    return make_error<UnsupportedDisassembly>();
+
+  Verifier.ObjectTriple = Verifier.Object->makeTriple();
+  Verifier.Features = Verifier.Object->getFeatures();
+
+  // Init the rest of the object.
+  auto InitResponse = Verifier.initialiseDisassemblyMembers();
+  if (InitResponse)
+    return std::move(InitResponse);
+
+  auto SectionParseResponse = Verifier.parseCodeSections();
+  if (SectionParseResponse)
+    return std::move(SectionParseResponse);
+
+  return std::move(Verifier);
+}
+
+FileVerifier::FileVerifier(object::OwningBinary<object::Binary> Binary)
+    : Binary(std::move(Binary)) {}
+
+FileVerifier::FileVerifier(const Triple &ObjectTriple,
+                           const SubtargetFeatures &Features)
+    : ObjectTriple(ObjectTriple), Features(Features) {}
+
+Error FileVerifier::printIndirectCFInstructions() const {
+  for (const auto &Address : IndirectInstructions) {
+    const auto &InstructionKV = Instructions.find(Address);
+    if (InstructionKV == Instructions.end())
+      return make_error<StringError>(
+          formatv("No instruction found at address {0:x}", Address),
+          inconvertibleErrorCode());
+
+    const auto &InstrMeta = InstructionKV->second;
+    outs() << format_hex(Address, 2) << " [" << InstrMeta.SectionName
+           << "] = " << MII->getName(InstrMeta.Instruction.getOpcode()) << " ";
+    InstrMeta.Instruction.print(outs());
+    outs() << "\n";
+    outs() << "  Protected? " << isCFIProtected(Address) << "\n";
+  }
+
+  return Error::success();
+}
+
+bool FileVerifier::isCFIProtected(uint64_t Address) const {
+  const Instr *InstrMetaPtr = getInstruction(Address);
+  if (!InstrMetaPtr)
+    return false;
+
+  const auto &InstrDesc = MII->get(InstrMetaPtr->Instruction.getOpcode());
+
+  if (!InstrDesc.mayAffectControlFlow(InstrMetaPtr->Instruction, *RegisterInfo))
+    return false;
+
+  bool UsesRegisterOperand = false;
+  for (const auto &Operand : InstrMetaPtr->Instruction)
+    if (Operand.isReg())
+      UsesRegisterOperand = true;
+
+  if (!UsesRegisterOperand)
+    return false;
+
+  auto Flows = GraphBuilder::buildFlowGraph(*this, Address);
+
+  if (!Flows.OrphanedNodes.empty())
+    return false;
+
+  for (const auto &BranchNode : Flows.BranchNodes) {
+    assert(BranchNode && "Branch node contained nullptr.");
+    if (!BranchNode->CFIProtection)
+      return false;
+  }
+
+  return true;
+}
+
+const Instr *
+FileVerifier::getPrevInstructionSequential(const Instr &InstrMeta) const {
+  std::map<uint64_t, Instr>::const_iterator KV =
+      Instructions.find(InstrMeta.VMAddress);
+  if (KV == Instructions.end() || KV == Instructions.begin())
+    return nullptr;
+
+  if ((--KV)->second.Bad)
+    return nullptr;
+
+  return &KV->second;
+}
+
+const Instr *
+FileVerifier::getNextInstructionSequential(const Instr &InstrMeta) const {
+  std::map<uint64_t, Instr>::const_iterator KV =
+      Instructions.find(InstrMeta.VMAddress);
+
+  if (KV++ == Instructions.end() || KV == Instructions.end())
+    return nullptr;
+
+  if (KV->second.Bad)
+    return nullptr;
+
+  return &KV->second;
+}
+
+const Instr *FileVerifier::getInstruction(uint64_t Address) const {
+  const auto &InstrKV = Instructions.find(Address);
+  if (InstrKV == Instructions.end())
+    return nullptr;
+
+  return &InstrKV->second;
+}
+
+const Instr &FileVerifier::getInstructionOrDie(uint64_t Address) const {
+  const auto &InstrKV = Instructions.find(Address);
+  assert(InstrKV != Instructions.end() && "Address doesn't exist.");
+  return InstrKV->second;
+}
+
+bool FileVerifier::isUndefinedInstruction(const Instr &InstrMeta) const {
+  return MII->getName(InstrMeta.Instruction.getOpcode()) == "TRAP";
+}
+
+bool FileVerifier::canFallThrough(const Instr &InstrMeta) const {
+  if (InstrMeta.Bad)
+    return false;
+
+  if (isUndefinedInstruction(InstrMeta))
+    return false;
+
+  const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
+  if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo))
+    return InstrDesc.isConditionalBranch();
+
+  return true;
+}
+
+const Instr *
+FileVerifier::getDefiniteNextInstruction(const Instr &InstrMeta) const {
+  if (InstrMeta.Bad)
+    return nullptr;
+
+  if (isUndefinedInstruction(InstrMeta))
+    return nullptr;
+
+  const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
+  if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo)) {
+    if (InstrDesc.isConditionalBranch())
+      return nullptr;
+
+    uint64_t Target;
+    if (!MIA->evaluateBranch(InstrMeta.Instruction, InstrMeta.VMAddress,
+                             InstrMeta.InstructionSize, Target))
+      return nullptr;
+
+    const auto &NextKV = Instructions.find(Target);
+    if (NextKV == Instructions.end())
+      return nullptr;
+
+    return &NextKV->second;
+  }
+
+  const auto &NextKV =
+      Instructions.find(InstrMeta.VMAddress + InstrMeta.InstructionSize);
+  if (NextKV == Instructions.end())
+    return nullptr;
+
+  if (NextKV->second.Bad)
+    return nullptr;
+
+  return &NextKV->second;
+}
+
+std::set<const Instr *>
+FileVerifier::getControlFlowXRefs(const Instr &InstrMeta) const {
+  std::set<const Instr *> CFCrossReferences;
+  const Instr *PrevInstruction = getPrevInstructionSequential(InstrMeta);
+
+  if (PrevInstruction && canFallThrough(*PrevInstruction))
+    CFCrossReferences.insert(PrevInstruction);
+
+  const auto &TargetRefsKV = StaticBranchTargetings.find(InstrMeta.VMAddress);
+  if (TargetRefsKV == StaticBranchTargetings.end())
+    return CFCrossReferences;
+
+  for (uint64_t SourceInstrAddress : TargetRefsKV->second) {
+    const auto &SourceInstrKV = Instructions.find(SourceInstrAddress);
+    if (SourceInstrKV == Instructions.end()) {
+      errs() << "Failed to find source instruction at address "
+             << format_hex(SourceInstrAddress, 2)
+             << " for the cross-reference to instruction at address "
+             << format_hex(InstrMeta.VMAddress, 2) << ".\n";
+      continue;
+    }
+
+    CFCrossReferences.insert(&SourceInstrKV->second);
+  }
+
+  return CFCrossReferences;
+}
+
+const std::set<uint64_t> &FileVerifier::getIndirectInstructions() const {
+  return IndirectInstructions;
+}
+
+const MCRegisterInfo *FileVerifier::getRegisterInfo() const {
+  return RegisterInfo.get();
+}
+
+const MCInstrInfo *FileVerifier::getMCInstrInfo() const { return MII.get(); }
+
+const MCInstrAnalysis *FileVerifier::getMCInstrAnalysis() const {
+  return MIA.get();
+}
+
+Error FileVerifier::initialiseDisassemblyMembers() {
+  std::string TripleName = ObjectTriple.getTriple();
+  ArchName = "";
+  MCPU = "";
+
+  std::string ErrorString;
+
+  ObjectTarget =
+      TargetRegistry::lookupTarget(ArchName, ObjectTriple, ErrorString);
+
+  if (!ObjectTarget)
+    return make_error<StringError>(Twine("Couldn't find target \"") +
+                                       ObjectTriple.getTriple() +
+                                       "\", failed with error: " + ErrorString,
+                                   inconvertibleErrorCode());
+
+  RegisterInfo.reset(ObjectTarget->createMCRegInfo(TripleName));
+  if (!RegisterInfo)
+    return make_error<StringError>("Failed to initialise RegisterInfo.",
+                                   inconvertibleErrorCode());
+
+  AsmInfo.reset(ObjectTarget->createMCAsmInfo(*RegisterInfo, TripleName));
+  if (!AsmInfo)
+    return make_error<StringError>("Failed to initialise AsmInfo.",
+                                   inconvertibleErrorCode());
+
+  SubtargetInfo.reset(ObjectTarget->createMCSubtargetInfo(
+      TripleName, MCPU, Features.getString()));
+  if (!SubtargetInfo)
+    return make_error<StringError>("Failed to initialise SubtargetInfo.",
+                                   inconvertibleErrorCode());
+
+  MII.reset(ObjectTarget->createMCInstrInfo());
+  if (!MII)
+    return make_error<StringError>("Failed to initialise MII.",
+                                   inconvertibleErrorCode());
+
+  Context.reset(new MCContext(AsmInfo.get(), RegisterInfo.get(), &MOFI));
+
+  Disassembler.reset(
+      ObjectTarget->createMCDisassembler(*SubtargetInfo, *Context));
+
+  if (!Disassembler)
+    return make_error<StringError>("No disassembler available for target",
+                                   inconvertibleErrorCode());
+
+  MIA.reset(ObjectTarget->createMCInstrAnalysis(MII.get()));
+
+  Printer.reset(ObjectTarget->createMCInstPrinter(
+      ObjectTriple, AsmInfo->getAssemblerDialect(), *AsmInfo, *MII,
+      *RegisterInfo));
+
+  return Error::success();
+}
+
+Error FileVerifier::parseCodeSections() {
+  for (const object::SectionRef &Section : Object->sections()) {
+    // Ensure only executable sections get analysed.
+    if (!(object::ELFSectionRef(Section).getFlags() & ELF::SHF_EXECINSTR))
+      continue;
+
+    StringRef SectionContents;
+    if (Section.getContents(SectionContents))
+      return make_error<StringError>("Failed to retrieve section contents",
+                                     inconvertibleErrorCode());
+
+    StringRef SectionName;
+    if (Section.getName(SectionName))
+      SectionName = "UNKNOWN";
+
+    ArrayRef<uint8_t> SectionBytes((const uint8_t *)SectionContents.data(),
+                                   Section.getSize());
+    parseSectionContents(SectionBytes, Section.getAddress(), SectionName);
+  }
+  return Error::success();
+}
+
+void FileVerifier::parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                                        uint64_t SectionAddress,
+                                        StringRef SectionName) {
+  MCInst Instruction;
+  Instr InstrMeta;
+  uint64_t InstructionSize;
+
+  for (uint64_t Byte = 0; Byte < SectionBytes.size();) {
+    bool BadInstruction = false;
+
+    SectionBytes.drop_front(Byte);
+
+    // Disassemble the instruction.
+    if (Disassembler->getInstruction(Instruction, InstructionSize,
+                                     SectionBytes.drop_front(Byte), 0, nulls(),
+                                     outs()) != MCDisassembler::Success)
+      BadInstruction = true;
+
+    Byte += InstructionSize;
+
+    uint64_t VMAddress = SectionAddress + Byte - InstructionSize;
+    InstrMeta.Instruction = Instruction;
+    InstrMeta.VMAddress = VMAddress;
+    InstrMeta.InstructionSize = InstructionSize;
+    InstrMeta.SectionName = SectionName;
+    InstrMeta.Bad = false;
+
+    if (BadInstruction) {
+      InstrMeta.Bad = true;
+      addInstruction(InstrMeta);
+      continue;
+    }
+
+    addInstruction(InstrMeta);
+
+    // Skip additional parsing for instructions that do not affect the control
+    // flow.
+    const auto &InstrDesc = MII->get(Instruction.getOpcode());
+    if (!InstrDesc.mayAffectControlFlow(Instruction, *RegisterInfo))
+      continue;
+
+    uint64_t Target;
+    if (MIA->evaluateBranch(Instruction, VMAddress, InstructionSize, Target)) {
+      // If the target can be evaluated, it's not indirect.
+      StaticBranchTargetings[Target].push_back(VMAddress);
+      continue;
+    }
+
+    // Skip instructions that do not operate on register operands.
+    bool UsesRegisterOperand = false;
+    for (const auto &Operand : Instruction) {
+      if (Operand.isReg())
+        UsesRegisterOperand = true;
+    }
+
+    if (!UsesRegisterOperand)
+      continue;
+
+    IndirectInstructions.insert(VMAddress);
+  }
+}
+
+void FileVerifier::addInstruction(const Instr &Instruction) {
+  Instructions[Instruction.VMAddress] = Instruction;
+}
+
+char UnsupportedDisassembly::ID;
+void UnsupportedDisassembly::log(raw_ostream &OS) const {
+  OS << "Dissassembling of non-objects not currently supported.\n";
+}
+
+std::error_code UnsupportedDisassembly::convertToErrorCode() const {
+  return std::error_code();
+}
+
+} // namespace cfi_verify
+} // namespace llvm

tools/llvm-cfi-verify/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 "FileVerifier.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <functional>
+#include <set>
+#include <string>
+#include <unordered_map>
+
+using Instr = llvm::cfi_verify::FileVerifier::Instr;
+
+namespace llvm {
+namespace cfi_verify {
+
+extern uint64_t SearchLengthForUndef;
+extern uint64_t SearchLengthForConditionalBranch;
+
+struct ControlFlowNode {
+  ControlFlowNode *Next;
+  uint64_t InstructionAddress;
+  uint64_t FlowLength;
+};
+
+struct ConditionalBranchNode {
+  ControlFlowNode *Target;
+  ControlFlowNode *Fallthrough;
+  uint64_t InstructionAddress;
+  // Does this conditional branch successfully instrument CFI protections.
+  bool CFIProtection;
+};
+
+// Print the provided node to standard output.
+void printConditionalBranchNode(const ConditionalBranchNode *Node);
+void printControlFlowNode(const ControlFlowNode *Node, unsigned depth);
+std::vector<uint64_t>
+flattenControlFlowNodeAddresses(const ControlFlowNode *Node);
+
+struct GraphResult {
+  ~GraphResult();
+
+  uint64_t BaseInstructionAddress;
+  std::vector<ConditionalBranchNode *> BranchNodes;
+  std::vector<ControlFlowNode *> OrphanedNodes;
+};
+
+class GraphBuilder {
+public:
+  // Build the control flow graph for a provided control flow node. This method
+  // will enumerate all branch nodes that can lead to this node, and provide
+  // them, fully evaulated, in GraphResult::BranchNodes. It will also provide
+  // any orphaned (i.e. did not make it to a branch node) flows to the provided
+  // node in GraphResult::OrphanedNodes.
+  static GraphResult buildFlowGraph(const FileVerifier &Verifier,
+                                    uint64_t Address);
+
+protected:
+  // Utilised by buildFlowGraph to build the tree out from the provided
+  // conditional branch node to an undefined instruction. The provided
+  // conditional branch node must have exactly one of its subtrees set, and will
+  // update the node's CFIProtection field if a deterministic flow can be found
+  // to an undefined instruction.
+  static void buildFlowsToUndefined(const FileVerifier &Verifier,
+                                    ConditionalBranchNode *BranchNode);
+
+  // Creates a control flow node with the information from the parent, and links
+  // it to the provided child.
+  static ControlFlowNode *createParentNode(const Instr &ParentMeta,
+                                           ControlFlowNode *ChildNode);
+
+private:
+  static void
+  buildFlowGraphImpl(const FileVerifier &Verifier, ControlFlowNode *Node,
+                     std::vector<ConditionalBranchNode *> *BranchNodes,
+                     std::vector<ControlFlowNode *> *OrphanedNodes);
+};
+
+} // end namespace cfi_verify
+} // end namespace llvm
+
+#endif // LLVM_CFI_VERIFY_GRAPH_BUILDER_H

tools/llvm-cfi-verify/GraphBuilder.cpp

+#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::FileVerifier::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));
+
+GraphResult::~GraphResult() {
+  std::set<ControlFlowNode *> CFNs;
+  std::set<ConditionalBranchNode *> CBNs;
+  for (const auto &BranchNode : BranchNodes) {
+    CBNs.insert(BranchNode);
+    for (ControlFlowNode *FlowNode = BranchNode->Target; FlowNode;
+         FlowNode = FlowNode->Next)
+      CFNs.insert(FlowNode);
+
+    for (ControlFlowNode *FlowNode = BranchNode->Fallthrough; FlowNode;
+         FlowNode = FlowNode->Next)
+      CFNs.insert(FlowNode);
+  }
+
+  for (const auto &FlowNode : OrphanedNodes)
+    CFNs.insert(FlowNode);
+
+  for (const auto &Node : CFNs)
+    delete Node;
+
+  for (const auto &Node : CBNs)
+    delete Node;
+}
+
+void printControlFlowNode(const ControlFlowNode *Node, unsigned depth) {
+  assert(Node && "Null pointer provided to printControlFlowNode.");
+  for (unsigned i = 0; i < depth; ++i)
+    outs() << "  ";
+
+  outs() << "[" << Node->FlowLength << "] "
+         << format_hex(Node->InstructionAddress, 2) << "\n";
+  if (Node->Next)
+    printControlFlowNode(Node->Next, depth + 1);
+}
+
+void printConditionalBranchNode(const ConditionalBranchNode *Node) {
+  assert(Node && "Null pointer provided to printConditionalBranchNode.");
+  outs() << format_hex(Node->InstructionAddress, 2) << "\n";
+  outs() << " Target:\n";
+  if (Node->Target)
+    printControlFlowNode(Node->Target, 1);
+  else
+    outs() << "  ???\n";
+
+  outs() << " Fallthrough:\n";
+  if (Node->Fallthrough)
+    printControlFlowNode(Node->Fallthrough, 1);
+  else
+    outs() << "  ???\n";
+}
+
+std::vector<uint64_t>
+flattenControlFlowNodeAddresses(const ControlFlowNode *Node) {
+  std::vector<uint64_t> Addresses;
+  while (Node != nullptr) {
+    Addresses.push_back(Node->InstructionAddress);
+    Node = Node->Next;
+  }
+  return Addresses;
+}
+
+GraphResult GraphBuilder::buildFlowGraph(const FileVerifier &Verifier,
+                                         uint64_t Address) {
+  GraphResult Result;
+  Result.BaseInstructionAddress = Address;
+
+  const auto &IndirectInstructions = Verifier.getIndirectInstructions();
+
+  if (IndirectInstructions.find(Address) == IndirectInstructions.end())
+    return Result;
+
+  ControlFlowNode *Node = new ControlFlowNode();
+  Node->Next = nullptr;
+  Node->InstructionAddress = Address;
+  Node->FlowLength = 0;
+
+  buildFlowGraphImpl(Verifier, Node, &Result.BranchNodes,
+                     &Result.OrphanedNodes);
+  return Result;
+}
+
+void GraphBuilder::buildFlowsToUndefined(const FileVerifier &Verifier,
+                                         ConditionalBranchNode *BranchNode) {
+  assert(BranchNode && "Null pointer provided to buildFlowsToUndefined.");
+  assert(SearchLengthForUndef > 0 &&
+         "Search length for undefined flow must be greater than zero.");
+
+  // Resolve the metadata for the provided node.
+  const auto &BranchInstrMetaPtr =
+      Verifier.getInstruction(BranchNode->InstructionAddress);
+  if (!BranchInstrMetaPtr) {
+    errs() << "Failed to build flows from instruction with address"
+           << format_hex(BranchNode->InstructionAddress, 2) << ".\n";
+    return;
+  }
+  const auto &BranchInstrMeta = *BranchInstrMetaPtr;
+
+  // Start setting up the next node in the chain.
+  const Instr *NextMetaPtr;
+  ControlFlowNode *NextNode = new ControlFlowNode();
+  NextNode->Next = nullptr;
+  NextNode->FlowLength = 1;
+
+  // Find out the next instruction in the chain and add it to the new node.
+  if (BranchNode->Target && !BranchNode->Fallthrough) {
+    // We know the target of the branch, find the fallthrough.
+    NextMetaPtr = Verifier.getNextInstructionSequential(BranchInstrMeta);
+    if (!NextMetaPtr) {
+      errs() << "Failed to get next instruction from "
+             << format_hex(BranchNode->InstructionAddress, 2) << ".\n";
+      delete NextNode;
+      return;
+    }
+
+    NextNode->InstructionAddress = NextMetaPtr->VMAddress;
+    BranchNode->Fallthrough = NextNode; // Add the new node to the branch head.
+  } else if (BranchNode->Fallthrough && !BranchNode->Target) {
+    // We already know the fallthrough, evaluate the target.
+    uint64_t Target;
+    if (!Verifier.getMCInstrAnalysis()->evaluateBranch(
+            BranchInstrMeta.Instruction, BranchInstrMeta.VMAddress,
+            BranchInstrMeta.InstructionSize, Target)) {
+      errs() << "Failed to get branch target for conditional branch at address "
+             << format_hex(BranchInstrMeta.VMAddress, 2) << ".\n";
+      delete NextNode;
+      return;
+    }
+
+    // Resolve the meta pointer for the target of this branch.
+    NextMetaPtr = Verifier.getInstruction(Target);
+    if (!NextMetaPtr) {
+      errs() << "Failed to find instruction at address "
+             << format_hex(Target, 2) << ".\n";
+      delete NextNode;
+      return;
+    }
+
+    NextNode->InstructionAddress = Target;
+    BranchNode->Target = NextNode; // Add the new node to the branch head.
+  } else {
+    errs() << "ControlBranchNode supplied to buildFlowsToUndefined should "
+              "provide Target xor Fallthrough.\n";
+    delete NextNode;
+    return;
+  }
+
+  ControlFlowNode *CurrentNode = NextNode;
+  const Instr *CurrentMetaPtr = NextMetaPtr;
+
+  // Now the branch head has been set properly, complete the rest of the chain.
+  for (uint64_t i = 1; i < SearchLengthForUndef; ++i) {
+    // Check to see whether the chain should die.
+    if (Verifier.isUndefinedInstruction(*CurrentMetaPtr)) {
+      BranchNode->CFIProtection = true;
+      return;
+    }
+
+    // Find the metadata of the next instruction.
+    NextMetaPtr = Verifier.getDefiniteNextInstruction(*CurrentMetaPtr);
+    if (!NextMetaPtr)
+      return;
+
+    // Setup the next node.
+    NextNode = new ControlFlowNode();
+    NextNode->Next = nullptr;
+    NextNode->InstructionAddress = NextMetaPtr->VMAddress;
+    NextNode->FlowLength = CurrentNode->FlowLength + 1;
+    CurrentNode->Next = NextNode;
+
+    // Finalise ready for the next loop.
+    CurrentMetaPtr = NextMetaPtr;
+    CurrentNode = NextNode;
+  }
+
+  // Final check of the last thing we added to the chain.
+  if (Verifier.isUndefinedInstruction(*CurrentMetaPtr))
+    BranchNode->CFIProtection = true;
+}
+
+ControlFlowNode *GraphBuilder::createParentNode(const Instr &ParentMeta,
+                                                ControlFlowNode *ChildNode) {
+  assert(ChildNode && "Null pointer provided to createParentNode");
+  ControlFlowNode *ParentNode = new ControlFlowNode();
+  ParentNode->Next = ChildNode;
+  ParentNode->InstructionAddress = ParentMeta.VMAddress;
+  ParentNode->FlowLength = ChildNode->FlowLength + 1;
+  return ParentNode;
+}
+
+void GraphBuilder::buildFlowGraphImpl(
+    const FileVerifier &Verifier, ControlFlowNode *ChildNode,
+    std::vector<ConditionalBranchNode *> *BranchNodes,
+    std::vector<ControlFlowNode *> *OrphanedNodes) {
+  assert(ChildNode && BranchNodes && OrphanedNodes &&
+         "Null pointer provided to buildFlowGraphImpl.");
+
+  // If we've exceeded the flow length, terminate.
+  if (ChildNode->FlowLength >= SearchLengthForConditionalBranch) {
+    OrphanedNodes->push_back(ChildNode);
+    return;
+  }
+
+  // Get the metadata for the node instruction.
+  const auto &InstrMetaPtr =
+      Verifier.getInstruction(ChildNode->InstructionAddress);
+  if (!InstrMetaPtr) {
+    errs() << "Failed to build flow graph for instruction at address "
+           << format_hex(ChildNode->InstructionAddress, 2) << ".\n";
+    OrphanedNodes->push_back(ChildNode);
+    return;
+  }
+  const auto &ChildMeta = *InstrMetaPtr;
+
+  std::set<const Instr *> CFCrossRefs = Verifier.getControlFlowXRefs(ChildMeta);
+
+  bool HasValidCrossRef = false;
+
+  for (const auto *ParentMetaPtr : CFCrossRefs) {
+    assert(ParentMetaPtr && "CFCrossRefs returned nullptr.");
+    const auto &ParentMeta = *ParentMetaPtr;
+    const auto &ParentDesc =
+        Verifier.getMCInstrInfo()->get(ParentMeta.Instruction.getOpcode());
+
+    if (!ParentDesc.mayAffectControlFlow(ParentMeta.Instruction,
+                                         *Verifier.getRegisterInfo())) {
+      // If this cross reference doesn't affect CF, continue the graph.
+      buildFlowGraphImpl(Verifier, createParentNode(ParentMeta, ChildNode),
+                         BranchNodes, OrphanedNodes);
+      HasValidCrossRef = true;
+      continue;
+    } else {
+      // Evaluate the branch target to ascertain whether this XRef is the result
+      // of a fallthrough or the target of a branch.
+      uint64_t BranchTarget;
+      if (!Verifier.getMCInstrAnalysis()->evaluateBranch(
+              ParentMeta.Instruction, ParentMeta.VMAddress,
+              ParentMeta.InstructionSize, BranchTarget)) {
+        errs() << "Failed to evaluate branch target for instruction at address "
+               << format_hex(ParentMeta.VMAddress, 2) << ".\n";
+        OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+        continue;
+      }
+
+      // Allow unconditional branches to be part of the upwards traversal.
+      // Ensures that the unconditional branch is actually an XRef to the child.
+      if (ParentDesc.isUnconditionalBranch()) {
+        if (BranchTarget == ChildMeta.VMAddress) {
+          // Ensure the unconditional branch can't fall back on itself. Check
+          // the current tree.
+          bool IsUniqueInTree = true;
+          for (const auto &InstructionAddressInTree :
+               flattenControlFlowNodeAddresses(ChildNode)) {
+            if (InstructionAddressInTree == ParentMeta.VMAddress) {
+              IsUniqueInTree = false;
+              break;
+            }
+          }
+
+          if (!IsUniqueInTree) {
+            OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+            continue;
+          }
+
+          ControlFlowNode *NewNode = new ControlFlowNode();
+          NewNode->Next = ChildNode;
+          NewNode->InstructionAddress = ParentMeta.VMAddress;
+          NewNode->FlowLength = ChildNode->FlowLength + 1;
+
+          buildFlowGraphImpl(Verifier, NewNode, BranchNodes, OrphanedNodes);
+          HasValidCrossRef = true;
+          continue;
+        } else {
+          errs() << "Control flow to " << format_hex(ChildMeta.VMAddress, 2)
+                 << ", but target resolution of "
+                 << format_hex(ParentMeta.VMAddress, 2)
+                 << " is not this address?\n";
+          OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+          continue;
+        }
+      }
+
+      // Ensure that any unknown CFs are caught.
+      if (!ParentDesc.isConditionalBranch()) {
+        errs() << "Unknown control flow encountered when building graph at "
+               << format_hex(ChildMeta.VMAddress, 2) << "\n.";
+        OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+        continue;
+      }
+
+      // Only direct conditional branches should be present at this point. Setup
+      // a conditional branch node and build flows to the ud2.
+      ConditionalBranchNode *BranchNode = new ConditionalBranchNode();
+      BranchNode->InstructionAddress = ParentMeta.VMAddress;
+      BranchNode->Target = nullptr;
+      BranchNode->Fallthrough = nullptr;
+      BranchNode->CFIProtection = false;
+      BranchNodes->push_back(BranchNode);
+
+      if (BranchTarget == ChildMeta.VMAddress)
+        BranchNode->Target = ChildNode;
+      else
+        BranchNode->Fallthrough = ChildNode;
+
+      HasValidCrossRef = true;
+      buildFlowsToUndefined(Verifier, BranchNode);
+    }
+  }
+
+  if (!HasValidCrossRef)
+    OrphanedNodes->push_back(ChildNode);
+}
+
+} // namespace cfi_verify
+} // namespace llvm

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

 // information.
 //
 // This tool is currently incomplete. It currently only does disassembly for
 // object files, and searches through the code for indirect control flow
 // instructions, printing them once found.
 //
 //===----------------------------------------------------------------------===//
 
-#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/ObjectFile.h"
-#include "llvm/Support/Casting.h"
+#include "FileVerifier.h"
+
+#include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/CommandLine.h"
-#include "llvm/Support/MemoryBuffer.h"
-#include "llvm/Support/TargetRegistry.h"
-#include "llvm/Support/TargetSelect.h"
-#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Error.h"
 
-#include <cassert>
 #include <cstdlib>
 
 using namespace llvm;
 using namespace llvm::object;
+using namespace llvm::cfi_verify;
 
-cl::opt<bool> ArgDumpSymbols("sym", cl::desc("Dump the symbol table."));
 cl::opt<std::string> InputFilename(cl::Positional, cl::desc("<input file>"),
                                    cl::Required);
 
-static void printSymbols(const ObjectFile *Object) {
-  for (const SymbolRef &Symbol : Object->symbols()) {
-    outs() << "Symbol [" << format_hex_no_prefix(Symbol.getValue(), 2)
-           << "] = ";
-
-    auto SymbolName = Symbol.getName();
-    if (SymbolName)
-      outs() << *SymbolName;
-    else
-      outs() << "UNKNOWN";
-
-    if (Symbol.getFlags() & SymbolRef::SF_Hidden)
-      outs() << " .hidden";
-
-    outs() << " (Section = ";
-
-    auto SymbolSection = Symbol.getSection();
-    if (SymbolSection) {
-      StringRef SymbolSectionName;
-      if ((*SymbolSection)->getName(SymbolSectionName))
-        outs() << "UNKNOWN)";
-      else
-        outs() << SymbolSectionName << ")";
-    } else {
-      outs() << "N/A)";
-    }
-
-    outs() << "\n";
-  }
-}
+ExitOnError ExitOnErr;
 
 int main(int argc, char **argv) {
   cl::ParseCommandLineOptions(argc, argv);
 
   InitializeAllTargetInfos();
   InitializeAllTargetMCs();
   InitializeAllAsmParsers();
   InitializeAllDisassemblers();
 
-  Expected<OwningBinary<Binary>> BinaryOrErr = createBinary(InputFilename);
-  if (!BinaryOrErr) {
-    errs() << "Failed to open file.\n";
-    return EXIT_FAILURE;
-  }
-
-  Binary &Binary = *BinaryOrErr.get().getBinary();
-  ObjectFile *Object = dyn_cast<ObjectFile>(&Binary);
-  if (!Object) {
-    errs() << "Disassembling of non-objects not currently supported.\n";
-    return EXIT_FAILURE;
-  }
-
-  Triple TheTriple = Object->makeTriple();
-  std::string TripleName = TheTriple.getTriple();
-  std::string ArchName = "";
-  std::string ErrorString;
-
-  const Target *TheTarget =
-      TargetRegistry::lookupTarget(ArchName, TheTriple, ErrorString);
-
-  if (!TheTarget) {
-    errs() << "Couldn't find target \"" << TheTriple.getTriple()
-           << "\", failed with error: " << ErrorString << ".\n";
-    return EXIT_FAILURE;
-  }
-
-  SubtargetFeatures Features = Object->getFeatures();
-
-  std::unique_ptr<const MCRegisterInfo> RegisterInfo(
-      TheTarget->createMCRegInfo(TripleName));
-  if (!RegisterInfo) {
-    errs() << "Failed to initialise RegisterInfo.\n";
-    return EXIT_FAILURE;
-  }
-
-  std::unique_ptr<const MCAsmInfo> AsmInfo(
-      TheTarget->createMCAsmInfo(*RegisterInfo, TripleName));
-  if (!AsmInfo) {
-    errs() << "Failed to initialise AsmInfo.\n";
-    return EXIT_FAILURE;
-  }
-
-  std::string MCPU = "";
-  std::unique_ptr<MCSubtargetInfo> SubtargetInfo(
-      TheTarget->createMCSubtargetInfo(TripleName, MCPU, Features.getString()));
-  if (!SubtargetInfo) {
-    errs() << "Failed to initialise SubtargetInfo.\n";
-    return EXIT_FAILURE;
-  }
-
-  std::unique_ptr<const MCInstrInfo> MII(TheTarget->createMCInstrInfo());
-  if (!MII) {
-    errs() << "Failed to initialise MII.\n";
-    return EXIT_FAILURE;
-  }
-
-  MCObjectFileInfo MOFI;
-  MCContext Context(AsmInfo.get(), RegisterInfo.get(), &MOFI);
-
-  std::unique_ptr<const MCDisassembler> Disassembler(
-      TheTarget->createMCDisassembler(*SubtargetInfo, Context));
-
-  if (!Disassembler) {
-    errs() << "No disassembler available for target.";
-    return EXIT_FAILURE;
-  }
-
-  std::unique_ptr<const MCInstrAnalysis> MIA(
-      TheTarget->createMCInstrAnalysis(MII.get()));
-
-  std::unique_ptr<MCInstPrinter> Printer(
-      TheTarget->createMCInstPrinter(TheTriple, AsmInfo->getAssemblerDialect(),
-                                     *AsmInfo, *MII, *RegisterInfo));
-
-  if (ArgDumpSymbols)
-    printSymbols(Object);
-
-  for (const SectionRef &Section : Object->sections()) {
-    outs() << "Section [" << format_hex_no_prefix(Section.getAddress(), 2)
-           << "] = ";
-    StringRef SectionName;
-
-    if (Section.getName(SectionName))
-      outs() << "UNKNOWN.\n";
-    else
-      outs() << SectionName << "\n";
-
-    StringRef SectionContents;
-    if (Section.getContents(SectionContents)) {
-      errs() << "Failed to retrieve section contents.\n";
-      return EXIT_FAILURE;
-    }
-
-    MCInst Instruction;
-    uint64_t InstructionSize;
-
-    ArrayRef<uint8_t> SectionBytes((const uint8_t *)SectionContents.data(),
-                                   Section.getSize());
-
-    for (uint64_t Byte = 0; Byte < Section.getSize();) {
-      bool BadInstruction = false;
-
-      // Disassemble the instruction.
-      if (Disassembler->getInstruction(
-              Instruction, InstructionSize, SectionBytes.drop_front(Byte), 0,
-              nulls(), outs()) != MCDisassembler::Success) {
-        BadInstruction = true;
-      }
-
-      Byte += InstructionSize;
-
-      if (BadInstruction)
-        continue;
-
-      // Skip instructions that do not affect the control flow.
-      const auto &InstrDesc = MII->get(Instruction.getOpcode());
-      if (!InstrDesc.mayAffectControlFlow(Instruction, *RegisterInfo))
-        continue;
-
-      // Skip instructions that do not operate on register operands.
-      bool UsesRegisterOperand = false;
-      for (const auto &Operand : Instruction) {
-        if (Operand.isReg())
-          UsesRegisterOperand = true;
-      }
-
-      if (!UsesRegisterOperand)
-        continue;
-
-      // Print the instruction address.
-      outs() << "    "
-             << format_hex(Section.getAddress() + Byte - InstructionSize, 2)
-             << ": ";
-
-      // Print the instruction bytes.
-      for (uint64_t i = 0; i < InstructionSize; ++i) {
-        outs() << format_hex_no_prefix(SectionBytes[Byte - InstructionSize + i],
-                                       2)
-               << " ";
-      }
-
-      // Print the instruction.
-      outs() << " | " << MII->getName(Instruction.getOpcode()) << " ";
-      Instruction.dump_pretty(outs(), Printer.get());
-
-      outs() << "\n";
-    }
-  }
+  FileVerifier Verifier = ExitOnErr(FileVerifier::Create(InputFilename));
+  ExitOnErr(Verifier.printIndirectCFInstructions());
 
   return EXIT_SUCCESS;
 }

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

+set(LLVM_LINK_COMPONENTS
+  AllTargetsAsmPrinters
+  AllTargetsAsmParsers
+  AllTargetsDescs
+  AllTargetsDisassemblers
+  AllTargetsInfos
+  MC
+  Object
+  MCParser
+  Object
+  Support
+  )
+
+add_llvm_unittest(CFIVerifyTests
+  FileVerifier.cpp
+  GraphBuilder.cpp
+  ../GraphBuilder.cpp
+  ../FileVerifier.cpp)

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

+//===- llvm/tools/llvm-cfi-verify/unittests/FileVerifier.cpp --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../FileVerifier.h"
+#include "../GraphBuilder.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>
+
+using Instr = ::llvm::cfi_verify::FileVerifier::Instr;
+using ::testing::Eq;
+using ::testing::Field;
+
+namespace llvm {
+namespace cfi_verify {
+namespace {
+class ELFx86TestFileVerifier : public FileVerifier {
+public:
+  ELFx86TestFileVerifier()
+      : FileVerifier(Triple("x86_64--"), SubtargetFeatures()) {}
+
+  // Expose this method publicly for testing.
+  void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                            uint64_t SectionAddress, StringRef SectionName) {
+    FileVerifier::parseSectionContents(SectionBytes, SectionAddress,
+                                       SectionName);
+  }
+
+  Error initialiseDisassemblyMembers() {
+    return FileVerifier::initialiseDisassemblyMembers();
+  }
+};
+
+class BasicFileVerifierTest : public ::testing::Test {
+protected:
+  virtual void SetUp() {
+    if (Verifier.initialiseDisassemblyMembers()) {
+      exit(EXIT_FAILURE);
+    }
+  }
+
+  ELFx86TestFileVerifier Verifier;
+};
+
+TEST_F(BasicFileVerifierTest, BasicDisassemblyTraversalTest) {
+  Verifier.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
+          0x2f,                         // 20: (bad)
+          0x41, 0x0e,                   // 21: rex.B (bad)
+          0x62, 0x72, 0x65, 0x61, 0x6b, // 23: (bad) {%k1}
+      },
+      0xDEADBEEF, "Test");
+
+  EXPECT_EQ(nullptr, Verifier.getInstruction(0x0));
+  EXPECT_EQ(nullptr, Verifier.getInstruction(0x1000));
+
+  // 0xDEADBEEF: nop
+  const auto *InstrMeta = Verifier.getInstruction(0xDEADBEEF);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF, InstrMeta->VMAddress);
+  EXPECT_EQ(1, InstrMeta->InstructionSize);
+  EXPECT_EQ("Test", InstrMeta->SectionName);
+  EXPECT_FALSE(InstrMeta->Bad);
+
+  const auto *NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(nullptr, Verifier.getPrevInstructionSequential(*InstrMeta));
+  const auto *PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 1: mov $0x0, %al
+  InstrMeta = Verifier.getInstruction(0xDEADBEEF + 1);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 1, InstrMeta->VMAddress);
+  EXPECT_EQ(2, InstrMeta->InstructionSize);
+  EXPECT_EQ("Test", InstrMeta->SectionName);
+  EXPECT_FALSE(InstrMeta->Bad);
+
+  NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 3: mov %rsp, %rbp
+  InstrMeta = Verifier.getInstruction(0xDEADBEEF + 3);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 3, InstrMeta->VMAddress);
+  EXPECT_EQ(3, InstrMeta->InstructionSize);
+  EXPECT_EQ("Test", InstrMeta->SectionName);
+  EXPECT_FALSE(InstrMeta->Bad);
+
+  NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 6: sub $0x18, %rsp
+  InstrMeta = Verifier.getInstruction(0xDEADBEEF + 6);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 6, InstrMeta->VMAddress);
+  EXPECT_EQ(4, InstrMeta->InstructionSize);
+  EXPECT_EQ("Test", InstrMeta->SectionName);
+  EXPECT_FALSE(InstrMeta->Bad);
+
+  NextInstrMeta = Verifier.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 10: movabs $0x4007c4, %rsi
+  InstrMeta = Verifier.getInstruction(0xDEADBEEF + 10);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 10, InstrMeta->VMAddress);
+  EXPECT_EQ(10, InstrMeta->InstructionSize);
+  EXPECT_EQ("Test", InstrMeta->SectionName);
+  EXPECT_FALSE(InstrMeta->Bad);
+
+  EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 20: (bad)
+  InstrMeta = Verifier.getInstruction(0xDEADBEEF + 20);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 20, InstrMeta->VMAddress);
+  EXPECT_EQ(1, InstrMeta->InstructionSize);
+  EXPECT_EQ("Test", InstrMeta->SectionName);
+  EXPECT_TRUE(InstrMeta->Bad);
+
+  EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(PrevInstrMeta, Verifier.getPrevInstructionSequential(*InstrMeta));
+
+  // 0xDEADBEEF + 21: rex.B (bad)
+  InstrMeta = Verifier.getInstruction(0xDEADBEEF + 21);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 21, InstrMeta->VMAddress);
+  EXPECT_EQ(2, InstrMeta->InstructionSize);
+  EXPECT_EQ("Test", InstrMeta->SectionName);
+  EXPECT_TRUE(InstrMeta->Bad);
+
+  EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(nullptr, Verifier.getPrevInstructionSequential(*InstrMeta));
+
+  // 0xDEADBEEF + 6: (bad) {%k1}
+  InstrMeta = Verifier.getInstruction(0xDEADBEEF + 23);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 23, InstrMeta->VMAddress);
+  EXPECT_EQ(5, InstrMeta->InstructionSize);
+  EXPECT_EQ("Test", InstrMeta->SectionName);
+  EXPECT_TRUE(InstrMeta->Bad);
+
+  EXPECT_EQ(nullptr, Verifier.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(nullptr, Verifier.getPrevInstructionSequential(*InstrMeta));
+}
+
+TEST_F(BasicFileVerifierTest, PrevAndNextFromBadInst) {
+  Verifier.parseSectionContents(
+      {
+          0x90, // 0: nop
+          0x2f, // 1: (bad)
+          0x90  // 2: nop
+      },
+      0xDEADBEEF, "Test");
+  const auto &BadInstrMeta = Verifier.getInstructionOrDie(0xDEADBEEF + 1);
+  const auto *GoodInstrMeta =
+      Verifier.getPrevInstructionSequential(BadInstrMeta);
+  EXPECT_NE(nullptr, GoodInstrMeta);
+  EXPECT_EQ(0xDEADBEEF, GoodInstrMeta->VMAddress);
+  EXPECT_EQ(1, GoodInstrMeta->InstructionSize);
+
+  GoodInstrMeta = Verifier.getNextInstructionSequential(BadInstrMeta);
+  EXPECT_NE(nullptr, GoodInstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 2, GoodInstrMeta->VMAddress);
+  EXPECT_EQ(1, GoodInstrMeta->InstructionSize);
+}
+
+TEST_F(BasicFileVerifierTest, UndefinedInstructionTest) {
+  Verifier.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
+          0x2f,                         // 20: (bad)
+          0x41, 0x0e,                   // 21: rex.B (bad)
+          0x62, 0x72, 0x65, 0x61, 0x6b, // 23: (bad) {%k1}
+          0x0f, 0x0b                    // 28: ud2
+      },
+      0xDEADBEEF, "Test");
+
+  EXPECT_FALSE(Verifier.isUndefinedInstruction(
+      Verifier.getInstructionOrDie(0xDEADBEEF)));
+  EXPECT_FALSE(Verifier.isUndefinedInstruction(
+      Verifier.getInstructionOrDie(0xDEADBEEF + 3)));
+  EXPECT_FALSE(Verifier.isUndefinedInstruction(
+      Verifier.getInstructionOrDie(0xDEADBEEF + 6)));
+  EXPECT_FALSE(Verifier.isUndefinedInstruction(
+      Verifier.getInstructionOrDie(0xDEADBEEF + 10)));
+  EXPECT_FALSE(Verifier.isUndefinedInstruction(
+      Verifier.getInstructionOrDie(0xDEADBEEF + 20)));
+  EXPECT_FALSE(Verifier.isUndefinedInstruction(
+      Verifier.getInstructionOrDie(0xDEADBEEF + 21)));
+  EXPECT_FALSE(Verifier.isUndefinedInstruction(
+      Verifier.getInstructionOrDie(0xDEADBEEF + 23)));
+  EXPECT_TRUE(Verifier.isUndefinedInstruction(
+      Verifier.getInstructionOrDie(0xDEADBEEF + 28)));
+}
+
+TEST_F(BasicFileVerifierTest, FallThroughTest) {
+  Verifier.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
+          0xe8, 0x45, 0xfe, 0xff, 0xff, // 10: callq [some loc]
+          0xff, 0x10,                   // 15: callq *(rax)
+          0x75, 0x00,                   // 17: jne +0
+          0xc3,                         // 19: retq
+      },
+      0xDEADBEEF, "Test");
+
+  EXPECT_TRUE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF)));
+  EXPECT_TRUE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 1)));
+  EXPECT_FALSE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 3)));
+  EXPECT_FALSE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 4)));
+  EXPECT_FALSE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 6)));
+  EXPECT_FALSE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 8)));
+  EXPECT_FALSE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 10)));
+  EXPECT_FALSE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 15)));
+  EXPECT_TRUE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 17)));
+  EXPECT_FALSE(
+      Verifier.canFallThrough(Verifier.getInstructionOrDie(0xDEADBEEF + 19)));
+}
+
+TEST_F(BasicFileVerifierTest, DefiniteNextInstructionTest) {
+  Verifier.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]
+          0xeb, 0x05,                   // 10: jmp 17 [+5]
+          0xe8, 0x00, 0x00, 0x00, 0x00, // 12: callq 17 [+0]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 17: callq 0x1234569f [+0x12345678]
+          0xe8, 0x04, 0x00, 0x00, 0x00, // 22: callq 31 [+4]
+          0xff, 0x10,                   // 27: callq *(rax)
+          0x75, 0x00,                   // 29: jne 31 [+0]
+          0x75, 0xe0,                   // 31: jne 1 [-32]
+          0xc3,                         // 33: retq
+          0xeb, 0xdd,                   // 34: jmp 1 [-35]
+          0xeb, 0xdd,                   // 36: jmp 3 [-35]
+          0xeb, 0xdc,                   // 38: jmp 4 [-36]
+      },
+      0xDEADBEEF, "Test");
+
+  const auto *Current = Verifier.getInstruction(0xDEADBEEF);
+  const auto *Next = Verifier.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress);
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 1);
+  EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current));
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 3);
+  EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current));
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 4);
+  EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current));
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 6);
+  EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current));
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 8);
+  Next = Verifier.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 10, Next->VMAddress);
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 10);
+  Next = Verifier.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress);
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 12);
+  Next = Verifier.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress);
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 17);
+  // Note, definite next instruction address is out of range and should fail.
+  EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current));
+  Next = Verifier.getDefiniteNextInstruction(*Current);
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 22);
+  Next = Verifier.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 31, Next->VMAddress);
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 27);
+  EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current));
+  Current = Verifier.getInstruction(0xDEADBEEF + 29);
+  EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current));
+  Current = Verifier.getInstruction(0xDEADBEEF + 31);
+  EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current));
+  Current = Verifier.getInstruction(0xDEADBEEF + 33);
+  EXPECT_EQ(nullptr, Verifier.getDefiniteNextInstruction(*Current));
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 34);
+  Next = Verifier.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress);
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 36);
+  Next = Verifier.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 3, Next->VMAddress);
+
+  Current = Verifier.getInstruction(0xDEADBEEF + 38);
+  Next = Verifier.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 4, Next->VMAddress);
+}
+
+TEST_F(BasicFileVerifierTest, ControlFlowXRefsTest) {
+  Verifier.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]
+          0xeb, 0x05,                   // 10: jmp 17 [+5]
+          0xe8, 0x00, 0x00, 0x00, 0x00, // 12: callq 17 [+0]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 17: callq 0x1234569f [+0x12345678]
+          0xe8, 0x04, 0x00, 0x00, 0x00, // 22: callq 31 [+4]
+          0xff, 0x10,                   // 27: callq *(rax)
+          0x75, 0x00,                   // 29: jne 31 [+0]
+          0x75, 0xe0,                   // 31: jne 1 [-32]
+          0xc3,                         // 33: retq
+          0xeb, 0xdd,                   // 34: jmp 1 [-35]
+          0xeb, 0xdd,                   // 36: jmp 3 [-35]
+          0xeb, 0xdc,                   // 38: jmp 4 [-36]
+      },
+      0xDEADBEEF, "Test");
+  const auto *InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF);
+  std::set<const Instr *> XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(XRefs.empty());
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 1);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 34))));
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 3);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 1)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 36))));
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 4);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 38))));
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 6);
+  EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 8);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 10);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 8))));
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 12);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 17);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 10)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 12))));
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 22);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 27);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 29);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 31);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 22)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 29))));
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 33);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31))));
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 34);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 36);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 38);
+  XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionInvalidTargets) {
+  Verifier.parseSectionContents(
+      {
+          0x90,       // 0: nop
+          0x0f, 0x0b, // 1: ud2
+          0x75, 0x00, // 3: jne 5 [+0]
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF));
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 1));
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 3));
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADC0DE));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionBasicFallthroughToUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0x0f, 0x0b, // 2: ud2
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionBasicJumpToUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x0f, 0x0b, // 4: ud2
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 2));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionDualPathUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x03, // 0: jne 5 [+3]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x0f, 0x0b, // 5: ud2
+          0x75, 0xf9, // 7: jne 2 [-7]
+          0x0f, 0x0b, // 9: ud2
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionDualPathSingleUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x05, // 0: jne 7 [+5]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x75, 0xfb, // 5: jne 2 [-5]
+          0x0f, 0x0b, // 7: ud2
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionDualFailLimitUpwards) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x06, // 0: jne 8 [+6]
+          0x90,       // 2: nop
+          0x90,       // 3: nop
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0xff, 0x10, // 6: callq *(%rax)
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF, "Test");
+  uint64_t PrevSearchLengthForConditionalBranch =
+      SearchLengthForConditionalBranch;
+  SearchLengthForConditionalBranch = 2;
+
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 6));
+
+  SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionDualFailLimitDownwards) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0x90,       // 6: nop
+          0x90,       // 7: nop
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF, "Test");
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 2;
+
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 2));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionGoodAndBadPaths) {
+  Verifier.parseSectionContents(
+      {
+          0xeb, 0x02, // 0: jmp 4 [+2]
+          0x75, 0x02, // 2: jne 6 [+2]
+          0xff, 0x10, // 4: callq *(%rax)
+          0x0f, 0x0b, // 6: ud2
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionWithUnconditionalJumpInFallthrough) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x04, // 0: jne 6 [+4]
+          0xeb, 0x00, // 2: jmp 4 [+0]
+          0xff, 0x10, // 4: callq *(%rax)
+          0x0f, 0x0b, // 6: ud2
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionComplexExample) {
+  // See unittests/GraphBuilder.cpp::BuildFlowGraphComplexExample for this
+  // graph.
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x12,                   // 0: jne 20 [+18]
+          0xeb, 0x03,                   // 2: jmp 7 [+3]
+          0x75, 0x10,                   // 4: jne 22 [+16]
+          0x90,                         // 6: nop
+          0x90,                         // 7: nop
+          0x90,                         // 8: nop
+          0xff, 0x10,                   // 9: callq *(%rax)
+          0xeb, 0xfc,                   // 11: jmp 9 [-4]
+          0x75, 0xfa,                   // 13: jne 9 [-6]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
+          0x90,                         // 20: nop
+          0x90,                         // 21: nop
+          0x0f, 0x0b,                   // 22: ud2
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 9));
+}
+
+} // anonymous namespace
+} // end namespace cfi_verify
+} // end namespace llvm
+
+int main(int argc, char **argv) {
+  ::testing::InitGoogleTest(&argc, argv);
+  llvm::cl::ParseCommandLineOptions(argc, argv);
+
+  llvm::InitializeAllTargetInfos();
+  llvm::InitializeAllTargetMCs();
+  llvm::InitializeAllAsmParsers();
+  llvm::InitializeAllDisassemblers();
+
+  return RUN_ALL_TESTS();
+}

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

+//===- llvm/tools/llvm-cfi-verify/unittests/GraphBuilder.cpp --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../GraphBuilder.h"
+#include "../FileVerifier.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <cstdlib>
+
+using Instr = ::llvm::cfi_verify::FileVerifier::Instr;
+using ::testing::Each;
+using ::testing::ElementsAre;
+using ::testing::Eq;
+using ::testing::Field;
+using ::testing::IsEmpty;
+using ::testing::ResultOf;
+using ::testing::SizeIs;
+
+namespace llvm {
+namespace cfi_verify {
+// Custom node printers for gtest.
+void PrintControlFlowNode(ControlFlowNode *Node, unsigned depth,
+                          ::std::ostream *os) {
+  for (unsigned i = 0; i < depth; ++i)
+    *os << "  ";
+
+  if (Node == nullptr) {
+    *os << "nullptr";
+    return;
+  }
+
+  *os << "[" << Node->FlowLength << "] 0x" << std::hex
+      << Node->InstructionAddress << std::dec;
+  if (Node->Next) {
+    *os << "\n";
+    PrintControlFlowNode(Node->Next, depth + 1, os);
+  }
+}
+
+void PrintTo(ControlFlowNode *Node, ::std::ostream *os) {
+  *os << "\nControl Flow Node:\n";
+  PrintControlFlowNode(Node, 0, os);
+}
+
+void PrintTo(ConditionalBranchNode *Node, ::std::ostream *os) {
+  *os << "\nConditional Branch Node:\n";
+  if (Node == nullptr) {
+    *os << "nullptr";
+    return;
+  }
+
+  *os << "0x" << std::hex << Node->InstructionAddress << std::dec << "\n";
+  *os << " Target:\n";
+  if (Node->Target) {
+    PrintControlFlowNode(Node->Target, 1, os);
+    *os << "\n";
+  } else {
+    *os << "  ???\n";
+  }
+
+  *os << " Fallthrough:\n";
+  if (Node->Fallthrough) {
+    PrintControlFlowNode(Node->Fallthrough, 1, os);
+  } else {
+    *os << "  ???";
+  }
+}
+
+namespace {
+class ELFx86TestFileVerifier : public FileVerifier {
+public:
+  ELFx86TestFileVerifier()
+      : FileVerifier(Triple("x86_64--"), SubtargetFeatures()) {}
+
+  // Expose this method publicly for testing.
+  void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                            uint64_t SectionAddress, StringRef SectionName) {
+    FileVerifier::parseSectionContents(SectionBytes, SectionAddress,
+                                       SectionName);
+  }
+
+  Error initialiseDisassemblyMembers() {
+    return FileVerifier::initialiseDisassemblyMembers();
+  }
+};
+
+class BasicGraphBuilderTest : public ::testing::Test {
+protected:
+  virtual void SetUp() {
+    if (Verifier.initialiseDisassemblyMembers()) {
+      exit(EXIT_FAILURE);
+    }
+  }
+
+  ELFx86TestFileVerifier Verifier;
+};
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathFallthroughUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0x0f, 0x0b, // 2: ud2
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF, "Test");
+  const auto Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 4);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(Result.BranchNodes,
+              Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress,
+                                   Eq(0xDEADBEEF)),
+                             Field(&ConditionalBranchNode::Fallthrough,
+                                   ResultOf(flattenControlFlowNodeAddresses,
+                                            ElementsAre(0xDEADBEEF + 2))),
+                             Field(&ConditionalBranchNode::Target,
+                                   ResultOf(flattenControlFlowNodeAddresses,
+                                            ElementsAre(0xDEADBEEF + 4))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x0f, 0x0b, // 4: ud2
+      },
+      0xDEADBEEF, "Test");
+  const auto Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 2);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(Result.BranchNodes,
+              Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress,
+                                   Eq(0xDEADBEEF)),
+                             Field(&ConditionalBranchNode::Fallthrough,
+                                   ResultOf(flattenControlFlowNodeAddresses,
+                                            ElementsAre(0xDEADBEEF + 2))),
+                             Field(&ConditionalBranchNode::Target,
+                                   ResultOf(flattenControlFlowNodeAddresses,
+                                            ElementsAre(0xDEADBEEF + 4))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x03, // 0: jne 5 [+3]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x0f, 0x0b, // 5: ud2
+          0x75, 0xf9, // 7: jne 2 [-7]
+          0x0f, 0x0b, // 9: ud2
+      },
+      0xDEADBEEF, "Test");
+  const auto Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 3);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(2));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
+          Field(&ConditionalBranchNode::Target,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 5))))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 7)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 9))),
+          Field(&ConditionalBranchNode::Target,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x05, // 0: jne 7 [+5]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x75, 0xfb, // 5: jne 2 [-5]
+          0x0f, 0x0b, // 7: ud2
+      },
+      0xDEADBEEF, "Test");
+  GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 3);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(2));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
+          Field(&ConditionalBranchNode::Target,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 7))))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 5)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 7))),
+          Field(&ConditionalBranchNode::Target,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) {
+  Verifier.parseSectionContents(
+      {
+          0x90,       // 0: nop
+          0x75, 0xfe, // 1: jne 1 [-2]
+      },
+      0xDEADBEEF, "Test");
+  GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+
+  Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 1);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+
+  Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADC0DE);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) {
+  Verifier.parseSectionContents(
+      {
+          0xeb, 0xfe, // 0: jmp 0 [-2]
+          0xff, 0x10, // 2: callq *(%rax)
+      },
+      0xDEADBEEF, "Test");
+  GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 2);
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+  EXPECT_THAT(Result.OrphanedNodes,
+              Contains(AllOf(Field(&ControlFlowNode::InstructionAddress,
+                                   Eq(0xDEADBEEF + 2)),
+                             Field(&ControlFlowNode::Next, Eq(nullptr)))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0xfe, // 0: jne 0 [-2]
+          0xff, 0x10, // 2: callq *(%rax)
+      },
+      0xDEADBEEF, "Test");
+  GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 2);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Each(AllOf(Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+                 Field(&ConditionalBranchNode::Target,
+                       ResultOf(flattenControlFlowNodeAddresses,
+                                ElementsAre(0xDEADBEEF))),
+                 Field(&ConditionalBranchNode::Fallthrough,
+                       ResultOf(flattenControlFlowNodeAddresses,
+                                ElementsAre(0xDEADBEEF + 2))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xeb, 0xfc, // 2: jmp 0 [-4]
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF, "Test");
+  GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 4);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))),
+          Field(&ConditionalBranchNode::Target,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 4))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x00, // 0: jne 2 [+0]
+          0xeb, 0xfc, // 2: jmp 0 [-4]
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF, "Test");
+  GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 4);
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.OrphanedNodes,
+              Contains(AllOf(Field(&ControlFlowNode::InstructionAddress,
+                                   Eq(0xDEADBEEF + 4)),
+                             Field(&ControlFlowNode::Next, Eq(nullptr)))));
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x06, // 0: jne 8 [+6]
+          0x90,       // 2: nop
+          0x90,       // 3: nop
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0xff, 0x10, // 6: callq *(%rax)
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF, "Test");
+  uint64_t PrevSearchLengthForConditionalBranch =
+      SearchLengthForConditionalBranch;
+  SearchLengthForConditionalBranch = 2;
+
+  GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 6);
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.OrphanedNodes,
+              Each(ResultOf(flattenControlFlowNodeAddresses,
+                            ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5,
+                                        0xDEADBEEF + 6))));
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+
+  SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0x90,       // 6: nop
+          0x90,       // 7: nop
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF, "Test");
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 2;
+
+  GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0xDEADBEEF + 2);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Each(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Target,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0xDEADBEEF + 2))))));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) {
+  // The following code has this graph (in DOT format):
+  //   digraph G {
+  //     "0" -> "20"
+  //     "0" -> "2"
+  //     "20" -> "21"
+  //     "4" -> "22 (ud2)"
+  //     "21" -> "22 (ud2)"
+  //     "4" -> "6"
+  //     "6" -> "7"
+  //     "2" -> "7"
+  //     "7" -> "8"
+  //     "8" -> "9 (indirect)"
+  //     "13" -> "15 (error)"
+  //     "13" -> "9 (indirect)"
+  //     "11" -> "9 (indirect)"
+  //   }
+  // Or, in image format: https://i.imgur.com/aX5fCoi.png
+
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x12,                   // 0: jne 20 [+18]
+          0xeb, 0x03,                   // 2: jmp 7 [+3]
+          0x75, 0x10,                   // 4: jne 22 [+16]
+          0x90,                         // 6: nop
+          0x90,                         // 7: nop
+          0x90,                         // 8: nop
+          0xff, 0x10,                   // 9: callq *(%rax)
+          0xeb, 0xfc,                   // 11: jmp 9 [-4]
+          0x75, 0xfa,                   // 13: jne 9 [-6]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
+          0x90,                         // 20: nop
+          0x90,                         // 21: nop
+          0x0f, 0x0b,                   // 22: ud2
+      },
+      0x1000, "Test");
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 5;
+
+  GraphResult Result = GraphBuilder::buildFlowGraph(Verifier, 0x1000 + 9);
+
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes, SizeIs(3));
+
+  EXPECT_THAT(
+      Result.OrphanedNodes,
+      Each(AllOf(Field(&ControlFlowNode::InstructionAddress, Eq(0x1000 + 11)),
+                 ResultOf(flattenControlFlowNodeAddresses,
+                          ElementsAre(0x1000 + 11, 0x1000 + 9)))));
+
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000)),
+          Field(&ConditionalBranchNode::Target,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0x1000 + 20, 0x1000 + 21, 0x1000 + 22))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0x1000 + 2, 0x1000 + 7, 0x1000 + 8,
+                                     0x1000 + 9))))));
+
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000 + 4)),
+          Field(&ConditionalBranchNode::Target,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0x1000 + 22))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0x1000 + 6, 0x1000 + 7, 0x1000 + 8,
+                                     0x1000 + 9))))));
+
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000 + 13)),
+          Field(&ConditionalBranchNode::Target,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0x1000 + 9))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                ResultOf(flattenControlFlowNodeAddresses,
+                         ElementsAre(0x1000 + 15))))));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+} // anonymous namespace
+} // end namespace cfi_verify
+} // end namespace llvm

unittests/CMakeLists.txt

 add_subdirectory(BinaryFormat)
 add_subdirectory(ObjectYAML)
 add_subdirectory(Option)
 add_subdirectory(ProfileData)
 add_subdirectory(Support)
 add_subdirectory(Target)
 add_subdirectory(Transforms)
 add_subdirectory(XRay)
+add_subdirectory(../tools/llvm-cfi-verify/unittests ../tools/llvm-cfi-verify/unittests)