[cfi-verify] Validate there are no register clobbers between CFI-check and instruction execution.

[hctim]

Summary

This patch adds another failure mode for validateCFIProtection(..), wherein any register that affects the indirect control flow instruction is clobbered to between the CFI-check and the instruction's execution.

Also includes a modification to make MCInstrDesc::hasDefOfPhysReg public.

[vlad.tsyrklevich]

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

294

I think Branch should explicitly be declared a reference to avoid copies.

306

Reading the MCInstrDesc docs it makes it seem like this will ONLY check for implicit uses, not explicit uses. It's confusing why then your add $0, %eax unit tests below works, maybe it' s because you're implicitly defining rax by adding to eax. Could you try using an add rax instruction instead and see if that works?

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

304

BranchNode.IndirectCFIsOnTargetPath = (BranchTarget == Address);
if (BranchNode.IndirectCFIsOnTargetPath) {

[hctim]

Addressed Vlad's comments: Added an explicit register check and some minor changes.

Also changed instances of 'spill' to 'clobber' as it's more representative of what we're actually checking for.

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

294

Thanks, nice catch!

306

I was similarly confused by the naming/comment of hasImplicitDefOfPhysReg, I've added a test and it's all good. It's interesting as getImplicitUses is described as "Return a list of registers that are potentially read by any instance of this machine instruction", which would indicate that it also gets the explicit uses.

I'm not sure why the documentation is (apparently) wrong for hasImplicitDefOfPhysReg...

[vlad.tsyrklevich]

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

734

Take a look at [1]. This uses 0x05 which is an encoding specifically for add %eax, if you use an instruction that explicit encodes %rax in the ModR/M encoding like 48 83 c0 00 this test will fail. This is a bit silly since from the assembly writers perspective %rax is explicit here but it's not at the MC layer.

[1] http://x86.renejeschke.de/html/file_module_x86_id_5.html

*Also this still says %eax

[vlad.tsyrklevich]

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

734

Oh, I forgot to mention you can witness this with llvm-mc:

$ echo "0x48 0x83 0xc0 0x00" | llvm-mc --disassemble -show-inst -show-inst-operands
	.text
	addq	$0, %rax                # <MCInst #187 ADD64ri8
                                        #  <MCOperand Reg:35>
                                        #  <MCOperand Reg:35>
                                        #  <MCOperand Imm:0>>
$ echo "0x48 0x05 0x00 0x00 0x00 0x00" | llvm-mc --disassemble -show-inst -show-inst-operands
	.text
	addq	$0, %rax                # <MCInst #181 ADD64i32
                                        #  <MCOperand Imm:0>>

[hctim]

Updated clobber checking to use hasDefOfPhysReg rather than the implicit counterpart. This change now includes a modification to make MCInstrDesc::hasDefOfPhysReg public on pcc's reccomendation.

Also added an explicit unit test that sets rax then jumps to it, rather than relying on a REX prefix byte to target the register, as this was still considered an 'implicitly' changed register.

[hctim]

Merged master in preparation for submission.

[hctim]

/s/eax/rax

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

 enum CFIProtectionStatus {
   PROTECTED,            // This instruction is protected by CFI.
   FAIL_NOT_INDIRECT_CF, // The instruction is not an indirect control flow
                         // instruction, and thus shouldn't be protected.
   FAIL_ORPHANS, // There is a path to the instruction that was unexpected.
   FAIL_BAD_CONDITIONAL_BRANCH, // There is a path to the instruction from a
                                // conditional branch that does not properly
                                // check the destination for this vcall/icall.
+  FAIL_REGISTER_SPILLED, // One of the operands of the indirect CF instruction
+                         // is modified between the CFI-check and execution.
   FAIL_UNKNOWN, // Something strange happened, e.g. the instruction was not in
                 // this file.
 };
 
 StringRef stringCFIProtectionStatus(CFIProtectionStatus Status);
 
 // Disassembler and analysis tool for machine code files. Keeps track of non-
 // sequential control flows, including indirect control flow instructions.
public:
 
   // Returns the inlining information for the provided address.
   Expected<DIInliningInfo> symbolizeInlinedCode(uint64_t Address);
 
   // Returns whether the provided Graph represents a protected indirect control
   // flow instruction in this file.
   CFIProtectionStatus validateCFIProtection(const GraphResult &Graph) const;
 
+  // Returns the first place the operand register spills between the CFI-check
+  // and the indirect CF instruction execution. If the register does not spill,
+  // returns the address of the indirect CF instruction. The result is undefined
+  // if the provided graph does not fall under either the FAIL_REGISTER_SPILLED
+  // or PROTECTED status (see CFIProtectionStatus).
+  uint64_t indirectCFOperandSpill(const GraphResult& Graph) const;
+
   // Prints an instruction to the provided stream using this object's pretty-
   // printers.
   void printInstruction(const Instr &InstrMeta, raw_ostream &OS) const;
 
 protected:
   // Construct a blank object with the provided triple and features. Used in
   // testing, where a sub class will dependency inject protected methods to
   // allow analysis of raw binary, without requiring a fully valid ELF file.

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

StringRef stringCFIProtectionStatus(CFIProtectionStatus Status) {
   case PROTECTED:
     return "PROTECTED";
   case FAIL_NOT_INDIRECT_CF:
     return "FAIL_NOT_INDIRECT_CF";
   case FAIL_ORPHANS:
     return "FAIL_ORPHANS";
   case FAIL_BAD_CONDITIONAL_BRANCH:
     return "FAIL_BAD_CONDITIONAL_BRANCH";
+  case FAIL_REGISTER_SPILLED:
+    return "FAIL_REGISTER_SPILLED";
   case FAIL_UNKNOWN:
     return "FAIL_UNKNOWN";
   }
   return "FAIL_UNKNOWN";
 }
 
 Expected<FileAnalysis> FileAnalysis::Create(StringRef Filename) {
   // Open the filename provided.
FileAnalysis::validateCFIProtection(const GraphResult &Graph) const {
   if (!Graph.OrphanedNodes.empty())
     return FAIL_ORPHANS;
 
   for (const auto &BranchNode : Graph.ConditionalBranchNodes) {
     if (!BranchNode.CFIProtection)
       return FAIL_BAD_CONDITIONAL_BRANCH;
   }
 
+  if (indirectCFOperandSpill(Graph) != Graph.BaseAddress)
+    return FAIL_REGISTER_SPILLED;
+
   return PROTECTED;
 }
 
+uint64_t FileAnalysis::indirectCFOperandSpill(const GraphResult &Graph) const {
+  assert(Graph.OrphanedNodes.empty() && "Orphaned nodes should be empty.");
+
+  // Get the set of registers we must spill check.
+  const Instr &IndirectCF = getInstructionOrDie(Graph.BaseAddress);
+  DenseSet<unsigned> RegisterNumbers;
+  for (const auto &Operand : IndirectCF.Instruction) {
+    if (Operand.isReg())
+      RegisterNumbers.insert(Operand.getReg());
+  }
+  assert(RegisterNumbers.size() && "Zero register operands on indirect CF.");
+
+  // Now check all branches to indirect CFs and ensure no spill happens.
+  for (const auto Branch : Graph.ConditionalBranchNodes) {
+    uint64_t Node;
+    if (Branch.IndirectCFIsOnTargetPath)
+      Node = Branch.Target;
+    else
+      Node = Branch.Fallthrough;
+
+    while (Node != Graph.BaseAddress) {
+      const Instr &NodeInstr = getInstructionOrDie(Node);
+      const auto &InstrDesc = MII->get(NodeInstr.Instruction.getOpcode());
+
+      for (unsigned RegNum : RegisterNumbers) {
+        if (InstrDesc.hasImplicitDefOfPhysReg(RegNum, RegisterInfo.get()))
+          return Node;
+      }
+
+      const auto &KV = Graph.IntermediateNodes.find(Node);
+      assert((KV != Graph.IntermediateNodes.end()) &&
+             "Could not get next node.");
+      Node = KV->second;
+    }
+  }
+
+  return Graph.BaseAddress;
+}
+
 void FileAnalysis::printInstruction(const Instr &InstrMeta,
                                     raw_ostream &OS) const {
   Printer->printInst(&InstrMeta.Instruction, OS, "", *SubtargetInfo.get());
 }
 
 Error FileAnalysis::initialiseDisassemblyMembers() {
   std::string TripleName = ObjectTriple.getTriple();
   ArchName = "";

tools/llvm-cfi-verify/lib/GraphBuilder.h

struct ConditionalBranchNode {
   uint64_t Address;
   uint64_t Target;
   uint64_t Fallthrough;
   // Does this conditional branch look like it's used for CFI protection? i.e.
   //  - The exit point of a basic block whos entry point is {target|fallthrough}
   //    is a CFI trap, and...
   //  - The exit point of the other basic block is an undirect CF instruction.
   bool CFIProtection;
+  bool IndirectCFIsOnTargetPath;
 };
 
 // The canonical graph result structure returned by GraphBuilder. The members
 // in this structure encapsulate all possible code paths to the instruction
 // located at `BaseAddress`.
 struct GraphResult {
   uint64_t BaseAddress;
 

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

for (const auto *ParentMetaPtr : CFCrossRefs) {
     // Only direct conditional branches should be present at this point. Setup
     // a conditional branch node and build flows to the ud2.
     ConditionalBranchNode BranchNode;
     BranchNode.Address = ParentMeta.VMAddress;
     BranchNode.Target = 0;
     BranchNode.Fallthrough = 0;
     BranchNode.CFIProtection = false;
 
-    if (BranchTarget == Address)
+    if (BranchTarget == Address) {
       BranchNode.Target = Address;
-    else
+      BranchNode.IndirectCFIsOnTargetPath = true;
+    } else {
       BranchNode.Fallthrough = Address;
+      BranchNode.IndirectCFIsOnTargetPath = false;
+    }
 
     HasValidCrossRef = true;
     buildFlowsToUndefined(Analysis, Result, BranchNode, ParentMeta);
     Result.ConditionalBranchNodes.push_back(BranchNode);
   }
 
   if (!HasValidCrossRef)
     Result.OrphanedNodes.push_back(Address);
 
   OpenedNodes.erase(Address);
 }
 
 } // namespace cfi_verify
 } // namespace llvm

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

TEST_F(BasicFileAnalysisTest, UndefSearchLengthOneTestFarAway) {
   Result = GraphBuilder::buildFlowGraph(Analysis, 0x775a68);
   EXPECT_EQ(PROTECTED, Analysis.validateCFIProtection(Result));
   SearchLengthForUndef = 3;
   Result = GraphBuilder::buildFlowGraph(Analysis, 0x775a68);
   EXPECT_EQ(PROTECTED, Analysis.validateCFIProtection(Result));
   SearchLengthForUndef = PrevSearchLengthForUndef;
 }
 
+TEST_F(BasicFileAnalysisTest, CFIProtectionSpillSinglePath) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02,                   // 0: jne 4 [+2]
+          0x0f, 0x0b,                   // 2: ud2
+          0x05, 0x00, 0x00, 0x00, 0x00, // 4: add $0x0, %eax
+          0xff, 0x10,                   // 9: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 9);
+  EXPECT_EQ(FAIL_REGISTER_SPILLED, Analysis.validateCFIProtection(Result));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionSpillDualPath) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x04, // 0: jne 6 [+4]
+          0x0f, 0x31, // 2: rdtsc (note: affects eax)
+          0xff, 0x10, // 4: callq *(%rax)
+          0x0f, 0x0b, // 6: ud2
+          0x75, 0xf9, // 8: jne 2 [-7]
+          0x0f, 0x0b, // 10: ud2
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 4);
+  EXPECT_EQ(FAIL_REGISTER_SPILLED, Analysis.validateCFIProtection(Result));
+}
+
 } // 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();
 }