[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

306

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

751

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

751

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

include/llvm/MC/MCInstrDesc.h

public:
   unsigned char Size;            // Number of bytes in encoding.
   unsigned short SchedClass;     // enum identifying instr sched class
   uint64_t Flags;                // Flags identifying machine instr class
   uint64_t TSFlags;              // Target Specific Flag values
   const MCPhysReg *ImplicitUses; // Registers implicitly read by this instr
   const MCPhysReg *ImplicitDefs; // Registers implicitly defined by this instr
   const MCOperandInfo *OpInfo;   // 'NumOperands' entries about operands
   // Subtarget feature that this is deprecated on, if any
-  // -1 implies this is not deprecated by any single feature. It may still be 
+  // -1 implies this is not deprecated by any single feature. It may still be
   // deprecated due to a "complex" reason, below.
   int64_t DeprecatedFeature;
 
   // A complex method to determine is a certain is deprecated or not, and return
   // the reason for deprecation.
   bool (*ComplexDeprecationInfo)(MCInst &, const MCSubtargetInfo &,
                                  std::string &);
 
int findFirstPredOperandIdx() const {
     if (isPredicable()) {
       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
         if (OpInfo[i].isPredicate())
           return i;
     }
     return -1;
   }
 
-private:
-
   /// \brief Return true if this instruction defines the specified physical
   /// register, either explicitly or implicitly.
   bool hasDefOfPhysReg(const MCInst &MI, unsigned Reg,
                        const MCRegisterInfo &RI) const;
 };
 
 } // end namespace llvm
 
 #endif

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

enum class CFIProtectionStatus {
   // The instruction is not an indirect control flow instruction, and thus
   // shouldn't be protected.
   FAIL_NOT_INDIRECT_CF,
   // There is a path to the instruction that was unexpected.
   FAIL_ORPHANS,
   // There is a path to the instruction from a conditional branch that does not
   // properly check the destination for this vcall/icall.
   FAIL_BAD_CONDITIONAL_BRANCH,
+  // One of the operands of the indirect CF instruction is modified between the
+  // CFI-check and execution.
+  FAIL_REGISTER_CLOBBERED,
   // The instruction referenced does not exist. This normally indicates an
   // error in the program, where you try and validate a graph that was created
   // in a different FileAnalysis object.
   FAIL_INVALID_INSTRUCTION,
 };
 
 StringRef stringCFIProtectionStatus(CFIProtectionStatus Status);
 
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 is clobbered between the CFI-
+  // check and the indirect CF instruction execution. If the register is not
+  // modified, returns the address of the indirect CF instruction. The result is
+  // undefined if the provided graph does not fall under either the
+  // FAIL_REGISTER_CLOBBERED or PROTECTED status (see CFIProtectionStatus).
+  uint64_t indirectCFOperandClobber(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 CFIProtectionStatus::PROTECTED:
     return "PROTECTED";
   case CFIProtectionStatus::FAIL_NOT_INDIRECT_CF:
     return "FAIL_NOT_INDIRECT_CF";
   case CFIProtectionStatus::FAIL_ORPHANS:
     return "FAIL_ORPHANS";
   case CFIProtectionStatus::FAIL_BAD_CONDITIONAL_BRANCH:
     return "FAIL_BAD_CONDITIONAL_BRANCH";
+  case CFIProtectionStatus::FAIL_REGISTER_CLOBBERED:
+    return "FAIL_REGISTER_CLOBBERED";
   case CFIProtectionStatus::FAIL_INVALID_INSTRUCTION:
     return "FAIL_INVALID_INSTRUCTION";
   }
   llvm_unreachable("Attempted to stringify an unknown enum value.");
 }
 
 Expected<FileAnalysis> FileAnalysis::Create(StringRef Filename) {
   // Open the filename provided.
FileAnalysis::validateCFIProtection(const GraphResult &Graph) const {
   if (!Graph.OrphanedNodes.empty())
     return CFIProtectionStatus::FAIL_ORPHANS;
 
   for (const auto &BranchNode : Graph.ConditionalBranchNodes) {
     if (!BranchNode.CFIProtection)
       return CFIProtectionStatus::FAIL_BAD_CONDITIONAL_BRANCH;
   }
 
+  if (indirectCFOperandClobber(Graph) != Graph.BaseAddress)
+    return CFIProtectionStatus::FAIL_REGISTER_CLOBBERED;
+
   return CFIProtectionStatus::PROTECTED;
 }
 
+uint64_t FileAnalysis::indirectCFOperandClobber(const GraphResult &Graph) const {
+  assert(Graph.OrphanedNodes.empty() && "Orphaned nodes should be empty.");
+
+  // Get the set of registers we must check to ensure they're not clobbered.
+  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 clobbering 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.hasDefOfPhysReg(NodeInstr.Instruction, RegNum,
+                                      *RegisterInfo))
+          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;
+    BranchNode.IndirectCFIsOnTargetPath = (BranchTarget == Address);
 
     if (BranchTarget == Address)
       BranchNode.Target = Address;
     else
       BranchNode.Fallthrough = Address;
 
     HasValidCrossRef = true;
     buildFlowsToUndefined(Analysis, Result, BranchNode, ParentMeta);
     Result.ConditionalBranchNodes.push_back(BranchNode);
   }

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

EXPECT_EQ(CFIProtectionStatus::PROTECTED,
             Analysis.validateCFIProtection(Result));
   SearchLengthForUndef = 3;
   Result = GraphBuilder::buildFlowGraph(Analysis, 0x775a68);
   EXPECT_EQ(CFIProtectionStatus::PROTECTED,
             Analysis.validateCFIProtection(Result));
   SearchLengthForUndef = PrevSearchLengthForUndef;
 }
 
+TEST_F(BasicFileAnalysisTest, CFIProtectionClobberSinglePathExplicit) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02,                         // 0: jne 4 [+2]
+          0x0f, 0x0b,                         // 2: ud2
+          0x48, 0x05, 0x00, 0x00, 0x00, 0x00, // 4: add $0x0, %eax
+          0xff, 0x10,                         // 10: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 10);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_REGISTER_CLOBBERED,
+            Analysis.validateCFIProtection(Result));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionClobberSinglePathExplicit2) {
+  if (!SuccessfullyInitialised)
+    return;
+  Analysis.parseSectionContents(
+      {
+          0x75, 0x02,             // 0: jne 4 [+2]
+          0x0f, 0x0b,             // 2: ud2
+          0x48, 0x83, 0xc0, 0x00, // 4: add $0x0, %eax
+          0xff, 0x10,             // 8: callq *(%rax)
+      },
+      0xDEADBEEF);
+  GraphResult Result = GraphBuilder::buildFlowGraph(Analysis, 0xDEADBEEF + 8);
+  EXPECT_EQ(CFIProtectionStatus::FAIL_REGISTER_CLOBBERED,
+            Analysis.validateCFIProtection(Result));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionClobberSinglePathImplicit) {
+  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(CFIProtectionStatus::FAIL_REGISTER_CLOBBERED,
+            Analysis.validateCFIProtection(Result));
+}
+
+TEST_F(BasicFileAnalysisTest, CFIProtectionClobberDualPathImplicit) {
+  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(CFIProtectionStatus::FAIL_REGISTER_CLOBBERED,
+            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();
 }