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