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

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

112

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

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.

tools/llvm-cfi-verify/FileVerifier.h

public:
   // constructor, prefer to use FileVerifier::Create instead.
   FileVerifier(object::OwningBinary<object::Binary> Binary);
   FileVerifier() = delete;
   FileVerifier(const FileVerifier &) = delete;
   FileVerifier(FileVerifier &&Other) = default;
 
   Error printIndirectCFInstructions() const;
 
+  // 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;
 

tools/llvm-cfi-verify/FileVerifier.cpp

 #include "FileVerifier.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"
if (InstructionKV == Instructions.end())
           formatv("No instruction found at address {0:x}", Address),
           inconvertibleErrorCode());
 
     const auto &InstrMeta = InstructionKV->second;
     outs() << format_hex(Address, 2) << " [" << InstrMeta.SectionName
            << "] = " << MII->getName(InstrMeta.Instruction.getOpcode()) << " ";
     InstrMeta.Instruction.print(outs());
     outs() << "\n";
+    outs() << "  Protected? " << isCFIProtected(Address) << "\n";
   }
 
   return Error::success();
 }
 
+bool FileVerifier::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;
+
+  bool UsesRegisterOperand = false;
+  for (const auto &Operand : InstrMetaPtr->Instruction)
+    if (Operand.isReg())
+      UsesRegisterOperand = true;
+
+  if (!UsesRegisterOperand)
+    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 *
 FileVerifier::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.Bad)

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

 //===- llvm/tools/llvm-cfi-verify/unittests/FileVerifier.cpp --------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "../FileVerifier.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"
TEST_F(BasicFileVerifierTest, ControlFlowXRefsTest) {
   XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
   EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
 
   InstrMetaPtr = &Verifier.getInstructionOrDie(0xDEADBEEF + 38);
   XRefs = Verifier.getControlFlowXRefs(*InstrMetaPtr);
   EXPECT_TRUE(Verifier.getControlFlowXRefs(*InstrMetaPtr).empty());
 }
 
+TEST_F(BasicFileVerifierTest, CFIProtectionInvalidTargets) {
+  Verifier.parseSectionContents(
+      {
+          0x90,       // 0: nop
+          0x0f, 0x0b, // 1: ud2
+          0x75, 0x00, // 3: jne 5 [+0]
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF));
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 1));
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 3));
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADC0DE));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionBasicFallthroughToUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0x0f, 0x0b, // 2: ud2
+          0xff, 0x10, // 4: callq *(%rax)
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionBasicJumpToUd2) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x02, // 0: jne 4 [+2]
+          0xff, 0x10, // 2: callq *(%rax)
+          0x0f, 0x0b, // 4: ud2
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 2));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionDualPathUd2) {
+  Verifier.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, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionDualPathSingleUd2) {
+  Verifier.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, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 3));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionDualFailLimitUpwards) {
+  Verifier.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, "Test");
+  uint64_t PrevSearchLengthForConditionalBranch =
+      SearchLengthForConditionalBranch;
+  SearchLengthForConditionalBranch = 2;
+
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 6));
+
+  SearchLengthForConditionalBranch = PrevSearchLengthForConditionalBranch;
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionDualFailLimitDownwards) {
+  Verifier.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, "Test");
+  uint64_t PrevSearchLengthForUndef = SearchLengthForUndef;
+  SearchLengthForUndef = 2;
+
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 2));
+
+  SearchLengthForUndef = PrevSearchLengthForUndef;
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionGoodAndBadPaths) {
+  Verifier.parseSectionContents(
+      {
+          0xeb, 0x02, // 0: jmp 4 [+2]
+          0x75, 0x02, // 2: jne 6 [+2]
+          0xff, 0x10, // 4: callq *(%rax)
+          0x0f, 0x0b, // 6: ud2
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_FALSE(Verifier.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionWithUnconditionalJumpInFallthrough) {
+  Verifier.parseSectionContents(
+      {
+          0x75, 0x04, // 0: jne 6 [+4]
+          0xeb, 0x00, // 2: jmp 4 [+0]
+          0xff, 0x10, // 4: callq *(%rax)
+          0x0f, 0x0b, // 6: ud2
+      },
+      0xDEADBEEF, "Test");
+  EXPECT_TRUE(Verifier.isCFIProtected(0xDEADBEEF + 4));
+}
+
+TEST_F(BasicFileVerifierTest, CFIProtectionComplexExample) {
+  // See unittests/GraphBuilder.cpp::BuildFlowGraphComplexExample for this
+  // graph.
+  Verifier.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, "Test");
+  EXPECT_FALSE(Verifier.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();
 }