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

   1 //===- GraphBuilder.cpp -----------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "GraphBuilder.h"
  10
  11 #include "llvm/BinaryFormat/ELF.h"
  12 #include "llvm/MC/MCAsmInfo.h"
  13 #include "llvm/MC/MCContext.h"
  14 #include "llvm/MC/MCDisassembler/MCDisassembler.h"
  15 #include "llvm/MC/MCInst.h"
  16 #include "llvm/MC/MCInstPrinter.h"
  17 #include "llvm/MC/MCInstrAnalysis.h"
  18 #include "llvm/MC/MCInstrDesc.h"
  19 #include "llvm/MC/MCInstrInfo.h"
  20 #include "llvm/MC/MCObjectFileInfo.h"
  21 #include "llvm/MC/MCRegisterInfo.h"
  22 #include "llvm/MC/MCSubtargetInfo.h"
  23 #include "llvm/MC/TargetRegistry.h"
  24 #include "llvm/Object/Binary.h"
  25 #include "llvm/Object/COFF.h"
  26 #include "llvm/Object/ELFObjectFile.h"
  27 #include "llvm/Object/ObjectFile.h"
  28 #include "llvm/Support/Casting.h"
  29 #include "llvm/Support/CommandLine.h"
  30 #include "llvm/Support/Error.h"
  31 #include "llvm/Support/MemoryBuffer.h"
  32 #include "llvm/Support/TargetSelect.h"
  33 #include "llvm/Support/raw_ostream.h"
  34
  35 using Instr = llvm::cfi_verify::FileAnalysis::Instr;
  36
  37 namespace llvm {
  38 namespace cfi_verify {
  39
  40 uint64_t SearchLengthForUndef;
  41 uint64_t SearchLengthForConditionalBranch;
  42
  43 static cl::opt<uint64_t, true> SearchLengthForUndefArg(
  44     "search-length-undef",
  45     cl::desc("Specify the maximum amount of instructions "
  46              "to inspect when searching for an undefined "
  47              "instruction from a conditional branch."),
  48     cl::location(SearchLengthForUndef), cl::init(2));
  49
  50 static cl::opt<uint64_t, true> SearchLengthForConditionalBranchArg(
  51     "search-length-cb",
  52     cl::desc("Specify the maximum amount of instructions "
  53              "to inspect when searching for a conditional "
  54              "branch from an indirect control flow."),
  55     cl::location(SearchLengthForConditionalBranch), cl::init(20));
  56
  57 std::vector<uint64_t> GraphResult::flattenAddress(uint64_t Address) const {
  58   std::vector<uint64_t> Addresses;
  59
  60   auto It = IntermediateNodes.find(Address);
  61   Addresses.push_back(Address);
  62
  63   while (It != IntermediateNodes.end()) {
  64     Addresses.push_back(It->second);
  65     It = IntermediateNodes.find(It->second);
  66   }
  67   return Addresses;
  68 }
  69
  70 void printPairToDOT(const FileAnalysis &Analysis, raw_ostream &OS,
  71                           uint64_t From, uint64_t To) {
  72   OS << "  \"" << format_hex(From, 2) << ": ";
  73   Analysis.printInstruction(Analysis.getInstructionOrDie(From), OS);
  74   OS << "\" -> \"" << format_hex(To, 2) << ": ";
  75   Analysis.printInstruction(Analysis.getInstructionOrDie(To), OS);
  76   OS << "\"\n";
  77 }
  78
  79 void GraphResult::printToDOT(const FileAnalysis &Analysis,
  80                              raw_ostream &OS) const {
  81   std::map<uint64_t, uint64_t> SortedIntermediateNodes(
  82       IntermediateNodes.begin(), IntermediateNodes.end());
  83   OS << "digraph graph_" << format_hex(BaseAddress, 2) << " {\n";
  84   for (const auto &KV : SortedIntermediateNodes)
  85     printPairToDOT(Analysis, OS, KV.first, KV.second);
  86
  87   for (auto &BranchNode : ConditionalBranchNodes) {
  88     for (auto &V : {BranchNode.Target, BranchNode.Fallthrough})
  89       printPairToDOT(Analysis, OS, BranchNode.Address, V);
  90   }
  91   OS << "}\n";
  92 }
  93
  94 GraphResult GraphBuilder::buildFlowGraph(const FileAnalysis &Analysis,
  95                                          object::SectionedAddress Address) {
  96   GraphResult Result;
  97   Result.BaseAddress = Address.Address;
  98   DenseSet<uint64_t> OpenedNodes;
  99
 100   const auto &IndirectInstructions = Analysis.getIndirectInstructions();
 101
 102   // check that IndirectInstructions contains specified Address
 103   if (IndirectInstructions.find(Address) == IndirectInstructions.end()) {
 104     return Result;
 105   }
 106
 107   buildFlowGraphImpl(Analysis, OpenedNodes, Result, Address.Address, 0);
 108   return Result;
 109 }
 110
 111 void GraphBuilder::buildFlowsToUndefined(const FileAnalysis &Analysis,
 112                                          GraphResult &Result,
 113                                          ConditionalBranchNode &BranchNode,
 114                                          const Instr &BranchInstrMeta) {
 115   assert(SearchLengthForUndef > 0 &&
 116          "Search length for undefined flow must be greater than zero.");
 117
 118   // Start setting up the next node in the block.
 119   uint64_t NextAddress = 0;
 120   const Instr *NextMetaPtr;
 121
 122   // Find out the next instruction in the block and add it to the new
 123   // node.
 124   if (BranchNode.Target && !BranchNode.Fallthrough) {
 125     // We know the target of the branch, find the fallthrough.
 126     NextMetaPtr = Analysis.getNextInstructionSequential(BranchInstrMeta);
 127     if (!NextMetaPtr) {
 128       errs() << "Failed to get next instruction from "
 129              << format_hex(BranchNode.Address, 2) << ".\n";
 130       return;
 131     }
 132
 133     NextAddress = NextMetaPtr->VMAddress;
 134     BranchNode.Fallthrough =
 135         NextMetaPtr->VMAddress; // Add the new node to the branch head.
 136   } else if (BranchNode.Fallthrough && !BranchNode.Target) {
 137     // We already know the fallthrough, evaluate the target.
 138     uint64_t Target;
 139     if (!Analysis.getMCInstrAnalysis()->evaluateBranch(
 140             BranchInstrMeta.Instruction, BranchInstrMeta.VMAddress,
 141             BranchInstrMeta.InstructionSize, Target)) {
 142       errs() << "Failed to get branch target for conditional branch at address "
 143              << format_hex(BranchInstrMeta.VMAddress, 2) << ".\n";
 144       return;
 145     }
 146
 147     // Resolve the meta pointer for the target of this branch.
 148     NextMetaPtr = Analysis.getInstruction(Target);
 149     if (!NextMetaPtr) {
 150       errs() << "Failed to find instruction at address "
 151              << format_hex(Target, 2) << ".\n";
 152       return;
 153     }
 154
 155     NextAddress = Target;
 156     BranchNode.Target =
 157         NextMetaPtr->VMAddress; // Add the new node to the branch head.
 158   } else {
 159     errs() << "ControlBranchNode supplied to buildFlowsToUndefined should "
 160               "provide Target xor Fallthrough.\n";
 161     return;
 162   }
 163
 164   uint64_t CurrentAddress = NextAddress;
 165   const Instr *CurrentMetaPtr = NextMetaPtr;
 166
 167   // Now the branch head has been set properly, complete the rest of the block.
 168   for (uint64_t i = 1; i < SearchLengthForUndef; ++i) {
 169     // Check to see whether the block should die.
 170     if (Analysis.isCFITrap(*CurrentMetaPtr)) {
 171       BranchNode.CFIProtection = true;
 172       return;
 173     }
 174
 175     // Find the metadata of the next instruction.
 176     NextMetaPtr = Analysis.getDefiniteNextInstruction(*CurrentMetaPtr);
 177     if (!NextMetaPtr)
 178       return;
 179
 180     // Setup the next node.
 181     NextAddress = NextMetaPtr->VMAddress;
 182
 183     // Add this as an intermediate.
 184     Result.IntermediateNodes[CurrentAddress] = NextAddress;
 185
 186     // Move the 'current' pointers to the new tail of the block.
 187     CurrentMetaPtr = NextMetaPtr;
 188     CurrentAddress = NextAddress;
 189   }
 190
 191   // Final check of the last thing we added to the block.
 192   if (Analysis.isCFITrap(*CurrentMetaPtr))
 193     BranchNode.CFIProtection = true;
 194 }
 195
 196 void GraphBuilder::buildFlowGraphImpl(const FileAnalysis &Analysis,
 197                                       DenseSet<uint64_t> &OpenedNodes,
 198                                       GraphResult &Result, uint64_t Address,
 199                                       uint64_t Depth) {
 200   // If we've exceeded the flow length, terminate.
 201   if (Depth >= SearchLengthForConditionalBranch) {
 202     Result.OrphanedNodes.push_back(Address);
 203     return;
 204   }
 205
 206   // Ensure this flow is acyclic.
 207   if (OpenedNodes.count(Address))
 208     Result.OrphanedNodes.push_back(Address);
 209
 210   // If this flow is already explored, stop here.
 211   if (Result.IntermediateNodes.count(Address))
 212     return;
 213
 214   // Get the metadata for the node instruction.
 215   const auto &InstrMetaPtr = Analysis.getInstruction(Address);
 216   if (!InstrMetaPtr) {
 217     errs() << "Failed to build flow graph for instruction at address "
 218            << format_hex(Address, 2) << ".\n";
 219     Result.OrphanedNodes.push_back(Address);
 220     return;
 221   }
 222   const auto &ChildMeta = *InstrMetaPtr;
 223
 224   OpenedNodes.insert(Address);
 225   std::set<const Instr *> CFCrossRefs =
 226       Analysis.getDirectControlFlowXRefs(ChildMeta);
 227
 228   bool HasValidCrossRef = false;
 229
 230   for (const auto *ParentMetaPtr : CFCrossRefs) {
 231     assert(ParentMetaPtr && "CFCrossRefs returned nullptr.");
 232     const auto &ParentMeta = *ParentMetaPtr;
 233     const auto &ParentDesc =
 234         Analysis.getMCInstrInfo()->get(ParentMeta.Instruction.getOpcode());
 235
 236     if (!ParentDesc.mayAffectControlFlow(ParentMeta.Instruction,
 237                                          *Analysis.getRegisterInfo())) {
 238       // If this cross reference doesn't affect CF, continue the graph.
 239       buildFlowGraphImpl(Analysis, OpenedNodes, Result, ParentMeta.VMAddress,
 240                          Depth + 1);
 241       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
 242       HasValidCrossRef = true;
 243       continue;
 244     }
 245
 246     // Call instructions are not valid in the upwards traversal.
 247     if (ParentDesc.isCall()) {
 248       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
 249       Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
 250       continue;
 251     }
 252
 253     // Evaluate the branch target to ascertain whether this XRef is the result
 254     // of a fallthrough or the target of a branch.
 255     uint64_t BranchTarget;
 256     if (!Analysis.getMCInstrAnalysis()->evaluateBranch(
 257             ParentMeta.Instruction, ParentMeta.VMAddress,
 258             ParentMeta.InstructionSize, BranchTarget)) {
 259       errs() << "Failed to evaluate branch target for instruction at address "
 260              << format_hex(ParentMeta.VMAddress, 2) << ".\n";
 261       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
 262       Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
 263       continue;
 264     }
 265
 266     // Allow unconditional branches to be part of the upwards traversal.
 267     if (ParentDesc.isUnconditionalBranch()) {
 268       // Ensures that the unconditional branch is actually an XRef to the child.
 269       if (BranchTarget != Address) {
 270         errs() << "Control flow to " << format_hex(Address, 2)
 271                << ", but target resolution of "
 272                << format_hex(ParentMeta.VMAddress, 2)
 273                << " is not this address?\n";
 274         Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
 275         Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
 276         continue;
 277       }
 278
 279       buildFlowGraphImpl(Analysis, OpenedNodes, Result, ParentMeta.VMAddress,
 280                          Depth + 1);
 281       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
 282       HasValidCrossRef = true;
 283       continue;
 284     }
 285
 286     // Ensure that any unknown CFs are caught.
 287     if (!ParentDesc.isConditionalBranch()) {
 288       errs() << "Unknown control flow encountered when building graph at "
 289              << format_hex(Address, 2) << "\n.";
 290       Result.IntermediateNodes[ParentMeta.VMAddress] = Address;
 291       Result.OrphanedNodes.push_back(ParentMeta.VMAddress);
 292       continue;
 293     }
 294
 295     // Only direct conditional branches should be present at this point. Setup
 296     // a conditional branch node and build flows to the ud2.
 297     ConditionalBranchNode BranchNode;
 298     BranchNode.Address = ParentMeta.VMAddress;
 299     BranchNode.Target = 0;
 300     BranchNode.Fallthrough = 0;
 301     BranchNode.CFIProtection = false;
 302     BranchNode.IndirectCFIsOnTargetPath = (BranchTarget == Address);
 303
 304     if (BranchTarget == Address)
 305       BranchNode.Target = Address;
 306     else
 307       BranchNode.Fallthrough = Address;
 308
 309     HasValidCrossRef = true;
 310     buildFlowsToUndefined(Analysis, Result, BranchNode, ParentMeta);
 311     Result.ConditionalBranchNodes.push_back(BranchNode);
 312   }
 313
 314   // When using cross-DSO, some indirect calls are not guarded by a branch to a
 315   // trap but instead follow a call to __cfi_slowpath.  For example:
 316   // if (!InlinedFastCheck(f))
 317   //    call *f
 318   //  else {
 319   //    __cfi_slowpath(CallSiteTypeId, f);
 320   //    call *f
 321   //  }
 322   // To mark the second call as protected, we recognize indirect calls that
 323   // directly follow calls to functions that will trap on CFI violations.
 324   if (CFCrossRefs.empty()) {
 325     const Instr *PrevInstr = Analysis.getPrevInstructionSequential(ChildMeta);
 326     if (PrevInstr && Analysis.willTrapOnCFIViolation(*PrevInstr)) {
 327       Result.IntermediateNodes[PrevInstr->VMAddress] = Address;
 328       HasValidCrossRef = true;
 329     }
 330   }
 331
 332   if (!HasValidCrossRef)
 333     Result.OrphanedNodes.push_back(Address);
 334
 335   OpenedNodes.erase(Address);
 336 }
 337
 338 } // namespace cfi_verify
 339 } // namespace llvm