Add FileVerifier::isCFIProtected().

[hctim]

Summary

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

[hctim]

Update to only diff with prev in stack.

[hctim]

Fixed warnings.

[vlad.tsyrklevich]

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

tools/llvm-cfi-verify/FileVerifier.cpp

102 ↗

(On Diff #117452)

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

112 ↗

(On Diff #117452)

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

[hctim]

Fixed issues from Vlad's comments.

[hctim]

tools/llvm-cfi-verify/FileVerifier.cpp

112 ↗

(On Diff #117452)

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

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

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

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

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

[hctim]

Backported D38564

[hctim]

clang-format

[hctim]

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

[vlad.tsyrklevich]

tools/llvm-cfi-verify/FileAnalysis.cpp

168 ↗

(On Diff #118112)

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

tools/llvm-cfi-verify/FileAnalysis.h

72 ↗

(On Diff #118112)

isCFIProtectedIndirectBranch ?

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

46 ↗

(On Diff #118112)

Only print this line for indirect branches?

[hctim]

Updated from Vlad's comments.

[hctim]

tools/llvm-cfi-verify/FileAnalysis.h

72 ↗

(On Diff #118112)

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

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

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

46 ↗

(On Diff #118112)

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

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

[hctim]

Merged updates from stack.

[vlad.tsyrklevich]

tools/llvm-cfi-verify/FileAnalysis.h

72 ↗

(On Diff #118112)

How about isIndirectInstructionCFIProtected() ?

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

46 ↗

(On Diff #118112)

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

[hctim]

Vlad's comments & merged changes from the stack.

[hctim]

Added successful initialisation checks.

[hctim]

Patched in changes from master.

[hctim]

Merged master in preparation for submission.

llvm/trunk/tools/llvm-cfi-verify/lib/FileAnalysis.h

public:
 
   // 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 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;
 
   // Returns the instruction at the provided adress, dying if the instruction is
   // not found.
   const Instr &getInstructionOrDie(uint64_t Address) const;
 

llvm/trunk/tools/llvm-cfi-verify/lib/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/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"

 
 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::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 =
       Instructions.find(InstrMeta.VMAddress);
   if (KV == Instructions.end() || KV == Instructions.begin())
     return nullptr;
 
   if (!(--KV)->second.Valid)
Error FileAnalysis::initialiseDisassemblyMembers() {
   MCPU = "";
   std::string ErrorString;
 
   ObjectTarget =
       TargetRegistry::lookupTarget(ArchName, ObjectTriple, ErrorString);
   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)
     return make_error<UnsupportedDisassembly>(
         "Failed to initialise RegisterInfo.");
 
   AsmInfo.reset(ObjectTarget->createMCAsmInfo(*RegisterInfo, TripleName));
   if (!AsmInfo)

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

void printIndirectCFInstructions(const FileAnalysis &Verifier) {
   for (uint64_t Address : Verifier.getIndirectInstructions()) {
     const auto &InstrMeta = Verifier.getInstructionOrDie(Address);
     outs() << format_hex(Address, 2) << " |"
            << Verifier.getMCInstrInfo()->getName(
                   InstrMeta.Instruction.getOpcode())
            << " ";
     InstrMeta.Instruction.print(outs());
     outs() << "\n";
+    outs() << "  Protected? "
+           << Verifier.isIndirectInstructionCFIProtected(Address) << "\n";
   }
 }
 
 int main(int argc, char **argv) {
   cl::ParseCommandLineOptions(argc, argv);
 
   InitializeAllTargetInfos();
   InitializeAllTargetMCs();
   InitializeAllAsmParsers();
   InitializeAllDisassemblers();
 
   FileAnalysis Verifier = ExitOnErr(FileAnalysis::Create(InputFilename));
   printIndirectCFInstructions(Verifier);
 
   return EXIT_SUCCESS;
 }

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

 //===- llvm/unittests/tools/llvm-cfi-verify/FileAnalysis.cpp --------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "../tools/llvm-cfi-verify/lib/FileAnalysis.h"
+#include "../tools/llvm-cfi-verify/lib/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"
TEST_F(BasicFileAnalysisTest, ControlFlowXRefsTest) {
   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) {
+  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
 
 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();
 }