[cfi-verify] Made FileAnalysis operate on a GraphResult rather than build one and validate it.

Refactors the behaviour of building graphs out of FileAnalysis, allowing for analysis of the GraphResult by the callee without having to rebuild the graph. Means when we want to analyse the constructed graph (planned for later revisions), we don't do repeated work.

Also makes CFI verification in FileAnalysis now return an enum that allows us to differentiate why something failed, not just that it did/didn't fail.

Reviewers: vlad.tsyrklevich

Subscribers: kcc, pcc, llvm-commits

Differential Revision: https://reviews.llvm.org/D39764

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@317927 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 127 insertions, 64 deletions

diff --git a/tools/llvm-cfi-verify/lib/FileAnalysis.cpp b/tools/llvm-cfi-verify/lib/FileAnalysis.cpp
index 863bbfb045e..42de8cb4f7d 100644
--- a/tools/llvm-cfi-verify/lib/FileAnalysis.cpp
+++ b/tools/llvm-cfi-verify/lib/FileAnalysis.cpp
@@ -54,6 +54,22 @@ static cl::opt<bool, true> IgnoreDWARFArg(
         "will result in false positives for 'CFI unprotected' instructions."),
     cl::location(IgnoreDWARFFlag), cl::init(false));
 
+StringRef stringCFIProtectionStatus(CFIProtectionStatus Status) {
+  switch (Status) {
+  case CFIProtectionStatus::PROTECTED:
+    return "PROTECTED";
+  case CFIProtectionStatus::FAIL_NOT_INDIRECT_CF:
+    return "FAIL_NOT_INDIRECT_CF";
+  case CFIProtectionStatus::FAIL_ORPHANS:
+    return "FAIL_ORPHANS";
+  case CFIProtectionStatus::FAIL_BAD_CONDITIONAL_BRANCH:
+    return "FAIL_BAD_CONDITIONAL_BRANCH";
+  case CFIProtectionStatus::FAIL_INVALID_INSTRUCTION:
+    return "FAIL_INVALID_INSTRUCTION";
+  }
+  llvm_unreachable("Attempted to stringify an unknown enum value.");
+}
+
 Expected<FileAnalysis> FileAnalysis::Create(StringRef Filename) {
   // Open the filename provided.
   Expected<object::OwningBinary<object::Binary>> BinaryOrErr =
@@ -89,32 +105,6 @@ FileAnalysis::FileAnalysis(const Triple &ObjectTriple,
                            const SubtargetFeatures &Features)
     : ObjectTriple(ObjectTriple), Features(Features) {}
 
-bool FileAnalysis::isIndirectInstructionCFIProtected(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.ConditionalBranchNodes) {
-    if (!BranchNode.CFIProtection)
-      return false;
-  }
-
-  return true;
-}
-
 const Instr *
 FileAnalysis::getPrevInstructionSequential(const Instr &InstrMeta) const {
   std::map<uint64_t, Instr>::const_iterator KV =
@@ -254,7 +244,34 @@ const MCInstrAnalysis *FileAnalysis::getMCInstrAnalysis() const {
   return MIA.get();
 }
 
-LLVMSymbolizer &FileAnalysis::getSymbolizer() { return *Symbolizer; }
+Expected<DIInliningInfo> FileAnalysis::symbolizeInlinedCode(uint64_t Address) {
+  assert(Symbolizer != nullptr && "Symbolizer is invalid.");
+  return Symbolizer->symbolizeInlinedCode(Object->getFileName(), Address);
+}
+
+CFIProtectionStatus
+FileAnalysis::validateCFIProtection(const GraphResult &Graph) const {
+  const Instr *InstrMetaPtr = getInstruction(Graph.BaseAddress);
+  if (!InstrMetaPtr)
+    return CFIProtectionStatus::FAIL_INVALID_INSTRUCTION;
+
+  const auto &InstrDesc = MII->get(InstrMetaPtr->Instruction.getOpcode());
+  if (!InstrDesc.mayAffectControlFlow(InstrMetaPtr->Instruction, *RegisterInfo))
+    return CFIProtectionStatus::FAIL_NOT_INDIRECT_CF;
+
+  if (!usesRegisterOperand(*InstrMetaPtr))
+    return CFIProtectionStatus::FAIL_NOT_INDIRECT_CF;
+
+  if (!Graph.OrphanedNodes.empty())
+    return CFIProtectionStatus::FAIL_ORPHANS;
+
+  for (const auto &BranchNode : Graph.ConditionalBranchNodes) {
+    if (!BranchNode.CFIProtection)
+      return CFIProtectionStatus::FAIL_BAD_CONDITIONAL_BRANCH;
+  }
+
+  return CFIProtectionStatus::PROTECTED;
+}
 
 Error FileAnalysis::initialiseDisassemblyMembers() {
   std::string TripleName = ObjectTriple.getTriple();
diff --git a/tools/llvm-cfi-verify/lib/FileAnalysis.h b/tools/llvm-cfi-verify/lib/FileAnalysis.h
index e0eecb037c3..dfeff13863b 100644
--- a/tools/llvm-cfi-verify/lib/FileAnalysis.h
+++ b/tools/llvm-cfi-verify/lib/FileAnalysis.h
@@ -44,8 +44,29 @@
 namespace llvm {
 namespace cfi_verify {
 
+struct GraphResult;
+
 extern bool IgnoreDWARFFlag;
 
+enum class CFIProtectionStatus {
+  // This instruction is protected by CFI.
+  PROTECTED,
+  // The instruction is not an indirect control flow instruction, and thus
+  // shouldn't be protected.
+  FAIL_NOT_INDIRECT_CF,
+  // There is a path to the instruction that was unexpected.
+  FAIL_ORPHANS,
+  // There is a path to the instruction from a conditional branch that does not
+  // properly check the destination for this vcall/icall.
+  FAIL_BAD_CONDITIONAL_BRANCH,
+  // The instruction referenced does not exist. This normally indicates an
+  // error in the program, where you try and validate a graph that was created
+  // in a different FileAnalysis object.
+  FAIL_INVALID_INSTRUCTION,
+};
+
+StringRef stringCFIProtectionStatus(CFIProtectionStatus Status);
+
 // Disassembler and analysis tool for machine code files. Keeps track of non-
 // sequential control flows, including indirect control flow instructions.
 class FileAnalysis {
@@ -69,12 +90,6 @@ public:
   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 isIndirectInstructionCFIProtected(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;
@@ -122,19 +137,13 @@ public:
   const MCRegisterInfo *getRegisterInfo() const;
   const MCInstrInfo *getMCInstrInfo() const;
   const MCInstrAnalysis *getMCInstrAnalysis() const;
-  symbolize::LLVMSymbolizer &getSymbolizer();
-
-  // Returns true if this class is using DWARF line tables for elimination.
-  bool hasLineTableInfo() const;
 
-  // Returns the line table information for the range {Address +-
-  // DWARFSearchRange}. Returns an empty table if the address has no valid line
-  // table information, or this analysis object has DWARF handling disabled.
-  DILineInfoTable getLineInfoForAddressRange(uint64_t Address);
+  // Returns the inlining information for the provided address.
+  Expected<DIInliningInfo> symbolizeInlinedCode(uint64_t Address);
 
-  // Returns whether the provided address has valid line information for
-  // instructions in the range of Address +- DWARFSearchRange.
-  bool hasValidLineInfoForAddressRange(uint64_t Address);
+  // Returns whether the provided Graph represents a protected indirect control
+  // flow instruction in this file.
+  CFIProtectionStatus validateCFIProtection(const GraphResult &Graph) const;
 
 protected:
   // Construct a blank object with the provided triple and features. Used in
diff --git a/tools/llvm-cfi-verify/llvm-cfi-verify.cpp b/tools/llvm-cfi-verify/llvm-cfi-verify.cpp
index 01f03158d6b..8ae905e2636 100644
--- a/tools/llvm-cfi-verify/llvm-cfi-verify.cpp
+++ b/tools/llvm-cfi-verify/llvm-cfi-verify.cpp
@@ -18,6 +18,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "lib/FileAnalysis.h"
+#include "lib/GraphBuilder.h"
 
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/CommandLine.h"
@@ -46,13 +47,15 @@ void printIndirectCFInstructions(FileAnalysis &Analysis,
   uint64_t ExpectedUnprotected = 0;
   uint64_t UnexpectedUnprotected = 0;
 
-  symbolize::LLVMSymbolizer &Symbolizer = Analysis.getSymbolizer();
   std::map<unsigned, uint64_t> BlameCounter;
 
   for (uint64_t Address : Analysis.getIndirectInstructions()) {
     const auto &InstrMeta = Analysis.getInstructionOrDie(Address);
+    GraphResult Graph = GraphBuilder::buildFlowGraph(Analysis, Address);
 
-    bool CFIProtected = Analysis.isIndirectInstructionCFIProtected(Address);
+    CFIProtectionStatus ProtectionStatus =
+        Analysis.validateCFIProtection(Graph);
+    bool CFIProtected = (ProtectionStatus == CFIProtectionStatus::PROTECTED);
 
     if (CFIProtected)
       outs() << "P ";
@@ -72,7 +75,7 @@ void printIndirectCFInstructions(FileAnalysis &Analysis,
       continue;
     }
 
-    auto InliningInfo = Symbolizer.symbolizeInlinedCode(InputFilename, Address);
+    auto InliningInfo = Analysis.symbolizeInlinedCode(Address);
     if (!InliningInfo || InliningInfo->getNumberOfFrames() == 0) {
       errs() << "Failed to symbolise " << format_hex(Address, 2)
              << " with line tables from " << InputFilename << "\n";
diff --git a/unittests/tools/llvm-cfi-verify/FileAnalysis.cpp b/unittests/tools/llvm-cfi-verify/FileAnalysis.cpp
index 00346ab5a14..3e8954f7a11 100644
--- a/unittests/tools/llvm-cfi-verify/FileAnalysis.cpp
+++ b/unittests/tools/llvm-cfi-verify/FileAnalysis.cpp
@@ -493,10 +493,18 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionInvalidTargets) {
           0x75, 0x00, // 3: jne 5 [+0]
       },
       0xDEADBEEF);
-  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF));
-  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 1));
-  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 3));
-  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADC0DE));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_NOT_INDIRECT_CF,
+            Analysis.validateCFIProtection(Result));
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 1);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_NOT_INDIRECT_CF,
+            Analysis.validateCFIProtection(Result));
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_NOT_INDIRECT_CF,
+            Analysis.validateCFIProtection(Result));
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0x12345678);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_INVALID_INSTRUCTION,
+            Analysis.validateCFIProtection(Result));
 }
 
 TEST_F(BasicFileAnalysisTest, CFIProtectionBasicFallthroughToUd2) {
@@ -509,7 +517,9 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionBasicFallthroughToUd2) {
           0xff, 0x10, // 4: callq *(%rax)
       },
       0xDEADBEEF);
-  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 4));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+  EXPECT_EQ(CFIProtectionStatus::PROTECTED,
+            Analysis.validateCFIProtection(Result));
 }
 
 TEST_F(BasicFileAnalysisTest, CFIProtectionBasicJumpToUd2) {
@@ -522,7 +532,9 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionBasicJumpToUd2) {
           0x0f, 0x0b, // 4: ud2
       },
       0xDEADBEEF);
-  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 2));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+  EXPECT_EQ(CFIProtectionStatus::PROTECTED,
+            Analysis.validateCFIProtection(Result));
 }
 
 TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathUd2) {
@@ -538,7 +550,9 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathUd2) {
           0x0f, 0x0b, // 9: ud2
       },
       0xDEADBEEF);
-  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 3));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
+  EXPECT_EQ(CFIProtectionStatus::PROTECTED,
+            Analysis.validateCFIProtection(Result));
 }
 
 TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathSingleUd2) {
@@ -553,7 +567,9 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathSingleUd2) {
           0x0f, 0x0b, // 7: ud2
       },
       0xDEADBEEF);
-  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 3));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 3);
+  EXPECT_EQ(CFIProtectionStatus::PROTECTED,
+            Analysis.validateCFIProtection(Result));
 }
 
 TEST_F(BasicFileAnalysisTest, CFIProtectionDualFailLimitUpwards) {
@@ -574,7 +590,9 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionDualFailLimitUpwards) {
       SearchLengthForConditionalBranch;
   SearchLengthForConditionalBranch = 2;
 
-  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 6));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 6);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_ORPHANS,
+            Analysis.validateCFIProtection(Result));
 
   SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
 }
@@ -596,7 +614,9 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionDualFailLimitDownwards) {
   uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
   SearchLengthForUndef = 2;
 
-  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 2));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 2);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_BAD_CONDITIONAL_BRANCH,
+            Analysis.validateCFIProtection(Result));
 
   SearchLengthForUndef = PrevSearchLengthForUndef;
 }
@@ -612,7 +632,9 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionGoodAndBadPaths) {
           0x0f, 0x0b, // 6: ud2
       },
       0xDEADBEEF);
-  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 4));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_ORPHANS,
+            Analysis.validateCFIProtection(Result));
 }
 
 TEST_F(BasicFileAnalysisTest, CFIProtectionWithUnconditionalJumpInFallthrough) {
@@ -626,7 +648,9 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionWithUnconditionalJumpInFallthrough) {
           0x0f, 0x0b, // 6: ud2
       },
       0xDEADBEEF);
-  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 4));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+  EXPECT_EQ(CFIProtectionStatus::PROTECTED,
+            Analysis.validateCFIProtection(Result));
 }
 
 TEST_F(BasicFileAnalysisTest, CFIProtectionComplexExample) {
@@ -653,7 +677,9 @@ TEST_F(BasicFileAnalysisTest, CFIProtectionComplexExample) {
       0xDEADBEEF);
   uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
   SearchLengthForUndef = 5;
-  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 9));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 9);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_ORPHANS,
+            Analysis.validateCFIProtection(Result));
   SearchLengthForUndef = PrevSearchLengthForUndef;
 }
 
@@ -670,7 +696,9 @@ TEST_F(BasicFileAnalysisTest, UndefSearchLengthOneTest) {
       0x688118);
   uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
   SearchLengthForUndef = 1;
-  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0x68811d));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0x68811d);
+  EXPECT_EQ(CFIProtectionStatus::PROTECTED,
+            Analysis.validateCFIProtection(Result));
   SearchLengthForUndef = PrevSearchLengthForUndef;
 }
 
@@ -699,11 +727,17 @@ TEST_F(BasicFileAnalysisTest, UndefSearchLengthOneTestFarAway) {
       0x775e0e);
   uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
   SearchLengthForUndef = 1;
-  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0x775a68));
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0x775a68);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_BAD_CONDITIONAL_BRANCH,
+            Analysis.validateCFIProtection(Result));
   SearchLengthForUndef = 2;
-  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0x775a68));
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0x775a68);
+  EXPECT_EQ(CFIProtectionStatus::PROTECTED,
+            Analysis.validateCFIProtection(Result));
   SearchLengthForUndef = 3;
-  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0x775a68));
+  Result = GraphBuilder::buildFlowGraph(Analysis, 0x775a68);
+  EXPECT_EQ(CFIProtectionStatus::PROTECTED,
+            Analysis.validateCFIProtection(Result));
   SearchLengthForUndef = PrevSearchLengthForUndef;
 }