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