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

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

tools/llvm-cfi-verify/FileAnalysis.h

72

isCFIProtectedIndirectBranch ?

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

46

Only print this line for indirect branches?

[hctim]

Updated from Vlad's comments.

[hctim]

tools/llvm-cfi-verify/FileAnalysis.h

72

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

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

How about isIndirectInstructionCFIProtected() ?

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

46

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

[hctim]

Vlad's comments & merged changes from the stack.

[hctim]

Added successful initialisation checks.

[hctim]

Patched in changes from master.

[hctim]

Merged master in preparation for submission.

tools/llvm-cfi-verify/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 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;

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/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::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) {
+    assert(BranchNode && "Branch node contained nullptr.");
+    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)
bool FileAnalysis::canFallThrough(const Instr &InstrMeta) const {
 
   const auto &InstrDesc = MII->get(InstrMeta.Instruction.getOpcode());
   if (InstrDesc.mayAffectControlFlow(InstrMeta.Instruction, *RegisterInfo))
     return InstrDesc.isConditionalBranch();
 
   return true;
 }
 
+bool FileAnalysis::usesRegisterOperand(const Instr& InstrMeta) const {
+  for (const auto &Operand : InstrMeta.Instruction) {
+    if (Operand.isReg())
+      return true;
+  }
+  return false;
+}
+
 const Instr *
 FileAnalysis::getDefiniteNextInstruction(const Instr &InstrMeta) const {
   if (!InstrMeta.Valid)
     return nullptr;
 
   if (isCFITrap(InstrMeta))
     return nullptr;
 
for (uint64_t Byte = 0; Byte < SectionBytes.size();) {
     uint64_t Target;
     if (MIA->evaluateBranch(Instruction, VMAddress, InstructionSize, Target)) {
       // If the target can be evaluated, it's not indirect.
       StaticBranchTargetings[Target].push_back(VMAddress);
       continue;
     }
 
     // Skip instructions that do not operate on register operands.
-    bool UsesRegisterOperand = false;
-    for (const auto &Operand : Instruction) {
-      if (Operand.isReg())
-        UsesRegisterOperand = true;
-    }
-
-    if (!UsesRegisterOperand)
+    if (!usesRegisterOperand(InstrMeta))
       continue;
 
     IndirectInstructions.insert(VMAddress);
   }
 }
 
 void FileAnalysis::addInstruction(const Instr &Instruction) {
   Instructions[Instruction.VMAddress] = Instruction;

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.isCFIProtected(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;
 }

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"
Analysis.parseSectionContents(
           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)));
+  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)
TEST_F(BasicFileAnalysisTest, ControlFlowXRefsTest) {
   XRefs = Analysis.getControlFlowXRefs(*InstrMetaPtr);
   EXPECT_TRUE(Analysis.getControlFlowXRefs(*InstrMetaPtr).empty());
 
   InstrMetaPtr = &Analysis.getInstructionOrDie(0xDEADBEEF + 38);
   XRefs = Analysis.getControlFlowXRefs(*InstrMetaPtr);
   EXPECT_TRUE(Analysis.getControlFlowXRefs(*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();
 }