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