Add FileVerifier::isCFIProtected().

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

Reviewers: vlad.tsyrklevich

Subscribers: llvm-commits, kcc, pcc, mgorny

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

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

4 files changed, 209 insertions, 1 deletions

diff --git a/tools/llvm-cfi-verify/lib/FileAnalysis.cpp b/tools/llvm-cfi-verify/lib/FileAnalysis.cpp
index 761b2ab1037f..928571bfd0a4 100644
--- a/tools/llvm-cfi-verify/lib/FileAnalysis.cpp
+++ b/tools/llvm-cfi-verify/lib/FileAnalysis.cpp
@@ -8,6 +8,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "FileAnalysis.h"
+#include "GraphBuilder.h"
 
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/MC/MCAsmInfo.h"
@@ -76,6 +77,32 @@ 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 =
@@ -226,7 +253,8 @@ Error FileAnalysis::initialiseDisassemblyMembers() {
   if (!ObjectTarget)
     return make_error<UnsupportedDisassembly>(
         (Twine("Couldn't find target \"") + ObjectTriple.getTriple() +
-        "\", failed with error: " + ErrorString).str());
+         "\", failed with error: " + ErrorString)
+            .str());
 
   RegisterInfo.reset(ObjectTarget->createMCRegInfo(TripleName));
   if (!RegisterInfo)
diff --git a/tools/llvm-cfi-verify/lib/FileAnalysis.h b/tools/llvm-cfi-verify/lib/FileAnalysis.h
index 803eeee97e04..1ed575bb9e43 100644
--- a/tools/llvm-cfi-verify/lib/FileAnalysis.h
+++ b/tools/llvm-cfi-verify/lib/FileAnalysis.h
@@ -66,6 +66,12 @@ 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;
diff --git a/tools/llvm-cfi-verify/llvm-cfi-verify.cpp b/tools/llvm-cfi-verify/llvm-cfi-verify.cpp
index c363cb1a6cba..00324ed0eb41 100644
--- a/tools/llvm-cfi-verify/llvm-cfi-verify.cpp
+++ b/tools/llvm-cfi-verify/llvm-cfi-verify.cpp
@@ -43,6 +43,8 @@ void printIndirectCFInstructions(const FileAnalysis &Verifier) {
            << " ";
     InstrMeta.Instruction.print(outs());
     outs() << "\n";
+    outs() << "  Protected? "
+           << Verifier.isIndirectInstructionCFIProtected(Address) << "\n";
   }
 }
 
diff --git a/unittests/tools/llvm-cfi-verify/FileAnalysis.cpp b/unittests/tools/llvm-cfi-verify/FileAnalysis.cpp
index c94a0fc75d9a..0df468e8995c 100644
--- a/unittests/tools/llvm-cfi-verify/FileAnalysis.cpp
+++ b/unittests/tools/llvm-cfi-verify/FileAnalysis.cpp
@@ -8,6 +8,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "../tools/llvm-cfi-verify/lib/FileAnalysis.h"
+#include "../tools/llvm-cfi-verify/lib/GraphBuilder.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
@@ -481,6 +482,177 @@ TEST_F(BasicFileAnalysisTest, ControlFlowXRefsTest) {
   EXPECT_TRUE(Analysis.getDirectControlFlowXRefs(*InstrMetaPtr).empty());
 }
 
+TEST_F(BasicFileAnalysisTest, CFIProtectionInvalidTargets) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x90,       // 0: nop
+          0x0f, 0x0b, // 1: ud2
+          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));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionBasicFallthroughToUd2) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0x0f, 0x0b, // 2: ud2
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionBasicJumpToUd2) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x0f, 0x0b, // 4: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 2));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathUd2) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x03, // 0: jne 5 [+3]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x0f, 0x0b, // 5: ud2
+          0x75, 0xf9, // 7: jne 2 [-7]
+          0x0f, 0x0b, // 9: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualPathSingleUd2) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x05, // 0: jne 7 [+5]
+          0x90,       // 2: nop
+          0xff, 0x10, // 3: callq *(%rax)
+          0x75, 0xfb, // 5: jne 2 [-5]
+          0x0f, 0x0b, // 7: ud2
+      },
+      0xDEADBEEF);
+  EXPECT_TRUE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualFailLimitUpwards) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x06, // 0: jne 8 [+6]
+          0x90,       // 2: nop
+          0x90,       // 3: nop
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0xff, 0x10, // 6: callq *(%rax)
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForConditionalBranch =
+      SearchLengthForConditionalBranch;
+  SearchLengthForConditionalBranch = 2;
+
+  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 6));
+
+  SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionDualFailLimitDownwards) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x90,       // 4: nop
+          0x90,       // 5: nop
+          0x90,       // 6: nop
+          0x90,       // 7: nop
+          0x0f, 0x0b, // 8: ud2
+      },
+      0xDEADBEEF);
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 2;
+
+  EXPECT_FALSE(Analysis.isIndirectInstructionCFIProtected(0xDEADBEEF + 2));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionGoodAndBadPaths) {
+  if (!SuccessfullyInitialised)
+    return;
+  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.isIndirectInstructionCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionWithUnconditionalJumpInFallthrough) {
+  if (!SuccessfullyInitialised)
+    return;
+  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.isIndirectInstructionCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionComplexExample) {
+  if (!SuccessfullyInitialised)
+    return;
+  // 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.isIndirectInstructionCFIProtected(0xDEADBEEF + 9));
+}
+
 } // anonymous namespace
 } // end namespace cfi_verify
 } // end namespace llvm