Parse DWARF information to reduce false positives.

[hctim]

Summary

Help differentiate code and data by parsing DWARF information. This will reduce false positive rates where data is placed in executable sections and is mistakenly parsed as code, resulting in an inflation in the number of indirect CF instructions (and hence an inflation of the number of unprotected).

Also prints the DWARF line data around the region of each indirect CF instruction.

[hctim]

backported a clang-format

[hctim]

Merged previous changes in the stack.

[probinson]

tools/llvm-cfi-verify/FileAnalysis.cpp

325

Does this tool run only on .o files, and not on executables? Because this decides line info is valid if any CU has a non-empty line table. If you are looking at a linked executable, one might have been compiled -g and another not, and this check will still succeed.

331

Type units can have an associated line table, but that's just to provide filespecs for DW_AT_file. There should never be any Rows in a type unit's line table.

[hctim]

• Modified tool to ensure that users are aware that all statically linked libraries are required to be compiled with '-g'.
• Removed type unit check (thanks probison)!
• Changed opt<uint64_t> to opt<unsigned long long> (known issue with opt<uint64_t>).
• Lexicographically sorted library names.

tools/llvm-cfi-verify/FileAnalysis.cpp

325

The goal for this tool is to run on both.

Thanks for reminding me :) I've had discussions with people about this exact topic offline, but forgot to update the commits.

The consensus we reached was in order to do elimination-by-dwarf (i.e. having --ignore-dwarf=false), anything that is statically linked into this binary is required to be compiled with -g. I'll update the documentation for this tool soon and add a comment around this section.

331

Thanks for the information, will remove the redundant check.

[hctim]

Patched from upstream.

[pcc]

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

54 ↗

(On Diff #119937)

I don't think you need cl::location or the external declaration of IgnoreDWARF, because this flag is only used in this file.

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

485 ↗

(On Diff #119937)

Am I missing something, or should these new tests include DWARF information?

[hctim]

• Fixed diff to be against the correct changelist (prev in stack instead of master).
• Removed external declaration of command line flag .

[pcc]

Should this include a test case?

[hctim]

• Moved DWARF handlers into virtual functions for mocking.
• Added unit tests for line table based instruction exclusion.

[hctim]

• Removed dependency injection onto DWARF lookups from unit tests.
• Added lit test suite for integration testing.
• Added lit tests for checking line table information.

[hctim]

Fixed small formatting issue from revert of dependency injection changes.

[hctim]

Removed tests that require clang with plugin/LTO support. Made the tests build from the supplied assembly instead.

[pcc]

test/tools/llvm-cfi-verify/X86/protected-lineinfo.s

21 ↗

(On Diff #120899)

I'd prefer if the output were smaller. Do you get a smaller output if you compile with -gmlt?

[hctim]

Compiled integration tests with -gmlt instead of -g

[pcc]

I'd expect there to be a test which makes sure that a jump with no line info in a file with line info doesn't count as an unprotected jump. Can you add one?

test/tools/llvm-cfi-verify/X86/protected-nolineinfo.s

1 ↗

(On Diff #121020)

I don't think you need more than one test for the line table check. I'd drop this one and keep the other one.

[hctim]

Added test where a file contains line table information, but an indirect CF instruction is not covered by the LT information.

[pcc]

LGTM

tools/llvm-cfi-verify/CMakeLists.txt

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

tools/llvm-cfi-verify/FileAnalysis.h

+//===- FileAnalysis.h -------------------------------------------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CFI_VERIFY_FILE_ANALYSIS_H
+#define LLVM_CFI_VERIFY_FILE_ANALYSIS_H
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/DebugInfo/DWARF/DWARFContext.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 {
+
+extern bool IgnoreDWARF;
+
+// Disassembler and analysis tool for machine code files. Keeps track of non-
+// sequential control flows, including indirect control flow instructions.
+class FileAnalysis {
+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.
+    bool Valid; // Is this a valid instruction? If false, Instr::Instruction is
+                // undefined.
+  };
+
+  // Construct a FileAnalysis from a file path.
+  static Expected<FileAnalysis> Create(StringRef Filename);
+
+  // Construct and take ownership of the supplied object. Do not use this
+  // constructor, prefer to use FileAnalysis::Create instead.
+  FileAnalysis(object::OwningBinary<object::Binary> Binary);
+  FileAnalysis() = delete;
+  FileAnalysis(const FileAnalysis &) = delete;
+  FileAnalysis(FileAnalysis &&Other) = default;
+
+  // 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. Returns 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 used by CFI to trap the program.
+  bool isCFITrap(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 fall through if they are conditional
+  // branches or calls.
+  bool canFallThrough(const Instr &InstrMeta) const;
+
+  // Returns whether this instruction uses a register operand.
+  bool usesRegisterOperand(const Instr &InstrMeta) const;
+
+  // Returns the definitive next instruction. This is different from the next
+  // instruction sequentially as it will follow unconditional branches (assuming
+  // they can be resolved at compile time, i.e. not indirect). This method
+  // 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 *>
+  getDirectControlFlowXRefs(const Instr &InstrMeta) const;
+
+  // Returns the list of indirect instructions.
+  const std::set<uint64_t> &getIndirectInstructions() const;
+
+  const MCRegisterInfo *getRegisterInfo() const;
+  const MCInstrInfo *getMCInstrInfo() const;
+  const MCInstrAnalysis *getMCInstrAnalysis() const;
+
+  DWARFContext *getDWARF();
+
+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.
+  FileAnalysis(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.
+  void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                            uint64_t SectionAddress);
+
+  // 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;
+
+  // DWARF debug information.
+  std::unique_ptr<DWARFContext> DWARF;
+
+  // A mapping between the virtual memory address to the instruction metadata
+  // struct. TODO(hctim): Reimplement this as a sorted vector to avoid per-
+  // insertion allocation.
+  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_ANALYSIS_H

tools/llvm-cfi-verify/FileAnalysis.cpp

+//===- FileAnalysis.cpp -----------------------------------------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "FileAnalysis.h"
+#include "GraphBuilder.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/DebugInfo/DWARF/DWARFContext.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <functional>
+
+using Instr = llvm::cfi_verify::FileAnalysis::Instr;
+
+namespace llvm {
+namespace cfi_verify {
+
+bool IgnoreDWARF;
+
+static cl::opt<bool, true> IgnoreDWARFArg(
+    "ignore-dwarf",
+    cl::desc("Ignore all DWARF data (warning: may generate false positives)."),
+    cl::location(IgnoreDWARF), cl::init(false));
+
+cl::opt<uint64_t> DWARFSearchRange(
+    "dwarf-search-range",
+    cl::desc("Address search range used to determine if instruction is valid."),
+    cl::init(0x10));
+
+Expected<FileAnalysis> FileAnalysis::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());
+  FileAnalysis Analysis(std::move(Binary));
+
+  Analysis.Object = dyn_cast<object::ObjectFile>(Analysis.Binary.getBinary());
+  if (!Analysis.Object)
+    return make_error<UnsupportedDisassembly>();
+
+  Analysis.ObjectTriple = Analysis.Object->makeTriple();
+  Analysis.Features = Analysis.Object->getFeatures();
+
+  // Init the rest of the object.
+  if (auto InitResponse = Analysis.initialiseDisassemblyMembers())
+    return std::move(InitResponse);
+
+  if (auto SectionParseResponse = Analysis.parseCodeSections())
+    return std::move(SectionParseResponse);
+
+  return std::move(Analysis);
+}
+
+FileAnalysis::FileAnalysis(object::OwningBinary<object::Binary> Binary)
+    : Binary(std::move(Binary)) {}
+
+FileAnalysis::FileAnalysis(const Triple &ObjectTriple,
+                           const SubtargetFeatures &Features)
+    : ObjectTriple(ObjectTriple), Features(Features) {}
+
+bool FileAnalysis::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;
+
+  if (!usesRegisterOperand(*InstrMetaPtr))
+    return false;
+
+  auto Flows = GraphBuilder::buildFlowGraph(*this, Address);
+
+  if (!Flows.OrphanedNodes.empty())
+    return false;
+
+  for (const auto &BranchNode : Flows.BranchNodes) {
+    if (!BranchNode.CFIProtection)
+      return false;
+  }
+
+  return true;
+}
+
+const Instr *
+FileAnalysis::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.Valid)
+    return nullptr;
+
+  return &KV->second;
+}
+
+const Instr *
+FileAnalysis::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.Valid)
+    return nullptr;
+
+  return &KV->second;
+}
+
+bool FileAnalysis::usesRegisterOperand(const Instr &InstrMeta) const {
+  for (const auto &Operand : InstrMeta.Instruction) {
+    if (Operand.isReg())
+      return true;
+  }
+  return false;
+}
+
+const Instr *FileAnalysis::getInstruction(uint64_t Address) const {
+  const auto &InstrKV = Instructions.find(Address);
+  if (InstrKV == Instructions.end())
+    return nullptr;
+
+  return &InstrKV->second;
+}
+
+const Instr &FileAnalysis::getInstructionOrDie(uint64_t Address) const {
+  const auto &InstrKV = Instructions.find(Address);
+  assert(InstrKV != Instructions.end() && "Address doesn't exist.");
+  return InstrKV->second;
+}
+
+bool FileAnalysis::isCFITrap(const Instr &InstrMeta) const {
+  return MII->getName(InstrMeta.Instruction.getOpcode()) == "TRAP";
+}
+
+bool FileAnalysis::canFallThrough(const Instr &InstrMeta) const {
+  if (!InstrMeta.Valid)
+    return false;
+
+  if (isCFITrap(InstrMeta))
+    return false;
+
+  const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
+  if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo))
+    return InstrDesc.isConditionalBranch();
+
+  return true;
+}
+
+const Instr *
+FileAnalysis::getDefiniteNextInstruction(const Instr &InstrMeta) const {
+  if (!InstrMeta.Valid)
+    return nullptr;
+
+  if (isCFITrap(InstrMeta))
+    return nullptr;
+
+  const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
+  const Instr *NextMetaPtr;
+  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;
+
+    NextMetaPtr = getInstruction(Target);
+  } else {
+    NextMetaPtr =
+        getInstruction(InstrMeta.VMAddress + InstrMeta.InstructionSize);
+  }
+
+  if (!NextMetaPtr || !NextMetaPtr->Valid)
+    return nullptr;
+
+  return NextMetaPtr;
+}
+
+std::set<const Instr *>
+FileAnalysis::getDirectControlFlowXRefs(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> &FileAnalysis::getIndirectInstructions() const {
+  return IndirectInstructions;
+}
+
+const MCRegisterInfo *FileAnalysis::getRegisterInfo() const {
+  return RegisterInfo.get();
+}
+
+const MCInstrInfo *FileAnalysis::getMCInstrInfo() const { return MII.get(); }
+
+const MCInstrAnalysis *FileAnalysis::getMCInstrAnalysis() const {
+  return MIA.get();
+}
+
+DWARFContext *FileAnalysis::getDWARF() { return DWARF.get(); }
+
+Error FileAnalysis::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 FileAnalysis::parseCodeSections() {
+  if (!IgnoreDWARF) {
+    DWARF.reset(DWARFContext::create(*Object).release());
+    if (!DWARF)
+      return make_error<StringError>("Could not create DWARF information.",
+                                     inconvertibleErrorCode());
+
+    bool LineInfoValid = false;
+
+    for (auto &Unit : DWARF->compile_units()) {
+      const auto &LineTable = DWARF->getLineTableForUnit(Unit.get());
+      if (LineTable && !LineTable->Rows.empty()) {
+        LineInfoValid = true;
+        break;
+      }
+    }
+
+    if (!LineInfoValid) {
+      for (auto &Range : DWARF->type_unit_sections()) {
+        for (auto &Unit : Range) {
+          const auto &LineTable = DWARF->getLineTableForUnit(Unit.get());
+          if (LineTable && !LineTable->Rows.empty()) {
+            LineInfoValid = true;
+            break;
+          }
+        }
+      }
+    }
+
+    if (!LineInfoValid)
+      return make_error<StringError>(
+          "DWARF line information missing. Did you compile with '-g'?",
+          inconvertibleErrorCode());
+  }
+
+  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());
+
+    ArrayRef<uint8_t> SectionBytes((const uint8_t *)SectionContents.data(),
+                                   Section.getSize());
+    parseSectionContents(SectionBytes, Section.getAddress());
+  }
+  return Error::success();
+}
+
+void FileAnalysis::parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                                        uint64_t SectionAddress) {
+  MCInst Instruction;
+  Instr InstrMeta;
+  uint64_t InstructionSize;
+
+  for (uint64_t Byte = 0; Byte < SectionBytes.size();) {
+    bool ValidInstruction =
+        Disassembler->getInstruction(Instruction, InstructionSize,
+                                     SectionBytes.drop_front(Byte), 0, nulls(),
+                                     outs()) == MCDisassembler::Success;
+
+    Byte += InstructionSize;
+
+    uint64_t VMAddress = SectionAddress + Byte - InstructionSize;
+    InstrMeta.Instruction = Instruction;
+    InstrMeta.VMAddress = VMAddress;
+    InstrMeta.InstructionSize = InstructionSize;
+    InstrMeta.Valid = ValidInstruction;
+
+    // Check if this instruction exists in the range of the DWARF metadata.
+    if (DWARF &&
+        DWARF->getLineInfoForAddressRange(InstrMeta.VMAddress, DWARFSearchRange)
+            .empty())
+      continue;
+
+    addInstruction(InstrMeta);
+
+    if (!ValidInstruction)
+      continue;
+
+    // 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;
+    }
+
+    if (!usesRegisterOperand(InstrMeta))
+      continue;
+
+    IndirectInstructions.insert(VMAddress);
+  }
+}
+
+void FileAnalysis::addInstruction(const Instr &Instruction) {
+  const auto &KV =
+      Instructions.insert(std::make_pair(Instruction.VMAddress, Instruction));
+  assert(
+      KV.second &&
+      "Failed to add instruction, instruction at this address already exists.");
+}
+
+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 "FileAnalysis.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <functional>
+#include <set>
+#include <string>
+#include <unordered_map>
+
+using Instr = llvm::cfi_verify::FileAnalysis::Instr;
+
+namespace llvm {
+namespace cfi_verify {
+
+extern uint64_t SearchLengthForUndef;
+extern uint64_t SearchLengthForConditionalBranch;
+
+struct ControlFlowNode {
+  void print(unsigned depth, raw_ostream &os) const;
+  std::vector<uint64_t> flatten() const;
+
+  ControlFlowNode *Next;
+  uint64_t InstructionAddress;
+  uint64_t FlowLength;
+};
+
+struct ConditionalBranchNode {
+  void print(raw_ostream &os) const;
+  ControlFlowNode *Target;
+  ControlFlowNode *Fallthrough;
+  uint64_t InstructionAddress;
+  // Does this conditional branch implement CFI successfully?
+  bool CFIProtection;
+};
+
+struct GraphResult {
+  ~GraphResult();
+
+  uint64_t BaseInstructionAddress;
+  std::vector<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 FileAnalysis &Analysis,
+                                    uint64_t Address);
+
+private:
+  // Implementation function that actually builds the flow graph. Retrieves a
+  // list of cross references to instruction referenced in `Node`. If any of
+  // these XRefs are conditional branches, it will build the other potential
+  // path (fallthrough or target) using `buildFlowsToUndefined`. Otherwise,
+  // this function will recursively call itself where `Node` in the recursive
+  // call is now the XRef. If any XRef results in an error, the XRef in question
+  // is added to `OrphanedNodes`. An error is defined as any of the following:
+  //   - The maximum search length `SearchLengthForConditionalBranch` has been
+  //     reached.
+  //   - The XRef cannot be calculated (e.g. it doesn't exist in the Analysis
+  //     object).
+  //   - The graph is cyclic.
+  static void
+  buildFlowGraphImpl(const FileAnalysis &Analysis, ControlFlowNode *Node,
+                     std::vector<ConditionalBranchNode> *BranchNodes,
+                     std::vector<ControlFlowNode *> *OrphanedNodes);
+
+  // Utilised by buildFlowGraphImpl to build the tree out from the provided
+  // conditional branch node to an undefined instruction. The provided
+  // conditional branch node must have exactly one of its subtrees set, and will
+  // update the node's CFIProtection field if a deterministic flow can be found
+  // to an undefined instruction.
+  static void buildFlowsToUndefined(const FileAnalysis &Analysis,
+                                    ConditionalBranchNode &BranchNode);
+
+  // Creates a control flow node with the information from the parent, and links
+  // it to the provided child.
+  static ControlFlowNode *createParentNode(const Instr &ParentMeta,
+                                           ControlFlowNode *ChildNode);
+};
+
+} // end namespace cfi_verify
+} // end namespace llvm
+
+#endif // LLVM_CFI_VERIFY_GRAPH_BUILDER_H

tools/llvm-cfi-verify/GraphBuilder.cpp

+//===- GraphBuilder.cpp -----------------------------------------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "GraphBuilder.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <functional>
+
+using Instr = llvm::cfi_verify::FileAnalysis::Instr;
+
+namespace llvm {
+namespace cfi_verify {
+
+uint64_t SearchLengthForUndef;
+uint64_t SearchLengthForConditionalBranch;
+
+static cl::opt<uint64_t, true> SearchLengthForUndefArg(
+    "search-length-undef",
+    cl::desc("Specify the maximum amount of instructions "
+             "to inspect when searching for an undefined "
+             "instruction from a conditional branch."),
+    cl::location(SearchLengthForUndef), cl::init(2));
+
+static cl::opt<uint64_t, true> SearchLengthForConditionalBranchArg(
+    "search-length-cb",
+    cl::desc("Specify the maximum amount of instructions "
+             "to inspect when searching for a conditional "
+             "branch from an indirect control flow."),
+    cl::location(SearchLengthForConditionalBranch), cl::init(20));
+
+void ControlFlowNode::print(unsigned depth, raw_ostream &os) const {
+  for (unsigned i = 0; i < depth; ++i)
+    os << "  ";
+
+  os << "[" << FlowLength << "] " << format_hex(InstructionAddress, 2) << "\n";
+  if (Next)
+    Next->print(depth + 1, os);
+}
+
+void ConditionalBranchNode::print(raw_ostream &os) const {
+  os << format_hex(InstructionAddress, 2) << "\n";
+  os << " Target:\n";
+  if (Target)
+    Target->print(1, os);
+  else
+    os << "  ???\n";
+
+  os << " Fallthrough:\n";
+  if (Fallthrough)
+    Fallthrough->print(1, os);
+  else
+    os << "  ???\n";
+}
+
+std::vector<uint64_t> ControlFlowNode::flatten() const {
+  std::vector<uint64_t> Addresses;
+  const ControlFlowNode *Node = this;
+  while (Node != nullptr) {
+    Addresses.push_back(Node->InstructionAddress);
+    Node = Node->Next;
+  }
+  return Addresses;
+}
+
+GraphResult::~GraphResult() {
+  std::set<ControlFlowNode *> CFNs;
+  for (const auto &BranchNode : BranchNodes) {
+    for (ControlFlowNode *FlowNode = BranchNode.Target; FlowNode;
+         FlowNode = FlowNode->Next)
+      CFNs.insert(FlowNode);
+
+    for (ControlFlowNode *FlowNode = BranchNode.Fallthrough; FlowNode;
+         FlowNode = FlowNode->Next)
+      CFNs.insert(FlowNode);
+  }
+
+  for (auto &FlowNode : OrphanedNodes) {
+    while (FlowNode) {
+      CFNs.insert(FlowNode);
+      FlowNode = FlowNode->Next;
+    }
+  }
+
+  for (const auto &Node : CFNs)
+    delete Node;
+}
+
+GraphResult GraphBuilder::buildFlowGraph(const FileAnalysis &Analysis,
+                                         uint64_t Address) {
+  GraphResult Result;
+  Result.BaseInstructionAddress = Address;
+
+  const auto &IndirectInstructions = Analysis.getIndirectInstructions();
+
+  if (IndirectInstructions.find(Address) == IndirectInstructions.end())
+    return Result;
+
+  ControlFlowNode *Node = new ControlFlowNode();
+  Node->Next = nullptr;
+  Node->InstructionAddress = Address;
+  Node->FlowLength = 0;
+
+  buildFlowGraphImpl(Analysis, Node, &Result.BranchNodes,
+                     &Result.OrphanedNodes);
+  return Result;
+}
+
+void GraphBuilder::buildFlowsToUndefined(const FileAnalysis &Analysis,
+                                         ConditionalBranchNode &BranchNode) {
+  assert(SearchLengthForUndef > 0 &&
+         "Search length for undefined flow must be greater than zero.");
+
+  // Resolve the metadata for the provided node.
+  const auto &BranchInstrMetaPtr =
+      Analysis.getInstruction(BranchNode.InstructionAddress);
+  if (!BranchInstrMetaPtr) {
+    errs() << "Failed to build flows from instruction with address"
+           << format_hex(BranchNode.InstructionAddress, 2) << ".\n";
+    return;
+  }
+  const auto &BranchInstrMeta = *BranchInstrMetaPtr;
+
+  // Start setting up the next node in the chain.
+  const Instr *NextMetaPtr;
+  ControlFlowNode *NextNode = new ControlFlowNode();
+  NextNode->Next = nullptr;
+  NextNode->FlowLength = 1;
+
+  // Find out the next instruction in the chain and add it to the new node.
+  if (BranchNode.Target && !BranchNode.Fallthrough) {
+    // We know the target of the branch, find the fallthrough.
+    NextMetaPtr = Analysis.getNextInstructionSequential(BranchInstrMeta);
+    if (!NextMetaPtr) {
+      errs() << "Failed to get next instruction from "
+             << format_hex(BranchNode.InstructionAddress, 2) << ".\n";
+      delete NextNode;
+      return;
+    }
+
+    NextNode->InstructionAddress = NextMetaPtr->VMAddress;
+    BranchNode.Fallthrough = NextNode; // Add the new node to the branch head.
+  } else if (BranchNode.Fallthrough && !BranchNode.Target) {
+    // We already know the fallthrough, evaluate the target.
+    uint64_t Target;
+    if (!Analysis.getMCInstrAnalysis()->evaluateBranch(
+            BranchInstrMeta.Instruction, BranchInstrMeta.VMAddress,
+            BranchInstrMeta.InstructionSize, Target)) {
+      errs() << "Failed to get branch target for conditional branch at address "
+             << format_hex(BranchInstrMeta.VMAddress, 2) << ".\n";
+      delete NextNode;
+      return;
+    }
+
+    // Resolve the meta pointer for the target of this branch.
+    NextMetaPtr = Analysis.getInstruction(Target);
+    if (!NextMetaPtr) {
+      errs() << "Failed to find instruction at address "
+             << format_hex(Target, 2) << ".\n";
+      delete NextNode;
+      return;
+    }
+
+    NextNode->InstructionAddress = Target;
+    BranchNode.Target = NextNode; // Add the new node to the branch head.
+  } else {
+    errs() << "ControlBranchNode supplied to buildFlowsToUndefined should "
+              "provide Target xor Fallthrough.\n";
+    delete NextNode;
+    return;
+  }
+
+  ControlFlowNode *CurrentNode = NextNode;
+  const Instr *CurrentMetaPtr = NextMetaPtr;
+
+  // Now the branch head has been set properly, complete the rest of the chain.
+  for (uint64_t i = 1; i < SearchLengthForUndef; ++i) {
+    // Check to see whether the chain should die.
+    if (Analysis.isCFITrap(*CurrentMetaPtr)) {
+      BranchNode.CFIProtection = true;
+      return;
+    }
+
+    // Find the metadata of the next instruction.
+    NextMetaPtr = Analysis.getDefiniteNextInstruction(*CurrentMetaPtr);
+    if (!NextMetaPtr)
+      return;
+
+    // Setup the next node.
+    NextNode = new ControlFlowNode();
+    NextNode->Next = nullptr;
+    NextNode->InstructionAddress = NextMetaPtr->VMAddress;
+    NextNode->FlowLength = CurrentNode->FlowLength + 1;
+    CurrentNode->Next = NextNode;
+
+    // Move the 'current' pointers to the new tail of the chain.
+    CurrentMetaPtr = NextMetaPtr;
+    CurrentNode = NextNode;
+  }
+
+  // Final check of the last thing we added to the chain.
+  if (Analysis.isCFITrap(*CurrentMetaPtr))
+    BranchNode.CFIProtection = true;
+}
+
+ControlFlowNode *GraphBuilder::createParentNode(const Instr &ParentMeta,
+                                                ControlFlowNode *ChildNode) {
+  assert(ChildNode && "Null pointer provided to createParentNode");
+  ControlFlowNode *ParentNode = new ControlFlowNode();
+  ParentNode->Next = ChildNode;
+  ParentNode->InstructionAddress = ParentMeta.VMAddress;
+  ParentNode->FlowLength = ChildNode->FlowLength + 1;
+  return ParentNode;
+}
+
+void GraphBuilder::buildFlowGraphImpl(
+    const FileAnalysis &Analysis, ControlFlowNode *ChildNode,
+    std::vector<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 =
+      Analysis.getInstruction(ChildNode->InstructionAddress);
+  if (!InstrMetaPtr) {
+    errs() << "Failed to build flow graph for instruction at address "
+           << format_hex(ChildNode->InstructionAddress, 2) << ".\n";
+    OrphanedNodes->push_back(ChildNode);
+    return;
+  }
+  const auto &ChildMeta = *InstrMetaPtr;
+
+  std::set<const Instr *> CFCrossRefs =
+      Analysis.getDirectControlFlowXRefs(ChildMeta);
+
+  bool HasValidCrossRef = false;
+
+  for (const auto *ParentMetaPtr : CFCrossRefs) {
+    assert(ParentMetaPtr && "CFCrossRefs returned nullptr.");
+    const auto &ParentMeta = *ParentMetaPtr;
+    const auto &ParentDesc =
+        Analysis.getMCInstrInfo()->get(ParentMeta.Instruction.getOpcode());
+
+    if (!ParentDesc.mayAffectControlFlow(ParentMeta.Instruction,
+                                         *Analysis.getRegisterInfo())) {
+      // If this cross reference doesn't affect CF, continue the graph.
+      buildFlowGraphImpl(Analysis, createParentNode(ParentMeta, ChildNode),
+                         BranchNodes, OrphanedNodes);
+      HasValidCrossRef = true;
+      continue;
+    }
+
+    // Call instructions are not valid in the upwards traversal.
+    if (ParentDesc.isCall()) {
+      OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+      continue;
+    }
+
+    // Evaluate the branch target to ascertain whether this XRef is the result
+    // of a fallthrough or the target of a branch.
+    uint64_t BranchTarget;
+    if (!Analysis.getMCInstrAnalysis()->evaluateBranch(
+            ParentMeta.Instruction, ParentMeta.VMAddress,
+            ParentMeta.InstructionSize, BranchTarget)) {
+      errs() << "Failed to evaluate branch target for instruction at address "
+             << format_hex(ParentMeta.VMAddress, 2) << ".\n";
+      OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+      continue;
+    }
+
+    // Allow unconditional branches to be part of the upwards traversal.
+    if (ParentDesc.isUnconditionalBranch()) {
+      // Ensures that the unconditional branch is actually an XRef to the child.
+      if (BranchTarget != ChildMeta.VMAddress) {
+        errs() << "Control flow to " << format_hex(ChildMeta.VMAddress, 2)
+               << ", but target resolution of "
+               << format_hex(ParentMeta.VMAddress, 2)
+               << " is not this address?\n";
+        OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+        continue;
+      }
+
+      // Stop if this graph is cyclic.
+      const auto &FlattenedList = ChildNode->flatten();
+      if (std::find_if(FlattenedList.begin(), FlattenedList.end(),
+                       [&ParentMeta](const uint64_t &Address) {
+                         return Address == ParentMeta.VMAddress;
+                       }) != FlattenedList.end()) {
+        OrphanedNodes->push_back(createParentNode(ParentMeta, ChildNode));
+        continue;
+      }
+
+      buildFlowGraphImpl(Analysis, createParentNode(ParentMeta, ChildNode),
+                         BranchNodes, OrphanedNodes);
+      HasValidCrossRef = true;
+      continue;
+    }
+
+    // Ensure that any unknown CFs are caught.
+    if (!ParentDesc.isConditionalBranch()) {
+      errs() << "Unknown control flow encountered when building graph at "
+             << format_hex(ParentMeta.VMAddress, 2) << ".\n";
+      const auto& ParentNode = createParentNode(ParentMeta, ChildNode);
+      OrphanedNodes->push_back(ParentNode);
+      ParentNode->print(1, errs());
+      continue;
+    }
+
+    // Only direct conditional branches should be present at this point. Setup
+    // a conditional branch node and build flows to the ud2.
+    ConditionalBranchNode BranchNode;
+    BranchNode.InstructionAddress = ParentMeta.VMAddress;
+    BranchNode.Target = nullptr;
+    BranchNode.Fallthrough = nullptr;
+    BranchNode.CFIProtection = false;
+
+    if (BranchTarget == ChildMeta.VMAddress)
+      BranchNode.Target = ChildNode;
+    else
+      BranchNode.Fallthrough = ChildNode;
+
+    HasValidCrossRef = true;
+    buildFlowsToUndefined(Analysis, BranchNode);
+    BranchNodes->push_back(BranchNode);
+  }
+
+  if (!HasValidCrossRef)
+    OrphanedNodes->push_back(ChildNode);
+}
+
+} // namespace cfi_verify
+} // namespace llvm

tools/llvm-cfi-verify/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Tool
 name = llvm-cfi-verify
 parent = Tools
-required_libraries = MC MCDisassembler MCParser Support all-targets
+required_libraries = MC MCDisassembler MCParser Support all-targets DebugInfoDWARF

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 "FileAnalysis.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 "llvm/Support/FormatVariadic.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 = ";
+ExitOnError ExitOnErr;
 
-    auto SymbolSection = Symbol.getSection();
-    if (SymbolSection) {
-      StringRef SymbolSectionName;
-      if ((*SymbolSection)->getName(SymbolSectionName))
-        outs() << "UNKNOWN)";
-      else
-        outs() << SymbolSectionName << ")";
+void printIndirectCFInstructions(FileAnalysis &Analysis) {
+  uint64_t ProtectedCount = 0;
+  uint64_t UnprotectedCount = 0;
+  DWARFContext *DWARF = Analysis.getDWARF();
+
+  for (uint64_t Address : Analysis.getIndirectInstructions()) {
+    const auto &InstrMeta = Analysis.getInstructionOrDie(Address);
+
+    if (Analysis.isCFIProtected(Address)) {
+      outs() << "P ";
+      ProtectedCount++;
     } else {
-      outs() << "N/A)";
+      outs() << "U ";
+      UnprotectedCount++;
     }
 
+    outs() << format_hex(Address, 2) << " | "
+           << Analysis.getMCInstrInfo()->getName(
+                  InstrMeta.Instruction.getOpcode())
+           << " ";
     outs() << "\n";
+
+    if (DWARF) {
+      for (const auto &LineKV :
+           DWARF->getLineInfoForAddressRange(Address, 0x10)) {
+        outs() << "  " << format_hex(LineKV.first, 2) << " = "
+               << LineKV.second.FileName << ":" << LineKV.second.Line << ":"
+               << LineKV.second.Column << " ("
+               << LineKV.second.FunctionName << ")\n";
+      }
     }
   }
 
+  if (ProtectedCount || UnprotectedCount)
+    outs() << formatv(
+        "Unprotected: {0} ({1:P}), Protected: {2} ({3:P})\n", UnprotectedCount,
+        (((double)UnprotectedCount) / (UnprotectedCount + ProtectedCount)),
+        ProtectedCount,
+        (((double)ProtectedCount) / (UnprotectedCount + ProtectedCount)));
+  else
+    outs() << "No indirect CF instructions found.\n";
+}
+
 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";
-    }
-  }
+  FileAnalysis Analysis = ExitOnErr(FileAnalysis::Create(InputFilename));
+  printIndirectCFInstructions(Analysis);
 
   return EXIT_SUCCESS;
 }

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

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

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

+//===- llvm/tools/llvm-cfi-verify/unittests/FileAnalysis.cpp --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../FileAnalysis.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::FileAnalysis::Instr;
+using ::testing::Eq;
+using ::testing::Field;
+
+namespace llvm {
+namespace cfi_verify {
+namespace {
+class ELFx86TestFileAnalysis : public FileAnalysis {
+public:
+  ELFx86TestFileAnalysis()
+      : FileAnalysis(Triple("x86_64--"), SubtargetFeatures()) {}
+
+  // Expose this method publicly for testing.
+  void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                            uint64_t SectionAddress) {
+    FileAnalysis::parseSectionContents(SectionBytes, SectionAddress);
+  }
+
+  Error initialiseDisassemblyMembers() {
+    return FileAnalysis::initialiseDisassemblyMembers();
+  }
+};
+
+class BasicFileAnalysisTest : public ::testing::Test {
+protected:
+  virtual void SetUp() {
+    if (Analysis.initialiseDisassemblyMembers()) {
+      FAIL() << "Failed to initialise FileAnalysis.";
+    }
+  }
+
+  ELFx86TestFileAnalysis Analysis;
+};
+
+TEST_F(BasicFileAnalysisTest, BasicDisassemblyTraversalTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                   // 0: nop
+          0xb0, 0x00,             // 1: mov $0x0, %al
+          0x48, 0x89, 0xe5,       // 3: mov %rsp, %rbp
+          0x48, 0x83, 0xec, 0x18, // 6: sub $0x18, %rsp
+          0x48, 0xbe, 0xc4, 0x07, 0x40,
+          0x00, 0x00, 0x00, 0x00, 0x00, // 10: movabs $0x4007c4, %rsi
+          0x2f,                         // 20: (bad)
+          0x41, 0x0e,                   // 21: rex.B (bad)
+          0x62, 0x72, 0x65, 0x61, 0x6b, // 23: (bad) {%k1}
+      },
+      0xDEADBEEF);
+
+  EXPECT_EQ(nullptr, Analysis.getInstruction(0x0));
+  EXPECT_EQ(nullptr, Analysis.getInstruction(0x1000));
+
+  // 0xDEADBEEF: nop
+  const auto *InstrMeta = Analysis.getInstruction(0xDEADBEEF);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF, InstrMeta->VMAddress);
+  EXPECT_EQ(1u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  const auto *NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta));
+  const auto *PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 1: mov $0x0, %al
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 1);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 1, InstrMeta->VMAddress);
+  EXPECT_EQ(2u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 3: mov %rsp, %rbp
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 3);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 3, InstrMeta->VMAddress);
+  EXPECT_EQ(3u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 6: sub $0x18, %rsp
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 6);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 6, InstrMeta->VMAddress);
+  EXPECT_EQ(4u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  NextInstrMeta = Analysis.getNextInstructionSequential(*InstrMeta);
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 10: movabs $0x4007c4, %rsi
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 10);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(NextInstrMeta, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 10, InstrMeta->VMAddress);
+  EXPECT_EQ(10u, InstrMeta->InstructionSize);
+  EXPECT_TRUE(InstrMeta->Valid);
+
+  EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+  PrevInstrMeta = InstrMeta;
+
+  // 0xDEADBEEF + 20: (bad)
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 20);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 20, InstrMeta->VMAddress);
+  EXPECT_EQ(1u, InstrMeta->InstructionSize);
+  EXPECT_FALSE(InstrMeta->Valid);
+
+  EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(PrevInstrMeta, Analysis.getPrevInstructionSequential(*InstrMeta));
+
+  // 0xDEADBEEF + 21: rex.B (bad)
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 21);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 21, InstrMeta->VMAddress);
+  EXPECT_EQ(2u, InstrMeta->InstructionSize);
+  EXPECT_FALSE(InstrMeta->Valid);
+
+  EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta));
+
+  // 0xDEADBEEF + 6: (bad) {%k1}
+  InstrMeta = Analysis.getInstruction(0xDEADBEEF + 23);
+  EXPECT_NE(nullptr, InstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 23, InstrMeta->VMAddress);
+  EXPECT_EQ(5u, InstrMeta->InstructionSize);
+  EXPECT_FALSE(InstrMeta->Valid);
+
+  EXPECT_EQ(nullptr, Analysis.getNextInstructionSequential(*InstrMeta));
+  EXPECT_EQ(nullptr, Analysis.getPrevInstructionSequential(*InstrMeta));
+}
+
+TEST_F(BasicFileAnalysisTest, PrevAndNextFromBadInst) {
+  Analysis.parseSectionContents(
+      {
+          0x90, // 0: nop
+          0x2f, // 1: (bad)
+          0x90  // 2: nop
+      },
+      0xDEADBEEF);
+  const auto &BadInstrMeta = Analysis.getInstructionOrDie(0xDEADBEEF + 1);
+  const auto *GoodInstrMeta =
+      Analysis.getPrevInstructionSequential(BadInstrMeta);
+  EXPECT_NE(nullptr, GoodInstrMeta);
+  EXPECT_EQ(0xDEADBEEF, GoodInstrMeta->VMAddress);
+  EXPECT_EQ(1u, GoodInstrMeta->InstructionSize);
+
+  GoodInstrMeta = Analysis.getNextInstructionSequential(BadInstrMeta);
+  EXPECT_NE(nullptr, GoodInstrMeta);
+  EXPECT_EQ(0xDEADBEEF + 2, GoodInstrMeta->VMAddress);
+  EXPECT_EQ(1u, GoodInstrMeta->InstructionSize);
+}
+
+TEST_F(BasicFileAnalysisTest, CFITrapTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                   // 0: nop
+          0xb0, 0x00,             // 1: mov $0x0, %al
+          0x48, 0x89, 0xe5,       // 3: mov %rsp, %rbp
+          0x48, 0x83, 0xec, 0x18, // 6: sub $0x18, %rsp
+          0x48, 0xbe, 0xc4, 0x07, 0x40,
+          0x00, 0x00, 0x00, 0x00, 0x00, // 10: movabs $0x4007c4, %rsi
+          0x2f,                         // 20: (bad)
+          0x41, 0x0e,                   // 21: rex.B (bad)
+          0x62, 0x72, 0x65, 0x61, 0x6b, // 23: (bad) {%k1}
+          0x0f, 0x0b                    // 28: ud2
+      },
+      0xDEADBEEF);
+
+  EXPECT_FALSE(Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 3)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 6)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 10)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 20)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 21)));
+  EXPECT_FALSE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 23)));
+  EXPECT_TRUE(
+      Analysis.isCFITrap(Analysis.getInstructionOrDie(0xDEADBEEF + 28)));
+}
+
+TEST_F(BasicFileAnalysisTest, FallThroughTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                         // 0: nop
+          0xb0, 0x00,                   // 1: mov $0x0, %al
+          0x2f,                         // 3: (bad)
+          0x0f, 0x0b,                   // 4: ud2
+          0xff, 0x20,                   // 6: jmpq *(%rax)
+          0xeb, 0x00,                   // 8: jmp +0
+          0xe8, 0x45, 0xfe, 0xff, 0xff, // 10: callq [some loc]
+          0xff, 0x10,                   // 15: callq *(rax)
+          0x75, 0x00,                   // 17: jne +0
+          0xc3,                         // 19: retq
+      },
+      0xDEADBEEF);
+
+  EXPECT_TRUE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF)));
+  EXPECT_TRUE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 1)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 3)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 4)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 6)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 8)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 10)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 15)));
+  EXPECT_TRUE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 17)));
+  EXPECT_FALSE(
+      Analysis.canFallThrough(Analysis.getInstructionOrDie(0xDEADBEEF + 19)));
+}
+
+TEST_F(BasicFileAnalysisTest, DefiniteNextInstructionTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                         // 0: nop
+          0xb0, 0x00,                   // 1: mov $0x0, %al
+          0x2f,                         // 3: (bad)
+          0x0f, 0x0b,                   // 4: ud2
+          0xff, 0x20,                   // 6: jmpq *(%rax)
+          0xeb, 0x00,                   // 8: jmp 10 [+0]
+          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);
+
+  const auto *Current = Analysis.getInstruction(0xDEADBEEF);
+  const auto *Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 1);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 3);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 4);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 6);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 8);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 10, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 10);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 12);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 17, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 17);
+  // Note, definite next instruction address is out of range and should fail.
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 22);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 31, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 27);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+  Current = Analysis.getInstruction(0xDEADBEEF + 29);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+  Current = Analysis.getInstruction(0xDEADBEEF + 31);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+  Current = Analysis.getInstruction(0xDEADBEEF + 33);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 34);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 1, Next->VMAddress);
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 36);
+  EXPECT_EQ(nullptr, Analysis.getDefiniteNextInstruction(*Current));
+
+  Current = Analysis.getInstruction(0xDEADBEEF + 38);
+  Next = Analysis.getDefiniteNextInstruction(*Current);
+  EXPECT_NE(nullptr, Next);
+  EXPECT_EQ(0xDEADBEEF + 4, Next->VMAddress);
+}
+
+TEST_F(BasicFileAnalysisTest, ControlFlowXRefsTest) {
+  Analysis.parseSectionContents(
+      {
+          0x90,                         // 0: nop
+          0xb0, 0x00,                   // 1: mov $0x0, %al
+          0x2f,                         // 3: (bad)
+          0x0f, 0x0b,                   // 4: ud2
+          0xff, 0x20,                   // 6: jmpq *(%rax)
+          0xeb, 0x00,                   // 8: jmp 10 [+0]
+          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);
+  const auto *InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF);
+  std::set<const Instr *> XRefs =
+      Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(XRefs.empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 1);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 34))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 3);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 1)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 36))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 4);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 38))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 6);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 8);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 10);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 8))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 12);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 17);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 10)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 12))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 22);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 27);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 29);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 31);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 22)),
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 29))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 33);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_THAT(XRefs, UnorderedElementsAre(
+                         Field(&Instr::VMAddress, Eq(0xDEADBEEF + 31))));
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 34);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 36);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+
+  InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 38);
+  XRefs = Analysis.getDirectControlFlowXRefs(*InstrMetaPtr);
+  EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionInvalidTargets) {
+  Analysis.parseSectionContents(
+      {
+          0x90,       // 0: nop
+          0x0f, 0x0b, // 1: ud2
+          0x75, 0x00, // 3: jne 5 [+0]
+      },
+      0xDEADBEEF);
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF));
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 1));
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 3));
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADC0DE));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionBasicFallthroughToUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0x0f, 0x0b, // 2: ud2
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionBasicJumpToUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x0f, 0x0b, // 4: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 2));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x03, // 0: jne 5 [+3]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x0f, 0x0b, // 5: ud2
+          0x75, 0xf9, // 7: jne 2 [-7]
+          0x0f, 0x0b, // 9: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathSingleUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x05, // 0: jne 7 [+5]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x75, 0xfb, // 5: jne 2 [-5]
+          0x0f, 0x0b, // 7: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualFailLimitUpwards) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x06, // 0: jne 8 [+6]
+          0x90,       // 2: nop
+          0x90,       // 3: nop
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0xff, 0x10, // 6: callq *(%rax)
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForConditionalBranch =
+      SearchLengthForConditionalBranch;
+  SearchLengthForConditionalBranch = 2;
+
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 6));
+
+  SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualFailLimitDownwards) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0x90,       // 6: nop
+          0x90,       // 7: nop
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 2;
+
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 2));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionGoodAndBadPaths) {
+  Analysis.parseSectionContents(
+      {
+          0xeb, 0x02, // 0: jmp 4 [+2]
+          0x75, 0x02, // 2: jne 6 [+2]
+          0xff, 0x10, // 4: callq *(%rax)
+          0x0f, 0x0b, // 6: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_FALSE(Analysis.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionWithUnconditionalJumpInFallthrough) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x04, // 0: jne 6 [+4]
+          0xeb, 0x00, // 2: jmp 4 [+0]
+          0xff, 0x10, // 4: callq *(%rax)
+          0x0f, 0x0b, // 6: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionComplexExample) {
+  // See unittests/GraphBuilder.cpp::BuildFlowGraphComplexExample for this
+  // graph.
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x12,                   // 0: jne 20 [+18]
+          0xeb, 0x03,                   // 2: jmp 7 [+3]
+          0x75, 0x10,                   // 4: jne 22 [+16]
+          0x90,                         // 6: nop
+          0x90,                         // 7: nop
+          0x90,                         // 8: nop
+          0xff, 0x10,                   // 9: callq *(%rax)
+          0xeb, 0xfc,                   // 11: jmp 9 [-4]
+          0x75, 0xfa,                   // 13: jne 9 [-6]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
+          0x90,                         // 20: nop
+          0x90,                         // 21: nop
+          0x0f, 0x0b,                   // 22: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_FALSE(Analysis.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 "../FileAnalysis.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include "llvm/BinaryFormat/ELF.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCDisassembler/MCDisassembler.h"
+#include "llvm/MC/MCInst.h"
+#include "llvm/MC/MCInstPrinter.h"
+#include "llvm/MC/MCInstrAnalysis.h"
+#include "llvm/MC/MCInstrDesc.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Object/Binary.h"
+#include "llvm/Object/COFF.h"
+#include "llvm/Object/ELFObjectFile.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <cstdlib>
+
+using Instr = ::llvm::cfi_verify::FileAnalysis::Instr;
+using ::testing::Each;
+using ::testing::ElementsAre;
+using ::testing::Eq;
+using ::testing::Field;
+using ::testing::IsEmpty;
+using ::testing::Property;
+using ::testing::SizeIs;
+
+namespace llvm {
+namespace cfi_verify {
+// Custom node printers for gtest.
+void PrintControlFlowNode(ControlFlowNode *Node, unsigned depth,
+                          ::std::ostream *os) {
+  for (unsigned i = 0; i < depth; ++i)
+    *os << "  ";
+
+  if (Node == nullptr) {
+    *os << "nullptr";
+    return;
+  }
+
+  *os << "[" << Node->FlowLength << "] 0x" << std::hex
+      << Node->InstructionAddress << std::dec;
+  if (Node->Next) {
+    *os << "\n";
+    PrintControlFlowNode(Node->Next, depth + 1, os);
+  }
+}
+
+void PrintTo(ControlFlowNode *Node, ::std::ostream *os) {
+  *os << "\nControl Flow Node:\n";
+  PrintControlFlowNode(Node, 0, os);
+}
+
+void PrintTo(ConditionalBranchNode *Node, ::std::ostream *os) {
+  *os << "\nConditional Branch Node:\n";
+  if (Node == nullptr) {
+    *os << "nullptr";
+    return;
+  }
+
+  *os << "0x" << std::hex << Node->InstructionAddress << std::dec << "\n";
+  *os << " Target:\n";
+  if (Node->Target) {
+    PrintControlFlowNode(Node->Target, 1, os);
+    *os << "\n";
+  } else {
+    *os << "  ???\n";
+  }
+
+  *os << " Fallthrough:\n";
+  if (Node->Fallthrough) {
+    PrintControlFlowNode(Node->Fallthrough, 1, os);
+  } else {
+    *os << "  ???";
+  }
+}
+
+namespace {
+class ELFx86TestFileAnalysis : public FileAnalysis {
+public:
+  ELFx86TestFileAnalysis()
+      : FileAnalysis(Triple("x86_64--"), SubtargetFeatures()) {}
+
+  // Expose this method publicly for testing.
+  void parseSectionContents(ArrayRef<uint8_t> SectionBytes,
+                            uint64_t SectionAddress) {
+    FileAnalysis::parseSectionContents(SectionBytes, SectionAddress);
+  }
+
+  Error initialiseDisassemblyMembers() {
+    return FileAnalysis::initialiseDisassemblyMembers();
+  }
+};
+
+class BasicGraphBuilderTest : public ::testing::Test {
+protected:
+  virtual void SetUp() {
+    if (Analysis.initialiseDisassemblyMembers()) {
+      exit(EXIT_FAILURE);
+    }
+  }
+
+  ELFx86TestFileAnalysis Analysis;
+};
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathFallthroughUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0x0f, 0x0b, // 2: ud2
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF);
+  const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(Result.BranchNodes,
+              Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress,
+                                   Eq(0xDEADBEEF)),
+                             Field(&ConditionalBranchNode::Fallthrough,
+                                   Property(&ControlFlowNode::flatten,
+                                            ElementsAre(0xDEADBEEF + 2))),
+                             Field(&ConditionalBranchNode::Target,
+                                   Property(&ControlFlowNode::flatten,
+                                            ElementsAre(0xDEADBEEF + 4))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestSinglePathJumpUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x0f, 0x0b, // 4: ud2
+      },
+      0xDEADBEEF);
+  const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(Result.BranchNodes,
+              Contains(AllOf(Field(&ConditionalBranchNode::InstructionAddress,
+                                   Eq(0xDEADBEEF)),
+                             Field(&ConditionalBranchNode::Fallthrough,
+                                   Property(&ControlFlowNode::flatten,
+                                            ElementsAre(0xDEADBEEF + 2))),
+                             Field(&ConditionalBranchNode::Target,
+                                   Property(&ControlFlowNode::flatten,
+                                            ElementsAre(0xDEADBEEF + 4))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathDualUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x03, // 0: jne 5 [+3]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x0f, 0x0b, // 5: ud2
+          0x75, 0xf9, // 7: jne 2 [-7]
+          0x0f, 0x0b, // 9: ud2
+      },
+      0xDEADBEEF);
+  const auto Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(2));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 5))))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 7)),
+          Field(
+              &ConditionalBranchNode::Fallthrough,
+              Property(&ControlFlowNode::flatten, ElementsAre(0xDEADBEEF + 9))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphTestDualPathSingleUd2) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x05, // 0: jne 7 [+5]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x75, 0xfb, // 5: jne 2 [-5]
+          0x0f, 0x0b, // 7: ud2
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
+
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(2));
+  EXPECT_THAT(Result.BranchNodes,
+              Each(Field(&ConditionalBranchNode::CFIProtection, Eq(true))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 7))))));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF + 5)),
+          Field(
+              &ConditionalBranchNode::Fallthrough,
+              Property(&ControlFlowNode::flatten, ElementsAre(0xDEADBEEF + 7))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF + 3))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphFailures) {
+  Analysis.parseSectionContents(
+      {
+          0x90,       // 0: nop
+          0x75, 0xfe, // 1: jne 1 [-2]
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 1);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADC0DE);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoXrefs) {
+  Analysis.parseSectionContents(
+      {
+          0xeb, 0xfe, // 0: jmp 0 [-2]
+          0xff, 0x10, // 2: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+  EXPECT_THAT(Result.OrphanedNodes,
+              Contains(AllOf(Field(&ControlFlowNode::InstructionAddress,
+                                   Eq(0xDEADBEEF + 2)),
+                             Field(&ControlFlowNode::Next, Eq(nullptr)))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphConditionalInfiniteLoop) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0xfe, // 0: jne 0 [-2]
+          0xff, 0x10, // 2: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Each(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten, ElementsAre(0xDEADBEEF))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphUnconditionalInfiniteLoop) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xeb, 0xfc, // 2: jmp 0 [-4]
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(Result.BranchNodes, SizeIs(1));
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2, 0xDEADBEEF))),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 4))))));
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphNoFlowsToIndirection) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x00, // 0: jne 2 [+0]
+          0xeb, 0xfc, // 2: jmp 0 [-4]
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.OrphanedNodes,
+              Contains(AllOf(Field(&ControlFlowNode::InstructionAddress,
+                                   Eq(0xDEADBEEF + 4)),
+                             Field(&ControlFlowNode::Next, Eq(nullptr)))));
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededUpwards) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x06, // 0: jne 8 [+6]
+          0x90,       // 2: nop
+          0x90,       // 3: nop
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0xff, 0x10, // 6: callq *(%rax)
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForConditionalBranch =
+      SearchLengthForConditionalBranch;
+  SearchLengthForConditionalBranch = 2;
+
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 6);
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.OrphanedNodes,
+              Each(Property(&ControlFlowNode::flatten,
+                            ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5,
+                                        0xDEADBEEF + 6))));
+  EXPECT_THAT(Result.BranchNodes, IsEmpty());
+
+  SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphLengthExceededDownwards) {
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0x90,       // 6: nop
+          0x90,       // 7: nop
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 2;
+
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+  EXPECT_THAT(Result.OrphanedNodes, IsEmpty());
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Each(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0xDEADBEEF)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 4, 0xDEADBEEF + 5))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0xDEADBEEF + 2))))));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+TEST_F(BasicGraphBuilderTest, BuildFlowGraphComplexExample) {
+  // The following code has this graph (in DOT format):
+  //   digraph G {
+  //     "0" -> "20"
+  //     "0" -> "2"
+  //     "20" -> "21"
+  //     "4" -> "22 (ud2)"
+  //     "21" -> "22 (ud2)"
+  //     "4" -> "6"
+  //     "6" -> "7"
+  //     "2" -> "7"
+  //     "7" -> "8"
+  //     "8" -> "9 (indirect)"
+  //     "13" -> "15 (error)"
+  //     "13" -> "9 (indirect)"
+  //     "11" -> "9 (indirect)"
+  //   }
+  // Or, in image format: https://i.imgur.com/aX5fCoi.png
+
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x12,                   // 0: jne 20 [+18]
+          0xeb, 0x03,                   // 2: jmp 7 [+3]
+          0x75, 0x10,                   // 4: jne 22 [+16]
+          0x90,                         // 6: nop
+          0x90,                         // 7: nop
+          0x90,                         // 8: nop
+          0xff, 0x10,                   // 9: callq *(%rax)
+          0xeb, 0xfc,                   // 11: jmp 9 [-4]
+          0x75, 0xfa,                   // 13: jne 9 [-6]
+          0xe8, 0x78, 0x56, 0x34, 0x12, // 15: callq OUTOFBOUNDS [+0x12345678]
+          0x90,                         // 20: nop
+          0x90,                         // 21: nop
+          0x0f, 0x0b,                   // 22: ud2
+      },
+      0x1000);
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 5;
+
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0x1000 + 9);
+
+  EXPECT_THAT(Result.OrphanedNodes, SizeIs(1));
+  EXPECT_THAT(Result.BranchNodes, SizeIs(3));
+
+  EXPECT_THAT(
+      Result.OrphanedNodes,
+      Each(AllOf(Field(&ControlFlowNode::InstructionAddress, Eq(0x1000u + 11)),
+                 Property(&ControlFlowNode::flatten,
+                          ElementsAre(0x1000 + 11, 0x1000 + 9)))));
+
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0x1000 + 20, 0x1000 + 21, 0x1000 + 22))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0x1000 + 2, 0x1000 + 7, 0x1000 + 8,
+                                     0x1000 + 9))))));
+
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(true)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u + 4)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten, ElementsAre(0x1000 + 22))),
+          Field(&ConditionalBranchNode::Fallthrough,
+                Property(&ControlFlowNode::flatten,
+                         ElementsAre(0x1000 + 6, 0x1000 + 7, 0x1000 + 8,
+                                     0x1000 + 9))))));
+
+  EXPECT_THAT(
+      Result.BranchNodes,
+      Contains(AllOf(
+          Field(&ConditionalBranchNode::CFIProtection, Eq(false)),
+          Field(&ConditionalBranchNode::InstructionAddress, Eq(0x1000u + 13)),
+          Field(&ConditionalBranchNode::Target,
+                Property(&ControlFlowNode::flatten, ElementsAre(0x1000 + 9))),
+          Field(
+              &ConditionalBranchNode::Fallthrough,
+              Property(&ControlFlowNode::flatten, ElementsAre(0x1000 + 15))))));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+} // anonymous namespace
+} // end namespace cfi_verify
+} // end namespace llvm

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)